## IPSC 1999

## Solution to Problem A – Billboard

The problem can be easily transformed to the terms of graph theory. The
crossings of streets will be **nodes** of our graph and streets will
be **edges**. The problem is to assign numbers 1,2,3 to the nodes so
that no edge connects to nodes with the same number. In graph theory such
assignment is called **coloring** of a graph. Therefore we will call
numbers 1,2,3 colors.

Both input files for this problem contained only graphs that had
coloring with 3 colors. Here we provide output files for both input files
(note that these output files are not unique!) as well as
a program that produced these output files.

Our program is uses classical exhaustive search, that tries to assign
recursively all possible colors to all nodes. However there are too many
assignments of colors and most of them turn out to be incorrect.
Our program tries to eliminate incorrect colorings as soon as possible.
Thus, it runs quite fast for both input files A1 and A2.

Program keeps for each node a list of colors that can be assigned to
this node. At the start this list contains all three colors. Each time program
assigns some color to some node, it removes this color from list of
options of neighbouring nodes. At each stage of computation the list of
options for given node contains only such colors that no neighbour of this
node has assigned such color. When we try to assign a color to a node we
use only colors from its list of options.

After assigning a color to a node and performing necessary
changes to lists of options, program needs to choose to which node it will
try to assign color in the next step. We again use lists of options and we
choose such a node that has the smallest number of options. This strategy
helps us to reduce running time substantially. For example if some node has
an empty list of options, it means that our current coloring cannot be
extended to all nodes and we do not need to continue. If some node has only
one option it can be directly assigned to it. Both these cases are handled
naturally if we choose as a next node the node with the smallest number
of options.