N-Queens II

The n-queens problem is a classic backtracking problem. You can use recursive function calls to place queens one by one, and in each recursive call, you’ll check if the newly placed queen is safe from the others. If it’s safe, you’ll continue to the next row, and if not, you’ll backtrack. Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution:
    def totalNQueens(self, n: int) -> int:
        def is_safe(board, row, col):
            # Check this column
            for i in range(row):
                if board[i] == col:
                    return False

            # Check upper diagonal on left side
            for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
                if board[i] == j:
                    return False

            # Check lower diagonal on left side
            for i, j in zip(range(row, -1, -1), range(col, n)):
                if board[i] == j:
                    return False

            return True

        def solve(board, row):
            if row == n:
                self.result += 1
                return

            for col in range(n):
                if is_safe(board, row, col):
                    board[row] = col
                    solve(board, row + 1)
                    board[row] = -1

        self.result = 0
        board = [-1] * n
        solve(board, 0)

        return self.result

This code uses a 1D list board where board[i] represents the column number where the queen is placed in row i. The is_safe function checks if a queen can be placed safely at a given row and column, and the solve function recursively places queens row by row. The time complexity of this code is (O(N!)), where (N) is the given input, and the space complexity is (O(N)) due to the recursive call stack.

10 Prerequisite LeetCode Problems

“N-Queens II” is about backtracking, recursion, and understanding how to work with a chess board. The following are 10 problems as preparation for tackling “N-Queens II”:

  1. 79. Word Search: This problem involves backtracking on a 2D grid, which is a similar concept to the chess board in the N-Queens problem.

  2. 22. Generate Parentheses: This problem involves generating all valid combinations of parentheses, which is a form of backtracking.

  3. 39. Combination Sum: This problem requires generating all combinations that sum up to a target, requiring both backtracking and recursion.

  4. 77. Combinations: This problem requires generating all combinations of a given set of numbers, again requiring both backtracking and recursion.

  5. 46. Permutations: This problem asks for generating all permutations of a given set of numbers, a fundamental problem for understanding backtracking.

  6. 216. Combination Sum III: Another combination sum problem, but with additional constraints.

  7. 90. Subsets II: This problem requires generating all subsets from a set of numbers, with a twist that the input might contain duplicates.

  8. 78. Subsets: A simpler variant of the above problem, this problem requires generating all possible subsets from a given set of distinct integers.

  9. 17. Letter Combinations of a Phone Number: This problem requires generating all possible letter combinations that a phone number can represent.

  10. 200. Number of Islands: This problem involves searching on a 2D grid, similar to a chessboard, and can help in understanding how to traverse such structures.

These cover recursion, backtracking, and handling 2D grid problems, which are critical for solving the “N-Queens II” problem.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def totalNQueens(self, n: int) -> int:
        state=[['.'] * n for _ in range(n)]

        visited_cols=set()
        visited_diagonals=set()
        visited_antidiagonals=set()

        res=set()
        def backtrack(r):
            if r==n:
                res.add(map('#'.join, map(''.join, state))) 
                return

            for c in range(n):
                if not(c in visited_cols or (r-c) in visited_diagonals or (r+c) in visited_antidiagonals):
                    visited_cols.add(c)
                    visited_diagonals.add(r-c)
                    visited_antidiagonals.add(r+c)
                    state[r][c]='Q'
                    backtrack(r+1)

                    visited_cols.remove(c)
                    visited_diagonals.remove(r-c)
                    visited_antidiagonals.remove(r+c)
                    state[r][c]='.'

        backtrack(0)
        return len(res)

Language Agnostic Coding Drills

The solution if for the problem of finding the total number of distinct solutions to the N-Queens puzzle. Here’s the breakdown of concepts:

  1. Using a 2D list (or matrix) to represent a chess board: This is a fundamental aspect of the problem. You can experiment with creating a 2D list, adding and removing elements, and iterating through it.

    1

    board = [["."] * 4 for _ in range(4)]

  2. Sets in Python: Sets are an unordered collection of unique elements. They are used here to keep track of visited columns, diagonals, and anti-diagonals. Practice creating sets, adding elements, removing elements, and checking membership.

    1
