JavaScript Sudoku Recursive Solver

Question

Thanks for all the great feedback in Part 1. I implemented a lot of it. Here is version 2. I am looking for feedback on:

• Recursive solve algorithm. It's too slow. I used Chrome DevTools Performance Profiler to optimize slow functions and I sped it up a lot. But fundamentally I think the algorithm just sucks.
• The slowest, hardest test puzzle I've found so far is the following. It would be good to be able to solve this puzzle in a short amount of time (couple of seconds). 400030000000600800000000001000050090080000600070200000000102700503000040900000000

Fiddle

https://jsfiddle.net/AdmiralAkbar2/80qgkps6/5/

Screenshot

Performance

// getSolutionCountRecursively speed, with limit set to 50,000
// 2508ms initially
// 2186ms added/refactored getTrueKey
// 1519ms added/refactored cloneBoard
//  789ms added/refactored squareIsSolved
//  298ms added/refactored setBoard
//  170ms commented out RegEx in get_legal_move

`use strict`;

class SudokuBoard {
  constructor() {
    // Not pretty, but I declare the same thing 3 times for performance. Else I have to deep copy the blank_board array, which is expensive according to Chrome devtools performance profile.
    this.blank_board = [
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0]
    ];
    this.board = [
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0]
    ];
    this.original_board = [
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0]
    ];
  }

  // This is only meant for use by getSolutionCountRecursively. Faster than set_board
  // Everything else should use set_board. set_board performs more data validation.
  setBoard(board) {
    this.board = board;
  }

  static cloneBoard(board) {
    let array = [
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0]
    ];
    for ( let i = 0; i < 9; i++ ) {
      for ( let j = 0; j < 9; j++ ) {
        array[i][j] = board[i][j];
      }
    }
    return array;

    // return Helper.deepCopyArray(board);
  }

  // returns if board changed or not
  set_board(board_string) {
    const old_board = SudokuBoard.cloneBoard(this.board);

    if ( ! board_string ) {
      return false;
    }

    if ( ! board_string.match(/^[0-9*_.]{81}$/m) ) {
      return false;
    }

    // TODO: foreach getBoardSquares
    for ( let row = 0; row < 9; row++ ) {
      for ( let column = 0; column < 9; column++ ) {
        let char = board_string.charAt(row*9+column);
        if ( char === `*` || char === `_` || char === `.` )
        {
          char = 0;
        }
        this.board[row][column] = parseInt(char);
      }
    }

    if ( ! this.puzzleIsValid() ) {
      this.board = SudokuBoard.cloneBoard(old_board);
      return false;
    }

    this.set_original_board(this.board);

    return true;
  }

  get_board() {
    return this.board;
  }

  getString() {
    let str = ``;
    for ( let row = 0; row < 9; row++ ) {
      for ( let col = 0; col < 9; col++ ) {
        str += this.board[row][col];
      }
    }
    return str;
  }

  // making this its own method to help with debugging
  set_original_board(obj) {
    this.original_board = SudokuBoard.cloneBoard(obj);
  }

  restart_puzzle() {
    this.board = SudokuBoard.cloneBoard(this.original_board);
  }

  make_move(row, col, value) {
    if ( value === `` ) {
      value = 0;
    }
    this.board[row][col] = value;
  }

  getSquaresOnBoard() {
    let squares = [];
    for ( let i = 0; i < 9; i++ ) {
      for ( let j = 0; j < 9; j++ ) {
        const value = this.board[i][j];
        squares.push(new SudokuSquare(i, j, value));
      }
    }
    return squares;
  }











  // TODO: consider splitting the below code into a SudokuSolver class
  // I haven't done it yet because I'd have to pass a board variable around. That's a lot of code re-writing. Not sure it's worth it.

  puzzleIsValid() {
    try {
      this.process_of_elimination(false, false);
    } catch {
      return false;
    }
    return true;
  }

  is_legal_move(row, col, value, checkForNonNumbers = true) {
    value = parseInt(value);

    // check for non numbers
    // Regex is very expensive. Only check this for user input.
    if ( checkForNonNumbers ) {
      if ( ! value.toString().match(/^[1-9]$/m) ) {
        return false;
      }
    }

    // check row
    // TODO: foreach getRowSquares
    for ( let i = 0; i < 9; i++ ) {
      if ( value === this.board[row][i] ) {
        return false;
      }
    }

    // check column
    // TODO: foreach getColumnSquares
    for ( let i = 0; i < 9; i++ ) {
      if ( value === this.board[i][col] ) {
        return false;
      }
    }

    // check 3x3 grid
    // TODO: foreach getBoxSquares
    const row_offset = Math.floor(row/3)*3;
    const col_offset = Math.floor(col/3)*3;
    for ( let i = 0 + row_offset; i <= 2 + row_offset; i++ ) {
      for ( let j = 0 + col_offset; j <= 2 + col_offset; j++ ) {
        if ( value === this.board[i][j] ) {
          return false;
        }
      }
    }

    return true;
  }

  // Possibilities {1:true, 2:true, 3:true, 4:true, 5:true, 6:true, 7:true, 8:true, 9:true}
  static squareIsSolved(possibilities) {
    let trueCount = 0;
    for ( let i = 1; i <= 9; i++ ) {
      if ( possibilities[i] ) {
        trueCount++;
      }
      if ( trueCount >= 2 ) {
        return false;
      }
    }
    if ( trueCount === 1 ) {
      return true;
    }
    return false;
  }

  // If 8 of 9 squares are filled in, fill in 9th square.
  process_of_elimination(hint_mode = false, modifyBoard = true) {
    let possibilities;
    let empty_col;
    let empty_row;

    // check row
    for ( let row = 0; row < 9; row++ ) {
      // bool array [true, true, true] is faster than list [1, 2, 3]
      possibilities = {1:true, 2:true, 3:true, 4:true, 5:true, 6:true, 7:true, 8:true, 9:true};
      empty_col = 0;

      for ( let col = 0; col < 9; col++ ) {
        const value = this.board[row][col];
        if ( value === 0 ) {
          empty_col = col;
          continue;
        } else if ( possibilities[value] ) {
          possibilities[value] = false;
        } else {
          this.throw_duplicate_number_error();
        }
      }

      if ( SudokuBoard.squareIsSolved(possibilities) ) {
        if ( hint_mode ) {
          return new SudokuSquare(row, empty_col);
        } else if ( modifyBoard ) {
          this.board[row][empty_col] = SudokuBoard.getTrueKey(possibilities);
        }
      }
    }

    // check column
    for ( let col = 0; col < 9; col++ ) {
      possibilities = {1:true, 2:true, 3:true, 4:true, 5:true, 6:true, 7:true, 8:true, 9:true};
      empty_row = 0;

      for ( let row = 0; row < 9; row++ ) {
        const value = this.board[row][col];
        if ( value === 0 ) {
          empty_row = row;
          continue;
        } else if ( possibilities[value] ) {
          possibilities[value] = false;
        } else {
          this.throw_duplicate_number_error();
        }
      }

      if ( SudokuBoard.squareIsSolved(possibilities) ) {
        if ( hint_mode ) {
          return new SudokuSquare(empty_row, col);
        } else if ( modifyBoard ) {
          this.board[empty_row][col] = SudokuBoard.getTrueKey(possibilities);
        }
      }
    }

    // check 3x3 grid
    for ( let row = 0; row < 9; row+=3 ) {
      for ( let col = 0; col < 9; col+=3 ) {
        possibilities = {1:true, 2:true, 3:true, 4:true, 5:true, 6:true, 7:true, 8:true, 9:true};
        empty_row = 0;
        empty_col = 0;

        const row_offset = Math.floor(row/3)*3;
        const col_offset = Math.floor(col/3)*3;
        // iterate around 3x3 area
        for ( let i = 0 + row_offset; i <= 2 + row_offset; i++ ) {
          for ( let j = 0 + col_offset; j <= 2 + col_offset; j++ ) {
            const value = this.board[i][j];
            if ( value === 0 ) {
              empty_row = i;
              empty_col = j;
              continue;
            } else if ( possibilities[value] ) {
              possibilities[value] = false;
            } else {
              this.throw_duplicate_number_error();
            }
          }
        }

        if ( SudokuBoard.squareIsSolved(possibilities) ) {
          if ( hint_mode ) {
            return new SudokuSquare(empty_row, empty_col);
          } else if ( modifyBoard ) {
            this.board[empty_row][empty_col] = SudokuBoard.getTrueKey(possibilities);
          }
        }
      }
    }
  }

  puzzleIsSolved() {
    for ( let i = 0; i < 9; i++ ) {
      for ( let j = 0; j < 9; j++ ) {
        if ( this.board[i][j] === 0 ) {
          return false;
        }
      }
    }
    return true;				
  }

  getNumberOfSolutions() {
    if ( ! this.puzzleIsValid() ) {
      this.throw_duplicate_number_error();
      return 0;
    }

    if ( this.puzzleIsSolved() ) {
      window.alert('Puzzle is already solved');
      return 1;
    }

    const initialRecursionTracker = new RecursionTracker();
    const initialSudoku = new SudokuBoard();
    initialSudoku.setBoard(SudokuBoard.cloneBoard(this.board));
    initialRecursionTracker.setSudokuToCheck(initialSudoku);

    const finalRecursionTracker = this.getSolutionCountRecursively(initialRecursionTracker);
    const numberOfSolutions = finalRecursionTracker.getNumberOfSolutions();
    const boardsChecked = finalRecursionTracker.getBoardsChecked();

    console.log(`Number of solutions: ` + numberOfSolutions);
    console.log(`Boards checked: ` + boardsChecked);

    // window.alert(`Puzzle has ${numberOfSolutions} solutions`);
    return finalRecursionTracker;
  }

  getSolutionCountRecursively(recursionTracker) {
    // for first recursion, recursionTracker will be
      // this.numberOfSolutions = 0;
      // this.solutionSudokuList = null;
      // this.sudokuToCheck = Sudoku;
      // this.boardsChecked = 0;
    // No need to clone recursionTracker. Just keep using the same one.

    // Benchmark History (with limit set to 50,000)
      // 2508ms initially
      // 2186ms added/refactored getTrueKey
      // 1519ms added/refactored cloneBoard
      //  789ms added/refactored squareIsSolved
      //  298ms added/refactored setBoard
      //  170ms commented out RegEx in get_legal_move

    const RECURSION_LIMIT = 500000;

    if ( recursionTracker.getNumberOfSolutions() > 500 ) {
      return recursionTracker;
    }

    if ( recursionTracker.getBoardsChecked() > RECURSION_LIMIT ) {
      recursionTracker.markEarlyExit();
      return recursionTracker;
    }

    const currentSudoku = recursionTracker.getSudokuToCheck();

    // foreach boardsquare
    for ( let square of currentSudoku.getSquaresOnBoard() ) {
      // if square is empty
      if ( square.getValue() === 0 ) {
        // for each possible number 1-9
        for ( let i = 1; i <= 9; i++ ) {
          if ( recursionTracker.getBoardsChecked() > RECURSION_LIMIT ) {
            recursionTracker.markEarlyExit();
            return recursionTracker;
          }

          const row = square.getRow();
          const col = square.getCol();

          if ( currentSudoku.is_legal_move(row, col, i, false) ) {
            recursionTracker.incrementBoardsChecked();

            // create new Sudoku
            let nextSudoku = new SudokuBoard();

            const board = SudokuBoard.cloneBoard(currentSudoku.board);
            nextSudoku.setBoard(board);

            // make move
            nextSudoku.make_move(row, col, i);

            // console.log(currentSudoku.getString());

            if ( nextSudoku.puzzleIsSolved() ) {
              recursionTracker.addSolution(nextSudoku);
              recursionTracker.incrementBoardsChecked();
              // console.log(nextSudoku.getString());
            } else {
              recursionTracker.setSudokuToCheck(nextSudoku);
              recursionTracker = this.getSolutionCountRecursively(recursionTracker);
            }
          }
        }
      }
    }

    return recursionTracker;
  }

  static getTrueKey(array) {
    let count = 0;
    let trueKey = false;
    for ( let key in array ) {
      if ( array[key] ) {
        trueKey = key;
        count++;
      }
    }
    if ( count === 1 ) {
      return parseInt(trueKey);
    } else {
      return false;
    }
  }
}

