A* on the Sudoku Cube
A* program
Your assignment is to implement A* on the Sudoku cube. Please refer to the following guidelines in order to get an A on this assignment:
• You must be able to generate “randomized” instances of the Sudoku cube;
• You must be using a valid admissible 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 instance, and for the randomizing parameter k from 3 to
at most 20, for each k generate 5 k-randomized puzzles and solve them,
using A*. (A k-randomized puzzle is one that has had k randomly generated
moves applied to it.) Note that we will look at your code, so backtracking
along the generation path will not be be accepted. Also note that you
are likely to run out of memory for some instances. At that point, you
have enough instances. You might not be able to solve for k=20.
You may find it helpful to choose to use only clockwise moves to randomize,
and only counterclockwise to solve.
Note that this will be slow. Do not leave this assignment to the last minute!
To hand in:
• 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;
• Your carefully commented code;
• Instructions on how to compile/run your code;
• A plot of the average number of nodes expanded in the last iteration of A*
as a function of the actual distance to a solution;
• A brief statement of what you learned from this assignment.
You should submit a tar, zip, or gzip file or similarly compressed
folder. When expanded, it should have your last name as part of the
directory name. However, for ease of anonymizing for the ABET
(accreditation) course portfolio, please do not put your name in the files.