经典算法问题之八皇后
???????????用回溯法解决该问题： G++：
??????????刚开始看到这个问题，会想到遍历，但是仔细想想会发现太复杂了，其实一个个皇后排的话，你会
发现前几列不能满足了，后面的就都不行了，所以我们要用回溯法倒回去，解决这种问题最好是用递归，
简洁，明了。
???????????变量的定义：
???????????
#include<iostream>using namespace std ;#define NUM 9static int a[NUM] ;//创建数组int count=0 ;//计数
??????????
????????? 判断本列的这个皇后能否满足情况：
???
bool judgeQueen(int index,int value){ int i,j,data; for(i=1;i<index;i++) { data = a[i] ; if(data == value) return 0 ; //列相等 if((data-i)==(value-index)) return 0 ;//负斜一条线 if((data+i)==(value+index)) return 0 ;//正邪一条线 } return true ;}?
?????????? 递归算法实现：
??????
void InitQueen(int index){ int i,j ; for(i=1;i<9;i++){ if(judgeQueen(index,i))//这列能放下皇后 { a[index] = i ; if(index == 8) //这种摆法能成功 { count++ ; a[index] = 1 ; continue ; } InitQueen(index + 1) ;//继续递归 a[index] = 1 ; } }}???? 解决方法二： Java
???? 声明变量：
????
// 同栏是否有皇后，1表示有 private int[] column; // 右上至左下是否有皇后 private int[] rup; // 左上至右下是否有皇后 private int[] lup; // 解答 private int[] queen; // 解答编号 private int num;
???
??? 构造方法初始化：
????
public Queen() { column = new int[8+1]; rup = new int[2*8+1]; lup = new int[2*8+1]; for(int i = 1; i <= 8; i++) column[i] = 1; for(int i = 1; i <= 8; i++) rup[i] = lup[i] = 1; queen = new int[8+1]; } ??
?? 回溯方法：
???
public void backtrack(int i) { if(i > 8) { showAnswer(); } else { for(int j = 1; j <= 8; j++) { if(column[j] == 1 && rup[i+j] == 1 && lup[i-j+8] == 1) { queen[i] = j; // 设定为占用 column[j] = rup[i+j] = lup[i-j+8] = 0; backtrack(i+1); column[j] = rup[i+j] = lup[i-j+8] = 1; } } } } ?