Fifteen (Fünfzehn)

Die Fünfzehn (15-Puzzle), auch Gem Puzzle, Boss Puzzle, Spiel der Fünfzehn, Mystic-Platz und viele andere genannt - ist ein Schiebepuzzle , die mit einem Stein fehlt eines Rahmens von nummerierten quadratischen Fliesen in zufälliger Reihenfolge besteht. Das Rätsel, wenn 4 × 4-Kacheln wird das Puzzle mit 15-Puzzle oder 16-Puzzle genannt, jeweils für die Anzahl der Kacheln und der Anzahl der Räume genannt.
Das Ziel des Puzzles ist, die Fliesen zu legen, um (von 1 bis 15) durch gleitende Bewegungen, die den leeren Raum nutzen. Die Fünfzehn ist ein klassisches Problem für die Modellierung von Algorithmen Einbeziehung Heuristiken. Häufig verwendete Heuristik für dieses Problem sind zwischen jedem Block und seine Position in der Zielkonfiguration die Anzahl der fehl am Platz Fliesen und der Suche nach der Summe der taxicab Entfernungen zu zählen. Beachten Sie, dass beide sind zulässig, das heißt, sie nie die Anzahl der Züge links überschätzen , die Optimalität für bestimmte Suchalgorithmen gewährleistet .