Page 183 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 183
05-4 8퀸 문제
이번에는 8퀸 문제에 대해 알아보겠습니다. 이 문제는 하노이의 탑과 마찬가지로 작은 문제
로 세분하여 해결합니다.
8퀸 문제란?
8퀸 문제(8-Queen problem)는 재귀 알고리즘에 대한 이해를 돕기 위한 예제로 자주 등장할
뿐만 아니라 19세기의 유명한 수학자 카를 프리드리히 가우스(C. F. Gauss)가 잘못된 해답을
낸 사실로도 잘 알려진 문제입니다. 이 문제는 아래와 같습니다. 언뜻 보면 간단한 문제처럼
보입니다.
서로 공격하여 잡을 수 없도록 8개의 퀸을 8 × 8 체스판에 놓으세요.
퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능합니다.
이 문제의 정답은 92가지의 조합입니다. 다음의 그림 5-12는 그중의 한 방법을 나타낸 것입
니다.
０ １ ２ ３ ４ ５ ６ ７
서로 공격하여 잡을 수 없도록 ０ ●
8개의 퀸을 놓습니다. １ ●
２ ●
３ ●
４ ●
５ ●
６ ●
７ ●
[그림 5-12] 8퀸 문제 풀이 중 한 예
체스판의 가로 줄을 행(行), 세로 줄을 열(列)이라 하고 배열 인덱스에 맞추어 행과 열에 0 ~ 7
의 번호를 부여합니다. 이 그림에 놓인 퀸은 왼쪽부터 차례로 0행 0열, 4행 1열, 7행 2열, 5행
3열, 2행 4열, 6행 5열, 1행 6열, 3행 7열입니다.
05•재귀 알고리즘 183
