Constraint Propagation

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.

Solver basics

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.

Solver intro

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.

Why tho

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.