#include "stdafx.h"
/*
算法系列---回溯算法
引言
尋找問題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個，在檢查完所有或部分候選解后，即可找到所需要的解。理論上，當候選解數量有限并且通過檢查所有或部分候選解能夠得到所需解時，上述方法是可行的。不過，在實際應用中，很少使用這種方法，因為候選解的數量通常都非常大(比如指數級，甚至是大數階乘），即便采用最快的計算機也只能解決規模很小的問題。對候選解進行系統檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方法。按照這兩種方法對候選解進行系統檢查通常會使問題的求解時間大大減少(無論對于最壞情形還是對于一般情形）。事實上，這些方法可以使我們避免對很大的候選解集合進行檢查，同時能夠保證算法運行結束時可以找到所需要的解。因此，這些方法通常能夠用來求解規模很大的問題。
算法思想
回溯(backtracking）是一種系統地搜索問題解答的方法。為了實現回溯，首先需要為問題定義一個解空間(solution space），這個空間必須至少包含問題的一個解(可能是最優的）。
下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖(迷宮問題)或樹(N皇后問題)。
一旦定義了解空間的組織方法，這個空間即可按深度優先的方法從開始節點進行搜索。
回溯方法的步驟如下：
1) 定義一個解空間，它包含問題的解。
2) 用適于搜索的方式組織該空間。
3) 用深度優先法搜索該空間，利用限界函數避免移動到不可能產生解的子空間。
回溯算法的一個有趣的特性是在搜索執行的同時產生解空間。在搜索期間的任何時刻，僅保留從開始節點到當前節點的路徑。因此，回溯算法的空間需求為O(從開始節點起最長路徑的長度）。這個特性非常重要，因為解空間的大小通常是最長路徑長度的指數或階乘。所以如果要存儲全部解空間的話，再多的空間也不夠用。
算法應用
回溯算法的求解過程實質上是一個先序遍歷一棵"狀態樹"的過程,只是這棵樹不是遍歷前預先建立的,而是隱含在遍歷過程中<<數據結構>>(嚴蔚敏).
回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
回溯法是一個既帶有系統性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解的空間樹。算法搜索至解的空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它適用于解一些組合數較大的問題。
算法框架：
1、問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應至少包含一個(最優）解。
2、回溯法的基本思想：確定了解空間的組織結構后，回溯法就從開始結點(根結點）出發，以深度優先的方式搜索整個解空間，這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點，這個新結點就成為一個新的活結點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動(回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
運用回溯法解題通常包含以下三個步驟：
(1）針對所給問題，定義問題的解空間；
(2）確定易于搜索的解空間結構；
(3）以深度優先的方式搜索解空間，并且在搜索過程中用剪枝函數避免無效搜索。
3、遞歸回溯：由于回溯法是對解的空間的深度優先搜索，因此在一般情況下可用遞歸函數來實現回溯法如下：
void backtrace(int i)
{
for (int j=下界;j<上界;j++)
{
matrix[i] = j;
//可行{滿足限界函數和約束條件}
if ( 可行())
{
//置值
if (i>n)
{
//中止搜索并輸出結果;
}
backtrace(i+1);
}
}
}
說明：
i是遞歸深度；
n是深度控制，即解空間樹的高度；
可行性判斷有兩方面的內容：
①不滿約束條件則剪去相應子樹；
②若限界函數越界，也剪去相應子樹；
③兩者均滿足則進入下一層；
搜索：全面訪問所有可能的情況，分為兩種：不考慮給定問題的特有性質，按事先設好的順序，依次運用規則，即盲目搜索的方法；另一種則考慮問題給定的特有性質，選用合適的規則，提高搜索的效率，即啟發式的搜索。
*/
//八皇后問題
//解空間
static int matirx[8] = {0};
static int count = 0;
void display()
{
int row;
int col;
printf("\r\n======%02d=======\n",count);
for(row = 0; row <8; row ++)
{
for(col = 0; col < matirx[row]; col ++)
printf("* ");
printf("# ");
for(col = matirx[row] + 1; col < 8; col ++)
printf("* ");
printf("\n");
}
}
bool place(int row, int col)
{
int prev;
int data;
for(prev = 0; prev < row; prev ++){
data = matirx[prev];
//同一列
if(col == data)
return false;
//左斜線
if ((prev-row) == (col - data) )
return false;
//右斜線
if((row - prev) == (col - data))
return false;
}
return true;
}
void queen(int row)
{
int col;
for(col=0;col<8;col++)
{
if(place(row,col))
{
matirx[row]=col;
if(row>=7)
{
count++,display();
//matirx[row]=0;
return;
}
queen(row+1);
//matirx[row]=0;
}
}
}
int main(void)
{
queen(0);
system("pause");
return 0;
}