image.png
法一矩陣維護(hù)法，思路相對簡單的方法
cheese_table為8*8的棋盤，queen數(shù)組記錄八個皇后各自的列數(shù)（前面說過已维，第N個皇后默認(rèn)放在第N行淆攻，所以行數(shù)是隱式記錄的）阔墩，lastqueen記錄著最后放置的那個皇后的列數(shù)（回溯時候很重要嘿架，保證回溯到上一行操作時候不會踏進(jìn)同一個坑即不會再把皇后放到剛剛放過的地方），solution記錄八皇后有幾種放的方法啸箫。Search_line（i耸彪，j）函數(shù)將會搜尋第i行從j列開始還有沒可以放的格子，set_queen（i忘苛，j）就是在可放皇后的(I,j)格子放下皇后蝉娜，并且在棋盤上對放下的這個皇后的行列和主副對角線的格子進(jìn)行標(biāo)記，標(biāo)記的方法是代表這些格子的數(shù)+1（這是本解法很關(guān)鍵的一點(diǎn)扎唾，并不是簡簡單單的對這些不可放置點(diǎn)從一個狀態(tài)比如0置為1代表不可放置了召川，而是每次把某個皇后對應(yīng)影響的這些格子的數(shù)都增加1，這么做極大的好處就是你回溯的時候只要逆著過去對拿走的皇后本會影響的格子減1即可稽屏，而不需要判斷這些格子是否還會被其他在棋盤上的的皇后影響從而決定維持不可放的狀態(tài)還是變?yōu)榭煞诺臓顟B(tài)扮宠，極大的減少了維護(hù)棋盤時候大量調(diào)用判斷函數(shù)的時間，而只要簡單的加減即可）狐榔。Uptate_queen（i）函數(shù)就是拿起第i行的皇后坛增，即本解法的回溯部分，對應(yīng)set的過程你這做即可薄腻。最后看看主函數(shù)收捣，初始化不說了，for循環(huán)中大致過程就是對每一行search出皇后可放位置庵楷，找到可放格子就放下皇后罢艾，如果八個皇后都放完了記一次數(shù)，并且在最后一行尋找是否有其他放皇后的位置尽纽，沒有的話往前一行回溯咐蚯；剛剛在某一行search不到放皇后的格子就只能回溯上一行。如果發(fā)現(xiàn)這一行就是第0行沒有上一行了還要回溯弄贿，證明我們算法結(jié)束了春锋，退出循環(huán)。這個for循環(huán)大概是假的for循環(huán)差凹，沒有限定i的大小期奔，依靠的其實(shí)是想要回溯之前看看還能不能回溯來跳出。
#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) //搜索這一行有沒有可以放的位置
{
for(;j<8;j++)
if(cheese_table[i][j]==0)
return j; //返回可放位置位于第幾列
return -1; //返回-1說明沒有可放的位置
}
void set_queen(int i,int j)//在可放的位置上放置皇后記錄下來并對棋盤進(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++)//西南對角線操作
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--]++;
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;
//初始化棋盤
for(i=0;;i++)
{
j=search_line(i,lastqueen+1);//判斷是否第i行有可放位置谊娇，若有返回列數(shù)肺孤，沒有就返回-1，
if(j==-1) //其中若第i行某列是0，但它下一行沒有可放的渠旁，就要回溯同時用lastqueen將其記錄攀例，
{ //然后從第i行l(wèi)astqueen+1列繼續(xù)判斷是否可放
if(i==0) break;
uptake_queen(i-1); //下一行沒有空位置，回到本行剛剛找到的空位置顾腊，將其取消粤铭，
lastqueen=queen[i-1]; //然后從它的下一個位置開始從新找符合的空位置
i=i-2; //因?yàn)閳?zhí)行完后馬上要執(zhí)行i++
}
else
{
lastqueen=-1; //本行有空位置，令lastqueen=-1為下一行從零開始找空位做鋪墊
set_queen(i,j); //本行有空位置杂靶，開始對本行操作梆惯，將它相關(guān)的行列和對角線加1.
if(i==7)
{
solution++; //方案+1
print_cheese(); //打印圖形
uptake_queen(7); //由于是最后一行，此空位后面的位置可能還有成立的吗垮，所以把此位置回溯垛吗，繼續(xù)找他下一個位置看還有沒有成立的。
lastqueen=j;
i--;
}
}
}
cout<<solution<<endl;
return 0;
}
92種具體放法烁登，這里是部分截圖
image.png
法二
遞歸法1怯屉！這里用了分支修剪的方法。解釋不夠饵沧，思路懂锨络，具體backtrack的實(shí)現(xiàn)原理沒看懂，找時間查具體原理再好好看狼牺。
#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; // 解答編號
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;//如果某一次還沒到8但已經(jīng)沒有可放的了，
} //比如執(zhí)行到第五排有放的是钥，但第六排沒有放的了掠归，
} //那么在執(zhí)行第六排的時候會將整個的for執(zhí)行完后結(jié)束所有第六排的工作，
} //然后跳回第五排執(zhí)行column[j] = rup[i+j] = lup[i-j+N] = 1;
} //然后第五排繼續(xù)j+1往下執(zhí)行悄泥，這兒其實(shí)就有了自動的回溯虏冻！
部分答案截圖：
image.png
image.png
遞歸法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)
{//判斷某個皇后是否與已有皇后沖突
for(int i=1;i<pointi;i++)
{
if(pointj==queen[i])return false;//同一列拒絕
if((pointi-i)==(pointj-queen[i]))return false;//同一主對角線拒絕
if((pointi-i)+(pointj-queen[i])==0)return false;//同一副對角線拒絕
}
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遍歷這一行的八個空位
if(available(queenNumber,i))
{
//如果可以放這個位置就記錄下第queenNumber個皇后的位置
queen[queenNumber]=i;
if(queenNumber==8)
{//如果八個皇后都放滿了統(tǒng)計一下
printit(queen);
count++;
return;
}
int nextNumber=queenNumber+1;//還有皇后沒放遞歸放下一個皇后
findSpace(nextNumber);
}
}
queen[--queenNumber]=-1;//如果這一行沒有可放的位置說明上一行皇后放的位置不行弹囚，要為上一個皇后尋找新的可放位置
return;
}
int main()
{
findSpace(1);//從（1兄旬，1）開始遞歸好理解
cout<<endl;
cout<<count<<endl;
return 0;
}
答案每一行表示八個皇后所在行的列數(shù)
部分答案截圖
