获取StackOverflow错误

Question

我正在试着写一个程序，它接受数独难题并解决它。然而，我在这一行遇到了一个StackOverflow错误：

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

它有一个isLegal方法，用于检查移动是否有效。如果move是有效的，并且下一次move也是有效的，则将其添加到堆栈中。如果它是有效的，但下一步是无效的，它应该继续搜索有效的数字。不确定是什么引起的。

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. 假定您调用的是new Move(i, j).
3. nMove，然后也将是sboard[i][j] = 0(因为在Move#nextMove中，您实际上说的是if sboard[i][j] == 0，这是它在步骤1中所做的)。
4. 您最终将调用D23和D24，您实际上是在重复调用D25。H226

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

Answer 2

因为您已经定义了一个(显式)堆栈，所以不应该递归地调用solve()。

只要循环，弹出一个棋盘，生成所有有效的下一步动作，看看其中是否有一个是解决方案，如果不是，就把它们推到堆栈上。

(我找不到您在哪里验证电路板是否完整，但我可能很累。)

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