// Copyright 2005 Thomas R. Davis // // This file is part of Soma. // // Soma is free software; you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation; either version 2 of the License, or // (at your option) any later version. // // Soma is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with Soma; if not, write to the Free Software Foundation, // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA #include #include // This code solves the soma cube by fitting the 7 pieces into // a 3x3x3 block. It is done purely by brute force. // Note that this, in a sense, double-counts // the solutions, since every piece is a mirror // image of itself, except that C and D are // mirror images of each other. If the pieces // are painted different colors, there are 480 // solutions; if the same, there are only 240, // since you can mirror any solution and the D // and C cubes swap jobs. // Following are the coordinates for one of // each of the typical blocks. The only thing // that's important here is that the block // have one cube with coordinates (0,0,0). int Apiece[4][3] = { {0, 0, 0}, {0, 0, 0}, {0, 1, 0}, {1, 0, 0} }; int Bpiece[4][3] = { {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {1, 0, 0} }; int Cpiece[4][3] = { {0, 0, 0}, {0, 1, 1}, {0, 1, 0}, {1, 0, 0} }; int Dpiece[4][3] = { {0, 0, 0}, {1, 0, 1}, {0, 1, 0}, {1, 0, 0} }; int Epiece[4][3] = { {0, 0, 0}, {1, 0, 0}, {2, 0, 0}, {1, 1, 0} }; int Fpiece[4][3] = { {0, 0, 0}, {1, 0, 0}, {2, 0, 0}, {2, 1, 0} }; int Gpiece[4][3] = { {0, 0, 0}, {0, 1, 0}, {1, 1, 0}, {1, 2, 0} }; // These arrays hold the encoded positions of // the cubes in a bitmapped way. Bits 0 through // 26 correspond to the locations in a 3x3x3 // cube. They are large since all configurations // are generated, but then sorted and duplicates // are erased later. int Aposns[500]; int Bposns[500]; int Cposns[500]; int Dposns[500]; int Eposns[500]; int Fposns[500]; int Gposns[500]; // counts of piece configurations: int Ac, Bc, Cc, Dc, Ec, Fc, Gc; // These are all the matrices for 3x3x3 // rotations in space generated by the // 90 degree turns. But not reflections. #define M -1 int m[24][3][3] = { {{1,0,0},{0,1,0},{0,0,1}}, {{0,0,1},{0,1,0},{M,0,0}}, {{0,0,1},{0,M,0},{1,0,0}}, {{0,0,1},{1,0,0},{0,1,0}}, {{0,0,1},{M,0,0},{0,M,0}}, {{0,0,M},{0,1,0},{1,0,0}}, {{0,0,M},{0,M,0},{M,0,0}}, {{0,0,M},{1,0,0},{0,M,0}}, {{0,0,M},{M,0,0},{0,1,0}}, {{0,1,0},{0,0,1},{1,0,0}}, {{0,1,0},{0,0,M},{M,0,0}}, {{0,1,0},{1,0,0},{0,0,M}}, {{0,1,0},{M,0,0},{0,0,1}}, {{0,M,0},{0,0,1},{M,0,0}}, {{0,M,0},{0,0,M},{1,0,0}}, {{0,M,0},{1,0,0},{0,0,1}}, {{0,M,0},{M,0,0},{0,0,M}}, {{1,0,0},{0,0,1},{0,M,0}}, {{1,0,0},{0,0,M},{0,1,0}}, {{1,0,0},{0,M,0},{0,0,M}}, {{M,0,0},{0,0,1},{0,1,0}}, {{M,0,0},{0,0,M},{0,M,0}}, {{M,0,0},{0,1,0},{0,0,M}}, {{M,0,0},{0,M,0},{0,0,1}}, }; // for debugging: void sanitycheckrots() { int i, det; for (i = 0; i < 24; i++) { det = m[i][0][0]*m[i][1][1]*m[i][2][2] + m[i][1][0]*m[i][2][1]*m[i][0][2] + m[i][2][0]*m[i][0][1]*m[i][1][2] - m[i][0][0]*m[i][2][1]*m[i][1][2] - m[i][1][0]*m[i][0][1]*m[i][2][2] - m[i][2][0]*m[i][1][1]*m[i][0][2]; if (det != 1) fprintf(stderr, "%d, error!\n", i); } } void rotate(int in[4][3], int out[4][3], int rot) { int i, j, k; for (i = 0; i < 4; i++) { for (j = 0; j < 3; j++) { out[i][j] = 0; for (k = 0; k < 3; k++) out[i][j] += in[i][k]*m[rot][k][j]; } } } // mix: finds a unique number from 0-26 for // a 3-dimensional set of coordinates. int mix(int a, int b, int c) { return a*9 + b*3 + c; } // compares two numbers for qsort int comp(const void *a, const void *b) { if (*(int *)a < *(int *)b) return -1; if (*(int *)a == *(int *)b) return 0; return 1; } // generates all rotations and translations // of a piece. Then it sorts and eliminates // the duplicates. int fillslots(int piece[4][3], int outpiece[500]) { int count = 0; int i, j, k, l, r, ok, last, ind; int out[4][3]; for (r = 0; r < 24; r++) for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) for (k = 0; k < 3; k++) { rotate(piece, out, r); ok = 1; for (l = 0; l < 4; l++) { out[l][0] += i; out[l][1] += j; out[l][2] += k; if (out[l][0]<0 || out[l][0]>2) ok=0; if (out[l][1]<0 || out[l][1]>2) ok=0; if (out[l][2]<0 || out[l][2]>2) ok=0; } if (ok) { outpiece[count] = 0; for (l = 0; l < 4; l++) outpiece[count] |= (1 << mix(out[l][0], out[l][1], out[l][2])); count++; } } qsort(outpiece, count, sizeof(int), comp); // nuke the dups: last = -1; ind = 0; for (i = 0; i < count; i++) if (outpiece[i] != last) { outpiece[ind++] = last = outpiece[i]; } return ind; } int pos[4][3] = { {0, 0, 0}, {1, 0, 0}, {1, 1, 0}, {1, 1, 1} }; // Puts one particular piece, the C piece, in // the only 4 possible positions that are unique // up to rotation. There's no need to treat C // differently, except that this eliminates all // of the symmetrical solutions. Or all but half // of them, depending on whether you think the // mirror images that swap C and D are the same. int fillspecial(int piece[4][3], int outpiece[500]) { int i, j, k, l, count = 0; int out[4][3]; for (i = 0; i < 4; i++) { rotate(piece, out, 0); for (l = 0; l < 4; l++) { out[l][0] += pos[i][0]; out[l][1] += pos[i][1]; out[l][2] += pos[i][2]; } outpiece[count] = 0; for (l = 0; l < 4; l++) outpiece[count] |= (1 << mix(out[l][0], out[l][1], out[l][2])); count++; } return count; } int Cube = 0; // checks to see if a piece fits; if so, it puts it // in and returns 1; otherwise, it returns 0. int load(int a) { if (a & Cube) return 0; Cube = Cube | a; return 1; } // unload nukes a piece from the cube void unload(int a) { Cube = Cube & (~a); } // dumppos dumps a found configuration dumppos(int a, int b, int c, int d, int e, int f, int g) { int i, probe; for (i = 0; i < 27; i++) { probe = 1 << i; if (probe & Aposns[a]) printf("a"); if (probe & Bposns[b]) printf("b"); if (probe & Cposns[c]) printf("c"); if (probe & Dposns[d]) printf("d"); if (probe & Eposns[e]) printf("e"); if (probe & Fposns[f]) printf("f"); if (probe & Gposns[g]) printf("g"); if (i%3 == 2) printf(" "); if (i%9 == 8) printf("\n"); } printf("\n"); } // main looks for all the solutions. The order // of the nesting was chosen to have the largest // sets of possible positions in the inner loops. // For the soma cube this isn't too important, // but it would be for larger puzzles and a // brute-force solution such as this. int main() { // sanitycheckrots(); int a, b, c, d, e, f, g; int solutions = 0; Ac = fillslots(Apiece, Aposns); Bc = fillslots(Bpiece, Bposns); Cc = fillspecial(Cpiece, Cposns); Dc = fillslots(Dpiece, Dposns); Ec = fillslots(Epiece, Eposns); Fc = fillslots(Fpiece, Fposns); Gc = fillslots(Gpiece, Gposns); //printf("%d %d %d %d %d %d %d\n", //Ac, Bc, Cc, Dc, Ec, Fc, Gc); //printf("%x %x %x %x %x %x %x\n", //Aposns[0], Bposns[0], Cposns[0], //Dposns[0], Eposns[0], Fposns[0], Gposns[0]); for (c = 0; c < Cc; c++) { load(Cposns[c]); for (b = 0; b < Bc; b++) { if (0 == load(Bposns[b])) goto labb; for (f = 0; f < Fc; f++) { if (0 == load(Fposns[f])) goto labf; for (d = 0; d < Dc; d++) { if (0 == load(Dposns[d])) goto labd; for (e = 0; e < Ec; e++) { if (0 == load(Eposns[e])) goto labe; for (g = 0; g < Gc; g++) { if (0 == load(Gposns[g])) goto labg; for (a = 0; a < Ac; a++) { if (0 == load(Aposns[a])) goto laba; dumppos(a, b, c, d, e, f, g); solutions++; unload(Aposns[a]); laba:;} unload(Gposns[g]); labg:;} unload(Eposns[e]); labe:;} unload(Dposns[d]); labd:;} unload(Fposns[f]); labf:;} unload(Bposns[b]); labb:;} unload(Cposns[c]); } printf("Total solutions found: %d\n", solutions); }