N Queens Ii - Leetcode Solution

The N-Queens II problem on LeetCode is a numerical representation of the famous N-Queens chess board problem. Given an integer n, the problem is to find the total number of distinct ways that n queens can be placed on an n x n chessboard such that no two queens threaten each other. The solution requires an efficient backtracking algorithm that tries all possible positions for the queens.

Here are the steps for solving the N-Queens II problem on LeetCode:

Step 1: Define the chessboard Define a two-dimensional boolean array called chessboard with dimensions n x n. The array will represent the chessboard, with each element either true or false indicating whether a queen is placed on that cell or not.

Step 2: Define the helper function Define a function called placeQueen that takes two parameters x and y, indicating the position of the queen to be placed. The function should mark the cell (x, y) on the chessboard as true and then update the values of all cells in the same row, column, and diagonal as that queen.

Step 3: Define the main function Define a function called totalNQueens that takes an integer n as its input and returns an integer indicating the total number of ways n queens can be placed on an n x n chessboard. The function should use a backtracking algorithm to try all possible positions for the queens.

Step 4: Initialize variables Initialize a variable called count to 0, which will store the total number of distinct ways that n queens can be placed on the chessboard.

Step 5: Call the backtracking function Call the backtracking function in totalNQueens function, which will use the backtracking algorithm to try all possible positions for the queens and update count accordingly.

Step 6: Return the result Return the count from the totalNQueens function as the result.

Here is the code for solving the N-Queens II problem on LeetCode in Python:

def totalNQueens(n: int) -> int: def placeQueen(x, y): chessboard[x][y] = True

    # Update same row and column
    for i in range(n):
        if not (i == x):
            chessboard[i][y] = True
        if not (i == y):
            chessboard[x][i] = True
    
    # Update same diagonal
    for i in range(1, n):
        if x+i < n and y+i < n:
            chessboard[x+i][y+i] = True
        if x-i >= 0 and y-i >= 0:
            chessboard[x-i][y-i] = True
        if x+i < n and y-i >= 0:
            chessboard[x+i][y-i] = True
        if x-i >= 0 and y+i < n:
            chessboard[x-i][y+i] = True
            
def backtrack(queens_placed):
    nonlocal count
    
    if queens_placed == n:
        count += 1
        return
    
    for i in range(n):
        if not chessboard[queens_placed][i]:
            placeQueen(queens_placed, i)
            backtrack(queens_placed+1)
            # backtrack
            chessboard[queens_placed][i] = False
            for j in range(n):
                if not (j == i):
                    chessboard[queens_placed][j] = False
                if not (j == queens_placed):
                    chessboard[j][i] = False
            for j in range(1, n):
                if queens_placed+j < n and i+j < n:
                    chessboard[queens_placed+j][i+j] = False
                if queens_placed-j >= 0 and i-j >= 0:
                    chessboard[queens_placed-j][i-j] = False
                if queens_placed+j < n and i-j >= 0:
                    chessboard[queens_placed+j][i-j] = False
                if queens_placed-j >= 0 and i+j < n:
                    chessboard[queens_placed-j][i+j] = False
            
# Initialize variables
count = 0
chessboard = [[False]*n for _ in range(n)]

# Call the backtracking function
backtrack(0)

# Return the count
return count

The time complexity of the algorithm is O(n!) where n is the size of the board. The space complexity is O(n^2) to store the chessboard.

1