Does Algorithm X find the cheapest solution?

Not by itself. Its basic task is finding exact covers, without a cost objective.

Must it use dancing links?

No. Other data structures can implement the same search, although reversible sparse updates are often useful.

What does an empty candidate column mean?

In the current branch, a required item cannot be covered, so that branch must fail and the search backtrack.

AI Glossary / Graphs and symbolic AI / Intermediate

Knuth's Algorithm X

Definition

Knuth's Algorithm X is a backtracking algorithm for solving exact cover problems. Given a collection of possible choices, it searches for a subset that covers each required item exactly once. It repeatedly selects an uncovered requirement, tries a compatible choice, removes conflicts, and reverses unsuccessful decisions so that alternatives can be explored.

What it means

An exact cover is stricter than simply covering everything. Every required item must be included, and none may be covered twice. A convenient representation is a matrix of zeros and ones: columns represent requirements, rows represent candidate choices, and a one indicates that a choice satisfies a requirement.
Algorithm X selects rows whose combined column totals are all exactly one. This makes it useful for problems that can be encoded as discrete, mutually compatible choices. Its name refers to the search algorithm; dancing links is a particularly efficient technique for maintaining the changing data structure during that search.

How it works

Start with no chosen rows. Select a remaining column and consider each available row containing a one in that column. When a row is chosen, remove every requirement it covers and every candidate row that conflicts by covering one of those same requirements. Search the reduced problem recursively.
If no requirements remain, the selected rows form a solution. If a remaining requirement has no candidate row, the branch fails and earlier removals are undone. Choosing a column with few available rows often reduces branching, but this is a search-order heuristic rather than a guarantee of fast completion. A solver can stop after one solution or continue systematically to enumerate solutions.

Three practical examples

A puzzle program encodes possible placements as rows and required board positions as columns, rejecting overlapping placements.
A small assignment tool selects compatible bundles so that each mandatory task is assigned exactly once.
A configuration experiment models permitted combinations of components and checks whether all required positions can be filled without conflict.

Think of it this way

Think of assembling a complete set of numbered cards from several sealed packets, with the rule that every number must appear once. Choosing one packet rules out other packets containing any of its numbers. The analogy is limited because real applications may require a sophisticated encoding, and many scheduling or optimization requirements are not naturally exact-cover constraints.

Worked example

Consider an invented universe of requirements {A, B, C, D}. There are four candidate rows: R1 covers {A, B}; R2 covers {A, C}; R3 covers {B, D}; and R4 covers {C}. Choose requirement A first, so the initial alternatives are R1 and R2.
Try R1. Requirements A and B are covered. R2 conflicts through A and R3 conflicts through B, so both disappear from this branch. R4 can cover C, but no remaining row can cover D. The branch fails. The solver must restore the removed information before trying the other option for A.
Now choose R2. Requirements A and C are covered. R1 conflicts through A and R4 conflicts through C, leaving R3 to cover B and D. Selecting R3 finishes the problem. The resulting exact cover is {R2, R3}, and each of A, B, C, and D is covered once.
Notice why {R1, R3, R4} is not acceptable: it covers all requirements, but B appears twice. Ordinary coverage alone would miss that violation. This small trace also shows that a failed branch does not mean the original problem has no solution.

Illustrative case study

In a fictional workshop, Mosaic Lab offers kits made from allowed bundles. Each completed kit must contain exactly one item for each of four required roles. A developer represents the bundles as exact-cover rows and checks a hand-worked example before testing larger catalogs.
When the business later adds a preference for lower cost, the team recognizes that finding any exact cover does not automatically optimize price. They introduce an explicit optimization approach instead of describing the first feasible solution as cheapest. The case is illustrative and reports no measured commercial results.

Common misconceptions and mistakes

Algorithm X is not identical to dancing links: the algorithm describes the search, while dancing links supports efficient reversible updates. Nor does the letter X denote a machine-learning model or a requirement to use randomness.
Exact cover differs from set cover, where overlap may be allowed and one may seek a small or low-cost covering collection. Algorithm X also does not make every exact-cover instance easy; the general problem is computationally difficult. A strong column-selection rule can help considerably without eliminating worst-case search. Finally, a correct solver cannot compensate for missing constraints in the encoding.

Business use

The method is worth considering when a business problem can be stated as selecting compatible discrete options with exactly-once requirements. Before implementation, create a small example and verify that every valid business arrangement corresponds to an exact cover and that invalid arrangements are excluded.
Keep feasibility separate from optimization, and make optional requirements explicit rather than quietly treating them as mandatory columns. For larger problems, compare the representation and search behavior with constraint-programming or mathematical-optimization alternatives. Record whether a run found one solution, enumerated all solutions, proved infeasibility, or stopped before completing the search.

Check your understanding

Why does choosing R1 fail in the worked example even though R4 can still cover C?

Answer: R1 removes R3 because both cover B. R3 was the only candidate covering D, leaving D impossible to satisfy in that branch.

Related terms

Dancing links
Constraint satisfaction
Search tree
exact cover
backtracking
set cover
feasibility
branching heuristic

Learn next

Convert the worked example into a four-column binary matrix. Trace which rows and columns disappear after each choice, then restore them in reverse order. Add a new candidate and check whether the number of exact covers changes.

Sources

Sources: Donald E. Knuth, Dancing Links, original paper describing Algorithm X and its implementation: https://arxiv.org/abs/cs/0011047

Previous: Knowledge space Next: Kohonen Network