Constraint programming is a field that is about solving problems where you have to find a solution in a (usually large) search space given specific constraints. A classic problem of this sort is the eight queens puzzle.

There are quite a few good constraint program libraries, among them are java based Choco and C++ based Gecode.

At first I didn’t understand why such powerful libraries provide the eight queen puzzle as an example that can be solved using constraint programming, as it is trivial to generate all the solutions to the eight queens puzzle with simple DFS. I wrote the following C program to illustrate this (which actually shows all the solutions to the n queen problem using Depth First Search):

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
    int *lines;
    int s,i, currentLine;


    if ( argc != 2 ) {
        printf( "Usage: nqueens <board-size>n" );
        return -1;
    }

    s = atoi( argv[1] );

    if ( s < 1 ) {
        printf( "Board size must be a positive number.n" );
        return -1;
    }

    lines = (int*) malloc( s * sizeof( int ) );

    for ( i=0; i < s; i++ ) {
        lines[ i ] = 0;
    }
    currentLine = 0;

    // begin the DFS
    while ( currentLine > -1 ) {
        while ( lines[ currentLine ]<s && !safe(currentLine, lines) )
            lines[ currentLine ]++;

        if ( lines[ currentLine ] == s ) {
            lines[ currentLine ] = 0;
            currentLine--;
            if ( currentLine > -1 )
                lines[currentLine]++;
            continue;
        }

        if (currentLine == s-1) {
            for (i=0; i<s; i++)
                printf( " %d", lines[ i ] );
            printf("n");
            lines[ currentLine ]++;
            continue;
        }

        currentLine++;
    }

    free( lines );
}

int safe( int currentLine, int* lines ) {
    int i;

    for ( i = currentLine-1; i > -1; i-- ) {
        if ( lines[ currentLine ] == lines[ i ] ||
                abs( lines[currentLine]-lines[i]) == (currentLine-i) )
        {
            return 0;
        }
    }

    return 1;
}

However, when the number of queens grows, the time it takes for the naive DFS method above grows much faster, and getting all the solutions for 30 queens and higher required waiting more time than I had patience for.

I then tested what Choco and Gecode could do with the same problem and was amazed. Both libraries generated results in seconds for 300 queens and higher. Note that each added queen exponentially expands the search space so this is very impressive.