为什么这个数独回溯会卡住？

Question

我正在编写一个数独回溯求解器，它被卡住了，我不明白为什么。我认为我的递归调用没问题。我缺少什么？

输入是从 input.txt 文件中读取的，网格初始布局在一行中：

input.txt:

004020000201950070090004852005490001006000900800051300958100020010072608000080500

编辑：我的意思是“卡住”，因为没有完成网格的求解

这是一个示例输出：

current move count is 6
3 6 4 7 2 8 1 9 0 
2 0 1 9 5 0 0 7 0 
0 9 0 0 0 4 8 5 2 
0 0 5 4 9 0 0 0 1 
0 0 6 0 0 0 9 0 0 
8 0 0 0 5 1 3 0 0 
9 5 8 1 0 0 0 2 0 
0 1 0 0 7 2 6 0 8 
0 0 0 0 8 0 5 0 0 

程序：

package sudoku;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;




public class Main {

 static boolean checkRow( int row, int num, int grid[][])
   {
      for( int col = 0; col < 9; col++ )
         if( grid[row][col] == num )
            return false ;

      return true ;
   }

static boolean checkCol( int col, int num, int grid[][] )
   {
      for( int row = 0; row < 9; row++ )
         if( grid [row][col] == num )
            return false ;

      return true ;
   }


static boolean checkBox( int row, int col, int num, int grid[][] )
   {
      row = (row / 3) * 3 ;
      col = (col / 3) * 3 ;

      for( int r = 0; r < 3; r++ ){
         for( int c = 0; c < 3; c++ ){
            if( grid[row+r][col+c] == num )
            return false ;          
         }
      }
      return true ;
   }


  static void printSolvedGrid(int grid[][]){

       for (int i=0; i<grid.length; i++){
            for (int j=0; j<grid.length;j++){
              System.out.print(grid[i][j]+" ");
            } System.out.println();
        }

  }


   static int moveCounter=0;

   static boolean solve(int row, int col, int [][]grid){

       if (row>=grid.length){

           System.out.println("solution found");
           printSolvedGrid(grid);

       }

       if( grid[row][col] != 0 ){
            next( row, col, grid ) ;
       }

       else {
         // Find a valid number for the empty cell
         for( int num = 1; num < 10; num++ )
         {
            if( checkRow(row,num,grid) && checkCol(col,num,grid) && checkBox(row,col,num,grid) )
            {
               grid[row][col] = num ;
               moveCounter++;
               System.out.println("current move count is " + moveCounter);
               printSolvedGrid(grid);
               next( row, col, grid );
               return true;
            }
         }

       }
       return false;
    }


  public static void next( int row, int col, int [][] grid )
   {
      if( col < 8 ) //pass to next col
         solve( row, col + 1, grid ) ;
      else //pass to next row 
         solve( row + 1, 0, grid ) ;
   }







    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new FileReader(new File("input.txt")));
        char gridChar[] = br.readLine().toCharArray();

       int [][] grid = new int [9][9];

        int gridCharIndex=0;
        for (int i=0; i<grid.length; i++){
            for (int j=0; j<grid.length;j++){

              grid[i][j]= Integer.parseInt(gridChar[gridCharIndex++]+"");
              System.out.print(grid[i][j]+" ");
            } System.out.println();
        }

        solve(0,0, grid);
        }//end method main
    }//end class Main

Answer 1

关于回溯没有发生的一个关键提示是，您有一个名为 solve 的布尔函数，其返回值根本没有被使用。

在此循环中：

     for( int num = 1; num < 10; num++ )
     {
        if( checkRow(row,num,grid) && checkCol(col,num,grid) && checkBox(row,col,num,grid) )
        {
           grid[row][col] = num ;
           moveCounter++;
           System.out.println("current move count is " + moveCounter);
           printSolvedGrid(grid);
           next( row, col, grid );
           return true;
        }
     }

您为当前单元找到合适的候选单元，将其插入，然后调用next。 next 然后调用 solve，但返回后，您只是假设这是正确的选择并返回 true; 因此，如果 solve code> 返回 false，您没有注意它，也没有尝试该单元格的其他选择。

Answer 2

您的解决方案陷入困境，因为当您使用递归时（优化代码不太容易，您可以使其尾部递归，以便堆栈不会建立，但您没有建立。虽然这是一个单独的问题），但实际上您并不是检查每个可能的分支。

让我给你举一个例子，你的代码会被卡住：

考虑一下你的数独谜题的左上角：

0 0 3
4 5 6
7 8 9
0 2

你的算法将检查平方 [0][0] 并发现 1 是合适的。然后它会继续检查方格 [0][1] 并发现 1 不合适。同样，当检查 2 时，它会发现该列中已经有一个 2。其余的数字都在盒子里。所以它被卡住了，因为它永远不会回溯到之前的决定。

它应该做什么？它应该递归，它应该能够后退并更改导致这种情况的决策。 “真正的”递归（即检查有效递归树的所有可能选项的递归）将能够“撤消”最后一个决定并尝试下一个决定，即找到 2 可以位于左上角，然后继续在。

Answer 3

已修复：

我拿走了布尔值和 return 语句:)

顺便说一句，看来我原来的测试用例没有解决方案，但这两个输入确实产生一个：

input1.txt

900576813630090002005000900001004730200000008076900500003000600400050091712869005 

input2.txt （这个更难）

200609050604083000000700000048000200000010000001000490000001000000970103020408005 

代码：

static void solve(int row, int col, int [][]grid){

       if (row>=grid.length){

           System.out.println("solution found");
           printSolvedGrid(grid);
           System.exit(0);

       }

       if( grid[row][col] != 0 ){
            next( row, col, grid ) ;
       }

       else {
         // Find a valid number for the empty cell
         for( int num = 1; num < 10; num++ )
         {
            if( checkRow(row,num,grid) && checkCol(col,num,grid) && checkBox(row,col,num,grid) )
            {
               grid[row][col] = num ;
               moveCounter++;
               System.out.println("current move count is " + moveCounter);
               printSolvedGrid(grid);
               next( row, col, grid );

            }
         }

         grid[row][col] = 0 ;
       }

    }

Answer 4

不确定“卡住”到底是什么意思，是代码卡住了还是无法解决难题。

简要地看一下，我找不到代码有什么问题，但同时，您使用递归的方式并不完全正确，但它应该运行，即使它没有找到解决方案......

但是有您没有使用的其他解决数独难题的技术，X-Wing 可能是最复杂的之一...

即使按照您现在正在做的事情，您可能需要多次运行这些测试...

编辑：

我运行您的代码，运行得很好，在最后阶段，它打印了：

current move count is 6
3 6 4 7 2 8 1 9 0 
2 0 1 9 5 0 0 7 0 
0 9 0 0 0 4 8 5 2 
0 0 5 4 9 0 0 0 1 
0 0 6 0 0 0 9 0 0 
8 0 0 0 5 1 3 0 0 
9 5 8 1 0 0 0 2 0 
0 1 0 0 7 2 6 0 8 
0 0 0 0 8 0 5 0 0 

和然后就完成了......它再也不能解决任何问题了。

我认为您不应该将其用作

row>=grid.length

终止条件，而应该遍历网格以查找是否还剩下“0”。在 row>=grid.length 的情况下，您应该重新开始：solve(0,0,grid)。
这可能仍然不能解决所有问题，但肯定会更进一步。