bahuanghou.c

八皇后算法完整程序

#include <stdio.h>
#include <math.h>

int c=0;
/* 输出棋盘*/
void PrintTheChessBoard(int queens[], int n)
{
    int i,j;

    for (i=0;i<n;i++)
    {
        for (j=0;j<queens[i]; j++)
        {
            printf("x");
        }
        printf("O");
        for (j=n; j>queens[i]; j--)
        {
            printf("x");
        };
        putchar('\n');
    }
    printf("this is no.%d answer \nPlease press enter to see the next answer\n",c);
    getch();

}

/* 检查棋盘从第 0 行到第 i 行的布局是否合法*/
int CheckTheChessBoard(int queens[], int i)
{
    int j, k;

    for (j=0; j<=i;j++)
    {
        for (k=0; k<=i;k++)
        {      /* 检查棋盘 列 和 对角线 上元素是否合法*/
            if (j!=k&&(queens[j]==queens[k]||abs(queens[j]-queens[k])==abs(j - k)))
            {
                return 0;
            }
        }
    }

    return 1;
}

void QUEENS(int queens[], int i, int n)
{
    if (i == n)
    {
        c ++;
        PrintTheChessBoard(queens, n);
    }
    else
    {
        int j;

        for (j = 0; j < n; j ++)
        {
            queens[i] = j;
            if (CheckTheChessBoard(queens, i))   /*递归判断*/
            {
                QUEENS(queens, i + 1, n);
            }
        }
    }
}

void main()
{
    int queens[8];
    int size=8;
    QUEENS(queens, 0, size);
    printf("There is %d answers for the %d queen question", c, size);
    getch();
}