八皇后

#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;
}

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<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;
}

/*非常朴素的八皇后问题，问题规模也已经框定好了，只要把每次得到的列号转化成要比较的十进制数字即可*/

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

vector<int> solut;            //用来放最终的结果
int position[9];            //行号从1开始，其中下标代表行号，其中存放的内容代表列号

void DFS(int row);

int main()
{
    DFS(1);                    //直接从第一行开始放
    sort(solut.begin(), solut.end());    //这里应该不用sort因为得到的solution应该都是从小到大
    int n;
    while (scanf("%d", &n) != EOF)
    {
        printf("%d\n", solut[n - 1]);    //因为vector是从0开始的    
    }
    return 0;
}

void DFS(int row)            //row代表要放入的行号,逐行放入，因为要用的是列号，而且按照习惯都是一列一列计算的
{
    if (row == 9)            //row==9意味着从1~8行全都放入,已完成解
    {
        int temp = 0;
        for (int i = 1; i <= 8; i++)
        {
            temp += position[i] * pow(10, 8 - i);    //非常朴素的计算方法_(:з」∠)_ 
        }
        solut.push_back(temp);                        //把得到的solution放进vector
    }

    else
    {
        for (int i = 1; i <= 8; i++)
        {
            position[row] = i;        //i在这里代表列号
            bool flag = true;        //用一个标志位来标记，是否冲突
            for (int j = 1; j <  row; j++)
            {
                if (position[row] == position[j] || row - position[row] == j - position[j] || row + position[row] == j + position[j])
                {
                    flag = false;
                    break;
                }        //这里的判断条件j - position[j]会把同一主对角线标记为同一个数字，与row - position[row]同时计算就能判断是否冲突
            }//for
            if (flag)
                DFS(row + 1);
        }
    }//endif
}//DFS

//考点:象棋，八皇后；知识点：递归
//S(n) = O(n!),递归
//思路:定义二维数组为92种解法的存储位置,根据题意选择适当的解
//步骤:1.初始化全局变量a[95][10],c[10],total置0；深度优先遍历棋盘，定义函数dfs(cur),cur表示从cur行开始检测通路
//2.0~7进行i循环，根据题意选择其实行对应的解——8位整数串
//3.详细dfs定义：如果cur为8，则total+1,0~7遍历a[total][i]=c[i]
//4.否则0~7循环，c[cur]接收索引i,初始ok为1，内层循环j从0~cur - 1,ok置0并退出内层循环的条件是c[j] == i 或cur - i == j - c[j]或cur + i ==c[j] + j。 
//5.内层循环结束后如果ok那递归调用dfs(cur + 1)
#include<bits/stdc++.h>
using namespace std;
int a[95][10];//解
int c[10];
int total = 0;
//深度优先遍历
void dfs(int cur){//起始位置
    if(cur == 8){
        total++;
        for(int i = 0; i < 8; i++){
            a[total][i] = c[i];
        }
    }else{
        for(int i = 0; i < 8; i++){
            c[cur] = i;//标记位置
            int ok = 1;//默认是所求的解
            for(int j = 0; j < cur; j++){
                if(c[j] == i || cur - i == j - c[j] || cur + i == c[j] + j){
                    ok = 0;
                    break;//此方案行不通啊
                }
            }
            if(ok){//i循环中此路可行
                dfs(cur + 1);//检测下一行
            }
        }
    }
}
int main(){
    int N;
    while(scanf("%d", &N) != EOF){
        dfs(0);//从索引号0开始逐行检测是否有通路
        for(int i = 0; i < 8; i++){//8皇后
            printf("%d", a[N][i] + 1);//根据需要取方案
        }
        //cout<<endl;
        printf("\n");
    }
    return 0;
}