Sudoku mit Brute-Force Algorithmus
-
hey leute,
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):
#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++)
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;
}
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*/
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 */
}
}
}
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;
}
}
-
Bitte lies dir mal den ersten Link in meiner Signatur und die als wichtig markierten Threads gründlich durch und passe deine Fragestellung an.
wir müssen ein sudoku-lösendes c-programm mit brute-force algorithmus schreiben.
Das hast du wahrscheinlich etwas falsch verstanden. Die Anzahl möglicher Sudokus ist von der Größenordnung 10^21. Die alle (oder im Durchschnittsfall die Hälfte davon) per Brute Force durchzugehen, würde ein paar hunderttausend CPU-Jahre brauchen.
Üblich wäre mindestens ein Backtrackingalgorithmus.
-
??versteh nur bahnhof??
-
chef__87 schrieb:
??versteh nur bahnhof??
Das geht uns auch so, nach dem Lesen deines Eröffnungsbeitrags. Das ist das Problem. Sieh ihn dir doch mal an. Glaubst du jemand, der nicht du selber bist, weiß danach, was du überhaupt wissen möchtest?
Selbst dein
chef__87 schrieb:
??versteh nur bahnhof??
ist sehr ungünstige schriftliche Kommunikation. Du verstehst also irgendetwas nicht. Das ist die gesamte Aussage dieses Beitrags. Ich weiß nicht, was du nicht verstehst, ich weiß nicht, warum du es nicht verstehst. Daher kann ich es dir auch nicht erklären.
Wir können nicht in deinen Kopf gucken. Drück dich klar aus! Deine Beiträge hier sind alles was wir von dir kennen. Sie müssen daher geeignet sein, dein Problem für einen völlig Fremden ausreichend darzulegen, wenn du Hilfe bekommen möchtest.
(Das ist übrigens auch beim Programmieren sehr wichtig. Der Computer weiß auch nicht, was du wirklich möchtest, sondern nimmt alles wörtlich, was du ihm sagst, sei es auch noch so sinnlos. Klare, schriftliche Ausdrucksweise und Programmieren haben vieles gemeinsam. Man erkennt oft schon an einem, ob jemand das andere beherrscht.)
-
erstmal vielen dank für die kompetente hilfe!
1. warum spuckt das programm nur zahlen von 1-9 in einer reihenfolge aus?
2. es liegt eine .txt-datei im selben ordner wie die visualbasic-projekt-datei. wie kann das programm darauf zugreifen?
3. was ist an der schleife falsch programmiert, dass eben nur zahlen "wirr" ausgespuckt werden und diese !nie! beendet wird.
-
...
