N-Queens (Recursive) 🎯

Welcome to this comprehensive guide on the N-Queens problem, a classic algorithmic puzzle that tests our understanding of recursion and backtracking. This lesson is suitable for beginners and intermediates, and we'll explore the problem from the ground up.

What is the N-Queens Problem? 📝

The N-Queens problem asks us to place N non-attacking queens on an N x N chessboard. The challenge lies in ensuring no two queens are in the same row, column, or diagonal. Let's break this down and understand why this is a great problem to learn about!

Breaking Down the Problem 💡

To solve the N-Queens problem, we'll:

Understand why we need recursion and backtracking.
Write a recursive function to solve the problem.
Implement the function and analyze its time complexity.

Recursion and Backtracking 📝

Recursion involves breaking down a problem into smaller sub-problems, solving them, and combining the solutions to find the solution to the original problem. Backtracking is a recursive problem-solving approach used when the solution space is large, and we need to explore different possibilities.

Solving the N-Queens Problem 💡

We'll write a recursive function that places queens on the board, ensuring no two queens are attacking each other. The function will take the current row as an argument and maintain a board to keep track of queen placements.

python

def place_queens(row, board):
    # Base case: if all rows are filled, we have a valid solution
    if row == n:
        print_board(board)
        return

    # Try placing a queen in each column of the current row
    for col in range(n):
        # Check if it's safe to place a queen in this position
        if is_safe(row, col, board):
            # Place the queen and recurse for the next row
            board[row][col] = 1
            place_queens(row + 1, board)
            # Backtrack: remove the queen and continue with the next column
            board[row][col] = 0

# Check if it's safe to place a queen at (row, col) on the board
def is_safe(row, col, board):
    # Check the current row and column for existing queens
    for queen in range(row):
        if board[queen][col] or board[row][queen]:
            return False

    # Check diagonally up-right and down-right for existing queens
    for queen_row, queen_col in ((row + 1, col + 1), (row - 1, col + 1), (row + 1, col - 1), (row - 1, col - 1)):
        if queen_row >= 0 and queen_col >= 0 and queen_row < n and queen_col < n and board[queen_row][queen_col]:
            return False

    return True

Time Complexity 📝

The time complexity of our solution is O(n! * n^2). This is because we have n queens (n! possibilities for the column), and each placement requires checking n columns and up to 4n diagonal positions, giving us a total of O(n^2) operations per recursive call.

Quiz 🎯

That's it for today's lesson on the N-Queens problem using recursion and backtracking! Stay tuned for more exciting topics on Data Structures and Algorithms here at CodeYourCraft. Happy coding! 💡💻🚀