개요

N개의 정사각형을 변에서 연결한 다각형을 폴리오미노이라고 한다. 예를 들어 유명한 낙하물 게임의 테트리스에서는 N = 4의 폴리오미노가 사용되고있다.

N이 증가함에 따라, 폴리오미노의 수는 다음과 같이 지수 함수 1로 증가한다.


N
조합수(유향)


1
1

2
2

3
6

4
19

5
63

6
216

7
760

8
2725

...
...

24
5239988770268


폴리오미노의 수를 산출하는 식을 찾기 위해, 연구자들에 의해 상당한 노력이 이루어져 왔지만, 현재 상태에서는 아직 발견에 이르지 못하고 있다.

폴리오미노를 열거하는 알고리즘으로서 Redelmeier's algorithm이라는 것이 있다. 세기 때문에 필연적으로 지수 시간이 걸려 버리지만, 공간 계산량은 O(N)가 되는 알고리즘이다.

이 기사에서는 실제로 JavaScript로 알고리즘을 구현하고 이것을 시각적으로 확인한다.

Redelmeier의 algorithm

y > 0 or (y == 0 and x >= 0) 될 셀 공간을 고려하십시오

[0, 0]에 번호를 흔들어 境界セル로 한다

境界セル를 선택하면 다음 작업이 수행됩니다.

선택한 셀의 인접 셀의 빈 곳에 사전 순서(하좌우 상단)에 번호를 흔들어

번호를 흔든 셀에서 하나씩 선택하고 境界セル

그러나 이미 境界セル 인 최대 번호보다 작은 번호의 셀을 선택하지 않음

경계 셀의 선택을 재귀 적으로 깊이 N까지 수행함으로써 폴리오미노를 열거 할 수있다.

구현

잡히 알고리즘 그대로 구현한다.
다만, 나중에 스텝 실행할 수 있도록 재귀의 스택은 스스로 준비해 둔다.

var N = 3;
var nodeStack = [
  {
    cells: [{ x: 0, y: 0, num: 1, isBorder: false }],
    availableNumbers: [1]
  }
]; // 状態を保持するスタック

function confirmBorderCellNumber(node, num) {
  var cells = node.cells;
  var cell = cells.find(e => e.num == num);
  cell.isBorder = true;
  var dx = [0, -1, 1, 0];
  var dy = [-1, 0, 0, 1];
  for (var i = 0; i < 4; i++) {
    var x = cell.x + dx[i];
    var y = cell.y + dy[i];
    if (!(y > 0 || (y == 0 && x >= 0))) continue;
    if (cells.find(e => e.x == x && e.y == y)) continue;
    cells.push({ x: x, y: y, num: cells.length + 1, isBorder: false });
    node.availableNumbers.push(cells.length);
  }
}

function nextStep() {
  var node = nodeStack[nodeStack.length - 1];
  if (nodeStack.length > N || node.availableNumbers == 0) {
    nodeStack.pop();
  } else {
    var num = node.availableNumbers.shift();
    var newNode = JSON.parse(JSON.stringify(node)); // deep copy
    confirmBorderCellNumber(newNode, num);
    nodeStack.push(newNode);
  }
}

// スタックが空になるまでステップ実行
var found = 0;
while (nodeStack.length > 0) {
  nextStep();
  // 葉（depth = N）の場合のみ出力
  if (nodeStack.length > N) {
    var node = nodeStack[nodeStack.length - 1];
    var str = "";
    for (var y = N - 1; y >= 0; y--) {
      for (var x = 1 - N; x < N; x++) {
        var cell = node.cells.find(e => e.x == x && e.y == y);
        str += cell && cell.isBorder ? "#" : "_";
      }
      str += "\n";
    }
    console.log(++found);
    console.log(str);
  }
}

※ 계산량적으로 좋지 않은 실장이므로, 큰 N 을 조사하고 싶은 경우 잘 수정하는 것.

실행 결과

1
_____
__#__
__##_

2
_____
_____
__###

3
_____
___#_
__##_

4
_____
_##__
__#__

5
_____
__##_
__#__

6
__#__
__#__
__#__

시각화

한 단계씩 웹상에서 실행할 수 있도록 해 보았다.

N = 4 를 스텝 실행한 모습의 Gif 는 이런 느낌.



잘 중복을 배제하고 있는 것이 시각적으로 알 수 있다.

정리(+관계없는 이야기)

이 기사에서 한 일

Redelmeier 's algorithm에 대한 간략한 설명

Redelmeier 's algorithm을 JavaScript로 구현하고 폴리오미노 열거

열거 상태를 단계별로 실행할 수있는 웹 사이트 준비

조사에 이르는 경위

원래 왜 폴리오미노의 열거에 대해 조사했는가라고 하면, 뿌요푸요의 연쇄형의 탐색에 사용하기 위한 것이었다. (푸요푸요의 1연쇄는 N >= 4의 폴리오미노의 형태로 간주한다.)

직접 이 알고리즘을 도움이 된 것은 아니지만, 흥미로운 체인도 발견되었다.

2색 4개 지우기 16연쇄 동영상 htps // t. 코 / Ps Pen Gs 7 W 피 c. 라고 r. 코 m / 111 유 dFYv — REF@푸요 (@refpuyo) 10월 30, 2019

이 동영상에서는 수동으로 열거 된 N = 4의 폴리오미노 (테트로 미노)를 사용하여 체인 조합을 탐색했습니다. 여기에서 임의의 연결 수의 체인을 사용하기 위해 폴리오미노 열거 알고리즘을 사용하려고합니다. 그러나 N이 증가하면 연쇄 조합이 폭발적으로 증가하기 때문에 아직 잘 작동하지 않습니다. 누군가 도와주세요 ...

참고

• 폴리오미노 열거 - phyllo’s algorithm note
• n-omino의 열거 (Redelmeier 's algorithm) - matsu7874 블로그
• Handbook of Discrete and Computational Geometry —Third Edition—