15 퍼즐

15 puzzle
"Magic 15"는 여기서 리다이렉트 됩니다.각 행과 열의 합계가 15가 되는 번호 격자는 매직 사각형을 참조하십시오.
퍼즐을 풀려면 숫자를 순서대로 정렬해야 합니다.

15개의 퍼즐(Game of Friefit, Boss Puzzle, Game of Fifty, Mystic Square 등)은 높이 4개의 타일, 너비 4개의 타일 프레임에 1~15개의 번호가 매겨진 15개의 정사각형 타일이 있는 슬라이딩 퍼즐입니다.개방위치의 같은 행 또는 열에 있는 타일은 각각 수평 또는 수직으로 슬라이드하여 이동할 수 있다.퍼즐의 목적은 타일을 숫자 순서대로 배열하는 것입니다.

프레임의 타일 수에서 이름을 따온 15개의 퍼즐은 총 타일 용량을 암시하는 16개의 퍼즐이라고도 불립니다.유사한 이름이 15개의 퍼즐의 다양한 크기 변형에 사용됩니다. 예를 들어, 3×3 프레임에 8개의 타일이 있는 8개의 퍼즐입니다.

n 퍼즐은 휴리스틱스를 포함하는 알고리즘 모델링에 대한 고전적인 문제이다.이 문제에 대해 일반적으로 사용되는 휴리스틱스에는 잘못 배치된 타일의 수를 카운트하고 각 블록과 목표 [1]구성에서 해당 위치 사이의 택시 거리 합계를 찾는 것이 포함됩니다.둘 다 허용된다는 점에 유의하십시오.즉, A*[1]와 같은 특정 검색 알고리즘의 최적화를 보장하는 나머지 이동 수를 과대평가하지 않습니다.

수학

해결 가능성

풀린 15개의 퍼즐

Johnson & Story (1879)는 n개 퍼즐의 시작 위치 중 절반이 아무리 많이 움직여도 해결할 수 없다는 것을 보여주기 위해 패리티 인수를 사용했다.이는 유효한 이동에서 불변하는 타일 구성의 함수를 고려한 후 이를 사용하여 라벨이 붙은 모든 상태의 공간을 도달 가능 상태와 도달 불가능 상태의 두 가지 동등성 클래스로 분할함으로써 이루어집니다.

불변량은 16개 정사각형의 순열 패리티에 오른쪽 아래 모서리에서 빈 정사각형의 택시 거리(행 수 + 열 수)의 패리티를 더한 값입니다.각 이동이 치환의 패리티와 택시카브 거리의 패리티를 모두 변경하기 때문에 이는 불변입니다.특히 빈 정사각형이 오른쪽 아래 구석에 있으면 나머지 조각의 순열이 고른 경우에만 퍼즐을 풀 수 있다.

또한 Johnson & Story(1879)는 m과 n이 둘 다 최소 2일 때 m×n 크기의 보드 상의 역방향 홀드가 모두 해결 가능하다는 것을 보여주었다.이것은 간단하지만 m=n=2로 시작하는 m과 n에 대한 유도로 증명하기에는 조금 복잡하다.Archer(1999)는 해밀턴 경로를 통해 동등성 클래스를 정의하는 것에 기초한 또 다른 증거를 제시했다.

윌슨(1974)은 15개의 퍼즐을 임의의 유한 그래프로 일반화하는 것을 연구했는데, 원래의 문제는 4×4 그리드 그래프의 경우였다.이 문제에는 일부 하위 그래프에서 동일한 문제에 대한 답변의 단순한 조합 또는 사소한 답변이 포함된 퇴화된 경우가 있습니다.즉, 경로와 다각형의 경우, 퍼즐은 자유롭지 않다; 그래프가 연결되지 않으면, "빈 공간"을 가진 정점의 연결된 구성요소만 관련이 있다; 그리고 만약 관절 정점이 있다면, 문제는 그 정점의 두 개의 연결된 구성요소 각각에서 동일한 퍼즐로 감소한다.이러한 경우를 제외하고, 윌슨은 7개의 정점에 있는 하나의 예외적인 그래프를 제외하고, 그래프가 양분되지 않는 한 모든 순열을 얻을 수 있으며, 이 경우 정확히 짝수 순열을 얻을 수 있다는 것을 보여주었다.예외 그래프는 하나의 대각선과 중심에 정점이 추가된 정육각형입니다.순열의 1/6을 얻을 수 있습니다.

