dlx

dlx is a Go implementation of Knuth's algorithm DLX (algorithm X implemented in terms of dancing links)

A fantastic explanation of dancing links algorithm can be found here (PDF).

Installation

go get github.com/dimchansky/dlx

Examples

There is sudoku solver included. The solver code provides an example of using dlx library to solve Sudoku.

Consider the exact cover problem specified by the matrix:

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 1 | 0 | 0 | 1 | 0 | 0 | 1 | | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | 0 | 0 | 0 | 1 | 1 | 0 | 1 | | 0 | 0 | 1 | 0 | 1 | 1 | 0 | | 0 | 1 | 1 | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

The following code finds all solutions to the exact cover problem:

m := dlx.NewMatrix(7)
m.AddRow(0, 3, 6)
m.AddRow(0, 3)
m.AddRow(3, 4, 6)
m.AddRow(2, 4, 5)
m.AddRow(1, 2, 5, 6)
m.AddRow(1, 6)

m.Solve(dlx.SolutionAccepterFunc(func(exactCover [][]int) bool {
	fmt.Println("Solution found:")
	for _, row := range exactCover {
		fmt.Println(row)
	}
	return false
}))

The code output:

Solution found:
[0 3]
[2 4 5]
[1 6]