【数据结构与算法(Java)】八皇后问题(回溯算法-递归)

1. 递归思路

  1. 基本情况:放置到第8个皇后(即找到一个解法)
  2. 向基本情况靠近:若当前皇后的放置位置不冲突,则放置下一个皇后到下一行
  3. 调用自身:将当前皇后数加1后作为参数,继续放置

2. 代码实现

/**
 * 八皇后问题 - 回溯算法(递归)
 */
public class EightQueenProblem {
    /**
     * 一位数组表示棋盘
     * index - 行
     * data  - 列
     */
    private static int[] chessArray = new int[8];
    // 存放解法集合
    public static ArrayList<int[]> solutionList = new ArrayList<>();

    // 检查次数
    public static int checkCount;

    /**
     * 添加一种解法到list
     */
    private static void addSolution() {
        int[] newSolution = new int[8];
        for (int i = 0; i < 8; i  ) {
            newSolution[i] = chessArray[i];
        }
        solutionList.add(newSolution);
    }

    /**
     * 检查是否可以放置
     *  1 同行不可放
     *  2 同列不可放: chessArray[line] == chessArray[line]
     *  3 同斜线不可放:
     *      行差 == 列差 <-> Math.abs(queenNumber - line) == Math.abs(chessArray[queenNumber] - chessArray[line])
     * @param queenNumber - 放置的第几个皇后
     * @return - true可放置,false不可
     */
    private static boolean canPut(int queenNumber) {
        checkCount  ;
        for (int line = 0; line < queenNumber; line  ) {
            if (chessArray[line] == chessArray[queenNumber]
                    || Math.abs(queenNumber - line) == Math.abs(chessArray[queenNumber] - chessArray[line])) {
                return false;
            }
        }
        return true;
    }

    /**
     *
     * @param queenNumber - 放置的第几个皇后
     */
    public static void putChessPieces(int queenNumber) {
        // 若放到第8个皇后:找到一个解法,添加到list,结束方法
        if (queenNumber == 8) {
            addSolution();
            return;
        }
        // 否则逐行放入皇后,判断是否可放置 (i 为列数)
        for (int i = 0; i < 8; i  ) {
            // 将 第queenNumber个皇后 放到第 i 列
            chessArray[queenNumber] = i;
            // 若此时可以放置,则继续放置下一个皇后(递归)
            if (canPut(queenNumber)) {
                putChessPieces(queenNumber   1);
            }
            // 若不可放,则继续遍历:即把皇后放到 第 i   1列 继续判断
        }

    }
}

3. 结果

  • 共92种解法
  • 共判断是否可放置皇后15720次
  • 解法:
    0 4 7 5 2 6 1 3
    0 5 7 2 6 3 1 4
    0 6 3 5 7 1 4 2
    0 6 4 7 1 3 5 2
    1 3 5 7 2 0 6 4
    1 4 6 0 2 7 5 3
    1 4 6 3 0 7 5 2
    1 5 0 6 3 7 2 4
    1 5 7 2 0 3 6 4
    1 6 2 5 7 4 0 3
    1 6 4 7 0 3 5 2
    1 7 5 0 2 4 6 3
    2 0 6 4 7 1 3 5
    2 4 1 7 0 6 3 5
    2 4 1 7 5 3 6 0
    2 4 6 0 3 1 7 5
    2 4 7 3 0 6 1 5
    2 5 1 4 7 0 6 3
    2 5 1 6 0 3 7 4
    2 5 1 6 4 0 7 3
    2 5 3 0 7 4 6 1
    2 5 3 1 7 4 6 0
    2 5 7 0 3 6 4 1
    2 5 7 0 4 6 1 3
    2 5 7 1 3 0 6 4
    2 6 1 7 4 0 3 5
    2 6 1 7 5 3 0 4
    2 7 3 6 0 5 1 4
    3 0 4 7 1 6 2 5
    3 0 4 7 5 2 6 1
    3 1 4 7 5 0 2 6
    3 1 6 2 5 7 0 4
    3 1 6 2 5 7 4 0
    3 1 6 4 0 7 5 2
    3 1 7 4 6 0 2 5
    3 1 7 5 0 2 4 6
    3 5 0 4 1 7 2 6
    3 5 7 1 6 0 2 4
    3 5 7 2 0 6 4 1
    3 6 0 7 4 1 5 2
    3 6 2 7 1 4 0 5
    3 6 4 1 5 0 2 7
    3 6 4 2 0 5 7 1
    3 7 0 2 5 1 6 4
    3 7 0 4 6 1 5 2
    3 7 4 2 0 6 1 5
    4 0 3 5 7 1 6 2
    4 0 7 3 1 6 2 5
    4 0 7 5 2 6 1 3
    4 1 3 5 7 2 0 6
    4 1 3 6 2 7 5 0
    4 1 5 0 6 3 7 2
    4 1 7 0 3 6 2 5
    4 2 0 5 7 1 3 6
    4 2 0 6 1 7 5 3
    4 2 7 3 6 0 5 1
    4 6 0 2 7 5 3 1
    4 6 0 3 1 7 5 2
    4 6 1 3 7 0 2 5
    4 6 1 5 2 0 3 7
    4 6 1 5 2 0 7 3
    4 6 3 0 2 7 5 1
    4 7 3 0 2 5 1 6
    4 7 3 0 6 1 5 2
    5 0 4 1 7 2 6 3
    5 1 6 0 2 4 7 3
    5 1 6 0 3 7 4 2
    5 2 0 6 4 7 1 3
    5 2 0 7 3 1 6 4
    5 2 0 7 4 1 3 6
    5 2 4 6 0 3 1 7
    5 2 4 7 0 3 1 6
    5 2 6 1 3 7 0 4
    5 2 6 1 7 4 0 3
    5 2 6 3 0 7 1 4
    5 3 0 4 7 1 6 2
    5 3 1 7 4 6 0 2
    5 3 6 0 2 4 1 7
    5 3 6 0 7 1 4 2
    5 7 1 3 0 6 4 2
    6 0 2 7 5 3 1 4
    6 1 3 0 7 4 2 5
    6 1 5 2 0 3 7 4
    6 2 0 5 7 4 1 3
    6 2 7 1 4 0 5 3
    6 3 1 4 7 0 2 5
    6 3 1 7 5 0 2 4
    6 4 2 0 5 7 1 3
    7 1 3 0 6 4 2 5
    7 1 4 2 0 6 3 5
    7 2 0 5 1 4 6 3
    7 3 0 2 5 1 6 4

来源:https://www.icode9.com/content-1-879401.html

(0)

相关推荐