Making Pair
IRCでみなさんが写真の話題で盛り上がるのを横目に、ワタクシ、ひたすらプログラム組んでました。
もとのソースをC#で組んでいたため、比較的C++への移植は容易か？と考えていたのですが、近年のjavaの呪いか、.NETの呪いか*1クラス宣言と実装を同時に書く癖が染み付いている自分に気付き愕然!(○□○)
感覚を取り戻すのに手間取ってしまいました*2。
さて、オリジナルのパズルを優先といいつつも、なぜかMaking Pairの方を先にC++化してしまっていて、「おまえ宣言したことぐらいちゃんとやれよ、この投げっぱなし男が！」と内外問わずお叱りを受けそうな気もしないでないですが、それはさておき、やはりデスクトップPCと比較するとリナザウは随分と遅いなぁ…というのが正直なところです。
…てなことで、今回は、Making Pairの問題自動生成にあたって感じたリナザウの速度について延べてみたいと思います(多分、プログラマン以外には、あまり面白くない話だと思います)。
昨日も少し触れましたが、Making Pairの問題作成には、詰め合わせ問題を解く必要があります。
元となるドミノを縦にしたり横にしたりしてどう配置すれば、７×８の長方形に納まるかを試行していくのですが、右→下→左→上といった風に試行するドミノの回転方向を固定してしまえば、解を導くこと自体はさほど難しくありません。
しかし、このパズルのキモは、ドミノがどのような形で置かれたかであって、どのドミノがどこに置かれるか？は重要ではないため、最初に出てきた解を採用するとすれば、このケースでは実は１パターンしか問題ができません*3。
そのために、今回のプログラムでは、試行する回転方向の順序も入れ替えて問題の多様性を実現する工夫をしています。
このように、ドミノを置く位置と方向を変えながら、順番に１つ１つ盤面にドミノを配置していき、２８個のドミノがすべて配置できた時点で問題が完成したとみなすのですが、回転試行方向をシャッフルしたパターンによっては、解に到達するまでに大量の計算を要する可能性があり、多いときには計算量が５０００回を越えることがあります。
動作周波数が1GHzのデスクトップPCであれば、一瞬待つくらいですが、A300で試したところ、３分待っても帰ってこないケースがありました*4。
問題の作成に１０秒以上かかるようであれば、レスポンス性としてどうしようもないので、現在は、ある程度の計算量を越える際は仕切り直すというような方法で、早期に問題を生成できるようにしています。
限定された環境下で、課題を実現するために、時に妥協をすることも必要となりますが、そのバランスを取るのは結構難しいものだなぁ…と感じる今日このごろです*5。
