Skip to content
/ dlx Public

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

Notifications You must be signed in to change notification settings

dimchansky/dlx

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

20 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

dlx Build Status Coverage Status Godoc

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]

About

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

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages