《算法谜题》英文版 //booksdescr.org/item/index ... E970CD2C9C83A605B6E
42. The Other Wolf-Goat-Cabbage Puzzle
You have 4n counters of four types: n wolfs, n goats, n cabbages, and
n hunters. The object is to place the counters in a row such that no one is in
danger; that is, no hunter is next to a wolf, no wolf is next to a goat, and no
goat is next to a cabbage. In addition, no two counters of the same kind may
be next to each other either. How many ways are there to solve the puzzle?
解位于 116 页
Solution Let W, G, C, and H represent a wolf, a goat, a cabbage, and a hunter,
respectively. Then the puzzle has two symmetric solutions:
WCWC. . . WCHGHG . . . HG and GHGH . . . GHCWCW . . . CW.
令狼羊菜猎人分别为 W G C H，他们的数量一样（n），则该问题有两种对称解
WCWC. . . WC+HGHG . . . HG 和 GHGH . . . GH+CWCW . . . CW
Comments: The solution to the puzzle can be considered based on decrease-andconquer
applied bottom up: the solution is obtained by solving smaller instances of
the same puzzle first and then extending their solutions to form the same patterns.