Error with DLX algorithm

Mary — Sat, 02 Dec 2023 18:05:34 +0000

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;
this.header = 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();
const headerNodes = [];

for (let i = 0; i < numCols; i++) {
const header = new Node(-1, i);
header.left = this.root.left;
header.right = this.root;
this.root.left.right = header;
this.root.left = header;
header.up = header;
header.down = header;
headerNodes.push(header);
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.header = headerNodes[j];
node.up = node.header.up;
node.down = node.header;
node.header.up = node;
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) {
const header = col.header;
header.left.right = header.right;
header.right.left = header.left;

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) {
if (col.header) {
const header = col.header;

 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;
     j.header.cols++;
   }
 }

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

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

 header.left = col;
 header.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.cover(j.header);
 }

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

 for (let j = rowNode.left; j !== rowNode; j = j.left) {
   this.uncover(j.header);
 }

}

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:
Uncaught TypeError: Cannot read properties of null (reading 'left')
at DLX.uncover
at DLX.search
at DLX.getSolutions
at getCoveringDesign

Any suggestions? Thanks

DEV Community: Mary

Error with DLX algorithm