펜토미노
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
펜토미노는 5개의 정사각면으로 이루어진 12개의 도형을 일컫는 말로, 1907년 헨리 듀더니의 저서에 처음 등장했다. 1953년 솔로몬 W. 골롬 교수가 공식 정의하고 1965년 마틴 가드너가 사이언티픽 아메리칸의 수학 게임 칼럼에서 다루면서 널리 알려졌다. 펜토미노는 대칭성에 따라 여러 그룹으로 나눌 수 있으며, 12개의 펜토미노 조각을 사용하여 직사각형을 채우는 타일링 퍼즐, 펜토미노 팜, 입체 펜토미노 퍼즐 등 다양한 게임 및 퍼즐로 활용된다. 또한 펜토미노를 이용한 보드 게임도 존재한다.
더 읽어볼만한 페이지
- 폴리폼 - 폴리아몬드
폴리아몬드는 정삼각형을 이어 붙여 만든 도형으로, 삼각형 개수에 따라 n-아몬드라 불리며 조합론에서 종류와 개수를 파악하는 것이 중요하고, 평행 이동, 회전, 반사에 따라 자유형, 단면형, 고정형으로 분류되며, 폴리오미노, 폴리헥스와 유사하고 보드 게임의 구성 요소로 활용된다. - 폴리폼 - 테트로미노
테트로미노는 4개의 정사각형이 변끼리 연결된 폴리오미노로, 회전 및 반사 고려 방식에 따라 자유, 단면, 고정 테트로미노로 나뉘며, 직사각형 채우기 퍼즐과 테트리스 게임에 활용된다. - 수학 게임 - 테트로미노
테트로미노는 4개의 정사각형이 변끼리 연결된 폴리오미노로, 회전 및 반사 고려 방식에 따라 자유, 단면, 고정 테트로미노로 나뉘며, 직사각형 채우기 퍼즐과 테트리스 게임에 활용된다. - 수학 게임 - 폴리오미노
폴리오미노는 n개의 정사각형을 변으로 연결하여 만든 도형으로, 평행이동, 회전, 반사를 통해 겹쳐지는지에 따라 분류되며, 테트리스와 같은 게임에 활용된다. - 퍼즐 - 다른 그림 찾기
다른 그림 찾기는 거의 동일한 두 그림에서 시각적 비교 등을 통해 서로 다른 부분을 찾아내는 퍼즐이다. - 퍼즐 - 몬티 홀 문제
몬티 홀 문제는 세 개의 문 중 하나를 선택한 후 진행자가 상품이 없는 문을 열어 보여줄 때, 선택을 바꾸는 것이 유리한지를 묻는 확률 문제로, 직관과 달리 선택을 바꾸는 것이 당첨 확률을 높이는 전략임을 보여주는 확률 역설이며, 의사 결정 방식에 대한 통찰을 제공한다.
| 펜토미노 |
|---|
2. 역사
펜토미노 전체 세트가 포함된 가장 초기의 퍼즐은 1907년에 출판된 헨리 듀더니의 저서, 캔터베리 퍼즐에 등장했다.[4] 펜토미노 전체 세트로 사각형을 채우는 가장 초기의 타일링 문제는 1935년 the Problemist 요정 체스 부록에 등장했으며, 이후 PFCS와 그 후속작인 Fairy Chess Review에서 더 많은 타일링 문제가 다루어졌다.[5][6]
펜토미노는 1953년 미국의 교수 솔로몬 W. 골롬에 의해 공식적으로 정의되었고,[1][7] 1965년 그의 저서 ''다각형 타일: 퍼즐, 패턴, 문제 및 포장''을 통해 소개되었다.[1][7] 같은 해 10월, 마틴 가드너가 사이언티픽 아메리칸의 수학 게임 칼럼에서 펜토미노를 다루면서 일반 대중에게 널리 알려지게 되었다.
펜토미노는 많은 제조사에서 퍼즐이나 사고력 장난감으로 출시되고 있으며, 플라스틱이나 나무 제품이 많다. 대표적인 제품으로 일본 텐요사의 플라퍼즐이 있다. 조각이 12종류라는 점을 이용하여 각 조각을 12 별자리나 십이지에 비유한 디자인도 발표되었다.
솔로몬 골롬은 1975년에 '펜토미노' 상표를 등록했지만, 1982년경에는 효력이 상실된 것으로 보인다. 후지쯔에서 컴퓨터 개발에 힘썼던 이케다 토시오는 완구 회사의 의뢰로 펜토미노를 접한 후 깊이 빠져 텔레비전에 출연하여 소개했다는 일화가 있다.[20] 알렉세이 파지트노프는 펜토미노에서 테트리스의 아이디어를 얻었다고 알려져 있다.[21]
2. 1. 명칭
펜토미노는 1953년 미국의 교수 솔로몬 W. 골롬에 의해 공식적으로 정의되었다.[1][7] 골롬은 고대 그리스어 πέντεgrc (''pénte'', "다섯")와 도미노의 "-omino"를 결합하여 "펜토미노"라는 용어를 만들었다. 이는 "도미노"의 "d-"를 마치 그리스어 접두사 "di-"(둘)처럼 해석한 것이다.[1][7]
골롬은 12개의 자유 펜토미노 각각에 라틴 문자를 사용하여 이름을 붙였는데, 이는 각 조각의 모양과 비슷하게 보이는 글자를 딴 것이다. 연상 기호로 "FILiPiNo"와 알파벳 끝 부분인 "TUVWXYZ"를 사용하면 12개의 이름을 기억하는 데 도움이 된다.[8]
존 호턴 콘웨이는 펜토미노에 대한 다른 명명 체계를 제안했다. 이 방식은 골롬의 명명법에서 I 대신 O, L 대신 Q, F 대신 R, N 대신 S를 사용한다. 문자 모양 자체는 골롬 방식보다 덜 직관적일 수 있지만(특히 O 펜토미노), 알파벳의 연속된 12개 문자(O, P, Q, R, S, T, U, V, W, X, Y, Z)를 사용한다는 장점이 있다. 콘웨이의 명명법은 콘웨이의 생명 게임과 같이 특정 맥락에서 사용되기도 한다. 예를 들어, 이 게임에서는 F-펜토미노 대신 R-펜토미노라는 명칭을 사용한다.
3. 대칭성
12개의 자유 펜토미노는 그 대칭성에 따라 분류할 수 있다.
- '''F, L, N, P, Y''' (5개): 8가지 방식으로 방향을 잡을 수 있다. 4가지 회전 방식과, 거울상으로 4가지 방식이 더 있다. 이들의 대칭군은 항등 사상만으로 구성된다.
- '''T, U''' (2개): 4가지 방식으로 회전하여 방향을 잡을 수 있다. 격자선과 평행한 반사 축을 갖는다. 이들의 대칭군은 두 개의 원소, 즉 항등원과 정사각형의 변과 평행한 선에서의 반사로 구성된다.
- '''V, W''' (2개): 회전을 통해 4가지 방식으로 방향을 잡을 수 있다. 격자선에 대해 45° 각도의 반사 대칭 축을 갖는다. 이들의 대칭군은 두 개의 원소, 즉 항등원과 대각선 반사로 구성된다.
- '''Z''' (1개): 4가지 방식으로 방향을 잡을 수 있다. 2가지 회전 방식과, 거울상으로 2가지 방식이 더 있다. 점대칭(2차 회전 대칭)을 갖는다. 이들의 대칭군은 두 개의 원소, 즉 항등원과 180° 회전으로 구성된다.
- '''I''' (1개): 회전을 통해 2가지 방식으로 방향을 잡을 수 있다. 격자선과 평행한 두 개의 반사 대칭 축을 갖는다. 이들의 대칭군은 네 개의 원소, 즉 항등원, 두 개의 반사, 180° 회전으로 구성된다. 이는 클라인 네 그룹이라고도 알려진 2차 이원수학군이다.
- '''X''' (1개): 단 하나의 방식으로만 방향을 잡을 수 있다. 격자선 및 대각선과 평행한 네 개의 반사 대칭 축과 4차 회전 대칭을 갖는다. 이들의 대칭군인 4차 이원수학군은 여덟 개의 원소를 갖는다.
F, L, N, P, Y, Z 펜토미노는 키랄성을 가진다. 즉, 자신의 거울상과 겹쳐지지 않는다. 이들의 거울상(F′, J, N′, Q, Y′, S)을 별개의 조각으로 간주하면, '단면' 펜토미노의 수는 총 18개가 된다.
만약 회전도 별개의 방향으로 간주한다면, 각 펜토미노는 다음과 같은 수의 '고정된' 방향을 가진다.
- F, L, N, P, Y: 각각 8가지 방향
- T, U, V, W, Z: 각각 4가지 방향
- I: 2가지 방향
- X: 1가지 방향
따라서 고정된 펜토미노의 총 개수는 5 × 8 + 5 × 4 + 1 × 2 + 1 × 1 = 40 + 20 + 2 + 1 = 63개이다.
다음은 각 펜토미노의 가능한 방향을 보여주는 예시이다.
'''8가지 가능한 방향'''
'''4가지 가능한 방향'''
4. 게임 및 퍼즐
펜토미노는 여러 제조사에서 퍼즐이나 사고력 장난감 형태로 출시되고 있으며, 주로 플라스틱이나 나무로 만들어진다. 일본의 완구 회사 텐요에서 만든 플라퍼즐이 대표적인 제품 중 하나이다.
펜토미노 조각이 12종류라는 특징을 활용하여, 각 조각을 12 별자리나 십이지에 비유한 디자인의 제품도 있다. 펜토미노를 이용한 퍼즐과 게임은 크게 평면 타일링 퍼즐, 입체 퍼즐, 보드 게임 등으로 나눌 수 있다.
4. 1. 타일링 퍼즐 (2D)
표준 '''펜토미노 퍼즐'''은 12개의 펜토미노 조각을 모두 사용하여 직사각형을 타일링하는 것이다. 즉, 조각들이 서로 겹치거나 빈틈이 생기지 않도록 완전히 덮어야 한다. 12개의 펜토미노는 각각 단위 정사각형 5개의 넓이를 가지므로(총 60 단위 정사각형의 넓이), 만들 수 있는 직사각형의 넓이도 60이어야 한다. 가능한 직사각형의 크기는 6×10, 5×12, 4×15, 3×20 네 가지이다.
각 크기의 직사각형을 만드는 해법의 개수는 다음과 같다(회전 및 대칭 이동으로 같은 모양이 되는 경우는 하나로 계산).
| 직사각형 크기 | 해의 개수 | 비고 |
|---|---|---|
| 6×10 | 2,339가지 | 1960년 콜린 브라이언 하젤그로브와 제니퍼 하젤그로브 부부가 처음 해결[9] |
| 5×12 | 1,010가지 | |
| 4×15 | 368가지 | |
| 3×20 | 2가지 | 아래 그림 참조 |
3×20 크기의 직사각형 퍼즐은 단 2가지 해법만 존재한다. 그림에 표시된 해법 외에 다른 하나는 L, N, F, T, W, Y, Z 펜토미노로 구성된 중앙 블록을 전체적으로 회전시켜 얻을 수 있다.
직사각형 채우기 외에 다른 형태의 펜토미노 타일링 퍼즐도 있다. 비교적 쉬운 문제 중 하나는 8×8 크기의 정사각형 중앙에 2×2 크기의 구멍이 있는 형태를 채우는 것인데, 이 문제는 1958년 다나 스콧이 해결하였으며 총 65가지 해법이 존재한다.[10] 스콧의 알고리즘은 최초의 백트래킹 컴퓨터 프로그램의 응용 사례 중 하나로 알려져 있다. 이 퍼즐의 변형으로 4개의 단위 정사각형 크기 구멍을 임의의 위치에 배치하는 규칙도 있다. 하지만 특정 위치에 구멍을 배치하면 퍼즐을 푸는 것이 불가능해지기도 한다. 예를 들어, 보드의 양쪽 모서리 근처에 구멍 쌍을 배치하여 P-펜토미노만 들어갈 수 있게 만들거나, 특정 펜토미노(T 또는 U)를 구석에 강제로 배치하게 만들어 다른 구멍이 생기도록 유도하는 경우가 해당된다.
이러한 펜토미노 타일링 문제를 푸는 효율적인 알고리즘은 도널드 커누스 등에 의해 연구되었으며,[11] 현대의 PC 성능으로는 대부분의 펜토미노 퍼즐을 몇 초 안에 해결할 수 있다.
펜토미노 세트는 단일 직사각형으로 구성된 사소한 모노미노 및 도미노 세트를 제외하고, 직사각형에 채울 수 있는 유일한 자유 폴리오미노 세트이다.
4. 2. 펜토미노 팜
펜토미노 1세트를 사용하여 빈 공간이 있는 도형을 만드는 문제를 통칭하여 펜토미노 팜이라고 부른다. 이때 빈 공간의 모양에는 제한이 없지만, 외부와 점으로 접촉해서는 안 된다는 조건이 있다.만약 외형과 빈 공간의 모양 모두에 아무런 제한이 없다면, 만들 수 있는 빈 공간의 최대 면적은 128임이 증명되었다.[18]
다양한 제한 조건을 가진 문제들도 존재한다. 예를 들어 다음과 같은 조건 하에서 확인된 최대 빈 공간 면적들이 있다.
많은 문제에서 해의 총수를 직접 손으로 구하는 것은 매우 어렵기 때문에, 컴퓨터를 이용하여 탐색하는 경우가 많다. 한편, 앞서 언급된 최대 빈 공간 면적(128)에 대한 증명은 기계적인 계산이 아닌 수학적 증명으로 이루어졌으며, 이를 증명한 시마우치(島内)는 문제 해결 과정에서 선입관에 사로잡히는 위험성에 대해 주의를 환기하기도 했다.
특정 형태의 펜토미노 팜 문제 중 하나로, 8×8 정사각형의 정중앙에 2×2 크기의 구멍(빈 공간)이 있는 형태를 펜토미노로 채우는 문제가 있다. 이 문제의 해는 1958년 데이 나 스코트(Dana Scott)에 의해 총 65가지임이 밝혀졌다.
4. 3. 입체 펜토미노 (3D)
각 펜토미노의 정사각형을 정육면체로 만든 12종류의 입체 도형을 '''입체 펜토미노''' 또는 '''플레이너 펜타큐브'''(Planar Pentacubeeng)라고 부른다. 이는 다섯 개의 정육면체로 이루어진 폴리큐브의 일종인 '''펜타큐브'''(Pentacubeeng) 중, 평면(1층 두께) 형태를 가지는 12가지 종류에 해당한다.[12]
이 12개의 입체 펜토미노 조각들을 모두 사용하여 직육면체 상자를 빈틈없이 채우는 퍼즐이 있다. 각 조각의 부피는 5 단위 정육면체이므로, 완성된 직육면체의 부피는 60 단위 정육면체가 되어야 한다. 가능한 직육면체의 크기와 알려진 해의 개수는 다음과 같다.
특히 3×4×5 크기의 퍼즐은 3940가지의 해가 있는데, 일본의 완구 회사 텐요에서 출시한 플라스틱 퍼즐 제품에는 'FACOM'이라는 애칭이 붙었다. 이는 당시 퍼즐의 모든 해를 계산하는 데 사용된 후지쯔의 컴퓨터 FACOM 270 시리즈에서 유래한 이름이다.
참고로, 평면 형태가 아닌 입체적인 형태의 펜타큐브도 존재한다. 평면 펜타큐브 12종 외에 키랄 쌍(서로 거울상 관계) 6세트와 5개의 추가 조각을 합쳐 총 29종의 펜타큐브가 있다. 하지만 이 29종의 펜타큐브 전체를 사용하여 직육면체를 만드는 것은 불가능하다.
또한, 12개의 서로 다른 조각 대신 한 종류의 입체 펜토미노만을 여러 개 사용하여 직육면체를 만드는 문제도 있다. 이 경우 'X' 모양 조각을 제외한 모든 종류의 조각으로 직육면체를 만들 수 있는 해가 존재하는 것으로 알려져 있다. 예를 들어 'I' 모양 조각은 그 자체로 1x1x5 또는 1x5x1 크기의 직육면체이며, 25개를 모아 5x5x1 형태의 정사각형 판이나 5x5x5 정육면체도 만들 수 있다.
4. 4. 보드 게임
펜토미노를 기반으로 하는 기술 중심의 보드 게임들이 있으며, 종종 단순히 "펜토미노"라고 불린다.그중 하나인 "골롬의 게임"은 8×8 격자판에서 두 명 또는 세 명의 플레이어가 진행한다. 플레이어들은 가지고 있는 펜토미노 조각을 서로 겹치거나 판 밖으로 나가지 않게 번갈아 놓으며, 마지막으로 조각을 놓는 사람이 승리한다. 2인용 버전은 1996년 힐러리 오만(Hilarie Orman)에 의해 약하게 해결되었는데, 약 220억 개의 게임 상태를 분석한 결과 먼저 두는 플레이어가 반드시 이기는 것으로 증명되었다.[13]
펜토미노 또는 유사한 모양들은 다른 여러 타일 배치 게임들의 기초가 되기도 한다. 예를 들어, 프랑스 보드 게임 ''블로커스''(Blokus)는 펜토미노 12개, 테트로미노 5개, 트리오미노 2개, 도미노 1개, 모노미노 1개로 구성된 4가지 색상의 폴리오미노 세트를 사용한다. 목표는 모든 타일을 사용하는 것이며, 마지막 조각으로 모노미노를 놓으면 보너스를 얻는다. 게임 종료 시 남은 블록 수가 가장 적은 플레이어가 승리한다. ''카테드랄''(Cathedral) 게임 역시 폴리오미노를 기반으로 한다.[14]
파커 브라더스는 1966년에 ''유니버스''(Universe)라는 여러 명이 즐길 수 있는 펜토미노 보드 게임을 출시했다. 이 게임은 1968년 영화 ''2001: 스페이스 오디세이''에서 우주비행사가 HAL 9000 컴퓨터와 펜토미노 게임을 하는 삭제된 장면에서 영감을 얻었다(영화에는 다른 우주비행사가 체스를 두는 장면만 남았다). 게임 상자 앞면에는 영화의 장면과 함께 '미래의 게임'이라고 묘사하는 문구가 있다. 게임에는 빨강, 노랑, 파랑, 하양의 4가지 펜토미노 세트가 포함되어 있으며, 보드에는 2인용 기본 10x10 영역과, 여러 명이 플레이할 경우 사용하는 추가 영역(각 측면에 25칸씩 추가됨)이 있다.
게임 제조업체 론포스(Lonpos)는 펜토미노를 사용하되 다양한 모양의 게임판 위에서 진행하는 여러 게임을 출시했다. 예를 들어, 론포스의 ''101 게임''은 5x11 크기의 평면 게임판을 사용한다.
참조
[1]
웹사이트
Eric Harshbarger - Pentominoes
http://www.ericharsh[...]
[2]
서적
Planar Tilings and the Search for an Aperiodic Prototile
PhD dissertation, Rutgers University
[3]
간행물
More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes
1975-08
[4]
웹사이트
The Project Gutenberg eBook of The Canterbury Puzzles, by Henry Ernest Dudeney
https://www.gutenber[...]
2022-03-26
[5]
웹사이트
Dissection Problems in PFCS/FCR: Summary of Results in Date Order
https://www.mayhemat[...]
2022-03-26
[6]
서적
Hexaflexagons and other mathematical diversions
https://archive.org/[...]
The University of Chicago Press
1988
[7]
웹사이트
people.rit.edu - Introduction - polyomino and pentomino
http://people.rit.ed[...]
[8]
서적
Polyominoes
https://archive.org/[...]
Charles Scribner's Sons
1965
[9]
간행물
A Computer Program for Pentominoes
https://www.archim.o[...]
1960-10
[10]
문서
Programming a combinatorial puzzle
Department of Electrical Engineering, Princeton University
1958
[11]
문서
Dancing links
http://www-cs-facult[...]
[12]
서적
Frontiers in Algorithmics
https://archive.org/[...]
Springer Science+Business Media
[13]
문서
Pentominoes: A First Player Win
http://www.msri.org/[...]
[14]
웹사이트
FAQ
http://www.cathedral[...]
[15]
문서
Could you solve Pentominoes?
Sunday Telegraph Magazine
1975-09-14
[16]
문서
Chasing Vermeer
Scholastic Paperbacks
[17]
웹사이트
The Crossword
https://www.nytimes.[...]
2020-07-30
[18]
서적
ルービック・キューブと数学パズル
日本評論社
[19]
웹사이트
両方のプレイヤーが完璧にプレイした場合の勝敗が決まっている「解決済み」ゲームにはどのようなものがあるのか？
https://gigazine.net[...]
2023-11-11
[20]
문서
FACOM
テンヨー
[21]
웹사이트
https://gigazine.net[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com