Contents Menu Expand Light mode Dark mode Auto light/dark, in light mode Auto light/dark, in dark mode Skip to content
Combinatorics
Light Logo Dark Logo
Version 10.6 Reference Manual
  • Home - Combinatorics
  • Comprehensive Module List
    • Abstract Recursive Trees
    • Affine Permutations
    • Algebraic combinatorics
    • Combinatorics
    • Alternating Sign Matrices
    • Backtracking
    • Baxter permutations
    • A bijectionist’s toolkit
    • Binary Recurrence Sequences
    • Binary Trees
    • Blob Algebras
    • Cartesian Products
    • Enumerated sets of partitions, tableaux, …
    • Combinatorial Hopf algebras
    • Poirier-Reutenauer Hopf algebra of standard tableaux
    • Word Quasi-symmetric functions
    • Cluster algebras and quivers
    • ClusterSeed
    • mutation_class
    • Helper functions for mutation types of quivers
    • Quiver
    • Quiver mutation types
    • Cluster complex (or generalized dual associahedron)
    • Colored Permutations
    • Combinatorial Functions
    • Fast computation of combinatorial functions (Cython + mpz)
    • Combinations
    • Combinatorial maps
    • Integer compositions
    • Signed Compositions
    • Composition Tableaux
    • Constellations
    • Cores
    • Counting
    • Affine Crystals
    • Affine factorization crystal of type \(A\)
    • Affinization Crystals
    • Alcove paths
    • Crystals
    • Benkart-Kang-Kashiwara crystals for the general-linear Lie superalgebra
    • Catalog Of Crystals
    • Catalog Of Elementary Crystals
    • Catalog Of Crystal Models For \(B(\infty)\)
    • Catalog Of Crystal Models For Kirillov-Reshetikhin Crystals
    • An introduction to crystals
    • Direct Sum of Crystals
    • Elementary Crystals
    • Fast Rank Two Crystals
    • Fully commutative stable Grothendieck crystal
    • Crystals of Generalized Young Walls
    • Highest weight crystals
    • Induced Crystals
    • \(\mathcal{B}(\infty)\) Crystals of Tableaux in Nonexceptional Types and \(G_2\)
    • Crystals of Kac modules of the general-linear Lie superalgebra
    • Kirillov-Reshetikhin Crystals
    • Kyoto Path Model for Affine Highest Weight Crystals
    • Crystals of letters
    • Littelmann paths
    • Crystals of Modified Nakajima Monomials
    • Crystal of Bernstein-Zelevinsky Multisegments
    • Crystal Of Mirković-Vilonen (MV) Polytopes
    • \(\mathcal{B}(\infty)\) Crystal Of PBW Monomials
    • PBW Data
    • Polyhedral Realization of \(B(\infty)\)
    • Spin Crystals
    • Star-Crystal Structure On \(B(\infty)\)
    • Tensor Products of Crystals
    • Tensor Products of Crystal Elements
    • Cyclic sieving phenomenon
    • De Bruijn sequences
    • Degree sequences
    • Derangements
    • Descent Algebras
    • Combinatorial designs and incidence structures
    • Balanced Incomplete Block Designs (BIBD)
    • Resolvable Balanced Incomplete Block Design (RBIBD)
    • Group-Divisible Designs (GDD)
    • Block designs
    • Covering Arrays (CA)
    • Covering designs: coverings of \(t\)-element subsets of a \(v\)-set by \(k\)-sets
    • Database of small combinatorial designs
    • Catalog of designs
    • Cython functions for combinatorial designs
    • Difference families
    • Difference Matrices
    • Evenly distributed sets in finite fields
    • External Representations of Block Designs
    • Database of generalised quadrangles with spread
    • Incidence structures (i.e. hypergraphs, i.e. set systems)
    • Mutually Orthogonal Latin Squares (MOLS)
    • Orthogonal arrays (OA)
    • Orthogonal arrays (build recursive constructions)
    • Orthogonal arrays (find recursive constructions)
    • Steiner Quadruple Systems
    • Hypergraph isomorphic copy search
    • Two-graphs
    • Combinatorial diagrams
    • Diagram and Partition Algebras
    • Exact Cover Problem via Dancing Links
    • Dyck Words
    • Substitutions over unit cube faces (Rauzy fractals)
    • Enumerated sets and combinatorial objects
    • Tools for enumeration modulo the action of a permutation group
    • Compute Bell and Uppuluri-Carpenter numbers
    • Families
    • Brent Yorgey’s fast algorithm for integer vector (multiset) partitions.
    • Fully commutative elements of Coxeter groups
    • Finite state machines, automata, transducers
    • Common Automata and Transducers (Finite State Machines Generators)
    • Free Quasi-symmetric functions
    • Free modules
    • Free Dendriform Algebras
    • Free Pre-Lie Algebras
    • Fully packed loops
    • Gelfand-Tsetlin Patterns
    • Paths in Directed Acyclic Graphs
    • Gray codes
    • Growth diagrams and dual graded graphs
    • Grossman-Larson Hopf Algebras
    • Hall Polynomials
    • The Hillman-Grassl correspondence
    • Enumerated set of lists of integers with constraints: base classes
    • Enumerated set of lists of integers with constraints: front-end
    • Enumerated set of lists of integers with constraints, in inverse lexicographic order
    • Counting, generating, and manipulating nonnegative integer matrices
    • (Non-negative) Integer vectors
    • Weighted Integer Vectors
    • Integer vectors modulo the action of a permutation group
    • Tamari Interval-posets
    • Strong and weak tableaux
    • Kazhdan-Lusztig Polynomials
    • Key polynomials
    • Knutson-Tao Puzzles
    • Combinatorics on matrices
    • Dancing Links internal pyx code
    • Dancing links C++ wrapper
    • Hadamard matrices
    • Latin Squares
    • Miscellaneous
    • Ordered Multiset Partitions into Sets and the Minimaj Crystal
    • Non-commutative symmetric functions and quasi-symmetric functions
    • Common combinatorial tools
    • Generic code for bases
    • Non-Commutative Symmetric Functions
    • Quasisymmetric functions
    • Introduction to Quasisymmetric Functions
    • Symmetric functions in non-commuting variables
    • Bases for \(NCSym\)
    • Dual Symmetric Functions in Non-Commuting Variables
    • Symmetric Functions in Non-Commuting Variables
    • Necklaces
    • Non-Decreasing Parking Functions
    • \(\nu\)-Dyck Words
    • \(\nu\)-Tamari lattice
    • Ordered Rooted Trees
    • Output functions
    • Parallelogram Polyominoes
    • Parking Functions
    • Catalog of Path Tableaux
    • Dyck Paths
    • Frieze Patterns
    • Path Tableaux
    • Semistandard Tableaux
    • Plane Partitions
    • Integer partitions
    • Partition/Diagram Algebras
    • Kleshchev partitions
    • Partition Shifting Algebras
    • Partition tuples
    • Iterators over the partitions of an integer
    • Perfect matchings
    • Permutations
    • Permutations (Cython file)
    • Posets
    • Cartesian products of Posets
    • D-Complete Posets
    • Mobile posets
    • Elements of posets, lattices, semilattices, etc.
    • Forest Posets
    • Hasse diagrams of posets
    • Incidence Algebras
    • Finite lattices and semilattices
    • Linear Extensions of Posets
    • Möbius Algebras
    • Catalog of posets and lattices
    • Finite posets
    • \(q\)-Analogues
    • \(q\)-Bernoulli Numbers and Polynomials
    • Combinatorics quickref
    • Rankers
    • Recognizable Series
    • \(k\)-regular sequences
    • Restricted growth arrays
    • Ribbons
    • Ribbon Shaped Tableaux
    • Ribbon Tableaux
    • Rigged configurations
    • Abstract classes for the rigged configuration bijections
    • Bijection between rigged configurations for \(B(\infty)\) and marginally large tableaux
    • Bijection classes for type \(A_n^{(1)}\)
    • Bijection classes for type \(A_{2n}^{(2)\dagger}\)
    • Bijection classes for type \(A_{2n}^{(2)}\)
    • Bijection classes for type \(A_{2n-1}^{(2)}\).
    • Bijection classes for type \(B_n^{(1)}\)
    • Bijection classes for type \(C_n^{(1)}\)
    • Bijection classes for type \(D_n^{(1)}\)
    • Bijection classes for type \(D_{n+1}^{(2)}\)
    • Bijection classes for type \(D_4^{(3)}\)
    • Bijection between rigged configurations and KR tableaux
    • Kleber Trees
    • Kirillov-Reshetikhin Tableaux
    • Crystal of Rigged Configurations
    • Rigged Configurations of \(\mathcal{B}(\infty)\)
    • Rigged Configuration Elements
    • Rigged Configurations
    • Rigged Partitions
    • Tensor Product of Kirillov-Reshetikhin Tableaux
    • Tensor Product of Kirillov-Reshetikhin Tableaux Elements
    • Root Systems
    • Ambient lattices and ambient spaces
    • Associahedron
    • Braid Move Calculator
    • Braid Orbit
    • Branching Rules
    • Cartan matrices
    • Cartan types
    • Coxeter Groups
    • Coxeter Matrices
    • Coxeter Types
    • Dynkin diagrams
    • Hecke algebra representations
    • Integrable Representations of Affine Lie Algebras
    • Nonsymmetric Macdonald polynomials
    • Pieri Factors
    • Tutorial: visualizing root systems
    • Finite complex reflection groups
    • Finite real reflection groups
    • Group algebras of root lattice realizations
    • Root lattice realizations
    • Root lattices and root spaces
    • Root systems
    • Root system data for super type A
    • Root system data for type A
    • Root system data for (untwisted) type A affine
    • Root system data for type A infinity
    • Root system data for type B
    • Root system data for type BC affine
    • Root system data for (untwisted) type B affine
    • Root system data for type C
    • Root system data for (untwisted) type C affine
    • Root system data for type D
    • Root system data for (untwisted) type D affine
    • Root system data for type E
    • Root system data for (untwisted) type E affine
    • Root system data for type F
    • Root system data for (untwisted) type F affine
    • Root system data for type G
    • Root system data for (untwisted) type G affine
    • Root system data for type H
    • Root system data for type I
    • Root system data for type Q
    • Root system data for affine Cartan types
    • Root system data for dual Cartan types
    • Extended Affine Weyl Groups
    • Fundamental Group of an Extended Affine Weyl Group
    • Root system data for folded Cartan types
    • Root system data for Cartan types with marked nodes
    • Root system data for reducible Cartan types
    • Root system data for relabelled Cartan types
    • Weight lattice realizations
    • Weight lattices and weight spaces
    • Weyl Character Rings
    • Weyl Groups
    • Rooted (Unordered) Trees
    • Robinson-Schensted-Knuth correspondence
    • Schubert Polynomials
    • Set Partitions
    • Fast set partition iterators
    • Ordered Set Partitions
    • Symmetric Functions
    • Characters of the symmetric group as bases of the symmetric functions
    • Classical symmetric functions
    • Generic dual bases symmetric functions
    • Elementary symmetric functions
    • Hall-Littlewood Polynomials
    • Hecke Character Basis
    • Homogeneous symmetric functions
    • Jack Symmetric Functions
    • Quotient of symmetric function space by ideal generated by Hall-Littlewood symmetric functions
    • Kostka-Foulkes Polynomials
    • LLT symmetric functions
    • Macdonald Polynomials
    • Monomial symmetric functions
    • Multiplicative symmetric functions
    • \(k\)-Schur Functions
    • Non-symmetric Macdonald Polynomials
    • Orthogonal Symmetric Functions
    • Symmetric functions defined by orthogonality and triangularity
    • Power sum symmetric functions
    • Schur symmetric functions
    • Symplectic Symmetric Functions
    • Symmetric functions, with their multiple realizations
    • Symmetric Functions
    • Witt symmetric functions
    • Shard intersection order
    • Shifted primed tableaux
    • Shuffle product of iterables
    • Sidon sets and their generalizations, Sidon \(g\)-sets
    • Similarity class types of matrices with entries in a finite field
    • sine-Gordon Y-system plotter
    • Six Vertex Model
    • Skew Partitions
    • Skew Tableaux
    • Functions that compute some of the sequences in Sloane’s tables
    • Combinatorial species
    • Characteristic Species
    • Composition species
    • Cycle Species
    • Empty Species
    • Functorial composition species
    • Generating Series
    • Examples of Combinatorial Species
    • Linear-order Species
    • Miscellaneous Functions
    • Partition Species
    • Permutation species
    • Product species
    • Recursive Species
    • Set Species
    • Combinatorial Species
    • Species structures
    • Subset Species
    • Sum species
    • Specht Modules
    • Subsets
    • Subsets satisfying a hereditary property
    • Subsets whose elements satisfy a predicate pairwise
    • Subwords
    • Subword complex
    • Super Tableaux
    • Super Partitions
    • Symmetric Group Algebra
    • Representations of the Symmetric Group
    • T-sequences
    • Tableaux
    • Residue sequences of tableaux
    • TableauTuples
    • Generalized Tamari lattices
    • Tiling Solver
    • Transitive ideal closure tool
    • Combinatorial triangles for posets and fans
    • Tuples
    • Introduction to combinatorics in Sage
    • Vector Partitions
    • Abstract word (finite or infinite)
    • Combinatorics on words
    • Alphabet
    • Finite word
    • Infinite word
    • Lyndon words
    • Word morphisms/substitutions
    • Word paths
    • Shuffle product of words
    • Suffix Tries and Suffix Trees
    • Word classes
    • Fast word datatype using an array of unsigned char
    • Datatypes for finite words
    • Common words
    • Datatypes for words defined by iterators and callables
    • User-customizable options for words
    • Set of words
    • Yang-Baxter Graphs
    • C-Finite Sequences
