[Algorithm] 8퀸 문제 알고리즘 (재귀)

💜 8퀸 문제란?

- 8x8 체스판에 8개의 퀸을 배치한다.

- 조건: 어떤 퀸도 다른 퀸을 위협해서는 안된다

- 추가 설명: 퀸은 상하좌우, 대각선 4방향으로 거리 제한 없이 이동할 수 있는 기물

퀸의 이동 경로

---

💜 어떤 기능을 하는 함수를 구현해야하는가? (문제 정의)

- 각 열에 퀸 하나만 배치한다. (규칙1)

- 각 행에 퀸 하나만 배치한다. (규칙2)

- 하나의 퀸은 상하좌우, 대각선 4방향으로 거리 제한 없이 이동할 수 있다. (규칙3)

=> 각 퀸은 상대 퀸의 이동 경로를 방해하지 않으면서 위치해야 한다.

---

💜 문제를 어떻게 해결할 것인가? (아이디어 얻기)

1) 분할정복(Divide and conquer): 큰 문제를 작은 문제로 세분화하여 해결

 

2) 가지 뻗기 (Branch) : 가지를 뻗으며 모든 조합을 나열하는 것

- 목표: "각 열에 퀸이 하나 있다"는 전제를 만족하는 조합 구하기 > 규칙 1 적용

- 퀸의 대각선 이동 경로를 배제하고 생각

 

3) 재귀를 활용!

- 가지뻗기: 하나의 열에 퀸 배치 완료 > 다음 열로 넘어가 퀸 놓는 과정 수행 > "퀸 놓는 과정"은 똑같이 반복 > 재귀 사용!

 

4) 분기 한정법(Branching and bounding method): 가지 뻗기와 한정 조작을 조합하여 문제를 풀어가는 방법

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

- 목표: 규칙 1과 규칙 2를 둘 다 반영하여 문제 풀기

 

5) 분기한정법 심화

- 규칙1, 규칙2 적용 시 > 규칙 3은 고려되지 않음!

- 대각선도 고려하여 최종적으로 문제 풀기!

---

💜 문제 접근하기  (with 실제 코드와 함께 분석)

1. 가지 뻗기 + 분기 한정법 (1)

- 목표: 각 열에 퀸을 1개만 배치 (규칙 1)

          : 각 행에 퀸을 1개만 배치 (규칙 2)

- 예시 (열은 "세로" 부분을 뜻한다. 행은 "가로" 부분을 뜻한다.)

8퀸 문제 - 가지 뻗기 예시

- 접근 방법

1) 각 열의 인덱스 범위는 0 ~ 7 이다. 각 행의 인덱스 범위도 0 ~ 7 이다.

2) 각 열에 퀸을 하나씩 배치한다.

3) 해당 열의 특정 행의 퀸 유무를 알 수 있는 플래그 배열이 존재한다. (플래그 배열의 값이 1이면 퀸 존재, 0이면 퀸 존재 X)

4) 해당 열의 특정 행에 퀸이 하나 있다면, 플래그 배열 값을 1로 만들어주고 다음 열로 넘어간다.

5) 플래그 배열 값을 다시 0으로 만들어준다. (다음 열에 넘어 갔을 땐, 특정 행에 퀸이 없음을 가정하고 함수 실행 )

6) (2) ~ (5)의 과정은 열이 끝날 때까지 반복 (재귀 함수 사용 가능!)

 

- 코드

// i는 열의 인덱스를 뜻한다.
// j는 행의 인덱스를 뜻한다.

int count = 0;  // 퀸을 배치할 수 있는 총 개수
int pos[8];		// 각 열에서 퀸의 행 위치를 저장하는 배열
int flag[8];	// 각 행의 퀸 유무를 확인하는 배열

void set_eight_queens(int i) {
	for (int j = 0; j < 8; j++) {
		if (!flag[j]) {   // j 행에 퀸을 배치 X
			pos[i] = j;   // 해당 열의 j(행)을 설정
			if (i == 7) { // 모든 열의 배치를 마쳤다. > 끝내라
				count++;
			}
			else {
				flag[j] = 1;             // 해당 행에 퀸이 있음을 확인
				set_eight_queens(i + 1); // 다음 열로 넘어가기
				flag[j] = 0;             // 해당 행을 0으로 초기화 
                                         // (다음 열은 해당 행의 퀸유뮤 모름 > 퀸이 없다고 가정)
			}
		}
		
	}
}

 

 

2. 가지 뻗기 + 분기 한정법(2)

- 목표: 각 열에 퀸을 1개만 배치 (규칙 1)

         : 각 행에 퀸을 1개만 배치 (규칙 2)

         : 어떤 대각선 방향에서도 퀸을 1개만 배치 (규칙 3)

 

- 8x8 체스판에서 대각선의 특징

1) 대각선의 방향 : / , \ (두 방향)

2) 대각선의 총 개수: 15개

3) 대각선의 인덱스 : 0 ~14

 

- 접근 방법 (대각선 방향을 중심으로)

** i: 열의 인덱스, j: 행의 인덱스

1) 대각선의 방향이 / 일 때

: 특정 칸을 지나는 대각선의 인덱스는 해당하는 각 칸의 열과 행의 인덱스 합과 같다.

: 대각선 인덱스의 값 = i + j 

: 예시

8퀸 문제 대각선 /

 

2) 대각선의 방향이 \ 일 때

: 특정 칸을 지나는 대각선의 인덱스는 해당하는 각 칸의 열의 인덱스에서 행의 인덱스를 빼고 7을 더한 값과 같다.

: 대각선 인덱스의 값 = 7 - i + j 

: 예시

8퀸 문제: 대각선 \

- 코드

#define n 8            // n = 8로 설정
int count = 0;         // 퀸을 배치할 수 있는 총 개수
int flag_a[n];         // 각 행에 퀸을 배치했는지 체크하는 배열
int flag_b[n *2 - 1];  // 대각선 "/" 에 퀸을 배치했는지 체크하는 배열
int flag_c[n * 2 - 1]; // 대각선 "\" 에 퀸을 배치했는지 체크하는 배열
int pos[n];            // 각 열에서 퀸의 위치 (해당 열의 행의 위치)

// i열에서 알맞은 위치(행)에 퀸을 배치하는 함수
void set_queens_of_branch(int i) {
	for (int j = 0; j < 8; j++) {
		// 현재 행에 퀸이 없고 대각선에도 퀸이 없다 > 배치 가능
		if (!flag_a[j] && !flag_b[i + j] && !flag_c[7 + i - j]) {
			pos[i] = j;   // i열 j행 위치에 퀸을 배치
			if (i == 7) { // 모든 열에 배치를 마쳤다. > 끝내라
				count++;
			}
			else {
				// 현재 행, 대각선 flag를 1로 설정 > 퀸이 있다!
				flag_a[j] = flag_b[i + j] = flag_c[7 + i - j] = 1; 

				// 다음 열에 배치를 시도
				set_queens_of_branch(i + 1); 

				// 현재 행, 대각선 flag를 0으로 설정. (다음 열에 퀸이 배치되어있지 않다고 가정)
				flag_a[j] = flag_b[i + j] = flag_c[7 + i - j] = 0;
			}
		}
	}
}

---

💜참고자료

- 여덟 퀸 문제 - 네이버: https://terms.naver.com/entry.naver?docId=5667830&cid=60205&categoryId=60205

- 8퀸 문제 - Jimmy48 : https://velog.io/@jimmy48/8%ED%80%B8-%EB%AC%B8%EC%A0%9C