Sparse set XCC solver in Go based on Donald Knuth's Dancing Cells presented in the 27th Annual Christmas Tree Lecture.
The solver takes:
- a set of primary items;
- a set of secondary items;
- a set of options, which are subsets of the primary and secondary items.
The solver’s job is to find a subset of the options that
- includes each primary item once and only once, and
- colors each secondary item consistently. Options can contain secondary items with or without colors. If a secondary item has no color, then the solver will not use it more than once (so that it defines a “zero or one” constraint). If an option has a secondary item with a color, then the solver can use it with the same color as many times as it wants, but not uncolored or with a different color.
p q r
x y
p q x y:A
p r x:A y
p x:B
q x:A
r y:B
It's an extension of the "exact cover" problem -- you're given a set of items that should be covered, and a set of options (sets of items) that may cover some items. Items are divided into two groups:
- Primary: these items need to be covered exactly once.
- Secondary: these items may be either uncovered, or have possibly-many covering options, but the "color" of the coverings must be the same.
Here you can find a more detailed explanation of XCC problems, however, they do not use the "exact covering with colors" used by Knuth.
ToDo: find a better reference, perhaps a link to The Art of Computer Programming book.
A sparse set is a simple data structure that has following properties:
- O(1) to add an item.
- O(1) to remove an item.
- O(1) to lookup an item.
- O(1) to clear the set.
- O(n) to iterate over the set.
- Does not require initializing its internal items storage.
Solving this problem on its own is an interesting programming exercise. For more information refer to these two blog posts:
- Sparse sets by Oleksandr Manenko
- Using Uninitialized Memory for Fun and Profit by Russ Cox Also this sparse set implemented in Go can be useful to Go programmers.