Page 184 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

퀸 놓기

8개의 퀸을 놓는 조합은 모두 몇 가지인지 알아보겠습니다. 체스판은 64칸(8 × 8)이므로 처
음에 퀸을 1개 놓을 때는 64칸 중 아무 곳이나 선택할 수 있습니다. 다음 퀸을 놓을 때는 나머
지 63칸에서 임의로 선택합니다. 마찬가지로 8번째까지 생각하면 다음처럼

64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760

가지의 조합이 만들어집니다. 그런데 이 조합을 모두 나열하고 각각의 조합이 8퀸 문제의 조
건을 만족하는지 조사하는 것은 현실적이지 않습니다. 퀸은 자신과 같은 열에 있는 다른 퀸을
공격할 수 있으므로 아래와 같은 규칙을 세울 수 있습니다.

[규칙 1] 각 열에 퀸을 1개만 배치합니다.

이렇게 하면 퀸을 놓는 조합의 수는 많이 줄어들었지만 여전히 그 수는

8 × 8 × 8 × 8 × 8 × 8 × 8 × 8 = 16,777,216

가지로 엄청나게 많습니다. 다음의 그림 5-13은 이 조합의 일부만 표현한 것으로, 이 가운데
8퀸 문제를 만족하는 풀이는 하나도 없습니다. 왜냐하면 퀸은 자신과 같은 행에 있는 다른 퀸

을 공격할 수 있기 때문입니다.
같은 행에 퀸이 2개 이상 놓이면 안 됩니다.

184 C 알고리즘