这里回溯算法还要好好研究一下
试探一个位置是否有效，如果有效，试探下一个位置（DFS），如果无效则回退
1.定义一个解空间，存放一个解的空间
2.DFS(暂且认为是DFS)
这里N皇后用的是递归+回溯实现的
package com.gxf.backtracking; /**
* n皇后问题
* @author Administrator
*
*/
public class Queen {
int num_queen; //皇后个数
int solution[]; //solution[i] = k表示第i行皇后在第k列 ,solution为解空间
int sum = 0; public Queen(int num){
num_queen = num;
solution = new int[num_queen + 1];
} /**
* 第k个皇后的位置是否有效
* 第k个皇后的列保存在solution[k]中，与前面k-1个皇后比较
* @param k
* @return
*/
boolean isValid(int k){
for(int i = 1; i < k; i++){
if(solution[i] == solution[k] || Math.abs(k - i) == Math.abs(solution[k] - solution[i]))
return false;
}
return true;
} /**
* 开始放第n个皇后
* @param queen
*/
public void placeQueen(int n){
if(n > num_queen)
{
showSolution();
System.out.println();
sum++;
}
else
for(int i = 1; i <= num_queen; i++){
solution[n] = i; //n个皇后放到i列
if(isValid(n))
placeQueen(n + 1);
}
} /**
* 将结果打印出来
*/
public void showSolution(){
for(int i = 1; i <= num_queen; i++){
for(int j = 1; j <= num_queen; j++){
if(j == solution[i])
System.out.print('Q' + " ");
System.out.print(0 + " ");
}
System.out.println();
}
} public static void main(String[] args) {
Queen queen = new Queen(4); queen.placeQueen(1);
System.out.println("sum = " + queen.sum);
} }