DancingLinks.DancingLinksModule

Exported:

• exactcover(matrix::Matrix{Bool}; docheck::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(startingstate::Vector{Int64}; verbose=false, maxsolutions=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
• vectorsanstype(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_linksMethod
    build_links() :: LinkedNode

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_columnMethod
    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_nanosecondsMethod
    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_coverMethod
    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.remove_columnMethod
    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.searchMethod

Actually 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.solveMethod
    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.solveMethod
    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`Method

vectorsanstype(vec::AbstractVector)::String

Example

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