算法設(shè)計(jì)與分析 課件 第六章 回溯法6.3.2 n皇后問(wèn)題

計(jì)算機(jī)算法設(shè)計(jì)與分析第6章回溯法6.3.2

n皇后問(wèn)題在一個(gè)n×n個(gè)方格的棋盤(pán)中，需要放置n個(gè)皇后，根據(jù)國(guó)際象棋的規(guī)則，任意兩個(gè)皇后不能處在同一行、同一列或同一斜線上，否則兩個(gè)皇后會(huì)彼此攻擊。下圖所示為n=4個(gè)皇后的一個(gè)合理擺放方案，試給出滿足條件的所有擺放方案。解空間向量--n皇后問(wèn)題用一個(gè)n元組x[1],x[2],...x[n]表示n后問(wèn)題的解，其中x[i]表示皇后i放置在棋盤(pán)的第i行的第x[i]列上。子集樹(shù)—n皇后問(wèn)題GDC3×

2×

1×

2×

1×

4...3...3×

2×

1×

4×

1×

3×

2×

4×

3×

4×

3×

2×

1×

4×

2×

1×

解ABEFHI約束條件—n皇后問(wèn)題①x[i]≠x[j],i≠j②x[i]-i≠x[j]-j(斜率-1)

i-j≠x[i]-x[j]③x[i]+i≠x[j]+j(斜率+1)

i-j≠x[j]-x[i]將②和③合并為一個(gè)條件：|i-j|≠|(zhì)x[i]-x[j]|剪枝判斷函數(shù)代碼實(shí)現(xiàn)//判斷第k行的皇后是否與前面已放置的皇后發(fā)生沖突？intjudge(intk){inti=1;while(i<k){//與1~k-1之前的皇后進(jìn)行判斷if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))//列或?qū)蔷€沖突return0;i++;}return1;}n皇后遞歸回溯代碼voidrecursion_queen(intt,intn){ if(t>n){ for(inti=1;i<=n;i++) printf("(%d,%d)",i,x[i]); count++; printf("-------這是其中第%d個(gè)解",count); printf("\n"); }else for(inti=1;i<=n;i++){ x[t]=i; if(judge(t)) recursion_queen(t+1,n); }}n個(gè)皇后位置都搜索完畢，輸出結(jié)果，記錄成功次數(shù)對(duì)皇后t去嘗試第t行的每一個(gè)列位置若滿足約束條件，則遞歸考慮下一個(gè)皇后時(shí)間復(fù)雜度分析n皇后問(wèn)題實(shí)際上就是在解向量x1,x2,...,xn的全排列中找到符合條件的解，當(dāng)整個(gè)解空間向量被全部搜索時(shí)，需要時(shí)間為O(n!)。另外，由judge函數(shù)可以看出每選擇一個(gè)位置，需要對(duì)沿列方向主副對(duì)角線方向進(jìn)行判斷，隨著層次增加而增加，判斷次數(shù)為：1+2+3+...+n=(n+1)×n/2，因此，n皇