Algorithms, part I, Week 4: 8-Puzzle

The Task of the Week:

Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
The problem. The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order, using as few moves as possible. You are permitted to slide blocks horizontally or vertically into the blank square. The following shows a sequence of legal moves from an initial board (left) to the goal board (right).

1  3        1     3        1  2  3        1  2  3        1  2  3
 4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6
 7  8  6        7  8  6        7  8  6        7  8  6        7  8 

 initial        1 left          2 up          5 left          goal

Best-first search. Now, we describe a solution to the problem that illustrates a general artificial intelligence methodology known as the A* search algorithm. We define a search node of the game to be a board, the number of moves made to reach the board, and the previous search node. First, insert the initial search node (the initial board, 0 moves, and a null previous search node) into a priority queue. Then, delete from the priority queue the search node with the minimum priority, and insert onto the priority queue all neighboring search nodes (those that can be reached in one move from the dequeued search node). Repeat this procedure until the search node dequeued corresponds to a goal board. The success of this approach hinges on the choice of priority function for a search node. We consider two priority functions:

• Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the search node. Intutively, a search node with a small number of blocks in the wrong position is close to the goal, and we prefer a search node that have been reached using a small number of moves.
• Manhattan priority function. The sum of the Manhattan distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the search node.

For example, the Hamming and Manhattan priorities of the initial search node below are 5 and 10, respectively.

8  1  3        1  2  3     1  2  3  4  5  6  7  8    1  2  3  4  5  6  7  8
 4     2        4  5  6     ----------------------    ----------------------
 7  6  5        7  8        1  1  0  0  1  1  0  1    1  2  0  0  2  2  0  3

 initial          goal         Hamming = 5 + 0          Manhattan = 10 + 0

First Approach

Compilation:  PASSED
Style:        FAILED
Findbugs:     No Potential bugs found.
API:          PASSED

Correctness:  16/25 tests passed
Memory:       8/8 tests passed
Timing:       0/17 tests passed

Raw score: 51.60% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]

For this first attempt, i changed the 2d array of int from the API to a 1D array of char which occupies at least half as much memory and is twice faster (2 memory accesses in the 2d array for 1 access for the 1D array). This improved notably the time spent to solve the less harder puzzles.

Another improvement i made was to implement the isSolvable() method not by putting a twin board in the MinPQ with the initial one, but rather analyzing the properties of the initial board itself following the rules of the Parity Check hereby:

1. If the grid width is odd, then the number of inversions in a solvable situation is even.
2. If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
3. If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

This allowed to leverage the amount of items in the Priority Queue or even having two Priority Queues working at the same time, one resolving for the initial board and the other resolving the twin() board. If the twin board was solved then we knew the initial board was not solvable.

So whether using one or two Priority Queues, this improvement avoids having to solve first one of the two cases to get to know if a given board is solvable.

The final improvement was to cache the manhattan distance for each board. It was calculated in the constructor and for the following calls to the method int manhattan() return the value

Another problem i figured out was when checking if a neighbor was already in the closedSet

I was doing something like:

closedSet.contains(neighbor);

When neighbor is a SearchNode. I was comparing references instead of the board object!!! thus no calls to board.equals() method. So i changed it to:

closedSet.contains(neighbor.board);

Second Approach

Compilation:  PASSED
Style:        FAILED
Findbugs:     No Potential bugs found.
API:          PASSED

Correctness:  25/25 tests passed
Memory:       8/8 tests passed
Timing:       12/17 tests passed

Raw score: 92.65% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]

Almost got there!! Finally, i realized i could get rid of the ClosedSet which in my case was an ArrayList<SearchNode> and thus avoiding to check against a huge list if one of the four possible neighbors was already there.

I coded the "critical optimization" as said in the checklist and it worked:

Compilation:  PASSED
Style:        FAILED
Findbugs:     No Potential bugs found.
API:          PASSED

Correctness:  25/25 tests passed
Memory:       8/8 tests passed
Timing:       17/17 tests passed

Raw score: 100.00% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]