صفحه 1:
Solution 2
re looking at another solution for the 8-Queens problem
inserting into a list
insert(X, [ ], [X]).
insert(X, [H | T], [X, H | T)).
insert(X, [H | T], [H | T1]):-
insert(X, T, T1).
?- findall(Z,insert(a,
[1,2,3],Z),L).
Z= _G346
L =a, 1, 2; 31,
11. بة 231,
,[3 بي ,2 ,1]
ey ee es a
صفحه 2:
Permutations
Permutations of a list are lists with the same elements
arranged in different orders. The lists
ها رای شاه تلا ات ها ملق ضا مرلو ر2 رلا
2, 4]
are all permutations of the list
|) sir
Notice that the list [1.2.31 is a permutation of itself.
?- permutation([1,2,3],P).
]دم
دا
P=[2, 3, 1];
P=(1, 3, 2];
P=([3,.1,2];
17 ره ر3] 22
No
صفحه 3:
De
permutation([ ],[ ]). permutation([1,2,3],P)
permutation([H|T], P):-
1 5 P=[1, 2,3];
permutation(T,L),insert(H,L,P). P=(2,1,3];
[trace] ?- permutation([1,2,3],P). P = [2, 3, 1];
Call: (6) permutation([1, 2, 3], _G411) ? creep[1, 3, 2];
Call: (7) permutation([2, 3], G474) ? creep — 31 21
Call: (8) permutation([3], G474) ? creep P=([3,2,11;
Call: (9) permutation([], G474) ? creep لت نس
Exit: (9) permutation([], []) ? creep
Call: (9) insert(3, [], G475) ? creep
Exit: (9) insert(3, [], [3]) ? creep
Exit: (8) permutation([3], [3]) ? creep
Call: (8) insert(2, [3], G478) ? creep
Exit: (8) insert(2, [3], [2, 3]) ? creep
Exit: (7) permutation([2, 3], [2, 3]) ? creep
Call: (7) insert(1, [2, 3], G411) ? creep
Exit: (7) insert(1, [2, 3], [1, 2, 3]) ? creep
Exit: (6) permutation([1, 2, 3], [1, 2, 3]) ? creep
P=[1, 2, 3];
صفحه 4:
Solution 2
In our previous solution, we represented the
ل asa decors ea y cooctiaties “aa
representing a queen on the board.
‘[1:Y1, 2:Y2, 3:3, 4:¥4, 5:Y5, 6:Y6, 7:Y7, 8:Y8]
Se eee any
information. ل ae
list may be used instead. To prevent horizontal attacks
now, all the Y’s must be different. So now the problem
is finding different permutations of the list
(1,2,3,4,5,6,7,8]
صفحه 5:
safe(P).
The predicate “safe” tests the possible solutions
generated by the predicate “permutation” in the above
solution.
Case 1 P is the empty list. The empty board is safe,
and we declare:
safe([ ]).
Case 2: P is not empty and may be broken into a head
and a tail
[Queen | Others]. This will be safe if Others is
safe and Queen does not attack the queens in the list
Others and we have:
safe(Others),
noattack(Queen,
Others).
صفحه 6:
The predicate noattack is trickier this time. The
problem is that we intentionally omitted the explicit
information about the X coordinates. However, the
available relative X locations may be used by adding an
argument, XDist, to the noattack relation to represent
the X distance between the Queen and the Others. The
safe relation has to be defined as:
safe([Queen | Others]):-
safe(Others),
noattack(Queen, Others, 1). % the others
start in the next
column
صفحه 7:
sR oO eH DWN اه
Ce a ee)
noattack(Y, [First | Rest], Xdist) :-
First - Y =\= Xdist,
Y - First =\= Xdist,
Dist1 is Xdist + 1,
noattack(Y, Rest, Dist1).
صفحه 8:
relation “noattack”
in the problem may be broken into two cases.
Case 1: There is nothing else on the board, then the no
attack condition holds and we may declare:
noattack(_, [ ], _).
Case 2: We have a list of others which we represent
as: [First|Rest]. These are queens which are
positioned at some distance Xdist away. We now check
that Queen does not attack First and the Rest, whose
elements start Xdist + 1 away. Recall that all the
values vara har awn Vo anardinatae Wa moar dnfina tha
predica noattack(Y, [First | Rest], Xdist) :-
First - Y =\= Xdist,
Y - First =\= Xdist,
Dist1 is Xdist + 1,
noattack(Y, Rest, Dist1).
صفحه 9:
Putting it all together
solution(P):-
permutation([1,2,3,4,5,6,7,8], P),
safe(P).
safe([]).
safe([Queen | Others]):-
safe(Others),
noattack(Queen, Others, 1). % the others start in
the next column
noattack(_, [ ], _).
noattack(Y, [First | Rest], Xdist) :-
First - Y =\= Xdist,
Y - First =\= Xdist,
Dist1 is Xdist + 1,
noattack(Y. Rest. Dist1).
Solution 2
ore looking at another solution for the 8-Queens problem
Inserting into a list
insert(X, [ ], [X]).
insert(X, [H | T], [X, H | T]).
insert(X, [H | T], [H | T1]):insert(X, T, T1).
?- findall(Z,insert(a,
[1,2,3],Z),L).
Z = _G346
L = [[a, 1, 2, 3],
[1, a, 2, 3],
[1, 2, a, 3],
Permutations
Permutations of a list are lists with the same elements
arranged in different orders. The lists
[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3,
2, 1]
are all permutations of the list
[1,2,3].
Notice that the list [1,2,3] is a permutation of itself.
?- permutation([1,2,3],P).
P = [1, 2, 3] ;
P = [2, 1, 3] ;
P = [2, 3, 1] ;
P = [1, 3, 2] ;
P = [3, 1, 2] ;
P = [3, 2, 1] ;
No
?permutation([ ],[ ]).
permutation([1,2,3],P)
.
permutation([H|T], P):P = [1, 2, 3] ;
permutation(T,L),insert(H,L,P).
P = [2, 1, 3] ;
P = [2, 3, 1] ;
[trace] ?- permutation([1,2,3],P).
Call: (6) permutation([1, 2, 3], _G411) ? creep
P = [1, 3, 2] ;
Call: (7) permutation([2, 3], _G474) ? creep
P = [3, 1, 2] ;
Call: (8) permutation([3], _G474) ? creep
P = [3, 2, 1] ;
Call: (9) permutation([], _G474) ? creep
No
Exit: (9) permutation([], []) ? creep
Call: (9) insert(3, [], _G475) ? creep
Exit: (9) insert(3, [], [3]) ? creep
Exit: (8) permutation([3], [3]) ? creep
Call: (8) insert(2, [3], _G478) ? creep
Exit: (8) insert(2, [3], [2, 3]) ? creep
Exit: (7) permutation([2, 3], [2, 3]) ? creep
Call: (7) insert(1, [2, 3], _G411) ? creep
Exit: (7) insert(1, [2, 3], [1, 2, 3]) ? creep
Exit: (6) permutation([1, 2, 3], [1, 2, 3]) ? creep
P = [1, 2, 3] ;
Solution 2
In our previous solution, we represented the
chessboard as a list of X and Y coordinates each
representing a queen on the board.
[1:Y1, 2:Y2, 3:Y3, 4:Y4, 5:Y5, 6:Y6, 7:Y7, 8:Y8]
We can omit the X coordinates without losing any
information. The position of each Y coordinate in the
list may be used instead. To prevent horizontal attacks
now, all the Y’s must be different. So now the problem
is finding different permutations of the list
[1,2,3,4,5,6,7,8]
and the ones in which the queens do not attack one
another is asolution(P):solution. So, we may formulate this in
Prolog as:
permutation([1,2,3,4,5,6,7,8], P),
safe(P).
The predicate “safe” tests the possible solutions
generated by the predicate “permutation” in the above
solution.
We break the problem into two cases:
Case 1: P is the empty list. The empty board is safe,
and we declare:
safe([ ]).
Case 2: P is not empty and may be broken into a head
and a tail
[Queen | Others]. This will be safe if Others is
safe and Queen does not attack the queens in the list
Otherssafe([Queen
and we have:
| Others]):safe(Others),
noattack(Queen,
Others).
The predicate noattack is trickier this time. The
problem is that we intentionally omitted the explicit
information about the X coordinates. However, the
available relative X locations may be used by adding an
argument, XDist, to the noattack relation to represent
the X distance between the Queen and the Others. The
safe relation has to be defined as:
safe([Queen | Others]):safe(Others),
noattack(Queen, Others, 1).
start in the next
column
% the others
Xdist=1
noattack(Y, [First | Rest], Xdist) :First - Y =\= Xdist,
Y - First =\= Xdist,
Dist1 is Xdist + 1,
noattack(Y, Rest, Dist1).
Xdist = 3
relation “noattack”
ain the problem may be broken into two cases.
Case 1: There is nothing else on the board, then the no
attack condition holds and we may declare:
noattack(_, [ ], _).
Case 2: We have a list of others which we represent as:
[First|Rest]. These are queens which are positioned at
some distance Xdist away. We now check that Queen
does not attack First and the Rest, whose elements
start Xdist + 1 away. Recall that all the values we have
are Y coordinates. We may define the predicate
noattack(Y,
[First | Rest], Xdist) :“noattack
as:
First - Y =\= Xdist,
Y - First =\= Xdist,
Dist1 is Xdist + 1,
noattack(Y, Rest, Dist1).
Putting it all together
solution(P):permutation([1,2,3,4,5,6,7,8], P),
safe(P).
safe([]).
safe([Queen | Others]):safe(Others),
noattack(Queen, Others, 1).
% the others start in
the next column
noattack(_, [ ], _).
noattack(Y, [First | Rest], Xdist) :First - Y =\= Xdist,
Y - First =\= Xdist,
Dist1 is Xdist + 1,
noattack(Y, Rest, Dist1).
