Prolog: Eine Art Minesweeper

Kiki

Hallo zusammen,

ich habe ein etwas größeres Problem (für Prolog Profis ist es wohl nicht mal ein kleines Problem ). Ich habe nur einen kleinen Einführungskurs in Prolog gehabt und komme deshalb nicht weiter. Ich habe folgendes Problem:

Ich habe eine Matrize (n x m) Diese Matritze ist teilweise mit Werten zwischen 1 und 8 beschrieben. Diese Zahl gibt die Summe der angrenzenden "Minen" an. die Gesamtzahl der vorhandenen Minen ist K. Nun möchte ich über ein Prolog Programm alle Möglichen "Minenfelder" ausgeben. Die Minenfelder sollen nur 0 oder 1 enthalten. Eins steht für eine Mine und Null für keine!

Meine Ausgangsfunktion sieht folgendermaßen aus:

Code

%Matritze mit Größe NxM, Lent=Eingangsmatitze, K= Anzahl der Minen und G ist die Lösungsmatitze
local(M,N,Lent,K,G):-lösungsaufbau(M,N,Lent,G),bedingungen(M,N,Lent,G).


lösungsaufbau(M,N,Lent,G):-matritze(M,N,G),einfuegen(Lent,G).


%NxM Matritze erstellen
matritze(_,0,[]).
matritze(M,N,G):-int(M),int(N),size(G)=N,G=[L|SL],size(L)=M,matritze(M,N-1,SL).


%überall eine Null einfügen, wo sicher keine Mine ist (Zahl in der Eingangsmatritze)
einfuegen([],_).
einfuegen(Lent,G):-Lent=[L|SL],G=[Lg|SLg],zeile(L,Lg),einfuegen(SL,SLg).


%jede Zeile 
zeile([],_).
zeile([X|SL],[Y|SLg]):- X=cc(0,8),Y=0,zeile(SL,SLg).
zeile([X|SL],[Y|SLg]):- X= -1, Y=cc(0,1),zeile(SL,SLg).




bedingungen(M,N,Lent,G):-
%Summe der umliegenden Felder = Anzahl der Minen

Alles anzeigen

Ich weiß einfach nicht, wie ich die Summe der umliegenden Felder berechnen kann. Meine Matritze liegt halt in einer dummen Form vor. Bin mir aber sicher, dass es trotzdem relativ einfach geht, oder?

Bitte um eure Hilfe,
danke im voraus

Gruß Kiki

The User

Hallo Kiki,
meld dich gleich mal an, für Prolog Fragen steh ich offen.

Was steht in der Matrix, wenn da nicht was von 1 bis 8 steht?
Ich gucks mir an.

Viele Grüße
The User

Kiki

Das ist eigentlich egal bzw. bin da noch offen. Kann entweder ein x oder ein ? reinmachen oder auch irgend was anderes. Aber es wird immer dasselbe Symbol sein und eigentlich kein Integerwert sein.

Danke für deine Hilfe
Gruß Kiki

The User

Ähh, eine ganz blöde Frage, damit soll man doch minesweeper spielen und nicht lösen, oder?
hab jetzt mal im schulunterricht, war nicht so spannend, mal den Anfang dafür gemacht, also das Füllen der Felder und so. Werd ich posten, wennn ichs abgetippt und getestet habe. dann kommt halt noch dieses summe rechnen dazu.
schau mal, wie weit ich heute abend noch komme.

PS: Registrier dich doch mal!

kiki_666

Nein, man soll mit dem Spiel alle möglichen Lösungen ausgeben bzw. berechnen!
Das füllen der Matrize habe ich heute auch in Angriff genommen, ist eigentlich nicht so schwer! Aber wie ich die Summe angehen soll hab ich absolut keinen blassen Schimmer!

The User

Wovon soll denn die Summe berechnet werden, ich versteh nicht ganz das Ziel davon.

Code

