Bei dem 14/15-Puzzle handelt es sich um eine Schöpfung des amerikanischen Rätselspezialisten Sam Loyd .

In einem quadratischen Rahmen der Größe 4×4 liegen 15 Steine, die von 1 bis 15 durchnummeriert sind. In der Ausgangsposition sind die Steine mit Ausnahme der Steine 14 und 15 in aufsteigender Reihenfolge sortiert, das letzte Feld bleibt frei. Dadurch ergibt sich folgendes Bild:

.

Die Aufgabe besteht nun darin, die Steine durch eine Folge von Zügen in die richtige Reihenfolge zu bringen:

.

Erlaubt sind nur solche Züge, bei denen ein Stein, der horizontal oder vertikal direkt neben dem freien Feld liegt, auf dieses verschoben wird. Sam Loyd setzte ein Preisgeld von 1000 Dollar für die erste richtige Lösung aus, wohl wissend, dass das Problem unlösbar ist. Der Beweis basiert auf der Tatsache, dass bei erlaubten Zügen die Parität von N = N₁ + N₂ erhalten bleibt (das heißt, wenn N vor dem Zug (un)gerade war, ist es das auch nach dem Zug). Dabei ist N₁ die Anzahl der Zahlenpaare, die sich in falscher Reihenfolge befinden und N₂ die Nummer der Reihe, in der sich das leere Feld befindet.

Weblinks

Sam Loyd's Fifteen Englischsprachige Seite mit Java-Applet und Beweis der Unlösbarkeit des Problems.