八皇åŽé—®é¢˜

转自我的CSDNåšå®¢ï¼šÂ http://blog.csdn.net/njdragonfly

8皇åŽé—®é¢˜å’Œç”±ä»–推广得到的N皇åŽé—®é¢˜æ¥æºäºŽå›½é™…è±¡æ£‹çš„çŽ©æ³•ï¼Œå› ä¸ºçš‡åŽæ‰€åœ¨çš„ä½ç½®å¯ä»¥çºµå‘ã€æ¨ªå‘ã€ä¸¤ä¸ªæ–œå‘四个方å‘çš„â€œæ•æ‰â€ï¼Œæ‰€ä»¥8皇åŽé—®é¢˜å°±æ˜¯è¦æ±‚如何布置8个皇åŽåœ¨8*8çš„æ£‹ç›˜ä¸Šè€Œä½¿ä»–ä»¬äº’ç›¸æ— æ³•â€œæ•æ‰â€ã€‚也就是说ä¸å­˜åœ¨ä¸¤ä¸ªçš‡åŽåŒè¡Œæˆ–åŒåˆ—,或在åŒä¸€æ–œçº¿ä¸Šã€‚而N皇åŽé—®é¢˜å°±æ˜¯å¦‚何布置N个皇åŽåœ¨N*N棋盘里使ä¸å­˜åœ¨ä¸¤ä¸ªçš‡åŽåœ¨åŒè¡ŒåŒåˆ—å’ŒåŒä¸€æ–œçº¿ä¸Šã€‚因为8皇åŽé—®é¢˜å¯ä»¥å½’为N皇åŽé—®é¢˜ï¼Œæ‰€ä»¥ä¸‹é¢æŒ‰ç…§N皇åŽé—®é¢˜æ¥è¿›è¡Œè®¨è®ºã€‚

解决N皇åŽé—®é¢˜çš„æœ€å¥½æœ€è‘—å的算法就是回溯法。在算法设计的基本方法中,回溯法是最一般的方法之一。在那些涉åŠåˆ°å¯»æ‰¾ä¸€ç»„解的问题或者求满足æŸäº›çº¦æŸæ¡ä»¶çš„æœ€ä¼˜è§£çš„问题中,有许多å¯ä»¥ç”¨å›žæº¯æ³•æ¥æ±‚解。回溯法是一个既带有系统性åˆå¸¦æœ‰è·³è·ƒæ€§çš„çš„æœç´¢ç®—法。它在包å«é—®é¢˜çš„æ‰€æœ‰è§£çš„è§£ç©ºé—´æ ‘ä¸­ï¼ŒæŒ‰ç…§æ·±åº¦ä¼˜å…ˆçš„ç­–ç•¥ï¼Œä»Žæ ¹ç»“ç‚¹å‡ºå‘æœç´¢è§£ç©ºé—´æ ‘。算法æœç´¢è‡³è§£ç©ºé—´æ ‘的任一结点时,总是先判断该结点是å¦è‚¯å®šä¸åŒ…å«é—®é¢˜çš„解。如果肯定ä¸åŒ…å«ï¼Œåˆ™è·³è¿‡å¯¹ä»¥è¯¥ç»“ç‚¹ä¸ºæ ¹çš„å­æ ‘的系统æœç´¢ï¼Œé€å±‚å‘其祖先结点回溯。å¦åˆ™ï¼Œè¿›å…¥è¯¥å­æ ‘,继续按深度优先的策略进行æœç´¢ã€‚å›žæº¯æ³•åœ¨ç”¨æ¥æ±‚问题的所有解时,è¦å›žæº¯åˆ°æ ¹ï¼Œä¸”æ ¹ç»“ç‚¹çš„æ‰€æœ‰å­æ ‘都已被æœç´¢éæ‰ç»“æŸã€‚è€Œå›žæº¯æ³•åœ¨ç”¨æ¥æ±‚问题的任一解时,åªè¦æœç´¢åˆ°é—®é¢˜çš„一个解就å¯ä»¥ç»“æŸã€‚è¿™ç§ä»¥æ·±åº¦ä¼˜å…ˆçš„æ–¹å¼ç³»ç»Ÿåœ°æœç´¢é—®é¢˜çš„è§£çš„ç®—æ³•ç§°ä¸ºå›žæº¯æ³•ï¼Œå®ƒé€‚ç”¨äºŽè§£ä¸€äº›ç»„åˆæ•°è¾ƒå¤§çš„问题。

