rekursives Sudoku will nicht

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.

PHP-Code:

$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;
} 


Zitat von JOat

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.)

Zitat von wahsaga

Klassischer Anwendungsfall für einen Backtracking-Algorithmus.

Danke, aber das weiß ich auch

Zitat von wahsaga

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...

Zitat von JOat

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

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.