八皇后问题

西西里 — Fri, 14 Dec 2007 23:59:00 GMT

人工智能的老师让我们做八皇后问题的算法，所以就整理了网上的两种算法，一个是用C语言做的，一个用的C++，全部都在VC++6.0上能过：

C语言版：

#include
#define NUM 8 /*定义数组的大小*/
int a[NUM+1];
void main()
{
    int i,k,flag,not_finish=1,count=0;
    i=1; /*正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素*/
    a[1]=1; /*为数组的第一个元素赋初值*/
    printf("The possible configuration of 8 queens are:\n");
    while(not_finish) /*not_finish=1:处理尚未结束*/
    {
        while(not_finish&&i<=NUM) /*处理尚未结束且还没处理到第NUM个元素*/
        {
            for(flag=1,k=1;flag&&k                if(a[k]==a[i])flag=0;
                for(k=1;flag&&k                    if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i))) flag=0;
                    if(!flag) /*若存在矛盾不满足要求，需要重新设置第i个元素*/
                    {
                        if(a[i]==a[i-1]) /*若a[i]的值已经经过一圈追上a[i-1]的值*/
                        {
                            i--; /*退回一步，重新试探处理前一个元素*/
                            if(i>1&&a[i]==NUM)
                                a[i]=1; /*当a[i]为NUM时将a[i]的值置1*/
                            else if(i==1&&a[i]==NUM)
                                not_finish=0; /*当第一位的值达到NUM时结束*/
                            else a[i]++; /*将a[i]的值取下一个值*/
                        }
                        else if(a[i]==NUM) a[i]=1;
                        else a[i]++; /*将a[i]的值取下一个值*/
                    }
                    else if(++i<=NUM)
                        if(a[i-1]==NUM) a[i]=1; /*若前一个元素的值为NUM则a[i]=1*/
                        else a[i]=a[i-1]+1; /*否则元素的值为前一个元素的下一个值*/
        }
        if(not_finish)
        {
            ++count;
            printf((count-1)%3?" \n[%2d]: ":" \n[%2d]: ",count);
            for(k=1;k<=NUM;k++) /*输出结果*/
                printf(" %d",a[k]);
            if(a[NUM-1]            else a[NUM-1]=1;
            i=NUM-1; /*开始寻找下一个足条件的解*/
        }
    }

    printf("\n");
}

///////////////////////////////////////////////////////////////////////////////////////////////////////
C++版：

#include
#include
#include

using namespace std;

int *position; //放置的位置
int queen; //皇后数目
int count; //第N种可能性

//判断第n行是否放置皇后
bool SignPoint(int n)
{
    for (int i=0;i    {
        if (*(position+i) == *(position+n)) //该列已经放置过皇后了
            return false;
        if (abs(*(position+i) - *(position+n)) == n-i) //对角线已经放置过了
            return false;
    }
    return true;
}

//设置皇后
void SetQueen(int n=0)
{
    if (queen==n)
    {
        //该处可以改成自己想要的显示方式
        printf("NO.%d: ",++count);
        printf("\n");
        for (int i=0;i        {
            for (int j=0;j            {
                if (j == position[i])
                {
                    printf("* ");
                }
                else
                {
                    printf("0 ");
                }
            }
            printf("\n");
        }
        printf("\n");
        return;
    }
    else
    {
        for (int i=0;i        {
            position[n] = i;

            if(SignPoint(n))//如果该位置放置皇后正确的话,则到下一行
            {
                SetQueen(n+1);
            }
        }
    }
}

void main()
{
    cout<<"请输入皇后的总数:"<    cin>>queen;
    position = (int*)malloc(sizeof(int));
    SetQueen();
    cout<<"摆放完毕"<    cin.get();
    cin.get();
}

西西里 2007-12-15 07:59 发表评论

IT博客-如果·喜欢

八皇后问题