Anmerkungen zu den Algorithmen
Mahjong
Aufbau des Shisen-Spielfelds:
Es wird kein Backtracking benötigt um ein garantiert lösbares Spielfeld aufzubauen. Das Spielfeld wird dazu zunächst mit allen benötigten Steinen belegt. Die Steine haben zu diesem Zeitpunkt jedoch noch keinen Typ / tragen noch kein Symbol. Es wird nun das Spiel gelöst, indem immer zwei beliebige (zufällig) gewählte Steine, die legal entfernt werden können aus dem Spiel genommen werden (der Typ der Steine spielt hierbei, wie gesagt noch keine Rolle, sondern nur die Lage der Steine). Dabei wird beiden Steinen jeweils derselbe Typ zugordnet (so dass am Ende jeweils 4 Steine denselben Typ haben).
Um nicht allzuviele direkt nebeneinanderliegende Stein-Paare zu erzeugen, wie es mit dem obigen Ansatz der Fall wäre, werden bei der Wahl des jeweils ersten Steins eines zu enfernenden Paares, solche Steine bevorzugt, die nicht vollständig von anderen Steinen "umzingelt" sind. Bei der Wahl des zweiten Steins werden solche Steine bevorzugt, die möglichst weit vom ersten Stein entfernt liegen. Es sind daher einige Iterationen über alle (jeweils noch vorhandenen) Steine nötig, bis alle Steine entfernt und ihnen ein Typ zugeordnet werden konnte - ein Backtracking ist aber nicht nötig, da immer (d.h. aus jeder Stellung heraus) ein nächstes Paar entfernbarer Steine gefunden werden kann, bis schließlich alle Steine entfernt wurden. Nach Abschluss kann das Spiel dann mit den typisierten Steinen aufgebaut werden.
Aufbau des Mahjong-Spielfelds:
Das Verfahren funktioniert ganz ähnlich, wie oben beim Shisen-Spiel beschrieben. Allerdings gibt es beim Mahjong die zusätzliche Problematik, dass sich Steine blockieren können indem sie übereinander liegen. Dadurch könnte es zu unlösbaren Stellungen kommen - z.B. wenn die letzten beiden Steine aufeinander liegen. Um wiederum ein potenziell langwieriges Backtracking zu vermeiden wird folgender Ansatz gewählt:
Zunächst wird für jeden Stein s bestimmt, wieviele Steine direkt unter ihm in einer senkrechten Reihe liegen (d.h. von oben gesehen vollständig von ihm verdeckt sind):
f(s).
Desweiteren wird für jeden Stein s bestimmt, wieviele weiteren Steine darunter direkt oder indirekt durch diesen Stein blockiert sind ("blockiert" ist hier nur in dem Sinne gemeint, dass ein Stein ganz oder teilweise auf einem anderen liegt):
p(s).
Anmerkung: f(s) und p(s) verändern sich für einen Stein s nicht (bis er aus dem Spiel genommen wird).
Zu jedem Zeitpunkt t ergibt sich damit aus der Anzahl der noch im Spiel befindlichen Steine n(t) auch die Anzahl der Steine die nicht von einem Stein s verdeckt sind:
u(s,t) = n(t) - (f(s) + p(s) + 1).
Sollte es zu einem Zeitpunkt t einen Stein s geben, für den gilt:
u(s,t) = f(s) + 1,
so muss dieser Stein als nächster entfernt werden. Sollte es mehrere solcher Steine geben ist es egal welcher davon gewählt wird.
Anmerkung: Als zweiter kommt dann nämlich nur der jeweils andere in Frage. Sollte für einen Stein s gelten u(s,t) < f(s) + 1, so kann das Spiel nicht gelöst werden, dies sollte aber mit dem gerade beschriebenen Verfahren niemals auftreten.
Erläuterungen (kein Beweis): p(s) ist nur indirekt interessant, um jeweils die übrigen Steine u(s,t) zu berechnen. Knackpunkt sind jeweils die Steine die direkt unter einem Stein s liegen (f(s)) - für diese muss es genug freie übrige Steine geben, um sie abräumen zu können. Die weiteren blockierten Steine p(s) haben dann entweder eine gerade Anzahl und lassen sich somit gegeneinander aufheben, oder es gibt außerhalb dieser Gruppe noch mindestens einen Stein mit dessen Hilfe sich diese Steine abräumen lassen (dieser zweite Fall kommt beim klassischen Mahjong allerdings nicht vor).
Feedback
Freue mich über eure Meinungen, Anregungen, usw.
Mail-Adresse
Feedback-Formular
Patrick Rammelt, 2014