goverture

README

Go Cover Solver

A Go library for solving exact cover problems using Donald Knuth's Algorithm X with the Dancing Links technique (DLX).

Features

• Solve exact cover problems efficiently.
• Simple API to integrate into your Go projects.
• Solutions are streamed via a Go channel for flexibility in handling results.

Installation

To install the library, run the following command:

go get github.com/goverture/exact_cover

Usage

You can use this library to solve exact cover problems by passing a 2D matrix (slice of slices) to the SolveDLX function. The function returns a channel that streams solutions.

Example

package main

import (
	"context"
	"fmt"

	cover_solver "github.com/goverture/exact_cover"
)

func main() {
    matrix := [][]int{
        {1, 0, 0, 1, 0, 0, 1},
        {1, 0, 0, 1, 0, 0, 0},
        {0, 0, 0, 1, 1, 0, 1},
        {0, 1, 1, 0, 0, 1, 0},
        {0, 1, 0, 0, 0, 0, 1},
        {0, 0, 1, 1, 1, 0, 0},
    }

    ctx := context.Background()
    solutions := cover_solver.SolveDLX(ctx, matrix)

    for solution := range solutions {
        fmt.Println("Solution:", solution)
    }
}

Function Signature

// SolveDLX initiates the DLX search and returns a channel of solutions
func SolveDLX(ctx context.Context, matrix [][]int) <-chan [][]int

• ctx context.Context: Used for cancellation and deadlines.
• matrix [][]int: The matrix representing the exact cover problem.
• Returns: A channel that streams all valid solutions ([][]int).

License

This project is licensed under the MIT License. See the LICENSE file for details.

Documentation

Index

• Variables
• func BuildDLX(itemsCount int, options <-chan SparseRow, isSecondaryColumn func(int) bool) ([]Column, []Node)
• func BuildDLXAsNeeded(ctx context.Context, matrixChan <-chan WordOption, ...) (*column, error)
• func Cover(col *column) bool
• func FindRowIndex(matrix SparseMatrix, row SparseRow) (int, bool)
• func InitializeRoot() *column
• func SolveDLX(ctx context.Context, matrix SparseMatrix, tickerPeriod time.Duration) <-chan Solution
• func SolveDLXWithChannel(ctx context.Context, matrixChan <-chan WordOption, tickerPeriod time.Duration) <-chan Solution
• func SolveDLXWithChannelAndSecondary(ctx context.Context, matrixChan <-chan WordOption, ...) <-chan Solution
• func SolveDLXWithSecondary(ctx context.Context, matrix SparseMatrix, isSecondaryColumn func(int) bool, ...) <-chan Solution
• func SolveExactCover(ctx context.Context, columns []Column, nodes []Node, solution []AppInt, ...) error
• func Uncover(col *column)
• type AppInt
• type Column
• type Node
• type NodeVisitor
• type Solution
• type SparseMatrix
  • func SparseMatrixFromArray(matrix [][]int) SparseMatrix
• type SparseRow
  • func RebuildRowFromNode(n *node) SparseRow
• type WordOption

Variables

var ThematicColsForPrimaryColsIDX map[int][]*column

Functions

func BuildDLX

func BuildDLX(itemsCount int, options <-chan SparseRow, isSecondaryColumn func(int) bool) ([]Column, []Node)

func BuildDLXAsNeeded

func BuildDLXAsNeeded(ctx context.Context, matrixChan <-chan WordOption, isSecondaryColumn func(int) bool) (*column, error)

BuildDLXAsNeeded constructs the Dancing Links structure from the sparse matrix by creating columns lazily (on-demand) as rows are processed. It listens for context cancellation and terminates early if the context is canceled. Returns the root column and an error if the context was canceled.

func Cover

func Cover(col *column) bool

Cover removes a column from the header list and primary columns list

func FindRowIndex

func FindRowIndex(matrix SparseMatrix, row SparseRow) (int, bool)

findRowIndex returns the index of the row in the matrix that matches the given row slice.

func InitializeRoot

func InitializeRoot() *column

InitializeRoot creates and initializes the root header

func SolveDLX

func SolveDLX(
	ctx context.Context,
	matrix SparseMatrix,
	tickerPeriod time.Duration,
) <-chan Solution

SolveDLX initiates the DLX search and returns a channel of solutions (each a SparseMatrix).

func SolveDLXWithChannel

func SolveDLXWithChannel(ctx context.Context, matrixChan <-chan WordOption, tickerPeriod time.Duration) <-chan Solution

func SolveDLXWithChannelAndSecondary

func SolveDLXWithChannelAndSecondary(
	ctx context.Context,
	matrixChan <-chan WordOption,
	isSecondaryColumn func(int) bool,
	tickerPeriod time.Duration,
) <-chan Solution

func SolveDLXWithSecondary

func SolveDLXWithSecondary(
	ctx context.Context,
	matrix SparseMatrix,
	isSecondaryColumn func(int) bool,
	tickerPeriod time.Duration,
) <-chan Solution

SolveDLXWithSecondary initiates the DLX search with secondary columns and returns a channel of solutions (each a SparseMatrix).

func SolveExactCover

func SolveExactCover(
	ctx context.Context,
	columns []Column,
	nodes []Node,
	solution []AppInt,
	solutions chan<- []int,
	ticker <-chan time.Time,
) error

Implementation of the Algorithm X ("Exact cover via dancing links") from Knuth's paper

func Uncover

func Uncover(col *column)

Uncover restores a previously covered column and updates the primary columns list

Types

type AppInt

type AppInt int32

AppInt is the base integer type used throughout the application

type Column

type Column struct {
	Name  string
	Llink AppInt
	Rlink AppInt
}

type Node

type Node struct {
	Top   AppInt
	Ulink AppInt
	Dlink AppInt
}

type NodeVisitor

type NodeVisitor func(depth int)

NodeVisitor is called at each depth for debugging or counting

type Solution

type Solution struct {
	IsFinal bool
	Matrix  SparseMatrix
}

Solution represents a solution with a flag indicating if it's final.

type SparseMatrix

type SparseMatrix []SparseRow

func SparseMatrixFromArray

func SparseMatrixFromArray(matrix [][]int) SparseMatrix

Helper function to convert a 2D array of ints to a SparseMatrix

type SparseRow

type SparseRow map[int]int

Type definitions for SparseRow, SparseMatrix, and Solution

func RebuildRowFromNode

func RebuildRowFromNode(n *node) SparseRow

type WordOption

type WordOption struct {
	Row              SparseRow
	Word             string
	IsThematic       bool
	ThematicColIndex int
}