되추적

• 임의의 집합 에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는 데 적합
• 트리 자료구조의 변형된 깊이우선탐색!
• n-Queens, 부분집합의 합, 0-1 배낭문제, etc.
  백트래킹에는 항상 상태공간트리가 있음
  상태공간 : 해답을 탐색하기 위한 탐색 공간
  상태공간트리 : 탐색 공간을 트리 형태의 구조로 '암묵적'으로 해석
  -> 실제 트리를 구현할 필요는 없음

백트래킹 기법

상태공간트리를 깊이우선탐색으로 탐색!

• Brute Force : 전체 탐색
• Backtracking : 방문 중인 노드에서 더 하위 노드로 가면 해답이 없을 경우, 해당 노드의 하위 트리를 방문하지 않고 부모 노드로 되돌아감

유망함 : 방문 중인 노드에서 하위 노드가 해답을 발견할 가능성이 있음
망함 : 방문 중인 노드에서 하위 노드가 해답을 발견할 가능성이 없음

가지치기(pruning)

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

ex)

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

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

n-Queens 문제

https://www.acmicpc.net/problem/9663

• 8-Queens(n=8) 문제의 일반화된 문제
• n x n 체스보드에 n개의 퀸을 배치하는 문제! (어떤 퀸도 다른 퀸에 의해서 잡아먹히지 않도록 배치해야 함)
  임의의 집합 : 체스보드에 있는 n^2개의 가능한 위치
  기준 : 새로 놓은 퀸이 다른 퀸을 위협할 수 없음
  원소의 순서 : 퀸을 놓을 수 있는 n개의 위치
  ex) (1, 1) -> (2, 1) and (2, 2)는 non-promising, 백트래킹 -> (2, 3) -> etc...

유망의 조건

• 같은 행에 퀸이 이미 존재하면 안됨
• 같은 열에 퀸이 이미 존재하면 안됨
• 대각선에 퀸이 이미 존재하면 안됨
  -> if abs(col[a] - col[b]) == abs(a - b), 대각선에 이미 퀸이 존재하는 것임!

n = int(input())
ans = 0
row = [0] * n

def promising (x) :
    for i in range(x) :
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x-i) :
            return False
    return True

def n_queens (x) :
    global ans
    if x == n:
        ans += 1
        return
    else :
        for i in range(n) :
            row[x] = i
            if promising(x) :
                n_queens(x+1)
                
n_queens(0)
print(ans)