기사의 여행 플래시게임

기사의 여행은 어떤 퍼즐인가요?

기사의 여행은 체스의 나이트 한 개로 판의 모든 칸을 정확히 한 번씩 밟는 퍼즐입니다. 영어로는 나이트 투어(Knight's Tour)라고 하고, 나이트 순회나 기사 순례라는 이름으로도 부릅니다.

나이트는 체스에서 유일하게 다른 말을 뛰어넘는 말로, 한 번에 가로나 세로로 두 칸 간 뒤 옆으로 한 칸 꺾어 L자 모양으로 내려앉습니다. 이 게임에서는 출발 칸을 고른 뒤 초록 고리로 빛나는 칸을 하나씩 누르며 나아갑니다. 지나간 칸에는 1, 2, 3 하는 순서 번호가 놋쇠 단추처럼 박히고, 칸과 칸 사이는 금빛 선으로 이어집니다. 모든 칸을 다 밟고 나면 선들이 겹쳐 별이나 꽃무늬 같은 그림이 완성됩니다.

규칙은 정확히 무엇인가요?

규칙은 둘입니다. 나이트 걸음으로만 움직이고, 한 번 밟은 칸은 다시 밟지 않습니다. 판의 칸 수만큼 밟으면 끝납니다.

나이트는 뛸 때마다 밝은 칸과 어두운 칸을 번갈아 밟습니다. 그래서 칸 수가 홀수인 5×5와 7×7 판은 한 색이 한 칸 더 많고, 많은 쪽 색(네 모서리와 같은 색)에서 출발해야만 완주할 수 있습니다. 게임에서는 완주가 가능한 칸에만 초록 점이 표시되며, 탐색기로 5×5의 13칸과 7×7의 25칸 모두에서 실제로 완주 길이 있다는 것을 확인했습니다.

Warnsdorff 규칙이란 무엇인가요?

Warnsdorff 규칙은 갈 수 있는 칸 가운데, 그 칸에 갔을 때 다음에 갈 곳이 가장 적은 칸을 먼저 고르는 방법입니다. 1823년 독일의 H. C. 폰 바른스도르프가 발표했습니다.

갈 곳이 적은 칸은 나중으로 미룰수록 고립되기 쉽습니다. 구석이나 가장자리 칸이 대표적입니다. 그런 칸을 먼저 처리하고 갈 곳이 많은 가운데 칸을 마지막까지 남겨 두면 막다른 곳에 몰릴 일이 크게 줄어듭니다. 예를 들어 지금 갈 수 있는 칸이 셋이고, 각 칸에서 다시 갈 수 있는 곳이 2곳, 5곳, 3곳이라면 2곳짜리 칸으로 갑니다. 이 규칙만 지켜도 8×8 판은 대부분 한 번에 완주됩니다.

이 게임의 힌트는 Warnsdorff 순서로 먼저 길을 찾아보고, 막히면 되돌아가 다른 가지를 살피는 탐색기로 완주가 정말 되는 다음 칸을 알려 줍니다. 이미 완주할 수 없는 길에 들어섰다면 몇 수 전으로 돌아가야 살릴 수 있는지 찾아 그 칸을 파랗게 반짝여 주고, 그 칸을 누르면 거기까지 한 번에 되돌아갑니다.

닫힌 여행(폐경로)은 무엇인가요?

닫힌 여행은 마지막으로 밟은 칸에서 첫 칸으로 나이트가 한 번 더 뛸 수 있게 끝난 완주입니다. 처음과 끝이 이어져 고리가 되므로 폐경로, 재진입 여행이라고도 합니다.

닫힌 여행으로 끝나면 마지막 칸과 첫 칸 사이에 빛나는 점선이 그려지고, 출발 칸 둘레에 별 고리가 돌며 결과 창에 닫힌 여행이 몇 번째인지 남습니다. 닫힌 여행은 칸 수가 짝수인 판에서만 나옵니다. 고리를 이루려면 밝은 칸과 어두운 칸의 수가 같아야 하기 때문입니다. 그래서 이 게임에서는 6×6과 8×8 판에서 노려 볼 수 있습니다.

기사의 여행은 언제부터 있었나요?

기사의 여행은 천 년이 넘은 퍼즐입니다. 알려진 가장 오래된 예는 9세기 인도 시인 루드라타의 시학서 「카비알랑카라」에 실린, 시의 음절을 반쪽 판 위에 나이트 걸음 순서로 늘어놓은 글귀입니다.

그 뒤 이슬람 세계의 체스 문헌에도 나이트 순회 문제가 실렸고, 18세기에는 수학자 레온하르트 오일러가 1759년 이 문제를 깊이 연구해 닫힌 여행을 만드는 방법과 대칭인 여행을 여럿 발표했습니다. 1823년에는 바른스도르프가 손으로도 쓸 수 있는 규칙을 내놓았습니다. 오늘날 기사의 여행은 그래프 이론에서 해밀턴 경로를 설명하는 대표 예제이고, 1997년 브렌던 매케이는 8×8 판의 닫힌 여행이 방향을 따지지 않고 13,267,364,410,532가지라고 셈해 냈습니다.

완주하려면 어떤 요령이 있나요?

1. 구석과 가장자리부터 처리하세요. 구석 칸은 들어오고 나가는 길이 두 개뿐이라 미뤄 두면 고립되기 쉽습니다.
2. 갈 곳이 가장 적은 칸으로 가세요. Warnsdorff 규칙 그대로입니다. 고르기 어려우면 판 가장자리에 가까운 쪽을 고릅니다.
3. 빨갛게 깜빡이는 칸을 보세요. 더는 닿을 길이 없어진 칸은 붉게 표시됩니다. 그 칸이 마지막 칸이 될 수 없다면 이미 실패한 길이니 일찍 되돌리세요.
4. 되돌리기를 아끼지 마세요. 한 수, 다섯 수 단추 말고도 지나온 칸을 두 번 누르면 그 칸까지 한 번에 돌아갑니다.
5. 작은 판부터 시작하세요. 6×6은 어디서 출발해도 완주가 되어 연습하기 좋고, 5×5와 7×7은 출발 칸 제약 때문에 오히려 까다롭습니다.

조작법

• 휴대폰·마우스: 처음에 초록 점이 있는 칸을 눌러 출발 칸을 정하거나 무작위 출발을 누릅니다. 그다음 초록 고리가 있는 칸을 누르거나 나이트를 끌어다 놓으면 포물선을 그리며 뛰어 내려앉습니다.
• 되돌리기: 한 수 단추는 바로 앞 칸으로, 다섯 수 단추는 다섯 칸 전으로 돌아갑니다. 지나온 칸을 한 번 누르면 몇 수 되돌릴지 알려 주고, 한 번 더 누르면 그 칸까지 돌아갑니다. 새 출발은 출발 칸부터 다시 고릅니다.
• 키보드: 방향키로 칸을 고르고 Enter나 Space로 뜁니다. Z나 Backspace 한 수, X 다섯 수, H 힌트, 출발 칸을 고를 때 R 무작위 출발입니다.
• 오늘의 판: 하루 동안 모두에게 같은 크기와 같은 출발 칸이 주어지고, 끝내면 출석 기록에 걸린 시간이 남습니다.

하던 판, 판 크기별 최고 기록, 닫힌 여행 횟수는 지금 쓰는 브라우저에만 저장되고 서버로 보내지 않습니다. 결과 자랑하기로 보낸 주소를 연 사람은 같은 크기, 같은 출발 칸으로 도전할 수 있습니다.