wir müssen ein sudoku-lösendes c-programm mit brute-force algorithmus schreiben. die zahlen werden über eine textdatei eingelesen (programm muss allerdings den speicherort nicht abfragen!). leider kriegen wir's nicht so ganz hin...
![Smile :)](./images/smilies/icon_e_smile.gif)
wenn wir das programm starten, laufen zahlen durch! wenn man dieses pausiert:
"Loesung XXX:
123456789
456789123
789123456
..."
was machen wir falsch, bzw. wie geht's richtig?? wär super, wenn uns jmd. helfen könnte!
![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
UNSER CODE (die main-funktion ist ganz unten):
Code: Alles auswählen
#define _CRT_SECURE_NO_WARNINGS /* Fehlermeldung für alte Stringfunktionen unterdrücken */
#include <stdio.h>
/* Überprüfung der Zeilen, Spalten */
#define N 9 /* Größe des Sudokus */
static int feld[N][N];
static int loesungen = 0;
int createSudoku(char *dateiname);
void printSudoku();
int solve(int x, int y);
int checkBox(int x, int y, int wert);
int checkVertikal(int x, int wert);
int checkHorizontal(int y, int wert);
int check(int x, int y, int wert);
/* Felder auf Zahlen überprüfen (0 = leeres Feld, 1 = Zahl gefunden) */
int check(int x, int y, int wert) {
if(checkHorizontal(y, wert))
return 1;
if(checkVertikal(x, wert))
return 1;
if(checkBox(x, y, wert))
return 1;
return 0;
}
/* Überprüfung der Horizontalen auf Zahl (0 = nein, 1 = ja) */
int checkHorizontal(int y, int wert) {
int i;
for(i = 0; i < N; i++)
if(feld[y][i] == wert)
return 1;
return 0;
}
/* Überprüfung der Vertikalen auf Zahl (0 = nein, 1 = ja) */
int checkVertikal(int x, int wert) {
int i;
for(i = 0; i < N; i++)
if(feld[i][x] == wert)
return 1;
return 0;
}
/* Überprüfung der 3x3-Box auf Zahl (0 = nein, 1 = ja) */
int checkBox(int x, int y, int wert) {
int x_box, y_box, i, j;
/* 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] == wert)
return 1;
return 0;
}
/* Alle Lösungen für ein Sudoku, Startwert x, y: 0, 0
* 1 Zahl passt
* 0 Zahl passt nicht
*/
int solve(int x, int y) {
int i;
if(x == N) { /* Zeilenende erreicht */
y++;
x = 0;
if(y == N) /* Ende erreicht */
return 1;
}
if(feld[y][x] > 0) /* Feld schon gesetzt */
return solve(x+1, y); /* Nächstes Feld */
for(i = 1; i <= N; i++) { /* Keine Zahl vorhanden */
if(!check(x, y, i)) { /* Alle Zahlen durchgehen, DIESES CHECK FÜR DAS OBERE SOLVE SETZEN*/
feld[y][x] = i; /* Wenn Zahl passt, setzen */
if(solve(x+1, y)) { /* Nächstes Feld prüfen */
loesungen++; /* Lösung gefunden, ausgeben */
printf("Loesung %d:\n", loesungen);
printSudoku();
printf("\n");
return 1; /*<-- Nur eine Loesung ausgeben */
}
}
}
feld[y][x] = 0; /* Keine Zahl hat gepasst, wieder 0 setzen */
return 0;
}
/* Ausgabe */
void printSudoku() {
int i, j;
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++) {
printf("%d", feld[i][j]);
}
printf("\n");
}
}
int main() {
int iAuswahl;
printf("SUDOKU - MENUE\nBitte waehlen Sie!\n");
printf("1. Spiel starten\n2. Beenden\n\n");
scanf("%d", &iAuswahl);
if(iAuswahl==1)
{
solve(0, 0);
printf("Loesungen: %d\n", loesungen);
return 0;
}
else
if(iAuswahl==2)
{
return 0;
}
}