八皇后问题求解
我今天好不容易上了一次课，然后数据结构老师给我们留大作业，丧心病狂，先解决一个叫八皇后的问题。
题目背景：
【问题描述】
在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。
【问题分析】
数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；
数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经有皇后，则为1，否则为0；
数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇后，则为1，否则为0；
【基本要求】
[if !supportLists]（1） [endif]用递归算法实现
[if !supportLists]（2） [endif]输出所有棋盘状态，其中空的地方为“*”，放置皇后的地方为“@”
11．最小生成树求解
【问题描述】
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
【基本要求】
（1）假设已知n个城市之间的网络是一个带权连通无向图。
（2）用邻接矩阵COST表示给定的带权连通无向图。知阵元素定义为
（3）利用普里姆或克鲁斯卡尔算法求图的最小生成树。
然后我们现在工具问题的描述进行分析：
首先，可归纳问题的条件为，8皇后之间需满足：
1.不在同一行上
2.不在同一列上
3.不在同一斜线上
4.不在同一反斜线上
这为我们提供一种遍历的思路，我们可以逐行或者逐列来进行可行摆放方案的遍历，每一行（或列）遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置与前面的棋子不在同一行（或列）。接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行（或列）所有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行（或列）的所有位置都不合适，就返回上一行（或列）继续该行（或列）的其他位置遍历，当我们顺利遍历到最后一行（或列），且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加一次八皇后可行方案的个数，然后继续遍历该行其他位置是否有合适的，如果没有，则返回上一行，遍历该行其他位置，依此下去。这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程，同时也是经典的递归思路。
接下来，我们以逐列遍历，具体到代码，进一步说明。
首先，从第一列开始找第一颗棋子的合适位置，我们知道，此时第一列的任何一个位置都是合适的，当棋子找到第一个合适的位置后，就开始到下一列考虑下一个合适的位置，此时，第二列的第一行及第二行显然就不能放第二颗棋子了，因为其与第一个棋子一个同在一行，第二列第二行同在一条斜线上。第二列第三行成为第二列第一个合适的位置，以此类推，第三列的第5行又会是一个合适位置，这个过程中，我们注意到，每一列的合适位置都是受到前面几列的位置所影响，归纳如下：
假设前面1列的棋子放在第3行，那当前列不能放的位置就一定是3行，2行，4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、同在斜线、同在反斜线上，不符合我们的要求。现在我们用cols数组来表示8个列棋子所放的行数，数组下标从0开始，其中数组下标表示列数，数组的元素值表示该列棋子所在行数，当前列为N（N>=0,N<8），即cols[N-1]=3,则有：
cols[N] != cols[N-1]（=3，表示不在同一行）
cols[N] != cols[N-1]-1（=3-1=2，表示不在同一斜线上)
cols[N]!=cols[N-1]+1(=3+1,表示不在同一反斜线上)
这里我们注意到，如果N-2列存在的话，那么我们还要考虑当前列N不与N-2列的棋子同行，同斜线，同反斜线。把当前列N的前面的某一列设为m,则m的所有取值为｛m>=0,m
cols[N] != cols[m]（与第m列的棋子不在同一行）
cols[N] != cols[m] -（N-m）(>=0 ,与第m列的棋子不在同一斜线上)
cols[N] != cols[m] + (N-m) (<=8-1,与第m列的棋子不在同一反斜线上)
具体到代码，很显然，取m的所有值只需要一句循环，同时我们为每一列定义一个长度为8的布尔数组row[],下标同样是从0开始，我们规定当row[i]=true时，表示该列第i行不能放棋子。这样我们就能写成下列程序段了：
棋表图
标记
增加一点：你其实也可以这样子想，我某一行和下面一行的横坐标数字相差不能超出集合下标的差。因为你这样子想，我两行最多相差16，因为每次都是先遍历第一行后再遍历第二行，所以不能超出这个范围。
第二点是：不能出现重复元素。重复了还玩个球球。就是集合表示的元素。
public static int num =0; //累计方案总数
public static final int MAXQUEEN =8;//皇后个数，同时也是棋盘行列总数
public static int[]cols =new int[MAXQUEEN]; //定义cols数组，表示8列棋子摆放情况
public Queen8() {//核心函数
getArrangement(0);
System.out.print("/n");
System.out.println(MAXQUEEN+"皇后问题有"+num+"种摆放方法。");
}
public void getArrangement(int n) {
//遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true
boolean[] rows =new boolean[MAXQUEEN];
for (int i =0; i < n; i++) {
rows[cols[i]] =true;
int d = n - i;
if (cols[i] - d >=0) rows[cols[i] - d] =true;
if (cols[i] + d <=MAXQUEEN -1) rows[cols[i] + d] =true;
}
for (int i =0; i
//判断该行是否合法
if (rows[i])continue;
//设置当前列合法棋子所在行数
cols[n] = i;
//当前列不为最后一列时
if (n
getArrangement(n +1);
}else {//累计方案个数
num++;
//打印棋盘信息
printChessBoard();
}
}
}
public void printChessBoard(){
System.out.print("\n"+"第"+num+"种走法 "+"\n");
for(int i=0;i
for(int j=0;j
if(i==cols[j]){
System.out.print("0 ");
}else
System.out.print("+ ");
}
System.out.print("\n");
}
}
public static void main(String args[]){
Queen8 queen =new Queen8();
queen.printChessBoard();
}
思路嘛其实很简单，就是为了避免两个棋子有相互接触的空间，然后先遍历第一行，然后得到位置以后放到数组里面，然后遍历第二行，获取位置放到数组，然后进行比对，看是否合适，合适继续遍历，不合适就重新返回第一行重新规划位置，继续遍历。
这种题目属于深度优先遍历的算法，当然也很无聊。就是平常下棋的时候的用的招数，只是平常没有想到还可以做算法，不过作为锻炼思维，倒是一种很好的玩具。这个算法可以运用到递归，不断判断然后return，继续遍历。
OK，介绍完毕。
