Eight queens puzzle (C)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C | Erlang | Forth | J | Scala

The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens problem places n queens on an n×n chessboard.

We present a few different solutions to the general n queens puzzle in C.

Contents

[edit] Brute force search

In this obvious but very slow solution, we simply consider all possible places on the board where the n queens could go, rejecting any that don't satisfy the conditions, including the implicit condition that no two queens occupy the same square. For eight queens, this solution considers 648 or 281 474 976 710 656 different solutions, of which only 92 are valid.

Rather than represent the board explicitly, we store the row and column number of each queen, between 0 and n − 1, in two arrays:

<<allocate data structures>>=
int* queen_rows = (int*)calloc(n, sizeof(int));
int* queen_cols = (int*)calloc(n, sizeof(int));

<<deallocate data structures>>=
free(queen_rows);
free(queen_cols);

Because we use calloc(), all queens start at row 0, column 0, or the upper-left corner of the board. The call to calloc() requires a header file:

<<header files>>=
#include <stdlib.h>   /* calloc() */

We can test the current position to see if it is valid by examining each pair of two different queens and making sure they are in different places and do not attack one another (the inner counter starts at queen_num_1 + 1 to ensure each pair of queens is visited only once):

<<variable declarations>>=
int queen_num_1, queen_num_2;
int is_valid;

<<verify current position>>=
is_valid = 1; /* Assume initially is valid, search for disproof */
for(queen_num_1=0; is_valid && queen_num_1 < n; queen_num_1++) {
    for(queen_num_2=queen_num_1 + 1; is_valid && queen_num_2 < n; queen_num_2++) {
        if (queen_rows[queen_num_1] == queen_rows[queen_num_2] ||
            queen_cols[queen_num_1] == queen_cols[queen_num_2] ||
            queens are on same diagonal)
        {
            is_valid = 0;
        }
    }
}
if (is_valid) {
    print out current position
}

There are two ways two queens could be on the same diagonal: in the first, the difference of their rows equals the difference of their columns, and the diagonal goes from upper-left to lower-right:

Q . . .
. . . .
. . Q .
. . . .

The other is that the difference of the rows is the negative of the difference of the columns, and the diagonal goes from upper-right to lower-left:

. . Q .
. . . .
Q . . .
. . . .
<<queens are on same diagonal>>=
queen_rows[queen_num_1] - queen_rows[queen_num_2] ==
  queen_cols[queen_num_1] - queen_cols[queen_num_2] ||
queen_rows[queen_num_1] - queen_rows[queen_num_2] ==
  -(queen_cols[queen_num_1] - queen_cols[queen_num_2])

To print out a position, we simply print the position of each queen:

<<variable declarations>>=
int queen_num;
<<print out current position>>=
for(queen_num=0; queen_num < n; queen_num++) {
    printf("(%d,%d) ", queen_rows[queen_num], queen_cols[queen_num]);
}
printf("\n");

I/O requires a header file:

<<header files>>=
#include <stdio.h>

To iterate through all the permutations, we move the very last queen one column to the right. If this puts it off the right side, we bring it down to the first column of the next row. If this puts it off the bottom side, we put it back in the top-left corner and move the previous queen forward one in the same manner. Finally, if the first queen moves off the board, we're done:

<<move to next position>>=
for(queen_num = n-1; queen_num >= 0; queen_num--) {
    queen_cols[queen_num]++;
    if (queen_cols[queen_num] >= n) {
        queen_cols[queen_num] = 0;
        queen_rows[queen_num]++;
    }
    if (queen_rows[queen_num] >= n) {
        queen_rows[queen_num] = queen_cols[queen_num] = 0;
    } else {
        break;
    }
}
if (queen_num < 0) {
    deallocate data structures
    return;
}

We put it all together with a simple test driver taking n on the command line to get our first implementation:

<<brute_force_search_queens.c>>=
header files

void search_for_queens_solutions(int n) {
    variable declarations
    allocate data structures
    while(1) {
        verify current position
        move to next position
    }
}

int main(int argc, char* argv[]) {
    search_for_queens_solutions(atoi(argv[1]));
    return 0;
}

