01.cpp

这是一个九宫图游戏,可自动生成也可手动生成初始状态,有过程演示!

//#ifndef EIGHTNUM_H_
//#define EIGHTNUM_H_

#include <iostream>
#include <ctime>
#include <string>
#include <windows.h>
using namespace std;


const int MAX = 9;
extern char target[MAX +1] ;
extern char joinArr[362880] ;


//节点定义.
class Qnode 
{
public:
    char *data;
    Qnode *next;
    int parentnum;
    Qnode();
    Qnode( const char * );
    Qnode( const Qnode & );
    Qnode& operator=( const Qnode & );
    bool operator==( Qnode & );
    bool IsJoined();
    bool HaveSolution();
    bool Goal()const;
    //friend ostream &operator<<( ostream &, char* );
};


//以节点组成的对列.
class Queen
{
public:
    int length;
    Qnode* head;
    Qnode* tail;
    Queen();
    Queen( const Queen &);
    Queen& operator=( const Queen &);
    bool Empty()const;
    void Back_insert( Qnode& );
    void Front_delete();
    Qnode GetFirNode();
};

/**//*全局函数*/

extern Qnode qq[362880] ;            //所有节点的状态数组.
bool Move(char*, int );                //把某个状态进行4个方向的移动.
void Calculate( char* p );            //本题的关键函数.用于实现八数码的扩展数组.
int Fac(int n);                        //递归函数
int SmallerNum(char *p, int index);
bool IsJoined(char *oldState);        //实现判断一个状态是否已经加入OPEN表
void GetFinalpath(Qnode *, int);    //获得最优路径

//#endif



char target[MAX +1] = "123804765" ;  // 自定义的目标状态.
char joinArr[362880] ={0};     // 判断所有状态的数组.
Qnode qq[362880];      //节点的数组,存放所有已经扩展的不重复的节点.

/******** 节点类的实现函数  *********/

Qnode::Qnode()
{
 parentnum = -1;
 next = NULL;
 data = new char[MAX];
 data[MAX] = '\0';
}

Qnode::Qnode( const char * p)
{
 parentnum = -1;
 this->next = NULL;
 data = new char[MAX];
 strcpy( data,p);
}

/*拷贝构造函数*/
Qnode::Qnode( const Qnode& node )
{
 parentnum = node.parentnum;
 data = new char[MAX];
 strcpy( data,node.data);
 this->next = NULL;
}

/*赋值重载*/
Qnode& Qnode::operator=( const Qnode & node)
{ 
 parentnum = node.parentnum;
 data = new char[MAX];
 strcpy( data,node.data);
 this->next = NULL;
 return *this;

}

/*判断一个状态是否为目标状态*/
bool Qnode::Goal()const
{
 if (strcmp(data, target)!=0)
  return false;
 else
  return true;
}

/*判断一个状态和另外一个状态是否相同*/
bool Qnode::operator ==( Qnode & node )
{
 for( int i = 0 ;i < MAX; i++ )
 {
  if( node.data[i] != this->data[i])
   return false;
 }
 return true;
}
/****************************************************

利用奇偶性判断所给出的初始状态有无解.

判别方法是：
以数组为一维的举例子.
将八数码的一个结点表示成一个数组a[9]，空格用0表示，设临时函数p(x)定义为：x数所在位置前面的数比x小的数的个数，
其中0空格不算在之内，那设目标状态为b[9]，那r=sigma(p(x)) sigma()表示取所有的x:1-8并求和，
那对于初始状态a[9]，t=sigma(p(x))，如果r和t同为奇数或者同为偶数，那么该状态有解，否则无解。

考虑到四种移动方法对sigma(p(x))的影响，左移和右移是不会影响它的值的，
更不会影响奇偶性，如果是上移或者下移就会影响：
上移:一次上移会使一个元素向前跳两个数字的位置，设这两个数字为a1,a2，
不妨设a1<a2，移的这个数字设为a0，那无非只有以下三次情况：
1，a0<a1<a2，考虑它们三者的p(x)值，p(a0)不变，p(a1)++，p(a2)++，总体增加了2
2，a1<a0<a2，p(a0)--,p(a1)不变,p(a2)++，总体不变
3，a1<a2<a0，p(a0)-=2,p(a1),p(a2)不变，总体减小了2

综合起来的结论就是不会影响sigma(p(x))的奇偶性。
*****************************************************/

