eg1：典型汉诺塔和八皇后问题

一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。

#include <stdio.h>
// 将 n 个盘子从 x 借助 y 移动到 z
void move(int n, char x, char y, char z)
{
    if( 1 == n )
    {
        printf("%c-->%c\n", x, z);
    }
    else
    {
        move(n-1, x, z, y);                // 将 n-1 个盘子从 x 借助 z 移到 y 上
        printf("%c-->%c\n", x, z);        // 将 第 n 个盘子从 x 移到 z 上
        move(n-1, y, x, z);                // 将 n-1 个盘子从 y 借助 x 移到 z 上
    }
}
int main()
{
    int n;
    printf("请输入汉诺塔的层数: ");
    scanf("%d", &n);
    printf("移动的步骤如下: \n");
    move(n, 'X', 'Y', 'Z');
    return 0;
}

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

#include <stdio.h>

int count = 0;

int notDanger( int row, int j, int (*chess)[8] )
{
    int i, k, flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;

    // 判断列方向
    for( i=0; i < 8; i++ )
    {
        if( *(*(chess+i)+j) != 0 )
        {
            flag1 = 1;
            break;
        }
    }

    // 判断左上方
    for( i=row, k=j; i>=0 && k>=0; i--, k-- )
    {
        if( *(*(chess+i)+k) != 0 )
        {
            flag2 = 1;
            break;
        }
    }

    // 判断右下方
    for( i=row, k=j; i<8 && k<8; i++, k++ )
    {
        if( *(*(chess+i)+k) != 0 )
        {
            flag3 = 1;
            break;
        }
    }

    // 判断右上方
    for( i=row, k=j; i>=0 && k<8; i--, k++ )
    {
        if( *(*(chess+i)+k) != 0 )
        {
            flag4 = 1;
            break;
        }
    }

    // 判断左下方
    for( i=row, k=j; 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;
    }
}

// 参数row: 表示起始行
// 参数n: 表示列数
// 参数(*chess)[8]: 表示指向棋盘每一行的指针
void EightQueen( int row, int n, int (*chess)[8] )
{
    int chess2[8][8], i, j;

    for( i=0; i < 8; i++ )
    {
        for( j=0; j < 8; j++ )
        {
            chess2[i][j] = chess[i][j];
        }
    }

    if( 8 == row )
    {
        printf("第 %d 种\n", count+1);
        for( i=0; i < 8; i++ )
        {
            for( j=0; j < 8; j++ )
            {
                printf("%d ", *(*(chess2+i)+j));
            }
            printf("\n");
        }
        printf("\n");
        count++;
    }
    else
    {
        for( j=0; j < n; j++ )
        {
            if( notDanger( row, j, chess ) ) // 判断是否危险
            {
                for( i=0; i < 8; i++ )
                {
                    *(*(chess2+row)+i) = 0;
                }

                *(*(chess2+row)+j) = 1;

                EightQueen( row+1, n, chess2 );
            }
        }
    }
}

int main()
{
    int chess[8][8], i, j;

    for( i=0; i < 8; i++ )
    {
        for( j=0; j < 8; j++ )
        {
            chess[i][j] = 0;
        }
    }

    EightQueen( 0, 8, chess );

    printf("总共有 %d 种解决方法!\n\n", count);

    return 0;
}