Eight Queens 문제 코드 중 재귀호출...
조회수 2319회
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 답변
-
재귀함수로 풀고 싶어 하시는것 같아서 재귀함수로 풀어 봤습니다.
하나의 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에 있는지를 알려주는거라고 하네요.
선공유 후공부. 왜 이게 되는지 공부좀 해 봐야겠네요. 파이썬스럽게 답이 짧게 나오는군요.
댓글 입력