八皇后问题求解——之递归-文章-基础课-汇编语言

八皇后问题求解——之递归

时间:09-14 09:14 阅读:2125次

*温馨提示：点击图片可以放大观看高清大图

简介：八皇后为题概述；解决八皇后为题的步骤；完整代码。

1.八皇后为题概述

什么是八皇后问题？

该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击。

所以，我们要了解皇后的攻击模式：皇后可以横着走任意步数、竖着走任意步数、斜着走任意步数。

翻译过来就是：即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。（实际上，总共有92种摆法）

例如，下面的这种摆法（0表示没有皇后，1表示摆放了皇后）：

2.解决八皇后为题的步骤 1.八皇后的存储问题 2.八皇后的打印 3.八皇后的和平相处（如何判断该位置是否可以放置一个皇后） 4.如何进行递归

问题1：八皇后的存储问题

八皇后为8*8的格式，为了节约内存，我们可以将棋盘定义为unsigned char chess[8]（当然char chess[8]也没问题）

为什么呢？char类型为8bit，所以总共就有8*8bit，其中，我们让有皇后的位置标记为1，让没有皇后的位置标记为0

问题2：八皇后的打印

我们把八皇后的打印单独写一个函数，模块化方便定位错误。

int count=0;//累积八皇后的方案个数，是一个全局变量

void Eight_Queen_Print(unsigned char *chess){
    printf("No.%d\n",count);
    for(int i=0;i<8;++i){
        for(int j=0;j<8;++j){
            printf("%c ",chess[i] & (1<<(7 & ~j))?'1':'0');
        }
        putchar('\n');
    }
    putchar('\n');
}

打印出来的格式可能是：

No.92

1 0 0 0 0 0 0 0

0 0 0 0 1 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 1 0

0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

问题3：八皇后的和平相处（如何判断该位置是否可以放置一个皇后）

1.首先，我们把有皇后的位置标记为1，把没有皇后的位置标记为0

2.其次，我们写一个函数单独检测该位置是否可以放置皇后：

—— a.检测横向时候是否已存在一个皇后

—— b.检测竖向是否已经存在一个皇后（由于我们排列皇后的顺序为从上到下，所以我们可以只检测该行上面的几个行上是否有皇后即可）

—— c.检测斜线方向（此时的斜线除了从左上角到右下角之外，还有从右上角到左下角；同上所述，我们只要检测该行上面几个行的斜线方向即可）

//这里用到了位运算，因为与八皇后问题无关，不做过多的解释了
//如果该位置可以放置皇后，返回0，否则返回1
//传入棋盘当前的状态：chess
//传入想要检测的位置：行数和列数
int Eight_Queen_Safe(unsigned char *chess,int row,int col){
    //检测同一行上是否已经有一个皇后了，其实这一步不太有必要，因为我们在写递归的时候，就已经确定，一行一行的往下找皇后可以摆放的安全位置了，横向的找到了，就往下找，所以横向的检测显得多余了。你可以不用检测横向的。
    for(int i=0;i<8;++i){
        if((chess[row] & (1<< (7& ~i))))return -1;
    }
    //检测竖向：我们只需要检测row个行数就像了，比如传入的row为3，那么此时我么就只要检测下标为0，1，2的行数即可
    for(int i=0;i<row;++i){
        if(chess[i] & (1<<(7 & ~col)))return -1;
    }
    //左上角到右下角的方向
    for(int i=row-1,j=col-1;i >= 0 && j >= 0;--i,--j){
        if(chess[i] & (1 << (7 & ~j)))return -1;
    }
    //右上角到左下角的方向
    for(int i=row-1,j=col+1;i>=0 && j<=7;--i,++j){
        if(chess[i] & (1 << (7 & ~j)))return -1;
    }
    return 0;
}

问题4：如何递归

1.首先，只要进入8皇后的递归函数，就表明该函数没有到结束条件，我们直接设置和检测皇后的位置（注意此时我们就要像递归函数传入：棋盘状态，行数和列数），我们从指定的行数和列数开始向后检测。并设置位置。当我们发现某个位置可行的时候，我们就开启递归，因为我们还有继续检测后面的位置是否可行

2.然后，我们跳出检测的循环，判断刚才循环的时候的那个位置是否有效。

a.如果整个循环下来没有发现任何一个有效位置的话，我们判断他的行数是不是最后一行，如果是最后一行，并且没有找到任何有效位置，就说明该方案不可行，直接返回即可。

