遞歸回溯問題

Question

我試圖在Java中實現回溯算法，以解決數獨問題。

我95％確定問題出在解決方法，但我在案例中包括了兩種附加方法。

我正在做的一些奇怪的事情只是由於需求/便利，就像拼圖的硬編碼初始值。我敢肯定，問題在於我的解決方法的底部附近，但我不知道它...

我目前的問題是這樣的：在第一行工作，並找到一個潛在的有效值的排列之後，我的程序簡單地放棄了。如果我取消打印「ROW IS DONE」的行的註釋，它將在一行後打印，並且不再給出輸出。爲什麼在第一行之後放棄？有什麼關於我的執行我應該擔心的

編輯：我做了很多改變。它變得非常接近。如果我在EXHAUST爲真的情況下進行打印，我會得到一個難題，除了最後一個解決方案以外，每行都解決了。它看起來像是在它解決/接近解決它之後撤消所有的東西。我覺得它可能已經達到了難題完全解決的地步，但是我沒有在正確的時間回傳TRUE ......我現在做錯了什麼？

import java.util.ArrayList; 

class Model 
{ 
    ArrayList<View> views = new ArrayList<View>(); 
    int[][] grid = 
      { 
       {5,3,0,0,7,0,0,0,0}, 
       {6,0,0,1,9,5,0,0,0}, 
       {0,9,8,0,0,0,0,6,0}, 
       {8,0,0,0,6,0,0,0,3}, 
       {4,0,0,8,0,3,0,0,1}, 
       {7,0,0,0,2,0,0,0,6}, 
       {0,6,0,0,0,0,2,8,0}, 
       {0,0,0,4,1,9,0,0,5}, 
       {0,0,0,0,8,0,0,7,9} 
      }; 

    /** 
    * Method solve 
    * 
    * Uses a backtracking algorithm to solve the puzzle. 
    */ 
    public boolean solve(int row, int col) //mutator 
    { 
     if(exhaust(row,col)) {printGrid(); return true;} 
     int rownext = row; 
     int colnext = col+1; 
     if(colnext>8) 
     { 
      colnext = 0; 
      rownext++; 
     }   
     if(grid[row][col] != 0) solve(rownext,colnext); 
     else //is == 0 
     { 
      for(int num = 1; num <= 9; num++) 
      { 
       if(!conflict(row,col,num)) //try a non-conflicting number 
       { 
        grid[row][col] = num; 
        if(solve(rownext,colnext)) return true;      
        grid[row][col] = 0; 
       } 
      } 
     } 
     return false;  

    } 
    /** 
    * Method exhaust 
    * 
    * Iteratively searches the rest of the puzzle for empty space 
    * using the parameters as the starting point. 
    * 
    * @return true if no 0's are found 
    * @return false if a 0 is found 
    */ 
    public boolean exhaust(int row, int col) 
    { 
     for(int i = row; i <= 8; i++) 
     { 
      for(int j = col; j <= 8; j++) 
      { 
       if(grid[i][j] == 0) return false; 
      } 
     } 
     System.out.printf("Exhausted.\n"); 
     return true; 
    } 

    /** 
    * Method conflict 
    * 
    * Checks if the choice in question is valid by looking to see 
    * if the choice has already been made in the same row or col, 
    * or block. 
    * 
    * @return true if there IS a conflict 
    * @return false if there is NOT a conflict 
    */ 
    public boolean conflict(int row, int col, int num) 
    { 
     for(int j = 0; j <= 8; j++) 
     { 
      if(grid[row][j] == num) { 
       return true; 
      } 
     } 
     for(int i = 0; i <= 8; i++) 
     { 
      if(grid[i][col] == num) { 
       return true; 
      } 
     }   

     int rowstart = 0; 
     if(row>=3) rowstart = 3; 
     if(row>=6) rowstart = 6; 

     int colstart = 0; 
     if(col>=3) colstart = 3; 
     if(col>=6) colstart = 6;      

     for(int r = rowstart; r <= (rowstart + 2); r++) 
     { 
      for(int c = colstart; c <= (colstart + 2); c++) 
      { 
       if(grid[r][c] == num) { 
        return true; 
       } 
      } 
     }  
     return false; 
    } 
} 

Answer 1

想象一下，你正在順利地前進，並排，並沒有回溯。你的下一個位置是solve(1,1);。在跟蹤代碼時請注意rownext。你應該很快看到問題。如果你沒有回溯，rownext應該保持至少爲1.