[알고리즘] 백트래킹(Backtracking): N-queens 문제

백트래킹 (Backtracking)

상태공간트리란 문제 해결 과정에서 해를 포함하고 있는 트리이다. 해가 존재한다면 그 해는 반드시 상태공간트리의 어떤 노드에 해당하므로, 이 트리를 체계적으로 탐색하면 언젠가는 해를 구할 수 있다.

해를 찾기 위해 상태공간트리를 완전탐색해야만 하는 것은 아니다. 상태공간트리를 깊이우선탐색(DFS)하여 효율적으로 해를 찾아낼 수 있다. 이런 탐색 방법을 되추적 기법(Backtracking)이라고 한다.

DFS로 트리를 탐색해 내려가면서 해를 찾지 못해 막힌다면(조건에 맞지 않는다면) 탐색을 중단하고 이전 단계로 퇴각한다.

N-queens Problem

---

N-퀸 문제는 백트래킹을 통해 풀 수 있는 유명한 알고리즘 문제이다.

N x N 크기의 체스판에 N개의 퀸을 배치하려고 한다. 체스에서 퀸은 아래와 같이 동일한 행, 열, 대각선 상으로 움직일 수 있다.

8-퀸에서는 총 8개의 퀸이 서로 동일한 행, 열, 대각선 상에 존재하지 않도록 배치되어야 한다. 가능한 해의 가짓수는 12가지가 있다.

소스코드

int cols[N + 1];
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;
}

// level은 0부터 시작
bool queens(int level) {
	if (!promising(level))
		return false;
	else if (level == N)
		return true;
	for (int i = 1; i <= N; i++) {
		cols[level + 1] = i;
		if (queens(level + 1))
			return true;
	}
	return false;
}

백트래킹 기법으로 문제의 해를 구하기 위해 queens 함수를 재귀함수로 구현한다. 함수의 리턴값은 bool 타입인데, 더 이상 내려갈 수 없다면 false를 리턴한다. queens 함수의 level은 현재 트리의 어떤 노드에 있는지를 나타내며 0부터 시작한다.

promising 함수는 충돌 여부를 검사하는 함수이다. 만약 promising 함수가 false를 리턴한다면 충돌이 있었던 것이므로 이전 단계로 퇴각해야 한다. 함수의 순환호출을 반복하면서 만약 level이 N과 같아진다면(모든 탐색이 끝난 뒤에도 여전히 탐색이 중지되지 않았다면) true를 리턴한다. 이때 cols 배열은 배치된 퀸의 위치를 나타내는 배열이다.

위 코드는 단순히 문제의 해가 존재하는지 여부를 bool 타입으로 리턴하는 함수이다. n퀸 문제의 해의 개수를 구하기 위해서는 아래 코드를 사용한다.

int cols[N + 1];
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;
}

int queens(int level, int N)
{
	if (!promising(level))
		return 0;
	else if (level == N) { // 모든 말이 전부 놓인 경우
		/*for (int i = 1; i <= N; i++) {
			printf("(%d, %d)", i, cols[i]);
		}*/
		return 1;
	}
	int count = 0;
	for (int i = 1; i <= N; i++) {
		cols[level + 1] = i;
		count += queens(level + 1, N);
		/*if (queens(level + 1, N))
			return true;
			*/
	}
	return count;
}

함수 반환 타입을 int로 바꾼 후 count 변수를 통해 해의 개수를 센다.

참고자료
Recursion의 응용: n queens problem / https://youtu.be/xKGbWC-DPT4