# Strategies for solving problems involving searches

As an example of a search-oriented problem, consider finding all constrained $n$-colorings of a graph. An "$n$-coloring" associates one of $n \ge 1$ colors to each vertex in such a way that no edge connects vertices of the same color. A "constrained" coloring requires that certain vertices have certain fixed colors.

For instance, here is a graph with one of its vertices already colored red; the default (cyan) vertices are as yet uncolored: There are 10 ways to color this graph using three colors; say, {red, green, blue}, while keeping the red vertex red: (Notice that the colorings are not up to isomorphism: all six vertices are considered to be distinct and not interchangeable.)

These solutions are found with a brute-force recursive search. The approach exemplifies a large class of problems, such as playing games and solving puzzles. In most interesting cases the search can take a long time (and have a large amount of output), so it is important to find appropriate data structures and efficient search methods. I am interested in Mathematica-specific advice and strategies for making such searches efficient.

To make this question clearer and more focused, I invite your critical comments concerning this particular solution to the constrained $n$-coloring problem:

constrainedColorings[graph[vertices_, nbrhds_], colors_List, start_List] := Module[
{unassigned, v, candidates},
unassigned = Complement[vertices, start[[All, 1]]];
If[unassigned == {}, Return[start]];
v = First[unassigned];
candidates = Complement[colors, v /. nbrhds /. start];
Map[constrainedColorings[graph[vertices, nbrhds], colors, Append[start, v -> #]] &, candidates]
];


Its arguments are

• graph, which contains a list of the vertices and a list of rules assigning to each vertex the set of its immediate neighbors in the graph;

• colors, which is a list of the available colors; and

• start, which is a (possibly empty) list of rules assigning vertices to colors: it stipulates any constraints. It is expected that the colors appearing in start are contained within colors.

Its output is a deeply nested list (representing the search tree) whose leaves are lists of rules assigning colors to vertices.

Like most such searches, it follows a familiar logic:

1. Determine whether the search is finished.

2. If not, make a list of possible next moves (candidates),

3. ... and tentatively make each move in turn, recursively searching for all solutions arising from it.

4. Return a set of all solutions found.

To illustrate its use, consider the preceding example. It started out as a Mathematica Graph (in order to exploit its graph visualization capabilities) and was converted into a more convenient graph structure for this search:

\[Gamma] = Graph[{v1, v2, v3, v4, v5},
{v1 \[UndirectedEdge] v2, v1 \[UndirectedEdge] v4, v1 \[UndirectedEdge] v5,
v2 \[UndirectedEdge] v3, v3 \[UndirectedEdge] v4, v3 \[UndirectedEdge] v5},
VertexShapeFunction -> "Circle", VertexSize -> 0.4];
g = graph[VertexList[\[Gamma]], # -> Cases[EdgeList[\[Gamma]],
# \[UndirectedEdge] v_ | v_ \[UndirectedEdge] # -> v] & /@ VertexList[\[Gamma]]];


Here is the search itself, whereby the available colors are stipulated and the initial constraints are provided:

colorings = constrainedColorings[g, {Red, Green, Blue}, {v5 -> Red}];


We can flatten the output to get a list of all solutions:

colorings /. x : List[_Rule ..] :> coloring @@ x // Flatten


If you care to play with this code, you will want to draw the output:

display[g_Graph, c_coloring] :=  HighlightGraph[g, List @@ c /. Rule -> Style];
display[\[Gamma], #] & /@ colorings


Here, then, is the specific question:

• In what ways can this code be improved to be faster, simpler, and more flexible?

I am especially interested in advice that would apply not just to this particular problem but to the entire class of problems. What kinds of data structures should one prefer to represent combinatorial objects: arrays, rules, something else? Or perhaps there is no general answer? Are there ways to expedite such searches, such as (possibly) exploiting Mathematica's built-in graph programming capabilities?

General replies are fine and so are answers that specifically improve the code here, provided it is clear how such improvements could be applied more generally.

• Happy first question – Rojo Feb 6 '13 at 17:56
• Makes me wonder if I learned something from this – Rojo Feb 6 '13 at 18:01
• @Rojo Me too (meaning myself here :-)) – Leonid Shifrin Feb 6 '13 at 18:06
• Maybe you could add "enumeration" to the title if you mean "find all" type of problems. Unfortunately, there are good reasons to believe that most problems of this type simply don't have an efficient solution. But it's still an interesting question to ask how to implement a non-polynomial complexity or brute force algorithm in an efficient way in Mathematica. Do you have the Combinatorica book? It's a very interesting read because it explains both the maths and the implementations. – Szabolcs Feb 11 '13 at 21:09
• I'm still reading it, so I can offer little concrete advice, but the section on Pólya theory might be of some use to you. Please email me if you're interested. – Szabolcs Feb 11 '13 at 21:10

## 1 Answer

One can also go about this using integer linear programming, with an array of 0-1 variables indexed by vertices and colors. Here is one encoding of that approach.

constrainedColorings2[graph[vertices_, nbrhds_], colors_List,
start_List, v_] := Module[
{unassigned, nv = Length[vertices], nc = Length[colors], vars,
fvars, c1, c2, c3, c4, pos1, pos2, constraints, solns},
vars = Array[v, {nv, nc}];
fvars = Flatten[vars];
c1 = Map[0 <= # <= 1 &, fvars];
c2 = Map[Total[#] == 1 &, vars];
c3 = Map[Table[
pos1 = Position[vertices, #[]][[1, 1]];
pos2 = Position[vertices, #[[2, j]]][[1, 1]];
v[pos1, k] + v[pos2, k] <= 1, {k, nc}, {j, Length[#[]]}] &,
nbrhds];
c4 = Map[(pos1 = Position[vertices, #[]][[1, 1]];
pos2 = Position[colors, #[]][[1, 1]];
v[pos1, pos2] == 1
) &, start];
constraints = Flatten[Join[c1, c2, c3, c4]];
solns = Solve[constraints, fvars, Integers];
Map[Thread[vertices -> ((vars /. #).colors)] &, solns]
]


Your example, slightly altered (I'm not getting the graphing right and don't have time for that now) looks like this.

c2 =
constrainedColorings2[g, {rRed, gGreen, bBlue}, {v5 -> rRed}, v]

(* Out= {{v1 -> bBlue, v2 -> gGreen, v3 -> bBlue, v4 -> gGreen,
v5 -> rRed}, {v1 -> bBlue, v2 -> gGreen, v3 -> bBlue, v4 -> rRed,
v5 -> rRed}, {v1 -> bBlue, v2 -> rRed, v3 -> bBlue, v4 -> gGreen,
v5 -> rRed}, {v1 -> bBlue, v2 -> rRed, v3 -> bBlue, v4 -> rRed,
v5 -> rRed}, {v1 -> bBlue, v2 -> rRed, v3 -> gGreen, v4 -> rRed,
v5 -> rRed}, {v1 -> gGreen, v2 -> bBlue, v3 -> gGreen, v4 -> bBlue,
v5 -> rRed}, {v1 -> gGreen, v2 -> bBlue, v3 -> gGreen, v4 -> rRed,
v5 -> rRed}, {v1 -> gGreen, v2 -> rRed, v3 -> bBlue, v4 -> rRed,
v5 -> rRed}, {v1 -> gGreen, v2 -> rRed, v3 -> gGreen, v4 -> bBlue,
v5 -> rRed}, {v1 -> gGreen, v2 -> rRed, v3 -> gGreen, v4 -> rRed,
v5 -> rRed}} *)

• +1 Linear programming is a good idea (I have used it in some of my own answers; cf mathematica.stackexchange.com/questions/6822/tiling-a-square/…). However, I wonder whether Solve and its kin are up to producing all solutions when the number starts getting large. I also suspect that once we get beyond the domain of toy examples, Solve might bog down and take a very long time. LinearProgramming can be fast but I don't expect it to return more than a single solution. – whuber Feb 6 '13 at 19:53
• Solve will use integer linear programming under the hood for this. I believe it will return all solutions. For large problems it certainly might take approximately forever to do so. In such cases I would write an explicit branching loop and use approximate rather than exact linear programming. That's not foolproof but works well in practice and can be significantly faster than Solve (which uses exact LP). – Daniel Lichtblau Feb 6 '13 at 20:04
• That tiling was a neat problem, by the way. Not sure how I missed it last summer. As for getting more solutions, you can set up a stack of problems with added constraints, and pop from the stack until it is exhausted (or you are). The new constraints are what keeps it from repeating solutions. You can get an example of such a stack and usage here e.g. slide 18 of the talk notebook. – Daniel Lichtblau Feb 6 '13 at 20:11
• Very nice paper--worth a lot of thought. Thanks. – whuber Feb 6 '13 at 20:21