[基础算法学习]backtrack回溯法(三):从N皇后、解数独带你掌握棋盘回溯问题-编程实验室

[基础算法学习]backtrack回溯法(三):从N皇后、解数独带你掌握棋盘回溯问题

在回溯法(一)和回溯法(二)两篇文章中，介绍了回溯法的万能模版以及树枝去重、树层去重剪枝技巧。本文将继续讲解回溯法中较难一类问题——棋盘问题，并通过N皇后和
解数独两道经典题目讲解棋盘问题的做题方法。

如果对于万能模版和去重剪枝不清楚，可以移步至前两篇文章：

[基础算法学习]：回溯法(二)——树层去重与树枝去重剪枝法
[基础算法学习]回溯法(一)：万能模板+全排列问题解析

一、从一维到二维

之前的回溯法都是在一维数组nums中选择数字，每一条路径path也都是一维数组，同时树枝与树层的约束也都是一维约束。

而棋盘问题是建立在二维矩阵之上的，每一条路径path都是二维矩阵，同时会存在行约束，列约束，甚至是对角线约束、格约束等等。

二、N皇后问题

题目

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的n 皇后问题的解决方案。

每一种解法包含一个不同的n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

参考下图：

分析

本题的约束条件分别为行约束，列约束，对角线约束，具体来说就是：

行约束：同一行只能有一个皇后
列约束：同一列只能有一个皇后
对角线约束：一个皇后所在的主、副对角线上只能有它一个皇后

方法

首先，对于矩阵的回溯法，通常有两种遍历方式——行遍历和列遍历，两种方法具有对称性，这里选择行遍历解题。

对于矩阵中的约束，常常用集合来实现。创建三个集合cols = set()，diag1 = set()，diag2 = set()分别用于记录列、主对角线和副对角线上是否已经放置了皇后。

我们知道，N皇后问题的约束是不能同行、同列、同对角线。

同行：因为我们采用的是“行遍历”（每递归一层row加 1），所以天然保证了每行只有一个皇后，不需要额外检查。
同列：利用 cols 集合，存储当前皇后所在的列索引col即可。
同对角线：这是难点，我们需要发现坐标(row, col)在对角线上的数学规律：

主对角线（左上到右下）：同一条对角线上的元素，其行与列之差是固定的。即row - col = 常数。我们用diag1集合存储这个差值。
副对角线（右上到左下）：同一条对角线上的元素，其行与列之和是固定的。即row + col = 常数。我们用diag2集合存储这个和值。

回溯的核心逻辑如下：

在递归函数中，我们遍历当前行row的每一列col：
剪枝（约束检查）：检查col是否在cols中，row - col是否在diag1中，以及row + col是否在diag2中。如果任一存在，说明冲突，直接跳过。
做选择：如果位置合法，将皇后放置在该处，并将col、row - col、row + col分别加入三个集合。
递归：进入下一行row + 1继续尝试。
撤销选择（回溯）：当递归返回后，说明该路径已探索完毕，需要将刚才加入集合的三个值移除，以便尝试当前行的下一列。

代码

classSolution:defsolveNQueens(self,n:int)->List[List[str]]:res=[]# 记录每一行皇后所在下标path=[]# 约束集合cols=set()diag1=set()diag2=set()defbacktrack(row):# 所有行都已经遍历，返回ifrow==n:res.append(board(path,n))returnforcolinrange(n):ifcolincolsor(row-col)indiag1or(row+col)indiag2:continuepath.append(col)cols.add(col)diag1.add(row-col)diag2.add(row+col)backtrack(row+1)# 回溯diag1.remove(row-col)diag2.remove(row+col)cols.remove(col)path.pop()# 构建题目要求的形式defboard(path,n):b=[]forcolinpath:row_str='.'*col+'Q'+'.'*(n-col-1)b.append(row_str)returnb backtrack(0)returnres

三、解数独

题目

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

分析

本题约束条件是行约束，列约束，格约束：

行约束：数字 1-9 在每一行只能出现一次。
列约束：数字 1-9 在每一列只能出现一次。
格约束：数字 1-9 在每一个以粗实线分隔的3x3宫内只能出现一次。

方法

与 N 皇后问题逐行递归不同，解数独通常采用逐个格子遍历（或者寻找下一个空位）的方式。

我们需要设计一个递归函数backtrack(board)，它的核心任务是在棋盘上寻找一个空白格'.'，并尝试填入数字'1'到'9'。

1. 递归逻辑：寻找空位与试探

每次进入递归，我们都使用双重循环遍历整个9×9的棋盘：

寻找空位：如果遇到'.'，说明找到了一个需要填的位置。
尝试填数：在这个位置尝试填入 ‘1’ 到 ‘9’。
判定合法：调用isValid()函数检查当前填入的数字是否违背了行、列或3x3宫的约束。

2. 递归与回溯：

如果合法，填入数字，并立即调用backtrack递归下一步。如果递归返回true，说明找到了解，我们也直接返回true（这是关键：只需要找到一个解）。
如果递归返回 false，说明这条路不通，我们将格子重置回'.'（回溯），并尝试下一个数字。

无解情况：如果 ‘1’ 到 ‘9’ 都尝试过且都不行，说明当前状态无解，返回false。

终止条件：如果双重循环跑完都没有发现任何空位（即没有 ‘.’），说明棋盘已填满，返回true。

3. 难点：`isValid()`函数

行和列的检查非常直观，最难的是如何判断3x3宫格内是否有重复。

假设我们要检查的坐标是( r o w , c o l ) (row,col)(row,col)，可以用s t a r t R o w = ( r o w / / 3 ) ∗ 3 , s t a r t C o l = ( c o l / / 3 ) ∗ 3 startRow = (row//3)*3,startCol = (col//3)*3startRow=(row//3)∗3,startCol=(col//3)∗3来找到这一点所在的格。

代码

classSolution:defsolveSudoku(self,board:List[List[str]])->None:self.backtrack(board)# 回溯函数defbacktrack(self,board)->bool:foriinrange(len(board)):forjinrange(len(board[0])):ifboard[i][j]!='.':continueforkinrange(1,10):val=str(k)ifself.isValid(i,j,val,board):board[i][j]=valifself.backtrack(board):returnTrue# 回溯board[i][j]='.'returnFalsereturnTrue# 检查函数defisValid(self,row,col,val,board):# 检查行forjinrange(9):ifboard[row][j]==val:returnFalse# 检查列foriinrange(9):ifboard[i][col]==val:returnFalsestart_row=(row//3)*3start_col=(col//3)*3# 检查格foriinrange(3):forjinrange(3):ifboard[start_row+i][start_col+j]==val:returnFalsereturnTrue

总结

面对棋盘问题时，回溯法要先考虑遍历行还是遍历列，利用集合来实现约束的实现，是这类问题的关键。
要多加掌握不同类型的约束的表示，灵活运用回溯法。

[基础算法学习]backtrack回溯法(三):从N皇后、解数独带你掌握棋盘回溯问题