算法问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？

public class Queue8 {
	
   //定义最大8个皇后
    private int max = 8;
	
   /*用一维数组存放皇后摆放的位置, 
  *因为我们采用回溯法每一行都会去遍历，
  *以我们定义一维数组只存列即可
	 */
    private int arr [] = new int [max];
	
 	//记录找到8皇后位置的总次数
    int count = 0 ;
	
	//main函数实例化，调用输出
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check( 0 );
        System.out.println(queue8.count);
    }
	
  //打印8皇后摆放完成后的位置
    public void print(){
        for ( int i=0 ; i<max ; i++ ){
            System.out.print( arr[i] + " " );
        }
        System.out.println(  );
    }
	
	//回溯算法 ， n是第几个皇后， 也是第几行
    public void check( int n ){
      
      	//如果当前摆放的皇后超过了8个，递归结束
        if( n == 8 ){
            //打印摆放路径
            print();
          	//正确次数+1
            count ++ ;
            return;
        }
      	//遍历n 行的 所有列， 找到可以放皇后的位置
        for ( int i=0 ; i< max ; i++  ){
          //每次循环都将皇后的列放入对应的数组
            arr[n] = i;
          //判断当前皇后的位置，是否可以摆放
            if( juged( n )){
              	//找下一个皇后位置
                check( n+1 );
            }
        }
    }

    /**
     * 冲突判断
     * @param n
     * @return
     */
    private boolean juged( int n ){
      	//对之前摆放的皇后进行冲突检查
        for ( int i=0 ; i< n ; i ++  ){
           //判断是否在同列上    || 判断是否在同一斜线上
            if( arr[i]  == arr[n]  || (Math.abs( n - i ) == Math.abs(arr[n] - arr[i]))){
                return false;
            }
        }
        return true;
    }
}

运行结果

...省略91种

7 3 0 2 5 1 6 4

92

结论

通过我们的算法对8皇后问题的摆放次数进行计算，一共为92次，体会到了算法的魅力了，再一个没有计算机的年代，是很难算出有多少中摆法的