bool Qnode::HaveSolution( )
{
 int i,j,sum2 = 0,sum1 = 0;
 for( i = 0; i< MAX; i++ )
  for( j = 0; j < i; j++ )
  {
   if(( this->data[i] - 48) * (this->data[j] - 48))
   {
    if( this->data[j] < this->data[i] )
    sum1++;
   }
  }
 for( i = 0; i< MAX; i++ )
  for( j = 0; j < i; j++ )
  {
   if( (target[i] - 48) * ( target[j] - 48 ) )
   {
    if( target[j] < target[i] )
    sum2++;
   }
  }

 if( sum1 % 2 == sum2 % 2 )
  return true;
  return false;
}

/*打印某个节点,用操作符重载*/
/*ostream &operator<<( ostream & os, char *p)
{
 int i,cnt = 0;
 for( i = 0; i != MAX; i++)
 {
  os << p[i] << " ";
  cnt++;
  if(cnt == 3)
  {
   os <<endl;
   cnt = 0;
  }
 }
 os << endl;
 return os;
}*/

/**********队列类的实现***********/


Queen ::Queen()
{
 length = 0;
 head = tail = NULL;
}

Queen::Queen( const Queen & queen )
{
 length = queen.length;
 Qnode *head = new Qnode;
 Qnode *tail = new Qnode;
 head = queen.head;
 tail = queen.tail;
 Qnode temp;
 while( !(temp.operator ==( *tail ) ) )
 {
  Qnode *newptr = new Qnode;
 }

}

Queen & Queen::operator=( const Queen & queen )
{
 length = queen.length;
 Qnode *head = new Qnode;
 Qnode *tail = new Qnode;
 head = queen.head;
 tail = queen.tail;
 Qnode temp;
 while( !(temp.operator ==( *tail ) ) )
 {
  Qnode *newptr = new Qnode;
 }
 return *this;
}

/*尾部插入*/
void Queen::Back_insert( Qnode& Qnode )
{
 if(head == NULL)
 {
  Qnode.next = NULL;
  head = tail = &Qnode;
  tail->next =  NULL;
  length++;
 }
 else
 {
  Qnode.next = NULL;
  tail->next = &Qnode;
  tail = &Qnode;
  length++;
 }
}

/*首删除*/
void Queen::Front_delete()
{
 if(!Empty())
 {
  Qnode * temp;
  temp = head;
  head = head->next;
  length--;
  //delete temp;????
 }
}

Qnode Queen::GetFirNode()
{
 if(!Empty())
 {
  return *(this->head) ;
 }
 else
  return NULL;
}

/* 判断队列是否为空.*/
bool Queen::Empty()const
{
 if( length == 0 )
  return true;
 return false;
}

/*打印节点*/
/*ostream &operator<<( ostream & os, const Qnode & Qnode )
{
 for( int i = 0; i< MAX; i++ )
  os << Qnode.data[i] << " ";
 return os;
}*/

/******其他的小函数.********/

/**********************************************

通过求出p数组中0的位置送给x,y,然后根据给定的m(移动方向)
0上,1下,2左,3右.然后综合两个变量,来判断是否可行.

**********************************************/

