파이썬, N Queen 퀸 배치 경우 수 구하는 백트래킹 예제

파이썬, N Queen 퀸 배치 경우 수 구하는 백트래킹 예제 

 

글. 오상문 sualchi@daum.net

 

백트래킹은 모든 경우를 검사하다가 더 이상 할 필요가 없으면 그 아래는 생략하고 다음 경우를 검사하는 방법이므로,

전수 조사보다 훨씬 빠른 알고리즘을 구현할 수 있습니다.

 

N개 퀸(여왕)을 보드(M*N크기)에 배치할 때, 각 퀸은 다음 조건을 만족해야 합니다. 

 

(1) 같은 줄에 다른 퀸이 없어야 한다.

(2) 같은 칸에 다른 퀸이 없어야 한다.

(3) 대각선 칸에 다른 퀸이 없어야 한다. 

 

N Queen 백트래킹 예제 코드는 다음과 같습니다.

xx = [None]*16  # 퀸이 존재하는 칸 저장 (최대 15)
yy = [None]*16  # 퀸이 존재하는 줄 저장 (최대 15) 

def go(y, x):
    # 백트래킹 가지치기
    for i in range(y):
        if y == yy[i]: return 0 # 같은 줄에 있으면 그냥 돌아감
        if x == xx[i]: return 0 # 같은 칸에 있으면 그냥 돌아감 
        if abs(x-xx[i]) == abs(y-yy[i]): return 0 # 대각선에 있으면 그냥 돌아감

 
    if y == N-1:   # 끝 줄까지 배치가 되었으면 1 반환 
        return 1

    yy[y] = y   # 퀸 y 위치 저장 
    xx[y] = x   # 퀸 x 위치 저장 

    rr = 0  # 가능한 경우 수 
    for i in range(N):      # 아래 줄의 모든 칸 검사 
        rr += go(y+1, i)

    return rr

# -------------- main ---------------------- 
N = int(input())   # N : 2~15, 퀸 숫자 
r = 0  # 퀸 배치 가능한 경우 수

for i in range(N):
    r += go(0, i)  # 첫줄 모든 칸 검사

print(r)

 

<이상>