# Leetcode 51. N-Queens

## 題解

### DFS Back Tracking

如果要知道 n * n 種棋盤組合，我們需要窮舉 n ** n 種組合，才會得到答案，但是 N 皇后問題中，每個皇后橫向、縱向、斜向都不能重複，所以我們可以假設每一行都只會有一個皇后，每一列也都只會有一格皇后，由此可以推導出這個問題的簡化版本 [Permutations](https://hackmd.io/@paxton0222/SyHyDV_l3)，可以假設 4 x 4 棋盤上的皇后 "Q..." 為 1， ".Q.." 為 2，以此類推，所以可能的皇后組合就會變成 [1,2,3,4] 的所有不重複排列組合，剩下的只需要去驗證，斜向排列的組合是否合法即可

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        pos = [("." * i) + "Q" + "." * (n - i-1) for i in range(n)] # 先生成 n 種排列組合
        output = []
        path = set()
        directions = [[-1,-1], [-1,1]] # left top, right top 這邊只需要向上斜巷驗證

        def vaild(x: int,y: int, board: List[List[str]]) -> bool:
            if y == 0: # 第一行不需要驗證
                return True
            for i in range(y):
                for _y,_x in directions:
                    new_x = x + (_x*(i+1))
                    new_y = y + (_y*(i+1))
                    if 0 <= new_y < n and 0 <= new_x < n:
                        if board[new_y][new_x] == "Q": # 如果斜向路徑上有皇后，代表組合不合法
                            return False
            return True # 所有路徑上都沒有皇后，目前組合合法

        def dfs(board: List[List[str]]):
            if len(board) == n:
                output.append(list(board))
            else:
                for i in range(n):
                    if i not in path:
                        board.append(pos[i])
                        path.add(i)
                        if vaild(i,len(board) - 1,board): # 合法就繼續找下去，不合法剪枝
                            dfs(board)
                        board.pop()
                        path.remove(i)
        dfs([])
        return output

### 斜向檢查優化



class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # Time complexity: O(N!)
        # Space complexity: O(N)
        pos = [("." * i) + "Q" + "." * (n - i-1) for i in range(n)]
        output = []
        path = set()
        nd = set()
        pd = set()
        def dfs(board: List[List[str]]):
            if len(board) == n:
                output.append(list(board))
            else:
                for x in range(n):
                    y = len(board)
                    rmc = y - x # y - x 負向斜線
                    rpc = y + x # y + x 正向斜線
                    if x not in path and rmc not in nd and rpc not in pd:
                        board.append(pos[x])
                        path.add(x)
                        nd.add(rmc)
                        pd.add(rpc)
                        dfs(board)
                        pd.remove(rpc)
                        nd.remove(rmc)
                        path.remove(x)
                        board.pop()
        dfs([])
        return output