The program produces many outputs for each possible solution, each placing the queens in a different order, although order is irrelevant. For example, here is the output for the 4 queens problem, showing 24 ways of arranging each of the 2 possible solutions:

(0,1) (1,3) (2,0) (3,2) <-- solution 1
(0,1) (1,3) (3,2) (2,0)
(0,1) (2,0) (1,3) (3,2)
(0,1) (2,0) (3,2) (1,3)
(0,1) (3,2) (1,3) (2,0)
(0,1) (3,2) (2,0) (1,3)
(0,2) (1,0) (2,3) (3,1) <-- solution 2
(0,2) (1,0) (3,1) (2,3)
(0,2) (2,3) (1,0) (3,1)
(0,2) (2,3) (3,1) (1,0)
(0,2) (3,1) (1,0) (2,3)
(0,2) (3,1) (2,3) (1,0)
(1,0) (0,2) (2,3) (3,1)
(1,0) (0,2) (3,1) (2,3)
(1,0) (2,3) (0,2) (3,1)
(1,0) (2,3) (3,1) (0,2)
(1,0) (3,1) (0,2) (2,3)
(1,0) (3,1) (2,3) (0,2)
(1,3) (0,1) (2,0) (3,2)
(1,3) (0,1) (3,2) (2,0)
(1,3) (2,0) (0,1) (3,2)
(1,3) (2,0) (3,2) (0,1)
(1,3) (3,2) (0,1) (2,0)
(1,3) (3,2) (2,0) (0,1)
(2,0) (0,1) (1,3) (3,2)
(2,0) (0,1) (3,2) (1,3)
(2,0) (1,3) (0,1) (3,2)
(2,0) (1,3) (3,2) (0,1)
(2,0) (3,2) (0,1) (1,3)
(2,0) (3,2) (1,3) (0,1)
(2,3) (0,2) (1,0) (3,1)
(2,3) (0,2) (3,1) (1,0)
(2,3) (1,0) (0,2) (3,1)
(2,3) (1,0) (3,1) (0,2)
(2,3) (3,1) (0,2) (1,0)
(2,3) (3,1) (1,0) (0,2)
(3,1) (0,2) (1,0) (2,3)
(3,1) (0,2) (2,3) (1,0)
(3,1) (1,0) (0,2) (2,3)
(3,1) (1,0) (2,3) (0,2)
(3,1) (2,3) (0,2) (1,0)
(3,1) (2,3) (1,0) (0,2)
(3,2) (0,1) (1,3) (2,0)
(3,2) (0,1) (2,0) (1,3)
(3,2) (1,3) (0,1) (2,0)
(3,2) (1,3) (2,0) (0,1)
(3,2) (2,0) (0,1) (1,3)
(3,2) (2,0) (1,3) (0,1)

[edit] Combination brute force search

A number of improvements can be made to this very simple search. The simplest is that we can change our iteration step so that the queens never occupy the same square and are always in order from left to right and top to bottom. Since the order of the queens doesn't matter, this still covers all possibilities but avoids duplicated effort. To do this, we start with the n queens occupying the n distinct columns of the first row:

<<combinations: set up initial queens position>>=
for(queen_num=0; queen_num < n; queen_num++) {
    queen_rows[queen_num] = 0;
    queen_cols[queen_num] = queen_num;
}

When resetting a queen that has passed off the bottom of the board, it is placed in the position after the previous queen, after the previous queen has itself been moved. This ensures that the queens remain in order:

<<combinations: move to next position>>=
for(queen_num = n-1; queen_num >= 0; queen_num--) {
    queen_cols[queen_num]++;
    if (queen_cols[queen_num] >= n) {
        queen_cols[queen_num] = 0;
        queen_rows[queen_num]++;
    }
    /* This condition makes sure there is room for all following queens */
    if (queen_rows[queen_num] < n - 1 ||
        (queen_rows[queen_num] == n - 1 && queen_cols[queen_num] <= queen_num))
    {
        for(queen_num_2 = queen_num + 1; queen_num_2 < n; queen_num_2++) {
            queen_cols[queen_num_2] = queen_cols[queen_num_2 - 1] + 1;
            if (queen_cols[queen_num_2] < n) {
                queen_rows[queen_num_2] = queen_rows[queen_num_2 - 1];
            } else {
                queen_cols[queen_num_2] = 0;
                queen_rows[queen_num_2] = queen_rows[queen_num_2 - 1] + 1;
            }
        }
        break;
    }
}
if (queen_num < 0) {
    deallocate data structures
    return;
}