class RecursionTracker {
  constructor() {
    this.numberOfSolutions = 0;
    this.solutionList = [];
    this.sudokuToCheck = null;
    this.boardsChecked = 0;
    this.earlyExit = false;
  }

  getNumberOfSolutions() {
    return this.solutionList.length;
  }

  getInfoString() {
    let string = ``;
    string += this.getBoardsChecked() + ` Boards Checked\r\n`;
    string += this.solutionList.length + ` Solutions Found\r\n`;
    if ( this.earlyExit ) {
      string += `Recursion Limit Reached. Exited Early.\r\n`;
    }
    if ( this.solutionList.length !== 0 ) {
      string += `Solutions:\r\n`;
    }
    for ( let solutionString of this.solutionList ) {
      string += solutionString + `\r\n`;
    }
    return string;
  }

  getSudokuToCheck() {
    return this.sudokuToCheck;
  }

  getBoardsChecked() {
    return this.boardsChecked;
  }

  markEarlyExit() {
    this.earlyExit = true;
  }

  addSolution(sudoku) {
    const sudokuStringToCheck = sudoku.getString();
    if ( ! this.solutionList.includes(sudokuStringToCheck) ) {
      this.solutionList.push(sudokuStringToCheck);
    }
  }

  setSudokuToCheck(sudoku) {
    this.sudokuToCheck = sudoku;
  }

