magcube-solve.c

/* 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;
}