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...
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!
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;
}
}