bool Move(char* p, int m)
{
 int x = 0,y = 0;
 char temp;
 for( int i = 0; i< MAX; i++)
  if( p[i] == '0' )
  {
   x = i / 3;
   y = i % 3;
  }
 if     ( m == 0 && x == 0 ) return false;
 else if( m == 1 && x == 2 ) return false;
 else if( m == 2 && y == 0 ) return false;
 else if( m == 3 && y == 2 ) return false;
 else    
 {

  switch(m)
  {
   case 0: //上移一步。
     temp = p[(x-1) * 3 + y];
     p[ x * 3 + y ] = temp;
     p[ (x-1) * 3 + y ] = '0';
     break;
    
   case 1://下移一步
     temp = p[(x+1) * 3 + y];
     p[ x * 3 + y ] = temp;
     p[ (x+1) * 3 + y ] = '0';
     break;
   
   case 2://左移一步
     temp = p[x * 3 + y - 1];
     p[ x * 3 + y ] = temp;
     p[ x * 3 + y - 1] = '0';
     break;
    
   case 3://右移一步
   
     temp = p[x * 3 + y + 1];
     p[ x * 3 + y ] = temp;
     p[ x * 3 + y + 1] = '0';
     break;
    
  }
  return true;
 }
  
}

bool IsJoined(char *oldState)
{
 int i;
 int index = 0;
 int base = MAX;
 char newState[MAX+1];
 strcpy(newState, oldState);
 for(i=0; newState[i]!='0';i++);
 newState[i] = '9';
 index += (newState[0]- '0' -1) * Fac(base-1);
 for (i=1; i!=base; i++)
 {
  index += Fac(base-1-i) * (newState[i] - '0' - 1 - SmallerNum(newState, i));
 }
 //如果newState已经加入则返回真
 //cout << index << endl;
 if (joinArr[index] == '1')
 {
  return true;
 }
 //否则将对应状态改为1,表示将当前状态加入
 joinArr[index] = '1';
 return false;
}

int Fac(int n)
{
 if (n==0 || n==1)
 {
  return 1;
 }
 return n * Fac(n-1);
}

int SmallerNum(char *p,int index)
{  
 int sum = 0; 
 for (int i=0; i!=index; i++)
 {
  if (p[i] < p[index])
  {
   sum++;
  }
 }
 return sum;
}

void GetFinalpath(Qnode *scanArr,int lastIndex)
{
 int index = 0;
 int wrap = 0;
 int parentID = scanArr[lastIndex].parentnum;
 string path[50];
 path[index++] = string(scanArr[lastIndex].data);
 while (scanArr[parentID].parentnum != -1)
 {
  path[index++] = string(scanArr[parentID].data);
  parentID = scanArr[parentID].parentnum;
 }
 path[index] = string(scanArr[0].data);
 int i = 0,j = index;
 string temp;
 while( i < j )
 {
  temp = path[i];
  path[i] = path[j];
  path[j] = temp;
  i++;j--;
 }
 int count = index + 1;
 int group = count / 8;
 int row = group * 3;
 int temp1 = 0;

 /***************打印分组类似于下面的图形**************************************

 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

 *************************************************************/

 ////////先打印每行都是满8个的/////////
 for(  i = 0; i != group ; i++ )
 {
  //分成行数,在组的基础上每组分三行.
  for( int j = 0; j != 3; j++ )
  {
   //每行分成八部分.
   for( int k = 0; k != 8; k++ )
   {
    int r = 0;
    cout << path[i*8+k][3*j+r] << " ";
    r++;
    cout << path[i*8+k][3*j+r] << " ";
    r++;
    cout << path[i*8+k][3*j+r] << '\t' ;
   }
   cout << endl;
  }
  cout << endl ;
  temp1 = i + 1;
 }

 ///////////////打印每行不满8个的/////////////
 if(count % 8 != 0)
 {
  for( int j = 0; j != 3; j++ )
   {
    //每行分成四部分.
    for( int k = 0; k != index + 1 - temp1 * 8; k++ )
    {
     int r = 0;
     cout << path[temp1*8+k][3*j+r] << " ";
     r++;
     cout << path[temp1*8+k][3*j+r] << " ";
     r++;
     cout << path[temp1*8+k][3*j+r] << '\t' ;
    }
    cout << endl;
   }
  cout << endl ;
 }
 cout << "从初始状态到目标状态最优路径要经过 "<< index+1 << "个节点."<< endl;
 cout << "按回车,开始动态演示.动态显示节点运行情况,请注意好0点的运作." << endl;
 cin.get();
 cin.get();
 system("cls");
 for( int p = 0; p <= index ; p++)
 {
  cout << endl << endl<< endl << endl<< endl << endl<< endl ;
  cout << "\t\t\t\t";
  for( int i = 0; i < 9; i++)
  {
   if(path[p][i] != '0')
   {
    cout << path[p][i] << "\t";
   }
   else
   {
    cout << " " << "\t";
   }
   if( (i+1) % 3 == 0)
   { 
    cout << endl<< endl<< endl<< endl;
    cout << "\t\t\t\t";
   }
  }
  Sleep(1000);
  if(p != index )
  {
   system("cls");
  }
 }
 cout <<  "\t演示结束,谢谢观看." << endl;
 cin.get();
 cin.get();

}


