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
The number of solutions:
sage: x.number_of_solutions()
3
Iterate over the solutions:
sage: 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]]
Return the first solution found when the computation is done in parallel:
sage: sorted(x.one_solution(ncpus=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]]
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
There is also a method reinitialize
to reinitialize the algorithm:
sage: x.reinitialize()
sage: x.search()
1
sage: x.get_solution()
[0, 1]

class
sage.combinat.matrices.dancing_links.
dancing_linksWrapper
¶ Bases:
object
A simple class that implements dancing links.
The main methods to list the solutions are
search()
andget_solution()
. You can also usenumber_of_solutions()
to count them.This class simply wraps a C++ implementation of Carlo Hamalainen.

all_solutions
(ncpus=None, column=None)¶ 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. IfNone
, it detects the number of effective CPUs in the system usingsage.parallel.ncpus.ncpus()
.column
– integer (default:None
), the column used to split the problem, ifNone
a random column is chosen
OUTPUT:
list of solutionsEXAMPLES:
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]]
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]]
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]]

get_solution
()¶ 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
()¶ 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

nrows
()¶ 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

number_of_solutions
(ncpus=None, column=None)¶ 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. IfNone
, it detects the number of effective CPUs in the system usingsage.parallel.ncpus.ncpus()
.column
– integer (default:None
), the column used to split the problem, ifNone
a random column is chosen (this argument is ignored ifncpus
is1
)
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
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
sage: S = Subsets(range(5)) sage: rows = map(list, S) sage: d = dlx_solver(rows) sage: d.number_of_solutions() 52

one_solution
(ncpus=None, column=None)¶ 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. IfNone
, it detects the number of effective CPUs in the system usingsage.parallel.ncpus.ncpus()
. Ifncpus=1
, the first solution is searched serially.column
– integer (default:None
), the column used to split the problem (seerestrict()
). IfNone
, a random column is chosen. This argument is ignored ifncpus=1
.
OUTPUT:
list of rows or
None
if no solution is foundNote
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
The number of CPUs can be specified as input:
sage: sorted(d.one_solution(ncpus=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
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

reinitialize
()¶ 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]
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
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

restrict
(indices)¶ 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 solverEXAMPLES:
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]]
To impose that the 0th 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]]
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]]
This method allows to find solutions where the 0th row is part of a solution:
sage: sorted(map(sorted, d.restrict([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]]
Here there are no solution using both 0th and 3rd row:
sage: list(d.restrict([0,3]).solutions_iterator()) []

rows
()¶ 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]]

search
()¶ Search for a new solution.
Return
1
if a new solution is found and0
otherwise. To recover the solution, use the methodget_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]

solutions_iterator
()¶ 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]]

split
(column)¶ Return a dict of independent solvers.
For each
i
th row containing a1
in thecolumn
, the dict associates the solver giving all solution using thei
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 solversEXAMPLES:
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]]
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}
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]]


sage.combinat.matrices.dancing_links.
dlx_solver
(rows)¶ Internaluse 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

sage.combinat.matrices.dancing_links.
make_dlxwrapper
(s)¶ 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.