IDA* program

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

• You must be able to generate ``randomized" states of the 6-ball Hungarian Rings and 8-ball Hungarian Rings puzzles;
• 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 4 to 8, 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!):

• Described and documented code, 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.