データ構造を考える (KATAMINOを解くプログラムを作成する)

★前回の記事

yucatio.hatenablog.com

具体的なプログラミングに入る前に、データ構造を考えておきましょう。

KATAMINOを解くのに必要なものは、KATAMINOを入れるフィールドとKATAMINOのピースです。

フィールドのデータ構造

フィールドは 5 x {ピースの数} のマス目です。

これは2次元配列で表現できそうです。 まだピースが置かれていない場所は-1にしておきます。フィールドの幅が3つの時は以下のようになります。

[
  [-1, -1, -1],
  [-1, -1, -1],
  [-1, -1, -1],
  [-1, -1, -1],
  [-1, -1, -1]
]

ピースが置かれた場所は、そのピースの番号(ID)で置き換えます。

上の図のようにピースが置かれたときのデータは以下のようになります。(このT字のピースのIDは9です)

[
  [ 9,  9,  9],
  [-1,  9, -1],
  [-1,  9, -1],
  [-1, -1, -1],
  [-1, -1, -1]
]

以上がフィールドのデータ構造です。

ピースのデータ構造

ピースの表現のしかたは、2次元配列とピースのある場所のリストの2パターン考えられます。

例えば、このピースの場合

このピースを2次元配列で表現すると以下のようになります。ピースの場所を1, ピースでない場所を0で表現しています。

[
  [1, 1, 0],
  [0, 1, 0],
  [0, 1, 1]
]

リストで表現する場合は、上記の配列のピースの場所のみを抜き出して配列にします。

[
  {x:0, y:0},
  {x:0, y:1},
  {x:1, y:1},
  {x:2, y:1},
  {x:2, y:2}
]

2次元配列でも埋まっている場所のリストでも解くことはできますが、 ピースを置いたり、重なっている部分の判定がリストの方が効率よくできるので、今回はリストを採用します。

以上がピースのデータ構造です。

【ポイント11倍】Gigamic（ギガミック）社 カタミノ KATAMINO 3歳〜 ギフト プレゼント (ネコポス不可) puzzle 新入学 新入園 【k0507】 価格：6048円（税込、送料無料) (2019/6/20時点) 楽天で購入

★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com