rekursives Sudoku will nicht

[JOat]

Hallo,

ich habe nachfolgenden code der ein Sudoku rekursiv lösen soll, leider funktioniert es nicht, als Ergebnis erhalte ich immer ein leeres Array in dem [1][1] mit 0 befüllt ist.

Als Vorlage/Vorgabe dient dieses Struktogramm (wobei hier auch ein Fehler drin sein könnte):


Wäre echt spitze wenn da mal jemand kurz drüber schaun könnte und mir evtl. einen Tipp geben kann.

$MemArr = array();

function MoeglichBlock($Spalte, $Zeile, $Ziffer)
{
    global $MemArr;
    
    $ZeileStart  = $Zeile  - (($Zeile-1)%3);
    $ZeileEnde   = $ZeileStart+2;
    $SpalteStart = $Spalte - (($Spalte-1)%3);    
    $SpalteEnde  = $SpalteStart+2;
    
    for($Z=$ZeileStart;$Z<=$ZeileEnde;$Z++) {
        for($S=$SpalteStart;$S<=$SpalteEnde;$S++) {
            if($MemArr[$Z][$S] == $Ziffer) {
                return false;
            }
        }
    }
    return true;
}


function MoeglichSpalte($Spalte, $Ziffer)
{
    global $MemArr;
    
    for($Zeile=1;$Zeile<=9;$Zeile++) {
        if($MemArr[$Zeile][$Spalte] == $Ziffer) {
            return false;
        }    
    }
    return true;
}

function MoeglichZeile($Zeile, $Ziffer)
{
    global $MemArr;    
    
    for($Spalte=1;$Spalte<=9;$Spalte++) {
        if($MemArr[$Zeile][$Spalte] == $Ziffer) {
            return false;
        }    
    }
    return true;
}

function Moeglich($Zeile, $Spalte, $Ziffer)
{
    global $MemArr;
    
    if (MoeglichZeile($Zeile, $Ziffer) &&
        MoeglichSpalte($Spalte, $Ziffer) &&
        MoeglichBlock($Spalte, $Zeile, $Ziffer)) {
        return true;
    }
    else {
        return false;
    }
}

function SudRek()
{
    global $MemArr;
    for($Zeile=1;$Zeile<=9;$Zeile++) {
        for($Spalte=1;$Spalte<=9;$Spalte++) {
            if($MemArr[$Zeile][$Spalte] == 0) {
                for($Ziffer=1;$Ziffer<=9;$Ziffer++) {
                    
                    if(Moeglich($Zeile, $Spalte, $Ziffer)) {
                        $MemArr[$Zeile][$Spalte] = $Ziffer;                    
                    }
                    
                    $Erg = SudRek();
                    if($Erg == true) {
                        return true;
                    }
                    else {                    
                        $MemArr[$Zeile][$Spalte] = 0;
                    }
                }
            }
            return false;    
        }    
    }
    return true;
} 

[wahsaga]

ich habe nachfolgenden code der ein Sudoku rekursiv lösen soll

Klassischer Anwendungsfall für einen Backtracking-Algorithmus.

Wäre echt spitze wenn da mal jemand kurz drüber schaun könnte und mir evtl. einen Tipp geben kann.

Tipp: Betreibe Debugging. (Nachdem du dich erst mal an Hand eines Beispiels vom grundsätzlichen Funktionieren des Algorithmus überzeugt hast.)

[JOat]

Klassischer Anwendungsfall für einen Backtracking-Algorithmus.

Danke, aber das weiß ich auch

Tipp: Betreibe Debugging. (Nachdem du dich erst mal an Hand eines Beispiels vom grundsätzlichen Funktionieren des Algorithmus überzeugt hast.)

Das habe ich die letzten paar Stunden schon gemacht, nur weiß ich nichtmal ob es ein PHP-Technisches Problem ist (hab seit mind. 3 Jahre keine PHP mehr gemacht) .... die Sache mit global z.B. war mir komplett unbekannt...

[AmicaNoctis]

Danke, aber das weiß ich auch

Bis auf Spezialfälle (versteckte Zwillinge und Drillinge) ist ein Sudoku-Solver komplett Backtracing-frei und rein kombinatorisch lösbar (Ausschlussverfahren).

Backtracing braucht man dabei nur in 10 bis 20% der Fälle, wenn man nur "schwere" Rätsel hat, vielleicht auch mehr. Es aber von vornherein damit zu machen, halte ich für zu ressourcenaufwändig.

Gruß,

Amica

[combie]

die Sache mit global z.B. war mir komplett unbekannt

Vergiss das auch am besten sofort wieder.
Globale Variablen sind eine übel riechende Zutat in des Teufels Küche.