a study in optimization
My command line program and source code can be downloaded here.
My command line executable can be downloaded here.
A version which prints out the board positions for each solution is
Note that printing out the board positions slows down the program quite
a bit, so you may want to pipe the output to a text file (nqprint 16
> output.txt) & then examine the results after the program has
The N Queens Problem
(chess graphics from this site)
How many ways are there to arrange N non-attacking queens on an N x N chessboard?
For a regular-sized board (8 x 8), there are 92 distinct solutions, one of which is shown above.
Note that for each solution, no two queens can occupy the same column, row or diagonal.
For a 1 x 1 board, there is one trivial solution:
For 2 x 2 and 3 x 3 boards, there are no solutions. For a 4 x
4 board, there are two:
These are considered distinct solutions, even though the solutions are mirror images of each other.
There is no quick and easy way to calculate the total number of N queen solutions for an N x N board.
My program is a heavily-optimized C program, yet it still takes over a week for an 800 MHz PC to calculate the number of solutions for a 21 x 21 board. (In case you're curious, there are 314,666,222,712 solutions.)
2x - 10x speedup over other solutions
My program is almost twice as fast as the program used to calculate the "world record" N queens solution (the 23 x 23 board). Source for that program, written by Sylvain Pion and Joel-Yann Fourre, can be found here.
It's also up to 10 times as fast the N-queens
program written by Dr. Timothy Rolfe.
Rolfe is a computer science professor who has written Algorithm
Alley columns for Dr. Dobb's Journal.
His paper on Queens on a Chessboard: Making the Best of a Bad Situation
can be found here.
To compile the "world record" program in Visual C++, just add algo.c and apart.c to your project. The board size is hard-coded in algo.h.
History and Algorithm
The 8 queens problem was studied by Gauss in the mid-1800's. It is often described in many undergraduate programming texts, since solving it requires students to understand how to program a backtracking algorithm.
The backtracking algorithm used to solve this problem
I became interested in this problem when I was considering taking an Artificial Intelligence course which used LISP as its programming language. I downloaded a LISP compiler and a sample program which found one solution for the 8 queens problem. This program was s....l....o....w. I figured I could write a program in C which found all solutions to the 8 queens problem faster than this LISP program could find one solution. I was right. Inspired by the writings of Michael Abrash, I've been trying to optimize that program ever since.
Postscript: To be fair, the LISP program was not compiled, and since then I've taken that A.I. course and learned to appreciate LISP's strengths.
Home page of Sylvain Pion, who co-wrote the "world record" N queens
Home page of Timothy Rolfe, Ph.D.:
Eric Weisstein's World of Mathematics:
Information on the n Queens problem:
Interesting chess problem page which appears to be in Czech:
return to my programming demos page.