include<cstdio>
include<stdio.h>
int queenPlaces[92][8];
int count = 0;
int board[8][8];
int putQueen(int ithQueen);
int ab(int n)
{
return n > 0 ? n : -n;
}
int main(){
int n, i, j;
for(i = 0; i < 8; i++)
{
for(j = 0; j < 8; j++)
board[i][j] = -1;
for(j = 0; j < 92; ++j) //一共九十二种算法
queenPlaces[j][i] = 0; //棋盘的初始化
}
putQueen(0);
scanf("%d",&n);
for(i = 0; i < n; ++i)
{
int ith;
scanf("%d",&ith);
for(j = 0;j < 8; ++j)
printf("%d",queenPlaces[ith-1][j]);
printf("\n");
}
return 0;
}
int putQueen(int ithQueen) //找到一组解，退出函数
{
int i, k, r;
if(ithQueen == 8)
{
count++;
return 0;
}
for( i =0;i < 8; i++){
if(board[i][ithQueen] == -1){
board[i][ithQueen] = ithQueen; //找到-1 可以摆皇后
for(k = count; k < 92; k++)
{
queenPlaces[k][ithQueen] = i + 1;
}
for( k = 0; k < 8; ++k)
for( r = 0; r < 8; r++) //当board[k][r] == -1 行列斜的时候 ，
if(board[k][r] == -1 &&(k ==i||r==ithQueen||ab(k-i)==ab(r-ithQueen)))
board[k][r] = ithQueen;
putQueen(ithQueen + 1); //递归
//back trace
for(k = 0; k < 8; ++k) //回溯算法体现
for(r = 0; r < 8; r++)
if(board[k][r] == ithQueen)
board[k][r] = -1;
}
}
}
