Advanced Backtracking

Why Advanced Backtracking Matters

A chessboard placement, a partially filled Sudoku, and a word hidden in a letter grid look like different problems. Each asks you to build a complete object through decisions while rejecting partial objects that cannot work. Trying every complete possibility wastes effort because many failures become visible much earlier.

Advanced backtracking makes that early information useful. N-Queens can represent occupied columns and attacked diagonals with bit masks. Sudoku can choose the blank cell with the fewest legal digits. Word Search can reject impossible letter inventories and track cells used by the current path. Symmetry breaking avoids exploring equivalent placements when the transformation and counting rule are justified.

You will implement all three searches, follow their state changes and undo operations, and compare meaningful node counters. The goal is exact search with less wasted work: the optimizations change which branches are explored or how cheaply legality is checked, while preserving the requested answer.

Advanced backtracking combines a valid partial state, a small set of legal next choices, early contradiction checks, and reliable restoration before exploring a sibling. Bit masks make constraints cheap, minimum-remaining-values selection exposes constrained decisions early, and justified symmetry breaking removes equivalent search work. None of these techniques removes the need to prove that every required solution is either explored or represented correctly.

Core Concepts and Terminology

The search state must contain everything needed to decide future legality. For N-Queens, one decision assigns a column to the next row; masks record occupied columns and the diagonals attacking that row. For Sudoku, the grid and row, column, and box masks determine each blank's legal digits. For Word Search, the current cell, matched prefix length, and visited cells determine which neighboring moves remain legal.

The output objective matters. The N-Queens routine counts every solution, using reflection weights without storing all boards. Sudoku searches for up to two solutions: count $0$ means unsatisfiable, count $1$ means unique after exhaustive search, and count $2$ means at least two. Word Search stops at the first valid path and returns that path in the original word's order.

A prune must prove that the current branch cannot contribute a required answer. A Sudoku blank with no legal digit is a contradiction. A used Word Search cell cannot be reused in the same path. A variable-ordering heuristic such as MRV is different: it chooses which unresolved decision to make next, without itself discarding any valid completion.

Term	Definition, example, and role
Partial assignment	Decisions already made, such as queen columns $[1,3]$ in the first two rows.
Domain	Legal values for the next decision; a Sudoku blank might allow $\{2,3\}$.
Constraint mask	A compact set of occupied or forbidden values; intersecting with the board's full mask prevents out-of-range bits.
MRV	Minimum remaining values: choose the blank with the smallest current candidate set. Ties here use row-major order.
Forward contradiction check	Detect a blank whose domain is empty after earlier placements, before making another choice.
Undo	Restore every changed component of the parent state before returning or trying another candidate.
Path-local visited set	Cells unavailable only because they occur on the current Word Search path; other branches can reuse them.
Symmetry breaking	Search one justified representative from an equivalence pair, then reconstruct or weight the omitted answers.
Node counter	One count per entered recursive state; it is not a count of every rejected candidate or every primitive operation.
Capped solution count	Stop at two solutions to distinguish no solution, uniqueness, and nonuniqueness without enumerating all completions.

All examples use deterministic ordering: increasing queen columns and Sudoku digits, row-major MRV tie-breaking and Word Search starts, and neighbor order up, right, down, left. This makes returned solutions, paths, and counters directly comparable across languages.

How Advanced Backtracking Works, Step by Step

Optimized N-Queens. Number columns from $0$ to $n-1$, with column $c$ represented by bit $2^c$. Let $U=2^n-1$, and let $C,H,L$ denote occupied columns and diagonal attacks in the current row. The legal-column mask is

$$A=U\land\neg(C\lor H\lor L),$$

where the operations are bitwise. Extract the lowest set bit with bit = available & -available, remove it from the candidate mask, and recurse with

$$C'=C\lor b,\qquad H'=((H\lor b)\ll1)\land U,\qquad L'=(L\lor b)\gg1.$$

The shifted masks describe attacks on the next row. The code's high mask shifts toward higher-numbered column bits, and low toward lower-numbered bits. These integer states are passed by value, so returning automatically resumes with the parent's unchanged masks.

Reflecting a complete board vertically maps first-row column $c$ to $n-1-c$. Search first-row columns strictly before the midpoint and double their solution counts. For odd $n$, search the center column separately with weight $1$: its reflected solutions also start in that center branch. The convention for $n=0$ is one empty placement. This reflection optimization counts all placements, not fundamental solutions under all board rotations and reflections.

Sudoku with MRV. Validate every given digit before searching. For a blank at row $r$, column $c$, and box $b$, compute the full digit mask minus the union of its three occupancy masks. If any blank has no candidate, return failure. Otherwise choose the blank with the fewest candidates, trying digits in increasing order. Update the grid and all three masks, recurse, then clear the added bit and restore the cell to zero. Even when the second solution triggers an early stop, undo happens before returning.

The diagram isolates one move in a small $4\times4$ Sudoku. Digits $1$ and $4$ occupy bits in mask 1001; placing digit $2$ adds bit 0010, giving 1011. Undo restores the row, column, and box masks to 1001, as well as restoring the blank cell.

Word Search. Validate a rectangular uppercase board and the target word. An empty word matches the empty path; a nonempty word cannot fit on an empty board or require more cells than the board has. Reject any word requiring more copies of a letter than the board contains. If the last letter is rarer than the first, search the reversed word; reversing a path is valid because orthogonal adjacency is undirected. Reverse the saved path back before returning it.

At a matching cell, mark it visited and append it to the path. Recurse only to an in-bounds, unvisited orthogonal neighbor matching the next letter. Save a copy when the final letter is reached. Then pop the current cell and clear its visited mark on every return, including success. The saved answer is separate from this reusable search state.

