Ich möchte gern ein Wort in eine quadratische Tabelle einfügen, wobei das Wort vom ersten bis zum letzten Buchstaben in einer „Schlange“ gelesen werden kann.
Ich habe bisher folgendes Vorgehen:
Ich suche mir die nächsthöhere Quadratzahl zu der Länge des übergebenen Wortes int quadratZahl = (int) Math.ceil(Math.sqrt(length));
Dann berechne ich mir einen Startpunkt in meiner Character- Matrix. (Via Random x,y)
Ich benutze zum Merken der aktuellen Position ein Point (X & Y- Wert).
Nun beginnt der Spaß… ich habe mir eine Liste mit den möglichen Himmelsrichtungen gemacht. Point(-1 , 0), Point(1 , 0) etc.
Diagonale Züge sind nicht vorgesehen nur N,S,O,W.
Aus dieser Liste wird nun Random ein Punkt gezogen, der mit der aktuellen Position verrechnet wird. Nun kann ich die neue Position in meiner Matrix prüfen:
Liegt der Punkt noch im Array?
Ist auf der Position schon ein Buchstabe?
Soweit so gut. Das würde auch alles schon funktionieren nun kommen aber die schwierigen Fälle. Ich hab mal kurz meine Paintkünste spielen lassen (s.h. Anhang)
Wenn es jetzt um das Wort „Hallo“ geht, würde es egal sein, in welche Richtung ich mein Wort nun fortführe. Aber wenn ich jetzt z.b. das Wort „HalloDuDa“ hätte, dürfte ich zum Beispiel nur nach Norden, da ich sonst kein Platz mehr hätte.
Bei dem Wort „HalloSie“ könnte ich auch nach Süden, da ich mir ein freies Feld erlauben kann.
Nun ist die Frage, wie ich diese Prüfungen am Besten berechne bzw. wie ich das angehe.
ps. falls es dafür schon etwas gibt, wo etwas ähnliches realisiert wurde, reicht mir ein Link
Ein spontaner Gedanke wäre Backtracking, falls die Worte nicht so lang werden, dass das ineffizient wird. Ansonsten müßte man da wohl etwas mehr Hirnschmalz reinstecken…
Ist das Feld schon vorausgefüllt, so wie in deinem Bild? Oder beginnt es immer mit einem leeren Feld? Was ist der Ziel des Ganzen? Soll die Schlange möglichst zufällig aussehen? Oder ist das Problem, dass einige Buchstaben vorausgefüllt sind und der Rest der Schlange noch irgendwie ins Feld soll?
Ach so, und o. B. d. A. kann man die Buchstaben weglassen und mit einem einfachen Zähler arbeiten, aber das ist dir sicherlich auch schon aufgefallen.
Also das „Feld“ (die Matrix) ist am Anfang komplett leer. Dann wird zufällig ein beliebiges Feld ausgewählt werden, wo die Wortschlange mit dem ersten Buchstaben des Wortes beginnt und ab dann soll sie zufällig durchs Feld gehen, aber so, dass das Wort auch passt. Die Schwierigkeit ist hierbei, wie oben schon angenommen, dass sie net in eine Sackgasse läuft und Buchstaben über hat, die nicht mehr gesetzt werden können
Dann wird das char- Array später nur in JLabeln im Gridlayout dargestellt.
Das Ganze soll einfach nur ein Ratespiel werden, welches Wort angezeigt wird, also nix aufwendiges
@Marco13 o also die Worte ansich sind meistens 10 - 15 Zeichen. Werde mir den Ansatz auch mal anschauen.
Das scheint jetzt im ersten Moment etwas themenfremd, aber… es erinnerte mich an einen Solver für http://en.wikipedia.org/wiki/Polarium (aka http://blackflip.org/ ) den ich mal geschrieben habe. (Oder immernoch schreibe. Seit 2008 oder so :o ). Auch da hat man ein Spielbrett, wo man bestimmte Felder besuchen muss. Gelöst wird das über Backtracking. Einer der entscheidenden Punkte ist, möglichst früh zu erkennen, WANN man backtracken muss. Wenn man ein Feld hat wie
01234
0
1
2PUZZL
3
4
dann kann man schon zu diesem Zeitpunkt feststellen, dass das Wort “PUZZLESPIELLÖSER” dort nicht mehr untergebracht werden kann: Sowohl oben als auch unten gibt es nicht mehr genug freie Felder für “…ESPIELLÖSER”, und einen Weg zwischen Oben und Unten gibt es nicht. (Ich hatte da dann irgendwann eine eigene, kleine Graph-Library gebastelt, mit Kürzesten Wegen, Zusammenhangskomponenten, Max-Flow-Min-Cut-Berechnung und so nem Scheiß, aber das ist hier (d.h. bei kleineren Spielfeldern) vielleicht gar nicht nötig…)
Backtracking käme mir da auch als erstes in den Sinn, allerdings wird es dabei etwas aufwändiger zu gewährleisten, dass alle möglichen Pfade evaluiert werden und keine Pfade doppelt vorkommen.
Allerdings ist eine obere Schranke für die möglichen Lösungen bei vorgegebenem Startpunkt [tex]3^{l-1}[/tex], wobei l die Wortlänge ist. Das macht bei 15 Buchstaben keine 5 Millionen Möglichkeiten, die sich wohl vollständig evaluieren lassen sollten. Dann könnte man alle gültigen Lösungen sammeln und eine davon zufällig auswählen.
Die andere Möglichkeit ist, in jedem Rekursionsschritt eine zufällige Richtung zu gehen, und die bereits beschrittenen Richtungen zu speichern. Bei 3 Möglichkeiten ist das auch überschauber und dürfte deutlich schneller gehen.
Schneller …als was? Ob man die Möglichkeiten systematisch oder zufällig durchprobiert, macht keinen Unterschied, solange es keine Kriterien gibt, nach denen man die „Systematik“ aufbauen könnte.
Ich dachte eben noch kurz an die Warnsdorffregel … http://de.wikipedia.org/wiki/Springerproblem#Warnsdorffregel … würde mich nicht wundern, wenn man die darauf übertragen (oder sogar direkt anwenden) könnte…
Unabhängig davon hat man natürlich immer das Problem, dass beim Backtracking u.U. vieeel doppelt gemacht wird. Man müßte sich genauer überlegen, ob das in diesem Fall auftreten kann, aber… nur zur Verdeutlichung: Angenommen man hat schon ein Wort nach diesem Schema eingetragen (jedes X ist ein Buchstabe, man ist gerade beim ‚*‘),
und müßte noch alle verbleibenden, freien Felder benutzen, um das Wort unterzubringen. Dann wird der Backtracker u.U. stundenlang (oder auch jahrelang - wir wissen, was „exponentielle Laufzeit“ bedeutet ;)) versuchen, den oberen Bereich irgendwie auf verschiedene Arten auszufüllen, aber er wird am Ende IMMER scheitern - weil es unten zwei Sackgassen gibt, und er das Wort nur in einer von beiden beenden kann.
Aber es stimmt schon, bei geringeren Feldgrößen dürfte das noch unproblematisch sein. Aus dem Bauch raus:
4x4 - eine kurze Verzögerung
5x5 - Kaffeepause
6x6 - „Mal schauen, ob er das bis heute Abend schafft“
7x7 - Nope
Schneller als mein zuerst beschriebener Ansatz: vollständige Enumeration aller Lösungen. Dabei hat man natürlich immer die Worst-Case-Laufzeit.
Im Übrigen würde ich die Laufzeiten noch pessimistischer Abschätzen. Bei 6x6 gibt es (pessimistisch geschätzt wie oben!) 5e16 Pfade. Wenn man davon pro Sekunde 1 Mio schafft, ist man läppische 1586 Jahre beschäftigt Auf der anderen Seite ist der Abschätzer aber extrem schlecht und eine fail-fast-Strategie wird dabei auch nicht berücksichtigt…
Ja, das fail-fast ist eben der Knackpunkt. Es gibt IMHO nur drei Möglichkeiten, Backtracking schnell zu machen:
Pruning
Pruning
Pruning
Dummerweise kann es dann passieren, dass man einen Trade-Off eingehen muss. (Zumindest habe ich das beim oben angedeuteten Löser knallhart bemerkt) : Man kann entweder höchsteffizient aber sehr dumm alles durchprobieren. Oder man versucht, möglichst früh zu erkennen, dass man abbrechen muss. Da kann die Berechnung aber SO aufwändig sein, dass man das Finden der Lösung durch den aufwändigen Test (ggf. auch nur für bestimmte Situationen, oder aber eben allgemein) verzögert.
OT: Seit 2009 liegt auf meinem Desktop die angehängte Datei: ALLE dort eingezeichneten Knoten KÖNNEN besucht werden. Und ALLE außer dem Rand MÜSSEN besucht werden. Ausgehend vom rosa-farbenen Knoten ist das nicht möglich. Als Mensch sieht man das recht leicht. Backtracking rechnet sich daran zu Tode. Und es in diesem Zustand zu erkennen ist schwierig…
(s.h. Anhang)
