目錄

????前言

????題目介紹

????引入：

????解決思路：

????理論存在，實踐開始！

????難點1：如何表示對角線被占領(lǐng)？

????難點2：如何用遞歸的方法來放皇后？

????難點3：如何實現(xiàn)回溯？

????難點4：如何實現(xiàn)皇后位置的輸出？

????全部代碼如下：

????總結(jié)：?

Love?is?worth?years.?熱愛可抵歲月漫長。

前言

各位和我一樣的剛學(xué)完遞歸的小白們，是不是突然遇見了一個大BOSS，八皇后????問題??！把自信的說著“老子遞歸學(xué)好了！”的你一棒子打回了出生點，就像你剛玩只狼遇到的那個大胖子，剛玩原神遇到的雪山。今天，我就和大家一起學(xué)習(xí)一下這個著名的八皇后????問題。

題目介紹

八皇后問題，是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法并輸出每一種擺法。

?升華：我在做這個東西的時候本來想用人腦將他們擺進(jìn)去，發(fā)現(xiàn)太！麻！煩！可能這就是計算機(jī)存在的意義吧！

引入：

不知道大家有沒有在前面學(xué)習(xí)遞推的時候?qū)W過馬攔過河卒的問題沒看過的可以點這，這個問題和那個問題都是一個棋類的問題，他們也有相同之處，都是需要用一個數(shù)組來表示這個地方有沒有被占領(lǐng)，象棋的那個題是馬占領(lǐng)的地方需要標(biāo)記，而這個題是皇后占領(lǐng)的每一行每一列每一個對角線都需要標(biāo)記。所以我們可以采用一些個數(shù)組來表示這個地方被皇后占領(lǐng)了。當(dāng)然這個題還用到了一個重要的算法就是遞歸算法和回溯的思想。

解決思路：

1.首先定義三個數(shù)組分別表示列被占領(lǐng)，左對角線被占領(lǐng)，和右對角線被占領(lǐng)。因為我們一行一行的放進(jìn)去所以不用考慮行的問題。????

2.利用遞歸算法在沒有被占領(lǐng)的地方一行一行的放入我們的皇后。????

3.利用遞歸和回溯算法一行一行的放入皇后。????

理論存在，實踐開始！

難點1：如何表示對角線被占領(lǐng)？

用數(shù)組來表示列被占領(lǐng)很簡單，只要讓皇后所在的那一列的數(shù)組的值都等于0，就可以解決這個問題，但如何用數(shù)組來表達(dá)對角線呢？？你知道吧！你數(shù)一數(shù)，這一共有多少個對角線？一共有15條對角線，所以我們可以定義兩個數(shù)組d1和d2來用來表示兩個方向的對角線。如果被占領(lǐng)就是0沒有被占領(lǐng)就是1

定義代碼如下：

int d1[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};//定義上對角線
int d2[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} ;//定義下對角線

如何在擺放的時候來確定哪一行哪一列呢？這樣定義十五行太好定義了但是想要表示就難了，我們來研究一下這個東西。看下圖，如這個第五列第三行的這個女皇，這個皇后占領(lǐng)了這兩個對角線，?如何來表示上對角線（皇后????的左上和右下從右上腳開始1、2、3、4、5...）？d1[n-col+7]=0;（col為女皇所在的列）也就是讓行減去列再加上7就是表示的上對角線的個數(shù)。

有小朋友要問了：你咋知道的？？？給你看一個上對角線的圖??！

用行-列得到的圖是這樣的（我的那個棋盤沒有第零行，大家可以看成有第零行的和列的，這個圖太難改了你懂我的意思吧）：

?而把這個數(shù)加7也就是行-列+7，是這樣的：

?這樣我們不就可以用行標(biāo)和列標(biāo)來表示他所在的上對角線了嘛，神器吧?。?/p>

希望各位xdm都把這個背過說實話我要是自己推我也推不出來這個玩意??！

下對角線：用行加列就會神奇的發(fā)現(xiàn)變成了下面這個樣子：

好了xdm現(xiàn)在讓我們大聲背三遍：

上對角線：行-列+7?。⌒?列+7??！行-列+7！！

下對角線：行+列?。⌒?列??！行+列！！

好了記住了吧?。。〔灰浟?！像對待女朋友的生日一樣對待這幾個字！??！

這樣我們就可以用：d1[n-col+7]，d2[n+col]來讀取皇后的對角線的占領(lǐng)情況了！

