why-is-the-15-puzzle-unsolvable

15퍼즐이 풀 수 없는 이유

“15퍼즐”, 또는 “15디지털 문제”는 풀 수 없기 때문이 아니라 특정 초기 상태에서는 목표 상태에 도달할 수 없기 때문입니다.

게임 설명

“15퍼즐”은 4×4 그리드에 15개의 슬라이더(1부터 15까지 번호가 매겨짐)와 하나의 공간이 있는 슬라이더 게임입니다. 플레이어의 목표는 슬라이더를 왼쪽에서 오른쪽으로, 위에서 아래로 순서대로 움직여 1부터 15까지의 정렬된 순서를 만들고 오른쪽 아래 모서리에 공간을 배치하는 것입니다.

풀 수 없는 경우

만약 초기 상태에서 역순 쌍의 개수가 홀수이면, 목표 상태로 이동할 수 없습니다. 역순 쌍이란, 일련의 숫자들 중에 앞의 숫자가 뒤의 숫자보다 큰 경우를 말합니다. 예를 들어, 2, 4, 3, 1 시퀀스에서 역순 쌍은 (2,1), (4,3), (4,1), (3,1) 로 모두 4개입니다.

증명

보드에서 슬라이더의 이동은 이러한 슬라이더의 배열 변환으로 생각할 수 있습니다. 슬라이더를 한 번 이동할 때마다 공간이 인접한 슬라이더와 교환됩니다. 그리고 이 교환 연산은 배열의 역순 로그의 패리티를 바꿉니다. 목표 상태의 역순 로그 값은 0으로 짝수입니다. 초기 상태의 역순 로그가 홀수이면, 이동 횟수에 관계없이 역순 로그 값은 짝수로 바뀌지 않으므로 목표 상태에 도달할 수 없습니다.

만약 Puzzles ball도 플레이하고 싶다면, 완전히 무료하고 재미있고 쉽습니다.