Backtracking

[districon]

Hallo, ich habe versucht einen Sudoku Solver zu programmieren. Dahinter steckt natürlich das Prinzip Backtracking. Aber irgendwie kommt es nicht aus der Endlosrekursion raus und ich sehe nicht genau warum. Hier sind die Hilfsmethoden:

public boolean isValid(int number, int row, int col, int[][] sudoku) {
        for (int i = 0; i < sudoku[row].length; i++) {
            if (sudoku[row][i] == number) return false;
            if (sudoku[i][col] == number) return false;
        }
        int r = row - row % 3;
        int c = col - col % 3;
        for (int x = r; x < r+3; x++) {
            for (int y = c; y < c+3; y++) {
                if (sudoku[x][y] == number) {
                    return false;
                }
            }
        }
        return true;
    }
    public boolean isFinal(int[][] sudoku) {
        for(int i = 0; i < sudoku.length; i++) {
            for (int j = 0; j < sudoku[i].length; j++) {
                if (sudoku[i][j] == 0) return false;
            }
        }
        return true;
    }

Und das meine Backtracking Methode:

public int[][] solve(int[][] sudoku) {
        int[] candidates = {1,2,3,4,5,6,7,8,9};
        if (isFinal(sudoku)) {
            return sudoku;
        } else {
            for(int i = 0; i < sudoku.length; i++) {
                for (int j = 0; j < sudoku[i].length; j++) {
                    if (sudoku[i][j] == 0) {
                        for (int x = 0; x < candidates.length; x++) {
                            int c = candidates[x];
                            if (isValid(c,i,j,sudoku)) {
                                sudoku[i][j] = i;
                            }
                            if (solve(sudoku) != null) {
                                return sudoku;
                            }
                            sudoku[i][j] = 0;
                        }
                    }
                }
            }
            return null;
        }
    }

Ich hoffe jemand kann mir helfen. Danke

 

[LimDul]

                                sudoku[i][j] = i;

Die Zeile ist falsch, da muss eine Zuweisung an den Kandidaten, also c stehen.

Kleiner Tipp: sprechendere Variablennamen verwenden.

Anstelle i/j rowIndex/colIndex z.B. und anstelle von c currentCandidate.

Grundsätzlich sind die hier schon um Längen besser was man sonst so im Forum sieht, aber aber sowas wie isValid(c,i,j,sudoku) ist schon nicht sehr sprechend mit 3 einbuchstabigen Variablen. Und eine Zeile:

                                sudoku[rowIndex][colIndex] = rowIndex;

der sieht man deutlich schneller beim lesen des Codes an, dass sie falsch ist.

 

[districon]

                                sudoku[i][j] = i;

Die Zeile ist falsch, da muss eine Zuweisung an den Kandidaten, also c stehen.

Kleiner Tipp: sprechendere Variablennamen verwenden.

Anstelle i/j rowIndex/colIndex z.B. und anstelle von c currentCandidate.

Grundsätzlich sind die hier schon um Längen besser was man sonst so im Forum sieht, aber aber sowas wie isValid(c,i,j,sudoku) ist schon nicht sehr sprechend mit 3 einbuchstabigen Variablen. Und eine Zeile:

                                sudoku[rowIndex][colIndex] = rowIndex;

der sieht man deutlich schneller beim lesen des Codes an, dass sie falsch ist.

Danke. Das hat aber noch nicht den Stackoverflow Error behoben, leider

 

[fhoffmann]

Du rufst in solve(sudoku) rekursiv solve(sudoku) auf, auch wenn du sudoku vorher nicht verändert hast; das führt zu der Unendlichschleife.

 

[districon]

Du rufst in solve(sudoku) rekursiv solve(sudoku) auf, auch wenn du sudoku vorher nicht verändert hast; das führt zu der Unendlichschleife.

Also darf ich das nur rekursiv aufrufen, wenn auch isValid true ist?

 

[LimDul]

Also darf ich das nur rekursiv aufrufen, wenn auch isValid true ist?

Ja, klar. Ansonsten hast du den gleichen Zustand wie vorher und machst immer das gleiche.

Zum Backtracking musst du auch einen Schritt gehen, ansonsten drehst du dich im Kreise.

 

[districon]

