15퍼즐 풀이 가능 판정기

아닙니다. 배치의 딱 절반은 아무리 밀어도 절대 맞춰지지 않습니다. 4×4라면 16!가지 배치 가운데 절반만 완성판에서 밀어 닿을 수 있고, 나머지 절반은 완전히 다른 세계에 있습니다. 조각을 손으로 빼서 바꿔 끼우면 이 두 세계를 건너뛰게 됩니다.

반전수와 빈칸의 위치로 판정합니다. 반전수는 빈칸을 빼고 왼쪽 위부터 읽어 내려가며 「뒤에 있는데 더 작은」 짝을 센 것입니다. 판의 너비가 홀수면 반전수가 짝수여야 풀리고, 너비가 짝수면 반전수와 아래에서 센 빈칸의 행 번호를 더한 값이 홀수여야 풀립니다.

빈칸이 한 행 위아래로 움직일 때 반전수가 너비−1만큼 바뀌기 때문입니다. 너비가 홀수면 너비−1이 짝수라 반전수의 홀짝이 그대로여서 빈칸의 행을 볼 필요가 없고, 너비가 짝수면 홀짝이 뒤집혀 빈칸의 행까지 같이 세어야 합니다. 이 자리가 가장 많이 틀리는 곳입니다.

1880년 샘 로이드가 14와 15만 자리를 바꾼 판을 내놓고 원래대로 맞추면 1,000달러를 주겠다고 한 현상 문제입니다. 이 배치는 반전수가 1이고 빈칸이 맨 아래 행에 있어 풀 수 없는 쪽에 속합니다. 아무도 상금을 받지 못했고, 애초에 받을 수 없는 문제였습니다.

아무 두 조각의 자리를 서로 바꾸면 됩니다. 맞바꿈 한 번이 순열의 홀짝을 뒤집으므로 판정이 반대로 넘어갑니다. 밀어서는 절대 건널 수 없는 경계를 조각을 빼서 바꿔 끼우면 한 번에 건너게 되는 셈입니다.

IDA* 탐색으로 찾습니다. 각 조각이 제자리까지 가야 하는 거리(맨해튼 거리)의 합을 어림값으로 쓰는데, 한 번 밀 때 이 합은 많아야 1 줄어들기 때문에 실제 최단 수를 절대 넘지 않습니다. 그래서 처음 찾아낸 답이 곧 최단 수순입니다. 이 도구는 칸이 9개 이하인 판에서만 찾습니다.

31수입니다. 8퍼즐에서 가장 먼 배치도 31번만 밀면 맞출 수 있습니다. 4×4인 15퍼즐은 최대 80수로 알려져 있으며, 이 값을 확인하는 데만 수십 년의 계산이 필요했습니다.

전송되지 않습니다. 판정과 탐색은 모두 브라우저 안에서 이뤄지고, 입력한 배치는 이 기기에만 남습니다.