Back to top
View this page
Edit this page

Dancing Links internal pyx code¶

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: x = dlx_solver(rows)
sage: x
Dancing links solver for 6 columns and 6 rows
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> x = dlx_solver(rows)
>>> x
Dancing links solver for 6 columns and 6 rows

The number of solutions:

sage: x.number_of_solutions()
3
>>> from sage.all import *
>>> x.number_of_solutions()
3

Iterate over the solutions:

sage: sorted(map(sorted, x.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
>>> from sage.all import *
>>> sorted(map(sorted, x.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]

All solutions (computed in parallel):

sage: sorted(map(sorted, x.all_solutions()))
[[0, 1], [2, 3], [4, 5]]
>>> from sage.all import *
>>> sorted(map(sorted, x.all_solutions()))
[[0, 1], [2, 3], [4, 5]]

Return the first solution found when the computation is done in parallel:

sage: sorted(x.one_solution(ncpus=2)) # random
[0, 1]
>>> from sage.all import *
>>> sorted(x.one_solution(ncpus=Integer(2))) # random
[0, 1]

Find all solutions using some specific rows:

sage: x_using_row_2 = x.restrict([2])
sage: x_using_row_2
Dancing links solver for 7 columns and 6 rows
sage: sorted(map(sorted, x_using_row_2.solutions_iterator()))
[[2, 3]]
>>> from sage.all import *
>>> x_using_row_2 = x.restrict([Integer(2)])
>>> x_using_row_2
Dancing links solver for 7 columns and 6 rows
>>> sorted(map(sorted, x_using_row_2.solutions_iterator()))
[[2, 3]]

The two basic methods that are wrapped in this class are search which returns 1 if a solution is found or 0 otherwise and get_solution which return the current solution:

sage: x = dlx_solver(rows)
sage: x.search()
1
sage: x.get_solution()
[0, 1]
sage: x.search()
1
sage: x.get_solution()
[2, 3]
sage: x.search()
1
sage: x.get_solution()
[4, 5]
sage: x.search()
0
>>> from sage.all import *
>>> x = dlx_solver(rows)
>>> x.search()
1
>>> x.get_solution()
[0, 1]
>>> x.search()
1
>>> x.get_solution()
[2, 3]
>>> x.search()
1
>>> x.get_solution()
[4, 5]
>>> x.search()
0

There is also a method reinitialize to reinitialize the algorithm:

sage: x.reinitialize()
sage: x.search()
1
sage: x.get_solution()
[0, 1]
>>> from sage.all import *
>>> x.reinitialize()
>>> x.search()
1
>>> x.get_solution()
[0, 1]
class sage.combinat.matrices.dancing_links.dancing_linksWrapper[source]¶

Bases: object

A simple class that implements dancing links.

The main methods to list the solutions are search() and get_solution(). You can also use number_of_solutions() to count them.

This class simply wraps a C++ implementation of Carlo Hamalainen.

all_solutions(ncpus=None, column=None)[source]¶

Return all solutions found after splitting the problem to allow parallel computation.

INPUT:

  • ncpus – integer (default: None); maximal number of subprocesses to use at the same time. If None, it detects the number of effective CPUs in the system using sage.parallel.ncpus.ncpus().

  • column – integer (default: None); the column used to split the problem, if None a random column is chosen

OUTPUT: list of solutions

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: S = d.all_solutions()
sage: sorted(sorted(s) for s in S)
[[0, 1], [2, 3], [4, 5]]
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> d = dlx_solver(rows)
>>> S = d.all_solutions()
>>> sorted(sorted(s) for s in S)
[[0, 1], [2, 3], [4, 5]]

The number of CPUs can be specified as input:

sage: S = Subsets(range(4))
sage: rows = map(list, S)
sage: dlx = dlx_solver(rows)
sage: dlx
Dancing links solver for 4 columns and 16 rows
sage: dlx.number_of_solutions()
15
sage: sorted(sorted(s) for s in dlx.all_solutions(ncpus=2))
[[1, 2, 3, 4],
 [1, 2, 10],
 [1, 3, 9],
 [1, 4, 8],
 [1, 14],
 [2, 3, 7],
 [2, 4, 6],
 [2, 13],
 [3, 4, 5],
 [3, 12],
 [4, 11],
 [5, 10],
 [6, 9],
 [7, 8],
 [15]]
>>> from sage.all import *
>>> S = Subsets(range(Integer(4)))
>>> rows = map(list, S)
>>> dlx = dlx_solver(rows)
>>> dlx
Dancing links solver for 4 columns and 16 rows
>>> dlx.number_of_solutions()
15
>>> sorted(sorted(s) for s in dlx.all_solutions(ncpus=Integer(2)))
[[1, 2, 3, 4],
 [1, 2, 10],
 [1, 3, 9],
 [1, 4, 8],
 [1, 14],
 [2, 3, 7],
 [2, 4, 6],
 [2, 13],
 [3, 4, 5],
 [3, 12],
 [4, 11],
 [5, 10],
 [6, 9],
 [7, 8],
 [15]]

If ncpus=1, the computation is not done in parallel:

sage: sorted(sorted(s) for s in dlx.all_solutions(ncpus=1))
[[1, 2, 3, 4],
 [1, 2, 10],
 [1, 3, 9],
 [1, 4, 8],
 [1, 14],
 [2, 3, 7],
 [2, 4, 6],
 [2, 13],
 [3, 4, 5],
 [3, 12],
 [4, 11],
 [5, 10],
 [6, 9],
 [7, 8],
 [15]]
>>> from sage.all import *
>>> sorted(sorted(s) for s in dlx.all_solutions(ncpus=Integer(1)))
[[1, 2, 3, 4],
 [1, 2, 10],
 [1, 3, 9],
 [1, 4, 8],
 [1, 14],
 [2, 3, 7],
 [2, 4, 6],
 [2, 13],
 [3, 4, 5],
 [3, 12],
 [4, 11],
 [5, 10],
 [6, 9],
 [7, 8],
 [15]]
get_solution()[source]¶

Return the current solution.

After a new solution is found using the method search() this method return the rows that make up the current solution.

ncols()[source]¶

Return the number of columns.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [1,2], [0], [3,4,5]]
sage: dlx = dlx_solver(rows)
sage: dlx.ncols()
6
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(1),Integer(2)], [Integer(0)], [Integer(3),Integer(4),Integer(5)]]
>>> dlx = dlx_solver(rows)
>>> dlx.ncols()
6
nrows()[source]¶

