Durango Bill's
The N-Queens Problem
(Originally, the Eight Queens Problem)
The N-Queens Problem
(Originally, the Eight Queens Problem)
How many ways (number
of solutions) are there to place "N" Queens
on an NxN Chessboard?
Also, how many solutions are there if you use "Superqueens"?
on an NxN Chessboard?
Also, how many solutions are there if you use "Superqueens"?
The N-Queens on an NxN
Chessboard Problem
Topics covered
The original eight (8) queens on a chessboard problem
Expanding the problem to "N" Queens on an NxN chessboard
Also, include "Superqueens"
Current Knowledge
Computational Considerations
The original eight
queens problem
The original eight queens problem consisted of trying to find a way to place eight queens on a chessboard so that no queen would attack any other queen. An alternate way of expressing the problem is to place eight “anythings” on an eight by eight grid such that none of them share a common row, column, or diagonal.
It has long been known that there are 92 solutions to the problem. Of these 92, there are 12 distinct patterns. All of the 92 solutions can be transformed into one of these 12 unique patterns using rotations and reflections.
The 12 basic solutions can be constructed using the following table. For example, if you are constructing solution number 1, then the Queen for chessboard row 1 should be placed in column 1, the Queen for row 2 should be placed in column 5, etc. A diagram showing solution number 1 appears below the table.
Sol. Elements show which column to use per chessboard row
Nbr. Row 1 Row 2 Row 3 Row 4 Row 5 Row 6 Row 7 Row 8
--------------------------------------------------------------
1 1 5 8 6 3 7 2 4
2 1 6 8 3 7 4 2 5
3 2 4 6 8 3 1 7 5
4 2 5 7 1 3 8 6 4
5 2 5 7 4 1 8 6 3
6 2 6 1 7 4 8 3 5
7 2 6 8 3 1 4 7 5
8 2 7 3 6 8 5 1 4
9 2 7 5 8 1 4 6 3
10 3 5 2 8 1 7 4 6
11 3 5 8 4 1 7 2 6
12 3 6 2 5 8 1 7 4
---------------------------------
8 | | | | Q | | | | |
---------------------------------
7 | | Q | | | | | | |
---------------------------------
6 | | | | | | | Q | |
---------------------------------
5 | | | Q | | | | | |
Rows ---------------------------------
4 | | | | | | Q | | |
---------------------------------
3 | | | | | | | | Q |
---------------------------------
2 | | | | | Q | | | |
---------------------------------
1 | Q | | | | | | | |
---------------------------------
1 2 3 4 5 6 7 8
Columns
If we rotate and reflect any solution so that the entry on row 1 is as far left as possible, then we can group solutions by this leftmost column. The above example is a “Column 1” solution. Of the 12 basic solutions, two are “Column 1” solutions, seven are “Column 2” solutions, and three are “Column 3” solutions. (We will show similar solution groupings for N x N where “N” = 20 below.)
Expanding the problem
to “N” Queens on an NxN chessboard
Also, include “Superqueens”
Also, include “Superqueens”
If we increase the size of the chessboard beyond 8 rows/columns, we might want to find how many solutions exist for any arbitrary board size “N”. For example, if “N” = 10, then there are 724 solutions. Of these, 92 are distinct. Also with “N” = 10, we find the first nontrivial “Superqueen” solution. A “Superqueen” not only covers all rows, columns, and diagonals as above, but also covers all possible “knight” moves. A knight move consists of moving two spaces in any direction (up, down, left, or right) followed by a single space at a right angle to this initial direction. Only one unique “Superqueen” solution exists for “N” = 10, and it is shown below. (There are three other variations with rotations/reflections).
-----------------------------------------
10 | | | | | | | | Q | | |
-----------------------------------------
9 | | | | | Q | | | | | |
-----------------------------------------
8 | | Q | | | | | | | | |
-----------------------------------------
7 | | | | | | | | | | Q |
-----------------------------------------
6 | | | | | | | Q | | | |
-----------------------------------------
5 | | | | Q | | | | | | |
Rows -----------------------------------------
4 | Q | | | | | | | | | |
-----------------------------------------
3 | | | | | | | | | Q | |
-----------------------------------------
2 | | | | | | Q | | | | |
-----------------------------------------
1 | | | Q | | | | | | | |
-----------------------------------------
1 2 3 4 5 6 7 8 9 10
Columns
Current Knowledge
The table below shows the Number of Solutions and the Number of Unique (Basic) Solutions (after disallowing rotations/reflections) for both Queens and Superqueens. The table is a composite from many sources. (Many are posted on the Internet) The results for Unique Superqueens are the author’s results. (The run out to 23x23 also confirmed results previously found by others.)
Order < ----- Ordinary Queens ----- > < ---- Superqueens --- > Exec
(“N”) Total Solutions Unique Solutions Total Sol. Unique Sol. Time
-------------------------------------------------------------------------------------
1 1 1 1 1
2 0 0 0 0
3 0 0 0 0
4 2 1 0 0
5 10 2 0 0
6 4 1 0 0
7 40 6 0 0
8 92 12 0 0
9 352 46 0 0
10 724 92 4 1
11 2,680 341 44 6
12 14,200 1,787 156 22
13 73,712 9,233 1,876 239
14 365,596 45,752 5,180 653 0.2 s
15 2,279,184 285,053 32,516 4,089 1.9 s
16 14,772,512 1,846,955 202,900 25,411 11.2 s
17 95,815,104 11,977,939 1,330,622 166,463 77.2 s
18 666,090,624 83,263,591 8,924,976 1,115,871 9.6 m
19 4,968,057,848 621,012,754 64,492,432 8,062,150 75.0 m
20 39,029,188,884 4,878,666,808 495,864,256 61,984,976 10.2 h
21 314,666,222,712 39,333,324,973 3,977,841,852 497,236,090 87.2 h
22 2,691,008,701,644 336,376,244,042 34,092,182,276 4,261,538,564 31.9 d
23 24,233,937,684,440 3,029,242,658,210 306,819,842,212 38,352,532,487 296 d
24 227,514,171,973,736 28,439,272,956,934 ? ?
25 2,207,893,435,808,352 275,986,683,743,434 ? ?
26 22,317,699,616,364,044 2,789,712,466,510,289 ? ?
(s = seconds m = minutes h = hours d = days)
The N=26 solutions were found in July, 2009 by a “massively-parallel, FPGA-based effort” organized out of Technische Universitat Dresden. Thanks to John Bass for the update. John has also indicated that the Dresden group is going to take a shot or two at higher orders. Please see http://queens.inf.tu-dresden.de/ and http://queens.inf.tu-dresden.de/?n=f&l=en for more info.
Execution time is a measure of computational complexity for the above results. It represents the amount of time that would be required for a single copy of the author’s computer program to run a complete search on a Falcon Northwest Skulltrail computer. (Twin QX9775 processors - each with 4 cores at 3.2 GHz) Execution times have been updated for a new optimized version of the program which uses a bitfield representation for used columns and diagonals. It does not include the time savings derived from running multiple copies of the program in parallel.
Jeff Somers has posted a “C” program for solving the “N Queens” problem at http://jsomers.com/nqueen_demo/nqueens.html . The bitfield algorithm goes back at least as far as John Bass’ “C” program which was written in 1983. Jeff Somers’ program includes good documentation which is a big help when you are trying to understand how the program works. The author modified his version so that multiple copies of the program can simultaneously search limited portions of the search tree. The modified version also includes provisions to restart at known interim results in case of power failure, “Windows demands that you restart your computer - NOW”, the antivirus program insists that you restart your computer - NOW, etc.
In practice, 6 or 7 copies of the program were usually running simultaneously on the computer. Thus the total execution time was a fraction of the time that would be required for a single copy of the program.
The “Print Screen” picture above shows the Skulltrail computer at work on the 23 x 23 version of the N-Queens problem. (Click on the picture for a full size image.) The background picture (computer desktop) is a satellite photograph of the Southwestern U.S. Lake Mead is in the lower left corner.
7 copies of the program were running simultaneously with each copy running a tree-search for different board combinations. At the time the picture was recorded, the combination of the 7 programs was averaging over 2,600,000 regular 23x23 solutions per second. (Symmetry doubles this number.) (After 6 elapsed days, this average solution rate was over 3,000,000 per second.)
Internet look-up hint
If you know a few integer numbers in any solution sequence, you can frequently find a web site that has considerably more information regarding that sequence. For example, if you enter 352 724 2680 14200 in the "Google" search engine, it will return links to several web sites that give solutions to the "N" Queens problem. We present the above table again but without commas in the numbers. This will make it easier for anyone using a search engine to find this table.
Order < --- Ordinary Queens --- > < - Superqueens - >
(“N”) Total Solutions Unique Solutions Tot. Sol. Unique Sol.
----------------------------------------------------------------------
1 1 1 1 1
2 0 0 0 0
3 0 0 0 0
4 2 1 0 0
5 10 2 0 0
6 4 1 0 0
7 40 6 0 0
8 92 12 0 0
9 352 46 0 0
10 724 92 4 1
11 2680 341 44 6
12 14200 1787 156 22
13 73712 9233 1876 239
14 365596 45752 5180 653
15 2279184 285053 32516 4089
16 14772512 1846955 202900 25411
17 95815104 11977939 1330622 166463
18 666090624 83263591 8924976 1115871
19 4968057848 621012754 64492432 8062150
20 39029188884 4878666808 495864256 61984976
21 314666222712 39333324973 3977841852 497236090
22 2691008701644 336376244042 34092182276 4261538564
23 24233937684440 3029242658210 306819842212 38352532487
24 227514171973736 28439272956934 ? ?
25 2207893435808352 275986683743434 ? ?
26 22317699616364044 2789712466510289 ? ?
Finally, as we saw in the solutions for the original 8 queens problem, it is possible to group solutions for any order “N”. The table below shows the solution groups for “N” = 20. Rotations and reflections were used for both “Queens” and “Unique Queens” so that the column for chessboard row 1 was moved as far left as possible. For example there were 8,325,567,828 total solutions and 1,040,698,100 unique solutions (after rotations/reflections) where the leftmost position for a queen on row 1 was in column 3.
Total Unique
Column Solutions Solutions
-------------------------------------------
1 3,650,783,696 456,347,962
2 8,344,182,020 1,043,024,907
3 8,325,567,828 1,040,698,100
4 7,374,769,956 921,848,953
5 5,602,569,796 700,324,106
6 3,482,340,140 435,295,219
7 1,674,994,644 209,376,713
8 506,375,636 63,299,062
9 65,833,888 8,230,084
10 1,771,280 221,702
------------- ------------
Totals 39,029,188,884 4,878,666,808
Computational
Considerations
Computer solutions to the N-Queens problem are basically the same as the method you would use by hand. It is simply a brute force trial and error method. (The buzzwords are: Tree search with backtracking) The amount of time required to find all solutions for any order “N” is roughly proportional to “N” Factorial. It took about 10 hours to get the results for “N” = 20. (Using only a single copy of the program.) If we increase “N” to 21, it would take a single copy of the program about 3.6 days to run. Beginning at about N = 20, the problem has to be broken into parts with each part delegated to a separate computer. (Alternately, to multiple cores on a single computer) At N = 23 it took nearly 2 months on a powerful Skulltrail computer - and this was taking full advantage of symmetry and parallel processing. For “N” in the middle 20s, hundreds of computers are needed. With present computing power, it is unlikely that the total number of solutions will be found when “N” equals 30 or higher.
Return to Durango Bill's Home page
Web page generated via KompoZer