51. N Queens (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        result = []
        board = [["."] * n for _ in range(n)]
        def isSafe(i, j):
            for k in range(n):
                if board[i][k] == "Q":
                    return False
                if board[k][j] == "Q":
                    return False
                if i + k < n and j + k < n and board[i + k][j + k] == "Q":
                    return False
                if i - k >= 0 and j - k >= 0 and board[i - k][j - k] == "Q":
                    return False
                if i + k < n and j - k >= 0 and board[i + k][j - k] == "Q":
                    return False
                if i - k >= 0 and j + k < n and board[i - k][j + k] == "Q":
                    return False
            return True
        def dfs(j):
            if j == n:
                result.append(["".join(x) for x in board])
            else:
                for i in range(n):
                    if isSafe(i, j):
                        board[i][j] = "Q"
                        dfs(j + 1)
                        board[i][j] = "."
        dfs(0)
        return result