matrixteil(_,0,_,0).
matrixteil(_,_,0,0).
matrixteil(_,"eine seitenlaenge"+1,_,0).
matrixteil(_,_,"andere seitenlaenge"+1,0).
matrixteil(M,A,B,E) :- nteselement(M,A,L),nteselement(L,B,E).
nteselement([H|_],1,H).
nteselement([H|T],N,Element) :- M is (N-1),nteselementcut(T,M,Element).
drumherumsumme(Matrix,N,M,Zahl) :- matrixteil(Matrix,N+1,M,A1),matrixteil(Matrix,N+1,M+1,A2),matrixteil(Matrix,N+1,M-1,A3),matrixteil(Matrix,N,M+1,A4),matrixteil(Matrix,N,M-1,A5),matrixteil(Matrix,N-1,M,A6),matrixteil(Matrix,N-1,M-1,A7),matrixteil(Matrix,N-1,M+1,A8),Zahl is (A1+A2+A3+A4+A5+A6+A7+A8).

Da hat man dann diese Summe.
Ich dachte, du meinst etwas viel komplizierteres.
Viele Grüße
The User
PS: Wenn ich das Minesweeper fertig gemacht hab, werd ichs posten. dann können beide programme ja kommunizieren.

kiki_666

Also ich versuche es nochmal. Glaube mein Problem ist einfach, dass ich nicht richtig ausdrücken kann, was ich haben will!
Ich hab als Eingang für meine Funktion "Minesweeper lösen" folgende Werte:
n und m die die Dimension angeben (=nxm Matritze), die Anzahl der vorhandenen Minen (=K) und ein teileweise "offenens" Spielfeld. Auf diesem Spielfeld befinden sich Zahlen zwischen 1 und 8, welche angeben, wie viele Minen sich um diese Zahl befinden.

Ich möchte zuerst eine komplett leere nxm Matitze erstellen (was ich ja schon gemacht habe). Diese möchte ich dann mit 0 oder 1 auffüllen. (0=keine Mine und 1=Mine). Die ersten 0en kann ich sofort anhand der Eingangsmatrix erstellen. Überall dort wo eine Zahl ist, kann ja keine Mine sein.
Dannach kommt das eigentliche Programm (und ab da komme ich nicht mehr weiter).
Prolog soll mir jetzt alle möglichen Matritzen bestimmen, die anhand der vorhandenen Eingangsmatrix möglich sind. Um dies zu tun, hatte ich an folgenden Algo gedacht:

1. Ich nehme mir jedes Feld, indem in der Eingangsmatrix eine Zahl steht. Dann beginne ich die umliegenden Felder mit Minen zu füllen und prüfe jedesmal, ob die Summer der umliegenden Felder bereits = der Zahl in der Mitte ist. Wenn ja höre ich auf und wenn nein mache ich weiter. Dann gehe ich zur nächsten Zahl und prüfe zuerst wieder die Summe. Ist diese gleich mal größer (weil ich bereits durch vorherige Zahlen zuviele Minen eingesetzt hab), dann ist diese Lösung nicht richtig.
...wenn ich dann alle zahlen durch hab und es keine Probleme gab, dann bin ich fertig!

Hoffe, dass der Algo so auch funzt. Was meinst du?

Gruß Kiki

PS: Sorry für die ganzen Rechtschreibfehler, ist schon spät!

The User

Klar, das könnte klappen, aber du musst dafür sorgen, dass er nicht stur eine nach der anderen auffüllt, sondern, wenns nicht hinhaut, also das einer anderen Stelle widerspricht, muss er dann eine andere Kombination ausprobieren. Also er fängt bei einer 2 an, nimmt er sich die ersten 2 drumherum, und geht zum nächsten, kommt es im Laufe der Rekursion zu einem Widerspruch, muss er andere 2 Nachbarn ausprobieren.
Am Ende, könnte man die Felder, die alle Möglichkeiten gemein haben, als sicher ansehen.

Das ganze wäre aber totales brute force.
Es würde klappen, eleganter wäre es jedoch, zum Beispiel solche Regeln zu formulieren:
Wenn um eine Zahl n 8-n Felder ohne Mine sind, sind die anderen garantiert Minen.
oder halt so Regeln, die wie deine Methode arbeiten, sich aber auf einen kleinen Bereich beschränken.
Sobald sicher eine Mine gefunden ist, wird sie dann an ein Minesweeper übergeben (bei meinem gibts ein Problem mit der Rekursion, das komplizierteste ist, das Feld mit Minen zu füllen, gar nicht mal das "Klicken"). Dann würde Lent aktualisiert werden, und das Arbeiten ginge weiter.

Viele Grüße
The User

Tags