【算法】回溯法四步走

# 回溯法 对于回溯法，网上有很多种解释，这里我依照自己的（死宅）观点做了以下三种通俗易懂的解释： - **正经版解释：**其实人生就像一颗充满了分支的n叉树，你的每一个选择都会使你走向不同的路线，获得不同的结局。如果能重来，我要选李白~呸！说错了，如果能重来，我们就能回溯到以前，选择到最美好的结局。 - **游戏版解释：**玩过互动电影游戏（如 行尸走肉）的都知道，你的每个选择都会影响游戏的结局，掌控他人的生死。每次选择错误导致主角或配角死亡，我们是不是回溯读档，希望得到一个更好的结局。 > **PS：**克莱曼婷天下无敌！ - **动漫版解释：**看过主角拥有死亡回归（疯狂暗示486）的都知道，主角的每个选择都能影响大局，可是486直接能回溯重选，这与我们今天要讲的回溯法极其相似。 > **PS：**爱蜜莉雅、雷姆我都要！ ## 专业名词 - **解空间：**即 所有的可能情况 ## 概念 > **回溯算法：**是类似于枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 它是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为**回溯法**，而满足回溯条件的某个状态的点称为**“回溯点”**（你也可以理解为**存档点**）。  上图为八皇后的解空间树，**如果当前点不符合要求就退回再走**。 许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 ## 基本思想 在包含问题的所有解的解空间树中，按照**深度优先搜索**的策略，从根结点出发深度探索解空间树。 当探索到某一结点时，要先判断该结点是否包含问题的解： - 如果**包含**，就从该结点出发继续探索下去； - 如果该结点**不包含**问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法） --- **结束条件：** - 若用回溯法求问题的**所有解**时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 - 若使用回溯法求**任一个解**时，只要搜索到问题的一个解就可以结束。 ## 网上的一般步骤 虽然我觉得网上的一般步骤太抽象了，但是还是摆在这里供大家参考吧。。 1. **针对所给问题，确定问题的解空间：** 首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。 2. **确定结点的扩展搜索规则：** 及时确定规则，并不是每个解空间都要走完才能发现是死路的，有时候走到一半就发现不满足条件了。 3. **以深度优先方式搜索解空间**，并在搜索过程中**用剪枝函数避免无效搜索：** 不满足条件的路径及时剪掉（即 剪枝），避免继续走下去浪费时间。 > **类比：**比如说**削苹果**， 我们规定：苹果皮必须不断，要完整地削完整个苹果。 那么，如果我们削到一半苹果皮断掉了，我们就可以直接退回去（即 回溯）换个苹果削了，如果继续削下去，只会浪费时间。 ## 算法框架 **问题框架：** 设问题的**解**是一个**n维向量(a1,a2,………,an)**，**约束条件**是**ai(i=1,2,3,…..,n)之间**满足某种条件，记为 **f(ai)**。 ### 非递归回溯框架 其中，**a[n]**为解空间，**i**为搜索的深度，框架如下： ``` int a[n],i; //a[n]为解空间，i为深度 初始化数组 a[]; i = 1; while (i>0(有路可走) and (未达到目标)) { //还未回溯到头 if(i > n) { //搜索到叶结点 搜索到一个解，输出； } else { //处理第 i 个元素 a[i]第一个可能的值； while(a[i]在不满足约束条件且在搜索空间内) { a[i]下一个可能的值； }//while if(a[i]在搜索空间内) { 标识占用的资源； i = i+1; //扩展下一个结点 } else { 清理所占的状态空间； //回溯 i = i – 1; }//else }//else }//while ``` ### 递归回溯框架 **回溯法**是对解空间的**深度优先搜索**，在一般情况下使用**递归函数**来实现回溯法比较简单。 其中，**a[n]**为解空间，**i**为搜索的深度，框架如下： ``` int a[n]; //a[n]为解空间 BackTrace(int i) { //尝试函数，i为深度 if(i>n) { 输出结果; } else { for(j = 下界; j <= 上界; j=j+1) { //枚举 i 所有可能的路径 if(check(j)) { //检查满足限界函数和约束条件 a[i] = j; ... //其他操作 BackTrace(i+1); 回溯前的清理工作（如 a[i]置空值等）; }//if }//for }//else }//BackTrace ``` ## 回溯四步走 由于上述网上的步骤太抽象了，所以在这里我自己总结了回溯四步走： - **编写检测函数：**检测函数用来检测此路径是否满足题目条件，是否能通过。 > 这步不做硬性要求。。不一定需要 1. **明确函数功能：**要清楚你写这个函数是想要做什么； 2. **寻找递归出口：**一般为某深度，或叶子节点。 3. **明确所有路径**（选择）**：**这个构思路径最好用**树形图**表示。 > **例如：**走迷宫有上下左右四个方向，也就是说我们站在一个点处有四种选择，我们可以画成无限向下延伸的四叉树。 直到向下延伸到叶子节点，那里便是出口； 从根节点到叶子节点沿途所经过的节点就是我们满足题目条件的选择。 4. **回溯还原现场：**若**该节点所有选择已做完却仍然没有找到出口**，那么我们需要**回溯还原现场**，将该节点重置为初始状态，回溯到一切都没有发生的时候，再退回去。 > **注意：**回溯还原现场是必要的，如果不还原现场，那你的回溯有什么意义呢。。 >> **类比：**大雄出意外了，哆啦A梦坐时空机回到过去想要改变这一切，结果过去的一切都没有被重置到初始状态，回到过去大雄还是现在这种受伤的样子没有改变，那么回到过去有什么意义呢。 ### 编写检测函数（非必须） > **第一步**，写出检测函数，来检测这个路径是否满足条件，是否能通过。 这个函数依据题目要求来编写，当然，如果要求不止一个，可能需要编写多个检测函数。 --- **例如：**凑算式  这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。 比如： 6+8/3+952/714 就是一种解法， 5+3/1+972/486 是另一种解法。 这个算式一共有多少种解法？ --- 要做出这个题， **第一步**，要写出检测函数 ``` public static int sum = 0; // 用来存放总共的解法数 public static double[] a = new double[10]; // 判断数组里前j个元素是否与t相同 /** * @param a 传入一个数组a * @param j 判断前j个元素 * @param t 是否与t相同 * @return */ public static boolean same(double[] a, int j, int t) { for (int i = 1; i < j; i++) { if (a[i] == t) { return true; } } return false; } /** * @param a 判断a数组是否满足表达式 * @return 如果满足就true，不满足就false */ public static boolean expression(double[] a) { if ((a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]) == 10)) return true; else return false; } ``` ### 明确函数功能 由于此题要填数字，所以我们定义choose(i)的含义为：在算式中自动填入数字 i 。 ### 寻找递归出口 **第二步**，要寻找递归出口，当1~9均已填入后，判断表达式是否成立，若成立，则输出。 ``` // 如果选择的数字大于9，则代表1~9均已选完，判断是否满足表达式，输出选择的表达式 if (i > 9) { if (expression(a)) { for (int x = 1; x < 10; x++) { System.out.print(a[x] + " "); } System.out.println(); sum++; } return; } ``` ### 明确所有路径 > **第三步**，要知道这个递归是几个选择，即 几叉树。 此题为1~9九个选择，九条路，九叉树。 ``` for (int j = 1; j <= 9; j++) { // 如果将要填入的数与前面不冲突，则填入 if (!same(a, i, j)) { a[i] = j; choose(i + 1); } } ``` ### 回溯还原现场 > **第四步**，若该节点没有找到出口，则将当前位置回溯，还原现场，重新选择 在本题中，**还原现场**即 重置为0（表示还未填入1~9的数字） ``` for (int j = 1; j <= 9; j++) { // 如果将要填入的数与前面不冲突，则填入 if (!same(a, i, j)) { a[i] = j; choose(i + 1); //若没有找到出口，则将当前位置重置为0，回溯，还原现场 a[i] = 0; } } ``` # 实例 ## 凑算式  这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。 比如： 6+8/3+952/714 就是一种解法， 5+3/1+972/486 是另一种解法。 这个算式一共有多少种解法？ --- **答案：** ``` // 凑算式 public class Sy1 { public static void main(String[] args) { // TODO Auto-generated method stub choose(1); System.out.println("一共"+sum+"种解法"); } public static int sum = 0; // 用来存放总共的解法数 public static double[] a = new double[10]; // 判断数组里前j个元素是否与t相同 /** * @param a 传入一个数组a * @param j 判断前j个元素 * @param t 是否与t相同 * @return */ public static boolean same(double[] a, int j, int t) { for (int i = 1; i < j; i++) { if (a[i] == t) { return true; } } return false; } /** * @param a 判断a数组是否满足表达式 * @return 如果满足就true，不满足就false */ public static boolean expression(double[] a) { if ((a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]) == 10)) return true; else return false; } /** * @param i 选择第i个数字 递归 */ public static void choose(int i) { // 如果选择的数字大于9，则代表1~9均已选完，输出选择的表达式 if (i > 9) { if (expression(a)) { for (int x = 1; x < 10; x++) { System.out.print(a[x] + " "); } System.out.println(); sum++; } return; } for (int j = 1; j <= 9; j++) { // 如果将要填入的数与前面不冲突，则填入 if (!same(a, i, j)) { a[i] = j; choose(i + 1); //若没有找到出口，则将当前位置重置为0，回溯，还原现场 a[i] = 0; } } } } ``` **程序运行结果：** ``` 3.0 5.0 1.0 9.0 7.0 2.0 4.0 8.0 6.0 4.0 9.0 3.0 5.0 2.0 8.0 1.0 7.0 6.0 5.0 3.0 1.0 9.0 7.0 2.0 4.0 8.0 6.0 5.0 4.0 3.0 7.0 2.0 6.0 1.0 9.0 8.0 5.0 4.0 9.0 7.0 3.0 8.0 1.0 6.0 2.0 5.0 8.0 6.0 4.0 7.0 3.0 1.0 2.0 9.0 6.0 4.0 2.0 3.0 5.0 8.0 1.0 7.0 9.0 6.0 4.0 2.0 7.0 1.0 8.0 3.0 5.0 9.0 6.0 7.0 3.0 4.0 8.0 5.0 2.0 9.0 1.0 6.0 8.0 3.0 9.0 5.0 2.0 7.0 1.0 4.0 6.0 9.0 8.0 4.0 3.0 7.0 1.0 5.0 2.0 7.0 1.0 4.0 9.0 6.0 8.0 3.0 5.0 2.0 7.0 3.0 2.0 8.0 1.0 9.0 5.0 4.0 6.0 7.0 3.0 2.0 9.0 8.0 1.0 6.0 5.0 4.0 7.0 5.0 3.0 2.0 6.0 4.0 1.0 9.0 8.0 7.0 5.0 3.0 9.0 1.0 2.0 6.0 8.0 4.0 7.0 9.0 6.0 3.0 8.0 1.0 2.0 5.0 4.0 7.0 9.0 6.0 8.0 1.0 3.0 5.0 4.0 2.0 8.0 1.0 3.0 4.0 6.0 5.0 2.0 7.0 9.0 8.0 6.0 9.0 7.0 1.0 2.0 5.0 3.0 4.0 8.0 7.0 6.0 1.0 9.0 5.0 2.0 3.0 4.0 9.0 1.0 3.0 4.0 5.0 2.0 6.0 7.0 8.0 9.0 1.0 3.0 5.0 2.0 4.0 7.0 8.0 6.0 9.0 2.0 4.0 1.0 7.0 8.0 3.0 5.0 6.0 9.0 2.0 4.0 3.0 5.0 8.0 7.0 1.0 6.0 9.0 3.0 4.0 1.0 5.0 7.0 6.0 2.0 8.0 9.0 4.0 8.0 1.0 7.0 6.0 3.0 5.0 2.0 9.0 4.0 8.0 3.0 5.0 6.0 7.0 1.0 2.0 9.0 6.0 8.0 1.0 4.0 3.0 5.0 7.0 2.0 一共29种解法 ``` ## 方格填数 如下的10个格子填入0~9的数字。  - 要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻） 一共有多少种可能的填数方案？ --- **答案：** ``` // 方格填数 public class Sy2 { public static void main(String[] args) { // TODO Auto-generated method stub Block bk = new Block(); bk.init(); bk.addNum(0);// , 0, 0); System.out.println("一共"+Block.sum+"种方案"); } } class Block { public int[][] b = new int[3][4]; public static int sum; /** * 初始化整个数组 */ public void init() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { b[i][j] = -2; } } } /** * @param y y行 * @param x x列 * @param n 填数n * @return 返回此方格是否能填数 */ public boolean isAble(int y, int x, int n) { // y行 x列 填数n if (b[y][x] != -2) return false; for (int j = y - 1; j <= y + 1; j++) { for (int i = x - 1; i <= x + 1; i++) { if (j < 3 && j >= 0 && i < 4 && i >= 0) { if (b[j][i] == n - 1 || b[j][i] == n + 1) { return false; } } } } return true; } /** * @param n 填入数字n */ public void addNum(int n) { if (n > 9) { sum++; return; } for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { if ((i == 0 && j == 0) || (i == 2 && j == 3)) continue; // 如果此方格能填数，则填入数字 if (this.isAble(i, j, n)) { b[i][j] = n; this.addNum(n + 1);// , y, x+1); b[i][j] = -2; // 当加入下一个不行返回后，还原现在方块，继续循环 } } } } } ``` **程序运行结果：** ``` 一共1580种方案 ``` ## 蛙跳河 在一个 5\*5 的地图上，一只蛙欲从起点跳到目的地。中间有一条河（如图），但这只蛙不会游泳，并且每次跳只能横着跳一格或者竖着跳一格。（聪明的蛙不会跳已经跳过的路） 1. 总共有多少种跳法。 2. 给出路径最短的跳法。  --- **答案：** - 明确函数功能：jump(m, n)为跳到(m, n)位置。 - 寻找递归出口：不在边界之内 或 已走过。 - 明确所有路径：右跳、左跳、下跳、上跳 - 回溯还原现场： path--; // 回溯法关键步骤 a[m][n] = 0; ``` //青蛙跳 public class Sy1 { static int count = 0; // 跳法种类计数 static int x = 4, y = 4; // 目的坐标 static int step = 0; // 记录步数 // 地图，0代表没有走过，1 代表已经走过 static int[][] map = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 1, 1, 0, 1, 1 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; static int min = 25; // 用来记录最小步数 static int sx[] = new int[25], sy[] = new int[25]; // 记录坐标 // 求解总共跳法，并求出最短步数，方便下面列出路径 static void jump(int m, int n) { if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { // 该点在地图边界之内并且未走过 return; } map[m][n] = 1; // 走到此节点 step++; if (m == x && n == y) { // 如果到达目的地 if (step < min)// 更新最短步数 min = step; count++; } // 所有路径 jump(m + 1, n); // 右跳 jump(m - 1, n); // 左跳 jump(m, n + 1); // 下跳 jump(m, n - 1); // 上跳 step--; // 回溯法关键步骤 map[m][n] = 0; } // 列出最短步数的路径 static void find(int m, int n) { if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { // 该点在地图边界之内并且未走过 return; } // 记录坐标 sx[step] = m; sy[step] = n; // 走到此节点 map[m][n] = 1; step++; if (m == x && n == y && step == min) { // 到达目的且为最短路径 int p = min - 1; System.out.print("最短 path:" + p + "步"); for (int i = 0; i < min; i++) System.out.print("(" + sx[i] + "," + sy[i] + ")"); System.out.println(); } find(m + 1, n); find(m - 1, n); find(m, n + 1); find(m, n - 1); step--; map[m][n] = 0; } public static void main(String[] args) { jump(0, 0); step = 0; System.out.println("总共" + count + "种解法"); find(0, 0); } } ``` **程序运行结果：**  ## 走迷宫 以一个 M×N 的长方阵表示迷宫，**0** 和 **1** 分别表示迷宫中的**通路**和**障碍**。 设计一个程序，对任意输入的迷宫，输出一条从入口到出口的通路，或得出没有通路的结论。 例： 输入： 请输入迷宫的行数 9 请输入迷宫的列数 8 请输入 9 行 8 列的迷宫 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 为了方便大家观看，我换成了矩阵： $$ \begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{matrix} $$ 输出： 有路径 路径如下： \# \# 1 0 0 0 1 0 0 \# 1 0 0 0 1 0 \# \# 1 0 1 1 0 1 \# 1 1 1 0 0 1 0 \# \# \# 1 \# \# \# 0 0 1 \# \# \# 1 \# 1 0 1 1 1 1 0 \# 1 1 1 0 0 0 1 \# 1 1 1 0 0 0 0 \# \# 为了方便大家观看，我换成了矩阵： $$ \begin{matrix} \# & \# & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & \# & 1 & 0 & 0 & 0 & 1 & 0 \\ \# & \# & 1 & 0 & 1 & 1 & 0 & 1 \\ \# & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ \# & \# & \# & 1 & \# & \# & \# & 0 \\ 0 & 1 & \# & \# & \# & 1 & \# & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & \# & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & \# & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & \# & \# \\ \end{matrix} $$ --- **答案：**这里用栈来实现的递归，算是一个新思路。 ``` //迷宫 /*位置类*/ class Position { int row; int col; public Position() { } public Position(int row, int col) { this.col = col; this.row = row; } public String toString() { return "(" + row + " ," + col + ")"; } } /*地图类*/ class Maze { int maze[][]; private int row = 9; private int col = 8; Stack stack; boolean p[][] = null; public Maze() { maze = new int[15][15]; stack = new Stack(); p = new boolean[15][15]; } /* * 构造迷宫 */ public void init() { Scanner scanner = new Scanner(System.in); System.out.println("请输入迷宫的行数"); row = scanner.nextInt(); System.out.println("请输入迷宫的列数"); col = scanner.nextInt(); System.out.println("请输入" + row + "行" + col + "列的迷宫"); int temp = 0; for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp = scanner.nextInt(); maze[i][j] = temp; p[i][j] = false; } } } /* * 回溯迷宫，查看是否有出路 */ public void findPath() { // 给原始迷宫的周围加一圈围墙 int temp[][] = new int[row + 2][col + 2]; for(int i = 0; i < row + 2; ++i) { for(int j = 0; j < col + 2; ++j) { temp[0][j] = 1; temp[row + 1][j] = 1; temp[i][0] = temp[i][col + 1] = 1; } } // 将原始迷宫复制到新的迷宫中 for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp[i + 1][j + 1] = maze[i][j]; } } // 从左上角开始按照顺时针开始查询 int i = 1; int j = 1; p[i][j] = true; stack.push(new Position(i, j)); while (!stack.empty() && (!(i == (row) && (j == col)))) { if ((temp[i][j + 1] == 0) && (p[i][j + 1] == false)) { p[i][j + 1] = true; stack.push(new Position(i, j + 1)); j++; } else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) { p[i + 1][j] = true; stack.push(new Position(i + 1, j)); i++; } else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) { p[i][j - 1] = true; stack.push(new Position(i, j - 1)); j--; } else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) { p[i - 1][j] = true; stack.push(new Position(i - 1, j)); i--; } else { stack.pop(); if(stack.empty()) { break; } i = stack.peek().row; j = stack.peek().col; } } Stack newPos = new Stack(); if (stack.empty()) { System.out.println("没有路径"); } else { System.out.println("有路径"); System.out.println("路径如下："); while (!stack.empty()) { Position pos = new Position(); pos = stack.pop(); newPos.push(pos); } } /* * 图形化输出路径 * */ String resault[][]=new String[row+1][col+1]; for(int k=0; k= m || y >= n || !maze[x][y].equals("0")) { // 注意字符串要用equals return; } maze[x][y] = "#"; // 走到此节点 if (x == m - 1 && y == n - 1) { for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { System.out.print(maze[i][j] + " "); } System.out.println(); } System.out.println("--------------------------------------------------------"); } find(x + 1, y); //下移 find(x - 1, y); //上移 find(x, y + 1); //右移 find(x, y - 1); //左移 maze[x][y] = "0"; } } ``` **程序运行结果：** ``` -------------------------------------------------------- 迷宫如下： 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 -------------------------------------------------------- # 0 1 0 0 0 1 0 # 0 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 # # 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # 0 1 0 0 0 1 0 # 0 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 0 0 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # 0 1 0 0 0 1 0 # # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 # # 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # 0 1 0 0 0 1 0 # # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 0 0 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # # 1 0 0 0 1 0 0 # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 # # 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # # 1 0 0 0 1 0 0 # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 0 0 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # # 1 0 0 0 1 0 # # 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 # # 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # # 1 0 0 0 1 0 # # 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 0 0 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- ``` ## 马走日 假设国际象棋棋盘有 5\*5 共 25 个格子。 设计一个程序，使棋子从初始位置（棋盘编号为 1 的位）开始跳马，能够把棋盘的格子全部都走一遍，每个格子只允许走一次。 1. 输出一个如图 2 的解，左上角为第一步起点。 2. 总共有多少解。 > **PS：**国际象棋的棋子是在格子中间的。国际象棋中的“马走日”，如下图所示，第一步为[1,1], 第二步为[2,8]或[2,12]，第三步可以是[3,5]或[3,21]等，以此类推。  --- **答案：** - 明确函数功能：jump(m, n)为跳到(m, n)位置。 - 寻找递归出口：不在边界之内 或 已走过。 - 明确所有路径：8个方位， > **技巧：**这里可以用一个数组存入八个方位的变化，再用循环依次取出，比写八个方位要聪明许多。 - 回溯还原现场： path--; // 回溯法关键步骤 a[m][n] = 0; ``` //马走日 class Sy2 { private static int[][] next = { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 } }; // 马的跳跃路径（技巧） private static int[][] map; // 地图 private static int m, n; private static int count = 0;// 统计有多少种走法 private static int step = 0; public static void main(String[] args) { m = 5; n = 5; int x = 0; int y = 0; map = new int[m][n]; jump(x, y); System.out.println("---------"); System.out.println(count); } private static void jump(int x, int y) { // 如果超出界限，那就继续下一轮 if (x < 0 || x >= m || y < 0 || y >= n || map[x][y] != 0) { return; } // 立足此节点 step++; map[x][y] = step; if (step == m * n) { if (count == 0) // 如果是第一次，那就输出一个 show(map); count++; } // 写出所有路径（技巧） int tx = 0, ty = 0; for (int i = 0; i < 8; i++) { tx = x + next[i][0]; // 技巧 ty = y + next[i][1]; jump(tx, ty); } // 还原 step--; map[x][y] = 0; } // 显示数组 private static void show(int[][] arr) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { System.out.print(arr[i][j] + " \t"); } System.out.println(); } } } ``` **程序运行结果：**  ## 八皇后 编程解决“八皇后问题”：即 在一个 8\*8 的矩形格子中排放 8 个皇后。 要满足的条件包括：任意两个皇后不能在同一行，同一列，也不能在同一条对角线上。 要求编程给出解的个数。 --- **答案：** 算法原理：回溯法 首先，可归纳问题的条件为，8 皇后之间需满足： 1. 不在同一行上 2. 不在同一列上 3. 不在同一斜线上 4. 不在同一反斜线上  这为我们提供一种遍历的思路，我们可以**逐行**或者**逐列**来进行可行摆放方案的遍历，每一行（列）遍历出一个符合条件的位置，接着就到下一行（列）遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置与前面的棋子**不在同一行**（列）。 这里我们**逐列摆放**，**数组下标代表列号，用数组元素存放行号。** 把当前列 N 的前面的某一列设为 m,则 m 的所有取值为｛m>=0,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 + "种摆放方法。"); } // 摆第n个皇后 public void put(int n) { // 遍历该列所有不合法的行，并用 rows 数组记录，不合法即 rows[i]=true boolean[] rows = new boolean[MAXQUEEN]; // boolean默认false 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; // 当前列不为最后一列时 if (n < MAXQUEEN - 1) { // 摆放下一个 put(n + 1); } else { // 累计方案个数 num++; } } } public static void main(String args[]) { Sy6 queen = new Sy6(); } } ``` **程序运行结果：**