N-Queens hard

Problem Statement

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

A queen can attack any piece in the same row, column, or diagonal.

Given an integer n, return all distinct solutions to the n-queens puzzle. 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"]]

Steps and Explanation

The core idea is to use backtracking. We'll explore placing queens row by row. For each row, we try placing a queen in each column. Before placing, we check if it's a safe position (no other queen attacks). If it's safe, we recursively call the function for the next row. If we reach the last row successfully, we've found a solution. If a placement is not safe or we reach a dead-end, we backtrack and try a different column.

We need to efficiently check for attacks. We'll use three sets:

• col: Keeps track of columns used in the current partial solution.
• diag1: Keeps track of diagonals (from top-left to bottom-right) used. The diagonal can be uniquely identified by row - col.
• diag2: Keeps track of diagonals (from top-right to bottom-left) used. The diagonal can be uniquely identified by row + col.

If placing a queen at (row, col) would result in adding to any of these sets an element already present then it means it is not safe to place the queen there.

Code

def solveNQueens(n: int) -> list[list[str]]:
    """Solves the N-Queens problem using backtracking."""
    
    result = []
    col = set()  # Tracks columns used
    diag1 = set() # Tracks diagonals (top-left to bottom-right)
    diag2 = set() # Tracks diagonals (top-right to bottom-left)

    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        if row == n:  # Base case: All queens placed successfully
            result.append(["".join(row) for row in board])
            return

        for col_idx in range(n):
            if col_idx not in col and row - col_idx not in diag1 and row + col_idx not in diag2:
                # Safe to place queen
                board[row][col_idx] = 'Q'
                col.add(col_idx)
                diag1.add(row - col_idx)
                diag2.add(row + col_idx)

                backtrack(row + 1) # Explore next row

                # Backtrack: Remove queen and update sets
                board[row][col_idx] = '.'
                col.remove(col_idx)
                diag1.remove(row - col_idx)
                diag2.remove(row + col_idx)

    backtrack(0)
    return result

Complexity

• Time Complexity: O(N!), where N is the size of the chessboard. In the worst case, we explore all possible permutations of queen placements.
• Space Complexity: O(N^2) to store the board and the sets used for tracking columns and diagonals. The recursion depth is also at most N.