N Puzzle.
A classic problem in Computer Science.
The problem utilizes search techniques which are parts of Artificial Intelligence(AI) techniques to find the solution to the problem.
The solution of N Puzzle is how to move tiles in a series that leads from the starting state(scrambled ordered tiles) to the goal state(properly ordered tiles).
There are various search techniques that can be used to solve the N Puzzle problem.
The videos above show solving N Puzzle with heuristic search(informed search) techniques.
Algorithms utilized are Best First Search, A*, and IDA*.
Each algorithm has a different behavior in solving the problem. The amount of time required, CPU usage, and memory consumption are also different.
N Puzzle problem can be varied in complexity. For example, consider 8 Puzzle problem(8 tiles) with empty tile shown as x:
Goal state is
1 2 3
4 5 6
7 8 x
while starting state can be varied
1 2 3 6 7 2
4 5 6 8 x 4
x 7 8 5 3 1
Clearly, the state on the left is much easier to solve than the state on the right, thus the state on the right is more complex than the state on the left.
Another major factor of the N Puzzle problem is the number of the puzzle. 8 Puzzle has 8 tiles(excluding empty tile). 15 Puzzle has 15 tiles. 24 Puzzle has 24 tiles and so on.
The complexity of the puzzle grows with the number of the puzzle and how scrambled the order of tiles in the puzzle is.
The complexity of the puzzle, search algorithm utilized, and heuristic functions used are key factors that determine the amount of time needed, CPU usage, and memory consumption when solving the puzzle. Puzzles can take a very long time to solve due to the factors described. The numbers of possible states are 9! (factorial) for 8 puzzle, 16! for 15 puzzle, 25! for 24 puzzle, and so on. The size of the answer space is huge. N Puzzle problem is proved to be NP-hard problem.
Heuristic functions utilized for solving the N puzzle shown in the videos are Manhattan Distance combined with Linear Conflict.
In the videos, the app would calculate the solution to the puzzle when the user presses the Solve button. While calculating the solution, the Solve button would appear gray. After the solution is found, the Solve button would return to normal and the solution would be shown, animating the tiles for the user to see.
The amount of time used in solving the problem and the number of steps that leads from the starting state to the goal state along with the number of states generated while searching are shown in the table below. The same size of puzzle with different algorithms have the same starting state of the puzzle in order to compare the performance of the algorithms.
| Number of puzzles - Search algorhthm | Time consumption (milliseconds) | Number of states generated | Number of steps for solution |
|---|---|---|---|
| 8 Puzzle - Best First Search | 19 | 176 | 37 |
| 15 Puzzle - Best First Search | 159 | 3746 | 239 |
| 24 Puzzle - Best First Search | 218 | 4438 | 317 |
| 8 Puzzle - A* | 223 | 1736 | 27 |
| 15 Puzzle - A* | X | X | X |
| 8 Puzzle - IDA* | 100 | 2363, 4 iterations | 27 |
| 15 Puzzle - IDA* | 20478 | 682684, 10 iterations | 59 |
In the scope of N Puzzle, as shown from the results in the table.
Best First Search can find the solution to the problem quickly but does not guarantee the shortest path(the least number of steps that are needed to be taken) from the starting state to the goal state.
A* takes a longer time in searching for a solution. However, the A* algorithm guarantees to give the shortest path solution.
A* in 15 puzzle could not find a solution to the problem in practical time. This is due to the behavior of the A* algorithm. Since 15 puzzle can have 16! possible states(20,922,789,888,000 states), the A* algorithm would try to find the shortest path solution, having almost all states generated in the process due to the heuristic function utilized being consistent. The amount of time needed is enormous.
Improvement can be made on this issue by using IDA* algorithm instead. Like A*, the IDA* algorithm guarantees to give the solution that is the shortest path. Combining Depth First Search with Iterative Deepening Search, the amount of time needed to solve the N Puzzle is significantly reduced compared to the case of A* algorithm.
However, for 24 puzzle and above, to solve the puzzle with A* or IDA* algorithm in practical time will need a better heuristic function than Manhattan Distance. Disjoint Pattern Database can fill in for this role. Using Disjoint Pattern Database with IDA* algorithm, an arbitrary solvable 15 puzzle can be solved in just about 30 milliseconds on average.
N Puzzle Solver part of the app is written in C/C++(Modern C++) and can run on any platform that supports C/C++. Testing for the solvable property of the puzzle presented is also implemented.
Platform: iOS
Programming Language: Objective-C, C/C++
Device: iPhone 5S