8 Puzzle
Beim 8 Puzzle geht es darum, 8 verschiebbare Plättchen in einem 3 x 3 Raster von einer Ausgangskonfiguration in eine Zielkonfiguration zu bewegen. Die Plättchen sind mit den Ziffern 1 bis 8 beschriftet. Die Zielkonfiguration ist
1 2 3
4 5 6
7 8
mit einer Leerstelle in der unteren rechten Ecke.
Eine Lösung ausgehend von der Ausgangskonfiguration
8 7 6
5 4 3
2 1
hat 31 Schritte (nil steht hier für die Leerstelle):
((8 7 6 5 4 3 2 1 nil)
(8 7 6 5 4 3 2 nil 1)
(8 7 6 5 4 3 nil 2 1)
(8 7 6 nil 4 3 5 2 1)
(nil 7 6 8 4 3 5 2 1)
(7 nil 6 8 4 3 5 2 1)
(7 4 6 8 nil 3 5 2 1)
(7 4 6 nil 8 3 5 2 1)
(7 4 6 5 8 3 nil 2 1)
(7 4 6 5 8 3 2 nil 1)
(7 4 6 5 nil 3 2 8 1)
(7 4 6 5 3 nil 2 8 1)
(7 4 6 5 3 1 2 8 nil)
(7 4 6 5 3 1 2 nil 8)
(7 4 6 5 3 1 nil 2 8)
(7 4 6 nil 3 1 5 2 8)
(nil 4 6 7 3 1 5 2 8)
(4 nil 6 7 3 1 5 2 8)
(4 3 6 7 nil 1 5 2 8)
(4 3 6 7 1 nil 5 2 8)
(4 3 nil 7 1 6 5 2 8)
(4 nil 3 7 1 6 5 2 8)
(4 1 3 7 nil 6 5 2 8)
(4 1 3 7 2 6 5 nil 8)
(4 1 3 7 2 6 nil 5 8)
(4 1 3 nil 2 6 7 5 8)
(nil 1 3 4 2 6 7 5 8)
(1 nil 3 4 2 6 7 5 8)
(1 2 3 4 nil 6 7 5 8)
(1 2 3 4 5 6 7 nil 8)
(1 2 3 4 5 6 7 8 nil))
Das 8 Puzzle wird hier mit der A* Suche gelöst. Deshalb wird die Klasse puzzle8 von der Kasse a*-search abgeleitet.
(defclass puzzle8 (a*-search))
Der Konstruktor ist anwendbar, wenn die angegebene Ausgangskonfiguration syntaktisch korrekt ist.
(defmethod initialize ((this puzzle8) start-state)
(and
(list? start-state)
(subset? (quote (1 2 3 4 5 6 7 8 nil)) start-state)
(= (length start-state) 9))
(progn
(.= this start-state start-state)
(.= this dimension 3)
(.= this goal (quote (1 2 3 4 5 6 7 8 nil)))
(.= this tile-indices (quote (0 1 2 3 4 5 6 7 8)))
(freeze this)
this))
Die A* Suche und ihre Superklassen (siehe Bestensuche und Suche in Graphen) erwarten, dass einige Methoden überschrieben werden.
Die Methode get-start-node liefert die Ausgangskonfiguration des Puzzels.
(defmethod get-start-node ((this puzzle8))
t
(. this start-state))
Die Methode get-next-nodes berechnet ausgehend von einer Konfiguration die möglichen Folgekonfigurationen. Dabei können die Leerstelle und ein an die Leerstelle angrenzendes Plättchen die Plätze tauschen.
(defmethod get-next-nodes ((this puzzle8) state)
t
(let
((coordinates (get-coordinates this state nil)))
(append
(swap-tiles this state coordinates (left this coordinates))
(swap-tiles this state coordinates (right this coordinates))
(swap-tiles this state coordinates (up this coordinates))
(swap-tiles this state coordinates (down this coordinates)))))
Die Methode get-coordinates bestimmt die Koordinaten des angegebenen Plättchens (oder der Lücke) in der angegebenen Konfiguration.
(defmethod get-coordinates ((this puzzle8) state tile)
t
(position tile state))
Die Methoden get-x und get-y liefern den horizontalen und vertikalen Anteil der angegebenen Koordinaten.
(defmethod get-x ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(rem coordinates dimension)))
(defmethod get-y ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(floor (/ coordinates dimension))))
Die Methoden left, right, up und down liefern zu den angegebenen Koordinaten das Feld links, rechts, oberhalb oder unterhalb davon, wenn es nicht außerhalb des Rasters liegt.
(defmethod left ((this puzzle8) coordinates)
t
(when
(> (get-x this coordinates) 0)
(- coordinates 1)))
(defmethod right ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(when
(< (get-x this coordinates) (- dimension 1))
(+ coordinates 1))))
(defmethod up ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(when
(< (get-y this coordinates) (- dimension 1))
(+ coordinates dimension))))
(defmethod down ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(when
(> (get-y this coordinates) 0)
(- coordinates dimension))))
Die Methode swap-tiles vertauscht zwei Plättchen bzw. die Lücke und ein Plättchen.
(defmethod swap-tiles ((this puzzle8) state coordinates-1 coordinates-2)
t
(with-slots-read-only (tile-indices) this
(when
(and coordinates-1 coordinates-2)
(list
(map-with
(lambda (index)
(cond
((= index coordinates-1) (nth state coordinates-2))
((= index coordinates-2) (nth state coordinates-1))
(t (nth state index))))
tile-indices)))))
Die Methode is-goal-node? prüft, ob die Zielkonfiguration erreicht ist.
(defmethod is-goal-node? ((this puzzle8) state)
t
(= state (. this goal)))
Die Methode path-length liefert die Länge eines Pfades bei der Lösung des Puzzles. Das entspricht der Anzahl der Züge, also der Länge der Liste vermindert um Eins.
(defmethod path-length ((this puzzle8) path)
t
(- (length path) 1))
Die Methode estimate-distance-to-goal schätzt ab, wie viele Züge von der übergebenen Konfiguration bis zur Zielkonfiguration noch nötig sind.
(defmethod estimate-distance-to-goal ((this puzzle8) state)
t
(with-slots-read-only (tile-indices) this
(apply +
(map-with
(lambda (index)
(let
((tile (nth state index)))
(if
(null? tile)
0
(manhattan-distance this (- tile 1) index))))
tile-indices))))
Die Methode manhattan-distance gibt die Manhattandistanz zwischen zwei Koordinatenpaaren an.
(defmethod manhattan-distance ((this puzzle8) source destination)
t
(+
(abs (- (get-x this source) (get-x this destination)))
(abs (- (get-y this source) (get-y this destination)))))
Die unten verlinkte Datei 8-puzzle.sheet.xml enthält den Code und kann mit dem Programm Calc angezeigt werden.
1 2 3
4 5 6
7 8
mit einer Leerstelle in der unteren rechten Ecke.
Eine Lösung ausgehend von der Ausgangskonfiguration
8 7 6
5 4 3
2 1
hat 31 Schritte (nil steht hier für die Leerstelle):
((8 7 6 5 4 3 2 1 nil)
(8 7 6 5 4 3 2 nil 1)
(8 7 6 5 4 3 nil 2 1)
(8 7 6 nil 4 3 5 2 1)
(nil 7 6 8 4 3 5 2 1)
(7 nil 6 8 4 3 5 2 1)
(7 4 6 8 nil 3 5 2 1)
(7 4 6 nil 8 3 5 2 1)
(7 4 6 5 8 3 nil 2 1)
(7 4 6 5 8 3 2 nil 1)
(7 4 6 5 nil 3 2 8 1)
(7 4 6 5 3 nil 2 8 1)
(7 4 6 5 3 1 2 8 nil)
(7 4 6 5 3 1 2 nil 8)
(7 4 6 5 3 1 nil 2 8)
(7 4 6 nil 3 1 5 2 8)
(nil 4 6 7 3 1 5 2 8)
(4 nil 6 7 3 1 5 2 8)
(4 3 6 7 nil 1 5 2 8)
(4 3 6 7 1 nil 5 2 8)
(4 3 nil 7 1 6 5 2 8)
(4 nil 3 7 1 6 5 2 8)
(4 1 3 7 nil 6 5 2 8)
(4 1 3 7 2 6 5 nil 8)
(4 1 3 7 2 6 nil 5 8)
(4 1 3 nil 2 6 7 5 8)
(nil 1 3 4 2 6 7 5 8)
(1 nil 3 4 2 6 7 5 8)
(1 2 3 4 nil 6 7 5 8)
(1 2 3 4 5 6 7 nil 8)
(1 2 3 4 5 6 7 8 nil))
Das 8 Puzzle wird hier mit der A* Suche gelöst. Deshalb wird die Klasse puzzle8 von der Kasse a*-search abgeleitet.
(defclass puzzle8 (a*-search))
Der Konstruktor ist anwendbar, wenn die angegebene Ausgangskonfiguration syntaktisch korrekt ist.
(defmethod initialize ((this puzzle8) start-state)
(and
(list? start-state)
(subset? (quote (1 2 3 4 5 6 7 8 nil)) start-state)
(= (length start-state) 9))
(progn
(.= this start-state start-state)
(.= this dimension 3)
(.= this goal (quote (1 2 3 4 5 6 7 8 nil)))
(.= this tile-indices (quote (0 1 2 3 4 5 6 7 8)))
(freeze this)
this))
Die A* Suche und ihre Superklassen (siehe Bestensuche und Suche in Graphen) erwarten, dass einige Methoden überschrieben werden.
Die Methode get-start-node liefert die Ausgangskonfiguration des Puzzels.
(defmethod get-start-node ((this puzzle8))
t
(. this start-state))
Die Methode get-next-nodes berechnet ausgehend von einer Konfiguration die möglichen Folgekonfigurationen. Dabei können die Leerstelle und ein an die Leerstelle angrenzendes Plättchen die Plätze tauschen.
(defmethod get-next-nodes ((this puzzle8) state)
t
(let
((coordinates (get-coordinates this state nil)))
(append
(swap-tiles this state coordinates (left this coordinates))
(swap-tiles this state coordinates (right this coordinates))
(swap-tiles this state coordinates (up this coordinates))
(swap-tiles this state coordinates (down this coordinates)))))
Die Methode get-coordinates bestimmt die Koordinaten des angegebenen Plättchens (oder der Lücke) in der angegebenen Konfiguration.
(defmethod get-coordinates ((this puzzle8) state tile)
t
(position tile state))
Die Methoden get-x und get-y liefern den horizontalen und vertikalen Anteil der angegebenen Koordinaten.
(defmethod get-x ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(rem coordinates dimension)))
(defmethod get-y ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(floor (/ coordinates dimension))))
Die Methoden left, right, up und down liefern zu den angegebenen Koordinaten das Feld links, rechts, oberhalb oder unterhalb davon, wenn es nicht außerhalb des Rasters liegt.
(defmethod left ((this puzzle8) coordinates)
t
(when
(> (get-x this coordinates) 0)
(- coordinates 1)))
(defmethod right ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(when
(< (get-x this coordinates) (- dimension 1))
(+ coordinates 1))))
(defmethod up ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(when
(< (get-y this coordinates) (- dimension 1))
(+ coordinates dimension))))
(defmethod down ((this puzzle8) coordinates)
t
(with-slots-read-only (dimension) this
(when
(> (get-y this coordinates) 0)
(- coordinates dimension))))
Die Methode swap-tiles vertauscht zwei Plättchen bzw. die Lücke und ein Plättchen.
(defmethod swap-tiles ((this puzzle8) state coordinates-1 coordinates-2)
t
(with-slots-read-only (tile-indices) this
(when
(and coordinates-1 coordinates-2)
(list
(map-with
(lambda (index)
(cond
((= index coordinates-1) (nth state coordinates-2))
((= index coordinates-2) (nth state coordinates-1))
(t (nth state index))))
tile-indices)))))
Die Methode is-goal-node? prüft, ob die Zielkonfiguration erreicht ist.
(defmethod is-goal-node? ((this puzzle8) state)
t
(= state (. this goal)))
Die Methode path-length liefert die Länge eines Pfades bei der Lösung des Puzzles. Das entspricht der Anzahl der Züge, also der Länge der Liste vermindert um Eins.
(defmethod path-length ((this puzzle8) path)
t
(- (length path) 1))
Die Methode estimate-distance-to-goal schätzt ab, wie viele Züge von der übergebenen Konfiguration bis zur Zielkonfiguration noch nötig sind.
(defmethod estimate-distance-to-goal ((this puzzle8) state)
t
(with-slots-read-only (tile-indices) this
(apply +
(map-with
(lambda (index)
(let
((tile (nth state index)))
(if
(null? tile)
0
(manhattan-distance this (- tile 1) index))))
tile-indices))))
Die Methode manhattan-distance gibt die Manhattandistanz zwischen zwei Koordinatenpaaren an.
(defmethod manhattan-distance ((this puzzle8) source destination)
t
(+
(abs (- (get-x this source) (get-x this destination)))
(abs (- (get-y this source) (get-y this destination)))))
Die unten verlinkte Datei 8-puzzle.sheet.xml enthält den Code und kann mit dem Programm Calc angezeigt werden.