#include <iostream>
#include <list>
#include <string>
#include <tuple>
#include <algorithm>
#include <boost/foreach.hpp>
using namespace std;
typedef pair<int, int> Position;
inline Position operator+(const Position& p1, const Position& p2)
{
return Position(p1.first + p2.first, p1.second + p2.second);
}
inline unsigned int myabs(int i)
{
return static_cast<unsigned int>(i < 0 ? -i : i);
}
Position offset[] = {
Position(0, -1),
Position(0, 1),
Position(-1, 0),
Position(1, 0),
};
struct puz_game
{
Position m_size;
string m_start, m_goal;
Position m_space;
puz_game(int r, int c, const string& start, const string& goal);
int rows() const {return m_size.first;}
int cols() const {return m_size.second;}
};
puz_game::puz_game(int r, int c, const string& start, const string& goal)
: m_size(r, c)
, m_start(start)
, m_goal(goal)
{
int n = m_start.find(' ');
m_space = Position(n / cols(), n % cols());
}
struct puz_state : string
{
puz_state() {}
puz_state(const puz_game& g)
: string(g.m_start), m_game(&g), m_space(g.m_space), m_move(0) {}
int rows() const {return m_game->rows();}
int cols() const {return m_game->cols();}
char cell(int r, int c) const {return at(r * cols() + c);}
char& cell(const Position& p) {return (*this)[p.first * cols() + p.second];}
bool is_valid(const Position& p) const {
return p.first >= 0 && p.first < rows() && p.second >= 0 && p.second < cols();
}
void make_move(const Position& p, char move){
cell(m_space) = cell(p);
cell(m_space = p) = ' ';
m_move = move;
}
//puz_solver_idastar interface
bool is_goal_state() const {return *this == m_game->m_goal;}
void gen_children(list<puz_state>& children) const;
unsigned int get_heuristic() const;
unsigned int get_distance(const puz_state& child) const {return 1;}
const puz_game* m_game;
Position m_space;
char m_move;
};
void puz_state::gen_children(list<puz_state> &children) const
{
char* moves = "wens";
for(int i = 0; i < 4; ++i){
Position p = m_space + offset[i];
if(is_valid(p)){
children.push_back(*this);
children.back().make_move(p, moves[i]);
}
}
}
unsigned int puz_state::get_heuristic() const
{
unsigned int md = 0;
for(size_t i = 0; i < size(); ++i) {
size_t j = m_game->m_goal.find(at(i));
md += myabs(j / cols() - i / cols()) + myabs(j % cols() - i % cols());
}
return md;
}
ostream& operator<<(ostream& out, const puz_state& s)
{
if(s.m_move)
out << "move: " << s.m_move << endl;
for(int r = 0; r < s.rows(); ++r) {
for(int c = 0; c < s.cols(); ++c)
out << s.cell(r, c) << ' ';
out << endl;
}
return out;
}
template<class puz_state>
class puz_solver_idastar
{
static bool dfs(unsigned int start_cost, const puz_state& cur,
unsigned int cost_limit, unsigned int& next_cost_limit,
list<puz_state>& spath, size_t& examined)
{
++examined;
unsigned int minimum_cost = start_cost + cur.get_heuristic();
if(minimum_cost > cost_limit)
return next_cost_limit = min(next_cost_limit, minimum_cost), false;
if(cur.is_goal_state())
return next_cost_limit = cost_limit, true;
list<puz_state> children;
cur.gen_children(children);
BOOST_FOREACH(const puz_state& child, children){
// full cycle checking
if(find(spath.begin(), spath.end(), child) != spath.end())
continue;
unsigned int new_start_cost = start_cost + cur.get_distance(child);
spath.push_back(child);
bool found = dfs(new_start_cost, child, cost_limit, next_cost_limit, spath, examined);
if(found)
return true;
spath.pop_back();
}
return false;
}
public:
static pair<bool, size_t> find_solution(const puz_state& sstart, list<puz_state>& spath)
{
unsigned int inf = numeric_limits<unsigned int>::max();
unsigned int cost_limit = sstart.get_heuristic(), next_cost_limit = inf;
size_t examined = 0;
spath.assign(1, sstart);
for(;;){
bool found = dfs(0, sstart, cost_limit, next_cost_limit, spath, examined);
if(found)
return make_pair(true, examined);
if(next_cost_limit == inf)
return make_pair(false, examined);
cost_limit = next_cost_limit, next_cost_limit = inf;
}
}
};
int main()
{
// start state
// 2 8 3
// 1 6 4
// 7 5
// goal state
// 1 2 3
// 8 4
// 7 6 5
puz_game g(3, 3, "2831647 5", "1238 4765");
list<puz_state> spath;
bool found;
size_t examined;
tie(found, examined) = puz_solver_idastar<puz_state>::find_solution(g, spath);
if(found){
cout << "Sequence of moves: " << endl;
BOOST_FOREACH(const puz_state& s, spath)
cout << s;
cout << "Number of moves: " << spath.size() - 1 << endl;
}
cout << "Number of states examined: " << examined << endl;
}
/*
Sequence of moves:
2 8 3
1 6 4
7 5
move: n
2 8 3
1 4
7 6 5
move: n
2 3
1 8 4
7 6 5
move: w
2 3
1 8 4
7 6 5
move: s
1 2 3
8 4
7 6 5
move: e
1 2 3
8 4
7 6 5
Number of moves: 5
Number of states examined: 19
*/