#include "stdio.h"
#include "Stdlib.h"
#define max 8
struct qipan
{
    int k[max+1];//0号不用,k[i]存放第i行棋子的列位置,k[i]在(1,max)之间
};

typedef struct Node
{
    qipan data;
    struct Node *next[max+1];//存放孩子指针
}*Tree;

void initqipan(qipan &p)//设置空棋盘(把棋盘的数组元素全部赋0)
{
    int i;
    for(i=1;i<=max;i++)
        p.k[i]=0;
}

int count_qipan(qipan p)//返回棋盘已摆放的行数
{
    int z=0,i=1;
    while(p.k[i]!=0&&i<=max){
        z++;
        i++;
    }
    return(z);
}

bool illage(qipan p)//判断棋盘摆放是否合法
{
    int i,j,count;
    count=count_qipan(p);
    for(i=0;i<=count;i++){
        for(j=i+1;j<=count;j++){
            if(p.k[i]==p.k[j]) return(0);//不同行两棋子同列
            if(p.k[j]==p.k[i]+(j-i)||p.k[j]==p.k[i]-(j-i)) return(0);//不同行两棋子在对角线上
        }
    }
    return(1);
}


void print(qipan p)//打印棋盘,用矩阵表示,1表示皇后放的位置,其余位置用0表示
{
    int i,j;
    for(i=1;i<=max;i++){
        for(j=1;j<p.k[i];j++)
            printf("%d  ",0);
        printf("%d  ",1);//打印第i行棋子的位置
        for(j++;j<=max;j++)
            printf("%d  ",0);
        printf("\n");
    }
    printf("\n");
}



void creat(Node * &t,int i,int j)//用递归建立棋盘树(在棋盘结点的第i行上棋子位置为j)
{
    int m,c;
    t->data.k[i]=j;
    for(c=i+1;c<=max;c++)
        t->data.k[c]=0;
    if(i==max){
        for(m=1;m<=max;m++)
            t->next[m]=NULL;
        return;
    }
    if(illage(t->data)){//合法才继续建立
        for(m=1;m<=max;m++){
            t->next[m]=(Node *)malloc(sizeof(Node));
            for(c=1;c<=i;c++)
                t->next[m]->data.k[c]=t->data.k[c];
            for(;c<=max;c++)
                t->next[m]->data.k[c]=0;
            creat(t->next[m],i+1,m);
        }
    }
}


void creattree(Tree &p)//建立树
{
    int i;
    p=(Tree)malloc(sizeof(Node));
    if(!p) exit(1);
    initqipan(p->data);
    for(i=1;i<=max;i++){
        p->next[i]=(Node *)malloc(sizeof(Node));
        creat(p->next[i],1,i);
    }
}

bool isleaf(Node *p)//判断结点是否为叶子
{
    if(count_qipan(p->data)==max) 
        return(1);
    return(0);
}



int traverse(Node *p)//先根便历棋盘,打印所有可能
{
    int i;
    static int num=0;
    if(isleaf(p)){
        if(illage(p->data)){
            print(p->data);
            num++;
        }
    }
    else{
        if(illage(p->data)){
            for(i=1;i<=max;i++)
                traverse(p->next[i]);
        }
    }
    return(num);
}



void main()
{
    Tree T;
    int count;
    creattree(T);
    count=traverse(T);
    printf("共有解法:%d",count);
}

不错不错，我怎么觉得8皇后的解的个数不对。。。

哦，是对的，是92个解。

