法一矩陣維護(hù)法，思路相對(duì)簡(jiǎn)單的方法
cheese_table為8*8的棋盤(pán)，queen數(shù)組記錄八個(gè)皇后各自的列數(shù)（前面說(shuō)過(guò)，第N個(gè)皇后默認(rèn)放在第N行，所以行數(shù)是隱式記錄的），lastqueen記錄著最后放置的那個(gè)皇后的列數(shù)（回溯時(shí)候很重要，保證回溯到上一行操作時(shí)候不會(huì)踏進(jìn)同一個(gè)坑即不會(huì)再把皇后放到剛剛放過(guò)的地方），solution記錄八皇后有幾種放的方法。Search_line（i，j）函數(shù)將會(huì)搜尋第i行從j列開(kāi)始還有沒(méi)可以放的格子，set_queen（i，j）就是在可放皇后的(I,j)格子放下皇后，并且在棋盤(pán)上對(duì)放下的這個(gè)皇后的行列和主副對(duì)角線的格子進(jìn)行標(biāo)記，標(biāo)記的方法是代表這些格子的數(shù)+1（這是本解法很關(guān)鍵的一點(diǎn)，并不是簡(jiǎn)簡(jiǎn)單單的對(duì)這些不可放置點(diǎn)從一個(gè)狀態(tài)比如0置為1代表不可放置了，而是每次把某個(gè)皇后對(duì)應(yīng)影響的這些格子的數(shù)都增加1，這么做極大的好處就是你回溯的時(shí)候只要逆著過(guò)去對(duì)拿走的皇后本會(huì)影響的格子減1即可，而不需要判斷這些格子是否還會(huì)被其他在棋盤(pán)上的的皇后影響從而決定維持不可放的狀態(tài)還是變?yōu)榭煞诺臓顟B(tài)，極大的減少了維護(hù)棋盤(pán)時(shí)候大量調(diào)用判斷函數(shù)的時(shí)間，而只要簡(jiǎn)單的加減即可）。Uptate_queen（i）函數(shù)就是拿起第i行的皇后，即本解法的回溯部分，對(duì)應(yīng)set的過(guò)程你這做即可。最后看看主函數(shù)，初始化不說(shuō)了，for循環(huán)中大致過(guò)程就是對(duì)每一行search出皇后可放位置，找到可放格子就放下皇后，如果八個(gè)皇后都放完了記一次數(shù)，并且在最后一行尋找是否有其他放皇后的位置，沒(méi)有的話(huà)往前一行回溯；剛剛在某一行search不到放皇后的格子就只能回溯上一行。如果發(fā)現(xiàn)這一行就是第0行沒(méi)有上一行了還要回溯，證明我們算法結(jié)束了，退出循環(huán)。這個(gè)for循環(huán)大概是假的for循環(huán)，沒(méi)有限定i的大小，依靠的其實(shí)是想要回溯之前看看還能不能回溯來(lái)跳出。
#include <iostream>
using namespace std;
int cheese_table[8][8];
int queen[8];//記錄皇后的列數(shù)
int lastqueen=-1;
int solution=0;
int search_line(int i,int j) //搜索這一行有沒(méi)有可以放的位置
{
for(;j<8;j++)
if(cheese_table[i][j]==0)
return j; //返回可放位置位于第幾列
return -1; //返回-1說(shuō)明沒(méi)有可放的位置
}
void set_queen(int i,int j)//在可放的位置上放置皇后記錄下來(lái)并對(duì)棋盤(pán)進(jìn)行操作
{
cheese_table[i][j]=-1;
queen[i]=j;
int temp;
for(temp=0;temp<8;temp++)//列操作
if(cheese_table[temp][j]!=-1) //為什么有條件cheese_table[temp][j]!=-1，
cheese_table[temp][j]++; //因?yàn)椴荒茏屗约旱奈恢眉?。
for(temp=0;temp<8;temp++)//行操作
if(cheese_table[i][temp]!=-1)
cheese_table[i][temp]++;
int tempj=j+1,tempi;
for(tempi=i+1;tempi<8&&tempj<8;tempi++)
cheese_table[tempi][tempj++]++;
tempj=j-1;
for(tempi=i+1;tempi<8&&tempj>=0;tempi++)//西南對(duì)角線操作
cheese_table[tempi][tempj--]++;
tempj=j+1;
for(tempi=i-1;tempi>=0&&tempj<8;tempi--)//東北對(duì)角線操作
cheese_table[tempi][tempj++]++;
tempj=j-1;
for(tempi=i-1;tempi>=0&&tempj>=0;tempi--)//西北對(duì)角線操作
cheese_table[tempi][tempj--]++;
return;
}
void uptake_queen(int i) //回溯部分，撤回當(dāng)前皇后
{
int j=queen[i];
int temp;
for(temp=0;temp<8;temp++)
if(cheese_table[temp][j]!=-1)
cheese_table[temp][j]--;
for(temp=0;temp<8;temp++)
if(cheese_table[i][temp]!=-1)
cheese_table[i][temp]--;
int tempj=j+1,tempi;
for(tempi=i+1;tempi<8&&tempj<8;tempi++)
cheese_table[tempi][tempj++]--;
tempj=j-1;
for(tempi=i+1;tempi<8&&tempj>=0;tempi++)
cheese_table[tempi][tempj--]--;
tempj=j+1;
for(tempi=i-1;tempi>=0&&tempj<8;tempi--)
cheese_table[tempi][tempj++]--;
tempj=j-1;
for(tempi=i-1;tempi>=0&&tempj>=0;tempi--)
cheese_table[tempi][tempj--]--;
cheese_table[i][j]=0;
return;
}
void print_cheese()
{
int i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(cheese_table[i][j]==-1)
cout<<"x ";
else
cout<<"0 ";
}
cout<<endl;
}
cout<<endl;
return;
}
int main()
{
int i,j;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
cheese_table[i][j]=0;
//初始化棋盤(pán)
for(i=0;;i++)
{
j=search_line(i,lastqueen+1);//判斷是否第i行有可放位置，若有返回列數(shù)，沒(méi)有就返回-1，
if(j==-1) //其中若第i行某列是0，但它下一行沒(méi)有可放的，就要回溯同時(shí)用lastqueen將其記錄，
{ //然后從第i行l(wèi)astqueen+1列繼續(xù)判斷是否可放
if(i==0) break;
uptake_queen(i-1); //下一行沒(méi)有空位置，回到本行剛剛找到的空位置，將其取消，
lastqueen=queen[i-1]; //然后從它的下一個(gè)位置開(kāi)始從新找符合的空位置
i=i-2; //因?yàn)閳?zhí)行完后馬上要執(zhí)行i++
}
else
{
lastqueen=-1; //本行有空位置，令lastqueen=-1為下一行從零開(kāi)始找空位做鋪墊
set_queen(i,j); //本行有空位置，開(kāi)始對(duì)本行操作，將它相關(guān)的行列和對(duì)角線加1.
if(i==7)
{
solution++; //方案+1
print_cheese(); //打印圖形
uptake_queen(7); //由于是最后一行，此空位后面的位置可能還有成立的，所以把此位置回溯，繼續(xù)找他下一個(gè)位置看還有沒(méi)有成立的。
lastqueen=j;
i--;
}
}
}
cout<<solution<<endl;
return 0;
}
法二
遞歸法1！這里用了分支修剪的方法。解釋不夠，思路懂，具體backtrack的實(shí)現(xiàn)原理沒(méi)看懂，找時(shí)間查具體原理再好好看。
#include <stdio.h>
#include <stdlib.h>
#define N 8
int column[N+1]; // 同欄是否有皇后，1表示有
int rup[2*N+1]; // 右上至左下是否有皇后
int lup[2*N+1]; // 左上至右下是否有皇后
int queen[N+1] = {0};
int num; // 解答編號(hào)
void backtrack(int); // 遞回求解
int main(void) {
int i;
num = 0;
for(i = 1; i <= N; i++)
column[i] = 1;
for(i = 1; i <= 2*N; i++)
rup[i] = lup[i] = 1;
backtrack(1);
return 0;
}
void showAnswer() {
int x, y;
printf("\n解答 %d\n", ++num);
for(y = 1; y <= N; y++) {
for(x = 1; x <= N; x++) {
if(queen[y] == x) {
printf(" Q");
}
else {
printf(" .");
}
}
printf("\n");
}
}
void backtrack(int i)
{
int j;
if(i > N) {
showAnswer();
}
else
{
for(j = 1; j <= N; j++)
{
if(column[j] == 1 &&
rup[i+j] == 1 && lup[i-j+N] == 1)
{
queen[i] = j;
// 設(shè)定為占用
column[j] = rup[i+j] = lup[i-j+N] = 0;
backtrack(i+1);
column[j] = rup[i+j] = lup[i-j+N] = 1;//如果某一次還沒(méi)到8但已經(jīng)沒(méi)有可放的了，
} //比如執(zhí)行到第五排有放的，但第六排沒(méi)有放的了，
} //那么在執(zhí)行第六排的時(shí)候會(huì)將整個(gè)的for執(zhí)行完后結(jié)束所有第六排的工作，
} //然后跳回第五排執(zhí)行column[j] = rup[i+j] = lup[i-j+N] = 1;
} //然后第五排繼續(xù)j+1往下執(zhí)行，這兒其實(shí)就有了自動(dòng)的回溯！
部分答案截圖：
遞歸法2！
//八皇后遞歸解法
#include<iostream>
using namespace std;
int queen[9]={-1,-1,-1,-1,-1,-1,-1,-1,-1};
int count=0;
bool available(int pointi,int pointj)
{//判斷某個(gè)皇后是否與已有皇后沖突
for(int i=1;i<pointi;i++)
{
if(pointj==queen[i])return false;//同一列拒絕
if((pointi-i)==(pointj-queen[i]))return false;//同一主對(duì)角線拒絕
if((pointi-i)+(pointj-queen[i])==0)return false;//同一副對(duì)角線拒絕
}
return true;
}
void printit(int queen[9])
{
int i;
for(i=1;i<9;i++)
{
cout<<queen[i]<<' ';
}
cout<<endl;
}
void findSpace(int queenNumber)
{//在第queenNumber行找能放皇后的位置
for(int i=1;i<9;i++)
{//從1~8遍歷這一行的八個(gè)空位
if(available(queenNumber,i))
{
//如果可以放這個(gè)位置就記錄下第queenNumber個(gè)皇后的位置
queen[queenNumber]=i;
if(queenNumber==8)
{//如果八個(gè)皇后都放滿(mǎn)了統(tǒng)計(jì)一下
printit(queen);
count++;
return;
}
int nextNumber=queenNumber+1;//還有皇后沒(méi)放遞歸放下一個(gè)皇后
findSpace(nextNumber);
}
}
queen[--queenNumber]=-1;//如果這一行沒(méi)有可放的位置說(shuō)明上一行皇后放的位置不行，要為上一個(gè)皇后尋找新的可放位置
return;
}
int main()
{
findSpace(1);//從（1，1）開(kāi)始遞歸好理解
cout<<endl;
cout<<count<<endl;
return 0;
}
答案每一行表示八個(gè)皇后所在行的列數(shù)
