dlx-cython 0.1.6

DLX (Dancing Links) implementation in Cython

DLX Implementation

A DLX (Dancing Links) algorithm implementation in Cython for solving exact cover problems.

Features

• Fast: Implemented in Cython for speed (sub-millisecond for typical problems)
• Memory Efficient: Optimized data structures for minimal memory overhead
• Python Interface: Easy-to-use Python API
• Exact Cover Solver: Solves exact cover problems efficiently

Installation

From PyPI (when published)

pip install dlx-cython

Local Development

# Install in editable mode
pip install -e /path/to/dlx

From Source

git clone https://github.com/robmbrooks/dlx.git
cd dlx
pip install -e .

See INSTALLATION.md for detailed installation options and troubleshooting.

Quick Start

from dlxsolver import DLXSolver

# Define your constraint matrix
matrix = [
    [1, 0, 1],  # Row 0 covers columns 0 and 2
    [0, 1, 0],  # Row 1 covers column 1
    [1, 1, 0],  # Row 2 covers columns 0 and 1
]

# Create solver and find solution
solver = DLXSolver(matrix)
solution = solver.solve_one()
print(f"Solution: {solution}")  # [0, 1]

Usage Examples

Basic Usage

from dlxsolver import DLXSolver

matrix = [[1, 0, 1], [0, 1, 0], [1, 1, 0]]
solver = DLXSolver(matrix)

# Find first solution
solution = solver.solve_one()

# Find all solutions
all_solutions = solver.solve(find_all=True)

Using Convenience Function

from dlxsolver import solve_exact_cover

solutions = solve_exact_cover(matrix, find_all=True)

With NumPy

import numpy as np
from dlxsolver import DLXSolver

matrix = np.array([[1, 0, 1], [0, 1, 0]], dtype=np.int32)
solver = DLXSolver(matrix)
solution = solver.solve_one()

Edge Cases

from dlxsolver import DLXSolver
import numpy as np

# Single row solution
matrix = [[1, 1, 1]]  # One row covers all columns
solver = DLXSolver(matrix)
solution = solver.solve_one()  # [0]

# Handling no solution
matrix = [[1, 0, 0], [0, 1, 0], [0, 0, 0]]  # Column 2 can't be covered
solver = DLXSolver(matrix)
solution = solver.solve_one()  # None
if solution is None:
    print("No solution exists")

# Getting solution rows
matrix = [[1, 0, 1], [0, 1, 0]]
solver = DLXSolver(matrix)
solution = solver.solve_one()  # [0, 1]
if solution:
    solution_rows = solver.get_solution_rows(solution)
    print(f"Solution rows:\n{solution_rows}")
    # Output:
    # [[1 0 1]
    #  [0 1 0]]

Error Handling

from dlxsolver import DLXSolver

# Invalid matrix (non-binary)
try:
    matrix = [[1, 2, 3]]  # Contains values other than 0/1
    solver = DLXSolver(matrix)
except ValueError as e:
    print(f"Error: {e}")  # "Matrix must contain only 0s and 1s"

# Empty matrix
try:
    matrix = []
    solver = DLXSolver(matrix)
except ValueError as e:
    print(f"Error: {e}")  # "Matrix must have at least one row and one column"

# Non-2D matrix
try:
    matrix = [1, 2, 3]  # 1D array
    solver = DLXSolver(matrix)
except ValueError as e:
    print(f"Error: {e}")  # "Matrix must be 2-dimensional"

Documentation

• INSTALLATION.md - Detailed installation instructions and troubleshooting
• PERFORMANCE_ANALYSIS.md - Performance benchmarks and analysis
• RELEASE.md - Release process for maintainers

Examples

See the examples/ directory for usage examples:

• examples/simple_example.py - Basic usage examples
• examples/sudoku_example.py - Sudoku solver using DLX
• example_usage.py - Comprehensive usage examples

Building from Source

# Install dependencies
pip install numpy cython setuptools

# Build Cython extension
python setup.py build_ext --inplace

# Install package
pip install -e .

Requirements

• Python 3.7+
• NumPy >= 1.19.0
• Cython >= 0.29.0 (for building)

API Reference

DLXSolver Class

Main solver class for exact cover problems.

DLXSolver(matrix)

Initialize the solver with a constraint matrix.

Parameters:

• matrix (array-like): Binary matrix of shape (n_rows, n_cols) where matrix[i][j] = 1 means row i covers column j. Can be a list of lists or NumPy array.

Raises:

