N-Queens — LeetCode #51

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

Solutions:

Python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(row, path, result):
            if row == n:
                result.append(path)
                return
            for col in range(n):
                if is_valid(row, col):
                    place_queen(row, col)
                    backtrack(row+1, path + [col], result)
                    remove_queen(row, col)

        def is_valid(row, col):
            for r, c in queens:
                if c == col or r - c == row - col or r + c == row + col:
                    return False
            return True

        def place_queen(row, col):
            queens.add((row, col))
            rows.add(row)
            cols.add(col)
            diagonals1.add(row - col)
            diagonals2.add(row + col)

        def remove_queen(row, col):
            queens.remove((row, col))
            rows.remove(row)
            cols.remove(col)
            diagonals1.remove(row - col)
            diagonals2.remove(row + col)

        queens, rows, cols, diagonals1, diagonals2 = set(), set(), set(), set(), set()
        result = []
        backtrack(0, [], result)
        return [["." * i + "Q" + "." * (n - i - 1) for i in sol] for sol in result]

I hope this helps! Let me know if you have any questions. Don’t forget to follow and give some claps to support my content