枚举法---八皇后

灰太狼 2021-11-22 22:02 389阅读 0赞

《c程序设计竞赛教程》例8.7 8皇后问题

问题描述：

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

问题分析：

这个问题是输出“所有”满足条件的放置方案，可以考虑采用枚举法实现。

首先考虑8个皇后在棋盘中的位置，皇后的位置是按棋盘的行列来表示的，行列的取值为1~8.由于皇后直接不能相互攻击，所以在每行和每列上都有且仅有一个皇后。

那么问题的解就可以用一个8位数表示，8位数的第k位为i，表示棋盘上的第k行的第j列放置了一个皇后。

可能解的区间，因为任意两个皇后不允许在同一行或者同一列，所以这个8位数中数字1~8应各出现一次，不能重复，因此，解的区间应为【12345678,87654321】。

约束条件：定义8位数存储结构，每位表示棋盘的一行，一个8位数能保证每行有一个皇后。若每列只有一个皇后，则该8位数的各位数字应互不相同，即1~8在8位数中各出现一次。检查方法可以设置数组f，f（x）为8位数中数字x出现的次数，若f（1）~f（8）均为1，即数字1~8在8位数中各出现一次，则满足条件，否则，不是问题的解。

对条件不能在同一对角线上的判断，设数组g，若8位数中第k个数字为x，则有g\[k\] = x,即第k行，第x列有一个皇后，若两个皇后同处一条45°线上时，

则有：|g\[j\]-g\[k\]| == |j-k|。

代码如下：

#include <stdio.h>
    #include <math.h>
    //检查1-8是否各出现一次，若是，则返回1，否则返回0
    int check_1_8( long m )
    {
        int f[10], i, flag;
        for ( i=0; i<10; i++ )
            f[i] = 0;
        while ( m!=0 )
        {
            f[m%10]++;
            m = m / 10;
        }
        for ( flag=1, i=1; i<=8; i++ )
        {
            if ( f[i]!=1 )
            {
                flag = 0;
                break;
            }
        }
        return flag;
    }
    
    //检测是否在同一对角线上，若不在，返回1，否则返回0；
    int check_dia( long m )
    {
        int g[9], i, j, flag;
        for ( i=8; i>=1; i-- )
        {
            g[i] = m % 10;
            m = m / 10;
        }
    
        flag = 1;
        for ( i=1; i<=7; i++ )
        {
            for ( j=i+1; j<=8; j++ )
            {
                if ( abs(g[j]-g[i]) == j-i)
                {
                    flag = 0;
                    break;
                }
            }
        }
        return flag;
    }
    
    int main()
    {
        int n=0;    //总数
        long a;     
    
        for ( a=12345678; a<=87654321; a+=9 ) //枚举所有可能数
        {
            if ( check_1_8( a ) == 0 )   //检查数字1-8
                continue;
            if ( check_dia( a ) == 0 )    //检测对角线
                continue;
            printf("%ld     ", a);     //得到一个解
            n++;
            if ( n%6==0 )            //每行打印6个
                printf("\n");
        }
        printf("\n%d\n", n);     //输出总的方案数
        return 0;
    }