n 皇后问题

问题分析

• 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
• xi 表示皇后i 放在棋盘的第i 行的第xi 列
  – 不能在同一行
  – 不能在同一列 xi 互不相同
  – 不能在同一斜线
  – 斜率为1 和值相等
  – 斜率为-1 差值相等
  – 若两个点 (i, j) (k, l), 则有
  – i – j = k – l => i – k = j – l
  – i + j = k + l => i – k = l -j
  – 即 |i – k| = |j – l| 成立即可Java 源代码/*
  * 若尘
  */
  package nqueen;

  /**
  * n 皇后问题
  * @author ruochen
  * @version 1.0
  */
  public class NQueen {

  /** 皇后个数 */
  static int n;
  /** 当前解 */
  static int[] x;
  /** 当钱已找到的可行方案数 */
  static long sum;

  public static void main(String[] args) {
  nQueen(5);
  System.out.println(“可行方案个数为： ” + sum);
  }

  /**
  * 初始化及返回可行解个数
  * @return 可行解个数
  */
  public static long nQueen(int nn) {
  n = nn;
  sum = 0;
  x = new int[n + 1];
  for (int i = 0; i <= n; i++) {
  // 初始化
  x[i] = 0;
  }
  backTrack(1);
  return sum;
  }

  /**
  * 可行性约束
  * @param k
  * @return 是否可行
  */
  public static boolean place(int k) {

  for (int j = 1; j < k; j++) {
  // 对应公式 |i – k| = |j – l| && 列号不能相同
  if ((Math.abs(k – j) == Math.abs(x[j] – x[k])) || x[j] == x[k]) return false;
  }
  return true;
  }

  /**
  * 回溯搜索
  * @param i
  */
  public static void backTrack(int t) {
  if (t > n) {
  // 已经找到一种可行解
  long temp = sum + 1;
  System.out.print(“第” + temp + “种可行解为： “);
  for (int k = 1; k <= n; k++) {
  System.out.print(x[k] + ” “);
  }
  System.out.println();
  sum++;
  } else {
  for (int i = 1; i <= n; i++) {
  x[t] = i;
  if (place(t)) backTrack(t + 1);
  }
  }
  }
  }第1种可行解为： 1 3 5 2 4
  第2种可行解为： 1 4 2 5 3
  第3种可行解为： 2 4 1 3 5
  第4种可行解为： 2 5 3 1 4
  第5种可行解为： 3 1 4 2 5
  第6种可行解为： 3 5 2 4 1
  第7种可行解为： 4 1 3 5 2
  第8种可行解为： 4 2 5 3 1
  第9种可行解为： 5 2 4 1 3
  第10种可行解为： 5 3 1 4 2
  可行方案个数为： 10