Constraint propagation is one of the key mechanisms that allows constructive search to efficiently explore huge search spaces. It does so by applying constraints whenever search state changes to remove parts of search space that cannot contain solutions.

In this post I’ll cover two constraint propagation techniques: forward checking and arc consistency. As these techniques apply to variables’ live domains, I’ll start by defining what that is first, and then dive into constraint propagation itself.

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.

In the previous post I’ve given a quick overview of what the solver is about, and in this post I’ll dive a little bit deeper into the subject, using N-queens with just 4 queens as an example problem. More specifically, I’ll fully specify the problem by defining the variables and constraints, and then walk through what a simple search would do, ultimately finding a solution.

The underlying general purpose solver is the most interesting and most complex part of the backend; it’s also the thing I have now rewritten 3 times for various reasons. So I’m going to talk about that a bit: what it does, why it is interesting and challenging to build, and where it is at today.