Intern

[in Bearbeitung]

In diesem Abschnitt wird der interne Lösungsalgorithmus vorgestellt und Probleme die während der Programmierung aufgetreten sind:

1. Der Lösungsalgorithmus

Die Lösungen der Stufe 1 und Stufe 2 sind trivial, deshalb wird hier lediglich der Algorithmus zur Lösung der 3. Stufe beschrieben.

1.1 Das Gleichungssystem

Def.: Ein Feld wird als VF (Variablefeld) bezeichnet, wenn der Zustand (vermint/minenfrei) noch nicht bekannt ist, und mind. ein Nachbarfeld offen ist. Aus ihnen werden die Variablen xi Î Wx = {0,1} gebildet, mit 1 £ i £ n (n: Anzahl der Variablenfelder)

Def.: Ein Feld wird KF (Konstantenfeld) genannt, falls es offen ist und min. eins der Nachbarfelder noch verdeckt ist. Aus ihnen werden die Konstanten bj Î Wb = {0,1, ... <Anzahl Nachbarfelder>} gebildet, mit1 £ j £ m (m: Anzahl der Konstantenfelder)

Def.: A ist eine n x m - Matrix, mit aij = {1, falls xi ein Nachbarfeld von bj ist; 0, sonst}, aij Î Wa

Þ Das zu lösende GLS (Gleichungssystem) lautet: A x = b mit A Î {0,1}n ´ m, x Î Wx n, b Î Wb m

1.2 Lösung des Gleichungssystems

Das GLS läßt sich leider nicht mit dem Gaußalgorithmus lösen, da der Lösungsraum nicht reell sondern ganzzahlig ist. Tatsächlich ist das Problem sogar NP-vollständig, wie Richard Kaye bewiesen hat.

Das besagt nichts anderes, als daß es keinen Algorithmus geben kann der das Problem mit polynomischen Aufwand löst. Somit muß man sich mit einem optimierten Algorithmus zufrieden geben, der zwar in der Regel sehr schnell sein kann im „Worst Case“ jedoch exponentiellen Aufwand besitzt. Es sei denn jemand beweist das P = NP und sackt nebenbei noch eine Million Dollar ein.

1.3 Erste Optimierung - Zusammenfassung von Variablen

Haben zwei Var. xi1 und xi2 diesselben Konstanten als Nachbarn, sprich die Zeilen i1 und i2 von A sind identisch, dann kann eine von beiden Var. inkl. der Zeile in A ersatzlos gestrichen werden.

1.4 Zweite Optimierung - Gruppen von Konstanten zusammmenfassen

Treten zwei Konstanten bj1 und bj2 immer nur gemeinsam als Nachbarfelder von Variablen auf, sprich die Spalten j1 und j2 aus A sind identisch, dann können diese zu einer neuen bj3 zsmgefaßt werden. Dabei ändert sich der Wertebereich der anliegenden Variablen von {0,1} in {0,1,2}. Werden mehr als zwei Kf zsmgefaßt oder hängt ein VF an mehreren KF-Gruppen, dann erhöht sich der Wertebereich entsprechend.

1.5 Dritte Optimierung - Inseln bilden

Def.: Zwei VF xi und xk heißen „direkt zusammenhängend“, falls es min. ein gemeinsames KF bj gibt.

Def.: Zwei VF xi und xk heißen „zusammenhängend“, falls es eine Folge von VF xi1, ... , xil gibt mit xi und xi+1 (0 <= i <= l-1) sind direkt zusammenhängend und xil = xk.

Def.: Alle mit einem VF zusammenhängenden VF'er bilden eine Insel

Beh.: Eine Zerteilung des GLS in Inseln entspricht einer Art Diagonalisierung von A.

Þ Es genügt nun diese Inseln zu lösen.

1.6 Vierte Optimierung - Aufteilung der Inseln

