Error with DLX algorithm
Tags: javascript, errors, dlx, algorithms
Published: 2023-12-02 18:05:34


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