This repository explores the N-Puzzle solver using the following algorithms (in order of increasing performance):

1. Breadth-First Search (BFS.py)
2. A* Search using Manhattan Distance (manhattanDistance.py)
3. A* Search using Manhattan Distance & Linear conflict (linearConflict.py)

python <filename> <inputfile> <outputfile>

The input file should be a 2D array representing the puzzle. Look at the test input for an example.

The scripts writes the series of steps to solve the N-puzzle into the output file. If no solution exists, it writes 'UNSOLVABLE'.

We can compute whether the grid is solvable in one step, by checking the position of the blank tile and the number of inversions in the grid. This improves performance significantly, as it would not have to generate all possible nodes before declaring that the puzzle is not solvable. Read more here.

Instead of computing Manhattan Distance for each grid, we could update the manhattan distance using the parent's manhattan distance, compute the change caused by a particular move.

Another minor optimisation done was to prevent generation of a new grid each time. By doing a simple swap to check if a particular state has been visited before, we saved on a couple of deepcopy operations, which were quite expensive.