问题描述：
在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;
}
}