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"?
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
https://web.archive.org/web/20160305032242/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.
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 Sea Monkey's Composer HTML editor
within a Linux Cinnamon Mint 18 operating system.
(Goodbye Microsoft)