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, and thus its origin is not known, but 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 backtrack method is the only known method. For 8queen, we have 92 solutions. If we exclude symmetry, there are 12 solutions.
Consider the general case of the nQueens 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. Coordinates start 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 pqueen and qqueen problems. That is, each queen position of the pqueen problem is regarded as a solution of the qqueen 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, ..., n1 and j=0, ..., n1.
Suppose n is even. For any k,
(1) If n is not 6k+2,
j = 2i+1, for 0 <= i < n/2Example 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
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 (n1, n1).
Example 4. n=9
7 








X 
7 


X 






6 




X 




5 

X 







4 







X 

3 
X 








2 






X 


1 



X 





0 





X 




0 
1 
2 
3 
4 
5 
6 
7 
The eight queens problem is frequently used as an example in Artificial Intelligence courses. The object is to place eight queens on an empty chess board so that none of them can take the other.
Back to the Bridges of Friendship Garden Homepage
Contact: Prof. Tadao Takaoka
Modified: 19Nov1998