Backtracking funktioniert nicht ganz

[districon]

Hallo,
folgendes ist ein Codestück aus meinem Programm:

public static boolean springtour(int[][] sol, int i, int j, int step_count, int[] x_move, int[] y_move, boolean[][] board, int counter) {
        if (step_count == counter)
            return true;
        

        for(int k=0; k<8; k++) {
            int nextI = i+x_move[k];
            int nextJ = j+y_move[k];
            if (isValid(nextI, nextJ, sol, board)) {
                sol[nextI][nextJ] = step_count;
                realsol[nextI][nextJ] = step_count;

                if (springtour(sol, nextI, nextJ, step_count+1, x_move, y_move,board, counter)) {
                    return true;
                }
                    sol[nextI][nextJ] = 0;
                realsol[nextI][nextJ] = 0;
            }
        }
        return false;
    }

Irgendwie funktioniert das Backtracking nicht. Es liefert auch eine true zurück, auch wenn step_count ungleich counter ist. Somit probiert es hier nicht alle Lösungen durch. Was habe ich falsch gemacht?

 

[Robertop]

Ich weiss zwar nicht genau, was das Programm macht, aber wenn du mit "alle Möglichkeiten durchgehen" meinst, dass die For-Schleife komplett durchlaufen werden soll, dann spielen da bestimmt Zeile 13 und 14 eine Rolle:
Weil Step Dort um eins erhöht wird gehe ich mal davon aus, dass die Funktion früher oder später mit steopCount == counter aufgerufen wird und sofort True antwortet. Ab da ist die Antwort, die man bekommt dann immer True, egal wie viele Schritte er gemacht hat und wie weit er in der For-Schleife ist.

 

[LimDul]

Ich weiss zwar nicht genau, was das Programm macht, aber wenn du mit "alle Möglichkeiten durchgehen" meinst, dass die For-Schleife komplett durchlaufen werden soll, dann spielen da bestimmt Zeile 13 und 14 eine Rolle:
Weil Step Dort um eins erhöht wird gehe ich mal davon aus, dass die Funktion früher oder später mit steopCount == counter aufgerufen wird und sofort True antwortet. Ab da ist die Antwort, die man bekommt dann immer True, egal wie viele Schritte er gemacht hat und wie weit er in der For-Schleife ist.

Das ist aber im Sinne des Backtrackings eigentlich auch korrekt - er hat dann eine Lösung gefunden und das soll auch zurückgegeben weren

 

[CSHW89]

Das Coding sieht erstmal korrekt aus. Allerdings ohne die Methode isValid, sowie deine nachträgliche Betrachtung des Arrays sol, lässt sich da nichts weiteres zu sagen. Und was macht eigentlich das Array realsol? Das erschließt sich mir bisher auch nicht.

Mal ganz davon ab, könntest du die Struktur noch etwas überarbeiten. x_move , y_move und board (vielleicht auch noch sol) sollten eher Instanzvariablen einer Klasse sein. Dann musst du diese Variablen nicht immer mitschleppen. Die Methode "springtour" dürfte dann natürlich nicht static sein. Aber das spielt für die Korrektheit erstmal keine Rolle.