Backtracking | The Knight’s tour problem

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다.
• 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

Backtracking(퇴각 검색)

Backtracking(퇴각 검색)은 정답을 찾을 때까지 다른 해답을 시도해보는 알고리즘이다. 보통 다른 알고리즘이 아닌 backtracking이 해법이 ㄴ경우 대부분 모든 경우의 수를 시도해야 해결되는 문제가 많다. Naive한 방법은 모든 경우의 수를 대입하겠지만 시간 복잡도의 문제로 인해 제시된 문제에서 파악할 수 있는 제약 조건이 있는 경우 모두 적용해서 최적화를 시도해야 한다.

나이트가 주어진 셀을 모두 거칠 수 있는 경로

그림과 같이 8*8 맵이 주어졌을 때, 셀에 적인 번호는 Knight 말이 몇 번째 움직임에 해당 셀을 지나갔음을 의미한다. 우리는 빈 맵이 주어지고 시작점이 $(0,0)$인 상황에서 Knight가 어떻게 움직여야 하는지 제시해야 한다.

Knight's tour에 대한 Naive Algorithm

1. 만약 시도하지 않은 경로가 있다면 경로를 생성한다
2. 해당 경로가 모든 셀을 지나가면 출력한다.

Knight's tour에 대한 backtracking Algorithm

1. 만약 모든 셀을 지나가는 경로를 발견했다면 경로를 출력한다.
2. 움직임 1회를 더할 때 해당 지점이 제한 요건을 위배하는지 검사한 뒤 위배된다면 경우의 수를 지우고 다음 대안으로 진행한다. 위배되지 않는다면 말을 움직인 뒤 재탐색한다.
3. 계속 반복하여 진행하였으나 모든 대안이 실패한 경우 이전 단계로 돌아가 움직였던 위치를 초기화하여 다음 대안을 시도한다.
4. 이런 식으로 2번의 넓이, 3번의 깊이 탐색을 모두 진행하였음에도 처음으로 돌아온 경우 ''해결법이 없다'라고 말할 수 있다.

C코드

#include <stdio.h>
#define N 8
// 메인함수에서 호출해야 하므로 어떤 조건이 필요한 지 먼저 명세하여 정의
int solveKTUtil(int x, int y, int movei, int sol[N][N],
                int xMove[], int yMove[]);
 
int isSafe(int x, int y, int sol[N][N])
{// X, Y가 주어진 셀을 벗어나는지, 이미 지나간 곳인지 검사한다.
    return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
 
void printSolution(int sol[N][N])
{
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            printf(" %2d", sol[x][y]);
        }
        printf("\n");
    }
}
 
int solveKT()
{
    int sol[N][N];
 
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            sol[x][y] = -1;  // 각 셀에 대해 초기화
        }
    }
 
    // Knight가 한 번에 움직일 수 있는 x, y 거리를 배열로 정의
    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; // Knight의 시작점 초기화
 
    // 만약 탐색이 끝날 때까지 결과가 없다면
    if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0)
    {
        printf("There's no Solution"); // 답이 없음을 출력
        return 0;
    }
    else // 재귀 탐색 중 해답이 있음를 반환하면
    {
        printSolution(sol); // Knight의 경로 출력
    }
    return 1;
}
 
// 재귀 탐색을 진행할 함수 정의
// 현재 좌표, 몇 번째 움직임인지, 전체 맵, 움직일 수 있는 거리 필요
int solveKTUtil(int x, int y, int movei, int sol[N][N],
                int xMove[8], int yMove[8])
{
    int k, next_x, next_y;
    if (movei == N*N) // 만약 모든 셀을 거쳐왔다면
    {
        return 1; // 탐색을 종료
    }
 
    for (k = 0; k < 8; k++) // Knight가 움직일 수 있는 모든 경우에 대해
    {
        next_x = x + xMove[k]; // 다음 x 좌표에 움직임 반영
        next_y = y + yMove[k]; // 다음 y 좌표에 움직임 반영
 
        if (isSafe(next_x, next_y, sol)) // 반영된 좌표가 가능한지 검사
        {
            sol[next_x][next_y] = movei; // 가능하면 다음 움직임으로 반영
            if (solveKTUtil(next_x, next_y, movei+1, sol, 
                            xMove, yMove) == 1)
            { // 이후 단계로부터 해법이 있음을 반환받으면
                return 1; // 이전 단계로 올라가 해법이 있음을 반환
            }
            else // 만약 해법이 없다고 반환 받으면 
            {
                 sol[next_x][next_y] = -1; // backtracking
            }
        }
    }
    return 0;
}
 
int main()
{
    solveKT();
    return 0;
}

Python 코드