public int[][] solve(int[][] sudoku) {
        int[] candidates = {1,2,3,4,5,6,7,8,9};
        if (isFinal(sudoku)) {
            return sudoku;
        } else {
            for(int i = 0; i < sudoku.length; i++) {
                for (int j = 0; j < sudoku[i].length; j++) {
                    if (sudoku[i][j] == 0) {
                        for (int x = 0; x < candidates.length; x++) {
                            int c = candidates[x];
                            if (isValid(c,i,j,sudoku)) {
                                sudoku[i][j] = c;
                                if (solve(sudoku) != null) {
                                    return sudoku;
                                }
                            }
                            sudoku[i][j] = 0;
                        }
                    }
                }
            }
            return null;
        }
    }

Jetzt läuft es die ganze Zeit und bringt gar kein Ergebnis mehr, auch keine Exception

 

[ing0-bing0]

Musst nen paar Werte vorgeben.

 

[districon]

Musst nen paar Werte vorgeben.

int[][] sudoku = { {4,1,0,0,6,5,0,0,7},
            {0,0,6,0,0,7,4,8,0},
            {2,0,7,4,9,0,0,0,6},
            {0,6,0,0,7,0,1,0,0},
            {3,0,1,5,0,0,0,7,2},
            {0,9,0,0,4,2,3,0,8},
            {1,0,8,6,0,0,0,2,9},
            {0,2,0,0,1,8,6,4,0},
            {6,0,0,3,0,0,0,1,0},
    };

Diese Werte hab ich mal benutzt

 

[LimDul]

Zähl mal die Nullen. Sind, wenn ich mich nicht verzählt habe, 39.

Für jedes gibt es 9 Möglichkeiten. Ergo 9^39 Möglichkeiten. Also ungefähr 1,6 * 10^37.

Wenn du eine Millionen Sudokus pro Sekunde prüfen kannst, brauchst du 16423203268260658146231467800709 Sekunden bzw. 520776359343628175616167 Jahre bis ein Ergebnis kommt

 

[ing0-bing0]

Jap, Sudokus immer eingrenzen... Es gibt einfach zu viele Möglichkeiten. Nimm am besten ein fertiges Sudoku und entferne schrittweise nur 1 oder 2 Zahlen.

 

[MarvinsDepression]

Guten Morgen, zusammen.
Ich habe das aufgeführete Sudoku mal schnell mit einem ganz ähnlichen Programm (welches allerdings iterativ arbeitet) durchlaufen lassen. Es gibt nur eine gültige Lösung. Es brauchte gerade mal 720 Iterationen, um zu sie zu finden. Selbst ein sehr schwachbrüstiger Rechner sollte das mit Backtracking in sehr kurzer Zeit schaffen ;-) Mein Arduino Unu schafte es in deutlich unter einer Minute.

Zu LimDuls Kommentar möchte ich bemerken, dass die allermeisten Möglichkeiten gar nicht durchprobiert werden, da bei einel Fail zu Beginn ja der ganze folgende Baum (von links oben nach rechts unten) gar nicht mehr durchprobiert wird.

Wo jetzt allerdings der Fehler im Code von districon ist... ???
Mal schaun

 

[LimDul]

Guten Morgen, zusammen.
Ich habe das aufgeführete Sudoku mal schnell mit einem ganz ähnlichen Programm (welches allerdings iterativ arbeitet) durchlaufen lassen. Es gibt nur eine gültige Lösung. Es brauchte gerade mal 720 Iterationen, um zu sie zu finden. Selbst ein sehr schwachbrüstiger Rechner sollte das mit Backtracking in sehr kurzer Zeit schaffen ;-) Mein Arduino Unu schafte es in deutlich unter einer Minute.

Zu LimDuls Kommentar möchte ich bemerken, dass die allermeisten Möglichkeiten gar nicht durchprobiert werden, da bei einel Fail zu Beginn ja der ganze folgende Baum (von links oben nach rechts unten) gar nicht mehr durchprobiert wird.

Wo jetzt allerdings der Fehler im Code von districon ist... ???
Mal schaun

Stimmt, man muss nicht alles probieren. Aber ich würde mal vermuten, der iterative Algorithmus hat ein paar Optimierungen bzgl. der Auswahl der wahrscheinlichsten Kandidaten.

