the N-Puzzle

You will program a solution to the N-puzzle (for small N).

For N = 4 the puzzle has 16 tiles organized in a 4 x 4 square: in 15 of the tiles you find the numbers 1 to 15 and one tile is left unoccupied.

The goal is to reorganize the tiles so that the numbers are ordered and the unoccupied tile is the last tile. Reorganization of tiles is done by moving a tile to the unoccupied tile. The puzzle is explained in 15-puzzle. In our project this is called the 4-puzzle because the square is 4 x 4. And we will use letters in the tiles instead of numbers because it makes the representation of the tiles easier.

For the program, a square can be represented using a string. First an example: the square we want to get to in the 4-puzzle is

We can represent it using the string ABCD/EFGH/IJKL/MNO_

If you start with the square

represented with ABCD/EFGH/IJKL/MN_O you can get to the goal by moving the O one step to the left.

If you start with the square

represented with ABCD/EFGH/IJK_/MNOL you will need more steps to get to the solution!

The important insight is that we can use a graph to describe the moves: the nodes are strings representing the squares and there is an edge between two squares (strings) if you can get from one square to the other one by a legal move.

Your task

Write a program to solve the N-puzzle (a puzzle for an N x N square).

Your program (a function) should take arguments N for the size of the puzzle and a string S that represents the square you want to start with.

In the program you should construct a graph and then use an algorithm for finding a shortest path from the argument S to the solution.

The program should print the sequence of squares (as strings) showing the moves used if the program found a path. If the program does not find a path it should print a message saying so.

You should also answer the following questions:

1) Is the graph directed or undirected?

2) Do the edges have weights?

3) What algorithm will you use for finding the shortest path? Why do you pick this algorithm?

4) Can your program solve 4-puzzles in a reasonable time?

Testing

Test your program with 2-puzzles and 3-puzzles that you construct yourself! The test you write should be part of your submission. Explain the test cases that you use so that we understand that your solution works correctly.