#include <stdio.h>
#include <time.h>
#define C_LIM 6
#define R_LIM 6
int adj[8]={-9,-8,-7,-1,1,7,8,9};
unsigned long flags[64];
unsigned long bit[37];
int grid[64],preset[37];
int count;
void update_flags(int pos,int val);
void recur(int val);
void print_grid();
void set(int row,int col,int val){
int i,pos;
pos=(row<<3)|col;
grid[pos]=val;
preset[val]=pos;
//update_flags(pos,val);
for(i=0;i!=8;++i)flags[pos+adj[i]]^=bit[val];
}
int main()
{
unsigned long b=1;
time_t t0,t1;
int i,r,c;
for(i=0;i<37;++i)bit[i]=b<<i;
//set(row,col,val)
set(1,2,7);
set(3,3,18);
t0=time(NULL);
recur(1);
t1=time(NULL);
printf("%d %ld\n",count,t1-t0);
return 0;
}
void update_flags(int pos,int val){
for(int i=0;i!=8;++i)
flags[pos+adj[i]]^=bit[val];
}
void recur(int val){
unsigned long u;
int i,j,r,c;
if(val<3){
if(preset[val])recur(val+1);
else{
for(r=6;--r;)
for(c=6;--c;){
i=(r<<3)|c;
if(grid[i])continue;
grid[i]=val;
for(j=8;j--;)flags[i+adj[j]]^=bit[val];
recur(val+1);
for(j=8;j--;)flags[i+adj[j]]^=bit[val];
grid[i]=0;
}
}
return;
}
if(val==26){
++count;
print_grid();
return;
}
if(preset[val]){
for(j=1;j+j<val;++j){
u=bit[j]|bit[val-j];
if((flags[preset[val]]&u)==u)break;
}
if(j+j<val)recur(val+1);
return;
}
for(r=6;--r;)
for(c=6;--c;){
i=(r<<3)|c;
if(grid[i])continue;
for(j=1;j+j<val;++j){
u=bit[j]|bit[val-j];
if((flags[i]&u)==u)break;
}
if(j+j<val){
grid[i]=val;
for(j=8;j--;)flags[i+adj[j]]^=bit[val];
recur(val+1);
for(j=8;j--;)flags[i+adj[j]]^=bit[val];
grid[i]=0;
}
}
}
void print_grid(){
int i,c,r;
//printf("$$\\begin{array}{|c|c|c|c|c|}\\hline ");
for(r=1;r<6;++r){
for(c=1;c<6;++c){
i=(r<<3)|c;
printf("%02d%c",grid[i],c==5?'\n':' ');
//printf("%d%s",grid[i],c==5?" \\\\ \\hline ":" & ");
}
}
//printf("\\end{array}$$\n");
}