Introduction

In this blog post, we will explore how to solve the LeetCode problem "51" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

Here's the solution to the N-Queens problem:

• Backtracking: The core idea is to explore possible queen placements row by row. If a placement leads to a conflict, we backtrack and try a different column in the current row.

• Efficient Conflict Detection: Instead of iterating through placed queens to check for attacks, we use three sets (or arrays) to track columns, diagonals, and anti-diagonals that are already occupied. This significantly speeds up conflict detection.

• Board Representation: We build the board row by row. Once a valid configuration is found, we convert it to the desired string representation.

• Runtime & Storage Complexity: O(N!) Time, O(N^2) Space

Code

    def solveNQueens(n: int) -> list[list[str]]:
    solutions = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    cols = set()
    pos_diags = set()  # (row + col)
    neg_diags = set()  # (row - col)

    def backtrack(row):
        if row == n:
            solution = ["".join(row) for row in board]
            solutions.append(solution)
            return

        for col in range(n):
            if col in cols or (row + col) in pos_diags or (row - col) in neg_diags:
                continue

            cols.add(col)
            pos_diags.add(row + col)
            neg_diags.add(row - col)
            board[row][col] = 'Q'

            backtrack(row + 1)

            cols.remove(col)
            pos_diags.remove(row + col)
            neg_diags.remove(row - col)
            board[row][col] = '.'

    backtrack(0)
    return solutions