Return the number of rows.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [1,2], [0], [3,4,5]]
sage: dlx = dlx_solver(rows)
sage: dlx.nrows()
4
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(1),Integer(2)], [Integer(0)], [Integer(3),Integer(4),Integer(5)]]
>>> dlx = dlx_solver(rows)
>>> dlx.nrows()
4
number_of_solutions(ncpus=None, column=None)[source]¶

Return the number of distinct solutions.

INPUT:

  • ncpus – integer (default: None); maximal number of subprocesses to use at the same time. If ncpus>1 the dancing links problem is split into independent subproblems to allow parallel computation. If None, it detects the number of effective CPUs in the system using sage.parallel.ncpus.ncpus().

  • column – integer (default: None); the column used to split the problem, if None a random column is chosen (this argument is ignored if ncpus is 1)

OUTPUT: integer

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2]]
sage: rows += [[0,2]]
sage: rows += [[1]]
sage: rows += [[3]]
sage: x = dlx_solver(rows)
sage: x.number_of_solutions()
2
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)]]
>>> rows += [[Integer(0),Integer(2)]]
>>> rows += [[Integer(1)]]
>>> rows += [[Integer(3)]]
>>> x = dlx_solver(rows)
>>> x.number_of_solutions()
2

The number of CPUs can be specified as input:

sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: x = dlx_solver(rows)
sage: x.number_of_solutions(ncpus=2, column=3)
3
>>> from sage.all import *
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> x = dlx_solver(rows)
>>> x.number_of_solutions(ncpus=Integer(2), column=Integer(3))
3

sage: S = Subsets(range(5))
sage: rows = map(list, S)
sage: d = dlx_solver(rows)
sage: d.number_of_solutions()
52
>>> from sage.all import *
>>> S = Subsets(range(Integer(5)))
>>> rows = map(list, S)
>>> d = dlx_solver(rows)
>>> d.number_of_solutions()
52
one_solution(ncpus=None, column=None)[source]¶

Return the first solution found.

This method allows parallel computations which might be useful for some kind of problems when it is very hard just to find one solution.

INPUT:

  • ncpus – integer (default: None); maximal number of subprocesses to use at the same time. If None, it detects the number of effective CPUs in the system using sage.parallel.ncpus.ncpus(). If ncpus=1, the first solution is searched serially.

  • column – integer (default: None); the column used to split the problem (see restrict()). If None, a random column is chosen. This argument is ignored if ncpus=1.

OUTPUT: list of rows or None if no solution is found

Note

For some case, increasing the number of cpus makes it faster. For other instances, ncpus=1 is faster. It all depends on problem which is considered.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: solutions = [[0,1], [2,3], [4,5]]
sage: sorted(d.one_solution()) in solutions
True
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> d = dlx_solver(rows)
>>> solutions = [[Integer(0),Integer(1)], [Integer(2),Integer(3)], [Integer(4),Integer(5)]]
>>> sorted(d.one_solution()) in solutions
True

