나이트 최소 이동 횟수 계산기

너비우선탐색(BFS)을 씁니다. 시작 칸에서 나이트가 한 수에 갈 수 있는 여덟 칸으로 물결처럼 퍼져나가며 각 칸을 처음 밟는 순간의 물결 수가 곧 그 칸까지의 최소 이동 횟수입니다. 모든 이동이 똑같이 1수라서(가중치가 균일해서) 이 방식이 항상 정확한 답을 보장합니다.

색깔 규칙으로 검산할 수 있습니다. 나이트는 한 번 움직일 때마다 반드시 칸 색이 바뀝니다(체스판처럼 칠했을 때). 그래서 시작·도착 칸의 색이 같으면 최소 이동 횟수는 항상 짝수, 다르면 항상 홀수여야 합니다. 이 계산기가 낸 값도 이 규칙을 항상 만족합니다.

edu/knight-tour는 판의 «모든 칸»을 정확히 한 번씩 밟는 경로(해밀턴 경로)를 찾는 문제로, 일반적으로 어려워 백트래킹과 휴리스틱이 필요합니다. 이 계산기는 «두 칸 사이»의 최단거리만 구하면 되는, 훨씬 단순하고 항상 정확히 풀리는 문제입니다.

네. 판이 아주 작으면(1×n 판 전체, 2×2, 2×3의 일부 칸 쌍 등) 나이트가 아예 이동할 곳이 없거나 특정 칸에 닿지 못할 수 있습니다. 이런 경우 «도달할 수 없습니다»로 정직하게 표시합니다.

됩니다. 가로·세로 칸 수를 원하는 대로(최대 200×200) 바꿀 수 있어 8×8 표준 체스판뿐 아니라 직사각형 격자나 다른 보드게임의 나이트형 말에도 그대로 적용할 수 있습니다.