DFS solving sudoku

Question

私はDFSアルゴリズムで16 * 16 sudoku問題に取り組んでいます。 Javaコードは次のようになります。

public class dfs { 

    public boolean dfs(int[][] puzzle,int i,int j){ 
     if(i==15&&j>=16) return true; 
     if(j==16){ 
      //System.out.println(String.valueOf(i)); 

      return dfs(puzzle,i+1,0); //{j=0; i++; 
     } 
     if(puzzle[i][j]!=-1){ 
      return dfs(puzzle,i,j+1); //next cell in the same row 
     } 
     else{ 
      for(int num=1;num<=16;num++){ 
       //System.out.println("trying"+i+","+j+","+num); 
       if(valid(puzzle,i,j,num)){ 
        //System.out.println(String.valueOf(num)); 
        puzzle[i][j]=num; 
        if(dfs(puzzle,i,j+1)){ 
         return true; 

        } 
       } 
       //else return false; 
      } 
     } 
     return false; 
    } 
    public boolean valid(int[][] puzzle,int x,int y,int num){ 
     for(int i=0;i<16;i++){ 
      if(puzzle[i][y]==num) { 
       //System.out.println("a"); 
       return false; 
      } 
     } 
     for(int j=0;j<16;j++){ 
      if(puzzle[x][j]==num){ 
       //System.out.println("b"); 
       return false; 
      } 
     } 
     int c=(x/4)*4; 
     int r=(y/4)*4; 
     for(int i=0;i<4;i++){ 
      for(int j=0;j<4;j++){ 
       if(puzzle[c+i][r+j]==num){ 
        //System.out.println("c"); 
        return false; 
       } 
      } 

     } 
     return true; 

    } 
} 

そして、mainメソッドは次のとおりです。私は、コードを実行すると、それは多くの場合、多く-1パズルでを残して、前にすべての空白を埋めることが終了

public static void main(String[] args) { 
     sudoku sudokuPuzzleGenerator = new sudoku(); 
     long start = System.currentTimeMillis(); 
     int numOfSudokuMatrix = 1; 
     List<int[][]> sudoku = new ArrayList<int[][]>(); 
     for (int count = 1; count <= numOfSudokuMatrix; count++) { 
      int[][] randomMatrix = sudokuPuzzleGenerator.generatePuzzleMatrix(); 
      int hole = 81; 
      while (hole > 0) { 
       Random randomGenerator = new Random(); 
       int x = randomGenerator.nextInt(16); 
       int y = randomGenerator.nextInt(16); 
       if (randomMatrix[x][y] != -1) { 
        randomMatrix[x][y] = -1; 
        hole--; 
       } 
      } 
      for(int i=0;i<16;i++){ 
       for(int j=0;j<16;j++){ 
        System.out.print(randomMatrix[i][j] + " "); 
       } 
       System.out.println(); 
      } 
      sudoku.add(randomMatrix); 
     } 
     System.out.println(); 


     long start2 = System.currentTimeMillis(); 
     for (int[][] p:sudoku) { 
      dfs d=new dfs(); 
      boolean b=d.dfs(p,0,0); 
      for (int rowNum = 0; rowNum < 16; rowNum++) { 
       for (int colNum = 0; colNum < 16; colNum++) { 
        System.out.print(p[rowNum][colNum] + " "); 
       } 
       System.out.println(); 
      } 
     } 
     Long end2 = System.currentTimeMillis(); 
     Long time2 = end2 - start2; 
     System.out.println("It took: " + time2 + " milliseconds."); 

    } 

。私は問題がどこにあるのか分からない。私は本当に助けに感謝します！

Answer 1

これは問題ではありませんが、これは恐らくbacktrackingという問題に分類されますが、検索ではありません。とにかく、これはそれだと思いますが、その方法がないとテストするのは難しいです。generatePuzzleMatrix与えられたセルで可能な数をすべて確認した後、答えが見つからない場合（ベースケースにヒットした場合）、セルを-1に戻す必要があります。

for(int num=1;num<=16;num++){ 
    if(valid(puzzle,i,j,num)){ 
     puzzle[i][j]=num; 
     if(dfs(puzzle,i,j+1)){ 
      return true; 
     } 
    } 
} 
puzzle[i][j] = -1; 

バック-1にこの値を設定せずに、あなたは答えを見つけられませんでした場合でも、最高の有効な値として設定され、これらの値を残すしようとしています。あなたの再帰アルゴリズムの将来の反復は、それが正しいと仮定してその値をスキップします。したがって、ループはすべての可能性をテストせずに答えを見つけることなく終了します。これがyaのためにそれをすることを願っています。

コメント応答

はい、私は、少なくとも1つの解が存在であることに同意。問題はすべての可能性を実際にテストする前にループが終了していることだと私は信じています。再帰呼び出しは、すべての可能性をテストしたら、グリッドを元に戻す必要があります。再帰的スタックの任意の深さで、グリッドに有効な数値を追加するとします。その段階で有効な番号が正しい位置にあることを意味するものではありません。リップル効果を作り出すことができます。現在のところ、この特定の番号には有効ですが、これまでに入力したセルに基づいて、意図せずにすべてのソリューションの可能性を排除しました。このシナリオに遭遇すると、問題が発生します。あなたのグリッドは最後に設定された値を保持します。値を無視する条件があるので、何も設定しないでください！= -1）。