N-Queens (Backtracking on Graph) 🎯

Welcome to our deep dive into the fascinating world of Data Structures and Algorithms! Today, we'll be exploring the N-Queens problem, a classic puzzle that involves placing N non-attacking queens on an NxN chessboard using the technique of Backtracking on Graph. Let's get started! 🎉

Understanding the N-Queens Problem 📝

The N-Queens problem is a well-known problem in computer science where the goal is to place N queens on an NxN chessboard such that no two queens attack each other (i.e., no two queens are in the same row, column, or diagonal). This problem is a great example of how to use backtracking to solve recursive problems.

Backtracking 💡

Backtracking is a recursive algorithmic technique for solving problems that can be broken down into subproblems. It's an iterative search process where we explore all possible solutions, and if we find a solution that doesn't satisfy the conditions, we backtrack (i.e., undo the last steps) and explore other possible solutions.

Solving the N-Queens Problem 🎲

Let's break down the problem and approach it step by step.

Initialization
- Initialize a boolean 2D array board of size NxN. All elements are initially set to False.
- Initialize a counter q to keep track of the number of queens placed so far.
Recursive Function
- Write a recursive function placeQueens(int n, int row) that will place the queens on the board.
- The function takes two parameters: n (the number of queens) and row (the current row being considered).
Placement Logic
- If all n queens have been placed (i.e., q == n), then the solution is found, and we print the solution.
- For each possible column (from 0 to n-1) in the current row row, check if it's safe to place a queen (i.e., no queen is attacking the queen we want to place).
- If a safe column is found, place the queen at that position (mark the cell as True in the board), increment the queen counter q, and recursively call the function placeQueens(n, row+1).
- If no safe column is found, undo the last placement (set the queen's position to False in the board and decrement the queen counter q), and continue searching for a safe column in the current row.
Termination
- If the function is called with row > n (i.e., we've tried all possible rows), it means that we've explored all possible solutions, and the function returns without printing any solution (since there might not be a solution for certain values of n).

Example and Quiz 📝

Let's solve the N-Queens problem for n=4 as an example.

python

def placeQueens(n, row):
    # Initialize the board
    board = [[False] * n for _ in range(n)]

    def isSafe(x, y):
        for i in range(row):
            if board[i][y] or abs(x - i) == abs(row - y):
                return False
        return True

    def solveNQUtil(n, row):
        if row > n:
            return True

        for col in range(n):
            if isSafe(row, col):
                board[row][col] = True

                if solveNQUtil(n, row + 1):
                    return True

                board[row][col] = False

        return False

    solveNQUtil(n, 0)

    for i in range(n):
        for j in range(n):
            if board[i][j]:
                print(f"Queen at ({i+1}, {j+1})")

# Printing the solution for n = 4
print("Solution for N = 4:")
placeQueens(4, 0)

Advanced Concepts 💡

Backtracking on Graph
- The N-Queens problem can be visualized as a graph, where each vertex represents a cell on the chessboard, and two vertices are connected by an edge if the cells they represent are in attacking positions.
Optimization
- The N-Queens problem can be optimized using a technique called "Early Termination." If we find a position where no queen can be placed safely, we can immediately terminate the search for that row.

We hope this lesson has helped you understand the N-Queens problem and the concept of backtracking. Practice is key, so try solving the problem for different values of n and experiment with the optimization technique. Happy coding! 🤓