å›žæº¯æ³•çš„åŸºæœ¬æ€æƒ³ï¼šç¡®å®šäº†è§£ç©ºé—´çš„组织结构åŽï¼Œå›žæº¯æ³•就从开始结点(根结点)出å‘ï¼Œä»¥æ·±åº¦ä¼˜å…ˆçš„æ–¹å¼æœç´¢æ•´ä¸ªè§£ç©ºé—´ã€‚这个开始结点就æˆä¸ºä¸€ä¸ªæ´»ç»“ç‚¹ï¼ŒåŒæ—¶ä¹Ÿæˆä¸ºå½“å‰çš„æ‰©å±•结点。在当å‰çš„æ‰©å±•结点处,æœç´¢å‘纵深方å‘移至一个新结点。这个新结点就æˆä¸ºä¸€ä¸ªæ–°çš„æ´»ç»“点,并æˆä¸ºå½“剿‰©å±•结点。如果在当å‰çš„æ‰©å±•结点处ä¸èƒ½å†å‘纵深方å‘ç§»åŠ¨ï¼Œåˆ™å½“å‰æ‰©å±•结点就æˆä¸ºæ­»ç»“点。æ¢å¥è¯è¯´ï¼Œè¿™ä¸ªç»“点ä¸å†æ˜¯ä¸€ä¸ªæ´»ç»“点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点æˆä¸ºå½“å‰çš„æ‰©å±•结点。回溯法å³ä»¥è¿™ç§å·¥ä½œæ–¹å¼é€’归地在解空间中æœç´¢ï¼Œç›´è‡³æ‰¾åˆ°æ‰€è¦æ±‚的解或解空间中已没有活结点时为止。
è¿ç”¨å›žæº¯æ³•解题通常包å«ä»¥ä¸‹ä¸‰ä¸ªæ­¥éª¤ï¼š
(1)针对所给问题,定义问题的解空间;
(2)确定易于æœç´¢çš„解空间结构;
(3ï¼‰ä»¥æ·±åº¦ä¼˜å…ˆçš„æ–¹å¼æœç´¢è§£ç©ºé—´ï¼Œå¹¶ä¸”在æœç´¢è¿‡ç¨‹ä¸­ç”¨å‰ªæžå‡½æ•°é¿å…无效æœç´¢ï¼›

一般回溯法å¯ç”¨é€’å½’æ¥å®žçŽ°ï¼Œä¸‹é¢æ˜¯ä»Žç½‘上找æ¥çš„一个éžå¸¸å…¸åž‹çš„递归程åºç»“构。

procedure try(i:integer);
var
begin
     if i>n then 输出结果
     else   for j:=下界 to 上界 do
          begin
           x[i]:=h[j];
           if å¯è¡Œ{满足é™ç•Œå‡½æ•°å’Œçº¦æŸæ¡ä»¶} then begin 置值;try(i+1); end;
        end;
end;

说明:
i是递归深度;
n是深度控制,å³è§£ç©ºé—´æ ‘的的高度;
å¯è¡Œæ€§åˆ¤æ–­æœ‰ä¸¤æ–¹é¢çš„å†…å®¹ï¼šä¸æ»¡çº¦æŸæ¡ä»¶åˆ™å‰ªåŽ»ç›¸åº”å­æ ‘;若é™ç•Œå‡½æ•°è¶Šç•Œï¼Œä¹Ÿå‰ªåŽ»ç›¸åº”å­æ ‘ï¼›ä¸¤è€…å‡æ»¡è¶³åˆ™è¿›å…¥ä¸‹ä¸€å±‚,直到最åŽçš„å¶å­è¾“出结果。

回到N皇åŽé—®é¢˜çš„解决æ¥ï¼Œçœ‹çœ‹å¦‚何用回溯法解。首先找出解空间:给棋盘的行和列都编上1到Nçš„å·ç ï¼Œçš‡åŽä¹Ÿç»™ç¼–上1到Nçš„å·ç ã€‚由于一个皇åŽåº”在ä¸åŒçš„行上,为ä¸å¤±ä¸€èˆ¬æ€§ï¼Œå¯ä»¥å‡å®šç¬¬i个皇åŽå°†æ”¾åœ¨ç¬¬i行上的æŸåˆ—。因此N皇åŽé—®é¢˜çš„解空间å¯ä»¥ç”¨ä¸€ä¸ªN元组(X1,X2,…..Xn)æ¥è¡¨ç¤ºï¼Œå…¶ä¸­Xi是放置皇åŽi所在的列å·ã€‚è¿™æ„å‘³ç€æ‰€æœ‰çš„解都是N元组(1,2,3,…….,N)的置æ¢ã€‚解空间大å°ä¸ºNï¼ã€‚å…¶æ¬¡æˆ‘ä»¬çœ‹çº¦æŸæ¡ä»¶ï¼šå› ä¸ºè§£ç©ºé—´å·²ç»ç»™æˆ‘们排除了ä¸åœ¨åŒä¸€è¡Œï¼ˆå› ä¸ºæ¯ä¸ªçš‡åŽåˆ†åˆ«å·²ç»å¯¹åº”ä¸åŒçš„行å·ï¼‰çš„çº¦æŸæ¡ä»¶ã€‚我们è¦åˆ¤æ–­çš„æ˜¯ä¸åœ¨åŒä¸€åˆ—å’Œä¸åœ¨åŒä¸€æ–œçº¿çš„约æŸã€‚因为Xiè¡¨ç¤ºçš‡åŽæ‰€åœ¨çš„列å·ï¼Œæ‰€ä»¥å¦‚果存在X(k)=X(i)那么肯定存在第k个皇åŽå’Œç¬¬i个皇åŽåŒåˆ—。所以ä¸åŒåˆ—的判段æ¡ä»¶æ˜¯X(k)ï¼=X(i),1<k<i 。åˆå› ä¸ºåŒä¸€æ–œçº¿çš„ç‰¹å¾æ˜¯è¦ä¹ˆè¡Œå·å’Œåˆ—å·ä¹‹å’Œä¸å˜ï¼ˆå³é«˜å·¦ä½Žï¼‰è¦ä¹ˆæ˜¯è¡Œå·å’Œåˆ—å·åªå·®ç›¸ç­‰ï¼ˆå·¦é«˜å³ä½Žï¼‰ï¼Œæ‰€ä»¥åŒæ–œçº¿çš„判断æ¡ä»¶æ˜¯ i+X(i)=  k+X(k) 或 i-X(i) =k-X(k),两å¼åˆå¹¶å¾— |X(i)-X(k)|=|i-k|  。

编程基本æ€è·¯ï¼šX(j)表示一个解的空间,j表示行数,里é¢çš„值表示å¯ä»¥æ”¾ç½®åœ¨çš„åˆ—æ•°ï¼ŒæŠ½è±¡çº¦æŸæ¡ä»¶å¾—到能放置一个皇åŽçš„çº¦æŸæ¡ä»¶(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法,当å¯ä»¥æ”¾ç½®çš‡åŽæ—¶å°±ç»§ç»­åˆ°ä¸‹ä¸€è¡Œï¼Œä¸è¡Œçš„è¯å°±è¿”å›žåˆ°ç¬¬ä¸€è¡Œï¼Œé‡æ–°æ£€éªŒè¦æ”¾çš„列数,如此åå¤ï¼Œç›´åˆ°å°†æ‰€æœ‰è§£è§£å‡ºã€‚

#include <iostream.h>
#include <math.h>
/*检查å¯ä¸å¯ä»¥æ”¾ç½®ä¸€ä¸ªæ–°çš„皇åŽ*/
bool place(int k, int *X)
{
        int i;
        i=1;
        while(i<k)
        {
                  if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))
                  return false;
                  i++;
         }
        return true;
}

