Я пытаюсь реализовать очень простой алгоритм, который использует обратное отслеживание методом грубой силы для решения сеток Судоку. Проблема, с которой я сталкиваюсь, заключается в том, что в моей реализации я включил две переменные экземпляра дляSudoku класс называетсяrow а такжеcol, которые соответствуют строке и столбцу пустой ячейки в двумерном массиве, который представляет сетку судоку.

Когда мойsolve() Метод выполняет сначала проверку, чтобы увидеть, нет ли пустых ячеек, и в этом случае головоломка уже завершена. В противном случае этот же метод назначает строку и столбец пустой ячейки переменным экземпляра.row а такжеcol изSudoku объект, который содержит сетку. После этого цикл for проверяет, какое число может быть помещено в эту пустую ячейку с помощью вызова метода.isSafe(int n) (Этот метод проверяет, соблюдаются ли ограничения головоломки, я могу гарантировать, что она отлично работает). Так чтоisSafe() метод помещает число в пустую ячейку, а затем делает рекурсивный вызовsolve() метод снова наSudoku объект.

Если мы столкнемся с ограничением, которое не может быть выполнено, то мы переназначим0 до концаrow а такжеcol это было заполнено. Это где проблема найдена! Так как программа постоянно обновляетrow а такжеcol переменных, то старые экземпляры теряются при каждом рекурсивном вызове. Я пытался выяснить, как сохранить эти значения, чтобы программа могла отменить действия, когда она возвращается. Я думал о толкании каждогоcol а такжеrow в стек, но я действительно не уверен, куда идти.

Может кто-нибудь сказать мне, что было бы простым способом решить эту проблему? Я не включаю весь класс, если вы думаете, что это будет полезно, дайте мне знать, и я опубликую это.

class Sudoku {
    int SIZE, N, row, col;
    int Grid[][];    

    public boolean solve() {
        if (!this.findNextZero()) return true;

        for (int num = 1; num <= 9; num++) {
            if (isSafe(num)) {
                this.Grid[this.row][this.col] = num;

                if (this.solve()) return true;

                this.Grid[this.row][this.col] = 0;
                // this.Grid[oldRow][oldCol] = 0;
            }
        }
        return false;
    }

    public boolean findNextZero() {
        for (int i = 0; i < this.N; i++) {
            for (int j = 0; j < this.N; j++) {
                if (this.Grid[i][j] == 0) {
                    this.row = i;
                    this.col = j;
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isSafe(int num) {
        return !this.usedInRow(num) 
                && !this.usedInColumn(num) 
                && !this.usedInBox(num);
    }

Если бы я должен был реализовать стек, имеет ли смысл следующее? ПослеfindNextZero() операции подтолкнутьrow а такжеcol целые числа в стек. Продолжайте делать это, а затем измените следующую строку кода

this.Grid[this.row][this.col] = 0;

что-то вроде

this.Grid[s.pop][s.pop] = 0;

Это разумный подход?