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)

Order        < ------  Ordinary Queens  ------ >              < ----- Superqueens ----- >
(“N”)      Total Solutions       Unique Solutions            Total 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                   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
15               2,279,184                285,053               32,516               4,089
16              14,772,512              1,846,955              202,900              25,411
17              95,815,104             11,977,939            1,330,622             166,463
18             666,090,624             83,263,591            8,924,976           1,115,871
19           4,968,057,848            621,012,754           64,492,432           8,062,150
20          39,029,188,884          4,878,666,808          495,864,256          61,984,976
21         314,666,222,712         39,333,324,973        3,977,841,852         497,236,090
22       2,691,008,701,644        336,376,244,042       34,092,182,276       4,261,538,564
23      24,233,937,684,440      3,029,242,658,210      306,819,842,212      38,352,532,487
24     227,514,171,973,736     28,439,272,956,934    2,883,202,816,808     360,400,504,834
25   2,207,893,435,808,352    275,986,683,743,434   28,144,109,776,812   3,518,014,210,402
26  22,317,699,616,364,044  2,789,712,466,510,289  286,022,102,245,804  35,752,764,285,788

Sources:
Total Solutions: https://oeis.org/A000170
Unique Solutions: https://oeis.org/A002562
Superqueens: https://oeis.org/A051223
Unique Superqueens: https://oeis.org/A051224

   The author was the original contributer to some of the results in the above table, but more recent results go well beyond what I was able to discover on a single PC. (See the above sources for credits.)

   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.



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    2883202816808    360400504834
25     2207893435808352    275986683743434   28144109776812   3518014210402
26    22317699616364044   2789712466510289  286022102245804  35752764285788



   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) 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