brainwagon

A question on Quora set me thinking about solving the N Queens problem, which is to list all ways that N queens can be positioned on an NxN checkerboard such that no queen can attack the other. I seemed to have misplaced my implementation of this that I did in Python, so I decided to do one in C while watching Agents of Shield. The code in general shows the lack of attention, but it does work. It can find all 92 solutions for the 8×8 checkerboard in under one second, but slows down rapidly after that, taking nearly half an hour to find all 73,712 solutions for the 13×13 board.

This program isn’t completely unclever (in fact, I think it is too clever in a way) but it should be properly described as a brute force search, since it generates all N! ways of positioning N queens in different rows, and tests them for diagonals. Thus, it’s runtime is O(N!), which isn’t great. It doesn’t even do backtracking, which would undoubtedly help a great deal.

One good page I found googling this morning is this one by Jeff Somer. His program is much more clever than mine. My estimate is that my program would take well over 100,000 years to count all the positions for a 21×21 board, Jeff’s does it in about a week.

Another cool page is this one, which introduces the idea of “super-queens”, which also capture with the same moves as a knight. Only one unique solution for N=10 exists, which is pretty cool. For higher N, more solutions become possible.

Code is archived here.

[sourcecode lang=”cpp”]
#include <stdio.h>
#include <stdlib.h>

#define MAX_N (15)

int board[MAX_N] ;
int total = 0 ;

void
print(int board[MAX_N], int n)
{
int i, j ;

printf("+") ;
for (i=0; i<n; i++) {
printf("-") ;
if (i < n-1)
printf("+") ;
}
printf("+\n") ;

for (i=0; i<n; i++) {
printf("|") ;
for (j=0; j<n; j++) {
if (j == board[i])
printf("O") ;
else
printf(" ") ;
if (j < n-1)
printf("|") ;
}
printf("?\n") ;
if (i < n-1) {
printf("+") ;
for (j=0; j<n; j++) {
printf("-") ;
if (j < n-1)
printf("+") ;
}
printf("+\n") ;
}
}

printf("+") ;
for (i=0; i<n; i++) {
printf("-") ;
if (i < n-1)
printf("+") ;
}
printf("+\n\n") ;
}

#define abs(n) ((n)<(0)?(-(n)):(n))

void
check(int board[MAX_N], int n)
{
int col[MAX_N] ;
int i, j ;

for (i=n-1; i>=0; i–) {
col[i] = board[i] ;
for (j=i+1; j<n; j++) {
if (col[i] <= col[j])
col[j]++ ;
}
}

// now, check for diagonals..
for (i=0; i<n; i++)
for (j=i+1; j<n; j++)
if (abs(col[i]-col[j]) == abs(j-i))
return ;

// we have a winner…
total++ ;
print(col, n) ;
}

void
place(int i, int n)
{
if (i == n) {
// check board
check(board, n) ;
} else {
int which ;
for (which=0; which < n-i; which++) {
board[i] = which ;
// recurse…
place(i+1, n) ;
}
}
}

int
main(int argc, char *argv[])
{
int n = atoi(argv[1]) ;
place(0, n) ;
if (total == 0)
fprintf(stderr, "There are no solutions for the %dx%d board..\n", n, n) ;
else
fprintf(stderr, "There is %d solution%s for the %dx%d board.\n",
total, total > 1 ? "s" : "", n, n) ;
return 0 ;
}
[/sourcecode]