數獨求解器調試

Question

我知道以前有幾個這樣的帖子，但他們沒有幫助我。我正在編寫一個可以解決數獨的程序。我在這裏找到了一個算法：http://www.heimetli.ch/ffh/simplifiedsudoku.html。我試圖用java編寫它，並從基於控制檯的程序開始。由於某種原因它會陷入無限循環，儘管我有辦法阻止它。

package sudokuSolver; 

public class Solver { 
static int[][] board; //teh board 
static boolean solved;   //if the sudoku is solved 

public static void main(String[] args) throws Exception 
{ 
    //establish temporary board for now 
    final int[][] TUE24JAN = {{0,0,9,0,0,0,8,0,0}, 
           {0,1,0,0,2,0,0,3,0}, 
           {0,0,0,7,0,8,0,0,0}, 
           {2,0,0,0,8,0,0,0,7}, 
           {0,3,0,1,0,2,0,4,0}, 
           {4,0,0,0,7,0,0,0,5}, 
           {0,0,0,6,0,3,0,0,0}, 
           {0,8,0,0,9,0,0,7,0}, 
           {0,0,6,0,0,0,9,0,0},}; 

    final int[][] WED25JAN = {{2,5,0,0,0,0,4,0,0}, 
           {0,0,3,1,0,0,7,0,0}, 
           {0,0,0,0,8,4,0,6,0}, 
           {4,0,0,0,0,0,0,8,0}, 
           {7,0,0,0,1,0,0,0,4}, 
           {0,3,0,0,0,0,0,0,9}, 
           {0,9,0,6,5,0,0,0,0}, 
           {0,0,1,0,0,9,2,0,0}, 
           {0,0,2,0,0,0,0,4,3},}; 

    board = TUE24JAN; 
    solved = false; 
    printBoard(); 

    solve(0,0); 
    System.out.println("\n"); 
    printBoard(); 
} 

public static void solve(int x, int y) throws Exception 
{ 
    //catches the end of the line 
    if(y > 8) 
    { 
     y = 0; 
     x++; 
    } 

    //catches the end of the board 
    if(x > 8 || solved) 
    { 
     solved = true; 
     return; 
    } 
    //put a number in the cell 
    for(int i = 1; i < 10; i++) 
    { 
     if(!inRow(x, i) && !inCol(y, i) && !inBox(x, y, i) && !solved) 
     { 
      board[x][y] = i; 
      solve(x, y+1); 
      board[x][y] = 0; 
     } 
    } 
} 

//returns if the value is in the specified row 
public static boolean inRow(int x, int val) 
{ 
    for(int i = 0; i < 9; i++) 
     if(board[x][i] == val) 
      return true; 
    return false; 
} 

//returns whether the value is in the specified column 
public static boolean inCol(int y, int val) 
{ 
    for(int i = 0; i < 9; i++) 
     if(board[i][y] == val) 
      return true; 
    return false; 
} 

//returns whether the value fits based 
public static boolean inBox(int x, int y, int val) 
{ 
    int row = (x/3) * 3; 
    int col = (y/3) * 3; 
    for(int r = 0; r < 3; r++) 
    for(int c = 0; c < 3; c++) 
     if(board[row+r][col+c] == val) 
      return true; 
    return false; 
} 

public static void printBoard() 
{ 

    for(int i = 0; i < 9; i++) 
    { 
     if(i % 3 == 0) 
      System.out.println("----------------------"); 
     for(int j = 0; j < 9; j++) 
     { 
      if(j % 3 == 0) 
       System.out.print("|"); 
      if(board[i][j] < 10 && board[i][j] > 0) 
       System.out.print(board[i][j] + " "); 
      else 
       System.out.print("- "); 
     } 
     System.out.println("|"); 
    } 
    System.out.print("----------------------\n"); 
} 

}

編輯： 因爲當它終於到達一個解決方案，它改變了解決真可以讓它知道不再變化值應該不明確的細胞。 我沒有收到堆棧溢出錯誤，它只是繼續運行。我不小心讓它運行了一個小時，它仍然在運行，它只是一直在重複，從未達到解決的狀態，並且從未達到第一個遞歸序列。

至於一步一步的調試，你能做到嗎？我使用eclipse，但是如果有一個不同的IDE允許你逐行執行，你能告訴我嗎？

Answer 1

上面的代碼示例沒有充分利用遞歸的全部潛力，主要是對全局變量solved做了全面的處理。我沒有從頭開始提出解決方案，而是試圖修正你提出的問題，以便看到差異。如果您有任何疑問，請發表評論。 無需調試但有一點記錄和上面我說了一些不錯的評論想出了：

