JavaScript的数独解算器。以前的数字来自哪里？

Question

我分析了暴力破解算法，并有一个问题。

var solveSudoku = function (grid, row, col) { 
    var field = findUnassignedLocation(grid, row, col); 
    row = field[0]; 
    col = field[1]; 
    if (row === -1) { 
     if (!newGameStatus) fillTheDom(grid); 
     return true; 
    } 

    for (var num = 1; num <= 9; num++) { 
     if (newGameStatus) { 
      num = Math.floor(Math.random() * 9) + 1; 
     } 
     if (isValid(grid, row, col, num)) { 
      console.log(row + ' ' + col) 
      grid[row][col] = num; 
      if (solveSudoku(grid, row, col)) { 
       return true; 
      } 
      console.log(row + ' ' + col) 
      grid[row][col] = 0; 
     } 
    } 
    return false; 
} 

var findUnassignedLocation = function (grid, row, col) { 
    var foundZero = false; 
    var location = [-1, -1]; 

    while (!foundZero) { 
     if (row === 9) { 
      foundZero = true; 
     } else { 
      if (grid[row][col] === 0) { 
       location[0] = row; 
       location[1] = col; 
       foundZero = true; 
      } else { 
       if (col < 8) { 
        col++; 
       } else { 
        row++; 
        col = 0; 
       } 
      } 
     } 
    } 
    return location; 
} 

如果没有数字要填充（每个数字都是无效的）递归函数返回false，对吗？然后以某种方式重置先前填充的单元格。它如何回到最后一个单元？

Answer 1

每一个函数被调用它的状态被保存（直到所有的下列状态已经失败），如果他们失败处理器跳回有至少一个又未失败的国家去，并一直持续到最后一个分支时间解决方案被发现或一切都失败。

我可以做一个GIF，将它解释为简单的，因为我可以，但我只能做到这一点下班后

Answer 2

想象递归简单的格式化。

solveSudoku(firstCell) 
# Context : Global 
On the first cell : 
From 1 to 9 : 
Is 1 valid ? 
Yes. 
If solveSudoku(nextCell): 
    # Context : We're in the loop of the first cell at iteration 1. 
    On the second cell : 
    From 1 to 9 : 
    Is 1 valid ? 
    No. 
    Is 2 valid ? 
    Yes. 
    If solveSudoku(nextCell): 
     # Context : We're in the loop of the second cell at iteration 2 which is in the loop of the first cell at iteration 1. 
     On the third cell : 
      From 1 to 9 : 
      Is 1 valid ? 
      No. 
      Is 2 valid ? 
      No. 
      Is 3 valid ? 
      No. 
      ... 
      Is 9 valid ? 
      No. 
      Return false. 
    solveSudoku(nextCell = thirdCell) returned false, going on the loop. <<<<<<<<< This is "How does it goes back to the last cell?" 
    # Context : We're in the loop of the first cell at iteration 1. 
    Is 3 valid ? 
    Yes. 
    If solveSudoku(nextCell): 
     # Context : We're in the loop of the second cell at iteration 3 which is in the loop of the first cell at iteration 1. 
     On the third cell : 
      From 1 to 9 : 
      Is 1 valid ? 
      No. 
      Is 2 valid ? 
      Yes. <<<<<<< 2 is now valid and we can go on ! 
      If solveSudoku(nextCell): 
       # Context : We're in the loop of the third cell at iteration 2 which is in the loop of the second cell at iteration 3 which is in the loop of the first cell at iteration 1. 
       On the fourth cell... 

正如你所看到的递归更深入，可以简单地转义一个深度级别来尝试另一条路径。