// 15-Puzzle Problem （15 ）
// PC/UVa IDs: 110802/10181, Popularity: B, Success rate: average Level: 3
// Verdict: Accepted
// Submission Date: 2011-06-22
// UVa Run Time: 0.320s
//
// （C）2011， 。metaphysis # yeah dot net
//
// You can fool some of the people all of the time, and all of the people
// some of the time, but you can not fool all of the people all of the time.
// Abraham Lincoln, 16th president of US (1809 - 1865).
//
// http://mathworld.wolfram.com/15Puzzle.html 。
// e ，n ，N ：
//
// 15 15
// N = ∑ ni = ∑ ni
// i = 1 i = 2
//
// N + e ， ， 。 ：
//
// 13 10 11 6
// 5 7 4 8
// 1 12 14 9
// 3 15 2 0
//
// 13 12， 10 9， ，
// n 9（11），5（6），4（5），4（7），3（4），3（8），0（1），3（12），
// 3（14），2（9），1（3），1（15），0（2）。 n N = 59， 4 ， e =
// 4， N + e = 63， ， 。
//
// [ （Depth-First Search）]
// [ George T. Heineman, Gary Pollice, and Stanley Selkow, ALGORITHMS In a
// Nutshell, O‘Reilly Media, Inc. 2008]
//
// ， ， ，
// ， ，
// ， 。 ，
// ， ， 。 ，
// 。 ， 。 ，
// 。 ：
//
// search (initial, goal)
// if (initial = goal) then return "Solution"
// initial.depth = 0
// open = new Stack
// closed = new Set
// insert(open, copy(initial))
// while (open is not empty) do
// n = pop(open)
// insert(closed, n)
// foreach valid move m at n do
// next = state when playing m at n
// if (closed doesn't contain next) then
// next.depth = n.depth + 1
// if (next = goal) then return "Solution"
// if (next.depth < maxDepth) then
// insert(open, next)
// return "No Solution"
// end
//
// ， 45 ，
// 50 ， 50。 ，
// ，
// ， ， ， ，
// ， 。 ， ，
// ， ，
// ， ， ，
// 。
//
// ， 。 16 ，
// ， ， 16 ，
// ：
//
// 13 * 16^15 + 10 * 16^14 + 11 * 16^13 + 6 * 16^12 + 5 * 16^11 + 7 * 16^10 +
// 4 * 16^9 + 8 * 16^8 + 1 * 16^7 + 12 * 16^6 + 14 * 16^5 + 9 * 16^4 +
// 3 * 16^3 + 15 * 16^2 + 2 * 16^1 + 0 * 16^1 = DAB657481CE93F20(hex) =
// 15759879913263939360(dec)
//
// 。
//
// [ （Breadth-First Search）]
//
// ， 。
// ， 。
// ， 。 ， ，
// ， ， ， ，
// 。 ， 。 ：
//
// search (initial, goal)
// if (initial = goal) then return "Solution"
// open = new Queue
// closed = new Set
// insert(open, copy(initial))
// while (open is not empty) do
// n = head(open)
// insert(closed, n)
// foreach valid move m at n do
// next = state when playing m at n
// if (closed doesn't contain next) then
// if (next = goal) then return "Solution"
// insert(open, next)
// return "No Solution"
// end
//
// [A* ]
// [ George T. Heineman, Gary Pollice, and Stanley Selkow, ALGORITHMS In a
// Nutshell, O‘Reilly Media, Inc. 2008]
//
// （ ）， ，
// ， ， ， ， ，
// 。A* ，
// 。A* ， 。 ，A*
// f*（n） ， 。 ：
//
// f*（n） = g*（n） + h*（n）
// g*（n） n 。
// h*（n） n 。
// f*（n） ， n， 。
//
// * （ 1968 ， ）， f*（n），
// g*（n），h*（n） f（n），g（n），h（n） ，
// 。f*（n） ， n 。f*（n） h*（n），
// g*（n） ， n 。 h*（n）
// ， A* 。
// h*（n）， f*（n） 。 ：
//
// search (initial, goal)
// initial.depth = 0
// open = new PriorityQueue
// closed = new Set
// insert(open, copy(initial))
// while (open is not empty) do
// n = minimum(open)
// insert(closed, n)
// if (n = goal) then return "Solution"
// foreach valid move m at n do
// next = state when playing m at n
// next.depth = n.depth + 1
// if (closed contains next) then
// prior = state in closed matching next
// if (next.score < prior.score) then
// remove(closed, prior)
// insert(open, next)
// else
// insert(open, next)
// return "No Solution"
// end
//
// [ A*（Iterative-Deepening A* Search，IDA*） ]
// [ Richard E. Korf, "Recent Progress in the Design and Analysis of Admissible
// Heuristic Functions," Proceeding, Abstraction, Reformulation, and Approximation:
// 4th International Symposium (SARA), Lecture notes in Computer Science #1864:
// 45 - 51, 2000]
//
// IDA* 。 ，
// 。IDA* ，
// 。
#include <iostream>
#include <cstring>
#include <limits>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define SQUARES 4 // 。
#define BASE 16 // 。
#define DEPTHBOUND 30 // 。
#define STEPSBOUND 50 // 。
#define MOVE_LEFT (-1)
#define MOVE_RIGHT 1
#define MOVE_UP (-SQUARES)
#define MOVE_DOWN SQUARES
#define MOVE_NONE 0
int manhattan[SQUARES * SQUARES][SQUARES * SQUARES]; // 。
int move[SQUARES]; // 。
// 。
struct node
{
vector < int > state; // 。
int moves[STEPSBOUND]; // 。
int depth; // 。
int score; // 。
int blank; // 。
};
// 。 。
bool operator<(node x, node y)
{
return x.score > y.score;
}
// 。
int absi(int x)
{
return x >= 0 ? x : (-x);
}
// 。
bool solvable(vector < int > tiles)
{
int sum = 0, row;
for (int i = 0; i < tiles.size(); i++)
{
int tile = tiles[i];
if (tile == 0)
{
row = (i / SQUARES + 1);
continue;
}
for (int m = i; m < tiles.size(); m++)
if (tiles[m] < tile && tiles[m] != 0)
sum++;
}
return !((sum + row) % 2);
}
// 。MOVE_LEFT = ，MOVE_RIGHT = ，
// MOVE_UP = ，MOVE_DOWN = 。
void valid_moves(node ¤t)
{
// ， 。
int last_move = MOVE_NONE;
if (current.depth)
last_move = current.moves[current.depth - 1];
memset(move, MOVE_NONE, sizeof(move));
if (current.blank % SQUARES > 0 && last_move != MOVE_RIGHT)
move[0] = MOVE_LEFT;;
if (current.blank % SQUARES < (SQUARES - 1) && last_move != MOVE_LEFT)
move[1] = MOVE_RIGHT;
if (current.blank / SQUARES > 0 && last_move != MOVE_DOWN)
move[2] = MOVE_UP;
if (current.blank / SQUARES < (SQUARES - 1) && last_move != MOVE_UP)
move[3] = MOVE_DOWN;
}
// 。
unsigned long long key(vector < int > &tiles)
{
unsigned long long key = 0;
for (int i = 0; i < tiles.size(); i++)
key = key * BASE + tiles[i];
return key;
}
// current move 。
node execute(node ¤t, int move)
{
node successor;
// 。
memcpy(successor.moves, current.moves, sizeof(current.moves));
successor.depth = current.depth + 1;
successor.moves[current.depth] = move;
// 。 move ， 。
successor.state = current.state;
successor.blank = current.blank + move;
successor.state[current.blank] = successor.state[successor.blank];
successor.state[successor.blank] = 0;
return successor;
}
// h*（n） ， ， ，
// h*（n） ， ，
// 。g*（n） ，
// ： f*（n） = g*（n） + 4 / 3 * h*（n），h*（n） ，
// 。 ， ，
// 。 ：
// [Bernard Bauer，The Manhattan Pair Distance Heuristic for the 15-Puzzle，1994]
int score(vector < int > &state, int depth)
{
int hn = 0;
for (int i = 0; i < state.size(); i++)
if (state[i] > 0)
hn += manhattan[state[i] - 1][i];
return (depth + 4 * hn / 3);
}
// 。
bool solved(vector < int > &state)
{
if (state[SQUARES * SQUARES - 1] != 0)
return false;
for (int i = 0; i < SQUARES * SQUARES - 1; i++)
if (state[i] != (i + 1))
return false;
return true;
}
// 。
int find_blank(vector < int > &state)
{
for (int i = 0; i < SQUARES * SQUARES; i++)
if (state[i] == 0)
return i;
}
// [ ]
// 。 （15 ） ，
// ， ， ，
// 。 ， ， ， ，
// 。
bool solve_puzzle_by_depth_first_search(vector < int > tiles, int directions[])
{
node copy;
copy.state = tiles;
copy.depth = 0;
copy.blank = find_blank(tiles);
memset(copy.moves, MOVE_NONE, sizeof(copy.moves));
// 。
if (solved(copy.state))
{
memcpy(directions, copy.moves, sizeof(copy.moves));
return true;
}
// 。
stack < node > open; // 。
open.push(copy);
// 。
set < unsigned long long > closed;
while (!open.empty())
{
// ， 。
node current = open.top();
open.pop();
closed.insert(key(current.state));
// ， 。
valid_moves(current);
for (int i = 0; i < SQUARES; i++)
{
if (move[i] == MOVE_NONE)
continue;
// 。
node successor = execute(current, move[i]);
// ， 。
if (closed.find(key(successor.state)) != closed.end())
continue;
// ， ， 。
// 。
if (solved(successor.state))
{
memcpy(directions, successor.moves,
sizeof(successor.moves));
return true;
}
// 。
if (successor.depth < DEPTHBOUND)
open.push(successor);
}
}
return false;
}
// [ ]
// （15 ） ， ，
// ， ， 。
bool solve_puzzle_by_breadth_first_search(vector < int > tiles, int directions[])
{
node copy;
copy.state = tiles;
copy.depth = 0;
copy.blank = find_blank(tiles);
memset(copy.moves, MOVE_NONE, sizeof(copy.moves));
// 。
if (solved(copy.state))
{
memcpy(directions, copy.moves, sizeof(copy.moves));
return true;
}
// 。
queue < node > open; // 。
open.push(copy);
// 。
set < unsigned long long > closed;
while (!open.empty())
{
// ， 。
node current = open.front(); // 。
open.pop();
closed.insert(key(current.state));
// ， 。
valid_moves(current);
for (int i = 0; i < SQUARES; i++)
{
if (move[i] == MOVE_NONE)
continue;
// 。
node successor = execute(current, move[i]);
// ， 。
if (closed.find(key(successor.state)) != closed.end())
continue;
// ， ， 。
if (solved(successor.state))
{
memcpy(directions, successor.moves,
sizeof(successor.moves));
return true;
}
// 。
open.push(successor);
}
}
return false;
}
// [A* ]
// ， ， ，
// A* ， （ ），
// ， ， DFS BFS
// ， ， A* ， ，
// ， 。 ，
// ， ， ， A*
// ， ， 。
bool solve_puzzle_by_a_star(vector < int > tiles, int directions[])
{
node copy;
copy.state = tiles;
copy.depth = 0;
copy.blank = find_blank(tiles);
copy.score = score(copy.state, 0);
memset(copy.moves, MOVE_NONE, sizeof(copy.moves));
priority_queue < node > open; // A* 。
open.push(copy);
map < unsigned long long, int > closed;
while (!open.empty())
{
// ， 。
node current = open.top();
open.pop();
// 。
closed.insert(make_pair< unsigned long long, int >
(key(current.state), current.score));
// ， 。
if (solved(current.state))
{
memcpy(directions, current.moves,
sizeof(current.moves));
return true;
}
// ， 。
valid_moves(current);
for (int i = 0; i < SQUARES; i++)
{
if (move[i] == MOVE_NONE)
continue;
// ， 。
node successor = execute(current, move[i]);
// 。
successor.score = score(successor.state, successor.depth);
// ， ，
// ， ， 。 ，
// ， ，
// ， ，
// ， “ ” 。
map < unsigned long long, int >::iterator it =
closed.find(key(successor.state));
if (it != closed.end())
{
if (successor.score >= (*it).second)
continue;
closed.erase(it);
}
// 。
open.push(successor);
}
}
return false;
}
// [IDA* ]
// ， ， ，A* ，
// ， 。IDA* 。IDA*
// 。
bool solve_puzzle_by_iterative_deepening_a_star(vector < int > tiles,
int directions[])
{
node copy;
copy.state = tiles;
copy.depth = 0;
copy.blank = find_blank(tiles);
memset(copy.moves, MOVE_NONE, sizeof(copy.moves));
// 。
if (solved(copy.state))
{
memcpy(directions, copy.moves, sizeof(copy.moves));
return true;
}
// 。
int depth_limit = 0, min_depth = score(copy.state, 0);
while (true)
{
// 。
if (depth_limit < min_depth)
depth_limit = min_depth;
else
depth_limit++;
numeric_limits< int > t;
min_depth = t.max();
// ， depth_limit。
stack < node > open;
open.push(copy);
while (!open.empty())
{
node current = open.top();
open.pop();
// ， 。
valid_moves(current);
for (int i = 0; i < SQUARES; i++)
{
if (move[i] == MOVE_NONE)
continue;
// 。
node successor = execute(current, move[i]);
// ， ， 。
// 。
if (solved(successor.state))
{
memcpy(directions, successor.moves,
sizeof(successor.moves));
return true;
}
// ， ， ，
// 。
successor.score = score(successor.state,
successor.depth);
if (successor.score < depth_limit)
open.push(successor);
else
{
if (successor.score < min_depth)
min_depth = successor.score;
}
}
}
}
return false;
}
void solve_puzzle(vector < int > tiles)
{
int moves[STEPSBOUND];
// 。
// solve_puzzle_by_depth_first_search(tiles, moves);
// 。
// solve_puzzle_by_breadth_first_search(tiles, moves);
// A* 。 30 - 50 7 s。UVa RT 1.004 s。
// solve_puzzle_by_a_star(tiles, moves);
// IDA* 。 30 - 50 1.5 s。UVa RT 0.320 s。
solve_puzzle_by_iterative_deepening_a_star(tiles, moves);
// 。
for (int i = 0; i < STEPSBOUND; i++)
{
if (moves[i] == MOVE_NONE)
break;
switch (moves[i])
{
case MOVE_LEFT:
cout << "L";
break;
case MOVE_RIGHT:
cout << "R";
break;
case MOVE_UP:
cout << "U";
break;
case MOVE_DOWN:
cout << "D";
break;
}
}
cout << endl;
}
// 。
void cal_manhattan(void)
{
for (int i = 0; i < SQUARES * SQUARES; i++)
for (int j = 0; j < SQUARES * SQUARES; j++)
{
int tmp = 0;
tmp += (absi(i / SQUARES - j / SQUARES) +
absi(i % SQUARES - j % SQUARES));
manhattan[i][j] = tmp;
}
}
int main(int ac, char *av[])
{
// ， 。
cal_manhattan();
int n, tile;
vector < int > tiles; // 。
cin >> n;
while (n--)
{
// 。
tiles.clear();
for (int i = 0; i < SQUARES * SQUARES; i++)
{
cin >> tile;
tiles.push_back(tile);
}
// ， ， 。
if (solvable(tiles))
solve_puzzle(tiles);
else
cout << "This puzzle is not solvable." << endl;
}
return 0;
}