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:
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;
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;
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.