// Author: Manfred Scheucher // Date : 12.06.2015 #include <assert.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #define MAXN 16 #define ATTACKS 1 int queenx[MAXN]; // x coordinate int queeny[MAXN]; // y coordinate int queena[MAXN][MAXN]; // after i iterations queen j is attacked by queena[i][j] queens char field[MAXN][MAXN]; char field1[MAXN][MAXN]; char field2[MAXN][MAXN]; long ct = 0; int n,N; inline int to_field() { int x,y; for(y=0;y<n;y++) { for(x=0;x<n;x++) { field[x][y]='.'; } } for(x=0;x<N;x++) { field[queenx[x]][queeny[x]]='X'; } } inline int print() { int x,y; to_field(); for(y=0;y<n;y++) { for(x=0;x<n;x++) { printf("%c ",field[x][y]); } printf("\n"); } printf("\n"); } inline int flip() { int x,y; for(y=0;y<n;y++) { for(x=0;x<n;x++) { field2[y][x] = field1[x][y]; } } } inline int rot() { int x,y; for(y=0;y<n;y++) { for(x=0;x<n;x++) { field2[n-1-y][x] = field1[x][y]; } } } inline int cmp() { int x,y; for(y=0;y<n;y++) { for(x=0;x<n;x++) { if(field[x][y] < field1[x][y]) return 1; if(field[x][y] > field1[x][y]) return 0; } } return 0; } inline int islexmin() { to_field(); memcpy(field1,field,MAXN*MAXN*sizeof(char)); // rot 90 rot(); memcpy(field1,field2,MAXN*MAXN*sizeof(char)); if(cmp()) return 0; // rot 180 rot(); memcpy(field1,field2,MAXN*MAXN*sizeof(char)); if(cmp()) return 0; // rot 270 rot(); memcpy(field1,field2,MAXN*MAXN*sizeof(char)); if(cmp()) return 0; // mirrored 0 memcpy(field1,field,MAXN*MAXN*sizeof(char)); flip(); memcpy(field1,field2,MAXN*MAXN*sizeof(char)); if(cmp()) return 0; // mirrored 90 rot(); memcpy(field1,field2,MAXN*MAXN*sizeof(char)); if(cmp()) return 0; // mirrored 180 rot(); memcpy(field1,field2,MAXN*MAXN*sizeof(char)); if(cmp()) return 0; // mirrored 270 rot(); memcpy(field1,field2,MAXN*MAXN*sizeof(char)); if(cmp()) return 0; return 1; } inline int valid(int k) { int i, prev, dx, dy; queena[k][k] = 0; for(i=0;i<k;i++) { queena[k][i] = queena[k-1][i]; dx = queenx[i]-queenx[k]; dy = queeny[i]-queeny[k]; if( dx == 0 || dy == 0 || dx == dy || dx == -dy) { queena[k][i]++; queena[k][k]++; if(queena[k][i]>ATTACKS || queena[k][k]>ATTACKS) return 0; } if(k==N-1 && queena[k][i]!=ATTACKS) return 0; } if(k==N-1 && queena[k][k]!=ATTACKS) return 0; return 1; } int place(int k) { int x,y; if(k==N && islexmin()) { ct++; print(); } else { for(y=0;y<n;y++) { for(x=0;x<n;x++) { if(k>0 && (y<queeny[k-1] || (y==queeny[k-1] && x<=queenx[k-1]))) continue; queenx[k]=x; queeny[k]=y; if(!valid(k)) continue; place(k+1); } } } } int main(int argc,char** argv) { n = atoi(argv[1]); N = 2*((2*n)/3); assert(n<MAXN); assert(N<MAXN); place(0); printf("%dx%d grid, %d queens, %ld solutions\n",n,n,N,ct); return 42; }