Logic Programming Prolog 8
اسلاید 1: ?- findall(Z,insert(a,[1,2,3],Z),L).Z = _G346L = [[a, 1, 2, 3], [1, a, 2, 3], [1, 2, a, 3], [1, 2, 3, a]] insert(X, [ ], [X]). insert(X, [H | T], [X, H | T]). insert(X, [H | T], [H | T1]):- insert(X, T, T1). Inserting into a listBefore looking at another solution for the 8-Queens problemSolution 2
اسلاید 2: 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. Permutations?- 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
اسلاید 3: permutation([ ],[ ]).permutation([H|T], P):-permutation(T,L),insert(H,L,P).?- 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[trace] ?- permutation([1,2,3],P). Call: (6) permutation([1, 2, 3], _G411) ? creep Call: (7) permutation([2, 3], _G474) ? creep Call: (8) permutation([3], _G474) ? creep 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]) ? creepP = [1, 2, 3] ;
اسلاید 4: Solution 2In 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 a solution. So, we may formulate this in Prolog as:solution(P):-permutation([1,2,3,4,5,6,7,8], P),safe(P).
اسلاید 5: safe([Queen | Others]):- safe(Others), noattack(Queen, Others). 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 Others and we have:
اسلاید 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: Xdist=1Xdist = 3noattack(Y, [First | Rest], Xdist) :- First - Y == Xdist, Y - First == Xdist, Dist1 is Xdist + 1, noattack(Y, Rest, Dist1).
اسلاید 8: 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 as: noattack(Y, [First | Rest], Xdist) :- First - Y == Xdist, Y - First == Xdist, Dist1 is Xdist + 1, noattack(Y, Rest, Dist1). Again 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(_, [ ], _). relation “noattack”
اسلاید 9: 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).Putting it all together
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.