영원 II 퍼즐

Eternity II puzzle
「E II」는 여기서 리다이렉트 됩니다.그 외의 용도는, EII(동음이의)를 참조해 주세요.
이터니티 II

Eternity II 퍼즐(E2 또는 EII)은 2007년 [1][2]7월 28일에 출시된 엣지 매칭 퍼즐입니다.Christopher Monckton에 의해 개발되었고 TOMY UK Ltd에 의해 오리지널 이터니티 퍼즐의 후속작으로 마케팅 및 저작권이 부여되었습니다.이 퍼즐은 첫 번째 완전한 해답에 200만 달러의 상금이 걸린 경쟁의 일부였다.이 대회는 2010년 12월 31일 정오에 솔루션을 찾지 못한 채 종료되었습니다.

묘사

이터니티 II 퍼즐은 인접한 모서리와 일치해야 하는 요건에 따라 256개의 정사각형 퍼즐 조각을 16 × 16 그리드에 배치해야 하는 에지 매칭 퍼즐입니다.이것은 무차별적인 컴퓨터 검색으로 해결하기 어렵도록 설계되어 있습니다.

각 퍼즐 조각은 한 면에 다른 모양/색 조합(여기서는 총칭 "색"이라고 함)으로 표시된 모서리를 가지고 있으며, 퍼즐이 완성되었을 때 각 퍼즐 조각의 인접 면과 정확하게 일치해야 합니다.각 조각의 다른 면은 식별 번호와는 별도로 공백이며 퍼즐에는 사용되지 않습니다.따라서 각 조각은 4방향으로만 사용할 수 있습니다.회색 테두리를 제외한 22가지 색상이 있습니다.5가지 색상은 최외곽 링의 60개의 엣지 페어("다이아몬드")에서만 볼 수 있으며, 나머지 17개는 나머지 420개의 "내부" 엣지 페어에 사용됩니다.색상은 정확히 12개의 엣지 쌍에 사용되는 5개의 테두리 색상과 24개의 엣지 쌍(5색) 또는 25개의 엣지 쌍(12색)에 사용되는 17개의 내부 색상으로 균등하게 사용됩니다.엣지 쌍의 총수는 480입니다.5가지 테두리 색상 중 하나는 모서리 조각에 없고, 17가지 안쪽 색상은 모두 테두리 조각에 한 번 이상 사용됩니다.

모서리 조각은 4개(회색 면 2개), 테두리 조각 56개2(회색 면 1개), 내부 조각 14개 = 196개(색면 4개)입니다.각 조각은 고유한 색상 배열을 가지며, 어떤 조각도 회전 대칭이 아니기 때문에 256 × 4 = 1024개의 조각과 방향을 각각 선택하면 다른 패턴의 가장자리 색상이 됩니다.

이 퍼즐은 첫 번째 [3]이터니티 퍼즐과는 다릅니다.첫 번째 이터니티 퍼즐은 선택사항이 아닌 스타터 조각(필수 힌트)을 보드 중앙 부근의 지정된 위치와 방향에 배치해야 합니다.

제품 출시와 함께 두 가지 힌트 퍼즐을 사용할 수 있으며, 풀면 각각 256피스 퍼즐에 피스 위치(힌트)를 부여합니다.클루 퍼즐 1은 36피스 정사각형(6×6) 퍼즐이고 클루 퍼즐 2는 72피스 직사각형(12×6) 퍼즐입니다.같은 차원의 두 개의 추가 단서 퍼즐이 2008년에 제공되었다: 36조각짜리 단서 퍼즐 3과 72조각짜리 단서 퍼즐 4.규칙서에는 [3]힌트를 사용하지 않고도 퍼즐을 풀 수 있다고 쓰여 있다.

복잡성

