Exact Covering with Colours
summary
Defines exact covering with color (XCC) that generalizes exact cover and CSPs, adds just a few dozen lines to an existing solver, and implements both dancing links and a new sparse-set variant called dancing cells. The new solver performs full-domain consistency, wins about two-thirds of tests often by 2–3×, supports multiplicities (MCC), and can produce ZDDs to count solutions; code and examples appear in Volume 4B and an online postscript draft.
AI-written summary · about
chapters (10)
- 0:00Intro
- 1:23Exact Covering
- 8:02Exact Covering with Colours
- 9:58Options and Items
- 15:51Current Draft
- 16:46Dancing Cells
- 18:16Forward Checking
- 19:51Full Domain Consistency
- 20:47Covering Matrix
- 21:41Summary
related talks
41mIntroduction to Constraint Programming
18mMaximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear(…)
31mIndexing the Extended Dyck-CFL Reachability for Context-Sensitive Program Analysis
01h 24mIntroduction to Constraint Logic Programming
38mThe Intensional-Extensional Problem in Probabilistic Databases
39mModel Counting Meets Distinct Estimation
44mEfficient Enumeration Algorithms via Circuits
01h 02mGaussian Free Fields and Computing the Cover Time