Backtracking is a better technique, obviously. The version from earlier today was actually not very clever, and took half an hour to find the 73,712 solutions to the 13×13 checkerboard. This version is less code (just 91 lines, compared to 107 for yesterdays) and finds all the 13×13 solutions in just 2.5 seconds (a speed up of around 720x).

[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
place(int r, int n)
{
int i, j ;
if (r == n) {
// We filled in all rows…
total++ ;
print(board, n) ;
} else {
for (i=0; i<n; i++) {
board[r] = i ;
for (j = 0; j<r; j++) {
if (board[j] == board[r])
goto skipit ;
if (abs(board[j]-board[r]) == abs(j-r))
goto skipit ;
}
place(r+1, n) ;
skipit:
continue ;
}
}
}

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]

Fun.

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]