JavaScript Sudokuソルバー。前の数字はどこから来たのですか？

Question

私はbruteforceアルゴリズムを分析しており、1つの質問があります。

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... 

ご覧のとおり、再帰が深くなり、別のパスを試すために1レベルの深さから逃げることができます。