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.

What and why?

First, the what: Dawn of the Dad is basically the 2 solvers: one for sudoku, and another for building crosswords. The first is largely complete, so most of my time now is dedicated to beefing up the crossword builder.

Now the why: why build the site and why ramble in this blog?

• The site is my excuse to write some code, both to stay sharp and because I like doing it, solve some algorithmically interesting problems, and revisit some of the neat things I’ve learned about back in grad school. Originally, this spun off as a yet-another-rewrite of a general-purpose CSP solver, which then led to adding fairly ad hoc visualization, which led to building a web server, hacking up a websocket protocol, glueing it all together and finally hosting it on Google Cloud.