Description

This is a JavaScript library to solve exact cover problems by implementing Donald E. Knuth's Algorithm X using the Dancing Links technique.

• Knuth's original paper
• Knuth's Algorithm X (Wikipedia)
• Dancing Links (Wikipedia)
• Exact cover (Wikipedia)

Demos

(These projects are hosted on the Heroku free tier so may take 10s or so to spin up)

• Visualisation of solving a Sudoku puzzle
• Visualisation of solving a Tetris Cube puzzle
• Visualisation of solving a Ripple Effect puzzle
  • demonstrates use of secondary columns
• Pentominoes
  • demonstrates use of a web worker to do the solving

Documentation

NOTE: This documentation pertains to the dlxlib@next release of dlxlib.

• https://taylorjg.github.io/dlxlibjs

Example

NOTE: This example pertains to the dlxlib@next release of dlxlib.

const { Dlx } = require('dlxlib')

const matrix = [
  [1, 0, 0, 0],
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 1],
  [0, 1, 0, 0],
  [0, 0, 1, 0]
]

const onStep = e =>
  console.log(`step[${e.stepIndex}]: ${e.partialSolution}`)

const onSolution = e =>
  console.log(`solution[${e.solutionIndex}]: ${e.solution}`)

const dlx = new Dlx()
dlx.on('step', onStep)
dlx.on('solution', onSolution)
dlx.solve(matrix)

// step[0]: 0
// step[1]: 0,3
// step[2]: 0,3,4
// solution[0]: 0,3,4
// step[3]: 2
// step[4]: 2,1
// solution[1]: 2,1
// step[5]: 2,4
// step[6]: 2,4,5
// solution[2]: 2,4,5

Migrating from 1.0.3 to 2.0.0

See the migration guide.