麻烦理解递归如何与这个数独求解器一起工作

Question

我一直在看这个代码块几个小时了，我不知道它是如何工作的。有人可以请详细解释递归如何与这些函数一起工作吗？请记住，我在编程方面非常新颖。

让我最困惑的部分是solve（）如何反复调用？难道它会在达到谜题后停止[row] [col] = 0？

这是工作代码的方式。

编辑：谢谢你的回答！但我不知道它在哪里回溯。

void solve(int row, int col) throws Exception 
{ 
    if(row > 8) 
    { 
     throw new Exception("Solution found") ; 
    } 

    if(puzzle[row][col] != 0) 
    { 
     next(row, col); 
    } 
    else 
    { 
     for(int num = 1; num < 10; num++) 
     { 
      if(checkHorizontal(row,num) && checkVertical(col,num) && checkBox(row,col,num)) 
      { 
       puzzle[row][col] = num ; 
       next(row, col) ; 
      } 
     } 
     puzzle[row][col] = 0 ; 
    } 
} 

public void next(int row, int col) throws Exception 
{ 
     if(col < 8) 
     { 
      solve(row, col + 1) ; 
     } 
     else 
     { 
      solve(row + 1, 0) ; 
     } 

} 

Answer 1

的next函数可以描述为发现的第一个自由场，并从该字段开始求解过程的功能。

实际的递归是一个简单的回溯（http://en.wikipedia.org/wiki/Backtracking）。总体方案可能会更容易一些伪把握：

Solution findSolution(Board board) { 
    if (board.isSolved()) return solutionFor(board); 


    // An "action" here refers to placing any number 
    // on any free field 
    for (each possible action) { 

     do the action // That is: place a number on a free field 

     // The recursion: 
     Solution solution = findSolution(board); 
     if (solution != null) return solution; 

     // No solution found 
     UNdo the action // That is: remove the number from the field 

     // Now the loop continues, and tries the 
     // next action... 
    } 

    // Tried all possible actions, none did lead to a solution 
    return null; 
} 

通常情况下，一个将决定这些“行动”有两个嵌套的for循环：

for (each free field f) 
{ 
    for (each number n in 1..9) 
    { 
     place 'n' on 'f' 
     try to find solution 
     remove 'n' from 'f' 
    } 
} 

外环在这种情况下有些“隐藏”在next函数中。

在这种情况下，对于数独，这种回溯的特定实现可能不会很好。它可能需要几万亿年才能找到解决方案，因为这种可能性非常多。但是这主要取决于如何实施“巧妙”的方法。快速检测（部分）解决方案已无效的情况很重要。也就是说，您是否遇到过无法找到解决方案的情况。例如，当一个3x3-sqares的两个单元格包含相同数字时，情况已经“无效”。例如，这可以通过显式存储仍然可用的数字来避免，但是当然，代码会变得更加复杂。