8皇后问题

小灰灰 2022-10-21 12:57 117阅读 0赞

8皇后问题可以用全排列和dfs来做。其中关键的问题就是如何判定是否在同一条斜线上。也就是经过任意量皇后的直线的斜率不为1或者-1。全排列算法判定皇后是否在同以列上可以用任意两皇后的列差的绝对值不为行差绝对值。而进行dfs，可以另外开辟两个数组进行优化，分别表示左斜线和右斜线。注意到n\*n的棋盘上，在同一左斜线上的点其行列坐标和相等；在右同一右斜线上的点，其行列坐标差相等，但是会出现负数的情况，所以用一个数组进行存储的时候需要加一个偏移量（至少8）。

dfs的效率是肯定要快与全排列的！！！！！

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <math.h>
    using namespace std;
    static int queen[8]={1,5,8,6,3,7,2,4};
    bool isOk(int a[])
    {
    	int i,j;
    	for (i=1;i<8;++i) //i表示行,a[i]为列，行差范围为[1,8)
    		for (j=0;j<8-i;++j)
    			if (abs(a[j+i]-a[j])==i) return false;
    	return true;		
    }
    
    int main()
    {
    	int i,j,n;
    	cin >> n;
    	int query,count;
    	for (i=0;i<n;i++)
    	{
    		cin >> query;
    		count = 0;
    		for (j=0;j<8;++j)
    			queen[j]=j+1;
    		while(1)
    		{
    			if (isOk(queen))
    			{
    				count++;
    				if (count==query)
    				{
    					for (j=0;j<8;j++)
    						cout << queen[j];
    					cout << endl;
    					break;
    				}
    			}
    			next_permutation(queen,queen+8);  //全排列
    		}			
    	}
    	return 0;
    }
    /**************************************************************
    Problem: 1140     
    User: sicofield     
    Language: C++     
    Result: Accepted     
    Time:70 ms     
    Memory:1520 kb 
    ****************************************************************/ 
    
    #include<stdio.h> 
    #include<math.h> 
    #include<algorithm> 
    using namespace std; 
    const int MAX=92; 
    const int INF=1000000000; 
    int ans[MAX],E=0; 
    bool col[MAX]={false}; 
    bool lft[MAX]={false},rgt[MAX]={false};//其实用不着这么大 
    void DFS(int deep,int t) //deep代表行
    {     
    	if(deep==9)     
    	{         
    		ans[E++]=t;         
    		return ;     
    	}     
    	int i;     
    	for(i=1;i<=8;i++)   //选列
    	{         
    		if(col[i])continue;  //该列已有皇后      
    		if(rgt[i-deep+8])continue;  //行列差不等，右斜线，为了将负数转化为正数，所有值偏移8(偏移量无所谓的，比8大就好)
    		if(lft[i+deep])continue;   //行列和不能相等，左斜线
    		col[i]=true;       
    		rgt[i-deep+8]=true;  
    		lft[i+deep]=true;  
    		DFS(deep+1,t*10+i);   
            col[i]=false;     //已经搜索过
    		rgt[i-deep+8]=false;   
    		lft[i+deep]=false;    
    	}
    } 
    int main() 
    {     
    	int n;              
    	int T;    
    	DFS(1,0);    
    	sort(ans,ans+92);  
    	scanf("%d",&T);   
    	while(T--)     
    	{         
    		scanf("%d",&n);     
    		printf("%d\n",ans[n-1]);  
    	}     
    	return 0;
    }  
    /**************************************************************    
    Problem: 1140     
    User: sicofield     
    Language: C++     
    Result: Accepted     
    Time:0 ms     
    Memory:1020 kb 
    ****************************************************************/