#include?
#include
#include
#include

using?namespace?std;

//全局變量
const?int?MAX?=?30;??//最多的皇后個數(shù)
int?col[MAX+1];??????//表示放置后每個皇后的列數(shù)
int?number?=?0;????//解的數(shù)目


//輸出一個解此解以數(shù)字的方式顯示出來
void?printNumber（int?n）
{
????number++;//每次輸出一個解?數(shù)目加一

????cout<<“第“;
????cout.width（2）;
????cout<????//輸出
????for（int?i=1;?i<=n;?i++）
????{

????????cout<????}
????cout?<}

//輸出一個解此解以圖形的方式顯示出來
void?printPicture（int?n）
{
????number++;//每次輸出一個解?數(shù)目加一
????char?table[n+1][n+1];?//表示棋盤

????cout<<“第“;
????cout.width（2）;
????cout<????//棋盤的初始化和輸出
????for（int?j=1;?j<=n;?j++）
????{
????????for（int?k=1;?k<=n;?k++）
????????{
????????????if（col[j]?==?k）
????????????????table[j][k]?=?‘-‘;//此解對應(yīng)的棋盤的布局中皇后的位置
????????????else
????????????????table[j][k]?=?‘*‘;???//沒有放置皇后的用黑塊表示

????????????//輸出
????????????cout<<“?“<
????????}
????????cout<????}

}

//在（row?cols）位置是否可以放置一個皇后
bool?ifFind（int?row?int?cols）
{
????//對前row-1?行所放置的皇后進(jìn)行一一比較
????for（int?i=1;?i?????????//如果前row-1?行所放置的某一個皇后的列數(shù)與cols相同或者
????????//和（row，cols）在同一對角線上，則（row?cols）位置不能放置皇后
????????if（col[i]==cols?||?（abs（i-row））==abs（col[i]-cols））
????????????return?false;
????//沒有產(chǎn)生相同列數(shù)和同一對角線
????return?true;
}

//放置皇后，采用回溯法
//第k個皇后放在第k行，需要放?n個皇后
void?placeBack（int?k??int?n）
{
????//結(jié)束條件
????if（k>n）
????{
?????????printNumber（n）;??//打印最終結(jié)果的數(shù)據(jù)表示
//????????printPicture（n）;???//打印圖形
????}

????else
????????//在第k行窮舉所有位置，逐一試探第k行的所有列
????????for（int?i=1;?i<=n;?i++?）
????????{
????????????//判斷第i列是否可以，如果可以則遞歸調(diào)用place（）
????????????//繼續(xù)在k+1行窮舉
????????????if（ifFind（k?i））?//在（k，i）位置是否可以放置皇后
????????????{
????????????????col[k]?=?i;
????????????????placeBack（k+1?n）;//遞歸調(diào)用place（），進(jìn)行下一行的試探和放置
????????????}

????????}

}

//優(yōu)化后的回溯方法第一步應(yīng)該先初始化col[]數(shù)組
void?initializationCol（int?n）
{
????number?=?0;???//解的數(shù)目
????//將每一行先填上一個皇后，保證每個皇后不在同一列
????for（int?i=1;?i<=n;?i++）
????????col[i]?=?n-i+1;
}

//放置皇后，采用優(yōu)化的回溯方法
//思想是全排列，先將皇后放好一個位置，保證沒有同行和同列的
//然后交換皇后，從前往后交換，實(shí)現(xiàn)沒有相同對角線的
void?placeOther（int?*theCol?int?n?int?beginRow）
{
????//判斷輸入的變量是否有效
????if（theCol?==?NULL?||?n>30）
????????cout<<“變量有誤~“;
????//建兩個數(shù)組來判斷對角線上是不是沖突
????bool?leftDown[2*n+1];??//用來判斷從左下到右上這個對角線方向是不是已經(jīng)有皇后
????bool?leftUp[2*n+1];????//用來判斷從左上到右上下這個對角線方向是不是已經(jīng)有皇后
????//初始化bool數(shù)組
????memset（leftDownfalsesizeof（leftDown））;
????memset（leftUpfalsesizeof（leftUp））;
????//如果已經(jīng)沒有了要交換的皇后，也就是一個已經(jīng)確定的順序
????if（（beginRow?==?n））
????{
????????bool?canPrint?=?true;
????????for（int?i=1;?i<=n;?i++）
????????{
????????????//如果從第一行開始，每一個皇后所在的主對角線和副對角線上已經(jīng)有其他皇后
????????????if（leftDown[i+theCol[i]]?||?leftUp[n+i-theCol[i]]）
????????????{
????????????????//不能打印出來
????????????????canPrint?=?false;
????????????????//因?yàn)檫@個順序不滿足要求，所以將判斷的數(shù)組重置
????????????????leftDown[i+theCol[i]]?=?leftUp[n+i-theCol[i]]?=?false;
????????????????//跳出循環(huán)
?????????????

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2017-03-05?09:03??nQueen\
?????目錄???????????0??2017-02-26?10:24??nQueen\bin\
?????目錄???????????0??2017-03-02?21:40??nQueen\bin\Debug\
?????文件?????1064404??2017-03-02?21:40??nQueen\bin\Debug\nQueen.exe
?????文件????????5220??2017-03-02?21:40??nQueen\main.cpp
?????文件????????1327??2017-02-28?01:40??nQueen\newWay.cpp
?????文件????????1103??2017-02-28?02:08??nQueen\nQueen.cbp
?????文件?????????178??2017-03-02?18:43??nQueen\nQueen.depend
?????文件?????????361??2017-03-05?09:03??nQueen\nQueen.layout
?????目錄???????????0??2017-02-26?10:24??nQueen\obj\
?????目錄???????????0??2017-03-02?21:40??nQueen\obj\Debug\
?????文件???????20175??2017-03-02?21:40??nQueen\obj\Debug\main.o
?????文件????????3070??2017-02-28?01:41??nQueen\obj\Debug\newWay.o