역추적을 적용하는 알고리즘의 한 가지 예를 살펴보자.

n-퀸 문제 n × n 체스판에 n개의 퀸을 배치하되 두 퀸이 서로 공격할 수 없도록 배치하라. 퀸은 같은 행, 같은 열, 또는 대각선 방향에 있으면 공격할 수 있다.

n = 1일 때는 그냥 하나뿐인 자리에 퀸을 배치하면 된다. n = 2, n = 3일 때는 해가 없다. 이제 n = 4인 경우에 대해 풀어야 하는데 역추적 방법으로 풀어보자. 네 개의 퀸은 서로 다른 열에 배치해야 할 텐데 그림 1-2에 있는 것과 같은 체스판에 네 개의 퀸을 각각 어느 열에 배치해야 할지 따져보자.

▲ 그림 1-2 4-퀸 문제에 해당하는 체스판