Since I started writing computer programs in 1976, I've been intrigued by this puzzle of placing N Queens on an N x N board so that no Queen is challenged by any other Queen.
For years (totalling thousands of hours) I have run my programs as a background task on various computers and servers, using progressively faster CPUs. But rather than seek the total number of solutions for each board size, for which I knew many others were searching, I focussed on seeking only the first solutions for those boards.
I define a "first solution" to this N-Queens puzzle as follows:
Assuming we start with a blank chess board, and assuming that we use the simple, step-by-step search algorithm which I describe here, where we step - laboriously, mechanically, sequentially and reliably - through every possible "no not yet" arrangement of Queens, then the "first solution" is the first arrangement of all N Queens which results in a "YES, GOTTIT" outcome.
From this point onwards, as our algorithm continues its search for maybe millions of subsequent solutions, we can guarantee that every subsequent arrangement of Queens will contain Queens in the same or later columns (or Files) on the board. No Queen on a particular row (or Rank) in any subsequent solution will appear in any earlier column than those discovered in that "first solution".
So - by using the algorithm which I summarise below, I have identified the first possible solution to all but two board sizes from 1 x 1 (a hypothetical board), via a 4 x 4 board (a trivial puzzle), all the way up to a board size of 49 x 49. The two exceptions which are still 'cooking' on my PCs are for board sizes 46 x 46 and 48 x 48.
Click hereto see the full table of all the First Solutions I have found, most of which have been independently verified by my son Martin.
We like to think that maybe someone, somewhere, seeking other solutions (or all solutions) for a specific board size, might be helped by knowing the coordinates of the Queens as they appear in these first possible solutions.
Counter-intuitive Counter-swings
As well as seeking those first solutions to this puzzle, I have recorded how hard our Queens have had to 'work' as they step millions of times from square to square to square, trying to find those elusive squares on which they can rest, unchallenged by other Queens. Those counts of "tentative Queen placements" for the different board sizes have shown some fascinating and unexpected swings in magnitude!
As an example, comparing a 4 x 4 board with a 5 x 5 board: In order to add 4 non-clashing Queens to a simple board of 4 x 4 squares, we need to place a tentative new Queen 26 times before we discover the first combination that allows all Queens to sit unchallenged. However, when it comes to the board size of 5 x 5, one row and one column larger than the previous board, we only need to place our tentative new Queens 15 times before we discover the first combination of 5 unchallenged Queens! That smaller number of tentative Queens required for the larger board size seems (to me) to be delightfully counter-intuitive and illogical, and we see similar oddness and unpredictability while seeking that first solution on all of the larger board sizes.
Here's a table showing just some of the magnitude swings:
Size of board Number of tentative Queen placements needed
prior to discovery of the first solution4 x 4 26 5 x 5 15 6 x 6 171 7 x 7 42 8 x 8 876 9 x 9 333 10 x 10 975 11 x 11 517 12 x 12 3066
The only 'pattern' in those numbers is that the even-numbered board sizes demand a higher number of tentative Queen-placements than the odd-numbered board sizes. Otherwise, the degree by which adjacent board sizes differ is deliciously unpredictable!
Click herefor a complete table which shows the 'tentative Queen placement' counts for all board sizes calculated so far, from the hypothetical 1 square by 1 square up to the enormous 49 squares by 49 squares.
The Queen-Placement Algorithm
The following pages describe one specific method of searching for a solution to the N-Queens on a chessboard. There are other search schemes, but this one (which, for the sake of clarity if not conciseness I'll call the "one Queen at a time, tentative-placement scheme") is the one I've used in the C and C++ programs that I've written and dabbled with for decades. A key feature of this algorithm is that, while it can find all possible solutions to an N x N board, it is guaranteed always to identify the first of those solutions. (Note that for this illustration, I stop immediately on the first solution and I don't look beyond it for any of the large number of further solutions that would surface if it was allowed to continue running.)
This algorithm can be applied to any board size. In the example that follows I use a board size of 5 x 5 because it needs the fewest number of tentative placements while still showing a reasonable number of intermediate steps. I make no claims about possible optimisations or shortcuts which could speed up this algorithm. In fact the algorithm is simple, mechanical and pedantic and - unless you're a computer - it's very boring ... But it is thorough, it is repeatable and it is exact.
My aim is simply to show how this algorithm finds the very first possible solution for a particular board size, and to show how I count the number of Queens placements that lead to that solution.
- Click here
to see the sample 5 x 5 board which illustrates the counting scheme I've used.
- Click here
to see a proposed "known next coordinate" notation schema for describing solutions to this puzzle.
- Click here
to download a free Windows®-based program that calculates these Queens-placed values
for board sizes up to 32 x 32.
( Updated on 27th Oct 2008 - Please download the new Version 2.2.0.1, which includes a minor bug-fix.)
The following two links are just repeats of the links near the top of this page:
- Click here
for a full table of First Solutions I have found so far.
- Click here
for the counts of 'tentative Queen placements' for all board sizes calculated so far.
External Links:
1. My son Martin now has his own Queens On A Chessboard web site in which he describes his work on this puzzle. His explanations are crystal clear and beautifully illustrated, and he includes a full 'board' diagram for every First Solution we have solved and/or verified! Martin has been an invaluable 'sounding board' for me on this project.
2. For almost everything else that there is to know about this N-Queens puzzle (and its original version, the 8 Queens puzzle),
I strongly recommend this Wikipedia page.
3. The On-Line Encyclopedia of Integer Sequences now includes our
4. The NQueens@Home project is using 'BOINC' technology and hundreds of internet-connected PCs to seek the Total Number Of Solutions for each board size (unlike my project here which seeks only the FIRST solution for each board size). The NQueens@Home contributers are currently (as at November 2008) working on the solutions for a 26 x 26 board.
Contact:
- You may contact me via this feedback page, although I do not promise to respond to every message or question.
Page updated: 01:08 on 5th November 2008
| Content on this CSP Queens site
by Colin S Pearson and Martin S Pearson
is licensed under a Creative Commons Attribution-Non-Commercial-Share Alike 2.0 UK: England & Wales License. Permissions beyond the scope of this license may be available via the feedback page. |
![]() |