代码随想录 -- 回溯 -- N皇后

51. N 皇后 - 力扣（LeetCode）

题解：

从抽象树中可以看出递归的层数取决于棋盘的行数，for循环的次数取决于棋盘的列数。

• 递归参数：存放当前棋盘的数组chessboard、当前行row、总行数n。
• 递归终止条件：当 row 等于 n 的时候收集结果并返回。
• 单层递归逻辑：在当前行、当前列添加皇后符合题意时：将皇后加入棋盘；递归调用进行下一行的皇后放置；将皇后移出棋盘（回溯）。

注意判定在当前行、当前列添加皇后是否符合题意的函数：

• 无需判断行
• 判断列
• 判断斜左上方
• 判断斜右上方

class Solution(object):
    def back(self,chessboard,n,row):
        if row==n:
            self.result.append(chessboard[:])
            return
        for i in range(n):
            if self.isValid(chessboard,row,i,n):
                chessboard[row]=chessboard[row][:i]+'Q'+chessboard[row][i+1:]
                self.back(chessboard,n,row+1)
                chessboard[row]=chessboard[row][:i]+'.'+chessboard[row][i+1:]

    def isValid(self,chessboard,row,cul,n):
        for i in range(row):
            if chessboard[i][cul]=='Q':
                return False

        i,j=row-1,cul-1
        while i>=0 and j>=0:
            if chessboard[i][j]=='Q':
                return False
            i-=1
            j-=1
        
        i,j=row-1,cul+1
        while i>=0 and j<n:
            if chessboard[i][j]=='Q':
                return False
            i-=1
            j+=1

        return True

    def solveNQueens(self, n):
        self.result=[]
        self.back(['.'*n for _ in range(n)],n,0)
        return self.result

原文地址：https://blog.csdn.net/weixin_56989647/article/details/142633411

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！