LeetCode 回溯专题 8：回溯法是经典的人工智能的基础
2019-05-28 本文已影响0人
李威威
回溯法是经典的人工智能的基础，这句话中"经典"可以理解为"传统"。现如今，人工智能领域有一个非常流行的话题，那就是机器学习。
下面我们就来介绍一个传统的人工智能问题：n 皇后问题。同样地，它是典型的递归回溯问题。
例题： LeetCode 第 51 题：N 皇后
传送门：英文网址：51. N-Queens ，中文网址：51. N皇后 。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
LeetCode 第 51 题：N 皇后
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。示例:
输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。
分析：虽然看起来，这是一个人工智能的问题，但是我们的代码实现方式完全可以理解为暴力解法，只不过我们使用“递归回溯”方式的暴力解法，可以很快地判断暴力的过程中产生的结果是否符合条件，而不是把所有的暴力解都的出来以后再去掉不符合条件的；
例如：我们在第 1 行第 1 列已经放置了元素，那么很显然，在第 2 行第 1 列和第 2 列放置元素的情况就已经被排除掉了，第 2 行的第 3 列我们发现可以放置元素，于是继续遍历下去；
从上面的分析中，我们可以看到“递归”、“回溯”与“暴力解法”、“深度优先遍历”有着千丝万缕的联系；
其实这道问题，很像我们前面介绍的排列问题。我们想想，是不是每一层的一开始其实我们都有 种摆放的方法，但是因为游戏规则，在每一层我们会排除掉一些可能，在每一层我们都会记录之前的状态，回溯以后，状态还要恢复；
在解题思路上，我们采用还是一行一行去思考皇后位置的摆放，因此外层只要用一层循环。
Java 实现：
public class Solution {
private boolean[] col; // 记录在列上第几列已经放置了元素
private boolean[] dia1; // 记录在主对角线上哪些位置已经放置了元素
private boolean[] dia2; // 记录在副对角线上哪些位置已经放置了元素
private List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
col = new boolean[n];
dia1 = new boolean[2 * n - 1]; // 可以用归纳法得到对角线上的元素个数
dia2 = new boolean[2 * n - 1]; // 可以用归纳法得到对角线上的元素个数
putQueue(n, 0, new ArrayList<Integer>());
return res;
}
/**
* 尝试在一个 n 皇后的问题中，摆放第 index 行的皇后的位置
*
* @param n
* @param index
* @param row
*/
private void putQueue(int n, int index, List<Integer> row) {
if (index == n) {
res.add(generateBoard(n, row));
return;
}
// i 表示第几列，循环的过程就是在尝试给每一行的每一列放置皇后，看看在列上能不能放，看看在对角线上能不能放
// 其实 n 皇后问题和使用回溯解决排列问题的思路是一致的：暴力遍历，使用额外数组记录状态，一层层减少，递归到底以后回溯，回溯的过程中，一层一层地恢复状态
for (int i = 0; i < n; i++) {
if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
row.add(i);
col[i] = true;
dia1[index + i] = true;
dia2[index - i + n - 1] = true;
putQueue(n, index + 1, row);
col[i] = false;
dia1[index + i] = false;
dia2[index - i + n - 1] = false;
row.remove(row.size() - 1);
}
}
}
private List<String> generateBoard(int n, List<Integer> row) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(".");
}
StringBuilder cur = null;
for (int i = 0; i < n; i++) {
cur = new StringBuilder(sb);
int queueLoc = row.get(i);
cur.replace(queueLoc, queueLoc + 1, "Q");
res.add(cur.toString());
}
return res;
}
// 测试用例
public static void main(String[] args) {
Solution solution = new Solution();
List<List<String>> solveNQueens = solution.solveNQueens(8);
for (int i = 0; i < solveNQueens.size(); i++) {
System.out.println("第 " + (i + 1) + " 种解法：");
List<String> sloveOne = solveNQueens.get(i);
printList(sloveOne);
System.out.println("********");
}
}
private static void printList(List<String> sloveOne) {
for (int i = 0; i < sloveOne.size(); i++) {
System.out.println(sloveOne.get(i));
}
}
}
知识补充：n 皇后问题有很多优化的思路，可以加快搜索的过程。（因为时间关系，以后我们再关注）
练习
练习1：LeetCode 第 52 题：N-Queens II
传送门：英文网址：52. N-Queens II ，中文网址：52. N皇后 II 。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
LeetCode 第 52 题：N-Queens II
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
Java 代码：
import java.util.Stack;
public class Solution {
private boolean[] marked;
private int count;
public int totalNQueens(int n) {
if (n == 0 || n == 1) {
return n;
}
int[] board = new int[n];
for (int i = 0; i < n; i++) {
board[i] = i;
}
permuta(board);
return count;
}
// 生成一个 [0,1,...,n-1] 的全排列
private void permuta(int[] board) {
int len = board.length;
marked = new boolean[len];
Stack<Integer> pre = new Stack<>();
findPermutation(board, 0, len, pre);
}
private void findPermutation(int[] board, int usedCount, int len, Stack<Integer> pre) {
if (usedCount == len) {
// 判断是否是符合要求的棋盘布局
if (noDanger(pre, len)) {
count++;
}
return;
}
for (int i = 0; i < len; i++) {
if (!marked[i]) {
marked[i] = true;
pre.push(board[i]);
findPermutation(board, usedCount + 1, len, pre);
marked[i] = false;
pre.pop();
}
}
}
private boolean noDanger(Stack<Integer> pre, int len) {
int[] board = new int[len];
for (int i = 0; i < len; i++) {
board[i] = pre.get(i);
}
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
// 得到所有不同的 i j 的组合，是一个组合问题，按顺序来就行
// System.out.println(i + "\t" + j);
if (i - j == board[i] - board[j]) {
return false;
}
if (i - j == -(board[i] - board[j])) {
return false;
}
}
}
// 走到这里表示通过检验
// System.out.println(Arrays.toString(board));
return true;
}
public static void main(String[] args) {
Solution solution = new Solution();
int totalNQueens = solution.totalNQueens(8);
System.out.println(totalNQueens);
}
}
练习2：LeetCode 第 37 题：求解数独
传送门：37. 解数独。
分析：这是比 n 皇后问题更酷的问题，典型的人工智能的问题，自动来解决，递归加上回溯，有效剪枝，人工智能的开始章节一般就将搜索问题。
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。- 数字
1-9在每一列只能出现一次。- 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。空白格用
'.'表示。
LeetCode 第 37 题：求解数独-1
一个数独。
LeetCode 第 37 题：求解数独-2
答案被标成红色。
Note:
- 给定的数独序列只包含数字
1-9和字符'.'。- 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9形式的。
Python 代码：
import time
import sys
# 虽然成功了，但是已经超时！！！
# 37. 解数独
# 编写一个程序，通过已填充的空格来解决数独问题。
#
# 一个数独的解法需遵循如下规则：
#
# 数字 1-9 在每一行只能出现一次。
# 数字 1-9 在每一列只能出现一次。
# 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
# 空白格用 '.' 表示。
class Solution:
def __print(self, board):
result = ''
# i 表示行，是纵坐标，要特别注意
for i in range(9):
# j 表示列，是横坐标，要特别注意
for j in range(9):
if board[i][j] == '.':
result += ' '
else:
result += board[i][j]
result += ' '
result += '\n'
return result
def check(self, board, x, y):
# x 表示横坐标，y 表示纵坐标
num = board[x][y]
# 水平方向上，已经出现的数
h_nums = [board[x][col_index] for col_index in range(9) if col_index != y and board[x][col_index] != '.']
# 判断
if num in h_nums:
return False
# print('h_nums', h_nums)
# 垂直方向方向上，已经出现的数
v_nums = [board[row_index][y] for row_index in range(9) if row_index != x and board[row_index][y] != '.']
# 判断
if num in v_nums:
return False
# print('v_nums', v_nums)
# 重点理解下面这个变量的定义：所在小正方形左上角的横坐标
x_left = (x // 3) * 3
# 重点理解下面这个变量的定义：所在小正方形左上角的纵坐标
y_up = (y // 3) * 3
block_nums = []
for row in range(3):
for col in range(3):
if not ((x_left + row) == x and (y_up + col) == y):
if board[x_left + row][y_up + col] != 0:
block_nums.append(board[x_left + row][y_up + col])
# print('block_nums', block_nums)
if num in block_nums:
return False
# 以上 3 个条件都判断完以后，才能把 val 放在坐标 (x,y) 处
return True
def next(self, board):
# i 表示每一行
for i in range(9):
# j 表示每一列
for j in range(9):
if board[i][j] == '.':
return i, j
# 表示没有下一个元素了，数独任务完成
return False
def __accept(self, board):
# 如果没有了，就表示填完，返回 True
if self.next(board) is False:
return True
# 否则就表示数独任务没有完成
return False
def __solve(self, board):
# time.sleep(0.1)
# print(board)
# sys.stdout.flush()
# 先写递归终止条件
if self.__accept(board):
return True
x, y = self.next(board)
for i in range(1, 10):
board[x][y] = str(i)
if self.check(board, x, y) and self.__solve(board):
return True
board[x][y] = '.'
return False
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
self.__solve(board)
if __name__ == '__main__':
board = [['5', '3', '.', '.', '7', '.', '.', '.', '.'],
['6', '.', '.', '1', '9', '5', '.', '.', '.'],
['.', '9', '8', '.', '.', '.', '.', '6', '.'],
['8', '.', '.', '.', '6', '.', '.', '.', '3'],
['4', '.', '.', '8', '.', '3', '.', '.', '1'],
['7', '.', '.', '.', '2', '.', '.', '.', '6'],
['.', '6', '.', '.', '.', '.', '2', '8', '.'],
['.', '.', '.', '4', '1', '9', '.', '.', '5'],
['.', '.', '.', '.', '8', '.', '.', '7', '9']]
solution = Solution()
solution.solveSudoku(board)
for row in board:
print(row)
这一部分的内容到此为止，下一部分我们学习动态规划。
（本节完）
