Implement a N-Queens Solver

The N-Queens puzzle is a classic combinatorial problem: place N chess queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal. It’s a great problem for illustrating backtracking algorithms. Let’s explore a Python solution.

Understanding the Backtracking Approach

The core of our solution lies in backtracking. We’ll look at possible queen placements row by row. If a placement is valid (doesn’t conflict with existing queens), we continue to the next row. If a placement is invalid, we backtrack – undo the placement and try a different position in the current row.

The Python Code

Here’s a Python function that solves the N-Queens puzzle using backtracking:

def is_safe(board, row, col, n):
    """Checks if it's safe to place a queen at board[row][col]."""
    # Check row on the left side
    for i in range(col):
        if board[row][i] == 1:
            return False

    # Check upper left diagonal
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # Check lower left diagonal
    for i, j in zip(range(row, n, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    return True


def solve_nqueens_util(board, col, n, solutions):
    """Recursive utility function to solve the N-Queens problem."""
    if col == n:
        solutions.append([row[:] for row in board])  # Add a copy of the solution
        return True

    res = False
    for i in range(n):
        if is_safe(board, i, col, n):
            board[i][col] = 1
            res = solve_nqueens_util(board, col + 1, n, solutions) or res
            board[i][col] = 0  # Backtrack

    return res


def solve_nqueens(n):
    """Solves the N-Queens problem and returns all solutions."""
    board = [[0 for _ in range(n)] for _ in range(n)]
    solutions = []
    solve_nqueens_util(board, 0, n, solutions)
    return solutions


# Example usage:
n = 4
solutions = solve_nqueens(n)
print(f"Solutions for {n}-Queens:")
for i, solution in enumerate(solutions):
    print(f"Solution {i+1}:")
    for row in solution:
        print(row)
    print()

Explanation of the Code

• is_safe(board, row, col, n): This function checks if placing a queen at board[row][col] is safe, considering existing queens.

• solve_nqueens_util(board, col, n, solutions): This is a recursive helper function. It explores placements column by column. If a column is filled successfully, it moves to the next column. If not, it backtracks.

• solve_nqueens(n): This function initializes the board and calls the recursive utility function. It returns a list of all solutions.

This implementation provides a clear and efficient way to tackle the N-Queens problem using Python and backtracking. You can easily modify and experiment with this code to look at different aspects of the problem. Remember that the number of solutions grows rapidly with n, so larger values of n will take longer to compute.