CIT 594 Assignment 8: Backtracking
Spring 2011, David Matuszek

Purposes:

• To teach backtracking.

General Idea:

You are given a set of` N `"color bars," each bar containing `N` colors (`3 <= N <= 12`). The colors on a color bar can be changed by rotating them one step to the right, end around: For example, `Red-Yellow-Green-Blue` can be rotated to `Blue-Red-Yellow-Green`.

• Read in some color bars, one per line. Colors will be represented by the integers `0` through `11`.
• Display these colors in an `NxN` grid.
• Rotate the color bars until every column contains every color, and no column contains the same color more than once.

Details:

Ask the user for a file, then read in the initial color bars from that file. One line of the file will represent one color bar, and each line will contain numbers representing the colors on that color bar. For example, for `N = 5`, the input might be:

```3 4 1 0 2
3 1 2 4 0
4 0 3 2 1
3 1 2 4 0
3 1 0 2 4```

(You can assign colors to the numbers any way you like.)

Hint: The easy way to read in these numbers is to use the String methods `trim()` and `split("\\s+")` and the Integer method `parseInt(s)`.

Display these colors in a grid. For example,

Your task is to rotate each color bar until no column contains more than one of any color. Display your work as you go.

Algorithm:

This is a simple (yes, simple!) backtracking program. Starting from the top, rotate each color bar until there no conflicts (duplicate colors) with any of the color bars above it. If that isn't possible, backtrack to the color bar above, and rotate it some more. Continue until all color bars are in the correct place.

If no solution is possible, display a message dialog to say so.

After each problem, allow the user to either read in another data file, or quit.

Supplied code:

ColorBar.java

The constructor `ColorBar(Color[] colors)` returns a JPanel containing buttons of those colors, arranged horizontally.

The `resetColors()` method uses the same array as was previously given in the constructor, and changes the button colors and text to match the new arrangement of colors. A separate Thread is used to provide a one-second delay between color changes.

ColorBarExample.java

The `main` method simply displays a single `ColorBar` in a JFrame, then shuffles the colors and calls `resetColors()` several times. This is a throwaway class whose only purpose is to give an example of the use of the `ColorBar` class.

Due date:

Turn your assignment in to Blackboard before 6AM Monday, March 21 Wednesday, March 23.