Originally written in Python with NumPy and pandas during my Robotics program; ported to TypeScript here so the solver runs live in the browser. Everything below computes in your own tab.
The problem
An exact cover asks: given a collection of sets, choose a subcollection so that every element is covered by exactly one chosen set. Sudoku, polyomino tiling, and N-Queens all reduce to it. It is NP-complete — no known way to find solutions in polynomial time — yet Knuth's Algorithm X solves it elegantly by depth-first backtracking, repeatedly picking the least-covered element and branching on the sets that cover it.
Algorithm X finds all solutions, but treats them as interchangeable. Many real problems have a notion of a better solution. So I modified the search: instead of backtracking depth-first, Algorithm X* explores the tree of partial solutions best-first — an A*-style priority queue ordered by a cost function — and yields solutions in nondecreasing cost order. If you only need the best few, you stop early and never pay for the rest.
The application: twelve-tone chord progressions
Partition the twelve notes of the octave into four three-note chords (major, minor, and their inversions), each note used once — a clean exact cover. But most such partitions sound arbitrary. I score every progression by voice-leading distance from Neo-Riemannian theory: two chords are "close" if you can move between them by shifting a single note, and a progression's cost is the sum of pairwise distances among its chords. Add a small reward for chords in root position and the twelve-fold rotational symmetry breaks, leaving a single best progression — F, C#m, Gm, B, at cost 23.
X* returns exactly that ordering below. Toggle the cost function, reveal solutions cheapest-first, and click ▶ to hear each one.
The core of X*
The whole algorithm is a priority queue over partial solutions. Pop the cheapest path; reduce the table by the rows it has chosen; if every requirement is met, it's a solution; otherwise pick the sparsest remaining column and enqueue a child for each row that covers it, scored by the cost function.
export function* xStar(t, cost) {
const heap = new MinHeap();
// seed from the sparsest column …
while (heap.size) {
const { k: curCost, v: path } = heap.pop();
const { remRows, colCount } = reduce(t, path);
if (colCount.size === 0) { yield { rows: path, cost: curCost }; continue; }
const col = chooseColumn(colCount); // sparsest requirement, or prune
if (col === null) continue;
for (const row of remRows)
if (t.rowCols.get(row).has(col)) enqueue(curCost, path, row);
}
}
The full solver and the twelve-tone setup are two small TypeScript modules
(xstar.ts, tonerow.ts). The solver is generic over any cost function
and supports optional columns, so the same code handles generalized exact cover — which sets up
the next step.
The same problem, on a neutral-atom quantum processor
This section runs on Pasqal's open-source stack (QoolQit / the
maximum-independent-set package) against its local emulator — Python, not the
browser. Numbers below are from that emulator; the code is a single runnable script.
Exact cover has a clean quantum-native form. Map each candidate set to a graph node, weight it by how many elements it covers, and connect two nodes whenever their sets overlap. An independent set — no two chosen nodes adjacent — is then a family of pairwise disjoint sets, and a maximum-weight independent set whose weight equals the size of the universe is an exact cover. On a neutral-atom processor this is almost literal: each set becomes an atom, overlapping sets are placed within the Rydberg blockade radius so they can't both be excited, and the array relaxes toward its lowest-energy independent set. The hardware constraint is the disjointness constraint.
# exact-cover instance -> weighted conflict graph
g = nx.Graph()
for name, s in subsets.items():
g.add_node(name, weight=len(s)) # weight -> per-atom detuning
for a, b in combinations(subsets, 2):
if subsets[a] & subsets[b]:
g.add_edge(a, b) # overlap -> blockade edge
# solve on the local neutral-atom emulator
cfg = SolverConfig(backend=BackendConfig(backend=BackendType.QUTIP),
weighting=Weighting.WEIGHTED, preprocessor=None, runs=300)
solutions = MISSolver(MISInstance(g), cfg).solve()
On Knuth's textbook instance (universe of 7, six subsets) the emulator places six atoms, takes
300 projective measurements, and returns the unique exact cover
{B, D, F} in 100% of shots — the array never settles
anywhere else.
Run the same reduction on the twelve-tone instance above and a nice structure falls out. Each triad covers exactly three notes and 4 × 3 = 12, so any independent set of size four already tiles the whole octave: here maximum independent set and exact cover are the same object. All eighteen covers appear, and every one is exactly two major plus two minor triads. Weighting the atoms by tonal centrality — roots near C on the circle of fifths — biases the array toward the most in-key cover, the neutral-atom analogue of X*'s preference ordering. At twenty-four atoms this exceeds local state-vector emulation (224 amplitudes); the identical program targets the tensor-network emulator or real QPU by swapping one backend line.