Solving the N queens problem, again…

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.

One thought on “Solving the N queens problem, again…

  1. Pew Mogel

    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!

Comments are closed.