#include <bits/stdc++.h>
using namespace std;
int num = 0;
int a[8][8];
int b[105][8];
int n;
int m;
int notDanger(int x, int y)
{
	int i, j;
	// 判断列方向
	for( i=0; i < 8; i++)
	{
		if( a[i][y]==1)
		{
			return 0;
		}
	}
	// 判断左对角线 
	for( i=x, j=y; i>=0 && j>=0; i--, j--)
	{
		if(a[i][j]==1)
		{
			return 0;
		}
	}
	// 判断右对角线 
	for( i=x, j=y; i>=0 && j<8; i--, j++)
	{
		if(a[i][j]==1)
		{
			return 0;
		}
	}
	return 1;
}

void Print()//打印结果 
{
	int x, y;
	for(x=0; x < 8; x++)
	{
		for(y=0; y < 8; y++)
		{
			if(a[x][y]==1)
			{
				b[num][x]=y;
			}
		}
	}
}

void EightQueen(int x)
{
	int y;
	if(x==8)//如果遍历完八行都找到放置皇后的位置则打印
	{
		Print();//打印八皇后的解 
		num++;
		return;
		
	}
	
	for(y=0; y < 8; y++)//回溯，递归
	{
		if(notDanger(x, y))// 判断是否危险
		{
			a[x][y]=1;//有皇后
			EightQueen(x+1);//回溯
			a[x][y]=0;//清零
		}
	}
}
int main()
{
	EightQueen(0);      
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> m;
		for(int j = 0; j < 8; j++)
		{
			cout << b[m-1][j]+1;
		}
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int num=0,a[8][8],b[105][8],n,m;
int checkr(int x,int y){
	for(int i=0;i<8;i++)if(a[i][y]==1)return false;
	for(int i=x,j=y;i>=0&&j>=0;i--,j--)if(a[i][j]==1)return false;
	for(int i=x,j=y;i>=0&&j<8;i--,j++)if(a[i][j]==1)return false;
	return true;
}
void ppp(int x){
	if(x==8){
		for(int i=0;i<8;i++)for(int j=0;j<8;j++)if(a[i][j]==1)b[num][i]=j;
		num++;
		return;
	}
	for(int i=0;i<8;i++)if(checkr(x,i)){
		a[x][i]=1;
		ppp(x+1);
		a[x][i]=0;
	}
}
int main(){
	ppp(0);      
	cin>>n;
	for(int i =0;i<n;i++){
		cin>>m;
		for(int j=0;j<8;j++)cout<<b[m-1][j]+1;
		cout<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int a[10][10], l[100][10], ans, n, t, p;

bool check(int x, int y) // 判断一下 
{
	for (int i = 1; i <= 8; i++)
		if (a[x][i] || a[i][y])
			return false;
	for (int i = 1; i <= 8; i++)
		for (int j = 1; j <= 8; j++)
			if ((a[i][j] && i + j == x + y) || (a[i][j] && i - j == x - y))
				return false;
	return true;
}

void dfs(int x)
{
	if (x > 8) // 递归出口 
	{
		for (int i = 1; i <= 8; i++)
			for (int j = 1; j <= 8; j++)
				if (a[i][j])
					l[ans][p++] = j; // 进行一堆乱七八糟的赋值 
		ans++, p = 0;
		return; // return出去 
	}
	for (int i = 1; i <= 8; i++)
	{
		if (check(x, i)) // 先判断是否符合dfs的条件，这也可以看作成一种剪枝 
		{
			a[x][i] = 1; 
			dfs(x + 1);  // 深搜 
			a[x][i] = 0; // 回溯 
		}
	}	
}

int main()
{
	dfs(1);
	cin >> n; // 输入n 
	while (n--)
	{
		cin >> t; // 输入t 
		for (int i = 0; i < 8; i++) cout << l[t - 1][i]; // 输出答案 
		cout << endl;
	}
	return 0;
}

AC呆马：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int n;
int x[100000];
int cnt;
int queen[100], a[100];
bool qu[10][10];

bool place(int t)
{
	for(int j = 1; j < t; j++)
	{
		if(x[t] == x[j] || t - j == abs(x[t] - x[j]))
			return false;
	}
	return true;
}

void backtrack(int t)
{
	if(t > n)
	{
		cnt++;
		for(int j = 1; j<= n; j++)
		{
			for(int i = 1; i <= n; i++)
			{
				qu[j][i] = ((x[i] == j) ? 1 : 0);
				if(qu[j][i] == 1)
					queen[cnt] = queen[cnt] * 10 + i;
			}
		}
		return;
	}
	for(int i = 1; i<= n; i++)
	{
		x[t] = i;
		if(place(t))
			backtrack(t+1);
	}
}

int main()
{
	n = 8;
	cnt = 0;
	int m;
	cin >> m;
	for(int i = 1; i <= m; i++)
	{
		cin >> a[i];
	}
	backtrack(1);
	sort(queen + 1, queen + 93);
	for(int i = 1; i <= m; i++)
	{
		cout << queen[a[i]] << endl;;
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;
bool vis[1000010];
int a[1000010];//列 
//int b[1000010];行
//1 0 0 
//0 1 0 
//0 0 1 
bool p(int t1){
	for(int i=1;i<t1;i++){
		// a[t1]==a[i]：判断列是否重复
		//t1-i==abs(a[t1]-a[i]):判断对角线是否相等 
		if(a[t1]==a[i]||t1-i==abs(a[t1]-a[i])){
			return false;
		}
	}
	//因为是升序遍历，所以行不会重复 
//	for(int i=1;i<t2;i++){
//		if(b[t2]==b[i]){
//			return false;
//		}
//	}
	return true;
}
int cnt=0;
void dfs(int u1){//u1为行数 
	if(u1>8){
		cnt++;
//		cout<<"No. "<<cnt<<'\n';
//		for(int i=1;i<=8;i++){
//			for(int j=1;j<=8;j++){
//				if(a[j]==i){//列数是否合适 
//					cout<<1<<" ";
//				}else{
//					cout<<0<<" ";
//				}
//			}
//			cout<<'\n';
//		}
//		cout<<'\n';
		for(int i=1;i<=8;i++){
			k[cnt][i]=a[i];
		} 
		return ;
	}
	for(int j=1;j<=8;j++){
		a[u1]=j;//第u1行j列 
		if(p(u1)){//判断位置是否合理 
			dfs(u1+1);
		}	
	}
}
int main(){
	//int n=8;
	//int cnt=0;
	dfs(1);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=8;i++){
			cout<<k[n][i]<<" ";
		}
	}
	return 0;
} 

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int n;
int x[100000];
int cnt;
int queen[100], a[100];
bool qu[10][10];

bool place(int t)
{
	for(int j = 1; j < t; j++)
	{
		if(x[t] == x[j] || t - j == abs(x[t] - x[j]))
			return false;
	}
	return true;
}

void backtrack(int t)
{
	if(t > n)
	{
		cnt++;
		for(int j = 1; j<= n; j++)
		{
			for(int i = 1; i <= n; i++)
			{
				qu[j][i] = ((x[i] == j) ? 1 : 0);
				if(qu[j][i] == 1)
					queen[cnt] = queen[cnt] * 10 + i;
			}
		}
		return;
	}
	for(int i = 1; i<= n; i++)
	{
		x[t] = i;
		if(place(t))
			backtrack(t+1);
	}
}

int main()
{
	n = 8;
	cnt = 0;
	int m;
	cin >> m;
	for(int i = 1; i <= m; i++)
	{
		cin >> a[i];
	}
	backtrack(1);
	sort(queen + 1, queen + 93);
	for(int i = 1; i <= m; i++)
	{
		cout << queen[a[i]] << endl;;
	}
	return 0;
}