Due date: Thursday, February 21, 2008.

Ex. 1 Download the file annealing.py. This file contains an implementation of the Simulated Annealing algorithm to solve the 8-tile puzzle. See 6_local_search.html for more details on the algorithm and the puzzle.

Complete the functions all_moves, do_moves, undo_moves by adding a test for each of the directions south, east, and west. The test for the direction north is given as an example in each of them.

Implement the functions energy and solved that are needed to complete the simulated annealing. The first should compute the energy of a state as discussed in class. The second should tell us if we have solved the puzzle already or not.

Ex. 2 Do some experiments with the algorithm to try to answer the following questions:

a. If the puzzle has a solution, how likely is the algorithm to solve it and what is a good combination of the temperature/control parameter p? To answer this you'll have to try out different variations of the temperature and of p to see which ones have a better chance to find the solution. You might want to try out both p>1 and p<1. You can also experiment with the "n" parameter in the proper_shuffle function for fun.

b. What percentage of random puzzles seem to be solvable? To answer this, change the randomizing function in the 'main', and keep the optimal combination of parameters that you found for point a, and do a few experiments. By comparing the percentage of solved puzzles in the two cases you should get a rough estimation of the resolvability of random puzzles.

For reference, here is the documentation of the modules used in this program:
math
random

Turn in: the completed program and your answer to the two questions with a brief explanation.