# Solving Leetcode Interviews in Seconds with AI: N-Queens


	# 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](https://www.chatmagic.app), 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
	```python
	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
	```