hrd_calculate.cpp

华容道算法的人工智能解题程序

#include "HRD_Calculate.h"

 hrd_calculate::hrd_calculate()
{
    //申请状态表空间
    first= new s_node[MAX_NODES];
}

hrd_calculate::~hrd_calculate()
{
    delete[]  first;
}

void hrd_calculate::NodeToSNode(node * pnode,s_node* psnode)
{
    int i,j;
	__int8  hgeneral=8,vgeneral=9;
	node * tnode= new node;
	*tnode=*pnode;

	for( i=0;i<5;i++)
       for( j=0;j<4;j++)
       {
           if (tnode->state[i][j]>=GENERAL1 && tnode->state[i][j]<=GENERAL5)
		   {
			   if (j<3)
			       if (tnode->state[i][j] == tnode->state[i][j+1])
				   {
					   tnode->state[i][j]=hgeneral;
					   tnode->state[i][j+1]=hgeneral;
				   }
			   
			   if(i<4)
				   if(tnode->state[i][j] == tnode->state[i+1][j])
				   {
					   tnode->state[i][j]=vgeneral;
					   tnode->state[i+1][j]=vgeneral;
				   }
		   }
	   }
    for( i=0;i<5;i++)
       for( j=0;j<4;j++)
       {
		   if(tnode->state[i][j]==hgeneral) tnode->state[i][j]=HGENERAL;
           if(tnode->state[i][j]==vgeneral) tnode->state[i][j]=VGENERAL;
	   }


	
	psnode->prior=(s_node *)pnode->prior;
    psnode->state=0;
	psnode->ext_state=0;
    for( i=0;i<5;i++)
       for( j=0;j<4;j++)
       {
           psnode->state += pnode->state[i][j];
           psnode->ext_state += tnode->state[i][j];
           if (!(i==4  && j==3))  psnode->state = psnode->state<<3;
           if (!(i==4  && j==3))  psnode->ext_state = psnode->ext_state<<3;
       }
    
    delete tnode;      
    
      
}


void hrd_calculate::SNodeToNode(s_node* psnode,node * pnode)
{
    __int64  temp,s;
    s = psnode->state;
    pnode->prior=(node*)psnode->prior;
    for(int i=4;i>=0;i--)
       for(int j=3;j>=0;j--)
       {   
           temp = s & 0x0000000000000007;
           pnode->state[i][j]= temp ;
           s = s >>3 ;
       }  
}


void hrd_calculate::OutputStep()
{
   node * outfirst,* outlast,*p;

   outfirst=&out[0];
   outlast=outfirst+(depth);
   p=outlast;

   while ( p>=outfirst)
   {
     SNodeToNode(last,p);
     last=last->prior;
     p--;    
   };

    
}


bool hrd_calculate::SearchNode()
{
    int nextnodes;
    node * tnode=new node;
    int total;
    while(true)
    {  
        nextnodes=0;
        table[depth+1]=(unsigned int)(last+1);
        for (  ;search<=current_last ; search++)
        {
            SNodeToNode(search,tnode);
            tnode->prior=(node *)search;
            
            total=SearchOneNode(tnode);
            nextnodes +=total;
            if (total==SUCCESS)
            { 
               delete tnode;
               return true;
            }    
               
        }
        if (nextnodes==0) 
        {
            delete tnode;
            return false;
        }    
        
        depth++;
        current_last=last;
    }
    
                    
}


int hrd_calculate::AddNode(node c)
{
    s_node *p;
    s_node  *snode=new s_node;
    
    if (depth<=3) p=first;
       else  p=(s_node*)table[depth-1];
    NodeToSNode(&c,snode);
    for (;p<=last;p++)
        if (p->ext_state== snode->ext_state) 
        {
            delete snode;
            return ADD_NO_NODE;
        }    
       
    //加入节点   
    last++;
    last->prior=snode->prior;
    last->state=snode->state;
    last->ext_state=snode->ext_state;
    totalnodes++;
    delete snode;
    


    if (c.state[3][1]==CAOCAO && c.state[4][2]==CAOCAO )
       return  SUCCESS;
    else
       return  ADD_ONE_NODE;      
}

