# **Leetcode筆記(N-Queens)**

:::info
:information_source: 題目 : N-Queens, 類型 : recursion , 等級 : hard
日期 : 2023/05/30，2023/07/13
:::

### 嘗試
2023/07/13
棋盤的規則也包括斜對角不能重複，可利用左上右下(r - c), 左下右上(r + c)數字相同的規則去紀錄
在dfs裡面，用for迴圈去試下一行(r + 1)的每一個col，在dfs前要加入set，在dfs後要remove from set

對於第一行，我們有 N 種選擇；對於第二行，由於要避免與第一行的皇后衝突，所以有 N-1 種選擇；對於第三行，由於要避免與前兩行的皇后衝突，所以有 N-2 種選擇；以此類推，直到最後一行。
因此，總的時間複雜度為 N * (N-1) * (N-2) * ... * 1，即 O(N!)。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        colSet, negSet, posSet = set(), set(), set() # 左上右下(r - c), 左下右上(r + c)
        res = [["."] * n for _ in range(n)]
        board = []

        def dfs(r, res):
            if r == n:
                # 從list用''當作連接符 變成字串 最後全部用[]包住
                board.append([''.join(row) for row in res])
            
            for c in range(n):

                if c in colSet or (r - c) in negSet or (r + c) in posSet:
                    continue

                colSet.add(c)
                negSet.add((r - c))
                posSet.add((r + c))
                res[r][c] = "Q"

                dfs(r + 1, res)
            
                colSet.remove(c)
                negSet.remove((r - c))
                posSet.remove((r + c))
                res[r][c] = "."

            return
        
        dfs(0, res)
        return board

---
### **優化**
總共分成三種
1.橫的不重複
2.直的不重複
3.斜的不重複

時間複雜度：
該算法使用回溯法，對於每個皇后的放置位置，都需要檢查是否與已放置的皇后衝突，因此每個位置的選擇都涉及到一次O(N)的檢查。因此，總時間複雜度為O(N!)。

空間複雜度：
該算法的空間複雜度主要取決於回溯過程中維護的數據結構。使用了三個集合（col、posDiag和negDiag）來記錄已放置的皇后的列和兩個對角線。此外，還需要一個二維數組（board）來表示棋盤狀態。因此，空間複雜度為O(N^2)。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set() # (r + c)
        negDiag = set() # (r - c)
        board = [["."] * n for _ in range(n)]
        res = []
        
        # 只傳入r(並自動跳r) 這樣只需要判斷其他三個
        def backtrack(r):
            if r == n:
                new_board = ["".join(row) for row in board]
                res.append(new_board)

            for c in range(n):
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue
                
                col.add(c)
                posDiag.add((r + c))
                negDiag.add((r - c))
                board[r][c] = "Q"

                backtrack(r + 1)
                # 如果在進行下一輪的backtrack時皆不符合
                # 那也就退回上一層 把上一層的相關參數拿掉
                col.remove(c)
                posDiag.remove((r + c))
                negDiag.remove((r - c))
                board[r][c] = "."

            return

        backtrack(0)
        return res

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**
斜線上的特性：
正斜線：x+y
負斜線：x-y
這邊我們計算圖片上的座標，我們就會發現，同一條斜線上的結果，規律會是 x-y 或 x+y 為定值

**講解連結**
https://www.wongwonggoods.com/all-posts/interview_prepare/python_leetcode/dfs/dfs-all-methods/leetcode-python-51/
Provided by. HOWARD WENG

###### tags: `recursion` `hard` `leetcode`