問題描述：
在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法
思路介紹：
其實這個題是回溯法的典型的應用，所謂回溯法就是先定義一個可以的解，然後從這個解出發往下一個解走去，以此類推，如果有一個解不成立就退回到他的上一步，再重新找解就僅此而已…
步驟如下：
就拿四皇後來說吧
我們首先需要建立一個一維數組：這個數組裡存放的就是皇後在該列合适的位置
這個數組存放的是皇後放的行數，我們首先在第一列中找一個可以放的地方，很明顯第一個位置就可以放是滿足條件的，即大緻皇後的方格如下：
| A |
|---|
此時n=0，代表第一列已經放好了，并且放在了第一行，大緻的圖形如下：
| A | 1 | ||
|---|---|---|---|
| 2 | |||
| 3 | |||
| – | – | – | – |
然後n+1即開始在下一列找合适的位置，經過測試發現1，2位置都是不合适的，是以我們就要把第二列的皇後放在第三行了，即圖形大緻如下：
此時的n=1
| 2 |
|---|
| A | 1 |
|---|---|
| 2 | |
| A | 3 |
| 5 | 4 |
然後n=n+1=2,即在第三列放一個皇後，可是經過測試發現1、2、3、4的位置都不滿足條件，這時候就要回溯帶n=1的時候了，即array[1]=2是不合适的，是以此時要繼續往下走了，即array[1]=3了，此時的情況大緻如下了
n=1
| 3 |
|---|
| A | 1 |
|---|---|
| 2 | |
| 3 | |
| A | 4 |
然後n=n+1=2，經過檢測發現第三行的1、3、4都是不合适的，是以第三列的應該放在2的位置，即array[2]=1；此時的位置應該大緻如下：
| 3 | 2 |
|---|
| A | 1 |
|---|---|
| A | 2 |
| 3 | |
| A | 4 |
然後n=n+1=3，即要給第四列放上一個皇後，但是經過比較發現1、2、3、4都是不合适的，這時候要回溯到n=2的時候了，當n=2的時候，經過比較可以發現，皇後已經沒有可以放得位置了，是以要回溯到n=1的時候了，當n=1的時候，由比較可以知此時已經沒有合适的位置了，那就隻能再回溯到n=0的時候了，此時明顯array[0]=0是不合适的了，是以array[0]=1，大緻的圖形如下：
| 1 |
|---|
| 1 | |
|---|---|
| A | 2 |
| 3 | |
| 4 |
然後n=n+1=1，此時發現1、2、3都不合适的，隻有一個4是合适的，故array[1]=3,
圖形大緻如下：
| 1 | 3 |
|---|
| 1 | |
|---|---|
| A | 2 |
| 3 | |
| A | 4 |
然後n=n+1=2,此時經過比較發現1的位置是合适的，故array[2]=0，圖形大緻如下：
| 1 | 3 |
|---|
| A | 1 |
|---|---|
| A | 2 |
| 3 | |
| A | 4 |
然後n=n+1=3，即在第四列找合适的位置，經過比較發現第四列可以放在3的位置上，大緻的圖形如下：
| 1 | 3 | 2 |
|---|
| A |
|---|
| A |
| A |
| A |
至此第一種情況已經找到了，然後就一直用回溯直到array[0]=3,然後就可以得出最後的結果了…
代碼如下
public class Main {
static int array[]=new int[4];
static int number=4;
static int count=0;
public static void main(String[] args) {
operate(0);
System.out.println(count);
}
public static void operate(int n ) {
if(n==number)
{
count++;
return ;
}
else if(n<number)
{
for(int i=0;i<number;i++)
{
array[n]=i;
if(panduan(n))
operate(n+1);
}
}
}
public static boolean panduan(int n) {
for(int i=0;i<n;i++)
if((array[i]==array[n])||(Math.abs(n-i)==Math.abs(array[i]-array[n])))
//判斷下一個皇後是否和上一個皇後在同一行或者是對角線
return false;
return true;
}
}