网站建设 镇江建材企业网站模板

网站建设 镇江,建材企业网站模板,s001网站建设公司,爱站网seo综合查询工具[基础算法学习]backtrack回溯法(三):从N皇后、解数独带你掌握棋盘回溯问题 在回溯法(一)和回溯法(二)两篇文章中#xff0c;介绍了回溯法的万能模版以及树枝去重、树层去重剪枝技巧。本文将继续讲解回溯法中较难一类问题——棋盘问题#xff0c;并通过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[]# 约束集合colsset()diag1set()diag2set()defbacktrack(row):# 所有行都已经遍历返回ifrown:res.append(board(path,n))returnforcolinrange(n):ifcolincolsor(row-col)indiag1or(rowcol)indiag2:continuepath.append(col)cols.add(col)diag1.add(row-col)diag2.add(rowcol)backtrack(row1)# 回溯diag1.remove(row-col)diag2.remove(rowcol)cols.remove(col)path.pop()# 构建题目要求的形式defboard(path,n):b[]forcolinpath:row_str.*colQ.*(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):valstr(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_rowi][start_colj]val:returnFalsereturnTrue总结面对棋盘问题时回溯法要先考虑遍历行还是遍历列利用集合来实现约束的实现是这类问题的关键。要多加掌握不同类型的约束的表示灵活运用回溯法。相关题目52.N皇后II36.有效的数独79.单词搜索212.单词搜索II如果这篇文章对你有帮助不妨点个赞 留个关注收藏 ⭐你的支持是我持续创作的动力相关文章[基础算法学习]回溯法(二)——树层去重与树枝去重剪枝法[基础算法学习]回溯法(一)万能模板全排列问题解析[基础算法学习] 用「人话」讲懂所有常见排序算法小白秒懂(附Leetcode练习题)[基础算法学习] 字符串匹配还在用暴力(一) Horspool算法高效的跳跃术[基础算法学习] 字符串匹配还在用暴力(二) Boyer-Moore算法终极优化版本