나이트 투어(기사 순회) 계산기

체스 나이트가 판의 모든 칸을 정확히 한 번씩 밟는 경로입니다. 나이트는 한 방향으로 두 칸, 옆으로 한 칸 뛰므로 이어 붙이기가 만만치 않습니다. 마지막 칸에서 출발 칸으로 한 수에 돌아올 수 있으면 닫힌 투어, 그렇지 않으면 열린 투어라고 부릅니다.

있습니다. 열린 투어는 64칸 어디에서 출발해도 있고, 닫힌 투어도 있습니다. 이 도구는 8×8을 되돌아가기 없이 거의 즉시 찾아냅니다.

있습니다. 열린 투어는 3×3, 3×5, 3×6, 4×4와 세로가 1~2칸인 판(1×1 제외)에만 없고 나머지 판에는 모두 있습니다. 닫힌 투어는 조건이 더 빡빡해서, 가로·세로가 둘 다 홀수이거나 짧은 변이 1·2·4칸이거나 3×4·3×6·3×8이면 없습니다.

아닙니다. 칸 수가 홀수인 판에서는 구석과 같은 색 칸에서만 출발할 수 있습니다. 나이트는 한 수마다 칸 색이 바뀌는데 칸 수가 홀수면 한 색이 하나 더 많아, 많은 쪽에서 시작해 많은 쪽에서 끝나야 하기 때문입니다. 세로가 4칸인 판도 가운데 두 줄에서는 출발할 수 없습니다.

칸 색이 한 수마다 바뀌기 때문입니다. 닫힌 투어는 검은 칸과 흰 칸을 번갈아 밟다가 제자리로 돌아오므로 두 색의 칸 수가 같아야 하는데, 홀수×홀수 판은 칸이 홀수 개라 한 색이 하나 더 많습니다. 그래서 5×5나 7×7은 열린 투어는 있어도 닫힌 투어는 없습니다.

갈 수 있는 칸 가운데 「거기서 다시 갈 수 있는 곳이 가장 적은」 칸을 고르는 규칙입니다. 1823년에 나온 방법으로, 드나들기 어려운 구석을 먼저 처리해 두는 셈이라 뒤로 갈수록 고립되는 칸이 남지 않습니다. 8×8은 이 규칙만으로 한 번도 되돌아가지 않고 풀립니다.

아닙니다. 갈 곳 수가 같은 후보가 여럿일 때 어느 쪽을 고르느냐에 따라 막히기도 합니다. 이 도구는 막히면 되돌아가는 탐색을 얹었고, 동점을 가르는 방법을 세 가지로 바꿔 가며 시도합니다. 그래도 정해 둔 탐색 한도 안에 못 찾으면 「없다」가 아니라 「한도 안에서 못 찾았다」고 알려 드립니다.

전송되지 않습니다. 경로 찾기는 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.