CSEC PS - chessboard and Queens

https://cses.fi/problemset/list/

코드가 깔끔한거같아서 올려봄

 

<문제설명> 

n-queen문제와 흡사함.

8*8 체스판에 8개의 퀸을 서로 공격할 수 없도록 두는 경우의수를 출력하는 문제.

퀸을 둘 수 없는 곳을 (*)로 표시해서 약간의 변형을 줬다. (풀이는 똑같음)

 

<풀이>

column, diag1, diag2에 대해 이미 사용중인 것이 있다면 가지치기를 하며 재귀

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
bool unable[8][8];

int ans = 0;
void go(int k, int col, ll d1, ll d2) {
	if (k == 8) {
		ans++;
		return;
	}

	for (int i = 0; i < 8; i++) {
		if (unable[k][i]) continue;
		if (col & (1 << i)) continue;
		if (d1 & (1 << (k + i))) continue;
		if (d2 & (1 << (i - k + 7))) continue;
		go(k + 1, col | (1 << i), d1 | (1 << (k + i)), d2 | (1 << (i - k + 7)));
	}
}

int main() {
	for (int i = 0; i < 8; i++) {
		string s; cin >> s;
		for (int j = 0; j < 8; j++)
			if (s[j] == '*') 
				unable[i][j] = true;
	}
	go(0, 0, 0, 0);

	cout << ans << '\n';
}