The goal of the game is to slide the tiles into their correct arrangement. Players can scramble the tiles any number of times before invoking the AI. Or if they prefer, players can manually play the game by clicking tiles.
This project focuses on artificial intelligence which solves the game. The main challenge is searching through a large state space. There is an average branching factor of 3, so a solution at depth 30 (30 moves) would have more than 100 trillion nodes above it. Basic graph search algorithms like breadth first search and depth first search are too slow. Even A* with a decent heuristic is too slow.
The key to solving the game was to divide the problem into smaller, more manageable sub-problems. First, get the top row in the correct place, ignoring the positions of the other tiles. Then from there, get the first two rows in their correct positions, etc. Each sub-problem was solved with A* using a heuristic that summed the Manhattan distances between each tile and its respective correct location. Dividing the problem like this dramatically reduces computation time, but it sacrifices optimality.
This solution isn't optimal, but it provides an upper bound on the depth of the optimal solution. I experimented with depth limited search, using this upper bound as the depth limit. This too, however, is too slow.