1.0.3 • Published 5 years ago
dlxlib v1.0.3
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
Example
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]:
// step[1]: 0
// step[2]: 0,3
// step[3]: 0,3,4
// solution[0]: 0,3,4
// step[4]: 2
// step[5]: 2,1
// solution[1]: 2,1
// step[6]: 2,4
// step[7]: 2,4,5
// solution[2]: 2,4,5
2.0.0-alpha.2
5 years ago
2.0.0-alpha.1
5 years ago
1.0.3
7 years ago
1.0.2
7 years ago
1.0.1
7 years ago
1.0.0
7 years ago