ポリオミノを列挙する

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/a4be66d4-3ba4-44a9-b9c5-04f52f1d7465.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/ec2d61b5-af11-4d39-818b-31ae2680260c.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/11176a42-d5a7-462b-9a51-459633d50385.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/584f6444-1742-471e-ae5c-f5caa38b8eac.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/323cb19e-7375-4dbd-824e-9fe0e4a77380.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/a7d0509d-a9a2-4932-856d-f7a2996bfdb8.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/1a6832e7-1deb-4b7b-b0e9-431906b22657.png)

# はじめに
ポリオミノを列挙するプログラムです。
小学校の宿題で、「何種類あるかな？」「全部、描けるかな？」というのが出たので、実装したくなった次第です。

# 環境
Apple M1 pro
Processing 4.2

# ポリオミノの種類
| 正方形の数 | 日本語 | English | 種類 | 計算時間 |
|:-:|--:|--:|:-:|:-:|
|1|モノミノ|monomino|1|<1s|
|2|ドミノ|domino|1|<1s|
|3|トロミノ|tromino|2|<1s|
|4|テトロミノ|tetromino|5|<1s|
|5|ペントミノ|pentomino|12|<1s|
|6|ヘキソミノ|hexomino|35|<1s|
|7|ヘプトミノ|heptomino|108|1.4s|
|8|オクトミノ|octomino|369|13.4s|
|9|ノノミノ|nonomino|1285|259s|
|10|デコミノ|decomino|4655|-|

※このサイトのhextominoというのは、造語です。-ominoというのは四角を意味します。あとは、音の語感です。

※立方体の展開図は11種類です。

# プログラム
```java:polyomino.pde
import java.util.*;

ArrayList<HashSet<PVector>> pentominoes = new ArrayList<HashSet<PVector>>();
HashSet<String> seenShapes = new HashSet<String>();

void setup() {
  size(1100, 800);
  findPentominoes();
  println("見つかったペントミノの数：" + pentominoes.size());
  noLoop();
}

void draw() {
  background(255);
  drawPentominoes();
}

// --- 探索ロジック（前回と同じ） ---
void findPentominoes() {
  HashSet<PVector> start = new HashSet<PVector>();
  start.add(new PVector(0, 0));
  grow(start);
}

void grow(HashSet<PVector> shape) {
  if (shape.size() == 5) {
    if (!isDuplicate(shape)) {
      pentominoes.add(shape);
      seenShapes.add(shapeKey(normalize(shape)));
    }
    return;
  }

  for (PVector block : shape) {
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] dir : dirs) {
      PVector next = new PVector(block.x + dir[0], block.y + dir[1]);
      if (!containsPoint(shape, next)) {
        HashSet<PVector> newShape = new HashSet<PVector>(shape);
        newShape.add(next);
        grow(newShape);
      }
    }
  }
}

boolean containsPoint(HashSet<PVector> shape, PVector point) {
  for (PVector p : shape) {
    if (p.x == point.x && p.y == point.y) return true;
  }
  return false;
}

boolean isDuplicate(HashSet<PVector> candidate) {
  for (int r = 0; r < 4; r++) {
    for (boolean f : new boolean[]{false, true}) {
      HashSet<PVector> transformed = transform(candidate, r, f);
      String key = shapeKey(normalize(transformed));
      if (seenShapes.contains(key)) return true;
    }
  }
  return false;
}

HashSet<PVector> transform(HashSet<PVector> shape, int rotation, boolean flip) {
  HashSet<PVector> result = new HashSet<PVector>();
  for (PVector p : shape) {
    PVector q = p.copy();
    if (flip) q.x *= -1;
    for (int i = 0; i < rotation; i++) {
      q = new PVector(-q.y, q.x);
    }
    result.add(q);
  }
  return result;
}

HashSet<PVector> normalize(HashSet<PVector> shape) {
  float minX = Float.MAX_VALUE, minY = Float.MAX_VALUE;
  for (PVector p : shape) {
    if (p.x < minX) minX = p.x;
    if (p.y < minY) minY = p.y;
  }
  HashSet<PVector> result = new HashSet<PVector>();
  for (PVector p : shape) {
    result.add(new PVector(p.x - minX, p.y - minY));
  }
  return result;
}

String shapeKey(HashSet<PVector> shape) {
  ArrayList<String> coords = new ArrayList<String>();
  for (PVector p : shape) {
    coords.add((int)p.x + "," + (int)p.y);
  }
  Collections.sort(coords);
  return String.join(";", coords);
}

// --- ペントミノ描画 ---
void drawPentominoes() {
  int cols = 4;
  int cellSize = 40;
  int padding = 20;
  int i = 0;

  for (HashSet<PVector> shape : pentominoes) {
    int row = i / cols;
    int col = i % cols;
    float offsetX = col * (cellSize * 6 + padding) + 50;
    float offsetY = row * (cellSize * 6 + padding) + 50;

    drawShape(shape, offsetX, offsetY, cellSize);
    i++;
  }
}

// 各ペントミノの形を描く
void drawShape(HashSet<PVector> shape, float offsetX, float offsetY, int s) {
  HashSet<PVector> norm = normalize(shape);
  fill(100, 150, 255);
  stroke(0);
  strokeWeight(2);
  for (PVector p : norm) {
    float x = offsetX + p.x * s;
    float y = offsetY + p.y * s;
    rect(x, y, s, s);
  }
}
```

・正方形からなる全ての連結形状を再帰で生成
・回転・反転させて重複を除外

### 形状の表現
・各ペントミノは、(x, y) 座標の5つの相対位置のセット
　（例：[(0,0), (1,0), (2,0), (2,1), (3,1)]）で表現
・正規化（左上を原点）して比較

### 全体の保存形式
・```ArrayList<HashSet<PVector>>```：各ペントミノは、5個のPVectorを持つHashSetとして格納
・HashSetであれば順序の違いは無視されるため、形状の一致判定に便利

### 重複除去
・回転・反転した形状をすべて生成して、既存のリストに同じものがないか確認。
・回転4種 × 反転2種 → 8通りをすべて比較
・「正規化」＋「全変換（8通り）」
・HashSet<PVector> を直接使うのではなく、各図形を正規化・ソートして → List<PVector> → String に変換。その文字列を HashSet<String> に登録して、重複除外。


# 参考リンク

https://en.wikipedia.org/wiki/Polyomino

https://ja.wikipedia.org/wiki/ポリオミノ

https://qiita.com/hextomino/items/4c0ba4a812bb49eddb92