Logic Programming Prolog 7

Logic Programming Prolog 7

اسلاید 1: 8 Queens

اسلاید 2: Problem:Placing 8 queens on a chessboard such that they don’t attack each otherThree different Prolog programs are suggessted as solutions to this problem.A chess-board is an 8x8 gridYX

اسلاید 3: The problem is now finding such a list with the queens positioned on the board in such a way that they don’t attack one another. We will define a predicate: solution(Pos).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 pair represents the position of one queen on the boardRepresenting the board

اسلاید 4: solution(Pos)returns a solution in a list “Pos”.YXY1 = 4,  Y2 = 2,  Y3 = 7,  Y4 = 3,  Y5 = 6,  Y6 = 8,  Y7 = 5,  Y8 = 1 Here is an example solution: [1:4, 2:2, 3:7, 4:3, 5:6, 6:8, 7:5, 8:1]

اسلاید 5: Q3 X=3 Y=4Q4 X=8 Y=4XQ1 X=1 Y=6Q2 X=5 Y=6Q6 X=5 Y=2Q5 X=1 Y=2Y = Y1,                % different rows    (Y1 - Y) = (X1 - X),    (Y1 - Y) = (X - X1),   % different diagonals

اسلاید 6: To avoid vertical attacks, queens have to be on different columns. We may fix the X coordinates to achieve this.[1:Y1, 2:Y2, 3:Y3, 4:Y4, 5:Y5, 6:Y6, 7:Y7, 8:Y8]Each of the Y’s will be a Y coordinate (a number between 1 to 8).Solution 1We will put the queens on the board one by one making sure they do not attack one another until we have them all on the board. We may break the problem down to two cases of having an empty list or a list with a head and a tail as we usually do with problems involving lists.

اسلاید 7: Case 1There are no queens on the board then the no attack condition holds and we have:solution([ ]).Case 2 first queen other queensThere are some queens on the board in which case the list will be [X:Y|Sofar]In such a case, there will be a solution if 1. No attacks between the queens in Sofar2. 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 Sofarsolution([ ]).                         % 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: noattack(X:Y, [X1:Y1 | Rest]):-     Y == Y1,                % different rows     (Y1 - Y) == (X1 - X),     (Y1 - Y) == (X - X1),   % different diagonalsnoattack(X:Y, Rest).     % OK with the others. Now we must define the predicatenoattack(Queen, List_of_Queens). This can again be broken into two cases.Case 1If the List_of_Queens is empty then there are no queens to be attacked: noattack( _, [ ]). Case 2If 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 Queen12. The queen at position Queen must not attack the ones in the Rest_of_Queens

اسلاید 9: 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(X:Y, Sofar).            % Test % A solution templatetemplate([1:Y1, 2:Y2, 3:Y3, 4:Y4, 5:Y5, 6:Y6, 7:Y7, 8:Y8])Putting it all togethernoattack(_, [ ]). 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 others.

اسلاید 10: 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.