sudoku.js

class Board {
  /**
   * @param {string[]} rows 
   */
  constructor(rows) {
    this.cells = new Array(9).fill(0).map(row => new Array(9).fill(0));
    this.fixedCells = new Array(9).fill(0).map(row => new Array(9).fill(false));

    if (rows) {
      for (let row = 0; row < rows.length; row++) {
        const values = rows[row].split(' ');
        for (let col = 0; col < values.length; col++) {
          const v = parseInt(values[col]);
          this.cells[row][col] = v;

          if (v !== 0) {
            this.fixedCells[row][col] = true;
          } else {
            this.fixedCells[row][col] = false;
          }
        }
      }
    }
  }

  /**
   * @param {number[]} summary
   * @returns {boolean}
   */
  isSummaryOk(summary) {
    // we shouldn't have a zero on the board
    if (summary[0] !== 0) {
      return false;
    }

    // and we shouldn't have duplicates or missing values
    for (let i = 1; i < 10; i++) {
      if (summary[i] !== 1) {
        return false;
      }
    }

    return true;
  };

  /**
   * @returns {boolean}
   */
  isSolved() {
    //  validate rows
    for (let row = 0; row < 9; row++) {
      // ten elements
      const summary = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

      for (let col = 0; (col < 9); col++) {
        const value = this.cells[row][col];
        summary[value]++;
      }

      if (!this.isSummaryOk(summary)) {
        return false;
      }
    }

    //  validate columns
    for (let col = 0; col < 9; col++) {
      const summary = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

      for (let row = 0; (row < 9); row++) {
        const value = this.cells[row][col];
        summary[value]++;
      }

      if (!this.isSummaryOk(summary)) {
        return false;
      }
    }

    // validate quadrant
    for (let i = 0; i <= 6; i += 3) {
      for (let j = 0; j <= 6; j += 3) {
        if (!this.isQuadrantValid(i, j)) {
          return false;
        }
      }
    }

    return true;
  };

  /**
   * 
   * @param {number} startRow 
   * @param {number} startCol
   * @returns {boolean}
   */
  isQuadrantValid(startRow, startCol) {
    const summary = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

    for (let i = startRow; i < startRow + 3; i++) {
      for (let j = startCol; j < startCol + 3; j++) {
        let value = this.cells[i][j];
        summary[value]++;
      }
    }

    return this.isSummaryOk(summary);
  }

  /**
   * 
   * @param {number} row 
   * @param {number} col 
   * @param {number} n 
   * @returns {boolean}
   */
  isPlayValid(row, col, n) {
    //  validate rows
    for (let r = 0; r < 9; r++) {
      if (this.cells[r][col] === n) {
        return false;
      }
    }

    //  validate columns
    for (let c = 0; c < 9; c++) {
      if (this.cells[row][c] === n) {
        return false;
      }
    }

    //  validate 3x3 matrix
    let br = Math.floor(row / 3);
    let bc = Math.floor(col / 3);
    for (let r = br * 3; r < (br + 1) * 3; r++) {
      for (let c = bc * 3; c < (bc + 1) * 3; c++) {
        if (this.cells[r][c] === n) {
          return false;
        }
      }
    }

    return true;
  }

  /**
   * @returns {string}
   */
  toString() {
    let boardStr = '';

    let cont = 0;
    for (let r = 0; r < 9; r++) {
      let contx = 0;

      for (let c = 0; c < 9; c++) {
        boardStr += this.cells[r][c] + ' ';
        contx++;
        if ((contx == 3) || (contx == 6)) {
          boardStr += "| ";
        }
      }

      boardStr = boardStr.trim();
      boardStr += '\n';

      cont++;
      if ((cont == 3) || (cont == 6)) {
        boardStr += "---------------------";
        boardStr += '\n';
      }

    }

    return boardStr;
  }


}

class Section {
  /**
   * 
   * @param {number} id 
   * @param {number} score 
   */
  constructor(id, score) {
    this.id = id;
    this.score = score;
  }
}

