2抜きを許したストラックアウトの抜き方(Ruby)

1 2 3
4 5 6
7 8 9

ストラックアウトといって 3×3 のボードに玉をぶつけて数字を抜いていく遊びがありますね。その抜き方は何通りあるでしょうといえば、9!(9の階乗)通りとすぐ求められてつまらないので、2抜きを許します。つまり、ひとつの玉で同時に、隣接した 2つを抜くことを許すわけです。ただし、真ん中の 5は同時に抜くことはできません。さて、この場合の抜き方は何通りでしょう。


Ruby で解くとこんな感じです。

A = (1..9).to_a
Hits = A.inject([]) {|r, a| r << [a]} +
   [[1, 2], [2, 3], [3, 6], [6, 9], [9, 8], [8, 7], [7, 4], [4, 1]]

#玉が当たれば false、外れれば true を返す
def check(rest, hit)
  hit.each {|i| return true unless rest.include?(i)}
  false
end

def throw(rest)
  return @h[rest] if @h[rest]
  return 1 if rest.empty?
  sum = 0
  Hits.each do |hit|
    next if check(rest, hit)
    sum += throw((rest - hit).sort)
  end
  @h[rest] = sum
end

@h = {}
puts throw(A)    #=>798000

798000通りと求められます。毎度おなじみの(?)深さ優先探索ですね。いわゆるメモ化をしないと現実的な時間で求められません。


下での模範解答はさらに短いです。すごいなあ。