8 Puzzle AI

One of my current projects is creating an 8 puzzle with an AI to solve it for the player. I’ve finished everything except the AI solver. The AI is fairly simple for a project like this, but I wanted to create a UML class diagram and an activity diagram for the project, just so I could break the code up over several weeks, as I have time to work on it, and just check bits and pieces off on the diagrams as done so I don’t forget what still needs working on, or the design I came up with.

In case you don’t know, an 8 puzzle is one of those flat sliding puzzles with the numbers one thru eight that you slide around until they are in order. Some people solve them with the empty square in the center, and some people solve them with the empty square down at the bottom righthand corner.

8 Puzzle Game
This is a screen capture of the 8 puzzle game I’m writing.

Mixing the 8 puzzle up in the first place takes a little more work that arranging the numbers randomly. There are many unsolvable configurations of an 8 puzzle. The basic trick is to check for an even number of inversions. If you have an even number of inversions, then the puzzle is solvable. If you have an odd number of inversions, then you have an unsolvable puzzle.

I already know you’re probably asking, What is an 8 puzzle inversion? If you were to think of the 8 puzzle as an array of numbers with the following 0 based index layout,

0 1 2
3 4 5
6 7 8

Then the numbers would be in the following order when solved,

1, 2, 3, 4, 5 , 6, 7, 8

For the purpose of counting inversions, ignore the empty square. (Just pretend the empty square isn’t there ūüėȬ†An inversion happens when a number is out of order, so that smaller numbers are after it in the array. For example,

2, 1, 3, 4, 5 , 6, 7, 8

has one inversion, because 1 comes after 2. In this example,

4, 2, 1, 3, 5 , 6, 7, 8

there are four inversion because 3, 2 and 1 come after 4 and 1 comes after 2.

To find the total number of inversions, count the number of smaller numbers that appear after every number in the array. When the count is even, you have your solvable puzzle.

Congratulations! You’re one of the cool kids that know how to generate solvable 8 puzzles.

Now on to the AI for solving 8 puzzles.

In the following diagrams, C2 refers to Construct 2 that I used for the GUI for the 8 puzzle. I created a plugin that calls JavaScript generated from ClojureScript. However, these diagrams are more for general AI design for an 8 puzzle solver.

The first concept to get straight for solving any puzzle with an AI is that of score. Each board or puzzle position is called a node and organized into a tree. Each node needs to be given a score that describes how close it is presumed to be to the solution of the game or puzzle. It has been long acknowledged that 8 puzzle nodes are best described by scoring with what is called the Manhattan Distance.

When using the Manhattan Distance, first you score each square, and then you add all the square’s scores together. Don’t forget the empty square. For calculating the Manhattan Distance, you need to also calculate it for the empty square. (This is the opposite of when you are counting inversions.)

The formula for Manhattan Distance for each square is |x1 Рx2| + |y1 Рy2| where the (x1, y1) is the current location in the grid, and (x2, y2) is the desired location in the grid. Note that the Manhattan Distance for a solved puzzle with turn out to be zero.

One of the biggest gotchas in AI design is knowing how to design the best scoring algorithm. Luckily, the hard work has already been done for you in the case of the 8 puzzle.

8 Puzzle AI Activity Diagram
Click on this 8 puzzle AI activity diagram to see a larger version.

After figuring out how to score moves toward a solution, understanding how to do a depth-first search with node pruning is the next thing to understand. A node in its simplest description is the puzzle that results from making each move. In an 8 puzzle, any given puzzle could have 2, 3, or 4 possible legal moves. That means 2, 3 or 4 new child nodes could be generated from each puzzle configuration. And, each of those new nodes could have 2-4 new child nodes.

If you do the math, the number of nodes can grow massively in a short time. If you have limited resources, or just want your AI to be fast, pruning your nodes is wise. The first step is to have a list of actively searched nodes. Limit this list after each step, but eliminating all low scoring nodes and only keeping the highest scoring nodes. Also, make sure your move generator doesn’t undo the move that just happened (so technically each 8 puzzle node only has 1-3 valid moves.)

One other thing about nodes for 8 puzzle solving is that they need to be self aware of their score, their parent node, and the move that generated them. Using this information, when a solution is found, it is simple to create a list of moves that generated the solution by traversing back up the node tree all the way to the root node, adding the moves that generated each node with each step to a solution array.

The activity diagram for my 8 puzzle solving AI is above. Essentially, it takes an JSON C2 array representing the current mixed up state of an 8 puzzle. It has a master list of best nodes found so far. It then creates an initial list of best nodes found using just the original puzzle given to be solved. Only, at each new search level, only the best node is selected to search. Only, in cases where the best node doesn’t appear to be doing well, will some other nodes end up being searched. When a node’s children are searched and scored, that node is removed from the best nodes list, though its children still have a reference to it. Finally a solution is found, and the tree is unwrapped to generate a solution move list.

8 Puzzle AI Class Diagram
Click on this 8 puzzle AI class diagram to see a larger version.

I also threw together a generic class diagram for 8 puzzle solving AI just to be thorough.