宣教師と人喰い人(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]

確かに 6人全員があちらの岸へ渡ることができています。

宣教師がひとりもいない場合は(当然ながら)喰べられないというのを上手く使わないといけないわけですね。