Sudoku



  • Hi,

    es geht um ein Programm, mit dem man beliebige Sudokus lösen kann. Ich gehe davon aus das die meisten wissen, was ein Sudoku ist.

    Das Programm ist fertig und ich muss nurnoch die Funktion "int loese_sudoku" hinzufügen. Da komme ich im Moment nicht mit dem rekursiven Aufruf zurecht. Es kommt was raus, was aber nicht vollständig ist. Also irgendwas stimmt mit der Schleife nicht.

    Ich wäre sehr dankbar, wenn mir da jemand nen Tip geben könnte.

    Dominik

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define BS 9    /* "Dimension" des Sudokus, Standard ist 9                */
    #define B  3    /* "Dimension" eines Quadranten ("Unterquadrat")          */
                    /*  typischerweise Wurzel aus BS                          */
    
    /* Diese Funktion prueft, ob ein "Feld" des Sudokus bereits belegt ist .. */
    /* Gibt 1 zurueck, fall ja, 0 sonst                                       */
    
    int ist_belegt( int i, int j, int b[BS][BS] )
    {
      if ( b[i][j] ) return 1; else return 0;
    }
    
    /* Diese Funktion prueft, ob es erlaubt ist, die Zahl z in das "Feld" mit */
    /* den Koordinaten (i,j), d.h. (i-te Zeile / j-te Spalte) zu schreiben    */
    /* Gibt 1 zurueck, falls ja, 0 sonst                                       */
    
    int ist_erlaubt( int z, int i, int j, int b[BS][BS] )
    {
      int k,l;
      int mini, maxi;
      int minj, maxj;
    
      /* Gibt es z schon in Zeile i  ?                                        */
    
      for (l=0; l<BS; l++)
        {
          if ( b[i][l] == z ) return 0;
        }
    
      /* Gibt es z schon in Spalte j ?                                        */
    
        for (k=0; k<BS; k++)
        {
          if ( b[k][j] == z ) return 0;
        }
    
      /* Gibt es z schon im Quadranten, in dem die Koordinate (i,j) liegt ?   */
    
        mini=(i/3)*3;
        maxi=mini+2;
        minj=(j/3)*3;
        maxj=minj+2;
    
        for (k=mini; k<=maxi; k++)
          {
    	for (l=minj; l<=maxj; l++)
    	  {
    	    if (b[k][l] == z) return 0;
    	  }
          }
    
        return 1;
    }
    
    /* Diese Funktion gibt das im Array b gespeicherte Sudoku bzw.
       die Zwischenloesung des Sudokus formschoen auf dem Bildschrim aus      */
    
    void gib_sudoku_aus( int b[BS][BS] )
    {
      int i,j;
    
      printf("    ");
      for (i=0; i<BS; i++)
        {
          printf("+");
          for (j=0; j<BS; j++)
    	{
    	  printf("---");
    	  printf("+");
    	}
          printf("\n    ");
          printf("|");
          for (j=0; j<BS; j++)
    	{
    	  if (b[i][j]!=0)
    	    {
    	      printf(" %i ", b[i][j] );
    	    }
    	  else
    	    {
    	      printf("   ");
    	    }
    	  printf("|");
    	}
          printf("\n    ");
        }
    
      printf("+");
      for (j=0; j<BS; j++)
        {
          printf("---+");
        }
    
      printf("\n\n\n\n\n");
    
    }
    
    /* Diese Funktion sucht die naechste freie Stelle im Sudoko (bzw. in der Zwischenloesung),
       welches im Array b gespeichert ist.
       Hierbei geht die Funktion zeilenweise vor.
       Der Funktion werden Zeiger auf die aktuelle Zeile i und die aktuelle Spalte j uebergeben.
       Nach Aufruf der Funktion enthalten i und j die Koordinaten des naechsten freien Feldes
       im Sudoku.
       Diese Funktion arbeitet mit Pointern, damit die Aenderungen der Parameter i und j
       fuer die aufrufende Funktion "sichtbar" sind.
       Beim Aufruf der Funktion daher unbedingt auf die Adressoperatoren ("&") achten!
       Vgl. dazu den Aufruf in der main()-Funktion !
       Diese Funktion liefert 1 zurueck falls es keine freien Stellen mehr gibt,
       ansonsten liefert die Funktion 0 zurueck                                                   */
    
    int suche_naechste_freie_stelle(int *i, int *j, int b[BS][BS] )
    {
      while( ist_belegt( *i,*j, b ) )
        {
          if (*j<BS-1) (*j)++;
          else
    	{
    	  (*i)++; *j=0;
    	  if (*i==BS) return 1;
    	}
        }
      return 0;
    }
    
    /* Diese Funktion muessen Sie noch ergaenzen.
       Analog zu dem von Ihnen entworfenen Algorithmus sollte diese Funktion rekursiv sein
       (d.h. an einer Stelle ruft loese_sudoku sich selbst auf)
       Sie duerfen (und sollten auch) fuer die Implementierung alle oben definierten Funktionen
       verwenden ....
       Diese Funktion liefert als Rueckgabewert 1, wenn alle Felder erfolgreich belegt worden sind
       (d.h. es gibt keine freien Felder mehr)
       Ansonsten liefert die Funktion 0 zurueck.                                                  */
    
    int loese_sudoku(int i, int j, int b[BS][BS] ){
    
        int z;
        for(z=1;z<=9;z++){;
                if (ist_erlaubt(z,i,j,b)){
                    b[i][j]=z;
                    suche_naechste_freie_stelle( &i, &j,b);
                    loese_sudoku(i,j,b);
    
                }
            else b[i][j]=0;
            }
    
    }
    
    int main(void)
    {
    
      int sudoku[BS][BS] =
        {
          { 0,0,1,6,0,0,0,0,0 },
          { 0,2,0,0,0,0,4,0,0 },
          { 0,0,8,0,9,0,0,1,0 },
          { 0,9,0,0,2,0,0,0,0 },
          { 3,0,0,0,8,9,6,0,0 },
          { 7,0,2,0,0,0,0,0,4 },
          { 6,0,0,5,0,0,8,0,3 },
          { 0,0,0,0,0,4,0,6,0 },
          { 0,0,9,8,7,0,0,0,0 }
        };
    
      int i,j;
      char c;
    
      printf("\n\n");
      printf("Sudoku-Loeser V1.0 (Backtracking) \n");
      printf("==================================\n\n\n");
    
      printf("Folgendes Sudoku soll geloest werden: \n\n\n");
    
      gib_sudoku_aus( sudoku );
    
      printf("Bitte geben Sie nun irgend ein Zeichen ein, um fortzufahren ! :");
    
      c=getchar();
    
      printf("\n\n");
    
      i=0; j=0;
    
      /* erstes freies Feld im Sudoku-Raetsel suchen ... */
    
      suche_naechste_freie_stelle( &i, &j, sudoku);
    
      loese_sudoku(i, j, sudoku );
    
      printf("Das Sudoku hat folgende Loesung: \n\n");
    
      gib_sudoku_aus(sudoku);
    
      return 0;
    }
    


  • Der Kommentar zur loese_sudoku() erzählt zwar etwas von Rückgabewerten (genauso wie das int davor), aber irgendwie vermisse ich da die return-Anweisung.



  • Hallo Dominik,

    du solltest deine Programme schon selber schreiben, wenn du die Zulassung zur Klausur erhalten möchtest. Außerdem ist das hilfreich, wenn man dann am Ende an der Klausur teil nimmt. Für Fragen könntest du z.B. eine der angebotenen Übungsgruppen besuchen. Außerdem solltest du vielleicht berücksichtigen, dass du nicht einfach den Copyright-Hinweis aus einem Programm entfernen solltest, um es dann ins Internet zu stellen.



  • Die Funktion suche_naechste_freie_stelle() greift nirgends auf das Feld b zu. Woher weiß dann die Funktion, dass das Feld frei ist?

    Dein gib_sudoku_aus() sieht ein bisschen ..äh.. grauselig aus.
    Hast du die aus Pascal portiert?



  • Richtig, das mit dem Hinweis. Aber wenn ich irgendwo nicht mehr weiter komme, muss ich mir schon einen Tip abholen dürfen. Ich habe ja die Funktion nicht leer gelassen und nichts probiert.



  • psigh schrieb:

    Richtig, das mit dem Hinweis. Aber wenn ich irgendwo nicht mehr weiter komme, muss ich mir schon einen Tip abholen dürfen. Ich habe ja die Funktion nicht leer gelassen und nichts probiert.

    Du könntest ja mal in deiner Übung erscheinen 😉

    Du willst ja die Backtracking-Variante lösen:

    Du solltest also beim zurück gehen in der Rekursion auch den Ursprünglichen Zustand im Feld wieder herstellen...



  • Ich habe super wenig Zeit, weil ich auch gerade Diplomarbeit schreibe und bin 100% nicht der Typ, der sagt: "Ich will ein Proframm schreiben, habe keinen Plan, macht mal".
    Das würde ja in einem Forum auch sowieso nicht akzeptiert. Ich probiere wirklich die ganze Zeit rum und versuche die Sachen alleine hinzubekommen. Und ich bin froh das ich in einem Zeitalter lebe, wo man sich via Internet weiterbilden kann und nicht für jede Minifrage mit dem Bus in die Uni fahren muss.



  • psigh schrieb:

    Das Programm ist fertig und ich muss nurnoch die Funktion "int loese_sudoku" hinzufügen.

    Der war gut. Insbesondere das "nur noch".



  • ProgChild schrieb:

    psigh schrieb:

    Richtig, das mit dem Hinweis. Aber wenn ich irgendwo nicht mehr weiter komme, muss ich mir schon einen Tip abholen dürfen. Ich habe ja die Funktion nicht leer gelassen und nichts probiert.

    Du könntest ja mal in deiner Übung erscheinen 😉

    Du willst ja die Backtracking-Variante lösen:

    Du solltest also beim zurück gehen in der Rekursion auch den Ursprünglichen Zustand im Feld wieder herstellen...

    Und vielen Dank für den Tip.



  • psigh schrieb:

    for(z=1;z<=9;z++){;
                          ^ was soll das denn?
    

    Du wertest den so mühsam ermittelten Rückgabewert aus suche_naechste_freie_stelle gar nicht aus!
    Du brauchst noch eine Funktionalität zum Zurücknehmen eines Versuches.



  • Und erwähnt wurde ja schon: Rückgabewert von suche_naechste_freie_stelle auswerten. Und die Funktion mal nicht hinter der ist_erlaubt Abfrage verstecken.



  • Das Programm ist fertig und ich muss nurnoch die Funktion "int loese_sudoku" hinzufügen.

    Das Programm ist nicht fertig, wenn der Hauptteil fehlt!

    Da komme ich im Moment nicht mit dem rekursiven Aufruf zurecht. Es kommt was raus, was aber nicht vollständig ist. Also irgendwas stimmt mit der Schleife nicht.

    Tolle Fehlerbeschreibung.



  • Also. Endlich klappts:

    /*********************************************/
    /*                                           */
    /*  Datei:  sudoku_backtracking.c            */
    /*  Autor:  Peter Langer                     */
    /*  Datum:  20/04/2006                       */
    /*  Zweck:  Rahmenprogramm fuer die          */
    /*          Implementierung des              */
    /*          Backtracking-Algorithmus         */
    /*          zur Loesung von Sudokus          */
    /*          (Uebungsblatt 4, Aufgabe 2)      */
    /*  Status: unvollstaendig, d.h. die         */
    /*          Funktion loese_sudoku            */
    /*          muss noch sinnvoll ergaenzt      */
    /*          werden.                          */
    /*                                           */
    /*********************************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define BS 9    /* "Dimension" des Sudokus, Standard ist 9                */
    #define B  3    /* "Dimension" eines Quadranten ("Unterquadrat")          */
                    /*  typischerweise Wurzel aus BS                          */
    
    /* Diese Funktion prueft, ob ein "Feld" des Sudokus bereits belegt ist .. */
    /* Gibt 1 zurueck, fall ja, 0 sonst                                       */
    
    int ist_belegt( int i, int j, int b[BS][BS] )
    {
      if ( b[i][j] ) return 1; else return 0;
    }
    
    /* Diese Funktion prueft, ob es erlaubt ist, die Zahl z in das "Feld" mit */
    /* den Koordinaten (i,j), d.h. (i-te Zeile / j-te Spalte) zu schreiben    */
    /* Gibt 1 zurueck, falls ja, 0 sonst                                       */
    
    int ist_erlaubt( int z, int i, int j, int b[BS][BS] )
    {
      int k,l;
      int mini, maxi;
      int minj, maxj;
    
      /* Gibt es z schon in Zeile i  ?                                        */
    
      for (l=0; l<BS; l++)
        {
          if ( b[i][l] == z ) return 0;
        }
    
      /* Gibt es z schon in Spalte j ?                                        */
    
        for (k=0; k<BS; k++)
        {
          if ( b[k][j] == z ) return 0;
        }
    
      /* Gibt es z schon im Quadranten, in dem die Koordinate (i,j) liegt ?   */
    
        mini=(i/3)*3;
        maxi=mini+2;
        minj=(j/3)*3;
        maxj=minj+2;
    
        for (k=mini; k<=maxi; k++)
          {
    	for (l=minj; l<=maxj; l++)
    	  {
    	    if (b[k][l] == z) return 0;
    	  }
          }
    
        return 1;
    }
    
    /* Diese Funktion gibt das im Array b gespeicherte Sudoku bzw.
       die Zwischenloesung des Sudokus formschoen auf dem Bildschrim aus      */
    
    void gib_sudoku_aus( int b[BS][BS] )
    {
      int i,j;
    
      printf("    ");
      for (i=0; i<BS; i++)
        {
          printf("+");
          for (j=0; j<BS; j++)
    	{
    	  printf("---");
    	  printf("+");
    	}
          printf("\n    ");
          printf("|");
          for (j=0; j<BS; j++)
    	{
    	  if (b[i][j]!=0)
    	    {
    	      printf(" %i ", b[i][j] );
    	    }
    	  else
    	    {
    	      printf("   ");
    	    }
    	  printf("|");
    	}
          printf("\n    ");
        }
    
      printf("+");
      for (j=0; j<BS; j++)
        {
          printf("---+");
        }
    
      printf("\n\n\n\n\n");
    
    }
    
    /* Diese Funktion sucht die naechste freie Stelle im Sudoko (bzw. in der Zwischenloesung),
       welches im Array b gespeichert ist.
       Hierbei geht die Funktion zeilenweise vor.
       Der Funktion werden Zeiger auf die aktuelle Zeile i und die aktuelle Spalte j uebergeben.
       Nach Aufruf der Funktion enthalten i und j die Koordinaten des naechsten freien Feldes
       im Sudoku.
       Diese Funktion arbeitet mit Pointern, damit die Aenderungen der Parameter i und j
       fuer die aufrufende Funktion "sichtbar" sind.
       Beim Aufruf der Funktion daher unbedingt auf die Adressoperatoren ("&") achten!
       Vgl. dazu den Aufruf in der main()-Funktion !
       Diese Funktion liefert 1 zurueck falls es keine freien Stellen mehr gibt,
       ansonsten liefert die Funktion 0 zurueck                                                   */
    
    int suche_naechste_freie_stelle(int *i, int *j, int b[BS][BS] )
    {
      while( ist_belegt( *i,*j, b ) )
        {
          if (*j<BS-1) (*j)++;
          else
    	{
    	  (*i)++; *j=0;
    	  if (*i==BS) return 1;
    	}
        }
      return 0;
    }
    
    /* Diese Funktion muessen Sie noch ergaenzen.
       Analog zu dem von Ihnen entworfenen Algorithmus sollte diese Funktion rekursiv sein
       (d.h. an einer Stelle ruft loese_sudoku sich selbst auf)
       Sie duerfen (und sollten auch) fuer die Implementierung alle oben definierten Funktionen
       verwenden ....
       Diese Funktion liefert als Rueckgabewert 1, wenn alle Felder erfolgreich belegt worden sind
       (d.h. es gibt keine freien Felder mehr)
       Ansonsten liefert die Funktion 0 zurueck.                                                  */
    
    int loese_sudoku(int i, int j, int b[BS][BS] ){
    
        int z;
        for(z=1;z<=9;z++){
            if (ist_erlaubt(z,i,j,b)){
                b[i][j]=z;
                int i2 = i, j2=j;
                if(suche_naechste_freie_stelle( &i2, &j2,b)){
                    return 1;
                }
                if(loese_sudoku(i2,j2,b)){
                return 1;}
            }
        }
        b[i][j] = 0;
        return 0;
    }
    
    int main(void)
    {
    
      /* Beispiel 1 : */
    
      /*
      int sudoku[BS][BS] =
        {
          { 3,0,9,0,7,0,0,0,1 },
          { 0,0,6,0,1,0,0,0,0 },
          { 0,0,0,0,0,5,0,4,9 },
          { 0,0,1,0,0,0,0,0,0 },
          { 4,2,0,0,0,0,0,9,8 },
          { 0,0,0,0,0,0,2,0,0 },
          { 6,8,0,2,0,0,0,0,0 },
          { 0,0,0,0,9,0,1,0,0 },
          { 1,0,0,0,6,0,3,0,7 }
        };
      */
    
      /* Beispiel 2 : Leichtes Sudoku zum Aufwaermen, entnommen aus der "Welt am Sonntag :        */
    
      /*
      int sudoku[BS][BS] =
        {
          { 0,8,5,3,0,2,1,4,0 },
          { 6,0,0,4,0,9,0,0,7 },
          { 3,0,4,0,0,0,9,0,2 },
          { 5,4,0,0,1,0,0,6,3 },
          { 0,0,0,6,0,8,0,0,0 },
          { 8,6,0,0,5,0,0,2,1 },
          { 1,0,8,0,0,0,3,0,4 },
          { 4,0,0,1,0,5,0,0,8 },
          { 0,2,3,8,0,4,6,1,0 }
        };
      */
    
      /* Beispiel 3 : Mittel-schweres Sudoku entnommen aus der "Welt am Sonntag :                 */
    
      /*
      int sudoku[BS][BS] =
        {
          { 0,3,0,7,1,5,0,9,0 },
          { 7,0,0,8,0,9,0,0,1 },
          { 0,0,0,0,6,0,0,0,0 },
          { 4,6,0,0,0,0,0,5,9 },
          { 8,0,3,0,0,0,7,0,6 },
          { 9,7,0,0,0,0,0,3,4 },
          { 0,0,0,0,9,0,0,0,0 },
          { 5,0,0,4,0,1,0,0,3 },
          { 0,0,0,5,2,3,0,4,0 }
        };
      */
    
      /* Beispiel 4 : Sehr schweres Sudoku ("Sudoku extrem"), entnommen aus einem Raetselheft :   */
      /*              Dies ist das auf dem Uebungsblatt abgedruckte Sudoku ...                    */
    
      int sudoku[BS][BS] =
        {
          { 0,0,1,6,0,0,0,0,0 },
          { 0,2,0,0,0,0,4,0,0 },
          { 0,0,8,0,9,0,0,1,0 },
          { 0,9,0,0,2,0,0,0,0 },
          { 3,0,0,0,8,9,6,0,0 },
          { 7,0,2,0,0,0,0,0,4 },
          { 6,0,0,5,0,0,8,0,3 },
          { 0,0,0,0,0,4,0,6,0 },
          { 0,0,9,8,7,0,0,0,0 }
        };
    
      int i,j;
      char c;
    
      printf("\n\n");
      printf("Sudoku-Loeser V1.0 (Backtracking) \n");
      printf("==================================\n\n\n");
    
      printf("Folgendes Sudoku soll geloest werden: \n\n\n");
    
      gib_sudoku_aus( sudoku );
    
      printf("Bitte geben Sie nun irgend ein Zeichen ein, um fortzufahren ! :");
    
      c=getchar();
    
      printf("\n\n");
    
      i=0; j=0;
    
      /* erstes freies Feld im Sudoku-Raetsel suchen ... */
    
      suche_naechste_freie_stelle( &i, &j, sudoku);
    
      loese_sudoku(i, j, sudoku );
    
      printf("Das Sudoku hat folgende Loesung: \n\n");
    
      gib_sudoku_aus(sudoku);
    
      return 0;
    }
    

    Danke für die Hilfe



  • Wenn ich ein unlösbares (falsches) Sudoku eingebe, wird trotzdem irgend eine (falsche) Lösung berechnet...
    da gehört noch was gemacht 😃


Log in to reply