Backtracking: Pruning the Search Tree with Permutations, Subsets and Sudoku

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests.

Guess First

There are 92 ways to place 8 queens on an 8 × 8 chessboard so that none threatens another. We wrote two programs that find them. Both put one queen in each row and move row by row. One does no checking while placing the queens and asks "is it valid?" only after all 8 are on the board. The other abandons a branch the moment a queen is placed on a column or diagonal already occupied by another queen.

foreach (int n in new[] { 4, 6, 8 })
{
    (int solutions, long pruned) = NQueens.Solve(n, prune: true);
    (_, long brute) = NQueens.Solve(n, prune: false);
    Console.WriteLine($"n={n}: solutions={solutions}, nodes with pruning={pruned:N0}, without={brute:N0}");
}

Both find 92. But how many half-filled boards (partial placements) do they visit? For the first one you can roughly calculate it: 8 choices per row, 8 rows. What is your guess for the second: half of that, a tenth, a thousandth?

Choose, Explore, Unchoose

Backtracking is a systematic search technique that builds a solution step by step, making a choice at each step. If a choice leads to a dead end, it goes back (back-tracks), undoes the choice and tries the next one. Every backtracking algorithm fits the same three-step skeleton: choose, explore with that choice, unchoose. Generating permutations is the simplest example:

// choose -> explore -> unchoose; results are produced lazily with yield return.
public static IEnumerable<T[]> Permutations<T>(IReadOnlyList<T> items)
{
    T[] current = new T[items.Count];
    bool[] used = new bool[items.Count];
    return Build(0);

    IEnumerable<T[]> Build(int depth)
    {
        if (depth == items.Count)
        {
            yield return [.. current]; // a copy: current changes on the next step
            yield break;
        }

        for (int i = 0; i < items.Count; i++)
        {
            if (used[i]) continue;
            used[i] = true;                 // choose
            current[depth] = items[i];
            foreach (T[] p in Build(depth + 1)) yield return p; // explore
            used[i] = false;                // unchoose
        }
    }
}

ABC ACB BAC BCA CAB CBA

You can picture the search as a tree whose root is the empty choice: each level a position, each branch a choice for that position, each leaf a complete permutation. Backtracking walks this tree with DFS (Depth-First Search), but never builds the tree in memory; it keeps only the path from the root to the current node (current and used). Memory is O(n), time proportional to the number of leaves: n! permutations.

The used[i] = false line, the "unchoose", is the most easily forgotten part of the skeleton. Without it the first branch pollutes used and later branches cannot pick any element.

Subsets and Combinations

For subsets there are two choices per element: take it or leave it. The tree is binary, with 2ⁿ leaves:

public static IEnumerable<List<T>> Subsets<T>(IReadOnlyList<T> items)
{
    List<T> current = [];
    return Build(0);

    IEnumerable<List<T>> Build(int index)
    {
        if (index == items.Count)
        {
            yield return [.. current];
            yield break;
        }

        foreach (List<T> s in Build(index + 1)) yield return s; // without items[index]
        current.Add(items[index]);
        foreach (List<T> s in Build(index + 1)) yield return s; // with items[index]
        current.RemoveAt(current.Count - 1);
    }
}

A combination, choosing k of n elements without order, is the "size exactly k" part of the subsets. Here is our first pruning example: if the remaining elements are not enough to reach k, do not enter that branch at all.

public static IEnumerable<List<T>> Combinations<T>(IReadOnlyList<T> items, int k)
{
    List<T> current = [];
    return Build(0);

    IEnumerable<List<T>> Build(int start)
    {
        if (current.Count == k)
        {
            yield return [.. current];
            yield break;
        }

        // Pruning: stop when not enough items are left to reach k.
        for (int i = start; i <= items.Count - (k - current.Count); i++)
        {
            current.Add(items[i]);
            foreach (List<T> c in Build(i + 1)) yield return c;
            current.RemoveAt(current.Count - 1);
        }
    }
}

{} {C} {B} {BC} {A} {AC} {AB} {ABC}
AB AC AD BC BD CD

The start parameter separates combinations from permutations: each element pairs only with those after it, so AB and BA are not produced separately.

Lazy Generation with yield return, and Exponential Growth

