downloadable math-based puzzle

here's a thang at http://vispo.com/software called CoLoRaTiOn i did back in the mid nineties
that *some* might enjoy. It's a puzzle/game , not a 'work of art'. it grew out of a
collaboration with Mike Fellows, a mathematician/computer scientist. we'd get together over
beers and dream up puzzles and games based on the mathematics of computer science, which is
quite visual in its structures. Mike would dream up the puzzles and i'd work on the playability
and the funness and so on. it was important to him to not just come up with puzzles but have
them key on unsolved problems. we dreamed up about 30 puzzles, but this is the only one i've
programmed.

the goal of CoLoRaTiOn is to 'properly color' the graph presented to you. in comp sci, a 'graph'
is just a collection of vertices (squares, here) and lines that join the vertices. a graph is
'properly colored' when no two joined vertices have the same color.

CoLoRaTiOn can be played by kids, but the underlying math issues go a bit deeper than all but
the most precocious of kids could deal with.

if i recall correctly, the problem of properly coloring a graph is considered 'intractable', ie,
the number of moves you have to make increases exponentially as the number of vertices
increases. but there can be heuristics that accomplish the task much quicker in most cases, or
within a certain range of vertices.

my own experience of playing CoLoRaTiOn indicated that at least for the graphs in CoLoRaTiOn (it
generates any graph on 4 to 16 vertices) the job can be done much quicker, which led me to
figure out a 'par' value you try to reach, ie, you have a definite number of moves to color the
graph in, and advance to the next level when you do this.

so the 'par' value and the way CoLoRaTiOn keeps track of the number of moves you make is meant
to encourage you to come up with an algorithm (or a range of algorithms) that let you properly
color the graphs.

For the mathematically demanding denizens of rhizome raw, below is the function I wrote (in
Delphi 2) to establish par. basically what it says is that if you can see the lines, par is
equal to the number of vertices, whereas in the mode where you can't see the lines, par is
max(NumberOfEdges, 2*NumberOfVertices) + (NumberOfVertices/2) which is *way* not exponential in
the number of vertices.

function ParFunc: Integer;
{This function establishes par. It has been programmed via trial and error.}
begin
If L1ShowEdges then
ParFunc:= L1NumOfVertices
{If the player is in Show Edges mode, then s/he should be able to color all
the vertices without any recoloring of vertices, i.e., color each vertex
once and only once.}
else
begin
If (L1NumOfVertices = 12) and (gNumOfColors = 3) then
Parfunc:= 33
else
begin
Parfunc:= ReturnMax(gNumOfEdges, 2*L1NumOfVertices);
if (L1NumOfVertices > 9) and (L1NumOfVertices <15) then
ParFunc:= ReturnMax(gNumOfEdges, 2*L1NumOfVertices) + (L1NumOfVertices div 2);
end;
end;
end;

The unsolved question involved here, if i recall correctly, is to come up with algorithms that
are not exponential in the number of vertices. It is apparently impossible to construct such
algorithms for n vertices and y lines. I've done this myself and you might also concerning the
graphs generated by CoLoRaTiOn. The graphs can be any graph on 4 to 16 vertices that requires 2
or 3 or 4 colors. The paint pot tells you how many colors you need to color a given graph. If
there are four colors in the paint pot, for instance, you need four colors to color it.

And how do your algorithms generalize to larger graphs and graphs requiring different numbers of
colors to properly color them?

Like I said, it might interest *some* :)

ja