Cube

There was once a 3 by 3 by 3 cube built of 27 smaller cubes. It has fallen apart into seven pieces:

Figure 1: The seven pieces that once formed a cube

The seven pieces can be assembled in many ways to again form the cube. Figure 2 shows one of these possibilities. The first square stands for the front plane, the next one for the middle plane and the last one for the back plane of the cube. The letters in
the cells stand for the name of piece filling out the corresponding space in the cube. The name of the seven pieces can be found in figure 1.

Figure 2: Two possibilities of assembling the cube

You are to write a program that outputs all possibilities of assembling the cube but suppress solutions that are mere rotations of another solution.

Hint: Piece a is the only part that, by rotation and translation, cannot be transformed into itself. In order to avoid solutions that are mere rotations of an already found solution, you may restrict transformations
of piece a to translations.

Input 

The input file has several test cases. Each test case indicates the initial position of piece `a'.
You can translate it, but you mustn't rotate it.

Output 

For each solution found, your program should output a line containing the solution as a string. The string is a linearized form of the cube.
Each letter stands for the piece filling out the corresponding space in the cube. It is linearized as follows:

• The string consists of substrings representing the front, middle and back plane.
• Each substring consists of substrings representing the top, middle and bottom row.
• Each row substring consists of letters representing the left, middle and right cell.

The solutions in figure 2 would be represented like this:

adcaccaacddgbfgffedggbfebee
aababbadcffegfcddcfeeggedgc

It is very important that your program uses the naming convention given in figure 1 and linearizes the cube as explained above.

Print a blank line after each test case.

Figure 3: Positions of the cells in the string

Figure 3 again shows how the cells of the cube are linearized.

Sample input 

aa.a..a....................
.........a..a..aa..........

Sample output 

aababbadcggeffcddcgeegfedfc
aababbadceffgdcgdceefedfggc
...
aababbadcffegfcddcfeeggedgc

adcaccaacfddfebgeeffdggbgeb
...

解题思路：这道题只是将平面上的俄罗斯方块搬到了空间上， 很简单的回溯思想，难点在于怎么样获得每种方块的立体坐标，而且每一种的立体坐标不止一种。

<1>首先，对与一个9 * 9立方体，摆放方式有24种（对于一个顶点来说，将该定点放在左上角固定，将有三种方法， 正方体有8个定点， 3 * 8 = 24），然后根据立方体的标号规律，可以写出24个面的序号，用于生成方块的旋转坐标（这点很重要，如果刚开始旋转坐标就求错了，后面会改个半死），具体看代码。

<2>得到24个面的序列之后，可以根据这24个面的序列求的每个立方体的旋转坐标（只要记录每个点与第一个点的关系就可以了），因为没个方块只能使用一次，所以要将一个方块的旋转看成一类。

前面两点可以放在循环的外面操作，因为对于任意一组数据都是可用的（记住不用求方块1），切记坐标不要手写，如果你可以保证将几十种三维坐标写的一点都没有错的话，你可以尝试一下。

<3>最后一点就是普通的回溯问题了， 只是换成三维的了。

剪枝：<1>当一个坐标找不到合适的方块是，回溯。

<2>每次DFS都要先找到未填充的位置，在进行判断（不要用递归去写这里，层数较多）

#include <stdio.h>
#include <string.h>

const int N = 30;
const int number[8] = {0, 4, 3, 4, 4, 4, 4, 4};	// 各个block的木块组成。
int p[N][N];	// 24面序列储存。

struct coor {
    int x[20];
    int y[20];
    int z[20];
    coor() {
        memset(x, 0, sizeof(x));
        memset(y, 0, sizeof(y));
        memset(z, 0, sizeof(z));
    }
};

struct block {
    int cnt;
    coor dir[20];
}blo[10];

////////////////////////////////////////////////////////////////////////////
//////			      数据处理				      //////

void get_seq(int cur, int now, int a, int b, int c) {	//打印单一面的序列。
    for (int k = 0; k < 3; k++)
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                p[cur][k * 9 + i * 3 + j] = now + c * k + b * i + j * a - 1;
}

void build_seq() {  // 打印24面的序列。
    int top[8] = {1, 3, 7, 9, 19, 21, 25, 27};
    int num[8][3] = { {1, 3, 9}, {3, -1, 9}, {-3, 1, 9}, {-1, -3, 9}, {3, 1, -9}, {-1, 3,-9}, {1, -3, -9}, {-3, -1, -9}};
    
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 3; j++)
            get_seq(i * 3 + j, top[i], num[i][j % 3], num[i][(j + 1) % 3], num[i][(j + 2) % 3]);
}

bool is_some_dir(int cur, int a, int b) {
    int bo[5] = {0};
    for (int i = 0; i < number[cur]; i++) {
        int k = 0;
        for (int j = 0; j < number[cur]; j++) {
            if (bo[j])	continue;
            if (blo[cur].dir[a].x[i] == blo[cur].dir[b].x[j] && blo[cur].dir[a].y[i] == blo[cur].dir[b].y[j] && blo[cur].dir[a].z[i] == blo[cur].dir[b].z[j] ) {
                bo[j] = 1;
                k = 1;
		break;
            }
        }
        if (!k)
            return false;
    }
    return true;
}

bool is_some_blo(int cur, int cas) {
    for (int i = 0; i < cas; i++)
        if (is_some_dir(cur, i, cas))
            return true;
    return false;
}

int get_block(int num[], int cur) { // 对于一个block进行24面转向判断。
    int cas = 0, f = 1;
    for (int t  = 0; t < 24; t++) {
	int ok = 0, a, b, c;
	for (int k = 0; k < 3; k++)
	    for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++) {
		    if (num[p[t][k * 9 + i * 3 + j]]) {
			if (ok) {
			    blo[cur].dir[cas].x[f] = i - a;
			    blo[cur].dir[cas].y[f] = j - b;
			    blo[cur].dir[cas].z[f] = k - c;
			    f++;
			}
			else {
			    ok = f = 1;
			    a = i, b = j, c = k;
			}
		    }
		}
	if (is_some_blo(cur, cas))	continue;
	cas++;
    }
    blo[cur].cnt = cas;
}

void build_block() {	// 获得除了1以外的所有block的转向值。
    int num[8][27] = { {0}, {0}, {1, 1, 0, 0, 1}, {1, 1, 1, 0, 1}, {1, 0, 0,1, 1, 0, 0, 1}, {1, 1, 0, 1, 0, 0, 0, 0, 0, 1}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1 }, {1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1} };

    for (int i = 2; i < 8; i++)
	get_block(num[i], i);
}

////////////////////////////////////////////////////////////////////////////

const int MANX = 1000;
const int R = 3;
int vis[N];
char str[MANX];

void handle(char str[]) {
    int ok = 0, cas = 1, a, b, c;
    for (int k = 0; k < R; k++)
	for (int i = 0; i < R; i++)
	    for (int j = 0; j < R; j++)
		if (str[k * 9 + i * 3 + j] == 'a') {
		    if (ok) {
			blo[1].dir[0].x[cas] = i - a;
			blo[1].dir[0].y[cas] = j - b;
			blo[1].dir[0].z[cas] = k - c;
			cas++;
		    }
		    else {
			ok = cas = 1;
			a = i, b = j, c = k;
		    }
		}
    blo[1].cnt = 1;
}

bool judge_take(coor cur, int x, int y, int z, int n) {
    for (int i = 0; i < n; i++) {
	if (cur.x[i] + x < 0 || cur.x[i] + x >= R)  return true;
	if (cur.y[i] + y < 0 || cur.y[i] + y >= R)  return true;
	if (cur.z[i] + z < 0 || cur.z[i] + z >= R)  return true;
	if (str[(cur.z[i] + z) * 9 + (cur.x[i] + x) * 3 + cur.y[i] + y] != '\0')
	    return true;
    }
    return false;
}

void take(coor cur, int x, int y, int z, int n) {
    for (int i = 0; i < number[n]; i++)
	str[(cur.z[i] + z) * 9 + (cur.x[i] + x) * 3 + cur.y[i] + y] = n + 'a' - 1;
}

void clear(coor cur, int x, int y, int z, int n) {
    for (int i = 0; i < n; i++)
	str[(cur.z[i] + z) * 9 + (cur.x[i] + x) * 3 + cur.y[i] + y] = '\0';
}

void dfs(int x, int y, int z, int sum) {
    if (sum == 7) {
	puts(str);
	return ;
    }

    while (1) {
	if (y >= 3) {
	    x++;
	    y = 0;
	}

	if (x >= 3) {
	    z++;
	    x = 0;
	}

	if (str[z * 9 + x * 3 + y] != '\0')
	    y++;
	else
	    break;
    }

    for (int cur = 1; cur < 8; cur++) {
	if (vis[cur])   continue;
	vis[cur] = 1;

	for (int now = 0; now < blo[cur].cnt; now++) {
	    if (judge_take(blo[cur].dir[now], x, y, z, number[cur]))    continue;
	    take(blo[cur].dir[now], x, y, z, cur);
	    dfs(x, y + 1, z, sum + 1);
	    clear(blo[cur].dir[now], x, y, z, number[cur]);
	}

	vis[cur] = 0;
    }
}

int main() {
    // 数据准备。
    memset(blo, 0, sizeof(blo));
    build_seq();
    build_block();

    while (gets(str) != NULL) {
	handle(str);
	memset(vis, 0, sizeof(vis));
	memset(str, 0, sizeof(str));

	dfs(0, 0, 0, 0);

	printf("\n");
    }
    return 0;}