八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。

本文用递归的方法来实现八皇后问题，并设置了期望的皇后数，可以设置不同的皇后期望值，来输出更多的其它组合。

JAVA程序代码：

/**
 * 八皇后问题
 * 八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。
 * 该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，
 * 使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 
 * 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，
 * 后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。
 * 
 * 本程序就是打印出皇后的各种解法。
 * 本文设置了EXPECT_QUEEN_NUMBER，这个用来控制期望的个皇后个数，默认是8个。
 * 
 * @author Eric
 *
 */
public class QueenProblem {

 private static final String SEPARATOR_BLANK = " ";

    /*
     * 期望的皇后数目，默认为8皇后
     * 如果想找9皇后的矩阵，那么只要EXPECT_QUEEN_NUMBER=9 即可。
     */
 private static final int EXPECT_QUEEN_NUMBER = 9;

 private int count = 0;// 统计8皇后解的个数

 private void processQueenProblem(int currentQueenCount, int[][] currentMatrix) {
  int[][] tempMatrix = copyArray(currentMatrix);//复制矩阵，将作为递归的输入
  /*
   * 当8 * 8的矩阵中有8个皇后，就输出矩阵的排列
   */
  if (currentQueenCount == EXPECT_QUEEN_NUMBER) {
   print(++count, tempMatrix);/*输出当前符合8皇后的矩阵*/
  } else {
   /*
    * 如果还没有达到8个，就在currentMatrix[currentQueenCount][]中寻找符合条件的Queen
    * 递归调用
    */
   for (int col = 0; col < EXPECT_QUEEN_NUMBER; col++) {
    //在当前行中，从左到右寻找符合八皇后条件的位置
    if (isQueenAvailable(currentQueenCount, col, tempMatrix)) {
     processQueenProblem(currentQueenCount + 1, selectOneQueen(currentQueenCount,col,tempMatrix));
    }
   }
  }
 }
 
 /**
  * 设置该位置为皇后。
  * 
  * 将当前行所有的元素先设置为0，然后将当前行，列的元素设置成1.
  * 
  * @param currentRow
  * @param currentCol
  * @param queenMatrix
  * @return
  */
 private int[][] selectOneQueen(int currentRow,int currentCol ,int[][] queenMatrix){
  for (int col = 0; col < EXPECT_QUEEN_NUMBER; col++) {
   queenMatrix[currentRow][col] = 0;
  }
  queenMatrix[currentRow][currentCol] = 1;
  return queenMatrix;
 }
 
 /**
  * 用于复制数组的元素
  * @param sourceData
  * @return
  */
 private int[][] copyArray(int[][] sourceData) {
  int[][] copyData = new int[EXPECT_QUEEN_NUMBER][EXPECT_QUEEN_NUMBER];
  for (int i = 0; i < EXPECT_QUEEN_NUMBER; i++) {
   for (int j = 0; j < EXPECT_QUEEN_NUMBER; j++) {
    copyData[i][j] = sourceData[i][j]; 
   }
  }
  return copyData;
 }

 /**
  * 符合8皇后的矩阵的输出
  * @param count
  * @param result
  */
 private void print(int count, int[][] result) {
  System.out.println("第" + count + "种解法");
  for (int i = 0; i < EXPECT_QUEEN_NUMBER; i++) {
   for (int j = 0; j < EXPECT_QUEEN_NUMBER; j++) {
    System.out.print(result[i][j]+SEPARATOR_BLANK);
   }
   System.out.println();
  }
 }


 /**
  * isQueenAvailable方法用来判断当前位置能否摆放皇后。
  * 
  * 因为递归调用中是根据row的增长而实现的，
  * 那么在当前的皇后矩阵中，当前行以后的元素暂时还不需要考虑，此时它们的值还都是默认值0。
  * 所以当前行，列是否符合皇后的位置，它需要与当前行之前的元素进行比较。
  * 因此，判断第row行第col列能不能摆皇后，只需要判断正上方，左上方和右上方三个方向即可。
  * 只要有一个方向不符合要求，就表明当前这个位置不能摆放皇后。
  * 
  * @param currentRow
  * @param currentCol
  * @param queenMatrix
  * @return
  */
 private boolean isQueenAvailable(int currentRow, int currentCol, int[][] queenMatrix) {
  //判断正上方（列方向）
  for (int row = 0; row < currentRow; row++)
   if (queenMatrix[row][currentCol] == 1) {
    return false;
   } 
  //判断左上方
  for (int row = currentRow, col = currentCol; row >= 0 && col >= 0; row--, col--)
   if (queenMatrix[row][col] == 1) {
    return false;
   }
  //判断右上方
  for (int row =currentRow, col = currentCol; row >= 0 && col < EXPECT_QUEEN_NUMBER; row--, col++)
   if (queenMatrix[row][col] == 1) {
    return false;
   }
  //return true 表明该位置可以摆放皇后。
  return true; 
 }
 
 public static void main(String[] args) {
  QueenProblem queen = new QueenProblem();
  queen.processQueenProblem(0, new int[EXPECT_QUEEN_NUMBER][EXPECT_QUEEN_NUMBER]);
  System.out.println("一共有" + queen.getCount() + "种解法");
 }

 public int getCount() {
  return count;
 }

 public void setCount(int count) {
  this.count = count;
 }
}