算法--策略-回溯八皇后问题

回溯可以理解为, 通过选择不同的岔路口来通往目的地, 每一步都选择一条路出发, 能进则进, 不能则退回上一步, 换一条路再尝试

树和图的深度优先搜索, 八皇后, 走迷宫都是典型的回溯应用

树的深度搜索

八皇后

在8 * 8 的国际象棋上摆放八个皇后, 使其不能相互攻击, 任意两个皇后都不能处于同一行, 同一列, 同一斜线上, 总共有多少摆法?

八皇后问题

解决思路

暴力法, 将每一种摆法进行尝试, 检查是否可行, 复杂度较高

回溯法, 回溯剪枝

回溯法求解

剪枝处理, 去除不合理的分支

剪枝

八皇后1

八皇后2

八皇后3

    /**
     * 数组索引是行号, 数组元素是列号
     */
    int[] cols;
    /**
     * 多少种摆放
     */
    int ways;
    
    void palceQueens(int n) {
        if (n < 1) return;
        cols = new int[n];
        place(0);
        System.out.println(n + "皇后一共有" + ways + "种摆法");
    }
    
    void place(int row) {
        if (row == cols.length) {
            ways++;
            show();
            return;
        }
        
        for (int col = 0; col < cols.length; col++) {
            if (isValid(row, col)) {
                cols[row] = col;
                place(row + 1);
            }
        }
        
    }
    
    /**
     * 判断第row 行第col 列是否可以摆放皇后
     * @param row
     * @param col
     * @return
     */
    boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 第col 列已经有皇后
            if (cols[i] == col) {
//              System.out.println("[" + row + "][" + col + "]=false");
                return false;
            }
            // 第i 行的皇后跟第row 行第col 列处在同一斜线上
            if (row - i == Math.abs(col - cols[i])) {
//              System.out.println("[" + row + "][" + col + "]=false");
                return false;
            }
        }
//      System.out.println("[" + row + "][" + col + "]=true");
        return true;
    }
    
    void show() {
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if (cols[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("-----------------------------");
    }

优化

增加记录左上和右上的变量是否摆放了皇后

    /**
     * 数组索引时行号, 数组元素是列号
     */
    int[] queens;
    
    /**
     * 标记某一行是否是皇后
     */
    boolean[] cols;
    
    /**
     * 标记某一斜线上是否有皇后, 左上角 -> 右下角
     */
    boolean[] leftTop;
    
    /**
     * 标记斜线, 右上角 -> 左下角
     */
    boolean[] rightTop;
    
    /**
     * 摆法
     */
    int ways;
    
    void placeQueens(int n) {
        if (n < 1) return;
        queens = new int[n];
        cols = new boolean[n];
        leftTop = new boolean[(n << 1) - 1];
        rightTop = new boolean[leftTop.length];
        place(0);
        System.out.println(n + "皇后共有" + ways + "种摆法");
    }
    
    /**
     * 从第row 行开始摆放
     * @param row
     */
    void place(int row) {
        if (row == cols.length) {
            ways++;
            show();
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            
            if (cols[col]) continue;
            // 左上角公式
            int ltIndex = row - col + cols.length - 1;
            if (leftTop[ltIndex]) continue;
            // 右上角公式
            int rtIndex = row + col;
            if (rightTop[rtIndex]) continue;
            
            queens[row] = col;
            cols[col] = true;
            leftTop[ltIndex] = true;
            rightTop[rtIndex] = true;
          // 注意将之前的值恢复
            place(row + 1);
            cols[col] = false;
            leftTop[ltIndex] = false;
            rightTop[rtIndex] = false;
        }
    }
    
    
    void show() {
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("-----------------------------");
    }

继续优化

使用位运算, 0 和1 记录当前位置是否摆放了皇后

    int ways;
    /**
     * 数组索引是行号, 元素是列号
     */
    int[] queens;
    /**
     * 标记某一列是否有皇后
     */
    byte cols;
    /**
     * 斜线上是否有皇后, 左上角 -> 右下角
     */
    short leftTop;
    /**
     * 斜线上是否有皇后, 右上角 -> 左下角
     */
    short rightTop;
    
    void placeQueens(int n) {
        if (n < 1) return;
        queens = new int[n];
        place(0);
        System.out.println(n + "皇后一共有" + ways + "种摆法");
    }
    
    void place(int row) {
        if (row == 8) {
            ways++;
            show();
            return;
        }
        
        for (int col = 0; col < 8; col++) {
            int cv = 1 << col;
            if ((cols & cv) != 0) continue;
            
            int lv = 1 << (row - col + 7);
            if ((leftTop & lv) != 0) continue;
            
            int rv = 1 << (row + col);
            if ((rightTop & rv) != 0) continue;
            
            queens[col] = col;
            cols |= cv;
            leftTop |= lv;
            rightTop |= rv;
            place(row + 1);
          // 恢复状态
            cols &= ~cv;
            leftTop &= ~lv;
            rightTop &= ~rv;
        }
        
    }

    void show() {
        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("-----------------------------");
    }