Search Algo in Go

My previous couple of posts talked about what the solver does (solves CSPs), how to model a problem as a CSP, and how the search tree is built as the solver searches for a solution. In this post I will expand on the details of search by outlining the key data structures and bits of code. The backend is written in Go lang, and so are all of the code snippets here.

Nodes in the search tree

We’ll be building a search tree, which is composed of nodes. We’ll also need to track a couple of things as we build the search tree. Here they are:

 1type nodeState int
 2const (
 3  freshNode nodeState = iota
 4  solutionFound
 5  assignmentTried
 6  unassignmentTried
 7)
 8
 9type decision struct {
10  variable *model.Variable
11  value    int
12  // When valueAssigned is true variable = value, else variable != value.
13  valueAssigned bool
14}
15
16type node struct {
17  parent      *node // nil at root
18  state       nodeState
19  decision    *decision
20}

The node struct above lets us:

• Keep track of the node’s parent, so we can easily go back up the tree when backtracking,
• Keep track of the nodeState, which we’ll use to tell us what to do when we visit or revisit a node,
• Keep track of the decision we made at this node, which we can use to evaluate constraints, and, when all variables are assigned, to tell us what the full solution is, by walking backwards up the tree and collapsing all the decisions that led to the solution into a full assignment of values to variables.

Building the search tree

My code has two key functions: Run(), which is the top-level function called by external clients, like the web server, and step(), which is a single step in the search tree where we look at the current node.state and decide what to do next. Here they are, along with the Search struct that they belong to:

 1type Search struct {
 2  root *node
 3  current *node
 4}
 5
 6func (s *Search) Run() *Solution {
 7  for {
 8    done, solution := s.step()
 9    if done {
10      return solution
11    }
12  }
13}
14
15func (s *Search) step() (bool, *Solution) {
16  switch s.current.state {
17  case freshNode:
18    s.current.decision = s.makeNextDecision()
19    if s.current.decision == nil {
20      // When there are no more variables to assign s.makeNextDecision()
21      // returns nil. That also means that all variables are assigned
22      // and we found a solution.
23      s.current.state = solutionFound
24      return true, s.Assignments()
25    }
26
27    s.current.decision.variable.Set(s.current.decision.value)
28    if !s.checkConstraints() {
29      return false, nil
30    }
31
32    s.current.state = assignmentTried
33    s.current = &node{parent: s.current}
34  case solutionFound:
35    // We can get here if we're resuming from a previous solution.
36    // We'll resume by backtracking out of this node.
37    s.current = s.current.parent
38  case assignmentTried:
39    s.undoLastStep()
40
41    s.current.decision.valueAssigned = false
42    s.current.decision.variable.Prune(s.current.decision.value)
43    if !s.checkConstraints() {
44      return false, nil
45    }
46
47    s.current.state = unassignmentTried
48    s.current = &node{parent: s.current}
49  case unassignmentTried:
50    if s.current == s.root {
51      // We exhausted the search space, no solutions are left.
52      return true, nil
53    }
54    s.undoLastStep()
55    s.current = s.current.parent
56    return false, nil
57  }
58  return false, nil
59}

As you can see, Run() is exceptionally straight-forward - it simply keeps calling step() until step() says it is done, which happens either because a solution has been found, or the entire search space has been exhausted, and no more solutions as exist.

On the other hand, step() is a bit more complicated - it looks at the state that the current node is in and:

• For freshNode search makes a decision; if that’s nil then we have a solution. Otherwise, we assign the variable, check constraints, and if no constraints are violated, create a child node and move into it. If at least one constraint is violated no solution can be found in this branch and we will need to try the other branch, relying on Run() to enter assignmentTried on next step.
• For solutionFound - this state will be entered when Run() is called again after finding a solution. In this case search simply backtracks, so that search can continue to the next solution.
• For assignmentTried search flips the assignment to unassignment (e.g., if the assignment was A = 5 it’ll become A ≠ 5). This is where the binary nature of the search tree comes from, that I mentioned in my other posts. Search will then prune the unassigned value from the variable’s live domain, and check if any constraints are broken (we’ll talk about live domains in another post, for now just think of this as removing this value as a possibility for the subtree rooted at the current node). If no constraints are broken search will traverse deeper into the search tree, otherwise no solution can be found and step() will return, relying on Run() to trigger a backtrack on the next step.
• For unassignmentTried search knows that at this point no more solutions can be found in the current subtree and it needs to backtrack. If search detects that it is already at the root node, that means it has nowhere to backtrack to and there are no more solutions at all.

And that’s the heart of the constructive search algorithm. A few important things are left out for now though, which make what is essentially just DFS effective. I’ll cover these later, but I will touch on them briefly here:

• Applying constraint propagation after making decisions, rather than simply checking constraints, and tracking results of propagation, so that they may be retracted upon backtracking. This will allow search to quickly eliminate parts of search space that are guaranteed to not contain solutions.
• Heuristics and decision making in general are alluded to with s.makeNextDecision(), but not fleshed out. This part delegates the heavy lifting to the variable and value ordering heuristics, and while those can be as simple as lexicographic, can get relatively sophisticated.
• Supporting backjumping rather than just simple backtracking.