八皇后問題是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上.
問題分析:
第一步 定義問題的解空間
這個(gè)問題解空間就是8個(gè)皇后在棋盤中的位置.
第二步 定義解空間的結(jié)構(gòu)
可以使用8*8的數(shù)組，但由于任意兩個(gè)皇后都不能在同行，我們可以用數(shù)組下標(biāo)表示
行，數(shù)組的值來表示皇后放的列，故可以簡(jiǎn)化為一個(gè)以維數(shù)組x[9]。
第三步 以深度優(yōu)先的方式搜索解空間，并在搜索過程使用剪枝函數(shù)來剪枝
根據(jù)條件:x[i] == x[k]判斷處于同一列
abs(k-i) == abs(x[k]-x[i]判斷是否處于同一斜線
我們很容易寫出剪枝函數(shù)：

      bool canPlace(int k){
	for(int i = 1; i < k; i++){
        //判斷處于同一列或同一斜線
	   if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i])) 		       return false;
	}
	return true;
}

    

然后我們按照回溯框架一，很容易寫出8皇后的回溯代碼：

      void queen(int i){
	if(i > 8){
		print();
		return;
	}
	for(int j = 1; j <= 8; j++){
	  x[i] = j;//記錄所放的列
	  if(canPlace(i)) queen(i+1);
	}
}

    

整個(gè)代碼：