Получение ошибки 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). Вы можете сделать эту функцию статической или удалить параметр 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) (поскольку в Move # 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

Так как вы определили (явный) стек, вы не должны вызывать execute () рекурсивно.

Просто зациклите, извлеките доску, сгенерируйте все допустимые следующие ходы, посмотрите, является ли один из них решением,и если нет, поместите их в стек.

(я не могу найти, где вы можете проверить, что доска готова, но я, вероятно, устал.)

Кстати, стек, вероятно, долженБудь Деку.Я считаю, что стек синхронизирован, что замедляет код.