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

KATAMINOとは

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


KATAMINOを解くアルゴリズム

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

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

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

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

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

  1. 使用するピースを決めます。今回は以下の3つのピースを使います。 f:id:yucatio:20190619230048p:plain
  2. 番号1のマスを埋めるように1つピースを置きます。
    • ピースは枠からはみ出して置くことはできません。

    f:id:yucatio:20190619225500p:plain:w250 f:id:yucatio:20190619225520p:plain:w250

  3. 残ったピースのうち、一番小さい番号(今回の例では3)を埋めるようにピースを置きます。
    • ピースは枠からはみ出して置くことはできません。
    • ピース同士は重なってはいけません。

    f:id:yucatio:20190619230949p:plain:w250 f:id:yucatio:20190619231009p:plain:w250

  4. 2を繰り返します。(今回の例では繰り返せないので下の手順へ進んでください)
  5. どのピースも置けなくなったら、ピースを回転または反転させます。2に戻ります。

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

    全てのピースの全ての回転を試したならば、1つ前のピースを回転または反転させます。

    f:id:yucatio:20190619231333p:plain:w250

  6. 全てのピースが置ければ終了です。

    f:id:yucatio:20190619231422p:plain:w250

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

f:id:yucatio:20190619231652p:plain

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

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

  1. スタックに、空のフィールドと次に置くピースの組み合わせを入れる
  2. スタックが空になるまで以下を繰り返す
    1. スタックからフィールドと次に置くピースの組み合わせを1つ取り出す
    2. ピースが置けるか判定する
      1. 置けなかったら繰り返しの先頭に戻る
    3. 置けたら、置いた状態のフィールドと次に置くピースをスタックに入れる
    4. 残っているピースがなければ完成
  3. スタックが空になった場合は解けない組み合わせだった

スタックのイメージ↓

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

以上がKATAMINOを解くプログラムの基本的なアルゴリズムです。次回はデータ構造について考えます。

★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com