b.如果我们循环下来有有效位置，我们就可以设置有效位置为皇后，然后判断，改行是不是最后一行了，如果是最后一行并且有位置可以放置皇后，那我们就可以打印该方案，同时，如果有记录可行方案的累积参数的话，我们让参数加一。

c.如果我们找到了有效位置，但是改行不是最后一行，我们就需要继续进入递归，在下一行寻找皇后的有效位置，此时传入的列数为0，因为我们要从新开的下一行的行首开始检测皇后的有效位置。

//传入棋盘的状态chess
//传入本次开始检测的其实位置：行数row和列数col
void Eight_Queen(unsigned char *chess,int row,int col){
    unsigned char chess_s[8];//这是一个临时的棋盘，只保存本次的递归的状态
    memcpy(chess_s,chess,sizeof(unsigned char)*8);//复制上次递归的状态到本次的临时棋盘当中
    int i=0;//循环计数
    for(i=col;i<8;++i){
        if(Eight_Queen_Safe(chess_s,row,i)==0){
            Eight_Queen(chess_s,row,i+1);//此时也许在i的后面还有安全的位置可以摆放皇后的位置，所以递归继续寻找
            EIGHT_QUEEN_SET(chess_s,row,i);
            //#define EIGHT_QUEEN_SET(chess,row,col) (chess[row] |= (1 << (7 & ~(col))))
            //单独谢了一个宏，用来设置棋盘中皇后的位置的
            break;//当找到安全位置的时候，跳出循环，此时的循环计数一定小于8
        }
    }
    if(i < 8 && row >=7){
        //检测循环计数i，如果i小于8，表示找到过安全位置，并且此时的row已经为7，也就是已经到了棋盘的最后一行，8皇后的一个完整的摆法已经形成，我们让方案计数count自加，并且打印范方案
        ++count;
        Eight_Queen_Print(chess_s);
    }
    else if(i < 8 && row < 7){
    //否则我们发现i小于8，也就是这次我们已经找到了一个安全为位置，但是此时不是棋盘的最后一行，我们还需要在下一行继续寻找可以摆放皇后的位置，所以行数row+1后，从列数为0出继续寻找可以摆放皇后的位置
        Eight_Queen(chess_s,row+1,0);
    }
}

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

int count=0;

#define EIGHT_QUEEN_SET(chess,row,col) (chess[row] |= (1 << (7 & ~(col))))

void Eight_Queen_Print(unsigned char *chess){
    printf("No.%d\n",count);
    for(int i=0;i<8;++i){
        for(int j=0;j<8;++j){
            printf("%c ",chess[i] & (1<<(7 & ~j))?'1':'0');
        }
        putchar('\n');
    }
    putchar('\n');
}

int Eight_Queen_Safe(unsigned char *chess,int row,int col){
    /*
    for(int i=0;i<8;++i){
        if((chess[row] & (1<< (7& ~i))))return -1;
    }
    */
    for(int i=0;i<row;++i){
        if(chess[i] & (1<<(7 & ~col)))return -1;
    }
    for(int i=row-1,j=col-1;i >= 0 && j >= 0;--i,--j){
        if(chess[i] & (1 << (7 & ~j)))return -1;
    }
    for(int i=row-1,j=col+1;i>=0 && j<=7;--i,++j){
        if(chess[i] & (1 << (7 & ~j)))return -1;
    }
    return 0;
}

void Eight_Queen(unsigned char *chess,int row,int col){
    unsigned char chess_s[8];
    memcpy(chess_s,chess,sizeof(unsigned char)*8);
    int i=0;
    for(i=col;i<8;++i){
        if(Eight_Queen_Safe(chess_s,row,i)==0){
            Eight_Queen(chess_s,row,i+1);
            EIGHT_QUEEN_SET(chess_s,row,i);
            break;
        }
    }
    if(i < 8 && row >=7){
        ++count;
        Eight_Queen_Print(chess_s);
    }
    else if(i < 8 && row < 7){
        Eight_Queen(chess_s,row+1,0);
    }
}

int main(void){
    unsigned char chess[8];//初始的棋盘
    memset(chess,0,sizeof(unsigned char)*8);//初始棋盘全部为0
    Eight_Queen(chess,0,0);//第一次调用八皇后，我们把行数和列数设为0即可
    //当然你也可以打印一下方案总数
    printf("\n一共有 %d 种摆法\n",count);
    return 0;
}

运行结果：

No.1

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

No.2

0 0 0 0 0 0 0 1