기사의 여행

기사의 여행은 체스판 위의 임의의 위치에서 기사가 출발하여 각 위치를 오직 한 번만 방문하면서 모든 위치를 방문하는 순서를 구하는 문제입니다. 오일러 등의 많은 수학자들이 이 문제를 다루었으며, 다양한 해법과 변형된 문제들이 있습니다. 가장 일반적인 해법은 되추적을 이용한 방법입니다.

19세기의 H. C. Warnsdorff는 기사의 여행 문제를 푸는 실용적인 방법을 제시하였습니다. 기사가 움직이면서 어느 곳으로도 움직일 수 없는 막다른 곳에 다다르지 않게 하는 것이 목적입니다. 막다른 곳에 다다르지 않게 하기 위하여 Warnsdorff가 제시한 규칙은 현재 기사가 한 번에 갈 수 있는 곳 중에서 다음 번 수에 갈 수 있는 곳이 가장 적은 곳으로 간다는 규칙입니다. 이 방법은 휴리스틱한 방법입니다만, 8 x 8의 체스판 공간에서 기사의 여행 문제를 잘 풀어 줍니다. 체스판의 공간이 넓어지면 제대로 풀리지 않는 경우가 생길 수 있습니다.

Warnsdorff의 규칙을 이용하여 기사의 여행 문제를 푸는 간단한 프로그램을 작성해 보았습니다. C언어로 작성되어 있고 시작행과 시작열의 위치를 기본 입력에서 읽어서 기본 출력으로 해를 출력해 줍니다.

  1 /*
  2  * Knight's Tour.
  3  *
  4  * Author: Jay
  5  * Date: 20th of December, 2006
  6  */
  7 #include <stdio.h>
  8 
  9 /* definitions */
 10 #define ROW_SIZE 8
 11 #define COL_SIZE 8
 12 #define NUM_WAYS 8
 13 typedef int board_t[ROW_SIZE][COL_SIZE];
 14 int dr[NUM_WAYS] = {-2, -1, 1, 2, 2, 1, -1, -2};
 15 int dc[NUM_WAYS] = {1, 2, 2, 1, -1, -2, -2, -1};
 16 
 17 /**
 18  * Set every element to -1
 19  */
 20 void initialize_board(board_t board)
 21 {
 22     int i, j;
 23     for (i=0; i<ROW_SIZE; i++)
 24         for (j=0; j<COL_SIZE; j++)
 25             board[i][j] = -1;
 26 }
 27 
 28 /**
 29  * Print the board out.
 30  */
 31 void print_board(board_t board)
 32 {
 33     int i, j;
 34     for (i=0; i<ROW_SIZE; i++)
 35     {
 36         for (j=0; j<COL_SIZE; j++)
 37             printf("%d\t", board[i][j]);
 38         printf("\n");
 39     }
 40 }
 41 
 42 /**
 43  * Check if (r,c) is inside board.
 44  * @return true if (r,c) is inside board, false otherwise.
 45  */
 46 int is_inside_board(int r, int c)
 47 {
 48     return r >= 0 && r < ROW_SIZE && c >= 0 && c < COL_SIZE;
 49 }
 50 
 51 /**
 52  * Check if (r,c) is available in board.
 53  * @return true if (r,c) is available, that is has value -1,
 54  *         false otherwise.
 55  */
 56 int is_available(board_t board, int r, int c)
 57 {
 58     return is_inside_board(r, c) && board[r][c] == -1;
 59 }
 60 
 61 /**
 62  * @return number of next moves of (r,c) in board.
 63  */
 64 int num_next_moves(board_t board, int r, int c)
 65 {
 66     int i, result=0;
 67     for (i=0; i<NUM_WAYS; i++)
 68         if (is_available(board, r+dr[i], c+dc[i]))
 69             result++;
 70     return result;
 71 }
 72 
 73 /**
 74  * Get next way id from (r,c) in board.
 75  * Next way is the way whose destination has minimal number of next moves.
 76  * @return next way id, which is in [0, NUM_WAYS).
 77  */
 78 int next_way_of(board_t board, int r, int c)
 79 {
 80     int i, min = NUM_WAYS, result=0;
 81     for (i=0; i<NUM_WAYS; i++)
 82         if (is_available(board, r+dr[i], c+dc[i])
 83                 && num_next_moves(board, r+dr[i], c+dc[i]) < min)
 84         {
 85             min = num_next_moves(board, r+dr[i], c+dc[i]);
 86             result = i;
 87         }
 88     return result;
 89 }
 90 
 91 /**
 92  * Get r, c from user and solve knight tour problem.
 93  * Print result out.
 94  * @return 0 for successful moves, 1 otherwise.
 95  */
 96 int main()
 97 {
 98     int r, c, move, next_way;
 99     board_t board;
100 
101     initialize_board(board);
102     while (1)
103     {
104         printf("Input start position r c: ");
105         scanf("%d %d", &r, &c);
106         fflush(stdin);
107         if (is_inside_board(r, c)) break;
108         printf("Please put them again.\n");
109     }
110     board[r][c] = 0;
111 
112     for (move=1; move<ROW_SIZE*COL_SIZE; move++)
113     {
114         if (num_next_moves(board, r, c) == 0)
115         {
116             printf("Failed.\n");
117             print_board(board);
118             return 1;
119         }
120         next_way = next_way_of(board, r, c);
121         r = r + dr[next_way];
122         c = c + dc[next_way];
123         board[r][c] = move;
124     }
125     print_board(board);
126 
127     return 0;
128 }

참고할 수 있는 URL:
Warnsdorff's rule - 영문 페이지