数据结构之线性表-递归解决八皇后问题-学习笔记-41

引入

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

简单思想

• 将大问题化简称小问题
• 8X8二维数组的任意一个位置
• 一行一行来检查，符合要求的就把0改成1
• 要求就是一列不能有1，一行不能有1，斜着不能有1
• 一行一行的递归是一部分、检查行列斜有没有棋子1是一部分
• 递归下去，然后回溯回来，就能将所有的情况列出来了。

#include <stdio.h>
int count = 0;

int notdanger(int row , int col ,int (*chess)[8]){
    int k , i , flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;
    //判断列
    for( i = 0; i<8;i++){
        if(*(*(chess+i)+col)!=0){
            flag1=1;
            break;
        }
    }
    
    //判断左上*
    for(i=row , k=col ; i>=0 && k>=0 ; i-- , k--){
        if(*(*(chess+i)+k)!=0){
            flag2=1;
            break;
        }
    }
    
    //判断右下*
    for(i=row , k=col ; i<8 && k<8 ; i++ , k++){
        if(*(*(chess+i)+k)!=0){
            flag3=1;
            break;
        }
    }
    
    
    //判断右上*
    for(i=row , k=col ; i>=0 && k<8 ; i-- , k++){
        if(*(*(chess+i)+k)!=0){
            flag4=1;
            break;
        }
    }
    
    //判断左下
    for(i=row , k=col ; i<8 && k>=0 ; i++ , k--){
        if(*(*(chess+i)+k)!=0){
            flag5=1;
            break;
        }
    }
    
    if(flag1 ||  flag2 ||  flag3 ||  flag4 ||  flag5 ){
        return 0;
    }else{
        return 1;
    }
    
    
}

void queen ( int row , int col , int (*chess)[8]){
    //接收棋盘
    int queen_chess[8][8],i , j;
    for(i=0;i<8;i++){
        for(j=0;j<8;j++){
            queen_chess[i][j]=chess[i][j];
        }
    }
    //递归开始
    if(row==8){
        printf("第%d种结果：\n",count);
        for(i=0;i<8;i++){
            for(j=0;j<8;j++){
                printf("%d",*(*(queen_chess+i)+j));
            }
            printf("\n");
        }
        printf("\n");
        count++;
    }else{
        //判断是否有危险
        //没有问题就继续向下
        for(j=0;j<col;j++){
            //判断是否有问题
            if( notdanger(row , j , chess)){
                for(i=0;i<8;i++){
                    *(*(queen_chess+row)+i)=0;  // i 的是危险的
                }
                *(*(queen_chess+row)+j)=1;  //j 是 notdanger 判断过的
                queen(row+1, col , queen_chess);  //递归继续测试下一行
            }
            
        }
        
    }
}
int main(){
    int chess[8][8],i,j;
    for(i=0;i<8;i++){
        for(j=0;j<8;j++){
            chess[i][j]=0;
        }
    }
    queen(0,8,chess);
    printf("总共有%d种解决方法",count);
}

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。