백트래킹(backtracking)이란 해를 찾는 도중 해가 될 가능성이 없다면, 되돌아가서 다시 해를 찾는 기법이다.

유망성 판단

어떤 노드의 유망성을 점검한 후 유망하지 않다고 결정되면
그 노드의 부모로 되돌아가 (backtracking) 다음 자식 노드로 간다.

• 유망하다 (promising)
  어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 있으면 유망하다고 한다.
• 가지치기 (pruning)
  유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.

글로만 보면 어렵게 느껴질 수 있으나, 사실 내용은 별거없다.
DFS로 탐색 중 if문으로 조건을 걸어 이미 해가 아닌 경우라면 더 이상 탐색하지 않고 돌아가는 것이다.

깊이 우선 탐색 (DFS)

백트래킹은 보통 DFS로 진행하며, 모든 경우의 수를 완전 탐색하며 답이 될수 없는 경로는 탐색을 중단한 후 이전단계로 돌아간다.

그렇기에 최악의 경우에는 완전 탐색과 비슷한 시간 복잡도를 가질 수 있다.

N-Queen

8 퀸 문제로도 유명한 문제이다.
8x8크기의 체스판에 퀸을 8개 배치하는 문제로 퀸이 서로를 공격하지 않도록 배치해야 한다.

N-Queen
이 문제는 8 퀸 문제와 마찬가지로 N x N 체스판에 퀸 N개를 배치하는 경우의 수를 찾아야 한다.

N이 8일 경우 전체 경우의 수는 64C8 = 44억개이며
시간제한이 10초지만 평범한 완전 탐색으로는 시간 안에 풀 수 없다.