8퀸 문제

지난 글 : [알고리즘/Do it 알고리즘] - 하노이의 탑

 

8퀸 문제 알아보기

8퀸 문제(8-Queen problem)는 재귀 알고리즘을 깊이 있게 이해하기 위한 예제로 자주 등장하며 19세기 유명 수학자 카를 프리드리히 가우스(C. F. Gaus)가 잘못된 해답을 내놓은 것으로도 알려져있는 문제라 한다. 문제는 아래와 같다.

서로 공격하여 잡을 수 없도록 8개의 퀸을 8 X 8 체스판에 놓이시오.

이 문제의 답이 되는 조합은 무려 92가지라 한다. 체스판의 가로줄을 행, 세로줄을 열이라 하고 배열 인덱스에 맞추어 행과 열에 0~7의 번호를 부여한다. 그리고 퀸을 아래와 같이 배치한다.

0행 0열
4행 1열
7행 2열
5행 3열
2행 4열
6행 5열
1행 6열
3행 7열

 

퀸 배치하기

8개의 퀸을 배치하는 조합은 모두 몇 가지인지 알아보자. 체스판은 64칸(8 X 8)이므로 처음 퀸을 1개 배치할 때는 아무 곳이나 선택해도 된다. 다음 퀸을 배치할 때는 남은 63칸 중 임의로 선택한다. 마찬가지로 8번째까지 생각하면 아래처럼 엄청난 수의 조합이 만들어진다.

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

하지만 이 조합을 모두 나열하고 각각의 조합이 8퀸 문제의 조건을 만족하는지 조사하는 것은 굉장히 어렵다. 퀸은 자신과 같은 줄에 있는 다른 퀸을 공격할 수 있으므로 아래와 같은 규칙을 세울 수 있다.

[규칙1] 각 열에 퀸을 1개만 배치한다.
[규칙2] 각 행에 퀸을 1개만 배치한다.

 

이렇게 하면 이 조합을 나열하는 알고리즘을 어떻게든 만들 수 있다. 그러나 간단하지는 않다.

 

이제 문제를 정리하기 위해 처음으로 돌아가 [규칙1]에 따라 조합을 나열하는 알고리즘을 생각해보자. 퀸을 배치하기 직전의 체스판은 '?'(열에 퀸이 배치되지 않은 상태)으로 채워져 있다. 처음에는 모든 열이 '?'이고, 모든 '?'를 채우면 퀸 배치가 완료된다. 같은 행에 여러 개의 퀸을 배치하는 조합은 생각하지 않으며, 퀸을 1개 배치하고 나서 문제를 8개의 부분 문제로 나누는 작업을 반복한다.

 

분기 조작

이번에는 분기하여 모든 조합을 나열하는 프로그램이다. 배열 pos는 퀸의 배치를 나타낸다. i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 한다. 예로 pos[1]의 값이 4이면 '1열의 퀸이 4행에 배치된 상태'를 뜻한다. 이 때 set 메서드는 pos[i]에 0부터 7까지 값을 순서대로 대입해 'i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀 메서드'다. 매개변수 i가 이 퀸을 배치할 열이다.

위에서 호출된 set 메서드는 매개변수 i에 0을 전달받기에 0열에 퀸 1개를 배치하게 된다. for문에 의한 반복을 통해 j값을 0부터 7까지 1씩 증가시키며 pos[i]에 j를 대입하는 것으로 퀸을 j행에 배치한다. 이 대입에서 0열이 확정되고 다음으로 1열을 확정해야 한다. 하여 set(i + 1)처럼 재귀 호출을 한다. set(i + 1)에 의해 앞에서 했던 작업을 다음 열인 1열에 대해 수행한다.

 

이렇게 재귀 호출을 거듭 반복하면 결국 i가 7이 되고 8개의 퀸이 모두 배치된다. 그러면 퀸을 더 배치할 필요가 없으므로 print 메서드를 호출해 퀸이 배치된 위치를 출력한다. 출력하는 값은 배열 pos의 요솟값이다. 프로그램을 실행하면 16,777,216개의 조합이 모두 나열된다. 

 

이렇게 분기하며 퀸을 배치하는 조합을 모두 나열했다. 이런 방법을 분기 조작 또는 가지 뻗기(branching)라 한다. 하노이의 탑이나 8퀸 문제처럼 문제를 작게 나누고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 분학 정복법(divide and conquer method)이라 한다. 물론 문제를 작게 나눌 때는 작은 문제의 풀이에서 원래 문제의 풀이가 쉽게 도출될 수 있도록 설계해야한다.

 

분기 한정법

분기 조작으로 퀸을 배치하는 조합을 나열할 수는 있지만 8퀸 문제의 답을 구할 수는 없다. 아래는 앞에서 분기를 할정하기 위해 정했던 규칙이다.

[규칙2] 각 행에 퀸을 1개만 배치한다.

이 개념을 적용해 다시 프로그램을 작성해보자.

위 프로그램은 flag라는 배열을 사용한다. flag는 같은 행에 중복해 퀸이 배치되는 것을 방지하기 위한 표시(flag)다. j행에 퀸을 배치하면 flag[j]의 값을 true로 하고, 배치되지 않은 상탯값은 false로 한다. 0열에 퀸을 배치하기 위해 호출한 set 메서드는 먼저 0행에 퀸을 배치한다. 0행에 퀸을 배치했기에 flag[0]의 값을 true로 변경한다. 그 후 set 메서드를 재귀적으로 호출한다. 이렇게 호출한 set 메서드는 다음 1열에 퀸을 배치한다.

 

또, 재귀 호출한 set(i + 1) 메서드 실행이 끝나면 퀸을 j행에서 제거하기 위해 flag[j]에 아직 배치하지 않았음을 나타내는 false를 대입한다. 이처럼 불필요한 분기를 없애 불필요한 조합을 줄이는 법을 한정(bounding) 조작이라 하고, 분기 조작과 한정 조작을 조합해 문제를 풀어 가는 법을 분기 한정법(branching and bounding method)이라 한다.

 

8퀸 문제를 해결하는 프로그램 만들기

위 프로그램은 사실 8퀸 문제를 해결하지 못했다. 체스에서 퀸은 대각선으로도 이동할 수 있기 때문이다. 그렇기에 어떤 대각선에서 보더라도 퀸을 1개만 배치하는 한정 조작을 추가해야 한다.

flag_b와 flag_c는 '/' 방향과 '\' 방향의 대각선 위에 퀸을 배치했는지 체크하는 배열이다. j행 i열에서 각각의 대각선 방향에 퀸이 배치되었는지 체크하는 배열의 인덱스는 flag_b[i + j]와 flag_c[i - j + 7]이다. 어떤 칸에 퀸을 배치할지 여부를 검토할 때 같은 행에 미이 퀸을 배치했는지 체크한 후 퀸을 배치한다.

 

다 작성은 했는데 코드가 어떤 방식으로 돌아가는 지를 아직 이해하지 못했다. 특히 대각선 방향에 퀸이 존재하는지를 검토하는 flag_b[i + j]와 flag_c[i - j + 7]이 이해가 어렵다. 이해할 때가지 계속 살펴봐야 겠다.

 

참고 서적 :