題目出處
難度
hard
個人範例程式碼
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
if n == 0:
return [[]]
self.ans = []
self.used_horizontal = set()
self.used_diagonal_x_add_y = set()
self.used_diagonal_x_minus_y = set()
board_set = set()
n = 5
self.dfs(n, board_set, 0)
return self.ans
def dfs(self, n, board_set, floor):
# end of recursion
if floor == n:
self.make_board(n, board_set)
return
# define and split
for i in range(n):
queen = (floor, i)
if self.check_board_conditions(queen):
board_set.add(queen)
self.add_board_conditions(queen)
self.dfs(n, board_set, floor+1)
self.remove_board_conditions(queen) # backtracking
board_set.remove(queen) # backtracking
def check_board_conditions(self, queen):
(floor, i) = queen
if i in self.used_horizontal:
return False
if floor + i in self.used_diagonal_x_add_y:
return False
if floor - i in self.used_diagonal_x_minus_y:
return False
return True
def remove_board_conditions(self, queen):
(floor, i) = queen
self.used_horizontal.remove(i)
self.used_diagonal_x_add_y.remove(floor + i)
self.used_diagonal_x_minus_y.remove(floor - i)
def add_board_conditions(self, queen):
(floor, i) = queen
self.used_horizontal.add(i)
self.used_diagonal_x_add_y.add(floor + i)
self.used_diagonal_x_minus_y.add(floor - i)
def make_board(self, n, board_set):
print(board_set)
board = []
for i in range(n):
each_floor = ["Q" if (i, j) in board_set else "." for j in range(n)]
board.append("".join(each_floor))
self.ans.append(board)
算法說明
經典的 N-皇后 難題，可以參考的 wiki 在這邊：
這邊採用的策略是先把座標存在 set() 當中，
最後等結果都確定了，再把 set() 轉為 board。
board 正確的判斷條件
總共分成三種
- 橫的不重複
- 直的不重複
- 斜的不重複
橫的不重複
- 橫的不重複：我們在 for 環圈的時候，一橫只允許一個，因此不用另外判斷
直的不重複
- 直的不重複：我們紀錄直的座標到 used，每次嘗試擺上一個新皇后時，看一下有沒有 used
斜的不重複
- 斜的不重複：這個比較複雜，基本還是使用 used 的概念，細節我們下面細講
斜的不重複，這邊我們會提到一些數學的技巧：
我們稍微看一下，會發現斜線上的特性：
- 正斜線：x+y
- 負斜線：x-y
這邊我們計算圖片上的座標，我們就會發現，同一條斜線上的結果，規律會是 x-y 或 x+y 為定值
我們嘗試區分析範圍，這邊我們就會知道
- 正斜線：x+y，範圍介於 0 ~ 2n
- 負斜線：x-y，範圍介於 -n ~ n
注意：但我們「不需要」去把這個範圍都掃過，因為也會有「不存在結果依然正確的可能性」
可以思考明明只有 n 個數，怎麼可能放的進 「0 ~ 2n」 或 「-n ~ n」。
我們透過紀錄 used，只要確保數值不重覆即可。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
當 n = 0 時，return [[]]
Boundary conditions
我們以 floor 來紀錄層數，我們每次 dfs floor 不斷增加，
搜尋至 floor = n 時，添加結果回傳 (表示已經排完全部結果，且因為我們是邊放 queen 邊檢查，能到這層必為正確結果)
