پیاده سازی:
#include <iostream>
#include <vector>
#include <queue>
#include <hash_map>
#include <algorithm>
#include <math.h>
using namespace std;
class _8_Puzzle_Solution;
class _8_Puzzle
{
public:
typedef unsigned int STATUS;
typedef unsigned int MOVE;
typedef int SERIAL;
static const STATUS ERROR = 0, DONE = 1;
static const MOVE UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3;
_8_Puzzle()
{
unsigned int i;
for (i = 0; i < 9; i++)
Element[i] = i;
}
STATUS USER_Set8_Puzzle();
void Print8_Puzzle();
static vector<_8_Puzzle> SearchSolution(_8_Puzzle&,_8_Puzzle&);
bool operator ==(_8_Puzzle &);
bool operator ==(_8_Puzzle const &);
bool operator !=(_8_Puzzle &);
bool operator !=(_8_Puzzle const &);
unsigned int HeuristicFunction(_8_Puzzle);
STATUS MoveZeroUp();
STATUS MoveZeroDown();
STATUS MoveZeroLeft();
STATUS MoveZeroRight();
STATUS Move(MOVE);
static SERIAL Encode(_8_Puzzle&);
static _8_Puzzle Decode(SERIAL);
private:
unsigned int Element[9];//Element[]>=0&&Element[]<=8
unsigned int FindZeroIn8_Puzzle(_8_Puzzle);
};
#include "8_Puzzle.h"
_8_Puzzle::STATUS _8_Puzzle::USER_Set8_Puzzle()
{
unsigned int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cout << "Row:" << i + 1 << endl << "Column:" << j + 1 << endl << "'0' represents a void." << endl << endl << "Enter a number(0-8). " << endl;
cin >> (this->Element[3 * i + j]);
}
}
return(_8_Puzzle::DONE);
}
void _8_Puzzle::Print8_Puzzle()
{
unsigned int i;
for(i=0;i<3;i++)
{
if (this->Element[i] != 0)
cout << "|" << this->Element[i];
else
cout << "| ";
}
cout<<"|"<<endl<<"-------"<<endl;
for(i=3;i<6;i++)
{
if(this->Element[i]!=0)
cout << "|" << this->Element[i];
else
cout << "| ";
}
cout << "|" << endl << "-------" << endl;
for(i=6;i<9;i++)
{
if(this->Element[i]!=0)
cout << "|" << this->Element[i];
else
cout << "| ";
}
cout << "| "<<endl;
}
bool _8_Puzzle::operator == (_8_Puzzle& Table)
{
unsigned int i;
for (i = 0; i < 9; i++)
{
if (this->Element[i] != Table.Element[i])
return(false);
}
return(true);
}
bool _8_Puzzle::operator == (_8_Puzzle const &Table)
{
unsigned int i;
for (i = 0; i < 9; i++)
{
if (this->Element[i] != Table.Element[i])
return(false);
}
return(true);
}
bool _8_Puzzle::operator != (_8_Puzzle &Table)
{
return(!(*this == Table));
}
bool _8_Puzzle::operator != (_8_Puzzle const &Table)
{
return(!(*this == Table));
}
unsigned int _8_Puzzle::FindZeroIn8_Puzzle(_8_Puzzle Puzzle)
{
unsigned int i;
for(i=0;i<9;i++)
{
if(Puzzle.Element[i]==0)
return(i+1);
}
return(0);
}
_8_Puzzle::STATUS _8_Puzzle::MoveZeroUp()
{
unsigned int num;
num=FindZeroIn8_Puzzle(*this);
if(num>3)
{
this->Element[num-1]=this->Element[num-4];
this->Element[num-4]=0;
return(_8_Puzzle::DONE);
}
else
return(_8_Puzzle::ERROR);
}
_8_Puzzle::STATUS _8_Puzzle::MoveZeroDown()
{
unsigned int num;
num=FindZeroIn8_Puzzle(*this);
if(num>0&&num<7)
{
this->Element[num-1]=this->Element[num+2];
this->Element[num+2]=0;
return(_8_Puzzle::DONE);
}
else
return(_8_Puzzle::ERROR);
}
_8_Puzzle::STATUS _8_Puzzle::MoveZeroLeft()
{
unsigned int num;
num=FindZeroIn8_Puzzle(*this);
if(num%3!=1&&num!=0)
{
this->Element[num-1]=this->Element[num-2];
this->Element[num-2]=0;
return(_8_Puzzle::DONE);
}
else
return(_8_Puzzle::ERROR);
}
_8_Puzzle::STATUS _8_Puzzle::MoveZeroRight()
{
unsigned int num;
num=FindZeroIn8_Puzzle(*this);
if(num%3!=0)
{
this->Element[num-1]=this->Element[num];
this->Element[num]=0;
return(_8_Puzzle::DONE);
}
else
return(_8_Puzzle::ERROR);
}
_8_Puzzle::STATUS _8_Puzzle::Move(_8_Puzzle::MOVE param)
{
switch (param)
{
case 0:
return(this->MoveZeroUp());
case 1:
return(this->MoveZeroDown());
case 2:
return(this->MoveZeroLeft());
case 3:
return(this->MoveZeroRight());
default:
return _8_Puzzle::ERROR;
}
}
int _8_Puzzle::Encode(_8_Puzzle &Puzzle)
{
unsigned int i;
int PuzzleID = 0;
for (i = 0; i < 9; i++)
PuzzleID = PuzzleID + Puzzle.Element[i] * pow(10, i);//12345678~876543210
return(PuzzleID);
}
_8_Puzzle _8_Puzzle::Decode(int serial)
{
_8_Puzzle decode;
for (int i = 0; i < 9; i++)
{
decode.Element[i] = serial % 10;
serial = serial / 10;
}
return(decode);
}
vector<_8_Puzzle> _8_Puzzle::SearchSolution(_8_Puzzle &Origin, _8_Puzzle &Target)
{
vector<_8_Puzzle> Solution;
if (Origin == Target)
{
Solution.push_back(Target);
return(Solution);
}
queue <int> open;
hash_map <int,int> closed;
const _8_Puzzle::SERIAL TargetSerial=Encode(Target);
open.push(Encode(Origin));
closed[Encode(Origin)] = 0;//closed[NodeSerial]=[ParentNodeSerial]
bool SolutionExistence = false;
while (SolutionExistence == false && open.empty() == false)
{
_8_Puzzle Node = Decode(open.front()), NewNode;
for (int move_i = 0; move_i < 4; move_i++)
{
NewNode = Node;
if (NewNode.Move(move_i) == _8_Puzzle::DONE)
{
int NewSerial = Encode(NewNode);
if (closed.find(NewSerial) == closed.end())
{
closed[NewSerial] = open.front();
open.push(NewSerial);
}
if (NewNode == Target)
{
SolutionExistence = true;
break;
}
}
}
open.pop();
}
if (SolutionExistence == false)
return Solution;
_8_Puzzle::SERIAL SolutionTrajectory = TargetSerial;
while (SolutionTrajectory!=0)
{
Solution.insert(Solution.begin(), Decode(SolutionTrajectory));
SolutionTrajectory = closed[SolutionTrajectory];
}
return(Solution);
}
void main()
{
_8_Puzzle Origin, Target;
cout << "Set Origin:" << endl;
Origin.USER_Set8_Puzzle();
cout << "Set Target:" << endl;
Target.USER_Set8_Puzzle();
system("cls");
cout << "Origin:" << endl;
Origin.Print8_Puzzle();
cout << "Target:" << endl;
Target.Print8_Puzzle();
cout << "Press anykey to confirm configuration and start searching for solution. " << endl;
system("pause>nul");
clock_t t_begin, t_end;
t_begin = clock();
vector<_8_Puzzle> Solution;
Solution = _8_Puzzle::SearchSolution(Origin, Target);
t_end = clock();
if (Solution.empty()==false)
{
for (int i = 0; i < Solution.size(); i++)
{
cout << "Step " << i << ": " << endl;
Solution[i].Print8_Puzzle();
}
cout << Solution.size()-1 << " step(s) in total. " << endl;
}
else
cout << "No Solution." << endl;
cout << "Total time elapsed: " << endl << (t_end - t_begin) << "ms" << endl;
system("pause");
}