Solving N-Queens

Place one queen per row, and for each row try every column. A column is legal if no other queen occupies that column and no other queen shares a diagonal with it. If every row can be filled, you have a solution; if a row cannot be filled, back up and try the previous row with a different column.

The state the search needs is which columns are taken and which diagonals are taken. Diagonals are identified in two ways: the row minus column value identifies one diagonal direction, and the row plus column value identifies the other. Keeping these in three sets, one for columns and one for each diagonal direction, means each legality check is a constant time membership test rather than a scan across the board.

The mechanism is that a queen on row r and column c attacks the cells that share a column, a row minus column value or a row plus column value. So the attack test becomes three set lookups. Placing the queen adds its column and its two diagonal identifiers, and removing it takes them out again, which is why the backtracking step has to undo exactly what the placement step did.

The trade-off to name is the search cost. The problem is exponential in the worst case, because the number of partial placements is enormous and only a few lead to a solution, but the pruning from the column and diagonal checks cuts it down enormously in practice. The eight queen case is solvable in milliseconds. Adding a symmetry optimisation, such as only trying the first half of the columns in the first row and mirroring the result, cuts the work further, and that kind of domain reasoning is what makes this problem a good interview topic.

Track the occupied columns and the two diagonal directions in sets, then place one queen per row and undo the placement whenever a row cannot be filled.

def solve_n_queens(n):
    columns = set()
    diagonals = set()
    anti_diagonals = set()
    board = []

    def place(row):
        if row == n:
            return True
        for col in range(n):
            if col in columns or row - col in diagonals or row + col in anti_diagonals:
                continue
            columns.add(col)
            diagonals.add(row - col)
            anti_diagonals.add(row + col)
            board.append(col)
            if place(row + 1):
                return True
            board.pop()
            columns.discard(col)
            diagonals.discard(row - col)
            anti_diagonals.discard(row + col)
        return False

    if not place(0):
        return []
    return [''.join('Q' if c == col else '.' for c in range(n)) for col in board]


for row in solve_n_queens(4):
    print(row)

The output is four rows. The first is dot Q dot dot, the second is dot dot Q dot, the third is Q dot dot dot and the fourth is dot dot dot Q. No two queens share a row, a column or a diagonal.

The mechanism is the three set lookups in the guard. A column is rejected if it is already used, if the row minus column value is already used, or if the row plus column value is already used. Each of those three conditions is exactly one of the ways a queen can attack another square.

The trade-off to name is the symmetry of the undo step. The removal code must undo precisely what the placement code did, and getting that wrong is the classic bug, because a stale entry in the diagonal set silently rejects legal positions later on. Using discard rather than remove means a missing entry does not raise, which is a small convenience but hides mistakes. For larger boards you would also add the symmetry optimisation and, for eight queens, the standard technique of precomputing the known solutions, because the search space is large even with good pruning.

Compare the proposed square against every queen already placed. It is unsafe if any of them shares the column, or if the row distance and column distance are equal, which means they lie on a shared diagonal.

def is_safe(board, row, col, n):
    for i in range(row):
        if board[i] == col:
            return False
        if abs(board[i] - col) == row - i:
            return False
    return True


board = [1, 3, 0]
print(is_safe(board, 3, 2, 4))
print(is_safe(board, 3, 0, 4))

The outputs are True and False. The first proposal puts a queen on row three, column two, where the diagonal distance is one while the row distance is three, so it is safe. The second proposal is on column zero, which is already occupied by the queen on row two.

The mechanism is the absolute difference test. Two queens share a diagonal exactly when the vertical distance between them equals the horizontal distance, so comparing the absolute column difference with the row difference catches both diagonal directions in one expression.

The trade-off to name is that this check is linear in the number of queens already placed, because it scans all of them. The set-based version in the previous answer is constant time per check because it looks up three identifiers, and that difference compounds over a full search. The scan version is still worth understanding because it makes the geometry explicit, and it is the version you would write if you were reasoning about the problem from scratch rather than optimising it.