八皇后问题JAVA版回溯法

public class EightQueens {
 
 public static void run(int row, int col,int n, int r[]){
  if(row == 0){
   for(int i = 0;i < n;i ++){
    r[row] = i;
    run(1, 0, n, r);
    r = formatArray(n);
   }
  }
  else{
   if(check(row, col, r)){
    r[row] = col;
    if(row < n - 1){//不是最后一行
     run(row + 1, 0, n, r);
     if(col < n - 1){//不是最后一列
      run(row, col + 1, n, r);
     }
    }
    else{//最后一行
     print(r);
     if(col < n - 1){//不是最后一列
      run(row, col + 1, n, r);
     }
    }
   }
   else{
    if(row < n - 1){//不是最后一行
     if(col < n - 1){//不是最后一列
      run(row, col + 1, n, r);
     }
    }
    else{//最后一行
     if(col < n - 1){//不是最后一列
      run(row, col + 1, n, r);
     }
     else{//最后一列
//      print(k);
     }
    }
   }
  }
 }
 
 private static boolean check(int row, int col, int r[]){
  for(int i = 0;i < row;i ++){
   if(col == r[i] + row - i || col == r[i] - (row - i) || col == r[i]){//不满足条件
    return false;
   }
  }
  return true;
 }
 
 private static int N = 0;
 
 private static void print(int k[]){
  String s = "";
  N ++;
  if(N > 9){
   System.out.println("=========解法" + N +"========");
  }
  else{
   System.out.println("=========解法0" + N +"========");
  }
  for(int a = 0;a < k.length;a ++){
   s = "";
   for(int i = 0;i < k.length;i ++){
    if(i != k[a]){
     s += "□";
    }
    else{
     s += "■";
    }
   }
   System.out.println(s);
  }
  System.out.println("=======================");
 }
 
 public static int[] formatArray(int n){
  int[] k = new int[n];
  for(int i = 0;i < n;i ++){
   k[i] = 0;
  }
  return k;
 }
 
 public static void main(String[] arg0){
  int n = 8;//改变这个值可以解决不同数量的皇后问题
  int[] r = new int[n];
  for(int i = 0;i < n;i ++){
   r[i] = 0;
  }
  System.out.println("BEGIN!");
  run(0, 0, n, r);
 }
}