/*本算法的核心*/
/*******************************************************

 宽度优先搜索算法如下： 
　　(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。
　　(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。
　　(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED(qq数组中)扩展节点表中。
　　(4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。
　　(5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。
　　(6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。

*******************************************************/

void Calculate( char* ptr )
{
 clock_t startTime;
 clock_t endTime;
 startTime = clock();

 int i,k = 0,cnt = 0;
 Qnode qnode(ptr);
 Queen queen;
 if( !IsJoined( qnode.data ) )
 {
  queen.Back_insert(qnode);
  qq[k++] = qnode;
 }
 Qnode Qhead;
 Qnode *tmp;
 while( queen.length)
 {
  strcpy(Qhead.data,(*queen.head).data);
  for( i = 0; i< 4; i++ )
  {
   tmp = new Qnode(Qhead);
   if( Move( (*tmp).data, i ) )
   {
    if( tmp->Goal())
    {
     (*tmp).parentnum = cnt;
     qq[k] = (*tmp);
     endTime = clock();
     cout << "整个八数码寻找最优路径耗时 " << static_cast<long>(endTime - startTime) << "毫秒..." << endl;
     GetFinalpath(qq,k);
     return;
    }
    else 
    {
     if( !IsJoined( (*tmp).data ) )
     {
      queen.Back_insert( *tmp);
      (*tmp).parentnum = cnt;
      qq[k++] = (*tmp);
     }
    }
   }
   else
   {
    delete tmp;
   }
  }
  queen.Front_delete();
  cnt++;
 }
}
extern int a = 4;
int main(void)
{
 int i;
 Qnode node;
 char choice;
 string str;
 cout << "\t\t\t\tthe second evrsion." << endl;
 cout << "请选择初始化方式:\n\ta: 手动初始化.\n\tb:自动初始化." << endl;
 cout << "您的选择是:";
 cin >> choice;
 if( choice == 'a' )
 {
  cout << "输入9个空格中所填写的数字(连续输入数字,回车结束.)." << endl;
  cin >> str;
  for( i = 0; i < 9; i++)
   node.data[i] =  str[i];
  node.data[9] = '\0';
 }
 else
 {
  srand((unsigned)time(0));
  for( i = 0; i < MAX; i++)
    node.data[i] = i + 48;
  node.data[MAX] = '\0';
  for( int i = 0; i < 20 ;i++ )
  {
   int m = rand() % 9;
   int n = rand() % 9;
   char temp = node.data[m];
   node.data[m] = node.data[n];
   node.data[n] = temp;
  }
 }
 cout << "初始状态是:" << endl;
 cout << node.data;
 cout << "请确认您是否要修改默认目标状态.?修改(y,Y),否(n,N) " << endl;
  cin >> choice;
 if( choice == 'y' || choice == 'Y')
 {
  cout << "请输入您要的目标状态." << endl;
  cin >> str;
  for( i = 0; i < MAX; i++)
   target[i] =  str[i];
  
 }
 cout << "打印目标状态:" << endl;
 cout << target;
 // 判断是否能够达到目标节点.
 if( !node.HaveSolution( ))
  cerr << "this puzzle is not solvable." << endl;
 else
  Calculate(node.data);
 cout << endl;
 return 0;
}