Soduko solving function takes forever with recursion

Question

class SudokuSolver {

  // check for string being sudoku
  validate(puzzleString) {
    const puzzleArr = puzzleString.split("")
    const digitCheck = puzzleArr.every( val => val.match(/[1-9]/) || val.match(/\./))
    const lengthCheck = puzzleArr.length == 81? true: false;
    const checkString = this.checkString(puzzleString)
    if(digitCheck && lengthCheck && checkString){
      return "valid"
    } 
    if(!lengthCheck){
        return "Expected puzzle to be 81 characters long"
    }
      if(!digitCheck){
        return "Invalid characters in puzzle"
      } 
    if(!checkString){
        return "Invalid puzzle string"
      } 
    }
 

  // check for string by digit.
  checkString(puzzleString){
    const puzzleArr = puzzleString.split("")
    const check = puzzleArr.every((val, index) => {
      let {row, column} = this.getRowColumn(index);
      if(val.match(/\./)){
        return true
      }
      if(val.match(/[1-9]/)){
        column += ""
        val = +val;
        const rowCheck = this.checkRowPlacement(puzzleString, row, column, val)
        const colCheck = this.checkColPlacement(puzzleString, row, column, val)
        const sqrCheck = this.checkSquareRegionPlacement(puzzleString, row, column, val)
        if(rowCheck && colCheck && sqrCheck){
          return true
        }
      }
          return false;
    })
    return check;
  }

  // check by place in array of string and returns row and column.
  getRowColumn(place){
    const value = +place
    place += ""
    let obj = {};
    place.match(/\b(9|1[0-7])\b/)? obj = {row: 'B', column: value - 8}
        : place.match(/1[8-9]|2[0-6]/)? obj = {row: 'C', column: value - 17}
        : place.match(/2[7-9]|3[0-5]/)? obj = {row: 'D', column: value - 26}
        : place.match(/3[6-9]|4[0-4]/)? obj = {row: 'E', column: value - 35}
        : place.match(/4[5-9]|5[0-3]/)? obj = {row: 'F', column: value - 44}
        : place.match(/5[4-9]|6[0-2]/)? obj = {row: 'G', column: value - 53}
        : place.match(/6[3-9]|7[0-1]/)? obj = {row: 'H', column: value - 62}
        : place.match(/7[2-9]|80/)? obj = {row: 'I', column: place - 71}
        : obj = {row: 'A', column: value + 1};
    return obj;
  }

  // check for valid inputs.
  checkValues(row, column, value){
    value += ""
    column += ""
    if(!value.match(/[1-9]/)){
        return "Invalid value"
      }
    if(!row.match(/[A-I]/) || !column.match(/[1-9]/)){
        return "Invalid coordinate"
      }
    return "fine"
  }

  // check for row(character) and return min and max value for that row.
  rowAdd(row){
    let arr;
      switch(row){
        case "A":
          arr = [0, 9];
          break;
        case "B":
          arr =  [9, 18];
          break;
        case "C":
          arr =  [18, 27];
          break;
        case "D":
           arr =  [27, 36];
          break;
        case "E":
          arr =  [36, 45];
          break;
        case "F":
          arr =  [45, 54];
          break;
        case "G":
          arr =  [54, 63];
          break;
        case "H":
          arr =  [63, 72];
          break;
        case "I":
          arr =  [72, 81];
          break;
      }
    return arr;
    }

  //check placement by row
  checkRowPlacement(puzzleString, row, column, value) {
    const [min, max] = this.rowAdd(row)
    const index = min + parseInt(column) - 1
    const puzzleArr = puzzleString.split("")
    for(let i = min; i < max; i++){
      if(puzzleArr[i] == value){
        if(i == index){
          continue
        }
        return false
      }
    }
    return true;
  }

  //check placement by col
  checkColPlacement(puzzleString, row, column, value) {
    const puzzleArr = puzzleString.split("")
    const startIndex = parseInt(column) - 1;
    const index = this.rowAdd(row)[0] + parseInt(column) - 1;
    for(let i = startIndex; i < 81; i+= 9){
      if(puzzleArr[i] == value){
        if(index == i){
          continue
        }
        return false;
      }
    }
    return true
  }

  // check for which square does the value belongs
  checkSquareRegion(row, column){
    column = +column;
    switch(row){
      case "A": case "B": case "C":
        if(column < 4){
          return "0"
        }
        if(column < 7){
          return "1"
        }
        if(column < 10){
          return "2"
        }
        ;
        
      case "D": case "E": case "F":
         if(column < 4){
          return "3"
        }
        if(column < 7){
          return "4"
        }
        if(column < 10){
          return "5"
        }
        ;
        
      case "G": case "H": case "I":
         if(column < 4){
          return "6"
        }
        if(column < 7){
          return "7"
        }
        if(column < 10){
          return "8"
        }
        ;
      default:
        return undefined
    }
  }

  // for square check of different values. return true if value does differ then others. 
  checkSquareRegionPlacement(puzzleString, row, column, value) {
    const puzzleArr = puzzleString.split("")
    const square = +this.checkSquareRegion(row,column)
    const check = this.checkValues(row, column, value)
    const index =  this.rowAdd(row)[0] + parseInt(column) - 1;
    if(check == "fine"){ 
      let startIndex = (square * 3)
      let flag = true;
      for(let i = 0; i < 3; i++){
        for(let j = startIndex; j < (startIndex + 3); j++){
          if((parseInt(puzzleArr[j]) == value)){
            if(puzzleArr[j] == puzzleArr[index]){
              continue;
            } else{
            flag = false
            }
          } else{
            continue;
          }
        }
        if(flag == false){
          break;
        }
        startIndex += 9;
      }
      if(flag){
        return true
      }
      return false;
    }else {
      return check;
    }
  }
// solve whole puzzle
  solve(puzzleString) {
    const validate = this.validate(puzzleString)
    if(validate == "valid"){
      puzzleString = this.fillSoduko(puzzleString)
    } else {
      return {error: validate};
      }
    return puzzleString;
    }

