八皇后

#include<bits/stdc++.h>
using namespace std;
int cb[9][9];
set<string> s;
string str;
int judge(int x,int y){
    for(int i=1;i<=8;i++)if(cb[i][y]==1)return 0;
    for(int i=1;i<=8;i++)if(cb[x][i]==1)return 0;
    for(int i=1;i<min(x,y);i++)if(cb[x-i][y-i]==1)return 0;
    for(int i=1;i<x&&y+i<9;i++)if(cb[x-i][y+i]==1)return 0;
    return 1;
}
void init(int x){
    if(str.size()==8){
        s.insert(str);
        return;
    }
    if(x>8)return;
    for(int i=1;i<9;i++){
        int tmp=judge(x,i);
        if(tmp==1){
            cb[x][i]=1;
            char ch=i+'0';
            str+=ch;
            init(x+1);
            cb[x][i]=0;str.pop_back();
        }
    }
}
int main(){
    init(1);
    int index;
    while(cin>>index){
        int cnt=1;
        for(auto iter=s.begin();iter!=s.end();iter++,cnt++)if(cnt==index){cout<<*iter<<endl;break;}
    }
    return 0;
}

//这是一道典型的DFS回溯题目
//注意削枝即可
#include<stdio.h>
#include<algorithm>
using namespace std;
int ans[92];//定义解空间  
int a[8];//定义临时解；
bool pan[8][8]; //定义棋盘
int flag=0;  //标记个数
bool panduan(int x,int i)
{
    for(int j=0;j<x;j++)
        for(int k=0;k<8;k++)
            if(pan[j][k]&&(k==i||k==i-(x-j)||k==i+(x-j)))  //判断是否可以放置
                return false;
    return true;
}
int translate(int a[])  //此数组转换成一个十进制数
{
    int count=0;
    for(int i=0;i<8;i++)
    {
        count*=10;
        count+=a[i];
    }
    return count;
}
void DFS(int x)
{
    if(x==8)
    {
        ans[flag++]=translate(a);  //如果到底了 那么放入数组
        return;
    }
    for(int i=0;i<8;i++)          //如果还可以放，寻找可以放的
    {
        if(panduan(x,i))
        {
            pan[x][i]=true; //代表放子
            a[x]=i+1;
            DFS(x+1);
            pan[x][i]=false;
        }
    }
}
int main()
{
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            pan[i][j]=false;  //初试化棋盘
    DFS(0);  //从零开始递归
    sort(ans,ans+92);  //排序，因为要输出
    int n;
    while(~scanf("%d",&n))
    {
        printf("%d\n",ans[n-1]);  //注意题目给的n在数组中是n-1
    }
}

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

int visit1[100],visit2[100],visit3[100];
int number[9];
vector<int> allAnswer;

void dfs(int row)
{
    if(row == 9)
    {
        int answer=0;//忘记初始化为0了
        for(int i=1; i<=8; i++)
        {
            answer += number[i] * pow(10,8-i);
        }
        allAnswer.push_back(answer);
        return;
    }
    for(int i=1; i<=8; i++)
    {
        if(!visit1[i] && !visit2[row+i] && !visit3[row-i+8])
        {
            visit1[i] = 1;
            visit2[row+i] = 1;
            visit3[row-i+8] = 1;
            number[row] = i;
            dfs(row+1);
            visit1[i] = 0;
            visit2[row+i] = 0;
            visit3[row-i+8] = 0;
        }
    }
    return;
}

int main()
{
    dfs(1);
    sort(allAnswer.begin(),allAnswer.end());
    int n;
    while(scanf("%d",&n) != EOF)
    {
        printf("%d\n",allAnswer[n-1]);//忘记n-1了
    }
    return 0;
}

#include <stdio.h>

int DFS(int row, int col[], int ans[][8], int len){
    for(int i=0; i<8; i++){	            // 遍历当前行的每一列
        int flag = 1;                   // 标记当前列是否满足条件
        for(int j=0; j<row; j++){       // 遍历前面行的确定的列号
            int dis = row-j;            // 前面行与当前行的距离
            if((col[j]+dis)==i || (col[j]-dis)==i || col[j]==i){ // 是否在同一列或同一斜线上
                flag=0;
                break;
            }
        }
        if(flag){
            col[row] = i;
            ans[len][row] = i+1;
            if(row+1==8){
                for(int j=0; j<8; j++)
                    ans[len+1][j] = ans[len][j];
                len++;
            }
            else
                len = DFS(row+1, col, ans, len);
        }
    }
    return len;
}

int main(){
    int n;
    int col[8];         // 已确定列号
    int ans[93][8];     // 满足条件的序列
    int len = 0;        // 序列个数
    len = DFS(0, col, ans, len);
    while(scanf("%d", &n)!=EOF){
        for(int j=0; j<8; j++)
            printf("%d", ans[n-1][j]);
        printf("\n");
    }
    return 0;
}

/*
*
*打表所有的皇后列序列，然后输出，关键是打表序列的存储方式。
*/


#include<bits/stdc++.h>

using namespace std;

const int NUM = 8;
const int maxn = 1e2;
vector<string> v;  //存储每次的皇后序列  因为搜索的过程就是字典序的 所以生成的序列也是字典序的
string a;
bool vis[3][20]; //一位分别表示  同一列 同一个主对角线  同一个副对角线  是否有皇后了
int n;

void DFS_CUT(int cur)     //剪枝搜索 打表
{
    if(cur == NUM)
    {
        v.push_back(a); return ;
    }
    else for(int i = 0;i < NUM; i++)
    {
        if(!vis[0][i] && !vis[1][i+cur] && !vis[2][i-cur+NUM])   //剪枝判断
        {
            a[cur] = i+1+'0';
            vis[0][i] = vis[1][i+cur] = vis[2][i-cur+NUM] = true;
            DFS_CUT(cur+1);
            vis[0][i] = vis[1][i+cur] = vis[2][i-cur+NUM] = false;  //回溯
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    memset(vis, false, sizeof(vis));
    a = string(NUM, ' ');     //拿string做数组用存每次的皇后列序列  所以必须事先开辟空间
    DFS_CUT(0);               //貌似vector里不能放数组  所以放的string
    while(cin >> n)
    {
        cout << v[n-1] << "\n";
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector<int> vt;
int p[9];
bool h[9]= {false};
void solve(int index) {
	if(index==9) {
		int temp=0;
		for(int i=1; i<=8; i++)
			temp=temp*10+p[i];
		vt.push_back(temp);
		return;
	}
	for(int x=1; x<=8; x++) {
		if(h[x]==false) {
			bool tag=true;
			for(int pre=1; pre<index; pre++) {
				if(abs(index-pre)==abs(x-p[pre])) {
					tag=false;
					break;
				}
			}
			if(tag==true) {
				p[index]=x;
				h[x]=true;
				solve(index+1);
				h[x]=false;
			}
		}
	}
}
int main() {
	int n,t;
	solve(1);
	while(cin>>n) {
		cout<<vt[n-1]<<endl;
	}
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<string> vec;
int q_rank[8]; //第行的皇后所在的列

bool is_valide(const int& row,const int& rank){  //row行 rank列是否合法
	if(row==0)
		return true;
	for(int i=0;i<row;i++){
		if(rank == q_rank[i])
			return false;
		if(row + rank ==i + q_rank[i])
			return false;
		if(row - rank == i- q_rank[i])
			return false;
	}
	return true;
}

string to_string(){ //把q_rank转换为string
	string str;
	for(auto a:q_rank)
		str += to_string(a+1);

	return str;
}
void dfs(int row,int rank){
	if(is_valide(row,rank))
	{
		q_rank[row] = rank;
		if(row == 7){
			vec.push_back(to_string());
			return;
		}else
			for(int i=0;i<8;i++)
				dfs(row+1,i);
	}
	return ;
}

inline void eight_queen(){ //八皇后问题入口
	for(int i=0;i<8;i++) //0行的0到7列依此开始深度优先遍历
		dfs(0,i);
}

int main(){
	eight_queen();
	int n=6;
	while(cin>>n && n<=92){
		cout<<vec[n-1]<<endl;
	}
	return 0;
}

#include <stdio.h>

int rst[92][8];
int idx=0;
int C[8];
void search(int cur)
{//递归回溯
    if(cur == 8)
    {
        for(int i=0;i<8;i++)
        {
            rst[idx][i]=C[i];
        }
        idx++;
    }
    else
    {
        for(int i=1;i<=8;i++)
        {
            int ok=1;
            C[cur]=i;
            for(int j=0;j<cur;j++)
            {
                if(C[cur] == C[j] ||C[cur]+cur == C[j]+j || C[cur] - cur == C[j] - j)
                {
                    ok =0;
                    break;
                }
            }
            if(ok)
                search(cur+1);
        }
    }
}
int main()
{
    int b;
    search(0);
    while(scanf("%d",&b)!=EOF)
    {
        for(int i=0;i<8;i++)
            printf("%d",rst[b-1][i]);
        printf("\n");
    }
    return 0;
}

	

#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
int board[8][8];//棋盘
int pos[9]; //存储每一行放置的棋子位置
long temp=0;


vector<int> res; //存放最终的92组解
bool check(int xi,int xj){ //遍历棋盘上已经放的子 判断是否与（i,j）同列 同对角线
    for(int i=0;i<xi;i++){
        for(int j=0;j<8;j++){
            if((board[i][j]==1)&&(j==xj||abs(i-xi)==abs(j-xj)))
                return false;
        }
    }
    return true;
}

void DFS(int row){
    if(row==8){  
        temp=0;
        for(int i=1;i<=8;i++) //将pos[1]...pos[8]拼接到一起
            temp+=pos[i]*pow(10,8-i);
        res.push_back(temp);
        return;

    }
    for(int col=0;col<8;col++){
        if(check(row,col))
        {  
         pos[row+1]=col+1; //第1行 第2行 第3行 ..第8行 序号从1开始
         board[row][col]=1;
         DFS(row+1);
         board[row][col]=0;
        }

    }

}


int main(){
    int n;

        for(int i=0;i<8;i++)
            for(int j=0;j<8;j++){
                board[i][j]=0;
            }

        DFS(0); //row从0开始，执行DFS(7)后得到一个结果，然后row=8

        sort(res.begin(),res.end());
        while(scanf("%d",&n)!=EOF)
            printf("%d\n",res[n-1]);
    }

递归求出符合要求的串，思路比较清晰

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

bool isOK(string queen)  //判断一个串各皇后位置是否冲突
{
    for (int i = 0; i < queen.size(); i++)
    {
        for (int j = i + 1; j < queen.size(); j++)
        {
            if (j - i == (queen[j] - '0') - (queen[i] - '0') || j - i == (queen[i] - '0') - (queen[j] - '0'))
                return false;
        }
    }
    return true;
}

void getQueen(string queen, int begin, vector<string>& queen_list)  //求一个串排除皇后位置冲突后的全排列
{
    if (begin == queen.size() - 1  && isOK(queen)) queen_list.push_back(queen);
    for (int i = begin; i < queen.size(); i++)
    {
        if (i != begin && queen[i] == queen[begin]) continue;
        swap(queen[begin], queen[i]);
        getQueen(queen, begin + 1, queen_list);
        swap(queen[begin], queen[i]);
    }
}

int main()
{
    vector<string> res;
    string queen = "12345678";
    getQueen(queen, 0, res);
    sort(res.begin(), res.end());
    int b;
    while (cin >> b)
    {
        int sum = 0, len = res[b - 1].size() - 1;
        for (int i = 0; i <= len; i++) 
            sum += (res[b - 1][len - i] - '0') * pow(10, i);
        cout << sum << endl;
    }
    system("pause");
    return 0;
}

def findAllResult(row):
    global results                  
    global tempPos
    if row == 9:
        tmp = ""
        for i in range(1,9):
            tmp += str(tempPos[i])
        results.append(tmp)
    else:
        for i in range(1,9):           #这个循环是寻找放在当前行row的合适皇后位置
            tempPos[row] = i
            flag = True
            for j in range(1,row):     #检查是否不在同一列或者斜线上
                if tempPos[row] == tempPos[j] or row - j == abs(tempPos[row] - tempPos[j]):
                    flag = False
                    break
            if flag:                   #如果放在该行位置不影响前面行的皇后则寻找下一行
                findAllResult(row+1)   #走到最后又会回来这里继续for循环
while True:
    try:
        num = int(input())
        results = []                   #保存着全部92种结果
        tempPos = list(range(9))       #临时存放着每一行皇后的位置
        findAllResult(1)
        results.sort()
        print(results[num-1])
    except Exception:
        break

Object C

#include<stdio.h>
#include<string.h>
int cnt, num, flag;
int ans[9], vis[9];
int abs(int x){
    return x > 0 ? x : -x;
}
int check(int cur){
    int i, j;
    for(i = 1; i<cur; i++){
        for(j = i+1; j<cur; j++)
            if(abs(ans[i]-ans[j]) == abs(i-j)) return 0;
    }
    return 1;
}
void dfs(int cur){
    int i;
    if(flag == 1) return ;
    if(!check(cur)) return ;
    if(cur == 9){
        num++;
        if(num == cnt){
            for(i = 1; i<9; i++)
                printf("%d", ans[i]);
            printf("\n");
            flag = 1;
        }
    }
    for(i = 1; i<9; i++)
        if(!vis[i]){
            vis[i] = 1;
            ans[cur] = i;
            dfs(cur+1);
            vis[i] = 0;
        }
}
int main(){

    while(~scanf("%d", &cnt)){
        num = 0, flag = 0;
        memset(vis, 0, sizeof vis);
        dfs(1);
    }
    return 0;    
}

#include <stdio.h>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

struct E{
    string s;
}list[100];
int loc;//list中已经存储的字符串数量
queue<string> Q;//用于BFS的队列
map<string, int> M;//标记某字符串是否曾经出现过

string Swap(string s, int i)//将s的i位与i+1位交换，生成新的字符串
{
    string newStr=s;
    char c=newStr[i];
    newStr[i]=newStr[i+1];
    newStr[i+1]=c;
    return newStr;
}

bool Judge(string s)
{//判断一个字符串是否是皇后串
    map<int, int> M1;//记录某个横纵坐标差是否出现过
    map<int, int> M2;//记录某个横纵坐标和是否出现过
    M1.clear();
    M2.clear();
    for(unsigned i=0; i<s.size(); i++)
    {//每个横纵坐标和只能出现一次，差也是
        int t1=(s[i]-'0')-i;
        int t2=(s[i]-'0')+i;
        if(M1.find(t1)!=M1.end()) return false;
        else M1[t1]=1;
        if(M2.find(t2)!=M2.end()) return false;
        else M2[t2]=1;
    }
    return true;
}

void BFS(string s)
{//从s出发，进行BFS。发现皇后串就记录在list里面
    while(!Q.empty()) Q.pop();//清空队列
    M.clear();//清空map
    Q.push(s);//把起点s塞进队列
    M[s]=1;//标记s出现过了
    while(!Q.empty())
    {
        s=Q.front();//队首出队，记在s里
        Q.pop();
        if(Judge(s)==true) list[loc++].s=s;//是皇后串的话就记下来
        for(unsigned i=0; i<s.size()-1; i++)
        {
            string newStr=Swap(s, i);//生成新的字符串
            if(M.find(newStr)==M.end())//该串没出现过的话
            {
                Q.push(newStr);//加入队列
                M[newStr]=1;//标记为"出现过"
            }
        }
    }
}

bool cmp(E a, E b)//排序规则，字典序升序
{
    return a.s<b.s;
}

int main()
{
    int n;
    loc=0;//清空皇后串列表
    BFS("12345678");//从"12345678"为起点开始BFS
    sort(list, list+loc, cmp);//按字典序升序排列
    while(scanf("%d", &n)!=EOF)
    {
        if(n<=0) break;
        cout<<list[n-1].s<<endl;//输出对应结果
    }
    return 0;//大功告成
}

#include<cstdio>
#include<cstring>
#include<algorithm> //利用algorithm下的next_permutation产生全排列
bool checkQueen(int *qList) { //验证一个排列是不是正确解 
    int i, j;
    for (i=0; i<7; ++i) //因数组中各个皇后行列数已不同，故只需看在不在斜线上 
        for (j=i+1; j<8; ++j) //遍历下面各行的皇后，看是否符合 
            if (j-i == abs(qList[j] - qList[i])) //在斜线上 
                return false; //两个皇后在斜线上可以互相攻击，不符合 
    return true;
}
int main() {
    int b, qList[] = {1, 2, 3, 4, 5, 6, 7, 8}, all_qList[92][8], i=0;
    while (i < 92) { //空间换时间，先把92个解全找出来
        if (checkQueen(qList))
            memcpy(all_qList[i++], qList, 8*sizeof(int));
        std::next_permutation(qList, qList+8); //变为全排列中的下一个 
    }
    while (scanf("%d", &b) != EOF)
        for (i=0; i<8; ++i)
            printf("%d%s", all_qList[b-1][i], i==7 ? "\n" : "");
    return 0;
}

//八皇后
#include<stdio.h>
#define MAXN 8
int cnt =0;
int num_arr[92][8];
int chess_board[8][8];
void display(){
	for(int row=0;row<MAXN;row++){
		for(int col=0;col<MAXN;++col){
			if(chess_board[row][col])num_arr[cnt][row]=col+1;
		}
	}
}
void show(int num){
    for(int i =0;i<MAXN;i++){
        printf("%d",num_arr[num][i]);        
    }
    printf("\n");
}
int avail_place(int row,int col)
{
	int k;
	for(k=0;k<MAXN;k++){
		if((chess_board[row][k] && k!=col)||(chess_board[k][col] && k!=row))return 0;
	}
	for(k=0;row-k>=0 && col-k>=0;k++)if(chess_board[row-k][col-k])return 0;
	for(k=0;row-k>=0 && col+k<MAXN;k++)if(chess_board[row-k][col+k])return 0;
	for(k=0;row+k<MAXN && col-k>=0;k++)if(chess_board[row+k][col-k])return 0;
	for(k=0;row+k<MAXN && col+k<MAXN;k++)if(chess_board[row+k][col+k])return 0;
	return 1;
}
void put(int row){
	if(row == MAXN -1){
		for(int col=0;col<MAXN;col++){
			if(avail_place(MAXN-1,col)){
				chess_board[MAXN-1][col] = 1;
				display();
				cnt++;
				chess_board[MAXN-1][col] = 0;
				return ;
			}
		}
		return ;	
	}
	else{
		for(int col = 0;col<MAXN;col++){
			if(avail_place(row,col)){
				chess_board[row][col] = 1;
				put(row+1);
				chess_board[row][col] = 0;
			}
		}
	}
}
int main(){
	put(0);
    int num;
    int idx;
	while(scanf("%d",&num)!=EOF){
       for(int i=0;i<num;i++){
           scanf("%d",&idx);
           show(idx-1);                      
       }
      
    }
	return 0;
}

#include <stdio.h>
#include <string.h>
int board[9]={0,0,0,0,0,0,0,0,0},count=0,boards[93][9];
int judge(int row,int col){
	char vist[9]={0,0,0,0,0,0,0,0,0};
	for(int i=1;i<row;vist[board[i++]]=1);
	if(vist[col]) return 0;
	for(int i=1;i<row;++i)
		if (col+i-row==board[i]) return 0;
		else if (col+row-i==board[i]) return 0;
	return 1;
}
void NQueen(int N,int row){
	if (row==N) memcpy(boards[++count],board,9*sizeof(int));
	else{
		for(int col=1;col<N;++col){
			if (judge(row,col)) {
				board[row]=col;
				NQueen(N,row+1);
				board[row]=0;
			}
		}
	}
}
int main(){
	NQueen(9,1);
	for(int n;~scanf("%d",&n);)
		for(int q;n-- && ~scanf("%d",&q);printf("\n"))
			for(int i=1;i<9;printf("%d",boards[q][i++]));
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 101;

string str[maxn];       // 时间换空间
int bite[maxn] = {0};   // 记录 i th 行皇后 在 j th 列
int count = 0;          // 用于计数

void solve(int num)
{
    if(num == 8)
    {
        char tmp;
        for(int i = 0; i < 8; ++i)
        {
            tmp = '1'+bite[i];
            str[count] += tmp;
        }
        ++count;
    }
    else
    {
        for(int i = 0; i < 8; ++i)
        {
            int flag = 1;
            // 判断这个位置是不是能放
            for(int j = 0; j < num; ++j)
            {
                if(i == bite[j] || (num+i == j+bite[j]) || (num-i == j-bite[j]))
                {
                    flag = 0;
                    break;
                }
            }
            // 如果能放继续放后序的皇后
            if(flag == 1)
            {
                bite[num] = i;
                solve(num+1);
            }
        }
    }
}

int main()
{
    solve(0);
    int n;
    int i;
    cin >> n;
    while(n--)
    {
        cin >> i;
        cout << str[i-1] << endl;
    }
    return 0;
}