八皇后問題二維數(shù)組方法帶分析的詳細(xì)程序

1、問題：將八個(gè)皇后放入 8*8 的方格中，她們不相互攻擊（每個(gè)皇后都能攻擊同行 同列同一條斜線上的棋子）。分析：定義一個(gè)二維數(shù)組z99 （用行列的1-8，數(shù)組的每個(gè)元素的初值為1）表示 8*8 的棋盤， 8 個(gè)皇后互相不能攻擊，則每行只有一個(gè)皇后，一位數(shù)組 a9 ， ai是第i行所在的列（例如a1=2,表示第1行上的皇后在第2歹U）。約束條 件：第 t 個(gè)皇后不與前1-t 個(gè)皇后同行同列同斜線。故放下第 t 個(gè)皇后要改變棋盤的布局，從此皇后的位置向下，與她同列同斜線上的元素都標(biāo)記為0。、第一個(gè)皇后可以放在第一行的（1-8）任意位置，故用for 循環(huán)，保證第一個(gè)皇后可以從第一個(gè)位置循環(huán)放到第八個(gè)位

2、置，將第一行的皇后放好，根據(jù)約束條件改變棋盤布局，即改變z 的值，然后調(diào)用本身即 A2、放第二個(gè)皇后之前把棋盤的布局（z 的所有元素的值）保存到 x中。由于第一個(gè)皇后已放好，并影響后面其他的皇后，第二個(gè)皇后要根據(jù)z2i判斷哪里能放，若z2i=1 ，表示可以放下，由于可以放的位置不止一個(gè)，故還要用 for 循環(huán)來控制，放下后根據(jù)約束條件改變z ，調(diào)用本身 A3、重復(fù)步驟2。若第t行全為0即ztN+1中所有元素都是0,返回上一次 調(diào)用。將此行（返回后的那行）上的皇后往后移動(dòng)，在移動(dòng)之前要將布局更新，即讓 z=x ，移動(dòng)到滿足約束條件，若都不滿足則返回上一級(jí)調(diào)用，重復(fù)步驟3。若t=8,滿足放入棋盤的

3、約束條件，則放入，并輸出結(jié)果，返回上一級(jí)調(diào)用，繼續(xù)查找合適的位置。#include#define N 8void A(int t);int zN+1N+1;int w=1;/ 只在結(jié)果輸出時(shí)用到，控制是否輸出“-”int aN+1=0;/定義數(shù)組a并初始全部元素賦值為0void main()int i,j;for(i=1;i=N;i+)for(j=1;j=N;j+)zij=1;/ 對二維數(shù)組初始化printf( 八皇后問題的解：n);A(1);/ 從第 1 個(gè)皇后開始 void A(int t)int i,y,t1,t2,d1,d2;int xN+1N+1;/ 用來存放 t 皇后放入棋盤之前，

4、棋盤的狀態(tài)if(t=1)for(d1=1;d1=N;d1+)for(d2=1;d2=N;d2+)xd1d2=zd1d2;/讓二維數(shù)組x等于t皇后放入前棋盤狀態(tài) zfor(i=1;i=N;i+)for(d1=1;d1=N;d1+)for(d2=1;d2=N;d2+)zd1d2=xd1d2;/將未放t時(shí)的初始狀態(tài)給z口口,每次返回時(shí)或調(diào)度進(jìn)入 時(shí)執(zhí)行at=i;t1=i;t2=i;for(y=t+1;y=N;y+)/改變棋盤布局zyi=0;t 所在列if(t11)zy-t2=0;/ 向左下延伸的的斜線A(t+1);elseif(t=N)for(d1=1;d1=N;d1+)for(d2=1;d2=N;d2+)xd1d2=zd1d2;/讓二維數(shù)組x等于t皇后放入前棋盤狀態(tài)z口口for(i=1;i=N;i+)for(d1=1;d1=N;d1+)for(d2=1;d2=N;d2+)zd1d2=xd1d2;/將未放t時(shí)的初始狀態(tài)給z口口,每次返回時(shí)或調(diào)度進(jìn)入 時(shí)執(zhí)行 if(zti)/ 判斷 zti 是否能夠放下 tat=i;t1=i;t2=i;if(t=N)如果最后一個(gè)也放入了則輸出結(jié)果printf(第d種解：n,w+);for(d1=1;d1”,d1,d1,ad1);printf(n);else/zti 為 0if(i=N)/t 行的所有元素為 0return;continue;繼續(xù) for