CIS 554 Color Grid
Fall 2016, David Matuszek

Purposes of this assignment

General idea

You have a set of N colors, and are given not more than N "color bars," All color bars are the same length, and each bar may have duplicated or omitted colors. 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.

Your task is to write a function solve that takes as a parameter a list of lists of colors, each sublist representing one color bar. Colors may be represented by integers, strings or symbols (such as :red). The goal is to rotate each color bar until no column contains duplicate colors. For example, if there are five color bars, each column should have five different colors in it.

Write a separate function to print the solution. The solve function should not do any printing.


In this example, colors are represented by the numbers 0 through 4. A puzzle might be given as

( (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) )
This is how this particular puzzle might be visualized:


There must be at least as many colors as rows, though there may be more. Your task is to rotate each color bar until no column contains more than one of any color.

This can be written as a 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.

Print the solution, or if no solution is possible, print a statement to that effect.

Keep all functions small, and unit test all functions that don't do input or output.

Due date

Turn in your program by 6am, Tuesday, October 4. As always, only files submitted to Canvas will be accepted. I do not accept assignments submitted by email.