獲取StackOverflow錯誤

Question

我試圖編寫一個程序，需要一個Sudoku難題並解決它。 不過，我遇到了一個錯誤的StackOverflow在這一行：

Move nMove = new Move(current.nextMove(current, sboard).i, current.nextMove(current, sboard).j); 

它具有檢查，此舉是否有效的方法isLegal。如果移動有效並且下一步移動也有效，則將其添加到堆棧。如果它是有效的，但下一步不是，它應該繼續搜索一個有效的數字。 不知道是什麼原因造成的。

import java.util.Stack; 

public class Board { 
    Stack<Move> stack = new Stack<Move>(); 
    int boardSize = 9; 
    public int[][] sboard = {{2,0,0,3,9,5,7,1,6}, 
      {5,7,1,0,2,8,3,0,9}, 
      {9,3,0,7,0,1,0,8,2}, 
      {6,8,2,0,3,9,1,0,4}, 
      {3,5,9,1,7,4,6,2,8}, 
      {7,1,0,8,6,0,9,0,3}, 
      {8,6,0,4,1,7,2,9,5}, 
      {1,9,5,2,8,6,4,3,7}, 
      {4,2,0,0,0,0,8,6,1}}; 

    public Board() { 
     //for every cell in board: 
     for (int i = 0; i < boardSize; i++) { 
      for (int j = 0; j < boardSize; j++) { 
       //get the value of each cell 
       int temp = getCell(i,j); 
       //if cell is empty: 
       if (temp == 0) { 
        //print out location of cell 
        System.out.print ("("+i+", "+j+") "); 

        //guess values for that cell 
        solve(i, j); 
       } 
      } 
     } 
    } 

    //places a value into specified cell 
    public void setCell(int value, int row, int col) { 
     sboard[row][col] = value; 
    } 

    //returns value contained at specified cell 
    public int getCell(int row, int col) { 
     return sboard[row][col]; 
    } 

    //if value is legal, continue 
    public boolean isLegal(int value, int row, int col) { 
     int r = (row/boardSize) * boardSize; 
     int c = (col/boardSize) * boardSize; 

     for (int i = 0; i < boardSize; i++) { 
      for (int j = 0; j < boardSize; j++) { 
       if (value == getCell(i, col) || value == getCell(row, j)) { 
        return false; 
       } 
      } 
     } 

     return true; 
    } 

    //guesses values for empty cells 
    public boolean solve(int i, int j) { 
     //set location as current 
     Move current = new Move(i, j); 
     Move nMove = new Move(current.nextMove(current, sboard).i, current.nextMove(current, sboard).j); 
     //guesses values 1 through 9 that are legal 
     for (int k = 1; k <= 9; k++) { 
      //if a legal value is found and the next move is possible: 
      if(isLegal(k, i, j) && solve(nMove.i, nMove.j)) { 
       //add current to stack 
       stack.push(current); 
       //enter the value k into the cell 
       setCell(k, i, j); 
       //print new value 
       System.out.print(sboard[i][j]+"\n"); 
       //return as true 
       return true; 
      } 

      else if (stack.empty()){ 

      } 
      //if next move is not possible 
      else if(!solve(nMove.i, nMove.j)){ 
       //remove last "solved" location from stack 
       stack.pop(); 
       //solve last location again 
       solve(stack.peek()); 
      } 
     } 
     return false; 
    } 

    public void solve(Move m) { 
     solve(m.i, m.j); 
    } 

    public static void main(String[] args) { 
     Board b = new Board(); 
    } 
}; 

class Move { 
    int i, j; 

    public Move(int i, int j) { 
     this.i = i; 
     this.j = j; 
    } 

    public int i() { return i;} 

    public int j() { return j;} 

    public Move nextMove(Move current, int[][] sboard){ 
     for (int i = current.i; i < 9; i++) { 
      for (int j = current.j; j < 9; j++) { 
       //get the value of each cell 
       int temp = sboard[i][j]; 
       if (temp == 0) { 
        return new Move(i, j); 
       } 
      } 
     } 
     return current; 
    } 
}; 

Answer 1

首先，我覺得這個函數的形式爲current.nextMove(current, board)似乎多餘。您可以使此功能靜態，或者刪除參數Move current。

但考慮看看你solve(i, j)功能，你基本上是這樣：

1. 假設sboard[i][j] = 0（這顯然不行，在某些情況下，從你的輸入）。
2. 假設您致電solve(i, j)。
3. current將是new Move(i, j)。然後
4. nMove也將new Move(i, j)（因爲在移動＃的NextMove， 你本質上說if sboard[i][j] == 0，它從步驟 1一樣）。
5. 你最終將調用solve(nMove.i, nMove.j)
6. 由於nMove.i == i和nMove.j == j，你基本上是在調用solve(i, j)一遍。

由於您使用相同的參數調用相同的函數，並且沒有達到任何基本情況，最終會導致堆棧溢出。

Answer 2

由於您已經定義了一個（顯式）堆棧，因此不應該以遞歸方式調用solve（）。

只需循環，彈出一個棋盤，生成所有有效的下一步棋，看看它們中的一個是否是解決方案，如果沒有，則將它們推入棧中。

（我無法找到你驗證板是完整的，但我可能累了。）

順便說一句，堆棧可能應該出列。我相信一個堆棧是同步的，這會降低代碼速度。