Durango Bill's
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"?
 
 
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

   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 Skulltrail computer at work on the N-Queens problem.

   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