Minesweeper < Künstl. Intelligenz < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Betrachten Sie das Spielfeld aus dem bekannten Spiel Minesweeper. Ziffern zwischen 0 und 8 geben die genaue Anzahl der Minen in direkt benachbarten Felder an. Ausserhalb des gegebenen Spielfeldes und auf mit Ziffern gekennzeichneten Feldern liegen keine Minen. Auf jedem weiteren Feld liegt maximal eine Mine. Gesucht ist eine mit den Angaben konsistente Belegung des Spielfeldes mit Minen.
1. Nehmen Sie an, dass die einzelnen Variablen mit ganzen Zahlen belegt werden. Formulieren Sie das Problem als CSP indem sie jedes Constraint als einzelne Formel aufschreiben. Geben Sie die Definitionsbereiche der Variable an.
2. Berechnen sie eine Lösung unter Verwendung von Forward checking. (8 + 6 Punkte) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo Leute,
hier mal meine Formulierung als CSP:
1)
Die einzelnen Variablen haben true oder false: true für "Es liegt eine Mine auf der Variablen" und false für das Gegenteil.
Meine Constraints:
0 = |A [mm] \vee [/mm] B [mm] \vee [/mm] E [mm] \vee [/mm] H [mm] \vee [/mm] G|
1 = |B [mm] \vee [/mm] E [mm] \vee [/mm] H [mm] \vee [/mm] K [mm] \vee [/mm] L [mm] \vee [/mm] F [mm] \vee [/mm] D [mm] \vee [/mm] C|
2 = |M [mm] \vee [/mm] G [mm] \vee [/mm] H [mm] \vee [/mm] K|
2 = |H [mm] \vee [/mm] K [mm] \vee [/mm] L [mm] \vee [/mm] N|
Die Betragsstriche sollen andeuten, wieviele true's es in dem Constraint gibt.
2)
0 = |A [mm] \vee [/mm] B [mm] \vee [/mm] E [mm] \vee [/mm] H [mm] \vee [/mm] G|
=> A = false, B = false, E = false, H = false, G = false
Diese Variablen streiche ich in den anderen Constraints:
1 = |K [mm] \vee [/mm] L [mm] \vee [/mm] F [mm] \vee [/mm] D [mm] \vee [/mm] C|
2 = |M [mm] \vee [/mm] K|
2 = |K [mm] \vee [/mm] L [mm] \vee [/mm] N|
Aus der zweiten Gleichung sehen wir, dass M und K true sein müssen => diese Streichen wir auch aus den anderen Constraints und subtrahieren dann je nachdem 1 oder 2 (jenachdem ob nur K oder M oder beide in der Formel sind).
0 = |L [mm] \vee [/mm] F [mm] \vee [/mm] D [mm] \vee [/mm] C||
1 = |L [mm] \vee [/mm] N|
Wir sehen, dass L, F D und C false sein müssen und streichen diese in allen anderen Constraints:
1 = |N| => N = true
Somit ist die Lösung dass die Variablen N, K und M true sind, während alle anderen false sind.
Was haltet ihr von meiner Lösung?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mi 02.03.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
