global.cpp

八数码问题源程序.

/*
  本文件是核心算法文件.
  前面的所有函数都是为了最后一个函数服务的.
  如果只是看算法的话,看最后一个函数就可以了.
  函数的排列顺序一般都是上面的函数为下面的函数服务的,
  所以看的时候从下往上看会比较好一点
*/
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop

#include "global.h"
#include "TList.h"
//#include <stdlib.h>

int BData[3][3]; //全局变量，记录将牌各位置的起始状态
int EData[3][3]; //全局变量，记录将牌各位置的目标状态
KTList<RULETYPE>* Paths;   //全局变量，解路径规则表


//---------------------------------------------------------------------------
//数组mData是否在当前位置(i,j)以前存在数mNum
int KExists(int mNum,int mData[][3],int mi,int mj)
{
   int i,j;

   if ( mi== 0 && mj==0 )
     return mNum;

   for(i=0;i<=mi;i++) {
      for (j=0; j<3 && i*3+j<mi*3+mj ;j++) {
         if (mData[i][j] == mNum)
           return -1;  //如果存在重复的数
      }
   }

   return mNum;
}

//---------------------------------------------------------------------------
//得到下一个1-9的、不同于珊格中原有的数
int KGetNextNum(int mData[][3],int mi,int mj)
{
//   int theNum;
//   while (  ( theNum=KExists(rand()*9/RAND_MAX,mData,mi,mj) ) == -1  );
//   return theNum;
   return 0;
}
//---------------------------------------------------------------------------
//重新设置起始状态
void ResetBData(int mData[][3])
{
   KCopy(BData,mData);
}
//---------------------------------------------------------------------------
//重新设置目标状态
void ResetEData(int mData[][3])
{
   KCopy(EData,mData);
}
//---------------------------------------------------------------------------
//寻找到空格位置(i,j)
bool FindSpace(int* pi,int* pj,int mData[][3])
{
   int i,j;
   for (i=0;i<3;i++) {
      for (j=0;j<3;j++) {
         if (mData[i][j]==0) {
            *pi = i;
            *pj = j;
            return true;
         }
      }
   }

   return false;
}
//---------------------------------------------------------------------------
//启发函数,当前状态nData与其目标位置mData的不在位的将牌数
int CompareData(int nData[3][3],int mData[3][3])
{
   int i,j;

   int sum = 0;

   for (i=0;i<3;i++)
     for (j=0;j<3;j++) {
        if (nData[i][j] != mData[i][j])
           sum = sum + 1;
     }

   return sum;
}
//---------------------------------------------------------------------------
//根据权值由小到大的顺序插入节点
void KInsert(KTList<RULETYPE>* mRules,RULETYPE R,int mData[][3])
{
   int nData[3][3];    //临时生成的状态，看看调用当前每一个可用规则后的情况
   int Weight;

   KCopy(nData,mData);       //拷贝当前状态
   Gen(R,nData);             //应用当前规则
   Weight = CompareData(nData,EData);  //启发函数
   
   mRules->LocateWeight(Weight);       //定位到Weight值刚好大于等于Weight的下一个节点
   mRules->Insert(R);                  //插入一个节点
   mRules->SetWeight(Weight);          //设置该节点权值
}
//---------------------------------------------------------------------------
//计算当前状态可用的规则集(空格上移，下，左，右)
void AppRules(KTList<RULETYPE>* mRules,int mData[][3])
{
   int i,j;
   RULETYPE R;

   Paths->Last();      //找到上一次用的规则的反向规则，避免重走
   if (Paths->GetData(R))
      R = Reverse(R);
   else
      R = WRONG;  

   //寻找到空格位置(i,j)
   FindSpace(&i,&j,mData);

   if (i>0 && R != UP)
      KInsert(mRules,UP,mData);    //有向上移的规则
   if (i<2 && R != DOWN)
      KInsert(mRules,DOWN,mData);  //有向下移的规则
   if (j>0 && R != LEFT)
      KInsert(mRules,LEFT,mData);  //有向左移的规则
   if (j<2 && R != RIGHT)
      KInsert(mRules,RIGHT,mData);  //有向右移的规则

//    mRules->Sort();      //根据权值对规则从小到大排序
//  已经是按顺序插入了，这一句可省
}
//---------------------------------------------------------------------------
//是否找到目标
bool Term(int mData[][3])
{
   int i,j;

   for (i=0;i<3;i++)
      for (j=0;j<3;j++) {
         if (mData[i][j] != EData[i][j] )
            return false;
      }

   return true;
}
//---------------------------------------------------------------------------
//两个状态是否重复
bool Repeat(int mData[][3],int nData[][3])
{
   int i,j;

   for (i=0;i<3;i++)
      for (j=0;j<3;j++) {
         if (mData[i][j] != nData[i][j] )
            return false;  //不重复
      }

   return true;    //如果重复
}
//---------------------------------------------------------------------------
//是否当前状态与解路上的状态重复
bool ReadEnd(int mData[][3])
{
   int nData[3][3];   //解路上的状态
   RULETYPE mR;

   KCopy(nData,BData);  //拷贝第一个状态

   Paths->First();

   while (!Paths->IsEof()) {
      if (Repeat(mData,nData))  //如果当前状态与解路上的状态重复
         return true;

      Paths->GetData(mR);
      Gen(mR,nData);  //应用规则序列的规则，得到解路上的下一个状态

      Paths->Next();            //下一个规则序列的节点
   }

   return false;
}
//---------------------------------------------------------------------------
//判断当空个位置为(mi,mj)、规则为mR时的合法性
bool KValid(RULETYPE mR,int mi,int mj)
{
   if (mR==WRONG)
      return false;
   if (mR==UP && mi==0)     //有向上移的规则
      return false;
   if (mR==DOWN && mi==2)     //有向下移的规则
      return false;
   if (mR==LEFT && mj==0)     //有向左移的规则
      return false;
   if (mR==RIGHT && mj==2)     //有向右移的规则
      return false;

   return true;   
}
//---------------------------------------------------------------------------
//调用规则R作用于当前状态，生成新状态
bool Gen(RULETYPE mR,int mData[3][3])
{
   int i,j;
   FindSpace(&i,&j,mData);   //寻找到空格位置(i,j)

   if (!KValid(mR,i,j)) {  //判断当空格位置为(mi,mj)、规则为mR时的合法性
      AnsiString s;
      s = " R="+IntToStr(mR)+",i="+IntToStr(i)+",j="+IntToStr(j);
      s ="规则不合法！" + s;
      MessageBox(NULL,s.c_str(),"错误",MB_OK);
      return false;
   }   

   if (mR == UP) {       //上移
      mData[i][j] = mData[i-1][j];
      mData[i-1][j] = 0;
   }
   if (mR == DOWN) {       //下移
      mData[i][j] = mData[i+1][j];
      mData[i+1][j] = 0;
   }
   if (mR == LEFT) {       //左移
      mData[i][j] = mData[i][j-1];
      mData[i][j-1] = 0;
   }
   if (mR == RIGHT) {       //右移
      mData[i][j] = mData[i][j+1];
      mData[i][j+1] = 0;
   }

   return true;
}
//---------------------------------------------------------------------------
//返回规则mR的反向规则
RULETYPE Reverse(RULETYPE mR)
{
   switch (mR)
   {
      case UP: return DOWN;     //上移->下移
      case DOWN: return UP;     //下移->上移
      case LEFT: return RIGHT;  //左移->右移
      case RIGHT: return LEFT;  //右移->左移
   }

   return WRONG;
}
//---------------------------------------------------------------------------
//拷贝mData的数据给NData
void KCopy(int nData[][3],int mData[][3])
{
   int i,j;
   for (i=0;i<3;i++)
      for (j=0;j<3;j++)
         nData[i][j] = mData[i][j];
}
//---------------------------------------------------------------------------
//核心函数！！！
//利用递归算法求一条解路径，但不一定是最佳路径
bool BackTrack(int mData[3][3],int deeps)
{
   KTList<RULETYPE>* Rules;    //规则集序列表
   RULETYPE R;            //当前调用规则(空格上移1，下2，左3，右4)
   bool Result;      //是否找到目标

   if (Term(mData))
      return true; //如果找到目标

   if (ReadEnd(mData))
      return false; //如果当前状态与解路上的状态重复,回溯

   if (deeps>30)   //递归的深度
      return false;

   deeps = deeps+1;       //深度加1

   Rules = new KTList<RULETYPE>;
   AppRules(Rules,mData);  //计算当前状态可用的规则集(空格上移，下，左，右)

   do {
      if (Rules->IsEmpty()) {      //如果规则用完，跳出循环返回，回溯
         deeps = deeps - 1;    //深度减1
         delete Rules;
         return false;
      }

      Rules->First();
      Rules->GetData(R); //取头条可应用规则
      Rules->Delete();   //删去头条规则

      Paths->Append(R);  //在解路径表尾部增加一个当前路径规则

      //调用规则R作用于当前状态，生成新状态
      Gen(R,mData);

      //对新状态递归调用本过程！！！
      Result = BackTrack(mData,deeps);

      //如果Result = true，不删除规则，退出循环，最后得到成功的规则序列
      //如果调用规则R而没有找到目标
      if (!Result) {
          //返回到最后一条规则调用之前的状态，继续循环调用其他规则，不回溯
         Paths->Last();
         Paths->GetData(R);
         Gen(Reverse(R),mData);

         Paths->Cut(); //删除解路径表中的最后一个规则
      }

   } while( !Result );

   //只有成功Return ture的时候才会退出循环执行到这两句，其他情况return时必定是以失败退出
   delete Rules;
   return true;
}

//---------------------------------------------------------------------------
#pragma package(smart_init)