题目

https://leetcode-cn.com/problems/n-queens/
file

我的思路

DFS思路,用一个列表记录每一步落子后的棋盘状态,每次向下递归都传递这个列表。对于非法防止位置的判定是每行逐个与“棋盘”列表board里面的棋子进行对比,满足以下任一条件:1)行相等;2)列相等;3)行列差的绝对值相等;则判定为非法落子。存在合法落子则进入下一层递归。递归退出条件为本行不存在合法落子或所有行都已经落子。

解法1:O(N*N!)

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:

        ans = []

        def solve(board, row):
            if row == n:
                ans.append(['.'*chess[1] + 'Q' + (n-chess[1]-1)*'.'  for chess in board])
                return
            for i in range(n):
                # 最坏 n次
                can_use = True
                for chess in board:
                    if row == chess[0] or i == chess[1] or (abs(row - chess[0]) == abs(i - chess[1])):
                        can_use = False
                        break
                if can_use:
                    new_board = board.copy()
                    new_board.append((row, i))
                    solve(new_board, row + 1)
            return

        solve([], 0)

        return ans

思考:可以使用集合set记录已放置的列、主对角线方向、副对角线方向位置。主对角线方向相同斜线具有差值相等的性质,副对角线方向相同斜线具有和相等的性质。注意我们其实并不需要记录放置行,因为我们沿着行的方向递归,必然不会出现行重复。

解法2:O(N!)

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:

        ans = []

        def solve(board, row, row_chess, dig1, dig2):
            if row == n:
                ans.append(['.'*chess[1] + 'Q' + (n-chess[1]-1)*'.'  for chess in board])
                return
            for i in range(n):
                if (i in row_chess) or (row - i in dig1) or (i + row in dig2):
                    continue

                new_board = board.copy()
                new_board.append((row, i))
                new_row_chess = row_chess.copy()
                new_row_chess.add(i)
                new_dig1 = dig1.copy()
                new_dig2 = dig2.copy()
                new_dig1.add(row-i)
                new_dig2.add(i+row)
                solve(new_board, row + 1, new_row_chess, new_dig1, new_dig2)
            return

        solve([], 0, set(), set(), set())

        return ans
最后修改日期: 2020年9月3日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。