这个数独回溯递归算法是如何触发回溯的？

Question

let row = this.findEmpty(puzzleString)[0];
let col = this.findEmpty(puzzleString)[1];
let i = this.findEmpty(puzzleString)[2];

if(!this.findEmpty(puzzleString)) return puzzleString
for(let num = 1; num < 10; num++){
  if(this.checkValue(puzzleString, row, col, num)){
    puzzleString[i] = num;
    this.solve(puzzleString)
  } 
}

findEmpty(puzzleString) 遍历拼图字符串和 returns 行 (A-I)、列 (1-9) 和空白网格的索引。 checkValue() 包含 3 个返回布尔值的辅助函数，确保行、列或区域之间没有冲突。

循环从1-9开始迭代，将1-9第一个通过checkValue()的值赋值给当前空白格子，然后调用父函数solve()触发递归。

我不明白的是下一条语句以及它如何触发回溯.

if(this.findEmpty(puzzleString)){ 
  puzzleString[i] = '.';
}

如果当前正在检查的空白网格没有解决方案，那么我认为网格仍然是空白 ('.')。如果这是正确的，为什么这个声明是必要的？这条语句触发回溯怎么办？

我最初的倾向是这个语句是一个伪 else 语句，运行只有在循环找不到解决方案时才会出现。它必须放在循环之外，以允许从 1 到 9 的完整迭代。但是如果 solve() 仅在 checkValue() 成功了吗？

完整代码如下：

solve(puzzleString) {
let row = this.findEmpty(puzzleString)[0];
let col = this.findEmpty(puzzleString)[1];
let i = this.findEmpty(puzzleString)[2];

if(!this.findEmpty(puzzleString)) return puzzleString
for(let num = 1; num < 10; num++){
  if(this.checkValue(puzzleString, row, col, num)){
    puzzleString[i] = num;
    this.solve(puzzleString)
  } 
}
if(this.findEmpty(puzzleString)){ 
  puzzleString[i] = '.';
} 

if(puzzleString.includes('.')) return { error: 'Puzzle cannot be solved' } 

return {
  solution: puzzleString.join('')
  }

}

findEmpty(puzzleString){
    for(let i = 0; i < puzzleString.length; i++){
      if(puzzleString[i] == '.'){
        let row = String.fromCharCode('A'.charCodeAt(0) + Math.floor(i / 9));
        let col = (i % 9) + 1;
        return [row, col, i];
      }
    } 
    return false;
  }

  checkValue(puzzleString, row, column, value){
    if(this.checkRowPlacement(puzzleString, row, column, value)&&
    this.checkColPlacement(puzzleString, row, column, value)&&
    this.checkRegionPlacement(puzzleString, row, column, value)){
      return true;
    }
    return false;
  }
checkRowPlacement(puzzleString, row, column, value) {

    let coordinates = [];
    let rowLetter;
    let colNum;
    let temp = [];
    if(row){row = row.toUpperCase();}
    for(let i = 0; i < puzzleString.length; i++){
      rowLetter = String.fromCharCode('A'.charCodeAt(0) + Math.floor(i / 9));
      colNum = (i % 9) + 1;
      coordinates.push(rowLetter + colNum);
    } 
    for(let i = 0; i < coordinates.length; i++){
        if(coordinates[i][0] == row){
            temp.push(puzzleString[i]);
        }
    } 
    temp = temp.join('');
    return !temp.includes(value) ? true : false
    
  }

  checkColPlacement(puzzleString, row, column, value) {
    let coordinates = [];
    let rowLetter;
    let colNum;
    let temp = [];
    if(row){row = row.toUpperCase();}
    for(let i = 0; i < puzzleString.length; i++){
      rowLetter = String.fromCharCode('A'.charCodeAt(0) + Math.floor(i / 9));
      colNum = (i % 9) + 1;
      coordinates.push(rowLetter + colNum);
    } 
    for(let i = 0; i < coordinates.length; i++){
        if(coordinates[i][1] == column){
            temp.push(puzzleString[i]);
        }
    } 
    temp = temp.join('');
    return !temp.includes(value) ? true : false
  }

  checkRegionPlacement(puzzleString, row, column, value) {
    let coordinates = [];
    let rowLetter;
    let colNum;
    let regions = [];
    if(row) row = row.toUpperCase();

    for(let i = 0; i < puzzleString.length; i++){
      rowLetter = String.fromCharCode('A'.charCodeAt(0) + Math.floor(i / 9));
      colNum = (i % 9) + 1;
      coordinates.push(rowLetter + colNum);
    }

    for(let i = 0; i < coordinates.length; i+=27){
      for(let k = 0; k < 9; k+=3){
        regions.push(
          coordinates.slice(i+k,i+k+3) + ',' +
          coordinates.slice(i+k+9, i+k+12) + ',' +
          coordinates.slice(i+k+18, i+k+21)
        )
      }
    }

    let region = regions.filter(x => x.includes(row + column))[0].split(',').map(x => puzzleString[coordinates.indexOf(x)]).join('');

    return region.includes(value) ? false : true;
  }

Answer 1

回溯发生在 findEmtpy returns false 时。但是由于您的代码不是最佳的，因此在回溯时仍然尝试了许多其他选项：递归树中挂起的 for 循环中的 none 被中断，但是让它们继续是浪费精力并且调用 checkValue，因为现在每个调用都会 return false。因此，最终所有这些 for 循环都将结束，递归将回溯，只是为了完成另一个循环并再次回溯，...等

这是对您的主要功能的更新，以避免一些导致无益的开销：

solve(puzzleString) {
    // Only call findEmpty once!
    let emptyCell = this.findEmpty(puzzleString);
    if (!emptyCell) return { solution: puzzleString.join('') }; // return the success object
    let [row, col, i] = emptyCell; // use destructuring assignment
    for (let num = 1; num < 10; num++) {
        if (this.checkValue(puzzleString, row, col, num)) {
            puzzleString[i] = num;
            let result = this.solve(puzzleString); // capture the return value
            if (result.solution) return result; // success: fast backtracking!
        }
    }
    puzzleString[i] = "."; // could not solve this spot
    // backtrack to possibly take a different route in previous decisions
    return { error: 'Puzzle cannot be solved' };
}

这个数独回溯递归算法是如何触发回溯的？

How does this Sudoku backtracking recursive algorithm trigger backtracking?

javascript

algorithm

recursion

sudoku

backtracking