Zu jeder Insel I wird nun eine möglichst kleine Teilmenge I0 gesucht, so daß der Rest der VF in nicht zshg. (möglichst gleichgrosse) Teilinseln I1, I2,... zerfällt. Nun brauchen nicht mehr alle Komb. für I durchlaufen werden, sondern nur noch alle I0 (-> besser Formulieren). Für eine bel. Komb. der Var. aus I0 sind die Lsg. der Teilinseln I1, I2,... paarweise unabhängig. Die Teilinseln werden anschließen weiter aufgeteilt.

1.7 Einbeziehung der Restminenzahl

Auch die Restminenzahl, die links oben angezeigt wird, enthält eine Information, die zur kompletten Lösung mit ausgewertet werden müssen. Wollte man diese Information mit in das Gleichungssystem miteinbausen, dann müsste man zunächst auch verdeckte Zellen, die keine offene Zelle als Nachbarn haben zu den VF zählen. Da diese jedoch nicht unterscheidbar sind könnte man sie zu einer Zelle zusammenfassen.

Mein Lösungsalgorithmus arbeitet nun so, daß er in zwei Durchgängen arbeitet. Beim ersten wird die Restminenzahl nicht beachtet. Werden dabei Lösungen gefunden die mit der Restminenzahl im Widerspruch liegen, so wird ein zweiter Durchlauf gestartet, bei dem nur die gültigen Lösungen beachtet werden.

Frage: Warum nicht beim 1. Durchlauf nur die gültigen Lösungen beachten?

----- nachtrag -----------------------------------

- Nach jeder Kombination alle Konsequenzen bestimmen

2. Probleme bei der Markierung von Feldern

Die problemlose Einteilung der Stufen funktioniert nur solange noch keine Felder falsch markiert sind, d.h. die die Flagge <Bild> ist gesetzt, obwohl es keine Mine in dem Feld liegt. Ist dies der Falls, sollte gewährleistet sein, daß nicht durch die Stufenanzeigen <Smileybilder> eine Feldzustandsbestimmung möglich ist.

Die naheliegenste Lösung wäre, diese Markierungen/Flaggen zu ignorieren. Allerdings könnte man dann in einer schwierigen Situation (z.B. 3. Stufe) durch markieren von bel. VF die 2. Stufe ereichen und wüßte dann, daß in dem entspr. Feld eine Miene liegt. <Bild - - x, 1 2, 0 1

Markierte Felder können in drei Typen unterteilt werden:

Gibt es Felder der letzten beiden Typen, so ist die Einordnung des Spielzustandes in eine Schwierigkeitsstufe erstmal nicht eindeutig. Folgende Lösungsansätze liegen auf der Hand:

2.1 Erste Lösungsansatz: Falsch markierte Felder ignorieren

Problem: Durch probeweise setzen einzelner Markierungen könnte u.U. der Zustand von einem oder mehreren Feldern bestimmt werden. z.B.

x

1 2

0 1

Dies entspricht aber nicht dem Sinn der Stufenanzeige.

Frage: Müßten dann auch die zufällig richtigen/falschen Markierungen ignoriert werden?

2.2 Zweiter Lösungsansatz

Markierte Felder tragen nicht zur Stufeneinteilung bei, es zählen alleine die aufgedeckten Felder.

Pro: Auch das Spielende wird alleine durch die aufgedeckten Felder bestimmt. Somit würde diese Lösung ins allg. Konzept passen.

Kontra: Es spielt sich etwas merkwürdig, wenn man sich in Stufe 1 befindet, aber erst eine Markierung der 2. Stufe (nach altem Prinzip) setzen müßte um dies zu sehen.

2.3 Endgültige Lösung

Für die Stufeneinteilung für Stufe 1 und Stufe 2 wird so getan, als ob alle Markierungen richtig wären.

Für die 3. Stufe ist dieses nicht nötig, da dort nur noch bestimmt werden muß, ob der Spieler alle bestimmbaren Zustände richtig erkannt hat oder nicht.

Mit dieser Lösung sind die Probleme der ersten beiden Ansätze überwunden.

(Gruppen anzeigen? -> nr oder hex-pfadnr)

(Var. + Cond. anzeigen)