# [Prolog] Problem mit Cut oder nicht Cut



## Scotty86 (15. März 2008)

Hallo,
so, da hab ich schon wieder ein (Verstaendnis-)Problem mit Prolog.
Ich habe ein Programm geschrieben, dass das 8-Damen-Problem loesen soll:

```
pos([1,2,3,4,5,6,7,8]).
genDamen(Pos) :- pos(X), permutation(Pos,X).

checkLeft(1,_).
checkLeft(_,[]).
%checkLeft(Pos, [Dame|Rest]) :- NextPos is Pos - 1, (Dame == NextPos -> write('FAIL LEFT \n'), fail ; checkLeft(NextPos, Rest)).
checkLeft(Pos, [Dame|Rest]) :- NextPos is Pos - 1, (Dame == NextPos -> fail ; checkLeft(NextPos, Rest)).

checkRight(8,_).
checkRight(_,[]).
%checkRight(Pos, [Dame|Rest]) :- NextPos is Pos + 1, (Dame == NextPos -> write('FAIL RIGHT \n'), fail ; checkRight(NextPos, Rest)).
checkRight(Pos, [Dame|Rest]) :- NextPos is Pos + 1, (Dame == NextPos -> fail ; checkRight(NextPos, Rest)).

checkStellung([]).
checkStellung([CurrentDame|RestDamen]) :-     checkRight(CurrentDame,RestDamen),
                                            checkLeft(CurrentDame,RestDamen),
                                            checkStellung(RestDamen), !. %Warum muss ich hier einen Cut machen?
                                            
getStellung(X) :- genDamen(X), checkStellung(X).

getAllStellung :- findall(X,(genDamen(X), checkStellung(X)),L), laenge(L,Muh), write(Muh).
```

Das Programm hat mir richtige Loesungen geliefert, nur leider wenn es fuendig geworden ist, die selbe Loesung x-fach... Als ich keinen Nerv mehr hatte hab ich einfach ans ende von checkStellung einen Cut gesetzt und siehe da es laeuft wunderbar, doch warum muss ich ans Ende einer Methode nen Cut setzen, is doch dort eigentlich eh schon vorbei?

Kurz zum Verstaendnis des Programmes:
Ich generiere mir eine Liste mit den Zahlen 1 bis 8, diese stellen die X-Koordinaten auf dem Schachfeld dar, die Stelle an der sie stehen die Y-Koordinate. Da nun keine Dame mehr in der selben Reihe oder Spalte stehen kann muss ich ledig lich noch ueberpruefen ob eine weitere Dame in einer Diagonalen steht. Dies uebernimmt die Funktion checkStellung. Durch checkLeft/checkRight geh ich ab der Zeile in der die aktuelle zu pruefende Dame steht, diagonal das Spielfeld nach links/rechts ab, bis ich an den Rand komme oder eine andere Dame finde, in diesem Fall wird der Vorgang mit fail abgebrochen.

Gruesse
Scotty86


----------



## deepthroat (17. März 2008)

Hi.





Scotty86 hat gesagt.:


> ```
> checkLeft(1,_).
> checkLeft(_,[]).
> checkLeft(Pos, [Dame|Rest]) :- NextPos is Pos - 1, (Dame == NextPos -> fail ; checkLeft(NextPos, Rest)).
> ```


Das Problem ist, das du hier Fälle hast, die sich überschneiden. Du hast im Grunde eine Abkürzung gefunden (nämlich wenn das Brett zuende ist), aber durch das Backtracking werden auch die anderen Alternativen gesucht:

Wenn checkLeft(1, _) wahr ist, dann ist evtl. auch checkLeft(_, []) wahr (nämlich dann, wenn die 1 an letzter Stelle steht, was 4 mal der Fall ist für alle Lösungen des 8 Damen-Problems), usw.

```
checkLeft(1, _) :- !.
```
Für checkRight natürlich genauso.

Gruß


----------



## Scotty86 (19. März 2008)

Hmm, ich glaub ich verstehe so halb was du meinst.

Hab des ganze etz auch bei nem simpleren Problem gefunden:

```
len([], 0).
len([H|T], L) :- len(T, L1), write('X'), L is 1+L1.
```

Wenn ich jetzt len(X,3). ausfuehre erstellt er zwar ne liste aus 3 Elementen, allerdings schreibt er 6mal X anstelle von 3mal?
Wenn ich diesen Code nehme sinds nur 3mal X:

```
len([], 0).
len([H|T], L) :- write('X'), len(T, L1),  L is 1+L1.
```

Bin ich froh, wenn ich ab morgen (hoffentlich) kein Prolog mehr sehen muss


----------



## deepthroat (19. März 2008)

Scotty86 hat gesagt.:


> Hmm, ich glaub ich verstehe so halb was du meinst.
> 
> Hab des ganze etz auch bei nem simpleren Problem gefunden:
> 
> ...


Das nennst du ein simples Problem?  Du hast dort sogar ein Prädikat definiert welches für die Frage len(X, 3) unendlich viele Backtrackingschritte durchführen wird (wenn du Pech hast, bzw. nach mehr Lösungen fragst).

Die 6 X stammen natürlich vom Backtracking welches bei len(T, L1) erfolgt. Da T und L1 keine gebunden Variablen sind, kann es trivialierweise erstmal durch len([], 0) unifiziert werden, wenn nämlich T die leere Liste und L1 = 0 ist. Das dies letztendlich nicht korrekt ist wird erst festgestellt wenn geprüft wird ob L = L1 + 1 ist...

Dann gehts eben wieder an der Stelle vor write('X') weiter und es wird versucht das Prädikat anders zu unifizieren...



Scotty86 hat gesagt.:


> Wenn ich diesen Code nehme sinds nur 3mal X:
> 
> ```
> len([], 0).
> ...


Ja, klar. Das Backtracking findet eben auch bei len(T, L1) statt, aber nach dem write und somit werden die "Sackgassen" nicht mitgezählt.


Scotty86 hat gesagt.:


> Bin ich froh, wenn ich ab morgen (hoffentlich) kein Prolog mehr sehen muss


Na, sooo schlecht ist es nun auch wieder nicht ;-)

Gruß


----------



## Scotty86 (20. März 2008)

Oky, so aehnlich hab ich mri das auch gedacht.
Nochmals vielen Dank fuer deine Hilfe, dann hoff ich mal, dass die Klausur heut net zu schwer wird, wobei Prolog wohl das kleinste Problem wird -.-"


----------

