欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回溯思想——八皇后问题

程序员文章站 2024-01-25 22:07:10
...

首先描述一下8皇后问题:

        在8x8的国际象棋棋盘上,放上八个皇后,使得每一个皇后都不能直接吃掉其他的皇后。在国际象棋中,皇后可以吃掉同行、列、45°线、135°线上的其他子。

介绍一下回溯法:

        回溯法与穷举法非常相似,只是通过“剪枝”的思想,减少穷举的次数。可以将回溯法理解为一种加强版的穷举法。

        首先来介绍一下穷举法解八皇后问题,可以这样想:任意两个皇后不能放在同一行,故8个皇后一定放在不同的8行中,每个皇后放的时候又有8个位置可以选择,所以穷举法应该是这样的逻辑:

for  1  ---->   8                                 //放第1行
    for  1  ---->   8                             //放第2行
        for  1  ---->   8                         //放第3行
            for  1  ---->   8                     //放第4行
                for  1  ---->   8                 //放第5行
                    for  1  ---->   8             //放第6行
                        for  1  ---->   8         //放第7行
                            for  1  ---->   8     //放第8行
                                judge_quene()     //判断摆放合法

        共有8^8种情况,这显然有些多。仔细分析如果第1次和第2次皇后分别放在了如图红色、蓝色的位置:

                回溯思想——八皇后问题

        这个时候已经违背了放置规则,那么余下6行的8^6种情况就一定都是不符合要求的,这就大大浪费了计算资源。合理的做法应该是这样:当蓝色的皇后放下时,判断一下当前位置是否合理,不合理则将这种情况对应的后6行的操作都放弃,将蓝色皇后从棋盘中拿出,继续流程(放到黄色位置)。

        这就是回溯法的主要思想——在每次操作后对本次操作进行一次判断,当本次操作已经违背了规则,则本次操作所对应的之后的操作就全都放弃不要了(这个过程称为“剪枝”)。当完成了一条“枝”的全部可行情况的遍历后,把本“枝”去掉(这个过程称为“回溯”),换下一个条“枝”继续。

        有了回溯思想,就可以把程序的逻辑变成这个样子:

            回溯思想——八皇后问题

        算法上使用递归法是最方便的,递归的跳出条件是:未被“剪枝”的行完成了1至8列的遍历。

        记录时使用:

                char quene_array[8];

        矩阵的行号代表棋盘的行号,矩阵的值代表对应行中皇后被放置在哪个列。递归函数如下:

void quene(char line, char * quene_array)
{
    int i;
    for (i = 0; i < 8; i++) {
        if (put_quene_judge(quene_array, line, i)) {
            quene_array[line] = i;                          //合法放置
            line++;
        }
        else {
            continue;                                       //剪枝动作
        }
        if (line == 8) {                                    //第8行完成了合法放置输出摆放方式
            num++;
            printf("The %d way is:\n", num);
            print_quene(quene_array);
        }
        else {
            quene(line, quene_array);                       //合法放置则继续递归
            line--;                                         //回溯动作
        }
    }
}

        最后介绍一下摆放合法性的判断函数。判断时遍历放置的所有皇后,假设已放置的皇后行号和列号为(a1,b1),本次放置的皇后行列号为(a2,b2),则需要满足:

        1、b1 != b2

        2、b1 - b2 != a1 - a2 45°对角线情况

        3、b1 - b2 != a2 - a1 125°对角线情况

判断程序片段如下:

	
//皇后放置合法性判断函数
char put_quene_judge(char *quene_array, char line, char num)
{
    int i;
    for (i = 0; i < line; i++) {
        if ((quene_array[i] == num) 
            || (line - i == num - quene_array[i]) 
            || (line - i == quene_array[i] - num))
            return 0;
    }
    return 1;
}

总结:

        本文通过八皇后的例子,说明了使用“剪枝”的思想,将穷举法升级为回溯法。在穷举实例数量很多,但符合条件实例却很少时,往往会使用回溯法。

附上完整的c语言程序:

#include

int num;        //全局变量,累加记录有几种可行的放置方法

//皇后位置打印
void print_quene(char *quene_array)
{
    int i, j;
    for (i = 0; i < 8; i++) {
        for (j = 0; j < 8; j++) {
            if (j == quene_array[i]) {
                printf(" O");
            }
            else {
                printf(" X");
            }
        }
        printf("\n");
    }
}

//皇后放置合法性判断函数
char put_quene_judge(char *quene_array, char line, char num)
{
    int i;
    for (i = 0; i < line; i++) {
        if ((quene_array[i] == num) 
            || (line - i == num - quene_array[i]) 
            || (line - i == quene_array[i] - num))
            return 0;
    }
    return 1;
}

void quene(char line, char * quene_array)
{
    int i;
    for (i = 0; i < 8; i++) {
        if (put_quene_judge(quene_array, line, i)) {
            quene_array[line] = i;                          //合法放置
            line++;
        }
        else {
            continue;                                       //剪枝动作
        }
        if (line == 8) {                                    //第8行完成了合法放置输出摆放方式
            num++;
            printf("The %d way is:\n", num);
            print_quene(quene_array);
        }
        else {
            quene(line, quene_array);                       //合法放置则继续递归
            line--;                                         //回溯动作
        }
    }
}

void main()
{
    char quene_array[8];
    num = 0;
    quene(0, quene_array);
}

 

相关标签: 基础算法