ペンタミノの回転、反転をするためのアルゴリズム (KATAMINOを解くプログラムを作成する)

★前回の記事

KATAMINOのピース(ペンタミノ)は以下の12種類です。

f:id:yucatio:20190621081852p:plain

KATAMINOを解いていくときに、それぞれのピースを回転させたり裏返したりする必要があります。

この時の方針として、

とありますが、全体的な実装のしやすさから、1の方法を選択します。

KATAMINOのピースは12個あります。それぞれ、回転させたり裏返したりすると、1つのピースにつき最大で8パターンの形になります。回転や裏返したものを違う形として数えると、全部で63パターンあります。

f:id:yucatio:20190621083130p:plain

63パターン全てを手で入力するのは少し面倒ですので、12ピースのもとの配列から、残りのパターンを作成することにします。

まず、1つのピースから回転・反転させて全8パターンを作成します。

８パターンはこのようになります。

f:id:yucatio:20190621084539p:plain

さて、回転・反転と言葉で言うのは簡単ですが、どのようにプログラミングしていけばよいでしょうか。

いくつか方法はありますが、今回は転置(transpose)と反転(reverse)を使います。

転置とは、行列の行と列を入れ替えることです。配列で書くと以下のような変換が転置です。

[
  [1,2,3]      [1,4,7]
  [4,5,6]  ->  [2,5,8]
  [7,8,9]      [3,6,9]
]

転置すると、以下の図のように斜めにひっくり返されます。

f:id:yucatio:20190702083100p:plain

0番の形を転置をすると、7番の形になります。次に、転置したものを上下反転させます。そうすると1番の形になります。さらにこの形を転置すると6番の形になり、さらに上下反転すると2番の形になります。これを繰り返すと8種類全ての形を作成することができます。

f:id:yucatio:20190702083723p:plain

全てのピースについて、回転、反転を繰り返したのがこちらになります。

f:id:yucatio:20190621121150p:plain

さて、対称性があるピースは形が重複しているので、重複を取り除きます。実装方法については以降で扱います。

f:id:yucatio:20190621083130p:plain

以上で63パターンのピースの位置を出すことができました。次回はコーディングしていきます。

★次回の記事

★目次

yucatio@システムエンジニア