class Solver {
  /**
   * 
   * @param {Board} board 
   * @returns {Board}
   */
  solve(board) {
    // optimize board
    // reorder so that we have the sections with more hints in the upper section (reduces the
    // search space)
    let sections = this.scoreSections(board);

    let swapInstructions = {};

    let sortedSections = sections.slice().sort((a, b) => b.score - a.score);

    let s = 0;
    for (let sortedSection of sortedSections) {
      // from ---> to
      swapInstructions[sortedSection.id] = s;
      s++;
    }

    let swappedBoard = this.swapSections(board, sections, swapInstructions);

    // solve using backtracking
    this.backtrack(swappedBoard);

    // validate that the board is solved
    if (swappedBoard.isSolved()) {
      // restore original section order
      let swapBackInstructions = {};
      for (let instruction of Object.entries(swapInstructions)) {
        const [key, value] = instruction;
        swapBackInstructions[value] = key;
        s++;
      }

      return this.swapSections(swappedBoard, sections, swapBackInstructions);
    } else {
      return null;
    }
  }

  /**
   * 
   * @param {Board} board 
   * @returns {Section[]}
   */
  scoreSections(board) {
    // calculate how many fixed values we have in the upper, middle and bottom sections
    let upperScore = 0;
    let middleScore = 0;
    let bottomScore = 0;

    for (let row = 0; row < 9; row++) {
      let score = 0;
      for (let col = 0; col < 9; col++) {
        if (board.fixedCells[row][col]) {
          score++;
        }
      }

      if (row < 3) {
        upperScore += score;
      } else {
        if (row < 6) {
          middleScore += score;
        } else {
          bottomScore += score;
        }
      }
    }

    var sections = [];
    sections.push(new Section(0, upperScore));
    sections.push(new Section(1, middleScore));
    sections.push(new Section(2, bottomScore));

    return sections;
  }

  /**
   * 
   * @param {Board} board 
   * @returns {void}
   */
  backtrack(board) {
    //  backtracing iterative version
    let row = 0;
    let col = 0;
    let n;
    let num = 1;

    //  if row = 9 then we have found a solution (matrix range is from 0 to 8)
    start:
    while (row < 9) {
      if (!board.fixedCells[row][col]) {
        for (n = num; n <= 9; n++) {
          if (board.isPlayValid(row, col, n)) {
            //  move forward
            //  increment poisition and start searching from 1 again for the next value
            board.cells[row][col] = n;
            col++;
            if (col > 8) {
              col = 0;
              row++;
            }
            num = 1;
            continue start;
          }
        }
      } else {
        // increment poisition and start searching from 1 again for the next value
        col++;
        if (col > 8) {
          col = 0;
          row++;
        }
        num = 1;
        continue start;
      }

      //  if it arrives here then no value is valid for the cell, so we need to go back
      //  clean the current cell
      board.cells[row][col] = 0;
      //  decrease position, we need to go back to the first non fixed cell
      while (true) {
        col--;
        if (col < 0) {
          col = 8;
          row--;
        }

        if (!board.fixedCells[row][col]) {
          break;
        }

      }

      // increase the value of the cell in order to keep searching for the solution
      num = board.cells[row][col] + 1;
    }
  }

  /**
   * 
   * @param {Board} board 
   * @param {Section[]} sections
   * @param {Record<number, number>} swapInstructions 
   * @returns {Board}
   */
  swapSections(board, sections, swapInstructions) {
    const tmpBoard = new Board();

    for (let section of sections) {

      let fromSection = section.id;
      let toSection = swapInstructions[fromSection];
      let rowFrom = fromSection * 3;
      let rowTo = toSection * 3;

      for (let i = rowFrom; i < rowFrom + 3; i++) {
        for (let j = 0; j < 9; j++) {
          tmpBoard.cells[rowTo][j] = board.cells[i][j];
          tmpBoard.fixedCells[rowTo][j] = board.fixedCells[i][j];
        }
        rowTo++;
      }
    }

    return tmpBoard;
  }
}

function Main() {
  console.time('Sudoku - Plain JS');

  const longest = [
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 3 0 8 5",
    "0 0 1 0 2 0 0 0 0",
    "0 0 0 5 0 7 0 0 0",
    "0 0 4 0 0 0 1 0 0",
    "0 9 0 0 0 0 0 0 0",
    "5 0 0 0 0 0 0 7 3",
    "0 0 2 0 1 0 0 0 0",
    "0 0 0 0 4 0 0 0 9"
  ];

  const board = new Board(longest);
  const solver = new Solver();
  const solved = solver.solve(board);
  if (solved) {
    console.log(solved.toString());
  } else {
    console.log('NOT SOLVED');
  }
  console.log("--------------------------------");

  console.timeEnd('Sudoku - Plain JS');
}


Main();