messiaendancing-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
`javascript
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.