Bisschen hilfe beim Sudoku Lösen benötigt

[Simon93]

Hey Leute,
ich möchte in Java ein Sudoku Programm schreiben (besser: ich SOLL es für die schule...) und jetzt sitz ich hier, und habe mir die "Dancing Links" Methode ausgesucht (siehe: sudokugarden.de). Also ein Int Array mit int[729][324] erzeugt. Soweit kein Problem.
Es gilt ja das exakt Cover Problem zu lösen. B0 heißt in Kästchen 1 steht die Ziffer 1, B1 heit in Kästchen 1 steht die Ziffer 2, usw. bis halt B729 heißt, dass in Kästchen 81 eine steht. Ich hatte es so vor, dass von oben erst nach rechts, und dann in der nächsten Zeile wieder nach rechts usw. gezählt wird (nur damit wir uns bei der Kästchennummerierung einig sind...)
So es gilt Allgemein Bx (x ist die Nummer der Kombinationsmöglichkeit) ist in einem bestimmten Kästchen (nennen wir das mal y). Die Ziffer, die dort gespeichert wird ermittle ich mit

int ziffer = (x%9)+1;

Den Kasten zu ermitteln ist auch nicht schwer:

int kasten = ((a-ziffer+1)/9)+1;

Die Spalte muss ich ja so ermitteln:

int spalte = ((kasten-1)%9)+1;

So jetzt kommt aber ein erstes Problem: Wie ermittle ich die Reihe(auf das 9*9 Sudokufeld bezogen)?
Ich bin glaub ich nah dran, komm aber nich drauf...
Ich würd mit Spalte arbeiten und durch 9 teilen, bzw. %9, keine Ahnung, kanns mir einer sagen?

So, dann komm ich zu meiner Tabelle, wie würdet ihr die Spalten machen? Es sind ja immer 324 Bedingungen, jeweils 81 für "Jede Ziffer muss in jeder Spalte einmal vorkommen", "Jeder Ziffer muss in jeder Reihe einmal vorkommen", "Jede Ziffer muss in jedem Block einmal vorkommen", und "In jeder Zelle darf jede Zahl nur einmal stehen" (die letzte müsste mir mal einer erklären....).

Mein erster Anstz für die Spalten ist: Erst kommen 81 Spalten mit z.B. den Reihen (1. Spalte: "Die Ziffer 1 steht in der ersten Reihe", 2. Spalte: "Die Ziffer 2 steht in der ersten Reihe", halt wie in der senkrechten...), dann der Reihe nach Spalten, Blöcke, und Zelle(???:L)
Weil ich das mit dem Zeiger nicht kann, möchte ich einfach zwei Boolean Arrays erstellen, jeweils eindimensional... Zu beginn sind die 729 und 324 Werte alle true, wenn ich ne Spalte oder Zeile "lösche", wird der Wert auf false gesetzt...
So, das wars für erste, wer bis hier gelesen hat, bei dem bedank ich mich schonmal, auch wenn er vlt. nicht helfen kann, oder nur ein Problem lösen kann...

 

[XHelp]

Warum versuchst du nicht einen trivialeren Lösungsansatz: alle Möglichkeiten durchzuprobieren, bis du eine passende Belegung gefunden hast?

 

[Simon93]

Hmm ich möchte eig. immer elegant programmieren, aber ok, wie soll ich das stumpfe ausprobieren machen?
Einfach ein 9*9 Array erzeugen, die vorgegeben Werte eintragen, die Tabelle mal kopieren und eintragen? Sprich das erste leere Feld suchen, da eine 1 eintragen, die überprüfen, wenn die ok ist, das nächste Feld, sonst ne 2 oder wie?
Ich würde gern ne logikbasierte Lösung verwenden...

 

[XHelp]

Wenn du elegant programmieren willst, dann kannst du das ganze etwas mehr objektorientierter machen.
Nein, das Verfahren läuft etwas anders ab. Schau einfach mal, was du zum Thema "Backtracking" findest.

 

[Simon93]

Ich finde die Dancing Links Methode aber ziemlich gut, daher werd ichs auch erstmal so versuchen, morgen hab ich Info, da werd ich den Typen mal ansprechen, ob der weiter hilft, aber wär super, wenn ihr hier noch ein paar meiner Fragen aus dem ersten Post beantworten könntet...

 

[Marco13]

Schau einfach mal, was du zum Thema "Backtracking" findest.

The "Dancing Links" are a very clever way to do backtracking, and it is non-trivial.

Übrigens gibt es IMHO keinen direkten Zusammenhang zwischen "elegant" und "objektorientiert", wenn es um solche eher number-crunching-artigen Sachen geht, die am besten eh auf einem plain int[] array laufen.

@Topic:

The "Dancing Links" are a very clever way to do backtracking, and it is non-trivial.

Also, da wird wohl spontan kaum jemand eine perfekte Lösung aus dem Ärmel schütteln, und deine Fragen sind ja teilweise schon sehr spezifisch ... das müßte man sich mal näher ansehen... kannst du die erste Frage irgendwie auf http://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm beziehen? (VIELLEICHT(!) würde das helfen...)

 

[Simon93]

Übrigens gibt es IMHO keinen direkten Zusammenhang zwischen "elegant" und "objektorientiert", wenn es um solche eher number-crunching-artigen Sachen geht, die am besten eh auf einem plain int[] array laufen.

Seh ich genau so. Nur was heißt plain int? Ach, das frag ich morgen in der Schule google
Ich komm auch schon voran.

Also, da wird wohl spontan kaum jemand eine perfekte Lösung aus dem Ärmel schütteln, und deine Fragen sind ja teilweise schon sehr spezifisch ... das müßte man sich mal näher ansehen... kannst du die erste Frage irgendwie auf http://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm beziehen? (VIELLEICHT(!) würde das helfen...)

Erstmal danke für den Link, hilft mir grade sehr, werd ich morgen noch genauer studieren.
Aha, die Fragen sind spezifisch... Ich hätte eig. gedacht, dass das für erfahrene Programmiere wie euch ne Minutensache ist... Hauptarbeit: einlesen=)
Ich bin nämlich überhaupt nicht erfahren, habe erst seit diesem Schuljahr Informatik, und vorher nie programmiert...

 

[Marco13]

"plain int[]" ist kein "stehender" Begriff, das soll nur so viel heißen wie "ein einfacher int-array ohne irgendwelche Objektorientierten Abstraktionskonzepte drumrum".

Ich vermute, dass die Frage zu den Indizes, die du da gestellt hast, aus rein Programmiertechnischer Sicht wirklich nicht schwierig ist - aber um rauszufinden, was diese "B0"s und Begiffe wie "Kästchen" in diesem Zusammenhang genau bedeuten, muss man sich ... ja :rtfm: