Abzählmechanismus für Sudoku mit C#

[oRigin]

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

[flashpixx]

Das Lösen von beliegen Sudokus ein NP-hartes Problem, das sich somit nicht mehr effizient lösen lässt

[oRigin]

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

[flashpixx]

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.

[oRigin]

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

[oRigin]

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