Introduction

In this blog post, we will explore how to solve the LeetCode problem "52" 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 the number of distinct solutions to the n-queens puzzle. Example 1: Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown. Example 2: Input: n = 1 Output: 1 Constraints: 1 <= n <= 9

Explanation

Here's a solution to the N-Queens problem, focusing on efficiency:

• Backtracking with Pruning: The core idea is to use backtracking to explore possible queen placements row by row. We prune the search space by checking for conflicts (same column or diagonals) before placing a queen.

• Using Sets for Efficient Conflict Detection: Instead of iterating through previously placed queens for each potential placement, we'll use sets to keep track of occupied columns and diagonals. This allows for O(1) conflict checking.

• Optimization for Small Constraints: Due to the constraint 1 <= n <= 9, using bit manipulation is an alternative for efficiency because it can provide very fast conflict checks for small values of n.

• Runtime Complexity: O(n!), Storage Complexity: O(n) - In the worst case, we may explore all permutations of column placements. The space complexity is dominated by the size of the queens array and the sets to track column and diagonal occupancy.

Code

    def totalNQueens(n: int) -> int:
    """
    Calculates the number of distinct solutions to the n-queens puzzle.

    Args:
        n: The size of the chessboard (n x n).

    Returns:
        The number of distinct solutions.
    """

    cols = set()
    pos_diag = set()  # (row + col)
    neg_diag = set()  # (row - col)

    res = 0

    def backtrack(row):
        nonlocal res
        if row == n:
            res += 1
            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)

            backtrack(row + 1)

            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)

    backtrack(0)
    return res