這篇文章給大家分享的是有關(guān)C++基于回溯法如何解決八皇后問(wèn)題的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。
目前成都創(chuàng)新互聯(lián)公司已為上千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁(yè)空間、綿陽(yáng)服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、資源網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶(hù)導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶(hù)和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。
具體如下：
回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。
回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。
回溯法指導(dǎo)思想——走不通，就掉頭。設(shè)計(jì)過(guò)程：確定問(wèn)題的解空間；確定結(jié)點(diǎn)的擴(kuò)展規(guī)則；搜索。
n皇后問(wèn)題
要在n*n的國(guó)際象棋棋盤(pán)中放n個(gè)皇后，使任意兩個(gè)皇后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一列、同一對(duì)角線(xiàn)的任意棋子。求所有的解。n=8是就是著名的八皇后問(wèn)題了。
設(shè)八個(gè)皇后為xi，分別在第i行(i=1，2，3，4……，8)；
問(wèn)題的解狀態(tài)：可以用(1,x1)，(2,x2)，……，(8,x8)表示8個(gè)皇后的位置；
由于行號(hào)固定，可簡(jiǎn)單記為：(x1,x2,x3,x4,x5,x6,x7,x8)；
問(wèn)題的解空間：(x1,x2,x3,x4,x5,x6,x7,x8)，1≤xi≤8(i=1，2，3，4……，8)，共88個(gè)狀態(tài)；
約束條件：八個(gè)(1,x1),(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)不在同一行、同一列和同一對(duì)角線(xiàn)上。
盲目的枚舉算法：通過(guò)8重循環(huán)模擬搜索空間中的88個(gè)狀態(tài)，從中找出滿(mǎn)足約束條件的“答案狀態(tài)”。程序如下：
/*
*作者：侯凱
*說(shuō)明：八皇后——盲目迭代法
*日期：2013-12-18
*/
#include
using namespace std;
bool check_1(int a[],int n)
{
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i-1;j++)
{
if ((a[i]==a[j])||(abs(a[i]-a[j])==i-j))
{
return false;
}
}
}
return true;//不沖突
}
void queens_1()
{
int a[9];
int count = 0;
for(a[1]=1;a[1]<=8;a[1]++)
{
for(a[2]=1;a[2]<=8;a[2]++)
{
for(a[3]=1;a[3]<=8;a[3]++)
{
for(a[4]=1;a[4]<=8;a[4]++)
{
for(a[5]=1;a[5]<=8;a[5]++)
{
for(a[6]=1;a[6]<=8;a[6]++)
{
for(a[7]=1;a[7]<=8;a[7]++)
{
for(a[8]=1;a[8]<=8;a[8]++)
{
if(!check_1(a,8))
continue;
else
{
for(int i=1;i<=8;i++)
{
cout<程序思想比較簡(jiǎn)單，最后可知共92種擺放方法。如果能夠排除那些沒(méi)有前途的狀態(tài)，會(huì)節(jié)約時(shí)間——回溯法（走不通，就回頭）。
bool check_2 (int a[ ],int n)
{//多次被調(diào)用，只需一重循環(huán)
for(int i=1;i<=n-1;i++)
{
if((abs(a[i]-a[n])==n-i)||(a[i]==a[n]))
return false;
}
return true;
}
void queens_2()
{
int a[9];
int count = 0;
for(a[1]=1;a[1]<=8;a[1]++)
{
for(a[2]=1;a[2]<=8;a[2]++)
{
if (!check_2(a,2)) continue;
for(a[3]=1;a[3]<=8;a[3]++)
{
if (!check_2(a,3)) continue;
for(a[4]=1;a[4]<=8;a[4]++)
{
if (!check_2(a,4)) continue;
for(a[5]=1;a[5]<=8;a[5]++)
{
if (!check_2(a,5)) continue;
for(a[6]=1;a[6]<=8;a[6]++)
{
if (!check_2(a,6)) continue;
for(a[7]=1;a[7]<=8;a[7]++)
{
if (!check_2(a,7)) continue;
for(a[8]=1;a[8]<=8;a[8]++)
{
if (!check_2(a,8))
continue;
else
{
for(int i=1;i<=8;i++)
{
cout<n此算法可讀性很好，體現(xiàn)了“回溯”。但它只針對(duì)八皇后問(wèn)題，解決任意的n皇后問(wèn)題還要修改程序結(jié)構(gòu)。如果要解決n皇后的問(wèn)題，就需要將n作為參數(shù)傳遞給函數(shù)，函數(shù)需要重寫(xiě)來(lái)實(shí)現(xiàn)回溯（不能采用級(jí)聯(lián)的for循環(huán)，n不確定）；從另一方面，程序中出現(xiàn)了大量的for循環(huán)，而且for中的函數(shù)結(jié)構(gòu)很相似，自然想到的是遞歸迭代回溯。這就是回溯比較常用的兩種實(shí)現(xiàn)方法：非遞歸回溯和遞歸回溯。
非遞歸回溯的程序?qū)崿F(xiàn)：
void backdate (int n)
{
int count = 0;
int a[100];
int k = 1;
a[1]=0;
while(k>0)
{
a[k]=a[k]+1;//對(duì)應(yīng)for循環(huán)的1~n
while((a[k]<=n)&&(!check_2(a,k)))//搜索第k個(gè)皇后位置
{
a[k]=a[k]+1;
}
if(a[k]<=n)//找到了合理的位置
{
if(k==n )
{//找到一組解
for(int i=1;i<=8;i++)
{
cout<這樣也可以得到，8皇后問(wèn)題的92中結(jié)果。更簡(jiǎn)單、可讀的方法是采用遞歸的方式，如下：
int a[100], n, count;
void backtrack(int k)
{
if (k>n)//找到解
{
for(int i=1;i<=8;i++)
{
cout<可見(jiàn)，遞歸調(diào)用大大減少了代碼量，也增加了程序的可讀性。給出其中的一個(gè)解，如下：
感謝各位的閱讀！關(guān)于“C++基于回溯法如何解決八皇后問(wèn)題”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！
網(wǎng)頁(yè)名稱(chēng)：C++基于回溯法如何解決八皇后問(wèn)題
鏈接URL：http://weahome.cn/article/ipjgse.html
重慶分公司
重慶分公司
