2.3 The 8-Puzzle

• The eight puzzle consists of a 3 x 3 grid with 8 consecutively numbered tiles arranged on it. Any tile adjacent to the space can be moved on it. A number of different goal states are used.

  5 4 . 6 1 8 7 3 2	1 2 3 8 . 4 7 6 5
  Start State	Goal State

• A state for this problem needs to keep track of the position of all tiles on the game board, with 0 representing the blank position (space) on the board.
• The initial state could be represented as: ( (5,4,0), (6,1,8), (7,3,2) )
• The final state could be represented as: ( (1,2,3) (8,0,4), (7,6,5) )
• The operators can be thought of in terms of the direction that the blank space effectively moves. ie. up, down, left, right.