2.3 N皇后（递归替代多重循环）DFS

r囧r小猫 2022-05-10 07:03 98阅读 0赞

![70][]

![70 1][]

![70 2][]

![70 3][]

![70 4][]

> 当第k行与前面的k-1行不冲突的时候，才将皇后放在不冲突的位置。

for(i = 1; i <= N; i++)//（i列）前面的（k-1)行皇后已经摆好，看第k行的i列皇后摆放位置是否和前面的k-1行冲突 
    	{
    		int j;
    		for(j = 1; j < k; j++)//前面的k-1行（j行） 
    		{
    			if(queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))//同一列或者列差等于行差 
    			{
    				break;
    			}
    		}
    		if(j == k)//k与前面的k-1行都没有冲突 
    		{
    			queenPos[k] = i;
    			NQueen(k+1);
    		}
    	}

![70 5][]

#include<iostream>
    #include<cmath>
    using namespace std;
    int N;
    int queenPos[100];
    void NQueen(int k);
    int main()
    {
    	cin >> N;
    	NQueen(1);
    	return 0; 
    } 
    
    void NQueen(int k)
    {
    	int i;
    	if(k==N+1)
    	{
    		for(i = 1; i <= N; i++)
    		{
    			cout << queenPos[i]<< " ";//第i行的皇后放在第queenPos[i]列 
    		}
    		cout << endl;
    		return ;
    	}
    	for(i = 1; i <= N; i++)//（i列）前面的（k-1)行皇后已经摆好，看第k行的i列皇后摆放位置是否和前面的k-1行冲突 
    	{
    		int j;
    		for(j = 1; j < k; j++)//前面的k-1行（j行） 
    		{
    			if(queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))//同一列或者列差等于行差 
    			{
    				break;
    			}
    		}
    		if(j == k)//k与前面的k-1行都没有冲突 
    		{
    			queenPos[k] = i;
    			NQueen(k+1);
    		}
    	}
    }

![70 6][]

计数：

#include<iostream>
    #include<cmath>
    using namespace std;
    int N;
    int queenPos[100];
    void NQueen(int k);
    int sum = 0;
    int main()
    {
    	cin >> N;
    	NQueen(1);
    	cout << "sum=" << sum << endl;
    	return 0; 
    } 
    
    void NQueen(int k)
    {
    	int i;
    	if(k==N+1)
    	{
    		++sum;
    		for(i = 1; i <= N; i++)
    		{
    			cout << queenPos[i]<< " ";//第i行的皇后放在第queenPos[i]列 
    		}
    		cout << endl;
    		return ;
    	}
    	for(i = 1; i <= N; i++)//（i列）前面的（k-1)行皇后已经摆好，看第k行的i列皇后摆放位置是否和前面的k-1行冲突 
    	{
    		int j;
    		for(j = 1; j < k; j++)//前面的k-1行（j行） 
    		{
    			if(queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))//同一列或者列差等于行差 
    			{
    				break;
    			}
    		}
    		if(j == k)//k与前面的k-1行都没有冲突 
    		{
    			queenPos[k] = i;
    			NQueen(k+1);
    		}
    	}
    }

![70 7][]

DFS：

#include<iostream>
    using namespace std;
    bool d[100] = {0}, b[100] = {0}, c[100] = {0};
    int sum = 0;
    int a[100];
    int search(int);
    int print();
    int n;
    int main()
    {
    	cin >> n;
    	search(1);
    	cout << "sum=" << sum << endl;
    	return 0;
    } 
    
    int search(int i)//i行 
    {
    	int j; //j列
    	for(j = 1; j <= n; ++j)
    	{
    		if((!b[j]) && (!c[i+j]) && (!d[i-j+7]))
    		{
    			a[i] = j;//第i行放在第j列
    			b[j] = 1;
    			c[i+j] = 1;
    			d[i-j+7] = 1;
    			if(i == n) print();
    				else search(i+1);
    			b[j] = 0;
    			c[i+j] = 0;
    			d[i-j+7] = 0;
    		}
    	}
    }
    
    int print()
    {
    	int i;
    	sum++;
    //	cout << "sum=" << sum << endl;
    	for(i = 1; i <= n; ++i)
    		cout << a[i] << " ";
    	cout << endl;
    }

![70 8][]

[70]: /images/20220510/0ce1a37350164455a9fb2ccd450665e8.png
[70 1]: /images/20220510/a7dd19e0f2f94156b3532ae7abec50ae.png
[70 2]: /images/20220510/9d48e3c3cc464b7e96d84c1a3545ceb4.png
[70 3]: /images/20220510/3278f09dc45f4a7d8b5823e6d1cc9bfa.png
[70 4]: /images/20220510/6837fe0c08a543f688336db1e50809f4.png
[70 5]: /images/20220510/6e61681cedbb4cd4bdd0a9884534d5de.png
[70 6]: /images/20220510/2ddb9d1d2caa4f1db698ab1dbeeffee1.png
[70 7]: /images/20220510/baf6b9ff77de41d1aad705c3e121a622.png
[70 8]: /images/20220510/b61e41b05e974d2abeaeadacd7bd14c4.png