N queens

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res  = []
        grid = [['.'] * n for i in range(n)]

        def check(grid, row, col):
            for i in range(row - 1, -1, -1):
                if grid[i][col] == "Q":
                    return False

            count = 1
            for i in range(row - 1, -1, -1):
                leftcol = col - count
                rightcol = col + count
                if leftcol >= 0 and grid[i][leftcol] == "Q":
                    return False
                if rightcol < n and grid[i][rightcol] == "Q":
                    return False
                count += 1

            return True


        def backtrack(grid, row):
            # print(grid)
            if row == n:
                res.append(["".join(i) for i in grid])
                return

            for col in range(n):
                grid[row][col] = 'Q'
                if check(grid, row, col):
                    backtrack(grid, row + 1)
                grid[row][col] = '.'

        backtrack(grid, 0)

        return res

N-Queens

Difficulty: Hard

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

 

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

 

Constraints:

  • 1 <= n <= 9