一 . 问题描述

          八皇后问题 （ 英文 ： Eight queens ），是由国际 西洋棋 棋手马克斯·贝瑟尔于1848年提出的问题，是 回溯算法 的典型案例。. 问题表述为：在8×8格的 国际象棋 上摆放8个 皇后 ，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。. 高斯 认为有76种方案。. 1854年在 柏林 的象棋杂志上不同的作者发表了40种不同的解，后来有人用 图论 的方法解出92种结果。. 如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。. 计算机 发明后，有多种计算机语言可以编程解决此问题。.

 

二 .  算法思路

          1. 第一个皇后先放在第一行第一列

          2.第二个皇后放在第二行 第一列  ，判断是否可以  如果不可以 继续放在第二列 ，第三列...

               依次把所有的列 放完 找到合适的

           3.继续放第三个皇后 ，按照2的方式 ，知道所有皇后放完 不冲突，找到一个正解；

            4.得到一个正解后，压的栈就会回退上一个栈 ，开始回溯  一直到回溯到第一个皇后在第                      一列的所有情况 ，

           5.然后继续把第一个皇后放到第二列 执行1 2 3 4 步骤 

注意 ：

           理论上创建二维数组 ，但是实际可以通过算法 用一维数组解决，

             数组下标表示第几个皇后   例如 arr[i]=val   val 表示第 i+1个皇后放在了 val+1 列

                 （数组下标是从0 开始的）

三 . 算法实现

         有具体的详细注释

package c05recursion;

import java.util.Date;

public class queen8 {

	
		//定义max 表示皇后的数量
		int max = 8;
		//定义一维数组  第一个表示在第一行 他的值表示在第几列
		int [] array = new int [max];
		static int total=0;
		//这些是全局变量 直接在下面共享值
		
		public static void main(String[] args) {
		
			//这里直接创建他的对象 因为这些方法都是在类里面的；
			long data1 =System.currentTimeMillis();
			queen8 queen = new queen8();
			queen.check(0);
			System.out.println(total);
			long data2 = System.currentTimeMillis();
			
			System.out.println((data2-data1)/600);
		
	}
		
		
	//判断放置第n个皇后  n 其实是数组的下标； 从0开始的
		private void check(int n) {
			if(n==max) {
				//表示皇后已经放置完了；
				print();
				return;
			}
			//依次放入皇后 并判断是否冲突  
			for(int i=0;i<max;i++) {
				//每次放这个皇后时都从第一个列开始判断
				array[n]=i;  //把第n 个皇后放的位置 从0 循环
				if(jadge(n)) {
					//此时的位置不冲突的话 放置下一个皇后
					check(n+1);
				}
				//这里如果冲突了  上面会循环列的位置  递归
			}
			
			
		}
		
		
	
	//这个方法判断摆放第n 个皇后是否冲突
		private boolean jadge(int n) {
			for(int i=0;i<n;i++) {
				if(array[n]==array[i]||Math.abs(n-i)==Math.abs(array[n]-array[i]))
					// 是否同列   行值差是否等于列值差（是否在对角线）
					//不可能在同一列
					return false;
			 }
			return true;
		}
		
		
		
	//这个方法打印皇后的位置
		private void print() {
			total++;
			for(int i=0;i<array.length;i++) {
				System.out.print(array[i]+" ");
			}
			//一次for循环打印一种情况；
			System.out.println();
		}
}