皇后问题(栈和队列)

时间: 1ms        内存:128M

描述:

编写一个函数,求解皇后问题:在n*n的方格棋盘上,放置n个皇后,要求每个皇后不同行、不同列、不同左右对角线。

 

要求:

1、皇后的个数由用户输入,其值不能超过20,输出所有的解。

2、采用类似于栈求解迷宫问题的方法。

输入:

输入一个整数n,代表棋盘的大小n*n,

输出:

将计算出的彼此不受攻击的n个皇后的所有放置方案输出,每种方案占一行。

示例输入:

4

示例输出:

2 4 1 3
3 1 4 2

提示:

参考答案(内存最优[0]):

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Max_Size 20
int q[Max_Size+1];
bool place(int q[],int k)
{
    int i;
    for(i=1;i<k;i++)//注意此处不能小于等于,若小于等于则没有结果
    {
        if(q[i]==q[k] || (fabs(k-i) == fabs(q[k]-q[i])))
            return false;
    }
    return true;
}
void print_solution(int q[],int n)
{
    /*int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(j == q[i])
                printf("Q ");
            else
                printf("* ");
        }
        printf("\n");
    }
    printf("\n");*/
    int i;
    for(i=1;i<=n;i++)
    {
        if(i!=n)
            printf("%d ",q[i]);
        else
            printf("%d\n",q[i]);

    }

}
void nQueen(int q[],int n)
{
    int k=1;
    q[k] = 0;
    while(k>0)
    {
        q[k]++;
        while(q[k]<=n && !place(q,k))
            q[k]++;
        if(q[k]<=n)
        {
            if(k==n)
                print_solution(q,n);
            else
            {
                 k++;
                 q[k] = 0;
            }
        }
        else
            k--;
    }
}
int main()
{
    int n;
    //printf("请输入是几皇后:");
    scanf("%d",&n);
    if(n > Max_Size)
    {
       // printf("数字过大!\n");
        exit(0);
    }
    nQueen(q,n);
    return 0;
}

参考答案(时间最优[0]):

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Max_Size 20
int q[Max_Size+1];
bool place(int q[],int k)
{
    int i;
    for(i=1;i<k;i++)//注意此处不能小于等于,若小于等于则没有结果
    {
        if(q[i]==q[k] || (fabs(k-i) == fabs(q[k]-q[i])))
            return false;
    }
    return true;
}
void print_solution(int q[],int n)
{
    /*int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(j == q[i])
                printf("Q ");
            else
                printf("* ");
        }
        printf("\n");
    }
    printf("\n");*/
    int i;
    for(i=1;i<=n;i++)
    {
        if(i!=n)
            printf("%d ",q[i]);
        else
            printf("%d\n",q[i]);

    }

}
void nQueen(int q[],int n)
{
    int k=1;
    q[k] = 0;
    while(k>0)
    {
        q[k]++;
        while(q[k]<=n && !place(q,k))
            q[k]++;
        if(q[k]<=n)
        {
            if(k==n)
                print_solution(q,n);
            else
            {
                 k++;
                 q[k] = 0;
            }
        }
        else
            k--;
    }
}
int main()
{
    int n;
    //printf("请输入是几皇后:");
    scanf("%d",&n);
    if(n > Max_Size)
    {
       // printf("数字过大!\n");
        exit(0);
    }
    nQueen(q,n);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。