Glossary
What is the exact cover problem?
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 make the remove and restore steps constant time. It is the subject of §7.2.2.1, and ZDDs 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.