Rephrase a simple mathy logic problem (yielding solution of an ordered procedure), and its generalized counterpart, into a solvable algorithm.

268 Views Asked by At

I'm given a selection of logic puzzles about different entities crossing a river safely (either from the same side to the same other side, or switching sides; utilizing the same boat, with certain restrictions about transient group proportions, driving ability, and boat occupancy). A few of the riddles assign jackals and coyotes as the entities, one of which is described as such:

Three jackals and three coyotes (all of whom smart) start together on a trek to the same place, which involves crossing a river by means of a boat that can hold no more than two occupants at once. At any one place, the jackals cannot outnumber the coyotes, else those coyotes get killed. What agreement can be forged to ensure safe passage of the coyotes, with minimal expenditure of time and energy?

The valid solutions with minimal crossings seem to necessitate coyote staying on the boat after carting a jackal across then crossing back to the original side, and actually I think that an alternative form of solution (allowing more crossings) does not exist. A slight variation to the problem stipulates that of the jackals only one member can drive the boat, although this doesn't appear to alter drastically the method to finding the possible solution-set (just shrinks it, eliminating some solutions).

I am interested in an answer provable as correct for analogous puzzle scalable to any cardinality of jackals and coyotes (with starting number of jackals equal to coyotoes, and also when smaller, or different yet with all entities not originating as a single group thus conceivably allowing for more jackals). So far I have designated the starting side as set A, the other side as set B, and the boat as T (for transportation, the vehicle), and R as river. There are are some overlapping intersections, as well as disjoint sections either adjacent disparate or potentially separate (non-adjacent, though not necessarily discontiguous from same parent set), which are distinguishable as such (though identifiable with respect to unions and intersections of preceding): each side with the river, shore$_A$=A∩R and shore$_B$=B∩R (loading/unloading zones); side A before the shore = A∩¬R; side B after the shore=B∩¬R (which includes the final end destination e as a subset); T is a proper subset of R, R⊃T ⇔ T⊃R; set d represents occupants than can drive.

Using the above designations, if we call X the starting state and Y the ending state, then

$X=\{A_{¬R}=\{2j_{¬d},1j_{d},3c_{d}\}, A_{R}=\{T=\{\}\}, B=\{0j,0c\}\}$

$↦$

$Y=\{A=\{0j,0c\}, B_{R}=\{T=\{\}\}, B_{e}=\{2j_{¬d},1j_{d},3c_{d}\}\}$

"T={}" represents the boat unoccupied. Its placement inclusion in the ending state is a direct inference. Identifying $B_Y$ and $A_X$ as each yielding no jackals and no coyotes is unnecessary, but I included it for clarity emphasis (similarly why I assigned all the coyotes to the "can drive" group, although redundant if defined succinctly in problem statement).

What should get modified orand how should I proceed? If the task were just to determine the minimal solution (such as number of crossings), then a relatively short equation should be possible. But requiring the order of steps to the solution (or possible variations to an equally valid solution) is a bit more involved.