void hrd_calculate::InitState(unsigned __int8 state[5][4])
{
    
    //设定初始状态
    node  initnode;
    initnode.prior=0;   //没有上一步
    for(int i=0;i<5;i++)
        for(int j=0;j<4;j++)
           initnode.state[i][j]=state[i][j];

    ////////////////////
    NodeToSNode(&initnode,first);
    ////////////
    last=first;
    search=first;
    current_last=first;
    depth=1;
    totalnodes=1;
    table[0]=0;
    table[depth]=(unsigned int)first;
}    
int hrd_calculate::SearchOneNode(node  *c)
{
 int i,j;
 int next_nodes=0;
 node t;  
    
 for(i=0;i<5;i++)
   for(j=0;j<4;j++)
   {
       if (c->state[i][j]==BLANK)
       {
/////////////////////////////////////////////////////////////////////////////// 
           //直走两步
           if (j<3)
           {
               if (c->state[i][j+1]==BLANK)
               {
                   if (j>0)//左边兵右移两格 
                   {
                       if (c->state[i][j-1] == SOLDIER)
                       {
                           t=*c;  t.prior=c->prior;
                           t.state[i][j-1]=BLANK;
                           t.state[i][j+1]=SOLDIER;
                           switch (AddNode(t))
                           {
                                case SUCCESS:  return  SUCCESS;
                                case ADD_ONE_NODE:  next_nodes++;
                           }    
                       }
                   }
                   if (j<2)//右边兵左移两格 
                   {
                       if (c->state[i][j+2]==SOLDIER)
                       {
                           t=*c;  t.prior=c->prior;
                           t.state[i][j+2]=BLANK;
                           t.state[i][j]=SOLDIER;
                           switch (AddNode(t))
                           {
                                case SUCCESS:  return  SUCCESS;
                                case ADD_ONE_NODE:  next_nodes++;
                           }    
                       }
                   }   
                   if (j==2)//左边将右移两格 
                   {
                       if (c->state[i][j-1]>=GENERAL1 && c->state[i][j-1]<=GENERAL5 && c->state[i][j-1]==c->state[i][j-2])
                       {
                           t=*c;  t.prior=c->prior;
                           t.state[i][j]=c->state[i][j-1];
                           t.state[i][j+1]=c->state[i][j-1];
                           t.state[i][j-1]=BLANK;
                           t.state[i][j-2]=BLANK;
                           switch (AddNode(t))
                           {
                                case SUCCESS:  return  SUCCESS;
                                case ADD_ONE_NODE:  next_nodes++;
                           }    
                       }
                   }
                   if (j==0)//右边将左移两格 
                   {
                       if (c->state[i][j+2]>=GENERAL1 && c->state[i][j+2]<=GENERAL5 && c->state[i][j+2]==c->state[i][j+3])
                       {
                           t=*c;  t.prior=c->prior;
                           t.state[i][j]=c->state[i][j+2];
                           t.state[i][j+1]=c->state[i][j+2];
                           t.state[i][j+2]=BLANK;
                           t.state[i][j+3]=BLANK;
                           switch (AddNode(t))
                           {
                                case SUCCESS:  return  SUCCESS;
                                case ADD_ONE_NODE:  next_nodes++;
                           }    
                       }
                   } 
               }
           }            
           
           if (i<4)
           {
               if (c->state[i+1][j]==BLANK)
               {
                   if (i>0)//上面兵下移两格 
                   {
                       if (c->state[i-1][j]==SOLDIER)
                       {
                           t=*c;  t.prior=c->prior;
                           t.state[i-1][j]=BLANK;
                           t.state[i+1][j]=SOLDIER;
                           switch (AddNode(t))
                           {
                                case SUCCESS:  return  SUCCESS;
                                case ADD_ONE_NODE:  next_nodes++;
                           }    
                       }
                   }
                   if (i<3)//下边兵上移两格 
                   {
                       if (c->state[i+2][j]==SOLDIER)
                       {
                           t=*c;  t.prior=c->prior;
                           t.state[i+2][j]=BLANK;
                           t.state[i][j]=SOLDIER;
                           switch (AddNode(t))
                           {
                                case SUCCESS:  return  SUCCESS;
                                case ADD_ONE_NODE:  next_nodes++;
                           }    
                       }
                   }   
                   if (i>1)//上边将下移两格 
                   {
                       if (c->state[i-1][j]>=GENERAL1 && c->state[i-1][j]<=GENERAL5 && c->state[i-1][j]==c->state[i-2][j])
                       {
                           t=*c;  t.prior=c->prior;
                           t.state[i][j]=c->state[i-1][j];
                           t.state[i+1][j]=c->state[i-1][j];
                           t.state[i-1][j]=BLANK;
                           t.state[i-2][j]=BLANK;
                           switch (AddNode(t))
                           {
                                case SUCCESS:  return  SUCCESS;
                                case ADD_ONE_NODE:  next_nodes++;
                           }    
                       }
                   }
                   if (i<2)//下边将上移两格 
                   {
                       if (c->state[i+2][j]>=GENERAL1 && c->state[i+2][j]<=GENERAL5 && c->state[i+2][j]==c->state[i+3][j])
                       {
                           t=*c;  t.prior=c->prior;
                           t.state[i][j]=c->state[i+2][j];
                           t.state[i+1][j]=c->state[i+2][j];
                           t.state[i+2][j]=BLANK;
                           t.state[i+3][j]=BLANK;
                           switch (AddNode(t))
                           {
                                case SUCCESS:  return  SUCCESS;
                                case ADD_ONE_NODE:  next_nodes++;
                           }    
                       }
                   } 
               }
           }
           
          
                     
                                         
///////////////////////////////////////////////////////////////////////////////
           //走一步           
           // 检查空格左边 
           if (j>0)
           {
              if (c->state[i][j-1]==SOLDIER) //左侧是一兵
              {
                  t=*c;  t.prior=c->prior;
                  t.state[i][j-1]=BLANK;
                  t.state[i][j]=SOLDIER;
                  switch (AddNode(t))
                  {
                      case SUCCESS:  return  SUCCESS;
                      case ADD_ONE_NODE:  next_nodes++;
                  }


              } 
              if (c->state[i][j-1]>=GENERAL1  &&  c->state[i][j-1]<=GENERAL5)
              {
                 if(j>=2)//左侧是一横将 
                 {
                     if(c->state[i][j-2]== c->state[i][j-1])
                     {
                         t=*c;  t.prior=c->prior;
                         t.state[i][j-2]=BLANK;
                         t.state[i][j]=t.state[i][j-1]; 
                         switch (AddNode(t))
                         {
                             case SUCCESS:  return  SUCCESS;
                             case ADD_ONE_NODE:  next_nodes++;
                         } 
                     } 
                 }
                 if(i<=3)//左侧是竖将
                 { 
                     if(c->state[i][j-1]==c->state[i+1][j-1]  && c->state[i+1][j]==BLANK)