순간 광기

Instant Insanity
"해결된" 구성에서의 즉각적인 광기어린 퍼즐.위에서 아래로 큐브 뒷면의 색상은 흰색, 녹색, 파란색, 빨간색(왼쪽), 파란색, 빨간색, 녹색, 흰색(오른쪽)입니다.
인스턴트 광기 큐브의 그물– 라인 스타일은 솔루션 내의 큐브를 식별하기 위한 것입니다.

인스턴트 인시던트는 파커 브라더스가 1967년판 퍼즐에 붙인 이름으로 고대부터 존재해 왔으며 다음과 같은 다양한 이름으로 많은 장난감 및 퍼즐 제조사에 의해 판매되고 있다.악마의 주사위(프레스맨), DamBlocks(쉐이퍼), Logi-Qubes(쉐퍼), Logi Cubes(Thinkin Games), Daffy Dots(Reiss)그 블록들 (오스트린);PsykoNosis (A to Z 아이디어) [1]등 많은 것들이 있습니다.

이 퍼즐은 네 가지 색으로 된 면이 있는 네 개의 큐브로 구성되어 있습니다(일반적으로 빨강, 파랑, 초록, 흰색이다.퍼즐의 목적은 스택의 각 측면(앞면, 뒷면, 왼쪽 및 오른쪽)이 4가지 색상의 각각을 나타내도록 이러한 큐브를 한 열에 쌓는 것입니다.각 큐브의 색상 분포는 고유합니다.

이 문제에는 B, G, R, W(파란색, 녹색, 빨간색 및 흰색의 경우)라는 라벨이 붙은 4개의 정점이 있는 그래프를 사용하여 각 정육면체를 나타낼 수 있는 그래프 이론 솔루션이 있습니다.입방체의 반대쪽에 있는 두 색이면 두 정육면체 사이에 가장자리가 있고 반대쪽이 같은 색이면 정점에 루프가 있습니다.4개의 큐브를 331,776개의 가능한 배열(각 큐브의 6면, 4회전 = 24개 위치, 4개의 큐브 곱하기, 총 331,776개)이 있기 때문에 시행착오는 이 문제를 해결하는 느린 방법입니다.솔루션은 대칭적인 8가지 방식입니다(솔루션이 있고 4개의 큐브를 모두 앞으로 뒤집으면 다른 유효한 솔루션이 있습니다).따라서 331,776을 8로 나누면 입방체를 랜덤하게 용액에 던질 확률이 41,472입니다. 즉, 입방체를 수직 축 주위에 180도 회전시키면 총 8개 대칭이 됩니다.그 퍼즐은 D에 의해 연구되었다. E. Knuth는 백트래킹에 의한 철저한 검색 절차의 실행 시간 견적에 관한 기사에서 다음과 같이 기술하고 있습니다.[2]

퍼즐의 모든 위치는 8개 이하의 [3]움직임으로 풀 수 있습니다.

이 퍼즐의 알려진 최초의 특허 버전은 프레드릭 A에 의해 만들어졌다.1900년 쇼쇼, 카젠재머 [4]퍼즐로 판매되었습니다.이 퍼즐은 프랭크 암브러스터로도 알려진 프란츠 오웬 암브러스터에 의해 재현되었고 1967년 파커 브라더스와 프레스맨에 의해 독립적으로 출판되었다.파커 브라더스에 의해서만 1200만개 이상의 퍼즐이 팔렸다.이 퍼즐은 다른[5][6] 수많은 퍼즐과 비슷하거나 동일하다(예: The Great Tantalizer, 1940년경, Instant Infanzy 이전의 가장 인기 있는 이름).

퍼즐의 한 버전은 현재 위닝 무브즈 게임즈 USA에 의해 판매되고 있다.

솔루션

큐브의 마주보는 면 그래프, 위의 그물 이미지의 큐브에 해당하는 선 스타일

이미 색이 입혀진 큐브와 4가지 색상이 (빨강, 초록, 파랑, 흰색)이기 때문에 모든 큐브의 모든 색상 위치를 명확하게 알 수 있는 그래프를 생성하도록 하겠습니다.결과 그래프에는 각 색상에 대해 하나씩 4개의 정점이 포함되며, 각 모서리에 1부터 4까지의 번호를 매깁니다(각 큐브에 대해 1개의 숫자).모서리가 두 개의 꼭지점(빨간색 및 녹색)을 연결하고 모서리 수가 세 개이면 세 번째 큐브에 서로 반대되는 빨간색 및 녹색 면이 있음을 의미합니다.

이 문제에 대한 해결책을 찾기 위해서는 각 큐브의 4개의 면을 배열해야 합니다.4개의 큐브의 2개의 마주보는 면 정보를 표현하려면 무방향 서브그래프 대신 방향 서브그래프가 필요합니다.왜냐하면 2개의 방향은 2개의 마주보는 면만 나타낼 수 있기 때문입니다.앞에 얼굴이 있어야 하는지 뒤에 있어야 하는지 할지는 알 수 없기 때문입니다.

따라서 두 개의 지시된 하위 그래프가 있는 경우 4개의 큐브 중 4개의 면(중요한 부분)을 모두 나타낼 수 있습니다.

  • 첫 번째 방향 그래프는 앞면과 뒷면을 나타냅니다.
  • 두 번째 방향 그래프는 왼쪽과 오른쪽 면을 나타냅니다.

2개의 서브그래프를 랜덤으로 선택할 수 없습니다.선택 기준은 무엇입니까?

다음과 같은 그래프를 선택해야 합니다.

  1. 두 개의 서브그래프는 공통되는 모서리가 없습니다. 왜냐하면 적어도 하나의 큐브가 정확히 같은 색의 마주보는 면 쌍을 가지고 있는 경우, 즉, 큐브의 앞면과 뒷면으로 빨간색과 파란색이 있는 경우 왼쪽과 오른쪽 면에도 마찬가지이기 때문입니다.
  2. 하위 그래프는 모든 큐브를 고려해야 하고 하나의 모서리가 완전히 마주보는 면 쌍을 나타낼 수 있기 때문에 하위 그래프는 각 큐브에서 모서리를 하나만 포함합니다.
  3. 2도는 색상이 2개의 큐브의 면에만 존재할 수 있음을 의미하기 때문에 하위 그래프는 2도의 꼭지점만 포함할 수 있습니다.쉽게 이해할 수 있는 방법은 네 가지 색으로 똑같이 나누어야 하는 8개의 면이 있다는 것이다.그래서 색깔별로 두 개씩.

이러한 제약사항을 이해한 후 2개의 서브그래프를 도출하려고 하면 이미지 3과 같이1개의 세트가 될 수 있습니다.각 모서리 선 스타일은 큐브를 나타냅니다.

두 방향 서브그래프의 가장자리를 왼쪽(L)과 오른쪽(R)과 앞(F)과 뒷(B) 면에 매핑하면 퍼즐이 해결됩니다.

위쪽 하위 그래프는 해당 큐브의 왼쪽 및 오른쪽 면 색상을 도출할 수 있습니다.예:

  1. 빨간색에서 녹색으로 표시된 화살표는 첫 번째 큐브의 왼쪽 면에 빨간색, 오른쪽 면에 녹색이 있음을 나타냅니다.
  2. 파란색에서 빨간색으로 점선된 화살표는 두 번째 큐브의 왼쪽 면에 파란색, 오른쪽에 빨간색이 있음을 나타냅니다.
  3. 흰색에서 파란색으로 점 표시된 화살표는 세 번째 큐브의 왼쪽 면에 흰색, 오른쪽 면에 파란색이 있음을 나타냅니다.
  4. 녹색에서 흰색으로 표시된 대시 점 화살표는 네 번째 큐브의 왼쪽 면에 녹색, 오른쪽 면에 흰색으로 표시됩니다.

하부 서브그래프를 사용하면 해당 큐브의 전면 및 후면 색상을 도출할 수 있습니다.예:

  1. 흰색에서 파란색으로 표시된 화살표는 첫 번째 큐브의 앞면에 흰색, 뒷면에 파란색이 있음을 나타냅니다.
  2. 녹색에서 흰색으로 점선된 화살표는 두 번째 큐브의 전면이 녹색이고 후면은 흰색임을 나타냅니다.
  3. 파란색에서 빨간색으로 점 표시된 화살표는 세 번째 큐브의 앞면에 파란색, 뒷면에 빨간색이 있음을 나타냅니다.
  4. 빨간색에서 녹색으로 점선된 화살표는 네 번째 큐브의 앞면에 빨간색, 뒷면에 녹색이 있음을 나타냅니다.

세 번째 이미지는 문제의 해결책인 큐브의 파생된 스택을 보여줍니다.

주의할 점은 다음과 같습니다.

  1. 큐브의 위치를 교환하지만 설정을 변경하지 않음으로써 이러한 솔루션 중 하나가 23을 더 렌더링하는 큐브에 임의로 라벨을 붙일 수 있습니다.
  2. 2개의 방향 서브그래프는 전면에서 후면으로, 왼쪽에서 오른쪽으로 번갈아 표시할 수 있습니다.즉, 1개는 전면에서 후면으로, 또는 왼쪽에서 오른쪽으로 나타낼 수 있습니다.이러한 솔루션 하나가 회전하는 것만으로 3개를 더 만들기 때문입니다.1.의 효과를 더하면, 1개의 솔루션만을 제공함으로써 95개의 솔루션을 더 창출할 수 있습니다.다시 말해, 이러한 4개의 큐브는 24 × 3 = 41472 구성을 생성할3 수 있습니다.
  3. 큐브 [7]스택의 상단과 하단을 주의하는 것은 중요하지 않습니다.

일반화

n개의 입방체가 주어진 상태에서 각 입방체의 면이 n개의 색상 중 하나로 색칠되어 스택의 각 4개 면에 정확히 한 번 나타나도록 입방체를 스택할 수 있는지 여부를 결정합니다.[8][9]

큐브 스태킹 게임은 이 퍼즐의 2인용 게임 버전입니다.큐브 목록이 순서대로 주어지면 플레이어는 다음 큐브를 큐브 스택의 맨 위에 번갈아 추가합니다.패자는 스택의 4개 면 중 하나의 색상이 여러 번 반복되도록 하는 큐브를 추가한 첫 번째 플레이어가 됩니다.Robertson과 Munro는[10] 이 게임이 PSPACE-complete임을 증명했으며, 이는 NP-complete 퍼즐이 PSPACE-complete 게임으로 이어지는 경향이 있다는 관찰을 보여준다.

레퍼런스

  1. ^ 악마의 주사위
  2. ^ Knuth, D. E. (1975), "Estimating the efficiency of backtrack programs", Math. Comp., 29: 132–136, doi:10.1090/S0025-5718-1975-0373371-6
  3. ^ https://habrahabr.ru/post/336858/(러시아어)
  4. ^ 미국 특허번호 646,463
  5. ^ Slocum; Botermans (1986), Puzzles Old & New, p. 38
  6. ^ "Archived copy". Archived from the original on 2007-10-22. Retrieved 2007-08-12.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  7. ^ 빌러, R.; 순간 광기: 그래프 이론 입문 보조 자료; 이스트 테네시 주립 대학교 수학 통계학과; 테네시 존슨 시티: 2017
  8. ^ Garey, M. R.; Johnson, D. S. (1979), Computers and Intractibility: a guide to the theory of NP-completeness, W.H. Freeman, p. 258 (문제 GP15);
  9. ^ 를 클릭합니다Robertson, E.; Munro, I. (1978), "NP-completeness, puzzles, and games", Util. Math., 13: 99–116.
  10. ^ Robertson, Edward; Munro, Ian (1978). "NP-completeness, puzzles and games". Utilitas Mathematica. 13: 99–116.
  • Slocum; Botermans (1987), Puzzles Old and New, Seattle: University of Washington Press, p. 38, ISBN 0-295-96579-7