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)
(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
NOTE: This documentation pertains to the dlxlib@next release of dlxlib.
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
See the migration guide.