This chapter is from the book
This chapter is from the book
This chapter is from the book
Contents
Preface
Notes on the Exercises
Mathematical Preliminaries Redux
Inequalities
Martingales
Tail inequalities from martingales
Applications
Statements that are almost sure, or even quite sure
Exercises
Chapter 7 — Combinatorial Searching
7.2. Generating All Possibilities
7.2.1. Generating Basic Combinatorial Patterns
7.2.2. Backtrack Programming
Data structures
Walker’s method
Permutations and Langford pairs
Word rectangles
Commafree codes
Dynamic ordering of choices
Sequential allocation redux
Lists for the commafree problem
A general mechanism for doing and undoing
Backtracking through commafree codes
Running time estimates
*Estimating the number of solutions
Factoring the problem
Historical notes
Exercises
7.2.2.1. Dancing links
Exact cover problems
Secondary items
Progress reports
Sudoku
Polyominoes
Polycubes
Factoring an exact cover problem
Color-controlled covering
Introducing multiplicity
*A new dance step
*Analysis of Algorithm X
*Analysis of matching problems
*Maintaining a decent focus
Exploiting local equivalence
*Preprocessing the options
Minimum-cost solutions
*Implementing the min-cost cutoffs
*Dancing with ZDDs
Summary
Historical notes
Exercises—First set
Exercises—Second set
Exercises—Third set
7.2.2.2. Satisfiability
Example applications
Backtracking algorithms
Random clauses
Resolution of clauses
Clause-learning algorithms
Monte Carlo algorithms
The Local Lemma
*Message-passing algorithms
*Preprocessing of clauses
Encoding constraints into clauses
Unit propagation and forcing
Symmetry breaking
Satisfiability-preserving maps
One hundred test cases
Tuning the parameters
Exploiting parallelism
History
Exercises
Answers to Exercises
Appendix A — Tables of Numerical Quantities
1. Fundamental Constants (decimal)
2. Fundamental Constants (hexadecimal)
3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers
Appendix B — Index to Notations
Appendix C — Index to Algorithms and Theorems
Appendix D — Index to Combinatorial Problems
Appendix E — Answers to Puzzles in the Answers
Index and Glossary
We — or the Black Chamber — have a little agreement with [Knuth];
he doesn’t publish the real Volume 4 of The Art of Computer Programming,
and they don’t render him metabolically challenged.
— CHARLES STROSS, The Atrocity Archive (2001)
In books of this nature I can only suggest you keep it
as simple as the subject will allow.
— KODE VICIOUS (2012)