Php einfacher Sudoku-Löser mit Backtracking

Question

Ich wollte kürzlich sehen, ob ich in der Lage bin, ein einfaches Sudoku (zunächst) innerhalb von PHP zu lösen. Ich weiß, dass PHP nicht wirklich die beste Wahl aus programmatischen Gründen ist, aber ich kenne PHP am besten und hatte Probleme mit dem Design in Java und C. Dennoch sehe ich keinen Grund, warum es nicht funktionieren sollte.

Zuerst wollte ich nicht fragen, da es einige gelöste Threads gab. Aber ich fand heraus, dass diese Lösungen für mich zu kompliziert sind (andere Sprachen, komplexe Strukturen) und außerhalb meiner Zielsetzung liegen.

Meine Frage lautet: Kann mir jemand einen Tipp geben, der auf mein Ziel basiert? Ich möchte einen einfachen Sudoku-Löser ohne Raten haben, nur mit Backtracking.

Der Algorithmus sieht wie folgt aus:

$cell;  // 1-81 - als Parameter der rekursiven Funktion solve()
$value; // 1-9  - als Parameter ...

class Sudoku {

function solve($cell = 1, $value = 1) {

    // Überspringen von Werten

    if die aktuelle Zelle festgelegt ist:

        return solve(cell++, $value);

    // Testen der Werte (Logik)

    if nicht:

        if der Wert innerhalb des Quadrats (3x3) selbst liegt:

            return solve($cell, $value++);

        if der Wert innerhalb der Zeile liegt:

            return solve($cell, $value++);

        if der Wert innerhalb der Spalte liegt:

            return solve($cell, value++);

        if der Wert größer als 9 ist:

            return solve($cell--, $value_prev);

        // Alle Tests bestanden, füge den neuen Wert der Liste hinzu
        $this->values[$cell] = $value;

        if alle Felder gefüllt sind:
            return;

        if noch Felder übrig sind:
            return solve($cell++, 1);
}
}

Wenn ich ein leeres Sudoku erstelle, wird es alles korrekt bis Zelle 43 ausfüllen. Dort stürzt das Skript mit einem schwerwiegenden Fehler ab: Tödlicher Fehler: Erlaubter Speicherplatz von 134217728 Bytes erschöpft (versuchte 261904 Bytes zu zuweisen).

Die Werte sind wie folgt eingetragen:

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
2 1 4 | 3 6 5 | 8 9 7
3 6 5 | 2 1 4 | . . .

Ich vermute, es gibt eine Endlosschleife oder etwas, das diesen Absturz verursacht. Vielleicht ist es auf diese Weise nicht lösbar. Ich wollte nur wissen, ob ich alles richtig mache oder was ich vergessen habe zu überprüfen. Ich habe diesen Algorithmus auch mit festen Werten aus einem einfachen Sudoku ausprobiert. Es stürzt auch ab ... vielleicht gibt es zu viel Backtracking.

Zuletzt möchte ich sagen, dass ich nicht gegen bessere Lösungen bin, aber ich will einfach, dass es funktioniert. Wenn Sie mir keine Antwort auf Basis dessen geben können, können Sie sich die PHP-Datei ansehen:

sudoku.php

Bearbeiten: sudoku2.php

Vielen Dank im Voraus.

Answer 1

Dies ist Ihr Hauptproblem:

if the value is bigger than 9:
    return solve($cell--, $value_prev);

Wenn Sie an diesem Punkt angelangt sind (wo nichts funktioniert, sodass Sie zurückgehen und etwas zuvor ändern müssen), können Sie nicht tiefer rekursiv vorgehen, da sich Ihr Stapelspeicher mit der Ansammlung von Fehlern zu stark ausweiten würde. Sie müssen tatsächlich zum vorherigen Stapelspeicherlevel zurückkehren und von dort aus weitermachen.

Zum Beispiel können Sie solve dazu bringen, TRUE zurückzugeben, wenn es abgeschlossen ist, oder FALSE, wenn es keine weiteren Optionen mehr gab. Dann, jedes Mal, wenn Sie solve rekursiv aufrufen, wenn es TRUE zurückgibt, geben Sie TRUE zurück, und wenn es FALSE zurückgibt, rufen Sie es erneut mit $value++ auf.