DEV Community

Mary
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;
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);
}
Enter fullscreen mode Exit fullscreen mode

}

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]++;
   }
 }
Enter fullscreen mode Exit fullscreen mode

}
}

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;
Enter fullscreen mode Exit fullscreen mode

}
}

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);
 }
Enter fullscreen mode Exit fullscreen mode

}

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();
     }
   }
 }
Enter fullscreen mode Exit fullscreen mode

}

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

AWS Q Developer image

Your AI Code Assistant

Automate your code reviews. Catch bugs before your coworkers. Fix security issues in your code. Built to handle large projects, Amazon Q Developer works alongside you from idea to production code.

Get started free in your IDE

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay