N-Queens

 

Clarify the problem

  • The N-Queens problem is to place N queens on an N x N chessboard such that no two queens threaten each other.
  • A queen can move horizontally, vertically, or diagonally.
  • The goal is to find all possible distinct solutions.

Analyze the problem

  • Input: An integer N representing the size of the chessboard.
  • Output: Return all possible distinct solutions to the N-Queens problem.
  • Constraints: N is a positive integer.

Design an algorithm

  • Create an empty N x N chessboard.
  • Start with the first row (row = 0) and iterate through each column (col) in that row.
  • Check if placing a queen at position (row, col) is valid:
    • Check if any queens in the previous rows (rows 0 to row - 1) threaten the current position.
  • If the position is valid, mark it as a queen on the chessboard and move to the next row (row + 1).
  • Recursively repeat the process for each column in the current row.
  • If all rows have been filled (row == N), it means we have found a valid solution.
  • Backtrack to find all distinct solutions by undoing the previous queen placements.
  • Return all distinct solutions found.

Explain your approach

  • We use a recursive backtracking approach to explore all possible queen placements on the chessboard.
  • We iterate through each column in the current row and check if placing a queen is valid.
  • If a valid position is found, we mark it as a queen and move to the next row.
  • If all rows have been filled, we have found a valid solution.
  • We backtrack to find all distinct solutions by undoing the previous queen placements.
  • We repeat this process until all possible queen placements have been explored.

Write clean and readable code

def is_valid(board, row, col):
    # Check if placing a queen at position (row, col) is valid
    for r in range(row):
        # Check if there is a queen in the same column or diagonals
        if board[r] == col or board[r] - col == r - row or board[r] - col == row - r:
            return False
    return True


def solve_n_queens_util(board, row, result):
    N = len(board)
    if row == N:
        # Found a valid solution, add it to the result
        result.append(board[:])
    else:
        for col in range(N):
            if is_valid(board, row, col):
                # Place a queen at position (row, col)
                board[row] = col
                # Recursively solve for the next row
                solve_n_queens_util(board, row + 1, result)
                # Backtrack by undoing the queen placement
                board[row] = -1


def solve_n_queens(n):
    board = [-1] * n
    result = []
    solve_n_queens_util(board, 0, result)
    return result

Test your code


#Test case 1:
n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    print(solution)

#Expected output:
[1, 3, 0, 2]
[2, 0, 3, 1]

#Test case 2:
n = 5
solutions = solve_n_queens(n)
for solution in solutions:
    print(solution)

#Expected output:
[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]

Optimize if necessary

  • The provided solution has a time complexity of O(N!), as there are N! possible solutions to consider.
  • Backtracking is an efficient approach for solving the N-Queens problem, and there are no further optimizations needed.

Handle error cases

  • The provided code assumes that the input N is a positive integer.
  • No specific error handling is required as the algorithm handles the constraints internally.

Discuss complexity analysis

  • The time complexity of the solution is O(N!), as we generate all possible permutations of queen placements.
  • The space complexity is O(N) to store the board and O(N!) to store the result.
  • The solution is efficient for moderate values of N, but it becomes computationally expensive for larger values of N due to the factorial complexity.

 

Next Post Previous Post