当我得到sudoku网格的结果时，如何停止递归？

Question

我试图使用递归函数和回溯来求解sudoku网格。实际上，它可以工作，但是递归性永远不会停止，即使使用返回语句也是如此。我不知道该怎么做。

bool solve(int idl, int idc){ 

  if( idl == N ){
    std::cout << std::endl;
    printGrid();
    return true;
  }

  if( grid[idl][idc] != 0 )
    if( idc == N-1 )
      tmp = solve(idl+1, 0);
    else
      tmp = solve(idl, idc+1);

  for(int i=1; i<=N; i++){
    if( ok(i, idl, idc) ){
      grid[idl][idc] = i;
      if( idc == N-1)
    tmp = solve(idl+1, 0);
      else
    tmp = solve(idl, idc+1);
    }else{
      grid[idl][idc] = 0;
    }
  }
}

Answer 1

在您的代码中有一些错误，这些错误会给出一个非常糟糕的运行时间，并且也会产生错误的结果。

1. 当当前单元格不为空(grid[idl][idc] != 0)时，您会递归地调用该函数，但之后您也会尝试用1到9之间的每个数字填充当前单元格。这显然是非常糟糕的。覆盖一个数字，这个数字固定在原来的sudoku网格中。您应该只执行for(int i=1; i<=N; i++){...}部分，当grid[idl][idc] == 0。

这就是你的程序慢的原因。即使已经有了一个数字，它也试图用所有的可能性来填补它。

1. 将当前单元格设置为0 (grid[idl][idc] = 0;)。只有当ok返回false时，才会执行此操作。这还不够。假设以下情况：ok返回true，因此您将数字写入grid[idl][idc]并递归调用solve。solve无法使用此数字解决网格的图像，solve返回false。所以我们还得抹去这个数字。你不能这么做。

在返回之前，在for循环之后擦除当前单元格就足够了。

1. 如果您找到了解决方案，请尽快退出。您可以通过检查递归调用的返回值来做到这一点。如果solve(...,...)返回true，那么您也可以立即返回true。你不需要检查这个细胞的其他可能性。你已经完成了。

这是修正后的代码。注意，我没有编译它，也没有测试它。但我很确定这是对的。我添加了相当多的注释，以便您能够理解更改。

bool solve(int idl, int idc)
{ 
    if (idl == N)
    {
        //sudoku solved
        std::cout << std::endl;
        printGrid();
        return true; //
    }

    if (grid[idl][idc] != 0)
    {
        // current cell has already a number, 
        // move on to the next cell
        if (idc == N-1)
            return solve(idl+1, 0);
            // if solve(idl+1, 0) returns true, then the sudoku is solved, 
            // so we also return true. If solve(idle+1, 0) returns false, 
            // then the sudoku is not solved and we also return false. 
        else
            return solve(idl, idc+1);
            // ditto
    }
    else
    {
        // the current cell is empty
        for (int i = 1; i <= N; i++)
        {
            if (ok(i, idl, idc))
            {
                grid[idl][idc] = i;
                if (idc == N-1)
                    if (solve(idl+1, 0))
                        return true;
                        // since the sudoku is already solved, exit the program
                        // if solve(...) return false, the sudoku isn't solved, 
                        // so we have to search further and can't exit. 
                else
                    if (solve(idl, idc+1))
                        return true;
                        // ditto
        }

        // if the program came this far, that means that all attempts of 
        // filling the current cell with digits failed. 
        // So we empty the current cell, and backtrack. 
        grid[idl][idc] = 0;
        return false; 
    }
}

顺便说一句，我不确定这段代码是否已经足够快，可以在合理的时间内解决sudokus问题。我把我的回溯sudoku解算器和一些逻辑策略结合在一起，比如“隐藏的单曲”策略。

Answer 2

好吧，首先，对不起我的英语，它不是我的主要语言。现在让我们讨论一下您的问题，正如我所看到的，您使用返回语句，但从不使用函数的结果。您正在执行tmp = solve(idl+1, 0);，但永远不要再次使用tmp。因此，你的功能的结果只是失去了，不要让其他的停止。你也许应该做这样的事

 bool solve(int idl, int idc){ 
 bool result = false;
  if( idl == N ){
    std::cout << std::endl;
    printGrid();
    result = true;
  }
 // if the result is not true than continue to solve
 if(!result){
  if( grid[idl][idc] != 0 )
    if( idc == N-1 )
      result = solve(idl+1, 0);
    else
      result = solve(idl, idc+1);
}
// if the result is not true than continue to solve
     if(!result){
      for(int i=1; i<=N; i++){
        if( ok(i, idl, idc) ){
          grid[idl][idc] = i;
          if( idc == N-1)
        result = solve(idl+1, 0);
          else
        result = solve(idl, idc+1);
        }else{
          grid[idl][idc] = 0;
        }
      }
     }
     return result;
    }