dlx

0.2.1 • Public • Published

dlx

An implementation of Knuth's Dancing Links algorithm for the exact cover problem. Many combinatoric problems, such as Sudoku and N-queens, can be reduced to exact cover problems and solved with the same algorithm.

Given a two-dimensional array of booleans, the problem is to select a subset of the rows that sums to [1, 1, 1, ..., 1]. In other words: for every column of the matrix, exactly one of the chosen rows must contain a one.

Usage:

var dlx = require("dlx");
var problem = [
    [0, 0, 1, 0, 1, 1, 0],
    [1, 0, 0, 1, 0, 0, 1],
    [0, 1, 1, 0, 0, 1, 0],
    [1, 0, 0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 1, 0, 1],
];

var solutions = dlx.solve(problem);
// solutions is [[0, 3, 4]]

Run tests:

$ npm install
$ npm test

See more:

Readme

Keywords

none

Package Sidebar

Install

npm i dlx

Weekly Downloads

829

Version

0.2.1

License

MIT

Last publish

Collaborators

  • jlaire