#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class Board;
class Solver;
class Board
{
friend class Solver;
friend class compare_node;
public:
typedef enum
{
TL_SPACE,
TL_1,
TL_2,
TL_3,
TL_4,
TL_5,
TL_6,
TL_7,
TL_8,
}TILE;
Board()
{
for (int i = 0; i != 8; tiles.push_back(TILE(++i)));
tiles.push_back(TL_SPACE);
}
Board(int t[3][3])
{
for (int i = 0; i != 3; ++i)
for (int j = 0; j != 3; ++j)
tiles.push_back(TILE(t[i][j]));
}
int hamming()
{
int count = 0;
for (int i = 0; i != tiles.size(); ++i)
if (tiles[i] != TILE((i + 1)) && tiles[i] != TL_SPACE)
++count;
return count;
}
int manhattan()
{
int count = 0;
int num;
for (int i = 0; i != tiles.size(); ++i)
{
if (tiles[i] == TL_SPACE)
continue;
num = (tiles[i] + 8) % 9;
count = count + (abs(num / 3 - i / 3) + abs(num % 3 - i % 3));
}
return count;
}
bool equals(const Board &b) const
{
bool ret = true;
for (int i = 0; i != b.tiles.size(); ++i)
{
if (this->tiles[i] != b.tiles[i])
{
ret = false;
break;
}
}
return ret;
}
void neighbors(vector<Board> &nghbrs)
{
nghbrs.clear();
int pos = 0;
for (; pos != tiles.size() && tiles[pos] != TL_SPACE; ++pos);
int row = pos / 3;
int col = pos % 3;
if (row > 0)
{
nghbrs.push_back(*this);
nghbrs.back().swap(pos, (row - 1) * 3 + col);
}
if (row < 2)
{
nghbrs.push_back(*this);
nghbrs.back().swap(pos, (row + 1) * 3 + col);
}
if (col > 0)
{
nghbrs.push_back(*this);
nghbrs.back().swap(pos, row * 3 + col - 1);
}
if (col < 2)
{
nghbrs.push_back(*this);
nghbrs.back().swap(pos, row * 3 + col + 1);
}
}
string toString()
{
string s;
ostringstream convert;
for (int i = 0; i != tiles.size(); ++i)
convert << static_cast<int>(tiles[i]) << " ";
s = convert.str();
return s;
}
private:
vector<TILE> tiles;
Board *parent = nullptr;
int f = 0;
int g = 0;
int h = 0;
void swap(size_t pos1, size_t pos2)
{
if (pos1 >= tiles.size() || pos2 >= tiles.size())
throw runtime_error("position not match");
std::swap(tiles[pos1], tiles[pos2]);
}
};
// function used to compared board in heap
class compare_node
{
public:
bool operator()(Board *&l, Board *&r)
{
return l->f > r->f;
}
};
// vector for board pointers
class bvector : public vector
{
public:
bvector()
{
make_heap(this->begin(), this->end(), compare_node());
}
void push_node(Board *b)
{
this->push_back(b);
push_heap(this->begin(), this->end(), compare_node());
}
void pop_node()
{
pop_heap(this->begin(), this->end(), compare_node());
this->pop_back();
}
};
class Solver
{
friend class Board;
public:
Solver() = default;
Solver(Board *p) : initial(p) {}
void init()
{
if (initial == nullptr)
{
cerr << "Solver not initialized" << endl;
return;
}
if (!isSolvable())
{
cerr << "No solution existed" << endl;
return;
}
initial->g = 0;
initial->h = initial->manhattan() + initial->hamming();
initial->f = initial->g + initial->h;
open_ref[initial->toString()] = initial;
open_set.push_node(initial);
while (!open_set.empty())
{
Board *closed_node = open_set.front();
open_ref.erase(closed_node->toString());
closed_ref[closed_node->toString()] = closed_node;
open_set.pop_node();
if (closed_node->equals(*end))
{
Board *p = closed_node;
while (p->parent != nullptr)
{
solution.push_back(p->toString());
p = p->parent;
}
solution.push_back(initial->toString());
reverse(solution.begin(), solution.end());
return;
}
vector<Board> neighbors;
closed_node->neighbors(neighbors);
for (auto iter = neighbors.begin(); iter != neighbors.end(); ++iter)
{
Board *new_node = new Board(*iter);
new_node->g = 0;
new_node->h = new_node->manhattan() + new_node->hamming();
new_node->f = new_node->f + new_node->h;
// ignore the neighbor which is already evaluated.
if (closed_ref.find(new_node->toString()) != closed_ref.end())
{
delete new_node;
continue;
}
if (open_ref.find(new_node->toString()) != open_ref.end())
{
delete new_node;
continue;
}
new_node->parent = closed_node;
open_set.push_node(new_node);
open_ref[new_node->toString()] = new_node;
}
}
return;
}
vector<string> getSolution()
{
return solution;
}
// http://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/
// It is not possible to solve an instance of 8 puzzle if the number of inversions is odd
// in the initial state
bool isSolvable()
{
int count = 0;
for (int i = 0; i != initial->tiles.size(); ++i)
for (int j = i + 1; j != initial->tiles.size(); ++j)
if (initial->tiles[i] != Board::TILE::TL_SPACE &&
initial->tiles[j] != Board::TILE::TL_SPACE &&
static_cast<int>(initial->tiles[i]) > static_cast<int>(initial->tiles[j]))
++count;
return (count % 2 == 0);
}
~Solver()
{
delete initial;
delete end;
for (auto iter = open_ref.begin(); iter != open_ref.end(); ++iter)
delete iter->second;
for (auto iter = closed_ref.begin(); iter != closed_ref.end(); ++iter)
delete iter->second;
}
private:
Board *initial = nullptr;
Board *end = new Board();
bvector open_set;
unordered_map<string, Board*> open_ref;
unordered_map<string, Board*> closed_ref;
vector<string> solution;
};
int main()
{
int t1[3][3] = { { 1, 2, 3 },{ 4, 5, 6 },{ 8, 7, 0 } };
int t2[3][3] = { { 8, 1, 3 },{ 4, 0, 2 },{ 7, 6, 5 } };
Board *b1 = new Board(t1);
Board *b2 = new Board(t2);
Solver s1(b1);
Solver s2(b2);
s1.init();
s2.init();
auto ret2 = s2.getSolution();
cout << "The solution to " << b1->toString() << endl;
for (auto str : ret2)
cout << str << endl;
system("PAUSE");
return 0;
}
