題目
設(shè)在初始狀態(tài)下在國(guó)際象棋棋盤(pán)上沒(méi)有任何棋子(皇后)。然后順序在第1行贬循，第2行……第8行上布放棋子。在每一行中有8個(gè)可選擇位置桃序，但在任一時(shí)刻杖虾，棋盤(pán)的合法布局都必須滿(mǎn)足3個(gè)限制條件，即任何兩個(gè)棋子不得放在棋盤(pán)上的同一行媒熊、或者同一列奇适、或者同一斜線上。試編寫(xiě)一個(gè)遞歸算法芦鳍，求解并輸出此問(wèn)題的所有合法布局嚷往。（提示：用用回溯法。在第n行第j列安放一個(gè)棋子時(shí),需要記錄在行方向柠衅、列方向皮仁、正斜線方向、反斜線方向的安放狀態(tài)，若當(dāng)前布局合法贷祈，可向下一行遞歸求解趋急，否則可移走這個(gè)棋子，恢復(fù)安放該棋子前的狀態(tài)付燥，試探本行的第j+1列宣谈。）
代碼
#include <iostream>
#include <set>
using namespace std;//<-這樣寫(xiě)不好，懶得改了
set<int> usedCol;
set<int> usedDiag;
set<int> usedADiag;//分別用于標(biāo)記已經(jīng)有棋子的列键科、對(duì)角線闻丑、反對(duì)角線
int record[8];//用于記錄解中每一行所放棋子的位置
int ans = 0;//解的個(gè)數(shù)
bool queen(int);
int main()
{
queen(1);//從第一行開(kāi)始
cout << ans << endl;
return 0;
}
bool queen(int i)
{
bool flag = 0;//返回值，標(biāo)記本行是否有合法位置
if(i == 8)
{
for(int j = 1; j <= 8; ++j)
//不合法勋颖，直接試探下一列
if(usedCol.find(j)!=usedCol.end() ||
usedDiag.find(i-j)!=usedDiag.end() ||
usedADiag.find(i+j)!=usedADiag.end())
continue;
//合法嗦嗡，輸出一個(gè)解
else
{
flag = 1;
ans++;
for(int cnt = 0; cnt < 7; ++cnt)
cout << '(' << cnt+1 << ',' << record[cnt] << ')';
cout << "(8," << j << ')' << endl;
}
return flag;
}
for(int j = 1; j <= 8; ++j)
//不合法，直接試探下一列
if(usedCol.find(j)!=usedCol.end() ||
usedDiag.find(i-j)!=usedDiag.end() ||
usedADiag.find(i+j)!=usedADiag.end())
continue;
else
{
//放置棋子
usedCol.insert(j); usedDiag.insert(i-j); usedADiag.insert(i+j);
record[i-1] = j;
//下一行有合法位置
if(queen(i+1))
flag = 1;
usedCol.erase(j); usedDiag.erase(i-j); usedADiag.erase(i+j);
}
return flag;
}