Advanced Backtracking control flow

flowchart TD
    A["Enter a valid partial state; count one node"] --> B{"Complete solution?"}
    B -->|Yes| C["Count or copy the solution"]
    C --> D["Return stop flag to caller"]
    B -->|No| E["Choose a decision; compute legal choices"]
    E --> F{"Contradiction or no choices?"}
    F -->|Yes| D
    F -->|No| G["Take the next legal choice"]
    G --> H["Apply grid, mask, or visited changes"]
    H --> I["Recurse into the child state"]
    I --> J["Restore every changed component"]
    J --> K{"Enough answers collected?"}
    K -->|Yes| D
    K -->|No| L{"More choices?"}
    L -->|Yes| G
    L -->|No| D

For the N-Queens value-state implementation, restoration means returning to unchanged caller arguments. For the Sudoku and Word Search implementations, restoration is explicit mutation reversal. A return flag communicates that the search objective is satisfied; it never authorizes skipping the caller's undo step.

Worked Example with a Full Trace

Count $4$-Queens solutions with vertical-reflection symmetry enabled. A prefix $[c_0,\ldots,c_{r-1}]$ places a queen in column $c_i$ of row $i$. The root is node $1$. Although all four first columns are legal, only $0$ and $1$ are searched, because $3$ and $2$ are their reflected partners.

The masks below are printed most-significant bit first: 0001 means column $0$. Diagonal masks refer to attacks in the next row to be filled. Legal columns are those remaining after all three masks are combined.

Entered node	Prefix	Columns $C$	High attacks $H$	Low attacks $L$	Legal next columns	Outcome or next transition
$1$	$[]$	`0000`	`0000`	`0000`	All $\{0,1,2,3\}$; search $\{0,1\}$	Enter first-column branch $0$.
$2$	$[0]$	`0001`	`0010`	`0000`	$\{2,3\}$	Try column $2$.
$3$	$[0,2]$	`0101`	`1100`	`0010`	$\varnothing$	Dead end; return to $[0]$ and try $3$.
$4$	$[0,3]$	`1001`	`0100`	`0100`	$\{1\}$	Try column $1$.
$5$	$[0,3,1]$	`1011`	`1100`	`0011`	$\varnothing$	Dead end; exhaust the first-column-$0$ branch.
$6$	$[1]$	`0010`	`0100`	`0001`	$\{3\}$	Try column $3$.
$7$	$[1,3]$	`1010`	`1000`	`0100`	$\{0\}$	Try column $0$.
$8$	$[1,3,0]$	`1011`	`0010`	`0010`	$\{2\}$	Try column $2$.
$9$	$[1,3,0,2]$	`1111`	`1100`	`0011`	No row remains.	One searched solution, counted with weight $2$.

The first root branch contributes zero solutions. The second contributes one searched solution, whose reflection is $[2,0,3,1]$. The reported count is therefore $2$, while the reported node count stays $9$: solution weights do not multiply the work counter. Searching all four first columns instead visits $17$ nodes.

The same principles appear in the other sample runs. The $9\times9$ Sudoku begins with $51$ blanks. MRV resolves this particular puzzle without a branching dead end, visits $52$ states including the root and completed board, and exhausts the remaining choices to establish uniqueness. A different puzzle can require many failed guesses; this sample's count is not a general Sudoku running-time bound.

For Word Search on rows ABCE, SFCS, ADEE, ABCCED is searched backward because D is rarer than A. The internal path follows D,E,C,C,B,A; reversing the saved coordinates gives $[(0,0),(0,1),(0,2),(1,2),(2,2),(2,1)]$. For SEE, the search visits matching prefixes at $(1,0)$, $(1,3)$, $(0,3)$, $(2,3)$, and $(2,2)$, with the first and third visits ending in failure. The word ABCB is rejected before recursion because it requires two B cells but the board has only one.

Worked Example

Trace It by Hand

At prefix $[0,3]$, combine 1001, 0100, and 0100, then keep only the four board bits not present in that union. The result is 0010, so column $1$ is the only next choice. After taking it, the next-row masks become 1011, 1100, and 0011; their union is 1111, so the branch must return. In the Sudoku diagram, try digit $3$ only after undoing digit $2$ in the grid and all three masks.

Implementation in Python, C++, and Java

Each panel is a complete program containing all three solvers and identical sample data. N-Queens supports $0\le n\le12$, avoiding native shift-width and count-size problems in this teaching range. Sudoku supports $4\times4$ grids with $2\times2$ boxes and $9\times9$ grids with $3\times3$ boxes; zero denotes a blank. Word Search accepts an empty board or a rectangular board of at most $8\times8$ uppercase ASCII letters, with words of length at most $16$.

Conflicting Sudoku givens are invalid input and raise an error. A locally consistent grid can still be globally unsatisfiable; that returns count $0$ and no solution. The count is capped at $2$, so the value $2$ reports nonuniqueness rather than the exact number of completions. The first solution is copied before the search restores its working grid.

Every solver owns its state and resets its counter for each call. N-Queens counts the empty root once, plus each recursively entered placement state. Sudoku counts every recursive entry, including completed boards and zero-domain failures. Word Search counts matching-prefix entries only: invalid neighbors and preprocessing rejections do not create recursive nodes. These counters describe search structure; Sudoku's MRV scan does substantially more work per node than one constant-size Word Search neighbor check.

The programs leave all supplied boards and grids unchanged. Recursion depth is at most $n$ queen placements, the number of Sudoku blanks, or the word length, plus the applicable initial call. Native node counters use signed $64$-bit integers; extending the implementation to much larger searches also requires reconsidering counter overflow and recursion limits.

