51. N-Queens

Question: N-Queens

Solution

想法：

篩選條件

1. 處理 Row:
   • 棋子如果放在一個 row 之後，就得往下一個 row 去找。假設棋子在 board[r][c]，下一個就會在board[r + 1][x]。所以不用 for loop n^2 n * n 去找每一格，而是可以一行一行看。
2. 處理 Column:
   • 當一行一行看時，棋子不能放在與前一個同一個 column，不能重複 → set。所以要有一個 column set，專門紀錄已經放過的 column，假設上一個棋子放在 (0, 1)，那麼 column = {1}，下一個放在 (1, 3)，column = {1, 3}，只要下一個 c 在 column 裡面，就跳過。
3. 處理 Negative Diagnosis:
   • 當棋子放在 (0, 1) 時，(1, 2), (2, 3) 都不能放，也就是 (r + 1, c + 1), (r + 2, c + 2)，可以觀察到，r - c 會是一個常數
     • 0 - 1 = -1
     • 1 - 2 = -1
     • 2 - 3 = -1
   • 因此只要 r - c = 某一常數，代表他們在同一條 Negative Diagnosis 的線上，準備一個 negativeDia set 把這個常數放進去 negativeDia = {-1}，只要 r - c = -1 就跳過
4. 處理 Positive Diagnosis:
   • 當棋子放在 (0, 3) 時，(1, 2), (2, 1) 都不能放，也就是 (r + 1, c - 1), (r + 2, c - 2) 不能放，可以觀察到，r + c 會是一個常數
     • 0 + 3 = 3
     • 1 + 2 = 3
     • 2 + 1 = 3
   • 因此只要 r + c = 某一常數，代表他們在同一個 Positive Diagnosis 的線上，準備一個 positiveDia set 把這個常數放進去 positiveDia = {3}，只要 r + c = 3 就跳過

遞迴

• 終止條件

  如果 row 走到底了，就把修改好的 board 加入 result 中，所以遞迴 function 要吃 row 參數，每次遞迴時 + 1: dfs(r + 1)

• 遞迴條件

• 每次都從第一個 column 開始找，那一行 (row) 有哪些位置可以放 “Q”: for c in range(n)
• 可以放
  • column.add(c)
  • negativeDia.add(r - c)
  • postiveDia.add(r + c)
  • board[r][c] = “Q”
• 經過上面的篩選條件，確認可以放 Q 後，進行遞迴 dfs(r + 1) 找下一行
• 遞迴後回復原狀：
• column.remove(c)
• negativeDia.remove(r - c)
• postiveDia.remove(r + c)
• board[r][c] = “.”

class Solution:

def solveNQueens(self, n: int) -> list[list[str]]:

res = list()

board = [["."] * n for i in range(n)]

column = set()

negitiveDia = set()

positiveDia = set()

def dfs(r):

if r == n:

res.append(["".join(row) for row in board])

return

for c in range(n):

if (c in column or

(r - c) in negitiveDia or

(r + c) in positiveDia):

continue

else:

column.add(c)

negitiveDia.add(r - c)

positiveDia.add(r + c)

board[r][c] = "Q"

# next row

dfs(r + 1)

column.remove(c)

negitiveDia.remove(r - c)

positiveDia.remove(r + c)

board[r][c] = "."

dfs(0)

return res

Video Solution