재귀응용3 ---- N-Queens (with Python)

 

내가 지나온 어느 결정들이 막다른 길이 보이면 내가 가장 최근에 내린 경로를 따라 가는 것이 back- tracking이다. 

오늘 풀어볼 문제는 N-Queen이라고 해서 이 백트레킹알고리즘을 사용하여 해결할 것이다. 

문제는 이렇다.

n*n 체스판에  n개의 말을 놓는데  그 어떤 두 말도 동일한 행이나 열 대각선에 위치하지 않게 하는 문제다.

 

일단 하나씩 해결해보자 

 

첫번째 말을 첫번째 행 중 하나 놓는다면 그 행과 열 대각선은 앉지 못한다.

계속해서 두번째 말을 실패하지 않는 경우에 계속해서 놨지만 결과적으로 더 이상 퀸을 체스판에 놓지못할 때 가장 최근의 경우의 수로 번복하여 새로 경우의 수를 둘 것이다.

 

그렇게 계속 두다가 첫번째 말이 첫 번째 행 모두를 뒀지만 만약 모든 경우가 막혔다면. 첫번째 행에 뒀던 경우를 번복하고 두번째 행으로 옮겨지는 경우도 생길 수 있다. 

 

다시 말해. 첫번째에 말했던 것과 같이 계속해서 체스를 두다가 실패하면 가장 최근의 둔 퀸을 번복하여 다른 경우의 수를 접근한다는 것이다.  

조금 더 이해하기 쉽게 상태공간 트리를 사용하겠다

4*4 체스판에 4개의 퀸을 둔다면 맨처음 시작에서 1번쨰 말이 (1,1) 위치에 존재한다면 ,(1,2)에 존재한다면 하는 모든 경우의 수를 트리로 표현한 것이다. 

 

그렇다고 상태공간 트리 모든 노드를 탐색한다는 것이 아니라 non- promising (실패노드) 를  만났다면 다시 최근에 존재하는 1,1 의 노드로 돌아가 2,2를 시행하는 것이다. 2,2가 또다시 실패했다면 2,3으로 가서 노드를 생성하는 것이 

바로 백트레킹이다.  

 

그렇게 찾다보면 결국에 우리가 원하는 해를 찾을 수 있다.  

 

이러한 정도의 알고리즘을 코드로 작성할 떄 가장 널리쓰이는 코드의 구조는 이러하다 

1. 매개 변수를 받아 상태공간 트리에서 어디에 도착했는지에 저장한다. 

2. 도착한 노드에 제일 먼저 promising한지 확인해본다. 

3. 실패한다면 ? 적절하게 실패 혹은 return으로 되돌아간다.

4. 가능하다면 ? 해당하는 조치를 하거나 return으로 돌아간다.

5. 내가 방문한 노드가 꽝고 성공도 아니라면? 이노드의 자식노드들을 하나씩 방문해보는 것이다. 

 

그럼 어떻게 매개변수를 보내고 어떤 매개변수를 받을지 설계를 해야하는데,,,, 

1. 현재 나의 위치를 확인할 수 있는 노드의 위치를 알아야한다.

2. 그리고 방문한 노드인지에 대한 정보를 전달해야한다.

다음의 경우 전역변수 혹은 매개변수를 통해 전달할 수 있다. 상황에 따라 잘 골라서 사용하면 된다 

 

def nqueen(sol, N):
    global count
    if len(sol) == N:  
        count += 1
        print(count, sol)
        return 0
    candidate = list(range(N))    
    for i in range(len(sol)):
        if sol[i] in candidate:  
            candidate.remove(sol[i])    
        distance = len(sol) - i     
        if sol[i] + distance in candidate:    
            candidate.remove(sol[i] + distance)       
        if sol[i] - distance in candidate:    
            candidate.remove(sol[i] - distance)      
    if candidate != []:
        for i in candidate:
            sol.append(i)   
            nqueen(sol, N)    
            sol.pop()
    else:    
        return 0 

count = 0
num = int(input())
for i in range(num):
    nqueen([i], num)
if count == 0:
    print("-1")

 

 

참고 코드 블로그) https://codepractice.tistory.com/82

N-queens 문제

참고이미지)https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C

여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전