Ich glaube immer noch, dass reines stupides Backtracking einfach zu lange dauert. Gibt es einen Link zu dem von dir erwähnten Algorithmus?

 

[MarvinsDepression]

Nun ja, optimiert ist da eigentlich nicht viel. Statt einem rekursiven Aufruf habe ich einen eigen Stack eingebaut, in dem sich die Indizes der einzelnen Nullen des ursprünglichen Sudoku ansammeln um zu verhindern, dass beim Backtracking die gegeben Zahlen überschrieben werden.
Ansonsten habe ich das Array eindimensional angelegt, weil ich verschachtelte Schleifen fast genau so wenig mag, wie Rekursion.

[CODE lang="java" title="Backtracking iterativ"]private final int BOX = 3;
private final int SIZE = BOX * BOX; // = 9


private boolean solve(final int[] array) { // array.length = BOX * BOX = 81
solvedSudokuList.clear();
final var stack = new int[array.length];
int stackPointer = 0;

int index = 0;
boolean valueFound = true;
while (true) {
while (index < array.length) {
if (valueFound && array[index] != 0) {
index++;
continue;
}

for (int candidate = array[index] + 1; candidate <= SIZE; candidate++) {
valueFound = testCandidate(array, index, candidate);

if (valueFound) {
array[index] = candidate;
stack[stackPointer++] = index++;
break;
}
}

if (!valueFound) {
array[index] = 0;
if (stackPointer <= 0) return false; // no more solutions

index = stack[--stackPointer];
}
}
var grid = new int[array.length];
System.arraycopy(array, 0, grid, 0, array.length);
solvedSudokuList.add(grid);

valueFound = false;
index = stack[--stackPointer];
}
}

private boolean testCandidate(final int[] array, final int index, final int candidate) {
perm++;
int iCol = index % SIZE;
int iRow = index - iCol;
int iBox = iBOX[index];
for (int i = 0; i < SIZE; iRow++, iCol += SIZE, iBox++) {
if (array[iRow] == candidate) return false;
if (array[iCol] == candidate) return false;
if (array[iBox] == candidate) return false;
i++;
if (i % BOX == 0) {
iBox += SIZE - BOX;
}
}
return true;
}[/CODE]

Die einzigen Optimierungen sind die Verwendung der Konstanten BOX und SIZE in der Methode testCandidate() sowie ein kleines Array iBOX[], in welchem zu jedem Index der Startindex der dazugehörigen Box gespeichert ist.

 

[KonradN]

Vielleicht doch einmal meine Gedanken zu dieser Problematik:

Der Code ist extrem unübersichtlich. Ich würde hier immer zu klaren Unterteilungen in Methoden raten. Eine Methode sollte nie viele Einrückungen haben. Das ist also wirklich existenziell. Daher einfach einmal ein paar generelle Refactorings, die ich direkt anraten würde:

a) Du hast eine Klasse und die Methoden sind Instanzmethoden. Deine Instanz hat aber keinen Status? Das ist schon etwas, das so blöd ist. Also wollen wir das einfach einmal etwas ausgleichen:
- Du erzeugst ein 2D Array für das Sudoku als Instanzvariable. values oder so könnte ein Name sein.
- Dann machst D ein rename auf den Parameter so dass er values heisst und im Anschluss löscht du den Parameter.
- In allen Aufrufen löscht Du den Parameter values.
(Dann noch Konstruktor und ein Getter oder so)

Und dann hast du ein Array candidates - das ist doch schon ganz offensichtlich eine Konstante, denn dies ändert sich ja nie. Also wandert das auch entsprechend in die Klasse.

b) Dann ist solve eine Methode, die etwas macht und etwas zurück gibt. Das sollte nicht sein - daher einfach de Rückgabe ändern zu einem Erfolg / kein Erfolg (boolean).

Dann machst Du für jedes Feld etwas -> Das kann direkt in eine eigene Methode. Also solveField.

c) ein if mit einem return im if block braucht kein else mehr -> Eine Einrück-Ebene weniger.

d) Wen eine ganze Methode in einem if gekapselt ist, dann kann man das auch umdrehen: if (!Bedingung) return; - auch wieder eine Einrückebene weniger.

