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.