宣教師と人喰い人（Ruby）

次の有名な問題があります。

問題：
宣教師 3人と人喰い人 3人が、船で川を渡ろうとしています。船は 2人まで乗れますが、最低 1人いなければ動かせません。ここで、こちらの岸もあちらの岸も、また船の上でも、宣教師の数が人喰い人の数を下回ると喰われてしまうので、そのような仕方は許されません。

さて、6人全員があちらの岸へ渡ることは可能でしょうか？

　
Ruby で解いてみました。
missionaries_and_cannibals1.rb

M, C = 3, 3
Boat = 2

possiblity = ->(m, c) {
  result = []
  Boat.downto(1) do |n|    #nは舟に乗る人数
    0.upto(n) do |i|       #iは舟に乗る人喰い人の人数
      boat_m, boat_c = n - i, i
      next if boat_m < boat_c and boat_m.nonzero?
      here_m = m - boat_m
      here_c = c - boat_c
      there_m = M - here_m
      there_c = C - here_c
      next if here_m < 0 or here_c < 0
      next if here_m < here_c and here_m.nonzero?
      next if there_m < there_c and there_m.nonzero?
      result << [boat_m, boat_c]
    end
  end
  result
}

try = ->(m, c, turn, procedure, memo) {
  possiblity.(m, c).each do |x|
    next_m, next_c = M - m + x[0], C - c + x[1]
    next if x == procedure[-1]    #同じ構成で引き返すのは無意味
    if next_m == M and next_c == C and turn.zero?
      p procedure + [x]
    else
      nxt = turn.zero? ? [M - next_m, C - next_c, turn] : [next_m, next_c, turn]
      next if memo.include?(nxt)    #調べたパターンが既にあるか？
      try.(next_m, next_c, 1 - turn, procedure + [x], memo + [nxt])
    end
  end
}

try.(M, C, 0, [], [[M, C, 1]])

深さ優先探索（DFS）ですべての解を求めています。mc はそれぞれ岸にいる宣教師、人喰い人の人数です。next_mnext_c はその反対岸の人数が次にどうなるかを表しています。turn は0なら行き、1なら帰りです。possibility.() は岸の状態から舟に乗れる人数のすべての組み合わせを返します。procedure には舟の状態が入っていって、全員が川を渡れれば答えになります。nxt は「こちら岸」の次の状態です。調べたパターンは memo に入れておいて、重複しないようにします。また、船の同じ構成での往復は無意味なので、これも行わないようにします。
　
結果は次のようです。

[[1, 1], [1, 0], [0, 2], [0, 1], [2, 0], [1, 1], [2, 0], [0, 1], [0, 2], [1, 0], [1, 1]]
[[1, 1], [1, 0], [0, 2], [0, 1], [2, 0], [1, 1], [2, 0], [0, 1], [0, 2], [0, 1], [0, 2]]
[[0, 2], [0, 1], [0, 2], [0, 1], [2, 0], [1, 1], [2, 0], [0, 1], [0, 2], [1, 0], [1, 1]]
[[0, 2], [0, 1], [0, 2], [0, 1], [2, 0], [1, 1], [2, 0], [0, 1], [0, 2], [0, 1], [0, 2]]

解は 4とおりありますが、ほぼ同じでちがいは些細なものです。それぞれの手続きで、中の配列 [a, b] は a が（船に乗る）宣教師の数、b が（船に乗る）人喰い人の数を表しています。いちばん上の解を表にしてみましょう。
　

移動	あちらの岸	こちらの岸
	[0, 0]	[3, 3]
←[1, 1]	[1, 1]	[2, 2]
→[1, 0]	[0, 1]	[3, 2]
←[0, 2]	[0, 3]	[3, 0]
→[0, 1]	[0, 2]	[3, 1]
←[2, 0]	[2, 2]	[1, 1]
→[1, 1]	[1, 1]	[2, 2]
←[2, 0]	[3, 1]	[0, 2]
→[0, 1]	[3, 0]	[0, 3]
←[0, 2]	[3, 2]	[0, 1]
→[1, 0]	[2, 2]	[1, 1]
←[1, 1]	[3, 3]	[0, 0]