cap5605assignment8_sb23w (3)

CAP5605 ASSIGNMENT 8 - Sai Sankar Bhuvanapalli(sb23w) 1. Program: 2. /* 3. * This is the code for the Farmer, Wolf, Goat and Cabbage Problem 4. * using the ADT Stack. 5. * 6. * Run this code by giving PROLOG a "go" goal. 7. * For example, to find a path from the west bank to the east bank, 8. * give PROLOG the query: 9. * 10. * go(state(w,w,w,w), state(e,e,e,e)). 11. */ 12. 13. :- [adts]. /* consults (reconsults) file containing the 14. various ADTs (Stack, Queue, etc.) */ 15. 16. go(Start,Goal) :- 17. empty_stack(Empty_been_stack), 18. stack(Start,Empty_been_stack,Been_stack), 19. path(Start,Goal,Been_stack). 20. 21. /* 22. * Path predicates 23. */ 24. 25. path(Goal,Goal,Been_stack) :- 26. write ( 'Solution Path Is:' ), nl, 27. reverse_print_stack(Been_stack). 28. 29. path(State,Goal,Been_stack) :- 30. move(State,Next_state), 31. not (member_stack(Next_state,Been_stack)), 32. stack(Next_state,Been_stack,New_been_stack), 33. path(Next_state,Goal,New_been_stack),!. 34. 35. /* 36. * Move predicates 37. */ 38. 39. move(state(X,X,G,C), state(Y,Y,G,C)) 40. :- opp(X,Y), not (unsafe(state(Y,Y,G,C))), 41. writelist([ 'try farmer takes wolf' ,Y,Y,G,C]). 42. 43. move(state(X,W,X,C), state(Y,W,Y,C))

44. :- opp(X,Y), not (unsafe(state(Y,W,Y,C))), 45. writelist([ 'try farmer takes goat' ,Y,W,Y,C]). 46. 47. move(state(X,W,G,X), state(Y,W,G,Y)) 48. :- opp(X,Y), not (unsafe(state(Y,W,G,Y))), 49. writelist([ 'try farmer takes cabbage' ,Y,W,G,Y]). 50. 51. move(state(X,W,G,C), state(Y,W,G,C)) 52. :- opp(X,Y), not (unsafe(state(Y,W,G,C))), 53. writelist([ 'try farmer takes self' ,Y,W,G,C]). 54. 55. move(state(F,W,G,C), state(F,W,G,C)) 56. :- writelist([ ' BACKTRACK from:' ,F,W,G,C]), fail. 57. 58. /* 59. * Unsafe predicates 60. */ 61. 62. unsafe(state(X,Y,Y,C)) :- opp(X,Y). 63. unsafe(state(X,W,Y,Y)) :- opp(X,Y). 64. 65. /* 66. * Definitions of writelist, and opp. 67. */ 68. 69. writelist([]) :- nl. 70. writelist([H|T]):- print (H), tab(1), /* "tab(n)" skips n spaces. */ 71. writelist(T). 72. 73. opp(e,w). 74. opp(w,e). 75. 76. reverse_print_stack(S) :- 77. empty_stack(S). 78. reverse_print_stack(S) :- 79. stack(E, Rest, S), 80. reverse_print_stack(Rest), 81. write (E), nl. 82. 83. /* 84. * Do a run. 85. */ 86. 87. test:-go(state(w,w,w,w),state(e,e,e,e)). 88. After running the program, the output, we get is

2.Prolog program for 8x8 knights tour problem is less_than_or_equals(A, B) :- A =< B. greater_than_or_equals(A, B) :- A >= B. equals(A, B) :- A is B. move(state(Row, Column), state(Newrow, Newcolumn)) :- less_than_or_equals(Row, 6), equals(Newrow, Row + 2), less_than_or_equals(Column, 7), equals(Newcolumn, Column + 1). move(state(Row, Column), state(Newrow, Newcolumn)) :- less_than_or_equals(Row, 7), equals(Newrow, Row + 1), less_than_or_equals(Column, 6), equals(Newcolumn, Column + 2). move(state(Row, Column), state(Newrow, Newcolumn)) :- less_than_or_equals(Row, 6), equals(Newrow, Row + 2), greater_than_or_equals(Column, 2), equals(Newcolumn, Column - 1). move(state(Row, Column), state(Newrow, Newcolumn)) :- less_than_or_equals(Row, 7), equals(Newrow, Row + 1), greater_than_or_equals(Column, 3), equals(Newcolumn, Column - 2). move(state(Row, Column), state(Newrow, Newcolumn)) :- greater_than_or_equals(Row, 3), equals(Newrow, Row - 2), less_than_or_equals(Column, 7), equals(Newcolumn, Column + 1). move(state(Row, Column), state(Newrow, Newcolumn)) :- greater_than_or_equals(Row, 2), equals(Newrow, Row - 1), less_than_or_equals(Column, 6), equals(Newcolumn, Column + 2). move(state(Row, Column), state(Newrow, Newcolumn)) :- greater_than_or_equals(Row, 3), equals(Newrow, Row - 2), greater_than_or_equals(Column, 2), equals(Newcolumn, Column - 1).

move(state(Row, Column), state(Newrow, Newcolumn)) :- greater_than_or_equals(Row, 2), equals(Newrow, Row - 1), greater_than_or_equals(Column, 3), equals(Newcolumn, Column - 2). display([]). display([H|T]) :- display(T), write (H), nl. path(X,X,L):-display(L). path(X,Y,L):-move(X,Z), not (member(Z,L)),path(Z,Y,[Z|L]). output :

move(state(Row, Column), state(Newrow, Newcolumn)) :- greater_than_or_equals(Row, 3), equals(Newrow, Row - 2), greater_than_or_equals(Column, 2), equals(Newcolumn, Column - 1). % Depth-first search algorithm go(Start, Goal) :- empty_stack(Empty_open), stack([Start, nil], Empty_open, Open_stack), empty_stack(Closed_set), path(Open_stack, Closed_set, Goal). path(Open_stack, _, _) :- empty_stack(Open_stack), write ( '' ). path(Open_stack, Closed_set, Goal) :- stack([State, Parent], Rest_open_stack, Open_stack), State = Goal, write ( 'A Solution is Found!' ), nl, printsolution([State, Parent], Closed_set). path(Open_stack, Closed_set, Goal) :- stack([State, Parent], Rest_open_stack, Open_stack), get_children(State, Rest_open_stack, Closed_set, Children), add_list_to_stack(Children, Rest_open_stack, New_open_stack), union([[State, Parent]], Closed_set, New_closed_set), path(New_open_stack, New_closed_set, Goal), !. get_children(State, Rest_open_stack, Closed_set, Children) :- bagof(Child, moves(State, Rest_open_stack, Closed_set, Child), Children); empty_set(Children). moves(State, Rest_open_stack, Closed_set, [Next, State]) :- move(State, Next), not (member_stack([Next, _], Rest_open_stack)), not (member_set([Next, _], Closed_set)). printsolution([State, nil], _) :- write (State), nl. printsolution([State, Parent], Closed_set) :- member_set([Parent, Grandparent], Closed_set), printsolution([Parent, Grandparent], Closed_set), write (State), nl.

% Run the search from (1,1) to (8,8) :- go(state(1, 1), goal_state). Output: