DFS求解数独

Question

我正在用DFS算法处理16 * 16数独问题。 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; 

    } 
} 

和主要方法是：

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

    } 

当我运行的代码，它经常终止之前的所有空格填满，留下许多-1难题。我不确定问题出在哪里。我将非常感谢任何帮助！

Answer 1

这并不重要，但这可能会被归类为backtracking问题，而不是搜索。无论如何，我认为这是事实，但如果没有这种方法，很难进行测试。在检查给定单元格中的每个可能的数字后，如果没有找到答案（击中基本情况），则需要将单元格设置回-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，即使没有找到答案，也会将这些值设置为最高有效值。递归算法的未来迭代将跳过该值，因为他们认为它是正确的。因此，你的循环将结束而不用测试所有的可能性并找到答案。希望这是为你做的。

评论响应

是，我同意有至少1种溶液。我相信问题在于，在你实际测试所有可能性之前，你的循环已经结束。您的递归调用需要在测试每种可能性后重新设置网格。在递归堆栈中的任意深度处，假设您将一个有效数字添加到网格中。在该阶段有效的数字并不意味着它处于正确的位置。你可以创造一个涟漪效应。虽然它目前对于这个特定的数字是有效的，但您已经无意中根据您填充的单元格解决了任何解决方案的可能性。一旦你遇到这种情况，你有一个问题。您的网格将保留最近设置的值，并且您将永远不会尝试将其设置为其他任何值（因为您有一个忽略值！= -1的条件）。