Hochhausrätsel < Praxis < Informatik < Vorhilfe
|
Hi,
mich beschäftig zur Zeit (ist ja Vorlesungsfreie Zeit ![[klatsch]](/images/smileys/klatsch.gif "[klatsch]") ) Das Lösen von s.g. Hochhausrätseln (Sudoku für Fortgeschrittene). Diese ![[]](/images/popup.gif) sehen so aus.
Es ist eigentlich genau Sudoku. Am Rand stehen Zahlen, die die Eintragungen einschränken. Man stellt sich vor, dass man auf dieser zahl steht und in das Sudoku von der Seite schaut. Jede Zahl n in einem Feld stellt ein n-stöckiges Hochhaus dar. Somit verdecken manche zahlen andere. Die Angabe am Rand gibt an, wie viele solcher Zahlen man "sieht".
Ich habe mir gedacht, diese mit C++ zu lösen.
Ich beschreib mal meine Idee. Ich benutze eine Backtracking um (fast) jede erdenkliche Kombination zu testen. Wenn eine zahl eingetragen wird, wird sofort überprüft, ob sie da hin darf, auch wenn die Zeile noch nicht ganz ausgefüllt ist. Der Quelltext befindet sich hier.
Vielleicht interessiert sich ja auch jemand für das Problem.
Das ist jetzt nicht direkt eine drigende Angelegenheit. Vielleicht sieht jemand etwas, was den Algo schneller macht. Bis jetzt spuckt er keine Lösung aus. Läuft aber so wie ich das einschätze prima (nur lange).
Mittlerweile arbeite ich an einer intelligenteren Lösung, die die Logik dieser Rätsel ausnutzt und pro Feld sich merkt, welche Zahlen hinein darf und welche nicht.
|
|
| |
|
Hallo wieschoo,
ich habe Deinen Algorithmus nicht kontrolliert. Schon die Beschreibung klingt zu sehr nach "brute force".
Diese Hochhausrätsel mache ich gerne, meist auf BrainBashers. Da gibts einen hohen Komfort an Eingabemöglichkeiten, z.B. "kleine" Ziffern. Im Normalfall mache ich das tägliche 7er- und 8er-Rätsel, Stufe "hard".
Ein paar logische Überlegungen sind doch ganz gut zu programmieren:
1) Wo kann die höchstmögliche Zahl in jeder Spalte und Reihe stehen? Da gibts oft ein paar Sofortlösungen.
2) Wo steht die zweithöchste Zahl? Auch da gibt es oft direkt einige Funde.
3) Die Sudoku-Techniken "X-Wing" und "XY-Wing" lassen sich auch relativ leicht implementieren. (Beschreibung auch auf der verlinkten Website, unter Sudoku Help)
4) "genaue Treppen": aufsteigende Folgen von n Zahlen auf n Feldern; auch bei Futoshiki oft gebraucht.
5) "locked sets": Kombinationen von n Feldern in einer Reihe oder Spalten, in denen eine Auswahl aus den gleichen n Zahlen steht.
Es gibt noch mehr logische Standardüberlegungen, die man implementieren könnte, aber ich lasse es mal hierbei. Mit einer üblichen Rechenleistungen müsstest du damit schon ziemlich weit kommen.
Grüße
reverend
PS: Ich lasse die Frage natürlich halboffen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:55 Mi 22.12.2010 | | Autor: | wieschoo |
Danke dir für die Webseite. Ich werde das mal einpflegen. Man brauch ja bestimmt nur 8 Zahlen, die fest sind damit Bruteforce schneller geht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:22 Fr 21.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