이터니티 II 퍼즐의 가능한 구성 수는 모든 조각이 구별된다고 가정하고 미리 정해진 위치가 있는 고정 조각을 무시한다고 가정할 때 256256! × 4, 대략 1.15661 × 10입니다.중앙의 고정편과 가장자리의 조각에 설정된 제한을 고려함으로써 가능한 구성 수에 대한 보다 엄격한 상한을 달성할 수 있습니다: 1 × 4! × 56! × 195195! × 4, 대략 1.12 × 10557.단서 퍼즐을 통해 얻은 힌트 조각의 위치 및 방향을 고려함으로써 한층 더 상한을 얻을 수 있다.이 경우, 4! × 56! × 191! × 4191 = 3.11 × 10의545 상한을 가지며, 5개의 조각의 위치와 방향이 알려져 있으며, 서치 공간은 첫 번째 근사치보다 3.70115 × 10배 작습니다.

첫 번째 근사치에서는 엣지 매칭 제약조건에 의해 유효한 설정의 수가 (1/5) 각 보더 엣지 쌍에 대해 (1/17) 계수만큼 감소합니다.유효한 구성의 수는 4! × 56! × 196! × 4196 × (1/605) × (1/17)420 16 16.4로 근사되며, 이는 통일성에 매우 가깝다.이는 퍼즐이 하나 또는 몇 가지 [4][5]해결책만을 가지도록 설계되었음을 나타냅니다. 즉, 난이도는 최대화됩니다. 더 많은 해결책(예: 더 적은 색상 등)은 해결책을 찾기 쉽게 하는 반면, 더 엄격한 제약 조건은 검색 공간을 감소시켜 (독특한) 해결책을 찾기 쉽게 만듭니다.이러한 [6]관찰을 뒷받침하는 작은 퍼즐에 대해 색상 수의 최적화를 경험적으로 조사했다.

경쟁 제품과 솔루션

2008년 12월 31일의 첫 번째 조사일 이후 완전한 해결책이 발견되지 않았다고 발표되었습니다.스웨덴 Lund의 Louis Verhaard는 [8]480개 중 467개의 일치하는 모서리를 가진 부분 솔루션을 수상하여[7] $10,000의 상금을 받았습니다.Verhaard는 동일한 수의 일치하는 [7]모서리를 가진 3개의 부분 솔루션을 추가로 발표했습니다.

2011년 1월 30일 현재, 공식 Eternity II 사이트는 "Eternity II 퍼즐의 정확한 해답에 대한 최종 날짜는 수상자 없이 지나가고, Eternity II 퍼즐의 정확한 해답에 대한 200만 달러의 상금은 청구되지 않는다."[9]

이터니티 2 퍼즐에 대한 검증된 완전한 해답은 아직 발표되지 않았습니다.여기에는 크리스토퍼 몽크턴이 의도한 해결책도 포함되지만 아직 공개되지 않았습니다.몇몇 가짜 해결책들이 온라인에서 유포된 것으로 알려져 있다.

이력 및 설계

오리지널 이터니티 퍼즐은 몽크톤이 만든 백만 파운드의 상금이 있는 타일 퍼즐이었다.1999년 6월에 출시된 이 프로그램은 Alex Selby와 Oliver Riordan이 설계한 컴퓨터 검색 알고리즘에 의해 해결되었으며, 이 알고리즘은 원래 퍼즐 [10]디자인의 조합적 약점을 이용했다.상금은 셀비와 리오단에게 전액 지급되었다.

두 영원의 퍼즐과 놀라운 유사성을 가진 퍼즐인 다이아몬드 딜레마는 오리지널 영원의 퍼즐이 마감되기 10년 전인 1990년에 마감된 퍼즐로 처음 두 영원의 퍼즐이 각각 209개, 256개로 퍼즐 조각이 적지만 다이아몬드 딜레마는 25년이 넘도록 풀리지 않고 있다.

Eternity II 퍼즐은 2005년에 Munkton에 의해 디자인되었는데, 이번에는 Eternity II 디자인을 [11]만든 컴퓨터 프로그램을 설계한 Selby와 Riordan이 공동으로 디자인했다.수학 게임 애호가 브렌단 오웬에 따르면, 이터니티 II 퍼즐은 이전 퍼즐의 조합적인 결점을 피하기 위해 고안된 것으로 보이며, 퍼즐을 풀기에 최대한 어렵게 만들기 위해 선택된 것으로 보인다.특히, 원래의 이터니티 퍼즐과는 달리,[4] 이 문제에 대한 가능한 해답은 극소수에 불과할 것이다.Owen은 무차별적인 역추적 [12]수색을 완료하는 데 약 2×1047 단계가 걸릴 것으로 추정합니다.

