Gary Fredericks
Generates and solves graph coloring problems using ABT.
I used simple integers to represent node values, corresponding to the indexes in the built-in base-colors array. So in a 3-color graph, the values will be the numbers [0,1,2], and they will refer to the corresponding colors in the base-colors array.
Priorities are implemented by who number, with lower numbers having lower priorities.
The program as written always generates solvable graphs. It does this by
1) Generating the specified number of turtles
2) Assigning random colors to each turtle (from the specified number of colors)
3) Generating legal links until either the links-to-nodes ratio has been reached, or no legal links can be generated. In the latter case, a warning is written to the console.
I implemented two no-good generators. The first, which is used by default, is the naive generator which uses the local view. I also tried to create a hyperresolution generator, but my simple implementation would just concatenate all of the previously generated nogoods (filtering out the elements referring to self), which certainly isn't sufficient to solve the problem, and may also be worse than the local-view version (it also generates tautological nogoods most of the time, i.e. NOT(TURTLE1(A) ^ TURTLE1(B) ^ ...)). If I had time, I think I would enjoy trying to do hyperresolution properly.
1) I used the table extension for the local-view datastructure, with the who-numbers for keys.
2) A single nogood is represented as a list of pairs, where [[1 3] [2 4]] means that "turtle 1 having value 3 and turtle 2 having value 4" is no-good.
3) Despite using who-numbers for local-view and no-goods, I implemented "naybors" as a list of turtles. Could've gone either way I guess.
20100623