java - 无法理解递归如何与数独求解器一起工作

Question

我已经查看这段代码几个小时了，但我不知道它是如何工作的。有人可以详细解释递归如何使用这些函数吗？请记住，我在编程方面还很陌生。

最让我困惑的是solve()是如何被重复调用的？难道不是到了 puzzle[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 函数中。

在这种情况下，对于数独，回溯的这种特定实现可能效果不太好。它可能需要几万亿年才能找到解决方案，因为可能性实在太多了。但这基本上取决于 check* 方法的实现有多“聪明”。快速检测(部分)解决方案已经无效的情况非常重要。也就是说，你是否遇到了无论如何也找不到解决办法的情况。例如，当 3x3 方格之一的两个单元格包含相同数字时，情况就已经“无效”。例如，可以通过显式存储仍然可用的数字来避免这种情况，但代码当然会变得更加复杂。