/*求解问题的所有解*/
void Nqueens(int n,int *X)
{
       int k;
       X[1]=0;k=1;
       while(k>0)
       {
             X[k]=X[k]+1; //䏿–­çš„在解空间里从å°åˆ°å¤§çš„试探

             while((X[k]<=n)&&(!place(k, X)))
                      X[k]=X[k]+1;                     //ä¸ç¬¦åˆæ¡ä»¶çš„马上å†å–解空间的下一个值æ¥è¯•探。

             if(X[k]<=n)   //找到了一个ä½ç½®ï¼Œè€Œä¸”æ˜¯åˆæ³•çš„
                  if(k==n)   //æ˜¯ä¸æ˜¯æœ€åŽä¸€ä¸ªçš‡åŽï¼Œè‹¥æ˜¯åˆ™å¾—出一个完整解
                 {
                          for(int i=1;i<=n;i++)
                          cout<<X[i]<<" ";
                          cout<<"/n";
                   }
                  else    //è‹¥ä¸æ˜¯æœ€åŽä¸€ä¸ªçš‡åŽï¼Œåˆ™ç»™ä¸‹ä¸€ä¸ªçš‡åŽæ‰¾ä½ç½®
                 {
                          k=k+1;
                          X[k]=0;
                 }

             else      k=k-1;  //若是找了全部的列都无法放置æŸä¸ªçš‡åŽï¼Œåˆ™å›žæº¯åˆ°ä¸Šä¸€ä¸ªk的情况,让上一个kå†å¾€ä¸‹è¯•
        }

}
/*主函数*/

void main()
{
        cout<<"|--------------N皇åŽé—®é¢˜--------------|"<<endl;
        cout<<"|-------------------------------------|"<<endl<<endl;
        int n;
        int *X;
        int i;
        while(i)
       {
                 cout<<"请输入皇åŽçš„个数:";
                 cin>>n;
                 X=new int[n];
                 cout<<"问题的解有:"<<endl;
                 Nqueens(n,X);
                 cout<<"Press<1> to run again"<<endl;
                 cout<<"Press<0> to exit"<<endl;
                 cin>>i;
         }
æ­¤æ¡ç›®å‘表在代ç ç‰‡æ®µ, 算法分类目录。将固定链接加入收è—夹。