2005년 더 타임스는 몽크턴의 말을 인용했다.

「당사의 계산으로는, 세계에서 가장 파워풀한 컴퓨터를 사용하고, 지금부터 우주의 종말을 예상할 때까지 컴퓨터를 계속 가동하면,[11] 솔루션 중 하나를 우연히 발견하지 않을 가능성이 있습니다.」

비록 이터니티 II가 특별한 경우인 가장자리 일치 퍼즐의 클래스가 일반적으로 [13]NP-완전하다는 것이 입증되었지만, 원래의 이터니티 퍼즐이 특별한 경우였던 폴리곤 패킹 문제의 일반적인 클래스에서도 같은 것을 말할 수 있다.

원래의 이터니티 퍼즐과 같이, 테두리가 모두 일치하는 보드 위에 상당한 수의 조각을 배치하는 많은 방법을 쉽게 찾을 수 있어 퍼즐이 쉬워 보입니다.그러나 예상 가능한 해결책의 수가 적기 때문에, 어떤 부분적인 해결책도 완전한 해결책으로 이어질 가능성은 아마 천문학적으로 희박할 것이다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ PRNewswire (26 July 2007). "Investegate TOMY Announcements TOMY: Eternity II Global Launch at Hamleys With US$2 ..." www.investegate.co.uk. Retrieved 5 October 2020.
  2. ^ "Television interview with Christopher Monckton and Brendan Owen". Mornings with Kerri-Anne, Brendan Owen's channel, YouTube. 26 July 2007. Archived from the original on 21 December 2021.
  3. ^ a b 설명 책자 (PDF, 아카이브), 공식 웹사이트에서 공개
  4. ^ a b Owen, Brendan (2007). "Eternity II - Design". Brendan Owen's Eternity II website. Archived from the original on 10 December 2007. Retrieved 9 November 2007.
  5. ^ Ansótegui, Carlos; Béjar, Ramon; Fernández, Cèsar; Mateu, Carles (3 July 2008). "How Hard is a Commercial Puzzle: the Eternity II Challenge". Proceedings of the 2008 Conference on Artificial Intelligence Research and Development: Proceedings of the 11th International Conference of the Catalan Association for Artificial Intelligence. NLD: IOS Press: 99–108. doi:10.3233/978-1-58603-925-7-99. ISBN 978-1-58603-925-7.
  6. ^ Willems, Daysel (24 June 2016). "On the Hardness of Framed Edge-Matching Puzzles" (PDF). Bachelor Thesis, Faculty of Science, University of Amsterdam.
  7. ^ a b Verhaard, Louis. "EII Solver - Best results". www.shortestpath.se. Retrieved 9 October 2020.
  8. ^ http://www.sydsvenskan.se/2009-01-20/lundafamilj-bast-i-varlden-pa-svarknackt-pussel 링크(스웨덴어)
  9. ^ "Eternity II". Archived from the original (official website) on 8 February 2010. Retrieved 30 January 2011.
  10. ^ "Description of Selby and Riordan's Eternity I solver method". Alex Selby (and Oliver Riordan). 16 June 2007. Retrieved 16 June 2007.
  11. ^ a b Elliott, John (4 December 2005). "£1m says this really is the hardest jigsaw". London: Times Online. Retrieved 9 November 2007.
  12. ^ ""Solving" page on Brendan Owen's Eternity II website". Archived from the original on 10 December 2007. Retrieved 9 November 2007.
  13. ^ Erik D. Demaine, Martin L. Demaine. "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity" (PDF). Retrieved 12 August 2007.
  14. ^ "LGR - TetraVex and the Unsolvable Puzzle". YouTube. 5 February 2016. Archived from the original on 21 December 2021.
  15. ^ Takenaga, Yasuhiko; Walsh, Toby (15 September 2006). "Tetravex is NP-complete". Information Processing Letters. 99 (5): 171–174. doi:10.1016/j.ipl.2006.04.010. ISSN 0020-0190. S2CID 7228681.

외부 링크

Wikimedia Commons에는 Ethernity II와 관련된 미디어가 있습니다.

소프트웨어: