Knight’s Tour Problem(임시_)

Knight’s Tour Problem

Knight’s Tour Problem is a problem where we have to find a path for a knight to visit all the cells of a chessboard without visiting any cell twice.

기사 투어 문제는 기사가 체스판의 모든 칸을 두 번 방문하지 않고 모든 칸을 방문할 수 있는 경로를 찾아야 하는 문제입니다.

 

 

Knight's Tour Problem은 그래프 이론에서 흔히 나오는 문제로, 기사가 이동할 수 있는 8개의 방향 중 어떤 방향으로 움직여야 체스판의 모든 칸을 한 번씩만 방문할 수 있는지를 찾는 문제입니다. 이를 해결하기 위해서는 깊이 우선 탐색(DFS)이나 휴리스틱 등 다양한 방법을 사용할 수 있습니다.

 

 

In Python

def knight_tour(n, start):
    # 기사가 이동할 수 있는 8가지 방향 정의
    dx = [2, 1, -1, -2, -2, -1, 1, 2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]
    
    # 체스판 초기화. 방문하지 않은 칸은 -1로 표시
    board = [[-1]*n for _ in range(n)]
    # 시작 위치를 0으로 설정
    board[start[0]][start[1]] = 0
    
    # 주어진 위치 (x, y)가 체스판 내에 있는지, 아직 방문하지 않은 칸인지 확인하는 함수
    def is_valid(x, y):
        if x<0 or y<0 or x>=n or y>=n:
            return False
        if board[x][y] != -1:
            return False
        return True
    
    def solve(x, y, move):
        # 모든 칸을 방문했다면 True를 반환
        if move == n*n:
            return True
        # 8가지 방향에 대해 각각 시도
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            # 이동하려는 칸이 유효하다면
            if is_valid(nx, ny):
                # 이동하려는 칸에 현재 움직임 횟수를 기록
                board[nx][ny] = move
                # 다음 칸으로 이동
                if solve(nx, ny, move+1):
                    return True
                # 만약 다음 칸으로 이동했을 때 해결이 불가능하다면, 현재 칸을 다시 -1로 변경 (백트래킹)
                board[nx][ny] = -1
        # 8가지 방향 모두를 시도했는데 해결이 불가능하다면, False를 반환
        return False
    
    # 체스판의 시작 위치에서 Knight's Tour를 시작
    if solve(start[0], start[1], 1):
        for row in board:
            print(' '.join(str(cell) for cell in row))
    else:
        print('No solution found.')

 

 

 

답이 잘 나오는데

 

원래 체스판인 8*8 에 0,1 위치에 시작해보니..

 

흠.. 차후 추가

 

이상해요..