« 接点と円と三角形のパズル | メイン | 接点と円と三角形のパズル(解答編) »

マッチ棒の並べ方パズル(解答編)

 以前に出題したマッチ棒の並べ方パズルの解答編です。

 この問題は N(120,12) を 108 で割った余り、つまり下8桁を求める問題です。ちょっと考えれば分かりますが、いわゆる単純な総当りでは決して解けません。並べ方は全部で 22*120*12+120+12 ≒ 5×10906 通りもありますので、これらを全て列挙して数えるというのはあまりに非現実的です。

 ではどうするか? プロジェクトオイラーを遊び倒すガイド(上級編)で説明した、大きすぎる問題を小さな問題に分割するアプローチが必要になります。今回の場合は、一回り小さいサイズの問題を考えることで目的のパターン数が表せないかを考えます。

 W=3, H=2 の場合を例にします。これより一回りサイズの小さい問題、2×2 の図形に対し、下図のように、右側にヨの形の数本のマッチ棒を足してやれば、新たに 3×2 の図形を得ることができます。このとき、もし 2×2 が条件を満たしているとすると、くっつけるマッチ棒の向きを適切に選んでやれば、3×2 でも条件を満たすことが可能になります。ですので、2×2 でのパターン数が既に分かっているならば、そこに可能なヨ型のパターン数を掛け合わせることで 3×2 のパターン数が分かるのではと期待されます。さらにこの手順を繰り返せば、4×2、5×2、・・・ のパターン数も分かるのではと期待されます。

 しかし、この考えはうまくいきません。下の例を見てください。2×2 から 3×2 を作る例を示していますが、もともとの 2×2 は、右列に頭のない格子点(青丸)があり、条件を満たしていません。ですが、ここに適切なマッチ棒を足せば、条件を満たす 3×2 を作ることが可能です。このように、条件を満たす並べ方だけに着目したのでは、うまく計算できません。

 ではどうすればいいか。条件を満たす並べ方だけを追うのでなく、頭のない格子点を右列に含む並べ方も一緒に求めるという考え方が必要になってきます。右列の格子点の頭のあるなしを1つの状態とみなして、可能な状態をすべて列挙します。右列以外の格子点はすべて条件を満たします。H=2 の場合、可能な状態は下記の5つです。なお H=2 なら手書きで十分列挙できますが、H=20 の場合は、列挙の手続きもプログラミングして自動化する必要があります。

 状態の列挙ができれば、次は、横 W-1 における各状態のパターン数が与えられたもとでの、横 W における各状態のパターン数を計算します。別の言い方をすると、横 W-1 における状態1~5のパターン数を P(W-1,状態1),・・・, P(W-1,状態5) と書くとき、これらの値から P(W,状態1),・・・, P(W,状態5) を得る変換行列を考え、この各要素の値を計算します。

 この行列が作られたら、あとは初期状態に相当する P(0,状態1),・・・, P(0,状態5) を別の手段で求めて、ここに行列を W 回作用させることで、P(W,状態1),・・・, P(W,状態5) が得られます。

 以上の手続きをまとめます。

