The N Queens Problem
a study in optimization

A version which prints out the board positions for each solution is here.  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 been run.

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.

My program

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. Dr. 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.

To compile Dr. Rolfe's program in Visual C++, just add seq.c to your project.  Then open timers.c and replace the line:

#if defined(__TURBOC__)

with

#if defined(WIN32)

 Board size My program "World Record" Program Dr. Timothy Rolfe's Program 14 x 14 00:00:01 00:00:01 00:00:05 15 x 15 00:00:03 00:00:06 00:00:36 16 x 16 00:00:23 00:00:43 00:03:58 17 x 17 00:02:38 00:05:12 00:29:14 18 x 18 00:19:26 00:37:56 03:25:05 19 x 19 02:31:24 04:57:38 28:24:52

 Board Size (length of one side of N x N chessboard) Number of Solutions to N Queens Problem Time to calculate on 800 MHz PC (Hours:Mins:Secs) 1 1 n/a 2 0 < 0 seconds 3 0 < 0 seconds 4 2 < 0 seconds 5 10 < 0 seconds 6 4 < 0 seconds 7 40 < 0 seconds 8 92 < 0 seconds 9 352 < 0 seconds 10 724 < 0 seconds 11 2680 < 0 seconds 12 14200 < 0 seconds 13 73712 < 0 seconds 14 365596 00:00:01 15 2279184 00:00:04 16 14772512 00:00:23 17 95815104 00:02:38 18 666090624 00:19:26 19 4968057848 02:31:24 20 39029188884 20:35:06 21 314666222712 174:53:45 22 2691008701644 ? 23 24233937684440 ? 24 ? ?

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
We place a queen in the top row, then note the column and diagonals it occupies.  We then place a queen in the next row down, taking care not to place it in the same column or diagonal.  We then keep track of the occupied columns and diagonals and move on to the next row.  If no position is open in the next row, we back track to the previous row and move the queen over to the next available spot in its row and the process starts over again.

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.

Further ideas

• I tried caching partial results in order to speed up the program.  A great idea, however it just made things slower.
• Assume we know the results for an N x N board.  Can we somehow leverage that to find the results for an (N + 1) x (N + 1) board?  There doesn't seem to be a away to apply the results of a previous search to the next-greater-board-size search.
• Consider the N Rooks problem.  There's no need to write a program to figure out the solutions, since the number of solutions for a N x N board is n!.  Is there a similar formula for the N Queens problem?

Home page of Sylvain Pion, who co-wrote the "world record" N queens code:
http://www-sop.inria.fr/prisme/personnel/pion/index_eng

http://penguin.ewu.edu/~trolfe/

Eric Weisstein's World of Mathematics:
http://mathworld.wolfram.com/QueensProblem.html

Information on the n Queens problem:
http://www.schoolnet.ca/vp-pv/amof/e_queeI.htm

Interesting chess problem page which appears to be in Czech:
http://web.iol.cz/vaclav.kotesovec/math.htm