## Algorithm

The 15-puzzle is a very popular game; even if you don’t know it by that name, you’ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. The object of the puzzle is to arrange the tiles so that they are ordered as below: Here the only legal operation is to exchange missing tile with one of the tiles with which it shares an edge. As an example, the following sequence of moves changes the status of a puzzle A random puzzle position The missing Tile moves to right. Denoted by R The missing Tile moves upwards. Denoted by U The missing Tile moves to the left. Denoted by L The letters in the previous row indicate which neighbor of the missing tile is swapped with it at each step; legal values are ‘R’, ‘L’, ‘U’ and ‘D’, for RIGHT, LEFT, UP, and DOWN, respectively. Given an initial configuration of a 15-puzzle you will have to determine the steps that would make you reach the final stage. The input 15-puzzles requires at most 45 steps to be solved with our judge solution. So you will not be allowed to use more than 50 steps to solve a puzzle. If the given initial configuration is not solvable you just need to print the line ‘This puzzle is not solvable.’ Input The first line of the input contains one integer N, which indicates how many sets of puzzle, will be given as input. Next 4N lines contain N sets of inputs. It means four lines make one set of input. Zero denotes the missing tile. Output For each set of input you will have to give one line of output. If the input puzzle is not solvable then print the line ‘This puzzle is not solvable.’ If the puzzle is solvable then print the move sequence as described above to solve the puzzle.

Sample Input 2 2 3 4 0 1 5 7 8 9 6 10 12 13 14 11 15 13 1 2 4 5 0 3 7 9 6 10 12 15 8 11 14

Sample Output LLLDRDRDR This puzzle is not solvable.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

`````` #include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define ROW_SIZE 4 // ROW_SIZE is a matrix of 4 x 4
#define PUZZLE (ROW_SIZE*ROW_SIZE)
#define X 15

int p[PUZZLE];
int lim, nlim;
int dr[] = { 0,-1, 0, 1}; // E,N,W,S
int dc[] = { 1, 0,-1, 0}; // R,U,L,D
map < int, int> pred;
map vis; // visited state with cost
char ans[] = "RULD";

inline int h1() { // heuristic: sum of Manhattan distances (compute all)
int ans = 0;
for (int i = 0; i  <  PUZZLE; i++) {
int tgt_i = p[i] / 4, tgt_j = p[i] % 4;
if (p[i] != X)
ans += abs(i / 4 - tgt_i) + abs(i % 4 - tgt_j); // Manhattan distance
}
return ans;
}

inline int h2(int i1, int j1, int i2, int j2) { // heuristic: sum of manhattan distances (compute delta)
int tgt_i = p[i2 * 4 + j2] / 4, tgt_j = p[i2 * 4 + j2] % 4;
return -(abs(i2 - tgt_i) + abs(j2 - tgt_j)) + (abs(i1 - tgt_i) + abs(j1 - tgt_j));
}

inline bool goal() {
for (int i = 0; i  <  PUZZLE; i++)
if (p[i] != X && p[i] != i)
return false;
return true;
}

inline bool valid(int r, int c) {
return 0  < = r && r < 4 && 0 <= c && c < 4;
}

inline void swap(int i, int j, int new_i, int new_j) {
int temp = p[i * 4 + j];
p[i * 4 + j] = p[new_i * 4 + new_j];
p[new_i * 4 + new_j] = temp;
}

bool DFS(int g, int h) {
// prune higher cost than existing best
if (g + h > lim) {
nlim = min(nlim, g + h); // set maximum cost allowed for next iteration
return false;
}

if (goal())
return true;

unsigned long long state = 0;
for (int i = 0; i  <  PUZZLE; i++) { // transform 16 numbers into 64 bits, exactly into ULL
state <<= 4; // move left 4 bits
state += p[i]; // add this digit (max 15 or 1111)
}

if (vis.count(state) && vis[state]  < = g) // not pure backtracking... this is to prevent cycling
return false;
vis[state] = g; // mark this as visited

// find blank
int i, j, d, new_i, new_j;
for (i = 0; i  <  PUZZLE; i++)
if (p[i] == X)
break;
j = i % 4;
i /= 4;

// all 4 directions
for (d = 0; d  <  4; d++) {
new_i = i + dr[d]; new_j = j + dc[d];
if (valid(new_i, new_j)) {
int dh = h2(i, j, new_i, new_j);
swap(i, j, new_i, new_j); // swap first
pred[g + 1] = d;
if (DFS(g + 1, h + dh)) // if ok, no need to restore, just go ahead
return true;
swap(i, j, new_i, new_j); // restore
}
}

return false;
}

// iteratively deepen/increase cost allowed
int IDA_Star() {
lim = h1();
while (true) {
nlim = INF; // next limit
pred.clear();
vis.clear();
if (DFS(0, h1()))
return lim; // found result
if (nlim == INF)
return -1;
lim = nlim; // nlim > lim
if (lim > 45) // pruning condition in the problem
return -1;
}
}

void output(int d) {
if (d == 0)
return;
output(d - 1);
printf("%c", ans[pred[d]]);
}

int main() {
int N;
scanf("%d", &N);
while (N--) {
int i, j, blank = 0, sum = 0, ans = 0;
for (i = 0; i  <  4; i++)
for (j = 0; j  <  4; j++) {
scanf("%d", &p[i * 4 + j]);
if (p[i * 4 + j] == 0) {
p[i * 4 + j] = X; // change to X (15)
blank = i * 4 + j; // remember the index
}
else
p[i * 4 + j]--; // use 0-based indexing
}

// check whether puzzle can be solved - https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
// a N*N puzzle can only be solved:
// If N is odd, then puzzle instance is solvable if number of inversions is EVEN in the input state.
// If N is even, puzzle instance is solvable if
//     - the blank is on an even row counting from the bottom (second-last, fourth-last, etc.) and number of inversions is ODD.
//     - the blank is on an odd row counting from the bottom (last, third-last, fifth-last, etc.) and number of inversions is EVEN.
// since N is even here, we count inversion and add row it is on
for (i = 0; i  <  PUZZLE; i++)
for (j = 0; j  <  i; j++)
if (p[i] != X && p[j] != X && p[j] > p[i]) // inversion if a > b
sum++;
sum += blank / ROW_SIZE;

if (sum % 2 != 0 && ((ans = IDA_Star()) != -1))
output(ans), printf("\n");
else
printf("This puzzle is not solvable.\n");
}

return 0;
}``````
Copy The Code &

Input

cmd
2
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11<15 13 1 2 4
5 0 3 7
9 6 10 12
15 8 11 14

Output

cmd
LLLDRDRDR
This puzzle is not solvable.