`DancingLinks.DancingLinks`

— Module**DancingLinks**

**Exported:**

- exact
*cover(matrix::Matrix{Bool}; do*check::Bool) #`matrix`

is the 'Exact Cover' incidence matrix

Initializes global vars `incidence_matrix`

, `nrows`

, `ncols`

. This must be executed before function `solve`

is called.

solve(; verbose=false, max_solutions=1, deterministic=false) ::Bool

solve(starting

*state::Vector{Int64}; verbose=false, max*solutions=1, deterministic=false) ::Bool`starting_state `List of rows by indices into the provided constraint matrix (global var `incidence_matrix`) that should be removed - they are "given" as part of the solution.` [verbose] `Sets global `VERBOSE` flag; print timings, etc.` [max_solutions] `Sets global `SOLUTIONSMAX`; number of solutions to find before returning.` [deterministic] `Sets global `DO_DETERMINISTICALLY; false=select rows at random.``

solutions

The resulting list of solutions found (each solution is a Vector{Int64} of row indices into the global `incidence_matrix`

and is ordered).

- convert_nanoseconds(nanosecs::Real; ncols::Integer=0, units::Union{Nothing, Symbol}=nothing, omitunits::Bool=false)::String
- vector
*sans*type(vec::AbstractVector)::String

**Example:**

```
`# build your incidence matrix first, a Matrix{Bool}`
exact_cover(matrix)
solve() # get a random solution (without 'givens')
```

Refer to the package "Sudoku2" for a thorough testing of this "DancingLinks" implementation.

`DancingLinks.build_links`

— Method` build_links() :: LinkedNode`

Build the doubly-linked toroidal lists.

Given the matrix, this builds the linked list that models it. It constructs all the column headers, then a node for each element in the column that is true. It links each element to its North, South, East, and West neighbors.

There are only N + H + 1 nodes in the mesh, where N is the number of 1's in the matrix, and H is the number of discrete columns in which those 1's appear. It is not necessary to create a LinkedNode for empty places in the matrix. This is especially important for sparse matrices, such as those modelling Sudoku or other problems.

`DancingLinks.choose_column`

— Method` choose_column() :: Union{Nothing, LinkedNode} -> column.head`

Choose and return a column's head deterministically to eliminate from the matrix.

The heuristic of using a column with the fewest 1's tends to make the search run much more quickly.

`DancingLinks.convert_nanoseconds`

— Method```
convert_nanoseconds(nanosecs::UInt64; # from time_ns() function
[ncols]::Integer = 0, # < 0 = discard leading zero values; print most significant column first (cf examples below)
[units]::Union{Nothing, Symbol}=nothing, # != nothing : eg. :ms; last columns is in these units
# otherwise last column is arbitrary units
# units = :d, :h, :m, {:s|:sec}, :ms, {:mus|μs}, :ns
[omitunits]::Bool=false # whether or not to print the units string
)::String
```

This function is to be used in conjunction with, for eg, `time_ns()`

**Examples**

```
t = 1.500600e9 # nanoseconds
convert_nanoseconds(t, ncols = 0, units=nothing) -> "01:500:600μs"
convert_nanoseconds(t, ncols = +1, units=nothing) -> "1500600μs"
convert_nanoseconds(t, ncols = -1, units=nothing) -> "2s"
convert_nanoseconds(t, ncols = +2, units=nothing) -> "1500:600μs"
convert_nanoseconds(t, ncols = -2, units=nothing) -> "01:501ms"
convert_nanoseconds(t, ncols = +3, units=:ms) -> "00:01:501ms"
convert_nanoseconds(t, ncols = -3, units=:ms) -> "01:501ms"
```

`DancingLinks.exact_cover`

— Method```
exact_cover(matrix::Matrix{Bool}; do_check::Bool)
matrix `The incidence matrix`
do_check `Whether to check for invalid rows or columns.
(This will slow the execution time.)`
```

Initialize globals `incidence_matrix`

, `nrows`

, `ncols`

.

`DancingLinks.reinsert_column`

— Method` reinsert_column(head::LinkedNode)`

`DancingLinks.remove_column`

— Method` remove_column(head::LinkedNode)`

Remove(cover) the head from the links-matrix along with all of it's rows.

Guard against removing the same column twice.

If we try to remove the same column twice, the pointers get corrupted. Must not do this!

Normally, there's no need to check to see if a column has already been removed. If the algorithm is correctly implemented, it will never try to remove a column twice.

BUT ! Supposing an incorrect Sudoku puzzle, which is not solvable (for example, there are two 9's in a single row), then it can result in the same column being removed twice, for the "givens".

So this safety flag protects against bad input.

`DancingLinks.search`

— MethodActually perform the search for the exact cover.

It does its work recursively, choosing a column heuristically and covering it, then randomly choosing a row to "try" when searching for the next candidate.

The solution state is maintained in global `solution_state`

, a Vector. When the matrix is solved, `solution_state`

lists the rows that provide the exact cover (the solution).

`DancingLinks.solve`

— Method```
solve(starting_state::Vector{Int64}; verbose=false, max_solutions=1, deterministic=false) :: Bool
starting_state `List of rows by indices into the provided constraint matrix (global `incidence_matrix`)
that should be removed - they are "given" as part of the solution.`
[verbose] `Sets global `VERBOSE` flag; print timings.`
[max_solutions] `Sets global `SOLUTIONSMAX`; number of solutions to find before returning.`
[deterministic] `Sets global `DO_DETERMINISTICALLY; false=select rows at random.`
```

Solve the constraint matrix, global `incidence_matrix`

.

Returns whether a solution was found or not.

You must have first set the global `incidence_matrix`

with function `exact_cover()`

.

`DancingLinks.solve`

— Method```
solve(; verbose=false, max_solutions=1, deterministic=false) :: Bool
[verbose] `Sets global `VERBOSE` flag; print timings, etc.`
[max_solutions] `Sets global `SOLUTIONSMAX`; number of solutions to find before returning.`
[deterministic] `Sets global `DO_DETERMINISTICALLY; false=select rows at random.`
```

Solve the constraint matrix, global `incidence_matrix`

.Solve with no givens.

Returns whether a solution was found or not.

This is useful when the matrix provided in global `incidence_matrix`

is the actual matrix (ie. there are no `givens`

).

`DancingLinks.vector_sans_type`

— Methodvector*sans*type(vec::AbstractVector)::String

**Example**

foo() = nothing l = [[:abc, nothing, foo], [:def, 'V', 2.0], [:ghi, "abc"]] # foo is a Function println(vector*sans*type(l))