[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)
- 예시 (열은 "세로" 부분을 뜻한다. 행은 "가로" 부분을 뜻한다.)
- 접근 방법
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
: 예시
2) 대각선의 방향이 \ 일 때
: 특정 칸을 지나는 대각선의 인덱스는 해당하는 각 칸의 열의 인덱스에서 행의 인덱스를 빼고 7을 더한 값과 같다.
: 대각선 인덱스의 값 = 7 - i + j
: 예시
- 코드
#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