https://www.acwing.com/problem/content/description/3475/

POJ - 1321 棋盘问题

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=20;

int T,n,u=0; 
int g[N];
vector<int> q;
bool row[N],col[N],dg[N],udg[N];

void dfs(int x,int cnt)
{
	if(cnt==n)
	{
		u++;
		int sum=0;
		for(int i=1;i<=n;i++) sum=sum*10+g[i];
		q.push_back(sum);
		return;
	}
	
	for(int i=x;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(!row[i] && !col[j] && !dg[i+j] && !udg[i-j+n])
			{
				row[i]=col[j]=dg[i+j]=udg[i-j+n]=true;
				g[x]=j;
				
				dfs(x+1,cnt+1);
				
				row[i]=col[j]=dg[i+j]=udg[i-j+n]=false;
			}
		}
	}
	
	return;
}


int main()
{
	n=8;
	dfs(1,0);
//	sort(q.begin(),q.end()); 因为搜索的时候是从1开始搜的，搜不到的时候回溯返回，所以本身就有序 
	
	cin>>T;
	int m;
	while(T--)
	{
		cin>>m;
		cout<<q[m-1]<<"\n";
	}
	
//	cout<<u<<"\n";
	
	return 0;
}