Visualgos: N-Puzzle

Search this site:

This 8 Puzzle visualization shows an implementation of a DFS algorithm, a greedy algorithm and an A* algorithm.


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: