代码随想录算法训练营第三十三天(回溯算法篇)| LeetCode 51. N皇后,37. 解数独

发布时间:2024年01月16日

51. N皇后

题目链接:51. N 皇后 - 力扣(LeetCode)

题目大意:如何将?n?个皇后放置在?n×n?的棋盘上,并且使皇后彼此之间不能相互攻击(即任意两个皇后不能在同行、同列、同斜线。

思路

回溯逻辑

回溯的树的宽度为棋盘的宽度,即每次for循环遍历的是棋盘每一列。树的深度为每一行,即每次recall backtracking时,递归到下一行,并判断此行可以放置Q的位置,若可以,就放下,继续进入下一行。当能递归到叶子节点,即row达到n时,说明此棋盘得到了一个解,加入到结果集。然后向上层层回溯(e.g. 若n为4,当前遍历到了第四行第三列,把结果加入,然后将此位置恢复成“.”,接着循环到第四行第四列,判断是否可行,若不行,第四行遍历结束,向上回到第三行...)

判断是否会互相攻击

创立一个isValid方程来判断在棋盘(row,col)位置上是否能放皇后:

  1. 判断此时的棋盘的col这一列上有没有Q,只用检验row以上的行数就可,以下的行数还没遍历到,肯定没有Q。
  2. 判断当前点左上斜线方向是否有Q。
  3. 判断当前点右上斜线方向是否有Q。
  4. 无需判断同一行上是否有Q,因为每一层递归,只会选for循环(即同一行)中的一个元素,其它没被选的地方都为“.”。

代码实现

class Solution(object):
    def solveNQueens(self, n):
        result = []  # 存储最终结果的二维字符串数组

        chessboard = ['.' * n for _ in range(n)]  # 初始化棋盘
        self.backtracking(n, 0, chessboard, result)  # 回溯求解
        return [[''.join(row) for row in solution] for solution in result]  # 返回结果集


    def backtracking(self, n, row, chessboard, result):
        if row == n:
            result.append(chessboard[:])
            return
        for col in range(n):
            if self.isValid(row, col, chessboard):
                chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]
                self.backtracking(n, row+1, chessboard, result)
                chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]  # 回溯,撤销当前位置的皇后

    def isValid(self, row, col, chessboard):
        # 检查在col列是否有皇后Q
        for i in range(row): # 只用检查当前row前面的就行,下面的还没轮到,不会有Q
            if chessboard[i][col] == 'Q':
                return False
        for i in range(col):
            if chessboard[row][i] == 'Q':
                return False

       # 检查左上方向
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if chessboard[i][j] == 'Q':
                return False  # 左上方向已经存在皇后,不合法
            i -= 1
            j -= 1
            
        # 检查右上方向
        i, j = row - 1, col + 1
        while i>= 0 and j<len(chessboard):
            if chessboard[i][j] == 'Q':
                return False
            i-=1
            j+=1
        return True

37. 解数独

题目链接:37. 解数独 - 力扣(LeetCode)

思路

用两个嵌套for循环遍历数独中每个空格,尝试数字1到9,如果可以就填入,继续试下一个空格。如果当前的空试了所有选择,都无法满足,就回到上一层,重新选上一个空格的数字。

代码实现

class Solution(object):
    def solveSudoku(self, board):
        self.backtracking(board)
        return board

    def backtracking(self, board):
        for col in range(len(board)):
            for row in range(len(board[0])):
                if board[row][col] != '.':
                    continue
                for val in range(1, 10):
                        if self.isValid(row, col, val, board):
                            board[row][col] = str(val)
                            if self.backtracking(board): return True # 如果找到合适的了,立刻就返回
                            board[row][col] = '.'
                return False  # 如果九个数都试过,没有找到,就返回False
        return True  # 遍历完没有返回False,说明找到了合适的棋盘
    
    def isValid(self, row, col, val, board):
        # 检查同一行是否有val
        for i in range(9):
            if board[row][i] == str(val):
                return False

        # 检查同一列
        for i in range(9):
            if board[i][col] == str(val):
                return False

        # 检查同一九宫格
        colIdx = col//3
        rowIdx = row//3
        for i in range(3*rowIdx, 3*(rowIdx+1)):
            for j in range(3*colIdx, 3*(colIdx+1)):
                if board[i][j] == str(val):
                    return False
        return True

文章来源:https://blog.csdn.net/Huiwen18/article/details/135618239
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。