Develop a Program to Solve the N-Queens Problem using Backtracking in Python

The N-Queens problem involves placing N queens on an N x N chessboard in such a way that no two queens threaten each other. This means no two queens should share the same row, column, or diagonal.

Python Program to Solve the N-Queens Problem using Backtracking

def is_safe(board, row, col, n):
    # Check this row on the left side
    for i in range(col):
        if board[row][i] == 1:
            return False

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

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

    return True


def solve_n_queens_util(board, col, n, solutions):
    # Base case: If all queens are placed, add the solution to the list
    if col >= n:
        solution = []
        for row in board:
            solution.append(''.join(['Q' if x == 1 else '.' for x in row]))
        solutions.append(solution)
        return True

    # Try placing this queen in all rows, one by one
    res = False
    for i in range(n):
        if is_safe(board, i, col, n):
            # Place this queen on the board
            board[i][col] = 1

            # Recur to place the rest of the queens
            res = solve_n_queens_util(board, col + 1, n, solutions) or res

            # If placing the queen doesn't lead to a solution, backtrack
            board[i][col] = 0

    return res


def solve_n_queens(n):
    board = [[0 for _ in range(n)] for _ in range(n)]
    solutions = []
    solve_n_queens_util(board, 0, n, solutions)
    return solutions


# Example usage
if __name__ == "__main__":
    n = 4  # Change this value to solve for different sizes of N
    solutions = solve_n_queens(n)

    if solutions:
        print(f"Number of solutions: {len(solutions)}")
        for solution in solutions:
            for row in solution:
                print(row)
            print()
    else:
        print("No solution exists.")

Explanation:

1. is_safe(board, row, col, n) Function:
   • This function checks if placing a queen on the board at position (row, col) is safe.
   • It checks the row on the left side, the upper diagonal, and the lower diagonal to ensure no other queens threaten the position.
2. solve_n_queens_util(board, col, n, solutions) Function:
   • This is the core backtracking function that tries to place queens one column at a time.
   • If a safe spot is found, it places the queen and recursively calls itself to place the next queen.
   • If placing a queen leads to an invalid solution, it backtracks by removing the queen and tries the next possible position.
   • If a solution is found (all queens placed), the current configuration is saved.
3. solve_n_queens(n) Function:
   • This function initializes the board and calls the utility function to start the backtracking process.
   • It collects all possible solutions in a list and returns it.

Example Output:
For n = 4, the program prints:
Number of solutions: 2
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..
This represents the two valid ways to place 4 queens on a 4x4 chessboard, where each 'Q' denotes a queen, and '.' denotes an empty square.

How Backtracking Works:

1. The program starts placing queens column by column.
2. For each column, it tries placing a queen in each row, checking if it’s safe to place.
3. If it finds a valid position, it places the queen and moves to the next column.
4. If placing a queen in a column doesn’t lead to a solution, it backtracks by removing the queen and tries the next row.

Time Complexity:

• The worst-case time complexity for solving the N-Queens problem is approximately O(N!)O(N!)O(N!), where N is the number of queens. This is because there are NNN possibilities in the first row, N−1N-1N−1 in the second, and so on, which leads to N×(N−1)×(N−2)⋯=N!N \times (N-1) \times (N-2) \dots = N!N×(N−1)×(N−2)⋯=N!.