一、全排列问题

问题简述

问题求解
列出所有从数字1到数字n的连续自然数的排列，要求所产生的人一数字序列中不允许出现重复的数字。
输入格式
一个正整数N（N<=20）
输出格式
若干行，由1-n组成的所有不重复的数字排列，每行一个序列。要求按照样例的所示的按字典序输出输出。
Sample Input
3
Sample Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路1：

这个问题有多个解，其中每个解都包含n个数字，如果n是确定的，则可以通过n层for循从小到大环枚举每个元素的值进行求解！（因为题目要求按字典序从小到大输出）

如：N=3：

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=n;j++)
	{
		for(int k=1;k<=n;k++)
		{
			if(i!=j && i!=k && j!=k)
			{
				cout<<i<<' '<<j<<' '<<k<<endl;
			}
		}
	}
}

复杂度：O()

算法漏洞1：

时间复杂度太高！超时！

算法漏洞2：

无法事先知道n的大小，所以不能知道要写几层for循环，此算法不可行！

尝试解决：

算法漏洞2可以解决，可以尝试写一个递归程序执行n次递归。

算法漏洞1无法此算法下无法解决，因为我们的思路是枚举方案中的每一个数，必定少不了n层循环！

结论：此算法不可行！

思路2：

搜索！当n不确定时，解中 元素数量也不确定，导致无法确定for循环的层数，可以使用递归模拟层次。

 这种穷举一个问题解空间中所有的可能情况，从而求出问题的解的一种方法称为搜索。

n个元素的全排列，使用搜索算法，总共会生成个解，其中只有n!个解是有效解。

画一个搜索树：

 搜索过程中如果发现某个解肯定不是有效解，则可以停止对当前解的搜索，降低搜索量!

二、回溯法

回溯法是一种优搜索法，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空
间树的任一节点时，先判断该节点是否包含问题的解，如果肯定不包含，则跳过对该节点
为根的子树的搜索（剪枝）；否则进入该子树，继续按深度优先策略搜索，如果发现原先
选择并不优或达不到目标，就退回一步重新选择。

所谓问题的解空间，即问题所有的解的集合。

回溯法在求解过程中不保留完整的搜索结果，而搜索则记下完整的搜索结果。

回溯法步骤：

① 定义问题的解和解空间，问题的解空间至少应包含问题的一个解。
② 确定结点的扩展搜索规则。
③ 以深度优先搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

三、例题

N皇后问题

题目描述

魔法世界历史上曾经出现过一个伟大的罗马共和时期，出于权力平衡的目的，当时的政治理论家波利比奥斯指出：“事涉每个人的权利，绝不应该让任何权力大到压过其他力量，使他人无法立足于平等条件与之抗辩的地步。”所以，即使关押修罗王和邪狼的监狱里的每个暗势力之间的关系十分紧张，但为了维持监狱的正常秩序，如非必要，他们会尽可能地避免直接接触。这类似著名的N皇后问题，即在N×N格的国际象棋上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，请问有多少种摆法。图所示即是摆法的一种。

输入格式

一行，一个整数N，3<N≤12

输出格式

一行，一个整数，输出一共有多少种摆法

输入输出样列

输入样例1：

4

输出样例1：

2

说明

N=4的棋盘输出的两种方案即图所示。

🔑思路

n个皇后必然分布在n行上，考虑每行上的皇后，可放范围为[1,n]列。
依次搜索每一行上皇后的放置位置，通过判断冲突进行剪枝。

 💯核心代码

bool check(int x,int xn)
{
	for(int i=1;i<xn;i++)
	{
		if(a[i]==x || abs(xn-i)==abs(x-a[i]))return false;
	}
	return true;
}
void dfs(int x)
{
	if(x>n)
	{
		ans++;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(check(i,x))
		{
			a[x]=i;
			dfs(x+1);
		}
	}
	return;
}

素数环[Prime Ring Problem,UVa524]

题目描述

如下图所示，一个圆环是有n个（n是偶数）圆组成的。把自然数1,2...n分别放到n每个圆上，使得两个相邻的数字之和是素数。

注意：第一个圆上的数字始终是1

输入格式

输入有多组数据。

每组数据，一行，一个偶数n，0＜n≤16

输出格式

输出格式，参考输出样例，两组输出之间有一个空行

每一行，代表一个圆环，是从1开始按照逆时针方向输出圆里面的数字。

输入输出样列

输入样例1：

6
8

输出样例1：

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4


Case 2:
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

🔑思路

解空间中的每个解包含n-1个元素，每个元素的取值范围为：[2,n]
搜索过程中通过判断i是否已被使用和i+a[cur-1]是否为质数进行剪枝。