快捷導(dǎo)航

C++基于回溯法解決八皇后問題示例

更新時(shí)間：2017年11月07日 09:06:07 作者：侯凱

這篇文章主要介紹了C++基于回溯法解決八皇后問題,簡(jiǎn)單描述了八皇后問題,以及回溯法的原理與解決八皇后問題的相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了C++基于回溯法解決八皇后問題的方法。分享給大家供大家參考，具體如下：

回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。

回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。

回溯法指導(dǎo)思想——走不通，就掉頭。設(shè)計(jì)過程：確定問題的解空間；確定結(jié)點(diǎn)的擴(kuò)展規(guī)則；搜索。

n皇后問題

要在n*n的國(guó)際象棋棋盤中放n個(gè)皇后，使任意兩個(gè)皇后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一列、同一對(duì)角線的任意棋子。求所有的解。n=8是就是著名的八皇后問題了。

設(shè)八個(gè)皇后為xi，分別在第i行(i=1，2，3，4……，8)；

問題的解狀態(tài)：可以用(1,x1)，(2,x2)，……，(8,x8)表示8個(gè)皇后的位置；

由于行號(hào)固定，可簡(jiǎn)單記為：(x1,x2,x3,x4,x5,x6,x7,x8)；

問題的解空間：(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ì)角線上。

盲目的枚舉算法：通過8重循環(huán)模擬搜索空間中的88個(gè)狀態(tài)，從中找出滿足約束條件的“答案狀態(tài)”。程序如下：

/*
 *作者：侯凱
 *說(shuō)明：八皇后——盲目迭代法
 *日期：2013-12-18
 */
#include <iostream>
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<<a[i];
          }
          cout<<endl;
          count++;
         }
        }
       }
      }
     }
    }
   }
  }
 }
 cout<<count<<endl;
}
void main()
{
 queens_1();
}

程序思想比較簡(jiǎn)單，最后可知共92種擺放方法。如果能夠排除那些沒有前途的狀態(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<<a[i];
          }
          cout<<endl;
          count++;
         }
        }
       }
      }
     }
    }
   }
  }
 }
 cout<<count<<endl;
}
void main()
{
 queens_2();
}

n此算法可讀性很好，體現(xiàn)了“回溯”。但它只針對(duì)八皇后問題，解決任意的n皇后問題還要修改程序結(jié)構(gòu)。如果要解決n皇后的問題，就需要將n作為參數(shù)傳遞給函數(shù)，函數(shù)需要重寫來(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<<a[i];
    }
    cout<<endl;
    count++;
   } 
   else 
   {
    k=k+1;//繼續(xù)為第k+1個(gè)皇后找到位置，對(duì)應(yīng)下一級(jí)for循環(huán) 
    a[k]=0;//下一個(gè)皇后一定要從頭開始搜索
   }
  }
  else
  {
   k=k-1;//回溯,對(duì)應(yīng)執(zhí)行外內(nèi)層for循環(huán)回到更上層 
  }
 }
 cout<<count<<endl;
}
void main()
{
 backdate(8);
}

這樣也可以得到，8皇后問題的92中結(jié)果。更簡(jiǎn)單、可讀的方法是采用遞歸的方式，如下：

int a[100], n, count;
void backtrack(int k)
{
 if (k>n)//找到解
 {
  for(int i=1;i<=8;i++) 
  {
   cout<<a[i];
  }
  cout<<endl;
  count++;
 }
 else
 {
  for (int i = 1;i <=n; i++)
  {
   a[k] = i;
   if (check_2(a,k) == 1)
   {backtrack(k+1);}
  }
 }
}
void main()
{
 n=8,count=0;
 backtrack(1);
 cout<<count<<endl;
}

可見，遞歸調(diào)用大大減少了代碼量，也增加了程序的可讀性。給出其中的一個(gè)解，如下：