Logic Programming Prolog 7

صفحه 1:
8 Queens 

صفحه 2:
Problem: Placing 8 queens on a chessboard such that they don’t ttack each other, anger sacl is an 8x8 grid SN Oe HD ‏ها ید و‎ 1 2 3 4 5 8 7 6 x Three different Prolog programs are suggessted as solutions to this problem. 

صفحه 3:
Representing the board We may represent the board as a list of eight elements. [X1:Y1, X2:Y2, X3:Y3, X4:Y4, X5:¥5, X6:Y6, X7:Y7, X8:Y8] rie hh ‏و96 لمم ةتوم معطا كانم مومهم‎ yard in such a way that they don’t attack one another. We v > a predicate: solution(Pos). 

صفحه 4:
solution(Pos) returns a solution in a list “Pos”. Here is an example solution: (1:4, 2:2)-3:7, 4:8, 5:6, 6:8), 7°5,-8:1] Y1=4, Y2=2, Y3=7, Y4=3, YS=6, Y6=8, Y7 2 NO eH ww OM ها بد © ب هاس نوراه 

صفحه 5:
8 17 Ql X=1 Y=6 65 Q2 X=5 Y=6 5 Q3 X=3 Y=4 4 Q4 X=8 Y=4 3 05 X=1 Y=2 ‏و‎ Q6 X=5 Y=2 4 x ۳ ۱ % different rows (Y1 - Y) \= (X1 - X), (Y1 - Y) \= (KX - X1), % different diagonals 

صفحه 6:
void vertical attacks, queens have to be on different colum: may fix the X coordinates to achieve this. (EVI, 2:Y2> 3:Y3;-4:Y4-5:Y5, G:Y6; 7-Y7, 6:Y6] 1 of the Y’s will be a Y coordinate (a number between 1 to € tion 1 vill put the queens on the board one by one making sure th ot attack one another until we have them all on the board. break the problem down to two cases of having an empty 1 list with a head and a tail as we usually do with problems ving lists. 

صفحه 7:
Case 1 There are no queens on the board then the no attack condition holds and we have: solution({ ]). Case 2 ___ first queen other queens 0 — There are some queens on the board in which case the list will be In such a case, there will be a solution if 1. No attacks between the queens in Sofar 2, X and Y are integers between 1-8. 3. A queen at square X:Y must not attack any of the queens in the list Sofar solution([ ]). % Nothing to attack! solution([X:Y | Sofar]) :- % Add a new queen solution(Sofar), % Sofar is OK member(Y, [1, 2, 3, 4, 5, 6, 7, 8]), % Generate Y noattack(X:Y, Sofar). % Test 

صفحه 8:
Now we must define the predicate noattack(Queen, List_of Queens). This can again be broken into two cases. Case 1 If the List_of Queens is empty then there are no queens to be attacked: noattack(_,[ ]). Case 2 If the List_of Queens is not empty then it can be represented as [Queen1 | Rest_of_Queens] 1. The queen at position Queen must not attack the one at position Queen1 2. The queen at position Queen must not attack the ones in the Rest_of Queens Y =\= Y1, % different rows (¥1 - Y) =\= (X1 - X), (Y1 -Y) =\=(X-X1), % different diagonals noattack(X:Y, Rest). | % OK with the others. 

صفحه 9:
Putting it all together solution([ ]). % Nothing to attack! solution([X:Y | Sofar]) :- % Add anew queen solution(Sofar), % Sofar is OK member(Y, [1, 2, 3, 4, 5, 6, 7, 8]), % Generate Y (X ‏ةا‎ 1 2 0 % Test Y =\=Y1, % different rows (¥1 - Y) =\= (X1 - X), (Y1 - Y) =\= (X- X1), % different diagonals noattack(X:Y, Rest). % OK with thesokbarson template template([1:Y1, 2:Y2, 3:Y3, 4:¥4, 5:Y5, 6:Y6, 7:Y7, 8:Y8]) 

صفحه 10:
The query: ?-template(Pos),solution(Pos). generates Y1=4, Y2=2, Y3=7, Y4=3, YS=6, Y6=8, Y7 =5, Y8=1 as the first solution. There are 92 solutions. 

8 Queens Problem: Placing 8 queens on a chessboard such that they don’t attack each other A chess-board is an 8x8 grid Y X Three different Prolog programs are suggessted as solutions to this problem. Representing the board We may represent the board as a list of eight elements. [X1:Y1, X2:Y2, X3:Y3, X4:Y4, X5:Y5, X6:Y6, X7:Y7, X8:Y8] Each X:Y pairfinding represents position of queens one queen on problem is now such the a list with the positioned the board oard in such a way that they don’t attack one another. We w e a predicate: solution(Pos). solution(Pos) returns a solution in a list “Pos”. Here is an example solution: [1:4, 2:2, 3:7, 4:3, 5:6, 6:8, 7:5, 8:1] Y1 = 4, Y2 = 2, Y3 = 7, Y4 = 3, Y5 = 6, Y6 = 8, Y7 = 5, Y8 = 1 Y X Q1 X=1 Y=6 Q2 X=5 Y=6 Q3 X=3 Y=4 Q4 X=8 Y=4 Q5 X=1 Y=2 Q6 X=5 Y=2 X Y \= Y1, (Y1 - Y) \= (X1 - X), (Y1 - Y) \= (X - X1), % different rows % different diagonals avoid vertical attacks, queens have to be on different column may fix the X coordinates to achieve this. [1:Y1, 2:Y2, 3:Y3, 4:Y4, 5:Y5, 6:Y6, 7:Y7, 8:Y8] h of the Y’s will be a Y coordinate (a number between 1 to 8 tion 1 will put the queens on the board one by one making sure the ot attack one another until we have them all on the board. W break the problem down to two cases of having an empty li list with a head and a tail as we usually do with problems lving lists. Case 1 There are no queens on the board then the no attack condition holds and we have: solution([ ]). Case 2 first queen other queens There are some queens on the board in which case the list will be In such a case, there will be a solution if [X:Y|Sofar] 1. No attacks between the queens in Sofar 2. X and Y are integers between 1-8. 3. A queen at square X:Y must not attack any of the queens in the list Sofar solution([ ]). attack! solution([X:Y | Sofar]) :queen solution(Sofar), Sofar is OK member(Y, [1, 2, 3, 4, 5, 6, 7, 8]), noattack(X:Y, Sofar). % Nothing to % Add a new % % Generate Y % Test Now we must define the predicate noattack(Queen, List_of_Queens). This can again be broken into two cases. Case 1 If the List_of_Queens is empty then there are no queens to be attacked: noattack( _, [ ]). Case 2 If the List_of_Queens is not empty then it can be represented as [Queen1 | Rest_of_Queens] and we must check two conditions: 1. The queen at position Queen must not attack the one at position Queen1 2. The queen at position Queen must not attack the ones in the noattack(X:Y, [X1:Y1Rest_of_Queens | Rest]):- Y =\= Y1, (Y1 - Y) =\= (X1 - X), (Y1 - Y) =\= (X - X1), noattack(X:Y, Rest). % different rows % different diagonals % OK with the others. Putting it all together solution([ ]). % Nothing to attack! solution([X:Y | Sofar]) :% Add a new queen solution(Sofar), % Sofar is OK member(Y, [1, 2, 3, 4, 5, 6, 7, 8]), % Generate Y (X is known) noattack(_, [ ]). noattack(X:Y, Sofar). % Test noattack(X:Y, [X1:Y1 | Rest]):Y =\= Y1, % different rows (Y1 - Y) =\= (X1 - X), (Y1 - Y) =\= (X - X1), % different diagonals noattack(X:Y, Rest). % OK with the % Aothers. solution template template([1:Y1, 2:Y2, 3:Y3, 4:Y4, 5:Y5, 6:Y6, 7:Y7, 8:Y8]) The query: ?-template(Pos),solution(Pos). generates Y1 = 4, Y2 = 2, Y3 = 7, Y4 = 3, Y5 = 6, Y6 = 8, Y7 = 5, Y8 = 1 as the first solution. There are 92 solutions.