//#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;
}