[recursion 응용] n queens problem

queens problem이란?

- 체스판에서 대각선, 상하좌우에 말이 없도록 겹치지 않게 놓는 문제를 말한다.

- 문제를 해결하기 위해서 '상태공간트리'를 활용해보자.

 

---

 

상태공간트리란?

 

- 위와 같이 해를 찾기 위해 정답을 향해 나아가는 트리를 말한다.

- 즉, 해가 존재한다면 그것은 반드시 이 트리의 어느 한 노드에 해당한다.

- 따라서 이 트리를 체계적으로 탐색한다면 해를 구할 수 있다!- 하지만 상태공간트리의 모든 노드를 탐색할 필요는 없다.

 

 

- 다음과 같이 깊이 우선으로 탐색하여 해를 찾는 알고리즘도 있다.- 이번 문제를 해결 할 때엔 "그 노드가 이미 infeasible한지, 즉 non-promising (꽝)인지"를 확인하면 된다.

 

---

 

코드를 구성해보자.

 

1. 변수 정하기

- 매개변수는 내가 현재 트리(N*N)의 어떤 노드에 있는지를 지정하면 된다.

- 1번에서 level까지 말이 어디에 놓였는지는 전역변수 배열 cols를 이용해 표현한다.

- 'cols[i]=j' 는 i번 말이 (i행, j열)에 놓였음을 의미한다!- return type은 '실패, 성공'을 뜻하기 위해 boolean으로 표현한다.

int[] cols = new int[N + 1];
bool queens(int level) {
	if non - promising
		report failure and return;
	else if success
		report answer and return;
	else
		visit children recursively;
}

---

2. 조건과 return 값 정하기

 

1) non-promising인 경우

if (!promising(level))
		return false;

- promising인지 아닌지를 test하는 함수 promising을 만들었다고 가정하자.

 

2)promising인 경우

else if (level == N)
		return true;

 - promising 테스트를 통과했다는 가정 하에 'level==N이면 1부터 level까지 모든 말이 놓였다'는 의미이다.

- 즉, 성공이다!

 

3)아무것도 아닌 경우

else {
	for (int i = 1; i < N; i++) {
		cols[level + 1] = i;//level+1번째 말을 각각의 열에 놓은 후
		if (queens(level + 1))//recursion 호출
			return true;
}
	return false;

- 말을 (level, i)에 놓은 후, 또다시 queens()함수에 다음 level+1을 넣으며 recursion실행한다.

 

[완성된 조건 queens 함수]

int[] cols = new int[N + 1];
bool queens(int level) {
	if (!promising(level))
		return false;
	else if (level == N)
		return true;
	else {
		for (int i = 1; i < N; i++) {
			cols[level + 1] = i;
			if (queens(level + 1))
				return true;
		}
		return false;
	}
}

---

 

3. promising 함수 만들기

- cols[level]까지 왔다는 이야기는 1~level전 까지는 충돌이 없음을 뜻한다.

- 따라서 마지막에 놓인 이 말이 이전에 놓인 다른 말들과 충돌하는지를 검사하도록 한다!

 

 

1) 같은 열 또는 행에 있어서 겹치는 경우

if (cols[i] == cols[level])//같은 열에 놓였는지 검사
		return false;

 

2) 같은 대각선에 있어서 겹치는 경우

- level - i == | cols[level] - cols[i] |

- '비교하는 대상의 거리와 cols의 level번째 에서 cols의 i번째 사이의 거리가 같다' 면 대각선에서 겹치는 경우이다!

else if (level-i==abs(cols[level]-cols[i])//같은 대각선에 놓였는지 검사
		return false;

 

[완성된 promising함수]

bool promising(int level) {
	for (int i = 1; i < level; i++) {
		if (cols[i] == cols[level])//같은 열에 놓였는지 검사
			return false;
		else if (level-i==abs(cols[level]-cols[i])//같은 대각선에 놓였는지 검사
			return false;
	}
	return true;
}

---

완성된 코드

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int *cols = new int[N + 1];
bool queens(int level);
bool promising(int level);

int main(void) {
	int level;
	cout << "N을 입력하시오";
	cin >> N;
	cout << "1~N중 입력하시오";
	cin >> level;
	queens(level);

	delete[] cols;
	return 0;
}
bool queens(int level) {
	if (!promising(level))
		return false;
	else if (level == N)
		for (int i = 1; i <= N; i++)
			cout << "(" << i << ", " << cols[i] << ")" << endl;
	return true;

	for (int i = 1; i < N; i++) {
		cols[level + 1] = i;
		if (queens(level + 1))
			return true;
	}
	return false;

}
bool promising(int level) {
	for (int i = 1; i < level; i++) {
		if (cols[i] == cols[level])//같은 열에 놓였는지 검사
			return false;
		else if (level - i == abs(cols[level] - cols[i]))//같은 대각선에 놓였는지 검사
			return false;
	}
	return true;
}

이것 또한 제대로 실행이 안된다..

---

(cols[level],level)로 좌표를 표현할 수 있다는 생각이 놀랍다.

알고리즘의 순환은 정말 유용한 듯하다.