Backtracking Algorithmus. (Zu) kompliziert?
-
Hallo, ich habe an einem Backtracking Algorithmus für Sudokus geschrieben (wie es in einem Thread zuvor schon einmal versucht wurde).
Mein Algorithmus löst leere Sudokus und Sudokus, bei denen nur wenige Zahlen vorgegeben sind. Sind aber mehrere Zahlen vorgegeben, wie z.B bei0 3 0 | 0 0 0 | 0 0 0 0 0 0 | 1 9 5 | 0 0 0 0 9 8 | 0 0 0 | 0 6 0 ------+-------+------ 8 0 0 | 0 0 0 | 0 0 0 0 0 0 | 0 0 0 | 0 0 0 0 0 0 | 0 0 0 | 0 0 0 ------+-------+------ 0 0 0 | 0 0 0 | 0 0 0 0 0 0 | 0 0 0 | 0 0 0 0 0 0 | 0 0 0 | 0 0 0hängt sich mein Programm ab einem Punkt auf.
Vorab ein paar Infos zum Programm:
pruefen() gibt "true" zurück, wenn das Sudoku gültig ist und "false", wenn es halt nicht gültig ist.
In int arr[9][9] sind die Zahlen des sudokus gespeichert (0 = leeres Feld) und bei bool start[9][9] haben die Felder den Wert true, die von Anfang an belegt waren.Hier meine backtracking Funktion:
bool backtracking() { int sum=0; int xc=0,yc=0; bool control=false; for(;;) { for(int y=yc; y!=9; ++y) //bewegung nach unten { for(int x=xc; x!=9; ++x) //bewegung nach rechts { xc=0;yc=0; //siehe unten sum=0; // for(int o=0;o!=9;++o) // Abbruchbedingung: { // Wenn die Werte aller for(int p=0;p!=9;++p) // Felder addiert { // 405 ergeben sum+=arr[p][o]; // (also 9*8 + 9*7 ...) } // dann ist das Sudoku } // fertig und die Funtkion if(sum==405) // gibt true zurück return true; // control=false; //control zurücksetzen if(arr[x][y]!=0) //wenn feld schon vorgegeben ist, nächstes Feld bearbeiten continue; for(int a=1;a!=10;++a) // systematisch alle Zahlen { // von 1 bis 9 in das leere arr[x][y]=a; // Feld einsetzen. Wenn das // Sudoku noch gültig ist, wird if(pruefen()) // control auf true gesetzt, { // die schleife verlassen und control = true; // mit dem nächsten feld weiter gemacht. break; // wenn keine zahl von 1 bis 9 zu einem } // gültigen Sudoku führt, bleibt control } // auf false und der eigentliche backtracking // algorithmus setzt ein if(! control) // dieser block wird ausgeführt, wenn keine { // zahl für das feld arr[x][y] zu einem gültigen Sudoku führt arr[x][y]=0; // das Feld arr[x][y] wird daher auf 0 gesetzt for(;;) // diese for-Schleife sucht nach einem Feld, das VOR { // dem Feld arr[x][y] liegt und nich von Anfang an belegt ist --x; // x Koordinate um eins verkleinern (also ein Feld zurück gehen) if(x<0){x=8;--y;} // falls das ende der zeile erreicht ist, eine zeile weiter oben suchen if(start[x][y]==false) // wenn das so ermittelte Feld nicht von Anfang an belegt ist, { // . xc=x; // siehe // . yc=y; // unten // . ++arr[x][y]; // wird sein Wert um 1 erhöht if(arr[x][y]==10) // Sollte in dem Feld nun eine 10 stehen (was ja ungültig ist) { // wird es auf 0 zurück gesetzt. die Schleife beginnt von neuem arr[x][y]=0; // und sucht das nächste editierbare Feld if(x==0 && y==0) // falls das feld[0][0] auf 10 gesetzt wird return false;// wurden ALLE möglichen Kombinationen für das Sudoku ausprobiert. } // das sudoku ist damit unlösbar if(arr[x][y]!=0) // wenn ++arr[x][y] einen gültigen Wert ergibt break; // werden ALLE schleifen - bis auf die große } // Endlosschleife - verlassen. } // Die Koordinaten des Feldes arr[x][y] wurden } // in den Variablen xc und yc gespeichert. if(!control) // Dies führt dazu, dass die Schleifen, die die break; // x- und y-koordinate ändern, NACH dem Feld beginnen, } // dessen Wert zuvor um 1 erhöht wurde if(!control) // . break; // . } // . } return true; }Wo liegt mein Denkfehler?
Bin über alle Tipps froh!
Mfg Greedy
-
Mein erster Tipp wär mal Funktionalität auszulagern, so wie du das mit pruefen schon angefangen hast. Der Test ob das Feld komplett ausgefüllt ist, kann auch ganz prima in eine Funktion.
Vielleicht kannst Du mit nem Debugger rausfinden wo er sich genau aufhängt?
-
Da gabs doch auch nen anderen Thread dazu... Da hatte ich dir auch gesagt, dass es so, wie du das machst nicht gerade toll ist - weil man eben nacheinander Zahlen ausschließt und nicht zwingend immer irgendwo nen Feld hat, wo es klar ist, welche Zahl reinkommt...
ansonsten: siehe Vorredner ^^
bb
-
Hängst sich denn das Ganze überhaupt auf oder braucht deine Funktion einfach nur tierisch lange weil du ja anscheinend den ganzen Lösungsraum durchsuchst ?
Nimm mal einen Debugger und schaue dir mal jedes Feld nach jedem Setzen eines Kästchen an.
-
Ich habe jetzt mal in die Schleife, die die Zahlen einsetzt, Folgenden Code eingefügt.
system("cls"); PrintArray(); //gibt Array aus getch();D.h. ich kann Schleifendurchlauf für Schleifendurchlauf genau verfolgen, was passiert.
Wenn ich jetzt als Ausgang folgendes Sudoku nehme
0 [b]3[/b] 0 | 0 0 0 | 0 0 0 0 0 0 | [b]1 9 5[/b] | 0 0 0 0 [b]9 8[/b] | 0 0 0 | 0 [b]6[/b] 0 ------+-------+------ [b]8[/b] 0 0 | 0 [b]6[/b] 0 | 0 0 0 [b]4[/b] 0 0 | 0 0 [b]3[/b] | 0 0 [b]1[/b] 0 0 0 | 0 [b]2[/b] 0 | 0 0 0 ------+-------+------ 0 [b]6[/b] 0 | 0 0 0 | [b]2 8[/b] 0 0 0 0 | [b]4 1 9[/b] | 0 0 [b]5[/b] 0 0 0 | 0 0 0 | 0 [b]7[/b] 0beginnt das programm auch ganz normal, Zahlen auszuprobieren. So erreicht das Programm irgendwann zB den Stand:
1 [b]3[/b] 2 | 6 4 7 | 5 9 8 6 4 7 | [b]1 9 5[/b] | 3 2 9 0 [b]9 8[/b] | 0 0 0 | 0 [b]6[/b] 0 ------+-------+------ [b]8[/b] 0 0 | 0 [b]6[/b] 0 | 0 0 0 [b]4[/b] 0 0 | 0 0 [b]3[/b] | 0 0 [b]1[/b] 0 0 0 | 0 [b]2[/b] 0 | 0 0 0 ------+-------+------ 0 [b]6[/b] 0 | 0 0 0 | [b]2 8[/b] 0 0 0 0 | [b]4 1 9[/b] | 0 0 [b]5[/b] 0 0 0 | 0 0 0 | 0 [b]7[/b] 0Da das ja ein ungültiges Sudoku ist wird weiter "gebacktrackt", bis Folgendes Sudoku entsteht:
1 [b]3[/b] 2 | 6 4 7 | 5 9 8 9 8 0 | [b]1 9 5[/b] | 3 2 9 0 [b]9 8[/b] | 0 0 0 | 0 [b]6[/b] 0 ------+-------+------ [b]8[/b] 0 0 | 0 [b]6[/b] 0 | 0 0 0 [b]4[/b] 0 0 | 0 0 [b]3[/b] | 0 0 [b]1[/b] 0 0 0 | 0 [b]2[/b] 0 | 0 0 0 ------+-------+------ 0 [b]6[/b] 0 | 0 0 0 | [b]2 8[/b] 0 0 0 0 | [b]4 1 9[/b] | 0 0 [b]5[/b] 0 0 0 | 0 0 0 | 0 [b]7[/b] 0Konnte ich vorher mit einem Tastendruck weitere Zahlen einsetzten, hängt sich das Programm hier auf (als wäre es in einer Endlosschleife gefangen).
Mit dem Debugger kenne ich mich leider überhaupt nicht aus. Kann jemand an meinem Quelltext sehen, woran das Problem liegen könnte?
-
Edit:
Das Feld, bei dem sich das Programm aufhängt ist dieses hier:1 [b]3[/b] 2 | 6 4 7 | 5 9 8 9 8 0 | [b]1 9 5[/b] | 0 0 0 0 [b]9 8[/b] | 0 0 0 | 0 [b]6[/b] 0 ------+-------+------ [b]8[/b] 0 0 | 0 [b]6[/b] 0 | 0 0 0 [b]4[/b] 0 0 | 0 0 [b]3[/b] | 0 0 [b]1[/b] 0 0 0 | 0 [b]2[/b] 0 | 0 0 0 ------+-------+------ 0 [b]6[/b] 0 | 0 0 0 | [b]2 8[/b] 0 0 0 0 | [b]4 1 9[/b] | 0 0 [b]5[/b] 0 0 0 | 0 0 0 | 0 [b]7[/b] 0
-
Edit2:
Fehler gefunden.
In Zeile 28 muss es statt
if(arr[x][y]!=0) continue;if(arr[x][y]!=0) { control=true; continue; }heißen
-
Siehste, mit Debugging und insbesondere Debugging-Ausgaben kann man viele Fehler finden
