#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int n; // MAX = 16
int solution_count = 0;
int solution_count_half = 0;
int solution_count_center = 0;
uint32_t col=0, asc=0, desc=0;
bool bCenter=false;
void backtrack(int i)
{
int max = n;
if (i==0) max = (n+1)/2;
if(i == n) {
if (bCenter)
solution_count_center++;
else
solution_count_half++;
return;
}
uint32_t mc, md, ma;
for(int j=0; j != max; j++) {
if (i==0 && (n%2)==1 && j==max-1)
bCenter=true;
if (col & (mc = 1<<j)) continue;
if (desc & (md = 1 << (i+j))) continue;
if (asc & (ma = 1 << (15+i-j))) continue;
uint32_t oldc = col, oldd = desc, olda = asc;
col |= mc;
desc |= md;
asc |= ma;
backtrack(i+1);
col = oldc;
desc = oldd;
asc = olda;
}
}
int main()
{
n=14;
backtrack(0);
if (n % 2 == 0)
solution_count = solution_count_half * 2;
else
solution_count = solution_count_half * 2 + solution_count_center;
printf("%d\n", solution_count);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGludC5oPgoKaW50IG47CS8vIE1BWCA9IDE2CmludCBzb2x1dGlvbl9jb3VudCA9IDA7CmludCBzb2x1dGlvbl9jb3VudF9oYWxmID0gMDsKaW50IHNvbHV0aW9uX2NvdW50X2NlbnRlciA9IDA7CnVpbnQzMl90IGNvbD0wLCBhc2M9MCwgZGVzYz0wOwoKCmJvb2wgYkNlbnRlcj1mYWxzZTsKdm9pZCBiYWNrdHJhY2soaW50IGkpIAp7CglpbnQgbWF4ID0gbjsKCWlmIChpPT0wKSBtYXggPSAobisxKS8yOwoKICAgIGlmKGkgPT0gbikgewoJCWlmIChiQ2VudGVyKQoJCQlzb2x1dGlvbl9jb3VudF9jZW50ZXIrKzsKCQllbHNlCgkgICAgICAgIHNvbHV0aW9uX2NvdW50X2hhbGYrKzsKICAgICAgICByZXR1cm47CiAgICB9CiAgICB1aW50MzJfdCBtYywgbWQsIG1hOwogICAgZm9yKGludCBqPTA7IGogIT0gbWF4OyBqKyspIHsKCQlpZiAoaT09MCAmJiAobiUyKT09MSAmJiBqPT1tYXgtMSkKCQkJYkNlbnRlcj10cnVlOwogICAgCWlmIChjb2wgJiAobWMgPSAxPDxqKSkgY29udGludWU7CiAgICAJaWYgKGRlc2MgJiAobWQgPSAxIDw8IChpK2opKSkgY29udGludWU7CiAgICAJaWYgKGFzYyAmIChtYSA9IDEgPDwgKDE1K2ktaikpKSBjb250aW51ZTsKICAgIAl1aW50MzJfdCBvbGRjID0gY29sLCBvbGRkID0gZGVzYywgb2xkYSA9IGFzYzsKICAgICAgICBjb2wgfD0gbWM7CiAgICAgICAgZGVzYyB8PSBtZDsKICAgICAgICBhc2MgfD0gbWE7CiAgICAgICAgYmFja3RyYWNrKGkrMSk7CiAgICAgICAgY29sID0gb2xkYzsKICAgICAgICBkZXNjID0gb2xkZDsKICAgICAgICBhc2MgPSBvbGRhOwogICAgfQp9CgppbnQgbWFpbigpIAp7IAoJbj0xNDsKCgliYWNrdHJhY2soMCk7CglpZiAobiAlIDIgPT0gMCkKCQlzb2x1dGlvbl9jb3VudCA9IHNvbHV0aW9uX2NvdW50X2hhbGYgKiAyOwoJZWxzZQoJCXNvbHV0aW9uX2NvdW50ID0gc29sdXRpb25fY291bnRfaGFsZiAqIDIgKyBzb2x1dGlvbl9jb3VudF9jZW50ZXI7CglwcmludGYoIiVkXG4iLCBzb2x1dGlvbl9jb3VudCk7CgoJcmV0dXJuIDA7Cn0K