为什么 return 语句不中断 Javascript 中的递归 for 循环

Question

拜托，我正在尝试在 JavaScript 中构建一个数独求解器，但是当我进入 求解函数 时遇到问题，递归循环不会停止当董事会满员时。即使找到解决方案，它也会执行到最后。如果我能得到一些帮助，我将不胜感激。这是我尝试做的事情：

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));

它 return 是错误的，但拼图字符串是有效的，而且当我在控制台登录 全食宿条件 它显示已解决的字符串但没有return它。

Answer 1

for (var i = 1; i <= 9; i++) {
   if (this.checkvalue(board, row, column, i)) {
     board[row][column] = i;
     var boardString = this.stringifyBoard(board);
     
     if(this.solve(boardString)) return true; //I've a modification here
   }
 }

Answer 2

因此，一旦棋盘被解决并且如果 this.solved(board) return 为真，那么您正在 return 解决棋盘。但这只是在递归链的最后一级。如果此特定移动达到已解决的棋盘状态，您需要在递归的每个级别进行检查。因此，验证下一个级别的结果，如果它 return 是一个已解决的板，return 也是当前级别的已解决板。我对求解函数做了适当的修改-

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;
  }

Answer 3

您没有编写任何代码来在找到解决方案时停止该函数。这是我的解决方案：

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

我刚才在 python 做过类似的。感兴趣的可以在这里查看：https://onlinegdb.com/SJt2PQrjP

为什么 return 语句不中断 Javascript 中的递归 for 循环

why does return statement not break recursive for loop in Javascript

javascript

recursion

for-loop

return

sudoku