4×4 판에는 완주 경로가 없다 — 증명

이 사이트의 스테이지는 12칸짜리부터 112칸짜리까지 298개가 있는데, 4×4(16칸)는 하나도 없습니다. 만들다 실패한 것이 아닙니다. 4×4 위에는 완주 경로가 존재하지 않고, 그건 종이와 색연필 두 자루로 증명할 수 있습니다.

첫 번째 색칠 — 나이트는 매 수마다 칸 색이 바뀐다

체스판처럼 칸을 흑백으로 칠합니다. 행과 열을 더해 짝수면 흰 칸, 홀수면 검은 칸입니다. 나이트의 이동은 한 방향으로 2칸, 다른 방향으로 1칸이라 행과 열의 변화량을 더하면 항상 홀수(2+1=3)입니다. 홀수를 더하면 짝홀이 뒤집히므로, 나이트는 절대로 같은 색 칸에 내릴 수 없습니다.

여기서 값싼 필터가 하나 나옵니다. 모든 칸을 한 번씩 밟는 경로는 색을 번갈아 밟게 되므로, 두 색의 개수 차가 1을 넘는 판에는 완주 경로가 아예 없습니다. 이 사이트의 생성기가 후보 보드를 만들 때 가장 먼저 보는 조건이 이것입니다. 곁가지로, 게임에 나오는 얼룩말의 2×3 뜀도 합이 5로 홀수라 같은 성질을 갖습니다. 반면 1×3으로 뛰는 낙타는 합이 짝수라 색을 바꾸지 못하고, 그래서 판의 절반에는 영원히 가지 못합니다.

그런데 4×4는 흰 칸 8개, 검은 칸 8개로 정확히 균형입니다. 이 필터를 통과합니다. 차수도 문제가 없고, 모든 칸이 나이트 이동으로 이어져 있기도 합니다. 값싼 검사 셋으로는 4×4를 걸러낼 수 없습니다.

두 번째 색칠

이번엔 다르게 칠합니다. 바깥 두 줄(1행과 4행)을 빨강, 안쪽 두 줄(2행과 3행)을 파랑. 빨강 8칸, 파랑 8칸입니다.

여기서 결정적인 사실 하나가 나옵니다. 빨강 칸에서 출발한 나이트는 반드시 파랑 칸에 내립니다. 1행의 나이트는 행이 1칸이나 2칸 움직이므로 2행 아니면 3행에만 갈 수 있고 둘 다 파랑입니다. 4행도 대칭으로 같습니다. 파랑에서 파랑으로 가는 것은 가능하지만(2행에서 3행으로), 우리에게 필요한 건 한쪽 방향뿐입니다.

모순

완주 경로가 있다고 가정합시다. 16칸을 한 번씩 밟는 순서열입니다. 빨강 다음은 항상 파랑이므로, 이 열에서 빨강이 연달아 나올 수 없습니다. 16개 자리에 빨강 8개를 어느 둘도 붙지 않게 놓는 방법은 홀수 자리 전부(1, 3, 5, …, 15)이거나 짝수 자리 전부(2, 4, …, 16)뿐입니다.

한편 흑백 색칠에서도 색이 매 수 바뀌므로, 검은 칸 역시 홀수 자리 전부이거나 짝수 자리 전부를 차지합니다.

그러면 빨강 8칸의 집합은 검은 8칸과 같거나 흰 8칸과 같아야 합니다 — 같은 자리들을 차지하니까요. 그런데 빨강(1행과 4행)을 실제로 세어 보면 검은 칸 4개와 흰 칸 4개가 섞여 있습니다. 8개가 전부 한 색일 수가 없습니다. 모순입니다.

따라서 4×4 판 위에 완주 경로는 존재하지 않습니다. 이 논증은 헝가리 수학자 러요시 포샤(Louis Pósa)의 이름으로 알려져 있고, 색칠 두 번이 전부라 손으로 따라가기 좋습니다.

생성기는 이 증명을 모른다

증명은 우아하지만 생성기는 이런 논증을 하지 못합니다. 4×4는 값싼 필터를 전부 통과하고, 솔버가 16칸짜리 탐색을 끝까지 마친 뒤에야 없다고 답합니다. 16칸이라 순식간이지만, 판이 커지면 이 "없음을 확인하는 비용"이 곧 생성 속도의 전부가 됩니다.