Estoy buscando implementar un algoritmo muy simple que use el seguimiento de fuerza bruta para resolver las cuadrículas de Sudoku. El problema al que me enfrento es que en mi implementación incluí dos variables de instancia para unSudoku clase llamadarow ycol, que corresponden a la fila y columna de una celda vacía en una matriz bidimensional que representa la cuadrícula de Sudoku.

Cuando misolve() El método lo ejecuta primero para ver si no hay celdas vacías, en cuyo caso el rompecabezas ya está completo. De lo contrario, ese mismo método asigna la fila y la columna de una celda vacía a las variables de instanciarow ycol delSudoku Objeto que contiene la cuadrícula. Luego, el bucle for verifica qué número se puede colocar en esa celda vacía a través de una llamada de métodoisSafe(int n) (Este método verifica si se cumplen las restricciones del rompecabezas, puedo garantizar que funciona perfectamente). Entonces elisSafe() El método coloca un número en la celda vacía y luego hace una llamada recursiva alsolve() método de nuevo en elSudoku objeto.

Si alcanzamos una restricción que no se puede cumplir, entonces reasignamos una0 hasta el ultimorow ycol que se llenó Aquí es donde se encuentra el problema! Dado que el programa está actualizando constantemente elrow ycol variables entonces las instancias antiguas se pierden con cada llamada recursiva. He estado tratando de averiguar cómo almacenar estos valores para que el programa pueda deshacer acciones cuando realiza un seguimiento. Pensé en empujar a cada unocol yrow a una pila, pero realmente no estoy seguro de dónde ir.

¿Alguien puede decirme cuál sería una manera simple de abordar este problema? No estoy incluyendo a toda la clase, si crees que sería útil, házmelo saber y lo publicaré.

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

Si tuviera que implementar una pila, ¿tiene sentido lo siguiente? Después de lafindNextZero() operaciones empujan elrow ycol enteros en la pila. Sigue haciendo esto y luego modifica la siguiente línea de código

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

a algo como

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

¿Es este un enfoque razonable?