//8QUEEN
#include <stdio.h>

#define MAXSIZE 8
#define TRUE  1
#define FALSE 0

int board[MAXSIZE];
int r_used[MAXSIZE * 2 - 1];
int l_used[MAXSIZE * 2 - 1];
int size;
int count;

int b[MAXSIZE+1][MAXSIZE+1];

/* 解法 */
void queen2( int n )
{
   int i;
   if( n == size ){
       count++;
   } else {
       for( i = n; i < size; i++ ){
           int m = board[i];
           /* 斜めの利き筋をチェック */
           if( r_used[m + n] || l_used[m - n + size - 1] ) continue;
           r_used[m + n] = l_used[m - n + size - 1] = TRUE;
           /* 未使用の数字（クイーン）と交換する */
           board[i] = board[n];
           board[n] = m;
           /* 再帰する */
           queen2( n + 1 );
           /* 元に戻す */
           r_used[m + n] = l_used[m - n + size - 1] = FALSE;
           board[n] = board[i];
           board[i] = m;
       }
   }
}

void queen(int i, int j)
{
   int p,q;
   // 横方向チェック、置かれてたら戻る
   for(q=j-1; q>=1; q--){
       if(b[i][q]==1){
           return;
       }
   }
   //斜め上方向チェック、置かれてたら戻る
   p=i-1; q=j-1;
   while( (p>=1)&&(q>=1) ){
       if(b[p][q]==1){
           return;
       }
       p--; q--;
   }
   //斜め下方向チェック、置かれてたら戻る
   p=i+1; q=j-1;
   while ( (p<=size)&&(q>=1) ) {
       if(b[p][q]==1){
           return;
       }
       p++; q--;
   }
   //他のクイーンがないので置く
   b[i][j]=1;
   if(j==size){
       count++; printf("[%d]\n", count);
       for(p=1; p<=size; p++){
           for(q=1; q<=size; q++){
               printf("%3d", b[p][q]);
           }
           printf("\n");
       }
   }else{//右下の升目を調べる
       for (p=size; p>=1; p--) {
           queen(p, j+1);
       }
   }
   b[i][j]=0;
}            
       
int main()
{
   int i,j;
   int start;
   
   // 盤面のサイズ（最大8）
   size=4;

   // 初期化
   for(i=1; i<=size; i++){
       for(j=1; j<=size; j++){
           b[i][j]=0;
       }
   }
   count=0;
   queen(size,0);
   
   /* データの初期化 */
   for( i = 0; i < size; i++ ){
       board[i] = i;
   }
   for( i = 0; i < size * 2 - 1; i++ ){
       r_used[i] = l_used[i] = FALSE;
   }
   count = 0;
   queen2( 0 );

   return 0;
}