php easy Sudoku Löser mit Backtracking

Question

Ich wollte vor kurzem sehen, ob ich in der Lage, ein einfaches Sudoku (zuerst) in PHP zu lösen. Ich weiß, PHP ist nicht wirklich die Wahl aus Programmiergründen, aber ich kenne PHP am besten und ich hatte Probleme mit dem Design in Java und c. Trotzdem sehe ich keinen Grund, warum es nicht funktionieren sollte.

Zuerst wollte ich dich nicht fragen, weil da draußen einige gelöste Threads waren. Aber ich fand heraus, dass diese Lösungen zu kompliziert für mich sind, um sie zu verstehen (andere Sprachen, komplexe Strukturen) und außerhalb meines Ziels.

Meine Frage ist: Kann mir jemand einen Hinweis auf mein Ziel geben? Ich möchte einen einfachen Sudoku-Löser ohne zu raten, nur mit Backtracking.

Der Algorithmus sieht wie folgt aus: Fatal error:

$cell; // 1-81 - as parameter of the recursive function solve() 
$value; // 1-9 - as parameter ... 

class Sudoku { 

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

    // skipping values 

    if the current cell is fix: 

     return solve(cell++, $value); 

    // testing values (logic) 

    if not: 

     if the value is within the square (3x3) itself: 

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

     if the value is within the row: 

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

     if the value is within the col: 

      return solve($cell, value++); 

     if the value is bigger than 9: 

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

     // all test passed, add the new value to list 
     $this->values[$cell] = $value; 

     if all fields are filled: 
      return; 

     if there are fields left: 
      return solve($cell++, 1); 
} 
} 

Wenn ich ein leeres Sudoku erstellen wird alles korrekt, bis Zelle 43. Dort wird das Skript stürzt mit einem fatalen Fehler füllen erlaubt Speichergröße von 134.217.728 Bytes erschöpft (versucht, 261904 Bytes zuzuordnen).

Die Werte werden in ähnlichem gefüllt:

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 denke, es gibt eine Endlosschleife oder etwas, das diesen Absturz verursacht. Vielleicht ist es so nicht lösbar. Ich wollte nur wissen, ob ich richtig handle oder was ich vergessen habe zu überprüfen. Ich habe diesen Algorithmus auch mit festen Werten aus einem einfachen Sudoku probiert. Es stürzt auch ab ... vielleicht gibt es zu viel Backtracking.

Schließlich möchte ich sagen, dass ich nicht gegen bessere Lösungen bin, aber ich will nur, dass das funktioniert. Wenn Sie nicht mir eine Antwort geben kann auf dieser Basis Sie einen Blick auf die PHP-Datei haben:

sudoku.php

Edit: sudoku2.php

Vielen Dank im Voraus.

Answer 1

Das Hauptproblem ist:

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

Wenn Sie zu diesem Punkt (wo nichts funktioniert, so dass Sie gehen müssen zurück und vorher etwas ändern), können Sie nicht tiefer Rekursion, wie Sie sind, weil dein Stack viel zu groß wird mit häufigen Fehlern. Sie müssen tatsächlich zum vorherigen Stack-Level zurückkehren und von dort weitermachen.

z. Sie könnten solve zurückgeben TRUE, wenn es abgeschlossen ist, oder FALSE, wenn es keine Optionen mehr. Wenn Sie dann solve rekursiv aufrufen, geben Sie TRUE zurück, wenn TRUE zurückgegeben wird, und wenn es FALSE zurückgibt, rufen Sie es erneut mit $value++ auf.