回溯可以理解为, 通过选择不同的岔路口来通往目的地, 每一步都选择一条路出发, 能进则进, 不能则退回上一步, 换一条路再尝试
树和图的深度优先搜索, 八皇后, 走迷宫都是典型的回溯应用
树的深度搜索
八皇后
在8 * 8 的国际象棋上摆放八个皇后, 使其不能相互攻击, 任意两个皇后都不能处于同一行, 同一列, 同一斜线上, 总共有多少摆法?
八皇后问题
解决思路
暴力法, 将每一种摆法进行尝试, 检查是否可行, 复杂度较高
回溯法, 回溯剪枝
回溯法求解
剪枝处理, 去除不合理的分支
剪枝
八皇后1
八皇后2
八皇后3
/**
* 数组索引是行号, 数组元素是列号
*/
int[] cols;
/**
* 多少种摆放
*/
int ways;
void palceQueens(int n) {
if (n < 1) return;
cols = new int[n];
place(0);
System.out.println(n + "皇后一共有" + ways + "种摆法");
}
void place(int row) {
if (row == cols.length) {
ways++;
show();
return;
}
for (int col = 0; col < cols.length; col++) {
if (isValid(row, col)) {
cols[row] = col;
place(row + 1);
}
}
}
/**
* 判断第row 行第col 列是否可以摆放皇后
* @param row
* @param col
* @return
*/
boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
// 第col 列已经有皇后
if (cols[i] == col) {
// System.out.println("[" + row + "][" + col + "]=false");
return false;
}
// 第i 行的皇后跟第row 行第col 列处在同一斜线上
if (row - i == Math.abs(col - cols[i])) {
// System.out.println("[" + row + "][" + col + "]=false");
return false;
}
}
// System.out.println("[" + row + "][" + col + "]=true");
return true;
}
void show() {
for (int row = 0; row < cols.length; row++) {
for (int col = 0; col < cols.length; col++) {
if (cols[row] == col) {
System.out.print("1 ");
} else {
System.out.print("0 ");
}
}
System.out.println();
}
System.out.println("-----------------------------");
}
优化
增加记录左上和右上的变量是否摆放了皇后
/**
* 数组索引时行号, 数组元素是列号
*/
int[] queens;
/**
* 标记某一行是否是皇后
*/
boolean[] cols;
/**
* 标记某一斜线上是否有皇后, 左上角 -> 右下角
*/
boolean[] leftTop;
/**
* 标记斜线, 右上角 -> 左下角
*/
boolean[] rightTop;
/**
* 摆法
*/
int ways;
void placeQueens(int n) {
if (n < 1) return;
queens = new int[n];
cols = new boolean[n];
leftTop = new boolean[(n << 1) - 1];
rightTop = new boolean[leftTop.length];
place(0);
System.out.println(n + "皇后共有" + ways + "种摆法");
}
/**
* 从第row 行开始摆放
* @param row
*/
void place(int row) {
if (row == cols.length) {
ways++;
show();
return;
}
for (int col = 0; col < cols.length; col++) {
if (cols[col]) continue;
// 左上角公式
int ltIndex = row - col + cols.length - 1;
if (leftTop[ltIndex]) continue;
// 右上角公式
int rtIndex = row + col;
if (rightTop[rtIndex]) continue;
queens[row] = col;
cols[col] = true;
leftTop[ltIndex] = true;
rightTop[rtIndex] = true;
// 注意将之前的值恢复
place(row + 1);
cols[col] = false;
leftTop[ltIndex] = false;
rightTop[rtIndex] = false;
}
}
void show() {
for (int row = 0; row < cols.length; row++) {
for (int col = 0; col < cols.length; col++) {
if (queens[row] == col) {
System.out.print("1 ");
} else {
System.out.print("0 ");
}
}
System.out.println();
}
System.out.println("-----------------------------");
}
继续优化
使用位运算, 0 和1 记录当前位置是否摆放了皇后
int ways;
/**
* 数组索引是行号, 元素是列号
*/
int[] queens;
/**
* 标记某一列是否有皇后
*/
byte cols;
/**
* 斜线上是否有皇后, 左上角 -> 右下角
*/
short leftTop;
/**
* 斜线上是否有皇后, 右上角 -> 左下角
*/
short rightTop;
void placeQueens(int n) {
if (n < 1) return;
queens = new int[n];
place(0);
System.out.println(n + "皇后一共有" + ways + "种摆法");
}
void place(int row) {
if (row == 8) {
ways++;
show();
return;
}
for (int col = 0; col < 8; col++) {
int cv = 1 << col;
if ((cols & cv) != 0) continue;
int lv = 1 << (row - col + 7);
if ((leftTop & lv) != 0) continue;
int rv = 1 << (row + col);
if ((rightTop & rv) != 0) continue;
queens[col] = col;
cols |= cv;
leftTop |= lv;
rightTop |= rv;
place(row + 1);
// 恢复状态
cols &= ~cv;
leftTop &= ~lv;
rightTop &= ~rv;
}
}
void show() {
for (int row = 0; row < 8; row++) {
for (int col = 0; col < 8; col++) {
if (queens[row] == col) {
System.out.print("1 ");
} else {
System.out.print("0 ");
}
}
System.out.println();
}
System.out.println("-----------------------------");
}
