엣지 매칭

모서리 맞추기 퍼즐은 인접한 타일의 모서리가 일치하도록 색이나 패턴으로 구분되는 (일반적으로 규칙적인) 폴리곤으로 영역을 타일링하는 타일링 퍼즐의 한 종류입니다.

엣지 매칭 퍼즐은 NP-완전이며, 동등한 직소 퍼즐 및 폴리오미노 패킹 퍼즐과 ^[1]변환이 가능한 것으로 알려져 있습니다.

첫 번째 모서리 맞추기 퍼즐은 E.L.에 의해 미국에서 특허를 받았다. 1892년 ^[2]서스턴.현재 상용 에지 매칭 퍼즐의 예로는 이터니티 II 퍼즐, Tantrix, Kadon Enterprises의 에지 매칭 퍼즐 및 Edge Match Puzzes iPhone 앱 등이 있습니다.

현저한 변화

맥마흔 광장

MacMahon Squares는 1921년 ^[4]다양한 모양의 가장자리 색채에 대한 논문을 발표한 영국 수학자 Percy MacMahon이 제안한 오락용 수학 퍼즐에 붙여진 이름이다.이 특정한 퍼즐은 정사각형의 모서리에 3가지 색상의 모든 배열로 구성된 24개의 타일을 사용합니다.타일은 모든 가장자리가 일치하도록 6×4 직사각형 영역으로 배치해야 하며 ^[5]직사각형의 바깥쪽 가장자리에는 한 가지 색상만 사용해야 합니다.

이 퍼즐은 10×^[6]7로 배열된 4색 배열의 타일로 확장할 수 있습니다.두 경우 모두 정사각형이 Wang 타일의 하위 집합이므로 회전 시 유사한 타일을 줄일 수 있습니다.솔루션은 ^[7]수천 개에 달합니다.

MacMahon Squares는 아이디어의 변형과 함께 Multimatch로 상용화되었습니다.

테트라벡스

TetraVex는 플레이어에게 정사각형 그리드와 타일 컬렉션을 제공하는 컴퓨터 게임입니다. 기본적으로 3×3 그리드용 정사각형 타일 9개입니다.각 타일에는 네 개의 한 자리 숫자가 있으며, 각 가장자리에 하나씩 있습니다.게임의 목적은 타일을 그리드에 적절한 위치에 배치하여 가능한 한 빨리 퍼즐을 완성하는 것입니다.타일은 회전할 수 없으며 인접한 모서리의 숫자가 ^[8][9]일치하는 경우에만 두 타일을 서로 옆에 배치할 수 있습니다.

TetraVex는 Donald Knuth가 그의 시리즈 The Art of Computer Programming의 첫 번째 책인 Volume 1: Fundamental Algorithms 382페이지에서 설명한 "평면 타일링 문제"에서 영감을 받았습니다.개발 책임자이자 Visual Basic의 첫 번째 버전의 설계자인 Scott Ferguson이 Windows Entertainment Pack ^[10]3을 위해 이 버전을 썼다.

테트라벡스는 GNOME Games ^[11]컬렉션에서 오픈 소스 게임으로도 이용 가능합니다.

가능한 TetraVex의 수는 셀 수 있습니다.$n{\displaystyle }$×$$(\$displaystyle n\$times {}$n}$ 보드에는$$ 일치해야 하는 n$n$-$$ )(\$displaystyle$ n$(n-1))$의 수평 및 수직 쌍과 임의로 선택할 수 있는 엣지를 따라 $(\displaystyle 4n)$의 숫자가 $있습니다{\displaystyle }$.${\displaystyle \mathrm{따라서}}$ 2n${\displaystyle (n}$ ${\displaystyle -1)+\mathrm{4n}}$ ${\displaystyle =}$ $($+ 1$displaystyle 2n(n-1)+4n=2n(n+1)}$개의$$ 10자리 숫자, 즉 ${\displaystyle {\mathrm{102n}(\mathrm{n}+}^{}}$1$)\$ 10$^{2n(n+1)}$개의$$ 가능한 보드가 $있습니다{\displaystyle \mathrm{}}$.

TetraVex 퍼즐에 해답이 있는지 아닌지는 일반적으로 NP-완료입니다.^[12]계산 접근법에는 더글라스-랙포드 ^[13][14]알고리즘이 포함됩니다.

육각형

사각형은 Psyche-Paths, Kaliko, Tantrix와 같은 다양한 추상 전략 게임에 사용되는 육각형 타일입니다.각 사각형 내에서 가장자리가 쌍을 이루므로 육각형 내에서 홀수 횟수만큼 가장자리 색상이 발생하지 않도록 타일 세트를 제한합니다.

3차원

수학적으로 가장자리를 맞추는 퍼즐은 2차원입니다.3D 모서리 일치 퍼즐은 유클리드 공간에서 평평하지 않은 퍼즐이므로, 정다면체의 표면과 같은 3차원 영역을 타일링하는 것을 포함합니다.이전과 같이 폴리곤 조각에는 인접한 조각의 가장자리가 일치하도록 구분된 가장자리가 있습니다.

3D 에지 매칭 퍼즐은 1892년 E. L.의 특허 이후 현재 미국의 직접적인 특허 보호를 받고 있지 않습니다.서스턴은 만료되었다.^[2]현재 상용 퍼즐의 예로는 Dodek Duo, The Enigma,^[15] Mental Misorry, Kadon Enterprises의 3차원 에지 ^[16]매칭 퍼즐이 있습니다.

가장자리 매칭 통합

카르카손 보드 게임은 모서리 매칭을 사용하여 정사각형 타일을 배치할 수 있는 위치를 제한합니다.원래 게임은 세 가지 종류의 가장자리가 있다: 들판, 도로, 그리고 도시.

「 」를 참조해 주세요.

• 도미노 타일링
• 왕도미노

레퍼런스

외부 링크

• 에리히의 매칭 퍼즐 컬렉션
• Peter^{[dead link]} Esser의 색상과 모서리 매칭 폴리곤
• Rob Stegmann의 Rob's 퍼즐 페이지
• 모서리 일치 정사각형