[알고리즘] C++로 N-Queen 문제풀기 (Back-Tracking 알고리즘)

1. N-Queen 문제란?

N-Queen 문제란 다음과 같이 (N * N) 체스판이 있을 때,

N개의 퀸을 체스판에 놓을 수 있는 경우를 찾는 문제이다.

이 문제는 백트래킹(Back-Tracking) 알고리즘을 적용하는 전형적인 문제이다.

 

 

2. Back-Tracking 이란?

말 그대로 가능하지 않는 노드는 배제하고 뒤로 돌아가는 형태이다.

어떤 노드에 방문했을 때, 그 노드가 '유망한' 노드가 아니라면 그 전 상태로 돌아가는 것이다.

 

 

3. 풀이 코드

#include <iostream>

using namespace std;

int n, cnt = 0;
bool cols[15], incs[29], decs[28];

void nQueen(int r)
{
	if (r > n)
	{
		cnt++;
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!cols[i] && !incs[r + i] && !decs[n + r - i])
		{
			cols[i] = incs[r + i] = decs[n + r - i] = true;
			nQueen(r + 1);
			cols[i] = incs[r + i] = decs[n + r - i] = false;
		}
	}
}

int main(void)
{
	cin >> n;

	nQueen(1);

	cout << cnt << '\n';

	return 0;
}