일단 비어 있는 체스판에서 시작해 첫 번째 퀸을 첫 번째 위치, 1행 1열에 놓는 것부터 시작해보자. 그다음에 두 번째 퀸을 놓을 자리를 따져보면 2열의 1행이나 2행에는 놓을 수 없으므로 맨 먼저 시도해볼 만한 위치는 3행 2열, 즉 (3, 2) 위치다. 하지만 이렇게 놓고 나면 3열에 세 번째 퀸을 놓을 자리가 없다. 이제 역추적해 돌아가 두 번째 퀸을 가능한 다음 위치인 (4, 2)에 배치해보자. 그러면 세 번째 퀸을 (2, 3)에 놓을 수밖에 없는데 여기도 막다른 골목이다. 결국 첫 번째 퀸을 놓는 단계까지 역추적해 돌아가 첫 번째 퀸을 (2, 1)에 놓아야 한다. 그러면 두 번째 퀸은 (4, 2) 위치로, 세 번째 퀸은 (1, 3) 위치로, 네 번째 퀸은 (3, 4) 위치로 갈 수 있고 이것은 정답이 된다. 지금까지 거쳐온 검색 과정에 대한 상태 공간 트리는 그림 1-3과 같이 그릴 수 있다.

▲ 그림 1-3 역추적 알고리즘으로 4-퀸 문제를 푸는 과정에 대한 상태 공간 트리. X는 주어진 행에 퀸을 놓을 수 없는 경우를 나타낸다. 노드 위에 적힌 알파벳은 노드가 생성된 순서를 뜻한다.