The number of CPUs can be specified as input:

sage: sorted(d.one_solution(ncpus=2)) in solutions
True
>>> from sage.all import *
>>> sorted(d.one_solution(ncpus=Integer(2))) in solutions
True

The column used to split the problem for parallel computations can be given:

sage: sorted(d.one_solution(ncpus=2, column=4)) in solutions
True
>>> from sage.all import *
>>> sorted(d.one_solution(ncpus=Integer(2), column=Integer(4))) in solutions
True

When no solution is found:

sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]]
sage: d = dlx_solver(rows)
sage: d.one_solution() is None
True
>>> from sage.all import *
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1),Integer(2),Integer(3)]]
>>> d = dlx_solver(rows)
>>> d.one_solution() is None
True
one_solution_using_milp_solver(solver=None, integrality_tolerance=0.001)[source]¶

Return a solution found using a MILP solver.

INPUT:

  • solver – string or None (default: None); possible values include 'GLPK', 'GLPK/exact', 'Coin', 'CPLEX', 'Gurobi', 'CVXOPT', 'PPL', 'InteractiveLP'

OUTPUT: list of rows or None if no solution is found

Note

When comparing the time taken by method one_solution, have in mind that one_solution_using_milp_solver first creates (and caches) the MILP solver instance from the dancing links solver. This copy of data may take many seconds depending on the size of the problem.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: solutions = [[0,1], [2,3], [4,5]]
sage: d.one_solution_using_milp_solver() in solutions                       # needs sage.numerical.mip
True
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> d = dlx_solver(rows)
>>> solutions = [[Integer(0),Integer(1)], [Integer(2),Integer(3)], [Integer(4),Integer(5)]]
>>> d.one_solution_using_milp_solver() in solutions                       # needs sage.numerical.mip
True

Using optional solvers:

sage: # optional - gurobi sage_numerical_backends_gurobi, needs sage.numerical.mip
sage: s = d.one_solution_using_milp_solver('gurobi')
sage: s in solutions
True
>>> from sage.all import *
>>> # optional - gurobi sage_numerical_backends_gurobi, needs sage.numerical.mip
>>> s = d.one_solution_using_milp_solver('gurobi')
>>> s in solutions
True

When no solution is found:

sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]]
sage: d = dlx_solver(rows)
sage: d.one_solution_using_milp_solver() is None                            # needs sage.numerical.mip
True
>>> from sage.all import *
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1),Integer(2),Integer(3)]]
>>> d = dlx_solver(rows)
>>> d.one_solution_using_milp_solver() is None                            # needs sage.numerical.mip
True
one_solution_using_sat_solver(solver=None)[source]¶

