数独求解器调试

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