• 모든 조합에서 나올 수 있는 해를 다 살펴본다 → 조건이 만족할 때만
• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
  • DFS 등으로 모든 경우의 수를 탐색
  • 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의
  • 그러한 상황일 경우에는 탐색을 중지
  • 그 이전으로 돌아가서 다시 다른 경우를 탐색
• 가지치기 → 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다
  • 유망성(Promising) : 가망이 있는가 없는가를 따지는 기준
  • 가지치기(Pruning) : 유망성을 따져보고, 유망하지 않는 경우의 수는 배제하는 것

한정 함수(Bounding Function)

• 현재 만들어진 해의 집합이 해답의 조건을 만족하는지 검사하는 함수
• **'특정조건(유망성)'**을 따지는 함수
• 가지치기를 위함

N-Queens

N * N 체스 판에서 N개의 Queen을 서로 같은 행, 열, 대각선 위에 오지 않도록 배치.

K행에 배치된 Queen의 열 번호를 $x_k$라고 하면 결국 $(x_1, x_2, ..., x_n)$을 찾는 것과 동일

• 첫 번째 행부터 차례대로 퀸을 하나씩 배치하는 것
• x[k] 는 k번째 행에 놓일 퀸의 열 번호를 의미
• 한계 함수 B 는 (k, x[k]) 에 이미 놓인 (k-1)개와 조건을 만족하는지 점검하는 함수로 정의
  • 1행부터 (k-1) 행까지 놓인 Queens과 충돌이 없어야 함

# pseudo code
def NQueens(k):    # x[k]를 결정
	if k >= N: return # 모든 x[k]가 결정 됨.
	for col in range(N):
		if queen can place at (k,c):    # x[k]에 놓을 수 있는가? -> 한계함수
				x[k] = c
				NQueens(k + 1)

1) N개의 퀸을 배치해야하므로 무조건 모든 행에 퀸이 들어가야한다.

2) 따라서 0열부터 N-1열까지 퀸을 놓는 방법을 for문을 통해 돌린다.

3) 유망한지(이전의 열로 인해 영향을 받는지) 검사하는 함수를 통해 유망함수만을 걸러준다.