回溯算法思想与八皇后问题解的个数

八皇后问题:

在8*8的国际象棋棋盘上,皇后是威力较大的棋子,它可以攻击到与自己同行、同列以及同一斜线上的棋子,如下图,所有橙色格子上的棋子,都可能会被皇后攻击:

而八皇后问题就是在8*8的棋盘上,找到合适的位置放置8个皇后,让它们不会相互攻击,而且需要找出这样的放法共有多少种。

回溯法的思想:

回溯法就是当我们确定了一个问题的解空间的结构后,从根节点出发,以深度优先的方式去遍历解空间,找到合适的解。所以用此方法分析八皇后问题如下:

解空间的结构:

将棋盘看作0-7的平面直角坐标系,八皇后问题的解就是寻找八个点的坐标(i,j)。先抛开具体问题的约束来看,我们要寻找的第一个坐标有64中可能,当第一个坐标确定后,第二个坐标也有64中可能,第三个同样如此......因此,所有可能的解形成了一个64叉树(类比二叉树的说法),这就是有可能的解(64^8种可能),解空间结构是64叉树形状的。

基于此解空间的结构,才能以深度优先的方式去遍历解空间,并寻找合适的解。

问题的解:

当我们结合问题对解的约束来看,八皇后问题的解就是这个64叉树上某些从根节点到叶子节点的路径上的坐标。具体约束就是皇后的攻击规则(任意两点不能在同一直线或斜线上)。

回溯遍历解空间:

也就是将皇后一个个摆上去,当我们摆到第n个皇后时,若发现按照约束条件,任何位置都不能摆放,那就说明第n-1个皇后在当前位置不能得到正确的解,所以需要重新确定第n-1个皇后的位置。若第n-1个皇后再无其他位置可摆放,则需要重新确定第n-2个皇后的位置......

这就是回溯遍历解空间,在算法实现时,可以使用递归或迭代进行回溯遍历,分别被称为递归回溯和迭代回溯。

八皇后问题算法解决:

算法使用名为queen的二维int数组表示棋盘,数组的索引表示0-7的坐标,值为0表示空白,值为1表示皇后的摆放位置。

由于任意一行不能有两个皇后,所以每一行必须摆放一个,因此程序在每一行依次尝试:

package com.yawn.queen;

/**
 * @author yawn
 */
public class QueenTest {

    private static final int SIZE = 8;

    private static int[][] queen = new int[SIZE][SIZE];

    public static void main(String[] args) {
        for (int i = 0; i < SIZE; i++) {
            // 每一行都从0位置开始尝试放置
            place(i, 0);
        }
        printQueen("结果为");
    }

    /**
     * 第i行的放置
     */
    private static void place(int i, int start) {
        // 是否放置成功
        boolean placed = false;
        for(int j = start; j < SIZE; j++) {
            if (check(i, j)) {
                queen[i][j] = 1;
                placed = true;
                printQueen("第 " + i + " 行放置");
                break;
            }
        }
        if (!placed) {
            int index = seek(i - 1);
            // 去掉已经放置的皇后
            queen[i-1][index] = 0;
            printQueen("回溯到第 " + (i-1) + " 行,从 " + (index+1) + " 开始");
            place(i-1, index+1);
            place(i, 0);
        }
    }