The result of this normalization is that in the 8 queen case, we only examine 64C8 or 4 426 165 368 solutions, about 63 000 times less, and moreover the output shows only different solutions, not reorderings (although it still separately shows solutions which are reflections or rotations of one another). Here is our new test main and example output:

<<combination_brute_force_search_queens.c>>=
header files

void search_for_queens_solutions(int n) {
    variable declarations
    allocate data structures
    combinations: set up initial queens position
    while(1) {
        verify current position
        combinations: move to next position
    }
}

int main(int argc, char* argv[]) {
    search_for_queens_solutions(atoi(argv[1]));
    return 0;
}

Sample output for 4 and 5 queens:

$ ./combination_brute_force_search_queens 4
(0,1) (1,3) (2,0) (3,2)
(0,2) (1,0) (2,3) (3,1)

$ ./combination_brute_force_search_queens 5
(0,0) (1,2) (2,4) (3,1) (4,3)
(0,0) (1,3) (2,1) (3,4) (4,2)
(0,1) (1,3) (2,0) (3,2) (4,4)
(0,1) (1,4) (2,2) (3,0) (4,3)
(0,2) (1,0) (2,3) (3,1) (4,4)
(0,2) (1,4) (2,1) (3,3) (4,0)
(0,3) (1,0) (2,2) (3,4) (4,1)
(0,3) (1,1) (2,4) (3,2) (4,0)
(0,4) (1,1) (2,3) (3,0) (4,2)
(0,4) (1,2) (2,0) (3,3) (4,1)

[edit] One queen per row

The above search based on combinations is much faster than the initial brute force solution: when compiled with "gcc -O3" under Ubuntu Linux on a 2.4 GHz CPU, it finds all 92 solutions to the 8 queens problem in 2 minutes and 8 seconds. However, we can do much better by observing that it's possible to avoid even examining the solutions in which queens appear in the same row. The nth queen must appear in the nth row, since there are only n rows and none can contain more than one queen. We start each queen at the beginning of its row:

<<one queen per row: set up initial queens position>>=
for(queen_num=0; queen_num < n; queen_num++) {
    queen_rows[queen_num] = queen_num;
    queen_cols[queen_num] = 0;
}

Iteration is particular simple. We move the queen to the right along its row, and if it moves off the end we reset it to the left side and do the same for the queen on the previous row:

<<one queen per row: move to next position>>=
for(queen_num = n-1; queen_num >= 0; queen_num--) {
    queen_cols[queen_num]++;
    if (queen_cols[queen_num] >= n) {
        queen_cols[queen_num] = 0;
    } else {
        break;
    }
}
if (queen_num < 0) {
    deallocate data structures
    return;
}

Because it's no longer possible to have two queens in the same row, we need not test for this anymore either:

<<one queen per row: verify current position>>=
is_valid = 1; /* Assume initially is valid, search for disproof */
for(queen_num_1=0; is_valid && queen_num_1 < n; queen_num_1++) {
    for(queen_num_2=queen_num_1 + 1; is_valid && queen_num_2 < n; queen_num_2++) {
        if (queen_cols[queen_num_1] == queen_cols[queen_num_2] ||
            queens are on same diagonal)
        {
            is_valid = 0;
        }
    }
}
if (is_valid) {
    print out current position
}

The test main is similar:

<<one_queen_per_row_search_queens.c>>=
header files

void search_for_queens_solutions(int n) {
    variable declarations
    allocate data structures
    one queen per row: set up initial queens position
    while(1) {
        one queen per row: verify current position
        one queen per row: move to next position
    }
}

int main(int argc, char* argv[]) {
    search_for_queens_solutions(atoi(argv[1]));
    return 0;
}