  incrementBoardsChecked() {
    this.boardsChecked++;
  }
}

class SudokuSquare {
  constructor(row, col, value = 0) {
    this.row = parseInt(row);
    this.col = parseInt(col);
    this.value = parseInt(value);
  }

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

  getRow() {
    return this.row;
  }

  getCol() {
    return this.col;
  }

  getValue() {
    return this.value;
  }

  setValue(row, col) {
    this.row = row;
    this.col = col;
  }
}

class SudokuDOM {
  static display_board(
    sudoku_object,
    sudoku_squares,
    string_box,
    sudoku_wiki_link,
    change_square_color = true
  ) {
    const board = sudoku_object.get_board();
    this.clear_board(sudoku_squares, change_square_color);
    for ( let row = 0; row < 9; row++ ) {
      for ( let col = 0; col < 9; col++ ) {
        const input = sudoku_squares[row][col];
        input.classList.remove(`hint`);
        input.disabled = false;

        if ( board[row][col] != 0 ) {
          input.value = board[row][col];
          if ( change_square_color ) {
            input.classList.add(`imported-square`);
            input.disabled = true;
          }
        }
      }
    }
    SudokuDOM.display_string(sudoku_object, string_box, sudoku_wiki_link);
  }

  static display_string(sudoku_object, string_box, sudoku_wiki_link) {
    string_box.value = sudoku_object.getString();
    sudoku_wiki_link.href = `https://www.sudokuwiki.org/SudokuBoard.htm?bd=` + sudoku_object.getString();	
  }