    /// 以下为工具方法,内容单一,浅显易懂
    /**
     * 输出棋盘
     */
    private static void printQueen(String action) {
        System.out.println("---> " + action);
        for (int[] cells : queen) {
            for (int cell : cells) {
                System.out.print(cell + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 寻找第i行放置皇后的位置
     */
    private static int seek(int i) {
        for (int j = 0; j < SIZE; j++) {
            if (queen[i][j] == 1) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 检查queen[i][j] 是否可以放置皇后
     */
    private static boolean check(int i, int j) {
        for(int m = 0; m < SIZE; m++) {
            for(int n = 0; n < SIZE; n++) {
                if (queen[m][n]==1 && (i == m || j == n || Math.abs(i - m) == Math.abs(j - n))) {
                    // queen[m][n]==1 :(m,n)位置有皇后
                    // i == m :同行
                    // j == n :同列
                    // Math.abs(i - m) == Math.abs(j - n) :同一斜线(两个位置连线的斜率绝对值为1)
                    // 如果满足if条件,则(i,j)不可放置皇后
                    return false;
                }
            }
        }
        return true;
    }
}

求解过程中的输出片段如下:

---> 第 5 行放置
1	0	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	
0	1	0	0	0	0	0	0	
0	0	0	0	0	0	0	1	
0	0	0	0	0	1	0	0	
0	0	1	0	0	0	0	0	
0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	
---> 回溯到第 5 行,从 3 开始
1	0	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	
0	1	0	0	0	0	0	0	
0	0	0	0	0	0	0	1	
0	0	0	0	0	1	0	0	
0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	
---> 第 5 行放置
1	0	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	
0	1	0	0	0	0	0	0	
0	0	0	0	0	0	0	1	
0	0	0	0	0	1	0	0	
0	0	0	1	0	0	0	0	
0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	

我们可以看出:第5行放置在了(5,2)位置,然后尝试放置第六行,结果第6行无法放置,所以回溯到第5行,从(5,3)位置继续尝试放置,并在(5,3)放置成功。

八皇后问题解的个数:

以上代码为我们找到了问题的一个解,但我们想知道一共有多少解存在,这就需要我们稍微修改代码,具体如下:

在以上代码中,若找到一个可行的解之后,程序就会执行结束。但我们若要找到所有的解,就需要在找到可行解后,继续让程序尝试下一个解即可。具体做法就是当最后一行都可以放置好皇后时,我们只记录这个解,然后再让程序尝试当前位置的下一个位置,而不退出程序。

当遍历完所有可能的解之后,就可以停止程序。由于在递归调用过程中,会产生很深的方法栈,导致栈满报错,所以棋盘不宜设置太大:

八皇后问题解的个数具体实现如下:

package com.yawn.queen;

/**
 * @author yawn
 */
public class QueenTest2 {

    private static final int SIZE = 12;
    private static int count = 0;

    private static int[][] queen = new int[SIZE][SIZE];

    public static void main(String[] args) {
        for (int i = 0; i < SIZE; i++) {
            place(i, 0);
        }
    }

    /**
     * 第i行的放置
     */
    private static void place(int i, int start) {
        if (i==0 && start== SIZE) {
            System.out.println("结果集已经遍历完毕,共找到结果数为:" + count);
            System.exit(0);
        }
        // 第i行是否放置成功
        boolean rowPlaced = false;
        // 遍历第i行每个位置是否可以放置皇后
        for(int j = start; j < SIZE; j++) {
            if (check(i, j)) {
                queen[i][j] = 1;
                rowPlaced = true;
                // 最后一行放置成功,则得到一个结果,打印结果后从下一位置继续回溯遍历结果集
                if (i== SIZE -1) {
                    count++;
                    printQueen("第" + count + "个结果,从(" + (SIZE-1) + "," + (j+1) + ")继续回溯寻找...");
                    // 去掉已经放置的皇后
                    queen[i][j] = 0;
                    place(i, j+1);
                }
                break;
            }
        }
        // 如果第i行没有放置成功,则回溯到第i-1行(重新放置第i-1行)
        if (!rowPlaced) {
            int index = seek(i - 1);
            reset(i-1, index);
            // 回溯放置第i-1行
            place(i-1, index+1);
            // 直到第i-1行放置成功,再开始放置第i行(最终将所有结果集遍历完毕后,只能使用exit(0)退出程序)
            place(i, 0);
        }
    }


    /// 以下为工具方法,内容单一,浅显易懂
    /**
     * 输出棋盘
     */
    private static void printQueen(String string) {
        System.out.println("---> " + string);
        for (int[] cells : queen) {
            for (int cell : cells) {
                System.out.print(cell + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 去掉(i,j)位置已经放置的皇后
     */
    private static void reset(int i, int j) {
        queen[i][j] = 0;
    }

    /**
     * 寻找第i行放置皇后的位置
     */
    private static int seek(int i) {
        for (int j = 0; j < SIZE; j++) {
            if (queen[i][j] == 1) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 检查queen[i][j] 是否可以放置皇后
     */
    private static boolean check(int i, int j) {
        for(int m = 0; m < SIZE; m++) {
            for(int n = 0; n < SIZE; n++) {
                if (queen[m][n]==1) {
                    if (i == m || j == n || Math.abs(i - m) == Math.abs(j - n)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
---> 第91个结果,从(7,4)继续回溯寻找...
0	0	0	0	0	0	0	1	
0	0	1	0	0	0	0	0	
1	0	0	0	0	0	0	0	
0	0	0	0	0	1	0	0	
0	1	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	
0	0	0	0	0	0	1	0	
0	0	0	1	0	0	0	0	
---> 第92个结果,从(7,5)继续回溯寻找...
0	0	0	0	0	0	0	1	
0	0	0	1	0	0	0	0	
1	0	0	0	0	0	0	0	
0	0	1	0	0	0	0	0	
0	0	0	0	0	1	0	0	
0	1	0	0	0	0	0	0	
0	0	0	0	0	0	1	0	
0	0	0	0	1	0	0	0	
结果集已经遍历完毕,共找到结果数为:92

最终棋盘规格为8*8时,共有92个解。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

深度学习对话系统实战篇 -- 简单 chatbot 代码实现

本文的代码都可以到我的 github 中下载:https://github.com/lc222/seq2seq_chatbot 前面几篇文章我们已经介绍了 s...

5848
来自专栏数据结构与算法

P1284 三角形牧场

题目描述 和所有人一样,奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师Hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40)块木板,每块的长度L...

34110
来自专栏数据结构与算法

学大伟业 国庆Day2

期望得分:30+100+0=130 实际得分:30+100+20=150 忍者钩爪 (ninja.pas/c/cpp) 【问题描述】 小Q是一名酷爱钩爪的忍者,...

3514
来自专栏数据结构与算法

tarjan系列算法代码小结

个人使用,可能不是很详细 强联通分量 这里的dfn可以写成low 因为都是在栈中,只要保证该节点的low值不为本身即可 void tarjan(int now)...

3387
来自专栏人工智能LeadAI

机器学习实战 | 第五章:模型保存(持久化)

一、工具 sklearn官方给出了两种保存模型的方式:3.4. Model persistence 其中一种是pickle的方式,还有一种就是joblib包的...

2878
来自专栏深度学习之tensorflow实战篇

R常用基本 函数汇总整理

help() 或者 ? + command 这是学习和使用R最常用到的命令。 help.search() 或者?? 搜索包含制定字串或pattern的...

2793
来自专栏Fish

蓝桥杯 幸运数

先说题意。题意有点长,我还是复制粘贴吧。。。 问题描述 幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。 首先从1开始写出自然数1,...

1906
来自专栏HansBug's Lab

算法模板——Tarjan强连通分量

功能:输入一个N个点,M条单向边的有向图,求出此图全部的强连通分量 原理:tarjan算法(百度百科传送门),大致思想是时间戳与最近可追溯点 这个玩意不仅仅是求...

3449
来自专栏数据结构与算法

1225 八数码难题

题目描述 Description Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们. 问题描述 在3×3的棋盘上,...

3117
来自专栏极客慕白的成长之路

关系代数中的除法运算

  这个概念的描述的非常抽象,刚开始学习的同学完全不知所云。这里通过一个实例来说明除法运算的求解过程

581

扫描关注云+社区