  // fill soduko.
 fillSoduko(puzzleString) {
    const puzzleArr = puzzleString.split("")
   var _this = this;
   fill(puzzleArr.indexOf(val => !val.match(/[1-9]/)))

  function fill(index){
      console.log(index)
      while (index < 81 && puzzleArr[index].match(/[1-9]/)) ++index; // skip non-empty cells
      if (index == 81) return true;               // we filled'em all, success!
      let moves = getChoices(index);
      for (let m of moves) {
        puzzleArr[index] = m;              // try one choice
        if (fill(index + 1))          // if we can solve for the next cell
            return true;               // then return true, success!
    }
      puzzleArr[index] = ".";  // no move worked; we failed, clear the cell
      return false;
    } // and backtrack

  function getChoices(index) {
    const {row, column} = _this.getRowColumn(index)
    let choices = [];
    for (let value = 1; value <= 9; ++value) {
        if (_this.checkPlaceAndValue(puzzleString, row, column, value) == true) {
            choices.push(value);
        }
    }
    return choices;
  }
    return puzzleArr.join("")
  }
  
// check for place and value of the value inserted.
  checkPlaceAndValue(puzzleString, row, column, value){
    value = +value;
    const validate = this.validate(puzzleString);
    const check = this.checkValues(row, column, value);
    if((check == "fine") && (validate == "valid")){
      const rowCheck = this.checkRowPlacement(puzzleString, row, column, value)
      const colCheck = this.checkColPlacement(puzzleString, row, column, value)
      const sqrCheck = this.checkSquareRegionPlacement(puzzleString, row, column, value)
      if(rowCheck && colCheck && sqrCheck){
        return true
      } else{
        let obj = {};
        !rowCheck ?  obj = {conflict: "row"}:
        !colCheck ?  obj = {conflict: "column"}:
        obj = {conflict: "region"};
        return obj;
      }
    } else{
      let obj = {}
      validate != "valid"? obj = {error: validate}:
        obj = { error: check};
      return obj;
    }
  }
  }

module.exports = SudokuSolver;

So I have portion of code above which takes for ever to process. I have to use recursion as there was no other option. Please notify me if I am doing something wrong.

The backend thought about this class method is that it takes puzzle String and automatically fills it. It checks for empty(".") value in string and then check if any(1-9) is working for it. Ofcourse there are plenty of cells empty so we get not 1 but too many number as choice. We are then checking for each choice if it completes and validate a board or not.

Answer 1

The first thing I note is that this:

   fill(puzzleArr.indexOf(val => !val.match(/[1-9]/)))

should be:

   fill(puzzleArr.findIndex(val => !val.match(/[1-9]/)))

It's an easy mistake to make. indexOf is to find the first index in the array of the supplied value. findIndex is to find the first index in the array for which the supplied predicate function returns true.

On fixing that, I was able to spot that there is an error in checkSquareRegionPlacement. I haven't dug deeply into it, but using a fully solved puzzle and simply removing the final value, I tried to test a really easy case:

const complete = "172396845549287316368514297634975182927831564851462973215749638793658421486123759"
const puzzle =   "17239684554928731636851429763497518292783156485146297321574963879365842148612375."

When we get into checkSquareRegionPlacement, we should be testing indices 60. 61, 62, 69, 70, 71, 78, 79, 80. But it was failing (by setting flag = false) when the index j was 25. I haven't dug in yet to see what's failing in this code, but that might at least point you in the right direction.

Overall, there are larger issues I would suggest you address:

• There is a constant breaking apart of the puzzle string. You need a more useful internal format for the puzzle. Assuming that this 81-character string filled with digits (1 - 9) or dots (.) is your required input format, then I would suggest that on entering your initial function you change this to a more useful format, either a single array containing 81 characters / numbers or a 9 x 9 array of them. If you need at the very end to convert back to the string format, that's fine. In between the beginning of your initial call and its return, keep everything in a more useful format.

• You repeatedly do the work of converting your plain array indices to the logical grid model and back. You could do this up front once with code something like this:

  const _09 = [0, 1, 2, 3, 4, 5, 6, 7, 8];
  const _03 = [0, 1, 2];
  const rows = _09 .map ((i) => _09 .map ((j) => 9 * i + j))
  const cols = _09 .map ((i) => _09 .map ((j) => i + 9 * j))
  const squares = _03 .flatMap ((i) => _03 .map ((j) => _03 .flatMap (
    (k) => _03 .map (l => 27 * i + 3 * j + 9 * k + l)
  )))
  const groups = Array .from ({length: 80}, (_, i) => [
    rows .find (row => row .includes (i)),
    cols .find (col => col .includes (i)),
    squares .find (square => square .includes (i))
  ])
  

  then use those stored values. For instance, "Can I place a 7 at index 80?" becomes something like groups [80] .every (g => ! g .includes (7)) (untested!). This would stop much of the fiddling with rows and columns.

• This is in a class for no obvious reason. Your methods are passing the relevant data between them, so there seems to be no internal state. It seems to me that this would be better as a module.

There are other issues, too. But overall, the issue seems to be that you're working too hard. I think a strong dose of simplification should really help.