ポリオミノを列挙する

はじめに

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

環境

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種類です。

プログラム

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 を直接使うのではなく、各図形を正規化・ソートして → List → String に変換。その文字列を HashSet に登録して、重複除外。

参考リンク