#include <graphics.h>                                                      //
#include <stdlib.h>                                                        //
#include <string.h>                                                        //
#include <stdio.h>                                                        //
#include <conio.h>                                                        //
#include <dos.h>                                                          //
#define  n    9                                                            //
//========================================================================
struct Node
 {
  short int  Dim[n];
  short int  Value;
  short int  Index;
  short int  Max;
  Node    *Link[n];
  Node    *Parent;
 };

Node *first,*source;
int  depth=0,buttom=0,select;
long maxobject=0,objectcounter=0,search=0;
int  selected[n]={0},bestindex,step=0;
int  clickdown,clickup,xmouse=320,ymouse=400;
//========================================================================
void OpenMouse()
{
  asm{
    MOV    AX,0x01      // { OPEN MOUSE }
    INT    0x33

    MOV    CX,xmouse
    MOV    DX,ymouse    // { SET DEFULT X,Y FOR MOUSE }
    MOV    AX,0x04
    INT    0x33
  }
}
//****************************************************
void CloseMouse()
{
  asm{
      MOV    AX,0x03
      INT    0x33
      MOV    xmouse,CX
      MOV    ymouse,DX

      MOV    AX,0x02        // { INIT MOUSE }
      INT    0x33
  }
}
//****************************************************
void TestMouse()  //push 1 click
{
  asm{
      MOV    AX,0x03
      INT    0x33
      MOV    clickdown,BX
      MOV    xmouse,CX
      MOV    ymouse,DX
  }
}
//****************************************************
void TestMouse2()  //push 1 click
{
  asm{
      MOV    AX,0x06
      INT    0x33
      MOV    clickup,BX
  }
}
//****************************************************
void MouseLimit()
{
 asm{
    MOV    AX,0X07
    MOV    CX,0
    MOV    DX,630
    INT    0X33

    MOV    AX,0X08
    MOV    CX,0
    MOV    DX,470
    INT    0X33
 }
}
//****************************************************
int Isinbox(int x1,int y1,int x2,int y2)
{
  if ( (xmouse>x1)&&(xmouse<x2) &&(ymouse>y1)&&(ymouse<y2))
    return 1;
  else return 0;
}
//****************************************************
void DetectVga(void)
{
  int gdriver = DETECT, gmode, errorcode;
  int left, top, right, bottom;
  initgraph(&gdriver, &gmode, "");
  errorcode = graphresult();
  if (errorcode != grOk)  /* an error occurred */
  {
    printf("Graphics error: %s\n", grapherrormsg(errorcode));
    printf("Press any key to halt:");
    getch();
    exit(1); /* terminate with an error code */
  }
  delay(1000);
}
//****************************************************
void CLS(void)
{
  setfillstyle(1,0);
  bar(0,0,639,479);
  setcolor(9);
  rectangle(258,178,382,302);
  rectangle(260,180,380,300);
  line(260,220,380,220);
  line(260,260,380,260);
  line(300,180,300,300);
  line(340,180,340,300);

  setcolor(14);  outtextxy(10,10,"Click on Box & try to win...");
  setcolor(1);  outtextxy(570,10,"jampour");
}
//****************************************************
void tic(int a)
{
  int x,y,z;
  z=a/3;
  a=a%3;
  x=280+ a*40;
  y=200+ z*40;
  CloseMouse();
  setcolor(12);
  line(x-7,y-7,x+7,y+7);
  line(x-7,y+7,x+7,y-7);
  OpenMouse();
}
//****************************************************
void tac(int a)
{
  int x,y,z;
  z=a/3;
  a=a%3;
  x=280+ a*40;
  y=200+ z*40;
  CloseMouse();
  setcolor(14);
  circle(x,y,7);
  OpenMouse();
}
//****************************************************
int Status(Node *obj)
{
 if(((obj->Dim[0]==-1)&&(obj->Dim[1]==-1)&&(obj->Dim[2]==-1) )
 ||( (obj->Dim[3]==-1)&&(obj->Dim[4]==-1)&&(obj->Dim[5]==-1) )
 ||( (obj->Dim[6]==-1)&&(obj->Dim[7]==-1)&&(obj->Dim[8]==-1) )
 ||( (obj->Dim[0]==-1)&&(obj->Dim[3]==-1)&&(obj->Dim[6]==-1) )
 ||( (obj->Dim[1]==-1)&&(obj->Dim[4]==-1)&&(obj->Dim[7]==-1) )
 ||( (obj->Dim[2]==-1)&&(obj->Dim[5]==-1)&&(obj->Dim[8]==-1) )
 ||( (obj->Dim[0]==-1)&&(obj->Dim[4]==-1)&&(obj->Dim[8]==-1) )
 ||( (obj->Dim[2]==-1)&&(obj->Dim[4]==-1)&&(obj->Dim[6]==-1)))
 return -1;
 else
 if(((obj->Dim[0]==-2)&&(obj->Dim[1]==-2)&&(obj->Dim[2]==-2) )
 ||( (obj->Dim[3]==-2)&&(obj->Dim[4]==-2)&&(obj->Dim[5]==-2) )
 ||( (obj->Dim[6]==-2)&&(obj->Dim[7]==-2)&&(obj->Dim[8]==-2) )
 ||( (obj->Dim[0]==-2)&&(obj->Dim[3]==-2)&&(obj->Dim[6]==-2) )
 ||( (obj->Dim[1]==-2)&&(obj->Dim[4]==-2)&&(obj->Dim[7]==-2) )
 ||( (obj->Dim[2]==-2)&&(obj->Dim[5]==-2)&&(obj->Dim[8]==-2) )
 ||( (obj->Dim[0]==-2)&&(obj->Dim[4]==-2)&&(obj->Dim[8]==-2) )
 ||( (obj->Dim[2]==-2)&&(obj->Dim[4]==-2)&&(obj->Dim[6]==-2)))
 return 1;
 else
 return 0;
}
//****************************************************
void Verify(Node  *obj,int depth)
{ int i,max=-128,min=128;
  for(i=0;i<n;i++)
  { Node  *child=obj->Link[i];
    if( (obj->Link[i]!=NULL) && (depth%2==1) && (child->Value > max) )
      {
    obj->Value=child->Value;
    max=child->Value;
    obj->Index=i;
      }
    if( (obj->Link[i]!=NULL) && (depth%2==0) && (child->Value < min) )
      {
    obj->Value=child->Value;
    min=child->Value;
    obj->Index=i;
      }
  }
  for(i=0;i<n;i++)        //delete used memory
  { Node  *child=obj->Link[i];
    if(obj->Link[i]!=NULL)
    {
      obj->Link[i]=NULL;
      delete child;
      objectcounter--;
    }
  }
}
//****************************************************
void Test(Node  *obj,int depth)
{
 if( ( (obj->Dim[0]==-1)&&(obj->Dim[1]==-1)&&(obj->Dim[2]==-1) )
 ||( (obj->Dim[3]==-1)&&(obj->Dim[4]==-1)&&(obj->Dim[5]==-1) )
 ||( (obj->Dim[6]==-1)&&(obj->Dim[7]==-1)&&(obj->Dim[8]==-1) )
 ||( (obj->Dim[0]==-1)&&(obj->Dim[3]==-1)&&(obj->Dim[6]==-1) )
 ||( (obj->Dim[1]==-1)&&(obj->Dim[4]==-1)&&(obj->Dim[7]==-1) )
 ||( (obj->Dim[2]==-1)&&(obj->Dim[5]==-1)&&(obj->Dim[8]==-1) )
 ||( (obj->Dim[0]==-1)&&(obj->Dim[4]==-1)&&(obj->Dim[8]==-1) )
 ||( (obj->Dim[2]==-1)&&(obj->Dim[4]==-1)&&(obj->Dim[6]==-1) ) )
 { obj->Value=-1*(n+1-depth);
  for(int i=0;i<n;i++)
      obj->Link[i]=NULL;
 }
 else
 if( ( (obj->Dim[0]==-2)&&(obj->Dim[1]==-2)&&(obj->Dim[2]==-2) )
 ||( (obj->Dim[3]==-2)&&(obj->Dim[4]==-2)&&(obj->Dim[5]==-2) )
 ||( (obj->Dim[6]==-2)&&(obj->Dim[7]==-2)&&(obj->Dim[8]==-2) )
 ||( (obj->Dim[0]==-2)&&(obj->Dim[3]==-2)&&(obj->Dim[6]==-2) )
 ||( (obj->Dim[1]==-2)&&(obj->Dim[4]==-2)&&(obj->Dim[7]==-2) )
 ||( (obj->Dim[2]==-2)&&(obj->Dim[5]==-2)&&(obj->Dim[8]==-2) )
 ||( (obj->Dim[0]==-2)&&(obj->Dim[4]==-2)&&(obj->Dim[8]==-2) )
 ||( (obj->Dim[2]==-2)&&(obj->Dim[4]==-2)&&(obj->Dim[6]==-2) ) )
 { obj->Value=1*(n+1-depth);
  for(int i=0;i<n;i++)
      obj->Link[i]=NULL;
 }
 else obj->Value=0;
}
//****************************************************
void DLS(Node *point,int depth)
{
 int i,j,exitcondition,game,next=0;
 Node    *object;
 search++; depth++;

 if (maxobject < objectcounter) maxobject=objectcounter;
 Test(point,depth);

  for(i=0;i<n+1;i++)
  {
    if (i==n)
      Verify(point,depth);
    else
    if(point->Link[i]!=NULL)
    {
    if (!(object=new Node))
    { printf("\n  Erorr!  memory is full.");  getch(); exit (1);}
    objectcounter++;
    for(j=0;j<n;j++)
    {
    object->Dim[j]=point->Dim[j];
    object->Link[j]=point->Link[j];
    }
    object->Value=-96;    object->Max=-96;
    point->Link[i]=object;    object->Parent=point;

    if( (depth%2)==0 ) buttom=-1; else buttom=-2;

    for(j=next;j<n;j++)
      if(!object->Dim[j])
      {
        object->Dim[j]=buttom;
        object->Link[j]= NULL;
        next=j+1;        break;
      }
      DLS(point->Link[i],depth);
    }//end if
  }//end for
}
//****************************************************
void UserSelection()
{
 if( (Isinbox(260,180,300,220)) && (!selected[0]) )  // 0
    { tic(0); selected[0]=1; select=1;
      first->Dim[0]=-1;  first->Link[0]=NULL; depth++;}
 else
 if( (Isinbox(300,180,340,220)) && (!selected[1]) )  //1
    { tic(1); selected[1]=1; select=1;
      first->Dim[1]=-1;  first->Link[1]=NULL; depth++; }
 else
 if( (Isinbox(340,180,380,220)) && (!selected[2]) )  //2
    { tic(2); selected[2]=1; select=1;
      first->Dim[2]=-1;  first->Link[2]=NULL; depth++; }
 else
 if( (Isinbox(260,220,300,260)) && (!selected[3]) )  //3
    { tic(3); selected[3]=1; select=1;
      first->Dim[3]=-1;  first->Link[3]=NULL; depth++; }
 else
 if( (Isinbox(300,220,340,260)) && (!selected[4]) )  //4
    { tic(4); selected[4]=1; select=1;
      first->Dim[4]=-1;  first->Link[4]=NULL; depth++; }
 else
 if( (Isinbox(340,220,380,260)) && (!selected[5]) )  //5
    { tic(5); selected[5]=1; select=1;
      first->Dim[5]=-1;  first->Link[5]=NULL; depth++; }
 else
 if( (Isinbox(260,260,300,300)) && (!selected[6]) )  //6
    { tic(6); selected[6]=1; select=1;
      first->Dim[6]=-1;  first->Link[6]=NULL; depth++; }
 else
 if( (Isinbox(300,260,340,300)) && (!selected[7]) )  //7
    { tic(7); selected[7]=1; select=1;
      first->Dim[7]=-1;  first->Link[7]=NULL; depth++; }
 else
 if( (Isinbox(340,260,380,300)) && (!selected[8]) )  //8
    { tic(8); selected[8]=1; select=1;
      first->Dim[8]=-1;  first->Link[8]=NULL; depth++; }
}
//****************************************************
void ComputerSelection(int depth)
{
 source=new Node;
 for(int i=0;i<n;i++)
 {
  source->Dim[i]=first->Dim[i];
  source->Link[i]=first->Link[i];
 }
 bestindex=0;
 DLS(source,depth);        bestindex=source->Index;
 tac(bestindex);        selected[bestindex]=1;

 source->Dim[bestindex]=-2;      source->Link[bestindex]=NULL;
 first->Dim[bestindex]=-2;      first->Link[bestindex]=NULL;
 gotoxy(1,1); printf(".: Maximum search = %ld :.        ",search);
 gotoxy(1,2); printf(".: Memory used = %ld Byte :.      ",maxobject*(4*n+8));
 gotoxy(1,3); printf(".: objcet used = %ld :.          ",maxobject);
 maxobject=0; search=0;
}
//****************************************************
void main(void)
{
  DetectVga();  CLS();
  MouseLimit();  OpenMouse();

  first=new Node;
  for(int i=0;i<9;i++)
  {
    first->Dim[i]=0;
    first->Link[i]=first;  //because should Not equal than NULL
  }

  int game;  int depth=0;  step=depth/2;
  do
  {
    select=0;    TestMouse2();          //for get click up of mouse
    if((Isinbox(260,180,380,300))&&(clickup))
    {
      UserSelection();
      step++;
    }

    game=Status(source);
    if( (step>n/2)||(game) )
      break;

    if( select)
    {
      ComputerSelection(depth);
      clickdown=0; depth+=2;
    }
    game=Status(source);
    if(game) break;

    TestMouse();            //for get click down of mouse
 }while( (!Isinbox(550,435,630,470)) || (!clickdown) );

 setcolor(14);      rectangle(10,400,200,470);

 if(game==1)
 {  setcolor(4);  outtextxy(35,420,"<<< You Lose ! >>>"); }
 else
 if(game==-1)
 {  setcolor(10); outtextxy(35,420,"<<<  You Win  >>>"); }
 else
 {  setcolor(15); outtextxy(35,420,"<<< Game Equal >>>"); }

 setcolor(12);    outtextxy(20,450,"Click here to exit.");
 do
  TestMouse();        //for get click down of mouse
 while( (!Isinbox(10,400,200,470)) || (!clickdown) );

 CloseMouse();
 closegraph();
}