翔泳社では10月13日（火）に『プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問』を刊行、それを記念してCodeZine上でオリジナル問題を出題しました。
→「プログラミング、楽しめてますか？ 『プログラマ脳を鍛える数学パズル』がもらえるクイズキャンペーン開催」
回答を応募いただいた皆さん、お待たせしました。この場で回答を発表いたします。ソースコードは解答例であり、すべての回答についてきちんと精査しますのでご安心ください。
今回、正解者の中から3名の方に本書をプレゼントします、どうぞお楽しみに。また、正解したのに抽選に外れてしまった方には翔泳社のオンラインショップ「SEshop」で使用できる20％オフクーポンをお送りします。当選の発表・プレゼントの送付については個別にご連絡いたします。
解答とソースコード例：カラーボックスで作る本棚
まずは問題を振り返っておきましょう。
カラーボックスで作る本棚
手軽で便利な家具として人気のカラーボックスは、さまざまな種類が販売されています。今回は3段のカラーボックス（縦90cm、横60cm）を複数組み合わせて本棚を作ることを考えます（カラーボックスは横に倒すことで、雑誌など大きな本も入れられるようになります）。
上下左右に並べて配置して、見た目がスッキリするように「全体として長方形」になるようにします。例えば、5個のカラーボックスを使うと、下記左図のような8パターンが考えられます（下記右図のような配置は「全体として長方形」になっていないのでNGです）。
上記の条件において、20個のカラーボックスを使った場合、その配置が何パターンあるかを求めてください。
※個々のカラーボックスは区別せず、配置のパターン数のみを考えてください。また、置く場所には充分な広さと高さがあるものとします。
解答
答えは610通りです。
すべて並べ終わったときの配置が「全体として長方形」になる必要がありますので、最初に全体の長方形の形を決めてしまいます。長方形の形が決まると、その中にカラーボックスを配置していきます。左上から右下に向けて、縦か横のカラーボックスを配置していき、置けなくなると探索終了です。
カラーボックスの数が固定なので、長方形の面積は自動的に決まります。このため、長方形の縦の長さを決めると、横の長さも決まります。あとはカラーボックスを配置したかどうかを記録すれば探索できます。カラーボックスは90cm×60cmなので、3×2のサイズだと考えることができます。
下のソースコードでは、1次元の配列（box）でカラーボックスを配置した位置を表現しています（配置した位置に「1」をセット、まだ配置していない位置に「0」をセット）。
この配列に対して、「縦に置いた場合(2×3)、横に置いた場合(3×2)の位置に「1」をセットして、次の位置に置けるかを調べる」ということを繰り返します。Rubyでは、以下のように書くことができます。
# カラーボックスの個数
N = 20
# 長方形の面積
S = N * 2 * 3
# 設定できる高さを配列にセット
height = (2..(S-1)).to_a.select{|i| (S / i) * i == S}
def bookshelf(box, w, h, x, y)
if x >= w then
# 一行を埋めた場合、次の行に移動
return bookshelf(box, w, h, 0, y + 1)
end
if y >= h then
# すべて埋まっていた場合1、空きがあった場合0を返す
return box.count(0) == 0 ? 1 : 0
end
cnt = 0
if box[x + y * w] == 0 then # 現在の位置が空いている場合
# 縦に配置
if (x + 2 <= w) && (y + 3 <= h) then
if (box[x + y * w, 2] == [0, 0]) &&
(box[x + (y + 1) * w, 2] == [0, 0]) &&
(box[x + (y + 2) * w, 2] == [0, 0]) then
3.times{|hh| 2.times{|ww| box[x + ww + (y + hh) * w] = 1}}
cnt += bookshelf(box, w, h, x + 2, y)
3.times{|hh| 2.times{|ww| box[x + ww + (y + hh) * w] = 0}}
end
end
# 横に配置
if (x + 3 <= w) && (y + 2 <= h) then
if (box[x + y * w, 3] == [0, 0, 0]) &&
(box[x + (y + 1) * w, 3] == [0, 0, 0]) then
2.times{|hh| 3.times{|ww| box[x + ww + (y + hh) * w] = 1}}
cnt += bookshelf(box, w, h, x + 3, y)
2.times{|hh| 3.times{|ww| box[x + ww + (y + hh) * w] = 0}}
end
end
else # 現在の位置が埋まっている場合、次の位置に移動
cnt += bookshelf(box, w, h, x + 1, y)
end
cnt
end
cnt = 0
height.each{|h|
# 高さから幅を決定
w = S / h
# 初期状態から探索開始
cnt += bookshelf([0] * w * h, w, h, 0, 0)
}
puts cnt
パズルを解くときに、左上から右下に探索する手法はいろいろ考えられます。シンプルに実装するために有効な再帰の使い方だけでなく、境界の判定などさまざまな方法が書籍の中で登場しますので、ぜひ読んでみてください。
