SuDoku lösen
-
Für alle, die nicht wissen, was ein Sudoku ist:
http://de.wikipedia.org/wiki/SudokuDa steht ja auch gleich, wie man sowas lösen kann. Ich hab mir da mal ein paar Gedanken gemacht, und ein Programm zur Sudoku Lösung angefangen. Das Sudoku wird aus einer Textdatei eingelesen und in eine 9x9 Felder Matrix geschrieben (das ist auch schon alles fertig) und danach soll es halt gelöst werden.
Die Matrix:int iWert[9][9];Und dann habe ich noch eine 3d-bool-Matrix. Die ersten beiden Dimensionen ([9][9]) sind wieder für die Felder, die dritte[10] für die Lösungsmenge (welche Zahl von 1-9 noch in das Feld kann):
bool bMenge[9][9][10];Die Funktion zum Lösen sieht so aus:
public void Loesen() { bool bFertig = false; int iRunde = 0; while (!bFertig) { if (++ iRunde == 50) break; // Verhinderung Endlosschleife for (int y=0; y<9; ++y) for (int x=0; x<9; ++x) { // Alle Werte, die bereits in der gleichen Reihe/Zeile/Kasten vorkommen werden aus der Lösungsmenge gelöscht for (int i=0; i<9; ++i) if (i != y) this.setMenge(x, y, this.getWert(x, i), false); for (int i=0; i<9; ++i) if (i != x) this.setMenge(x, y, this.getWert(i, y), false); for (int yTemp = (y/3)*3; yTemp < (y/3)*3 + 3; ++ yTemp) for (int xTemp = (x/3)*3; xTemp < (x/3)*3 + 3; ++ xTemp) if (!(yTemp == y && xTemp == x)) this.setMenge(x, y, this.getWert(xTemp, yTemp), false); // Wenn in einer Reihe/Zeile/(Kasten) in 8 Feldern ein Wert ausgeschlossen ist, muss er in das 9. Feld int iMenge[] = new int [11]; for (int i=1; i<10; ++i) iMenge[i+1] = 0; for (int i=0; i<9; ++i) if (i != y) for (int n=1; n<10; ++n) if (this.getMenge(x, i, n)) ++ iMenge[n]; for (int i=1; i<10; ++i) if (iMenge[i] == 0) if (this.getWert(x, y) != i) this.setWert(x, y, i); for (int i=1; i<10; ++i) iMenge[i+1] = 0; for (int i=0; i<9; ++i) if (i != x) for (int n=1; n<10; ++n) if (this.getMenge(i, y, n)) ++ iMenge[n]; for (int i=1; i<10; ++i) if (iMenge[i] == 0) if (this.getWert(x, y) != i) this.setWert(x, y, i); } // Ende for this.WerteAktualisieren(); bFertig = this.IstFertig(); } // Ende while } // Ende Loesen()Hmm, das ist jetzt wahrscheinlich nicht so leicht zu durchschauen^^
Wenn nötig, kommentiere ich das noch ein bisschen.
Aber nun zu meinem Problem:
Das Programm kann fast alle Sudokus lösen, die ich getestet habe. Aber eben nicht alle! Ein Blick ins Inet sagt mir:Wikipedia schrieb:
Bei den meisten eindeutig lösbaren Rätseln, insbesondere den schwierigen, führt diese Methode allein nicht zur Lösung. In diesen Fällen müssen z.B. Paare oder Tripel von Kandidaten gemeinsam betrachtet werden, um die Kandidatenmengen in einem ersten Schritt zu verkleinern. Alternativ kann, falls in einem Iterationsschritt keine einelementige Kandidatenmenge existiert, aus einer der (kleinsten) Kandidatenmengen eine Zahl ausgewählt werden, um eine der mehreren möglichen Lösungen zu erhalten (Versuch und Irrtum-Methode).
Wie kriege ich jetzt die "Versuch und Irrtum-Methode" in das Programm?
-
Auch wenns jetzt OT ist: Sowas hab ich auch mal gemacht und bin damals an der selben Stelle wie du nun gescheitert
Gruß
-
Das ist Java Code.
-
Ja ich hab es in java geschrieben (woran du das jetzt auch immer erkannt hast
) aber ich dachte hier im c++ forum bekomme ich mehr antworten, darum hab ich die paar sachen, die unterschiedlich sind, umgeschrieben, boolean->bool und so...aber hat keiner eine idee, wie ich try and error in den code reinkriege?
-
Dieser Thread wurde von Moderator/in volkard aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
warum probierste nicht einfach alle sinnvollen Möglichkeiten durch? Eben genau nach try and error Methode oO.
-
Sudoku ist np complete aber wenn nen Algorithmus findest kannst ihn mir gerne schicken.
-
dali schrieb:
Sudoku ist np complete aber wenn nen Algorithmus findest kannst ihn mir gerne schicken.
ohne jetzt mehr als 5 Minuten drueber nachgedacht zu haben, aber koennte man dafuer nicht ein lineares Gleichungsystem in n (bei einem n*n-Sudoku) Unbekannten aufstellen und loesen?
-
Du kannst soviele Gleichungssysteme wie du willst aufstellen aber wie schon gesagt in polynomialer Zeit wirst nicht auf eine Lösung kommen...
-
Du kannst soviele Gleichungssysteme wie du willst aufstellen aber wie schon gesagt in polynomialer Zeit wirst nicht auf eine Lösung kommen...
-
dali schrieb:
Du kannst soviele Gleichungssysteme wie du willst aufstellen aber wie schon gesagt in polynomialer Zeit wirst nicht auf eine Lösung kommen...
Woher willste das wissen? Es ist nicht bewiesen, dass es keinen effektiven Algorithmus für NP-Vollständige Problemstellungen gibt..
-
life schrieb:
dali schrieb:
Du kannst soviele Gleichungssysteme wie du willst aufstellen aber wie schon gesagt in polynomialer Zeit wirst nicht auf eine Lösung kommen...
Woher willste das wissen? Es ist nicht bewiesen, dass es keinen effektiven Algorithmus für NP-Vollständige Problemstellungen gibt..
dali schrieb:
Sudoku ist np complete aber wenn nen Algorithmus findest kannst ihn mir gerne schicken.
-
also widersprichst du dir selber?
-
Gut ok schlecht ausgedrückt... Naja mit blos Gleichungen aufstellen wirst kein NP Problem polynomiell lösen werden können dafür haben sich schon genug Leute damit auseinandergesetzt... Wenn bräuchtest eine superneue tolle Idee und alle Leute die sich auskennen sagen dass es die Idee nie geben wird...
-
java konnte man anhand public void lösen erkennen.
zu deiner abbruchbedingung: du kannst die schleife so lange laufen lassen, wie noch veränderungen stattfinden. das heißt, sobald in einem schleifendurchlauf gar keine neue zahl gesetzt werden konnte, is feierabend.
du berücksichtigst folgendes nicht:
--x --- ---
1-- --- ---
--- 1-- ----1- --- ---
--- --- ---
--- --- ------ --- ---
--- --- ---
--- --- ---da im oberen linken quadrat nirgends anders eine 1 kann, außer an die mit x markierte stelle, kannst du diese dort setzen. dadurch kannst du mehr sudokus lösen.
try and error geht dann mit backtracking. sobald du keine zahl mehr setzen konntest, nimmst du eine stelle (vielleicht die, wo am wenigstens möglichkeiten bleiben) und probierst die erste möglichkeit aus, und lässt dann deinen normalen algo wieder laufen (rekursiv).
gruß mata
-
Immer diese Rekursion
Ich sehe ja ein, dass sowas sinnvoll ist, aber ich durchschaue das immer nicht so ganz. Wenn man es sieht ist es ja nich so schwer, aber selber drauf zu kommen...
Könntest du mir vielleicht mal einen Ansatz für die rekursive Funktion geben?
-
sudoku(feld){ for(alle möglichen zahlen z im feld){ m(feld)=z if(feld != letztes feld) sudoku(feld+1) else lösung m(feld)=leer } }das is es im groben. da kann man dann eben noch deine lösung einbauen, man muss ja nur backtracking nutzen, wenn nix anderes geht.
-
hmm, das müsste bei mir dann so ungefähr so aussehen
public void BackTrack(int iFeld) { for (int i=0; i<9; ++i) { if (getMenge(iFeld % 9, iFeld / 9, i)) setWert(iFeld % 9, iFeld / 9, i); if (iFeld < 81) BackTrack(iFeld + 1); else // Lösung ??? setWert(iFeld % 9, iFeld / 9, 0); } }aber was mache ich jetzt bei Lösung?
Einfach den ganzen Kram reinkopieren, den ich am Anfang gepostet hab?Und ist das jetzt überhaupt noch so, dass das in zumutbarer Zeit fertig wird? Es sieht irgendwie aus, als würde es 81 ineinander verschachtelte for Schleifen produzieren...