1.可能な状態を列挙する。
2.W-1 に対する各状態のパターン数から W に対する各状態のパターン数を得る変換行列を計算する。
3.W=0 に対する各状態のパターン数を計算する。
4.3に2の行列を W 回作用させる。

 この後、右列のすべての格子点が頭を含む状態の値を見れば、それが求めるべき N(W,H) の値になります。

 以下、各ステップの処理を少し詳しく見ていきます。

 可能な状態というのは、もういちど書くと、W×H のうち右列以外の格子点がすべて頭を含む状態です。右列の頭のあるなしに応じて、状態を分類します。

 実際に紙に書いてみると容易にわかりますが、隣り合う2点は必ず少なくとも一方が頭を含むため、可能な状態の数はそれほど多くはありません下記のコードでは EnumerateState() 関数で、再帰的に計算しています。なお本コードでは、各状態を表現するために、右列の書く格子点の頭のあるなしを、std::bitset を用いて上から順に1または0で表しています。もちろん好きなデータ構造で表現して構いません。

 横 W-1 の各状態から横 W の各状態へ推移するパターン数を求めます。これは少々プログラミングが複雑です。頭を含まない格子点にくっつくマッチ棒は、向きが一意に定まりますが、そうでないマッチ棒は、どちらの向きでも構わないため、可能なパターン数は増えます。下記のコードでは GetNext() 関数で計算しています。詳細は省きますが、再帰呼び出しを用いて、上から下へ、推移の前後の bitset の並びを見比べながら可能なパターン数を計算していきます。可能なマッチ棒の向きは直前に置いたマッチ棒の向きに依存するため、この情報を下位に伝えるためのフラグ f を設けています。また、計算時間の節約のため、いちど算出した数値をキャッシュしておいて再利用しています。これをすべての状態×状態の組み合わせについて行います。

 初期状態、すなわち W=0 における並び方を調べます。W=0 というのはつまりは H 本のマッチ棒が縦1列に並んだ形です。本問の H=20 の場合、総数は 220≒106 にすぎないので、すべての並び方を網羅して対応する状態のカウントを1ずつ増やすやり方で十分です。

 最後に、初期状態に対し、2で求めた行列を作用させます。これはちょうどベクトルに行列を掛け算するのに等しいです。

 先に挙げた H=2 を再び例にします。5つの各状態から各状態へ推移するパターン数は次の通り表されます。横 W に置ける状態iのパターン数を P(W,状態i) と表しています。初期状態は状態1~4がそれぞれ1つずつですので、ベクトル (1,1,1,1,0) に下の行列を繰り返し作用させると任意の W に対する各状態のパターン数が分かります。実際 W=3 では (1977,4603,3031,4603,7618) になります。状態5の数がたしかに 7618 になっていることが分かります。

 以上の処理を書いたコードをこちらに示します。走らせると、数秒程度で正解の 59942368 が出てきます。もちろんコードの書き方やアルゴリズムの組み方は人それぞれですし、今回紹介したものよりずっと簡潔な方法があるかもしれません。今回の解き方はあくまで一例いうことで。。。

 ちなみに完全な形の答えは N(120,12) =
17268157720477448259243004642083272767058997861064539380548157646
33971465843490790094653847489451623670371334807715010826881954216
81518396262143363955934295105735894303039445053069663558074250869
71127010260826397810760477040616285745335811808026930999091677122
36805752608974117681035771110869541626782209001481564264373963313
39838762704623389687564055706386321430111296854386558533084209538
14340043982473734048668990820611548322915560216458700736569321496
70391027855602024022416850165800817096410887071327241158229355795
83929217390134709480431524138275991128496503121774907338471997857
24138028609176030496280078858249167414757118968829723052086617843
77839890128387810174960169017474650667064878746786424853688716591
77929646402110533795992955207959809188783443567703722824428780526
9494241230319482006866744324939170288791240823607240834559942368 です。

 なお、本問は xsd さんと niino さんのお二人に正答いただきました。出題した翌日には正解という早さでした。多謝!

 

トラックバック

このエントリーのトラックバックURL:
http://www.riverplus.net/cgi/mt/mt-tb.cgi/3201

コメント (4)

抹茶ょ:

おぉぉ~、凄い!!
完全な形の答え、凄すぎ(笑)
海外にある、IQいくつか以上の人しか入れない団体(MENSA?)に入れないかな♪

riverplus:

完全な形のは圧倒されますね。
実際に数え上げたわけでもないのに、こういう数がちゃんと計算できてしまうのが面白いところです:)

なるほど。気づきませんでした。行列表示ができるということは、N(2^64, 120)みたいな値も求められるということですね。

riverplus:

そうなりますねー、n乗の計算を工夫すれば 2^64 ぐらいでもいけちゃいますね。
n乗をがんばって書き下せば、一般項を与えることも可能なのかな。。

コメントを投稿