All the generator methods return IEnumerable and produce results one at a time with yield return (the "C# Collection Interfaces: IEnumerable, ICollection, IList and yield return" post of the C# Collections series). The benefit is that the consumer can take as many as it wants and stop:

[Fact]
public void Permutations_IsLazy()
{
    // 12! = 479,001,600 permutations; taking 3 must return immediately.
    Assert.Equal(3, Backtracking.Permutations([.. Enumerable.Range(1, 12)]).Take(3).Count());
}

But lazy does not mean cheap. Count them all and exponential growth shows itself:

foreach (int n in new[] { 8, 9, 10, 11 })
{
    Stopwatch sw = Stopwatch.StartNew();
    long count = Backtracking.Permutations([.. Enumerable.Range(1, n)]).LongCount();
    Console.WriteLine($"permutations of {n,2}: {count,12:N0} in {sw.ElapsedMilliseconds,6:N0} ms");
}

permutations of  8:       40,320 in     25 ms
permutations of  9:      362,880 in    188 ms
permutations of 10:    3,628,800 in    345 ms
permutations of 11:   39,916,800 in  4,282 ms

Each extra element multiplies the time by roughly n; at this rate 12 elements take about a minute and 13 more than ten minutes (not measured, an estimate). Nested yield return has a cost too: each result travels out through as many iterator layers as the recursion depth, which is O(n) extra work per element. Lazy generation is readable and memory friendly, but if you need millions of results in a hot loop, an implementation that hands results to a callback or mutates a single array in place is noticeably faster. The language of these growth rates is the O(2ⁿ) and O(n!) classes from the "What Is Big-O Notation" post of the Big-O and Complexity series.

Pruning: N-Queens

Pruning means cutting a branch that certainly cannot lead to a solution, before opening it. That is what separates backtracking from brute force. In N-Queens we put one queen in each row; we track columns and the diagonals in both directions with a bool[] each, so "is this square under attack?" is O(1):

// Counts solutions; nodes = how many partial boards were visited.
public static (int Solutions, long Nodes) Solve(int n, bool prune)
{
    int[] queenCol = new int[n];
    bool[] cols = new bool[n], diag = new bool[2 * n], anti = new bool[2 * n];
    int solutions = 0;
    long nodes = 0;
    Place(0);
    return (solutions, nodes);

    void Place(int row)
    {
        nodes++;
        if (row == n)
        {
            if (prune || IsValid()) solutions++;
            return;
        }

        for (int c = 0; c < n; c++)
        {
            if (prune && (cols[c] || diag[row + c] || anti[row - c + n]))
            {
                continue; // this branch can never lead to a solution
            }

            queenCol[row] = c;
            cols[c] = diag[row + c] = anti[row - c + n] = true;
            Place(row + 1);
            cols[c] = diag[row + c] = anti[row - c + n] = false;
        }
    }

    bool IsValid()
    {
        for (int a = 0; a < n; a++)
            for (int b = a + 1; b < n; b++)
                if (queenCol[a] == queenCol[b] || Math.Abs(queenCol[a] - queenCol[b]) == b - a)
                    return false;
        return true;
    }
}

On the same diagonal, row + c (top right to bottom left) or row - c (top left to bottom right) is constant; the + n avoids a negative index. With prune: false the same code tries every placement without any check and validates at the end. The answer to the opening question:

n=4: solutions=2, nodes with pruning=17, without=341
n=6: solutions=4, nodes with pruning=153, without=55,987
n=8: solutions=92, nodes with pruning=2,057, without=19,173,961

With 8 queens pruning cuts 19 million nodes down to 2,057: about 9,300 times fewer. A single continue skips the whole subtree below a half-filled board with two queens on a diagonal (with a conflict in the 2nd row, 8⁶ = 262,144 leaves). The complete pruned tree for the 4-queen board:

A Sudoku Solver: Start with the Most Constrained Cell

Sudoku fits the same skeleton: pick an empty cell, try a digit that can go there, continue, undo if you hit a dead end. A second pruning technique comes into play here: which cell you pick. If instead of the first empty cell we pick the cell with the fewest candidate digits (most constrained first), single-candidate cells fill without guessing and a cell with zero candidates reports the dead end immediately:

// grid: 81 digits, 0 = empty. Solves in place; guesses counts placements tried.
public static bool Solve(int[] grid, out long guesses, bool mostConstrainedFirst = true)
{
    long count = 0;
    // Reject conflicting givens up front; the search would only discover it after a long walk.
    for (int i = 0; i < 81; i++)
    {
        int given = grid[i];
        if (given == 0) continue;
        grid[i] = 0;
        bool ok = CanPlace(i, given);
        grid[i] = given;
        if (!ok)
        {
            guesses = 0;
            return false;
        }
    }

    bool solved = Fill();
    guesses = count;
    return solved;

    bool Fill()
    {
        // Pick the empty cell with the fewest candidates (most constrained first),
        // or simply the first empty cell.
        int best = -1, bestCount = 10;
        for (int i = 0; i < 81 && bestCount > 1; i++)
        {
            if (grid[i] != 0) continue;
            int candidates = 0;
            for (int d = 1; d <= 9; d++) if (CanPlace(i, d)) candidates++;
            if (candidates < bestCount) (best, bestCount) = (i, candidates);
            if (!mostConstrainedFirst) break;
        }

        if (best == -1) return true;      // no empty cell left
        if (bestCount == 0) return false; // dead end: prune

        for (int d = 1; d <= 9; d++)
        {
            if (!CanPlace(best, d)) continue;
            grid[best] = d;
            count++;
            if (Fill()) return true;
            grid[best] = 0;                // undo
        }

        return false;
    }

    bool CanPlace(int index, int digit)
    {
        int row = index / 9, col = index % 9;
        int boxRow = row / 3 * 3, boxCol = col / 3 * 3;
        for (int k = 0; k < 9; k++)
        {
            if (grid[row * 9 + k] == digit || grid[k * 9 + col] == digit) return false;
            if (grid[(boxRow + k / 3) * 9 + boxCol + k % 3] == digit) return false;
        }

        return true;
    }
}

With the example puzzle from Wikipedia's Sudoku article (51 empty cells):

first empty cell: placements tried=4208
sudoku solved=True, placements tried=51
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

The version that starts from the first empty cell tries 4,208 placements. The version that picks the most constrained cell fills the 51 empty cells with exactly 51 placements: in this puzzle there is a single-candidate cell at every step and the search never backtracks. Scanning 81 cells at every step to find the most constrained one looks expensive, but the gain from shrinking the tree more than pays for it. Rejecting conflicting givens up front is pruning too: in the test, a board with two 1s in its first row did not finish within two minutes without this check, and I had to stop the test run.

A Real Scenario: A Product Configurator

The Bookstore sells books with options: edition (hardcover, paperback, e-book), language (EN, TR), gift wrap and a signature. The options have rules between them and the customer has a budget. The sales page wants to list "the valid bundles you can buy with this budget":

public sealed record BundleOption(string Slot, string Value, decimal Price);

public static class BundleConfigurator
{
    // One option per slot; rules reject a partial bundle as early as possible.
    public static IEnumerable<BundleOption[]> Valid(
        IReadOnlyList<BundleOption[]> slots,
        Func<IReadOnlyList<BundleOption>, bool> isAllowed,
        decimal budget)
    {
        List<BundleOption> chosen = [];
        return Build(0, 0m);

        IEnumerable<BundleOption[]> Build(int slot, decimal total)
        {
            if (slot == slots.Count)
            {
                yield return [.. chosen];
                yield break;
            }

            foreach (BundleOption option in slots[slot])
            {
                if (total + option.Price > budget) continue; // prune: over budget
                chosen.Add(option);
                if (isAllowed(chosen))                       // prune: rule violated
                {
                    foreach (BundleOption[] bundle in Build(slot + 1, total + option.Price))
                    {
                        yield return bundle;
                    }
                }

                chosen.RemoveAt(chosen.Count - 1);
            }
        }
    }
}

BundleOption[][] slots =
[
    [new("Format", "Hardcover", 450m), new("Format", "Paperback", 280m), new("Format", "Ebook", 190m)],
    [new("Language", "EN", 0m), new("Language", "TR", 0m)],
    [new("Wrap", "GiftWrap", 40m), new("Wrap", "NoWrap", 0m)],
    [new("Signature", "Signed", 120m), new("Signature", "Unsigned", 0m)],
];

bool Allowed(IReadOnlyList<BundleOption> c)
{
    bool Has(string v) => c.Any(o => o.Value == v);
    if (Has("Ebook") && (Has("GiftWrap") || Has("Signed"))) return false;   // nothing physical on an ebook
    if (Has("TR") && Has("Hardcover")) return false;                       // TR edition: no hardcover
    if (Has("Signed") && !Has("Hardcover")) return false;                  // signed copies are hardcover only
    return true;
}

List<BundleOption[]> bundles = [.. BundleConfigurator.Valid(slots, Allowed, budget: 600m)];

Hardcover + EN + GiftWrap + Unsigned        490
Hardcover + EN + NoWrap + Signed            570
Hardcover + EN + NoWrap + Unsigned          450
Paperback + EN + GiftWrap + Unsigned        320
Paperback + EN + NoWrap + Unsigned          280
Paperback + TR + GiftWrap + Unsigned        320
Paperback + TR + NoWrap + Unsigned          280
Ebook + EN + NoWrap + Unsigned              190
Ebook + TR + NoWrap + Unsigned              190
valid bundles=9 of 24 combinations

9 of 24 combinations are valid. What matters is that the rule runs on a partial bundle: Hardcover + TR is rejected at the second slot, so the 4 combinations below it are never generated; a hardcover, gift-wrapped and signed bundle is cut the moment it exceeds the budget at 610. That is why rules must be written with the discipline of "assume nothing about slots not chosen yet": the Has("Signed") && !Has("Hardcover") rule works correctly on a partial bundle thanks to the ordering (format is always the first slot); if the slot order changes, the rule may reject early and wrongly. The backtracking tests:

Test run summary: Passed!
  total: 12
  failed: 0
  succeeded: 12
  skipped: 0
  duration: 300ms

Production Notes

Set a limit. A backtracking search driven by user input (if the number of slots and options in the configurator can be increased from an admin panel) will hit the exponential wall one day. Add an upper bound on the number of results (Take(100)), a CancellationToken or a time limit to the search; an endpoint pinning a CPU (Central Processing Unit) core for 30 seconds is a service incident.

Estimate the scale from real data, not test data. With 4 slots and 2-3 options everything runs instantly; 15 slots with 5 options means 5¹⁵ ≈ 30 billion combinations. Putting a node counter (like nodes in N-Queens) into production logs is a cheap and instructive way to know how much pruning actually cuts.

Where backtracking is not enough. If the constraints are many and complex (class timetables, shift planning, warehouse slotting), using a constraint solver or an integer programming tool instead of writing your own backtracking is often the right call. These tools also run a pruned search internally, but with much stronger techniques such as constraint propagation.

Shared state and threads. current, used and chosen are shared mutable state; consuming the iterator from two threads at the same time, or storing results without copying them, corrupts the results. That is why every yield return [.. current] returns a copy.

Common Pitfalls

Not noticing the exponential cost on small test inputs. The permutations of 8 elements take 25 ms and the test is green; 11 elements took 4 seconds, and 13 would take more than ten minutes by estimate. Measure with a few different sizes in tests to see the growth rate.

Forgetting to undo state. If used[i] = false or chosen.RemoveAt(...) is missing, the first branch poisons the later ones; the result comes out incomplete and the bug throws no exception. Deleting the grid[best] = 0 line in Sudoku makes a solvable puzzle "unsolvable".

Returning the result without copying. If you write yield return current;, the consumer gets the same array reference every time; all permutations collected with ToList() show the last value.

Pruning in the wrong place. If the constraint check is postponed to the leaf (the complete solution), the code is correct but as slow as brute force; the 19 million versus 2,057 difference in N-Queens comes entirely from where the check is. Check at the moment the choice is made.

A Small Experiment

★☆☆ Using Combinations, find the sets of 3 books from a Bookstore list of 6 whose total price is exactly 100. Then do the same while pruning branches that exceed the total, and compare the number of nodes visited.

★★☆ Rewrite Permutations to take an Action<T[]> callback instead of using yield return, and time both versions with 10 elements. Where does the difference come from?

★★★ In N-Queens track columns and diagonals with three int bit masks instead of bool[] (free columns are ~(cols | diag | anti)). For n = 12 compare the solution count (14,200) and the time of the two versions.

Backtracking tries every option and prunes the hopeless ones. The next post has the opposite strategy: at every step make the choice that looks best right now and never go back. Greedy algorithms sometimes work surprisingly well and sometimes silently give the wrong answer; we will see how to tell the two apart.