oRigin Geschrieben 20. Januar 2010 Teilen Geschrieben 20. Januar 2010 Hallo, da ich mir autodidaktisch C# beigebracht habe und noch nicht so viel Übung darin habe, steh ich vor einem für mich schwierigen Problem. Wie der Titel schon sagt versuch ich eine Abzählmethode für Sudokus zu programmieren! Man hat also entweder zb. ein leeres 2x2-Sudoku ( also die Zahlen 1-4 ) oder ein zb. ein schon besetztes 3x3- Sudoku( zb. die ersten beiden Blöcke sind schon mit Zahlen besetzt ). Die Frage ist jetzt, wie kann ich anhand dieser Beispiele die versch. Möglichkeiten ausrechnen, mit Hilfe eines Computers. Also wie könnte ein solches Programm aussehen, dass mir die 288 möglichen 4er-Sudokus ausrechnet? Das Programm soll also schauen, wie viele richtig ausgefüllte (!) Sudokus es mit den Vorgaben gibt ( egal ob es viele oder gar keine sind!Das Prinzip sollte hier das gleiche sein. ) Mir fällt dazu kein Prinzip mit Schleifen oä. ein! Ich hab aber schon die Methoden um eine Sudoku zu lösen ( rekursiv* ) und zu überprüfen ob ein Sudoku richtig besetzt ist. Kann mir hier jmd. helfen? oRigin *Backtracking Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 20. Januar 2010 Teilen Geschrieben 20. Januar 2010 Das Lösen von beliegen Sudokus ein NP-hartes Problem, das sich somit nicht mehr effizient lösen lässt Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
oRigin Geschrieben 20. Januar 2010 Autor Teilen Geschrieben 20. Januar 2010 ja, ich brauch zum Glück nicht das von einem höheren Sudoku als der Ordnung 3. Ich würde mich auch schon mit dem Prinzip zufrieden geben. Also wie ich die Zahl 288 programmiertechnisch bei einem 2x2 Sudoku herausfinde. Ich brauch nur das Prinzip um alle möglichen kombinationen einsetzten zu können. Die einzelnen Felder hab ich in einem Array gespeichert, also insgesamt 16 Stück. Ich kann überprüfen ob ein Sudoku richtig ist und ich kann es Lösen. Da ist nur das Problem, wenn ich ein leeres Sudoku lösen lasse, dann gibt es mir nur eine Lösung, aber ich will wenigstens die anzahl aller möglichen lösungen herauskriegen! Also wie kann ich basteln, dass ich die Zahl 288 als Resultat erhalte? PS:es geht mir hier hauptsächlich um das Prinzip "brute force" alle ausgefüllte sudokus ausrechnen zu können. Der Zeitaufwand ist hier unwichtig, da ich es nur bei einem kleinen Sudoku ausprobieren werde ( also 288 Lösungen ) und nicht bei höheren. Das Prinzip ist wichtiger Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 20. Januar 2010 Teilen Geschrieben 20. Januar 2010 Du musst halt "jede" Möglichkeit durcharbeiten, d.h. Du musste jede Permutation einer Reihe, Spalte und eines Quadrates erzeugen und diese verwenden, wenn sie korrekt ist. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
oRigin Geschrieben 20. Januar 2010 Autor Teilen Geschrieben 20. Januar 2010 Da reichen die Permutation ja wohl nicht aus! Vor allem habe ich bei einem leeren 4x4 Sudoku keine Sachen zu permutieren, also auszutauschen. Das bräuchte ich um reduzieren zu können, das hab ich aber bereits gemacht. Ich bräcuhte bloß eine kleine Schleife, die alle möglichen Kombination für eine bestimmte Anzahl von Feldern ausprobiert. Und selbst wenn ich bloß immer die Zahl 111111111111111 einsetze und die bis 999999999999999 inkrementiere. Selsbt das kann ich nicht ausprobieren, da ich keine Funktion kenne, mit der ich die 16 1er in einzelne Arrays speichern könnte :-(. Die Splitfunktion geht nicht. Vorerst wäre ich auch mit dem zufrieden, aber ich bräuchte auch eine bessere Lösung. Ich weiß nicht wie ich den Baum programmieren soll: also zb. [man geht hier eine Reihe runter ab!] 1.Lücke: die 1,2,3,4 kann man einsetzen! also 4 Möglichkeiten --> 1 geht rein 2.Lücke: 2,3,4 --> 2 geht rein 3.Lücke: 3,4 --> ... ... ... und dann wieder von vorne, allerdings mit der 2. es teilt sich alles auf wie ein Baum, aber ich weiß nicht, wie ich das programmiere soll. Wie viele Möglichkeiten ein einzelnes Feld hat OK, aber nicht wie ich das dann alles abgehen könnte!!! help! oRigin Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
oRigin Geschrieben 21. Januar 2010 Autor Teilen Geschrieben 21. Januar 2010 yo ich hab die Lösung selbst gefunden :-D man muss einfach bei der rekursiven Methode, falls das letzte feld regelkonform ausgefüllt wurde, inkrementieren und alle lösungen notieren. natürlich gibts noch ein paar kleinigkeiten, die man beachten sollte. Falls da jmd. ne Frage hat, PM an mich. thx Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.