• 首页

  • 文章归档

  • 友链

  • 关于页面
D u e l s , I S h e e p !
D u e l s , I S h e e p !

ISheep

Code for fun, Make world better

02月
18
大学课程

DS-八皇后问题

发表于 2020-02-18 • 字数统计 2644 • 被 130 人看爆

Create by Yang

十行对我也太难了十行解法

题目描述

小灰图示
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

分析

其实也是个递归的问题,并且可衍生出N皇后问题,思路就是要让计算机不停的尝试每个摆法,直到找到正确的方案。首先看皇后存在的条件:
一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉

  1. x=row(在纵向不能有两个皇后)
  2. y=col(横向)
  3. col + row = y+x;(斜向正方向)
  4. col - row = y-x;(斜向反方向)
    本来想定义一个二维数组来表示棋盘,看了网上的解答后发现太过繁琐,直接用数组下标和value表示皇后的位置更为简便,之后学习了一个可读性比较好的解法。
  5. 首先定义两个全局变量Queen和Count分别表示皇后和解的个数。
  6. 定义一个print函数将具体摆放位置打印出来
void print()
{
    int outer, inner;
    for (outer = 0; outer < 8; outer++) //打印8行
    {
        for (inner = 0; inner < Queen[outer]; inner++)
            cout << "0 ";
        cout << "1 "; //每行首个元素打印为1
        for (inner = Queen[outer] + 1; inner < 8; inner++)
            cout << "0 "; //打印后面7列
        cout << "\n";
    }
    cout << "==================" << endl;
}
  1. 判断皇后位置的正确性,条件就是上面所说的4个条件
int is_true(int loop, int value)
{
    int index, data; //相当于皇后的坐标(x, y)
    for (index = 0; index < loop; index++)
    {
        data = Queen[index];
        if (data == value)
        {
            return 0;
        }
        if ((index + data) == (loop + value))
        {
            return 0;
        }
        if ((index - data) == (loop - value))
        {
            return 0;
        }
    }
    return 1;
}
  1. 最后是对皇后进行计算
void eight_queue(int index)
{
    int loop;
    //这里是用来构造八个皇后
    for (loop = 0; loop < 8; loop++)
    {
        //用来判断第index个皇后在loop位置是否可行
        if (is_true(index, loop))
        {
            //如果可行就将结构记录在这个全局数组中
            Queen[index] = loop;
            if (7 == index)
            {
                //打印并将全局变量增加一次
                Count++;
                print();
                //将index这个皇后清空,方便下一次遍历
                Queen[index] = 0;
                return;
            }
            //这里使用了递归
            eight_queue(index + 1);
            //这里是回溯的思想,方便下一次遍历
            Queen[index] = 0;
        }
    }
}

参考

分享到:
MathType
DS-汉诺塔
  • 文章目录
  • 站点概览
ISheep

🐏 ISheep

放羊么?

Github Twitter Email Telegram RSS
看爆 Top5
  • 2020年终总结 538次看爆
  • 【转载】 2010年的房地产调控,我们收获了什么?写在房价暴涨前 423次看爆
  • 正则表达式入门 415次看爆
  • 搬家 408次看爆
  • 二〇二一 · 迷茫 、恐慌 368次看爆

站点已萌萌哒运行 00 天 00 小时 00 分 00 秒(●'◡'●)ノ♥

Copyright © 2022 ISheep 浙ICP备19046944号

由 Halo 强力驱动 · Theme by Sagiri · 站点地图