Sudokulöser in C verrechnet sich!
-
Hallo erstmal,
bin ganz neu in diesem Forum und hoffe auf eure Hilfe. Sitze hier schon ewig dran, und bin fast am verzweifeln. Ich möchte einen Sudokulöser programmieren, welcher Eingaben der Form: x y Wert annimmt und dann schrittweise das Sudoku löst. Soweit so gut, leider verhaspelt er sich da und berechnet irgentwann falsche Zahlen. Komme echt nicht mehr weiter und weiß nicht wo das Problem steckt. Ich vermute, das das Problem in der void solveField liegt. Bitte euch daher dringend um Hilfe.
Ciao Alexandra
#include <stdio.h> /* * Struktur f¨ur eine Sudoku-Zelle * Die Struktur besteht aus zwei Teilen. Dem eigentlichen Wert, der der Zelle * zugewiesen werden soll und einem Feld mit neun Eintr¨agen, die als * Streichliste benutzt wird. F¨ur den eigentlichen Wert und die Streichliste * gilt, dass der Wert 0 unbelegt bedeutet. Wenn also der eigentliche Wert * nicht 0 ist, wird nur der zugewiesene Wert ausgegeben, sonst wird die * Streichliste ausgegeben. Ist eine Stelle der Streichliste 0 wird dieser Wert * ebenfalls nicht ausgegeben, sondern nur die Werte ungleich 0. * In der Streichliste entspricht die Stelle 0 der Zahl 1, die Stelle 1 der Zahl * 2 usw. Die Stelle 8 entspricht dann der 9. */ typedef struct _sudokuzelle { int wert; int streichliste[9]; } sudokuzelle; /*------------------------------------------------------------------------------ * Diese Funktion f¨ugt eine Zahl in eine Soduk-Zelle ein und korrigiert die * Streichlisten aller betroffenen Felder. * Idee: Die Streichliste einer Zelle wird vollst¨andig gef¨ullt. Anschliessend * werden alle Zahlen der Streichliste zur¨uckgesetzt, die bereits in der Zeile, * Spalte oder dem Block vorkommen. Dieses wird f¨ur alle Zellen durchgef¨uhrt. *----------------------------------------------------------------------------*/ void setValue( int x, int y, int value, sudokuzelle array[9][9] ){ printf("%d, %d, %d\n",x,y,value); /* Schleifenzähler f¨ur die Pr¨ufung der Zeilen und Spalten */ int i; /* Schleifenzähler f¨ur die Schleifen beim Pr¨ufen des Blocks */ int x1, y1; /* Variablen die den Anfang des zu pr¨ufenden Blocks beinhalten */ int xbegin, ybegin; /* Zun¨achst den Wert in die entsprechende Zelle setzen */ array[y-1][x-1].wert = value; /* Jetzt m¨ussen die Streichlisten angepasst werden. */ /* Alle Zeilen durchgehen */ for( y = 0; y < 9; y++ ){ /* Alle Spalten durchgehen */ for( x = 0; x < 9; x++ ){ /* Die Streichliste der Zelle initialisieren */ for( i = 0; i < 9; i++ ){ array[y][x].streichliste[i] = 1; } /* jetzt m¨ussen alle Zahlen aus der Streichliste entfernt werden, die entweder in der Zeile, Spalte oder dem Block vorkommen. Zuerst die Zeile und Spalte durchgehen. Das geht mit einer Schleife. */ for( i = 0; i < 9; i++ ){ if( array[y][i].wert > 0 ) array[y][x].streichliste[array[y][i].wert-1] = 0; if( array[i][x].wert > 0 ) array[y][x].streichliste[array[i][x].wert-1] = 0; } /* und dann noch den Block pr¨ufen. Dazu m¨ussen zwei Schleifen benutzt werden, die jeweils beim Blockanfang beginnen und dann nur drei Felder in x und y Richtung gehen. */ xbegin = x/3; ybegin = y/3; for( y1 = ybegin*3; y1 < ybegin*3+3; y1++ ){ for( x1 = xbegin*3; x1 < xbegin*3+3; x1++ ){ if( array[y1][x1].wert > 0 ) array[y][x].streichliste[array[y1][x1].wert-1] = 0; } } } } } void printGrid(sudokuzelle array[9][9]) { /* Deklaration von Hilfsvariablen in Reihenfolge der Nutzung */ int g, h, i, j, k; /* Zeichnen der oberen Begrenzung */ printf("#########################################################################\n"); /* Wir iterieren - in dieser Reihenfolge - durch * - Block-Zeilen (also drei Sudoku-Zeilen à drei Computer-Zeilen) (g) * - Sudoku-Zeilen (h) * - Lines (i) * - Horizontale Blöcke (j) * - Einzelne Felder (k) * Und hoffen dass danach ein ansehnliches Ergebnis heraus kommt. */ for( g = 0; g < 3; g++ ) /* Block-Zeilen */ { for( h = 0; h < 3; h++ ) /* Sudoku-Zeilen */ { for ( i = 0; i < 3; i++ ) /* Lines */ { /* Rechte Begrenzung des Line */ printf("#"); for ( j = 0; j < 3; j++ ) /* Horizontale Blöcke */ { for ( k = 0; k < 3; k++ ) /* Einzelne Felder */ { /* Falls das Feld schon wirklich ausgefüllt ist, hat * einen Wert (value); wenn dieser nicht zugegen ist, * zeigen wir die Möglichkeiten der Streichliste an */ if (array[g*3+h][j*3+k].wert) { /* Ausgabe des Werts in der Mitte der Sudoku-Zelle */ if (1 == i) { printf(" %i ", array[g*3+h][j*3+k].wert); } else { printf(" "); } } else { /* Wir fragen jeweils ab ob das Entsprechende Feld der Streichliste * keine 0 enthält und geben ansonsten die zugehörige Zahl aus. * Die zugehörige Zahl entspricht dem Index des Arrays 'possibilities' * plus 1, da der Index 0-basiert ist. */ if (array[g*3+h][j*3+k].streichliste[3*i]) { printf(" %i", 3*i+1); } else { printf(" "); } if (array[g*3+h][j*3+k].streichliste[3*i+1]) { printf(" %i", 3*i+2); } else { printf(" "); } if (array[g*3+h][j*3+k].streichliste[3*i+2]) { printf(" %i", 3*i+3); } else { printf(" "); } } /* rechte Begrenzung des Felds (falls nicht schon gegeben) */ if (k != 2) printf(" |"); } /* rechte Begrenzung des Blocks falls nicht schon die ganze * Line begrenz wird */ if (j != 2) printf(" #"); } /* rechte Begrenzung der Line */ printf(" #\n"); } /* untere Begrenzung der Sudoku-Zeile FALLS nicht schon eine Begrenzung der * Blockzeile ausgegeben werden wird. */ if (h != 2) printf("#-------+-------+-------#-------+-------+-------#-------+-------+-------#\n"); } /* untere Begrenzung der Block-Zeile */ printf("#########################################################################\n"); } } /* Zur L¨osung des Problems wird über jedes 3x3 Feld im Sudoku-Feld ein Block * (3x3 Feld) gelegt, in dem alle Felder mit einer Zahl vorbelegt werden. An den * Stellen, an denen im Sudoku-Feld bereits eine Zahl eingetragen wurde, wird * eine 0 eingesetzt. Dann wird f¨ur jede Zeile und Spalte gepr¨uft, ob die * Zahl vorkommt. Wenn ja, wird die entsprechende Zeile und Spalte im Block auf * 0 gesetzt. Zum Schluss werden denn die Vorkommen der Zahl gez¨ahlt. Wenn die * Zahl nur genau einmal im Block vorkommt, kann sie an der entsprechenden * Stelle im Sudoku-Feld eingetragen werden. Das ganze wird f¨ur jeden Block und * alle Zahlen von 1 bis 9 durchgef¨uhrt. */ void solveField( sudokuzelle array[9][9]){ /* Einen Block definieren, der jeweils mit einer Zahl vordefiniert wird. */ int block[3][3]; /* Die Zahl, die gerade gepr¨uft wird. */ int zahl; /* Hilfsvariablen */ int i, k; // xbegin und ybegin enthalten die Koordinaten des zu betrachtenden Blocks int xbegin, ybegin; /* Hilfsvariablen */ int x, y; int x1, y1, anzahl; /* Jeden Block im Sudokufeld einzeln pr¨ufen. xbegin und ybegin enthalten die x und y kooridnaten des entsprechenden Blocks. Diese Daten werden f¨ur die Auswahl der richtigen Spalten und Zeilen bei der Pr¨ufung der Zahl ben¨otigt. */ for( ybegin = 0; ybegin < 9; ybegin += 3 ) { for( xbegin = 0; xbegin < 9; xbegin += 3) { /* Das ganze wird f¨ur jede Zahl durchgef¨uhrt */ for( zahl = 1; zahl < 10; zahl++ ){ /* Zu Beginn den Block mit der Zahl vollständig belegen. Dabei ist zu beachten, dass die Felder, in denen bereits eine Zahl zugewiesen wurde, nicht belegt werden dürfen und deswegen mit 0 belegt werden. */ for( y = 0; y < 3; y++ ){ for( x = 0; x < 3; x++){ /* Im Sudoku-Feld nachschauen, ob das entsprechende Feld schon belegt ist. Dazu werden xbegin und ybegin als Offset benutzt.*/ if( array[ybegin+y][ybegin+x].wert != 0 ){ block[y][x] = 0; } else { block[y][x] = zahl; } } } /* Jetzt wird f¨ur jede Spalte und Zeile des Blocks gepr¨uft, ob die Zahl irgend wo vorkommt. Wenn ja, wird jeweils die ganze Zeile bzw. Spalte des Blocks auf 0 gesetzt, weil sie dort ja nicht noch einmal vorkommen darf.*/ for( i = 0; i < 3; i++ ){ /* Zuerst die Zeile pr¨ufen */ for( k = 0; k < 9; k++ ) { /* Wenn die Zahl gefunden wurde, die Zeile auf 0 setzen und die innersten Schleife durch den break verlassen. */ if( array[ybegin+i][k].wert == zahl ){ block[i][0] = 0; block[i][1] = 0; block[i][2] = 0; break; } } /* Jetzt die Spalte pr¨ufen */ for( k = 0; k < 9; k++ ) { /* Wenn die Zahl gefunden wurde, die Spalte auf 0 setzen und die innersten Schleife durch den break verlassen. */ if( array[k][xbegin+i].wert == zahl ){ block[0][i] = 0; block[1][i] = 0; block[2][i] = 0; break; } } } /* Jetzt die Anzahl der Einträge zählen. Wenn genau ein Eintrag übrig ist, kann dieser in das Sudoku-Feld ¨ubernommen werden. */ anzahl = 0; for( y = 0; y < 3; y++ ){ for( x = 0; x < 3; x++){ /* Im Block nachschauen, ob das entsprechende Feld belegt ist. */ if( block[y][x] != 0 ){ x1 = x; y1 = y; anzahl++; } } } /* Wenn genau ein Eintrag ¨ubrig war, diesen ¨ubernehmen */ if( anzahl == 1 ) { printf( "test"); printf( "Automatische Belegung fuer Zelle (%d,%d)=%d\n",xbegin+x1+1, ybegin+y1+1, zahl ); setValue( xbegin+x1+1, ybegin+y1+1, zahl, array ); } } } } } /* diese Funktion belegt das zweidimensionale * Sudoku-Array mit lauter Nullen */ void clearArray(sudokuzelle array[9][9]){ int row, col,p; for ( row = 0; row < 9; ++row ){ for ( col = 0; col < 9; ++col ){ array[row][col].wert = 0; for ( p = 0; p < 9; p++ ) { array[row][col].streichliste[p] = 1; } } } } /* Diese Funktion pruft das Sudokufeld auf Richtigkeit * R¨uckkgabewert ist 1 bei erfolgreicher L¨osung, ansonsten 0. * * F¨ur die L¨osung des Problems wird nicht gepr¨uft, ob alle Zahlen * von 1 bis 9 in jeder Zeile, Spalte und in jedem Block vorkommen, * sonder es wird gepr¨uft, ob jede Zahl jeweils genau einmal vorkommt. */ int isSolved( sudokuzelle array[9][9] ){ int digit, row, col, count; int bigrow, bigcol; /* Hilfsvariablen f¨ur die drei gr¨oßeren Spalten/Zeilen */ /* F¨ur jede Ziffer wird nachgesehen, ob die Ziffer genau einmal pro * Zeile, genau einmal pro Spalte und genau einmal pro Block vorkommt */ for ( digit = 1; digit <= 9; ++digit ){ /* Wie oft kommt die Ziffer in jeder Zeile vor? */ for ( row = 0; row < 9; ++row ){ /* count z¨ahlt die Anzahl der Vorkommen von digit und wird am Anfang * mit 0 belegt. Bei jedem Vorkommen von digit wird count dann um 1 erh¨oht. */ count = 0; // innerhalb der Zeile jedes Feld pr¨ufen for ( col = 0; col < 9; ++col ){ // Wenn in dem betrachteten Feld der Wert von digit steht, wird count um 1 erh¨oht. if ( array[row][col].wert == digit ){ ++count; } } /* Wenn alle Felder der Zeile gepr¨uft wurden, muss count den Wert 1 haben, * weil sonst der wert von digit mehr als einmal in der Zeile vorgekommen w¨are * und das darf laut Regelwerk nicht sein. */ if ( count != 1 ){ return 0; /* false */ } } /* Wie oft kommt die Ziffer in jeder Spalte vor? * Hier findet das ¨aquivalente vorgehen wie bei den Zeilen statt. */ for ( col = 0; col < 9; ++col ){ count = 0; for ( row = 0; row < 9; ++row ){ if ( array[row][col].wert == digit ){ ++count; } } if ( count != 1 ){ return 0; /* false */ } } /* Wie oft kommt die Ziffer in jedem Viereck vor? * Zur Pr¨ufung der Vierecke werden 3 mal 3 Vierecke betrachtet. * Es werden somit zwei Schleifen ben¨otigt, die jeweils den Beginn * des aktuellen Vierecks beschreiben. */ for ( bigrow = 0; bigrow < 3; ++bigrow ){ for ( bigcol = 0; bigcol < 3; ++bigcol ){ count = 0; /* Innerhalb des Vierecks werden dann jeweils nur die zugeh¨origen Zellen gepr¨uft. * Es muss somit f¨ur die Zeilen und Spalten jeweils nur auf 3 gez¨ahlt werden. */ for ( row = bigrow*3; row < bigrow*3+3; ++row ){ for ( col = bigcol*3; col < bigcol*3+3; ++col ){ if ( array[row][col].wert == digit ){ ++count; } } } if ( count != 1 ){ return 0; /* false */ } } } } return 1; /* true */ } int main(void) { // Erstellen des leeren Sudokufelds: sudokuzelle array[9][9] = {}; clearArray(array); // Wir machen was damit int x, y, z; printf("> "); while (scanf("%d %d %d", &x, &y, &z)==3) { // muss gesetzt werden damit weiter gearbeitet werden kann, // da noch ein return im Inputstream ist getchar(); setValue(x, y, z, array); printf("Setze für (%d,%d) den Wert %i.\n", x, y, z); solveField(array); printGrid(array); printf("> "); } // Aus die Maus return 0; }
-
Dieser Thread wurde von Moderator/in estartu aus dem Forum MFC (Visual C++) in das Forum DOS und Win32-Konsole verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
tip: den debugger nutzen und schritt für schritt durchlaufen.
-
wenn du mir erstmal erklärst wie sudoku funktioniert xD ....
-
Hallo
Du solltest den Fehler schon noch etwas einkreisen.
chrische
-
Ein Sudoku ist ein Zahlenrätsel.
Es funktioniert so, das es insgesamt 81 Felder gibt.
In einer Reihe, einer Spalte und einem 3x3 Block dürfen jeweils nur die
Zahlen 1-9 vorkommen, und zwar nicht doppelt.
Hoffe das reicht zur Erklärung einigermaßen, sonst mal kurz Wiki gucken.
Ist ein ganz interessantes und beliebtes spiel.Hier soll man ein paar Zahlen vorgeben und die restlichen soll das
Programm dann lösen.Leider weiß ich auch nicht wo der Fehler liegen könnte. Aber
vielleicht gibts hier ja noch irgendwo nen Fux der das weiß !Gruß,
SoniX
