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

Question

我正在尝试使用带回溯的递归函数来求解数独网格。实际上，它可以工作，但递归性永远不会停止，即使使用 return 语句也是如此。而且我不知道如何让它发挥作用。

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

好的，首先，对不起我的英语，它不是我的主要语言。现在让我们谈谈您的问题，正如我所见，您使用 return 语句但从未使用函数的结果。你正在做 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;
    }

Answer 2

您的代码中存在一些错误，导致运行时间非常糟糕，并且还会产生错误的结果。

当当前单元格不为空（grid[idl][idc] != 0）时，递归调用该函数，但之后您还尝试用 1 到 9 之间的每个数字填充当前单元格。这显然真的很糟糕。您覆盖一个数字，该数字固定在原始数独网格中。当 grid[idl][idc] == 0 时，你应该只做 for(int i=1; i<=N; i++){...} 部分。

这就是您的程序运行缓慢的原因。即使已经有一个数字，它也会尝试用所有可能性填充它。
正在将当前单元格设置回 0 (grid[idl][idc] = 0;)。仅当 ok returns false 时，您才执行此操作。这还不够。想象如下： ok returns true，所以你将数字写入 grid[idl][idc] 并递归调用 solve。图片solve无法使用这个数字求解网格，solve returns false。所以我们也必须擦除这个数字。你不这样做。

在 for 循环之后擦除当前单元格就足够了，就在您 return 之前。
如果找到解决方案，请尽快退出。您可以通过检查递归调用的 return 值来做到这一点。如果 solve(...,...) returns true，那么你也可以立即 return 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; 
    }
}

顺便说一句，我不确定这段代码是否已经足够快，可以在合理的时间内解决数独问题。我将我的回溯数独求解器与一些逻辑策略相结合，例如 "Hidden Singles" 策略。

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

How to stop recursivity when I got the result of sudoku's grid?

c++

recursion

sudoku