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

大佬教程收集整理的这篇文章主要介绍了这个数独回溯递归算法是如何触发回溯的？，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

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

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

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

我不明白下一个语句以及它如何触发回溯。

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

如果当前被检查的空白网格没有解决方案，那么我认为网格仍然是空白的 ('.')。如果这是正确的，为什么需要这种说法？这个语句会触发回溯吗？

我最初的倾向是这个语句是一个伪else语句，只有在循环无法找到解决方案时才运行。它必须被放置在循环之外以允许从 1 到 9 的完整迭代。但是如果 solve() 仅在 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,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,i];
      }
    } 
    return false;
  }

  checkValue(puzzleString,column,value){
    if(this.checkRowPlacement(puzzleString,value)&&
    this.checkColPlacement(puzzleString,value)&&
    this.checkRegionPlacement(puzzleString,value)){
      return true;
    }
    return false;
  }
checkRowPlacement(puzzleString,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,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,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;
  }

解决方法

for

大佬总结

以上是大佬教程为你收集整理的这个数独回溯递归算法是如何触发回溯的？全部内容，希望文章能够帮你解决这个数独回溯递归算法是如何触发回溯的？所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。