From: dnk@OMIT.cs.mu.OZ.AU
In <41f9262e$1@news.unimelb.edu.au> "Eddie901" writes:
> I have a problem with this classic problem. Many cite the solution
> takes 11 steps but my program tells me there's a 9-step soln.
> Start
> -> moving 1 M and 1 C across [M 2]:[C 2]:[B false]
> -> moving 0 M and 1 C back [M 2]:[C 3]:[B true]
> -> moving 2 M and 0 C across [M 0]:[C 3]:[B false]
> -> moving 1 M and 0 C back [M 1]:[C 3]:[B true]
> -> moving 1 M and 1 C across [M 0]:[C 2]:[B false]
> -> moving 0 M and 1 C back [M 0]:[C 3]:[B true]
> -> moving 0 M and 2 C across [M 0]:[C 1]:[B false]
> -> moving 1 M and 0 C back [M 1]:[C 1]:[B true]
> -> moving 1 M and 1 C across [M 0]:[C 0]:[B false]
> Goal found at depth 9
> [M 0]:[C 0]:[B false]
> I guess it depends how you interpret the constraints on legal states. I
> assume no Ms or Cs can be outnumbered unless the boat is present.
> Does anyone have any thoughts on this?
> Thanks.
You've chosen a rather original set of constraints. In the classic
M&C problem, the presence of the boat makes no difference - cannibals
should never outnumber missionaries on either bank at any time.
(Unlike the farmer with fox, goose and grain problem, there is noone
but the missionaries and cannibals to row the boat or control things.)
Above, the 3 cannibals eat the 2 missionaries after the second step!
The classic 11-step solution:
MC cross, M returns
CC cross, C returns
MM cross, MC return
MM cross, C returns
CC cross, C returns
CC cross
David
[ comp.ai is moderated. To submit cross(es), just post and be patient, or if ]
[ that fails mail your article to cross(es), and ]
[ ask your news administrator to fix the problems with your system. ]
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
