DSA/Chessboards and Queens

Chessboard and Queens (CSES) — Backtracking Notes

Problem: Place 8 queens on an 8×8 chessboard so that no two queens attack each other. Some squares are reserved (marked with a star in the input) and cannot hold a queen. Count the number of valid placements.

Why Is This a Recursion Problem?

There are two strong signals that point to recursion (specifically backtracking):

1. No natural iterative solution. We're placing 8 queens, and the number of valid choices for queen k depends entirely on how queens 1..k-1 were placed. You'd need 8 nested for-loops, one per queen — and even that doesn't work cleanly, since the number of valid choices at each level changes dynamically.
2. Tiny constraints. An 8×8 board is a dead giveaway. Constraints this small almost always mean the intended complexity is something like O(2^n) or O(n!) — both are hallmarks of brute-force / backtracking search.

The Core Idea

Since we need exactly one queen per row (8 queens, 8 rows), we can place them row by row:

• Write a recursive function place(row).
• For the current row, try every column from 0 to 7.
• If the square is free (not reserved) and not attacked, place a queen there, recurse into row + 1, then undo the placement (this is the "backtrack" step) before trying the next column.
• If row == n, it means all 8 queens were placed successfully — increment the answer.

The undo step is critical: after exploring one branch, the board must be restored to its previous state so the next column can be tried cleanly.

First Working Version: Brute-Force Attack Checks

The simplest (but slowest) way to check if a square is attacked is to literally scan:

• Upward in the same column, for an existing queen.
• Diagonally up-left (decrementing both row and column).
• Diagonally up-right (decrementing row, incrementing column).

This works, and on the actual 8×8 test case it's already fast (a couple of milliseconds), because the search space collapses quickly once conflicts are found. But it does unnecessary work — every single placement attempt re-scans the whole column and both diagonals.

Optimizing: O(1) Attack Checks

Instead of scanning every time, keep track of which columns and diagonals are already occupied using boolean arrays, updated incrementally as queens are placed and removed.

Columns

Trivial — one boolean array indexed by column:

vector<bool> colAttacked(n, false);

Diagonals: The Grid Math Trick

This is the part worth internalizing, since it comes up in many other grid problems.

There are two diagonal directions on a grid, and each has a simple invariant:

Diagonal type 1 (↘ direction, i.e. going down-right / cells where row and column both increase together):

Take a 4×4 board and look at the diagonal containing (0,3), (1,2), (2,1), (3,0). Notice:

$row+col=3\text{for every cell on this diagonal}$

The next diagonal over — (1,3), (2,2), (3,1) — satisfies $row+col=4$. In general:

Two cells lie on the same "↘"-type diagonal if and only if $row+col$ is the same for both.

This matches the geometric fact that a line of the form $y+x=c$ is a straight line tilted at 45°.

Diagonal type 2 (↙ direction):

Look at (1,0), (2,1), (3,2): here $row-col=1$ for all of them. In general:

Two cells lie on the same "↙"-type diagonal if and only if $row-col$ is the same for both.

The negative-index problem: $row-col$ can be negative (e.g. row=0, col=7 gives −7), and arrays can't have negative indices. The fix is a constant offset: since the minimum possible value of $row-col$ is $-(n-1)$, add $n-1$ to shift everything into the non-negative range:

$index=row-col+(n-1)$

Both diagonal arrays need size $2n-1$ (for n=8, that's 15 — matching the fact that an 8×8 board really does have 15 diagonals in each direction).

Final Code

Same algorithm, three languages. The logic is identical in all three: row-by-row backtracking with O(1) column/diagonal checks via boolean arrays.

C++PythonRust

#include <bits/stdc++.h>
using namespace std;

int n = 8;
vector<string> grid;

vector<bool> colAttacked(8, false);
vector<bool> diag1Attacked(15, false); // indexed by row + col
vector<bool> diag2Attacked(15, false); // indexed by row - col + (n - 1)

long long answer = 0;

void place(int row) {
    if (row == n) {
        answer++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (grid[row][col] == '*') continue;               // reserved square
        if (colAttacked[col]) continue;
        if (diag1Attacked[row + col]) continue;
        if (diag2Attacked[row - col + n - 1]) continue;

        // place queen
        colAttacked[col] = true;
        diag1Attacked[row + col] = true;
        diag2Attacked[row - col + n - 1] = true;

        place(row + 1);

        // backtrack: undo placement
        colAttacked[col] = false;
        diag1Attacked[row + col] = false;
        diag2Attacked[row - col + n - 1] = false;
    }
}

int main() {
    grid.resize(n);
    for (auto &row : grid) cin >> row;

    place(0);
    cout << answer << endl;
}

import sys

def place(row):
    global answer
    if row == n:
        answer += 1
        return
    for col in range(n):
        if grid[row][col] == '*':
            continue
        if col_attacked[col]:
            continue
        if diag1_attacked[row + col]:
            continue
        if diag2_attacked[row - col + n - 1]:
            continue

        col_attacked[col] = True
        diag1_attacked[row + col] = True
        diag2_attacked[row - col + n - 1] = True

        place(row + 1)

        col_attacked[col] = False
        diag1_attacked[row + col] = False
        diag2_attacked[row - col + n - 1] = False

def main():
    global n, grid, col_attacked, diag1_attacked, diag2_attacked, answer
    n = 8
    grid = [input() for _ in range(n)]
    col_attacked = [False] * n
    diag1_attacked = [False] * (2 * n - 1)
    diag2_attacked = [False] * (2 * n - 1)
    answer = 0

    sys.setrecursionlimit(10000)
    place(0)
    print(answer)

if __name__ == "__main__":
    main()

use std::io::{self, Read};

const N: usize = 8;

struct Solver {
    grid: Vec<Vec<u8>>,
    col_attacked: [bool; N],
    diag1_attacked: [bool; 2 * N - 1], // indexed by row + col
    diag2_attacked: [bool; 2 * N - 1], // indexed by row + (N - 1) - col
    answer: u64,
}

impl Solver {
    fn place(&mut self, row: usize) {
        if row == N {
            self.answer += 1;
            return;
        }
        for col in 0..N {
            if self.grid[row][col] == b'*' {
                continue; // reserved square
            }
            if self.col_attacked[col] {
                continue;
            }
            let d1 = row + col;
            let d2 = row + N - 1 - col; // usize-safe version of row - col + (N - 1)
            if self.diag1_attacked[d1] || self.diag2_attacked[d2] {
                continue;
            }

            self.col_attacked[col] = true;
            self.diag1_attacked[d1] = true;
            self.diag2_attacked[d2] = true;

            self.place(row + 1);

            // backtrack: undo placement
            self.col_attacked[col] = false;
            self.diag1_attacked[d1] = false;
            self.diag2_attacked[d2] = false;
        }
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let grid: Vec<Vec<u8>> = input
        .lines()
        .take(N)
        .map(|line| line.as_bytes().to_vec())
        .collect();

    let mut solver = Solver {
        grid,
        col_attacked: [false; N],
        diag1_attacked: [false; 2 * N - 1],
        diag2_attacked: [false; 2 * N - 1],
        answer: 0,
    };

    solver.place(0);
    println!("{}", solver.answer);
}

Note: it's not necessary to actually mark the square in grid as a queen ('Q'); the three boolean arrays already fully capture every constraint we need to check, so there's nothing to gain from also mutating the grid string. The Rust version sidesteps the negative-index offset by rewriting $row-col+(n-1)$ as $row+(n-1)-col$, which is equivalent but never underflows a usize mid-expression.

Complexity

• Row 0 has at most 8 choices, row 1 has at most 7 (one column already taken), and so on — giving a rough bound of O(n!), possibly with an extra factor of n from the per-row scan: O(n! · n).
• In practice it's much faster than this bound suggests, because diagonal constraints prune the search tree aggressively. On the empty 8×8 board (the worst case, since nothing is reserved), the recursion has exactly 92 leaves (the well-known number of solutions to the 8-queens problem) and runs in about a millisecond.
• This approach does not scale to large n (e.g. n = 1000). Placing n non-attacking queens under arbitrary reserved-square constraints is a much harder problem in general — for large boards you need entirely different techniques (or the instance may simply be intractable).

What Is Backtracking?

Backtracking is the name for exactly this pattern: recursively try a choice, recurse further assuming that choice, and if a later step hits a dead end (no valid moves possible), undo the choice ("backtrack") and try the next alternative. The name comes from the fact that the recursion tree doesn't just go forward — it routinely retreats and retries.

Some useful mental models:

• It's the same technique behind Sudoku solvers: try a digit, recurse, and if a contradiction is eventually reached, undo and try a different digit.
• Backtracking is typically used to find one valid solution (Sudoku) or to count all valid solutions (this problem) when there's no faster closed-form or DP approach — often because the problem is NP-hard in general.
• Backtracking problems are almost always about a "good enough" solution rather than a provably optimal one. There is nearly always room to add smarter pruning:
  • Example: if you can detect before recursing that some later row has only one legal column left, you can propagate that constraint early and cut off huge unproductive branches. This kind of look-ahead pruning can make backtracking hundreds or even thousands of times faster — but it's an enhancement on top of the base algorithm, not a change to its fundamental structure.

Key Takeaways

• Small constraints (like n = 8) are a strong hint that the intended solution is exponential/factorial-time backtracking.
• Always pair "make a move" with "undo the move" (backtrack) after the recursive call returns — this is what makes the search correct.
• For diagonal checks on a grid, remember:
  • $row+col$ is constant along one diagonal direction.
  • $row-col$ is constant along the other (add an offset of $n-1$ to keep indices non-negative).
• Prefer O(1) incremental state (boolean arrays) over re-scanning the board on every check — it turns an already-fast solution into a very fast one.
• Global arrays/variables are common in competitive programming for exactly this kind of state — avoids passing/copying containers on every recursive call.