Return a solution found using a SAT solver.

INPUT:

  • solver – string or None (default: None), possible values include 'picosat', 'cryptominisat', 'LP', 'glucose', 'glucose-syrup'.

OUTPUT: list of rows or None if no solution is found

Note

When comparing the time taken by method one_solution, have in mind that one_solution_using_sat_solver first creates the SAT solver instance from the dancing links solver. This copy of data may take many seconds depending on the size of the problem.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: solutions = [[0,1], [2,3], [4,5]]
sage: d.one_solution_using_sat_solver() in solutions                        # needs sage.sat
True
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> d = dlx_solver(rows)
>>> solutions = [[Integer(0),Integer(1)], [Integer(2),Integer(3)], [Integer(4),Integer(5)]]
>>> d.one_solution_using_sat_solver() in solutions                        # needs sage.sat
True

Using optional solvers:

sage: s = d.one_solution_using_sat_solver('glucose')                # optional - glucose, needs sage.sat
sage: s in solutions                                                # optional - glucose, needs sage.sat
True
>>> from sage.all import *
>>> s = d.one_solution_using_sat_solver('glucose')                # optional - glucose, needs sage.sat
>>> s in solutions                                                # optional - glucose, needs sage.sat
True

When no solution is found:

sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]]
sage: d = dlx_solver(rows)
sage: d.one_solution_using_sat_solver() is None                             # needs sage.sat
True
>>> from sage.all import *
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1),Integer(2),Integer(3)]]
>>> d = dlx_solver(rows)
>>> d.one_solution_using_sat_solver() is None                             # needs sage.sat
True
reinitialize()[source]¶

Reinitialization of the search algorithm.

This recreates an empty dancing_links object and adds the rows to the instance of dancing_links.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: x = dlx_solver(rows)
sage: x.get_solution() if x.search() else None
[0, 1]
sage: x.get_solution() if x.search() else None
[2, 3]
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> x = dlx_solver(rows)
>>> x.get_solution() if x.search() else None
[0, 1]
>>> x.get_solution() if x.search() else None
[2, 3]

Reinitialization of the algorithm:

sage: x.reinitialize()
sage: x.get_solution() if x.search() else None
[0, 1]
sage: x.get_solution() if x.search() else None
[2, 3]
sage: x.get_solution() if x.search() else None
[4, 5]
sage: x.get_solution() if x.search() else None
>>> from sage.all import *
>>> x.reinitialize()
>>> x.get_solution() if x.search() else None
[0, 1]
>>> x.get_solution() if x.search() else None
[2, 3]
>>> x.get_solution() if x.search() else None
[4, 5]
>>> x.get_solution() if x.search() else None

Reinitialization works after solutions are exhausted:

sage: x.reinitialize()
sage: x.get_solution() if x.search() else None
[0, 1]
sage: x.get_solution() if x.search() else None
[2, 3]
sage: x.get_solution() if x.search() else None
[4, 5]
sage: x.get_solution() if x.search() else None
>>> from sage.all import *
>>> x.reinitialize()
>>> x.get_solution() if x.search() else None
[0, 1]
>>> x.get_solution() if x.search() else None
[2, 3]
>>> x.get_solution() if x.search() else None
[4, 5]
>>> x.get_solution() if x.search() else None
restrict(indices)[source]¶

Return a dancing links solver solving the subcase which uses some given rows.

For every row that is wanted in the solution, we add a new column to the row to make sure it is in the solution.

INPUT:

  • indices – list; row indices to be found in the solution

OUTPUT: dancing links solver

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: d
Dancing links solver for 6 columns and 6 rows
sage: sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> d = dlx_solver(rows)
>>> d
Dancing links solver for 6 columns and 6 rows
>>> sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]

To impose that the \(0\)-th row is part of the solution, the rows of the new problem are:

sage: d_using_0 = d.restrict([0])
sage: d_using_0
Dancing links solver for 7 columns and 6 rows
sage: d_using_0.rows()
[[0, 1, 2, 6], [3, 4, 5], [0, 1], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]
>>> from sage.all import *
>>> d_using_0 = d.restrict([Integer(0)])
>>> d_using_0
Dancing links solver for 7 columns and 6 rows
>>> d_using_0.rows()
[[0, 1, 2, 6], [3, 4, 5], [0, 1], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]

After restriction the subproblem has one more columns and the same number of rows as the original one:

sage: d.restrict([1]).rows()
[[0, 1, 2], [3, 4, 5, 6], [0, 1], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]
sage: d.restrict([2]).rows()
[[0, 1, 2], [3, 4, 5], [0, 1, 6], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]
>>> from sage.all import *
>>> d.restrict([Integer(1)]).rows()
[[0, 1, 2], [3, 4, 5, 6], [0, 1], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]
>>> d.restrict([Integer(2)]).rows()
[[0, 1, 2], [3, 4, 5], [0, 1, 6], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]

This method allows to find solutions where the \(0\)-th row is part of a solution:

sage: sorted(map(sorted, d.restrict([0]).solutions_iterator()))
[[0, 1]]
>>> from sage.all import *
>>> sorted(map(sorted, d.restrict([Integer(0)]).solutions_iterator()))
[[0, 1]]

