Search improvements

The order in which options are tried changes how much of the tree is visited, though not the answers. Two rules of thumb: try the **most constraining** choice first (a large item that fits few places, a vertex with many neighbours), and, for optimisation, try the **most promising** choice first so a good answer is found early and lets later bounds prune more.

Both pruned searches in this chapter rely on sorting: combination sum sorts candidates so it can break at the first overshoot, k-partition sorts values in descending order so groups overflow early, and the knapsack below sorts items by value per weight. Sorting costs O(n log n) once and can save exponential work.

1static int best;
2static void search(int[] w, int[] v, int cap, int i, int weight, int value, boolean bound) {   // items sorted by v/w, descending
3    if (i == w.length) { best = Math.max(best, value); return; }
4    if (bound && value + fractionalBound(w, v, cap - weight, i) <= best) return;         // cannot beat the best: prune
5    if (weight + w[i] <= cap)                                                             // take item i, if it fits
6        search(w, v, cap, i + 1, weight + w[i], value + v[i], bound);
7    search(w, v, cap, i + 1, weight, value, bound);                                      // skip item i
8}

For optimisation problems you do not need every solution, only the best. **Branch and bound** keeps the best value found so far and, at each node, computes an optimistic **bound** on the best value any completion could reach. If the bound cannot beat the best known value, the whole subtree is abandoned. For 0/1 knapsack, a valid bound is the fractional knapsack value of the remaining items: it relaxes the problem and is never smaller than the true answer.

With items 5:10, 4:40, 6:30, 3:50 and capacity 10, plain backtracking visits 29 nodes and finds the optimum 90; with the bound the same optimum is found after 9 nodes. The bound must be a true upper bound, otherwise a branch containing the optimum could be cut.

1static int best;
2
3static int knapsackBb(int[] w, int[] v, int cap) {            // items must be sorted by v/w, descending
4    best = 0;
5    search(w, v, cap, 0, 0, 0);
6    return best;
7}
8private static void search(int[] w, int[] v, int cap, int i, int weight, int value) {
9    if (i == w.length) { best = Math.max(best, value); return; }
10    if (value + fractionalBound(w, v, cap - weight, i) <= best) return;     // cannot beat the best: prune
11    if (weight + w[i] <= cap) search(w, v, cap, i + 1, weight + w[i], value + v[i]);   // take item i, if it fits
12    search(w, v, cap, i + 1, weight, value);                               // skip item i
13}
14private static double fractionalBound(int[] w, int[] v, int room, int from) {
15    double total = 0;
16    for (int k = from; k < w.length && room > 0; k++) {
17        int take = Math.min(room, w[k]);
18        total += (double) v[k] * take / w[k];                              // the whole item, or the part that fits
19        room -= take;
20    }
21    return total;
22}

1static int best;
2static void search(int[] w, int[] v, int cap, int i, int weight, int value, boolean bound) {   // items sorted by v/w, descending
3    if (i == w.length) { best = Math.max(best, value); return; }
4    if (bound && value + fractionalBound(w, v, cap - weight, i) <= best) return;         // cannot beat the best: prune
5    if (weight + w[i] <= cap)                                                             // take item i, if it fits
6        search(w, v, cap, i + 1, weight + w[i], value + v[i], bound);
7    search(w, v, cap, i + 1, weight, value, bound);                                      // skip item i
8}

Many search spaces contain **symmetric** branches that differ only by renaming: swapping two colours, two identical groups, the mirror image of a board. They cannot change whether a solution exists, so searching more than one of them is wasted work. Add a rule that keeps only one representative: for colouring, open **at most one new colour at a time** (colour c may be used only if colour c − 1 is already in use); for k-partition, try only the first of several identical **empty** groups.

K4 with 3 colours has no solution: the plain search visits 49 nodes, the symmetry-breaking search 12. For [4, 4, 4, 3, 3] in 3 groups of 6 the counts are 49 and 12 as well. On satisfiable inputs the saving is smaller, because the search stops at the first solution anyway.

1static boolean colorSym(int[][] adj, int v, int[] colors, int m) {    // colors[] starts filled with -1
2    if (v == adj.length) return true;
3    int maxUsed = -1; for (int c : colors) maxUsed = Math.max(maxUsed, c);
4    for (int c = 0; c < m; c++) {
5        if (c > maxUsed + 1) break;                           // colours are interchangeable: open at most one new colour
6        boolean clash = false;
7        for (int u : adj[v]) if (colors[u] == c) clash = true;
8        if (clash) continue;
9        colors[v] = c;
10        if (colorSym(adj, v + 1, colors, m)) return true;
11        colors[v] = -1;
12    }
13    return false;
14}

