3. 대표적인 제약만족문제 N-Queen 문제
대표적인 제약만족문제로 N-QUEEN 문제가 있습니다. N×N 판에 N개의 퀸을 배치하는 문제이죠.
제약조건은 어떤 자리의 가로, 세로, 대각선 방향에 퀸이 있다면 그 자리에는 퀸을 둘 수 없다는 점입니다. 아래 그림은 4×4 퀸 문제의 해입니다.
각 퀸의 가로, 세로, 대각선에는 다른 퀸이 위치하지 않죠. 그러므로 제약조건에 적합한 해를 찾았다고 볼 수 있습니다. N퀸 문제는 백트래킹 알고리즘을 사용하여 해를 찾을 수 있습니다.
문제를 해결하기 위해 N퀸 문제를 모델링해봅시다.
N퀸 문제는 (x1, x2, x3, … ,xn)을 구하는 문제라고 볼 수 있습니다.
퀸은 한 행에 한 개만 배치할 수 있습니다. 그러므로 각 행에 오는 퀸의 위치(x)를 (x1, x2, x3, … ,xn)과 같이 행열로 나타낼 수 있습니다. 왼쪽 그림의 경우 (3, 1, 4, 2)로 표현할 수 있습니다.
4퀸 문제의 해답을 구하는 과정을 백트래킹 알고리즘을 사용하여 알아봅시다.
1행의 1열에 퀸이 올 경우 2행에는 3열 또는 4열에 퀸이 올 수 있습니다.
먼저 2행 3열에 퀸을 배치해 봅시다. 그러면 다음 그림과 같이 3행에 퀸을 배치할 자리가 없게 되어 해를 구할 수 없게 됩니다.
그렇다면 어떻게 해야할까요? 백트래킹해서 위로 올라가 2행의 4열이 가능한 지를 판단하게 되겠지요. 그러나 2행에 4열을 추적하면 (1, 4, 2, ?)까지는 추적이 가능하나 4행에 올 수 있는 퀸의 자리가 없습니다. 그러므로 1행 1열에는 퀸이 올 수 없다는 결론을 얻게 됩니다.
다시 백트래킹 하여 1행 2열부터 추적을 시작합니다. 그 추적 결과를 상태공간트리로 나타내면 다음과 같습니다.
4×4 퀸의 문제의 해는 (2, 4, 1, 3)과 (3, 1, 4, 2)를 얻을 수 있습니다.
4×4 퀸 문제의 경우 해가 2개 뿐이기 때문에 쉽게 구할 수 있습니다. 그러나 N의 수가 점점 커지면 어떻게 될까요? N의 수에 따른 N퀸 문제의 해답은 다음과 같습니다.
N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … | 24 |
해의 수 | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | … | 28,439,272,956,934 |
해의 수 (대칭구별) | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | … | 227,514,171,973,736 |
N의 수가 증가함에 따라 해를 찾는데 소요되는 시간이 굉장히 늘어나겠군요.
퀴즈
N 퀸 문제에 대한 설명으로 맞는 것을 3가지 고르세요.
Please select 3 correct answers
시뮬레이션
http://eightqueen.becher-sundstroem.de/
해당 사이트에 가서 N퀸 문제의 조건을 달리하여 N퀸 문제를 해결해보고, N퀸 문제를 백트래킹으로 해결하는 과정을 체험해보세요!
① Manual(수동) : 직접 N퀸을 배치해보거나 Simulation(시뮬레이션)을 택하여 자동으로 퀸 문제를 풀도록 할 수 있습니다.
② 시뮬레이션으로 할 경우 속도를 Slow(천천히), Moderate(보통), Fast(빠르게) 조절할 수 있습니다.
③ N퀸의 사이즈를 정할 수 있습니다. 기본 8 x 8로 되어 있고, 한 단계식 낮춰 4 x 4 까지 해 볼 수 있습니다.
