This 8 Puzzle visualization shows an implementation of a DFS algorithm, a greedy algorithm and an A* algorithm.
Explanations
In the N-puzzle you have an M by M board (where M = sqrt(N)) filled with tiles numbered 1 through N. Therefore there is always one empty tile. For instance - in the 8 puzzle, there is a 3 by 3 board with tiles numbered 1 through 8. The tiles start out in some initial placement, and the goal is to bring them to a placement in which the tiles are ordered according to the numbers that appear on them, and the empty tile is the bottom right-hand corner. In each turn only one tile can be moved. This tile must be one of the tiles adjacent to the empty spot, and moving a tile simply moves it into the empty spot.
Note: While the algorithms are searching for a valid sequence of moves, they do not necessarily perform only valid moves. For instance - several algorithms treat the positioning of the tiles on the board as a node in a search tree. Going between nodes in the search tree is allowed even though there is no single valid move which will bring the board between the two nodes. This is fine as long as when the algorithm finds a path from the initial state to the goal state and the path itself consists solely of valid moves.
For the sake of visualizing the search process, when an algorithm is processing a certain node, it may appear that an invalid move has been performed (moving more than one tile or moving tiles diagonally). This can happen only in the search phase and is done solely for the sake of visualizing the search process.
The search algorithms implemented here are:
- DFS: The algorithm searches through all the possible movements, making sure the same state is never repeated. When it reaches a "dead end" (a state from which all movements lead to states that have already been explored), it backtracks to the previous state. This algorithm can run very slowly, because there are (N+1)! different states, and the DFS iterates over them randomly. For instance - for the 8-puzzle there are 9! = 362,880 possible states.
- Best-First Search: The algorithm doesn't appear in the list, but it serves as a basis for other algorithms and therefore deserves some explanation. The Best-First Search algorithm treats each positioning of tiles on the board as a state. Each state is given a score which may differ between the different implementations of this algorithm. The algorithm keeps two lists of states: a list of states for which all children have been searched (the closed list) and a list of states which should still be checked (the open list). The open list is a prioritized queue according to the state score. A state's children are any other states reachable by a valid move from the state. The algorithm begins with the initial board state in the open list. During each search iteration it takes the first state out of the open list and processes its children. Each child's score is calculated. If the child exists with a better score in either list, it is skipped. Otherwise the child is added to the open list (in case the child already exists in the open list, its existing copy is first removed from the open list). The algorithm continues processing until either the open list is empty (in which case all of the states have been processed and no solution has been found) or until a goal state is found.
- Greedy: The algorithm is an implementation of the Best-First Search algorithm. The score is a sum over the Manhattan Block Distance between each tile and its target position on the board. Manhattan Block Distance is the distance between two locations on the board, where only horizontal and vertical movements are allowed.
- A*: The algorithm is an implementation of the Best-First Search algorithm. The score is a sum over the Manhattan Block Distance beween each tile and its target position on the board plus the length of the path from the initial state to the current state.
- Greedy Solution Only: The algorithm is the same Greedy algorithm, except that the best path is searched without being displayed. Once a path is found - it is played out step after step. Note that the search process can be long and can take up a lot of memory and CPU. Press the stop button if you wish to stop the search at any stage.
- A* Solution Only: The algorithm is the same A* algorithm, except that the best path is searched without being displayed. Once a path is found - it is played out step after step. Note that the search process can be long and can take up a lot of memory and CPU. Press the stop button if you wish to stop the search at any stage.
