DancingLinks

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.

    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.

    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.

    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"

    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.

    reinsert_column(head::LinkedNode)

    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.

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).

    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().

    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).

vectorsanstype(vec::AbstractVector)::String

Example

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