這個難點解決了，我們來進(jìn)入下一個難點遞歸。

難點2：如何用遞歸的方法來放皇后？

1.皇后的放置問題：place[8]={0};來表示皇后的位置的話，用table[8][8]={0};來表示一個8*8的大棋盤用一個for循環(huán)來訪問棋盤的每一行，如果這個位置可以放（那幾個約束條件都是1沒有被占領(lǐng)的話）我們就可以讓這一行的皇后的位置棋盤上放上皇后即place[n]=col;，表示皇后在此列????（一會打印的時候可以用的到）然后讓皇后的列和那兩個對角線為0，表示占領(lǐng)!?flag[col]=0;?d1[n-col+7]=0;d2[n+col]=0;

2.皇后的遞歸調(diào)用問題：

我們想要一行一行的擺放皇后，然后一列一列的嘗試對不對

用col來表示列的話，用一個循環(huán)：?? ?for (col=0;col<8;col++)來訪問每一列！

放置皇后用數(shù)組place[n]=col;（n表示行）來表示這個列，我皇后????占了！??！

flag[col]=0;? d1[n-col+7]=0;d2[n+col]=0;//將該皇后所在的行、列、對角線設(shè)置為被占領(lǐng)

這樣我們皇后在一行的放置問題解決了！，那么如何訪問每一行呢？

這時候我們就需要用到神奇的遞歸神器！

如果queen(n+1);發(fā)現(xiàn)，老資????沒座位了！他就會對queen(n);說：“姐姐，姐姐你能不能去下一個座位讓妹妹我坐下呀”如果queen(n)；發(fā)現(xiàn)她如果向下面去她也沒座位了她會向queen(n-1)說：....直到這8個皇后全坐下了，他們不吵架了，我們才能把這個棋盤輸出出來?。。?/p>

這不就是老和尚給小和尚講故事的遞歸嘛，而這個故事的大結(jié)局是皇后全都坐下！

我們?nèi)绻@個行數(shù)小于七行（初始行為0你要是初始行為一可以加一）我們就可以繼續(xù)向下擺放，對不對，就繼續(xù)使用遞歸，來擺這個棋盤的下一行。

if(n<7)?? ?{queen(n+1);}//當(dāng)行數(shù)小于7時；遞歸調(diào)用下一行。

如果我們的皇后把這次棋盤的擺好了我們就可以把這個棋盤輸出出來了！

else{print();}（這個函數(shù)我們下面講）//調(diào)用輸出函數(shù)，

請大家看代碼：

int queen(int n )//定義遞歸回溯函數(shù)
{
	int col;
	for (col=0;col<8;col++)
	{
		if (flag[col]&&d1[n-col+7]&&d2[n+col])//判斷皇后是否沖突
		{
			place[n]=col;//放置皇后
			flag[col]=0;
			d1[n-col+7]=0;
            d2[n+col]=0;//將該皇后所在的行、列、對角線設(shè)置為被占領(lǐng)
			if(n<7)	{queen(n+1);}//當(dāng)行數(shù)小于7時；遞歸調(diào)用下一行
		else{print();}//調(diào)用輸出函數(shù)
			flag[col]=1;//回溯
			d1[n-col+7]=1;
			d2[n+col]=1;
		}
	}
	return count;
}

輸出了一個棋盤還不夠，我們要輸出所有的棋盤，怎么辦呢？？這時候我們就要請我們的回溯算法登場了！?

難點3：如何實現(xiàn)回溯？

因為我們用的是遞歸算法如果這一行輸出不了我們就把責(zé)任退回給上一行，直到我們找到了一個棋盤上面正好能夠放著這八個皇后的時候我們就把他打印出來了。邏輯是不是這樣的

那么如果我們在循環(huán)的最后加上flag[col]=1;?d1[n-col+7]=1;?d2[n+col]=1;是不是就是把這個占領(lǐng)的皇后踢出去了，然后再把這個皇后放在下一列來看看后面的那些皇后能不能成功擺放？

什么時候會觸發(fā)這個回溯算法呢？？

答案是：當(dāng)上面的遞歸算法全執(zhí)行完了一次，并且輸出了一個棋盤后，我們就可以讓她執(zhí)行第二次了！！