Some other examples:

sage: sorted(map(sorted, d.restrict([1]).solutions_iterator()))
[[0, 1]]
sage: sorted(map(sorted, d.restrict([2]).solutions_iterator()))
[[2, 3]]
sage: sorted(map(sorted, d.restrict([3]).solutions_iterator()))
[[2, 3]]
>>> from sage.all import *
>>> sorted(map(sorted, d.restrict([Integer(1)]).solutions_iterator()))
[[0, 1]]
>>> sorted(map(sorted, d.restrict([Integer(2)]).solutions_iterator()))
[[2, 3]]
>>> sorted(map(sorted, d.restrict([Integer(3)]).solutions_iterator()))
[[2, 3]]

Here there are no solutions using both 0th and 3rd row:

sage: list(d.restrict([0,3]).solutions_iterator())
[]
>>> from sage.all import *
>>> list(d.restrict([Integer(0),Integer(3)]).solutions_iterator())
[]
rows()[source]¶

Return the list of rows.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [1,2], [0]]
sage: x = dlx_solver(rows)
sage: x.rows()
[[0, 1, 2], [1, 2], [0]]
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(1),Integer(2)], [Integer(0)]]
>>> x = dlx_solver(rows)
>>> x.rows()
[[0, 1, 2], [1, 2], [0]]
search()[source]¶

Search for a new solution.

Return 1 if a new solution is found and 0 otherwise. To recover the solution, use the method get_solution().

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2]]
sage: rows+= [[0,2]]
sage: rows+= [[1]]
sage: rows+= [[3]]
sage: x = dlx_solver(rows)
sage: print(x.search())
1
sage: print(x.get_solution())
[3, 0]
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)]]
>>> rows+= [[Integer(0),Integer(2)]]
>>> rows+= [[Integer(1)]]
>>> rows+= [[Integer(3)]]
>>> x = dlx_solver(rows)
>>> print(x.search())
1
>>> print(x.get_solution())
[3, 0]
solutions_iterator()[source]¶

Return an iterator of the solutions.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> d = dlx_solver(rows)
>>> sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
split(column)[source]¶

Return a dict of independent solvers.

For each i-th row containing a 1 in the column, the dict associates the solver giving all solution using the i-th row.

This is used for parallel computations.

INPUT:

  • column – integer; the column used to split the problem into independent subproblems

OUTPUT: dict where keys are row numbers and values are dlx solvers

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: d
Dancing links solver for 6 columns and 6 rows
sage: sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(3),Integer(4),Integer(5)], [Integer(0),Integer(1)], [Integer(2),Integer(3),Integer(4),Integer(5)], [Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]]
>>> d = dlx_solver(rows)
>>> d
Dancing links solver for 6 columns and 6 rows
>>> sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]

After the split each subproblem has one more column and the same number of rows as the original problem:

sage: D = d.split(0)
sage: D
{0: Dancing links solver for 7 columns and 6 rows,
 2: Dancing links solver for 7 columns and 6 rows,
 4: Dancing links solver for 7 columns and 6 rows}
>>> from sage.all import *
>>> D = d.split(Integer(0))
>>> D
{0: Dancing links solver for 7 columns and 6 rows,
 2: Dancing links solver for 7 columns and 6 rows,
 4: Dancing links solver for 7 columns and 6 rows}

The (disjoint) union of the solutions of the subproblems is equal to the set of solutions shown above:

sage: for x in D.values(): sorted(map(sorted, x.solutions_iterator()))
[[0, 1]]
[[2, 3]]
[[4, 5]]
>>> from sage.all import *
>>> for x in D.values(): sorted(map(sorted, x.solutions_iterator()))
[[0, 1]]
[[2, 3]]
[[4, 5]]
to_milp(solver=None)[source]¶

Return the mixed integer linear program (MILP) representing an equivalent problem.

See also sage.numerical.mip.MixedIntegerLinearProgram.

INPUT:

  • solver – string or None (default: None); possible values include 'GLPK', 'GLPK/exact', 'Coin', 'CPLEX', 'Gurobi', 'CVXOPT', 'PPL', 'InteractiveLP'

OUTPUT:

  • MixedIntegerLinearProgram instance

  • MIPVariable with binary components

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [0,2], [1], [3]]
sage: d = dlx_solver(rows)
sage: p,x = d.to_milp()                                                     # needs sage.numerical.mip
sage: p                                                                     # needs sage.numerical.mip
Boolean Program (no objective, 4 variables, ... constraints)
sage: x                                                                     # needs sage.numerical.mip
MIPVariable with 4 binary components
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(0),Integer(2)], [Integer(1)], [Integer(3)]]
>>> d = dlx_solver(rows)
>>> p,x = d.to_milp()                                                     # needs sage.numerical.mip
>>> p                                                                     # needs sage.numerical.mip
Boolean Program (no objective, 4 variables, ... constraints)
>>> x                                                                     # needs sage.numerical.mip
MIPVariable with 4 binary components

In the reduction, the boolean variable \(x_i\) is True if and only if the \(i\)-th row is in the solution:

