For this assignment, we will apply A* search to the eight puzzle problem. The eight puzzle consists of a three by three board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. The object is to figure out the steps needed to get from one configuration of the tiles to another.
For this problem, a state should specify the location of each the eight tiles as well as the blank space in the three by three grid. The operators are most efficiently represented as moving the blank left, right, up, or down, rather than creating operators for each of the numbered tiles.
For example, suppose we wanted to get from the initial state to the goal state given below.
1 2 3 1 2 3 8 6 --> 8 4 7 5 4 7 6 5 initial goalWe could accomplish this with the following sequence of operators on the blank.
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 8 6 right 8 6 down 8 6 4 left 8 6 4 up 8 4 7 5 4 7 5 4 7 5 7 5 7 6 5 initial goal
You may work with a partner on this assignment. Be sure to add both names to the top of every file. Only one of the partners needs to turn in the code.
Before you begin do an update63 to get a copy of the files you'll need to complete this homework. They should appear in the directory cs63/labs/2.
Informed search is very similar to the basic search that we used last week. Because they are so similar it makes sense to have the informed classes inherit from the basic classes.
Similar to last week, you'll need to come up with a representation of the state of the problem as well as its operators. In addition, you'll need to implement several heuristics.
1 3 1 3 4 1 3 7 1 2 8 1 2 2 6 3 7 3 4 7 4 5 8 2 4 8 6 2 4 2 5 8 3 7 4 4 5 6 1 5 6 3 7 6 5 7 5 8 7 6 6 5 4 6 5 3 1 8 7 8 2 8 1 2 A B C D E F G Husing the same goal each time:
1 2 3 8 4 7 6 5 goalState A should take 2 steps, state B should take 6 steps, and state C should take 8 steps. You'll need to determine the length of the other solutions.
In order to demonstrate that the Manhattan distance heuristic is more informed than the tiles out of place heuristic, you will compare the number of nodes that each search expands on the problems given above (A-H). A node is expanded when it is removed from the priority queue. Inside a comment in your 8puzzle.py file, create and fill in the following table:
Node Expansions Problem A*(tiles) A*(dist) A B C D E F G H
Once you are satisfied with your programs, hand them in by typing handin63 at the unix prompt.