1 Background

8-puzzle is a children’s game. The game consists of a board divided into three rows and three columns (for a total of 9 squares). The board has affixed to it eight tiles that are free to move vertically or horizontally into the open space left by the missing ninth tile.

For instance one possible starting board configuration is:

There are three moves possible from this board corresponding to the three possible tiles adjacent to the open space. They result in the following boards respectively:

The object of the game is to move the tiles around legally until you reach the board:

2 Caveat

The solutions to this problem are well known and can be done using a simple Breadth First search or A^⋆ algorithm. These solutions rely on the fact that it is the same “cost” to move any tile as it is for any other tile.

This project makes it more interesting by forcing a specific cost to move each tile. That is it may cost you $5 to move the tile 2 while is may cost you only $2 to move tile 4.

3 Task

Calculate and print the sequence of moves that yields the goal state while minimizing the cost spent to arrive at the goal. Also print out the minimum cost found.

4 Input

The program will be run in a manner such as:

java Puzzle 7418362 5 3 5 2 3 7 19 12 4

The first argument to Puzzle is a string representing the initial board state. Each following integer is the cost of moving the respective tile. In the example shown it costs $3 to move the 7 tile while it takes $12 to move the 2 tile and $4 to move the 5 tile.

5 Output

The output must be in the format:

If there is a solution then the output should be:

5635287413528741256 = $130

(This output example is a possible solution but necessarily a minimal solution.)

If there is no solution possible then the output should be:

Unsolvable.

Exactly half of the possible inputs are unsolvable.

6 Deliverables

Upload your .java files to the WebCT assignment prior to the cut-off time.

7 Extra Credit

15 puzzle is the exact same game only played with 15 tiles on a 4 × 4 grid.

You can acquire 3 extra points if you make your solution capable of solving 15 puzzles as well as eight puzzles.

In the case of 15-puzzle the tiles are enumerated with hexadecimal digits.

8-puzzles must be solved using Dijkstra’s algorithm. 15-puzzles may also be solved in this manner though you are free to choose any algorithm you desire for the 15 tile game. (I suggest researching the A^⋆ (A-star) algorithm.

In this case a sample input is: java Puzzle B7941AF83CD62 5E 3 5 2 3 7 19 12 4 9 34 2 0 34 5 8

and corresponds to the initial board state: