A program for solving the Mind Jewel puzzle

mind_jewel_solver.cpp

//  mind_jewel_solver.cpp
//  mind_jewel_solver
//
//  Created by James McCartney on 10/14/21.
//

// A program to solve the Mind Jewel puzzle.

#include <vector>
#include <stdio.h>

// This is a list of adjacent faces for a dodecahedon in clockwise order.
// The particular numbering scheme for the faces doesn't really matter.
int adjacent_faces[12][5] = {
	{ 1, 2, 3, 4, 5 },
	{ 0, 5, 8, 7, 2 },
	{ 0, 1, 7, 6, 3 },
	{ 0, 2, 6, 10, 4 },
	{ 0, 3, 10, 9, 5 },
	{ 0, 4, 9, 8, 1 },
	{ 2, 7, 11, 10, 3 },
	{ 1, 8, 11, 6, 2 },
	{ 1, 5, 9, 11, 7 },
	{ 4, 10, 11, 8, 5 },
	{ 3, 6, 11, 9, 4 },
	{ 6, 7, 8, 9, 10 }
};

// Find the next face, by rotating clockwise from the previous face.
int outgoing_face(int prev_face, int cur_face, int rotation) {
	for (int i = 0; i < 5; ++i) { // find the previous face and rotate from there.
		if (adjacent_faces[cur_face][i] == prev_face) {
			int k = (i + rotation) % 5;
			return adjacent_faces[cur_face][k];
		}
	}
	throw -1;
}

// Each pentagonal tile has a number of possible clockwise rotations of the rubber band.
// This assumes starting from the green end.
std::vector<int> availableRotations[12] = {
	{},
	{ 2, 3 },
	{ 1, 2, 3, 4 },
	{ 1, 2, 3 },
	{ 2, 3 },
	{ 2, 3, 4 },
	{ 1, 2, 3, 4 },
	{ 2, 3 },
	{ 2, 3 },
	{ 2, 3 },
	{ 2, 3, 4 },
	{},
};

int faces[12] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int rotations[12] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

int failures = 0;

bool place_tile(int tile, int prev_face, int cur_face) {
	if (tile == 11) {
		printf("success!\n");
		// Print a list of the number of rotations for each tile
		// except for the first and last tile, which have no freedoms.
		// This assumes starting from the green end.
		printf("rotations: ");
		for (int i = 1; i < 11; ++i) {
			if (i > 1) printf(", ");
			printf("%d", rotations[i]);
		}
		printf("\n\n");
		return true;
	}
	
	for (int rotation : availableRotations[tile]) {
		// determine the next face that would be occupied by this rotation.
		int next_face = outgoing_face(prev_face, cur_face, rotation);
		if (faces[next_face] >= 0) {
			// the face is already occupied.
			++failures;
			continue;
		}
		
		faces[next_face] = tile; // mark the face as occupied by the tile.
		rotations[tile] = rotation; // keep track of rotations used.
		place_tile(tile+1, cur_face, next_face); // recurse for next tile.
		faces[next_face] = -1; // mark the face as unoccupied.
	}
	return false;
}

int main(int argc, const char * argv[]) {
	// fill in first two tiles.
	faces[0] = 0;
	faces[1] = 1;
	
	// begin search
	place_tile(1, 0, 1);
	
	printf("failures %d\n", failures);
	
	return 0;
}