● 基本戦略
一言で言うと、箱の隅から順に駒を置いてゆき、置けなくなったら別の向きや駒を試してみる、ということになります。しかし、これでプログラムがいきなり書ける人はいないでしょう。
その昔、人工知能ブームのとき、Prologという言語を使うと、問題を記述するだけで、あとは計算機が勝手に解いてくれる、などというまことしやかな宣伝が、おそらく何かの政治的意図で流されたことがあります。しかし、ほどなくして誇張であることがバレてしまい、Prologという優れたプログラム記述言語とともに人工知能は葬られてしまいました。
21世紀初頭の現在に至っても、C言語のような、いわゆる手続き型言語が主流として用いられています。そこでは与えられた問題をデータ型とアルゴリズムに分解して直接記述する必要があります。つまり、計算機が分かる程度に問題を噛み砕く必要があります。
まず、箱の単位となる各正方形に番号を付けます。そんなこと当たり前じゃないか、という人は、もうすでに計算機に毒されていると言ってよいでしょう。ちなみに、私など、何か多数の項目があると、どのように数字を割り振ればよいのか、と本能的に考えてしまうほどの中毒者です。
後で話題にするでしょうが、この番号の割り振り方は計算の速度に多大な影響を与えてしまうので、油断も隙もありません。結論を言うと、短い辺に平行に順に割り付けるとうれしくなります。
ペントミノのプログラムは公開していない(あまりにみじめな表示なので恥ずかしいから)ので、ヘキソミノのプログラムソースファイルsqu6s.cppの最初の部分を、時間があれば、ご覧ください。配置計算を容易にするために、ガードの正方形を設け、各行を連続した数値で割り振ってゆきます(上図。空色の部分が箱、紫がガード)。10x6の長方形なので、二次元の配列が自明に思えますが、ガード付きの一次元配列の方が都合が良いと思います。
つぎに、ペントミノの12種の駒に番号を付けます。こちらは順番に駒を詰めてゆく、という戦略を取る限り、趣味の問題です。たいてい駒にはアルファベットの一文字が割り当てられます。TやXみたいに文句のつけようの無いものもあれば、MなのかWなのかと議論の分かれそうなのもあり、実際、何通りかの割り当て方法があるようです。アルファベットの順番に番号を付ければよいでしょう。ちなみに、本スクリーンセーバーでは駒を回転させるプログラム(未公開)の出力順をそのまま採用しています。
駒は裏返しにしたり90度回転したりで、最大8通りの置き方ができます(上図。Fペントミノの例)。
駒を箱の任意の位置に置き、駒の5つの正方形にどの番号が割り振られたかを記録します。最も若い番号を0になるように調整します。整数5個の配列を用意し、5つの番号を小さい順に記録します。
後は箱に駒を詰めてゆくだけです。
箱内でまだ置かれていない正方形で最も若い番号のを探します。残っている駒の一つを取り出し、0番を合わせて、置けるかどうかチェックします。置ければ、次の駒の可能性を探すか、もう駒が無ければ完成なので適当に出力します。置けなければ、次の向きを試します。向きが尽きたら、次の駒を試します。駒が残っていなければ、これまでの置き方が失敗ですから、箱内の一つ前の駒に戻って考えます。最初の駒が失敗したら、もう可能性は無いのでプログラムを停止します。
文章で書くと以上のようになります。
● 速度向上のために
▼ 駒順は最終的には速度に関係しない
上述の、ペントミノの解の探索は現在の計算機ではお茶を飲んでいる間にやり尽くすと思います。ヘキサモンドの全解探索もほんのしばらくです。ですから、速度向上を考える気になるのは、ヘプタモンド、ヘキソミノ、ペンタセン、ということになります。
ヘキソミノの解探索に挑戦した人は多いようで、速度向上の議論がWeb上で行われていました。駒順を適当に変えると劇的に初期の検索速度が向上します。しかし、ペントミノで試してみれば分かりますが、駒順を変えても、内部的な全探索数は変わりません。つまり、平均速度は変わらないのです。ただし、以下に述べるすべての条件を試していないので、もしかしたら何かあるかもしれません。
▼ 駒を置く方向は速度を劇的に変える
一方、縦方向に詰めるか、横方向に詰めるかは重大問題です。なるべく短い辺に沿って詰めるのがコツです。
ペンタセンの場合はほぼ自明で、箱を縦長のダイヤモンド型に置いて、横優先で探索するの簡単でかつ強力と思います。本スクリーンセーバでも、もちろんその方式を採用しています。
ヘプタモンドはほとんどどうしようもなく、本スクリーンセーバでは単純にそのままの配置としています。というより、何とか見栄え良く動いているので、それ以上あまり努力しなかった、というのが正直なところです。
ヘキソミノは議論されただけあって、Webですばらしいアイデアが提案されていました。つまり、最初はもちろん短辺に沿って並べてゆくのですが、しだいに残りの領域が縦長になってゆきます。そこで、適当な場所で探索方向を90度変更するのです。ヘキソミノは駒数が多いので、多分効果は絶大でしょう。
しかし、ここで私のへそ曲がり精神が顔を出してしまいました。ペンタセンが斜め順のように見えますので、ヘキソミノも箱を45度傾けてみました。こうすると早めに方向転換の効果が現れると思われました。このページをここまで見ていただいた方には申し訳ないのですが、暇が無いので実測していません。斜め+方向転換方式にはいくつかのバリエーションがあるので、本気になるなら慎重に実験して速度を計測すべきでしょう。
▼ 残りの領域が分割されているかを調べる
これは効果絶大です。無駄な探索を大幅に節約してくれます。つまり、箱の中の連続した空欄の数が、たとえばヘキソミノなら6で割り切れるかどうかを調べるのです。もちろん、半端なら、いくらその先努力しても完全には埋まりません。ですからその時点で配置失敗です。
▼ その他
ヘキソミノ等では箱を構成する正方形と駒を市松模様に彩色し、奇遇検査(パリティチェック)をすれば良いのかもしれません(アイデアだけで試していません)。他にもアイデアは出ると思います。
しかし、いずれにせよ、一つ一つ解を求めるやり方では、ヘキソミノなどの全解を求めるのは不可能と思われます。
こんなときは、部分問題に分割するのが常道です。
スクリーンセーバーをしばらく眺めていると分かりますが、同じ残り駒で同じ形を再び埋めようとする努力を計算機がしていることがあります。これは全く無駄です。ですから、ある程度のところでまとめて、各々の組み合わせ数を求め、掛け算すれば解の小計が求まります。副次効果として、多数のCPUで並行して計算できる可能性が生じます。世界のパソコンは誕生から今までに10億台売れたそうですから、首尾よく協調動作させると手に届く問題に還元できるのではないでしょうか。もっとも、ヘキソミノの探索にCPU時間を貸してくれるかどうかは微妙と思います。
2002年7月9日 岡田好一