dancing-links-algorithm

About

This is implementation of Knuth's Algorithm X, called also Dancing Links Algorithm.

It lets you solve binary matrix, dictionary and sudoku as well.

Usage

const dlx = require('dancing-links-algorithm');

// algorithm finds all subsets of matrix rows, such that there is exactly one 1 in every column

let mat = [[1, 0, 0, 1, 0, 0, 1],
        [1, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 1, 0, 1],
        [0, 0, 1, 0, 1,	1, 0],
        [0, 1, 1, 0, 0, 1, 1],
        [0, 1, 0, 0, 0, 0, 1],
        [0, 1, 1, 0, 1, 1, 0]];

let solutions = dlx.solve(mat)
console.log(solutions)

// OUTPUT: [ [ '0', '6' ], [ '1', '3', '5' ] ]

for (let i = 0; i < solutions.length; i++) {
    console.log(`Solution No. ${i + 1}`);
    for (let j = 0; j < solutions[i].length; j++) {
        console.log(mat[solutions[i][j]]);
    }
}

// OUTPUT:
// Solution No. 1
// [ 1, 0, 0, 1, 0, 0, 1 ]
// [ 0, 1, 1, 0, 1, 1, 0 ]
// Solution No. 2
// [ 1, 0, 0, 1, 0, 0, 0 ]
// [ 0, 0, 1, 0, 1, 1, 0 ]
// [ 0, 1, 0, 0, 0, 0, 1 ]

// you can also pass object and elements as parameters

let elements = [1, 2, 3, 4, 5, 6, 7];
let dict = {
    'A': [1, 4, 7],
    'B': [1, 4],
    'C': [4, 5, 7],
    'D': [3, 5, 6],
    'E': [2, 3, 6, 7],
    'F': [2, 7],
    'H': [3, 7, 1, 2],
    'G': [4, 5, 6]
}

let sols = dlx.solve(elements, dict);
console.log(sols);

// OUTPUT: [ [ 'B', 'D', 'F' ], [ 'H', 'G' ] ]

// you can solve 9x9 sudoku

let sudoku = '050020108000100200820900050090540070047000083080000000000200004600030000210000000';
let sudokuSolutions = dlx.solve(sudoku);

console.log(sudokuSolutions.length); // OUTPUT: 21
for (let i = 0; i < sudokuSolutions.length; i++) {
    console.log(`Solution No. ${i + 1}`);
    console.log(sudokuSolutions[i]);
}

// OUTPUT: 
// Solution No. 1
// [ [ 7, 5, 9, 3, 2, 6, 1, 4, 8 ],
//   [ 4, 6, 3, 1, 8, 5, 2, 9, 7 ],
//   [ 8, 2, 1, 9, 7, 4, 3, 5, 6 ],
//   [ 3, 9, 2, 5, 4, 8, 6, 7, 1 ],
//   [ 1, 4, 7, 6, 9, 2, 5, 8, 3 ],
//   [ 5, 8, 6, 7, 1, 3, 4, 2, 9 ],
//   [ 9, 3, 8, 2, 5, 1, 7, 6, 4 ],
//   [ 6, 7, 5, 4, 3, 9, 8, 1, 2 ],
//   [ 2, 1, 4, 8, 6, 7, 9, 3, 5 ] ]
// Solution No. 2
// [ [ 7, 5, 9, 3, 2, 6, 1, 4, 8 ],
//   [ 4, 6, 3, 1, 8, 5, 2, 9, 7 ],
//   [ 8, 2, 1, 9, 7, 4, 3, 5, 6 ],
//   [ 3, 9, 2, 5, 4, 8, 6, 7, 1 ],
//   [ 5, 4, 7, 6, 1, 2, 9, 8, 3 ],
//   [ 1, 8, 6, 7, 9, 3, 4, 2, 5 ],
//   [ 9, 3, 8, 2, 5, 1, 7, 6, 4 ],
//   [ 6, 7, 5, 4, 3, 9, 8, 1, 2 ],
//   [ 2, 1, 4, 8, 6, 7, 5, 3, 9 ] ]
//
//      etc.