Reference no: EM132402383

CSC 361 Artificial Intelligence, King Saud University, Saudi Arabia

The n-puzzle consists of n square tiles, labeled numerically from 1 to n. They are arranged in a random ordering within a square tray that is just large enough to hold n+1 tiles (see fig. 1, n = 15). The tiles should then be slid around the tray until they are in the correct ordering as shown in fig. 2, with the blank space at the bottom-right hand corner. The tiles must not be picked out of the tray.

In this programming assignment you are asked to find the optimal solution using A* of a n-puzzle, where n <= 128, if the n-puzzle is solvable. The solution is a set of actions (the minimum number of moves) that need to be performed in order to solve the puzzle.

1 Input

Your program takes as input a text file that represents the n-puzzle to be solved. The file below represents a 15-puzzle.

The first line of the text file is n (the size of the n-puzzle).

Starting from line 2 in the input file, each line represents one row of the n-puzzle.

The characters are separated by a blank character. The empty tile is represented by the number zero.

2 Output

Your program must display:

• The input (display the board you are going to solve).

• The Hamming distance of the input puzzle.

• The Manhattan distance of the input puzzle.

• Whether the input board is a goal or not.

• The number of inversions in the input puzzle.

• Whether the input puzzle is solvable or not.

• If solvable, display the solution and the length of the solution.

The following output is obtained for the input file described in the previous section.

3 Formula for determining solvability

Not all configurations are solvable. For example, the configuration in fig 3 is not solvable.

There is a method to check whether any given puzzle is solvable. First, consider the tiles written out in a row.

An inversion is a pair of tiles (a,b) such that a appears before b, but a > b. For example, if, in a 4 x 4 grid, number 12 is top left, then there will be 11 inversions from this tile, as numbers 1-11 come after it. For example, on the grid of fig.4, we have:

• the 12 gives us 11 inversions

• the 1 gives us none

• the 10 gives us 8 inversions

• the 2 gives us none

• the 7 gives us 4 inversions

• the 11 gives us 6 inversions

• the 4 gives us one inversion

• the 14 gives us 6

• the 5 gives us one

• the 9 gives us 3

• the 15 gives us 4

• the 8 gives us 2

• 2 from the 13

• one from the 6

So there are 49 inversions in this example. The solution state (the goal) has always zero inversions.

To know if a puzzle is solvable or not, use the following rules:

• If the grid width is odd, then the number of inversions in a solvable situation is even.

• 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.

• 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.

That gives us this formula for determining solvability:

((grid width odd) and (#inversions even)) or

((grid width even) and ((blank on odd row from bottom) == (#inversions even)))

4 Implementation

You need to implement the class State and the class Solver, in addition to the class Test that contains the method main and the method:
public static State readBoard(String s) throws Exception that reads a puzzle from a text file (input file described previously) and returns a State object. This method throws an exception if the format of the input file is not correct or the file does not exists.

The method public List<State> neighbors() returns a list of all neighbors of the current state. A board can have 4 neighbors maximum depending on the position of the blank tile. When generating the neighbors, use the following order for the actions:

1. move the blank tile to the previous row if possible.

2. move the blank tile to the next row if possible.

3. move the blank tile to the previous column if possible.

4. move the blank tile to the next column if possible.

5 Deliverable

You must deliver:

1. Source code (commented): class Solver, class State, class Test in addition to any other class you implemented.

2. A report containing the following sections:

(a) Introduction

(b) Problem formulation

(c) The evaluation function: explain the cost function and the heuristic used.

(d) Design: write a detailed description of how the project was designed. The description should be readable by less technical people, and at the same time helpful for more technical people. Use tables, uml and diagrams if needed.

(e) Implementation: write a detailed description of the most important implementation parts. Use code snippets if needed.

(f) Results: include some run samples with a brief discussion.

(g) Conclusion

Attachment:- Project.rar