我們來繼續(xù)講一個故事：最后那個????在自己家里呆夠了，老娘不想呆了，她又和樓上說，我要去下一個地方玩玩，你們看看怎么給我協(xié)調(diào)一下，原來我的位置就空出來了。樓上想；你去下面我去哪??！于是他只好和樓上說，樓下和他說過的話。

這就是flag[col]=1;?d1[n-col+7]=1;?d2[n+col]=1;老娘不想待了，全給我搬家！

運行完這個以后呢，for循環(huán)中的col就進(jìn)入下一列了，他這樣一進(jìn)不要緊，又觸發(fā)了遞歸算法，一層一層的倒換，來滿足需求。

當(dāng)這個皇后全嘗試了一遍其他能嘗試的地方，就安穩(wěn)了。

這樣講應(yīng)該能講明白為什么使用這個回溯算法，以及回溯算法為什么在if里面了吧如果不在if里面，這個回溯算法就沒有意義了。

            flag[col]=1;//回溯
			d1[n-col+7]=1;
			d2[n+col]=1;

難點4：如何實現(xiàn)皇后位置的輸出？

這個時候我們可以直接用一個輸出函數(shù)來輸出

這部分簡單直接上代碼：

void print()//定義輸出函數(shù)
{
	int i,j;
    count++;//每調(diào)用一次輸出函數(shù)number自加一次，記錄擺放方法個數(shù)
	printf("No.%2d\n",count);
	int table[8][8]={0};//設(shè)置一個8*8的棋盤
	for (i=0;i<8;i++)
	{
		table[i][place[i]]=1;//將每一行皇后所在位置賦值為1
	}
	for (i=0;i<8;i++)
	{
		for (j=0;j<8;j++)
		{
	printf("%d|",table[i][j]);
		}printf("\n");
	}
}

這樣我們就能輸出這些傲嬌的皇后們了！！

全部代碼如下：

#include<stdio.h>
int place[8]={0};//皇后位置
int flag[8]={1,1,1,1,1,1,1,1};//定義列
int d1[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};//定義上對角線（共有15個對角線,
//因此定義一個長度為15的數(shù)組，初值為1代表該對角線沒有被皇后占領(lǐng)，
//若被皇后占領(lǐng)則賦值為0
int d2[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} ;//定義下對角線
int count=0;//記錄輸出次數(shù)
void print()//定義輸出函數(shù)
{
	int i,j;
    count++;//每調(diào)用一次輸出函數(shù)number自加一次，記錄擺放方法個數(shù)
	printf("No.%2d\n",count);
	int table[8][8]={0};//設(shè)置一個8*8的棋盤
	for (i=0;i<8;i++)
	{
		table[i][place[i]]=1;//將每一行皇后所在位置賦值為1
	}
	for (i=0;i<8;i++)
	{
		for (j=0;j<8;j++)
		{
	printf("%d|",table[i][j]);
		}printf("\n");
	}
}
int queen(int n)//定義遞歸回溯函數(shù)
{
	int col;
	for (col=0;col<8;col++)
	{
		if (flag[col]&&d1[n-col+7]&&d2[n+col])//判斷皇后是否沖突
		{
			place[n]=col;//放置皇后
			flag[col]=0;
			d1[n-col+7]=0;
            d2[n+col]=0;//將該皇后所在的行、列、對角線設(shè)置為被占領(lǐng)
			if(n<7)	{queen(n+1);}//當(dāng)行數(shù)小于7時；遞歸調(diào)用下一行
            else{print();}//調(diào)用輸出函數(shù)
            flag[col]=1;//回溯
			d1[n-col+7]=1;
			d2[n+col]=1;
		}
	}
	return count;
}
int main()
{
count=queen(0);//從第0行開始擺放皇后
printf("共有%d種方法",count);//輸出擺放皇后的方法個數(shù)
	return 0;}

運行結(jié)果部分如下：

可以看到一共有92種方法。

總結(jié)：?

遞歸問題就是推責(zé)任問題，下邊不行就推給上邊，上邊不行，就推給上上邊。

而回溯就像一個追求完美主義的人，我這邊成了，我還要試試另一種解法行不行，等我把所有的結(jié)果都試出來就完美了！

我們?nèi)四?，既不能追求完美，也不能推卸?zé)任，只有做好自己。

大家仔細(xì)的把這個八皇后算法搞懂，就會發(fā)現(xiàn)原來遞歸和回溯這么簡單，不要得過且過?。?/strong>