IDA* program

Your assignment is to implement IDA* on the Hungarian Rings puzzle. In order to get an A on this assignment,

• You must be able to generate ``randomized" states of the Hungarian Rings puzzle;
• you must be using a valid admissable heuristic;
• your code must run;
• you must run the code on many instances, and graph the outcomes as described below;
• you must provide a high-level description of your code, with comments, and
• you must describe what you learned from this exercise.

In particular, for each puzzle, and for the randomizing parameter k from 10 to 100, for each k generate 5 k-randomized puzzles and solve them, using IDA*. (A i>k-randomized puzzle is one that has had k randomly generated moves applied to it.) Note that I will look at your code, so backtracking along the generation path will not be be accepted.

You may use any programming language that supports the necessary operations.

Note that this may be slow. Do not leave this assignment to the last minute!

To hand in (on paper!):

• A description of your program, including a separate description of the the data structures used in the search algorithm, and a separate description of the heuristic you used;
• a plot of the average number of nodes expanded in the last iteration of IDA* as a function of the actual distance to a solution;
• your code;
• in no more than one page, a description of what you learned from this assignment.

To email: