This chapter is from the book
This chapter is from the book
This chapter is from the book
Contents
Chapter 7—Combinatorial Searching
7.2. Generating All Possibilities
7.2.1. Generating Basic Combinatorial Patterns
7.2.2. Backtrack Programming
7.2.2.1. Dancing links
7.2.2.2. Satisfiability
7.2.2.3. Constraint satisfaction
Related models
*Statistical mechanics
A simple example
Automating automobiles
Line labeling in computer vision
Graph labeling
*Graceful digraphs
Graph embedding
*Supplemental labels and graphs
Special cases of subgraph isomorphism
Solving a CSP
Translating CSP to SAT
SAT encodings of general relations
Consistency
Efficiency
Representing the domains
*Dancing cells
*Dynamic variable ordering heuristics
*Maintaining XCC supports
Performance on benchmarks
*Sparse-set methods for MCC problems
Tractable families of CSPs
Implicational constraints
Max-closed constraints
CRC constraints
Polymorphisms
The indicator problem
NP-complete families of CSPs
*Polarities and clones
*The dichotomy theorem
*Exploiting a polymorphism
*Visiting all solutions
A brief history
For further reading
Exercises
Answers to Exercises
Index to Algorithms and Theorems
Answers to Puzzles in the Answers
Index and Glossary
I always thought Volume 4 was a myth, like the missing part of the Dead Sea scrolls.
— BILL GASARCH (blog post, 10 January 2008)
