rekursives Sudoku will nicht

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • 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;

    the end comes faster than you think - you've already reached it!

  • #2
    Zitat von JOat Beitrag anzeigen
    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.)
    I don't believe in rebirth. Actually, I never did in my whole lives.

    Kommentar


    • #3
      Zitat von wahsaga Beitrag anzeigen
      Klassischer Anwendungsfall für einen Backtracking-Algorithmus.
      Danke, aber das weiß ich auch

      Zitat von wahsaga Beitrag anzeigen
      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...
      the end comes faster than you think - you've already reached it!

      Kommentar


      • #4
        Zitat von JOat Beitrag anzeigen
        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
        [COLOR="DarkSlateGray"]Hast du die [COLOR="DarkSlateGray"]Grundlagen zur Fehlersuche[/color] gelesen? Hast du Code-Tags benutzt?
        Hast du als URL oder Domain-Beispiele example.com, example.net oder example.org benutzt?
        Super, danke!
        [/COLOR]

        Kommentar


        • #5
          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.
          Wir werden alle sterben

          Kommentar

          Lädt...
          X