N Queens II Leetcode Problem 52 [Python Solution]

Problem Overview

The N Queens II problem is a classic combinatorial puzzle that falls under the category of backtracking problems.

The objective is to place N queens on an N x N chessboard in such a way that no two queens can attack each other.

Given an integer N, the goal is to determine the total number of distinct solutions to this puzzle.

In chess, a queen can move in any of the four primary directions—horizontally, vertically, and diagonally—for an unlimited number of spaces.

Our challenge is to find the number of ways to position N queens on the board so that they don't threaten each other.

Example 1:

Let's consider a simple example with N = 4:

Input: n = 4
Output: 2

There are two distinct solutions to the 4-queens puzzle, as shown below:
“`
Q . . .
. .

Q .
. . .

Q
.

Q . .

.

Q . .
. . .

Q
Q . . .
. .

Q .
“`

Constraints

The problem comes with some constraints:

• 1 <= n <= 9: The chessboard dimensions are between 1×1 and 9×9.

Understanding the Constraints

To understand the constraints, let's break down the problem:

1. The chessboard dimensions can range from 1×1 to 9×9.
2. We need to place N queens on the board (where N is between 1 and 9).
3. The objective is to find the total number of valid solutions.

The constraints are relatively straightforward: the board can be small (1×1) or moderately sized (9×9), and the number of queens to be placed follows the board's dimensions.

Efficient Python Code Solution

Now, let's dive into an efficient Python solution to solve the N Queens II problem.

The primary approach to solving this problem is through backtracking.

We will create a function that explores all possible queen placements on the board and counts the valid solutions.

class Solution:
    def totalNQueens(self, n: int) -> int:
        result = 0

        cols = set()
        posdiag = set()
        negdiag = set()

        def backtrack(row):
            nonlocal result  # To modify the outer result variable

            # Base case: If we have successfully placed queens in all rows, increment the result.

if row == n:
                result += 1
                return

            for col in range(n):
                # Check if the current position is not attacked by previously placed queens
                if col in cols or (row + col) in posdiag or (row - col) in negdiag:
                    continue

                # Mark the current position as occupied by a queen
                cols.add(col)
                posdiag.add(row + col)
                negdiag.add(row - col)

                # Move to the next row
                backtrack(row + 1)

                # Backtrack by removing the queen from the current position
                cols.remove(col)
                posdiag.remove(row + col)
                negdiag.remove(row - col)

        backtrack(0)  # Start the backtracking from the first row
        return result

This Python solution efficiently counts the total number of valid solutions to the N Queens II problem using backtracking.

It maintains sets to keep track of occupied columns and diagonals, ensuring that queens are placed without attacking each other.

The backtrack function explores all possible queen placements and increments the result when a valid solution is found.

Now, let's analyze the time and space complexity of this solution.

Time and Space Complexity

• Time Complexity: O(N!) – The time complexity is O(N!) because, in the worst case, we explore all possible permutations of queen placements.

Each row has N choices, and there are N rows.

• Space Complexity: O(N) – The space complexity is O(N) due to the sets used to track occupied columns and diagonals.

The depth of the recursion stack is limited to N.

The code efficiently handles the constraints and provides an optimal solution to the N Queens II problem.

Reasoning Behind Our Approach

The key to solving the N Queens II problem efficiently is backtracking.

Backtracking is a search algorithm that explores all possible solutions and backtracks when it encounters invalid choices.

In this problem, we need to place N queens on an N x N chessboard such that no two queens attack each other.

The backtracking approach allows us to explore different queen placements while ensuring they meet the puzzle's constraints.

Here's the reasoning behind our approach:

1. We define a backtracking function that explores possible queen placements row by row.
2. Within the backtracking function, we use sets to keep track of occupied columns and diagonals to ensure queens do not attack each other.
3. The base case of the recursion is when we have successfully placed queens in all rows, at which point we increment the result.
4. We iterate through each column in the current row, checking if it's a valid placement (not attacking other queens).

If it is, we mark the position as occupied and move to the next row.
5. After exploring all possibilities, we backtrack by removing the queen from the current position and continue the search.

This approach guarantees that we explore all valid solutions while avoiding duplicates.

The time complexity is factorial due to the nature of exploring all permutations, and the space complexity is limited to N due to the sets used for bookkeeping.

In summary, the N Queens II problem is efficiently solved through a backtracking approach that ensures all distinct solutions are counted while adhering to the puzzle's constraints.

Related Interview Questions By Company:

• Reconstruct Itinerary LeetCode
• Regular Expression Matching LeetCode
• N Queens II LeetCode

Related Interview Questions By Difficulty:

• Word Search LeetCode
• Letter Combinations Of A Phone Number LeetCode
• Maximum Length Of A Concatenated String With Unique Characters

Related Interview Questions By Category:

• Open The Lock LeetCode
• First Missing Positive LeetCode
• Sort Colors LeetCode

Conclusion

In this blog post, we explored the N Queens II problem, a classic combinatorial puzzle that involves placing queens on a chessboard without allowing them to attack each other.

We provided a detailed explanation of the problem, its constraints, and an efficient Python solution using backtracking.

The backtracking approach, as demonstrated in the code, allows us to explore all possible queen placements while ensuring that they do not threaten each other.

We discussed the time and space complexity of the solution, highlighting its efficiency even for larger chessboard dimensions.

For beginners learning about backtracking and combinatorial problems, the N Queens II problem serves as an excellent example.

It demonstrates the power of backtracking algorithms in searching for solutions to complex puzzles.

If you found this guide helpful, please consider liking and subscribing for more programming and problem-solving content.

Feel free to comment, ask questions, make suggestions, and share this content with others who might benefit from it.

For further practice and exploration, you can access the full problem on LeetCode: N Queens II – LeetCode.

Happy problem-solving!