sage: p.show()                                                              # needs sage.numerical.mip
Maximization:


Constraints:...
  one 1 in 0-th column: 1.0 <= x_0 + x_1 <= 1.0
  one 1 in 1-th column: 1.0 <= x_0 + x_2 <= 1.0
  one 1 in 2-th column: 1.0 <= x_0 + x_1 <= 1.0
  one 1 in 3-th column: 1.0 <= x_3 <= 1.0
Variables:
  x_0 is a boolean variable (min=0.0, max=1.0)
  x_1 is a boolean variable (min=0.0, max=1.0)
  x_2 is a boolean variable (min=0.0, max=1.0)
  x_3 is a boolean variable (min=0.0, max=1.0)
>>> from sage.all import *
>>> p.show()                                                              # needs sage.numerical.mip
Maximization:
<BLANKLINE>
<BLANKLINE>
Constraints:...
  one 1 in 0-th column: 1.0 <= x_0 + x_1 <= 1.0
  one 1 in 1-th column: 1.0 <= x_0 + x_2 <= 1.0
  one 1 in 2-th column: 1.0 <= x_0 + x_1 <= 1.0
  one 1 in 3-th column: 1.0 <= x_3 <= 1.0
Variables:
  x_0 is a boolean variable (min=0.0, max=1.0)
  x_1 is a boolean variable (min=0.0, max=1.0)
  x_2 is a boolean variable (min=0.0, max=1.0)
  x_3 is a boolean variable (min=0.0, max=1.0)

Using some optional MILP solvers:

sage: d.to_milp('gurobi')           # optional - gurobi sage_numerical_backends_gurobi, needs sage.numerical.mip
(Boolean Program (no objective, 4 variables, 4 constraints),
 MIPVariable with 4 binary components)
>>> from sage.all import *
>>> d.to_milp('gurobi')           # optional - gurobi sage_numerical_backends_gurobi, needs sage.numerical.mip
(Boolean Program (no objective, 4 variables, 4 constraints),
 MIPVariable with 4 binary components)
to_sat_solver(solver=None)[source]¶

Return the SAT solver solving an equivalent problem.

Note that row index \(i\) in the dancing links solver corresponds to the boolean variable index \(ì+1\) for the SAT solver to avoid the variable index \(0\).

See also sage.sat.solvers.satsolver.

INPUT:

  • solver – string or None (default: None), possible values include 'picosat', 'cryptominisat', 'LP', 'glucose', 'glucose-syrup'.

OUTPUT: SAT solver instance

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [0,2], [1], [3]]
sage: x = dlx_solver(rows)
sage: s = x.to_sat_solver()                                                 # needs sage.sat
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)], [Integer(0),Integer(2)], [Integer(1)], [Integer(3)]]
>>> x = dlx_solver(rows)
>>> s = x.to_sat_solver()                                                 # needs sage.sat

Using some optional SAT solvers:

sage: x.to_sat_solver('cryptominisat')      # optional - pycryptosat        # needs sage.sat
CryptoMiniSat solver: 4 variables, 7 clauses.
>>> from sage.all import *
>>> x.to_sat_solver('cryptominisat')      # optional - pycryptosat        # needs sage.sat
CryptoMiniSat solver: 4 variables, 7 clauses.
sage.combinat.matrices.dancing_links.dlx_solver(rows)[source]¶

Internal-use wrapper for the dancing links C++ code.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2]]
sage: rows+= [[0,2]]
sage: rows+= [[1]]
sage: rows+= [[3]]
sage: x = dlx_solver(rows)
sage: print(x.search())
1
sage: print(x.get_solution())
[3, 0]
sage: print(x.search())
1
sage: print(x.get_solution())
[3, 1, 2]
sage: print(x.search())
0
>>> from sage.all import *
>>> from sage.combinat.matrices.dancing_links import dlx_solver
>>> rows = [[Integer(0),Integer(1),Integer(2)]]
>>> rows+= [[Integer(0),Integer(2)]]
>>> rows+= [[Integer(1)]]
>>> rows+= [[Integer(3)]]
>>> x = dlx_solver(rows)
>>> print(x.search())
1
>>> print(x.get_solution())
[3, 0]
>>> print(x.search())
1
>>> print(x.get_solution())
[3, 1, 2]
>>> print(x.search())
0
sage.combinat.matrices.dancing_links.make_dlxwrapper(s)[source]¶

Create a dlx wrapper from a Python string s.

This was historically used in unpickling and is kept for backwards compatibility. We expect s to be dumps(rows) where rows is the list of rows used to instantiate the object.

Next
Dancing links C++ wrapper
Previous
Combinatorics on matrices
Copyright © 2005--2025, The Sage Development Team
Made with Sphinx and @pradyunsg's Furo
On this page
  • Dancing Links internal pyx code
    • dancing_linksWrapper
      • all_solutions()
      • get_solution()
      • ncols()
      • nrows()
      • number_of_solutions()
      • one_solution()
      • one_solution_using_milp_solver()
      • one_solution_using_sat_solver()
      • reinitialize()
      • restrict()
      • rows()
      • search()
      • solutions_iterator()
      • split()
      • to_milp()
      • to_sat_solver()
    • dlx_solver()
    • make_dlxwrapper()