• ValueError: If matrix is not 2-dimensional, empty, or contains non-binary values.

Example:

matrix = [[1, 0, 1], [0, 1, 0]]
solver = DLXSolver(matrix)

solve(find_all=True)

Solve the exact cover problem.

Parameters:

• find_all (bool, optional): If True (default), find all solutions. If False, return only the first solution.

Returns:

• list of lists: List of solutions, where each solution is a list of row indices forming an exact cover. Returns empty list if no solution exists.

Example:

solutions = solver.solve(find_all=True)
# [[0, 1], [2, 3]]  # Multiple solutions

solve_one()

Find the first solution.

Returns:

• list or None: First solution as a list of row indices, or None if no solution exists.

Example:

solution = solver.solve_one()
# [0, 1] or None

get_solution_rows(solution)

Get the actual matrix rows for a solution.

Parameters:

• solution (list): List of row indices (as returned by solve() or solve_one()).

Returns:

• numpy.ndarray: The rows of the matrix corresponding to the solution.

Example:

solution = [0, 1]
rows = solver.get_solution_rows(solution)
# Returns the actual matrix rows as a NumPy array

solve_exact_cover() Function

Convenience function to solve an exact cover problem without creating a solver instance.

Parameters:

• matrix (array-like): Binary constraint matrix.
• find_all (bool, optional): Whether to find all solutions (default: True).

Returns:

• list of lists: Solutions to the exact cover problem.

Example:

from dlxsolver import solve_exact_cover

matrix = [[1, 0, 1], [0, 1, 0]]
solutions = solve_exact_cover(matrix, find_all=True)

Performance

Characteristics

The DLX algorithm has the following performance characteristics:

• Time Complexity:

  • Best case: O(n) where n is the number of rows
  • Average case: O(n × m) where m is average branching factor
  • Worst case: Exponential (inherent to exact cover problems)

• Space Complexity: O(n × m) where n is rows and m is columns

• Typical Performance:

  • Small problems (100x50): ~0.08ms
  • Medium problems (500x200): ~10ms
  • Large problems (1000x500): ~100ms

Factors Affecting Performance

1. Matrix Density: Sparse matrices (low density) solve faster
2. Solution Count: Finding all solutions takes longer than finding one
3. Problem Structure: Problems with many overlapping constraints may be slower
4. Early Termination: Using find_all=False stops after first solution

Optimization Tips

• Use solve_one() instead of solve(find_all=True) if you only need one solution
• For very large problems, consider breaking into smaller sub-problems
• Sparse matrices (many zeros) perform better than dense matrices

See PERFORMANCE_ANALYSIS.md for detailed benchmarks and analysis.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Citation

If you use this library in your research, please cite:

@software{dlx_cython,
  title = {DLX-Cython: Dancing Links Implementation},
  author = {Robert Brooks},
  year = {2024},
  url = {https://github.com/robmbrooks/dlx},
  version = {0.1.0}
}

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

Troubleshooting

Common Issues

"No module named 'dlx'"

Problem: The Cython extension hasn't been built.

Solution:

cd /path/to/dlx
python setup.py build_ext --inplace
pip install -e .

"Matrix must contain only 0s and 1s"

Problem: Your matrix contains values other than 0 or 1.

Solution: Ensure your matrix is binary:

import numpy as np
matrix = np.array(your_matrix, dtype=np.int32)
# Verify it's binary
assert np.all((matrix == 0) | (matrix == 1))

"Matrix must be 2-dimensional"

Problem: You passed a 1D array instead of a 2D matrix.

Solution: Reshape your data:

# Wrong
matrix = [1, 0, 1, 0, 1, 0]

# Correct
matrix = [[1, 0, 1], [0, 1, 0]]
# or
matrix = np.array([1, 0, 1, 0, 1, 0]).reshape(2, 3)

Solver returns empty list / None

Problem: No exact cover solution exists for your matrix.

Solution: Verify your problem has a solution:

# Check if all columns can be covered
coverage = np.sum(matrix, axis=0)
if np.any(coverage == 0):
    print("Some columns cannot be covered")

Slow performance on large problems

Problem: Very large or dense matrices may take longer.

Solutions:

• Use solve_one() instead of solve(find_all=True) if possible
• Consider if the problem can be decomposed into smaller sub-problems
• Check matrix density - sparse matrices perform better

Getting Help

• Check the examples/ directory for usage patterns
• Review PERFORMANCE_ANALYSIS.md for performance tips
• Open an issue on GitHub

Changelog

See CHANGELOG.md for version history.