# What is the exact cover problem?

> Exact cover asks for a set of options that covers every item exactly once. Sudoku, pentominoes and N-queens as exact cover, and how to solve it.

**Exact cover**: An exact cover problem gives a set of items and a collection of options, each a subset of the items, and asks for options that together contain every item exactly once.

**Exact cover**: you have a set of **items** and a list of **options**, each option a subset of the items. Pick options so that every item is in exactly one picked option. It is NP-complete in general, and a surprising number of puzzles are exact cover in disguise.

## Sudoku as exact cover

A sudoku has 324 items: each cell must be filled (81), and each row, column and box must contain each digit (3 x 81). Each option is "put digit d in cell (r, c)", which covers four items: that cell, d in row r, d in column c and d in its box. A solution is exactly 81 options covering all 324 items once. Pentomino tilings work the same way with squares and pieces as items.

## Solving it

Knuth's Algorithm X backtracks: choose the item with the fewest remaining options, try each option that covers it, remove everything that conflicts, recurse. [Dancing links](https://cracked.guide/glossary/dancing-links) make the remove and restore steps constant time. It is the subject of [§7.2.2.1](https://cracked.guide/guide/knuth-w119-0), and [ZDDs](https://cracked.guide/glossary/zdd) offer a second way to count and list solutions.

## Questions

### Is exact cover NP-complete?

Yes, it is one of Karp's classic NP-complete problems. Good heuristics still solve real puzzle instances quickly.

---

Source: https://cracked.guide/glossary/exact-cover
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.