For the 8 queen problem, this searches through 88 or 16 777 216 positions, about 260 times less than the previous one. On the same hardware and software, it requires only half a second to find all 92 solutions to the 8 queens problem.

[edit] Permutations

The natural next question is, if we can avoid ever placing two queens in the same row, can we avoid ever placing them in the same column as well? The answer is that a set of queens with no two in the same row or column correspond to the mathematical concept of a permutation or reordering of the first n integers. For example, if the queens on rows 0 through 7 fall in columns 3, 6, 2, 7, 1, 4, 0, and 5 respectively, this corresponds to the reordering of the numbers 0, 1, 2, 3, 4, 5, 6, 7 into the order 3, 6, 2, 7, 1, 4, 0, 5. There are 8! = 40 320 such reorderings, corresponding to about 416 times less positions than in the previous implementation. We only need to check for diagonals:

<<permutations: verify current position>>=
is_valid = 1; /* Assume initially is valid, search for disproof */
for(queen_num_1=0; is_valid && queen_num_1 < n; queen_num_1++) {
    for(queen_num_2=queen_num_1 + 1; is_valid && queen_num_2 < n; queen_num_2++) {
        if (queens are on same diagonal)
        {
            is_valid = 0;
        }
    }
}
if (is_valid) {
    print out current position
}

In the initial position, the queens are along the main diagonal, representing the identity permutation that does not change the order:

<<permutations: set up initial queens position>>=
for(queen_num=0; queen_num < n; queen_num++) {
    queen_rows[queen_num] = queen_cols[queen_num] = queen_num;
}

To iterate through the permutations, we ensure that we never place a queen in the same column as one of the previous queens by using an auxilary flag array that tracks which columns are "in use", with a sentinel value at the end indicating that the "n+1"th column is never in use, whereas all the others initially are:

<<permutations: variable declarations>>=
int col_num;

<<permutations: allocate additional data structures>>=
int* col_in_use = (int*)calloc(n + 1, sizeof(int));

<<permutations: deallocate additional data structures>>=
free(col_in_use);

<<permutations: set up initial queens position>>=
for(queen_num=0; queen_num < n; queen_num++) {
    col_in_use[queen_num] = 1;
}

<<permutations: move to next position>>=
for(queen_num = n-1; queen_num >= 0; queen_num--) {
    col_in_use[queen_cols[queen_num]] = 0;
    do {
        queen_cols[queen_num]++;
    } while(col_in_use[queen_cols[queen_num]]);
    if (queen_cols[queen_num] < n) {
        col_in_use[queen_cols[queen_num]] = 1;
        break;
    }
}
if (queen_num < 0) {
    permutations: deallocate additional data structures
    deallocate data structures
    return;
}
/* Put the remaining queens in the remaining free columns in order */
queen_num++;
for(col_num = 0; queen_num < n && col_num < n; col_num++) {
    if (col_in_use[col_num] == 0) {
        col_in_use[col_num] = 1;
        queen_cols[queen_num] = col_num;
        queen_num++;
    }
}

The test main is similar:

<<permutation_search_queens.c>>=
header files

void search_for_queens_solutions(int n) {
    variable declarations
    permutations: variable declarations

    allocate data structures
    permutations: allocate additional data structures
    permutations: set up initial queens position
    while(1) {
        permutations: verify current position
        permutations: move to next position
    }
}

int main(int argc, char* argv[]) {
    search_for_queens_solutions(atoi(argv[1]));
    return 0;
}

On the same software and hardware, this solves the 8 queen problem in negligible time (<0.01s). Whereas the one queen per row approach took nearly 6 minutes and examined 10 billion positions to solve the 10 queen problem, the permutation approach solved it in half a second and examined only 3 628 800 positions.

[edit] Backtracking search

We can improve the permutation approach by noting that currently, even if a diagonal conflict occurs among the first k queens, we still iterate through all possible positions involving the rest of the queens and discard them all for the same reason. This is wasteful. Instead, we should immediately advance a queen if it ever enters the diagonal of a preceding queen. With this change our "move to next position" and "verify current position" blocks collapse into one, and we iterate only over valid solutions; this is effectively a backtracking search over the solution space.

