首页 > 编程语言 > 详细

回溯算法 - 八皇后

时间:2021-02-23 11:24:09      阅读:28      评论:0      收藏:0      [点我收藏+]

1、八皇后问题
我们有一个 8x8 的棋盘,希望往里放 8 个棋子(皇后),每个棋子所在的行、列、对角线
都不能有另一个棋子。你可以看我画的图,第一幅图是满足条件的一种方法,第二幅图是不
满足条件的。八皇后问题就是期望找到所有满足这种要求的放棋子方式。
技术分享图片

2、解答

/**
 * 回溯算法-八皇后问题
 */
public class NQueen {

    int[] res = new int[4];

    public static void main(String[] args) {
        new NQueen().cal8Queens(0);
    }

    public void cal8Queens(int row) {
        if (row == 4) {
            printRes(res);
            return;
        }

        for (int col = 0; col < 4; col++) {
            if (isOk(row, col)) {
                res[row] = col;
                cal8Queens(row  +1);
            }
        }

    }

    private void printRes(int[] res) {
        for (int row = 0; row < 4; row++) {
            for (int col = 0; col < 4; col++) {
                if (res[row] == col) {
                    System.out.print("Q");
                } else {
                    System.out.print("*");
                }
            }
            System.out.println();
        }
        System.out.println();

    }

    private boolean isOk(int row, int col) {
        //左上角
        int leftUp = col - 1;
        // 右上角
        int rightUp = col + 1;
        for (int i = row - 1; i >= 0; i--) {
            // 当前点上有,返回false
            if (res[i] == col) {
                return false;
            }
            // 左上角或右上角有
            if (leftUp >= 0) {
                if (res[i] == leftUp) {
                    return false;
                }
            }
            if (rightUp < 4) {
                if (res[i] == rightUp) {
                    return false;
                }
            }

            leftUp--;
            rightUp++;
        }

        return true;
    }

}

回溯算法 - 八皇后

原文:https://www.cnblogs.com/noaman/p/14433836.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!