N-Queen

문제 링크

• 크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수
• 조건
  - 퀸이 놓였을 때 퀸 자신을 기준으로 가로, 세로, 대각선 방향에 아무것도 놓여있으면 안된다.

백트래킹

• 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 감.
• 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.
• 가지치기(prunning): 유망하지 않는 노드가 포함된 경로는 더 이상 고려하지 않는다.

백트래킹(Backtracking) vs 깊이 우선 탐색

• 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다.
• 깊이 우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단한다.
• 깊이 우선 탐색을 가하기에는 경우의 수가 너무나 많다.

일반 백트래킹 알고리즘

checknode(node v)
	if promising(v):
    	if there is a solution at v
        	write the solution
        else
        	for each child u of v
            	checknode(u)

N-Queen

체스판을 배열로 표시해보면
0번째 행 -> 2번째 열
1번째 행 -> 0번째 열
2번째 행 -> 3번째 열
3번째 행 -> 1번째 열이므로 [2, 0, 3, 1]로 표현할 수 있다.

이와 같은 방식으로 표현한다고 했을 때

1. 배열 안에 같은 수가 들어간다면 같은 열에 있다는 뜻이므로, 모두 다른 수가 들어가야 한다. (ex. [2, 0, 2, 1]은 불가능)

2. 행 번호의 차이가 열 번호의 차이와 같다면 같은 대각선 상에 있다는 뜻이므로, 유망하지 않다. (ex. [2, 0, 1, 3]에서 (1, 0)과 (2, 1)은 같은 대각선에 있으므로 불가능)

이 솔루션을 바탕으로 코드를 작성하면,

def nqueen(queen, n, row):
    count = 0
    
    if n == row:
        return 1
    
    # 가로로 한번만 진행
    for col in range(n):
        queen[row] = col
        
        # 앞의 것과 비교
        for x in range(row):
            if queen[x] == queen[row]:
                break
            if abs(queen[x]-queen[row]) == row-x:
                break
        else:
            count += nqueen(queen, n, row+1)
    return count

def solution(n):
    queen = [0] * n
    return nqueen(queen, n, 0)