回溯法求N皇后问题
?回溯法：是一种选优搜索法， 回溯法从开始节点（根节点）出发，以深度优先方式搜索整个解空间。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
N皇后问题描述：在n乘n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之在同行或同列或同一斜线上的棋子。n后问题等价于在n?乘 n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
求解思路：有序地从第 1 行的第 1 列开始，尝试放上一个皇后，然后再尝试第 2 行的第几列能够放上一个皇后，如果第 2 行也放置成功，那么就继续放置第 3 行，如果此时第?3 行没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 步），将上一步（第 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯，最后得到和规则的解。
package 算法实验;/** * n皇后类 * 回溯法求n皇后 * */public class NQueens {private static int queensNum ;//皇后的个数//定义一个数组，x[k]表示第k行的列数，x[k]=j表示第k行的第j位置放一位皇后private static int []x;/** * 产生n位皇后的方法 */public void produceNQueens(){x[1]=0;//每一行从0开始int k=1;//从第1行开始while(k>0){x[k]=x[k]+1;while((x[k]<=queensNum)&&!(place(k)))//判断约束条件x[k]=x[k]+1;if(x[k]<=queensNum)if(k==queensNum){//输出各行皇后的位置for(int i=1;i<=queensNum;i++)System.out.print("("+i+","+x[i]+") ");System.out.println();}else {k++;x[k]=0;}else k--;//回溯}}/** * 判断放置皇后的约束条件的方法 * @param k * @return */public boolean place(int k){for(int j=1;j<k;j++)//任何2个皇后不能放在同一行或同一列或同一斜线上。if((Math.abs(j-k))==(Math.abs(x[j]-x[k]))||(x[j]==x[k]))return false;return true;}/** * 程序入口：主函数 * @param args */public static void main(String[] args){ queensNum=4;//给皇后个数初始值x = new int[queensNum+1];//给数组x赋长度//实例化对象NQueens nq = new NQueens();System.out.println(+queensNum+"位皇后的位置是：");//调用产生n位皇后的方法nq.produceNQueens();}}?
当N=4时，运行结果是：
?4位皇后的位置是：
(1,2) (2,4) (3,1) (4,3)
(1,3) (2,1) (3,4) (4,2)
?
?当N=6时，运行结果是：
?6位皇后的位置是：
(1,2) (2,4) (3,6) (4,1) (5,3) (6,5)
(1,3) (2,6) (3,2) (4,5) (5,1) (6,4)
(1,4) (2,1) (3,5) (4,2) (5,6) (6,3)
(1,5) (2,3) (3,1) (4,6) (5,4) (6,2)
?
?
?