<백준> 9663

N-Queen

문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

퀸이 일직선 배치일 때와 대각선 배치일 때를 제외한 나머지 공간을 백트래킹으로 찾으면 된다.

int a[15];
int n;
int cnt = 0;

bool Check(int row)
{
	for (int i = 0; i < row; i++)
	{
		if (a[i] == a[row]) //일직선 배치
			return false;
		if (abs(row - i) == abs(a[i] - a[row])) //대각선 배치
			return false;
	}
	return true;
}

void BackTracking(int row)
{
	if (row == n)
	{
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++)
	{
		a[row] = i;
		if (Check(row))
			BackTracking(row + 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	

	cin >> n;

	BackTracking(0);
	cout << cnt;
}