CSP solver

As an excercis in minimalism, I tried to implement a simple library for solving Constrained Satisfaction Problems (CSP) in C++ without including any library at all.
A CSP is any problem in which we have some variables with finite domains and we want to find an assignment to those variables such that it satisfies some given constraints. Usually, CSP solvers find a solution by performing a search in the space of partial assignments, until they find a complete one.

Graph coloring is an instance of a CSP. Nodes colors are the variables, possible colors are their domains, the constraints are that adjacent nodes can’t be of the same color.

My simple solver

The implementation of my simple solver can be found here on GitHub.
I ended up including only <stdio.h> for printing, but I still consider this as a success in the “no dependencies” game. As far as features, my solver performs a standard backtrack tree search, with the following heuristics:

These features are what makes the project interesting. Without heuristics the solver would be unusable as it would be orders of magnitude slower.

N-Queens

N-Queens is a classic NP toy-problem in artificial intelligence. The goal is to find an arrangement of N queens on a N x N chessboard so that no two queens threaten each other. With N = 8, this is fun puzzle to solve for a human. For N = 20, it is already beyond the human brain reach.
The simple solver is instead very happy to play with large boards and finds a solution with N = 20 in less than 0.01 seconds. Here’s the solution.

20-Queens example

A solution for the 20-Queens problem, found by my solver

With N = 100 timings are still reasonable, around 20 seconds. No image this time, it’s too ugly.

Sudoku

The game of Sudoku is actually a constraint satisfaction problem waiting to be solved.
In sudoku we have 81 variables (minus initial numbers), each of which has the same domain in theĀ 1 to 9 range. The constraints are the rules of the game: no duplicates in each row, in each column, and in each 3 by 3 square.
This is the result of my solver run on the hardest sudoku I colud find online. The solution is found instantly and it is correct of course. It is a simple test, but it was quite useful while debugging.

Before After
20-Queens example

Memory allocation

Since I chose to cut down on dependecies, I could not use std::vector. This meant that dynamic memory allocation had to be done excplicitely. I took the chance to implement a custom allocator that was well-suited for this very application. Since the solver finds a solution via recursive search in the space of partial assignments, we need to allocate and deallocate a lot of temporary values. This is the classic situation in which the RAII (resource-acquistiono-is- intialization) pradigm performs poorly. So, I implemented a custom stack allocator: a big memory pool is allocated with malloc at the beginning of the program, then, as memory is requested, it is allocated incrementally on the global stack by just returing the pointer of the stack’s head and bumping it foward. Freeing memory is equally simple, you just move back the head of the stack.

The interface is pretty simple. If you want to imitate the behavior of std::vector, the call stack_frame() begins a stack frame, so all the data allocated in this scope or in any sub-scope will be autmatically freed at the end of the scope.

void do_something() {
  stack_frame();
  // The stack_frame() call tells the stack allocator that everything that is allocated after
  // this must be freed at the end of the scope. This is useful for allocating temporary values.
  Array<float> values = allocate(1024, 0.0f);
  
  // do something with values while it is alive...
}

But how do you return allocated resources from functions if they are freed at the end of scopes?
Well, just don’t call stack_frame()! Any data you allocate before the call of stack_frame(), is “owned” by the scope of the caller and will survive the current scope.

Array<int> make_range(int n) {
    // This will be returned.
    Array<int> result = allocate<int>(n);

    // This is temporary.
    stack_frame();
    Array<int> ones = allocate<int>(n, 1);
    for (int i = 1; i < n; i++) result[i] = result[i-1] + ones[i];

    return result;
}

When, on a first implementation, I swapped std::vector with this custom allocator I got a 2x speedup on large problems. This is not surprising: with many recursive calls, the program was spending more time in malloc and free than in doing actual work.

Procedurally generated content

A nice application of CSP solvers is in procedurally generated content for videogames.
An increasingly popular method in this field is the so called Wave Function Collapse algorithm. While it is marketed as insipired by quantum physics, the WFC algorithm is actually the solution of a CSP. The variables are the tile types and their rotations, the constraints are rules for adjacent tiles, which are deduced from the example image. The the CSP is solved for the required grid of tiles.
WFC-like approaches are not limited to grid domains, any adjacency structure will work.

20-Queens example
The WFC algorithm is actually a CSP.