【模板】回溯法 （八皇后、素数环题解）

回溯法

在问题的解空间树中，按深度优先策略从根结点出发搜索解空间树。算法搜索到解空间树任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树继续按照深度优先策略搜索。

两种剪枝策略

1. 用约束函数在扩展结点处减去不满足约束的子树。

2. 用限界函数剪去得不到最优解的子树。

伪代码模板

void dfs(int t)//t记录递归深度
{
    if(t>n) Output(x);//n控制递归深度
    else
        for(int i=f(n,t);i<=g(n,t);i++){//在当前扩展结点处未搜索过的子树的起始编号和终止编号
            x[t]=h(i);//h(i)表示当前扩展结点x[t]的第i个可选择的值
            if(Constraint(t)&&Bound(t)) dfs(t+1);
        }
}

子集树（如01背包问题）

void dfs(int t)
{
    if(t>n) output(x);
    else{
        for(int i=0;i<=1;i++){
            x[t]=i;
            if(Constraint(t)&&Bound(t)) dfs(t+1);
        }
    }
}

排列树（如TSP问题）

//在dfs(1)以前，需要先将变量数组x[]初始化为单位排列(1,2,3,……)
void dfs(int t)
{
    if(t>n) output(x);
    else{
        for(int i=t;i<=n;i++)
        {
            swap(x[t],x[i]);
            if(Constraint(t)&&Bound(t)) dfs(t+1);
            swap(x[t],x[i]);
        }
    }
}

八皇后

描述

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。

输入

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量

输出

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

样例

输入:8

输出:92

输入:5

输出:10

#include<iostream>
#include<cstring>
#include<cmath> 
using namespace std;
int pos[11];
int sum;
int n;
bool place(int k)
{
	for(int i=1;i<k;i++)
	{
		if(pos[i]==pos[k]||abs(i-k)==abs(pos[i]-pos[k])) return false;
	}
	return true;
}
void dfs(int t)
{
	if(t>n) sum++;//深度n+1时,说明到达叶子结点，是一个可选方案 
	else
	{
		for(int i=1;i<=n;i++)//相当于一个n叉树
		{
			pos[t]=i;// 放置棋子 
			if(place(t)) dfs(t+1);//检查落子合法性 
		 } 
	}
}
int main(void)
{
	while(cin>>n)
	{
		memset(pos,0,sizeof(pos));
		sum=0;
		dfs(1);
		cout<<sum<<endl;
	}
	return 0;
}

素数环

描述

素数环是像这样的一个图形，将1~N排列成一个环，让环中任意相邻两个数的和都是素数。如图就是一个简单的素数环:

    1

 /     \

6       4

|        |

5        3

 \      /

     2

注意，考虑到对称性,我们假设素数环的元素都是从1开始的。

输入

第一行为两个正整数 ,代表素数环中元素的个数。0<n<20。

输出

所有可能的素数环，按字典序从小到大输出。

输入

6

输出

1 4 3 2 5 6 
1 6 5 2 3 4

输入

8

输出

1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2

#include<iostream>
#include<cstring>
using namespace std;
int x[21];
bool mark[21];
int n;
bool prime(int num)
{
	int primeNum[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43};
	for(int i=0;i<14;i++){
		if(primeNum[i]==num) return true;
	}
	return false;
}
void output()
{
	for(int i=1;i<=n;i++)
	{
		 if(i==1) cout<<x[i];
		 else printf(" %d",x[i]);
	}
	printf("\n");
}
void dfs(int t)
{
	if(t>n){
		if(prime(x[n]+x[1])==true) output();
		return;
 	}
 	else
 	{
 		for(int i=2;i<=n;i++)
 		{
 			if(mark[i]==true) continue;
 			x[t]=i;
 			mark[i]=true;
 			if(prime(x[t]+x[t-1])) dfs(t+1);
 			mark[i]=false;
		 }
	 }
}
int main(void)
{
	cin>>n; 
	memset(x,0,sizeof(x)); 
	for(int i=1;i<=n;i++){
		mark[i]=false;
	}
	x[1]=1;mark[1]=true;
	dfs(2);
	return 0;
 }