题目
https://leetcode-cn.com/problems/n-queens/
我的思路
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
留言