問題描述：八皇後問題是一個以國際象棋為背景的問題：如何能夠在8×8的國際象棋棋盤上放置八個皇後， 使得任何一個皇後都無法直接吃掉其他的皇後？為了達到此目的，任兩個皇後都不能處於同一條橫行、縱行或斜線上,此問題進而可以推廣為n皇後的問題。
解題思路：n*n的矩陣，遞歸每一個點，當皇後數量達到n的時候，進行判斷，若滿足題目條件，則答案加一(number++)，否則繼續進行遍歷。
保存皇後點的方法：構造一個二維數組reserve[][]，當reserve[i][j] == 1時候，則該點已經有皇後，若reserve[i][j]==0則，皇後可以存在於該點，且該點置為一。
判斷皇後數量的方法，定義一個int sign ，當sign<8的時候遞歸遍歷，並且重復上一操作，否則對reserve數組進行判斷，判斷此數組內等於1的點的坐標，是否滿足題意，判斷完之後，當前點置為0.
判斷x,y軸只需要判斷是否有相等的坐標值即可。
判斷斜線，則判斷每兩個點之間坐標值相減的絕對值是否相等，（這裡需要遞歸遍歷每一個點）若相等，則點在斜線上重復，返回false,若不相等，則點在斜線上不重復，返回true。
先定義全局變量：
? 1 2 3
private static int number = 0; //表示答案數量
int count = 0; //下文的數組下標
static String[] str ; //保存正確答案的字符串數組，為了去除重復
定義主函數：
? 1 2 3 4 5 6 7 8 9 10 11public static void main(String[] args) {
com c = new com();
System.out.print("請輸入皇後數字n：");
Scanner s = new Scanner(System.in);
int n = Integer.parseInt(s.nextLine());
int[][] reserve = new int[n][n]; //儲存皇後的狀態
str = new String[n*100];
int sign = 1;
c.startRun(reserve, n ,sign);
System.out.println(number);
}
下面執行遍歷操作的函數：
? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21public void startRun(int[][] reserve , int n ,int sign){
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(reserve[i][j] == 0)
reserve[i][j] = 1; //該點為一個皇後
else{
continue;
}
if(sign == n){
if(checkAllQuean(reserve,n)){ //對n皇後進行位置判斷
output(reserve,n); //一個輸出函數，輸出n皇後的點
System.out.println();
number++;
}
}else if(sign < n){
startRun(reserve , n ,sign + 1); //進行遍歷操作
}
reserve[i][j] = 0;
}
}
}
下面對數組reserve進行皇後位置判斷：
? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27/*<br> * 檢查兩個皇後是否在同一行，同一列，或者同一斜線上<br> * 存在返回false<br> * 不存在返回true<br> */<br>public boolean checkAllQuean(int[][] reserve , int n){
int[] x = new int[n];
int x1 = 0;
int[] y = new int[n];
int y1 = 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(reserve[i][j] == 1){
x[x1++] = i;
y[y1++] = j;
}
}
}// 獲得所有皇後的點坐標
for(x1 = 0;x1 < n;x1++){
for(y1 = 0;y1 < n;y1++){
if(x1 == y1)
continue;
if(!checkTwoQuean(x[x1],y[x1],x[y1],y[y1])){ //比較每一次n皇後的點點點點坐標
return false;
}
}
}
if(!checkReNumber(x,y,n)){
return false;
}
return true;
}
刪除重復答案的函數：
? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20/*
* 將確定的解答數組，保存在一個String[]裡面，用來避免重復
* 若重復則返回false
* 不重復則返回true
*/
public boolean checkReNumber(int[] x,int [] y , int n){
String test = null ;
for(int j = 0; j < n;j++){
test += x[j]+""+y[j]+"";
}
for(String st : str){
if(st == null)
continue;
if(st.equals(test)){
return false;
}
}
str[count++] = test;
return true;
}
下面進行對兩個皇後位置的判斷：
? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16/*
* 檢查兩個皇後是否在同一行，同一列，或者同一斜線上
* 存在返回false
* 不存在返回true
*/
public boolean checkTwoQuean(int i , int j , int m ,int n){
if(i == m)
return false;
else if(j == n)
return false;
else if(Math.abs((m - i)) == Math.abs((n - j)))
return false;
else{
return true;
}
}
下面是輸出reserve點的函數：
? 1 2 3 4 5 6 7 8 9public void output(int[][] reserve , int n){
for(int k = 0; k < n;k++){
for(int h = 0;h< n;h++){
if(reserve[k][h] == 0)
continue;
System.out.print(k+","+h+" ");
}
}
}
完，但是效率極低，非常低。
輸出案例：
? 1 2 3 4請輸入皇後數字n：4
0,1 1,3 2,0 3,2
0,2 1,0 2,3 3,1
2
n皇後問題在大於等於4的時候有解
