Knight Tour Problem

체스판에서 나이트(Knight)가 임의의 한 위치에서 출발하여 체스판의 모든 지점을 한 번씩 방문하는 것을 Knight Tour 문제라고 한다. 엄청나게 많은 경로의 가지수가 있지만, 여기서는 한 종류의 패스를 완성하는 문제를 생각해보자.

이 문제는 폭우선 검색에서 사용한 색구분이 있는 꼭지점을 사용하는 그래프를 이용한다. 패스를 생성하는 함수는 재귀적으로 현재 노드에서 다음 노드를 선택해나간다. 따라서 다음 기능을 포함하면 된다.

1. 일단 현재 노드를 회색으로 칠하고 지나온 패스리스트에 추가한다.
2. 패스의 크기가 모든 지점의 개수와 같으면 모든 점을 방문한 셈이므로 True를 리턴하고 종료한다.(재귀 호출의 base case다)
3. 매 호출 시 현재 노드에서 방문 가능한 노드를 나열하고, 그 중 흰색이 노드가 다음 후보가 된다. 후보에 대해 재귀호출을 수행한다.
4. 3에서 만약 모든 후보가 회색이거나(다음번 갈 곳이 없음), 재귀 호출이 False를 리턴했다면 데드엔드이므로 현재 노드를 흰색으로 되돌리고 패스에서 뺀 후, False를 리턴한다.
5. 만약 3에서 True가 리턴된다면 다른 노드를 탐색할 필요가 없으므로 바로 True를 리턴해준다.

나이트 투어는 깊이 우선 검색의 일종이다. 현재 위치에서 가능한 이후 진로를 모두 펼치지 않고 하나의 노드를 선택한 후 갈 수 있는 한 깊이 내려가는 것이다.
일단 보드의 크기를 가변적으로 쓸 수 있게 전역변수에 할당하자.

boardSize = 8

또한 각 vertex는 좌표 정보를 가지고 있는데, 간단히 키를 좌표에 대입하기 위해서 튜플 타입의 데이터를 문자열로 상호 변환하는 두 개의 변환함수가 필요하다.

## convert tuple to string
def tuple2key(t):
    return ",".join([str(i) for i in t])
## key string to tuple (<int>, <int>)
def key2tuple(k):
    return tuple([int(i) for i in k.split(',')])

그래프를 만드는 방법은 다음과 같다. 모든 좌표에 대해서, 각 좌표에서 나이트가 갈 수 있는 좌표의 대상을 구해서, 두 좌표를 잇는 edge를 그래프에 추가한다.

def buildChessGraph():
    g = BFSGraph()
    for row in range(boardSize):
        for col in range(boardSize):
            s = (row, col)
            for n in makeNextMoves(s):
                g.addEdge(tuple2key(s), tuple2key(n), weight=1)
    return g
def makeNextMoves(t):
    x, y = t
    res = []
    offsets = ((1, 2), (2, 1), (-1, 2), (2, -1),
               (1, -2), (-2, 1), (-1, -2), (-2, -1))
    for offset in offsets:
        nx = (offset[0] + x, offset[1] + y)
        if isLegalMove(nx):
            res.append(nx)
    return res
def isLegalMove(coords):
    x, y = coords
    return (x >= 0 and x < boardSize) and (y >= 0 and y < boardSize)

그래프가 완성되면 투어를 떠나는 함수를 다음과 같이 작성할 수 있다.

def runTour(v, path=None, limit=0):
    done = False
    if limit == 0:
        limit = boardSize ** 2
    if path is None:
        path = []
    path.append(v)
    v.setColor('grey')
    if len(path) == limit:
        return True
    for i in v.getNeighbors():
        if i.getColor() == 'white':
            done = runTour(i, path, limit=limit)
        if done:
            return done
    if not done:
        path[-1].setColor('white')
        path.pop()
    return done

만약 보드 크기를 5로 잡는다면 금방 답이 나올 것이다. (운이 좋다면 1초 이내) 하지만, 보드 크기가 6이상이되면 상당히 오랜 시간이 걸린다. 이 문제에 대해서는 다음과 같은 방법으로 성능을 향상 시킬 수 있다.
특정 노드에서 다음 노드로 진행한 후 데드엔드를 만나면 되돌아오게 되는데, 조금이라도 빠른 성능을 원한다면 다음 노드에서 갈 수 있는 후보의 수가 적은 것을 먼저 방문하는 것이 낫다. (그만큼 하위에서 데드엔드나 종착지를 빠르게 만날 수 있다.) 언뜻 생각하기에 이는 좀 말이 안되는 것 같아 보이는데 확실히 효과가 있다. 위 함수의 재귀 호출 루프 부분을 다음과 같이 수정해보자.

nexts = sorted([k for k in v.getNeighbors() if k.getColor() == 'white'],
               key=lambda x: len(x.getNeighbors()))
for i in nexts:
    if i.getColor() == 'white':
        done = runTour(i, path, limit=limit)
    if done:
        return done

단 한줄의 코드를 추가하여 다음 이동 노드의 경우의 수가 적은 쪽으로 유도해주기만하는 것으로도 엄청난 성능의 증가를 볼 수 있다. (8X8 크기의 보드에서도 1초 이내에 답이 나온다)
이상의 코드를 테스트할 수 있는 함수는 다음과 같다.

def main():
    g = buildChessGraph()
    s = g['4,4']
    path = []
    if runTour(s, path):
        print('tour completed.')
    else:
        print('tour failed.')

결과를 시각적으로 표현하기 위해서 다음의 코드를 추가로 작성해 보았다.

LINE = 50
OFFSETS = (-200, 200)
def drawResult(path):
    import turtle
    t = turtle.Turtle()
    s = turtle.Screen()
    t.up()
    t.goto(-200, 200)
    t.down()
    # 테두리를 그린다.
    for i in range(4):
        t.forward(LINE*BDSize)
        t.right(90)
    t.right(90)
    # 가로 선을 그린다.
    for i in range(1, BDSize):
        t.up()
        t.goto(OFFSETS[0] + LINE*i, OFFSETS[1])
        t.down()
        t.forward(LINE*BDSize)
    #세로선을 그린다.
    t.left(90)
    for i in range(1, BDSize):
        t.up()
        t.goto(OFFSETS[0], OFFSETS[1] - LINE*i)
        t.down()
        t.forward(LINE*BDSize)
    # 특정 칸으로 이동하는 궤적을 그리기
    def moveTo(a, l=1):
        if l==0:
            t.up()
        else:
            t.down()
        x, y = key2tuple(a.key)
        t.goto(LINE * x + LINE/2 + OFFSETS[0],  (LINE * y + LINE/2) * -1 + OFFSETS[1])
    전체 패스를 그린다.
    moveTo(path[0], 0)
    for i in path[1:]:
        moveTo(i)
    s.exitonclick()

아래는 위에서 소개하지 않는 그래프 관련 코드를 포함한 전체 코드이다.