HardLeetCode #51Backtracking

N-Queens

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.

Constraints

1 <= n <= 9

Examples

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Solution

Approach

Place queens row by row. Track columns and diagonals under attack using sets. Backtrack if no valid position in current row.

def solveNQueens(n):
    result = []
    cols = set()
    pos_diag = set()
    neg_diag = set()
    board = [["."]*n for _ in range(n)]
    def backtrack(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row+col) in pos_diag or (row-col) in neg_diag:
                continue
            cols.add(col)
            pos_diag.add(row+col)
            neg_diag.add(row-col)
            board[row][col] = "Q"
            backtrack(row + 1)
            cols.remove(col)
            pos_diag.remove(row+col)
            neg_diag.remove(row-col)
            board[row][col] = "."
    backtrack(0)
    return result

Complexity

Time:O(n!)

Space:O(n²)

Hints

1.Place one queen per row
2.Track attacked columns and diagonals
3.Diagonals identified by row+col and row-col

Asked at

Google