一、迷宫问题介绍
给定一个方阵表示迷宫，其中 1 表示能走的路，0 为障碍或走不通（死胡同），迷宫左上为出发点，迷宫右下角为终点。在迷宫中的移动方式只能横着走或竖着走，不能斜着走，找出冲出发点到达出口有效路径的迷宫（maze problem）问题。
二、回溯法简单求解
给定迷宫：
迷宫的二维矩阵表示：
{1，0，0，0}
{1，1，0，1}
{0，1，0，0}
{1，1，1，1}
以下是具有突出解决方案路径的迷宫。
以下是上述输入矩阵的解决方案矩阵（程序的输出）：
1 {1，0，0，0}
2 {1，1，0，0}
3 {0，1，0，0}
4 {0，1，1，1}
回溯算法思想：
如果到达目的地，打印解决方案矩阵。若没有到达目的地，则：
a）在解决方案矩阵中将当前单元格标记为 1；
b）沿水平方向向前移动并递归检查是否这次移动解决了问题；
c）如果在上述步骤中选择的举动没有导致解决方案 然后向下移动并检查此举是否可以解决；
d）如果以上解决方案均无效，则将该单元格取消标记为 0 （回溯）并返回 false。
1 /**
2 * 回溯法递归求解迷宫问题
3 *
4 * @param maze
5 * @param x
6 * @param y
7 * @param sol
8 * @return
9 */
10 private boolean solveMazeUtil(int[][] maze, int x, int y, int[][] sol) {
11 /* 到达终点 */
12 if (x == (N - 1) && y == (N - 1)) {
13 sol[x][y] = 1;
14 return true;
15 }
16
17 /* 每次检查(x, y)是否能走 */
18 if (isSafe(maze, x, y)) {
19 /* 能走则标记该位置 */
20 sol[x][y] = 1;
21
22 /* 沿x方向向前移动 */
23 if (solveMazeUtil(maze, x + 1, y, sol)) {
24 return true;
25 }
26
27 /* 如果沿x方向移动没有给出解，则沿y方向向下移动 */
28 if (solveMazeUtil(maze, x, y + 1, sol)) {
29 return true;
30 }
31
32 /* 如果以上动作均无效，则回溯：将(x，y)标记为解决方案路径的一部分记为不可行 */
33 sol[x][y] = 0;
34 return false;
35 }
36
37 return false;
38 }
本文源代码：
1 package algorithm;
2
3 public class RatMaze {
4 /* 迷宫规模 */
5 private static int N;
6
7 /**
8 * 打印解矩阵
9 *
10 * @param sol
11 */
12 private void printSolution(int[][] sol) {
13 for (int i = 0; i < N; i++) {
14 for (int j = 0; j < N; j++) {
15 System.out.print(" " + sol[i][j] + " ");
16 }
17 System.out.println();
18 }
19 }
20
21 /**
22 * 判断当前路劲是否可行
23 *
24 * @param maze
25 * @param x
26 * @param y
27 * @return
28 */
29 private boolean isSafe(int[][] maze, int x, int y) {
30 return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
31 }
32
33 /**
34 * 解决迷宫问题, 有则打印解矩阵
35 *
36 * @param maze
37 * @return
38 */
39 private boolean solveMaze(int[][] maze) {
40 int[][] sol = new int[N][N];
41 if (!solveMazeUtil(maze, 0, 0, sol)) {
42 System.out.println("Solution doesn't exist");
43 return false;
44 }
45 printSolution(sol);
46 return true;
47 }
48
49 /**
50 * 回溯法递归求解迷宫问题
51 *
52 * @param maze
53 * @param x
54 * @param y
55 * @param sol
56 * @return
57 */
58 private boolean solveMazeUtil(int[][] maze, int x, int y, int[][] sol) {
59 /* 到达终点 */
60 if (x == (N - 1) && y == (N - 1)) {
61 sol[x][y] = 1;
62 return true;
63 }
64
65 count++;
66 /* 每次检查(x, y)是否能走 */
67 if (isSafe(maze, x, y)) {
68 /* 能走则标记该位置 */
69 sol[x][y] = 1;
70
71 /* 沿x方向向前移动 */
72 if (solveMazeUtil(maze, x + 1, y, sol)) {
73 return true;
74 }
75
76 /* 如果沿x方向移动没有给出解，则沿y方向向下移动 */
77 if (solveMazeUtil(maze, x, y + 1, sol)) {
78 return true;
79 }
80
81 /* 如果以上动作均无效，则回溯：将(x，y)标记为解决方案路径的一部分记为不可行 */
82 sol[x][y] = 0;
83 return false;
84 }
85
86 return false;
87 }
88
89 public static void main(String[] args) {
90 RatMaze ratMaze = new RatMaze();
91 int[][] maze = {
92 { 1, 0, 0, 0 },
93 { 1, 1, 1, 0 },
94 { 0, 1, 0, 0 },
95 { 1, 1, 1, 1 }
96 };
97 N = maze.length;
98 ratMaze.solveMaze(maze);
99 }
100 }
View Code