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通りと求められます。毎度おなじみの(?)深さ優先探索ですね。いわゆるメモ化をしないと現実的な時間で求められません。
下での模範解答はさらに短いです。すごいなあ。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (7件) を見る