komplettes Sudoku mit Backtracking - Hab ne Frage
-
Hallo,
das Programm funktioniert einwandfrei. Ich hab nur eine Verständniss Frage bei der Backtrack funktion.
In Zeile 128 setzt er ja die vorhergegange Zahl auf 0, weil keine Lösung passt.
Woher weiß aber das Programm, dass er nicht wieder die gleiche Zahl ausprobiert und in der gleichen Sackgasse landet, weil eigentlich müsste der doch dann in einer dauerschleife enden?Vielen Dank
#include <stdio.h> #include <stdlib.h> int sudoku[9][9]={{9,7,6},{1,2,8}}; int solution[9][9]; int test_value(int x, int y, int value) { int i, j; // Ueberpruefe Zeile und Spalte for (i = 0; i < 9; i++) { if (value == solution[i][y] || value == solution[x][i]) { return 0; } } // Ueberpruefe jedes Quadrat if (x < 3) { //links oben if (y < 3) { for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { if (value == solution[i][j]){ return 0; } } } } else if (y < 6) { //links mitte for (i = 0; i < 3; i++) { for (j = 3; j < 6; j++) { if (value == solution[i][j]) { return 0; } } } } else { //links unten for (i = 0; i < 3; i++) { for (j = 6; j < 9; j++) { if (value == solution[i][j]) { return 0; } } } } } else if (x < 6) { //mitte oben if (y < 3) { for (i = 3; i < 6; i++) { for (j = 0; j < 3; j++) { if (value == solution[i][j]) { return 0; } } } } else if (y < 6) { //mitte mitte for (i = 3; i < 6; i++) { for (j = 3; j < 6; j++) { if (value == solution[i][j]) { return 0; } } } } else { //mitte unten for (i = 3; i < 6; i++) { for (j = 6; j < 9; j++) { if (value == solution[i][j]) { return 0; } } } } } else { //rechts oben if (y < 3) { for (i = 6; i < 9; i++) { for (j = 0; j < 3; j++) { if (value == solution[i][j]) { return 0; } } } } else if (y < 6) { //rechts mitte for (i = 6; i < 9; i++) { for (j = 3; j < 6; j++) { if (value == solution[i][j]) { return 0; } } } } else { //rechts unten for (i = 6; i < 9; i++) { for (j = 6; j < 9; j++) { if (value == solution[i][j]) { return 0; } } } } } return value; } int backtrack(int x, int y) { int step_value,trial_value; if (solution[x][y] == 0) //wenn das Feld unbesetzt ist mach... { for (trial_value= 1; trial_value < 10; trial_value++) //zählt die Zahl 1 bis 9 hoch { step_value = test_value(x,y,trial_value); // ruft für jeden Schritt die Funktion test_value auf und prüft ob die Zahl dort rein passt if (step_value > 0) //überprüft ob Feld besetzt werden kann { solution[x][y] = step_value; if (x == 8 && y == 8) //alle Felder wurden besetzt { return 1; } else if (x == 8) { if (backtrack(0,y+1)) return 1; //neue Zeile anfangen } else { if (backtrack(x+1,y)) return 1 ; //neue Spalte anfangen } } } if (trial_value == 10) { //keine Zahl passt in das Feld solution[x][y] = 0; // Das vorherige Feld wird 0 gesetzt return 0; } } else { if (x == 8 && y == 8) // alle Felder wurden { return 1; } else if (x == 8) { if (backtrack(0,y+1)) return 1; } else { if (backtrack(x+1,y)) return 1 ; } } return 0; } void display(void) { int i,j; for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { printf("%d ", solution[i][j]); } printf("\n"); } } int main(){ int i,j; FILE * pFile; printf("Eingabe aus sudoku.txt \n"); pFile = fopen ("sudoku.txt","r+"); for (i = 0; i < 9; i++) { fscanf (pFile, "%d %d %d %d %d %d %d %d %d", &sudoku[i][0],&sudoku[i][1], &sudoku[i][2], &sudoku[i][3],&sudoku[i][4], &sudoku[i][5], &sudoku[i][6],&sudoku[i][7], &sudoku[i][8]); } fclose (pFile); for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { solution[i][j] = sudoku[i][j]; } } display(); if (backtrack(0,0)) { printf("Loesung ist :\n"); display(); } else { printf("Keine Loesung\n"); } return 0; }
-
Nach der Copy&Paste-Orgie am Anfang liest doch keiner mehr weiter. Ich war mal so frei und hab die offensichtlichsten Kürzungen gemacht, und die unnötigen Kommentare entfernt (erkläre in Kommentaren niemals, wie die Sprache funktioniert, sonst liest keiner deine Kommentare). Die wesentliche Ausdrucksweise des Algorithmus hab ich nicht verändert.
So diskutiert es sich wahrscheinlich leichter.
#include <stdio.h> int sudoku[9][9] = {{9, 7, 6}, {1, 2, 8}}; int solution[9][9]; int backtrack(int, int); int test_value(int x, int y, int value) { int i, j; int i_start, i_end; // Ueberpruefe Zeile und Spalte for (i = 0; i < 9; i++) if (value == solution[i][y] || value == solution[x][i]) return 0; // Ueberpruefe jedes Quadrat // [mngbd] er meint "Feld", also das, wo eine Zahl stehen kann i_start = x / 3 * 3; i_end = i_start + 3; for (i = i_start; i < i_end; i++) { int j_start = y / 3 * 3; int j_end = j_start + 3; for (j = j_start; j < j_end; j++) if (value == solution[i][j]) return 0; } return value; } int alle_besetzt(int x, int y) { if (x == 8 && y == 8) return 1; //alle Felder wurden besetzt else if (x == 8 && backtrack(0,y+1)) return 1; //neue Zeile anfangen else if (backtrack(x+1,y)) return 1; //neue Spalte anfangen return 0; } int backtrack(int x, int y) { if (solution[x][y] == 0) // wenn das Feld unbesetzt ist mach... { int trial_value; for (trial_value = 1; trial_value < 10; trial_value++) { int step_value = test_value(x,y,trial_value); // prüft ob die Zahl dort rein passt if (step_value > 0) // überprüft ob Feld besetzt werden kann { solution[x][y] = step_value; if (alle_besetzt(x, y)) return 1; } } if (trial_value == 10) // keine Zahl passt in das Feld { solution[x][y] = 0; // Das vorherige Feld wird 0 gesetzt return 0; } } else if (alle_besetzt(x, y)) return 1; return 0; } void display(void) { int i, j; for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) printf("%d ", solution[i][j]); printf("\n"); } } int main(void) { int i, j; for (i = 0; i < 9; i++) for (j = 0; j < 9; j++) solution[i][j] = sudoku[i][j]; printf("Eingabe:\n"); display(); if (backtrack(0, 0)) { printf("Loesung ist:\n"); display(); } else printf("Keine Loesung\n"); return 0; }
Ach ja: das Dateieinlesen hab ich auch rausgenommen, weil für den Algorithmus prinzipiell nicht nötig.
Edit 2 bis n:
Diverse unnötige Zeilen gelöscht.