Solutions to the 8-Queens Problem

 

This problem is to place 8 queens on the chess board so that they do not check each other.  This problem is probably as old as the chess game itself; it is known that Gauss studied this problem.  If we want to find a single solution, it is not difficult as shown below.  If we want to find all possible solutions, the problem is difficult, and the backtracking approach is the only known method.  For 8 queens, there are 92 solutions.  If we exclude symmetry, there are just 12 solutions.

A good activity to try in the garden is to solve the problem with a smaller number of queens; for example, 4 people can try to position themselves on a 4x4 sub-grid on the island so that none are in the same row, column or diagonal.

For the general case of the n-Queens Problem, if n is a prime number, a solution is easily found by drawing a straight line in the (n, n) finite plane.  Since no two straight lines can intersect at two points, a straight line y=ax+b where a is not equal to 1 or -1 can give a solution (with coordinates starting from 0).

Example 1
n = 7, y = 2x
6 X
5 X
4 X
3 X
2 X
1 X
0 X
0 1 2 3 4 5 6

 

n = 7, y = 3x + 1
6 X
5 X
4 X
3 X
2 X
1 X
0 X
0 1 2 3 4 5 6

 

We can easily find 28 solutions by a=2, 3, 4, 5, and b=0, 1, 2, 3, 4, 5, 6.
The ratio of analytical solutions for the total solutions for some small p is as follows:
p=5, 10/10, 100%
p=7, 28/40, 70%
p=11, 99/2680, 4%
For composite numbers n=pq, we can make a direct product of the p-queen and q-queen problems.  That is, each queen position of the p-queen problem is regarded as a solution of the q-queen problem.  We can change the roles of p and q.  Thus for 35=5*7, we can generate 10*(40)^5 + 40*(10)^7 solutions.
To generate one solution for a general n, let the plane coordinated by i=0, ..., n-1 and j=0, ..., n-1.
Suppose n is even.  For any k,
(1) If n is not 6k+2,
j = 2i+1, for 0 <= i < n/2
j = 2i mod n, for n/2 <= i < n

Example 2
n=6
5 X
4   X
3 X  
2 X  
1 X
0   X
0 1 2 3 4 5

(2) If n is not 6k
j = (n/2 + 2i -1) mod n, for 0 <= i < n/2
j = (n/2 + 2i + 2) mod n, for n/2 <= i 

Example 3
n = 8
7 X  
6 X  
5 X  
4   X
3 X  
2   X
1   X
0   X
0 1 2 3 4 5 6 7

For odd numbers, we can attach a queen at (n-1, n-1).

8     X
Example 4
n = 9
7 X  
6 X    
5 X  
4   X
3 X  
2   X  
1   X
0   X
0 1 2 3 4 5 6 7 8

Related Sites

 

Return to Bridges of Frientship Garden home page...