% problem-set/puzzles/space_state/mission.ver1.clauses % created : 07/13/88 % revised : 07/13/88 % description: % % This run solves "The Missionaries and Cannibals Puzzle" using % UR-resolution. % % The Missionaries and Cannibals Puzzle % % There are three missionaries and three cannibals on the west % bank of a river. There is a boat on the east bank. But they % have a problem: If on either bank the cannibals ever outnumber % the missionaries, the outnumbered will be eaten. Is there a % way for the missionaries to get their wish - to get to the % east bank without losing anyone? % representation: % % PREDICATES : % ACHEIVABLE - The puzzle starts with an 'acheivable' arrangement % and deduces other states. The arguements of this % predicate, represented as lists, indicate the number % of missionaries and cannibals on the west and East % bank and the position of the boat. % FUNCTIONS : % West(x,y) :Indicates that there are x number of % missionaries and y number of cannibals on the west bank. % East(mx,cy):Indicates that there are x number of % missionaries and y number of cannibals on the East bank. % s(x) :gives successor of x,ie.,s(0) =1, etc % m(s(x)) :there are s(x) number of missionaries % c(s(x)) :there are s(x) number of cannibals. % Take one cannibal from the west bank to the East bank . This % automatically implies that the number of cannibals on the west % bank is reduced by one. % The number of cannibals on the East bank should now be increased by one. -ACHIEVABLE(West(m(x),c(s(y))),boatonwest,East(m(z),c(w))) |ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(z),c(s(w)))). -ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(z),c(s(w)))) |ACHIEVABLE(West(m(x),c(s(y))),boatonwest,East(m(z),c(w))). % Two missionaries are taken from the west bank to the East. -ACHIEVABLE(West(m(s(s(x))),c(y)),boatonwest,East(m(z),c(w))) |ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(s(s(z))),c(w))). % Two missionaries from East to west. -ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(s(s(z))),c(w))) |ACHIEVABLE(West(m(s(s(x))),c(y)),boatonwest,East(m(z),c(w))). % One missionary and one cannibal from west to East. -ACHIEVABLE(West(m(s(x)),c(s(y))),boatonwest,East(m(z),c(w))) |ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(s(z)),c(s(w)))). % One missionary and one cannibal from East to west. -ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(s(z)),c(s(w)))) |ACHIEVABLE(West(m(s(x)),c(s(y))),boatonwest,East(m(z),c(w))). % One missionary from west to East. -ACHIEVABLE(West(m(s(x)),c(y)),boatonwest,East(m(z),c(w))) |ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(s(z)),c(w))). % One missionary from East to west . -ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(s(z)),c(w))) |ACHIEVABLE(West(m(s(x)),c(y)),boatonwest,East(m(z),c(w))). % Two cannibals from west to East. -ACHIEVABLE(West(m(x),c(s(s(y)))),boatonwest,East(m(z),c(w))) |ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(z),c(s(s(w))))). % Two cannibals from East to west. -ACHIEVABLE(West(m(x),c(y)),boatoneast,East(m(z),c(s(s(w))))) |ACHIEVABLE(West(m(x),c(s(s(y)))),boatonwest,East(m(z),c(w))). % The possible combinations of the missionaries and the cannibals on % either banks may be characterised by the differance their number % (of one or two). This idea is captured in the following. ACHIEVABLE(West(m(s(x)),c(s(s(x)))),y,East(z,w)). ACHIEVABLE(West(m(s(x)),c(s(s(s(x))))),y,East(z,w)). ACHIEVABLE(West(x,y),z,East(m(s(w)),c(s(s(w))))). ACHIEVABLE(West(x,y),z,East(m(s(w)),c(s(s(s(w)))))). % Corresponds to the unachievable state that corresponds to assuming % the puzzle unsolvable. ACHIEVABLE(West(m(s(s(s(0)))),c(s(s(s(0))))),boatonwest, East(m(0),c(0))). -ACHIEVABLE(West(m(0),c(0)),x,East(m(s(s(s(0)))),c(s(s(s(0)))))).