Exact Cover Example

Download Notebook

The Exact Cover problem asks whether there exists a sub-collection of subsets such that every element in the universe is contained in exactly one selected subset. It is NP-complete and is the basis for Knuth's Algorithm X.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.exact_cover import (
    ExactCoverCollection,
    ExactCoverData,
    ExactCoverFormulation,
    ExactCoverInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define 5 subsets over 5 elements. An exact cover uses subsets that together cover each element exactly once.

subset_matrix = [
    [1, 1, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 0, 1],
]
data = ExactCoverData.from_matrix(subset_matrix)
print(data.to_string())

Exact Cover Problem:
  Number of elements: 5
  Number of subsets: 5
  Subset 0: elements [0, 1]
  Subset 1: elements [2, 3]
  Subset 2: elements [4]
  Subset 3: elements [0, 2]
  Subset 4: elements [1, 4]

Alternative: Create Data from Subset Lists

Instead of a binary matrix, you can specify subsets as lists of element identifiers.

data_from_subsets = ExactCoverData.from_subsets(
    subsets=[[0, 1], [2, 3], [4], [0, 2], [1, 4]],
)
print(data_from_subsets.to_string())

Exact Cover Problem:
  Number of elements: 5
  Number of subsets: 5
  Subset 0: elements [0, 1]
  Subset 1: elements [2, 3]
  Subset 2: elements [4]
  Subset 3: elements [0, 2]
  Subset 4: elements [1, 4]

Plot Data

Visualize subset-element membership.

data.plot()

<Axes: title={'center': 'Exact Cover -- Subset Matrix'}, xlabel='Element j', ylabel='Subset i'>

Create Formulation

Find a collection of subsets that covers every element exactly once.

formulation = ExactCoverFormulation()
print(formulation.to_string(data))

Exact Cover Formulation:
  Subsets: 5
  Elements: 5

Decision Variables:
  x[s] in {0,1} for s = 0, ..., 4
  x[s] = 1 if subset s is selected
  Total: 5 binary variables

Objective:
  minimize sum_s x[s]

Constraints:
  1. Each element covered exactly once (5 constraints):
     sum_{s containing e} x[s] == 1  for all e = 0, ..., 4

Create Instance

Combine data and formulation into a solvable instance.

instance = ExactCoverInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Exact Cover Problem:
  Number of elements: 5
  Number of subsets: 5
  Subset 0: elements [0, 1]
  Subset 1: elements [2, 3]
  Subset 2: elements [4]
  Subset 3: elements [0, 2]
  Subset 4: elements [1, 4]
Formulation:Exact Cover Formulation:
  Subsets: 5
  Elements: 5

Decision Variables:
  x[s] in {0,1} for s = 0, ..., 4
  x[s] = 1 if subset s is selected
  Total: 5 binary variables

Objective:
  minimize sum_s x[s]

Constraints:
  1. Each element covered exactly once (5 constraints):
     sum_{s containing e} x[s] == 1  for all e = 0, ..., 4

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

2026-05-29 11:33:35 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:33:41 INFO     Sleeping for 10.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:33:53 INFO     Sleeping for 15.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:34:09 INFO     Sleeping for 20.0 seconds. Waiting and checking a function in a loop.

Exact Cover Solution:
  Subsets used: 3
  Selected subsets: [0, 1, 2]
  Valid (each element covered exactly once): True

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'Exact Cover Solution -- 3 subsets'}, xlabel='Element j', ylabel='Subset i'>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = ExactCoverCollection.from_random(min_num_elements=5, max_num_elements=8, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: exact_cover<exact_cover>
Minimize
  x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7
Subject To
  cover_element_0: x_0 + x_1 + x_3 == 1
  cover_element_1: x_2 + x_3 + x_5 + x_6 == 1
  cover_element_2: x_1 + x_3 + x_4 + x_7 == 1
  cover_element_3: x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 == 1
  cover_element_4: x_2 + x_3 + x_6 == 1
Binary
  x_0 x_1 x_2 x_3 x_4 x_5 x_6 x_7