why does return statement not break recursive for loop in Javascript

Question

Please i am trying to build a Sudoku solver in JavaScript but i face a problem when i get to the solve function, the recursive loop doesn't stop when the board is full. It executes till the end even after finding the solution. Please I'll be grateful if i can get some help. Here is what i tried doing:

class SudokuSolver {

  // convert puzzle string to 2D array
  boardParser(puzzleString) {
    var board = [];
    var i, j;

    for (i = 0; i < 81; i += 9) {
      var boardRow = [];
      for (j = 0; j < 9; j++) {
        boardRow.push(puzzleString.charAt(i + j));
      }
      board.push(boardRow)
    }

    // console.log(board);
    return board;
  }

  // Look for empty space on board (empty space = ".")
  // return [row, col] if empty space found
  // return [-1,-1] if no empty space found (board is full)
  getDot(board) {
    var i, j;

    for (i = 0; i < 9; i++) {
      for (j = 0; j < 9; j++) {
        if (board[i][j] == ".") {
          return [i, j];
        }
      }
    }
    return [-1, -1];
  }

  checkRowPlacement(board, row, column, value) {
    var i;
    for (i = 0; i < 9; i++) {
      if (board[row][i] == value) {
        // console.log("row check false");
        return {
          valid: false
        };
      }
    }
    // console.log("row check true");
    return {
      valid: true
    }
  }

  checkColPlacement(board, row, column, value) {
    var i;

    for (i = 0; i < 9; i++) {
      if (board[i][column] == value) {
        // console.log("col check false")
        return {
          valid: false
        }
      }
    }
    // console.log("col check true")
    return {
      valid: true
    };
  }

  checkRegionPlacement(board, row, column, value) {
    var i, j;
    var regRow = Math.floor(row / 3) * 3;
    var regCol = Math.floor(column / 3) * 3;

    for (i = 0; i < 3; i++) {
      for (j = 0; j < 3; j++) {
        if (board[regRow + i][regCol + j] == value) {
          // console.log("reg check false")
          return {
            valid: false
          }
        }
      }
    }
    // console.log("reg check true");
    return {
      valid: true
    }
  }

  checkvalue(board, row, column, value) {
    var rowCheck = this.checkRowPlacement(board, row, column, value).valid
    var colCheck = this.checkColPlacement(board, row, column, value).valid
    var regCheck = this.checkRegionPlacement(board, row, column, value).valid
    // console.log(rowCheck, colCheck, regCheck);

    if (rowCheck && colCheck && regCheck) {
      // console.log(true)
      return true;
    }
    // console.log(false)
    return false;
  }

  // convert 2D array back to string
  stringifyBoard(board) {
    var string = ""
    var i, j;

    for (i = 0; i < 9; i++) {
      for (j = 0; j < 9; j++) {
        string += board[i][j];
      }
    }

    // console.log(string);
    return string;
  }

  // check for any more empty spaces
  solved(board) {
    var i, j;

    if (this.getDot(board)[0] == -1) {
      return true
    }
    return false
  }

  solve(puzzleString) {
    var board = this.boardParser(puzzleString)
    var emptySpot = this.getDot(board);
    var row = emptySpot[0];
    var column = emptySpot[1];

    // full board condition
    if (this.solved(board)) {
      return puzzleString;
    }

    for (var i = 1; i <= 9; i++) {
      if (this.checkvalue(board, row, column, i)) {
        board[row][column] = i;
        var boardString = this.stringifyBoard(board);
        this.solve(boardString);
      }
    }

    // if board is unsolvable return false
    return false;
  }
}

const input = '5..91372.3...8.5.9.9.25..8.68.47.23...95..46.7.4.....5.2.......4..8916..85.72...3';

console.log(new SudokuSolver().solve(input));

it returns false, but the puzzle string is valid and also when i console log in the full board condition it shows the solved string but doesn't return it.

There's a lot here to review. Can you boil it down a bit? Remember, return only exits the current function, not all functions. — tadman
Is this your code? Did you author it I mean? And if so where are your debugging details? Because it has smell of copied code. — GetSet
Can you give an input for which the issue is reproducible? The input you have given returns the result as false. — maddy
Hello @tadman, thank you for your kind respond. I was hoping the return will break the recursive loop when it doesn't find any more empty spaces. Please if am wrong about the return in that context help me out I'll be grateful. — Fru Promise
Hello @GetSet, i got inspired by this article https://medium.com/swlh/backtracking-algorithm-to-solve-sudoku-puzzle-in-javascript-732aedcf5e2 and tried to use it for my project. I didn't copy and paste code snippets as it wouldn't be very helpful to my learning journey. — Fru Promise

maddy maddy · Accepted Answer · 2020-12-02T14:32:18

So once the board is solved and if this.solved(board) returns true, you are returning the solved board. But this is only at the last level of recursion chain. You need to check at every level of recursion if this particular move reaches a solved board state. Hence, validate the result of the next level and if it returns a solved board, return the solved board from the current level too. I have made appropriate changes in the solve function-

solve(puzzleString) {
    var board = this.boardParser(puzzleString)
    var emptySpot = this.getDot(board);
    var row = emptySpot[0];
    var column = emptySpot[1];

    // full board condition
    if (this.solved(board)) {
      return puzzleString;
    }

    for (var i = 1; i <= 9; i++) {
      if (this.checkvalue(board, row, column, i)) {
        board[row][column] = i;
        var boardString = this.stringifyBoard(board);
        var result = this.solve(boardString);
        if(result !== false){
            return result;
        }
      }
    }

    // if board is unsolvable return false
    return false;
  }

why does return statement not break recursive for loop in Javascript

3 Answers