八皇后问题算法实现

还是闲来无事，做个八皇后问题，复习下回溯

 

八皇后问题是个相当经典的回溯问题：在一个8*8大小的棋盘上，在每排放一个皇后，要求改皇后的横竖斜排上没有其他的皇后，找出所有的可能性。

 

其实主要问题就是在一排上找个位置，找前先判断该位置是否可以放置皇后。即可进行递归求解。

 

由于是找所有的可能性，所以找完一个方案或某一方案进行不下去，必须进行回溯。

问题的简化版，4皇后，看第四行，发现没有符合条件的位置，去掉第三行第二列的皇后，进行下一个位置的判断，即回溯。

 

主要就是用递归和回溯进行求解，代码如下：

public class Queen8 {

    public static void main(String[] args) {
  int[][] queen = new int[8][8];
  deal(queen, 0, 0);
  System.out.println("totle numbers: " + num);
    }

    public static void deal(int[][] queen, int i, int j) {
  if (i == 8) {
      print(queen);
      return;
  }
  for (int k = 0; k < 8; k++) {
      if (queen[i][k] == 0) {
    judge2(queen, i, k, 1);
    deal(queen, i + 1, 0);
    judge2(queen, i, k, -1);
      }
  }
    }

    public static void judge2(int[][] queen, int i, int j, int n) {
  // vertical
  for (int k = 0; k < 8; k++)
      queen[k][j] += n;
  // horizon
  for (int k = 0; k < 8; k++)
      queen[i][k] += n;
  queen[i][j] -= n;
  // left slope
  for (int ki = i - 1, kj = j - 1; ki >= 0 && kj >= 0; ki--, kj--)
      queen[ki][kj] += n;

  for (int ki = i + 1, kj = j + 1; ki < 8 && kj < 8; ki++, kj++)
      queen[ki][kj] += n;

  // right slope
  for (int ki = i - 1, kj = j + 1; ki >= 0 && kj < 8; ki--, kj++)
      queen[ki][kj] += n;

  for (int ki = i + 1, kj = j - 1; ki < 8 && kj >= 0; ki++, kj--)
      queen[ki][kj] += n;

    }

    public static void print(int[][] queen) {
  for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 8; j++) {
    if (queen[i][j] > 1)
        System.out.print('*' + " ");
    else
        System.out.print('X' + " ");
      }
      System.out.println();
  }
  System.out.println();
  num++;
    }

    private static int num = 0;
}