Python Program to Solve the N-Queens Problem Using Backtracking

The N-Queens problem asks: can you place N chess queens on an N×N board so that no two queens attack each other — meaning no two share a row, a column, or a diagonal? It's one of the most famous backtracking problems in computer science (the classic version uses an 8×8 board), and it's a great exercise for learning how to prune a search space instead of brute-forcing every possible arrangement.

The approach places one queen per row, working row by row. Before placing a queen in a column, it checks whether that column or either diagonal is already under attack from a queen placed in an earlier row. If the spot is safe, place the queen and recurse to the next row; if a full board of N rows is reached, a solution has been found. If no column in the current row is safe, backtrack to the previous row and try a different column there.

Python Program to Solve the N-Queens Problem Using Backtracking

def solve_n_queens(n):
    board = [-1] * n  # board[row] = column of the queen in that row

    def is_safe(row, col):
        for prev_row in range(row):
            prev_col = board[prev_row]
            same_col = prev_col == col
            same_diagonal = abs(prev_col - col) == abs(prev_row - row)
            if same_col or same_diagonal:
                return False
        return True

    def backtrack(row):
        if row == n:
            return True  # all N queens placed successfully
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                if backtrack(row + 1):
                    return True
                board[row] = -1  # undo and try the next column
        return False

    if backtrack(0):
        return board
    return None


def print_board(board, n):
    for row in range(n):
        line = ["Q" if col == board[row] else "." for col in range(n)]
        print(" ".join(line))


n = 8
solution = solve_n_queens(n)
if solution:
    print_board(solution, n)
else:
    print(f"No solution exists for N = {n}")

Output:

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

---

This version stops at the first valid solution, which is enough for most interview settings — to find all distinct solutions (there are 92 for the classic 8×8 board), remove the early `return True` and instead append a copy of `board` to a results list every time `row == n` is reached, then keep backtracking. The key optimization here versus brute force is that `is_safe` prunes an entire branch of the search tree the moment a conflict is found, rather than generating every possible arrangement of N queens and checking each one afterward — that brute-force approach would need to examine up to C(N², N) placements, while backtracking with pruning explores a dramatically smaller fraction of that space in practice.