java - 出现 StackOverflow 错误

Question

我正在尝试编写一个程序来解决数独难题。 但是，我在这一行遇到了 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) 的形式使用此函数似乎是多余的。您可以将此函数设置为静态，也可以删除移动当前参数。

但是看看你的 solve(i, j) 函数，你基本上有这个:

1. 假设 sboard[i][j] = 0(在某些情况下，根据您的输入，显然是这样)。
2. 假设您调用 solve(i, j)。
3. 当前将是new Move(i, j)。
4. nMove 也将是 new Move(i, j) (因为在 Move#nextMove 中， 你本质上是说 if sboard[i][j] == 0，它在步骤中执行 1).
5. 您最终将调用 solve(nMove.i, nMove.j)
6. 由于 nMove.i == i 和 nMove.j == j，您实际上是在再次调用 solve(i, j)。

由于您使用相同的参数调用相同的函数，并且没有达到任何基本情况，因此最终会出现堆栈溢出。