[BOJ] N-Queen

문제설명

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

• 퀸이 공격할 수 있는 위치는 같은 열, 같은 대각선 내에 존재할때
• 같은 대각선 내의 위치좌표들간의 공통점이 뭔지 알아내는게 중요

풀이

#include <iostream>
#include <vector>

using namespace std;

int n;
int answer;
vector<bool> line; //열
vector<bool> left_line; //좌하향 대각선
vector<bool> right_line; //우하향 대각선

void nQueen(int cnt) {
	if (cnt == n) {
		answer = answer+1;
		return;
	}

    //우하향 대각선에 속한 애들은 다 행-열값이 똑같음
    //좌하향의 경우에는 다 행+열이 같음
    //근데 행-열은 음수일 수 있으니까 n을 더하는것
	for (int i = 0; i < n; i++) {
		if (!line[i] && !left_line[cnt+i] && !right_line[cnt-i+n]) {
			line[i] = true;
			left_line[cnt + i] = true;
			right_line[cnt - i + n] = true;
			nQueen(cnt+1);

			line[i] = false;
			left_line[cnt + i] = false;
			right_line[cnt - i + n] = false;
		}
	}
	return;
}

int main() {
	cin >> n;

	line.assign(n, false);
	left_line.assign(n*2, false); //cnt+i가 최대 n+n일 수 있으니까
	right_line.assign(n*2, false); //cnt-i+n이 최대 n-0+n일 수 있으니까

	answer = 0;
	nQueen(0);

	cout << answer;

}