回溯算法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
算法应用
八皇后问题
八皇后问题，是一个古老而著名的问题，是 回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。
/**
* 八皇后
* 皇后的横列纵列 正斜反斜方不能放皇后
* 回溯法
* 2017年9月8日 下午10:20:39
*
*/
public class Queen {
public static int num = 0;// 累计方案
public static final int MAXQUEEN = 8;
public static int[] cols = new int[MAXQUEEN];// 定义cols数组，每位的数字表示对应列的棋子所在行
/**
*
* @param n 填第n列的皇后
*/
public void getCount(int n) {
boolean[] rows = new boolean[MAXQUEEN];// 记录每列每个方格是否可以放皇后
// 循环已经填过的列
for (int m = 0; m < n; m++) {
// col[m]表示m列棋子所在的的行
// 棋子所在列不可填
rows[cols[m]] = true;
// m表示正在遍历的列，n表示要填的列
// d表示两列的距离，斜对角的差值
int d = n - m;// 斜对角
// 正斜方向
// m列棋子所在的行-差值 表示正斜方向/的对应行
if (cols[m] - d >= 0) {
// 正斜方向对应行不可填
rows[cols[m] - d] = true;
}
// 反斜方向
// m列棋子所在行+差值 表示反斜方向\的对应行
if (cols[m] + d <= (MAXQUEEN - 1)) {
// 反斜方向对应行不可填
rows[cols[m] + d] = true;
}
}
// 到此知道了哪些位置不能放皇后
for (int i = 0; i < MAXQUEEN; i++) {
// 如果该行为true
if (rows[i]) {
// 不能放
continue;
}
// n列该行可以放
cols[n] = i;
// 如果n不是第8列
if (n < MAXQUEEN - 1) {
// 递归寻找下一列
getCount(n + 1);
} else {
// 找到完整的一套方案
num++;
// 打印本套方案
printQueen();
}
// 下面可能仍然有合法位置
}
}
private void printQueen() {
System.out.println("第" + num + "种方案");
for (int i = 0; i < MAXQUEEN; i++) {
for (int j = 0; j < MAXQUEEN; j++) {
if (i == cols[j]) {
System.out.print("0 ");
} else {
System.out.print("+ ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
Queen queen = new Queen();
queen.getCount(0);
}
}
更新
