AI Solver Details

The AI solver that that I created uses a modified Breadth-first Search (BFS) algorithm to iteratively solve the puzzle. As this 4X4 puzzle can be shuffled into 20,922,789,888,000 unique positions, the computed BFS solution tree quickly grows too large for a conventional computer and a maximum depth is reached at approximately 16 swaps. The average puzzle requires around one hundred moves to complete, so I designed the solver to run the BFS algorith at a limited depth, always choosing the partial solution path that provides the swap selection. Ultimately, each run of the BFS must result in an path that leads to a puzzle that is ordered more closely to the solved puzzle.

I observed that choosing the best path based on a simple cost function that sums the total distance of each piece from its destination would lead to puzzles orders that still could not be solved because the solution depth to find improved puzzle states was still too deep. To mitigate this issue I altered the cost function and assigned higher costs to misplaced tiles from the upper left corner of the puzzle. The closer to the upper left an image tile belongs, the algorithm is more incentivized to solve it sooner. When observing any solution you may notice that the solution path is more likely to place the upper left tiles sooner and move to the lower right tiles near the end of the swapping. This method works particularly well due to the fact that only the empty tile (which belongs in the lower right) can be used to move pieces around. The empty tile and lower right tiles are therefore the last pieces moved into place.