Formulate the 8 puzzle as a search problem. See the text, Section 3.2.1, for a start and then lay out the data structures and implementation details that will be required to implement an 8 puzzle search using the AIMA search tools.

Note that because the AIMA graph search uses hashing to keep track of which states it has visited, your state representation must be a hash-compatible type like an integer or a string. Unfortunately, lists are not hash-compatible.

Save this as a text file to submit later.

Download this starter module and modify it to solve the 8 puzzle by doing the following:

1. Run the code as it stands. What puzzle configuration is it solving? Does it get the right answer?

2. Download and run its test module. This will be helpful as you develop the basic search methods.

3. Implement the basic search methods:

   1. Implement the actions() method.

      This method should receive a state and return a list of actions that can legally be executed from the state. See the header documentation for a specification of the proper state and action formats.

      One algorithm for this method is:

      create an empty actions list
      if the open space is in the bottom two thirds of the board
      	add 'u' to actions
      if the open space is in the top two thirds of the board
      	add 'd' to actions
      if the open space is in the right two thirds of the board
      	add 'l' to actions
      if the open space is in the left two thirds of the board
      	add 'r' to actions
      return actions list
      							

   2. Implement the result() method.

      This method should receive a state and an action pair and return a new state representing the results of the given action in the given starting state. Use the given swap() method to actually do the swap.

      One algorithm for this method is:

      find the index of the space
      if the action is 'u'
      	return a new board that swaps the space index with the index just "above" it
      if the action is 'd'
      	return a new board that swaps the space index with the index just "below" it
      if the action is 'l'
      	return a new board that swaps the space index with the index just "right" it
      if the action is 'r'
      	return a new board that swaps the space index with the index just "left" it
      							

4. You should now be able to run the search mechanism on more interested problems. Try A* searches on the following initial states:

   32 415 678	This has a 4-step solution.
   125 634 78	This has a 8-step solution.
   63 712 854	This has a 16-step solution.

   Do these searches run as fast as you would expect? Why or why not?

Save your code file, with comments, to submit later.

Implementing a decent heuristic function can speed up the search considerably. See the text, Section 3.6 for a detailed discussion of this.

1. Implement one (or more) heuristic methods:

   1. Implement the h_misplaced_tiles() method (and modify h() to call it).

      This method should compute the number of misplaced tiles, i.e., the number of tiles not currently in their goal locations. The space is not a tile, so it can't be out of place. See the text, Section 3.6 for a description of this heuristic and its value.

   2. If there is time, implement the second heuristic method, h_manhattan_distance(), for the Manhattan distance heuristic.

   Use the unit test methods for the heuristic functions to verify that your implements are implemented correctly.

2. Now, with either or both of these heuristic methods in place, rerun the searches from the previous exercise. Is there a measurable difference in the time?

3. Try these other initial configurations:

   187 2 6 345	This has a 22-step solution.
   724 5 6 831	This has a 26-step solution. It is discussed in the text, see Figure 3.28.
   8 6 547 231	This has a 31-step solution. According to Gerhard Wickler, this state is the worst-case scenario for the given start state.

   Set aside plenty of time if you want to run these goal states with no heuristic function!

Include this code in your main code file.