从8皇后开始求排列组合
对于金典的8皇后大家肯定能给出以下解法
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int sum=0;/*记录方案的个数*/
int Place(int k,int *x)
/*判断新加入的皇后所在的位置 k 是否与其他皇后的位置冲突，此函数用来作为是否进行剪枝的判断条件*/
{
intj;
for(j=1;j<k;j++)
if((abs(k-j) == abs(x[j]-x[k])) || (x[j]==x[k]) )/*x[i]表示皇后 i 放在棋盘的第 i 行的第x[i]列*/
return0;/*能攻击到其他皇后，返回 0 */
return1;/*不能攻击到其他皇后，返回 1 */
}
void Backtrack(int t,int n,int *x)
/*递归回溯求解*/
{
inti;
if(t>n)
{
sum++;
/*输出一个方案*/
printf("方案%d：",sum);
for(i=1;i<=n;i++)
printf("(%d,%d)",i,x[i]);
printf("\n");
}
else
{
for(i=1;i<=n;i++)
{
x[t]=i;
if(Place(t,x))Backtrack(t+1,n,x);/*如果新加入第t个皇后所在的位置 i 没有与其他皇后的位置冲突，则进入解空间子树，试探第t+1个皇后的位置；否则不进入子树，舍弃该段子树，即进行剪枝*/
}
}
}
main()
{
intn,*x;
inti;
printf("请输入皇后的个数：");
scanf("%d",&n);
x=(int*)malloc((n+1)*sizeof(int));/*x[0]未使用*/
printf("以下每个方案都表示出了%d个皇后在棋盘上的坐标\n\n",n);
Backtrack(1,n,x);/*求解*/
printf("总共有%d种方案\n",sum);
}
以代码改成n皇后也是非常容易的。把搜索的过程画成一棵子树是比较容易理解的。
然后，上面代码的本质是一个递归过程。在这个递归的过程中，我们可以看出一个问题，就是把前面几个皇后的序列放在x中，于是，我们修改代码如下就可以输入n个数的所有排列。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int sum=0;/*记录方案的个数*/
int Place(int k,int *x)
/*判断新加入的皇后所在的位置 k 是否与其他皇后的位置冲突，此函数用来作为是否进行剪枝的判断条件*/
{
intj;
for(j=1;j<k;j++)
if((x[j]==x[k]))/*x[i]表示皇后 i 放在棋盘的第 i 行的第x[i]列*/
return0;/*能攻击到其他皇后，返回 0 */
return1;/*不能攻击到其他皇后，返回 1 */
}
void Backtrack(int t,int n,int *x)
/*递归回溯求解*/
{
inti;
if(t>n)
{
sum++;
/*输出一个方案*/
printf("方案%d：",sum);
for(i=1;i<=n;i++)
printf("(%d,%d)",i,x[i]);
printf("\n");
}
else
{
for(i=1;i<=n;i++)
{
x[t]=i;
if(Place(t,x))Backtrack(t+1,n,x);/*如果新加入第t个皇后所在的位置 i 没有与其他皇后的位置冲突，则进入解空间子树，试探第t+1个皇后的位置；否则不进入子树，舍弃该段子树，即进行剪枝*/
}
}
}
int main()
{
intn,*x;
inti;
printf("请输入皇后的个数：");
scanf("%d",&n);
x=(int*)malloc((n+1)*sizeof(int));/*x[0]未使用*/
printf("以下每个方案都表示出了%d个皇后在棋盘上的坐标\n\n",n);
Backtrack(1,n,x);/*求解*/
printf("总共有%d种方案\n",sum);
}
同样的，我们可以修改函数使其输入n个数中m个数的组合。代码如下：
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int sum=0;/*记录方案的个数*/
int m;
int Place(int k,int *x)
/*判断新加入的皇后所在的位置k 是否与其他皇后的位置冲突，此函数用来作为是否进行剪枝的判断条件*/
{
return1;/*不能攻击到其他皇后，返回 1 */
}
void Backtrack(int t,int n,int *x,intitotalbit)
/*递归回溯求解*/
{
inti;
if(itotalbit>m)
return;
if(t>n)
{
printf("Ok");
if(itotalbit<m)
return;
sum++;
/*输出一个方案*/
printf("方案%d：",sum);
for(i=1;i<=n;i++)
if(x[i])
printf("%d",i);
printf("\n");
}
else
{
for(i=0;i<2;i++)
{
x[t]=i;
if(Place(t,x))Backtrack(t+1,n,x,itotalbit+i);/*如果新加入第t个皇后所在的位置 i 没有与其他皇后的位置冲突，则进入解空间子树，试探第t+1个皇后的位置；否则不进入子树，舍弃该段子树，即进行剪枝*/
}
}
}
int main()
{
intn,*x;
inti;
printf("请输入数的个数和你要取的个数");
scanf("%d%d",&n,&m);
x=(int*)malloc((n+1)*sizeof(int));/*x[0]未使用*/
Backtrack(1,n,x,0);/*求解*/
printf("总共有%d种方案\n",sum);
}
