이 사이트의 스테이지 298개는 사람이 그린 것이 아니라 생성기가 만든 것입니다. 모양을 뽑고, 걸러내고, 남은 것에 이름을 붙입니다. 여기서 곧바로 문제가 하나 생깁니다 — 생성한 판이 애초에 풀리는 판이라는 걸 누가 보장하나?
답은 단순합니다. 완주 경로를 실제로 하나 찾아본 판만 내보냅니다. 그리고 빌드할 때마다 테스트가 298판을 처음부터 다시 풉니다. 못 푸는 판은 배포 자체가 되지 않습니다.
솔버
백트래킹 깊이 우선 탐색인데, 다음에 갈 칸을 고르는 순서가 핵심입니다. 갈 수 있는 칸들을 그 칸에서 다시 갈 수 있는 곳의 수가 적은 순으로 정렬해서 먼저 시도합니다. 1823년 H. C. 폰 바른스도르프가 제안한 규칙이고, 200년이 지난 지금도 이 문제에서 가장 좋은 휴리스틱입니다.
직관은 이렇습니다. 구석처럼 드나들 길이 좁은 칸은 나중에 갈수록 고립됩니다. 그러니 선택지가 적은 칸부터 처리하라는 것. 코드로는 정렬 한 줄이 전부인데, 이것만으로 대부분의 판이 되돌아 나오는 일 없이 한 번에 풀립니다.
값싼 필터가 먼저인 이유
이 탐색에는 지독한 비대칭이 있습니다. 풀리는 판은 금방 끝나고, 풀리지 않는 판은 예산을 전부 태웁니다. 경로가 있으면 운이 좋을 때 칸 수만큼의 노드로 끝나지만, 없으면 없다는 걸 알기 위해 가능한 배치를 사실상 전부 뒤져야 합니다. 그래서 솔버를 돌리기 전에 값싼 검사부터 통과시킵니다.
- 패리티 — 나이트는 매 수마다 칸 색이 바뀌므로, 두 색의 개수 차가 1을 넘는 판에는 완주 경로가 없습니다
- 차수 — 갈 곳이 아예 없는 칸이 하나라도 있으면 안 되고, 갈 곳이 하나뿐인 칸은 두 개까지만 허용됩니다 (경로의 양 끝자리)
- 연결성 — 나이트 이동만으로 모든 칸이 서로 닿아야 합니다
셋 다 보드를 한 번 훑는 비용이면 끝납니다. 여기서 탈락하는 후보가 상당수라, 실제로는 이 세 줄이 생성 속도의 대부분을 만듭니다.
난이도는 칸 수가 아니다
스테이지를 쉬운 것부터 늘어놓아야 하는데, 칸 수는 난이도의 지표로 형편없었습니다. 100칸인데 바른스도르프 순서대로 두면 술술 풀리는 판이 있고, 20칸인데 되돌아 나오기를 수만 번 해야 하는 판이 있습니다.
그래서 솔버가 경로를 찾는 데 쓴 탐색 노드 수를 난이도로 씁니다. 백트래킹이 전혀 없으면 노드 수는 칸 수 근처에 머물고, 그리디한 직감이 안 통하는 판일수록 커집니다. 100 미만이면 쉬움, 2,000 미만이면 중간, 50,000 미만이면 어려움, 그 위는 매우 어려움 — 이 값이 사람이 실제로 느끼는 어려움과 꽤 잘 맞았습니다.
예산을 아끼다 두 판을 놓친 이야기
두루마리 세상 챕터는 보드의 좌우 끝이 이어져 있습니다. 왼쪽 끝에서 더 왼쪽으로 뛰면 오른쪽 끝으로 나옵니다. 이 챕터가 후보에게 요구한 조건은 단순히 "풀리는 판"이 아니라 "좌우를 이어야만 풀리는 판"이었습니다. 이어 붙이지 않고도 풀린다면 두루마리라는 규칙이 아무 의미가 없으니까요.
그래서 후보마다 두 번 물었습니다. 이어 붙인 판에서 풀리는가 — 예여야 합니다. 그리고 평범한 판에서도 풀리는가 — 아니오여야 합니다. 두 번째 질문에서 시간을 아끼려고 탐색 예산을 30만 노드로 낮췄습니다. 어차피 안 풀릴 판이니 오래 볼 것 없다고 생각한 겁니다.
테스트는 200만 노드로 검증합니다. 그리고 두 판에서 평범한 판의 풀이를 찾아냈습니다. 생성기가 "30만 노드 안에 못 찾았다"를 "없다"로 읽은 것입니다. 두 판은 좌우를 잇지 않고도 풀리는, 챕터의 규칙이 무의미한 판이었습니다.
교훈은 한 줄입니다. "솔버가 못 찾았다"는 "존재하지 않는다"가 아닙니다. 존재를 보이려 할 때는 예산을 아껴도 됩니다 — 찾으면 그 순간 끝나니까요. 부재를 보이려 할 때는 아끼면 안 됩니다. 필터의 예산을 기본값으로 되돌리고, 대신 테스트 쪽에 넉넉한 제한 시간을 줬습니다.
보장하는 것과 하지 않는 것
보장하는 건 하나입니다. 모든 스테이지에 완주 경로가 적어도 하나 있다는 것. 유일하다는 뜻이 아닙니다. 대부분의 판에는 경로가 여럿이라, 같은 판을 두 번 깨도 같은 길을 걷지 않습니다.
사람이 쉽게 찾을 수 있다는 뜻도 아닙니다. 기계가 5만 번 되돌아 나와서 찾아낸 길이라면, 사람도 꽤 헤맵니다.
이어서: 4×4 판에는 완주 경로가 없다 — 증명스테이지 모드