1static boolean color(int[][] adj, int v, int[] colors, int m, boolean symmetry) {   // colors[] starts filled with -1
2    if (v == adj.length) return true;                          // every vertex is coloured
3    int maxUsed = -1; for (int c : colors) maxUsed = Math.max(maxUsed, c);
4    for (int c = 0; c < m; c++) {
5        if (symmetry && c > maxUsed + 1) break;                // colours are interchangeable: open at most one new colour
6        if (conflict(adj, v, c, colors)) continue;             // a neighbour already has colour c
7        colors[v] = c;                                         // choose
8        if (color(adj, v + 1, colors, m, symmetry)) return true;   // explore
9        colors[v] = -1;                                        // unchoose
10    }
11    return false;
12}

Instead of waiting for a dead end, **propagate** the consequences of each decision: when a choice removes candidates from other variables, check whether any variable is now forced (exactly one candidate left) or impossible (none left). Forced moves are filled in without guessing, and an impossible variable ends the branch immediately. In Sudoku the simplest form is the *naked single*: a cell with one remaining digit.

On the 4×4 puzzle with givens 1 at the corners the first-empty-cell strategy needs 12 placements, but with forced moves only 4 placements are guesses and 8 cells are filled by propagation. Pick “Most constrained + forced moves” in the animation and watch the “Forced by propagation” cells appear before each guess.

1static boolean solve(int[][] g, int mode) {          // 0 = first empty cell, 1 = fewest candidates, 2 = fewest candidates + forced moves
2    List<int[]> forced = new ArrayList<>();
3    if (mode == 2 && !propagate(g, forced)) { undo(g, forced); return false; }   // a cell with no candidate: dead end
4    int[] cell = mode == 0 ? firstEmpty(g) : mostConstrained(g);
5    if (cell == null) return true;                    // no empty cell: solved
6    for (int v = 1; v <= 4; v++) {
7        if (!legal(g, cell[0], cell[1], v)) continue;   // row, column or box clash
8        g[cell[0]][cell[1]] = v;                        // choose
9        if (solve(g, mode)) return true;                // explore
10        g[cell[0]][cell[1]] = 0;                        // unchoose
11    }
12    undo(g, forced);
13    return false;
14}

Which variable (cell, vertex, column) should the search branch on next? The **most-constrained-variable** (also called minimum remaining values) heuristic picks the one with the fewest legal options: it is the likeliest to fail, so failure is found high in the tree, and a variable with a single option is a free move. Algorithm X (next lesson) uses exactly this rule for columns.

On a 4×4 board the difference between “First empty cell” and “Most constrained first” is invisible: both place the same 12 digits for the default puzzle, because the board is tiny. The heuristic pays off on large instances such as 9×9 Sudoku or exact cover, where choosing the wrong variable can multiply the search by orders of magnitude. The point of the animation is the strategy switch; combine it with forced moves to see the effect.

1static int[] mostConstrained(int[][] g) {                      // 9x9 Sudoku: the empty cell with the fewest candidates
2    int[] best = null; int bestCount = 10;
3    for (int r = 0; r < 9; r++)
4        for (int c = 0; c < 9; c++) {
5            if (g[r][c] != 0) continue;
6            int count = 0;
7            for (int v = 1; v <= 9; v++) if (legalDigit(g, r, c, v)) count++;
8            if (count < bestCount) { bestCount = count; best = new int[]{r, c}; }
9        }
10    return best;                                               // null when the grid is full
11}
12private static boolean legalDigit(int[][] g, int r, int c, int v) {
13    for (int k = 0; k < 9; k++) if (g[r][k] == v || g[k][c] == v) return false;
14    int br = r / 3 * 3, bc = c / 3 * 3;
15    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (g[br + i][bc + j] == v) return false;
16    return true;
17}

1static boolean solve(int[][] g, int mode) {          // 0 = first empty cell, 1 = fewest candidates, 2 = fewest candidates + forced moves
2    List<int[]> forced = new ArrayList<>();
3    if (mode == 2 && !propagate(g, forced)) { undo(g, forced); return false; }   // a cell with no candidate: dead end
4    int[] cell = mode == 0 ? firstEmpty(g) : mostConstrained(g);
5    if (cell == null) return true;                    // no empty cell: solved
6    for (int v = 1; v <= 4; v++) {
7        if (!legal(g, cell[0], cell[1], v)) continue;   // row, column or box clash
8        g[cell[0]][cell[1]] = v;                        // choose
9        if (solve(g, mode)) return true;                // explore
10        g[cell[0]][cell[1]] = 0;                        // unchoose
11    }
12    undo(g, forced);
13    return false;
14}