n-queen

대표적인 백트래킹 문제 

 

n*n체스 보드판에 n개의 queen을 서로 공격하지 못하도록 배치하는 방법을 찾아내는 문제이다.

 

아래의 사이트에서 문제를 풀어볼 수 있다.

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

문제풀이 

 

우선 알고리즘문제를 풀기위해서는 큰 하나의 문제를 작은 여러개의 문제(순서)로 쪼갤 수 있어야한다.

 

퀸은 모든방향으로 이동이가능하다. 

 

즉 행과 열, 대각선이 겹치면안된다.

 

대각선의경우 두가지가 존재할 수있다.

 

오른쪽위로 올라가는 우상향대각선

 

오른쪽아래로 내려가는 우하향대각선

 

N=4라고 가정해보자

(0,0) (0,1) (0,2) (0,3)

(1,0) (1,1) (1,2) (1,3)

(2,0) (2,1) (2,2) (2,3)

(3,0) (3,1) (3,2) (3,3)

 

위와같은 좌표형식으로 체스판을 나타낼 수있는데,

우상향 대각선의 경우 행과 열의 합이 일정하다. ex) (1+0), (0+1)  

inc => 0 ~ 6까지의 범위존재

 

우하향 대각선의 경우 행과 열의 차가 일정하다. ex) (0-2), (1-3) 

-3 ~ 3 // 단 음수배열은 없기 때문에 N을더해 범위를 설정해준다. =

dec => 1 ~ 7까지의 범위존재

 

=> 한개의 체스말을 둘때 대각선의 겹침여부를 inc,dec 배열의 값체크여부로 확인할 수 있다.

=> 열의 경우 col배열의 값 체크여부로 확인할 수 있다.

=> 행의 경우 애초에 값을 넣을때 다르게 넣어주기 때문에 겹칠 수가 없다.

 

==========================================================================

1. 첫번째 행, 첫번째 열에 퀸을 놓는다.

2. 다음 행에서 가능한 가장 왼쪽 열에 퀸을 놓는다.

3. n번째 열에 더 이상 퀸을 놓을 수 없다면 백트랙한다.

4. 마지막 행에 퀸을 놓으면 하나의 해를 구한 것

5. 모든 경우를 조사할 때까지 백트래킹해가며 해들을 구한다

===========================================================================

코드는 아래와 같다.

#include <iostream>

using namespace std;
int col[10];
int inc[20];
int decc[20];
int N;
int ans;
void solve(int level) {
if (level > N) {
ans++;
return;
}
else {
for (int i = 1; i <= N;i++) {
if (!col[i] && !inc[level + i] && !decc[level - i + N]) {
col[i] = inc[level + i] = decc[level - i + N] = 1;
solve(level + 1);
col[i] = inc[level + i] = decc[level - i + N] = 0;
}
}
}

}

int main() {
cin >> N;
solve(1);
printf("%d", ans);
}