实验内容
（1）八皇后及N皇后问题
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。
请编程实现八皇后问题，并把92种解的前三种解输出到屏幕（8*8的二维矩阵，Q代表皇后，X代表空）。并把此问题的求解过程延伸到N皇后问题。
代码实现：
package com.alogrithm;
public class NQueen {
private int queenCount ; //皇后个数
private int[] feasible ; //可接受的分配方案,feasible为皇后所在行,feasible[n]为第n行皇后所在列
private int[] vol={0,0,0,0,0,0,0,0};//保存所在列值，用于将置放皇后所在位置的值置为1
private long sum ; //当前已找到的可行方案数
private static int index ; //记录遍历方案序数
private int[][] location;//皇后所在的位置i，j第i行第j列
/**
*
* @param n 皇后的个数
*/
public NQueen(int n){
sum = 0 ; //初始化方案数为1，当回溯到最佳方案的时候，就自增1
queenCount = n ; //求n皇后问题，由自己定义
feasible = new int[n+1]; //x[i]表示皇后i放在棋盘的第i行的第x[i]列
index = 1 ; //这个是我额外定义的变量，用于遍历方案的个数，请看backTrace()中h变量的作用，这里将它定义为static静态变量
location = new int[n][n];
for(int i=0;i<queenCount;i++){
for(int j=0;j<queenCount;j++)
location[i][j]=0;
}
}
/**
*
* @param k 第k行判断
* @return 是否可置于该位置
*/
public boolean place (int k){
for (int j = 1 ; j < k ; j++){
//皇后所在的位置不可同行，同列，且斜率不为-1或1
if ( (Math.abs(k - j)) == (Math.abs(feasible[j]-feasible[k])) || (feasible[j] == feasible[k]) ){
return false;
}
}
return true ;
}
/**
*
* @param t 检测后可放置的皇后个数
*/
public void backTrace (int t){
//t大于皇后的数目
if (t > queenCount){
sum ++ ; //可行方案数+1
System.out.println ("可行方案" + (index++) + "↓");
output(feasible);
System.out.println("------------------------------");
}
//t小于皇后的数目
else {
//扩展queenCount个子节点
for (int i = 1 ; i <= queenCount ; i++){
feasible[t] = i ;
if (place (t)){ //检查子结点的可行性
backTrace (t+1);//递归调用
}
}
}
}
/**
*
* @param mid 中间变量
*/
public void output (int[] mid){
for (int i = 1 ; i < mid.length ; i++){
vol[i-1] =mid[i];//可放置皇后的列值
}
//将皇后所在的位置的值为1
for(int n=0;n<location.length;n++){
location[n][vol[n]-1] = 1;
}
//输出皇后所在位置的数组，1为皇后所在的位置
for(int m=0;m<location.length;m++){
for(int n=0;n<location[m].length;n++){
if(location[m][n] == 1){
//删除最后一个','
if(n==location.length-1)
System.out.print("Q");
else
System.out.print("Q,");
}
else{
//删除最后一个','
if(n==location.length-1)
System.out.print("X");
else
System.out.print("X,");
}
}
//将皇后所在位置的置置为0，以便下一次数组安排皇后的位置
location[m][vol[m]-1] = 0;
System.out.println();
}
}
public static void main (String[] args){
System.out.println("------------------------------");
NQueen queen= new NQueen(7);
queen.backTrace(1); //从1开始回溯
System.out.println ("\n综上所述，"+queen.queenCount+"皇后的可行方案个数为:" + queen.sum);
}
}
运行结果：
