Backtracking Algorithmus
-
Hallo Leute,
ich weiß, dass es bei google unzählige Treffer zu diesem Thema gibt, allerdings möchte ich eine Lösung nicht einfach copy-pasten.Das Programm schreibe ich zur Übung. Ich habe bisher nicht viel erfahrung mit C++.
Mein Ansatz ist Folgender:
(Eine Funktion, die überprüft, ob das Sudoku gültig ist, habe ich schon geschrieben)
int arr[9][9]; //sudokufeld, global (also außerhalb einer Funktion erstellt) //0 bedeutet, das Feld ist leer //backtracking funktion for(int y=0;y!=9;++y) { for(int x=0;x!=9;++x) { } }Mit diesen beiden Schleifen gehe ich das Feld zeilenweise ab.
Als erstes Suche ich ein unbesetztes Feld:for(int y=0;y!=9;++y) { for(int x=0;x!=9;++x) { if(arr[x][y]==0) { } } }In dieses Feld setze ich jetzt systematisch die Zahlen von 1 bis 9 ein
for(int y=0;y!=9;++y) { for(int x=0;x!=9;++x) { if(arr[x][y]==0) { for(int a=1;a!=10;++a) { arr[x][y]=a; } } } }Dann wird geprüft, ob das Sudoku durch das Einsetzten der neuen zahl noch gültig ist
bool erfolg=FALSE; //Kontroll variable
for(int y=0;y!=9;++y)
{
for(int x=0;x!=9;++x)
{
if(arr[x][y]==0)
{
for(int a=1;a!=10;++a)
{
arr[x][y]=a;if(pruefen()) //wenn das sudoku so gültig ist
{
controle=TRUE
break; //schleife verlassen und nächstes feld verlassen
}
}
if(control==FALSE)
{
//FEHLER
}
else
control=FALSE; //control zurücksetzen
}
}
}
[/cpp]
Mein Problem ist jetzt, dass ich nicht "backtracken" kann. D.h. wenn alle Zahlen von 1 bis 9 für das aktuelle Feld kein gültiges Sudoku liefern, müsste ich ja im zuletzt bearbeiteten Feld den Wert um 1 erhöhen.
Ich habe bei meinem Programm jetzt folgendes Versuchtif(control==FALSE) { //FEHLER arr[x][y]=0; //aktuelles Feld auf 0 zurück setzten x=x-1; //ein Feld zurück gehen if(x<0){x=8;--y;} for(zahl=arr[x][y]+1;zahl!=10;++zahl) //wert im vorletzten Feld erhöhen, bis if(pruefen()) //sich ein gültiges Sudoku ergibt break;Das Problem dabei ist natürlich, dass ich mit dieser Methode nur EIN Feld zurück gehen kann.
Hat jemand eine Idee, wie ich diese Backtracking Methode implementieren könnte?
Und nehmt Rücksicht darauf, dass ich nicht wirklich viel C++ kann
Bin für alle Ideen offen!
Mfg Sudokumaster
-
*edit:
der unformatierte Codeschnipsel oben sollte wie Folgt aussehen
bool erfolg=FALSE; //Kontroll variable for(int y=0;y!=9;++y) { for(int x=0;x!=9;++x) { if(arr[x][y]==0) { for(int a=1;a!=10;++a) { arr[x][y]=a; if(pruefen()) //wenn das sudoku so gültig ist { controle=TRUE break; //schleife verlassen und nächstes feld verlassen } } if(control==FALSE) //wenn keine gültige Zahl gefunden wurde { //FEHLER } else control=FALSE; //control zurücksetzen } } }
-
Hmm... Um jz alles zu lesen bin ich ein wenig zu faul...
Aber hier mal ein paar Tips:Sudokumaster schrieb:
bool erfolg=FALSE; //FALSE ist nen makro aus irgend nem windows-header auf false - also kannste das auch gleich nehmen for(int y=0;y!=9;++y) { for(int x=0;x!=9;++x) { if(arr[x][y]==0) //prüf doch auf != 0 und mach dann nen continue - da hat man ne einrückungsebene weniger... { for(int a=1;a!=10;++a) { arr[x][y]=a; if(pruefen()) //wenn das sudoku so gültig ist { controle=TRUE //e zu viel + semikolon vergessen + marko genutzt... break; //schleife verlassen und nächstes feld verlassen } } if(control==FALSE) //wenn keine gültige Zahl gefunden wurde { //wieder das hässliche makro... //FEHLER } else control=FALSE; //control zurücksetzen //control ist hier also auf jeden fall auf false gesetzt... könnte man also auch schon am anfang der schleife machen... } } }würde man also besser so schreiben:
bool erfolg=false; for(int y=0; y != 9; ++y) { for(int x=0; x!=9; ++x) { if(arr[x][y]!=0) continue; control=false; //control zurücksetzen for(int a=1;a!=10;++a) { arr[x][y]=a; if(pruefen()) { control = true; break; //schleife verlassen und nächstes feld verlassen //der kommentar klingt ein wenig komisch - überhaupt solltest du die schleife doch nicht gleich ganz verlassen, nur weil der eine wert nicht gestimmt hat... } } if(! control) //wenn keine gültige Zahl gefunden wurde { //FEHLER } } }machen wir mal ein wenig weiter:
int arr[9][9]; //sudokufeld, global (also außerhalb einer Funktion erstellt) //0 bedeutet, das Feld ist leerübergib es doch besser immer an die Funktionen - globale Variable sind hässlich und erzeugen oft Fehler und sind immer daran schuld, dass man net mehr durchsieht -.-
außerdem würde ich es so machen:
bool arr[9]/*x*/[9]/*y*/[9]/*moeglichkeiten*/;für alle unbekannten felder initialisiert du einfach die 3. dimension komplett mit true - also es könnten alle 9 zahlen drin stehen
-> so lange in der 3. dimension mehr als einmal true steht sind noch mehrere möglichkeiten offen - wenn nur einmal true vorkommt, steht die zahl fest und bei nur false ist es nicht möglich das soduko zu lösen...du gehst also dann das ganze feld durch und schließt immer die zahlen aus, die nicht mehr hinkommen dürfen, überprüfst also:
- zeilen
- spalten
- quadratedas ganze wirst du wahrscheinlich mehrfach machen müssen - wie oft sollte vom soduko abhängig sein - maximalstens [i]hmm...[i] - kommt drauf an ^^
dein ansatz würde ewig dauern da du so weit ich das sehe alle möglichkeiten durchgehen möchtest - da wird selbst der tollste rechner paar jahre brauchen xD
selbst wenn bei einem 9x9 feld 50% der felder gegeben sind müsstest du noch 40 felder durch bruteforce rausbekommen...
würdest also schon 40^9 möglichkeiten haben - also über 262 billionen - müsstest also auch so oft das feld testen...bb
-
Danke für deine Antwort!
ich hoffe ich habe deinen Vorschlag richtig verstanden:
zuerst habe ich ein array erstellt:
bool field[9][9][9];
Dann habe ich ALLE felder auf true gesetzt.
Dann habe ich alle Felder, die nicht unbelegt sind (also != 0) in der 3. Dimension mit false belegt, bis auf die Stelle, der dem Wert an der Stelle entspricht.
Beispiel:for(int y=0;y!=9;++y) { for(int x=0;x!=0;++x) { if(arr[x][y]) //wenn feld belegt { for(int z=0;z!=9;++z) field[x][y][z]=false; //die 3. Dimension an der Stelle gleich false setzen if(arr[x][y]==1) // field[x][y][0]=true; // die stelle, die dem wert des Feldes entspricht if(arr[x][y]==2) // wieder auf true setzen field[x][y][1]=true; // //usw }Damit ist das array schonmal initialisiert.
Dann gehts ans prüfen. Wenn ich alles richtig verstanden habe, müsste folgende Funktion stimmen, oder?//zeilen prüfen int control=0; int zc; //copy von z for(int y=0;y!=9;++y) { for(int x=0;x!=9;++x) { control=0; for(int z=0;z!=9;++z) { if(field[x][y][z]==true) //durchzaehlen, wie viele offene Möglichkeiten es an der stelle gibt { ++control; zc=z; } } if(control==0) return 1; //unloesbar if(control==1) //das feld [x][y] ist eindeutig { for(int g=0;g!=9;++g) { if(g!=x) //alle felder der Reihe außer dem mit nur field[g][y][zc]=false; //einer möglichkeit an der stelle zc 'false' setzten } } } }ist das von der idee her richtig?
-
Hi ^^
for (int y (0); y != 9; ++y) { for (int x (0); x != 9 ; ++x) // { if (arr[x][y]) { //ein bestimmter Wert ist gesetzt for (int z (0); z != 9; ++z) field[x][y][z] = false; //alle Stellen auf false setzen field[x][y][arr[x][y]] = true; //und nur das eine auf true setzen continue; //dann gehen wir zum nächsten Feld } //wenn wir hier hin kommen, ist das feld nicht gesetzt for (int z (0); z != 9; ++z) field[x][y][z] = true; //wir setzen also alles einfach auf true } }field[x][y][arr[x][y]] = true;ist zwar ein bisschen hässlich, aber man kann ja nicht alles haben ;o)
würde auch mit 2 for schleifen gehen, also in etwa so was:int z = 0; for (int end (arr[x][y]); z != end; ++z) field[x][y][z] = false; field[x][y][++z] = true; for (++z; z != 9; ++z) field[x][y][z] = false;ich weiß aber nicht genau ob das eleganter ist - musst du selbst entscheiden, was du hübscher findest, was du besser verstehst oder was auch immer ^^
Sudokumaster schrieb:
Damit ist das array schonmal initialisiert.
Dann gehts ans prüfen.Sudokumaster schrieb:
Wenn ich alles richtig verstanden habe, müsste folgende Funktion stimmen, oder?
Hmm.. Ich meinte das eigtl ein wenig anders... ^^
for (int y (0); y != 9; ++y) { for (int x (0); x != 9; ++x) { /*die zeile durchgehen und jedes mal, wenn ein feld nur ein true hat, alle felder in dem gleichen quadrat, in der gleichen zeile und in der gleichen spalte, an der stelle, wo das true bei dem einen feld steht, auf false setzen*/ } }bb
edit:
aber wenn du möchtest, dann kannst du es auch so machen, wie du es gemacht hast - ich denke, es geht so, wie du es gemacht hast ^^
nur ist es eben wieder nicht sooo übersichtlich ;-Paber ich würd das schleifeninnere anders machen ^^:
int control = 0; int copy_z; for (int z (0); z != 9; ++z) { if (field[x][y][z]) { ++control; copy_z = z; } } if (!control) return 1; //unloesbar if (control == 1) //das feld [x][y] ist eindeutig { int x2 (0); for(; x2 != x; ++x2) { field[x2][y][copy_z] = false; } for(++x2; x2 != 9; ++x2) { field[x2][y][copy_z] = false; } }