#include "stdio.h"
#include "Stdlib.h"
#define max 5
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);
}



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



void main()
{
    Tree T;
    creattree(T);
    traverse(T);
}  vc下通过