/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include <stdio.h>
int max_rotation(int board[]);
void stage_two(int board[],int threat[],int q[]);
int main()
{
// board[64] is used to print solutions
// threat[64] is used to indicate which square are threatened
// stores the value of first queen to threaten specific square
// q[15] are the queens, value indicates where each is located
int board[64],threat[64],q[15];
int i,n,safe; // counter variable, index to queens array,
// 'safe' is count of remaining non-threatened squares
// these non-threatened square will be occupied by the last army
// (no need to search for those positions)
int x,y,x1,y1;//grid coordinates
//initialize arrays
for(i=0;i<64;i++){board[i]=0;threat[i]=0;}
n=1; // first queen
q[n]=0;// at position 0
for(;;){
// while current position is not allowed, move to next position
while(threat[q[n]]<0)if(++q[n]==64)break;
if(q[n]<64){ // if current position is on the board
board[q[n]]=1; // '1' indicates a queen of the first army ('x')
x=q[n]%8;y=q[n]/8;// grid coordinates of current position
for(i=0,safe=0;i<64;i++){ // loop to update threatened squares
x1=i%8;y1=i/8; // grid coordinates of test position
if(threat[i]==0){ // if test position not already threatened
// if test position threatened by current queen:
if(x==x1||y==y1||x-x1==y-y1||x-x1==y1-y)threat[i]=n;
else safe++; // count non-threatened squares
}
}
// if we have 5 queens in first army and enough safe squares
if(n==5 && safe>8){ // to hold remaining armies
// max_rotation avoids repeated searches
// stage_two places queens of second army
if(max_rotation(board)==1)stage_two(board,threat,q);
}else if(n<5 && safe>8){ // condition for continuing
q[n+1]=q[n]+1; // next queen starts in next position
n++; // advance index to next queen
continue;
}
}else{
// if queen n is off the board, return to previous queen
if(--n==0)break; // if first queen is off the board, we're done
}
for(;;){
// before moving queen, clear all squares
// first threatened by the current queen
for(i=0;i<64;i++)if(threat[i]==n)threat[i]=0;
board[q[n]]=0; // '0' is vacant square
if(n==1){ // if the first queen is moving
// mark this position and all rotations/reflections
// as forbidden to avoid most repeated positions
x=q[n]%8;y=q[n]/8;
threat[8*y+x]=-1;
threat[8*x+y]=-1;
threat[8*y+7-x]=-1;
threat[8*x+7-y]=-1;
threat[8*(7-y)+x]=-1;
threat[8*(7-x)+y]=-1;
threat[8*(7-y)+7-x]=-1;
threat[8*(7-x)+7-y]=-1;
}
// if more positions available for current queen,
if(++q[n]<64)break; // return to outer loop
// no more positions, return to previous queen
if(--n==0)break; // return to outer loop if no more queens
}
if(n==0)break; // in no queens, we're done
}
return 0;
}
void stage_two(int board[],int threat[],int q[])
{
static int k=0; // counts number of solutions found (some may be repeated)
int i,n,safe; // same as before
int x,y,x1,y1;
n=6;q[n]=0; // first army has 5 queens, start this army with 6th queen
for(;;){
// while current position is threatened by first army
while(threat[q[n]]!=0 && threat[q[n]]<6)if(++q[n]==64)break;
if(q[n]<64){
board[q[n]]=2; // '2' indicates second army ('o')
x=q[n]%8;y=q[n]/8;
for(i=0,safe=0;i<64;i++){
x1=i%8;y1=i/8;
if(threat[i]==0){
if(x==x1||y==y1||x-x1==y-y1||x-x1==y1-y)threat[i]=n;
else safe++;
}
}
// if 5 queens in second army and at least
if(n==10 && safe>3){ // 4 safe squares for third army
k++;
printf("(%d) %d %d\n",k,n,safe);
for(i=0;i<64;i++){
if(threat[i]==0)board[i]=3; // safe squares = third army ('#')
switch(board[i]){
case 0:printf(". ");break;
case 1:printf("x ");break;
case 2:printf("o ");break;
case 3:printf("# ");break;
}
if(i%8==7)printf("\n");
if(board[i]==3)board[i]=0; // remove third army
}
printf("\n");
}else if(n<10 && safe>3){
q[n+1]=q[n]+1;
n++;
continue;
}
}else{
if(--n==5)break;
}
for(;;){
for(i=0;i<64;i++)if(threat[i]==n)threat[i]=0;
board[q[n]]=0;
if(++q[n]<64)break;
if(--n==5)break;
}
if(n==5)break;
}
if(k>1000)for(i=0;i<64;i++)threat[i]=-1;
}
int max_rotation(int board[])
{
unsigned long boardbits[8]={0,0,0,0,0,0,0,0};
unsigned long currentbit;
int i,x,y;
currentbit=1;
currentbit<<=63;
for(i=0;i<64;i++){
x=i%8;y=i/8;
if(board[8*y+x]==1)boardbits[0]|=currentbit;
if(board[8*x+y]==1)boardbits[1]|=currentbit;
if(board[8*y+7-x]==1)boardbits[2]|=currentbit;
if(board[8*x+7-y]==1)boardbits[3]|=currentbit;
if(board[8*(7-y)+x]==1)boardbits[4]|=currentbit;
if(board[8*(7-x)+y]==1)boardbits[5]|=currentbit;
if(board[8*(7-y)+7-x]==1)boardbits[6]|=currentbit;
if(board[8*(7-x)+7-y]==1)boardbits[7]|=currentbit;
currentbit>>=1;
}
for(i=1;i<8;i++)if(boardbits[i]>boardbits[0])return 0;
return 1;
}