Home
TOC

TAOCP Notes: Algorithm Backtracking

These are my reading notes for TAOCP Vol. 4, a brief extension of my reflections after reading the book, accompanied by the code I wrote to deepen my understanding.

Boolean Basics

Section 7.1.1 examines two specialized functions: Horn (see code) and Krom (see code). Due to their unique structures, the satisfiability of both functions can be determined using linear-time algorithms. A closer analysis reveals the inherent beauty of these approaches; by utilizing elegant data structures—such as linked lists for pending variable assertions and strongly connected component (SCC) graphs for 2-SAT relationships—the deduction proceeds through a series of graceful logical steps, leveraging precise information to reach a definitive conclusion.

Optimization The implementation for the Krom function is structured in two distinct stages: first, it invokes Algorithm T (Section 7.4.1.2) to identify all strongly connected components; this is followed by an efficient verification procedure—as outlined in Exercise 54—to determine satisfiability. A key optimization involves checking whether a variable and its complement coexist within the same component. Specifically, within step T8 (see T8), as each new strongly connected component is identified, the initial node is recorded as \(u_1\) (per Exercise 54, page 86), allowing for an in-place validation of all nodes within that specific component.

Basic Backtrack

On Section 7.2.2 (Page 30 of Vol 4B), Algorithm B (the C++ code with goto can be found here) introduces a simple yet powerful backtracking scheme. It is built on properties \((1)\) and \((2)\): namely, that \(P_{l}\) holds whenever \(P_{l+1}\) holds. This monotonicity allows entire subtrees to be pruned during the search. A key characteristic of the algorithm is that, at each level, it systematically iterates over all values in the domain. While this exhaustive enumeration makes the algorithm conceptually simple and easy to reason about, it can result in a substantial amount of work during the search process.

To estimate runtime overhead effectively, memory access can serve as a reliable proxy. For improved code readability, a macro may be implemented to automate the tracking of these access counts.


#ifdef COUNTER
#define MEM_READ(p, i) (counter++, p[i])
#else
#define MEM_READ(p, i) p[i]
#endif

Similarly, a macro can be defined to track memory write operations, ensuring consistent monitoring across the codebase.

Optimization Optimizing the implementation to use registers (see code) instead of auxiliary data structures, such as the A, B, and C arrays, is an interesting direction that I explored. In theory, the memory access count, for \(N=16\) queens problem, should reduce from 34 billion mems to 9 billion mems; however, I did not find it to be sufficiently fast: 40 seconds for memory version vs 33 seconds register version (tested on Apple Silicon M4 Max with clang++17 and CXXFLAGS=-DNDEBUG -O3 -march=native -flto). My hypothesis is that all data already resides within cache lines, making the cost of memory reads and writes negligible.

In addition to C++, I implemented the register-based bit-vector version in Go and Rust. For Rust, I explored unsafe implementations, disabled bounds checking, and enabled aggressive inlining and native optimizations. The measured wall-clock runtimes are 33 seconds for C++, 47 seconds for Go, and 44 seconds for Rust. Implementing the algorithm in Rust presented unique challenges due to the language's lack of a goto statement. This necessitated a shift toward a structured programming model, leveraging recursive function calls in conjunction with iterative loops. In the original version, the X array functions as a set of lightweight stack frames, effectively managing state in a manner analogous to recursive function calls.

Walker's Backtrack Initially, it was surprising that Walker's method (Algorithm 7.2.2W, The Art of Computer Programming, Vol. 4A) would be recommended, given its higher memory access count. On the surface, both algorithms traverse same number of nodes in the branching tree. In fact, basic backtracking—leveraging register-stored states as seen in Algorithm B*—appears more efficient due to its significantly lower memory overhead.

However, post-optimization benchmarks reveal a stark contrast: Walker's Backtrack completed the task in 4.7 seconds, while Basic Backtrack required 33 seconds. Deep profiling explains this disparity: although node counts are comparable, Algorithm 7.2.2W employs aggressive pruning heuristics. This allows it to trigger backtrack branches only 400 million times, compared to the staggering 16.8 trillion backtrack operations executed by the basic backtrack 7.2.2B* algorithm.

Backtrack for \(N=16\) Queens
Profiling Basic Backtrack Walker's Backtrack
# of Mems 2'282'380'604 6'952'497'635
# of Nodes 1'141'190'302 1'141'190'302
# of Mems per Node 2 6.09
# of \(B_3^*\rightarrow B_4^*\) or \(W_3\rightarrow W_4\) 16'881'494'354 400'742'864
Wall time 33 seconds 4.7 seconds

Furthermore, by meticulously aligning my optimization strategy with the memory access counts reported in TAOCP, I was able to significantly reduce memory overhead. By refactoring the logic to carry state within registers across label jumps and implementing strategic early-exit conditions, I eliminated a substantial volume of redundant memory accesses. These refinements proved so effective that the resulting execution speeds actually surpassed the benchmark results documented in the text.

The efficiency gains stem from minimizing redundant data movement. Instead of a monolithic 'load-then-check' approach, the optimized logic performs a lightweight check of the backtrack conditions using minimal state. This early-jump mechanism (see the simple early-jump here) bypasses the heavy memory-load cycle whenever a branch can be pruned, allowing the implementation to outperform standard benchmarks by avoiding the primary bottleneck of state-restoration overhead.

Dancing Links

In Section 7.2.2.1 (Volume 4B, page 69), Algorithm X (see code) establishes the fundamental structure of the Dancing Links algorithm. This technique serves as a versatile framework, providing an efficient approach to solving a wide array of combinatorial problems. This implementation is driven by two primary insights:

Applying the Dancing Links algorithm to a practical example, such as Sudoku (see example code), is a highly rewarding exercise. It provides a clear demonstration of how to map complex problem constraints into the discrete items and options required by the framework.

Based on these observations, several potential improvements emerge:

Heuristic Optimization
Unlike a brute-force approach, a human solving Sudoku does not exhaustively test every possibility, even when backtracking is computationally "cheap." Instead, we identify strategic bottlenecks to effectively prune the search tree. While the Minimum Remaining Values (MRV) heuristic in X3 adopts this logic, there remains significant room for further optimization.
Data Structure Efficiency
While "undo" operations carry low overhead, they are not cost-free. The lazy data structures detailed in Section 7.2.2.2 and the sequentially allocated lists—referenced in (16)–(23) of Section 7.2.2—offer a more elegant and efficient implementation for managing these states.

Satisfiability

In Section 7.2.2.2, boolean Satisfiability (SAT) is studied. It is a well-established and rigorously studied framework. While mathematically intensive, it is a compelling field of study because it serves as a universal interface between high-level applications and algorithmic problem-solving. This abstraction allows innovations in the underlying solver to benefit a diverse range of applications simultaneously.

Example: Dependency Resolution Problem Let's see an interesting problem first (see source). The databases for all packages are as follows:

Package Dependencies
Package Versions
app0
sql0, 1, 2
threads0, 1, 2
http0, 1, 2, 3, 4
stdlib0, 1, 2, 3, 4

And we want to install app:0, which has dependencies sql, threads, http, and stdlib. Each dependency, as a package, might have its own dependencies; and dependencies are different for different versions.

For this case study, we also assume the dependency is recorded with a minimum version and a maximum version. For example,


              min,max
 app:0
   -  sql     0,  2
   -  threads 1,  1

means app:0 needs two dependencies sql and threads. Any version \(0, 1, 2\) of sql is OK, but only version \(1\) of threads is allowed for app:0.

With that, the entire dependency tree is as follows


             min,max                   min,max
app:0                       threads:1
  -  sql     2,  2            -  stdlib  2,  4
  -  threads 2,  2          threads:2
  -  http    3,  4            -  stdlib  3,  4
  -  stdlib  4,  4          http:0
sql:0                         -  stdlib  0,  3
sql:1                       http:1
  -  stdlib  1,  4            -  stdlib  0,  3
  -  threads 1,  1          http:2
sql:2                         -  stdlib  1,  4
  -  stdlib  2,  4          http:3
  -  threads 1,  2            -  stdlib  2,  4
threads:0                   http:4
  -  stdlib  2,  4            -  stdlib  3,  4

With all the problem setup now, we could map the problem into SAT (full code can be found here):

Package Versions are Variables
We assign one boolean variable for each \(\hbox{package}_{\hbox{version}}\) pair, where \(1\) means installed and \(0\) means not installed.
Version Ranges are Disjunctions
For \(\hbox{app}_0\) and one of its dependencies http (min:3, max:4), we can write a disjunction of all allowed versions, i.e., \[\hbox{http}_3 \vee \hbox{http}_4\] Then the fact either of them is installed (true) means the disjunction is true.
Dependencies are Implications
For \(\hbox{app}_0\) and one of its dependencies http, we express the dependency as \[\hbox{app}_0 \rightarrow \hbox{http}_3 \vee \hbox{http}_4\] which is equivalent to \[\overline{\hbox{app}_0} \vee \hbox{http}_3 \vee \hbox{http}_4.\]
Consistency
For sql with three versions \(0, 1, 2\), only one version is allowed to be installed, which can be expressed as \[ \overline{\hbox{sql}_0 \wedge \hbox{sql}_1} \wedge \overline{\hbox{sql}_0 \wedge \hbox{sql}_2} \wedge \overline{\hbox{sql}_1 \wedge \hbox{sql}_2} \] which is same as \[ (\overline{\hbox{sql}_0} \vee \overline{\hbox{sql}_1}) \wedge (\overline{\hbox{sql}_0} \vee \overline{\hbox{sql}_2}) \wedge (\overline{\hbox{sql}_1} \vee \overline{\hbox{sql}_2}) \]
The Root of the DAG
The final SAT problem is the conjunction of all terms above with \(\hbox{app}_0\) as \(1\) (the root).

Satisfiability by Watching Algorithm B (see code) is a particularly elegant optimization within this domain. In a clause consisting of a disjunction of literals, only one variable needs to be "watched" to monitor whether the clause is satisfied or at risk of becoming a conflict. This approach makes backtracking highly efficient, as the solver only needs to visit clauses containing the specific variable being unassigned, rather than scanning all clauses. Furthermore, if a watched literal becomes false, the solver can cheaply update the watch to another non-false literal. By leveraging the inherent structure of Conjunctive Normal Form (CNF), this mechanism significantly reduces the overhead of undo operations during search.

Components and Traversal

There is a distinct beauty in Algorithm 7.4.1.2T; it avoids the heavy-handedness of global scans in favor of a singular, elegant pass. By allowing the LOW value to cascade through the graph's hierarchy, the algorithm listens to the local state of each vertex to pinpoint the exact moment a component is born. It exemplifies the brilliance of an algorithm that makes 'smart' decisions not through complexity, but through the perfect placement of simple information.

Iterative DFS Upon closer inspection, Algorithm T follows an iterative Depth-First Search (DFS) structure characterized by precise stack management and explicit control flow jumps. This design ensures that all memory allocations, stores, and loads remain transparent. However, these advantages come with a trade-off: the algorithm requires rigorous engineering to maintain critical invariants. I have documented these invariants extensively within the codebase (see code) to ensure clarity and maintainability.

Recursive DFS In contrast, it is more common to conceptualize and implement this process using recursive function calls, as seen in the standard Wikipedia implementation (see pseudocode here). However, this approach carries the risk of stack overflow when processing large graphs and tends to obscure the inherent overhead of frequent function calls.