package sudoku; 

public class Solver { 
    static int[][] board; //teh board 
    static boolean solved; //if the sudoku is solved 

    public static void main(String[] args) throws Exception { 

     //establish temporary board for now 
     final int[][] TUE24JAN = 
      { 
       {0, 0, 9, 0, 0, 0, 8, 0, 0}, 
       {0, 1, 0, 0, 2, 0, 0, 3, 0}, 
       {0, 0, 0, 7, 0, 8, 0, 0, 0}, 

       {2, 0, 0, 0, 8, 0, 0, 0, 7}, 
       {0, 3, 0, 1, 0, 2, 0, 4, 0}, 
       {4, 0, 0, 0, 7, 0, 0, 0, 5}, 

       {0, 0, 0, 6, 0, 3, 0, 0, 0}, 
       {0, 8, 0, 0, 9, 0, 0, 7, 0}, 
       {0, 0, 6, 0, 0, 0, 9, 0, 0}, 
      }; 

     final int[][] WED25JAN = 
      { 
       {2, 5, 0, 0, 0, 0, 4, 0, 0}, 
       {0, 0, 3, 1, 0, 0, 7, 0, 0}, 
       {0, 0, 0, 0, 8, 4, 0, 6, 0}, 
       {4, 0, 0, 0, 0, 0, 0, 8, 0}, 
       {7, 0, 0, 0, 1, 0, 0, 0, 4}, 
       {0, 3, 0, 0, 0, 0, 0, 0, 9}, 
       {0, 9, 0, 6, 5, 0, 0, 0, 0}, 
       {0, 0, 1, 0, 0, 9, 2, 0, 0}, 
       {0, 0, 2, 0, 0, 0, 0, 4, 3}, 
      }; 

     board = TUE24JAN; 
     solved = false; 
     printBoard(); 

     solve(0, 0); 
     System.out.println("\n"); 
     printBoard(); 
    } // end method main 

    public static void solve(int x, int y) throws Exception { 

     //printBoard(); 
     System.out.println(x + " : " + y); 

     //catches the end of the line 
     if (y > 8) { 
      y = 0; 
      x++; 
     } 

     //catches the end of the board 
     if ((x > 8) || solved) { 
      solved = true; 
      return; 
     } 

     //put a number in the cell 
     for (int i = 1; i < 10; i++) { 

      if ((board[x][y] == 0)) { // cell to be filled 

       if (!inRow(x, i) && !inCol(y, i) && !inBox(x, y, i)) { // can use number 

        board[x][y] = i; 

        solve(x, y + 1); 

        if (solved) { 
         return; 
        } 

        board[x][y] = 0; 

       } 
      } 
      else { 
       solve(x, y + 1); 

       return; 

      } 
     } // end for 
    } // end method solve 

    //returns if the value is in the specified row 
    public static boolean inRow(int x, int val) { 

     for (int i = 0; i < 9; i++) { 

      if (board[x][i] == val) { 
       return true; 
      } 
     } 

     return false; 
    } 

    //returns whether the value is in the specified column 
    public static boolean inCol(int y, int val) { 

     for (int i = 0; i < 9; i++) { 

      if (board[i][y] == val) { 
       return true; 
      } 
     } 

     return false; 
    } 

    //returns whether the value fits based 
    public static boolean inBox(int x, int y, int val) { 
     int row = (x/3) * 3; 
     int col = (y/3) * 3; 

     for (int r = 0; r < 3; r++) { 

      for (int c = 0; c < 3; c++) { 

       if (board[row + r][col + c] == val) { 
        return true; 
       } 
      } 
     } 

     return false; 
    } 

    public static void printBoard() { 
     StringBuilder sb = new StringBuilder(); 

     for (int i = 0; i < 9; i++) { 

      if ((i % 3) == 0) { 
       sb.append("----------------------\n"); 
      } 

      for (int j = 0; j < 9; j++) { 

       if ((j % 3) == 0) { 
        sb.append("|"); 
       } 

       if ((board[i][j] < 10) && (board[i][j] > 0)) { 
        sb.append(board[i][j] + " "); 
       } 
       else { 
        sb.append("- "); 
       } 
      } 

      sb.append("|\n"); 
     } 

     sb.append("----------------------\n"); 
     System.out.println(sb.toString()); 

     /*try { 
      Thread.sleep(100); 
     } 
     catch (InterruptedException e) { 

      // TODO Auto-generated catch block 
      e.printStackTrace(); 
     }*/ 
    } // end method printBoard 
} // end class Solver