这是我原来写的，用深搜写的：
/*p118.4*/
/*N Queen Problem*/
#include<stdio.h>
#define MAX 100
int s[MAX];
int n;
int m1[MAX],m2[MAX],m3[MAX];
long count=0;
void output_solution()
{
    int i,j;
    printf("No.%d\n",++count);
    for(i=0;i<n;++i)
    {
    for(j=0;j<s[i];++j)printf(" ");
    printf("Q\n");
    }
    printf("---------------\n");
}
void dfs(int c)
{
    int i;
    if(c==n)
    {
    output_solution();
    }
    else
    {
    for(i=0;i<n;++i)
    {
         if(m1[i]==0&&m2[c+i]==0&&m3[n+i-c-1]==0)
         {
          s[c]=i;
          m1[i]=1;
          m2[c+i]=1;
          m3[n+i-c-1]=1;
          dfs(c+1);
          m1[i]=0;
          m2[c+i]=0;
          m3[n+i-c-1]=0;
         }
    }
    }
}
void main()
{
    scanf("%d",&n);
    dfs(0);
}

你必须把max改为8,我的程序是92个,与答案相同

不知道速度如何，一分钟之内求解几个皇后？？

我用回蒴法用138秒求解16皇后

"四皇后问题＂有多少解？？？？？？？

bool illage(qipan p)//判断棋盘摆放是否合法
{
    int i,j,count;
    count=count_qipan(p);
    for(i=0;i<=count;i++){
        for(j=i+1;j<=count;j++){
            if(p.k[i]==p.k[j]) return(0);//不同行两棋子同列
            if(p.k[j]==p.k[i]+(j-i)||p.k[j]==p.k[i]-(j-i)) return(0);//不同行两棋子在对角线上



我对这段中 if(p.k[i]==p.k[j]) return(0);//不同行两棋子同列  有点疑惑，应该写成  if(k[i]==k[j]) return(0); 是吗？

哦  不好意思看错了  已经定义了一个结构

那这段

void initqipan(qipan &p)//设置空棋盘(把棋盘的数组元素全部赋0)
{
    int i;
    for(i=1;i<=max;i++)
        p.k[i]=0;
}
既然p.k[i]是列位置，怎么能让它等于0呢？

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long sum = 0, upperlim = 1;      // sum用来记录排列总数，upperlim用来作bit mark。
                              // 有多少个皇后，就有多少bit被置1。（从低位到高位）

// 放置顺序是从右边列开始的。
void test(long row, long ld, long rd) // row记录了列的放置信息。bit为1时代表已经放置了皇后。
// ld记录了上一个皇后的左边1列不能放置皇后。
//rd记录了左边1列不能放置皇后。
// 如：上一次放的是第6列: 则
// row  ****  ****  **1*  ****
// ld   ****  ****  *1**  *****
// rd   ****  ****  ***1  ****
{
   if (row != upperlim)
   {
  long pos = upperlim & ~(row | ld | rd); // 将row，ld，rd同时为0的bit提出来。
  while (pos) // if pos = 0，那么皇后没有地方放？？？
  {
 long p = pos & -pos; // 将pos除最低的为1的bit外，所有的位清零后赋值给p
                           // pos不改变。（取得可以放皇后的最右边的列）

 pos -= p;  // 将pos的最低的为1的bit清零。（次右边的列，为循环做准备）
 test(row + p, (ld + p) << 1, (rd + p) >> 1); // row + p将当前列置1，表示放上了皇后
                                             // (ld + p) << 1。设置左边列不能放。
  }
   } else  // row的每一位为1，即所有皇后都放好了。
  sum++;
}

int main(int argc, char *argv[])
{
   time_t tm;
   int n = 16;

   if (argc != 1)
  n = atoi(argv[1]);
   tm = time(0);
   if ((n < 1) || (n > 32))      // long为32位，呵呵，所以这里是<=32
   {
  printf(" 只能计算1-32之间\n");
  exit(-1);
   }
   printf("%d 皇后\n", n);
   upperlim = (upperlim << n) - 1;  //有多少个皇后，就有多少bit被置1。（从低位到高位）

   test(0, 0, 0);
   printf("共有%ld种排列, 计算时间%d秒 \n", sum, (int) (time(0) - tm));
}
速度最快的八皇后算法