# CSCE 782: Problem Set 1

## Due: Monday, 8 February 2010 @10am

### Email me your .nlogo file.

### Asynchronous Backtracking

You will implement the ABT algorithm as shown in the book and
explained in class. Your implementation must have the following features:

- The
*setup* button will generate a random graph. Let the
user choose the number of nodes, the ratio of edges to nodes, and the
number of colors. In a
random graph every edge is created between 2 randomly chosen
nodes. Can you create a graph that is guaranteed to have a coloring?
- The
*layout* button will layout the graph, making it look
pretty.
- The
*go* buttons will let the user step thru the execution
of the algorithm.

### Programming Tips

You will need to implement a message queue on each node. At each step
of the simulation the agents will fetch the first message from this
queue and handle it, possibly placing messages at the end of other
agents' queues as a result.

You do not need to implement a full hyper-resolution rule for all
pairs. At minimum, you can just use the complete local-view as the
nogood. But, if you want to explore with better no-good generators, by
all means, be my guest! Note that, since you are not generating all
possible no-goods your algorithm will, therefore, not be
*complete*, so it might fail to find solutions when they
exist.

José M. Vidal
Last modified: Mon Jan 25 09:00:12 EST 2010