4. Sudoku Solver mit Backtracking

Sudoku Solver mit Backtracking

  • P

    Hallo,

    ich bin, was Backtracking/Rekursion angeht, nicht auf der Höhe und stecke in einer
    Sackgasse.

    Ich möchte ein Sudoku (bzw. globales Array) lösen, dann ausgeben.
    Die Schnittstellen sind fest vorgegeben.

    hier nun mein Code:

    /*
 *      return 0 <=> erfolgreich
 *      return 1 <=> fehler
 */

#include <stdio.h>

//prototypes
int finde_freies_feld(int *, int *);
int teste_zahl(int, int, int);
void ausgabe();
void loes();

//global vars
int a[9][9]={   {9,0,0, 3,0,0, 0,0,6},
                {0,8,0, 0,0,0, 0,0,7},
                {0,0,5, 2,0,8, 9,0,0},

                {0,0,8, 0,0,4, 0,7,3},
                {0,9,0, 0,0,0, 0,4,0},
                {7,6,0, 1,0,0, 2,0,0},

                {0,0,7, 1,0,0, 2,0,0},
                {1,0,0, 0,0,0, 0,5,0},
                {8,0,0, 0,0,9, 0,0,1}};

int main(){
        loes();
        return 0;
}

int finde_freies_feld(int *z, int *s){
        return (a[*z][*s]==0)?0:1;
}

int teste_zahl(int z, int s, int zahl){
        int i,j;
        for(i=0;i<3;i++) //pruefe 3x3 quadrant
                for(j=0;j<3;j++)
                        return (zahl!=a[i+3*(z/3)][j+3*(s/3)])?0:1;//pruefe das 3x3 feld
        for(i=0;i<9;i++) //pruefe zeile
                return (zahl!=a[i][s])?0:1;
        for(j=0;j<9;j++) //pruefe spalte
                return (zahl!=a[z][j])?0:1;
        return 1;
}

void loes(){
        int i=0,z,s,null=0;
        while(i<81){
                z=&(a[i/9][0]);
                s=&(a[0][i%9]);
                null+=finde_freies_feld(z,s)
        }
        i=1;
        while(i<10 && 1-teste_zahl(*z,*s,i))
                ++i;
        a[*z][*s]=i;

}

void ausgabe(){
        int i,j;
        system("clear");
        printf("geloestes Sudoku:\n");
        for(i=0;i<9;i++){
                (i%3==0)?printf("\n\n"):printf("\n");
                for(j=0;j<9;j++){
                        (j%3==0)?printf(" "):0;
                        printf("%d",a[i][j]);
                }
        }
        printf("\n\n");
}

    Bin für jegliche Tipps dankbar 👍

    gruss

    0
  • M

    Hallo,
    Du hast vergessen eine Frage zu stellen, bzw. dein Problem zu schildern.
    Könnte helfen, wenn man Antworten erwartet.

    0
  • M

    Folgendes geht so schon mal nicht. Du setzt null auf 0 und betrittst die while-Schleife nur wenn null ungleich 0 ist (also nie).

    void loes(){
        int i=0,z,s,null=0;
        while(i<81 && null!=0){
    0
  • P

    MiP schrieb:

    Folgendes geht so schon mal nicht. Du setzt null auf 0 und betrittst die while-Schleife nur wenn null ungleich 0 ist (also nie).

    void loes(){
        int i=0,z,s,null=0;
        while(i<81 && null!=0){

    oops das stimmt natürlich.

    die Frage ist: Wie verknüpfe ich die Funktionen, damit ich das Sudoku gelöst bekomme (bzw. ausgegeben)?

    0
  • P

    sum berechnet mir ob das feld voll ist, da 405=(1+2+3+4+5+6+7+8+9)*9

    0
  • P

    Hallo,

    ich habe nun parallel versucht das Programm von hier:
    http://newsgroups.derkeiler.com/Archive/De/de.sci.informatik.misc/2006-01/msg00012.html

    in ein Struktogramm zu wandeln, dass ich dann in C kodieren kann.

    aber komme nicht auf die richtige lösung... 😕

    0
  • M

    Ich werde aus deinen oben geposteten Funktionen nicht so ganz schlau.

    Das Prinzip von Backtracking ist ja erstmal: Wenn du nicht mehr weiter weißt, rate den nächsten Schritt und versuche damit weiterzukommen. Wenn du dann mitkriegst, dass du in eine Sackgasse gelaufen bist, mache alle Schritte rückgängig und rate an der letzten Stelle erneut.

    Für ein Sudoku kann man das nun folgendermaßen adaptieren:
    - Suche nächstes ungesetztes Feld
    - Suche Zahl aus [1,9] die an dieser Stelle erlaubt ist. Falls es keine solche Zahl gibt, gib False zurück
    - Setze Zahl im Feld und rufe die Prozedur rekursiv auf.
    - Falls die Prozedur False zurückgibt, mache Änderung rückgängig und versuche nächste Zahl. Gibt die Prozedur eine Lösung zurück, gib diese Lösung zurück.

    Da ich in C und in diesen komischen Strukturdiagrammen nicht fit bin, überlass ich dir die praktische Ausarbeitung 😉 :p

    0
Anmelden zum Antworten