Sudoku
-
Hallo! ich bin gerade dabei, ein programm für sudoku zu schreiben, komme aber an einer stelle bzw. funktion nicht weiter. wäre lieb wenn mir jemand helfen könnte!
die funktion ist loese_sudoku.#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, fall 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 muss ich noch ergaenzen. Sie soll rekursiv sein (d.h. an einer Stelle ruft loese_sudoku sich selbst auf) Man darf 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 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; }
-
deine Frage?
-
camper schrieb:
deine Frage?
ich komme bei der oben genannten funktion nicht weiter. meine frage wäre ob mir da evtl jemand behilflich sein kann
-
Auf die Schnelle:
Freie Stelle suchen, Koordinaten merken, 1 einsetzen.
Ist das erlaubt, Funktion rekursiv aufrufen. Wenn nicht, mit 2 weiter machen. usw.
Ist die 10 erreicht, dann eine 0 für nicht möglich zurückgeben.Wenn du keine freie Stelle mehr finden kannst und alles erlaubt ist, bist du fertig und gibst eine 1 zurück.
-
DirkB schrieb:
Auf die Schnelle:
Freie Stelle suchen, Koordinaten merken, 1 einsetzen.
Ist das erlaubt, Funktion rekursiv aufrufen. Wenn nicht, mit 2 weiter machen. usw.
Ist die 10 erreicht, dann eine 0 für nicht möglich zurückgeben.Wenn du keine freie Stelle mehr finden kannst und alles erlaubt ist, bist du fertig und gibst eine 1 zurück.
Fast richtig, allerdings sollten die Zahlen natürlich im gültigen Bereich liegen:
Juli84 schrieb:
#define BS 9 /* "Dimension" des Sudokus, Standard ist 9 */ #define B 3 /* "Dimension" eines Quadranten ("Unterquadrat") */ /* typischerweise Wurzel aus BS */Bei BS=9 gerne zwischen 1..BS (hier 9)
Was die beiden Variablen i und j in
Juli84 schrieb:
loese_sudoku(i, j, sudoku );sollen erschliesst sich mir momentan nicht. Die werden m.E. nicht benötigt.