N-Queens Puzzle

December 23, 2023

Problem #

Place N queens on an N x N chessboard such that no two queens can attack each other.

Solution #

The Python code for solving the “N Queens” problem is provided below. This problem involves placing N queens on an N x N chessboard such that no two queens can attack each other. A solution to the problem means that no two queens share the same row, column, or diagonal.

def solve_n_queens(n):
    def is_safe(board, row, col):
        # Check for a queen in the same column
        for i in range(row):
            if board[i][col] == 'Q':
                return False

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

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

        return True

    def solve(board, row):
        if row >= n:
            solutions.append(["".join(row) for row in board])
            return

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

    solutions = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    solve(board, 0)
    return solutions

# Example usage
n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    for row in solution:
        print(row)
    print()

In this code:

• The solve_n_queens function generates all the possible solutions for placing N queens on an N x N chessboard.
• The is_safe function checks whether it’s safe to place a queen at a given position.
• The solve function uses backtracking to place queens and check for safe positions.
• If a safe position is found, the function places a queen ('Q') and moves to the next row.
• If it’s not possible to place a queen in any column of a row, the function backtracks (removes the queen) and tries a different position in the previous row.
• When a valid arrangement is found (all rows have a queen), it’s added to the solutions list.
• The example usage with n = 4 finds all solutions for 4 queens on a 4x4 board and prints them.

The output for n = 4 shows two possible arrangements of queens on the board where they do not attack each other.