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))



조회수 582


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([])

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

  • 2016년 03월 13일에 작성됨
    루비와 파이썬을 좋아합니다. 새로운 언어를 배우는것도 좋아해요. 모바일 게임도 조금 만들어 봤습니다.

  • 감사합니다.    Sizz Flair   2016.3.13 11:08     

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에 있는지를 알려주는거라고 하네요.

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

출처

  • 2016년 06월 01일에 수정됨
    루비와 파이썬을 좋아합니다. 새로운 언어를 배우는것도 좋아해요. 모바일 게임도 조금 만들어 봤습니다.
  • 2016년 03월 13일에 작성됨
    루비와 파이썬을 좋아합니다. 새로운 언어를 배우는것도 좋아해요. 모바일 게임도 조금 만들어 봤습니다.

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close