计算所有解决方案的递归回溯算法

Question

我正在构建一个数独生成器-求解器应用程序，目前正在完成无用单元格的隐藏算法。

我有一个有效的回溯算法，当找到解决方案时 return 是正确的，但我需要检查是否有任何其他解决方案来防止创建错误的板。

findEmpty 函数查找数独板内的下一个空单元格。 isValid 函数检查传递的参数是否适合当前单元格。如果电路板已解决，则提供的代码 return 为真。它确实会覆盖传递的变量，因此为了访问已求解的板，我调用变量传递。

如果至少有一个额外的解决方案，则该函数必须 return 为假。如果棋盘无法解出，函数必须return false。如果有解决方案（只有 1 个），return true

function backTrackSolve(board)
  {
      let find = findEmpty(board)
      if (find[0] == -1)
          return true
      
      let row = find[0]
      let col = find[1]
  
  
      for (let i = 1; i < 10; i++)
      {
  
          if (isValid(board, { row,col }, i))
          {
              board[row][col] = i
              if (backTrackSolve(board)){
                    return true
              }
  
            }
              board[row][col] = 0
      }
  
      return false
  
  }

Answer 1

    function backTrackSolve(board)
      {
          let find = findEmpty(board)
          if (find[0] == -1){
              //count stuff here
              return false;
          }
          let row = find[0]
          let col = find[1]
      
      
          for (let i = 1; i < 10; i++)
          {
      
              if (isValid(board, { row,col }, i))
              {
                  board[row][col] = i
                  if (backTrackSolve(board)){
                        return true
                  }
      
                }
                  board[row][col] = 0
          }
      
          return false
      
     }

计算所有解决方案的递归回溯算法

recursive backtracking algorithm that counts all solutions

javascript

algorithm

recursion

sudoku

backtracking