八皇后问题的非递归实现
2008-03-08 21:27:07 来源：WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁惧墽鎳撻—鍐偓锝庝簻椤掋垺銇勯幇顖毿撻柟渚垮妼椤粓宕卞Δ鈧獮濠勭磽閸屾艾鈧懓顫濋妸鈺佺疅缂佸顑欓崥瀣煕椤愵偅绶氱紓鍐╂礋濮婂宕掑▎鎴М濠电姭鍋撻梺顒€绉甸幆鐐哄箹濞ｎ剙濡肩紒鎰殜閺屸€愁吋鎼粹€茬敖婵炴垶鎸哥粔鐢稿Φ閸曨垰鍐€妞ゆ劦婢€濞岊亪姊虹紒妯诲蔼闁稿海鏁诲濠氭晲婢跺﹤宓嗛梺缁樺姈缁佹挳宕戦幘璇叉嵍妞ゆ挻绋戞禍鐐叏濡厧浜鹃悗姘炬嫹
闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁惧墽鎳撻—鍐偓锝庝簼閹癸綁鏌ｉ鐐搭棞闁靛棙甯掗～婵嬫晲閸涱剙顥氬┑掳鍊楁慨鐑藉磻濞戔懞鍥偨缁嬫寧鐎梺鐟板⒔缁垶宕戦幇鐗堢厵缂備焦锚缁椦囨煃瑜滈崜锕傚矗閸愵煈娼栭柛婵嗗珔瑜斿畷鎯邦槾濞寸姴銈稿铏规嫚閼碱剛顔夐梺鐓庣秺缁犳牠骞冩ィ鍐╁€婚柦妯侯槼閹芥洟姊洪棃娑辨濠碘€虫喘瀹曘垽鎮介崨濞炬嫼闁荤喐鐟ョ€氱兘宕箛娑欑厱闁绘ê纾晶鐢告煏閸℃鈧湱缂撴禒瀣窛濠电姴瀚獮鍫ユ⒑绾懎顥嶉柟娲讳簽濡叉劙寮撮悢鍝勨叞闂傚倸鍊风欢姘缚瑜嶇叅闁靛牆娲犻崑鎾愁潩椤愩垹绁梺缁樹緱閸ｏ綁鐛幒鎳虫棃鍩€椤掑倻涓嶉柨婵嗘缁♀偓闂傚倸鐗婄粙鎴﹀汲濞嗗緷鐟扳堪閸垻鏆梺鍝勭焿缂嶄焦鎱ㄩ埀顒勬煃閹増纭炬繝鈧潏銊х彾闁哄洨鍠撶弧鈧┑顔斤供閸橀箖宕㈤悽鍛娾拺缂備焦锚婵箓鏌涢幘鏉戝摵闁诡喗蓱濞煎繘濡搁妶鍥╃暰闂備礁婀辩划顖滄暜閻愬瓨娅犳繛鎴炴皑绾捐偐绱撴担璐細婵炴彃顕埀顒冾潐濞叉牕鐣烽鍐簷闂備礁鎲￠崝鏇㈠疮閻樿绀堟繝闈涚墛瀹曞弶绻涢幋鐐ㄧ細闁哄棗妫楅埞鎴︽偐鏉堫偄鍘￠梺杞扮劍閻楁粎妲愰幘瀛樺濞寸姴顑呴幗鐢告⒑閸︻厽鍤€婵炲眰鍊濋幃楣冩倻閽樺顔婇梺瑙勬儗閸樹粙宕撻悽鍛娾拺闁荤喐婢橀幃渚€鏌ｉ幒鐐电暤闁诡喗顨婇獮鏍ㄦ媴閸忓瀚藉┑鐐舵彧缁插潡宕曢妶澶婂惞闁逞屽墴濮婃椽骞栭悙娴嬪亾閺嶎厽鍋嬮柣妯垮吹瀹撲線鐓崶銊р姇闁哄懏鎮傞弻銊╂偆閸屾稑顏�
婵犵數濮烽弫鍛婃叏閻戣棄鏋侀柛娑橈攻閸欏繘鏌ｉ幋锝嗩棄闁哄绶氶弻娑樷槈濮楀牊鏁鹃梺鍛婄懃缁绘垿濡甸崟顖氱闁告鍋熸禒鑲╃磽娴ｅ搫顎岄柛銊ョ埣瀵鈽夐姀鐘电杸闂傚倸鐗婄粙鎺楁倶閸儲鍊甸柣鐔哄閸熺偟绱掔拠鎻掓殻濠碉紕鏁诲畷鐔碱敍濮橀硸鍟嬮梺璇查叄濞佳囧箺濠婂牊鍋╁┑鍌氭啞閳锋垹鐥鐐村婵炲吋鍔栫换娑㈡嚑椤掆偓閺嬪孩銇勯銏㈢缂佽鲸甯掕灒闁兼祴鏅滈崵宀勬⒒娓氣偓閳ь剛鍋涢懟顖涙櫠椤旇偐鏆嗛柨婵嗙墕閸斿灚銇勯敂鐣屽弨闁诡噯绻濇俊鑸靛緞鐎ｎ剙甯鹃梻浣稿閸嬪懐鎹㈤崘顔肩；妞ゅ繐鎳愮粻鍓р偓鐟板閸犳洜鑺辨繝姘畾闁绘柨鍚嬮埛鎴︽倵閸︻厼校闁靛棗鍟撮弻銈夊礃閼碱剙鐓熼悗瑙勬礃缁诲牓寮崘顔肩劦妞ゆ帒瀚ч埀顒佹瀹曟﹢顢欓崲澹洦鐓曢柍鈺佸枤濞堟﹢鏌ｉ悢绋垮婵﹥妞介幃鈩冩償閳╁啯鐦ｉ梻浣虹帛閻楁洟濡剁粙璺ㄦ殾闁绘垶岣跨弧鈧梺鎼炲劀閸愩劎銈梻鍌欑窔濞佳勵殽韫囨洘顫曢柡鍥ュ灩閸屻劍銇勮箛鎾跺闁抽攱鍨块弻鐔兼嚃閳轰椒绮堕梺鍛婃⒐椤ㄥ﹪寮婚敓鐘插窛妞ゆ棃鏁慨鍥╃磽娴ｇǹ鈧湱鏁悢濡撳洨鈧潧鎽滅壕濂稿级閸稑濡肩紒妤佺缁绘盯鎮℃惔锝囶啋闂佺硶鏂侀崜婵嬪箯閸涘瓨鐓ラ悗锝呯仛缂嶆姊婚崒姘偓宄懊归崶褜娴栭柕濞炬櫆閸婂潡鏌ㄩ弴鐐测偓鍝ョ不閺屻儲鐓曢柕澶樺枛婢ь噣鏌＄€ｂ晝绐旈柡宀€鍠栧畷婊嗩槾閻㈩垱鐩弻锟犲川椤旇棄鈧劙鏌＄仦璇插闁诡喓鍊濆畷鎺戔槈濮楀棔绱�闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁惧墽鎳撻—鍐偓锝庝簻椤掋垺銇勯幇顖毿撻柟渚垮妼椤粓宕卞Δ鈧獮濠勭磽閸屾艾鈧懓顫濋妸鈺佺疅缂佸顑欓崥瀣煕椤愵偅绶氱紓鍐╂礋濮婂宕掑▎鎴М濠电姭鍋撻梺顒€绉甸幆鐐哄箹濞ｎ剙濡肩紒鎰殜閺屸€愁吋鎼粹€茬敖婵炴垶鎸哥粔鐢稿Φ閸曨垰鍐€妞ゆ劦婢€濞岊亪姊虹紒妯诲蔼闁稿海鏁诲濠氭晲婢跺﹤宓嗛梺缁樺姈缁佹挳宕戦幘璇叉嵍妞ゆ挻绋戞禍鐐叏濡厧浜鹃悗姘炬嫹 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻锝夊箣閿濆憛鎾绘煕閵堝懎顏柡灞诲€濆畷顐﹀Ψ閿旇姤鐦庡┑鐐差嚟婵潧顫濋妸褎顫曢柟鎹愵嚙绾惧吋绻涢崱妯虹瑨闁告﹫绱曠槐鎾寸瑹閸パ勭彯闂佹悶鍔岄悥鍏间繆閹绢喖绀冩い鏃傚帶缁愭盯姊洪崫鍕垫Ч闁搞劌缍婂畷銏犆洪鍛偓鍨殽閻愯尙浠㈤柛鏃€纰嶉妵鍕晜鐠囪尙浠搁悗瑙勬穿缁绘繈鐛惔銊﹀殟闁靛／鍐ㄥ闂傚倸饪撮崑鍕洪敃鈧叅闁哄秲鍔庢晶锟犳⒒閸屾瑦绁版い鏇嗗應鍋撻崹顐㈡诞鐎规洘绮撻幃銏＄附婢跺绋侀梻浣瑰劤缁绘劕锕㈡潏鈺侇棜闁稿繘妫跨换鍡樸亜閺嶃劎顣查柟顖氱墛閵囧嫰顢曢姀銏㈠姱濠殿喖锕ㄥ▍锝夊箯閻樼粯鍤戞い鎺戝亞閸炶绻濆▓鍨灍閼垦囨煕閺冣偓閸ㄥ灝鐣峰ú顏勭劦妞ゆ帊闄嶆禍婊堟煙閸濆嫮肖妞わ讣绠撻弻娑㈠Χ鎼粹€斥拫闂佸搫鏈惄顖炵嵁濡吋宕夐柣鎴炨缚閳ь剝顕ч—鍐Χ鎼粹€茬盎缂備胶绮崝妤呭矗閸涱収娓婚柕鍫濇噽缁犱即鎮楀鐓庡⒋闁诡喗顨婇、姗€鎮滈崱妯虹槣闂備線娼ч悧鍡椢涘▎鎴犵焼闁逞屽墴濮婃椽鎮烽弶鎸庢瘣闂備礁搴滅徊浠嬫偩瀹勬壋鍫柛鏇ㄥ亽閸ゃ倝鏌ｆ惔銏⑩姇閼裤倝鏌熼柨瀣仢婵﹦绮粭鐔煎炊瑜岀花浠嬫⒑缁嬫鍎愰柣鈺婂灦楠炲﹪鎮㈢喊杈ㄦ櫖濠电偞鍨堕悷锕傛偟瀹勯偊娓婚柕鍫濇閻撱儱顭胯閺咁偅绔熼弴銏″亗閹兼惌鍠氶崬鐢告煟閻樼儤顏犻悘蹇嬪姂瀹曟繈鎮㈤搹鍦紲婵犮垼娉涚€涒晠顢旈悩缁樼厓鐟滄粓宕滃棰濇晩闁哄稁鍘肩粣妤呮煛瀹ュ骸骞愰柍褜鍓ㄧ粻鎾诲蓟閵娧€鍋撻敐鍌涙珖缂佺姵鑹鹃埞鎴︻敊閻ｅ瞼鐣甸梺娲诲幖閻楀棗宓勯梺缁樺灱婵倝鍩涢幋鐘电＜閻庯綆鍋掗崕銉╂煕鎼淬垹濮嶉柡宀€鍠栭幃鐑芥偋閸喐鍊烽梺鎹愬吹閸嬨倝寮诲☉銏犵疀闁宠桨绀佸敮婵犵鍓濊ぐ鍐偋婵犲嫭宕叉繛鎴欏灩楠炪垺淇婇妶鍛殶妞ゆ柨顦埞鎴︽倷閼碱剙顤€闂佹寧娲忛崹褰掞綖韫囨洜纾兼俊顖濐嚙椤庢挻淇婇悙宸剰缂併劏鍋愰幉浼村幢濞嗘垹锛濋梺绋挎湰濮樸劏鈪甸梻浣呵归鍡涘箰閼姐倖宕叉繛鎴炲焹閸嬫挸鈽夊▎瀣窗闂佹椿鍘归崐婵嬪蓟濞戙垹绠婚悹铏瑰劋閻忓牓鎮楃憴鍕婵＄偘绮欏畷娲焵椤掍降浜滈柟鍝勭Ч濡惧嘲霉濠婂嫮鐭掗柡宀€鍠栭幃婊兾熼搹閫涙樊闂備線鈧偛鑻晶顔剧磽瀹ュ拑宸ユい鏇秮楠炲海绮电€ｎ偅娅岄梻浣告啞濞诧箓宕滃☉銏犲偍闂侇剙绉甸悡鐔煎箹閹碱厼鐏ｇ紒澶愭涧闇夋繝濠傛噹閸樻挳鏌ｉ幙鍐ㄥ⒋妞ゃ垺顨婂畷鎺懳旈埀顒佺妤ｅ啯鍋℃繛鍡楃箰椤忣亞鐥幆褜鐓奸柡灞剧☉铻栭柍褜鍓熷畷顖炲锤濡ゅ﹥鏅梺鎸庣箓椤︻垳澹曡ぐ鎺撶厽闁哄洦姘ㄩ崝宥夋鐎ｎ喗鈷掗柛灞剧懅椤︼箓鏌熺喊鍗炰簻閾荤偤鎮楅棃娑欐喐濞戞挸绉归弻鐔煎箲閹伴潧娈梺钘夊暟閸犳牠寮婚弴鐔虹闁绘劦鍓氶悵鏇㈡⒑缁嬫鍎忔俊顐ｇ箞瀵鈽夊顐ｅ媰闂佸憡鎸嗛埀顒€危閸繍娓婚柕鍫濇嚇閻涙粓鏌熼崙銈嗗
核心提示：我们都知道八皇后问题是一个很经典的问题，当时很多解决八皇后问题的编程解法都是用递归解法，八皇后问题的非递归实现，下面我用非递归的解法来实现如下：
我们都知道八皇后问题是一个很经典的问题，当时很多解决八皇后问题的编程解法都是用递归解法，下面我用非递归的解法来实现如下：
#include
#define available 1 //用来标志该位是否可用，availabel表示可用，unailable表示不可
用
#define unavailable 0
#define true 1
#define false 0
int j,top=-1,flag,i,is_pop,total=0;
// top用来保存栈顶指针，flag用来说明该次是否成功下了一个皇后
//is_pop用来说明是否把栈弹出,total用来保存共有多少种下法
//i用来保存下一次皇后应下的列
int stack[8],a[15],b[15],c[7];
//stack保存皇后的位置，a,b,c三个数住用来保存该位是否可以下皇后
void init(void);//初始化各位状态，使之可以下皇后
void release (void);//当该列都不能下皇后，则解除上次下皇后试对相关位的锁定
main()
{
cout<
init();
is_pop=false;//初始化
for( ; ;)
{
do {
for (j=is_pop? stack[i]+1:0;j<=7;j++)
if (a[i+j]&&b[i-j+7]&&c[j])//判定该位是否可用
{//若可用，则栈顶指针上移，在该位存入皇后号
top++;
stack[top]=j;
a[i+j]=b[i-j+7]=c[j]=unavailable;//并把相关位设为不可用
i++;//i指向下一个应填入皇后德列
flag=true;//设标志，说明成功
is_pop=false;
break;//则直接退出循环
}
if (!flag)//若不成功，则释放被锁定的位
release();
flag=false;
if (stack[0]+1==8&&top==-1)//若第一列也没有位置可以放皇后，
goto END; //则说明没有其他的放法了，则退出
}
while (top!=7);
for (int k=0;k<=7;k++)
cout
中查找“八皇后问题的非递归实现”更多相关内容
中查找“八皇后问题的非递归实现”更多相关内容更多精彩
赞助商链接
