Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: [合集]有八皇后算法么？
发信站: 哈工大紫丁香 (2002年07月26日23:31:29 星期五), 站内信件


────────────────────────────────────────
 samuel (孔雀翎)                      于 2002年07月25日15:28:31 星期四 说道:

请帖一下 :)

────────────────────────────────────────
 fobcaesar (温泉企鹅)                 于 2002年07月25日16:01:54 星期四 说道:

这是求n皇后问题的所有解的。
#include "stdio.h"
#define MAXN 20
int n, s;
int col[MAXN+1], a[MAXN+1];
int b[2*MAXN+1], c[2*MAXN+1];
void queen(int k, int n)
{
    int i, j;
    char awn;
    for (i=1; i<=n; i++)
        if (a[i]&&b[k+i]&&c[n+k-i])
        {
            col[k]=i;
            a[i]=b[k+i]=c[n+k-i]=0;
            if (k==n)
            {
                s++;
                printf("\nAnswer: %d\n", s);
                for (j=1; j<=n; j++) printf("(%d,%d)\t", j, col[j]);
                printf("\nPress any key to continue......");
                scanf("%c", &awn);
            }
            else queen(k+1, n);
            a[i]=b[k+i]=c[n+k-i]=1;
        }
}
void main(void)
{
    int i;
    printf("\nEnter n:");
    scanf("%d", &n);
    for (i=0; i<=n; i++) a[i]=b[i]=c[i]=1;
    for (;i<=2*n;i++) b[i]=c[i]=1;
    s=0;
    queen(1, n);
}

────────────────────────────────────────
 samuel (孔雀翎)                      于 2002年07月25日16:09:48 星期四 说道:

thanks，有算法的描述么

────────────────────────────────────────
 fobcaesar (温泉企鹅)                 于 2002年07月25日16:11:38 星期四 说道:

这是我以前写的了，我想想看！
当时不懂怎么写注释，不好意思！

────────────────────────────────────────
 samuel (孔雀翎)                      于 2002年07月25日16:16:14 星期四 说道:

呵呵，要不我自己读吧，读别人写的程序的确是一个头疼的差事，hoho~

────────────────────────────────────────
 allen (夏夜晚风·没有烦恼)           于 2002年07月25日17:46:43 星期四 说道:

 no   读fobcaesar这等大家的作品 如同抒情诗歌一般~~

────────────────────────────────────────
 fobcaesar (温泉企鹅)                 于 2002年07月25日18:12:15 星期四 说道:

ft!
我是菜鸟呀！

────────────────────────────────────────
 samuel (孔雀翎)                      于 2002年07月25日18:13:10 星期四 说道:

你是说我比菜鸟还菜 :(

────────────────────────────────────────
 GREnTOFEL (Crazy Plucking)           于 2002年07月26日08:14:10 星期五 说道:


────────────────────────────────────────
 fobcaesar (温泉企鹅)                 于 2002年07月25日16:01:54 星期四 说道:

这是求n皇后问题的所有解的。
#include "stdio.h"
#define MAXN 20
int n, s; //该程序不用数组的第0个元素
int col[MAXN+1], a[MAXN+1];//col[i]第i行皇后所在的列;a[i]=0
//则表示第i列已经有皇后了
int b[2*MAXN+1], c[2*MAXN+1];//b[i]=0表示x+y=i的直线已经有皇后
//占了;c[i]=0表示x+n-y=i的直线已经有皇后占了
void queen(int k, int n)
{
    int i, j;
    char awn;
    for (i=1; i<=n; i++)
        if (a[i]&&b[k+i]&&c[n+k-i]) //判断新放一个皇后所在列，
//和两条斜线有无其他皇后
        {
            col[k]=i;
            a[i]=b[k+i]=c[n+k-i]=0;
            if (k==n)
            {
                s++;
                printf("\nAnswer: %d\n", s);
                for (j=1; j<=n; j++) printf("(%d,%d)\t", j, col[j]);
                printf("\nPress any key to continue......");
                scanf("%c", &awn);
            }
            else queen(k+1, n); //递归，进行下一个皇后的放置
            a[i]=b[k+i]=c[n+k-i]=1; //回溯，返回上一个皇后
        }
}
void main(void)
{
    int i;
    printf("\nEnter n:");
    scanf("%d", &n);
    for (i=0; i<=n; i++) a[i]=b[i]=c[i]=1;
    for (;i<=2*n;i++) b[i]=c[i]=1;
    s=0;
    queen(1, n);
}
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]

────────────────────────────────────────
 fobcaesar (温泉企鹅)                 于 2002年07月26日17:19:39 星期五 说道:

还是你解释的比较全呀！

────────────────────────────────────────
 fobcaesar (温泉企鹅)                 于 
────────────────────────────────────────