[Gold IV] N-Queen - 9663

문제 링크

문제 링크

성능 요약

메모리: 2020 KB, 시간: 200 ms

문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

코드

#include <iostream>
using namespace std;

int n;
int result = 0;

void solve(int row, int col_mask, int diag1_mask, int diag2_mask) {
	if (row == n) {
		result++;
		return;
	}

	// 가능한 열 위치를 비트마스크로 표현
	int available = ((1 << n) - 1) & ~(col_mask | diag1_mask | diag2_mask);

	while (available) {
		int bit = available & -available;  // 가장 오른쪽의 1비트 추출
		available -= bit;  // 현재 선택한 열을 제거
		solve(row + 1, col_mask | bit, (diag1_mask | bit) << 1, (diag2_mask | bit) >> 1);
	}
}

int main() {
	cin >> n;
	solve(0, 0, 0, 0);
	cout << result << endl;
	return 0;
}