八皇后问题－C语言

柔光的暖阳◎ 2022-08-19 15:06 94阅读 0赞

## 八皇后问题－C语言 ##

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后共有92种解法。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

![这里写图片描述][20160121191820462]

用回溯算法解，代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #define length 8
    
    int count = 0;  // 计数 
    int ms[length][length] = {
       0};
    
    // 判断将皇后放在(a, b)位置上是否合法 
    int isTrue(int a, int b)
    {
        int t;
        // 向上判断 
        for(t=a-1; t>=0; t--)
        {
            if(ms[t][b] == 1)
                return 0;
        }
    
        // 向左判断左
        for(t=b-1; t>=0; t--){
            if(ms[a][t] == 1)
                return 0;
        }
    
        int m, n;
        // 向左上判断 
        for(m=a-1,n=b-1; m>=0&&n>=0; m--,n--)
        {
            if(ms[m][n] == 1)
                return 0;
        }
        // 向右上判 
        for(m=a-1,n=b+1; m>=0&&n<length; m--,n++)
        {
            if(ms[m][n] == 1)
                return 0;
        }
        return 1;
    }
    
    // 打印八皇后 
    void print(){
        count++;
        printf("%d:\n", count);
        int a, b;
        for(a=0; a<length; a++) // 行 
        {
            for(b=0; b<length; b++) // 列 
            {
                if(ms[a][b] == 0)
                {
                    printf("* ");
                }
                else if(ms[a][b] == 1)
                {
                    printf("# ");
                }
            }
            printf("\n");
        }
        printf("\n\n");
    }
    
    // 递归调用 m表示层数 
    void fun(int m){
        if(m == length)  
        {
            print();    // 输出 
            return;     // 递归出口
        }
        int i;
        for(i=0; i<length; i++)
        {
            if(isTrue(m, i))    // 回溯算法 
            {
                ms[m][i] = 1;   // 10表示此位置有皇后
                fun(m+1);       // 递归调用 
                ms[m][i] = 0;   // 0表示此位置无皇后 
            }
        }
    }
    
    int main(void)
    {
        fun(0);
        return EXIT_SUCCESS;
    }

运行结果：  
![这里写图片描述][20160121192809505]

> 运行环境：Dev-C++ 5.11

[20160121191820462]: /images/20220731/cab8c284cc374addb5a4adef53ed93b7.png
[20160121192809505]: /images/20220731/0c6073eda70145d6865e06879f1884cb.png