Блог

Я пытаюсь написать программу, которая берет головоломку судоку и решает ее. Тем не менее, я сталкиваюсь с ошибкой 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) amp;amp; 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;
    }
};
 

Во-первых, мне кажется излишним иметь эту функцию в форме 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 and nMove.j == j , вы, по сути, вызываете solve(i, j) снова.

Поскольку вы вызываете ту же функцию с тем же параметром, и вы не достигаете какого-либо базового варианта, вы получите переполнение стека.

Поскольку вы определили (явный) стек, вы не должны вызывать функцию solve() рекурсивно.

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

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

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