20個のカラーボックスで作る本棚は何通り？『プログラマ脳を鍛える数学パズル』キャンペーンクイズの解答

答えは610通りです。 すべて並べ終わったときの配置が「全体として長方形」になる必要がありますので、最初に全体の長方形の形を決めてしまいます。長方形の形が決まると、その中にカラーボックスを配置していきます。左上から右下に向けて、縦か横のカラーボックスを配置していき、置けなくなると探索終了です。 カラーボックスの数が固定なので、長方形の面積は自動的に決まります。このため、長方形の縦の長さを決めると、横の長さも決まります。あとはカラーボックスを配置したかどうかを記録すれば探索できます。カラーボックスは90cm×60cmなので、3×2のサイズだと考えることができます。 下のソースコードでは、1次元の配列（box）でカラーボックスを配置した位置を表現しています（配置した位置に「1」をセット、まだ配置していない位置に「0」をセット）。 この配列に対して、「縦に置いた場合(2×3)、横に置いた場合(3