The N-Queens problem

I’ve been thinking about depth first backtracking algorithms recently (more on what those are in a moment).  So when I couldn’t sleep on a recent over night train trip I decided to dust off a classic programming problem to pass the time.

How many ways can you place 8 queens on a chessboard so that no two of them are mutually attacking?  The first step of this problem is to determine what constitutes a really bad idea.

The worst possible case is to consider every single placement of queens.  We have 64 choices for the placement of the first queen, 63 choices for the placement of the second, 62 choices ….. So there are a total of 64*63*62*61*60*59*58*57 = 2*10^14 (approximately).  This is a very big number.

How might we do better?  Well, in the original statement of this problem we consider every arrangement of queens including obviously bad ones with all 8 queens in the same row or column.  We know immediately that all the queens must be in different rows and columns so they won’t be attacking each other.  We can use this to say, in the first column of the chessboard we have 8 choices for placement of a queen. Now, since this choice has eliminated a row, we have 7 choices for the second column and so on.

This search procedure will leave us with 8! = 8*7*6*5*4*3*2*1 = 40320 potential solutions to check.  This is much more doable.  Here’s some simple code to do this in MATLAB and Octave:

clear all

clc

tic; %start the clock, want to see how long this will take

count = 0;

n = 8;

cols = 1:n;

col_perms = perms(cols); %find all permutations of 1:n

for i = 1:length(col_perms) % for each permutation, do:

this_col = col_perms(i,:); % get the permutation

for j = 1:n                % for 1:n, check for conflicts on the diagonals

upper(j) = this_col(j) + j;

lower(j) = this_col(j) – j;

end

if and(length(unique(upper)) == n,length(unique(lower))==n)

% if there are no conflicts we’ve found a partition

% let’s count it

count = count+1;

end

end

disp([‘Found ‘ num2str(count) ‘ arrangements of queens.’…

‘ This took ‘ num2str(toc) ‘ seconds.’]);

Which, on my mac book will work for a little while then print out:

“Found 92 arrangements of queens. This took 8.8268 seconds.  ”

That’s awesome.  With only a few lines of code in less than 10 seconds we’ve been able to confirm that there are 92 possible arrangements of queens on the chessboard in which they no two queens are mutually attacking.

But, there are several ways to do better.  Once such way can be achieved if we build the solution iteratively.  That is to say we first place a queen, then check the board, then place another queen and repeat until we realize there’s a problem.  When we realize there’s a problem (that is to say, we’ve placed the queens in such a way that we know we can’t place all 8) we remove queens until we can make a different placement  we can do much better.

The process we just described is the depth first backtracking algorithm.  This is slightly more challenging to program.  If you’re interested in the gory details you can see them here (will update that link shortly).  I took an object oriented approach using a MATLAB class.  Also included in the post is the code I wrote to make pretty pictures of chessboards.

How fast can we find all the possible arrangements of queens on a chessboard?  1.848 seconds, or more than 4.5 times faster than brute force.  The fact that I find that supremely awesome probably betrays me as a nerd.There are many good ways to solve the N-queens problem (of which we’ve solved the 8-queens problem above).  I might come back to it at some time if I find myself unable to sleep on a train again.  Until then I leave you with some pretty pictures of chessboards.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>