Checker Challenge « Computer programming

Checker Challenge is a very famous programming problem. It’s one of the first examples of backtracking anyone learns and variations of it frequently appare in contests.

In this article, I’ll present the classic algorithm for solving it and then a few optimisations to make it run less like a geriatric turtle.

First the problem:

Given a checker table of n lines and n columns, find all the ways of placing n checker pieces so that no two are on the same line, column or diagonal.

If n is greater or equal to 6 there is always at least one way to arrange the pieces. Usually there are a lot of ways (there are 73712 for n = 13).

For n = 6, this is one of the possible four arrangements:
| | O | | | | | | | | | O | | | | | | | | | O | | O | | | | | | | | | O | | | | | | | | | O | |

First of all, you need a way to memorise the board. A matrix of n x n is the obvious solution, but it’s not really necessary. Notice that there can be at most one piece on any column, so it’s enough to use an array of n, each element containing the number of the row on which the corresponding element in the matrix is located. e.g. For the board above, the array would be {4, 1, 5, 2, 6, 3}.

Now, how do you approach such a problem? The simplest way (and, as it happens, the fastest) is to solve it recursively: first take the first column and attempt to place a piece on each of the n rows; for each of these, attempt to place a piece on each row of the second column; for every valid such arrangement, try to place a piece on each row of the third column; …; and so on until you place a piece on the n^th column, at which point, you have a valid arrangement.

The key point in this algorithm is to know that when you’re working on the k^th column, all the pieces on the first k - 1 columns form a valid arrangement.

As it happens, this is way to slow. For n = 10, I got tired of waiting and stopped the programme. If you do the math, you’ll see that for n, this algorithm does about nⁿ recursive calls. This is bad, but if you write the checking routines inefficiently, you can easily make it slower by a factor of n.

There are three ways I know of to check if a position is valid (i.e. if a piece can be placed there). The first checks for validity after the piece has been placed, while the other two work by marking positions as invalid:

The first is simple: let’s say you’ve reached column c and are wondering whether or not you can place a piece of row r. First take all the columns before c and check whether a piece is already on row r; afterwards, for every column c’ before c, and for every row r’ on that column check if abs(r - r’) = c - c’. If any of there conditions are true, than you can’t place a piece on row r.
The second is just a way of trading memory for speed. Instead of doing as above, keep three vectors of boolean values (1 for the lines (usedRows) and 2 for the two types of diagonals (d1 and d2)), and for every piece you place on the board mark the corresponding elements in the three vectors as used. That is, mark r^th element in rows, the n - c - 1 + r ^th element in d1 and the r + c ^th element in d2. If any of the corresponding elements for any position are marked, than that position is invalid.
The third way is just combining the first two. For every row column c’ before c, supposing the piece is on row r’, mark the rows r’, r’ - (c - c’) and r’ + (c - c’) as invalid.

That’s it. For another speed boost, I use bitsets instead of vectors. Anyway, here’s the code in C (checker.c):


#include <stdio.h>
#include <string.h>

int q[14];

int sol[3][14];

int r = 0,
        d1 = 0,
        d2 = 0;

int solP = 0;

int n;

void gen_sol(int col) {
        if (col == n) {
                if (solP < 3)
                        memcpy(sol[solP], q, sizeof(int) * n);
                ++solP;
                return;
        }

//NOTE Just calculating the non-admisible rows for this col every time is slightly faster than the "keep track of used rows and diagonals" solution
//      int oc = 0;
//      for (int i(0); i < col; ++i) {
//              oc |= 1<<q[i];
//              oc |= 1<<(q[i] - (col - i));
//              oc |= 1<<(q[i] + (col - i));
//      }

        int i;
        for (i = 0; i < n; ++i) {
                if (!(r & 1<<i) && !(d1 & 1<<(n - col - 1 + i)) && !(d2 & 1<<(i + col))) {
                        r |= 1<<i;
                        d1 |= 1<<(n - col - 1 + i);
                        d2 |= 1<<(i + col);

                        q[col] = i;
                        gen_sol(col + 1);

                        r ^= 1<<i;
                        d1 ^= 1<<(n - col - 1 + i);
                        d2 ^= 1<<(i + col);
                }
        }
}

int main(int argc, char *argv[]) {
        n = 6;

        // Every solution's reflection is also a valid solution, so for the first
        // calculate only the first n/2 arrangements.
        int max = n;
        if (6 != n) {
                max = (n + 1) / 2;
        }

        // This complication appears because the odd values of n. Think about
        // it for a while and it will become obvious.
        int temp;
        int i;
        for (i = 0; i < max; ++i) {
                temp = solP;

                r |= 1<<i;
                d1 |= 1<<(n - 1 + i);
                d2 |= 1<<(i);

                q[0] = i;
                gen_sol(1);

                r ^= 1<<i;
                d1 ^= 1<<(n - 1 + i);
                d2 ^= 1<<(i);
        }

        int j;
        for (i = 0; i < 3; ++i) {
                for (j = 0; j < n; ++j)
                        printf("%d ", sol[i][j] + 1);
                printf("\n");
        }

        if ((n % 2 == 0) && (6 < n))
                solP *= 2;
        else if ((n % 2 == 1) && (n > 6))
                solP += temp;
        printf("%d\n", solP);

        return 0;
}

There are a few other optimisations littered throughout the code, but they’re not hard to understand. Good luck. Always open to comments.

P.S. This also is also called “The Queens Problem” or the like.

Checker Challenge

Archived Entry