def nqueens(n, symmetry=True):
    if not 0 <= n <= 12:
        raise ValueError("n must be in 0..12")
    full, nodes = (1 << n) - 1, 1
    if n == 0:
        return 1, nodes

    def dfs(cols, high, low):
        nonlocal nodes
        nodes += 1
        if cols == full:
            return 1
        available = full & ~(cols | high | low)
        total = 0
        while available:
            bit = available & -available
            available -= bit
            total += dfs(cols | bit, ((high | bit) << 1) & full, (low | bit) >> 1)
        return total

    total = 0
    for col in range(n // 2 if symmetry else n):
        bit = 1 << col
        total += (2 if symmetry else 1) * dfs(bit, (bit << 1) & full, bit >> 1)
    if symmetry and n % 2:
        bit = 1 << (n // 2)
        total += dfs(bit, (bit << 1) & full, bit >> 1)
    return total, nodes


def sudoku(grid):
    n = len(grid)
    if n not in (4, 9) or any(len(row) != n for row in grid):
        raise ValueError("use a square 4x4 or 9x9 grid")
    side, full = (2 if n == 4 else 3), (1 << n) - 1
    work = [row.copy() for row in grid]
    rows, cols, boxes = [0] * n, [0] * n, [0] * n
    for r in range(n):
        for c in range(n):
            value = work[r][c]
            if not 0 <= value <= n:
                raise ValueError("invalid Sudoku digit")
            if value:
                bit, box = 1 << (value - 1), (r // side) * side + c // side
                if (rows[r] | cols[c] | boxes[box]) & bit:
                    raise ValueError("conflicting givens")
                rows[r] |= bit
                cols[c] |= bit
                boxes[box] |= bit
    count, nodes, first = 0, 0, []

    def dfs():
        nonlocal count, nodes, first
        nodes += 1
        best, best_count = None, n + 1
        for r in range(n):
            for c in range(n):
                if work[r][c] == 0:
                    box = (r // side) * side + c // side
                    mask = full & ~(rows[r] | cols[c] | boxes[box])
                    size = mask.bit_count()
                    if size == 0:
                        return False
                    if size < best_count:
                        best, best_count = (r, c, box, mask), size
        if best is None:
            count += 1
            if count == 1:
                first = [row.copy() for row in work]
            return count == 2
        r, c, box, mask = best
        while mask:
            bit = mask & -mask
            mask -= bit
            work[r][c] = bit.bit_length()
            rows[r] |= bit
            cols[c] |= bit
            boxes[box] |= bit
            stop = dfs()
            rows[r] ^= bit
            cols[c] ^= bit
            boxes[box] ^= bit
            work[r][c] = 0
            if stop:
                return True
        return False

    dfs()
    assert work == grid
    return count, nodes, first


def word_search(board, word):
    rcount, ccount = len(board), len(board[0]) if board else 0
    if rcount > 8 or (rcount and not 1 <= ccount <= 8) or any(len(row) != ccount for row in board):
        raise ValueError("invalid board shape")
    if len(word) > 16 or any(len(ch) != 1 or not 'A' <= ch <= 'Z' for row in board for ch in row) or any(not 'A' <= ch <= 'Z' for ch in word):
        raise ValueError("use uppercase letters and a word of length at most 16")
    if not word:
        return True, 0, []
    if len(word) > rcount * ccount:
        return False, 0, []
    have, need = [0] * 26, [0] * 26
    for row in board:
        for ch in row:
            have[ord(ch) - 65] += 1
    for ch in word:
        need[ord(ch) - 65] += 1
    if any(a > b for a, b in zip(need, have)):
        return False, 0, []
    reverse = have[ord(word[0]) - 65] > have[ord(word[-1]) - 65]
    search = word[::-1] if reverse else word
    used = [[False] * ccount for _ in board]
    nodes, path, answer = 0, [], []

    def dfs(r, c, index):
        nonlocal nodes, answer
        nodes += 1
        used[r][c] = True
        path.append(r * ccount + c)
        found = index + 1 == len(search)
        if found:
            answer = path.copy()
        else:
            for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rcount and 0 <= nc < ccount and not used[nr][nc] and board[nr][nc] == search[index + 1]:
                    if dfs(nr, nc, index + 1):
                        found = True
                        break
        path.pop()
        used[r][c] = False
        return found

    for r in range(rcount):
        for c in range(ccount):
            if board[r][c] == search[0] and dfs(r, c, 0):
                if reverse:
                    answer.reverse()
                assert not path and not any(any(row) for row in used)
                return True, nodes, answer
    assert not path and not any(any(row) for row in used)
    return False, nodes, []


def path_text(path, cols):
    return "[" + ",".join(f"({p // cols},{p % cols})" for p in path) + "]"


def main():
    q4, q8, full8 = nqueens(4), nqueens(8), nqueens(8, False)
    print(f"queens 4 symmetry: solutions={q4[0]}, nodes={q4[1]}")
    print(f"queens 8 symmetry: solutions={q8[0]}, nodes={q8[1]}")
    print(f"queens 8 full: solutions={full8[0]}, nodes={full8[1]}")
    lines = ["530070000", "600195000", "098000060", "800060003", "400803001", "700020006", "060000280", "000419005", "000080079"]
    grid = [[int(ch) for ch in row] for row in lines]
    count, nodes, solved = sudoku(grid)
    print(f"sudoku: solutions capped at 2={count}, nodes={nodes}")
    for row in solved:
        print("".join(map(str, row)))
    board = [list("ABCE"), list("SFCS"), list("ADEE")]
    results = []
    for word in ["ABCCED", "SEE", "ABCB"]:
        found, nodes, path = word_search(board, word)
        results.append(found)
        print(f"word {word}: found={int(found)}, nodes={nodes}, path={path_text(path, 4)}")
    unchanged = ["".join(map(str, row)) for row in grid] == lines and ["".join(row) for row in board] == ["ABCE", "SFCS", "ADEE"]
    print("inputs unchanged = " + str(int(unchanged)))
    ok = q4[0] == 2 and q8[0] == full8[0] == 92 and count == 1 and results == [True, True, False] and unchanged
    print("checks = " + ("PASS" if ok else "FAIL"))


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
using Grid = std::vector<std::vector<int>>;
using Count = std::int64_t;
std::pair<Count, Count> nqueens(int n, bool symmetry = true) {
    if (n < 0 || n > 12) throw std::invalid_argument("n must be in 0..12");
    int full = (1 << n) - 1; Count nodes = 1;
    if (n == 0) return {1, nodes};
    std::function<Count(int,int,int)> dfs = [&](int cols, int high, int low) -> Count {
        ++nodes; if (cols == full) return 1;
        int available = full & ~(cols | high | low); Count total = 0;
        while (available) {
            int bit = available & -available; available -= bit;
            total += dfs(cols | bit, ((high | bit) << 1) & full, (low | bit) >> 1);
        }
        return total;
    };
    Count total = 0;
    for (int col = 0; col < (symmetry ? n / 2 : n); ++col) {
        int bit = 1 << col;
        total += (symmetry ? 2 : 1) * dfs(bit, (bit << 1) & full, bit >> 1);
    }
    if (symmetry && n % 2) { int bit = 1 << (n / 2); total += dfs(bit, (bit << 1) & full, bit >> 1); }
    return {total, nodes};
}
int popcount(int mask) { int count = 0; while (mask) { mask &= mask - 1; ++count; } return count; }
int digit(int bit) { int d = 1; while (bit > 1) { bit >>= 1; ++d; } return d; }
struct SudokuResult { int count; Count nodes; Grid first; };
SudokuResult sudoku(const Grid& grid) {
    int n = static_cast<int>(grid.size());
    if (n != 4 && n != 9) throw std::invalid_argument("use 4x4 or 9x9");
    for (const auto& row : grid) if (static_cast<int>(row.size()) != n) throw std::invalid_argument("nonsquare grid");
    int side = n == 4 ? 2 : 3, full = (1 << n) - 1;
    Grid work = grid, first; std::vector<int> rows(n), cols(n), boxes(n);
    for (int r = 0; r < n; ++r) for (int c = 0; c < n; ++c) {
        int value = work[r][c];
        if (value < 0 || value > n) throw std::invalid_argument("invalid Sudoku digit");
        if (value) {
            int bit = 1 << (value - 1), box = (r / side) * side + c / side;
            if ((rows[r] | cols[c] | boxes[box]) & bit) throw std::invalid_argument("conflicting givens");
            rows[r] |= bit; cols[c] |= bit; boxes[box] |= bit;
        }
    }
    int count = 0; Count nodes = 0;
    std::function<bool()> dfs = [&]() {
        ++nodes; int br = -1, bc = -1, bx = -1, best_mask = 0, best_count = n + 1;
        for (int r = 0; r < n; ++r) for (int c = 0; c < n; ++c) if (work[r][c] == 0) {
            int box = (r / side) * side + c / side;
            int mask = full & ~(rows[r] | cols[c] | boxes[box]), size = popcount(mask);
            if (size == 0) return false;
            if (size < best_count) { br = r; bc = c; bx = box; best_mask = mask; best_count = size; }
        }
        if (br == -1) { ++count; if (count == 1) first = work; return count == 2; }
        while (best_mask) {
            int bit = best_mask & -best_mask; best_mask -= bit;
            work[br][bc] = digit(bit); rows[br] |= bit; cols[bc] |= bit; boxes[bx] |= bit;
            bool stop = dfs();
            rows[br] ^= bit; cols[bc] ^= bit; boxes[bx] ^= bit; work[br][bc] = 0;
            if (stop) return true;
        }
        return false;
    };
    dfs(); assert(work == grid); return {count, nodes, first};
}
struct WordResult { bool found; Count nodes; std::vector<int> path; };
WordResult word_search(const std::vector<std::string>& board, const std::string& word) {
    int nr = static_cast<int>(board.size()), nc = nr ? static_cast<int>(board[0].size()) : 0;
    if (nr > 8 || (nr && (nc < 1 || nc > 8))) throw std::invalid_argument("invalid board shape");
    for (const auto& row : board) {
        if (static_cast<int>(row.size()) != nc) throw std::invalid_argument("ragged board");
        for (char ch : row) if (ch < 'A' || ch > 'Z') throw std::invalid_argument("invalid board letter");
    }
    if (word.size() > 16) throw std::invalid_argument("word too long");
    for (char ch : word) if (ch < 'A' || ch > 'Z') throw std::invalid_argument("invalid word letter");
    if (word.empty()) return {true, 0, {} };
    if (word.size() > static_cast<std::size_t>(nr * nc)) return {false, 0, {} };
    std::vector<int> have(26), need(26);
    for (const auto& row : board) for (char ch : row) ++have[ch - 'A'];
    for (char ch : word) ++need[ch - 'A'];
    for (int i = 0; i < 26; ++i) if (need[i] > have[i]) return {false, 0, {} };
    bool reverse = have[word.front() - 'A'] > have[word.back() - 'A'];
    std::string search = word; if (reverse) std::reverse(search.begin(), search.end());
    std::vector<std::vector<bool>> used(nr, std::vector<bool>(nc));
    Count nodes = 0; std::vector<int> path, answer;
    const int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
    std::function<bool(int,int,int)> dfs = [&](int r, int c, int index) {
        ++nodes; used[r][c] = true; path.push_back(r * nc + c);
        bool found = index + 1 == static_cast<int>(search.size());
        if (found) answer = path;
        else for (int d = 0; d < 4; ++d) {
            int rr = r + dr[d], cc = c + dc[d];
            if (rr >= 0 && rr < nr && cc >= 0 && cc < nc && !used[rr][cc] && board[rr][cc] == search[index + 1])
                if (dfs(rr, cc, index + 1)) { found = true; break; }
        }
        path.pop_back(); used[r][c] = false; return found;
    };
    for (int r = 0; r < nr; ++r) for (int c = 0; c < nc; ++c) if (board[r][c] == search[0] && dfs(r,c,0)) {
        if (reverse) std::reverse(answer.begin(), answer.end());
        assert(path.empty()); for (const auto& row : used) for (bool mark : row) assert(!mark);
        return {true, nodes, answer};
    }
    assert(path.empty()); for (const auto& row : used) for (bool mark : row) assert(!mark);
    return {false, nodes, {} };
}
std::string path_text(const std::vector<int>& path, int cols) {
    std::string s = "[";
    for (std::size_t i = 0; i < path.size(); ++i) {
        if (i) s += ",";
        s += "(" + std::to_string(path[i] / cols) + "," + std::to_string(path[i] % cols) + ")";
    }
    return s + "]";
}
int main() {
    auto q4 = nqueens(4), q8 = nqueens(8), full8 = nqueens(8, false);
    std::cout << "queens 4 symmetry: solutions=" << q4.first << ", nodes=" << q4.second << '\n';
    std::cout << "queens 8 symmetry: solutions=" << q8.first << ", nodes=" << q8.second << '\n';
    std::cout << "queens 8 full: solutions=" << full8.first << ", nodes=" << full8.second << '\n';
    std::vector<std::string> lines = {"530070000", "600195000", "098000060", "800060003", "400803001", "700020006", "060000280", "000419005", "000080079"};
    Grid grid(9, std::vector<int>(9));
    for (int r = 0; r < 9; ++r) for (int c = 0; c < 9; ++c) grid[r][c] = lines[r][c] - '0';
    auto solved = sudoku(grid);
    std::cout << "sudoku: solutions capped at 2=" << solved.count << ", nodes=" << solved.nodes << '\n';
    for (const auto& row : solved.first) { for (int x : row) std::cout << x; std::cout << '\n'; }
    std::vector<std::string> board = {"ABCE", "SFCS", "ADEE"}; std::vector<bool> results;
    for (const char* raw : {"ABCCED", "SEE", "ABCB"}) {
        std::string word = raw;
        auto result = word_search(board, word); results.push_back(result.found);
        std::cout << "word " << word << ": found=" << result.found << ", nodes=" << result.nodes << ", path=" << path_text(result.path,4) << '\n';
    }
    bool unchanged = board == std::vector<std::string>({"ABCE", "SFCS", "ADEE"});
    for (int r = 0; r < 9; ++r) for (int c = 0; c < 9; ++c) unchanged = unchanged && grid[r][c] == lines[r][c] - '0';
    std::cout << "inputs unchanged = " << unchanged << '\n';
    bool ok = q4.first == 2 && q8.first == 92 && full8.first == 92 && solved.count == 1 && results == std::vector<bool>({true,true,false}) && unchanged;
    std::cout << "checks = " << (ok ? "PASS" : "FAIL") << '\n';
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    static long[] nqueens(int n, boolean symmetry) {
        if (n < 0 || n > 12) throw new IllegalArgumentException("n must be in 0..12");
        if (n == 0) return new long[] {1,1};
        int full = (1 << n) - 1;
        class Search {
            long nodes = 1;
            long dfs(int cols, int high, int low) {
                ++nodes; if (cols == full) return 1;
                int available = full & ~(cols | high | low); long total = 0;
                while (available != 0) {
                    int bit = available & -available; available -= bit;
                    total += dfs(cols | bit, ((high | bit) << 1) & full, (low | bit) >>> 1);
                }
                return total;
            }
        }
        Search search = new Search(); long total = 0;
        for (int col = 0; col < (symmetry ? n / 2 : n); ++col) {
            int bit = 1 << col;
            total += (symmetry ? 2 : 1) * search.dfs(bit, (bit << 1) & full, bit >>> 1);
        }
        if (symmetry && n % 2 != 0) { int bit = 1 << (n / 2); total += search.dfs(bit, (bit << 1) & full, bit >>> 1); }
        return new long[] {total, search.nodes};
    }
    static int[][] copyGrid(int[][] grid) {
        int[][] copy = new int[grid.length][];
        for (int i = 0; i < grid.length; ++i) copy[i] = grid[i].clone();
        return copy;
    }
    static class SudokuResult {
        final int count; final long nodes; final int[][] first;
        SudokuResult(int count, long nodes, int[][] first) { this.count = count; this.nodes = nodes; this.first = first; }
    }
    static SudokuResult sudoku(int[][] grid) {
        int n = grid.length;
        if (n != 4 && n != 9) throw new IllegalArgumentException("use 4x4 or 9x9");
        for (int[] row : grid) if (row.length != n) throw new IllegalArgumentException("nonsquare grid");
        int side = n == 4 ? 2 : 3, full = (1 << n) - 1;
        int[][] work = copyGrid(grid); int[] rows = new int[n], cols = new int[n], boxes = new int[n];
        for (int r = 0; r < n; ++r) for (int c = 0; c < n; ++c) {
            int value = work[r][c];
            if (value < 0 || value > n) throw new IllegalArgumentException("invalid Sudoku digit");
            if (value != 0) {
                int bit = 1 << (value - 1), box = (r / side) * side + c / side;
                if (((rows[r] | cols[c] | boxes[box]) & bit) != 0) throw new IllegalArgumentException("conflicting givens");
                rows[r] |= bit; cols[c] |= bit; boxes[box] |= bit;
            }
        }
        class Search {
            int count; long nodes; int[][] first = new int[0][];
            boolean dfs() {
                ++nodes; int br = -1, bc = -1, bx = -1, bestMask = 0, bestCount = n + 1;
                for (int r = 0; r < n; ++r) for (int c = 0; c < n; ++c) if (work[r][c] == 0) {
                    int box = (r / side) * side + c / side;
                    int mask = full & ~(rows[r] | cols[c] | boxes[box]), size = Integer.bitCount(mask);
                    if (size == 0) return false;
                    if (size < bestCount) { br = r; bc = c; bx = box; bestMask = mask; bestCount = size; }
                }
                if (br == -1) { ++count; if (count == 1) first = copyGrid(work); return count == 2; }
                while (bestMask != 0) {
                    int bit = bestMask & -bestMask; bestMask -= bit;
                    work[br][bc] = Integer.numberOfTrailingZeros(bit) + 1;
                    rows[br] |= bit; cols[bc] |= bit; boxes[bx] |= bit;
                    boolean stop = dfs();
                    rows[br] ^= bit; cols[bc] ^= bit; boxes[bx] ^= bit; work[br][bc] = 0;
                    if (stop) return true;
                }
                return false;
            }
        }
        Search search = new Search(); search.dfs();
        if (!Arrays.deepEquals(work,grid)) throw new AssertionError("undo failed");
        return new SudokuResult(search.count,search.nodes,search.first);
    }
    static class WordResult {
        final boolean found; final long nodes; final ArrayList<Integer> path;
        WordResult(boolean found, long nodes, ArrayList<Integer> path) { this.found = found; this.nodes = nodes; this.path = path; }
    }
    static WordResult wordSearch(String[] board, String word) {
        int nr = board.length, nc = nr == 0 ? 0 : board[0].length();
        if (nr > 8 || (nr != 0 && (nc < 1 || nc > 8))) throw new IllegalArgumentException("invalid board shape");
        for (String row : board) {
            if (row.length() != nc) throw new IllegalArgumentException("ragged board");
            for (char ch : row.toCharArray()) if (ch < 'A' || ch > 'Z') throw new IllegalArgumentException("invalid board letter");
        }
        if (word.length() > 16) throw new IllegalArgumentException("word too long");
        for (char ch : word.toCharArray()) if (ch < 'A' || ch > 'Z') throw new IllegalArgumentException("invalid word letter");
        if (word.isEmpty()) return new WordResult(true,0,new ArrayList<>());
        if (word.length() > nr * nc) return new WordResult(false,0,new ArrayList<>());
        int[] have = new int[26], need = new int[26];
        for (String row : board) for (char ch : row.toCharArray()) ++have[ch - 'A'];
        for (char ch : word.toCharArray()) ++need[ch - 'A'];
        for (int i = 0; i < 26; ++i) if (need[i] > have[i]) return new WordResult(false,0,new ArrayList<>());
        boolean reverse = have[word.charAt(0) - 'A'] > have[word.charAt(word.length()-1) - 'A'];
        String target = reverse ? new StringBuilder(word).reverse().toString() : word;
        boolean[][] used = new boolean[nr][nc];
        int[] dr = {-1,0,1,0}, dc = {0,1,0,-1};
        class Search {
            long nodes; ArrayList<Integer> path = new ArrayList<>(), answer = new ArrayList<>();
            boolean dfs(int r, int c, int index) {
                ++nodes; used[r][c] = true; path.add(r * nc + c);
                boolean found = index + 1 == target.length();
                if (found) answer = new ArrayList<>(path);
                else for (int d = 0; d < 4; ++d) {
                    int rr = r + dr[d], cc = c + dc[d];
                    if (rr >= 0 && rr < nr && cc >= 0 && cc < nc && !used[rr][cc] && board[rr].charAt(cc) == target.charAt(index + 1))
                        if (dfs(rr,cc,index+1)) { found = true; break; }
                }
                path.remove(path.size() - 1); used[r][c] = false; return found;
            }
            void checkUndo() {
                if (!path.isEmpty()) throw new AssertionError("path undo failed");
                for (boolean[] row : used) for (boolean mark : row) if (mark) throw new AssertionError("visited undo failed");
            }
        }
        Search search = new Search();
        for (int r = 0; r < nr; ++r) for (int c = 0; c < nc; ++c) if (board[r].charAt(c) == target.charAt(0) && search.dfs(r,c,0)) {
            if (reverse) Collections.reverse(search.answer); search.checkUndo();
            return new WordResult(true,search.nodes,search.answer);
        }
        search.checkUndo(); return new WordResult(false,search.nodes,new ArrayList<>());
    }
    static String pathText(ArrayList<Integer> path, int cols) {
        StringBuilder b = new StringBuilder("[");
        for (int i = 0; i < path.size(); ++i) { if (i > 0) b.append(','); int p = path.get(i); b.append('(').append(p / cols).append(',').append(p % cols).append(')'); }
        return b.append(']').toString();
    }
    public static void main(String[] args) {
        long[] q4 = nqueens(4,true), q8 = nqueens(8,true), full8 = nqueens(8,false);
        System.out.println("queens 4 symmetry: solutions=" + q4[0] + ", nodes=" + q4[1]);
        System.out.println("queens 8 symmetry: solutions=" + q8[0] + ", nodes=" + q8[1]);
        System.out.println("queens 8 full: solutions=" + full8[0] + ", nodes=" + full8[1]);
        String[] lines = {"530070000", "600195000", "098000060", "800060003", "400803001", "700020006", "060000280", "000419005", "000080079"};
        int[][] grid = new int[9][9];
        for (int r = 0; r < 9; ++r) for (int c = 0; c < 9; ++c) grid[r][c] = lines[r].charAt(c) - '0';
        SudokuResult solved = sudoku(grid);
        System.out.println("sudoku: solutions capped at 2=" + solved.count + ", nodes=" + solved.nodes);
        for (int[] row : solved.first) { StringBuilder b = new StringBuilder(); for (int x : row) b.append(x); System.out.println(b); }
        String[] board = {"ABCE", "SFCS", "ADEE"}; ArrayList<Boolean> results = new ArrayList<>();
        for (String word : new String[] {"ABCCED", "SEE", "ABCB"}) {
            WordResult result = wordSearch(board,word); results.add(result.found);
            System.out.println("word " + word + ": found=" + (result.found ? 1 : 0) + ", nodes=" + result.nodes + ", path=" + pathText(result.path,4));
        }
        boolean unchanged = Arrays.equals(board,new String[] {"ABCE", "SFCS", "ADEE"});
        for (int r = 0; r < 9; ++r) for (int c = 0; c < 9; ++c) unchanged = unchanged && grid[r][c] == lines[r].charAt(c) - '0';
        System.out.println("inputs unchanged = " + (unchanged ? 1 : 0));
        boolean ok = q4[0] == 2 && q8[0] == 92 && full8[0] == 92 && solved.count == 1 && results.equals(new ArrayList<>(Arrays.asList(true,true,false))) && unchanged;
        System.out.println("checks = " + (ok ? "PASS" : "FAIL"));
    }
}

Use Python 3.10 or later for int.bit_count(), compile C++ with g++ -std=c++14 -O2 main.cpp -o backtracking, or compile Java 17 or later with javac Main.java and run java Main. The programs print the same eighteen lines:

queens 4 symmetry: solutions=2, nodes=9
queens 8 symmetry: solutions=92, nodes=1029
queens 8 full: solutions=92, nodes=2057
sudoku: solutions capped at 2=1, nodes=52
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
word ABCCED: found=1, nodes=6, path=[(0,0),(0,1),(0,2),(1,2),(2,2),(2,1)]
word SEE: found=1, nodes=5, path=[(1,3),(2,3),(2,2)]
word ABCB: found=0, nodes=0, path=[]
inputs unchanged = 1
checks = PASS

Complexity, Correctness, and Invariants

Let $T$ be the number of entered search states. For N-Queens, assume the supported masks fit in one machine word. Generating one legal bit and computing child masks take constant work, so the search uses $\Theta(T)$ time and $O(n+1)$ stack space. Ignoring diagonals, depth $r$ has at most $n!/(n-r)!$ distinct-column prefixes. Therefore $T\le\sum_{r=0}^n n!/(n-r)!=O(n!)$ for $n\ge1$; diagonals and symmetry reduce the actual tree.

Write $F(c)$ for the number of solutions with first-row column $c$. For $n\ge1$, vertical reflection gives

$$Q_n=2\sum_{c=0}^{\lfloor n/2\rfloor-1}F(c)+\mathbf1_{n\text{ odd}}F(\lfloor n/2\rfloor).$$

The first-half branches have distinct reflected partners, while the center branch, when present, is already searched in full. For even $n$, the searched nonroot subtrees also pair in equal sizes, giving $T_{\mathrm{sym}}=1+(T_{\mathrm{full}}-1)/2$. This explains the sample counts without claiming a different factorial worst-case upper bound.

For Sudoku, let $S$ be the number of rows or digits per unit and $E$ the number of initial blanks. The code scans up to $S^2$ cells per node to choose MRV and detect zero domains. With word-sized masks, its time is $O(S^2T)$ and its grid, saved answer, masks, and recursion stack use $O(S^2+E)=O(S^2)$ extra space. A conservative search-tree bound is $T=O(S^E)$, giving $O(S^2S^E)$ time. This is a generalized-size analysis; the runnable solver deliberately restricts $S$ to $4$ or $9$.

For Word Search, let $B$ be the board's cell count and $\ell$ the word length. Validation and frequency checks cost $O(B+\ell)$. Each recursive entry checks at most four neighbors, so time is $O(B+\ell+T)$. After the first move, at most three directions remain because the previous cell is already visited; consequently a standard upper bound for nonempty words is $O(B3^{\ell-1})$, in addition to preprocessing. Boundaries, letter mismatches, and the no-reuse rule often reduce this greatly. The visited matrix and recursion/output paths use $O(B+\ell)$ extra space.

Approach	Time and best-case behavior	Space and assumptions
Full queen column permutations	Up to $n!$ complete arrangements before diagonal checking	Linear placement state; delaying checks wastes invalid prefixes.
Masked N-Queens count	$\Theta(T)$ actual search work; $O(n!)$ upper bound under word-sized masks	$O(n+1)$ stack; reflection roughly halves this implementation's even-size search work, while still counting every solution.
Sudoku MRV with occupancy masks	$O(S^2T)$, conservatively $O(S^2S^E)$; a completed grid or immediate contradiction takes $\Theta(S^2)$ including validation	$O(S^2)$ extra state; MRV changes decision order, and zero-domain checks prune impossible completions.
Word Search with local visited state	$O(B+\ell+T)$; frequency rejection takes $\Theta(B+\ell)$; exponential path-search upper bound remains	$O(B+\ell)$ extra space; a cell may be reused by another branch, never twice in one path.
Copy all state for each child	Search tree may be unchanged, but every edge pays the state-copy cost	Simpler isolation, with larger allocation or copying costs than a carefully maintained undo trail.
Constraint programming or exact cover	Depends on propagation, branching, encoding, and instance structure	Offers additional modeling and inference machinery; its cost must be analyzed for the chosen solver and model.

There is no universal average-case bound for backtracking without an input distribution and a precise search objective. Counting every queen placement requires exhausting the retained tree. Finding one word may stop early, while proving a Sudoku unique requires excluding all alternatives. Fewer recursive nodes can still take longer if a heuristic performs much more work at every node.

Every entered state is a legal partial assignment, every required completion extends one of its enumerated choices, and every mutation is undone before the caller resumes. N-Queens preserves this through value-passed masks and correct reflection weights; Sudoku preserves row, column, and box occupancy; Word Search preserves a path with distinct cells spelling the matched prefix. These invariants establish soundness, completeness for the stated objective, and isolation between sibling branches.

Soundness follows by extending only legal assignments. Completeness follows because legal candidates are exhausted unless the specified stopping goal has already been achieved. MRV only reorders variables. Frequency pruning is necessary rather than sufficient: having enough letters does not guarantee an adjacent path. Reflection omits paired queen branches only because their counted answers can be reconstructed by a bijection.

Undo is essential to the induction. On return, the caller must see the same grid, masks, path, and visited information it held before the child was applied. A successful path or Sudoku board must therefore be copied before restoration. Restoring only the visible grid while retaining a candidate bit or visited mark can incorrectly remove valid sibling completions.

Variants, Pitfalls, and Optimizations

A Word Search visited set belongs to the current path, not the entire run. On the board with rows AB and AC, the word ABA has enough letters, but the B at $(0,1)$ is adjacent to only one A, at $(0,0)$. Returning to that same cell would falsely accept a repeated-cell path. The other A, at $(1,0)$, is not orthogonally adjacent to the B.

Several extensions are useful once the basic invariants are tested:

Stronger Sudoku propagation: maintain candidate domains, propagate forced singles, and detect digits with only one available location in a unit. Record every domain change on an undo trail; restoring only the last placed digit is insufficient when a move updates many peers.
Additional ordering heuristics: degree heuristics break MRV ties by constraint interaction; least-constraining-value ordering tries a value that leaves more options. Both change work rather than the set of valid solutions, and their own computation has a cost.
General symmetry handling: lexicographic constraints or canonical representatives can remove rotations and other reflections. Do not multiply every representative by $8$: orbit sizes vary, and even $8$-Queens has $92$ total solutions, which is not a multiple of $8$.
Multiword search: a trie shares prefix exploration across a dictionary. It does not remove the need for path-local visited cells or correct restoration. Removing a reported word or exhausted trie branch needs its own completeness argument.
Memoization: cache only a state description that determines all legal futures. For Word Search, position and word index alone omit the used-cell set. For Sudoku, cached results also depend on the actual assignments or an equivalent complete constraint state.
Exact cover: Sudoku can be expressed through cell, row-digit, column-digit, and box-digit constraints. Algorithm X and Dancing Links offer a different reversible-search representation; the encoding and solution objective still need validation.
Counting and early stopping: a first-solution flag, a capped count, and full enumeration are different APIs. Applying a first-solution shortcut to the queen counter would lose solutions; treating the Sudoku cap as an exact count would overstate the result.
Search budgets: if work is capped, report an explicit incomplete result when exhausted. A partially explored tree does not justify “unsatisfiable” or “unique.” The programs here complete their specified searches without a node budget.

Undo all state changes before every return, including a successful one; copy answers that must survive restoration. Mask out off-board bits, keep visited cells local to the current path, and use only sound pruning conditions. Symmetry weights must preserve the requested count, and finding one completion must never be confused with proving uniqueness or exhausting all solutions.

Practice Problems and Real-World Use

Compare small N-Queens counts against an independent implementation that tests queen coordinates directly, then compare symmetry-enabled and full searches. For Sudoku, check every returned row, column, and box, preserve all givens, and test invalid clues, consistent unsatisfiable instances, unique instances, and multiple-solution instances. Exhaustive $4\times4$ solution sets make a useful independent oracle for partial grids.

For Word Search, verify every returned coordinate is in bounds, adjacent to the next coordinate, distinct, and matched to the corresponding original letter. Enumerate small boards and compare existence with a simple independent path search. Repeat queries on the same inputs, test successful early returns, and include endpoint reversal, frequency failures, and paths that require revisiting a cell only after a previous branch has been undone.

Problem or application	Idea tested	Difficulty
N-Queens counting laboratory	Bit-mask diagonals, full counts, and measured work reduction from reflection.	Intermediate
Fundamental queen placements	Canonicalization under board symmetries and correct orbit sizes.	Advanced
Sudoku uniqueness checker	MRV, zero-domain pruning, preserved givens, and counting up to two.	Intermediate
Sudoku propagation engine	Candidate domains, forced assignments, reversible trails, and consistency checks.	Advanced
Single-word grid search	Path-local visited state, letter inventory pruning, and reversible endpoint selection.	Intermediate
Dictionary grid search	Trie-guided prefix sharing while retaining the no-reuse path constraint.	Advanced
Timetabling or resource assignment	Model domains and incompatibilities; distinguish feasibility from optimization and incomplete search.	Advanced
Exact-cover model comparison	Encode constraints and compare reversible search with Algorithm X or a constraint solver.	Advanced

For further reading, see Google OR-Tools' N-Queens model, Peter Norvig's Sudoku discussion, and Donald Knuth's Dancing Links paper. These provide complementary views of constraint modeling, propagation, and reversible search; the implementations here use the explicit masks, MRV policy, and undo rules described above.

Cookie Consent