더 큰 버전의 n 퍼즐의 경우, 해답을 찾는 것은 쉽지만, 최단 해답을 찾는 문제는 NP-hard입니다.가법 상수 내에서 가장 적은 슬라이드를 근사하는 것도 NP-어렵지만 다항식 시간 상수 요인 [2][3]근사치가 있습니다.15개의 퍼즐의 경우 최적 해법의 길이는 0에서 80개의 싱글 타일 이동(17개의 구성이 80개의 [4][5]이동을 필요로 함) 또는 43개의 멀티 타일 [6]이동입니다. 8개의 퍼즐은 항상 31개의 싱글 타일 이동 또는 24개의 멀티 타일 이동(정수열 A087725) 이하로 풀 수 있습니다.다중 타일 메트릭은 [6]빈 타일의 동일한 방향에서의 후속 이동을 카운트합니다.

24개 퍼즐의 가능한 위치 수는 25!/2 7 7.76×10으로24 신의 수를 계산하기에는 너무 많다.2011년에는 152개의 단일 타일 이동 또는 41개의 다중 타일 이동의 하한과 208개의 단일 타일 이동 또는 109개의 다중 타일 [7][8][9][10]이동의 상한이 설정되었다.2016년에는 상한을 205개의 단일 타일 [11]이동으로 개선하였습니다.

15개의 퍼즐의 변환은 그룹로이드(모든 움직임을 [12][13][14]구성할 수 있는 것은 아니기 때문에 그룹이 아님)를 형성한다.이 그룹로이드(groupoid)

군론

