回溯法是经典的人工智能的基础,这句话中"经典"可以理解为"传统"。现如今,人工智能领域有一个非常流行的话题,那就是机器学习。
下面我们就来介绍一个传统的人工智能问题: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)
这一部分的内容到此为止,下一部分我们学习动态规划。
(本节完)
网友评论