Skip to content

51. N-Queens

Difficulty Topics

Description

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

Solution

n-queens.py
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [["."] * n for _ in range(n)]
        cols, diag1, diag2 = set(), set(), set()
        res = []

        def place(row, col):
            board[row][col] = "Q"
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

        def discard(row, col):
            board[row][col] = "."
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

        def ok(row, col):
            return col not in cols and (row - col) not in diag1 and (row + col) not in diag2

        def go(row):
            if row == n:
                nonlocal res

                res.append(["".join(b) for b in board])
                return

            for col in range(n):
                if ok(row, col):
                    place(row, col)
                    go(row + 1)
                    discard(row, col)

        go(0)

        return res