プログラミング問題「六角形のテトロミノ」を解いてみた
オフラインどう書くシリーズの、「六角形のテトロミノ」問題を解いてみた。
この記事はネタバレになってしまうので、日々のコーディング筋トレネタに困っているプログラマの方は、先に問題にチャレンジすることをオススメする。
また、今回私が考えたことなどを振り返って、あらためて言うまでもないのだが、私には数学の技術的な知識が不足していることを痛感した。地道に学んでいきたい。今回私がとった解法について、すでに数学の世界には理論やアルゴリズムが確立されているはずだと思うのだが、浅学な私はそのような知見にたどり着けなかった（何を調べたらよいかも分かっていない）。もしご存知の方がいらしたら、ポインタだけでも教えていただけると幸いだ。
さて、今回の問題を見て最初に思い浮かぶ常套的な解法は、テトロミノの形を「4つの六角形のうち1つを原点とした位置ベクトル」で表し、そのベクトル列によって形を比較するというものだ。どのように座標に表わすかといった部分で、問題をきれいに表現できたり解けたりする。
このアプローチで解きかけていたのだが、途中でどうしても「回転」のことが気になり始めた。今回の問題では、回転や並行移動を行って重なる図形は同じ形とみなすのだ。つまり、「回転」や「移動」という操作を行っても変化しない「形の特徴」のみを抽出し、それ同士を比較するようにすればよいのではないか？
そんなアイデアが浮かんでしまい、どうしてもその道で行けるところまで進んでみたくなった。
六角形テトロミノの形をどう表わすか
そこで自分なりに考えてみた。考えるヒントとなったのは、中西昌武先生の概念フォーム理論で、データソース間の関係の構造を行列で扱っていたことだ。今回の問題の入口として、ある1つの六角形テトロミノを次のような規則で行列で表わすことにした。
(1) 六角形の各辺を、右上を0として0〜5のインデックスで表わす
(2) 六角形の位置を表わす文字を、六角形の識別子とする
(3) テトロミノを構成する各六角形ごとに、「隣接している六角形」を、隣接している辺インデックスと対象六角形の識別子とで表わす。
例：以下の六角形テトロミノの場合、次のような情報が抽出できる。
a: (2 → f)、f: (1 → g, 2 →k, 5 → a)、k: (0 → g, 5 → f)、g: (3 → k, 4 → f)
(4) 取り出した情報から行列を作る。行: 六角形ごとの情報、列: 辺ごとの情報。4行6列の行列になる。
これで、一旦形の情報を表現することができた。しかし、このままでは問題がある。
最初の行列表現の問題
これまでの手順では、最初に構成されたテトロミノの記号などをそのまま反映しただけなので、当然ながら以下の問題には対処していない。
- 行列の情報が、テトロミノの回転に依存したまま
- 行列の情報が、テトロミノの位置に依存したまま
この行列に何らかの手を施して、位置と回転に関する要素を取り除かなければいけない。一体どうしたら・・・
まず、現段階の行列でも、次の特徴は持っている。
- 行の順序を入れ替え（aを3行目、kを1行目にするなど）ても、同じ形を表現している
- 列をローテーション（インデックス0の列を一番右へ持ってくる）させても、同じ形を表現している
2はテトロミノを回転させる操作にあたる。
1と2を組み合わせると、行の順序を入れ替えたり、列のローテーションを行っても同じ形を表していることになるので、何らかのアルゴリズムで行の順序とローテーション回数が一意に定まるようにしてやれば、位置や回転に依存しない「構造行列」を導けるはずだ。
テトロミノの構造行列を導くアルゴリズム
- 行の順序（＝テトロミノの各要素の取り出し順）を決めるため、まず、どこを起点にするのかを決める。
この際、六角形毎の隣接数を評価して最小のものを選択する。これが同数ある場合は、1つ先の隣接要素の隣接数も可算して再評価する。テトロミノの場合は全要素数が4で、その半数である2、つまり今回は1つ先の隣接要素まで評価し、それでも最小スコアのものが同数ある場合は、その中の1つに決める。 - 起点六角形で隣接がある辺のうち最小のインデックスをもつものがインデックス0になるように、テトロミノ全体をローテーションする。
- 行の順序を決める。ローテーション後のテトロミノに対して起点六角形から開始して、隣接辺インデックスの昇順に、深さ優先で辿っていく。（ローテーションしているので、この時点で辺インデックスが変わっていることに注意）
- 行の順序に従って、行を入れ替える。
- 六角形の識別子を、行インデックスに変換する。
この操作を行うこと、最初の行列は、
- 起点六角形：a
- 順序：a→f→k→g
となり、変換を施すと次のような構造行列になる。
プログラムでは、10個の形の構造行列を最初に求めておき、テスト入力のテトロミノの構造行列を都度求めて、行列同士のマッチングにより形を決定している。ただそれだけだ。
この先の課題
もう少し先へ進んでみたいと思っており、具体的には以下の点をなんとかしたい。
- アルゴリズムの汎用化：N角形の場合、ポリオミノの場合
- 別のプログラミング言語での実装：この種の問題を解くコードをPHPで書くのはなんだかツライ・・
- 概念フォーム理論との対比：構造を行列で表わすという点は似ているが、実際に表現している特徴点が異なる、と思っている。その違いをハッキリさせておきたい。
- ユニットテスト：書く
