102 lines
2.2 KiB
C++
102 lines
2.2 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
using ull = unsigned long long;
|
||
|
||
int n;
|
||
ull ans = 0;
|
||
|
||
// 每行/每列已经出现过的形状、颜色
|
||
int rowShape[4], rowColor[4], colShape[4], colColor[4];
|
||
|
||
// usedPair[s] 的第 c 位为 1，表示 (shape=s, color=c) 已经用过
|
||
int usedPair[4];
|
||
|
||
void dfs(int rem) {
|
||
if (rem == 0) {
|
||
++ans;
|
||
return;
|
||
}
|
||
|
||
// 选择候选数最少的空格子（MRV剪枝）
|
||
int bestIdx = -1;
|
||
int bestCnt = 100;
|
||
pair<int,int> bestCand[16];
|
||
int bestLen = 0;
|
||
|
||
int tmp = rem;
|
||
while (tmp) {
|
||
int idx = __builtin_ctz((unsigned)tmp);
|
||
int i = idx / n, j = idx % n;
|
||
|
||
pair<int,int> cand[16];
|
||
int len = 0;
|
||
|
||
for (int s = 0; s < n; ++s) {
|
||
if ((rowShape[i] >> s) & 1) continue;
|
||
if ((colShape[j] >> s) & 1) continue;
|
||
for (int c = 0; c < n; ++c) {
|
||
if ((rowColor[i] >> c) & 1) continue;
|
||
if ((colColor[j] >> c) & 1) continue;
|
||
if ((usedPair[s] >> c) & 1) continue;
|
||
cand[len++] = {s, c};
|
||
}
|
||
}
|
||
|
||
if (len == 0) return; // 这个格子已经无解，直接剪掉
|
||
if (len < bestCnt) {
|
||
bestCnt = len;
|
||
bestIdx = idx;
|
||
bestLen = len;
|
||
for (int k = 0; k < len; ++k) bestCand[k] = cand[k];
|
||
if (bestCnt == 1) break;
|
||
}
|
||
|
||
tmp &= tmp - 1;
|
||
}
|
||
|
||
int i = bestIdx / n, j = bestIdx % n;
|
||
rem ^= (1 << bestIdx);
|
||
|
||
for (int k = 0; k < bestLen; ++k) {
|
||
int s = bestCand[k].first;
|
||
int c = bestCand[k].second;
|
||
|
||
rowShape[i] |= (1 << s);
|
||
rowColor[i] |= (1 << c);
|
||
colShape[j] |= (1 << s);
|
||
colColor[j] |= (1 << c);
|
||
usedPair[s] |= (1 << c);
|
||
|
||
dfs(rem);
|
||
|
||
usedPair[s] ^= (1 << c);
|
||
colColor[j] ^= (1 << c);
|
||
colShape[j] ^= (1 << s);
|
||
rowColor[i] ^= (1 << c);
|
||
rowShape[i] ^= (1 << s);
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(nullptr);
|
||
|
||
cin >> n;
|
||
|
||
if (n == 1) {
|
||
cout << 1 << '\n';
|
||
return 0;
|
||
}
|
||
if (n == 2) {
|
||
cout << 0 << '\n';
|
||
return 0;
|
||
}
|
||
|
||
int rem = (1 << (n * n)) - 1;
|
||
dfs(rem);
|
||
|
||
cout << ans << '\n';
|
||
return 0;
|
||
}
|