#include #include /*************************************************************/ /* rotate solution begin */ /*************************************************************/ typedef struct { int x; int y; int z; } pos_t; void normalize(pos_t *p, pos_t *out, int *norm) { int i; int dx; int dy; int dz; int cur; /* we need to rotate/translate for points norm[0,1,2] to be at their * position, but we won't solve the matrix. Instead we do it piece by * piece. First translation, then three rotations. */ /* translation to (0,0,0) for point norm[0] */ cur = norm[0]; dx = -p[cur].x; dy = -p[cur].y; dz = -p[cur].z; for (i = 0; i < 27; i++) { out[i].x = p[i].x + dx; out[i].y = p[i].y + dy; out[i].z = p[i].z + dz; } /* rotation centered at (0,0,0) to (0,0,1) for point norm[1] */ cur = norm[1]; /* let's not get the matrix, do it coordinate by coordinate */ if (out[cur].x) { /* pi/2 around z: (x,y,z) goes to (-y,x,z) */ int nx, ny; for (i = 0; i < 27; i++) { nx = -out[i].y; ny = out[i].x; out[i].x = nx; out[i].y = ny; } } if (out[cur].y) { /* pi/2 around x: (x,y,z) goes to (x,z,-y) */ int ny, nz; for (i = 0; i < 27; i++) { ny = out[i].z; nz = -out[i].y; out[i].y = ny; out[i].z = nz; } } if (out[cur].z == -1) { /* pi around y: (x,y,z) goes to (-x,y,-z) */ int nx, nz; for (i = 0; i < 27; i++) { nx = -out[i].x; nz = -out[i].z; out[i].x = nx; out[i].z = nz; } } /* point norm[2] is now at (1,0,1) or (0,1,1) or (-1,0,1) or (0,-1,1) */ /* find the rotation that puts it at (0,1,1) */ //x+iy * a+ib = x*a-y*b x*b+y*a //x+iy * a+ib = 0 1 // x*a-y*b = 0 // x*b+y*a = 1 // x*y*a-y*y*b = 0 // x*x*b+x*y*a = x // b*(x*x+y*y) = x // b = x / (x*x+y*y) // a = b*y/x or a = 1/y cur = norm[2]; int x = out[cur].x; int y = out[cur].y; int a, b; /* we simplify, x is -1 or 1, so x = 1/x, same for y */ a = y; b = x; int nx, ny; for (i = 0; i < 27; i++) { nx = out[i].x * a - out[i].y * b; ny = out[i].x * b + out[i].y * a; out[i].x = nx; out[i].y = ny; } /* now move things to 0..2 for all dimensions */ int minx = out[0].x; int miny = out[0].y; int minz = out[0].z; for (i = 1; i < 27; i++) { if (out[i].x < minx) minx = out[i].x; if (out[i].y < miny) miny = out[i].y; if (out[i].z < minz) minz = out[i].z; } for (i = 0; i < 27; i++) { out[i].x -= minx; out[i].y -= miny; out[i].z -= minz; } } void pos_to_piece(pos_t *pos, int *pieces) { int i; int j; for (i = 0; i < 7; i++) { /* first piece: 3 small cubes, the others: 4 small cubes */ int n = i ? 4 : 3; int v = 0; for (j = 0; j < n; j++) { int x = pos->x; int y = pos->y; int z = pos->z; v |= 1 << (x * 9 + y * 3 + z); pos++; } pieces[i] = v; } } void rotate(pos_t *pos, int *pieces) { pos_t pos_rotated[27]; int normalize_points[3] = { 3, 4, 5 }; normalize(pos, pos_rotated, normalize_points); pos_to_piece(pos_rotated, pieces); } /*************************************************************/ /* rotate solution end */ /*************************************************************/ int solutions[480][7]; pos_t solutions_small_cubes[480][27]; int symmetry[480]; #define X_AXIS 0 #define Y_AXIS 1 #define Z_AXIS 2 void symmetrize(pos_t *p1, pos_t *p2, int axis) { /* this s[] array permutes pieces 5 and 7 */ int s[27] = { 0, 1, 2, /* piece 1 */ 3, 4, 5, 6, /* piece 2 */ 7, 8, 9, 10, /* piece 3 */ 11, 12, 13, 14, /* piece 4 */ 23, 24, 25, 26, /* piece 5 */ /* -> piece 7 */ 19, 20, 21, 22, /* piece 6 */ 15, 16, 17, 18 /* piece 7 */ /* -> piece 5 */ }; int i; for (i = 0; i < 27; i++) { int j = s[i]; switch (axis) { case X_AXIS: p2[j].x = 2 - p1[i].x; p2[j].y = p1[i].y; p2[j].z = p1[i].z; break; case Y_AXIS: p2[j].x = p1[i].x; p2[j].y = 2 - p1[i].y; p2[j].z = p1[i].z; break; case Z_AXIS: p2[j].x = p1[i].x; p2[j].y = p1[i].y; p2[j].z = 2 - p1[i].z; break; } } } void compute_symmetry(int i, int axis) { pos_t pos_symmetry[27]; int pieces_symmetry[7]; int j; symmetrize(solutions_small_cubes[i], pos_symmetry, axis); #if 0 pieces_symmetry[0] = symmetrize(solutions[i][0], axis); pieces_symmetry[1] = symmetrize(solutions[i][1], axis); pieces_symmetry[2] = symmetrize(solutions[i][2], axis); pieces_symmetry[3] = symmetrize(solutions[i][3], axis); pieces_symmetry[4] = symmetrize(solutions[i][6], axis); /* piece 7 -> 5 */ pieces_symmetry[5] = symmetrize(solutions[i][5], axis); pieces_symmetry[6] = symmetrize(solutions[i][4], axis); /* piece 5 -> 7 */ #endif /* we need to go to the canonical position! */ rotate(pos_symmetry, pieces_symmetry); /* look for the symmetrical solution, it has to exist! */ for (j = 0; j < 480; j++) { int k; for (k = 0; k < 7; k++) if (solutions[j][k] != pieces_symmetry[k]) break; if (k == 7) { symmetry[i] = j; break; } } if (j == 480) { fprintf(stderr, "what? no symmetry found for solution %d?\n", i); exit(1); } } void read_solutions(void) { int i; int j; int x; for (i = 0; i < 480; i++) { for (j = 0; j < 27; j++) { if (scanf("%d", &x) != 1) { fprintf(stderr, "error\n"); exit(1); } solutions_small_cubes[i][j].x = x; if (scanf("%d", &x) != 1) { fprintf(stderr, "error\n"); exit(1); } solutions_small_cubes[i][j].y = x; if (scanf("%d", &x) != 1) { fprintf(stderr, "error\n"); exit(1); } solutions_small_cubes[i][j].z = x; } scanf(" +"); for (j = 0; j < 7; j++) { if (scanf("%x", &x) != 1) { fprintf(stderr, "error\n"); exit(1); } solutions[i][j] = x; } } } void check_symmetry(int i) { int j = symmetry[i]; if (symmetry[j] != i) { fprintf(stderr, "uh oh, symmetry fails!\n"); exit(1); } } int main(void) { int i; read_solutions(); /* verify with X axis */ fprintf(stderr, "x\n"); for (i = 0; i < 480; i++) compute_symmetry(i, X_AXIS); for (i = 0; i < 480; i++) check_symmetry(i); /* verify with Y axis */ fprintf(stderr, "y\n"); for (i = 0; i < 480; i++) compute_symmetry(i, Y_AXIS); for (i = 0; i < 480; i++) check_symmetry(i); /* verify with Z axis */ fprintf(stderr, "z\n"); for (i = 0; i < 480; i++) compute_symmetry(i, Z_AXIS); for (i = 0; i < 480; i++) check_symmetry(i); /* let's print the 240 unique solutions */ for (i = 0; i < 480; i++) { int j; /* we print the solution and we cancel the symmetric solution */ /* if the current solution was cancelled, skip it */ if (symmetry[i] == -1) continue; /* cancel the symmetric solution */ symmetry[symmetry[i]] = -1; /* and print this one */ for (j = 0; j < 7; j++) printf("%x%c", solutions[i][j], j==6 ? '\n' : ' '); } return 0; }