java实现算法-n皇后

什么是n皇后

n皇后是一个经典的算法问题, 即一个 n × n的棋盘上, 每一行放置一个皇后棋子. 这个棋子的竖行, 横行, 斜行都没有其他的皇后冲突

如图

思路

先说思路, 这里采用的是回溯法, 即先采用一种可能性, 然后将这个可能性进行判断是否可行, 可行的话继续采用下一种可能性, 串起来就是一个正确的解.

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 ---- 来自百度百科

我们弄一个数组arr, 大小是n, 表示每行中, 皇后的列数
预计是要写一个迭代, 每个迭代只计算一行的逻辑. 那么迭代方法一开始要写跳出的逻辑, 这里应该就是当循环次数达到n. 或者说行数到了最后一行.
跳出方法写完后, 写主要的逻辑, 那么这里就遍历每一列, 然后试着把皇后放在这列, 也就是放到数组arr中, 再去判断合不合规,合规就递归判断下一行, 不合规就判断下一列
判断合规的方法, 就是将上面那个数组arr已经确定的皇后和现在这个皇后进行比对

代码

顺便说下, n皇后回溯法的话, 相当是一个n叉树, 每个节点有n列, 每列下面是下一行的n列的孩子节点.
如果暴力遍历n×n的话, 时间复杂度是O(n的n次方), 下面的方法, 每次遍历不是n*n…, 第二行满足条件的肯定比第一行少, 如果n=4, 则第二行只能有1-2列满足, n=5则只有2-3列满足, 应该近似于阶乘, 即 O(n!)

package com.zgd.demo.suanfa.exam;


public class NQueen {


  public static void main(String[] args) {
    int n = 16;
    int nqueen = nqueen(n, 0, new int[n], 0);
    System.out.println("nqueen = " + nqueen);
  }


  
  public static int nqueen(int n,int row,int[] res,int count){
    if (row == n){
      //打印
      print(n, res);
      count++;
      System.out.println("-----------");
      return count;
    }
    for (int col = 0; col < n; col++) {
      //先尝试着把皇后放在这一列
      res[row] = col;
      //判断和上面行的皇后是否冲突
      if (isOk(row,col,res)){
        //迭代,下一行
        count = nqueen(n,row+1,res,count);
      }
    }
    return count;
  }

  private static boolean isOk(int row, int col, int[] res) {
    for (int i = 0; i < row; i++) {
      //判断上面每行皇后所在列, 如果和当前列相同则为false
      if (res[i] == col){
        return false;
      }
      //判断撇和捺方向, 是两个斜率为1和-1的直线, 则他们两个坐标 |y2 - y1| == |x2 - x1|
      if (row - i == col - res[i] || row - i == res[i] - col ){
        return false;
      }
    }
    return true;
  }

  private static void print(int n, int[] res) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (res[i] == j){
          System.out.print("Q");
        }else{
          System.out.print("*");
        }
        System.out.print(" ");
      }
      System.out.println();
    }
  }

}

试下, n=4

* Q * * 
* * * Q 
Q * * * 
* * Q * 
-----------
* * Q * 
Q * * * 
* * * Q 
* Q * * 
-----------
nqueen = 2

试下n=5

Q * * * * 
* * Q * * 
* * * * Q 
* Q * * * 
* * * Q * 
-----------
Q * * * * 
* * * Q * 
* Q * * * 
* * * * Q 
* * Q * * 
-----------
* Q * * * 
* * * Q * 
Q * * * * 
* * Q * * 
* * * * Q 
-----------
* Q * * * 
* * * * Q 
* * Q * * 
Q * * * * 
* * * Q * 
-----------
* * Q * * 
Q * * * * 
* * * Q * 
* Q * * * 
* * * * Q 
-----------
* * Q * * 
* * * * Q 
* Q * * * 
* * * Q * 
Q * * * * 
-----------
* * * Q * 
Q * * * * 
* * Q * * 
* * * * Q 
* Q * * * 
-----------
* * * Q * 
* Q * * * 
* * * * Q 
* * Q * * 
Q * * * * 
-----------
* * * * Q 
* Q * * * 
* * * Q * 
Q * * * * 
* * Q * * 
-----------
* * * * Q 
* * Q * * 
Q * * * * 
* * * Q * 
* Q * * * 
-----------
nqueen = 10

java实现 算法-n皇后

Java相关栏目本月热门文章

java实现算法-n皇后