八皇后 订阅
八皇后问题(英文:Eight queens),是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。计算机发明后,有多种计算机语言可以编程解决此问题。 展开全文
八皇后问题(英文:Eight queens),是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。计算机发明后,有多种计算机语言可以编程解决此问题。
信息
外文名
Eight queens
提出时间
1848 年
中文名
八皇后
学    科
计算机算法
八皇后问题回溯算法思路
八皇后问题如果用穷举法需要尝试88=16,777,216种情况。每一列放一个 八皇后问题(3张) 皇后,可以放在第 1 行,第 2 行,……,直到第8行。穷举的时候从所有皇后都放在第1行的方案开始,检验皇后之间是否会相互攻击。如果会,把列H的皇后挪一格,验证下一个方案。移到底了就“进位”到列G的皇后挪一格,列H的皇后重新试过全部的8行。这种方法是非常低效率的,因为它并不是哪里有冲突就调整哪里,而是盲目地按既定顺序枚举所有的可能方案。回溯算法优于穷举法。将列A的皇后放在第一行以后,列B的皇后放在第一行已经发生冲突。这时候不必继续放列C的皇后,而是调整列B的皇后到第二行,继续冲突放第三行,不冲突了才开始进入列C。如此可依次放下列A至E的皇后,如图2所示。将每个皇后往右边横向、斜向攻击的点位用叉标记,发现列F的皇后无处安身。这时回溯到列E的皇后,将其位置由第4行调整为第8行,进入列F,发现皇后依然无处安身,再次回溯列E。此时列E已经枚举完所有情况,回溯至列D,将其由第2行移至第7行,再进入列E继续。按此算法流程最终找到如图3所示的解,成功在棋盘里放下了8个“和平共处”的皇后。继续找完全部的解共92个。回溯算法求解八皇后问题的原则是:有冲突解决冲突,没有冲突往前走,无路可走往回退,走到最后是答案。为了加快有无冲突的判断速度,可以给每行和两个方向的每条对角线是否有皇后占据建立标志数组。放下一个新皇后做标志,回溯时挪动一个旧皇后清除标志。
收起全文
精华内容
下载资源
问答
  • 八皇后

    2016-10-15 14:45:54
    八皇后
    #include <math.h>
    #include <stdio.h>
    
    #define MAX 8 // 宏定义皇后个数
    
    typedef struct // 位置结构体
    {
        int x; // x 坐标
        int y; // y 坐标
    }Point;
    
    int count = 0; // 统计方法的总数
    Point queen[MAX + 2]; // 皇后数组
    
    /**
        @function:  将第index个皇后放在(x, y)的位置
        @param:     x-->当前皇后所放的行
                    y-->当前皇后所放的列
                    index-->当前皇后的下标
        @return:    void
    */
    void putQueen(int x, int y, int index)
    {
        int i;
        // 下标超出范围,返回
        if (index > MAX)
        {
            return;
        }
        // 暂定当前皇后的位置
        queen[index].x = x;
        queen[index].y = y;
    
        // 判断与前面放的皇后是否符合规则
        for (i = 1; i<index; i++)
        {
            // 如果同行或同列有皇后,则返回
            if (x == queen[i].x || y == queen[i].y)
            {
                return;
            }
            // 如果斜方向有皇后,则返回 
            if (abs(x - queen[i].x) == abs(y - queen[i].y))
            {
                return;
            }
        }
        // 下标等于皇后个数,说明已经放完,输出当前情况
        if (index == MAX)
        {
            printf("\n第 %d 种方法:\n", ++count);
            for (i = 1; i <= MAX; i++)
            {
                printf("Queen %d: (%d, %d)\n", i, queen[i].x, queen[i].y);
            }
            return;
        }
        // 已经暂定index个皇后的位置,讨论第index+1个皇后的位置 
        for (i = 1; i <= MAX; i++)
        {
            putQueen(x + 1, i, index + 1);
            // 讨论完一种情况后将index+1个皇后的的下标初始化 
            queen[index + 1].x = 0;
            queen[index + 1].y = 0;
        }
    }
    
    int main()
    {
        count = 0; // 初始化放法为0
        putQueen(0, 0, 0); // 从第0个皇后开始
        return 0;
    }
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,253
精华内容 4,101
关键字:

八皇后