Simple 8-puzzle solver written in JavaScript. User interface is realizes as a simple web page, where user can choose size of the puzzle (3x3, 4x4, or 5x5) and heuristic type.
Interface of the program is a simple web page. To start it, open the index.html file in your browser.
Since solution for a puzzle may contain over hundred of steps, it is recommended to use chromium based browsers, because they implement content-visibility CSS attribute that improves rendering of large web pages.
This implementation utilizes Greedy search algorithm with min heap as the priority queue and hash map data structure for the visited states.
Algorithm is initialized with a single entry in the min heap and in the visited states map (the initial state). Then, each iteration following steps occur:
- Check if queue is empty. If it is - solution has not been found, exit.
- Pop (extract min) value from the priority queue.
- Check if its heuristic value is 0. If it is - solution has been found, exit.
- For each puzzle cell, that is around the empty space, check if it can be moved. If yes:
- move it;
- generate new state;
- calculate its heuristic value;
- add it to the priority queue.
- Repeat step 1.
This implementation contains two heuristic functions to choose from:
- Manhattan Distance - sum of distances from current position of each puzzle cell to its target position. Formula for the distance calculation is:
|x2 - x1| + |y2 - y1|, wherex1,y1,x2,y2are coordinates of the puzzle cell, and its target position, respectively. - Invalid placed cells count - count of invalid placed cells.
Second options is obviously much worse, because it provides much less relevant information about the state of the puzzle. This is also projected in the final testing results.
Each puzzle state stored in the priority queue is represented as an object with these fields:
| Field Name | Data type | Sample Value |
|---|---|---|
state |
number[] |
[1, 0, 2, 3, 5, 4, 6, 8, 7] |
stateKey |
string |
1-0-2-3-5-4-6-8-7 |
cursorIndex |
number |
1 |
heuristicValue |
number |
4 |
state- current state of the puzzle, represented as one dimensional array, where0is an empty space;stateKey- string representation of the puzzle state, used to identify it in the hash table of the visited states;cursorIndex- locations of the element0(empty space) in the puzzle;heuristicValue- value returned by the heuristic function for the current state of the puzzle.
Since, exact size of each data type in JavaScript is dependent on the engine and its specific implementation, we can only approximate size of each node based on the representative size of each primitive data type. So in our case, each node, which holds puzzle state, may approximately have these sizes for each of its fields:
| Field Name | Data type | Size in bytes |
|---|---|---|
state |
number[] |
8 * N * M |
stateKey |
string |
2 * N * M - 1 |
cursorIndex |
number |
8 |
heuristicValue |
number |
8 |
| Total | 10 * N * M + 15 |
Primitive data structure sizes were taken from the MDN page.
Where N and M are the dimensions of the puzzle.
So node of the classical 8 puzzle would approximately have the size of 105 bytes.
To provide specific numbers, below are data from snapshots taken in Edge (Chromium) browser, that uses V8 JavaScript engine. Each row represents node size inside of the priority queue with specified puzzle size.
| Puzzle Size | Shallow Size (bytes) | Retained Size (bytes) |
|---|---|---|
| 3x3 | 28 | 120 |
| 4x4 | 28 | 120 |
| 5x5 | 28 | 120 |
Yes, they are the same. This has been tested multiple times, but same results were received.
Shallow size - is the actual size of memory used by given object.
Retained size - is the size of memory that will be freed, when garbage collectors collects given object.
Here are some results of node generation for the given amount of steps.
With Manhattan Distance heuristic:
| Puzzle Size | Steps count | Nodes count |
|---|---|---|
| 3x3 | 4 | 12 |
| 3x3 | 36 | 82 |
| 3x3 | 39 | 208 |
| 3x3 | 81 | 763 |
| 3x3 | 93 | 479 |
| 4x4 | 81 | 616 |
| 4x4 | 162 | 2913 |
| 4x4 | 171 | 2367 |
| 4x4 | 195 | 3334 |
| 4x4 | 247 | 3724 |
| 5x5 | 317 | 15359 |
| 5x5 | 430 | 35238 |
| 5x5 | 444 | 13747 |
| 5x5 | 519 | 22754 |
| 5x5 | 542 | 122182 |
With Invalid placed cells count heuristic:
| Puzzle Size | Steps count | Nodes count |
|---|---|---|
| 3x3 | 4 | 12 |
| 3x3 | 48 | 621 |
| 3x3 | 72 | 727 |
| 3x3 | 76 | 941 |
| 3x3 | 95 | 909 |
| 4x4 | 245 | 21507 |
| 4x4 | 307 | 30847 |
| 4x4 | 361 | 21006 |
| 4x4 | 466 | 39759 |
| 4x4 | 529 | 82370 |
| 5x5 | 504 | 108010 |
| 5x5 | 561 | 255612 |
| 5x5 | 579 | 62502 |
| 5x5 | 708 | 289949 |
| 5x5 | 716 | 206154 |
Here are average results of duration for each heuristic with random state generation:
| Puzzle Size | Runs count | Manhattan Distance | Invalid placed cells count |
|---|---|---|---|
| 3 | 250 | ~0.0041777s | ~0.0125658s |
| 4 | 125 | ~0.0576453s | ~0.35580458 |
| 5 | 100 | ~0.3606378s | ~1.7524236s |
Greedy algorithm is not an ideal solution for 8, 15, or 24 puzzles, because it utilizes single heuristic and doesn't evaluate its previous states to make better decisions. Something like A* algorithm with good heuristic function, would produce much better results.
As far as the heuristic functions go, it is evident from the results that Manhattan Distance heuristic is much more efficient than Invalid placed cells count, both in time and memory complexities.
It also worth noting that JavaScript is not the fastest language out there. It's main limitation in terms of execution speed comes from the fact that it is an interpreted language. Languages such as C and C++ can solve this type of problems with higher time and memory efficiency. But JavaScript has an advantage of being sole programming language that web browsers understand. This allows to create beautiful user interfaces with HTML and CSS, and define their logic with JavaScript. Browser environment also allows to directly take memory snapshots to analyze memory consumption of the page. These are the main reasons why JavaScript was selected for this project.
Several test scenarios can be found in the puzzle-solver-tests.js file in the src/tests directory of the project.