200년 된 요령이 아직도 최선이다 — 바른스도르프 규칙

나이트 투어를 처음 잡으면 대개 이렇게 됩니다. 판 가운데를 신나게 돌아다니다가, 어느 순간 구석 몇 칸이 갈 수 없는 섬이 되어 남습니다. 되돌리기를 눌러도 이미 스무 수 전에 갈림길이 있었던 터라 어디로 돌아가야 할지 모릅니다.

이 문제의 해법은 1823년에 나왔습니다. H. C. 폰 바른스도르프가 제안한 규칙은 한 줄입니다. 갈 수 있는 칸 중에서, 그 칸에 갔을 때 다시 갈 수 있는 곳이 가장 적은 칸을 먼저 밟아라.

왜 통하나

칸마다 "문의 개수"가 다릅니다. 판 한가운데 칸은 나이트가 드나들 길이 여덟 개까지 있지만, 구석 칸은 둘뿐입니다. 문이 둘인 방은 하나로 들어가서 하나로 나오면 끝입니다. 그런데 그 두 문 중 하나를 이미 다른 데서 써버렸다면, 그 방은 들어가면 나올 수 없는 방이 됩니다. 남은 칸이 있는데 나올 수 없다면 그 판은 거기서 끝입니다.

그러니 문이 적은 방부터 처리하라는 것입니다. 넓은 방은 나중에 가도 여전히 넓지만, 좁은 방은 시간이 갈수록 더 좁아집니다. 게임에서 구석과 가장자리를 먼저 밟으라는 조언은 이 규칙의 사람용 요약입니다.

놀라운 건 효과입니다. 정렬 한 줄을 넣었을 뿐인데 대부분의 판이 한 번도 되돌아 나오지 않고 풀립니다. 200년 동안 더 나은 일반 휴리스틱이 나오지 않았습니다.

그런데 이건 보장이 아니다

바른스도르프 규칙은 휴리스틱입니다. 정리가 아니라 요령이라는 뜻이고, 실제로 실패합니다. 실패의 대부분은 동점에서 나옵니다.

갈 수 있는 칸 두 개의 선택지 수가 똑같이 3이라면 규칙은 아무 말도 해주지 않습니다. 그리고 이런 동점은 아주 흔합니다. 어느 쪽을 고르냐에 따라 스무 수 뒤의 운명이 갈리는데, 규칙 자체에는 그걸 가릴 근거가 없습니다.

그래서 이 사이트의 솔버는 바른스도르프를 정답이 아니라 순서로만 씁니다. 낮은 차수 순으로 정렬해 먼저 시도하되, 막히면 되돌아 나와 다음 후보를 봅니다. 휴리스틱이 잘 맞으면 백트래킹이 거의 없고, 안 맞으면 그만큼 되돌아 나옵니다. 그 되돌아 나온 횟수가 곧 그 판의 난이도가 됩니다.

변형 규칙에서 무너지는 지점

이 게임에는 규칙이 조금씩 다른 챕터가 있는데, 그중 둘은 바른스도르프 직감을 정면으로 깨뜨립니다.

두루마리 세상에서는 판의 좌우 끝이 이어져 있습니다. 왼쪽 끝에서 더 왼쪽으로 뛰면 오른쪽 끝으로 나옵니다. 그러면 좌우 가장자리 칸의 문이 확 늘어납니다. 구석이 더 이상 구석이 아니고, "구석부터 처리하라"는 요령의 전제 자체가 사라집니다. 위아래는 여전히 막혀 있어서 절반만 무너지는데, 그 어긋남이 이 챕터를 어렵게 만듭니다.

정해진 끝에서는 깃발이 꽂힌 칸에서 여행을 마쳐야 합니다. 바른스도르프는 이걸 모릅니다. 목표 칸은 다른 칸이 채워질수록 선택지가 줄어들어, 규칙대로라면 오히려 일찍 밟게 됩니다. 정확히 하면 안 되는 일입니다. 여기서는 마지막 한 수를 위해 그 칸을 일부러 비워 두는 계산이 필요한데, 이건 그리디 규칙이 표현할 수 없는 종류의 계획입니다.

사람이 쓰는 법

연습 모드에서 수 세기를 켜면 각 칸에 그 칸의 남은 선택지 수가 표시됩니다. 힌트는 그중 가장 작은 칸을 짚어 줍니다. 몇 판만 이대로 따라가 보면 규칙이 몸에 붙고, 동시에 규칙이 흔들리는 순간도 보입니다. 동점이 셋씩 생기는 자리, 그리고 규칙대로 갔는데도 막히는 자리입니다.

그 자리가 이 퍼즐의 진짜 재미입니다. 규칙이 다 해주면 게임이 아니니까요.