node package manager

dlx

Knuth's Dancing Links algorithm for the exact cover problem

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: