Skip to content

Exact Cover API Reference

Data

Data model for ExactCover use case.

ExactCoverData

Bases: UcData

Data for the Exact Cover Problem.

Given a universe of elements and a collection of subsets, the Exact Cover problem asks whether there exists a sub-collection of subsets such that every element is contained in exactly one subset.

Attributes:

  • name (Literal['exact_cover']) –

    Identifier for this data type.

  • subset_matrix (NumPyArray) –

    A matrix where each row represents a subset and each column an element. subset_matrix[i][j] = 1 if subset i contains element j, 0 otherwise.

  • n_elements (int) –

    Number of elements in the universe.

plot(*, ax: Axes | None = None) -> Axes

Plot the subset matrix as a binary heatmap.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the data.

Returns:

  • str –

    String representation of the data.

from_matrix(subset_matrix: list[list[int]] | NDArray[np.int_]) -> ExactCoverData staticmethod

Create an ExactCoverData instance from a subset matrix.

Parameters:

  • subset_matrix (list[list[int]] | NDArray[int_]) –

    A matrix where each row is a subset and each column an element. subset_matrix[i][j] = 1 if subset i contains element j.

Returns:

  • ExactCoverData –

    An ExactCoverData instance with the given matrix.

Examples:

>>> data = ExactCoverData.from_matrix([[1, 1, 0], [0, 1, 1]])

from_subsets(subsets: list[list[int | str]], elements: list[int | str] | None = None) -> ExactCoverData staticmethod

Create an ExactCoverData instance from element and subset lists.

Parameters:

  • subsets (list[list[int | str]]) –

    List of subsets, where each subset is a list of elements.

  • elements (list[int | str] | None, default: None ) –

    List of all elements in the universe. If None, inferred as list(range(n)) where n is the largest integer element + 1.

Returns:

  • ExactCoverData –

    An ExactCoverData instance with the generated subset matrix.

Examples:

>>> data = ExactCoverData.from_subsets(
...     subsets=[[0, 1], [2, 3], [1, 2]],
... )

generate_random(n_elements: int = 5, n_subsets: int = 8, density: float = 0.4, seed: int | None = None) -> ExactCoverData staticmethod

Generate a random exact cover instance.

Parameters:

  • n_elements (int, default: 5 ) –

    Number of elements in the universe, by default 5.

  • n_subsets (int, default: 8 ) –

    Number of subsets, by default 8.

  • density (float, default: 0.4 ) –

    Probability that an element is included in a subset, by default 0.4.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Formulation

Formulation for ExactCover use case.

ExactCoverFormulation

Bases: UcFormulation[ExactCoverData, ExactCoverSolution]

Constraint-based formulation for the Exact Cover Problem.

Mathematical Formulation 
Decision Variables:
    x_s in {0,1} for each subset s: 1 if subset s is selected

Objective:
    minimize sum_s x_s (minimize number of subsets used)

Constraints:
    For each element e:
        sum_{s containing e} x_s == 1
    (each element must be covered exactly once)

to_string(data: ExactCoverData) -> str staticmethod

Return a string describing the formulation.

Parameters:

Returns:

  • str –

    String representation of the formulation.

formulate(data: ExactCoverData) -> Model staticmethod

Formulate the Exact Cover Problem using constraint-based approach.

Parameters:

Returns:

  • Model –

    A LunaModel ready to be solved.

Raises:

interpret(solution: Solution, data: ExactCoverData) -> ExactCoverSolution staticmethod

Extract solution from quantum result.

Parameters:

  • solution (Solution) –

    The quantum solution.

  • data (ExactCoverData) –

    The problem data.

Returns:

Solution

Solution model for ExactCover use case.

ExactCoverSolution

Bases: UcSolution

Solution for the Exact Cover Problem.

Attributes:

  • name (Literal['exact_cover']) –

    Identifier for this solution type.

  • selected_subsets (list[int]) –

    Indices of selected subsets forming the exact cover.

  • n_subsets_used (int) –

    Number of subsets used in the solution.

  • is_valid (bool) –

    Whether each element is covered exactly once.

plot(data: ExactCoverData | None = None, *, ax: Axes | None = None) -> Axes

Plot the exact cover solution.

Parameters:

  • data (ExactCoverData | None, default: None ) –

    Problem data for context.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the solution.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for ExactCover use case.

ExactCoverInstance

Bases: UcInstance[ExactCoverData, ExactCoverFormulation, ExactCoverSolution]

Instance combining data and formulation for ExactCover.

Collection

Collection of ExactCover instances.

ExactCoverCollection

Bases: UcInstanceCollection[ExactCoverInstance]

Collection of Exact Cover instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.

from_random(min_num_elements: int | None = None, max_num_elements: int | None = None, num_instances: int = 1, *, sizes: Sequence[int] | None = None, density: float = 0.4, subset_ratio: float = 1.6, seed: int | None = None) -> ExactCoverCollection classmethod

Generate random exact cover instances.

Parameters:

  • min_num_elements (int | None, default: None ) –

    Minimum number of elements per instance.

  • max_num_elements (int | None, default: None ) –

    Maximum number of elements per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • density (float, default: 0.4 ) –

    Probability that an element is included in a subset, by default 0.4.

  • subset_ratio (float, default: 1.6 ) –

    Ratio of subsets to elements, by default 1.6.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

  • sizes (Sequence[int] | None, default: None ) –

    Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_num_elements/max_num_elements, by default None.

Returns:

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

  • max_runtime (float, default: 3600 ) –

    SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • list[bool] –

    Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises: