[재귀알고리즘]8퀸

8퀸 문제

재귀 알고리즘에 대한 이해를 돕기 위한 예제로 자주 등장
19세기 유명 수학자 카를 프리드리히 가우스(C. F. Gauss)가 잘못된 해답을 내놓은 사실로도 유명

• Q. 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 X 8 체스판에 놓으세요.
• 퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향 직선 이동이 가능. 즉, 상하좌우 + X 모양의 대각선 방향으로의 이동이 가능!
• 이 문제의 정답은 92가지의 조합이다.
• 8퀸 문제나 하노이의 탑 같은 문제는 문제를 세분화하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이해야 하는데, 이와 같은 방식을 분할 정복법(divide and conquer)이라고 한다.
• 물론, 이때 작은 문제의 풀이 방식은 전체 문제를 풀이하기 위한 부분이므로, 설계시 이것을 유념해야 한다.

 

1. 퀸 배치하기

• 임의의 자리에 8개의 퀸을 놓는 방법은 64 * 63 * 62 * 61 * 60 * 59 * 58 * 57 의 곱인 178,462,987,637,760 가지이다.
• 그러나 이 조합 안에서 8퀸 문제의 정답을 찾는 것은 현실적이지 않다. 따라서, 조건을 추가한다.

조건 1 : 각 열에 퀸은 1개만 존재한다

• 위에서도 말했듯 퀸은 상하좌우 대각선방향 그 어디라도 직선으로의 이동이 가능하다. 따라서, 같은 열에 퀸이 있다면 단 1번의 공격으로 다른 퀸을 잡을 수 있다.
• 조건 1이 추가된 상태에서 임의의 자리에 8개의 퀸을 놓는 방법은 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 의 곱인 16,777,216 가지이다.
• 그러나 이 조합 역시 현실적이지도 않고, 8퀸 문제의 풀이가 될 수도 없다. 퀸은 같은 행에 있는 퀸과 대각선 방향의 퀸도 단 1번의 공격으로 잡을 수 있기 때문이다. 따라서 또 다른 조건이 필요하다.

조건 2 : 각 행에 퀸은 1개만 존재한다

• 이러한 방식으로 퀸이 놓일 수 있는 자리에 대한 조건을 계속해서 추가하다보면 8퀸 문제에 대한 올바른 풀이 방법을 찾을 수 있게 된다. 우리는 여기서 8퀸 문제를 풀이할 수 있는 알고리즘에 대해 고민해보기로 하자.

 

 

2. 가지뻗기 : branching method

00000000 ~ 77777777 까지 순서대로

package com.study.Algorithm;
// 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열합니다.

class QueenB_addCondition01 {
	static int[] cb = new int[8];	// 각 열의 퀸의 위치

	// 각 열의 퀸의 위치를 출력합니다. 
	static void print() {
		for (int i = 0; i < 8; i++)
			System.out.printf("%2d", cb[i]);
		System.out.println();
	}

	// i열에 퀸을 놓습니다. 
	static void set(int i) {
		for (int j = 0; j < 8; j++) {
			cb[i] = j;			// 퀸을 j행에 배치합니다.
			if (i == 7)			// 모든 열에 배치합니다.
				print();
			else
				set(i + 1);		// 다음 열에 퀸을 배치합니다.
		}
	}

	public static void main(String[] args) {
		set(0);					// 0열에 퀸을 배치합니다.
	}
}

▼ 설명

1. int형 배열 cb는 체스판을 의미한다. 즉, 배열의 크기가 8개라는 소리는 8개의 열을 가지고 있는 체스판이란 이야기이다.
2. 처음에는 i열, cb[i]의 j행에 퀸을 놓는다. 이때 j행의 위치는 for문을 이용해 0부터 7까지 8개의 자리를 만들어준다. 이렇게하면 8 * 8의 체스판이 만들어진다.
3. i열이 7번째 열이라는 이야기는, 배열이 가득 찼다는 이야기이며 동시에 체스판에 퀸이 전부 놓였다는 이야기이다. 따라서 현재 놓인 체스판을 출력한ㄷ.
4. 그게 아니라면, 열을 하나 옮겨서 퀸을 마저 놓는다.
5. 이렇게 반복하면 00000000 부터 77777777까지의 모든 조합이 구해진다. 즉, 16,777,216개의 조합을 구할 수 있게 된다.

 

 

3. 분기 한정법: branching and bounding method

가지 뻗기와 한정 조작을 합하여 문제를 풀어가는 방법

package com.study.Algorithm;
// 각 행, 열에  1개의 퀸을 배치하는 조합을 재귀적으로 나열합니다.

class QueenBB_addCondition02 {
	static boolean[] chk = new boolean[8];		// 각 행에 퀸을 배치했는지 체크
	static int[] cb = new int[8];				// 각 열의 퀸의 위치

	// 각 열의 퀸의 위치를 출력합니다. 
	static void print() {
		for (int i = 0; i < 8; i++)
			System.out.printf("%2d", cb[i]);
		System.out.println();
	}

	// i열의 알맞은 위치에 퀸을 배치합니다. 
	static void set(int i) {
		for (int j = 0; j < 8; j++) {
			if (chk[j] == false) {		// j행에는 퀸을 아직 배치하지 않았다면
				cb[i] = j;				// 퀸을 j행에 배치합니다.
				if (i == 7)				// 모든 열에 배치한 경우
					print();
				else {
					chk[j] = true;
					set(i + 1);
					chk[j] = false;
				}
			}
		}
	}

	public static void main(String[] args) {
		set(0);
	}
}

▼ 설명

가장 처음에는 체스판에 퀸이 하나도 올라가 있지 않다.
따라서 set(0)을 호출한 당시에는 chk 배열의 어느곳에도 true가 들어있지 않게 된다.

 

1. int형 배열 cb는 체스판을 의미한다. 즉, 배열의 크기가 8개라는 소리는 8개의 열을 가지고 있는 체스판이란 이야기이다.
2. boolean형 배열 chk는 같은 행에 중복하여 퀸이 배치되는것을 방지하기 위한 배열이다.
3. set이 호출되면 퀸이 들어있는지 아닌지를 먼저 판단하기 위해 chk에 쓰일 변수를 먼저 설정해준다.
4. chk[j]의 값이 false이라면, 같은 행에는 아직 퀸이 없다는 것이고, 퀸이 들어갈 수 있다는 이야기이다. 따라서 cb[i]의 j행에 퀸을 넣어준다.
5. 그 후에 ch[i]에서 i가 7이라면 모든 열에 퀸이 들어갔다는 이야기이므로, 체스판의 형태를 출력한다.
6. 그러나 i가 7이 아니라면, 아직 넣어야 하는 퀸이 남아있으므로, 먼저 chk[j]를 true로 바꿔주고 set에 i+1을 넣어 호출해준다. 이 호출이 끝나면 chk[j]를 false로 바꿔준다.
7. 바꿔주는 이유는, 8개의 퀸을 모두 넣어 한번 출력해주었기 때문에, chk 배열을 초기화하기 위해서이다.

한정(bounding) 조작 : 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법

 

 

4. 8퀸 문제를 푸는 프로그램

package com.study.Algorithm;
// 8퀸 문제 풀이

class EightQueen {
	static boolean[] flag_a = new boolean[8];	// 각 행에 퀸을 놓았는지 체크
	static boolean[] flag_b = new boolean[15]; 	// ／대각선 방향으로 퀸을 놓았는지 체크
	static boolean[] flag_c = new boolean[15]; 	// ＼ 대각선 방향으로 퀸을 놓았는지 체크
	static int[] cb = new int[8];				// 각 열의 퀸의 위치
	static int count = 0;

	// 각 열의 퀸의 위치를 출력
	static void print() {
		for (int i = 0; i < 8; i++) {
			System.out.printf("%2d", cb[i]);
		}
		System.out.println();
	}

	// i열의 알맞은 위치에 퀸을 배치 
	static void set(int i) {
		for (int j = 0; j < 8; j++) {
			if (flag_a[j] == false &&			  	// 가로(j행)에 아직 배치하지 않았습니다.
				 flag_b[i + j] == false &&		  	// 대각선 ／에 아직 배치하지 않았습니다.
				 flag_c[i - j + 7] == false) {  	// 대각선 ＼에 아직 배치하지 않았습니다.
				cb[i] = j;							// 퀸을 j행에 배치합니다.
				if (i == 7)	{						// 모든 열에 배치한다면
					print();
					count++;
				}
				else {
					flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true;
					set(i + 1);
					flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false;
				}
			}
		}
	}

	public static void main(String[] args) {
		set(0);
		System.out.println(count);
	}
}

 

[자료출처:www.notion.so/b1afde9993c6462892ad9ec8fc176103]