回溯算法————n皇后、素數串 -开发者知识库

回溯算法————n皇后、素數串 -开发者知识库,第1张

 

回溯就是算法是搜索算法中一種控制策略,是一個逐個試探的過程。在試探的過程中,如果遇到錯誤的選擇,就會回到上一步繼續選擇下一種走法,一步一步的進行直到找到解或者證明無解為止。

如下是一個經典回溯問題n皇后的解答樹:

回溯算法————n皇后、素數串 -开发者知识库,image,第2张

下面就從n皇后說起:


【問題描述】

在n×n的國際象棋盤上,放置n個皇后,使任何一個皇后都不能吃掉另一個,需滿足的條件是:同一行、同一列、同一對角線上只能有一個皇后。求所有滿足要求的放置方案。4皇后的放置方案如下:

【輸入】一個正整數n。

【輸出】每行代表一種放置方案:第i行的第一個數是i,表示第i種方案,后面一個冒號,然后是用空格隔開的n個數,其中第i個數x[i]表示第i行上的皇后放在第x[i]列;最后一行:一個整數,表示方案總數。

【樣例輸入】

4

【樣例輸出】

1:2 4 1 3

2:3 1 4 2

2

回溯算法————n皇后、素數串 -开发者知识库,image,第3张

這個題目簡直是太經典了,一提到回溯第一個想到的就是它。這個題非常的通俗易懂,就是在一個n*n的棋盤上滿足條件地放置n個皇后,每種組合搜一遍就好了。在搜的過程中判斷下一步的某種方向是否可以走,如果可以的話就進入下一層,如果不符合要求就搜下一個方向,搜完這一層的所有方向以后就回到上一層,繼續搜上一層的下一個方向。

不知道大家看懂了沒有,如果沒看懂,看代碼就懂了。。

上代碼:

#include<iostream>
#include<cstdio>

using namespace std;

int n;
int sum=0;//解法存放個數
int a[100000];//存放皇后位置數據
bool b[1000000]={0},c[1000000]={0},d[10000000]={0};//b存儲y方向,c、d存儲對角線

void print()
{
	sum  ;
	cout<<sum<<':';
	for(int i=1;i<=n;i  )
	{
		cout<<a[i]<<' ';
	}
	cout<<endl;
}

int search(int x)
{
	for(int j=1;j<=n;j  )//遍歷本層中每種方向
	{
		if((!b[j])&&(!c[x j])&&(!d[x-j n-1]))//如果滿足條件
		{
			a[x]=j;//存入皇后數據
			b[j]=1;//占領y軸
			c[x j]=1;//占領對角線
			d[x-j n-1]=1;//占領對角線
			if(x==n) 
			{
				print();//如果有完整解,輸出
			}
			else
			{
				search(x 1);//如果沒有繼續找下一行
			} 
			b[j]=0;//找完之后取消占領
			c[x j]=0;
			d[x-j n-1]=0;
		}
	}
}

int main()
{
	cin>>n;
	search(1);//從第一個開始找
	cout<<sum;
} 

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复