CS 463, Fall 2014, Program 1
Due at the beginning of class (1pm) on Monday,
September 8th.
Consider the
>Hungarian Rings Puzzle. You will, in the next assignment,
be asked to program a particular style of solver for it.
For this assignment, you have
some programming and some problem solving.
Programming
Design and implement data structures for the puzzle itself, produce
some (possibly crude) GUI for sanity checks, and write a program to
to randomize the puzzle.
The GUI could be very simple, with each ball in the puzzle represented by a single letter or number representing its color.
Plain text is fine. If you use someone else's code (just
for the GUI---the rest must be your own code!),
CITE YOUR SOURCE: url, author, title of link, and dates posted (if
known) and read.
The randomizer function should take as input the
the number of moves. Each move is a rotation of one of the circles by
one place in one direction. You need to choose a circle and a direction.
Note that 10 rotations in the same direction brings you back to where you started.
You should prohibit the randomizer from undoing the action that was
just taken, and from taking a 10th rotation in a row of a circle in one direction.
Problem Solving
Come up with at least one heuristic for the puzzle, and explain
both the heuristic and why you believe that that heuristic is
admissable. A heuristic, in this context, is NOT an algorithm. It is an approximation of the number of steps to the solved state. Read the book, about and before the discussion of the A$^*$ algorithm.
To hand in:
- A description in English of your data structure;
- code for the data structures (this can be emailed to Dr. Goldsmith);
- an example of the GUI output;
- a description of the randomizer;
- code for the randomizer (this can be emailed to Dr. Goldsmith);
- your heuristic, clearly described and justified, including an argument that it is admissable;
- a statement of what you learned from this assignment.