  static clear_board(sudoku_squares, change_square_color = true) {
    for ( let row = 0; row < 9; row++ ) {
      for ( let col = 0; col < 9; col++ ) {
        sudoku_squares[row][col].value = ``;
        if ( change_square_color ) {
          sudoku_squares[row][col].classList.remove(`imported-square`);
        }
      }
    }
  }

  static highlight_illegal_move(obj){
    obj.classList.add(`invalid`);
    setTimeout(function(){
      obj.classList.remove(`invalid`);
    }, 2000);
  }
}

class Helper {
  static createArray(length) {
    var arr = new Array(length || 0), i = length;
    if (arguments.length > 1) {
      var args = Array.prototype.slice.call(arguments, 1);
      while ( i-- ) {
        arr[length-1 - i] = Helper.createArray.apply(this, args);
      }
    }
    return arr;
  }
}

// Listeners
window.addEventListener(`DOMContentLoaded`, (e) => {
  // DOM elements stored as constants
  const sudoku_table = document.getElementById(`sudoku`);
  const restart_button = document.getElementById(`restart`);
  const import_button = document.getElementById(`import`);
  const new_button = document.getElementById(`new`);
  const string_box = document.getElementById(`string-box`);
  const puzzle_picker = document.getElementById(`puzzle_picker`);
  const sudoku_wiki_link = document.getElementById(`sudoku-wiki-link`);
  const algorithm = document.getElementById(`algorithm`);
  const validate_button = document.getElementById(`validate`);
  const consoleBox = document.getElementById(`console`);

  const game1 = new SudokuBoard();
  const sudoku_squares = Helper.createArray(9,9);
  const CUSTOM_PUZZLE_SELECTEDINDEX = 3;
  const DEFAULT_PUZZLE_SELECTEDINDEX = 4;

  // Store all the Sudoku square <input type=`text`> elements in variables for quick accessing
  for ( let row = 0; row < 9; row++ ) {
    for ( let col = 0; col < 9; col++ ) {
      sudoku_squares[row][col] = sudoku_table.rows[row].cells[col].children[0];
    }
  }

  for ( let row = 0; row < 9; row++ ) {
    for ( let col = 0; col < 9; col++ ) {
      sudoku_squares[row][col].addEventListener(`input`, function(e) {
        e.target.classList.remove(`invalid`);
        e.target.classList.remove(`hint`);

        // Listen for illegal moves. If illegal, delete input and turn square red for 2 seconds.
        if ( ! game1.is_legal_move(row, col, e.target.value) && e.target.value != `` ) {
          e.target.value = ``;
          SudokuDOM.highlight_illegal_move(e.target);
        } else {
          game1.make_move(row, col, e.target.value);
        }

        SudokuDOM.display_string(game1, string_box, sudoku_wiki_link);
      });
    }
  }

  validate_button.addEventListener(`click`, function(e) {
    const t1 = performance.now();
    const recursionTracker = game1.getNumberOfSolutions();
    const t2 = performance.now();
    // TODO: display recursionTracker stuff like # of solutions, strings of the solutions, etc.
    document.querySelector(`#algorithm span`).innerHTML = (t2 - t1).toFixed(1);
    algorithm.style.display = `block`;
    consoleBox.children[0].innerHTML = recursionTracker.getInfoString();
    consoleBox.style.display = `block`;
  });

  restart_button.addEventListener(`click`, function(e) {
    game1.restart_puzzle();
    SudokuDOM.display_board(game1, sudoku_squares, string_box, sudoku_wiki_link);
  });

  import_button.addEventListener(`click`, function(e) {
    const board = window.prompt(`Please enter a sequence of 81 numbers, with 0 representing an empty square.`);
    const board_changed = game1.set_board(board);
    if ( board_changed ) {
      puzzle_picker.selectedIndex = CUSTOM_PUZZLE_SELECTEDINDEX;
      SudokuDOM.display_board(game1, sudoku_squares, string_box, sudoku_wiki_link);
    }
  });

  puzzle_picker.addEventListener(`change`, function(e) {
    if ( puzzle_picker.value === `import` ) {
      import_button.click();
    } else if ( puzzle_picker.value === `random` ) {
      new_button.click();
    } else {
      game1.set_board(puzzle_picker.value);
      SudokuDOM.display_board(game1, sudoku_squares, string_box, sudoku_wiki_link);
    }
  });

  // Pick the default puzzle. Trigger the <select>.change listener so the puzzle gets loaded.
  // selectedIndex starts from 0
  puzzle_picker.selectedIndex = DEFAULT_PUZZLE_SELECTEDINDEX;
  puzzle_picker.dispatchEvent(new Event(`change`));
});

