N皇后排序树(C语言)--回溯法

ゝ一纸荒年。 2022-01-11 06:53 246阅读 0赞

## ***N后问题*** ##

**题目描述**  
在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上

**解题思路**  
由于N个皇后的任意两个不能处在同一行，那么肯定是每个皇后占据一行，于是我们定义一个数组，长度为N。  
数组的第i个数字代表位于第i行的皇后的列号。先把数组中的N个数字用（1–>N）初始化，然后对该数组中的数字作全排列。

因为我们是用不同的数字初始化数组，故而所有皇后肯定不同列。
    	因此我们只需要判断每一个排列对应的N个皇后是否在同一条对角线上，
    	也就是对于数组的两个下标i和j，是不是有 abs(A[i]-A[j]) = abs(i - j)。
    	如果成立，则该解法不满足条件。筛选过后可以得到所有满足条件的解法。

**具体代码实现**

#include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
    
    int N;		//皇后个数
    int count;	//排序结果的数量 
    
    //打印N后排序后的状态 
    void Printf(int data[]){
    	int a[N+1][N+1]={0};
    	for(int i = 1; i<=N;i++){
    		a[data[i]][i] = 1;
    	}
    	printf("\n第%d种排列方式：    \n",count+1); 
    	for(int i = 1;i<=N;i++){
    		for(int j = 1; j<=N;j++){
    			printf("%d ",a[i][j]);
    		}
    		printf("\n");
    	}
    	count++;
    }
    
    void swap(int &x, int &y)
    {
    	int temp;
    	temp=x;
    	x=y;
    	y=temp;
    }
     
     //判断此位置是否能够插入 
    int Judge(int data[], int k)
    {
    	if(k == 1){   //如果为第一个皇后则返回true 
    		return 1;
    	} 
    	for(int j=1;j<k;j++)
    		if(abs(k-j)==abs(data[j]-data[k]))		//判断是否在同一对角线上 
    			return 0;
    	return 1;
    } 
    
    
    void perm(int data[], int k, int N)
    {
    	if(k>N)
    	{
    		//如果N后排序完成则打印此次结果 
    		Printf(data);
    	}
    	else
    	{
    		//k代表当前是第几个皇后 
    		for(int i=k;i<=N;i++)
    		{
    			swap(data[k],data[i]);
    			if(Judge(data,k))
    				perm(data,k+1,N);
    			swap(data[i],data[k]);
    		}
    	}
    }
    
    int main()
    {
    	printf("请输入N: ");
    	scanf("%d",&N);
    	int * data = (int *)malloc((N+1)*sizeof(int));
    	for(int i=1;i<=N;i++)
    		data[i]=i;				//数组的第i个数字代表位于第i行的皇后的列号
    		
    	perm(data,1,N);
    	printf("\n共%d组答案\n",count);
    	return 0;
    }