趣谈八皇后问题

1,507 阅读3分钟
Money is not everything. There's MasterCard.
金钱不是万能的, 有时还需要信用卡。

背景

大话西游之月光宝盒这部电影已经刷了N遍了。每一次看都有每一次的感悟。如果时光可以到倒流,我当初就不应该。。。 悔不当初,悔不当初。


虽然世界上没有后悔药,但是算法界却是有后悔药的,呢就是---回溯算法。人生不能时光倒流,呢我让我的算法时光倒流。

 八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔于1848年提出的,现在都21世纪了,八皇后怎么能满足我,我决定实现一个N皇后,我想要几个皇后就要几个皇后。

所有源码均已上传至github:链接

N皇后

思考

家家有本难念的经,一个皇后已经了不得了。这N皇后嘛,可得好好处理,不能让她们打架。可以先声明一个大小为N的一维数组,来存储我的这N位皇后。然后分成N个阶段。

  • 第一个阶段随便选一个位置。
  • 第二个阶段需要判断一下我的横排,竖排,左对角线,右对角线(只需要和第一阶段和本身相比即可)有没有皇后。如果没有,则继续往下走。
  • 第三个阶段以此类推,发现有皇后,不慌,没关系,时光倒流,到第二阶段,重新摆放。
  • 第N阶段....直到摆出让每一位皇后满意的位置。

大概思路就是这样。

初始化

    /**
     * 皇后数组
     */
    private int[] queens;
    /**
     * n皇后
     */
    private int n;
    /**
     * 摆法数量
     */
    private int count;

    /**
     * 基于8皇后而衍生的N皇后
     *
     * @param n 皇后的数量
     */
    private SolveNQueens(int n) {
        queens = new int[n];
        this.n = n;
        count = 0;
    }

递归

虽然代码很精简,但是关键就在于这个递归不好理解。循环里套递归,很巧妙。需要一步一步跟一下就知道了。

一维数组存储的值是皇后的位置(0,n-1)。

默认是要从头开始的,需要这么调用该方法calNQueens(0)

    private void calNQueens(int row) {
        if (row == n) {
            printQueens(queens);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSatisfy(row, col)) {
                queens[row] = col;
                calNQueens(row + 1);
            }
        }
    }

是否满足条件

该方法需要判断自己的横竖排,左右对角线是否有皇后。

这里为了便于理解,所以循环里放着三个if。

    private boolean isSatisfy(int row, int col) {
//        System.out.println("(" + row + "," + col + ")");
        int leftUp = col - 1;
        int rightUp = col + 1;
        for (int i = row - 1; i >= 0; --i) {
            if (queens[i] == col) return false;
            if (leftUp >= 0 && queens[i] == leftUp) return false;
            if (rightUp < n && queens[i] == rightUp) return false;
            --leftUp;
            ++rightUp;
        }
        return true;
    }

打印

    private void printQueens(int[] queens) {
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (queens[row] == col) System.out.print("1 ");
                else System.out.print("0 ");
            }
            System.out.println();
        }
        System.out.println();
        ++count;
    }

测试代码

    public static void main(String[] args) {
        int n = 8;
        SolveNQueens solveNQueens = new SolveNQueens(n);
        solveNQueens.calNQueens(0);
        System.out.println("共计" + solveNQueens.count + "种摆法.");
    }

测试结果

4皇后


八皇后(这里是包含了旋转和对称的解的解,否则是12种摆法)


end


您的点赞和关注是对我最大的支持,谢谢!