Mary

Posted on

# Error with DLX algorithm

Hi.Welcome back everyone
My script is:
`class Node {
constructor(row, col) {
this.row = row;
this.col = col;
this.up = null;
this.down = null;
this.left = null;
this.right = null;
}
}

class Matrix {
constructor(rows, columns) {
this.rows = rows;
this.columns = columns;
this.matrix = [];

``````for (let i = 0; i < rows; i++) {
const row = new Array(columns).fill(0);
this.matrix.push(row);
}
``````

}

getColumnNodes(col) {
const nodes = [];
for (let i = 0; i < this.rows; i++) {
if (this.matrix[i][col] === 1) {
nodes.push(new Node(i, col));
}
}
return nodes;
}

setEntry(row, col, value) {
this.matrix[row][col] = value;
}

getEntry(row, col) {
return this.matrix[row][col];
}

print() {
for (let i = 0; i < this.rows; i++) {
console.log(this.matrix[i].join(' '));
}
}

getRow(row) {
return this.matrix[row];
}

getColumn(col) {
const column = [];
for (let i = 0; i < this.rows; i++) {
column.push(this.matrix[i][col]);
}
return column;
}

getNumRows() {
return this.rows;
}

getNumColumns() {
return this.columns;
}
}

class DLX {
constructor(matrix) {
this.root = new Node(-1, -1);
this.root.left = this.root;
this.root.right = this.root;
this.matrix = matrix;
this.cols = [];
this.solutionRows = [];
this.solutions = [];
this.initialize();
}

initialize() {
const numRows = this.matrix.getNumRows();
const numCols = this.matrix.getNumColumns();

for (let i = 0; i < numCols; i++) {
const header = new Node(-1, i);
this.cols.push(0);
}

for (let i = 0; i < numRows; i++) {
let last = null;
for (let j = 0; j < numCols; j++) {
if (this.matrix.getEntry(i, j) === 1) {
const node = new Node(i, j);
node.up.down = node;

``````     if (last === null) {
last = node;
} else {
node.left = last;
node.right = last.right;
last.right = node;
node.right.left = node;
last = node;
}

this.cols[j]++;
}
}
``````

}
}

cover(col) {

for (let node = header.down; node !== header; node = node.down) {
for (let j = node.right; j !== node; j = j.right) {
j.down.up = j.up;
j.up.down = j.down;
this.cols[j.col]--;
}
}
}

uncover(col) {

`````` for (let node = header.up; node !== header; node = node.up) {
for (let j = node.left; j !== node; j = j.left) {
j.down.up = j;
j.up.down = j;
}
}

if (col.right) {
col.right.left = col;
}

if (col.left) {
col.left.right = col;
}

``````

}
}

search() {
if (this.root.right === this.root) {
this.solutions.push([...this.solutionRows]);
return;
}

let minCols = Infinity;
let colNode = null;

for (let node = this.root.right; node !== this.root; node = node.right) {
if (this.cols[node.col] < minCols) {
minCols = this.cols[node.col];
colNode = node;
}
}

this.cover(colNode);

for (let rowNode = colNode.down; rowNode !== colNode; rowNode = rowNode.down) {
this.solutionRows.push(rowNode.row);

`````` for (let j = rowNode.right; j !== rowNode; j = j.right) {
}

this.search();
this.solutionRows.pop();

for (let j = rowNode.left; j !== rowNode; j = j.left) {
}
``````

}

this.uncover(colNode);
}

getSolutions() {
while (this.root.right !== this.root) {
this.search();
this.solutionRows = [];

`````` if (this.root.right === this.root) {
break;
}

for (let i = 0; i < this.cols.length; i++) {
if (this.cols[i] === 0) {
continue;
}

const nodes = this.matrix.getColumnNodes(i);
const candidates = [];

for (const node of nodes) {
candidates.push(node.row);

if (candidates.length === 2) {
let isValid = true;

for (const solution of this.solutions) {
if (
solution.indexOf(candidates[0]) === -1 ||
solution.indexOf(candidates[1]) === -1
) {
isValid = false;
break;
}
}

if (isValid) {
this.solutionRows.push([...candidates]);
break;
}

candidates.pop();
}
}
}
``````

}

return this.solutions;
}
}

function getCoveringDesign() {
const v = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
const k = 3;
const t = 2;
const matrix = new Matrix(v.length * (v.length - 1) * (v.length - 2), v.length);

for (let i = 0; i < v.length; i++) {
for (let j = i + 1; j < v.length; j++) {
for (let l = j + 1; l < v.length; l++) {
const row = new Array(v.length).fill(0);
row[i] = 1;
row[j] = 1;
row[l] = 1;
matrix.matrix.push(row);
}
}
}

const dlx = new DLX(matrix);
const solutions = dlx.getSolutions();
let minSize = Infinity;
let bestSolution = null;

for (const solution of solutions) {
if (solution.length < minSize) {
minSize = solution.length;
bestSolution = solution;
}
}

const blocks = [];

for (const indices of bestSolution) {
const block = [];
for (const index of indices) {
block.push(v[index]);
}
blocks.push(block);
}

return blocks;
}

console.log(getCoveringDesign());`

It gives error: