Welcome to N-Puzzle
This web application allows you to view a graphical representation of a range of different graph search algorithms, whilst solving your choice of 8-puzzle problems.
Getting Started
On the left-hand side of this application, you will see the Control Panel. Using the Control Panel, you can configure the following aspects of the application:
- Initial State and Goal State
- Which Search Algorithm to use
- Which Heuristic Function to use, if using an Informed Search Algorithm
- And whether to use single-step or burst mode
Each of these options will be described in more detail below.
Initial and Goal States
To set the Initial or Goal states, you can click either the 'Edit state' button or the graphical representation of the state.
You should see a popup like the following:
To change a tile, simply click on the tile that you would like to replace, then enter the new value on your keyboard. This will swap the tile with the one that previously held that value.
Search Algorithm
N-Puzzle supports five different Graph-based Search Algorithms. The first three are Uninformed Search Algorithms:
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
The other two are Informed Search Algorithms:
- A* Search
- Greedy Search
If you choose an Informed Search Algorithm, then you will also need to select a Heuristic Function.
Heuristic Function
N-Puzzle supports three different Heuristic Functions:
- Euclidean Distance
- Manhattan Distance (City-Block distance)
- Tiles Out-of-place
Single-Step or Burst Mode
N-Puzzle can be used in two modes. The default is Single-Step mode, which allows you to 'rewind' a search, one step at a time. This is useful for getting a better understanding of how a Search Algorithm works.
The other mode is Burst Mode. Once started, Burst Mode continues running a search until the goal state has been found. A Burst Mode search can be paused, but cannot be 'rewound'.
The Search Tree
State Representation
While a search is active, you will be able to see a visual representation of the search tree. Each node in this search tree represents an arrangement of tiles (or state), and is drawn as a box that is split into 4 sections.
The following diagram shows a node taken from a Greedy search:
The largest section is the puzzle state. Below that you will see two smaller sections.
Below the puzzle state are two sections. The section on the left is the depth of the node. The section on the right is the heuristic score. The heuristic score is only used with Informed Search Algorithms, so if you are using Breadth-first, Depth-first or Iterative Deepening Search, the heuristic score will be omitted.
The last section records the order in which nodes were expanded. For example, the root node will always be '#1', and the next node to expanded will be marked as '#2'.
Node Colours
To help make the Search Tree more 'readable', the border of each node is colour-coded based on its current state.
The following diagram shows the A* algorithm (with the Euclidean distance heuristic) applied to a problem that can be solved in just two moves:
The colours can be interpreted as follows:
| Colour | Meaning |
|---|---|
| Blue | If a node is in the Open List then it will be highlighted in blue. |
| Red | After each iteration of a search algorithm, the node that will be expanded next will be highlighted in red. This applies even when the goal node has been found. |
| Grey | If a state has been explored, it will be greyed out. For example, in step 2) of the diagram above, the initial state has been coloured grey to indicate that it has been explored. In step 3), a node representing the initial state is rediscovered but it will not be expanded since the initial state has been expanded via the root node. |
| Green | Once the goal state has been found, it will be highlighted in green. |
| Gold | Once a node representing the goal state has been found, any nodes on the path back to the root node will be highlighted in gold. |
| Purple | When using Iterative Deepening Search, unexplored nodes that exceed the maximum depth will not be added to the open list. These nodes will be colored purple. |
Open and Closed Lists
While the search algorithms are running, two lists are maintained. The first is the Open List - this is used to keep track of nodes that have been discovered, but not yet explorered.
The second is the Closed List - this is used to keep track of nodes that have been explored, or nodes that will not be explored because they represent states that have already been explored via other nodes.
When a search is active, the number of nodes in the Open and Closed Lists will be visible in the top-left corner:
Credits
N-Puzzle was developed by Tristan Penman. The source code can be on Github, and is distributed under the Simplified BSD License. See the LICENSE file included in the source code for more information.
This project is based on the AI-Search Java applet developed at RMIT University by Vic Ciesielski, James Harland and Peter McDonald.