51. N-Queens

51.N-Queens.py

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        leftright = [0] * (2 * n - 1)
        rightleft = [0] * (2 * n - 1)
        row = [0] * n
        col = [0] * n
        
        def valid(board, x, y):
            return not (
                row[x] or col[y]
                or leftright[n - 1 + x - y]
                or rightleft[x + y]
            )
        
        ans = []
        board = [["."] * n for _ in range(n)]
        def dfs(board, x, q=0):
            if q == n:
                ans.append(["".join(row) for row in board])
                return

            for y in range(n):
                if not valid(board, x, y):
                    continue

                row[x] = 1
                col[y] = 1
                leftright[n - 1 + x - y] = 1
                rightleft[x + y] = 1
                board[x][y] = "Q"

                for nx in range(x, n):
                    dfs(board, nx, q + 1)
                
                row[x] = 0
                col[y] = 0
                leftright[n - 1 + x - y] = 0
                rightleft[x + y] = 0
                board[x][y] = "."
        
        dfs(board, 0, 0)
        return ans