Advanced Algorithms · Lecture Notes
Chapter 4: Backtracking
For some problems no fast, exact algorithm is known. Placing eight queens on a board so that none attacks another, filling in a Sudoku, and coloring a map with three colors are all of this kind. For such problems a solution is found by trying choices. Backtracking is a method for organizing that search. The solution is built step by step; as soon as a step breaks a rule, the last decision is undone and the next option is tried. These notes first explain how hard problems are classified. They then develop the general template of backtracking, the state-space tree, and pruning through maze and permutation examples. The n-queens problem is treated in detail with Java code and a line-by-line trace, and the min-conflicts heuristic approaches the same problem in a completely different way. Sudoku, graph coloring, Hamiltonian paths, word search, and subset sum are further applications of the template. The notes end with the complexity analysis, heuristics that strengthen pruning, and a comparison of backtracking with the other design methods.
Learning outcomes
- Concepts
- Explain backtracking in terms of partial solutions, candidates, constraints, and pruning; draw the state-space tree of a small problem; tell the classes P, NP, NP-hard, and NP-complete apart.
- Template
- Write the recursive “choose → explore → unchoose” template in Java and adapt it to a new problem. Distinguish the version that stops at one solution from the version that counts all solutions.
- Applications
- Solve the n-queens, Sudoku, maze, graph coloring, Hamiltonian path, word search, and subset sum problems step by step and trace their code.
- Analysis
- Show why the worst case is exponential; evaluate with numbers the effect of pruning, of an O(1) constraint test, and of heuristics such as MRV and min-conflicts.
4.1Hard problems: P, NP, and NP-hard
Most of the algorithms seen so far in the course are fast. Merge sort sorts an array in O(n log n) time. Dijkstra's algorithm finds shortest paths, and Kruskal's algorithm finds a minimum spanning tree, in polynomial time. But not every problem is so well behaved. Is there a path that passes through every vertex of a graph exactly once? Can the countries of a map be colored with three colors so that neighboring countries get different colors? For both questions, no polynomial-time algorithm has ever been found, and none has been proved impossible. Backtracking is a search method developed for problems of this kind. To see why it is needed, it helps first to look briefly at the classes of problem difficulty.
4.1.1Decision problems and polynomial time
Complexity classes are usually defined in terms of decision problems, whose answer is only “yes” or “no.” “Does this graph contain a Hamiltonian path?” is a decision problem. “What is the length of the shortest Hamiltonian tour in this graph?” is an optimization problem. An optimization problem can often be turned into a decision problem: “Is there a tour of length at most 100?” If the decision version could be solved quickly, binary search on the threshold would also yield the optimal value. The hardness of the decision version therefore says something about the hardness of the optimization version too.
An algorithm runs in polynomial time if its running time is O(nk) for some constant k, where n is the input size. O(n), O(n log n), and O(n3) are polynomial; O(2n) and O(n!) are not. The difference is barely visible on small inputs, but a chasm opens as the input grows. For n = 60, n3 = 216,000 operations take a computer an instant, whereas 260 ≈ 1.15 · 1018 operations take more than thirty years on a machine doing a billion operations per second. That is why polynomial time is taken to mean “solvable in practice.”
4.1.2P and NP
P is the class of decision problems that can be solved in polynomial time. NP is the class of decision problems for which a proposed solution can be verified in polynomial time. When the answer is “yes,” there is a witness, also called a certificate, that shows it, and the correctness of the witness can be checked in polynomial time.
Two examples from P are two weighted-graph questions: “Is there a path from s to t of length at most 50?” and “Is there a spanning tree of weight at most 30?” Dijkstra's algorithm answers the first and Kruskal's algorithm the second in polynomial time.
The definition of NP is about checking, not solving. The Hamiltonian path problem is a good example. Finding a Hamiltonian path in a graph is hard. But if someone proposes an ordering of the vertices, checking that the ordering contains every vertex once and that consecutive vertices are adjacent takes O(n) steps. Sudoku is of the same kind. Checking a filled-in grid is easy: each row, column, and box is scanned once. Filling in an empty grid requires search.
A problem that can be solved in polynomial time can also be verified in polynomial time: the verifier can ignore the proposed witness and solve the problem from scratch. So P lies inside NP. The real question goes the other way: is every problem that is easy to verify also easy to solve? This is known as the P = NP question, and it is the most important open problem in computer science. Most researchers believe that P ≠ NP, but this has not been proved.
4.1.3Reductions, NP-hard, and NP-complete
The tool for comparing the difficulty of two problems is the reduction. If every instance of problem A can be transformed in polynomial time into an instance of problem B, and the two instances have the same answer, then A reduces to B. In that case a fast algorithm for B also solves A quickly: transform first, then run B's algorithm. So B is at least as hard as A.
A problem B is NP-hard if every problem in NP can be reduced to B in polynomial time. If B is both in NP and NP-hard, it is NP-complete. An NP-hard problem is at least as hard as the hardest problems in NP; it need not itself be in NP.
NP-complete problems are the “hardest” members of NP. If one of them could be solved in polynomial time, then by the reductions every problem in NP could be solved in polynomial time, and P = NP would hold. The first NP-complete problem is Boolean satisfiability (SAT): given a formula built from Boolean variables, is there an assignment of values that makes it true? 3-SAT, a restricted form of SAT, is also NP-complete. Hamiltonian path and Hamiltonian cycle, graph 3-coloring, and the decision version of subset sum are likewise among the NP-complete problems.
The optimization versions of the traveling salesman problem (TSP) and of the knapsack problem, on the other hand, are NP-hard. These versions are not decision problems; they return a number or a tour. Checking that a proposed tour is the shortest one is not easy either. So they are not counted as being in NP, but because their decision versions are NP-complete, they are at least that hard.
The picture in Figure 4.1 rests on an assumption. If P = NP held, the regions P, NP, and NP-complete would coincide (apart from a few trivial exceptions). The distinction the picture shows is the common belief, not our current knowledge.
| Problem | Version | Class |
|---|---|---|
| Shortest path, minimum spanning tree | decision | P |
| SAT, 3-SAT | decision | NP-complete |
| Hamiltonian path, Hamiltonian cycle | decision | NP-complete |
| Graph 3-coloring | decision | NP-complete |
| Subset sum | decision | NP-complete |
| Traveling salesman, 0/1 knapsack | optimization | NP-hard |
4.1.4What can be done about exact solutions?
If P ≠ NP, there is no polynomial-time exact algorithm for NP-complete and NP-hard problems. Three routes remain.
- Exponential but clever search. If an exact solution is required, the possible solutions are searched. The search space is exponential, but it is often enough to visit a small part of it. The aim is to discard early the parts that are seen to be hopeless. This is called pruning. Backtracking and branch and bound follow this route.
- Approximate solutions. If polynomial time is required, the best solution is given up. Approximation algorithms produce a solution that is within a provable ratio of the optimum.
- Heuristic search. Methods are used that give no guarantee but often work well in practice. The min-conflicts heuristic is of this kind.
The subject of these notes is the first route. In the worst case backtracking takes exponential time. But with good pruning it solves most of the instances met in practice in reasonable time. The n-queens problem shows the difference in numbers: for 8 queens, instead of trying all 16.7 million complete placements one by one, it is enough to generate only 2056 partial placements.
4.2The basic idea of backtracking
4.2.1Trying and turning back
To solve a problem it is sometimes necessary to try different paths and to turn back from wrong ones. Someone who has forgotten the three-digit code of a padlock tries every combination in turn. Someone solving a puzzle writes a digit in a cell, runs into a contradiction a few steps later, erases the digit, and tries another. Backtracking turns this intuitive behavior into a systematic algorithm.
Backtracking is a search method that builds a solution step by step as a partial solution. At each step a candidate is added to the partial solution. If the added candidate violates the constraints of the problem, that path is abandoned. If the partial solution is complete, a solution has been found. If no candidate is left to try at some step, the last decision is undone and the next candidate of the previous step is tried.
The four terms in the definition recur throughout these notes. The partial solution is the choices made so far: the queens already placed in the first few rows in n-queens, the filled cells in Sudoku. A candidate is a choice that can be made at the next step: one of the columns of the next row, one of the digits 1–9 that can be written in an empty cell. A constraint is a rule that a valid solution must obey: no two queens attack each other, no digit appears twice in a row. Undoing means removing the most recently added candidate and restoring the previous state.
This is what separates backtracking from brute force. Brute force generates all complete candidate solutions and tests each one afterward. Backtracking stops as soon as a partial solution becomes invalid. No extension of an invalid partial solution is ever generated. If the first two queens attack each other, no placement of the remaining six queens can repair that mistake. Brute force tries all 86 = 262,144 placements of these six queens one by one; backtracking tries none of them.
4.2.2The traveler in the maze
A backtracking algorithm can be compared to a traveler looking for a way through a maze. At every junction the traveler makes a decision and enters a corridor. If the corridor leads to the exit, the job is done. If it ends in a dead end, the traveler returns to the last junction and tries a corridor not yet tried. If all the corridors at that junction are dead ends, the traveler goes back to the previous junction. This trial and error continues until the exit is found or all options are exhausted.
The analogy also shows the most important requirement of the algorithm. To be able to turn back, one must remember where one came from. The traveler leaves a mark at each junction or writes the junctions entered in a list. In backtracking algorithms, recursion provides this list automatically. Each recursive call is a junction. The frames stacked on the call stack are the list of junctions that have been entered but not yet finished. When a call ends with return, control goes back to the previous frame. That is the traveler returning to the previous junction.
The maze example has the structure common to artificial intelligence and puzzle problems. In Sudoku every empty cell is a junction and the digits that can be written are corridors. In chess every move is a junction. In all of them the same question is asked: is it possible to continue with this decision, and if not, which decision should we return to?
4.2.3Backtracking in the maze, step by step
The maze is a 5 × 5 grid. Cells are written as (row, column) pairs; the start is cell (0, 0) and the exit is cell (4, 4). The gray cells are walls: (1, 1), (1, 2), (1, 3), (2, 3), (3, 0), (3, 1), (3, 3), and (4, 3). In every cell the algorithm tries the four directions in a fixed order: down, right, up, left. Every visited cell is marked, so that no cell is entered twice. Without the marks the traveler could go back and forth between two cells forever.
The search proceeds as follows. From the start, two steps down are taken: (1, 0), (2, 0). Since (3, 0) is a wall, the down direction is closed, and the next direction, right, is tried. Two steps to the right reach (2, 1) and (2, 2). Cell (2, 2) is a junction: below it is open, while its right, (2, 3), and its top, (1, 2), are walls. Down is tried first: (3, 2), (4, 2). Below (4, 2) is outside the grid and to its right, (4, 3), is a wall, so we turn left: (4, 1), (4, 0). In cell (4, 0) all four directions are closed: below and left are the boundary, above is a wall, and to the right is a visited cell. This is a dead end.
Now the return begins. Cells (4, 0), (4, 1), (4, 2), and (3, 2) are removed from the path, because they have no untried open direction. We are back at junction (2, 2). The remaining directions of this junction are closed as well: right and up are walls, and left is visited. The return continues: (2, 2), (2, 1), (2, 0), and (1, 0) are also left behind as dead ends. Finally we are back at the start. At the start the down direction is exhausted; the next direction, right, is tried.
We go right along the top corridor: (0, 1), (0, 2), (0, 3), (0, 4). Below (0, 1), (0, 2), and (0, 3) there are walls; below (0, 4) it is open. Through (1, 4), (2, 4), (3, 4) we reach the exit, (4, 4).
Question. How many different simple paths lead from the start to the exit in the maze? (In a simple path a cell is used at most once.) If the direction order were “right, down, up, left,” how many cells would the search mark as dead ends?
Solution. The lower-left region, that is, cells (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), and (4, 0)–(4, 2), is connected to the rest of the maze only through the start. Because (2, 3), (3, 3), (4, 3), and (1, 2) are walls, there is no way from this region to the right-hand column. The only connection to the exit is the top corridor and the right-hand column. So there is only 1 simple path: the 9-cell orange path. With a direction order starting with right, the first direction tried at the start would be the top corridor. At every cell the search goes right first and reaches (0, 4). There the right direction is outside the grid; it goes down and follows the right-hand column to the exit. The search never enters a dead end: 0 cells are marked as dead ends. In the same maze, the direction order reduces the cost of the search from 8 dead-end cells to 0. Which option is tried first is an important decision that determines the speed of backtracking.
4.2.4The state-space tree
It helps to think of the search done by backtracking as taking place on a tree. At the root no choice has been made yet. The children of the root are the options for the first choice. The children of each child are the options for the second choice, and so on. This tree is called the state-space tree.
The state-space tree is a rooted tree in which partial solutions are the nodes and choices are the edges. The root is the empty partial solution. The path from the root to a node is the choices made so far. The children of a node are the choices that can be made at the next level. The leaves are either complete solutions or partial solutions that cannot be extended.
Figure 4.8 shows the terms of the definition together. A partial solution is a path from the root to a node: the node x₁ = b, x₂ = c is the partial solution (b, c). The candidates are the children of a node. If a constraint is violated, the subtree of the node is pruned: the partial solution (a, a) is invalid and no node below it is generated. The goal test asks whether a complete and valid solution has been reached; in this tree (b, c, a) is a leaf and a solution.
Two properties of the tree are important. First, the tree is not built in advance. The algorithm keeps in memory only the node it is currently at and the path to the root. The tree is generated as it is traversed, and the branches already visited are forgotten. Second, the traversal order is depth-first (DFS). The algorithm goes down a branch to the bottom. When the branch ends or is pruned, it climbs to the parent and moves on to the next child. Backtracking is a depth-first search of the state-space tree. The only difference is that the subtrees of invalid nodes are never generated.
Taking the state-space tree to be a data structure built in memory. The tree is only a model for thinking about the search. At any moment memory holds only the single path from the root to the current node. In n-queens this path has at most n nodes, whereas the tree itself may contain thousands of nodes.
4.2.5The general template: choose, explore, unchoose
Almost all backtracking algorithms are written with the same skeleton. The skeleton is a recursive method. The method takes a partial solution, checks whether it is a complete solution, and if not, tries each candidate in turn.
void backtrack(State partial) {
if (isSolution(partial)) {
save(partial);
return;
}
for (Candidate c : candidates(partial)) {
if (isValid(partial, c)) {
choose(partial, c); // choose
backtrack(partial); // explore
unchoose(partial, c); // unchoose
}
}
}The code has four parts.
- Goal test.
isSolution(partial)checks whether the partial solution is complete. If it is, the solution is saved and the method returns. If a single solution is enough, the search can be stopped completely here. - Choose.
candidates(partial)gives the options for the next step. A valid candidate is added to the partial solution withchoose(partial, c). - Explore.
backtrack(partial)descends one level by recursion. This call traverses the entire subtree below the added candidate. - Unchoose. When the call returns,
unchoose(partial, c)removes the candidate from the partial solution. The state returns to what it was before the call, and the loop continues with the next candidate.
Pruning happens inside isValid. For an invalid candidate the recursive call is never made. In this way the whole subtree below that candidate is skipped with a single if. The power of pruning comes from here: one check eliminates a subtree of possibly thousands of nodes.
To see why the undo step is essential, look at how the partial solution is stored. partial is a single object shared by all calls: a board, an array, or a list. Every call modifies this object. When a call returns, the object stays in the state the call left it in. If this change is not erased before the next candidate is tried, the new candidate is tested together with the leftovers of the old one. Primitive parameters passed by value, such as an int sum or an index, return to their old values on their own, because each call has its own copy.
If a single solution is enough, the template returns a boolean with a small change. The goal test returns true. If the recursive call returns true, the caller also returns true at once. So when the first solution is found, all the calls end in turn. The n-queens, Sudoku, graph coloring, and Hamiltonian path code is of this form.
4.2.6Applying the template: permutations
The cleanest application of the template is generating all permutations of a set. Every ordering of the numbers 1, 2, and 3 is a permutation. The partial solution is the numbers written in the first k positions. A candidate is a number not yet used. There is a single constraint: a number cannot be used twice.
void permute(int[] p, boolean[] used, int k) {
if (k == p.length) { // solution
System.out.println(Arrays.toString(p));
return;
}
for (int a = 1; a <= p.length; a++) {
if (!used[a]) { // valid
p[k] = a; used[a] = true; // choose
permute(p, used, k + 1); // explore
used[a] = false; // unchoose
}
}
}The array p holds the partial solution; p[0..k−1] is filled. The array used records which numbers have been used. Its length is n + 1, because the numbers start at 1 and used[0] stays empty. k == p.length is the goal test: if all positions are filled, the permutation is printed. The loop tries every number from 1 to n. !used[a] is the validity test. If the number is unused, it is written to p[k] and marked (choose). The recursive call fills the next position (explore). When the call returns, the mark is removed (unchoose).
The unchoose line contains only used[a] = false; p[k] is not reset. The reason is that p[k] will be overwritten by the next candidate anyway. The validity test looks at used, not at p. So the old value in p[k] influences no decision. The structure that checks the constraint, however, must always be undone.
k = 0 the candidate 1 has been chosen. The dashed nodes have not been generated yet.| Step | k | Action | p | Used | Output |
|---|---|---|---|---|---|
| 1 | 0 | a = 1 is chosen | [1, –, –] | {1} | |
| 2 | 1 | a = 1 is used; a = 2 is chosen | [1, 2, –] | {1, 2} | |
| 3 | 2 | only 3 is unused; it is chosen | [1, 2, 3] | {1, 2, 3} | |
| 4 | 3 | k == p.length: solution | [1, 2, 3] | {1, 2, 3} | [1, 2, 3] |
| 5 | 1 | 3 and 2 are undone; a = 3 is chosen | [1, 3, 3] | {1, 3} | |
| 6 | 2 | only 2 is unused; it is chosen | [1, 3, 2] | {1, 2, 3} | |
| 7 | 3 | solution | [1, 3, 2] | {1, 2, 3} | [1, 3, 2] |
| 8 | 0 | 2, 3, 1 are undone; a = 2 is chosen | [2, 3, 2] | {2} | |
| 9 | 1–3 | a = 1, then 3 | [2, 1, 3] | {1, 2, 3} | [2, 1, 3] |
| 10 | 1–3 | undo; a = 3, then 1 | [2, 3, 1] | {1, 2, 3} | [2, 3, 1] |
| 11 | 0–3 | the branch starting with 3 proceeds the same way | [3, 1, 2], [3, 2, 1] | — | [3, 1, 2], [3, 2, 1] |
The value of p in step 5 deserves attention: [1, 3, 3]. p[2] still holds the 3 left over from the previous permutation. This value breaks nothing, because we are at k = 1 and p[2] is not yet part of the partial solution. In step 6 a 2 is written over it. The output of the program is:
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]Because the candidates are tried from smallest to largest, the permutations come out in lexicographic order. This observation holds for all backtracking algorithms: solutions are found in the same order in which the candidates are tried.
Question. For n = 3, how many nodes does the state-space tree have, counting the root? How many times is “choose” done, and how many times “unchoose”? How are the same questions answered for n = 4?
Solution. It is enough to count the levels separately. At the root there is 1 node. At the first level there are 3 options, at the second level 2 options remain under each of them, and at the third level 1 option. The number of nodes is 1 + 3 + 3 · 2 + 3 · 2 · 1 = 1 + 3 + 6 + 6 = 16. Every node other than the root is a “choose” operation, and every choose has an “unchoose”: 15 chooses and 15 unchooses. The number of leaves is 3! = 6. For n = 4 the nodes number 1 + 4 + 12 + 24 + 24 = 65; there are 64 chooses, 64 unchooses, and 24 leaves.
In general, the permutation tree of n items has n · (n − 1) · … · (n − k + 1) = n!/(n − k)! nodes at level k. The last two levels have equal numbers of nodes (n!), and the total is a small constant multiple of n! (close to e · n!). Printing a permutation at each leaf takes O(n). So generating all permutations takes O(n · n!) time. Here pruning does not reduce the work, because all the leaves are solutions anyway. What pruning gains is that the branches that violate the constraint are never opened: in an unpruned tree that allowed the same number to be chosen again, there would be 44 = 256 leaves for n = 4.
Adding the partial solution itself to the list when collecting all permutations. If results.add(path) were written in the code below, the reference to the same object would be added to the list six times. Because path will be empty when the search ends, the list would consist of six empty lists. The right thing is to store a copy at the moment of the solution.
List<List<Integer>> results = new ArrayList<>();
void collect(List<Integer> path, boolean[] used, int n) {
if (path.size() == n) {
results.add(new ArrayList<>(path)); // store a copy
return;
}
for (int v = 1; v <= n; v++) {
if (!used[v]) {
used[v] = true; path.add(v); // choose
collect(path, used, n); // explore
path.remove(path.size() - 1); // unchoose
used[v] = false;
}
}
}This version keeps the partial solution in a List. The choose step appends to the list, and the unchoose step deletes the last element. new ArrayList<>(path) is an independent copy of the current contents; later changes do not affect the copy. After the call collect(new ArrayList<>(), new boolean[4], 3), results holds the six permutations in lexicographic order.
4.2.7Brute force and pruning
How much work pruning saves can be shown numerically with the 8-queens problem. The problem is this: place 8 queens on an 8 × 8 chessboard so that no two attack each other. There are several ways to solve it, and each examines a different number of candidates.
| Approach | Candidates examined | Explanation |
|---|---|---|
| Choose 8 of the 64 squares | 4,426,165,368 | C(64, 8): generate every placement, then test it |
| One queen per row | 16,777,216 | 88 complete placements |
| One queen per row, distinct columns | 40,320 | 8! permutations |
| Backtracking, all solutions | 2056 | number of safe placements (92 solutions) |
| Backtracking, first solution | 113 | safe placements; 105 undone |
The first three rows of the table are increasingly clever versions of brute force. The first row is the purest approach: there are C(64, 8) = 4,426,165,368 ways to choose 8 of the 64 squares. The second row uses an observation: there must be exactly one queen in each row, because two queens in the same row attack each other. The queen in each row has 8 column choices, which leaves 88 = 16,777,216 placements. The third row applies the same logic to columns: the columns must be distinct as well. A placement is then a permutation of the columns, and 8! = 40,320 candidates remain. What these three approaches have in common is that every candidate is a complete placement that is tested only at the end.
Backtracking, on the other hand, generates not complete placements but partial ones. The queens are placed row by row. If a queen conflicts with one of the earlier ones, no extension of that partial placement is ever tried. The result is striking: to find all 92 solutions only 2056 safe placements are made. The first solution is found in 113 placements. Compared with the 88 complete placements, even finding all the solutions takes about 16,777,216 / 2056 ≈ 8160 times less work.
Pruning does not change the worst case; backtracking is still an exponential algorithm. In practice, though, only a very small part of the state-space tree is visited. The power of pruning depends on how early the constraint is checked. The constraint must be checked on the partial solution, at every new candidate. A check left to the end is no different from brute force.
4.2.8Strengths and weaknesses
The strengths of backtracking come from its generality.
- Wide range of application. It applies to any problem whose solution can be expressed as a sequence of choices. The same template is used unchanged from permutation generation to Sudoku.
- Often efficient. For problems whose constraints can be checked early, most of the tree is pruned.
- Short, readable code. The algorithm is a recursive method a few lines long.
- Exhaustive search. Backtracking finds all solutions or shows with certainty that none exists. If the search traverses the whole tree and finds nothing, there is no solution. This property is called completeness.
The weaknesses are just as clear.
- Exponential worst case. The time complexity is bounded by exponential functions such as 2n, n!, or 9m.
- Slow on large search spaces. When the number of possible solutions is very large, good pruning and heuristics are needed.
- Stack memory. Deep recursion uses one frame per level: O(depth) memory. In very deep searches the Java stack can overflow.
- Repeated work. The same subproblem may be solved again and again along different paths. Dynamic programming stores these results in a table; backtracking does not.
4.3The n-queens problem
4.3.1The problem
In chess the queen is the most powerful piece. It can move any number of squares along its row, its column, and both diagonals, and it attacks every piece on these four lines. The eight queens problem is an old puzzle posed in a chess magazine in 1848: can 8 queens be placed on an 8 × 8 board so that no queen attacks another?
The n-queens problem: n queens are placed on an n × n board. No two queens may be in the same row, the same column, or the same diagonal. A solution is such a placement.
Some small cases of the general problem are interesting. For n = 1, a single queen is placed on the single square; this is a solution. For n = 2 and n = 3 there is no solution. On the 2 × 2 board every pair of squares lies in the same row, the same column, or the same diagonal. For n ≥ 4 there is always at least one solution. The 8-queens problem has 92 solutions. If solutions that can be turned into one another by rotating and reflecting the board are counted as the same, 12 fundamental solutions remain.
The solution in Figure 4.11 is given in chess notation. a1 is rank 1 of file a, that is, the bottom-left corner. The correctness of the solution can be checked: the eight letters are distinct (distinct columns), and the eight numbers are distinct (distinct rows). For the diagonal check, the absolute values of the row difference and the column difference are compared for each pair; they are equal for no pair. This check is a small example of why the problem is in NP: finding a solution requires search, while checking one ends with comparing C(8, 2) = 28 pairs.
4.3.2Placing queens row by row
The backtracking solution proceeds in the following steps.
- Every cell of the board is initially empty.
- The first queen is placed in some column of the first row.
- In the next row each column is tried in turn. When a queen is put in that column, we check whether it conflicts with the earlier queens: is there a queen in the same column or on either of the two diagonals?
- If there is no conflict, the position is accepted as valid and we move on to the next row.
- If all the columns of a row have been tried and no safe place is found, the queen in the previous row is removed and the next column is tried in that row. This is the backtrack.
- When all the queens have been placed, a solution has been found.
Placing the queens row by row is a deliberate design decision. There must be exactly one queen in every row. This observation builds the row constraint into the structure. Queen 0 goes to row 0 and queen 1 to row 1; two queens in the same row become impossible. Each placement therefore checks only the column and the two diagonals. The search space also falls from 648 (64 squares for each queen) to 88. Guaranteeing constraints through the structure instead of checking them is a technique often used in backtracking.
4.3.3Four queens: the board and the state-space tree
The way the algorithm works is best seen on a small example. For n = 4 the queens are placed row by row; in each row columns 0, 1, 2, 3 are tried in that order. In the state-space tree each level below the root is a row; a node shows the column chosen in that row. The red cells on the board are the squares attacked by the queens already placed.
- Row 0: column 0 is safe; the queen is placed and we descend to row 1.
- Row 1: columns 0 and 1 are under attack; column 2 is safe. The queen is placed and we descend to row 2.
- Row 2: all four columns are under attack. This is a dead end. The queen in row 1 (column 2) is removed; the next column is tried in row 1.
- Row 1: column 3 is safe; the queen is placed and we descend to row 2.
- Row 2: column 0 is under attack, column 1 is safe. The queen is placed and we descend to row 3.
- Row 3: all four columns are under attack; dead end. The queen in row 2 (column 1) is removed.
- Row 2: the remaining columns, 2 and 3, are also under attack; dead end. The queen in row 1 (column 3) is removed.
- Row 1 has no columns left to try. The queen in row 0 (column 0) is removed as well.
- Row 0: column 1 is safe; the queen is placed.
- Row 1: columns 0, 1, 2 are under attack, column 3 is safe.
- Row 2: column 0 is safe.
- Row 3: columns 0 and 1 are under attack, column 2 is safe. The fourth queen is placed and
row == nholds. A solution has been found: the columns are [1, 3, 0, 2].
Counting the nodes in the tree gives the breakdown of the work. Apart from the root there are 8 nodes: 4 nodes on the solution path and 4 nodes that were undone (0, 2, 3, and 1). Each node is a placement; each undone node is a backtrack. Because no queen is ever put on an attacked square, those squares do not even appear as nodes in the tree. That is exactly the gain from pruning.
Note the representation of the solution. The i-th element of the array [1, 3, 0, 2] is the column of the queen in row i. The queen in row 0 is in column 1, the one in row 1 in column 3, the one in row 2 in column 0, and the one in row 3 in column 2. This representation is the natural result of building the row constraint into the structure: a single number per row is enough.
Question. How many solutions does the 4-queens problem have? How is the second solution obtained from the first?
Solution. If the search is not stopped at the first solution, columns 2 and 3 are also tried in row 0. The column 2 branch gives the second solution: [2, 0, 3, 1]. The column 3 branch ends in a dead end. The 4-queens problem has only 2 solutions. The second solution is the mirror image of the first: if each column c is replaced by 3 − c, the array [1, 3, 0, 2] becomes [2, 0, 3, 1]. When the board is reflected about the vertical axis, the attack relations are preserved. So the reflection of a solution is also a solution.
4.3.4Java code
The algorithm is written with two methods. isSafe checks whether a queen put on square (r, c) conflicts with the queens placed earlier. solve is the backtracking method that proceeds row by row. The board is the array int[][] b; b[i][j] == 1 means there is a queen on square (i, j). n is a field of the class.
boolean isSafe(int[][] b,
int r, int c) {
// same column
for (int i = 0; i < r; i++)
if (b[i][c] == 1) return false;
// upper-left diagonal
for (int i = r-1, j = c-1;
i >= 0 && j >= 0; i--, j--)
if (b[i][j] == 1) return false;
// upper-right diagonal
for (int i = r-1, j = c+1;
i >= 0 && j < n; i--, j++)
if (b[i][j] == 1) return false;
return true;
}isSafe looks in only three directions: up, the upper-left diagonal, and the upper-right diagonal. There is no need to look at the rows below, because the queens are placed row by row, and when a queen is put in row r the lower rows are empty. The same row is not examined either, because each row has at most one queen. The first loop scans the r cells of the column. The second loop starts at (r − 1, c − 1) and moves toward the upper-left corner, decreasing the row and the column together. The third loop decreases the row while increasing the column. The loop conditions keep the scan from leaving the board: j >= 0 guards the left edge and j < n the right edge. If any loop finds a queen, the method returns false at once.
boolean solve(int[][] b, int row) {
if (row == n)
return true;
for (int col = 0; col < n;
col++) {
if (isSafe(b, row, col)) {
b[row][col] = 1; // place
if (solve(b, row + 1))
return true;
b[row][col] = 0; // undo
}
}
return false;
}solve is a direct application of the template. row == n is the goal test: if n queens have been placed, a solution has been found. The loop tries every column of the row. isSafe is the validity test and does the pruning. A queen is placed on a safe square (choose), and solve is called for the next row (explore). If the call returns true, a solution has been found. This true is passed up at once; the board stays as it is and contains the solution. If the call returns false, there is no way to continue with this column; the queen is removed (unchoose) and the loop continues with the next column. If the loop ends, no column worked in this row and false is returned. This false forces the solve one level up to remove its own queen.
The cost has two parts. isSafe runs at most three loops, each of at most n steps, so one call takes O(n). For solve the worst case is traversing the whole state-space tree. The first row has n safe columns and the second at most n − 1, since at least one column is taken. With this bound the number of nodes is O(n!). At each node, isSafe at O(n) is called for each of the n columns, giving a crude upper bound of O(n2 · n!). The real number of nodes is much smaller than n!. Memory use is O(n2) for the board and O(n) for the call stack.
Not propagating the result of the recursive call. If only solve(b, row + 1); is written instead of if (solve(b, row + 1)) return true;, the loop continues even after a solution has been found. On the next line of code b[row][col] = 0 runs, and the solution is erased from the board. The search traverses the whole tree and finally returns false; the board is left empty.
4.3.5Code trace: solve(b, 0), n = 4
Tracing the code line by line reveals a detail that does not show up in the tree trace: every safety test is a call to isSafe, and the method returns at the first attack it finds. The method checks the column first, then the upper-left diagonal, and the upper-right diagonal last. If a square is attacked by more than one queen, only the attack found by the first check is visible. For example, square (2, 2) is both in the column of the queen at (1, 2) and on the diagonal of the queen at (0, 0). Because the method scans the column first, it finds the attack at (1, 2).
solve(b, 0) has been called; the board is empty, row = 0.| # | Square | isSafe | Reason / action | Queens | Stack depth |
|---|---|---|---|---|---|
| 1 | (0, 0) | true | b[0][0] = 1, solve(b, 1) | [0, –, –, –] | 2 |
| 2 | (1, 0) | false | same column: (0, 0) | [0, –, –, –] | 2 |
| 3 | (1, 1) | false | upper-left diagonal: (0, 0) | [0, –, –, –] | 2 |
| 4 | (1, 2) | true | b[1][2] = 1, solve(b, 2) | [0, 2, –, –] | 3 |
| 5 | (2, 0) | false | same column: (0, 0) | [0, 2, –, –] | 3 |
| 6 | (2, 1) | false | upper-right diagonal: (1, 2) | [0, 2, –, –] | 3 |
| 7 | (2, 2) | false | same column: (1, 2) | [0, 2, –, –] | 3 |
| 8 | (2, 3) | false | upper-left diagonal: (1, 2) | [0, 2, –, –] | 3 |
| — | — | — | the loop in row 2 ends, return false; undo: b[1][2] = 0 | [0, –, –, –] | 2 |
| 9 | (1, 3) | true | b[1][3] = 1, solve(b, 2) | [0, 3, –, –] | 3 |
| 10 | (2, 0) | false | same column: (0, 0) | [0, 3, –, –] | 3 |
| 11 | (2, 1) | true | b[2][1] = 1, solve(b, 3) | [0, 3, 1, –] | 4 |
| 12 | (3, 0) | false | same column: (0, 0) | [0, 3, 1, –] | 4 |
| 13 | (3, 1) | false | same column: (2, 1) | [0, 3, 1, –] | 4 |
| 14 | (3, 2) | false | upper-left diagonal: (2, 1) | [0, 3, 1, –] | 4 |
| 15 | (3, 3) | false | same column: (1, 3) | [0, 3, 1, –] | 4 |
| — | — | — | row 3 is a dead end; undo: b[2][1] = 0 | [0, 3, –, –] | 3 |
| 16 | (2, 2) | false | upper-left diagonal: (0, 0) | [0, 3, –, –] | 3 |
| 17 | (2, 3) | false | same column: (1, 3) | [0, 3, –, –] | 3 |
| — | — | — | row 2 is a dead end; undo: b[1][3] = 0; column 4 = n, so the loop in row 1 ends too | [0, –, –, –] | 2 |
| — | — | — | row 1 is a dead end; undo: b[0][0] = 0 | [–, –, –, –] | 1 |
| 18 | (0, 1) | true | b[0][1] = 1, solve(b, 1) | [1, –, –, –] | 2 |
| 19 | (1, 0) | false | upper-right diagonal: (0, 1) | [1, –, –, –] | 2 |
| 20 | (1, 1) | false | same column: (0, 1) | [1, –, –, –] | 2 |
| 21 | (1, 2) | false | upper-left diagonal: (0, 1) | [1, –, –, –] | 2 |
| 22 | (1, 3) | true | b[1][3] = 1, solve(b, 2) | [1, 3, –, –] | 3 |
| 23 | (2, 0) | true | b[2][0] = 1, solve(b, 3) | [1, 3, 0, –] | 4 |
| 24 | (3, 0) | false | same column: (2, 0) | [1, 3, 0, –] | 4 |
| 25 | (3, 1) | false | same column: (0, 1) | [1, 3, 0, –] | 4 |
| 26 | (3, 2) | true | b[3][2] = 1, solve(b, 4) → row == n, true | [1, 3, 0, 2] | 5 |
The table shows the whole behavior of the code. isSafe is called 26 times. Of these, 8 return true; these 8 calls are placements. There are 4 undo steps. The stack depth is the number of solve frames open at that moment. When the depth reaches 5, the frame solve(b, 4) is open and the goal test returns true. This value is carried up through four frames. No frame removes its own queen; the board contains the solution.
row == n, the value true is carried up the stack; the solution [1, 3, 0, 2] stays on the board.Question. How does solve(b, 0) find the first solution for n = 5? How many placements and how many backtracks are made?
Solution. In row 0, column 0 is safe. In row 1, column 0 is in the same column and column 1 is on a diagonal; column 2 is safe. In row 2, columns 0, 1, 2, and 3 are under attack; column 4 is safe. In row 3, column 0 is under attack and column 1 is safe. In row 4, columns 0, 1, and 2 are under attack and column 3 is safe. The solution is [0, 2, 4, 1, 3]. 5 placements are made and there is no backtracking: in every row the first safe column is the right choice. With 4 queens, 8 placements and 4 backtracks were needed. A larger problem can need less work; the cost of finding the first solution does not grow smoothly with n.
4.3.6Eight queens: the first solution found
When solve(b, 0) is run for n = 8, the columns are tried from smallest to largest, so the first solution in lexicographic order is always found. This solution is [0, 4, 7, 5, 2, 6, 1, 3]: the queen in row 0 is in column 0, the one in row 1 in column 4, and so on.
Up to this solution, isSafe is called 876 times, 113 queens are placed, and there are 105 backtracks. The relation between the numbers is striking: 113 − 105 = 8. Every placement is either undone or stays in the solution; since 8 queens stay in the solution, the remaining 105 placements were undone. This equality holds for every n-queens search that stops at the first solution: placements − undos = n.
The placement a1, b7, c4, d6, e8, f2, g5, h3 in Figure 4.11 is also a solution, but it is not the first one the algorithm finds. All 92 solutions are valid; the algorithm stops only at the first one, which is determined by the candidate order. To find all the solutions, the solution is recorded in the goal test and false is returned. false means that the search continues: the call above removes its queen and tries the next column.
4.3.7Solution and placement counts
To see how the algorithm behaves as n grows, two numbers are measured: the number of safe placements made to find all the solutions, and the number of placements made up to the first solution. A “placement” is a queen found safe and put on the board; it equals the number of non-root nodes in the state-space tree.
| n | Solutions | nn (brute force) | Placements (all solutions) | Up to the first solution |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 4 | 2 | — |
| 3 | 0 | 27 | 5 | — |
| 4 | 2 | 256 | 16 | 8 |
| 5 | 10 | 3,125 | 53 | 5 |
| 6 | 4 | 46,656 | 152 | 31 |
| 7 | 40 | 823,543 | 551 | 9 |
| 8 | 92 | 16,777,216 | 2056 | 113 |
| 9 | 352 | 387,420,489 | 8393 | 41 |
| 10 | 724 | 10,000,000,000 | 35,538 | 102 |
Three conclusions can be drawn from the table.
- For n = 2 and n = 3 there is no solution. The algorithm traverses the whole tree and returns
false. For n = 3 the tree has only 5 non-root nodes; all 5 placements are undone. This is the proof of the answer “no solution”: the search is complete and has skipped no possibility. - The cost of finding all the solutions is far smaller than nn, but it still grows quickly. From n = 9 to 10 the number of placements grows by a factor of about 4.2. The growth is roughly like n!: about one percent of 10! = 3,628,800.
- The work up to the first solution does not grow smoothly with n. For n = 6, 31 placements are needed, while for n = 7 only 9 suffice. The lexicographically first solution for n = 6, [1, 3, 5, 0, 2, 4], starts with column 1; all the branches starting with column 0 are explored in vain. The first solution for n = 7, [0, 2, 4, 6, 1, 3, 5], needs almost no backtracking: only 2 undos are made.
4.3.8An O(1) safety test
At every call isSafe scans the column and the two diagonals and takes O(n). Considering that for 8 queens 876 calls are made up to the first solution, this cost is not negligible. If instead a flag is kept for each column and each diagonal, the test drops to O(1). For this we need to know how to number the diagonals.
Denote a square by (r, c). On an anti-diagonal, which runs from the upper right down to the lower left, moving from one square to the next increases the row by one and decreases the column by one. So the sum r + c stays constant. On a diagonal running from the upper left down to the lower right, the row and the column increase together; the difference r − c is constant. On an n × n board r + c takes values from 0 to 2n − 2; there are 2n − 1 anti-diagonals. r − c lies between −(n − 1) and n − 1. If n − 1 is added to this value, the index starts at 0 and again takes 2n − 1 values.
d1 (r + c) and d2 (r − c + n − 1) of each square on a 4 × 4 board. The highlighted squares share an index: those on the left form anti-diagonal number 3, those on the right form diagonal number 3.boolean[] cols = new boolean[n];
boolean[] d1 = new boolean[2*n-1]; // r+c
boolean[] d2 = new boolean[2*n-1]; // r-c+n-1
void solve(int r) {
if (r == n) { count++; return; }
for (int c = 0; c < n; c++) {
int a = r + c, b = r - c + n - 1;
if (cols[c] || d1[a] || d2[b])
continue;
cols[c] = d1[a] = d2[b] = true;
solve(r + 1);
cols[c] = d1[a] = d2[b] = false;
}
}The code has three boolean arrays. cols[c] says whether column c has a queen; d1[a] says whether the anti-diagonal numbered a = r + c has one; d2[b] says whether the diagonal numbered b = r − c + n − 1 has one. Whether a square is safe is learned with three array accesses. If any one of the flags is true, the square is under attack and continue moves to the next column. Otherwise all three flags are set to true (choose), the next row is solved (explore), and then all three flags are set to false (unchoose).
This version differs in two ways. First, there is no need for a board array. The flags alone check for conflicts. If the solution itself is needed, it is enough to keep an array place[row] = col. Second, the method is void and does not stop at the first solution. In the goal test count is incremented and the method returns; the search goes on. So the code counts all the solutions. For n = 8, count becomes 92 and 2056 placements are made; these numbers are the same as for the board-based version, because the two versions traverse the same tree in the same order. Only the work at each node changes.
Question. In the flag version for n = 8, there is a queen only at square (3, 1). Which flags are true? Are the squares (5, 3), (1, 3), and (4, 4) safe?
Solution. cols[1], d1[3 + 1] = d1[4], and d2[3 − 1 + 7] = d2[9] are true. For (5, 3), a = 8 and b = 5 − 3 + 7 = 9; d2[9] is occupied. The square is not safe: (3, 1), (4, 2), (5, 3) are on the same diagonal. For (1, 3), a = 4; d1[4] is occupied. (3, 1), (2, 2), (1, 3) are on the same anti-diagonal; the square is not safe. For (4, 4), cols[4], d1[8], and d2[7] are empty; the square is safe.
Forgetting to add n − 1 to the diagonal index. If d2[r - c] is written, the index for square (0, 3) is −3 and an ArrayIndexOutOfBoundsException is thrown. Taking the length of the array to be n gives the same error: the number of diagonals is 2n − 1, not n.
4.3.9Counting all solutions
The board-based solve can also be changed to count all the solutions. The change is only in the goal test.
int count = 0;
boolean solve(int[][] b, int row) {
if (row == n) {
count++; // count the solution
return false; // keep searching
}
for (int col = 0; col < n; col++) {
if (isSafe(b, row, col)) {
b[row][col] = 1;
solve(b, row + 1);
b[row][col] = 0; // undo
}
}
return false;
}In the goal test count is incremented and false is returned. The value false tells the calling frame, “this path is finished; keep searching.” The caller removes its queen and tries the next column. Because the method never returns true, there is no need to look at the result of the recursive call. For n = 4, 5, 6, 7, 8 the code counts 2, 10, 4, 40, and 92 solutions respectively.
Returning true in the goal test would be wrong. All the calls would then end at the first solution and count would stay at 1. Deleting the undo line would be wrong as well. The board would fill up with the queens of earlier attempts, and later attempts would be pruned incorrectly.
When all solutions are searched for, the symmetry of the board can be exploited. Reflecting a solution about the vertical axis gives another solution. If the queen in the first row is in column c, its mirror image is in column n − 1 − c. So the first queen is tried only in the left half, and every solution found is counted twice. If n is odd, the mirror image of a solution that starts in the middle column also starts in the middle column; those are counted once. For n = 8 this method reaches the same result of 92 with 1028 placements instead of 2056: the work is cut exactly in half. For n = 9 the placements fall from 8393 to 4703; because the middle column is counted on its own, the gain is somewhat smaller.
4.4The min-conflicts heuristic
4.4.1From complete placement to repair
Backtracking builds the solution starting from an empty board and keeps it valid at every step. The n-queens problem can also be approached in a completely different way. First all the queens are put on the board, one in each column. This placement is very likely invalid: some queens attack each other. Then the conflicts are repaired one by one with small local changes. This approach is called the min-conflicts heuristic.
The min-conflicts heuristic is a local search method that starts from a complete assignment, which may be invalid. At each step one of the variables that violate constraints is chosen. This variable is given the value that creates the fewest conflicts with the other variables. The search stops when no conflicts remain or when the step limit is reached.
For n-queens the variables are the columns, and the value of each variable is the row of the queen in that column. queen[k] = r means that the queen in column k is in row r. The column constraint is built into the structure; there is exactly one queen in each column. Conflicts arise in rows and on diagonals.
minConflicts(n, maxSteps):
// start: greedy placement
for k = 0 .. n-1:
queen[k] = row with the fewest conflicts
for step = 1 .. maxSteps:
if no conflicts: return queen
k = random conflicted column
queen[k] = argmin_r conflicts(k, r)
// break ties at random
return failureThe pseudocode has two phases. The initialization phase places the queens column by column. In each column the row that conflicts least with the queens placed so far is chosen; if there is a tie, one of the rows is taken at random. This is a greedy start and often leaves only a few conflicts. The repair phase picks one of the conflicted queens at random at each step. The chosen queen is moved, within its own column, to the row that creates the fewest conflicts. Here too ties are broken at random. When no conflicts remain, the placement is a solution. If no solution is found within maxSteps steps, the search counts as failed.
4.4.2The number of conflicts
The basic computation of the algorithm is this: if the queen in column k were moved to row r, how many queens would it conflict with? This number is the count of the other queens in the same row and on the same diagonals.
int conflicts(int[] queen, int k, int r) {
int c = 0;
for (int j = 0; j < queen.length; j++) {
if (j == k) continue; // the queen itself
if (queen[j] == r // same row
|| Math.abs(queen[j] - r) == Math.abs(j - k)) // diagonal
c++;
}
return c;
}The method scans all the columns. The queen's own column is skipped. If the queen in column j is in the same row, the counter is incremented. If the absolute value of the row difference equals the absolute value of the column difference, the two squares lie on the same diagonal; the counter is incremented again. The computation takes O(n). Computed for all the rows of one column it is O(n2). For large n, counters are kept for how many queens are in each row, each diagonal, and each anti-diagonal. Then a single conflict count is read in O(1).
Question. On the 4 × 4 board, queen = [1, 3, 0, 3]. Which queens conflict? If column 3 is chosen for repair, what is the conflict count of this queen for each row? Where is the queen moved?
Solution. The queens are at (row, column) positions (1, 0), (3, 1), (0, 2), and (3, 3). The queens in columns 1 and 3 are in the same row (3); there is no other conflict. The computation for column 3:
- Row 0: (0, 2) is in the same row: 1.
- Row 1: (1, 0) is in the same row; (0, 2) is on a diagonal (row difference 1, column difference 1); (3, 1) is on a diagonal (2 and 2): 3.
- Row 2: it conflicts with no queen: 0.
- Row 3: (3, 1) is in the same row: 1.
The counts are 1, 3, 0, 1. The smallest value, 0, occurs only in row 2. The queen is moved there and the placement becomes [1, 3, 0, 2]. No conflicts remain; the 4-queens solution has been found with a single repair step.
4.4.3Repair steps
One run of the algorithm on 8 queens goes as follows. The greedy start produces the placement queen = [7, 2, 4, 1, 4, 0, 3, 6]. In this placement only one pair conflicts: the queens in columns 2 and 4 are in the same row (4). In the figures, the numbers in the highlighted column show how many queens the red queen would conflict with if it were moved to that row; the queen's own row is left blank.
| Step | queen | Conflicting | Chosen | Minimum value | Decision |
|---|---|---|---|---|---|
| 1 | [7, 2, 4, 1, 4, 0, 3, 6] | 2 and 4 (row 4) | column 4 | 1 (row 7) | to row 7 |
| 2 | [7, 2, 4, 1, 7, 0, 3, 6] | 0 and 4 (row 7) | column 0 | 1 (rows 0, 5) | one at random |
| … | a few repair steps | ||||
| 3 | [2, 5, 3, 0, 7, 3, 1, 6] | 2 and 5 (row 3) | column 5 | 1 (rows 4, 5) | to row 4 |
| 4 | [2, 5, 3, 0, 7, 4, 1, 6] | 5 and 7 (diagonal) | column 5 | 1 (rows 3, 5) | plateau; to row 5 |
| 5 | [2, 5, 3, 0, 7, 5, 1, 6] | 1 and 5 (row 5) | column 1 | 1 (row 7) | to row 7 |
| 6 | [2, 7, 3, 0, 7, 5, 1, 6] | 1 and 4 (row 7) | column 4 | 1 (rows 0, 2) | to row 2 |
| 7 | [2, 7, 3, 0, 2, 5, 1, 6] | 0 and 4 (row 2) | column 0 | 0 (row 4) | to row 4 |
| 8 | [4, 7, 3, 0, 2, 5, 1, 6] | none | — | — | solution |
The table shows two important behaviors of local search. First, a repair does not always remove a conflict; sometimes it only moves it. In step 1 the queen in column 4 is moved to row 7. The conflict with column 2 ends, but the queen in column 0 is also in row 7, and a new conflict arises. The number of conflicting pairs stays at 1. The algorithm never increases the number of conflicts, but it does not guarantee decreasing it either.
Second, the algorithm can get stuck on plateaus. In step 4 the queen in column 5 is in row 4 and is on the same diagonal as the queen at square (6, 7). In rows 3, 4, and 5 the conflict count is 1. No move improves the situation; this is a plateau. The heuristic breaks the tie at random and the queen goes to row 5. There, this time, it is in the same row as column 1. The queen in column 5 may go back and forth a few times among rows 3, 4, and 5 on the plateau. Thanks to the random choice, another conflicted queen, in column 1, is eventually chosen, and the search leaves the plateau. In step 7 there are 0 conflicts in row 4 for column 0; the queen is moved there and the solution is found.
The solution found is written in column order, not in row order. This difference should be kept in mind when comparing it with the solution [0, 4, 7, 5, 2, 6, 1, 3] of the backtracking algorithm. Both representations are permutations; one is the mapping from row to column, the other from column to row.
4.4.4Local search and completeness
Min-conflicts is a local search method. It differs from backtracking in three basic ways.
- State. In backtracking the state is partial but always valid. In local search the state is complete but may be invalid.
- Memory. Local search has no backtrack stack. The algorithm keeps only the current placement; it does not remember past decisions.
- Completeness. Local search is not complete. It can wander on plateaus and enter a cycle, which is why a step limit is needed. It finds only a solution and cannot prove that none exists. Reaching the step limit does not mean “no solution”; it means only “not found in this run.”
On the other hand, min-conflicts is surprisingly fast for large n. According to the 1992 work of Minton and colleagues, with a good greedy start even a problem with a million queens is solved in an average of a few tens of repair steps. Backtracking, by contrast, slows down rapidly as n grows. The strengths of the two methods complement each other. To count all the solutions or to show that none exists, backtracking is needed. If a single solution to a very large instance is wanted quickly, local search is more suitable.
Taking local search to be complete. For n = 3, min-conflicts always reaches the step limit, because there is no solution. But for n = 100 reaching the step limit is also possible: the limit may have been chosen too small or the search may have fallen onto a bad plateau. The two cases cannot be told apart from the output of the algorithm. Local search cannot prove the answer “no solution.”
4.5Sudoku
4.5.1Sudoku as a constraint satisfaction problem
The goal of Sudoku is to fill in a 9 × 9 grid. In every row, every column, and each of the nine 3 × 3 boxes, the digits 1 to 9 are used once each. Some cells are given at the start; these are called clues. The remaining cells are filled in so as to obey these rules. A well-formed puzzle has a single solution.
Sudoku is an example of a more general kind of problem.
A constraint satisfaction problem (CSP) has three parts. The first is a set of variables. The second is, for each variable, the set of values it may take (its domain). The third is the constraints that the variables must obey together. A solution is an assignment that gives each variable a value from its domain and satisfies all the constraints.
In Sudoku the variables are the empty cells. The domain of each variable is {1, …, 9}. The constraints are of the form “all different within a unit”: cells in the same row, the same column, and the same box must get different digits. N-queens is also a constraint satisfaction problem: the variables are the rows and the domains are the columns. In graph coloring the variables are the vertices and the domains are the colors. Backtracking is the general method for solving constraint satisfaction problems.
4.5.2The algorithm
The backtracking algorithm solves Sudoku in the following steps.
- A digit is assigned to an empty cell.
- If the assigned digit is valid, that is, it does not already appear in the same row, column, or box, we move on to the next empty cell.
- If it is not valid, the next digit is tried.
- If all the digits have been tried in a cell and none worked, we return to the previous cell and try a different digit there.
- The steps are repeated until all the cells are filled.
This is a direct application of the general template. The partial solution is the filled cells. The candidates are the digits 1–9. The constraint test is isValid. The goal is that no empty cell remains.
The small puzzle in the figure is played with 2 × 2 boxes and the digits 1–4. In this puzzle no dead end is ever reached: 2 is written to (0, 1), 3 to (0, 2), and the remaining six empty cells are also filled with the first valid digit. The solution is found in eight placements. In a large puzzle the situation is very different.
4.5.3Java code
boolean solve(int[][] b) {
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (b[r][c] == 0) {
for (int d = 1; d <= 9; d++)
if (isValid(b, r, c, d)) {
b[r][c] = d;
if (solve(b)) return true;
b[r][c] = 0; // undo
}
return false; // no digit fits
}
return true; // no empty cell
}At each call solve scans the grid from the beginning, looking for the first empty cell. When it finds an empty cell (r, c), it tries every digit from 1 to 9. A valid digit is written and solve is called again. That call finds the next empty cell. If the call returns true, a solution has been found. If it returns false, the digit is erased and the next digit is tried. If none of the nine digits works, return false runs. This line triggers the backtrack: the calling frame erases the digit in its own cell.
There is a subtle point in the structure of the code. return false is inside the two loops, at the end of the block that handles the first empty cell. After handling the first empty cell, the method does not look at the remaining cells. If the first empty cell cannot be filled, there is no point in trying to fill the others. If the loops finish without finding any empty cell, the return true at the bottom runs: the grid is full.
boolean isValid(int[][] b,
int r, int c, int d) {
for (int i = 0; i < 9; i++)
if (b[r][i] == d || b[i][c] == d)
return false;
int br = r / 3 * 3;
int bc = c / 3 * 3;
for (int i = br; i < br + 3; i++)
for (int j = bc; j < bc + 3; j++)
if (b[i][j] == d)
return false;
return true;
}isValid checks whether the digit d can be written in cell (r, c). The first loop scans both the row (b[r][i]) and the column (b[i][c]) in a single pass. Then the cell's box is scanned. The top-left corner of the box is found with br = r / 3 * 3 and bc = c / 3 * 3. Integer division rounds down; multiplying by 3 converts the box number back to an index. For cell (7, 4), 7 / 3 = 2, 2 · 3 = 6; 4 / 3 = 1, 1 · 3 = 3. The box covers rows 6–8 and columns 3–5. The method looks at no more than 27 cells, 18 for the row and column and 9 for the box; this is constant work.
Computing the box corner as r / 3. This expression gives the number of the box (0, 1, or 2), not the index of its first row. For cell (7, 4) the box comes out as (2, 1), and rows 2–4 and columns 1–3 are scanned. That region is the wrong box. Forgetting the box check altogether causes a similar error: “solutions” are produced that obey the row and column rules but have invalid boxes.
4.5.4Step-by-step solution
On the example puzzle the algorithm fills the empty cells row by row, from left to right; in each cell 1–9 are tried in order. In row 0 the clues are 5, 3, and 7. The first five empty cells, (0, 2), (0, 3), (0, 5), (0, 6), and (0, 7), receive 1, 2, 4, 8, and 9 respectively. Each is the smallest valid digit for that cell. In cell (0, 8) no digit is valid: the only digit still missing from the row is 6, and it is already in column 8, at cell (5, 8). This is the first dead end; up to this point 5 placements have been made and none undone.
The backtrack begins. The 9 in (0, 7) is erased; there is no digit larger than 9 in that cell, so (0, 7) is also a dead end. The 8 in (0, 6) is erased and 9 is tried. This time no digit fits in (0, 7); the 9 is erased too. (0, 6) is also a dead end. The backtrack reaches (0, 5), where 6 is tried instead of 4. At this point 7 placements and 4 undos have been made. Then 4 is written to (0, 6), 9 to (0, 7), and 8 to (0, 8), and row 0 is completed for the first time: 5 3 1 2 7 6 4 9 8. This row is valid in itself, but it is not yet known whether it leads to a solution.
In fact it does not. All the attempts made in row 1 end in dead ends. The backtrack reaches row 0 and the 8 in (0, 8) is erased; by then 31 placements and 26 undos have been made. A decision made early can turn out to be wrong only much later. The algorithm finds this out only after trying everything that depends on that decision.
| Row | Placements | Undos | Note |
|---|---|---|---|
| 0 | 10 | 4 | 5 3 1 2 7 6 4 9 8 (will change later) |
| 1 | 229 | 218 | |
| 2 | 377 | 360 | the first three rows are now the same as in the final solution |
| 3 | 395 | 372 | |
| 4 | 1520 | 1492 | |
| 5 | 4185 | 4151 | most of the work is done by this row |
| 6 | 4197 | 4157 | |
| 7 | 4202 | 4157 | no more undos |
| 8 | 4208 | 4157 | solution |
The table shows the irregular progress of the search. The first three rows settle into place within 377 placements. Between row 4 and row 5, however, 2665 placements are made. In this interval the algorithm changes the choices in rows 3–5 over and over. After row 6 almost no backtracking remains: none of the last 11 placements is undone. In the end all 51 empty cells are filled and all the constraints are satisfied. In total 4208 placements and 4157 undos were made. The difference is 4208 − 4157 = 51: the digits that remain in the solution.
4.5.5Cost and MRV
If brute force wrote one of 9 digits into each of the 51 empty cells and only then checked, 951 ≈ 4.6 · 1048 assignments would be needed. Pruning reduces this number to 4208. The upper bound for the worst case is still O(9m), where m is the number of empty cells. In practice, though, only a small part of the tree is visited.
The same puzzle can be solved with much less work. It is not compulsory to fill the first empty cell in row-by-row order. Which cell to fill first is a choice, and this choice determines the height of the search. The MRV (minimum remaining values) heuristic fills, at each step, the empty cell that has the fewest candidates left.
boolean solveMRV(int[][] b) {
int br = -1, bc = -1, fewest = 10;
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (b[r][c] == 0) {
int cands = 0;
for (int d = 1; d <= 9; d++)
if (isValid(b, r, c, d)) cands++;
if (cands < fewest) { fewest = cands; br = r; bc = c; }
}
if (br < 0) return true; // no empty cell
for (int d = 1; d <= 9; d++)
if (isValid(b, br, bc, d)) {
b[br][bc] = d;
if (solveMRV(b)) return true;
b[br][bc] = 0; // undo
}
return false;
}The method first scans all the empty cells and counts how many valid digits are left for each. The cell with the fewest candidates, (br, bc), is chosen. If there is no empty cell, the grid is full. In the chosen cell the valid digits are tried in order; the structure is the same as in the other backtracking code. If a cell has 0 candidates, the loop never runs and the method returns false at once. This is an early detection of a contradiction.
| Strategy | Placements | Undos |
|---|---|---|
| Row by row, first empty cell | 4208 | 4157 |
| MRV: cell with the fewest candidates | 51 | 0 |
In this puzzle MRV finds a cell with a single candidate at every step. At the start, 4 of the 51 empty cells have a single candidate. When one of them is filled, the candidates of the neighboring cells shrink and new single-candidate cells appear. The chain never breaks. All 51 placements are correct and no backtracking is needed. Because the scan at each step calls isValid for 81 cells and 9 digits, the work per step grows. But since the number of steps falls from 4208 to 51, the total work still drops a great deal.
MRV does not eliminate backtracking in every puzzle. In hard puzzles there comes a point at which every empty cell has at least two candidates left. Then MRV picks a cell with two candidates, and if it tries the wrong candidate it has to backtrack. Even so, starting with the cell with the fewest candidates keeps the branching smallest and exposes contradictions as early as possible.
4.6Graph coloring
4.6.1The problem
We want the neighboring countries on a map to be painted in different colors. If the countries are thought of as vertices and the shared borders as edges, this question becomes a graph problem. The same problem appears in other guises. In an exam schedule, two exams taken by the same student cannot be placed at the same time; the exams are vertices, the clashes are edges, and the time slots are colors. In a compiler, two variables that are live at the same time cannot share a register; the variables are vertices and the registers are colors.
The m-coloring problem: can the vertices of a graph be assigned colors from 1 to m so that no two vertices joined by an edge get the same color? The smallest value of m that suffices to color a graph is called its chromatic number.
Backtracking fits this problem naturally. The vertices are colored in the order 0, 1, 2, …. The partial solution is the colors of the first k vertices. The candidates are the m colors. The constraint is that the color of a vertex must differ from the color of each of its neighbors. The decision version of 3-coloring is NP-complete; for m = 2, on the other hand, the problem is solved in polynomial time, because 2-colorability is equivalent to being bipartite and can be tested with a breadth-first search.
4.6.2Step by step: a graph with six vertices
The graph has six vertices and nine edges: 0–1, 0–2, 0–5, 1–3, 1–4, 2–3, 2–5, 3–4, and 4–5. Three colors are used: 1 blue, 2 green, 3 orange. At each vertex the colors are tried in the order 1, 2, 3.
| Step | Vertex | Neighbor colors | Decision | colors[0..5] |
|---|---|---|---|---|
| 1 | 0 | — | color 1 | [1, 0, 0, 0, 0, 0] |
| 2 | 1 | 0: 1 | 1 is taken; color 2 | [1, 2, 0, 0, 0, 0] |
| 3 | 2 | 0: 1 | 1 is taken; color 2 | [1, 2, 2, 0, 0, 0] |
| 4 | 3 | 1: 2, 2: 2 | color 1 | [1, 2, 2, 1, 0, 0] |
| 5 | 4 | 1: 2, 3: 1 | 1 and 2 are taken; color 3 | [1, 2, 2, 1, 3, 0] |
| 6 | 5 | 0: 1, 2: 2, 4: 3 | dead end; the color of vertex 4 is erased | [1, 2, 2, 1, 0, 0] |
| 7 | 4 | — | no color left to try; the color of vertex 3 is erased | [1, 2, 2, 0, 0, 0] |
| 8 | 3 | 1: 2, 2: 2 | 2 is taken; color 3 | [1, 2, 2, 3, 0, 0] |
| 9 | 4 | 1: 2, 3: 3 | color 1 | [1, 2, 2, 3, 1, 0] |
| 10 | 5 | 0: 1, 2: 2, 4: 1 | 1 and 2 are taken; color 3 | [1, 2, 2, 3, 1, 3] |
The source of the dead end is the decision in step 4. When vertex 3 is painted blue, vertex 4 is forced to be orange. Vertex 5 is adjacent to the blue vertex 0, the green vertex 2, and the orange vertex 4. The backtrack goes first to vertex 4. Vertex 4 has no color greater than 3 and it, too, hits a dead end. The backtrack extends to vertex 3. When vertex 3 becomes orange, vertex 4 can be blue; the neighbors of vertex 5 are then blue, green, and blue, and vertex 5 is painted orange. The valid 3-coloring [1, 2, 2, 3, 1, 3] is found.
4.6.3Java code and code trace
boolean colorGraph(int v) {
if (v == n) return true; // done
for (int c = 1; c <= m; c++) {
if (canUse(v, c)) {
colors[v] = c; // choose
if (colorGraph(v + 1)) return true; // explore
colors[v] = 0; // unchoose
}
}
return false; // dead end
}
// canUse: true if v has no neighbor of color ccolorGraph(v) assumes that vertices 0 through v − 1 have been colored and continues coloring from vertex v. If v == n, all the vertices have been colored. The loop tries the colors from 1 to m. A suitable color is written to colors[v] and we move on to the next vertex. If the recursive call fails, the color is set back to 0; 0 means “uncolored.” If all the colors fail, false is returned.
The slides give the body of canUse only as a one-line description. A version written with an adjacency matrix is as follows:
boolean canUse(int v, int c) {
for (int u = 0; u < n; u++)
if (adj[v][u] == 1 && colors[u] == c)
return false; // a neighbor has color c
return true;
}The method looks at all the neighbors of v. If one of the neighbors has color c, it returns false. Neighbors not yet colored have color 0, which matches no c. So only neighbors colored earlier affect the constraint. With an adjacency matrix this check takes O(n); with an adjacency list it takes O(degree).
For the code trace, let us use a smaller graph: five vertices and six edges, 0–1, 0–3, 1–3, 1–4, 2–4, and 3–4, with m = 3.
colorGraph(0) begins. Vertex 0 has been given color 1; the other cells of the colors array are 0.| Call | Colors tried | Result | colors |
|---|---|---|---|
colorGraph(0) | 1 fits | colors[0] = 1 | [1, 0, 0, 0, 0] |
colorGraph(1) | 1 (used by 0), 2 fits | colors[1] = 2 | [1, 2, 0, 0, 0] |
colorGraph(2) | 1 fits | colors[2] = 1 | [1, 2, 1, 0, 0] |
colorGraph(3) | 1 (used by 0), 2 (used by 1), 3 fits | colors[3] = 3 | [1, 2, 1, 3, 0] |
colorGraph(4) | 1 (used by 2), 2 (used by 1), 3 (used by 3) | dead end, false; colors[3] = 0 | [1, 2, 1, 0, 0] |
colorGraph(3) resumes | no color left | false; colors[2] = 0 | [1, 2, 0, 0, 0] |
colorGraph(2) resumes | 2 fits | colors[2] = 2 | [1, 2, 2, 0, 0] |
colorGraph(3) | 1, 2 are taken; 3 fits | colors[3] = 3 | [1, 2, 2, 3, 0] |
colorGraph(4) | 1 fits | colors[4] = 1 | [1, 2, 2, 3, 1] |
colorGraph(5) | — | v == n, true | [1, 2, 2, 3, 1] |
The interesting point of the trace is vertex 2. The only neighbor of vertex 2 is vertex 4, and when 2 is colored, vertex 4 is not yet colored. So vertex 2 takes color 1 on the first try. This choice is locally correct, but it forces the three neighbors of vertex 4 (1, 2, and 3) into three different colors. The mistake is discovered only when vertex 4 is reached. The backtrack passes through vertex 3 and reaches vertex 2. When vertex 2 becomes green, vertex 4 can be painted blue. The result is [1, 2, 2, 3, 1].
v = 5 = n: all the vertices are colored; the valid 3-coloring is [1, 2, 2, 3, 1].In terms of cost, in the worst case every vertex tries all m colors. The tree has at most mn leaves. At each node canUse takes O(n). The total time is O(n · mn). Memory is O(n) for the colors array and the call stack.
The symmetry of the colors is a source of unnecessary work. If the names of the colors in a coloring are permuted, another valid coloring results: [1, 2, 2, 3, 1] and [2, 1, 1, 3, 2] give the same structure. So fixing the color of vertex 0 to 1 shrinks the search by roughly a factor of m. When a dead end is found, it is pointless to try vertex 0 with another color; even with the color names changed, the same dead end is reached.
4.6.4Odd cycles and the minimum number of colors
Question. We try to color the five-vertex cycle graph C5 (edges 0–1, 1–2, 2–3, 3–4, 4–0) with m = 2 colors using colorGraph(0). What does the search return? What is the minimum number of colors needed?
Solution. Vertex 0 takes color 1. The neighbor of vertex 1, vertex 0, has color 1; it takes color 2. Vertex 2 takes color 1 and vertex 3 takes color 2. The neighbors of vertex 4 are 0 (color 1) and 3 (color 2). Both colors are taken; dead end. The backtracks do not change the outcome. With two colors on a cycle, the colors necessarily alternate: 1, 2, 1, 2, … Even if vertex 0 is tried with color 2, the sequence becomes 2, 1, 2, 1 and vertex 4 is again adjacent to both colors. The search traverses the whole tree and returns false. This result is a proof that there is no solution; the search is complete. With m = 3, colorGraph(0) finds the coloring [1, 2, 1, 2, 3] on the first attempt. The chromatic number of C5 is 3.
The example is a special case of a general rule. A cycle of odd length cannot be colored with two colors. Cycles of even length can be colored with two colors: the colors are distributed alternately and the last vertex ends up with a color different from the first. More generally, a graph is 2-colorable if and only if it contains no odd cycle, that is, if it is bipartite. To find the chromatic number of a graph, colorGraph can be run with increasing values of m: 1, 2, 3, … The first m that succeeds is the chromatic number. Note that every failed attempt traverses the whole tree; the most expensive step is usually the last failed attempt.
4.7Hamiltonian path
4.7.1The problem and a step-by-step solution
A Hamiltonian path is a path that visits every vertex of a graph exactly once. If the last vertex of the path is also adjacent to the first, the path closes and a Hamiltonian cycle is obtained.
A Hamiltonian path looks similar to an Euler path, which traverses every edge exactly once, but the two are very different in difficulty. The existence of an Euler path is decided in linear time by looking at the vertex degrees. The Hamiltonian path problem, on the other hand, is NP-complete; all known exact algorithms take exponential time.
In backtracking the partial solution is a path: path[0..pos − 1]. The candidate is the next vertex to be appended to the path. The constraint has two parts: the new vertex must be adjacent to the last vertex of the path, and it must not already be on the path. The goal is for the path to reach n vertices.
The example graph has five vertices and six edges: 0–1, 0–2, 1–3, 1–4, 2–3, and 3–4. The path starts at vertex 0; path[0] = 0. At each position the vertices are tried in the order 0, 1, 2, ….
path[0] = 0, the other positions are −1 (empty).- Position 1: vertex 1 is adjacent to 0;
path[1] = 1. - Position 2: the neighbors of 1 are 0, 3, and 4. 0 is on the path; the first suitable vertex is 3.
path[2] = 3. - Position 3: the neighbors of 3 are 1, 2, and 4. The first suitable vertex is 2.
path[3] = 2. - Position 4: the neighbors of the last vertex, 2, are 0 and 3; both are on the path. Dead end. Vertex 2 is removed.
- Position 3: the next suitable vertex is 4.
path[3] = 4. - Position 4: the neighbors of 4, namely 1 and 3, are on the path. Dead end. Vertex 4 is removed.
- Position 3: vertex 3 has no untried neighbor left. Vertex 3 is removed too.
- Position 2: the next suitable neighbor of 1 is 4.
path[2] = 4. - Position 3: the neighbor of 4 that is not on the path is 3.
path[3] = 3. - Position 4: the neighbor of 3 that is not on the path is 2.
path[4] = 2. The path has reached five vertices.
4.7.2Java code
boolean find(int[][] g, int[] path, int pos) {
if (pos == g.length) return true;
for (int v = 0; v < g.length; v++) {
if (canExtend(v, g, path, pos)) {
path[pos] = v;
if (find(g, path, pos + 1)) return true;
path[pos] = -1; // undo
}
}
return false;
}
boolean canExtend(int v, int[][] g,
int[] path, int pos) {
if (g[path[pos - 1]][v] == 0) return false;
for (int i = 0; i < pos; i++)
if (path[i] == v) return false;
return true;
}g is the adjacency matrix; g[u][v] == 1 means there is an edge between u and v. The calling code fills the path array with −1, sets path[0] = 0, and calls find(g, path, 1). pos == g.length is the goal test: the path has n vertices. The loop tries every vertex as a candidate. canExtend checks the two constraints. The first line checks whether the candidate is adjacent to the last vertex, that is, to path[pos − 1]. The loop scans whether the candidate is already on the path. The undo line is path[pos] = -1.
Here too the observation from the permutation code applies: the undo line is not essential for correctness. canExtend looks only at path[0..pos − 1], and the old value in path[pos] is overwritten in the next attempt. Even so, writing −1 keeps the state clean and makes debugging easier.
The cost analysis is similar to permutations. Each position of the path is one of the remaining vertices; in the worst case (n − 1)! orders are tried. At each node, for n candidates, canExtend takes O(n). The crude bound is O(n · n!). If membership in the path is kept in a boolean array, canExtend drops to O(1).
4.7.3Code trace: the second graph
Let us trace the code on a second graph. It has five vertices and six edges: 0–1, 0–2, 1–2, 1–3, 2–3, and 2–4. The only neighbor of vertex 4 is 2. So vertex 4 can be on a Hamiltonian path only at an end.
find(g, path, 1) has been called with path[0] = 0; at position 1 the first vertex adjacent to 0, vertex 1, has been chosen.| Position | Last vertex | Decision | path |
|---|---|---|---|
| 1 | 0 | 0 is on the path; first suitable is 1 | [0, 1, −1, −1, −1] |
| 2 | 1 | first suitable is 2 | [0, 1, 2, −1, −1] |
| 3 | 2 | first suitable is 3 | [0, 1, 2, 3, −1] |
| 4 | 3 | the neighbors of 3, namely 1 and 2, are on the path; dead end, 3 is removed | [0, 1, 2, −1, −1] |
| 3 | 2 | next suitable is 4 | [0, 1, 2, 4, −1] |
| 4 | 4 | the only neighbor of 4, vertex 2, is on the path; dead end, 4 is removed | [0, 1, 2, −1, −1] |
| 3 | 2 | no candidates left; dead end, 2 is removed | [0, 1, −1, −1, −1] |
| 2 | 1 | next suitable is 3 | [0, 1, 3, −1, −1] |
| 3 | 3 | first suitable is 2 | [0, 1, 3, 2, −1] |
| 4 | 2 | first suitable is 4 | [0, 1, 3, 2, 4] |
| 5 | — | pos == n, true | Hamiltonian path 0 → 1 → 3 → 2 → 4 |
In the trace the algorithm does not know that vertex 4 can be only at an end. It tries 3 after 2, and then 4. Both attempts end in dead ends. A person looking at this graph says, “4 must be the last vertex, and 2 the one before it,” and narrows the search at once. Reasoning of this kind can be turned into pruning rules. For example, if a vertex not on the path has no neighbor off the path and is not adjacent to the last vertex either, the branch can be cut at once.
4.7.4Hamiltonian cycle
To search for a Hamiltonian cycle, the only change in the code is in the goal test. When the path reaches n vertices, we also check whether the last vertex is adjacent to the starting vertex.
boolean cycle(int[][] g, int[] path, int pos) {
if (pos == g.length)
return g[path[pos - 1]][path[0]] == 1; // last adjacent to start?
for (int v = 0; v < g.length; v++) {
if (canExtend(v, g, path, pos)) {
path[pos] = v;
if (cycle(g, path, pos + 1)) return true;
path[pos] = -1; // undo
}
}
return false;
}If the goal test returns false, the search continues; this path has not closed into a cycle, and other paths are tried. In the first example graph, the last vertex of the path 0 → 1 → 4 → 3 → 2, vertex 2, is adjacent to the starting vertex 0. So cycle finds the same path and yields a Hamiltonian cycle closed by the edge 2 → 0. The second graph has no Hamiltonian cycle. Vertex 4 has only one neighbor; in a cycle each vertex uses two neighbors. cycle traverses the whole tree and returns false.
Looking only at the test pos == n when searching for a Hamiltonian cycle. This test finds a Hamiltonian path. If it is not checked separately that the last vertex is adjacent to the first, the path 0 → 1 → 3 → 2 → 4 in the second graph is wrongly taken to be a cycle.
4.8Word search
4.8.1The problem
A word is searched for in a grid of letters. The word must be read along a path through adjacent cells. Adjacency is four-directional: up, down, left, and right. A cell may be used at most once in the same path. The question is: is there such a path that spells the word?
The example grid has three rows: ABCE, SFCS, and ADEE. Let the word searched for be “SEE.” Every cell is tried in turn as the starting point. The neighboring directions are tried in the order up, down, left, right.
- (1, 0) = 'S' matches the first letter of the word and is marked as visited. Its neighbors are A, A, and F; none is 'E'. We backtrack and the mark is removed.
- (1, 3) = 'S' matches and is marked. Its upper neighbor (0, 3) = 'E' matches and is marked.
- The neighbors of (0, 3): above is outside the grid, below is (1, 3), which is visited, left is (0, 2) = 'C', right is outside the grid. The third letter cannot be found; the mark is removed.
- The lower neighbor of (1, 3), (2, 3) = 'E', matches and is marked.
- The left neighbor of (2, 3), (2, 2) = 'E', matches. The last letter matches too: “SEE” is found.
4.8.2Java code
boolean search(char[][] g, String word, int i,
int r, int c, boolean[][] seen) {
if (i == word.length()) return true;
if (r < 0 || r >= g.length || c < 0
|| c >= g[0].length || seen[r][c]
|| g[r][c] != word.charAt(i))
return false;
seen[r][c] = true;
for (int d = 0; d < 4; d++)
if (search(g, word, i + 1, r + dr[d],
c + dc[d], seen))
return true;
seen[r][c] = false; // undo
return false;
}search tells whether the part of the word after its i-th letter can be found starting from cell (r, c). i == word.length() is the goal test: all the letters have matched. The second if rejects three cases at once: the cell is outside the grid, it has already been used on this path, or its letter is not the expected one; then false is returned. This is a style in which the constraint test is made at the start of the recursive call. In the n-queens code, by contrast, the test was made before the call, with isSafe. Both styles do the same pruning.
A cell that passes the tests is marked (choose). search is called for the four neighbors with the next letter (explore). dr and dc are the direction arrays. If one of the neighbors succeeds, true is passed straight up. If none succeeds, the mark is removed (unchoose) and false is returned. The outer code tries every cell as the starting point:
int[] dr = {-1, 1, 0, 0}; // up, down, left, right
int[] dc = {0, 0, -1, 1};
boolean exists(char[][] g, String word) {
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++) {
boolean[][] seen = new boolean[g.length][g[0].length];
if (search(g, word, 0, r, c, seen))
return true;
}
return false;
}There is a reason the goal test comes before the boundary check. If the last letter of the word matches in a cell on the edge of the grid, some of the four neighbor calls fall outside the grid. But in these calls i already equals the length of the word, and the first line returns true. If the order were reversed, two problems would arise. The calls falling outside the grid would return false. The calls inside the grid would try to read beyond the end of the word with word.charAt(i) and throw an exception. For example, in a one-cell grid a one-letter word could never be found.
| Word | Result | Path or reason |
|---|---|---|
| ABCCED | found | (0, 0) A → (0, 1) B → (0, 2) C → (1, 2) C → (2, 2) E → (2, 1) D |
| SEE | found | (1, 3) S → (2, 3) E → (2, 2) E |
| ABCB | not found | B cannot be used twice |
| SADE | found | (1, 0) S → (2, 0) A → (2, 1) D → (2, 2) E |
The search for “SADE” also involves a backtrack. From the S at (1, 0), the A above, at (0, 0), is tried first. The neighbors of this A are B, S (visited), and outside the grid; 'D' cannot be found. The mark is removed and the A below, at (2, 0), is tried. From there, with (2, 1) = 'D' and (2, 2) = 'E', the word is completed.
4.8.3Code trace: “ABCB”
The word “ABCB” is not in the grid, but to see why, the search must be traced. The search starts at (0, 0).
- (0, 0) = 'A' = word[0]. The cell is marked.
- word[1] = 'B' is sought. Up is outside the grid, down (1, 0) = 'S' ≠ 'B', left is outside the grid. The cell to the right, (0, 1) = 'B', matches and is marked.
- word[2] = 'C' is sought. Up is outside the grid, down (1, 1) = 'F' ≠ 'C', left (0, 0) is visited. The cell to the right, (0, 2) = 'C', matches and is marked.
- word[3] = 'B' is sought. Up is outside the grid, down (1, 2) = 'C' ≠ 'B', left (0, 1) is visited, right (0, 3) = 'E' ≠ 'B'. All four directions fail. The only B in the grid is at (0, 1), and it has been used on this path.
- Undo for (0, 2):
seen[0][2] = false,falseis returned. - The remaining directions of (0, 1) and (0, 0) fail as well. The marks of both are removed.
search(…, 0, 0, 0, …)returnsfalse. - The outer loop tries the other cells. The only other cell starting with A is (2, 0); its neighbors are S, D, and outside the grid, and there is no B. “ABCB” is not in the grid.
For the cost, let the length of the word be L and the dimensions of the grid R × C. Every cell is a starting point. After the first letter there are at most 3 new directions at each step, because the cell we came from is visited. So the number of paths traversed from one starting point is bounded by O(3L) and the total time is O(R · C · 3L). Memory is O(R · C) for the seen array and O(L) for the stack. In practice, letter matching cuts the search very early; the search for “ABCB” marks only 4 cells.
Not removing the visited mark when backtracking. If the mark stays, cells passed through in a failed attempt look “used” in later attempts. In the search for “SADE”, even if the mark on the A at (0, 0) stayed after it was tried and abandoned, the result would not change. But if the S at (1, 0) stayed marked and the word needed to use this S on another path, a word that exists would not be found. The correct order is: the cell is marked first, then the neighbors are explored, and finally the mark is removed.
4.9Other applications
4.9.1Subset sum
Given a set of positive integers and a target value, is there a subset whose sum is exactly the target? This question is the subset sum problem, and its decision version is NP-complete. This time the state-space tree is a binary tree. At level i there are two options for the i-th item: it is taken or it is not. For n items the tree has 2n leaves; each leaf is a subset.
int[] a = {3, 5, 6, 7};
int TARGET = 15;
boolean[] chosen = new boolean[a.length];
boolean subset(int i, int sum) {
if (sum == TARGET) return true;
if (i == a.length || sum > TARGET) return false; // prune
chosen[i] = true; // take
if (subset(i + 1, sum + a[i])) return true;
chosen[i] = false; // skip
return subset(i + 1, sum);
}subset(i, sum) is called when the first i items have been decided and the sum of those chosen is sum. If the target has been reached, true is returned. If no items are left or the sum has exceeded the target, false is returned. The second condition is the pruning: because the items are positive, once the sum has exceeded the target it can never decrease again. Then the two branches are tried in turn. First the i-th item is taken; if this branch fails, the item is left out and the second branch is tried. In this code sum, which is part of the partial solution, is passed by value, so no undo is needed for it. Only the chosen array is undone.
| # | Call | Meaning | Result |
|---|---|---|---|
| 1 | subset(0, 0) | root | descends into the branch that takes 3 |
| 2 | subset(1, 3) | 3 was taken | descends into the branch that takes 5 |
| 3 | subset(2, 8) | 5 was taken | descends into the branch that takes 6 |
| 4 | subset(3, 14) | 6 was taken | descends into the branch that takes 7 |
| 5 | subset(4, 21) | 7 was taken | 21 > 15: pruned, false |
| 6 | subset(4, 14) | 7 was not taken | no items left, 14 ≠ 15: false |
| 7 | subset(3, 8) | 6 was not taken | descends into the branch that takes 7 |
| 8 | subset(4, 15) | 7 was taken | sum == TARGET: true |
The search ends in 8 calls and chosen = [true, true, false, true]: the subset found is {3, 5, 7}. The whole tree has 25 − 1 = 31 nodes. Call 5 is where the pruning acts: the sum of 3, 5, 6, and 7 is 21, which exceeds the target.
This pruning cuts only “excess” sums. A pruning in the opposite direction is also possible: if the target cannot be reached even by taking all the remaining items, the branch is cut. For this, remaining[i], the sum of the items from the i-th to the end (a suffix sum), is computed in advance, and the following line is added:
if (sum + remaining[i] < TARGET) return false;Question. Let the target be 22 in the same set. How many calls does subset(0, 0) make without and with the remaining-sum pruning?
Solution. The sum of the items is 3 + 5 + 6 + 7 = 21; no subset can reach 22. In the code without the extra pruning, no sum exceeds 22, so the “excess” pruning never fires. The search traverses all 31 nodes of the tree and returns false. With the remaining-sum pruning, in the first call 0 + remaining[0] = 21 < 22. The search ends in a single call. When the target in the same set is 15, on the other hand, the search makes 8 calls in both versions; the pruning does not help in this example. The gain from pruning always depends on the input.
4.9.2Other problems solved by backtracking
The template can be adapted to a large number of problems. In each adaptation two questions are answered: what choice is made at each level, and when is a branch cut?
| Problem | Choice at each level | Pruning (constraint) |
|---|---|---|
| Subset sum / knapsack | take the i-th item or not? (2 branches) | the sum or the weight limit is exceeded |
| Traveling salesman (TSP) | the next city | the path is longer than the best known tour |
| Bin packing | which bin does the item go in? | the bin capacity is exceeded |
| Maximum coverage | pick the set or not? | no improvement is possible with the remaining sets |
| Boolean satisfiability (SAT) | is the variable true or false? | a clause has become false |
| Minesweeper | is the cell a mine? | a contradiction with the revealed numbers |
| Permutation / combination generation | the next item | the item is already used |
Some of the problems in the table are decision or counting problems and some are optimization problems. In traveling salesman and knapsack the goal is not a solution but the best solution. For these problems a second kind of pruning is added next to constraint pruning. The best solution found so far is stored during the search. If the best value a branch can reach is worse than the best known solution, the branch is cut. In traveling salesman, if the length of a partly built tour already exceeds the best known tour, there is no need to complete it. This idea is the basis of the branch and bound method.
The SAT row is also important. The foundation of the SAT solvers used today is backtracking too: values are given to the variables in turn, and when a clause becomes false we backtrack. Modern solvers add unit propagation, conflict-driven learning, and smart variable ordering to this skeleton. In this way they can solve industrial formulas with millions of variables.
4.10Analysis
4.10.1Complexity
The running time of a backtracking algorithm is the product of two factors:
Time = number of nodes visited in the state-space tree × work per node
The work per node is usually polynomial: a constraint test, a copy, a printout. The number of nodes depends on the shape of the tree. If there are b branches at each level and d levels, the tree has at most bd leaves. If the number of options shrinks as the level increases (as with permutations), the number of leaves grows like n!.
| Problem | Worst-case time | Explanation |
|---|---|---|
| n-queens | O(n2 · n!) | O(n!) nodes × n columns × isSafe at O(n) |
| Sudoku | O(9m) | m: number of empty cells; 9 candidates in each cell |
| Graph m-coloring | O(n · mn) | n vertices, m colors each; the check is O(n) or O(degree) |
| Hamiltonian path | O(n · n!) | the remaining vertices for each position on the path |
| Word search | O(R · C · 3L) | at most 3 new directions after the first letter |
| Subsets / permutations | O(2n) / O(n · n!) | number of leaves in the tree |
These bounds do not take pruning into account. Pruning often shrinks the number of nodes a great deal, but it usually does not change the worst case. Bad inputs can always be constructed on which pruning never acts. For example, a subset sum input in which no subset reaches the target and the sums never exceed the target makes the search traverse the whole tree.
In terms of memory, backtracking is very economical. Only a single partial solution and the frames on the call stack are kept at any time. The depth of the stack equals the depth of the tree: n in n-queens, m in Sudoku, L in word search. So memory is O(depth) plus the size of the partial solution itself. However wide the tree may be, memory does not change. Compared with methods that search breadth-first, this is an important advantage.
Question. If brute force tested the 88 complete placements for 8 queens, and each test compared 28 pairs of queens, how many comparisons would be made? How many isSafe calls does backtracking make for the first solution?
Solution. 16,777,216 × 28 = 469,762,048 pair comparisons, that is, about 470 million operations, would be needed. Backtracking calls isSafe 876 times up to the first solution, and each call looks at no more than 3 · 8 = 24 cells. The upper bound is 876 × 24 = 21,024 cell reads. The difference is more than four orders of magnitude.
4.10.2Heuristics that strengthen pruning
The speed of backtracking depends on two things: how much of the tree is pruned and how long each node takes. The techniques seen in these notes shrink these two factors.
- Variable ordering (MRV). The variable with the fewest options left is filled first. Contradictions appear early and the branching stays small. In the example Sudoku the number of backtracks falls from 4157 to 0.
- Value ordering. Among the values of a variable, the least constraining value is tried first. This is the counterpart in backtracking of the idea behind min-conflicts. Value ordering does not reduce the work when all solutions are searched for, but the first solution is found earlier. Changing the direction order in the maze reduced the number of dead-end cells from 8 to 0.
- Forward checking. After an assignment, conflicting values are removed from the domains of neighboring variables. If some variable's domain becomes empty, we backtrack at once. In this way a dead end is noticed before that variable's turn comes.
- Fast constraint tests. In n-queens, column and diagonal flags are used; in Sudoku, bit masks for rows, columns, and boxes. The test drops from O(n) to O(1).
- Symmetry breaking. Only one of the symmetric solutions is searched for. In n-queens the first queen is tried only in the left half and the solutions found are reflected: for 8 queens the number of placements falls from 2056 to 1028. In graph coloring the color of the first vertex is fixed.
- Bounding. In optimization, if the best value a partial solution can reach is worse than the best known solution, the branch is cut. This is the branch and bound method.
These techniques share a lesson: the cost of a search depends less on the size of the space searched than on how the search is organized. A space of size 951 is solved in 51 steps with the right cell order.
4.10.3What sets backtracking apart?
The place of backtracking is better understood when it is compared with the other algorithm design methods of the course.
| Method | Idea | Difference from backtracking |
|---|---|---|
| Divide and conquer | Split into independent subproblems, combine | No choosing and trying; each subproblem is solved exactly once |
| Greedy | Locally best at every step; no turning back | Follows a single branch; a wrong choice cannot be corrected |
| Dynamic programming | Solve overlapping subproblems once and store them | All options are tried but the results are kept in a table; the number of subproblems must be polynomial |
| Backtracking | Extend the partial solution, undo it if invalid | Choices are tried and undone; constraint satisfaction, all solutions, decision problems |
The comparison with the greedy method is instructive. A greedy algorithm follows a single path from the root to a leaf of the state-space tree. At each node it descends to the child that looks best and never turns back. Backtracking does a depth-first search of the same tree. If a greedy choice is wrong, backtracking notices it and corrects it. The greedy start of min-conflicts shows this: the start is almost correct, but repair is still needed to resolve a single conflict.
The comparison with dynamic programming is also important. Both methods try all the options. The difference is whether the subproblems are stored. In subset sum the same pair (i, sum) can arise several times along different paths. For example, in the set {1, 2, 3, 4}, after the first four decisions the choices {1, 4} and {2, 3} give the same sum, 5. Backtracking solves this pair from scratch every time. Dynamic programming stores the result in a table. If the target is small, dynamic programming runs in O(n · TARGET) time. But in problems like n-queens or Hamiltonian path, the state that defines a subproblem is the set of columns used or of vertices visited. The number of such sets is exponential and a table stops being practical.
In short, backtracking is a depth-first search of the state-space tree. The tree is not built in advance; it is generated as it is traversed. Invalid branches are never generated.
4.11Common mistakes
Backtracking code is short, but small mistakes lead to very different results. Each of the mistakes below is treated in detail somewhere in these notes.
Forgetting to undo. If b[r][c] = 0 or seen[r][c] = false is not done on returning from the recursion, the old choice corrupts the later branches. In n-queens the board fills up with the queens of earlier attempts, and valid columns are wrongly rejected.
Not propagating the result. If only solve(...) is written instead of if (solve(...)) return true;, the search continues even after a solution is found, and the board is undone. The program shows an empty board even though it has found a solution.
An early return false. Leaving the loop at the first invalid candidate. If if (!isSafe(...)) return false; is written, the remaining columns are never tried. With 4 queens, when column 0 is rejected in row 1, the method returns and column 2 is never tried.
Storing the shared list. When collecting all solutions, a copy, new ArrayList<>(path), must be added instead of results.add(path). Otherwise the list fills with references that point to the same object.
An incomplete constraint check. Forgetting to check one of the diagonals in n-queens, or the 3 × 3 box in Sudoku. The algorithm quickly finds a “solution,” but the placements it finds are invalid.
Taking local search to be complete. Min-conflicts cannot prove that there is no solution. Reaching the step limit does not mean “no solution.” For a definite “no” answer, a backtracking search that traverses the whole tree is needed.
4.12Summary
- Hard problems: P consists of the decision problems solved in polynomial time, NP of those verified in polynomial time. NP-complete problems are both in NP and NP-hard. If P ≠ NP, these problems have no polynomial-time exact algorithm; the known exact algorithms take exponential time in the worst case, and the aim is to shrink the search by pruning.
- The idea: the solution is built step by step as a partial solution. If a candidate violates a constraint, that branch is abandoned; if no candidate is left at a step, the last decision is undone and the next candidate is tried. No extension of an invalid partial solution is ever generated.
- The template: a goal test, then for each candidate: if valid, choose, recurse, unchoose. For a single solution a
booleanis returned andtrueis passed up; for all solutions, count at the goal and returnfalse. - State-space tree: partial solutions are the nodes and choices are the edges. Backtracking is a depth-first search of this tree; the tree is generated as it is traversed, and pruning skips invalid subtrees.
- n-queens: queens are placed row by row; the column and the two diagonals are checked. For 4 queens the first solution is [1, 3, 0, 2] (8 placements, 4 backtracks); for 8 queens there are 92 solutions, and the first is [0, 4, 7, 5, 2, 6, 1, 3] (113 placements, 105 backtracks). With flags (r + c, r − c + n − 1) the safety test becomes O(1).
- Min-conflicts: start from a complete placement and move a conflicted queen to the row with the fewest conflicts. It is fast but not complete: it can wander on plateaus and cannot prove that no solution exists.
- Sudoku: 1–9 are tried in an empty cell; the row, column, and box are checked. In row-by-row order the example puzzle needs 4208 placements and 4157 undos; with MRV, 51 placements and 0 undos.
- Other applications: graph coloring (color constraint, O(n · mn)), Hamiltonian path and cycle (adjacency and repetition constraints, O(n · n!)), word search (undoing the visited mark, O(R · C · 3L)), subset sum (a binary take/skip tree, pruning of excess and insufficient sums).
- Cost: time is the product of the number of nodes visited and the work per node; the worst case is exponential (2n, n!, 9m). Memory is only O(depth). Variable and value ordering, forward checking, fast constraint tests, and symmetry breaking shrink the tree that is visited.
4.13Key terms
- backtracking
- partial solution
- pruning
- state-space tree
- brute force
- depth-first search (DFS)
- decision problem
- polynomial time
- reduction
- NP-hard
- NP-complete
- N-queens problem
- min-conflicts heuristic
- local search
- heuristic
- constraint satisfaction problem
- minimum remaining values (MRV)
- forward checking
- graph coloring
- Hamiltonian path
- subset sum
- lexicographic order
- branch and bound
4.14Test Yourself
The permutation code is called as
permute(new int[4], new boolean[5], 0). Which is the 7th permutation printed? How many times is “choose” done during the search?Answer
The permutations come out in lexicographic order: [1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], and the 7th is [2, 1, 3, 4]. The number of chooses is the number of non-root nodes of the tree: 4 + 12 + 24 + 24 = 64.
A search generates the subsets of a four-element set by “take / skip” decisions. How many nodes (counting the root) and how many leaves does its state-space tree have?
Answer
The number of nodes doubles at each level: 1 + 2 + 4 + 8 + 16 = 31 nodes. The number of leaves is 24 = 16; each leaf is a subset.
For n = 4 in the flag version, the queens are at squares (0, 1) and (1, 3). Which cells of
cols,d1, andd2aretrue? Are the squares (2, 0) and (2, 2) safe?Answer
cols[1],cols[3];d1[1],d1[4];d2[0 − 1 + 3] = d2[2],d2[1 − 3 + 3] = d2[1]. For (2, 0),cols[0],d1[2], andd2[5]are empty: safe. For (2, 2),d1[4]is occupied: it is on the same anti-diagonal as (1, 3), so it is not safe.For n = 6,
solve(b, 0)places 31 queens before it finds the first solution. How many undos are made? Why does the first solution not start with column 0?Answer
Every placement is either undone or stays in the solution; the solution has 6 queens. 31 − 6 = 25 undos are made. None of the four solutions of the 6-queens problem uses column 0 in row 0. All the branches starting with column 0 end in dead ends, and the lexicographically first solution is [1, 3, 5, 0, 2, 4].
On a 4 × 4 board,
queen = [1, 3, 0, 0](queen[k]is the row of the queen in column k). Column 2 is chosen for repair. What are the conflict counts of this queen for rows 0–3? Does moving it to the row with the smallest value solve the problem?Answer
The counts are 1, 2, 1, 2. Row 0 is the queen's current position (the same row as column 3). Row 2 also has 1 conflict: it is on the same diagonal as (3, 1). If the queen is moved to row 2,
queen = [1, 3, 2, 0]and this time columns 1 and 2 conflict; the number of conflicting pairs is again 1. This is a plateau. Had column 3 been chosen, the counts would have been 1, 3, 0, 1, and moving the queen to row 2 would have given the solution [1, 3, 0, 2].In the example Sudoku puzzle, which rows and columns does the box of cell (4, 7) cover? What are the candidates of this cell at the start?
Answer
4 / 3 · 3 = 3, 7 / 3 · 3 = 6: the box is rows 3–5 and columns 6–8. Row 4 contains 4, 8, 3, 1; column 7 contains 6, 8, 7; the box contains 3, 1, 6. The unused digits are 2, 5, and 9. In the solution, 9 is written in the cell.
The graph with edges 0–1, 1–2, 2–0, and 2–3 is colored with
colorGraph(0)using m = 2 and m = 3 colors. What are the results?Answer
Vertices 0, 1, 2 form a triangle; all three are adjacent to each other and two colors are not enough. For m = 2 the search traverses the whole tree and returns
false. For m = 3 the first attempt finds [1, 2, 3, 1]: the only neighbor of vertex 3 is 2 (color 3), so color 1 is suitable.In a star graph with vertex 0 at the center and vertices 1, 2, and 3 connected only to the center, what does
find(g, path, 1)return? Would another starting vertex change the result?Answer
false. When we go from 0 to 1, vertex 1 has no neighbor that is not on the path; the same happens for 2 and 3. Changing the starting vertex does not help either: a path has at most two end vertices, but this graph has three vertices of degree 1. There is no Hamiltonian path.Do the words “ASFB” and “ECE” occur in the grid ABCE / SFCS / ADEE?
Answer
“ASFB” does occur: (0, 0) A → (1, 0) S → (1, 1) F → (0, 1) B. “ECE” does not. The letter C is at (0, 2) and (1, 2). The only E neighbor of (0, 2) is (0, 3); it was used at the start of the path. The only E neighbor of (1, 2) is (2, 2); if the path starts there, no other neighbor is left for the second E. In both cases an E cell would have to be used twice.
For
a = {2, 4, 5, 9}and target 13, which subset does the subset sum search (taking first) find? How does the number of calls change if remaining-sum pruning is added?Answer
All the branches starting with 2 fail: 2 + 4 + 5 = 11, and adding 9 gives 20; 2 + 4 + 9 = 15; 2 + 5 + 9 = 16; 2 + 9 = 11. Then 2 is skipped and 4 is taken. Adding 9 to 4 + 5 = 9 gives 18 and the branch is pruned. When 5 is skipped and 9 is taken, 4 + 9 = 13 is found. The result is {4, 9}. The code without pruning makes 23 calls, and the code with remaining-sum pruning makes 21; the gain is small, because most sums exceed the target and are pruned anyway.
4.15Further reading
- A. Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed., chapter 12: presents backtracking and branch and bound within the same framework. It works through the n-queens, Hamiltonian cycle, and subset sum examples.
- S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed., chapter 6: treats constraint satisfaction problems, MRV, forward checking, and the min-conflicts heuristic in detail.
- D. E. Knuth, The Art of Computer Programming, Volume 4B: gives the history of backtrack programming, methods for estimating its cost, and the “dancing links” technique.
- S. W. Golomb and L. D. Baumert, “Backtrack Programming” (1965): one of the first papers to describe the method as a general programming technique.
4.16References
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
- A. Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed., Pearson, 2012 (chapter 12: Backtracking).
- S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed., 2020 (chapter 6: constraint satisfaction, min-conflicts).
- S. Minton, M. D. Johnston, A. B. Philips, and P. Laird, “Minimizing Conflicts: A Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems”, Artificial Intelligence 58, 1992.
- D. E. Knuth, The Art of Computer Programming, Volume 4B, Addison-Wesley, 2022 (Backtrack programming, Dancing Links).
- S. W. Golomb and L. D. Baumert, “Backtrack Programming”, Journal of the ACM 12(4), 516–524, 1965.
- S. A. Cook, “The Complexity of Theorem-Proving Procedures”, Proceedings of the 3rd ACM Symposium on Theory of Computing (STOC), 151–158, 1971.