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.

The problem

The solver is designed to solve constraint satisfaction problems; aka CSPs. These problems are generally expressed by some number of variables with constraints on these variables. Here are a couple of examples of CSPs:

• N-queens problem: for an NxN chess board, how can one position the queens such that none of them are attacking each other? A common way of expressing this as a CSP is to have one variable per column (because having more than one queen per column clearly violates the requirement that queens should not attack each other) and constraints that ensure that no two queens share a row, or a diagonal.

• Sudoku: for a 9x9 grid, how can one fill in the grid with digits from 1 to 9 such that no row, column, or block has the digit appear more than once? A way to model this as a CSP is to have one variable per cell, so 81 variables total, and for each row, horizontal and block an all-different constraint. Sudokus can also be generalized to NxN grids; e.g., 25x25 sudoku has cells which can be filled in with a value between 1 and 25 and 25 rows, columns, and blocks.

The solver

There are a few different kinds of solvers for CSPs, the kind I have built is a constructive solver which has the ability to enumerate all solutions to a CSP, and similarly, guarantee that no solutions exist when that is the case. Here’s a quick rundown in bullet-form of how it works:

• The core algorithm is building a tree that searches for a solution by making decisions, and after making a decision seeing if a solution still exists.
• A decision is basically of the form “I think I can put the first queen on row #2”. Once a decision is made it holds until the solver either finds a solution that includes that decision, or proves that no solution exists with that decision.
• When the solver does learn that no solutions exist based on an earlier decision, it backtracks; i.e., undoes that decision.
• This algorithm will thus try all possibilities until an answer is found, or no answer is proven to exist.

TL;DR: the algo is basically just DFS (depth first search). Easy peasy, right?

… wait, the number of possible states gets pretty obscene, doesn’t it? Sure does! So how do we have any hope of finding a solution? Well, we’ll need to be smart about how we explore the possible states (aka the search space):

• When making a decision we can be more careful about what that decision is. For example, we may want to pick a queen that only has two possible spots where it won’t be attacked. This is an example of first fail variable ordering heuristic.

• After making a decision, like “first queen goes on row #2”, we can deduce that placing other queens on the same row doesn’t make any sense, and not attempt doing so. This is an example of constraint propagation. Conveniently, this makes it easier for us to choose the next queen (see previous bullet point).

• We can get smart about recovering from failing to find a solution. An example of this is backjumping, where rather than going back to the latest decision, i.e., simply backtracking, we jump further back and skip parts of the search tree that are guaranteed to not have a solution.

I’ll cover these in separate posts, but for now hopefully this gives you an idea how the simplistic-looking DFS algorithm can be extended and handle traversing rather obscene search spaces.

Why it’s hard to build

In short, because the search space is huge, optimization becomes critical. This applies to just about every step of the search process, from efficiently representing the problem and the search state, to efficiently updating the state and auxillary data structures, to quickly and correctly applying the techniques above, like constraint propagation and backjumping. I’ll cover these in more detail later as I intend to write some posts about different kinds of all-different constraints, constraint propagation in general, and backjumping vs backtracking.

Where it is today

The solver runs on an E2 instance in Google Cloud, on freebie quota. As such, there are significant limitations to the CPU and RAM, yet it is still able to easily chew through most 15x15 crosswords and generalized NxN sudokus, up to 36x36 in size. The solver itself also supports finding the best solution and not just any solution, which requires providing an objective function as part of the problem, however this isn’t yet surfaced through the site. An example application would be picking words for a crossword that are more common and avoiding other words, like abbreviations. There are also other, “infrastructural” improvements, which I may get to in the future. I may also look to apply the solver to a new class of problems, but I’m not sure what those will be yet.

With that, I’ll close this post out with a quick plug for my solver for NxN sudoku where you can see that by applying the techniques mentioned here the solver is able to find a solution for a 25x25 sudoku in a couple of seconds. In contrast, with a pure brute-force algorithm, we may need to consider an enormous number of states: $$(25 \times 25) ^ {25} = 7.889 \times 10^{69}$$