Eu estou olhando para implementar um algoritmo muito simples que usa back-tracking de força bruta para resolver grids de Sudoku. O problema que estou enfrentando é que na minha implementação incluí duas variáveis ​​de instância para umSudoku classe chamadarow ecol, que correspondem à linha e coluna de uma célula vazia em uma matriz bidimensional que representa a grade de Sudoku.

Quando meusolve() método executa primeiro verifica para ver se não há células vazias, caso em que o quebra-cabeça já está completo. Caso contrário, esse mesmo método atribui a linha e a coluna de uma célula vazia às variáveis ​​de instânciarow ecol doSudoku objeto que contém a grade. Posteriormente, o loop for verifica qual número pode ser colocado naquela célula vazia por meio de uma chamada de métodoisSafe(int n) (Esse método verifica se as restrições do quebra-cabeça estão sendo atendidas, posso garantir que ele funcione perfeitamente). Então oisSafe() método coloca um número na célula vazia e, em seguida, faz uma chamada recursiva para osolve() método novamente noSudoku objeto.

Se acertarmos uma restrição que não pode ser cumprida, então reatribuímos0 até o últimorow ecol que foi preenchido. É aqui que o problema é encontrado! Como o programa está constantemente atualizandorow ecol variáveis, em seguida, as instâncias antigas são perdidas com cada chamada recursiva. Eu tenho tentado descobrir como armazenar esses valores para que o programa possa desfazer ações quando voltar atrás. Eu pensei em empurrar cadacol erow para uma pilha, mas eu realmente não tenho certeza para onde ir.

Alguém pode me dizer qual seria uma maneira simples de abordar esse problema? Eu não estou incluindo a turma inteira, se você acha que seria útil, me avise e postarei.

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);
    }

Se eu fosse implementar uma pilha, o seguinte faz sentido? Depois defindNextZero() operações empurrar orow ecol inteiros na pilha. Continue fazendo isso e, em seguida, modifique a linha de código a seguir

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

para algo como

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

Esta é uma abordagem razoável?