KATAMINOを解くアルゴリズム (KATAMINOを解くプログラムを作成する)

KATAMINOとは、Gigamic社が発売するパズルゲームです。ペンタミノという、5個の正方形をつなげてできる形をしたピースを使い、長方形の枠にぴったり収まるように組み合わせて遊ぶゲームです。

KATAMINOを解くアルゴリズムとして、総当たりの方法を採用します。

以下のように、左上から右に向かって順番に番号を振ります。

f:id:yucatio:20190619224647p:plain:w250

ピースが置かれていないマスのうち、一番小さい番号を埋めるようにピースを置いていきます。全てのピースが置ければおしまい、全ての組み合わせを試してみてどの組み合わせでもマスを全て埋めることができなければ解けない組み合わせです。

総当たりの手順は以下のようになります。

使用するピースを決めます。今回は以下の3つのピースを使います。
番号1のマスを埋めるように1つピースを置きます。
- ピースは枠からはみ出して置くことはできません。
残ったピースのうち、一番小さい番号(今回の例では3)を埋めるようにピースを置きます。
- ピースは枠からはみ出して置くことはできません。
- ピース同士は重なってはいけません。
2を繰り返します。(今回の例では繰り返せないので下の手順へ進んでください)
どのピースも置けなくなったら、ピースを回転または反転させます。2に戻ります。

全ての回転・反転を試した場合は、ピースを1つ戻して、まだ試していない別のピースを置きます。2に戻ります。

全てのピースの全ての回転を試したならば、1つ前のピースを回転または反転させます。
全てのピースが置ければ終了です。

解く過程を図にすると、以下のような木構造になります。

f:id:yucatio:20190619231652p:plain

KATAMINOを解くには、この木をもれなくたどっていけば良いことがわかります。木をたどるには、幅優先探索と深さ優先探索と2つのアルゴリズムがあり、上のアルゴリズムは深さ優先探索を用いています。

プログラムを書きやすくするために、もう少しプログラミングしやすい言葉を使って手順を書きます。深さ優先探索を採用するので、スタックを使用します。

スタックのイメージ↓

f:id:yucatio:20190619231821p:plain:w250