回溯

• 从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到” 尽头 “的时候, 再倒回出发点, 从另一个可能出发, 继续搜索。这种不断” 回溯 “寻找解的方法, 称作” 回溯法 “。
• 回溯是一种算法思想，可以用递归实现。
• 通俗点讲回溯就是一种试探，类似于穷举，但回溯有“剪枝”功能，比如求和问题。给定7个数字，1 2 3 4 5 6 7求和等于7的组合，从小到大搜索，选择1+2+3+4 =10>7，已经超过了7，之后的5 6 7就没必要在继续了，这就是一种搜索过程的优化。

八皇后问题

• 如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后?
• 为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

算法

1. 逐一尝试当前皇后的摆放位置
2. 如果当前皇后与前面任意皇后处于同一条横行、纵行或斜线上，则跳过循环。
3. 如果当前皇后没有冲突，则确定摆放位置，并摆放下一位皇后
4. 如果所有皇后摆放完毕，则算法结束。

代码

class EightQueen {
int N;
int[] pos;
int[] result;
public EightQueen() {
this.N = 8;
this.pos = new int[this.N];
this.result = new int[this.N];
}
public void setQueen(int k) {
//函数出口
if (k == this.N) {
//保存结果，因为有多种解，可以将结果保存到链表里面。
//本文为了简便，只保存了一组结果。
for (int i = 0; i < pos.length; i++) {
this.result[i] = this.pos[i];
}
return;
}
for (int j = 0; j < pos.length; j++) {
int i;
for (i = 0; i < k; i++) {
//列重复
//斜线重复，|x|=|y|的几何图形正好是斜线
if (this.pos[i] == j || Math.abs(j - this.pos[i]) == Math.abs(i - k)) {
break;
}
}
if (i == k) {
this.pos[i] = j;
setQueen(k + 1);
}
}
}
public void showResult() {
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result.length; j++) {
System.out.print(this.result[i] == j ? "X " : "O ");
}
System.out.println();
}
}
public static void main(String[] args) {
EightQueen eQueen = new EightQueen();
eQueen.setQueen(0);
eQueen.showResult();
}
}

核心回溯函数

	public void setQueen(int k) {
if (k == this.N) {
for (int i = 0; i < pos.length; i++) {
this.result[i] = this.pos[i];
}
return;
}
for (int j = 0; j < pos.length; j++) {
int i;
for (i = 0; i < k; i++) {
//列重复
//斜线重复，|x|=|y|的几何图形正好是斜线
if (this.pos[i] == j || Math.abs(j - this.pos[i]) == Math.abs(i - k)) {
break;
}
}
if (i == k) {
this.pos[i] = j;
setQueen(k + 1);
}
}
}

重点理解

1. 皇后在棋盘上的位置本来应该用二维矩阵表示，但是因为每行只有一个皇后，所以可以用一维数组简化代替。
2. k既可以理解为皇后的序号，也可以理解为矩阵的row。
3. 通常我们对数据（比如矩阵）做双重循环时，习惯性的将外部for循环用于row的迭代，内部for循环用于col的迭代。因为内部循环速度快于外部，于是我们就可以对数据进行从上到下，从左到右的操作。但在这个回溯函数中，我们的外部循环反相当于col迭代，这是因为，对于每一个可能的位置，我们都要和前面所有已经就为的皇后进行比对。
4. pos[i] == j表示当我们将皇后k摆放在j位置时，很不幸皇后i也在j位置，所以列重复
5. Math.abs(k - i) == Math.abs(j - pos[i])表示斜线重复，斜线有4个方向，45°角左上右上左下右下，刚好就是几何方程$|x|=|y|$的样子，进一步展开就是$|x1-x2|=|y1-y2|$

结果

O O O O O O O X
O O O X O O O O
X O O O O O O O
O O X O O O O O
O O O O O X O O
O X O O O O O O
O O O O O O X O
O O O O X O O O

最后

以上就是稳重学姐为你收集整理的算法学习笔记：回溯回溯八皇后问题的全部内容，希望文章能够帮你解决算法学习笔记：回溯回溯八皇后问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。