理論輔助：

回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的解的方法?；厮菟惴ǖ幕舅枷胧牵簭囊粭l路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。用回溯算法解決問題的一般步驟為：

1、定義一個(gè)解空間，它包含問題的解。

2、利用適于搜索的方法組織解空間。

3、利用深度優(yōu)先法搜索解空間。

4、利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。

問題的解空間通常是在搜索問題的解的過程中動(dòng)態(tài)產(chǎn)生的，這是回溯算法的一個(gè)重要特性。

還是那個(gè)基調(diào)，不喜歡純理論的東西，喜歡使用例子來講訴理論，在算法系列總結(jié)：動(dòng)態(tài)規(guī)劃(解公司外包成本問題） 的那一節(jié)里面 我們舉得是經(jīng)典的0-1背包問題，在回溯算法里面也有一些很經(jīng)典的問題，當(dāng)然，動(dòng)態(tài)規(guī)劃的0-1背包問題其實(shí)也可以使用回溯算法來解。在諸如此類似的求最優(yōu)解的問題中，大部分其實(shí)都可以用回溯法來解決，可以認(rèn)為回溯算法一個(gè)”通用解題法“，這是由他試探性的行為決定的，就好比求一個(gè)最優(yōu)解，我可能沒有很好的概念知道怎么做會(huì)更快的求出這個(gè)最優(yōu)解，但是我可以嘗試所有的方法，先試探性的嘗試每一個(gè)組合，看看到底通不通，如果不通，則折回去，由最近的一個(gè)節(jié)點(diǎn)繼續(xù)向前嘗試其他的組合，如此反復(fù)。這樣所有解都出來了，在做一下比較，能求不出最優(yōu)解嗎？

例子先行，現(xiàn)在我們來看看經(jīng)典的N后問題

問題描述：在n*n格的棋盤上放置彼此不受攻擊的n個(gè)皇后。按照國際象棋的規(guī)矩，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價(jià)于在n*n格的棋盤上方置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。我們需要求的是可放置的總數(shù)。
 

基本思路：   用n元組x[1；n]表示n后問題的解。其中，x[i]表示皇后i放置在棋盤的第i行的第x[i]列。由于不容許將2個(gè)皇后放在同一列上，所以解向量中的x[i]互不相同。2個(gè)皇后不能放在同一斜線上是問題的隱約束。對(duì)于一般的n后問題，這一隱約束條件可以化成顯約束的形式。如果將n*n 格的棋盤看做二維方陣，其行號(hào)從上到下，列號(hào)從左到右依次編號(hào)為1,2，...n。從棋盤左上角到右下角的主對(duì)角線及其平行線（即斜率為-1的各斜線）上，2個(gè)下標(biāo)值的差（行號(hào)-列號(hào)）值相等。同理，斜率為+1的每條斜線上，2個(gè)下標(biāo)值的和（行號(hào)+列號(hào)）值相等。因此，若2個(gè)皇后放置的位置分別是（i,j）和（k,l）,且 i-j = k -l 或 i+j = k+l，則說明這2個(gè)皇后處于同一斜線上。以上2個(gè)方程分別等價(jià)于i-k = j-l 和 i-k =l-j。由此可知，只要|i-k|=|l-j|成立，就表明2個(gè)皇后位于同一條斜線上。

1、從空棋盤起，逐行放置棋子。
2、每在一個(gè)布局中放下一個(gè)棋子，即推演到一個(gè)新的布局。
3、如果當(dāng)前行上沒有可合法放置棋子的位置，則回溯到上一行，重新布放上一行的棋子。
代碼：

復(fù)制代碼 代碼如下:
#include <stdio.h> 
#include <math.h> 
#include<stdlib.h> 
static int n,x[1000]; 
static    long sum; 
int Place(int k) 
{ 
for(int j=1;j <k; j++) 
    if((abs(k-j) == abs(x[j]-x[k]))||(x[j]==x[k])) return 0; 
     return 1; 
  }

void Backtrak(int t) 
{ 
   if(t>n) sum++; 
   else 
       for(int i=1; i <= n; i++) 
       { 
            x[t] =i;