PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (08/07/86)
PROLOG Digest Friday, 8 Aug 1986 Volume 4 : Issue 34
Today's Topics:
Announcement - LP conference,
Query - Bagof Bug,
Puzzle - Farmer's
----------------------------------------------------------------------
Date: 7 August 1986, 10:52:40 EDT
From: Jean-Louis Lassez <JLL@ibm.com>
Subject: LP conference
The dates of the 4th International Logic Programming
Conference have now been determined. The conference
will be held at the University of Melbourne on the
25-29 May 1987.
Thank you,
-- jl
------------------------------
Date: Wed 6 Aug 86 14:38:43-CDT
From: Dave Plummer <ATP.PLUMMER@R20.UTEXAS.EDU>
Subject: DEC-10 Bagof - Bug?
Given the program:
p(1,_).
p(2,_).
p(3,3).
p(4,4).
and the goal bagof(X, p(X,Y), S). Edinburgh DEC-10 Prolog
returns,
S = [1,2,3]
X = _??
Y = 3
and on backtracking
S = [4]
X = _??
Y = 4
This behaviour doesn't agree with my reading of the
documentation, since the solution set [1,2,4] is
consistent with Y = 4. Is this a bug?
-- Dave
------------------------------
Date: Wed, 6 Aug 86 17:22:00 BST
From: William Clocksin <wfc%cam.cl@Cs.Ucl.AC.UK>
Subject: Farmer Puzzle
Mario Bougoin's Farmer problem: does it help to say
that this problem is a thinly disguised "Missionaries
and Cannibals" problem, the solution to which appears
in various places i.e., Kowalski's book.
------------------------------
Date: Thu, 7 Aug 86 10:46:32 pdt
From: Allen VanGelder <avg@diablo>
Subject: Farmer problem
My suggestion is to first take all the or's (;'s) out
of the program and see if what you have makes sense.
This will give you a better chance of having a correct
program. In particular, the rule for linked_state
looks suspicious and is overly complicated. Taking the
or's out will also make it more obvious why the program
loops. Others will no doubt point out the cause, but
you can see for yourself using 'trace'.
There are 2 ways to remove or's from the rule p :- a,(b; c),d.
If goal 'a' is cheap, just split it into
p :- a, b, d. p :- a, c, d.
If 'a' is expensive, and you don't want to pay to redo it when
b fails, invent a new predicate, say b_or_c, and write
p :- a, b_or_c, d. b_or_c :- b. b_or_c :- c.
10 or 20 simple rules are easier to check for correctness and
completeness than 4 complicated ones.
------------------------------
Date: 06 Aug 86 15:25:08 PDT (Wed)
From: vis!greg@sdcsvax.ucsd.edu
Subject: Farmer, Wolf, Goose/Goat, Grain/Cabbage
% Here's a solution to the Farmer, Wolf, Goat/Goose,
% Cabbage/Grain problem. Improvements could be made by:
%
% 1. Using a better data structure for states already
% seen, e.g. a tree, a hash table, assert, or a bit set.
%
% 2. Using best first search.
%
% Fortunately, we can separate these concerns from the
% problem.
%
% Domain independent depth first search rules:
% solve( initial State, Goal state, solution Path )
solve(S,G,P) :- path(S,G,[S],P).
% path( current State, Goal state, History list,
% solution Path
path(G,G,H,H).
path(S,G,H,P) :- move(S,N), % move to a New state
not(unsafe(N)), % which is legal
not(member(N,H)), % and not seen before
path(N,G,[N|H],P). % then complete the path
member(X,[X|T]) :- !.
member(X,[Y|T]) :- member(X,T).
% Domain rules (independent of search strategy):
move(fwgc(X,W,G,C), fwgc(Y,W,G,C)) :- opp(X,Y). % farmer goes alone
move(fwgc(X,X,G,C), fwgc(Y,Y,G,C)) :- opp(X,Y). % farmer takes wolf
move(fwgc(X,W,X,C), fwgc(Y,W,Y,C)) :- opp(X,Y). % farmer takes goat
move(fwgc(X,W,G,X), fwgc(Y,W,G,Y)) :- opp(X,Y). % farmer takes cabbage
opp(e,w). opp(w,e). % East and West are opposites
unsafe(fwgc(F,X,X,C)) :- opp(F,X). % wolf would eat goat
unsafe(fwgc(F,W,X,X)) :- opp(F,X). % goat would eat cabbage
% example query:
% ?- solve( fwgc(e,e,e,e), fwgc(w,w,w,w), Solution ).
-- J. Greg Davidson
------------------------------
Date: Thu, 7 Aug 86 12:42:10 edt
From: Yasuda%upenn-graded@cis.upenn.edu
Subject: Solution; Farmer Problem
Here we go! The solution here is due to
Ronald M. Lee.
/*********************************************************/
/* The Farmer and the River Problem */
/*********************************************************/
/*********************************************************/
/* Problem:
The Farmer has a goat, a cabbage, and a wolf. He needs to
cross a river, but his boat will only hold himself and one
other article. The problem arises because 1)the cabbage and
the goat cannot be left unattended, nor 2) can the goat and
the wolf.
*/
/* state predicate describes the arrangement of the
four individuals, whether they are here or there.
state(Farmer, Cabbage, Goat, Wolf) */
forbid( state(here, there, there, _)). /* restriction 1 */
forbid( state(here, _, there, there)). /* restriction 2 */
forbid( state(there, here, here, _)). /* dual of 1 */
forbid( state(there, _, here, here)). /* dual of 2 */
crossing( state(here, X, Y, Z),
state(there, X, Y, Z)). /* cross alone */
crossing( state(here, here, Y, Z),
state(there, there, Y, Z)). /* cross with Cabbage */
crossing( state(here, X, here, Z),
state(there, X, there, Z)). /* cross with Goat */
crossing( state(here, X, Y, here),
state(there, X, Y,there)). /* cross with Wolf */
trans(X, Y) :- crossing(X, Y),
not(forbid(Y)).
trans(X, Y) :- crossing(Y, X),
not(forbid(Y)).
go(X, Z, [X|L]) :- plan(X, Z, L, [X]).
plan(X, X, [], _). /* terminating condition */
plan(X, Z, [Y|L], Q) :-
trans(X,Y),
not(member(Y, Q)),
plan(Y, Z, L, [Y|Q]).
/* plan(From, To, Update_Route, Old_route):
You can read it as: "You can go from From to
To via Update_Route, if there is a trans from From
to To, and if you haven't been to Y before ( prevents
looping), and if you can go gom From to To."
*/
/* member/2 */
member(X,[X|_]).
member(X,[_|Rest]):- member(X,Rest).
/* to test this program just call
go(state(here,here,here,here),
state(there,there,there,there),
L).
*/
Sincerely,
-- Osvaldo
------------------------------
End of PROLOG Digest
********************