We can no longer set up a valid initial position, since this would amount to finding a solution. Instead, we have only the first k queens on the board at any one time, and we advance the last one until it reaches a valid position before adding another one. We use the column -1 to indicate a queen that has yet to be placed.

Because this implementation handles problems with a very large number of solutions, printing time becomes significant, so we modify it to only print the first solution and count the rest.

<<backtracking: variable declarations>>=
int current_queen = 0;
int num_solutions = 0;
int went_off_right_side;

<<backtracking: set up initial queens position>>=
for(queen_num=0; queen_num < n; queen_num++) {
    queen_rows[queen_num] = queen_num;
    queen_cols[queen_num] = -1;
}

<<backtracking: search for solutions>>=
while(current_queen >= 0) {
    if (queen_cols[current_queen] != -1) {
        col_in_use[queen_cols[current_queen]] = 0;
    }
    do {
        /* Find next open column */
        do {
            queen_cols[current_queen]++;
        } while(col_in_use[queen_cols[current_queen]]);

        went_off_right_side = (queen_cols[current_queen] >= n) ||
                              (current_queen == 0 && queen_cols[0] > (n-1)/2);
        if (went_off_right_side) {
            break;
        }

        /* Check for diagonals */
        is_valid = 1;
        queen_num_1 = current_queen;
        for(queen_num_2 = 0; queen_num_2 < queen_num_1; queen_num_2++) {
            if (queens are on same diagonal) {
                is_valid = 0;
                break;
            }
        }
    } while(!is_valid);

    if (!went_off_right_side) {
        col_in_use[queen_cols[current_queen]] = 1;
        if (current_queen + 1 < n) {
            current_queen++;
            queen_cols[current_queen] = -1;
        } else {
            if (num_solutions == 0) {
                print out current position
            }
            num_solutions++;
            if (queen_cols[0] < n/2) {                
                num_solutions++; /* Add mirrored solution */
            }
        }
    } else {
        /* Backtrack */
        queen_cols[current_queen] = -1;
        current_queen--;
    }
}

We achieve an additional speedup by exploting symmetry. There is a one-to-one correspondence between solutions with the first queen in the first \lfloor{n/2}\rfloor of the columns and the mirrored solutions with it in the last \lfloor{n/2}\rfloor. Thus, we count these solutions twice and only allow the first queen to go up through \lceil{n/2}\rceil. If the board has an odd size, solutions with the first queen in the middle column are only counted once.

The test driver is as usual:

<<backtracking_search_queens.c>>=
header files

void search_for_queens_solutions(int n) {
    variable declarations
    backtracking: variable declarations

    allocate data structures
    permutations: allocate additional data structures
    backtracking: set up initial queens position
    backtracking: search for solutions
    permutations: deallocate additional data structures
    deallocate data structures

    printf("Number of solutions: %d\n", num_solutions);
}

int main(int argc, char* argv[]) {
    search_for_queens_solutions(atoi(argv[1]));
    return 0;
}

This is considerably faster than the simple permutation algorithm. On the same software and hardware, the basic permutation solution requires 77 seconds to solve the 12 queens problem, whereas backtracking search needs only 0.1 seconds, and can enumerate all solutions to the 15 queens problem in 30 seconds, confirming the known result that it has 2 279 184 solutions. Moreover, it can find a single solution to the 29 queen problem in 1 second.

[edit] Single solutions

Although the above backtracking search technique does well at enumerating all solutions, there are techniques for finding single solutions that scale well to much larger n. One successful technique, called the minimum-conflicts heuristic, works by beginning with a partial solution where queens are attacking one another and attempting to eliminate them by moving queens. Here's how one such solution might work:

<<find single solution>>=
void find_single_solution() {
    variable declarations
    allocate data structures

    for(queen_num = 0; queen_num < n; queen_num++) {
        place queen in the column with the least conflicts
    }

    while(1) {
        find queen with the most conflicts
        move it to the column with the least conflicts
    }
    
    print out current position
    deallocate data structures
}
Under construction.gif
TODO
Finish this solution
Download code
hijacker
hijacker
hijacker
hijacker