2
3
4

    visited = set()
visited.add('a')
print('b' in visited)  # False
visited.remove('a')

  3. Backtracking: This is a classic algorithmic paradigm that involves exploring all possibilities and undoing a move if it leads to a solution that violates the constraints. In this case, backtracking is used to place queens on the board and remove them if they can be attacked by another queen.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    def backtrack(i):
    if violates_constraints(i):
        return False
    if i == goal:
        return True
    for j in range(i+1, n):
        if backtrack(j):
            return True
    return False
backtrack(0)

  4. Recursive functions: A recursive function is a function that calls itself. In this solution, the backtrack function is recursive because it calls itself within its body. Understand the concept of a base case (the case that ends the recursion) and recursive case.

  5. String Manipulation: In this problem, the chess board is represented as a 2D list of strings. Practice creating strings, concatenating them, and replacing characters in a string.

    1
2
3

    row = ['.', '.', '.', 'Q']
str_row = ''.join(row)  # Convert list of strings to a single string
replaced = str_row.replace('.', 'Q')  # Replace all occurrences of '.' with 'Q'

  6. Depth-First Search (DFS): Backtracking is essentially a depth-first search over the search space of all possible arrangements of queens. Understanding DFS is crucial to understand backtracking.

Starting from the first row, the backtrack function is called to place a queen in a safe position and then recursively called to place the rest of the queens. If no safe position can be found in a row, it means that the previous queen was not placed correctly, so we go back and move the previous queen. The process continues until we have found all valid arrangements.

Targeted Drills in Python

  1. Creating and Manipulating a 2D list (or matrix):

    1
2
3
4
5
6
7

    # Create a 4x4 2D list filled with '.'
board = [["."] * 4 for _ in range(4)]
print(board)

# Change the element in the 1st row and 2nd column to 'Q'
board[0][1] = 'Q'
print(board)

  2. Using sets in Python:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    # Create an empty set
visited = set()
print(visited)

# Add an element to the set
visited.add('a')
print(visited)

# Check if an element is in the set
print('a' in visited)  # Should print True
print('b' in visited)  # Should print False

# Remove an element from the set
visited.remove('a')
print(visited)

  3. Implementing a simple Backtracking algorithm:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    def place_queen(board, row, col):
    """Return True if it's safe to place a queen at board[row][col]"""
    # Fill in your implementation here
    pass

def backtrack(board, col):
    """Place a queen in column `col` and recursively in the next columns"""
    if col >= len(board):
        return True
    for row in range(len(board)):
        if place_queen(board, row, col):
            board[row][col] = 'Q'
            if backtrack(board, col + 1):
                return True
            board[row][col] = '.'  # Undo the move
    return False

# Create a 4x4 chess board
board = [["."] * 4 for _ in range(4)]

# Call the backtracking function to place queens
backtrack(board, 0)

# Print the board
print(board)

  4. Practicing Recursive functions:

    1
2
3
4
5
6
7

    def factorial(n):
    """Return the factorial of `n` (n!)"""
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # Should print 120

  5. Performing String Manipulation:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    # Create a list of strings
row = ['.', '.', '.', 'Q']

# Convert list of strings to a single string
str_row = ''.join(row)
print(str_row)  # Should print "..."

# Replace all occurrences of '.' with 'Q'
replaced = str_row.replace('.', 'Q')
print(replaced)  # Should print "QQQ"

  6. Implementing a Depth-First Search (DFS):

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    def dfs(graph, node, visited):
    """Perform a depth-first search starting from `node`"""
    if node not in visited:
        visited.append(node)
        for neighbour in graph[node]:
            dfs(graph, neighbour, visited)
    return visited

# Represent a graph as a dictionary where each key is a node and each value is a list of neighbours
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']

}

# Perform a depth-first search starting from 'A'
visited_nodes = dfs(graph, 'A', [])
print(visited_nodes)  # Should print ['A', 'B', 'D', 'E', 'F', 'C']
```

For each of these drills, you’ll need to understand the problem statement and the expected output, then try to write the Python code to achieve the expected output. After doing all these drills, you should be better equipped to understand and implement the N-Queens solution in Python.