TmpDir - Mi 06.12.06 11:15
Titel: Einstieg, aber wo? Rekursion oder andere Bäume?

---

Hi,

Das Ausgangsproblem ist im folgenden Bild dargestellt:




Ok, wie man sieht geht's um Zocken. Und es wird wohl auch klar sein, das hier ein Lösungsalgo gefunden werden soll. (Ja, den Spass wollte ich mir nicht entgehen lassen, nachdem ich festgestellt habe, das ich morgens um 2 doch zu blöd bin sowas manuell zu lösen 8) .)

Regeln:
- Blöcke von mindestens 2 gleichen Steinen können entfernt werden.
- Die Steine hören auf die Schwerkraft und fallen alle nach unten so weit als möglich.
- Leere Spalten werden zusammengeschoben
- Ein Feld ist immer Lösbar!

Mir ist es auch gelungen einen Rekursive Funktion ( :D ) zu schreiben, die das macht was ich will. Sie ackert quasie der Reihe nach alles durch was möglich ist, bis was gefunden wurde. Ohne Rücksicht auf irgendwas.
ABER bei geschätzten (160/2.5)^70 = 2,7076852481648582613070451017022e+126 durchschnittlichen Versuchen um alle Lösungsmöglichkeiten zu durchsuchen ist mein Rechner doch gut 3 Monate oder länger mit einer Lösungfindung beschäftigt :shock:


Daher die Frage, nach anderen Systemen um

a) eine gültige Lösung zu finden
b) um die optimale/kürzeste Lösung zu finden.
c) wie ein solches Feld generiert wird, damit es immer Lösbar ist.


Tips in Form von fertigen Aplikationen mit Sourcecode und Verfielfätigungsrechten herzlichst Willkommen. :P
Da ich aber Bescheiden bin, würden mir die Leseempfehlungen zu a,b,c schon mehr als reichen.

Mfg

BenBE - Mi 06.12.06 15:58

---

Naja, vereinfache deine Rekursive Methode doch einfach so, dass Du für jeden Schritt die Klicks die möglich sind, auf die Bereiche, anstatt die Felder legst.

D.h. wenn ein Feld min. 2 Steine umfasst, ist es anklickbar, wir vorgemerkt (insgesamt).

2. Lösungen, die offensichtlich nicht mehr lösbar sind, werden möglichst schnell verworfen.
Eine Prüfung hierfür könnte "vorausschauendes Denken" sein, indem Du z.B. prüfst, ob es für ein gegebenes Feld links noch mindestens ein weiteres zugehöriges Feld gibt, dass durch entfernen andersfarbiger Felder zusammengeführt werden kann.

TmpDir - Mi 06.12.06 18:47

---

Hi,
also das mit den Bereichen (1 Klick pro Block) ist schon implementiert.

Das mit dem Vorausschauen muss ich mir mal genauer vornehmen. Ich denke mal du meinst sowas wie eine Zählung der Teile und wenn nur ein Teil von einer Sorte da ist, dann geht's nicht mehr zu lösen.



Was ich mir bei der Fragestellung allerdings gedacht habe, war soetwas wie eine Gewichtung der Züge vornehmen. Deswegen auch die Frage nach dem Baum, da ich mit solchen Themen bisher in keiner Art und Weise in kontakt kam. Aber da hab ich inzwischen schon ein wenig gewikit (?), allerdings ohne wirklich was nutzbares zu finden.


[edit]
Siehe auch "Clickomania" oder "SameGame"

mfg