获取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（）。

只需循环，弹出一个棋盘，生成所有有效的下一步棋，看看它们中的一个是否是解决方案，如果没有，则将它们推入栈中。

（我无法找到你验证板是完整的，但我可能累了。）

顺便说一句，堆栈可能应该出列。我相信一个堆栈是同步的，这会降低代码速度。