e) Gewisse Prüfungen mit magic numbers sollte man nicht stehen lassen. Etwas wie
if (values[i][j] != 0) return false;
ist schwer lesbar. Da also lieber ein:
if (values[i][j] != EMPTY_FIELD) return false;
oder ggf. sogar gleich eine Methode, so dass daraus wird:
if (!isFieldEmpty(i, j)) return false;
Dann ist der Lesefluss erst einmal gegeben.

Mit so Schritten bekommt man immer lesbareren Code und man kann Fehler ggf. direkt erkennen.

Dann bleibt am Ende nur noch das Testing. Da immer klein anfangen. Also einfach irgend ein Sudoku nehmen (vollständig gelöst) um das dann durchlaufen zu lassen.

Und dann kann man nach und nach einzelne Felder leer machen um dann zu schauen:
a) funktioniert es?
b) wie ist die Laufzeit?

Das Ganze kann dann z.B. so aussehen:

public class Sudoku {
    private static final int[] CANDIDATES = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    private static final int EMPTY_FIELD = 0;

    int[][] values;


    public Sudoku (int[][] values) {
        // TODO: Check Size of values!
        this.values = values.clone();
    }

    public boolean solve() {
        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values[i].length; j++) {
                if (solveField(i,j)) return true;
            }
        }

        return isFinal();
    }

    public boolean solveField(int i, int j) {
        if (values[i][j] != EMPTY_FIELD) return false;

        for (int x = 0; x < CANDIDATES.length; x++) {
            System.out.println("Try: " + i + ", " + j + " := " + (x+1));
            int c = CANDIDATES[x];
            if (isValid(c, i, j)) {
                values[i][j] = c;
                if (solve()) {
                    return true;
                }
            }
            values[i][j] = 0;
        }

        return false;
    }

    public boolean isFinal() {
        for(int i = 0; i < values.length; i++) {
            for (int j = 0; j < values[i].length; j++) {
                if (values[i][j] == 0) return false;
            }
        }
        return true;
    }

    public boolean isValid(int number, int row, int col) {
        for (int i = 0; i < values[row].length; i++) {
            if (values[row][i] == number) return false;
            if (values[i][col] == number) return false;
        }
        int r = row - row % 3;
        int c = col - col % 3;
        for (int x = r; x < r+3; x++) {
            for (int y = c; y < c+3; y++) {
                if (values[x][y] == number) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Sudoku sudoku = new Sudoku( new int[][] {
                { 2, 1, 9,   5, 4, 3,   6, 7, 8 } ,
                { 5, 4, 3,   8, 7, 6,   9, 1, 2 } ,
                { 0, 7, 6,   2, 1, 9,   3, 4, 5 } ,
//              { 8, 7, 6,   2, 1, 9,   3, 4, 5 } ,

                { 4, 3, 2,   7, 6, 5,   8, 9, 1 } ,
                { 7, 6, 5,   1, 9, 8,   2, 3, 4 } ,
                { 1, 9, 8,   4, 3, 2,   5, 6, 7 } ,

                { 3, 2, 1,   6, 5, 4,   7, 8, 9 } ,
                { 6, 5, 4,   9, 8, 7,   1, 2, 3 } ,
                { 0, 0, 7,   3, 2, 1,   4, 5, 6 }
//              { 9, 8, 7,   3, 2, 1,   4, 5, 6 }
        });
        System.out.println(sudoku.solve());
    }
}

Im Aufruf habe ich dann die Lösungszeile auch stehen gelassen, damit ich weiss, was da als Lösung heraus gekommen ist.

Da kann man dann nach und nach immer mehr Elemente löschen um dabei die Laufzeit zu beobachten. Und man erkennt auch: funktioniert der Algorithmus? Und natürlich kann man auch Ausgaben einbauen - was versucht er denn gerade?

Die Refactorings habe ich ansonsten abgebrochen um da nicht mehr Zeit zu investieren. Meine Empfehlung ist aber, dass man hier durchaus her geht und wirklich eine weitergehende Unterteilung macht. isValid würde ich noch etwas unterteilen. Und Validierungen fehlen mir noch etwas - es kann ja schon etwas nicht valides gegeben werden. Das Ergebnis soll aber auf jeden Fall valide sein.

Das einfach einmal von meiner Seite als kleine Anregung.