8 Puzzle Problem in Artificial Intelligence

8-Puzzle Problem:

The 8-tile puzzle consists of a 3 by 3 (3*3) square frame board which holds eight (8) movable tiles numbered 1 to 8. One square is empty, allowing the adjacent tiles to be shifted. The objective of the puzzle is to find a sequence of tile movements that leads from a starting configuration to a goal configuration.

The states of the 8-tile puzzle are the different permutations of the tiles within the frame.

Note: An optimal solution maps an initial arrangement of the tiles to the goal state with the smallest (minimum) number of moves. It also notes that the root node can be any random starting state.

8-Puzzle Problem Formulation:

States: It specifies the location of each of the 8 tiles and the blank in one of the nine squares.

Initial State: Any state can be designated as the initial state.

Goal: Many goal configurations are possible .

Legal Moves: They generate legal states that result from trying the four actions –
i. Blank moves left
ii. Blank moves right
iii. Blank moves up
iv. Blank moves down

Path Cost: Each step costs 1, so the path cost is the number of steps in the path.