#include?
#include
#include
#include

using?namespace?std;

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


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

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

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

//輸出一個解此解以圖形的方式顯示出來
void?printPicture（int?n）
{
????number++;//每次輸出一個解?數目加一
????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]?=?‘-‘;//此解對應的棋盤的布局中皇后的位置
????????????else
????????????????table[j][k]?=?‘*‘;???//沒有放置皇后的用黑塊表示

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

}

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

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

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

????????}

}

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

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

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????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