#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <dos.h>
#include <graphics.h>

void *buff1,*buff2;

typedef struct
{
int A[21],B[21],C[21],Y[8];
}Queen;

void SetQueen(Queen *Q)                       /* 初始化 */
{
int i;
for(i=0;i<21;i++)
{
  Q->A[i]=0;
  Q->B[i]=0;
  Q->C[i]=0;
}
for(i=0; i<8; i++)
  Q->Y[i]=-1;
}

void QueenPic(void)                 /* 画皇后图象，然后存储到缓冲区 */
{
int size,
polypoints1[10]={9,1,11,1,20,20,1,20,9,1},
polypoints2[10]={29,1,31,1,40,20,21,20,29,1};
setfillstyle(SOLID_FILL,GREEN);           /* 画绿色棋格 */
setcolor(GREEN);
rectangle(1,1,20,20);
floodfill(10,10,GREEN);
setfillstyle(SOLID_FILL,WHITE);          /* 画白色棋格 */
setcolor(WHITE);
rectangle(21,1,40,20);
floodfill(30,10,WHITE);
setfillstyle(SOLID_FILL,RED);
setcolor(YELLOW);
drawpoly(5,polypoints1);
drawpoly(5,polypoints2);
floodfill(10,10,YELLOW);
floodfill(30,10,YELLOW);
size=imagesize(1,1,20,20);          /* 计算缓冲区大小，然后存储 */
buff1=(void *)malloc(size);
buff2=(void *)malloc(size);
getimage(1,1,20,20,buff1);
getimage(21,1,40,20,buff2);
cleardevice();
}

void Checker(void)     /* 画棋盘函数 */
{
int i,k;
for(k=0;k<8;k++)
  for(i=0;i<8;i++)
   if(k%2==0&&i%2==0||k%2!=0&&i%2!=0)
    {
     setfillstyle(SOLID_FILL,GREEN);
     setcolor(GREEN);
     rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);
     floodfill(i*20+10,20+k*20+10,GREEN);
    }
    else
    {
     setfillstyle(SOLID_FILL,WHITE);
     setcolor(WHITE);
     rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);
     floodfill(i*20+10,20+k*20+10,WHITE);
    }
}

void PrintQueen(Queen *t)      /* 图形输出函数 */
{
int k;
char str[20];
static total=0;
total++;
setviewport(240,80,400,260,1);    /* 设置窗口 */
sprintf(str,"NO.%d",total);
setcolor(BROWN);
settextstyle(0,0,1);
outtextxy(0,0,str);
Checker();
for(k=0;k<8;k++)
  if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)
   putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);
  else
   putimage((t->Y[k])*20,20+k*20,buff2,COPY_PUT);
getch();
clearviewport();
}

void QueenRe(Queen *Q, int y)               /* 八皇后的递归算法 */
{
int x;
if(y>7)
  return;
for(x=0;x<8;x++)
  if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])  /* 下一棵要遍历的子树由状态数确定 */
  {
   Q->Y[y]=x;
   Q->A[x+7]=1;
   Q->B[x+y+7]=1;
   Q->C[x-y+7]=1;
   if(y==7)
    PrintQueen(Q);
   QueenRe(Q,y+1);                       /* 进入下一层递归 */
   Q->A[x+7]=0;
   Q->B[x+y+7]=0;
   Q->C[x-y+7]=0;
  }
}

void main(void)
{
Queen Q;
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode,"C://Win-TC");
SetQueen(&Q);
setcolor(YELLOW);
QueenPic();
cleardevice();
setcolor(BROWN);
settextstyle(0,0,2);
outtextxy(160,0,"Eight Queen Problem.");
settextstyle(0,0,1);
outtextxy(120,30,"produced by George Lee 23:00 Dec.7th,1999");
QueenRe(&Q,0);
getch();
closegraph();
}