8-Puzzle-Solver — A* mit Manhattan-Distanz auf einer Seite

Das 8-Puzzle ist das, was Sie zuerst schreiben, am Tag, an dem Sie über heuristische Suche lernen. Es ist klein genug, dass fast jeder Ansatz funktioniert, groß genug, dass schlechte Ansätze sichtbar schlechter sind als gute. Dieser Artikel geht die Standardlösung von oben nach unten durch.

Der Zustand

Stellen Sie das Brett als Array von neun Ganzzahlen dar, indiziert 0..8 in Zeilen-Major-Reihenfolge:

Positionen:   Indizes:
 1 2 3        0 1 2
 4 5 6   ↔    3 4 5
 7 8 _        6 7 8

Die leere Zelle ist ein Sentinel-Wert — meist 0. Der Zielzustand ist [1, 2, 3, 4, 5, 6, 7, 8, 0].

Die Züge

Aus einer Position mit der Lücke an Index e können Sie die Lücke mit ihren orthogonalen Nachbarn tauschen: e-3 (oben), wenn nicht in der obersten Zeile; e+3 (unten), wenn nicht in der untersten; e-1 (links), wenn nicht in der linken Spalte; e+1 (rechts), wenn nicht in der rechten.

Eine Funktion neighbors(state) gibt die bis zu vier in einem Zug erreichbaren Zustände zurück.

Die Heuristik: Manhattan-Distanz

Für jedes Plättchen (die Lücke ignorierend) Zeilen- plus Spaltendistanz von aktueller zu Zielposition berechnen. Über alle Plättchen summieren. Die Summe ist eine Untergrenze für die verbleibenden Züge — jedes Plättchen muss mindestens so weit reisen.

In Pseudocode:

h(state) = sum über Plättchen t:
  abs(row(current) - row(goal)) + abs(col(current) - col(goal))

Manhattan-Distanz ist zulässig (überschätzt nie) und konsistent (erfüllt die Dreiecksungleichung). Beide Eigenschaften sind für A* wichtig.

A* in zwölf Zeilen

A* hält eine Prioritäts-Warteschlange von Zuständen, geordnet nach f = g + h, wobei g die Tiefe (bisherige Züge) ist und h die heuristische Schätzung der verbleibenden Züge. In jeder Iteration: niedrigsten f-Zustand ziehen, expandieren, Nachbarn mit aktualisiertem f einreihen.

open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}

while open is not empty:
  state = open.pop()
  if state == goal: return reconstruct_path(came_from, state)
  for n in neighbors(state):
    tentative_g = g[state] + 1
    if n not in g or tentative_g < g[n]:
      g[n] = tentative_g
      came_from[n] = state
      open.push(n, f=tentative_g + h(n))

Das ist der ganze Solver. Implementieren Sie h, implementieren Sie neighbors, und Sie können jedes 8-Puzzle lösen.

Leistung

A* mit Manhattan-Distanz löst jedes 8-Puzzle in ein paar hundert Mikrosekunden und expandiert dabei ein paar hundert bis ein paar tausend Zustände bei den schwersten Instanzen. Der Zustandsraum ist klein genug, dass A* auf dieser Größe IDA* dominiert — A* ist die richtige Wahl für 3×3, IDA* übernimmt bei 4×4 und größer.

Typische Fallstricke

Drei Dinge, die Sie beim ersten Versuch falsch machen werden:

Zustands-Hashing. Pythons Tupel hashen schön; Javas Int-Arrays nicht. Welche Sprache auch immer, der Zustand muss hashbar sein, damit Closed/Open-Mengen funktionieren. Ein verbreiteter Trick ist, den 9-Plättchen-Zustand als eine einzelne 32-Bit-Ganzzahl zu kodieren (4 Bit pro Zelle, da Zellen 0..8 sind).

Die Inversions-Paritätsprüfung vergessen. Wenn Sie ein zufälliges 8-Puzzle durch Mischen erzeugen, ist es in der Hälfte der Fälle unlösbar, und A* erkundet den gesamten 181.440-Zustands-Halbraum auf der Suche nach einem nicht existierenden Pfad. Fügen Sie vor dem A*-Lauf eine schnelle Paritätsprüfung ein, oder erzeugen Sie durch Rückwärtslaufen vom Ziel.

Die Lücke als Plättchen in der Heuristik behandeln. Manhattan-Distanz wird nur über die echten Plättchen summiert. Die Lücke einzubeziehen, bläst die Heuristik auf und bricht die Zulässigkeit (man kann die Lücke „kostenlos“ mit einem Zug „richten“).

Jenseits von Manhattan

Sie können auf dem 8-Puzzle besser als Manhattan, aber nicht viel:

• Linear Conflict — sind zwei Plättchen in derselben Zeile beide in ihrer Zielzeile, aber falsch sortiert, brauchen sie mindestens zwei Extrazüge, um aneinander vorbei zu kommen. Pro Konflikt 2 addieren. Verbessert Manhattan um 5–15 %.
• Mustertabellen — optimale Kosten über Plättchen-Teilmengen vorberechnen. Riesiger Speicheraufwand für winzigen Geschwindigkeitsgewinn beim 8-Puzzle. Lohnt sich für 15-Puzzle-Solver, nicht hier.

Für 8-Puzzles ist Manhattan plus Linear Conflict der praktische Sweetspot.

Was als Nächstes bauen

Wenn Sie einen 8-Puzzle-Solver geschrieben haben, sind die natürlichen Erweiterungen:

1. 15-Puzzle-Solver mit IDA* + Walking Distance. Dieselben Grundideen, tiefere Suche. (Anleitung hier.)
2. Allgemeiner N-Puzzle-Solver mit Mustertabellen. Ein Wochenend-Projekt.
3. Lösbarkeitstest — eine 30-Zeilen-Funktion, die true zurückgibt, wenn ein Brett vom Ziel aus erreichbar ist. Nützlich für App-Entwicklung. (Basierend auf dem Paritätstheorem.)

Das 8-Puzzle ist klein. Die Techniken, die Sie damit lernen, skalieren bis ganz nach oben.