def isSafe(x,y,board): 
    if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1): 
        return True
    return False
 
def printSolution(n, board): 
    for i in range(n): 
        for j in range(n): 
            print(board[i][j],end =' ') 
        print() 
 
 
def solveKT(n): 
    board = [[-1 for i in range(n)]for i in range(n)] 
 
    move_x = [2, 1, -1, -2, -2, -1, 1, 2] 
    move_y = [1, 2, 2, 1, -1, -2, -2, -1] 
 
    board[0][0] = 0
    pos = 1
 
    if(not solveKTUtil(n, board, 0, 0, move_x, move_y, pos)): 
        print("Solution does not exist") 
    else: 
        printSolution(n, board) 
 
def solveKTUtil(n,board,curr_x,curr_y,move_x,move_y,pos): 
    if(pos == n**2): 
        return True
 
    for i in range(8): 
        new_x = curr_x + move_x[i] 
        new_y = curr_y + move_y[i] 
        if(isSafe(new_x,new_y,board)): 
            board[new_x][new_y] = pos
            if(solveKTUtil(n, board, new_x, new_y, 
                           move_x, move_y, pos+1)): 
                return True
            board[new_x][new_y] = -1 # backtracking
    return False
 
n = 8
solveKT(n) 

C++ 코드

#include <bits/stdc++.h>
using namespace std;
#define N 8
// 메인 함수에 사용하기 전 미리 요구사항 담아서 함수 정의
int solveKTUtil(int x, int y, int movei, int sol[N][N],
                int xMove[], int yMove[]);
 
int isSafe(int x, int y, int sol[N][N])
{ // x, y가 범위를 벗어나는 지, 해당 셀이 미리 지나간 곳인지 검사
    return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
 
void printSolution(int sol[N][N])
{
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        { // 2칸에 맞춰서 숫자를 출력하고 뒤에 한 칸 띄움
            cout << setw(2) << sol[x][y] << " ";
        }
        cout << endl; // 각 행 출력 뒤 개행
    }
}
 
int solveKT()
{
    int sol[N][N];
 
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            sol[x][y] = -1; // 맵 초기화
        }
    }
    // 나이트가 한번에 갈 수 있는 x, y 좌표 등록
    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; // 시작점 등록
 
    if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0) // 해법이 없으면
    {
        cout << "There's no Solution"; // 답없음 출력
        return 0;
    }
    else // 해법이 있으면
    {
        printSolution(sol); // 전체 맵 출력
    }
    return 1;   
}
 
int solveKTUtil(int x, int y, int movei, int sol[N][N], 
                int xMove[], int yMove[])
{
    int k, next_x, next_y; // 경우의 수, 다음 xy좌표 선언
    if (movei == N*N) // 전체 맵을 돌았으면
    {
        return 1; // 탐색 종료
    }
 
    for (k = 0; k < 8; k++) // 나이트가 갈 수 있는 각 경우에 대해
    {
        next_x = x + xMove[k];
        next_y = y + yMove[k];
        if (isSafe(next_x, next_y, sol)) // 갈 수 있다면
        {
            sol[next_x][next_y] = movei; // 다음 좌표로 지정
            if (solveKTUtil(next_x, next_y, movei + 1, sol,
                            xMove, yMove) == 1)
            { // 이후에도 문제가 없으면
                return 1; // 이전 단계에 문제 없음을 반환
            }
            else // 이후에 문제가 발생하면
            {
                sol[next_x][next_y] = -1; // backtracking
            }
        }
    }
    return 0; // 이번 탐색의 모든 경우에 대해 답이 없음을 반환
}
 
int main()
{
    solveKT();
    return 0;
}

결국 backtracking 알고리즘을 구현하는 코드는 다음 순서로 진행된다.

1. 그리고 조건을 검사하는 함수와 출력 함수를 정의한다.
2. 메인 함수를 선언한 뒤 모든 조건들을 정의한다. 그리고 초기 조건을 설정하여 재귀 탐색을 시작한다.
3. 마지막으로 재귀함수를 선언하며 재귀 함수의 목적은 이전 단계의 탐색을 성공하여 현재 단계의 경우의 수를 시도하는 함수이므로 현재 단계가 시도할 수 있는 가지 수를 모두 적용한 뒤 제한 요건에 위배되지 않는 경우 다음 단계를 탐색하도록 재귀함수를 구성한다. 그리고 이후 단계에서 결과가 나오지 않아 회귀된 경우 backtracking을 하여 다음 경우의 수를 대입한다. 그리고 마지막으로 False를 반환하여 모든 경우의 수를 대입했음에도 답이 없었음을 반환한다.

참고자료

1. The Knight’s tour problem | Backtracking-1