Hey Leute,
ich hatte mir in den Kopf gesetzt einen Sudoku Solver zu programmieren. Ich habe bewusst NICHT im Internet danach gesucht und mir meine eignen Gedanken gemacht.
Das Endprodukt war ein Solver, welcher an der Stelle aufgehört hat zu lösen, wo ein Widerspruch herauskam. Habe alles probiert, bin aber nicht weiter gekommen.
Dann habe ich mich mal im Internet inspirieren lassen und damit letztendlich auch meinen Code so anpassen können, dass er funktioniert. Jedoch verstehe ich die Funktionsweise von
solveField() nicht 100%. Wenn ich es mir Schrittweise debugge, dann stelle ich fest, dass der x Wert immer sobald es einen Widerspruch gibt in das zuletzt genutzte Feld springt.
Dies ist mir aber aus dem Code nicht ersichtlich. Für mich wird x immer weiter erhöht und wenn die Zeile zu Ende ist, geht es in die Nächste. Das Zurückspringen ist echt irgendwie komisch.
Ich hoffe mir kann jmd da auf die Sprünge helfen.
Hier der Code:
Spoiler anzeigen
LG
Michael
ich hatte mir in den Kopf gesetzt einen Sudoku Solver zu programmieren. Ich habe bewusst NICHT im Internet danach gesucht und mir meine eignen Gedanken gemacht.
Das Endprodukt war ein Solver, welcher an der Stelle aufgehört hat zu lösen, wo ein Widerspruch herauskam. Habe alles probiert, bin aber nicht weiter gekommen.
Dann habe ich mich mal im Internet inspirieren lassen und damit letztendlich auch meinen Code so anpassen können, dass er funktioniert. Jedoch verstehe ich die Funktionsweise von
solveField() nicht 100%. Wenn ich es mir Schrittweise debugge, dann stelle ich fest, dass der x Wert immer sobald es einen Widerspruch gibt in das zuletzt genutzte Feld springt.
Dies ist mir aber aus dem Code nicht ersichtlich. Für mich wird x immer weiter erhöht und wenn die Zeile zu Ende ist, geht es in die Nächste. Das Zurückspringen ist echt irgendwie komisch.
Ich hoffe mir kann jmd da auf die Sprünge helfen.
Hier der Code:
C-Quellcode
- #include <stdio.h>
- #include <stdlib.h>
- #include <locale.h>
- #define G 9
- int feld[G][G] = {
- {0,4,5,7,0,0,0,6,1}, //Reihe 1
- {0,0,0,8,0,5,4,0,0}, //Reihe 2
- {0,0,7,6,4,0,0,0,2}, //Reihe 3
- {5,0,0,9,6,4,0,0,0}, //Reihe 4
- {6,0,8,5,0,1,0,3,0}, //Reihe 5
- {0,7,0,0,0,0,0,9,0}, //Reihe 6
- {3,0,2,4,0,0,1,0,0}, //Reihe 7
- {9,0,0,1,0,0,0,0,6}, //Reihe 8
- {0,0,0,0,0,3,8,0,0}};//Reihe 9
- void printField();
- void fillField();
- int solveField(int x, int y);
- int checkSudoku(int zahl, int x, int y);
- int getNextEmptyField(int *a, int *b);
- int main(void)
- {
- setlocale( LC_ALL, "" );
- //Programmablauf
- printField();
- printf("Taste drücken zum Starten...");
- getch();
- //Lösen
- solveField(0,0);
- printf("Sudoko gelöst!");
- getch();
- return 0;
- }
- //Sukoku Lösen
- int solveField(int x, int y)
- {
- if(x == G) //Zeilenende
- {
- y++;
- x = 0;
- }
- if(y == G)
- {
- //-> Solved
- return 1;
- }
- //Prüfen ob Feld gefüllt
- if(feld[y][x] > 0)
- {
- //Nächstes Feld
- return solveField(x+1, y);
- }
- //Zahl von 1-9 in aktuelles freies Feld einsetzen
- int z;
- for(z = 1; z < 10; z++)
- {
- //Zeilen prüfen - Spalten prüfen - 3er Päckchen prüfen
- if(checkSudoku(z,x,y) == 0)
- {
- feld[y][x] = z;
- //Auskommentieren zum Schrittweise anzeigen
- //printf("X: %d | Y: %d",x+1,y+1);
- //getch();
- //printField();
- if(solveField(x, y) == 1) //Gerade diese Zeile ist mir nicht ganz klar...
- {
- //Fertig -> Print
- printField();
- }
- } //else nächste Zahl z
- }
- feld[y][x] = 0; //Auch wenn die Zeile auf 0 gesetzt wird, dann ist doch x um +1 erhöht worden und es wäre jetzt ein Feld leer und übersprungen?
- return 0;
- }
- //Spielfeld nach den Regeln überprüfen
- int checkSudoku(int zahl, int x, int y)
- {
- int i,j;
- //Zeilen
- for(i = 0; i < 9; i++)
- {
- if(feld[y][i] == zahl)
- {
- return 1; //Vorhanden
- }
- }
- //Spalten
- for(i = 0; i < 9; i++)
- {
- if(feld[i][x] == zahl)
- {
- return 1; //Vorhanden
- }
- }
- //3er Kästchen
- int x_box, y_box;
- // Passende Ecke der Box herausfinden
- x_box = (int)(x / 3) * 3;
- y_box = (int)(y / 3) * 3;
- for(i = y_box; i < y_box + 3; i++)
- {
- for(j = x_box; j < x_box + 3; j++)
- {
- if(feld[i][j] == zahl)
- return 1; //Vorhanden
- }
- }
- return 0; //Nicht vorhanden.
- }
- //Funktion für späteres Vorhaben (zuerst auch für den algo. genutzt)
- int getNextEmptyField(int *a, int *b)
- {
- int i,j;
- for(i = 0; i < 9; i++)
- {
- for(j = 0; j < 9; j++)
- {
- if(feld[i][j] < 1)
- {
- //Treffer
- *a = i;
- *b = j;
- return 1;
- }
- }
- }
- //Kein Feld gefunden
- return 0;
- }
- //Funktion für späteres Vorhaben
- void fillField()
- {
- int x,y,w = 0;
- printf("Zeile: ");
- scanf("%d", &x);
- printf("Spalte: ");
- scanf("%d", &y);
- //Feld auf leere Stelle prüfen
- if(feld[y-1][x-1] < 1)
- { //Leer
- printf("Zahl: ");
- scanf("%d", &w);
- //Überprüfung einbauen ob Zahl korrekt
- feld[y-1][x-1] = w;
- }
- main();
- }
- //Ausgabe des Spielfeldes in der CMD
- void printField()
- {
- //Console leeren
- system("cls");
- system("color 0F");
- printf(" .:[Sudoku Solver v1]:.\n\n");
- int i,j;
- //Zeilen, Y-Achse
- printf(" 1 2 3 4 5 6 7 8 9\n");
- for(i=0; i<9; i++)
- {
- printf(" +---+---+---+---+---+---+---+---+---+\n");
- printf("%d |", i+1);
- //Spalten, X-Achse
- for(j=0; j<9; j++)
- {
- if(feld[i][j] < 1)
- { //Feld leer
- printf(" |");
- }
- else
- { //Feld gefüllt
- printf(" %d |", feld[i][j]);
- }
- }
- printf("\n");
- }
- printf(" +---+---+---+---+---+---+---+---+---+\n");
- }
LG
Michael