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 Luna Model 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, max_num_elements: int, num_instances: int = 1, *, 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) –

    Minimum number of elements per instance.

  • max_num_elements (int) –

    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.

Returns: