数独バックトラッキングソルバーを書いていますが、行き詰まっていて、理由がわかりません。私の再帰呼び出しは大丈夫だと思います。私が欠けているものは何ですか？
入力は、1行のグリッド初期レイアウトで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