Skip to content

Instantly share code, notes, and snippets.

@jes
Last active January 22, 2018 10:46
Show Gist options
  • Save jes/cd42c4ee8314436e6bb2fb0f4b5dcd8f to your computer and use it in GitHub Desktop.
Save jes/cd42c4ee8314436e6bb2fb0f4b5dcd8f to your computer and use it in GitHub Desktop.
/* magcube solver
* James Stanley 2018
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* uncomment this if you want to find new cube sets instead of using the set I settled on, ... */
//#define FIND_CUBESETS
/* ..., uncomment this if you don't care what the outer faces look like, ... */
//#define IGNORE_OUTER_FACES
/* ..., comment this out if you want to solve for 3C-style outer faces instead of 3R-style outer faces, ... */
#define LOOK_FOR_3R
/* ... and for any other modifications, you'll have to change the code; good luck */
#define X 0
#define Y 1
#define Z 2
#define MAX_CUBE 64
#define face(cube,axis,end) (!! (cube & (1 << (axis*2+end))))
#define _6N 0
#define _6S 1
#define _1N 2
#define _1S 3
#define _2Na 4
#define _2No 5
#define _2Sa 6
#define _2So 7
#define _3C 8
#define _3R 9
#define MAX_CUBE_TYPE 10
/* cubes are represented as 6-bit numbers, where a 0 bit means South and a 1 bit means North
The bits are as follows (LSB at right):
ZzYyXx
*/
int grid[3][3][3];
int type[MAX_CUBE] = {
/* 0 */ _6S, _1N, _1N, _2No, _1N, _2Na, _2Na, _3C,
/* 8 */ _1N, _2Na, _2Na, _3C, _2No, _3C, _3C, _2So,
/* 16 */ _1N, _2Na, _2Na, _3C, _2Na, _3R, _3R, _2Sa,
/* 24 */ _2Na, _3R, _3R, _2Sa, _3C, _2Sa, _2Sa, _1S,
/* 32 */ _1N, _2Na, _2Na, _3C, _2Na, _3R, _3R, _2Sa,
/* 40 */ _2Na, _3R, _3R, _2Sa, _3C, _2Sa, _2Sa, _1S,
/* 48 */ _2No, _3C, _3C, _2So, _3C, _2Sa, _2Sa, _1S,
/* 56 */ _3C, _2Sa, _2Sa, _1S, _2So, _1S, _1S, _6N
};
char *typename[MAX_CUBE_TYPE] = {" 6N", " 6S", " 1N", " 1S", "2Na", "2No", "2Sa", "2So", " 3C", " 3R"};
int avail[MAX_CUBE_TYPE];
int solutions = 0;
int best_score = 0;
int can_place(int cube, int x, int y, int z) {
/* satisfy physical laws */
if (x > 0 && face(grid[z][y][x-1], X, 1) == face(cube, X, 0))
return 0;
if (y > 0 && face(grid[z][y-1][x], Y, 1) == face(cube, Y, 0))
return 0;
if (z > 0 && face(grid[z-1][y][x], Z, 1) == face(cube, Z, 0))
return 0;
#ifdef IGNORE_OUTER_FACES
return 1;
#endif
#ifdef LOOK_FOR_3R
/* consistent faces (3R) */
if (x == 0 && (face(cube, X, 0) != 0))
return 0;
if (x == 2 && (face(cube, X, 1) != 1))
return 0;
if (y == 0 && (face(cube, Y, 0) != 0))
return 0;
if (y == 2 && (face(cube, Y, 1) != 1))
return 0;
if (z == 0 && (face(cube, Z, 0) != 0))
return 0;
if (z == 2 && (face(cube, Z, 1) != 1))
return 0;
#else
/* consistent faces (3C) */
if (x == 0 && (face(cube, X, 0) != 1))
return 0;
if (x == 2 && (face(cube, X, 1) != 1))
return 0;
if (y == 0 && (face(cube, Y, 0) != 0))
return 0;
if (y == 2 && (face(cube, Y, 1) != 1))
return 0;
if (z == 0 && (face(cube, Z, 0) != 0))
return 0;
if (z == 2 && (face(cube, Z, 1) != 0))
return 0;
#endif
return 1;
}
void dfs(int x, int y, int z) {
int cube;
if (z == 3) {
int i;
int count[MAX_CUBE_TYPE];
int score = 0;
solutions++;
if (solutions % 100000 == 0)
printf("%d solutions\n", solutions);
for (i = 0; i < MAX_CUBE_TYPE; i++)
count[i] = 0;
for (z = 0; z < 3; z++) {
for (y = 0; y < 3; y++) {
for (x = 0; x < 3; x++) {
count[type[grid[z][y][x]]]++;
}
}
}
for (i = 0; i < MAX_CUBE_TYPE; i++) {
score += 100 - fabs(count[i] - 2.7f);
}
if (score >= best_score) {
best_score = score;
for (z = 0; z < 3; z++) {
for (y = 0; y < 3; y++) {
for (x = 0; x < 3; x++) {
printf("%2d (%s) ", grid[z][y][x], typename[type[grid[z][y][x]]]);
}
printf("\n");
}
printf("--\n");
}
for (i = 0; i < MAX_CUBE_TYPE; i++)
printf("%d x %s\n", count[i], typename[i]);
printf("Score = %d\n", score);
printf("---------\n\n");
}
return;
}
int nx = x;
int ny = y;
int nz = z;
nx++;
if (nx == 3) {
nx = 0;
ny++;
if (ny == 3) {
ny = 0;
nz++;
}
}
for (cube = 0; cube < MAX_CUBE; cube++) {
if (!avail[type[cube]])
continue;
if (!can_place(cube, x, y, z))
continue;
grid[z][y][x] = cube;
avail[type[cube]]--;
dfs(nx, ny, nz);
avail[type[cube]]++;
}
}
int main() {
int i;
#ifdef FIND_CUBESETS
for (i = 0; i < MAX_CUBE_TYPE; i++)
avail[i] = 27;
#else
for (i = 0; i < MAX_CUBE_TYPE; i++)
avail[i] = 3;
avail[_6N] = 2;
avail[_6S] = 2;
avail[_3R] = 2;
#endif
dfs(0,0,0);
printf("%d solutions found\n", solutions);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment