SICP 4.3.2

Baker, Cooper, Fletcher, Miller, Smithは五階建てアパートの異なる階に住んでいる。Bakerは最上階には住んでいない。Cooperは最下階に住んでいない。Fletcherは最上階にも最下階にも住んでいない。MillerはCooperより上の階に住んでいる。SmithとFletcherの部屋は隣接していない。FletcherとCooperの部屋も隣接していない。それぞれはどの階に住んでいるか。

cc関連でrubyで実装している例があったなあと思い出す．→関西オープンソース2005発表, 非決定性計算, KOF宴会 - Journal InTime(2005-10-29)

継続は自分には難しいとしても，バックトラックの機構だけをくくりだすくらいならいけそうな気がする．昔書いた，リンクリストの探索 - ロバの耳を改造して：

def pseud_amb(*ar, &block)
  result = []
  amb_impl = lambda {|a, work|
    if a[0]==nil # 終端に到達
      result.push( work.dup) if !block_given? || block[work]
    else
      a[0].each {|d| amb_impl[a[1..-1], work.dup.push(d)] }
    end
  }
  amb_impl[ar, []]
  result
end

p pseud_amb([1,2,3], %w[a b])
#=> [[1, "a"], [1, "b"], [2, "a"], [2, "b"], [3, "a"], [3, "b"]]


old = Process.times.utime
a = pseud_amb(1..5, 1..5, 1..5, 1..5, 1..5) {|baker, cooper, fletcher, miller, smith|
    (([baker, cooper, fletcher, miller, smith].uniq.length == 5) and
      (baker != 5) and
      (cooper != 1) and
      (fletcher != 1 and fletcher != 5) and
      (miller > cooper) and
      ((smith - fletcher).abs != 1) and
      ((fletcher - cooper).abs != 1))
  }
p a
p Process.times.utime - old
#=> [[3, 2, 4, 5, 1]]
#=> 0.062

総当りでも，固まるほど遅いって訳でもないのか．しかし，早期に枝刈りできたほうがいいに決まっている．

そして元になったルート探索の問題をambにあわせるのはどうすればいいんだ？SICPの関連する節を読みなおすか．

ところで，最初の3条件ってチェックする必要なくない？

a = pseud_amb(1..4, 2..5, 2..4, 1..5, 1..5) {|baker, cooper, fletcher, miller, smith|
    (([baker, cooper, fletcher, miller, smith].uniq.length == 5) and
=begin
      (baker != 5) and
      (cooper != 1) and
      (fletcher != 1 and fletcher != 5) and
=end
      (miller > cooper) and
      ((smith - fletcher).abs != 1) and
      ((fletcher - cooper).abs != 1))
  }
p a