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).
#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 ; }
Fun.
Hi Mark – Thanks for posting that. How about commenting the code so when others discover this via web searches, they can see how this textbook example of a constraint satisfaction problem is solved? It’s applicable to a variety of problems of course and I think it would be educational. Keep posting. I enjoy the blog!