body {font-family:sans-serif; background-color:#1E1E1E; color:white;}
p {margin-block-start:0; margin-block-end:0.5em;}
a {color:yellow;}
a:hover {color:orange;}
a:visited {color:yellow;}
nav {float:left; width:250px; height:100vh; background-color:#383838; padding:1em;}
article {float:left; padding:1em;}

.done {background-color:limegreen;}
.in-progress {background-color:yellow;}
.todo {background-color:red;}



#string-box {width:610px;}
#algorithm {display:none;}
#console {display:none;}
#console textarea {width:85ch; height:8em;}

.invalid {background-color:red;}
.imported-square {background-color:lightgray;}
.hint {background-color:limegreen;}

#sudoku {border:4px solid black; border-collapse: collapse; margin-bottom:0.5em;}
#sudoku tr {padding:0;}
#sudoku td {padding:0; border:2px solid black; width:35px; height:35px;}
#sudoku input {width:35px; height:35px; border:0; font-size:25pt; text-align:center; padding:0; color:black;}
#sudoku .thick-right {border-right:4px solid black;}
#sudoku .thick-bottom {border-bottom:4px solid black;}

<!DOCTYPE html>

<html lang="en-us">

<head>
  <title>Sudoku</title>
</head>

<body>

<p>
  <button id="import" class="done">Import</button>
  <button id="restart" class="done">Restart</button>
  <button id="validate" class="todo">Solve Recursively</button>
</p>

<p>
  <select id="puzzle_picker">
    <option value="000000000000000000000000000000000000000000000000000000000000000000000000000000000">[Blank Board]</option>
    <option value="import">[Import Puzzle]</option>
    <option value="custom">[Custom Puzzle]</option>
    <option value="123056789467000000580000000600000000700000000800000000000000000200000000300000000">Testing - Process Of Elimination</option>
    <option value="080165427145372968726984135871296354964531782532847691213759846497628513658413279">Testing - Solution Count 1</option>
    <option value="380160407140370968726980135870296354964501782532847601213059846497028513658403279">Testing - Solution Count 2</option>
    <!-- from https://www.sudokuwiki.org/ -->
    <option value="080100007000070960026900130000290304960000082502047000013009840097020000600003070">Beginner</option>
    <option value="240070038000006070300040600008020700100000006007030400004080009860400000910060002">Intermediate - Last Number In Row, Col, & Box</option>
    <option value="246070038000306074370040600008020700100000006007030400004080069860400007910060042">Intermediate - Naked Single</option>
  </select>
</p>

<table id="sudoku">
  <tbody>
    <tr>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
    <tr>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
    <tr class="thick-bottom">
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
    <tr>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
    <tr>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
    <tr class="thick-bottom">
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
    <tr>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
    <tr>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
    <tr>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td class="thick-right"><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
      <td><input type="text" maxlength="1" /></td>
    </tr>
  </tbody>
</table>

<p>
  <input id="string-box" type="text" />
</p>

<p>
  Or solve this using <a id="sudoku-wiki-link">Sudoku Wiki Solver</a>
</p>

<p id="algorithm">
  <span></span> ms
</p>

<p id="console">
  <textarea></textarea>
</p>

Answer 1

Performance

The main source of slowness is the lack of something: when an empty square is found and all possibilities for it have been tried, getSolutionCountRecursively does not return, it tries to fill in some other empty square. Filling in the board in a different order just results in the same boards being created but with a different "move history", which doesn't matter, so equal solutions are created many times over.

To make it explicit, the fix is this: (scroll to bottom)

getSolutionCountRecursively(recursionTracker) {
    
    const RECURSION_LIMIT = 500000;
    
    if ( recursionTracker.getNumberOfSolutions() > 500 ) {
        return recursionTracker;
    }
    
    if ( recursionTracker.getBoardsChecked() > RECURSION_LIMIT ) {
        recursionTracker.markEarlyExit();
        return recursionTracker;
    }
    
    const currentSudoku = recursionTracker.getSudokuToCheck();
    
    // foreach boardsquare
    for ( let square of currentSudoku.getSquaresOnBoard() ) {
        // if square is empty
        if ( square.getValue() === 0 ) {
            // for each possible number 1-9
            for ( let i = 1; i <= 9; i++ ) {
                if ( recursionTracker.getBoardsChecked() > RECURSION_LIMIT ) {
                    recursionTracker.markEarlyExit();
                    return recursionTracker;
                }
                
                const row = square.getRow();
                const col = square.getCol();
                
                if ( currentSudoku.is_legal_move(row, col, i, false) ) {
                    recursionTracker.incrementBoardsChecked();
                    
                    // create new Sudoku
                    let nextSudoku = new SudokuBoard();
                    
                    const board = SudokuBoard.cloneBoard(currentSudoku.board);
                    nextSudoku.setBoard(board);
                    
                    // make move
                    nextSudoku.make_move(row, col, i);
                    
                    if ( nextSudoku.puzzleIsSolved() ) {
                        recursionTracker.addSolution(nextSudoku);
                        recursionTracker.incrementBoardsChecked();
                    } else {
                        recursionTracker.setSudokuToCheck(nextSudoku);
                        recursionTracker = this.getSolutionCountRecursively(recursionTracker);
                    }
                }
            }
            return recursionTracker;  // <------------------- add this
        }
    }
    
    return recursionTracker;
}

With this, "Solution count 2" runs in around 2ms on my PC. A handful of minor tricks could be used to get the time down a bit more, I could go into them if you want, but nothing else is even in the same league as adding that extra return.

---

For fast solving of more dificult puzzles, also incorporate constraint propagation into the recursive solver. These are the techniques that you are already implementing in process_of_elimination, and more of them. Every time the recursive solver fills in a cell, iteratively apply these elimination steps to fill in as much of the board as possible.

What tends to happen then is that for an easy puzzle, the solution is found without any search, the iterative solving steps just finish it. For harder puzzles, once the resursive solver has filled some cells, the puzzle either becomes an easy puzzle or a conflict is detected.

Just filling in Naked Singles, the easiest propagation to implement, is already enough to solve your hard puzzle (300ms on my PC):

400030000
000600800
000000001
000050090
080000600
070200000
000102700
503000040
900000000 

But not yet enough for this other hard puzzle:

000000000
000003085
001020000
000507000
004000100
090000000
500000073
002010000
000040009

For example, filling in Naked Singles might look like this:

  propagate() {
    // For each row, column and block,
    // get a mask indicating which values are already present in it.
    let rowmask = new Int32Array(9);
    let colmask = new Int32Array(9);
    let blockmask = new Int32Array(9);
    for ( let i = 0; i < 9; i++ ) {
      for ( let j = 0; j < 9; j++ ) {
        rowmask[i] |= 1 << this.board[i][j];
        colmask[j] |= 1 << this.board[i][j];
        blockmask[(i / 3 | 0) * 3 + (j / 3 | 0)] |= 1 << this.board[i][j];
      }
    }
    
    // For each cell, get a mask indicating
    // which values are valid to fill in into it.
    // Excludes zero, as zero is the lack of a value.
    // For a filled cell, the only value it can have is the value it already has.
    // For empty cells, the possible values are values that
    // are not already used in the same row/column/block.
    let cellmask = new Int32Array(81);
    for ( let i = 0; i < 9; i++ ) {
      for ( let j = 0; j < 9; j++ ) {
        var mask = rowmask[i] | colmask[j] | blockmask[(i / 3 | 0) * 3 + (j / 3 | 0)];
        // invert to take the *unused* values
        // 0x3FE = 0011_1111_1110 (bits 1 to 9 are set)
        cellmask[i * 9 + j] = ~mask & 0x3FE;
        if ( this.board[i][j] !== 0 )
          cellmask[i * 9 + j] = 1 << this.board[i][j];
      }
    }

    var changed = false;
    do {
      changed = false;

      for ( let i = 0; i < 9; i++ ) {
        for ( let j = 0; j < 9; j++ ) {
          let mask = cellmask[i * 9 + j];                    
          if ( this.board[i][j] !== 0 ) continue;
          if ( mask === 0 ) return false;
          if ( this.isSingleSetBit(mask) ) {
            let move = this.getSetBitPos(mask);
            this.make_move(i, j, move);
            changed = true;
            
            // we just filled a cell with the value 'move' 
            // remove that as a possible value from cells in
            // the same row/column/block
            for ( let k = 0; k < 9; k++ ) {
              cellmask[i * 9 + k] &= ~(1 << move);
              cellmask[k * 9 + j] &= ~(1 << move);
            }
            for ( let k = 0; k < 3; k++ ) {
              for ( let l = 0; l < 3; l++ ) {
                cellmask[((i / 3 | 0) * 3 + k) * 9 + (j / 3 | 0) * 3 + l] &= ~(1 << move);
              }
            }
          }
        }
      }

    } while (changed);
    return true;
  }

  isSingleSetBit(x) {
    return x !== 0 && (x & -x) === x;
  }

  getSetBitPos(x) {
    for ( let i = 0; i < 31; i++ ) {
      if ((x & (1 << i)) !== 0)
        return i;
    }
    return -1;
  }

Though I'm not saying that this is the nicest way to do it.

The intended usage is:

// make move
nextSudoku.make_move(row, col, i);
// propagate forced-moves
if (!nextSudoku.propagate())
    continue;

Hidden Singles can be filtered with some more bitwise trickery. For example this filters them out of the rows only, turning them into Naked Singles which will immediately be detected:

  for ( let i = 0; i < 9; i++ ) {
    var m1 = 0;
    var m2 = 0;
    for ( let j = 0; j < 9; j++ ) {
      var m = cellmask[i * 9 + j];
      m2 |= m1 & m;
      m1 |= m;
    }
    for ( let j = 0; j < 9; j++ ) {
      var m = cellmask[i * 9 + j];
      m &= ~m2;
      if ( m !== 0 )
        cellmask[i * 9 + j] = m & -m;
    }
  }

(fiddle)

A similar thing can be done for columns and blocks.

Perhaps these bitwise tricks are not your style, of course the same effects can be accomplished with sets.