02月
18

发表于 • 字数统计 2644 • 被 56 人看爆

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;
        }
    }
}

参考

分享到：