Eight Queens 문제 코드 중 재귀호출...

Eight Queens 문제를 파이썬 3.5.1로 풀어보고 있는데요... 답은 92인데 29가 나옵니다. 알고리즘 상으로는 문제가 없는 것 같은데, 뭐가 문제일까요? 가장 윗 줄 부터 놓은 뒤 재귀호출 하여 아랫줄에 놓을 수 있는 경우를 찾아 반복하는 방식입니다.

global count
count = 0

def locate(b, co):
    br = b[:]
    y, x = (co[0], co[1])
    if br[y][x] == 1:
        return br
    else:
        for i in range(8):
            br[i][x] = 1
            br[y][i] = 1
            for i in range(min(x,7-y)):br[y+i+1][x-i-1] = 1
            for i in range(min(x,y)):br[y-i-1][x-i-1] = 1
            for i in range(min(7-x,7-y)):br[y+i+1][x+i+1] = 1
            for i in range(min(7-x,y)):br[y-i-1][x+i+1] = 1
            return br

def newbr(li = []):
    br = li[:]
    if br == []:
        for i in range(8):
            br.append([])
            for j in range(8):
                br[i].append(0)
    return br

def n0(br, y):
    tmp = []
    if len(br[y]) == 0:return tmp
    for x in range(len(br[y])):
        if br[y][x] == 0:
            tmp.append(x)
    return tmp

def cal(br, depth = 0):
    l0 = n0(br, depth)
    if depth == 7:
        counter()
        return
    for x in l0:
        print(depth, end='')
        tmp = br[:]
        tmp = locate(tmp, (depth, x))
        if len(n0(tmp, depth+1)) != 0:
            cal(tmp, depth+1)

def counter():
    global count
    count += 1

if __name__ == '__main__':
    board = newbr()
    cal(board)
    print('\n'+str(count))


2답변

  • 좋아요

    3

    싫어요
    채택취소하기

    재귀함수로 풀고 싶어 하시는것 같아서 재귀함수로 풀어 봤습니다.

    하나의 row와 하나의 column에는 두개의 queen이 올 수 없습니다. 그래서 결과는 길이 8짜리 리스트가 되는데요. 리스트의 index가 row번호, 해당 index에 있는 값이 column번호입니다. 예를들어 결과가 [0, 4, 7, 5, 2, 6, 1, 3] 이라면 (0,0)에 퀸 하나, (1,4)에 퀸 하나, (2,7)에 퀸 하나... 이렇게 배치하면 됩니다.

    코드를 작성한 로직은

    • 한 row에는 하나씩만 나와야 하니까 row를 증가시켜가면서 가능한 조합을 찾는다
    • 이미 찾은 조합에서 같은 column에 퀸이 배치되어 있으면 해당 column은 skip(코드의 7~8째줄)
    • 이미 찾은 조합과 대각선 방향에 퀸이 배치되어 있으면 해당 column은 skip(코드의 9~14째 줄). 대각선 방향에 있는지는 해당 위치와 가로길이와 세로길이가 같으면 대각선 방향이라고 봅니다. 예를들어 2,5와 3,6에 퀸이 배치되어 있으면 대각선에 있다고 볼 수 있져.
    • 조건을 만족한다면 리스트에 해당 column을 추가하고 다음 row를 찾기 위해 함수를 재귀적으로 호출합니다.(코드 15)

    이렇게 동작하는 search_8queens라는 함수에 빈 리스트를 넘겨서 돌리면 됩니다.

    def search_8queens(pos):
        current_row = len(pos)
        if current_row == 8:
            print(pos)
    
        for current_column in range(8):
            if current_column in pos:
                continue
            break_rule = False;
            for previous_row, previous_column in enumerate(pos):
                if abs(current_column - previous_column) == abs(current_row - previous_row):
                    break_rule = True
                    break
            if not break_rule:
                search_8queens(pos+[current_column])
    
    search_8queens([])
    

    실행해 보면 전에 올렸던 짧은 코드보다는 동작속도는 빠르네요.

  • 8 queens문제는 체스판에 퀸을 8개 배치해서 8개의 퀸이 서로를 공격하지 않는 상태가 되도록 만드는건데요. 퀸은 상하좌우/대각선 방향 모두 움직일 수 있기 때문에 쉽지 않아 보이는군요.

    검색해서 우선 답을 하나 찾았습니다.

    from itertools import permutations
    
    n = 8
    cols = range(n)
    for vec in permutations(cols):
        if (n == len(set(vec[i]+i for i in cols))
              == len(set(vec[i]-i for i in cols))):
            print vec 
    

    [실행하기] 눌러서 나오는 코드실행기에서 실행해보면 92개의 줄이 출력되는데, 각 row에 퀸이 몇번째 column에 있는지를 알려주는거라고 하네요.

    선공유 후공부. 왜 이게 되는지 공부좀 해 봐야겠네요. 파이썬스럽게 답이 짧게 나오는군요.

    출처

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

작성한 답변에 다른 개발자들이 댓글을 작성하거나 댓글에 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.