回溯法（八皇后）-蒲公英云

回溯法（八皇后）

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

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

这里写图片描述

代码：

public class Queen { 
    public static int num = 0;//累计方案
    public static final int MAXQUEEN = 8;
    public static int[] cols = new int[MAXQUEEN];//定义cols数组，表示8列棋子皇后摆放的位置,一列一列的插入
    /** * * @param n 填第n列的皇后 */
    public void getCount(int n){
        boolean [] rows = new boolean[MAXQUEEN];//记录每列每个方格是否可以放皇后
        for(int m = 0;m<n;m++){
            rows[cols[m]] = true;
            int d = n - m;//斜对角
            //正斜方向
            //if判断防止行数为负或大于最大行数
            if(cols[m]-d>=0){
                rows[cols[m] -d] = true;
            }
            //反斜方向
            if(cols[m]+d<=(MAXQUEEN-1)){
                rows[cols[m]+d] = true;
            }
        }
        //到此知道了哪些位置不能放皇后
        for(int i = 0;i<MAXQUEEN;i++){
            if(rows[i]){
                //不能放
                continue;
            }
            cols[n] = i;
            if(n<MAXQUEEN-1){
                getCount(n+1);
            }else{
                //找到完整的一套方案
                num++;
                printQueen();
            }
            //下面可能仍然有合法位置
        }
    }
    private void printQueen() {
        System.out.println("第"+num+"种方案");
        for(int i = 0;i<MAXQUEEN;i++){
            for(int j = 0;j<MAXQUEEN;j++){
                if(i == cols[j]){
                    System.out.print("0 ");
                }else{
                    System.out.print("+ ");
                }
            }
            System.out.println();
        }
    }
    public static void main(String[] args){
        Queen queen = new Queen();
        queen.getCount(0);
    }
}

结果：

第1种方案
0 + + + + + + +
+ + + + + + 0 +
+ + + + 0 + + +
+ + + + + + + 0
+ 0 + + + + + +
+ + + 0 + + + +
+ + + + + 0 + +
+ + 0 + + + + +
第2种方案
0 + + + + + + +
+ + + + + + 0 +
+ + + 0 + + + +
+ + + + + 0 + +
+ + + + + + + 0
+ 0 + + + + + +
+ + + + 0 + + +
+ + 0 + + + + +
未显示完全