为什么数独回溯被卡住了?

本文介绍了为什么数独回溯被卡住了?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在写一个数独回溯解算器，它卡住了，我不明白为什么.我认为我的递归调用很好.我想念的是什么?

I'm writing a sudoku backtracking solver, it's getting stuck and I don't understand why. I think my recursive calls are alright. What I'm missing?

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

Input is read from input.txt file with the grid initial layout in a single line:

input.txt:

input.txt:

004020000201950070090004852005490001006000900800051300958100020010072608000080500

我的意思是卡住"是指尚未完成对网格的求解

I mean 'stuck' as not finishing its solving of the grid

这是示例输出:

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

推荐答案

固定:

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

I took away the boolean and return statements :)

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

BTW, it appears my original test case doesn't have solution, but these two inputs do yield one:

input1.txt

input1.txt

900576813630090002005000900001004730200000008076900500003000600400050091712869005

input2.txt(这很难)

input2.txt (this one is harder)

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 ; } }