N-queens 문제

체스에서 여왕(queen) 은 가로, 세로, 대각선으로 움직이며 상대를 공격할 수 있다. N-queens 문제는 $N \times N$ 크기의 체스판에 $N$ 개의 여왕을 서로 서로 공격하지 못하도록 배치하는 법을 찾아내는 문제이다. 예를 들어, $N=4$ 일 때는 다음과 같이 $4$ 개의 여왕을 배치하면 된다. 

즉, 어떤 두 개의 여왕도 같은 행, 같은 열, 같은 대각선 상에 놓이지 않도록 $N$ 개의 여왕을 배치하는 문제이다.

이 문제를 풀기 위해서는 위와 같은 배치를 표현하는 방법을 정의해야 한다. 이를 위해서 크기가 $N$ 인 배열을 만들고, 배열의 $i$ 번째 요소가 $i$ 번째 행에 놓이는 여왕의 열 위치를 나타내도록 표현하면 된다. 위의 해법을 이런 배열로 표현하면 (2, 0, 3, 1) 이 된다. 각 행과 열에 쓰이는 index $i$ 는 다음과 같이 정의한다. 

즉 0행에는 2열에 여왕이 놓이고, 1행에는 0열에 여왕이 놓이며, 2행에는 3열에, 3행에는 1열에 여왕이 놓이게 된다는 것을 표현하면 (2, 0, 3, 1) 이 되는 것이다. 이와 같은 배열을 정답 배열이라고 부르자.

이제 우리는 정답 배열의 첫 번째 요소를 0, 1, 2, 3 으로 변화시키면서 조건을 만족시키는 정답 배열을 만들어 갈 것이다. 여기서 조건은 같은 열이나 같은 대각선 상에 여왕이 놓이면 안되다는 것인데, 이는 다음과 같은 방법으로 체크할 수 있다.

1) 같은 열에 놓이지 않게 하는 방법

정답 배열의 $i$ 번째 요소에는 $j$  $(j=0, \;1,\; \cdots, \;  i-1)$  번째 요소와 똑같은 숫자가 올 수 없다. 따라서 똑같은 숫자는 $i$ 번째 요소의 후보군에서 제외한다.

2) 같은 대각선 상에 놓이지 않게 하는 방법

정답 배열의 $i$ 번째 요소와 $j$  $(j=0, \; 1,\; \cdots, i-1)$번째 요소의 차가 $|i-j|$ 과 같다면 같은 대각선 상에 있는 것과 같다. 따라서 $j$ 번째 요소를 $i$ 번째 요소의 후보군에서 제외한다.

이렇게 만들어진 $i$ 번째 요소의 후보군을 $i$ 번째 요소에 대입하면서 다시 $i+1$ 번째 후보군을 찾는다. 이를 위해서 재귀적 용법이 사용된다j. 위와 같은 과정을 정답 배열의 길이 (요소의 개수)가 $N$ 과 같아질 때까지 반복한다. 

위 과정을 파이썬 코드로 표현하면 다음과 같다.

def nqueen(sol, N):
    global count
    if len(sol) == N:    # 정답 배열(sol)의 길이가 N과 같아지면 sol 을 프린트한다.
        count += 1
        print(count, sol)
        return 0
    candidate = list(range(N))    # 0 부터 N-1 까지로 구성된 후보군(cadidate) 배열을 만든다.
    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)    # 후보군의 요소를 정답 배열의 i+1 번째 요소로 설정
            nqueen(sol, N)    # 재귀적으로 다음 후보군 체크 
            sol.pop()
    else:    
        return 0 

count = 0
num = int(input("Input N : "))
for i in range(num):
    nqueen([i], num)
if count == 0:
    print("No solution")

다음은 $N=2, \; N=4, \; N=5$ 에 대한 실행 결과이다.

JKMBP:python jk$ python nqueen.py
Input N :  2
No solution
JKMBP:python jk$ python nqueen.py
Input N : 4
1 [1, 3, 0, 2]
2 [2, 0, 3, 1]
JKMBP:python jk$ python nqueen.py
Input N : 5
1 [0, 2, 4, 1, 3]
2 [0, 3, 1, 4, 2]
3 [1, 3, 0, 2, 4]
4 [1, 4, 2, 0, 3]
5 [2, 0, 3, 1, 4]
6 [2, 4, 1, 3, 0]
7 [3, 0, 2, 4, 1]
8 [3, 1, 4, 2, 0]
9 [4, 1, 3, 0, 2]
10 [4, 2, 0, 3, 1]