CIT 594, Assignment 4: Backtracking
Dave Matuszek, Spring 2002

Purposes of this assignment:

Your task:

Suppose you have six rings, and each ring has six digits inscribed on its circumference. The six digits are chosen from the set {1, 2, 3, 4, 5, 6}, but some digits may be duplicated and some omitted. For example, a ring might have the digits 2 5 1 6 4 4 on it, and would look something like this (apologies for the terrible drawings):

Your task is to stack these six rings, turning them so that every column has all six numbers in it. For example,

Use Forté to write this as an application, with a Swing GUI. Your application should have two JButtons:

Randomize
"Spins" the six rings into a new starting configuration, and randomizes the vertical order of the rings. However, don't try to create a new set of rings; just use the ones that are given.
Solve
Uses backtracking to turn each ring, starting from the top and working down (or vice versa).

The best way to do this is probably to use a 6x6 array of ints, with each row representing a ring. (More accurately, in Java this would be an array of six int arrays; something like: int rings[][] = new int[6][6];) Turning a ring means moving the numbers in an array end-around; for example, 2 5 1 6 4 4 might become 5 1 6 4 4 2. It doesn't matter whether you turn the rings clockwise or counterclockwise (left end-around or right-end around); choose one direction and use it consistently. Turning a ring is easily done in a separate method, so as not to clutter up your backtracking method. Reordering the rings means reordering the rows; you do not have to move the individual numbers around. For example, the following code swaps rings 2 and 5:

int[] temp = rings[2];
rings[2] = rings[5];
rings[5] = temp;

Randomizing an entire array (such as the array of rings) can best be done by a method such as the following:

public static void randomize(int[] array) {
    Random random = new Random();
    for (int i = array.length - 1; i >= 1; i--) {
        int j = random.nextInt(i + 1);
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

This method needs to be modified slightly, since it is set up to randomize an array of integers, and what you need to randomize is an array of arrays of integers. Again, move all such code out of the way of the backtracking method; keep the backtracking method as clean and to the point as possible.

Try to keep all your code, especially the part that does the backtracking, "showcase clean." Use well-named methods to make the code as easy to follow as possible. Pretend that you are going to teach a class in backtracking, and this is the program that you are going to use to show your students how it should be done.

The GUI:

In addition to the two JButtons mentioned above (Randomize and Solve), your GUI should display your name and the six rings. Probably the best way to display the rings is simply as six JTextFields, arranged vertically, with six numbers in each field.

As you perform the backtracking, change the display to show the current configuration of the rings. This will normally happen too fast to watch, so add a bit of code to pause after each time you change the display. For example,

try { Thread.sleep(1000); }
catch (InterruptedException e) {}

1000 milliseconds (one second) is almost certainly too long to pause; experiment a bit until you find a pause that looks good and doesn't make your program take an annoyingly long time to finish.

Use Swing for this assignment. Do not use the AWT; Swing and the AWT don't play well together.

The data:

Ring 0:   1  2  3  4  5  6
Ring 1:   1  2  3  4  5  6
Ring 2:   1  2  3  4  5  6
Ring 3:   1  3  3  4  5  6
Ring 4:   2  3  4  2  6  4
Ring 5:   1  5  2  1  5  6

(I may change this data set later.)

What to turn in:

Make a folder to work in. Use Forté to create your program in this folder. When you are ready to submit your assignment, jar the entire folder, including all the files you don't care about but Forté does. Turn your jar file in via Blackboard.

Due date: Midnight, February 7.