Eight

The 15-puzzle has been around for over 100 years; 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. Let's call the missing tile `x'; the object of the puzzle is to arrange the tiles so that they are ordered as:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  x

where the only legal operation is to exchange `x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

 1  2  3  4     1  2  3  4     1  2  3  4     1  2  3  4 
 5  6  7  8     5  6  7  8     5  6  7  8     5  6  7  8
 9  x 10 12     9 10  x 12     9 10 11 12     9 10 11 12
13 14 11 15    13 14 11 15    13 14  x 15    13 14 15  x
            r->            d->            r->

The letters in the previous row indicate which neighbor of the `x' tile is swapped with the `x' tile at each step; legal values are `r',`l',`u' and `d', for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing `x' tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.

Input 

The first line of the input is an integer N, then a blank line followed by N datasets. There is a blank line between datasets.

In each dataset, you will receive a description of a configuration of the 8 puzzle. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus `x'.

For example, this puzzle

1 2 3
x 4 6
7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8

Output 

For each dataset, you will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters `r', `l', `u' and `d' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Print a blank line between datasets.

Sample Input 

1

2 3 4 1 5 x 7 6 8

Sample Output 

ullddrurdllurdruldr

---

懶得用 IDA* 就使用 BFS 建出所有可能吧！
另外加上 hash 讓 map 插入稍微降低一點。

#include <stdio.h>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
#define hash_r 131071
using namespace std;
map<int, string> R[hash_r];
void insert(int state, string& s) {
    R[state%hash_r][state] = s;
}
int find(int state) {
    return R[state%hash_r].find(state) != R[state%hash_r].end();
}
void build_bfs() {
    string step = "";
    int i, j, k, board[3][3];
    int tn, state, ix, iy;
    int tx, ty;
    int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    char dirc[4] = {'l', 'r', 'u', 'd'};
    insert(123456789, step);
    queue<int> Q;
    Q.push(123456789);
    int cnt = 0;
    while(!Q.empty()) {
        cnt++;
        tn = state = Q.front();

        Q.pop();
        for(i = 2; i >= 0; i--) {
            for(j = 2; j >= 0; j--) {
                board[i][j] = tn%10, tn /= 10;
                if(board[i][j] == 9)
                    ix = i, iy = j;
            }
        }/*
        for(i = 0; i < 3; i ++, puts(""))
            for(j = 0; j < 3; j++)
                printf("%d", board[i][j]);
        cout << R[state%hash_r][state] << endl;*/
        for(i = 0; i < 4; i++) {
            tx = ix+dir[i][0], ty = iy+dir[i][1];
            if(tx < 0 || ty < 0 || tx >= 3 || ty >= 3)
                continue;
            swap(board[ix][iy], board[tx][ty]);
            tn = 0;
            for(j = 0; j < 3; j++) {
                for(k = 0; k < 3; k++) {
                    tn = tn*10 + board[j][k];
                }
            }
            if(!find(tn)) {
                step = dirc[i] + R[state%hash_r][state];
                //cout << tn << " " << step << endl;
                insert(tn, step);
                Q.push(tn);
            }
            swap(board[ix][iy], board[tx][ty]);
        }
        //getchar();
    }
    //printf("%d\n", cnt);
}
int main() {
    build_bfs();
    int t, i, x, state;
    char s[2];
    scanf("%d", &t);
    while(t--) {
        state = 0;
        for(i = 0; i < 9; i++) {
            scanf("%s", s);
            if(s[0] == 'x')
                x = 9;
            else
                x = s[0]-'0';
            state = state*10 + x;
        }
        if(find(state))
            cout << R[state%hash_r][state] << endl;
        else
            cout << "unsolvable" << endl;
        if(t)
            cout << endl;
    }
    return 0;
}
/*
luurrdldruuldrdlurd
ullddrurdllurdruldr
*/