백트래킹과 n-Queens

되추적(backtracking)

• 임의의 집합(set)에서 주어진 기준대로
  - 원소의 순서(sequence)를 선택하는 문제를 푸는 데 적합
• 트리 자료구조의 변형된 깊이 우선 탐색(DFS:depth-first-search)
• 모든 문제 사례에 대해서 효율적이지 않지만,
  - 많은 문제 사례에 대해서 효율적이다.
  • 예) n-Queens,부분집합의 합, 0-1, 배낭문제 etc

상태공간트리(State Space Tree)

• 상태 공간: 해답을 탐색하기 위한 탐색 공간
• 상태공간트리: 탐색 공간을 트리 형태의 구조로 암묵적으로 해석

백트래킹 기법

• 상태공간트리를 깊이우선탐색으로 탐색
  - 전체 탐색: 브루스 포드
• 방문 중인 노드에서 더 하위노드로 가면 해답이 없을 경우
  - 해당 노드의 하위 트리를 방문하지 않고 부모 노드로 되돌아 감
  -> 효율적!
  

유망함(promising)

• 방문 중인 노드에서 하위 노드가 해답을 발견할 가능성이 있으면 유망(promising)
• 하위 노드에서 해답을 발견할 가능성이 없으면 유망하지 않음(nonpromising)

백트래킹과 가지치기(pruning)

• 백트래킹: 상태공간트리를 DFS로 탐색
• 방문 중인 노드가 유망한지 체크
• 만약 유망하지 않으면, 부모 노드로 되돌아감(backtrack)

가지치기(pruning)

• 유망하지 않으면 하위 트리를 가지치기함
• 가지치기한 상태: 방문한 노드의 방문하지 않는 하위 트리(pruned state)

일반적인 백트래킹 알고리즘

checknode(node v):
	node u
    if (promising(v))
    	if (v에 해답이 있으면):
        	해답을 출력
        else:
        	for(v의 모든 자식 노드 u에 대해서):
            	checknode(u)

백트래킹 알고리즘의 구현

• 상태공간트리를 실제로 구현할 필요는 없음
• 현재 조사중인 가지의 값에 대해 추적만 하면됨
• 상태공간트리는 암묵적으로 존재한다고 이해하면됨

n-Queens 문제

• 8-Queens 문제의 일반화된 문제
• n x n 체스보드에 n개의 퀸을 배치하는 문제
  - 어떤 퀸도 다른 퀸에 의해서 잡아먹히지 않도록 배치해야 함
  • 즉, 같은 행, 열, 대각선에는 다른 퀸을 놓을 수 없음

백트래킹으로 문제 해결:

• 임의의 집합에서 기준에 따라 원소의 순서를 선택

• 임의의 집합(set): 체스보드에 있는 n^2개의 가능한 위치

• 기준(criterion): 새로 놓을 퀸이 다른 퀸을 위협할 수 없음

• 원소의 순서(sequence): 퀸을 놓을 수 있는 n개의 위치

4-Queens 문제

• 4개의 퀸 4x4 체스보드에 배치
  - 일단 기본 가정으로 같은 행에는 놓을 수 없다고 두자
• 후보 해답: 4x4x4x4=256가지의 탐색 공간이 있음
  

prune을 어떻게 할래?

promising 하다는 것을 어떻게 알까?

이런 경우 아래 가지를 가지치기하기
(3,1) (3,2) (3,4) 하지 않기

n-Queens의 문제 해결

• 기본 가정: 같은 행에는 퀸을 놓지 않는다.
• 유망 함수의 구현
  - 같은 열이나 같은 대각에 놓이는 지를 확인
  • 대각선 체크:
  • 왼쪽에서 위협하는 퀸에 대해서:
    • 열에서의 차이 == 행에서의 차이
  • 오른쪽에서 위협하는 퀸에 대해서
    • 열에서의 차이 == 행에서의 차이의 마이너스

def n_queens (i, col):
	n = len(col) - 1
    if (promising(i, col)):
    	if (i == n):
        	print(col[1: n+1])
        else:
        	for j in range(1, n+1):
            	col[i + 1] = j
                n_queens(i+1, col)
                
def promising (i, col):
	k = 1
    flag = True
    while(k<i and flag):
    	if(col[i] == col[k] or abs(col[i] - col[k]) == (i-k)):
        	flag = False
         k += 1
     return flag
     
n = 4
col = [0] * (n+1)
n_queens(0,col)