N-Queens Problem

Welcome to our deep dive into the fascinating world of Data Structures and Algorithms! Today, we're going to explore the N-Queens Problem, a classic puzzle that tests our problem-solving skills in computer science. Let's get started! 🎯

What is the N-Queens Problem?

The N-Queens Problem is a challenge where we need to place N queens on an N x N chessboard such that no two queens attack each other (they cannot be in the same row, column, or diagonal). For example, on a 4x4 board, a valid placement could look like this:

Q . . .
. Q . .
. . Q .
. . . Q

Why is the N-Queens Problem important?

The N-Queens Problem is a great way to understand backtracking, a depth-first search algorithm used to solve problems with a tree-like structure. It's also a fundamental problem in computer science, appearing in various domains, such as logic puzzles, artificial intelligence, and combinatorics. 💡

Solving the N-Queens Problem

To solve the N-Queens Problem, we'll implement a recursive backtracking algorithm. Let's break it down step by step.

Algorithm Overview

Initialize an empty N x N board.
Start by placing a queen in the first row (column 0).
Recursively place queens in the remaining rows, considering the safety rules for each queen (no two queens can attack each other).
If a solution is found (all queens are safely placed), return the solution.
If we cannot place a queen in the current row, backtrack (remove the last queen) and try a different placement in the same row or the next one.
Repeat the process until all rows are filled, or we exhaust all possible placements for the current row.

Python Code Example

Here's a Python implementation of the N-Queens Problem algorithm:

python

def solve_n_queens(n):
    board = ['.' * n for _ in range(n)]
    board[0][0] = 'Q'

    def place_queens(row):
        if row == n:
            print_board(board)
            return

        for col in range(n):
            if is_safe(board, row, col):
                board[row][col] = 'Q'
                place_queens(row + 1)
                board[row][col] = '.'

    def is_safe(board, row, col):
        for i in range(row):
            if board[i][col] == 'Q':
                return False

        for i, j in enumerate(range(row - 1, -1, -1)):
            if (row - i - 1) == abs(col - j):
                if board[i][j] == 'Q':
                    return False

        for i, j in enumerate(range(row + 1, n)):
            if (row - i + 1) == abs(col - j):
                if board[i][j] == 'Q':
                    return False

        return True

    place_queens(1)

def print_board(board):
    for row in board:
        print(' '.join(row))
    print()

solve_n_queens(4)

Conclusion

The N-Queens Problem is a captivating introduction to the world of backtracking algorithms. By understanding this problem and its solution, you'll gain valuable insights into problem-solving and recursion in computer science. Remember, practice makes perfect! Keep solving the N-Queens Problem with different board sizes to reinforce your understanding. 💡

Happy coding! 🎯