N皇后问题

本是古典何须时尚 2022-08-08 14:38 168阅读 0赞

在n\*n的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n\*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

回溯法：

#include <stdio.h>
    #include <math.h>
    int *x;
    int n;
    int sum;
    
    int place(int k)
    {
    	int i;
    	for(i=1;i<k;i++)
    		if(x[i]==x[k] || abs(i-k)==abs(x[i]-x[k])) 
    			return false;
    	
    	return true;
    }
    
    void backtrack(int t)
    {
    	int i;
    	if(t>n) sum++;
    	else
    	{
    		for(i=1;i<=n;i++){
    			x[t]=i;
    			if(place(t)) 
    				backtrack(t+1);
    		}
    
    	}
    }
    int main()
    {
    	int i;
    	
    	printf("input the number of queens:");
    	scanf("%d",&n);
    	
    	x=new int [n+1];
    	for(i=0;i<n+1;i++)
    		x[i]=0;
    
    	sum=0;
    	backtrack(1);
    
    	printf("%d\n",sum);
    	return 0;
    }

暴力搜索：

#include <stdio.h>
    #include <math.h>
    
    int main()
    {
    	int num,n;
    	int count=0;
    	int i,j,k;
    	int *a;
    
    	scanf("%d",&n);
    
    	a=new int[n];
    
    	for(num=0;num<pow(n,n);num++){
    		j=num;
    		for(i=0;i<n;i++){
    			a[i]=j%n;	//模n取余，转换为n进制
    			j=j/n;
    		}
    		
    		k=1;
    		for(i=0;i<n;i++){
    			for(j=i+1;j<n;j++){
    				if(a[i]==a[j] || abs(i-j)==abs(a[i]-a[j])){
    					k=0;
    					break;
    				}
    			}
    		}
    
    		if(k==1)
    			count++;
    	}
    
    	printf("%d\n",count);
    
    	return 0;
    }

还有一个方法是我在其他地方看到的，具体是哪我也不记得了，这个方法真的是很快的。写这个程序的也是个大神啊。

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    long sum = 0, upperlim = 1;
    
    void test(long row, long ld, long rd)
    {
    
    	if (row != upperlim){
    		long pos = upperlim & ~(row | ld | rd);
    		while (pos)
    		{
    			long p = pos & -pos;
    			pos -= p;
    			test(row + p, (ld + p) << 1, (rd + p) >> 1);
    		}
    	}else
    		sum++;
    }
    
    int main(int argc, char *argv[])
    {
    	time_t tm;
    	int n = 15;
    	if (argc != 1)
    	n = atoi(argv[1]);
    	tm = time(0);
    	if ((n < 1) || (n > 32)){
    		printf(" 只能计算1-32之间\n");
    		exit(-1);
    	}
    	printf("%d 皇后\n", n);
    	upperlim = (upperlim << n) - 1;
    	test(0, 0, 0);
    	printf("共有%ld种排列, 计算时间%d秒 \n", sum, (int) (time(0) - tm));
    }