[알고리즘] 백트래킹(Backtracking) | C언어 N-Queen구현

백트래킹이란? 백트래킹(Backtracking) 은 해를 찾는 도중 해가 아니어서 막힌다면, 되돌아가서 다시 해를 찾아가는 기법이다.

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더이상 가지 않고 되돌아간다. 이것을 가지치기(Pruning) 이라고 한다.

즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다. 해가 될 가능성이 있다면 유망하다(promising)고 한다.

N-Queen 문제 N-Queen 문제는 N X N 크기의 체스판에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 문제이다. 이 때 퀸은 상하좌우, 대각선 방향으로 체스판의 끝까지 공격을 할 수 있다.

따라서 아래 그림처럼 직선, 대각선 상에는 퀸을 배치 할 수 .....