체스에서 나이트(knight)는 다른 말들과 달리 특별한 방식으로 점프할 수 있습니다. 나이트는 가로로 두 칸, 세로로 한 칸 이동하거나, 세로로 두 칸, 가로로 한 칸 이동할 수 있으며, 어느 방향이든 이동 경로가 영문자 'L' 모양을 그리게 됩니다.
이 문제는 비어 있는 체스판 위에서 나이트가 임의의 위치에서 출발했을 때, 체스판의 모든 칸을 정확히 한 번씩 방문할 수 있는지 확인하는 것입니다. 모든 칸을 방문하는 것이 가능하다면, 각 칸에 시작점으로부터 그 위치에 도달하기까지 필요한 이동(점프) 횟수를 기록합니다.
나이트 투어는 여러 가지 해답을 가질 수 있지만, 이 글에서는 그중 하나의 유효한 해를 찾는 방법을 다룹니다.
입력과 출력
입력: 체스판의 크기. 일반적으로 8입니다. (8 x 8은 표준 체스판의 크기입니다.) 출력: 나이트의 이동 순서. 각 칸에는 숫자가 들어가며, 이 숫자는 나이트가 시작점에서 몇 번째 이동으로 해당 칸에 도착하는지를 나타냅니다. 0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12
알고리즘
이 문제는 대표적인 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 위치에서 나이트가 이동할 수 있는 8가지 방향을 차례대로 시도합니다.
- 다음 위치가 체스판 범위 안에 있고 아직 방문하지 않은 칸이라면, 그곳으로 이동하고 이동 횟수를 기록합니다.
- 그 이후의 탐색이 실패하면, 기록을 지우고 이전 상태로 되돌아가(백트래킹) 다른 방향을 시도합니다.
isValid(x, y, solution)
입력 − 좌표 x, y와 해답 행렬(solution matrix)
출력 − (x, y)가 체스판 범위 안에 있고 아직 값이 할당되지 않았는지 검사한 결과
Begin
if 0 ≤ x ≤ Board Size and 0 ≤ y ≤ Board Size, and (x, y) is empty, then
return true
EndknightTour(x, y, move, sol, xMove, yMove)
입력 − 현재 위치 (x, y), 이동 횟수(move), 해답 행렬(sol), 나이트가 이동 가능한 x축·y축 방향 목록(xMove, yMove)
출력 − 해가 존재하는 경우 갱신된 해답 행렬
Begin
if move = Board Size * Board Size, then //모든 칸을 방문한 경우
return true
for k := 0 to number of possible xMovement or yMovement, do
xNext := x + xMove[k]
yNext := y + yMove[k]
if isValid(xNext, yNext, sol) is true, then
sol[xNext, yNext] := move
if knightTour(xNext, yNext, move+1, sol, xMove, yMove), then
return true
else
remove move from the sol[xNext, yNext] to backtrack
done
return false
EndC++ 구현 예제
#include <iostream>
#include <iomanip>
#define N 8
using namespace std;
int sol[N][N];
bool isValid(int x, int y, int sol[N][N]) { //범위 안에 있고 아직 할당되지 않은 칸인지 검사
return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
void displaySolution() {
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
cout << setw(3) << sol[x][y] << " ";
cout << endl;
}
}
int knightTour(int x, int y, int move, int sol[N][N], int xMove[N], int yMove[N]) {
int xNext, yNext;
if (move == N*N) //체스판 전체를 커버한 경우
return true;
for (int k = 0; k < 8; k++) {
xNext = x + xMove[k];
yNext = y + yMove[k];
if (isValid(xNext, yNext, sol)) { //해당 칸이 이미 점유되었는지 검사
sol[xNext][yNext] = move;
if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true)
return true;
else
sol[xNext][yNext] = -1;// 백트래킹
}
}
return false;
}
bool findKnightTourSol() {
for (int x = 0; x < N; x++) //처음에 해답 행렬의 모든 값을 -1로 초기화
for (int y = 0; y < N; y++)
sol[x][y] = -1;
//나이트가 이동 가능한 모든 방향
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
sol[0][0] = 0; //(0, 0)에서 시작
if (knightTour(0, 0, 1, sol, xMove, yMove) == false) {
cout << "Solution does not exist";
return false;
} else
displaySolution();
return true;
}
int main() {
findKnightTourSol();
}실행 결과
0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12
위 결과에서 각 칸의 숫자는 나이트가 (0, 0)에서 출발하여 해당 칸에 도착하는 이동 순서를 의미합니다. 숫자 0은 시작 위치이며, 63은 마지막(64번째) 방문 칸입니다. 이처럼 백트래킹을 활용하면 나이트가 체스판의 모든 칸을 한 번씩 거쳐가는 경로를 효과적으로 찾을 수 있습니다.