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 data for
“Queens” and “Total Superqueens” is a composite
of many sources. (Many are posted on the Internet) The author has
calculated the “Unique Superqueens” numbers.
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
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
? ?
22
2,691,008,701,644
336,376,244,042
? ?
23
24,233,937,684,440
3,029,242,658,210
? ?
24
227,514,171,973,736
?
? ?
25
2,207,893,435,808,352
?
? ?
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
? ?
22
2691008701644
336376244042
? ?
23
24233937684440
3029242658210
? ?
24
227514171973736
?
? ?
25
2207893435808352
?
? ?
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 amount of time required to find all
solutions for any order “N” is roughly proportional to
“N” Factorial. It took over 11 days to get the results for
“N” = 20. If we increase “N” to 21, it would
take about 4 months for the program to run. For higher orders of
“N”, the problem has to be broken into parts with each part
delegated to a separate computer. Thus, dozens and more likely,
hundreds of computers are needed to solve problems with “N”
in the low 20's. 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