⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

[[WP:Algorithm_X|"Algorithm X"]] is the name Donald Knuth used in his paper "Dancing Links" to refer to "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem. This is an implementation of based on that paper.

The Rosetta Code tasks this can used for include:

• [[Pentomino tiling]]
• [[N-queens problem]]
• [[Sudoku]]

## Go

```// Package dlx is an implementation of Knuth's Dancing Links for algorithm X
// to solve a generalized cover problem.
//
// See:
//     arXiv:cs/0011047
// An alternative implementation can be found within:
//     https://rosettacode.org/wiki/Sudoku#Go
package dlx

import (
"bufio"
"errors"
"fmt"
"io"
"strings"
)

// x is Knuth's data object.
type x struct {
left, right *x      // row links
up, down    *x      // column links
col         *column // column list header
}

// column is Knuth's column object.
type column struct {
x
size int // number of 1's in column
id   int // XXX name string?
}

// Matrix represents the matrix for a generalized cover problem.
type Matrix struct {
root    *x       // up, down, col fields unused
sol     []*x     // solution so far
cells   []x      // pre-allocated cells
stats   []stat

maxCols int      // maximum number of columns seen in any row constraint
}

type stat struct {
nodes   int
}

// New returns a new DLX Matrix with the specified number of columns
func New(primaryCols, secondaryCols int) *Matrix {
return NewWithHint(primaryCols, secondaryCols, 0, 0)
}

// NewWithHint is like New but provides an allocation hint for the
// estimated number of cells and estimated maximum number of rows in
// solutions.
func NewWithHint(primaryCols, secondaryCols, estCells, estSolutionRows int) *Matrix {
n := primaryCols + secondaryCols
m := &Matrix{
sol:     make([]*x, 0, estSolutionRows),
cells:   make([]x, estCells+1), // +1 to use as the root
stats:   make([]stat, 0, estSolutionRows),
}
m.root = &m.cells[0]
m.cells = m.cells[1:]
m.root.left.right = m.root
prev := m.root
for i := 0; i < n; i++ {
c.id = i
c.col = c
c.up = &c.x
c.down = &c.x
if i < primaryCols {
c.left = prev
prev.right = &c.x
prev = &c.x
} else {
c.left = &c.x
c.right = &c.x
}
}
return m
}

// 'cols' indicates which column indices should have a 1 for this row.
func (m *Matrix) AddRow(cols []int) {
if len(cols) == 0 {
return
}
if len(cols) > m.maxCols {
m.maxCols = len(cols)
}
var buf []x
if len(cols) <= len(m.cells) {
buf = m.cells[:len(cols)]
m.cells = m.cells[len(cols):]
} else {
buf = make([]x, len(cols))
}
//sort.Ints(cols) // not strictly required
prev := &buf[len(cols)-1]
for i, id := range cols {
c.size++
x := &buf[i]
x.col = c
x.up = c.up
x.down = &c.x
x.left = prev
x.up.down = x
x.down.up = x
prev.right = x
prev = x
}
}

// SearchFunc is the type of the function called for each solution
// found by Matrix.Search.
//
// The pseudo error value Stop may be returned to indication the search
// should terminate without error.
type SearchFunc func(*Matrix) error

// Stop is used as a return value from SearchFuncs to indicate that
// the search should terminate instead of continuing to search for
// alternative solutions.
// It is not returned as an error by any function.
var Stop = errors.New("terminate search")

func (m *Matrix) callFn(fn SearchFunc) error {
return fn(m)
}

// SolutionString returns a text representation of
// the solution using the provided column names.
func (m *Matrix) SolutionString(names []string) string {
var buf strings.Builder
_ = m.SolutionWrite(&buf, names)
return buf.String()
}

// SolutionWrite writes a text representation of the
// solution to `w` using the provided column names.
func (m *Matrix) SolutionWrite(w io.Writer, names []string) error {
bw := bufio.NewWriter(w)
for _, x := range m.sol {
n := names[x.col.id]
fmt.Fprint(bw, n)
for j := x.right; j != x; j = j.right {
n = names[j.col.id]
fmt.Fprint(bw, " ", n)
}
fmt.Fprintln(bw)
}
return bw.Flush()
}

// SolutionIDs writes the column IDs of the solution
// to `buf` and returns the extended slice.
func (m *Matrix) SolutionIDs(buf [][]int) [][]int {
if cap(buf) < len(m.sol) {
new := make([][]int, len(buf), len(m.sol))
copy(new, buf)
buf = new
}
solIDs := buf[:len(m.sol)]
for i, x := range m.sol {
n := 1
min := x
for j := x.right; j != x; j = j.right {
n++
if j.col.id < min.col.id {
min = j
}
}
ids := solIDs[i]
if cap(ids) < n {
ids = make([]int, 1, m.maxCols)
} else {
ids = ids[:1]
}
ids[0] = min.col.id
for j := min.right; j != min; j = j.right {
ids = append(ids, j.col.id)
}
//sort.Ints(ids) // not strictly required
solIDs[i] = ids
}
return solIDs
}

// ProfileString returns profiling output as a string.
func (m *Matrix) ProfileString() string {
var buf strings.Builder
_ = m.ProfileWrite(&buf)
return buf.String()
}

// ProfileWrite writes profiling output to `w`.
func (m *Matrix) ProfileWrite(w io.Writer) error {
bw := bufio.NewWriter(w)
var total stat
for _, s := range m.stats {
total.nodes += s.nodes
}
for i, s := range m.stats {
pn := float64(s.nodes) / float64(total.nodes) * 100.0
fmt.Fprintf(bw, "%5d %8d  (%2.0f%%) %10d  (%2.0f%%) %14.1f\n",
i, s.nodes, pn, s.updates, pu, per)
}
fmt.Fprintf(bw, "Total %8d (100%%) %10d (100%%) %14.1f\n",
return bw.Flush()
}

// Search runs Knuth's algorithm X on `m`
// and for each solution found calls `fn`.
func (m *Matrix) Search(fn SearchFunc) error {
if len(m.sol) > 0 {
return errors.New("recursive call to Matrix.Search")
}
err := m.search(fn)
if err == Stop {
return nil
}
return err
}

func (m *Matrix) search(fn SearchFunc) error {
k := len(m.sol)
j := m.root.right
if j == m.root {
return m.callFn(fn)
}
c := j.col
if true { // Knuth's "S heuristic"
for j = j.right; j != m.root; j = j.right {
if j.col.size < c.size {
c = j.col
}
}
}
if c.size < 1 {
return nil
}
if len(m.stats) <= k {
m.stats = append(m.stats, stat{})
}
s := &m.stats[k]
s.nodes += c.size

cover(c, s)
m.sol = append(m.sol, nil)
for r := c.down; r != &c.x; r = r.down {
m.sol[k] = r
for j = r.right; j != r; j = j.right {
cover(j.col, s)
}
if err := m.search(fn); err != nil {
return err
}
for j = r.left; j != r; j = j.left {
uncover(j.col)
}
}

m.sol = m.sol[:k]
uncover(c)
return nil
}

func cover(c *column, s *stat) {
c.right.left, c.left.right = c.left, c.right
for i := c.down; i != &c.x; i = i.down {
for j := i.right; j != i; j = j.right {
j.down.up, j.up.down = j.up, j.down
j.col.size--
}
}
}

func uncover(c *column) {
for i := c.up; i != &c.x; i = i.up {
for j := i.left; j != i; j = j.left {
j.col.size++
j.down.up, j.up.down = j, j
}
}
c.right.left, c.left.right = &c.x, &c.x
}
```