N Queens Leetcode Problem 51 [Python Solution]

Welcome to another coding tutorial!

Today, we're going to tackle the N Queens problem, a famous and challenging puzzle in the realm of backtracking.

This LeetCode problem, categorized as "Hard," asks us to place N queens on an N x N chessboard in such a way that no two queens can attack each other.

We'll provide you with a Python solution that efficiently finds all distinct solutions to this intriguing puzzle.

Problem Overview

The N-queens puzzle involves placing N queens on an N x N chessboard, ensuring that no two queens threaten each other.

Each solution represents a unique board configuration with 'Q' representing a queen and '.' indicating an empty space.

Example 1:

For instance, when given N = 4, the puzzle can have two distinct solutions, as shown below:

Solution 1:

[".Q..",
"...Q",
"Q...",
"..Q."]


Solution 2:

["..Q.",
"Q...",
"...Q",
".Q.."]


These configurations illustrate that two distinct solutions are possible for the 4-queens puzzle.

Understanding Constraints

Before delving into the solution, let's understand the constraints.

We are given:
– 1 <= N <= 9: The chessboard size ranges from 1 x 1 to 9 x 9. Now, let's explore how we can efficiently solve the N-queens problem.

N Queens LeetCode Problem Solution

1. Bruteforce Approach

The N Queens problem is inherently a backtracking problem, and the brute force approach is based on recursive backtracking.

Here's a Python solution that solves this problem:

def solveNQueens(n: int):
    col = set()
    posDiag = set()  # (r + c)
    negDiag = set()  # (r - c)

    res = []
    board = [["."] * n for i in range(n)]

    def backtrack(r):
        if r == n:
            copy = ["".join(row) for row in board]
            res.append(copy)
            return

        for c in range(n):
            if c in col or (r + c) in posDiag or (r - c) in negDiag:
                continue

            col.add(c)
            posDiag.add(r + c)
            negDiag.add(r - c)
            board[r][c] = "Q"

            backtrack(r + 1)

            col.remove(c)
            posDiag.remove(r + c)
            negDiag.remove(r - c)
            board[r][c] = "."

    backtrack(0)
    return res

Time and Space Complexity

The time and space complexity of this solution are both essential to evaluate.

Time Complexity:
The time complexity of this backtracking solution is approximately O(N!).

This is because in the worst case, we explore all possible permutations of queens on the board.

For each row, we have N choices, and thus, the total number of configurations is N x (N-1) x (N-2) x …

x 2 x 1, which is N!.

Space Complexity:
The space complexity is O(N) due to the storage required for the sets that track occupied columns, positive diagonals, and negative diagonals.

Reasoning Behind Our Approach

The primary idea behind this solution is to use backtracking to systematically explore and place queens on the chessboard.

We start with the first row and proceed row by row, placing queens in valid positions while avoiding conflicts with already placed queens.

To efficiently identify valid positions, we maintain three sets: one for the columns, one for the positive diagonals, and one for the negative diagonals.

These sets help us quickly check whether a position is available for placing a queen.

Related Interview Questions By Company:

• Maximum Performance Of A Team LeetCode
• Serialize And Deserialize Binary Tree LeetCode
• N Queens II LeetCode

Related Interview Questions By Difficulty:

• Splitting A String Into Descending Consecutive Values LeetCode
• Letter Combinations Of A Phone Number LeetCode
• Combination Sum LeetCode

Conclusion

In this tutorial, we've addressed the N Queens problem, a challenging backtracking puzzle.

We provided a Python solution that efficiently finds all distinct solutions to this puzzle.

We hope you've found this guide helpful in understanding the problem and its solution.

If you have any questions, suggestions, or comments, please feel free to share them.

We encourage you to engage with our content, ask questions, make suggestions, and share it with others who might find it useful.

Happy coding!

For the full problem description and more details, you can visit the N Queens LeetCode Problem.

Now, it's your turn to explore this fascinating puzzle and test your skills.

Have fun coding, and keep challenging yourself with more coding problems!