DFS résolvant le sudoku

Question

Je travaille sur un problème de sudoku 16 * 16 avec l'algorithme DFS. code Java ressemble à:

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; 

    } 
} 

Et la principale méthode est:

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."); 

    } 

Quand je lance le code, il se termine souvent devant être remplis espaces vides tout en laissant beaucoup -1 dans le casse-tête. Je ne suis pas sûr d'où le problème est. Je serai vraiment reconnaissant pour toute aide!

Answer 1

Peu importe, mais cela serait probablement classé comme un problème , pas une recherche. Quoi qu'il en soit, je pense que c'est ça, mais il est difficile de tester sans cette méthode generatePuzzleMatrix. Après avoir vérifié chaque nombre possible dans une cellule donnée, si vous ne trouvez pas de réponse (tapez votre cas de base), vous devez redéfinir la cellule sur -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; 

Sans cette mise en valeur à -1, vous allez laisser ces valeurs définies comme la valeur la plus élevée valable, même si vous ne trouvez pas de réponse. Les itérations futures de votre algorithme récursif ignorent cette valeur car elles supposent qu'elle est correcte. Ainsi, votre boucle se terminera sans tester toutes les possibilités et trouver une réponse. J'espère que ça le fait pour toi.

Commentaire Réponse

Oui, je suis d'accord il y a au moins une solution. Je crois que le problème est que votre boucle se termine avant de tester toutes les possibilités. Vos appels récursifs doivent replacer la grille une fois qu'ils ont testé toutes les possibilités. À une profondeur arbitraire dans la pile récursive, disons que vous ajoutez un nombre valide à votre grille. Le nombre étant valide à ce stade n'implique pas qu'il est dans la bonne position. Vous pourriez créer un effet d'entraînement. Bien qu'il soit actuellement valide pour ce nombre particulier, vous avez involontairement éliminé la possibilité d'une solution basée sur les cellules que vous avez remplies jusqu'à présent. Une fois que vous avez atteint ce scénario, vous avez un problème. Votre grille conservera la dernière valeur définie, et vous n'essaierez jamais de la définir sur autre chose (car vous avez une condition qui ignore les valeurs! = -1).