Solver for puzzle 3x3

Please place an x in the position for the empty space.

Initial State

Goal State








8 Puzzle Game (Advanced Artificial Intelligence Assignment)

The main goal of this assignment is the implementation of the the solution of any 3x3 puzzle configuration using a Best First Search Algorithm [5]. This algorithm is based on heuristics to identify which is the best possible movement the next iteration. Heuristics methods [4] used in this assignment are Hamming Distance and Manhattan Distance.

Hamming Distance is calculated counting each missplaced position of the numbers in the board respect to the goal(A or B). On the other hand Manhattan Distance is calculated by summing up each one of the required movements for each number from position in current board to position in the goal (A or B).

Furthermore the implementation of the algorithm could be summarized by finding the state with the lower heuristic value in each iteration, following by generating children from this state. Finally the process is repeated until one of the states is the goal (A or B). An additional step is performed in the middle which check if one of the children has not been reached by a shorter path, if so, the state is changed for the one with shortest path to the Start.

Detecting unsolvable puzzles was one of the main initial issues; the fact is that there are configurations in which a solution can not be found for either (A or B) goal, in order to find solubility this resources were read [1],[2],[3].

References:

[1] http://mathworld.wolfram.com/15Puzzle.html

[2] http://mathworld.wolfram.com/15Puzzle.html

[3] http://www.laborion.com/Portals/0/Ai/Heuristicssearch/93ijcai.pdf

[4] http://heuristicswiki.wikispaces.com/N+-+Puzzle

[5] Artificial Intelligence: Structures and Strategies for Complex Problem Solving, by George F Luger