題目出處

51. N-Queens

難度

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 在這邊：

• 八皇后問題 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 邊檢查，能到這層必為正確結果)

Reference

• N皇后问题（一） · N-Queens