【Leetcode】python – [52] N-Queens II 個人解法筆記

➣ Reading Time: 9 minutes

題目出處

52. N-Queens II

難度

hard

個人範例程式碼

class Solution:
    def totalNQueens(self, n: int) -> int:
        if n == 0:
            return [[]]

        self.ans = 0
        self.used_horizontal = set()
        self.used_diagonal_x_add_y = set()
        self.used_diagonal_x_minus_y = set()

        board_set = set()
        self.dfs(n, board_set, 0)
        return self.ans

    def dfs(self, n, board_set, floor):
        # end of recursion
        if floor == n:
            self.ans += 1
            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)

算法說明

  • 此題目的前一題要求列出全部結果,而這題只須回傳結果數量,但做法相同,前一題可參考:

【Leetcode】python – [51] N-Queens 個人解法筆記

經典的 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 邊檢查,能到這層必為正確結果)

Reference

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 693

★留個言吧!內容有誤或想要補充也歡迎與我討論!