왜냐하면 15퍼즐의 조합 3-cycles에 의해 발생할 수 있다면 그것은 슬라이딩 퍼즐 교대의 그룹에 의해 사실 15{\displaystyle A_{15}}.[15]표시할 수 있고, 동일한 크기의 제곱 타일들과 2개 k− 1{2k-1\displaystyle}슬라이딩 퍼즐는 2k− 1{\displaystyle로 표시할 수 있증명할 수 있다.A_{

대체 증명

이 문제의 대체 뷰에서는 불변성을 15개의 번호가 매겨진 조각의 현재 순서의 반전 수의 패리티와 마지막 행의 행 번호와의 빈 정사각형의 행 번호의 차이의 패리티의 합으로 간주할 수 있습니다(마지막 행으로부터의 행 거리라고 합니다).같은 열 내에서 피스를 이동할 때 각 열 이동 시 반전 횟수의 패리티(반전 횟수 ±1, ±3)와 마지막 열과의 행 거리 패리티(행 거리 ±1 변경)가 모두 변경되므로 각 행 이동은 변경되지 않습니다.두 패리티 중 하나를 선택합니다.퍼즐의 해결 상태를 보면, 이 합은 짝수입니다.따라서 상기 합계가 홀수인 퍼즐의 어떤 상태도 풀 수 없다는 것을 유도에 의해 증명하기 쉽다.특히 빈 정사각형이 오른쪽 아래 구석에 있는 경우(마지막 줄의 어느 곳이라도), 번호가 매겨진 조각의 반전의 수가 짝수인 경우에만 퍼즐을 풀 수 있습니다.

역사

타일 14와 15를 교환한 샘 로이드의 풀 수 없는 15개의 퍼즐.이 퍼즐은 풀린 상태로 이동하기 위해서는 불변의 변화가 필요하기 때문에 풀 수 없다.
1880년 공화당 대통령 후보를 찾는 것에 관한 미국 정치 만화

이 퍼즐은 뉴욕 카나스토타의 우체국장인 노예스 팔머 [16]채프먼에 의해 "발명"되었는데, 그는 1874년에 친구들에게 16개의 번호가 매겨진 블록으로 구성된 전구 퍼즐을 보여주었고, 각각은 34개가 될 것이다.개량된 15개의 퍼즐의 복사본은 노예스의 아들 프랭크를 거쳐 뉴욕 시러큐스로, 그리고 그곳에서 로드아일랜드의 워치 힐, 그리고 마침내 미국 청각장애학교 학생들이 퍼즐을 만들기 시작했고 1879년 12월까지 두 퍼즐을 모두 팔기 시작한 코네티컷주 하트포드까지 갔다.메사추세츠 주 보스턴에서요보스턴에서 화려한 목공 사업을 운영하던 마티아스 라이스는 1879년 12월 어느 날 퍼즐을 만들기 시작했고 "양키 개념"의 한 팬시 상품 판매상을 설득하여 "젬 퍼즐"이라는 이름으로 팔았다.1880년 1월 말, 메사추세츠 주 우스터에 있는 치과 의사 찰스 페비는 15 [16]퍼즐의 해답에 대한 현금 보상을 제시하여 관심을 끌었다.

이 게임은 [17]1880년 미국에서 열풍을 일으켰다.

노예스 채프먼은 1880년 2월 21일 블록 솔리테어 퍼즐에 대한 특허를 출원했다.그러나 이 특허는 1878년 8월 20일 어니스트 킨지에게 부여된 [16]"퍼즐 블록" 특허(US 207124)와 충분히 다르지 않았기 때문에 기각되었다.

샘 로이드

샘 로이드의 1914년 불가해한 변이 삽화

샘 로이드. Sam.1891년에서 1911년에 그의 죽음까지 그가, 예는 Cyclopedia Puzzles의(1914년 출판되)에 쓰기용으로 퍼즐을 발명했었다:"Puzzleland의 좀 더 나이 많은 주민들이 어떻게 70대 초반의 나는 않아서 광기는 '14-15 Puzzle'으로 알려져 가동들 작은 상자 전체 세계를 기억할 것이라고 주장한다."[18][검증 실패한]하지만, 로이드는 퍼즐의 발명이나 초기 인기와는 아무런 관련이 없었고, 어떤 경우든 열풍은 1870년대 초가 아니라 1880년에 있었다.이 퍼즐에 대한 로이드의 첫 번째 기사는 1886년에 발표되었고, 1891년이 되어서야 비로소 그가 [16][19]발명가라고 주장했다.

이후 로이드사가 14-15 [1]퍼즐이라고 부르는 14와 15를 뒤집는 등 로이드사가 지정한 특정 조합을 달성할 수 있는 해결책을 제공할 수 있는 사람에게 1,000달러의 상금을 주겠다는 제안으로 관심을 모았습니다.이는 10년 이상 전에 존슨 앤 스토리(1879)가 보여줬듯이 짝수에서 홀수 치환으로 변환해야 하기 때문에 불가능하다.

여러가지 종류의

소련에서 제작된 마이너스 큐브는 15개의 퍼즐과 비슷한 연산을 가진 3D 퍼즐이다.

체스 세계 챔피언 바비 피셔는 15퍼즐을 [20]푸는 데 전문가였다.그는 이 문제를 25초 안에 해결할 수 있도록 시간을 쟀다; 피셔는 1972년 11월 8일 조니 [21][22]카슨 주연의 투나잇 쇼에서 이것을 시연했다.

「 」를 참조해 주세요.

메모들

  1. ^ a b c Korf, R. E. (2000), "Recent Progress in the Design and Analysis of Admissible Heuristic Functions" (PDF), in Choueiry, B. Y.; Walsh, T. (eds.), Abstraction, Reformulation, and Approximation (PDF), SARA 2000. Lecture Notes in Computer Science, vol. 1864, Springer, Berlin, Heidelberg, pp. 45–55, doi:10.1007/3-540-44914-0_3, ISBN 978-3-540-67839-7, retrieved 2010-04-26
  2. ^ Ratner, Daniel; Warmuth, Manfred (1986). "Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable" (PDF). National Conference on Artificial Intelligence. Archived (PDF) from the original on 2012-03-09.
  3. ^ Ratner, Daniel; Warmuth, Manfred (1990). "The (n2−1)-puzzle and related relocation problems". Journal of Symbolic Computation. 10 (2): 111–137. doi:10.1016/S0747-7171(08)80001-6.
  4. ^ Richard E. Korf, 리니어 타임 디스크 기반의 암묵적 그래프 검색, ACM Volume 55 제6호(2008년 12월호), 제26-30쪽. "4 × 4 15 퍼즐의 경우, 깊이 80의 경우 초기 상태에서 17개의 다른 상태가 있으며, 모서리에 공백이 있는 반면, 2 × 8 퍼즐의 경우, 8 퍼즐 상태는 고유합니다.140의 상태가 초기 상태에서 이동합니다."
  5. ^ A. Brüngger, A. Marzetta, K.후쿠다와 J. 니에버겔트, 병렬 검색 벤치 ZRAM 및 그 응용 프로그램, 운영 연구 연보(Annals of Operations Research90)(1999년), 페이지 45-63.
    : "가서는 9개의 위치를 찾았고 80개의 이동이 필요합니다...현재 가장 어려운 15퍼즐 포지션도 80개의 동작이 필요하다는 것을 증명했습니다.또한 이전에는 알려지지 않았던 두 가지 위치를 발견했으며, 정확히 80개의 조치를 취해야 했습니다."
  6. ^ a b 15개의 퍼즐은 43개의 움직임으로 풀 수 있다.큐브 포럼의 도메인
  7. ^ "24 퍼즐 새로운 하한: 152"큐브 포럼의 도메인
  8. ^ "m × n 퍼즐(현재 기술 수준)"슬라이드식 타일 퍼즐 코너.
  9. ^ "5x5에 대한 계산"큐브 포럼의 도메인입니다.
  10. ^ "5x5는 109MTM으로 해결할 수 있습니다." 큐브 포럼 도메인.
  11. ^ "5x5 슬라이딩 퍼즐은 205개 동작으로 풀 수 있습니다."큐브 포럼의 도메인입니다.
  12. ^ Jim Belk (2008) 퍼즐, 그룹, 그룹, 모든 것 세미나
  13. ^ 네버엔딩북스 15퍼즐 그룹로이드 (1)
  14. ^ 네버엔딩북스 15퍼즐 그룹로이드(2)
  15. ^ Beeler, Robert. "The Fifteen Puzzle: A Motivating Example for the Alternating Group" (PDF). faculty.etsu.edu/. East Tennessee State University. Retrieved 26 December 2020.
  16. ^ a b c d Jerry Slocum & Dic Sonneveld의 15 퍼즐, 2006.ISBN 1-890980-15-3
  17. ^ Slocum & Singmaster (2009년, 페이지 15)
  18. ^ 퍼즐의 사이클로피디아, 페이지 235
  19. ^ Barry R. Clarke, Puzzes for Fleas, 10-12페이지, 케임브리지 대학 출판부, 1994 ISBN 0-521-46634-2.
  20. ^ 클리포드 A.픽오버, 수학책: 피타고라스에서 57차원에 이르기까지 수학사 250개 이정표, 262, 스털링 출판사, 2009 ISBN 1402757964.
  21. ^ "바비 피셔는 Carson Tonight Show - 11/08/1972에서 15개의 퍼즐을 17초 만에 풀었습니다," The Tonight Show, 1972년 11월 8일, 조니 카슨 프로덕션에서 2021년 8월 1일을 회수했습니다.
  22. ^ 아담 스펜서, 아담 스펜서의 빅 북 오브 넘버스: 숫자 1~100에 대해 알고 싶은 모든 것, Brio Books, 2014 ISBN 192113433X, 페이지 58.

레퍼런스

외부 링크

Wikimedia Commons에는 15개의 퍼즐과 관련된 미디어가 있습니다.