【算法】回溯法四步走 (13)

日期：2021-11-07 栏目：程序人生浏览：次

这为我们提供一种遍历的思路，我们可以逐行或者逐列来进行可行摆放方案的遍历，每一行（列）遍历出一个符合条件的位置，接着就到下一行（列）遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置与前面的棋子不在同一行（列）。

这里我们逐列摆放，数组下标代表列号，用数组元素存放行号。

把当前列 N 的前面的某一列设为 m,则 m 的所有取值为｛m>=0,m<N｝的集合,故又可在上面式子的基础，归纳为如下：

【算法】回溯法四步走

从这个图可以看出，m和N若在同一斜线上，那么行差Am和列差AN应该相等。

【算法】回溯法四步走

所以，在点m存在的情况下，与点m列差为d的点，若行差也为±d，那么就在一条斜线上，不合法。

cols[N] != cols[m]（与第 m 列的棋子不在同一行）

cols[N] != cols[m] - (N-m) （>=0 ,与第 m 列的棋子不在同一斜线上）

cols[N] != cols[m] + (N-m) （<=8-1,与第 m 列的棋子不在同一反斜线上）

我们规定当 row[i]=true 时，表示该列第 i 行不能放棋子。

总结：

编写检测函数：正如上面的分析，每摆一个，将不合法的位置用数组标识，就不涉足了。当然，也可以写成函数，不过没有数组快。

明确函数功能：put(n)为摆第n个皇后。

寻找递归出口：当摆完第八个皇后；不同行、不同斜线、不同反斜线。

明确所有路径：八行。

回溯还原现场：不需要还原，没有破坏现场，因为检测的时候提前用数组标识了，所以不合法的现场都没涉足。

这样我们就能写成下列程序段了：

// 八皇后 class Sy6 { public static int num = 0; // 累计方案总数 public static final int MAXQUEEN = 8;// 皇后个数，同时也是棋盘行列总数 public static int[] cols = new int[MAXQUEEN]; // 定义cols数组，表示8列棋子摆放情况，数组元素存放行号 public Sy6() { // 核心函数 put(0); System.out.println(MAXQUEEN + "皇后问题有" + num + "种摆放方法。"); } public void put(int n) { // 当摆完第八个皇后，摆第九个时 if (n > MAXQUEEN - 1) { // 累计方案个数 num++; return; } // 遍历该列所有不合法的行，并用 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) // 判断是否超界 // 行差为-d的斜线点，不合法 rows[cols[i] - d] = true; if (cols[i] + d <= MAXQUEEN - 1)// 判断是否超界 // 行差为d的斜线点，不合法 rows[cols[i] + d] = true; } // 所有路径：八行都能摆 for (int i = 0; i < MAXQUEEN; i++) { // 判断该行是否合法，如果不合法，那就继续下一轮 if (rows[i]) continue; // 设置当前列合法棋子所在行数 cols[n] = i; // 摆放下一个 put(n + 1); } } public static void main(String args[]) { Sy6 queen = new Sy6(); } }

程序运行结果：

【算法】回溯法四步走