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

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

关于为什么不进行回溯的关键提示是你有一个名为boolean函数的函数,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,但是在返回之后,你只是假设这是正确的选择,return true; 所以如果solve返回false,你就不会注意它而不是为那个单元格尝试其他选择.