brainwagon

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.