数据结构--递归之八皇后问题

• 问题概述

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

public class EightQueen {
 private static int count=0;//记录第几种可能
 private static int N=8;
 public static void main(String[] args) {
  int[][] arr=new int[N][N];//默认元素为0，1当作皇后
  eightQueen(0,arr);
 }
 
 private static void eightQueen(int row, int[][] arr) {
  if(row==N){
   count++;
   System.out.println("第"+count+"种：");
   for(int i=0;i<arr.length;i++){
    for(int j=0;j<arr[i].length;j++){
     System.out.print(arr[i][j]+" ");
    }
    System.out.println();
   }
  }else{
   //做一个数组备份
   int[][] newArr=new int[N][N];
   for(int i=0;i<arr.length;i++){
    for(int j=0;j<arr[i].length;j++){
     newArr[i][j]=arr[i][j];
    }
   }
   for(int col=0;col<N;col++){
    if(noDangerous(row,col,newArr)){
     for(int c=0;c<N;c++){
      newArr[row][c]=0;
     }
     newArr[row][col]=1;
     eightQueen(row+1, newArr);
    }
   }
  }
 }
 private static boolean noDangerous(int row, int col, int[][] newArr) {
  //正上
  for(int r=row-1;r>=0;r--){
   if(newArr[r][col]==1){
    return false;
   }
  }
  //左上
  for(int r=row-1,c=col-1;r>=0&&c>=0;r--,c--){
   if(newArr[r][c]==1){
    return false;
   }
  }
  //右上
  for(int r=row-1,c=col+1;r>=0&&c<N;r--,c++){
   if(newArr[r][c]==1){
    return false;
   }
  }
  
  return true;
 } 
}