Commits

Anonymous committed 3a80f17

first attempt at optimal 2x2x2 solver, will test and continue when cubeutils for 2x2x2 exist

Comments (0)

Files changed (1)

stand_alone/2_solve.c

+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+char *names[] = { "UFRUF", "URBUR", "UBLUB", "ULFUL", "DRFDR", "DFLDF", "DLBDL", "DBRDB" };
+/*
+ * index  : 0   1   2   3   4   5   6   n/a
+ * corners: UFR URB UBL ULF DRF DFL DLB DBR
+ */
+char cp[7],             co[7];
+char cp_prune[5040],    co_prune[729];
+int  cp_trans[5040][3], co_trans[729][3];
+
+/*
+ * moves are:
+ * U U2 U' F F2 F' L L2 L'
+ * 0 1  2  3 4  5  6 7  8
+ */
+int sol[11];
+
+char c_cycles[6][4] = {
+	{ 0, 1, 2, 3 }, // U
+	{ 0, 3, 5, 4 }, // F
+	{ 2, 6, 5, 3 }, // L
+};
+char c_twists[6][4] = {
+	{ 0, 0, 0, 0 }, // U
+	{ 2, 1, 2, 1 }, // F
+	{ 1, 2, 1, 2 }, // L
+};
+
+/*
+ * perform the permutation cycle 1 - 3 times based on move
+ * perform the orientation twists on the cubies that are being cycled
+ */
+void move_pieces(char *perm, char *orie, char *cycle, char *twist, int mod)
+{
+	char otmp, ptmp, i;
+
+	ptmp = perm[cycle[0]];
+	otmp = orie[cycle[0]];
+	for (i = 0; i < 3; i++) {
+		orie[cycle[i]] = (orie[cycle[i + 1]] + twist[i + 1]) % mod;
+		perm[cycle[i]] =  perm[cycle[i + 1]];
+	}
+	orie[cycle[3]] = (otmp + twist[0]) % mod;
+	perm[cycle[3]] =  ptmp;
+}
+
+/*
+ * perform the given move on the array cube
+ */
+void do_move(int mv)
+{
+	int face = mv / 3;
+
+	for (mv = mv % 3 + 1; mv; mv--)
+		move_pieces(cp, co, c_cycles[face], c_twists[face], 3);
+}
+
+/*
+ * coordinate functions
+ *
+ * the oriention and permuation functions are based on descirptions at http://www.jaapsch.net/puzzles/compindx.htm
+ *
+ * the get functions return the coordinate for the current state of the array cube
+ * the set functions set the current state of the array cube to the given coordinate
+ */
+
+/*
+ * orientation coordinate
+ */
+void set_co_coord(int coord)
+{
+	int i, s = 0, len = sizeof(co);
+
+	for (i = len - 2; i >= 0; i--) {
+		co[i] = coord % 3;
+		s = (s - co[i] + 3) % 3;
+		coord /= 3;
+	}
+	co[len - 1] = s;
+}
+
+int get_co_coord(void)
+{
+	int i, coord = 0, len = sizeof(co);
+
+	for (i = 0; i < len - 1; i++)
+		coord = coord * 3 + co[i];
+
+	return coord;
+}
+
+/*
+ * permutation coordinate
+ */
+void set_cp_coord(int coord)
+{
+	int i, j, len = sizeof(co);
+
+	cp[len - 1] = 1;
+
+	for (i = len - 2; i >= 0; i--) {
+		cp[i] = (coord % (len - i)) + 1;
+		coord /= len - i;
+		for (j = i + 1; j < len; j++)
+			if (cp[j] >= cp[i])
+				cp[j]++;
+	}
+}
+
+int get_cp_coord(void)
+{
+	int i, j, coord = 0, len = sizeof(co);
+
+	for (i = 0; i < len - 1; i++) {
+		coord *= (len - i);
+		for (j = i + 1; j < len; j++)
+			if (cp[i] > cp[j])
+				coord++;
+	}
+	return coord;
+}
+
+/*
+ * generic pruning table initialization
+ */
+void init_prune(int coord, char prune_table[], int trans_table[][3], int mdepth, int depth, int last)
+{
+	int i, mv, old = coord;
+
+	if (depth == mdepth || prune_table[coord] <= depth)
+		return;
+
+	prune_table[coord] = depth;
+
+	for (mv = 0; mv < 9; mv += 3, coord = old) {
+		if (mv / 3 == last / 3)
+			continue;
+		for (i = 0; i < 3; i++) {
+			coord = trans_table[coord][mv / 3];
+			init_prune(coord, prune_table, trans_table, mdepth, depth + 1, mv);
+		}
+	}
+}
+
+/*
+ * specific pruning table initializations
+ */
+void init_prune_tables(void)
+{
+	memset(cp_prune,  127, sizeof(cp_prune ));
+	memset(co_prune,  127, sizeof(co_prune ));
+
+	init_prune(0, cp_prune, cp_trans, 8, 0, -1);
+	init_prune(0, co_prune, co_trans, 7, 0, -1);
+}
+
+/*
+ * generic transition table initialization
+ */
+void init_trans(int tran_table[][3], int len, void (*set_coord)(int), int (*get_coord)(void))
+{
+	int i, mv;
+
+	for (i = 0; i < len; i++) {
+		for (mv = 0; mv < 9; mv += 3) {
+			set_coord(i);
+			do_move(mv);
+			tran_table[i][mv / 3] = get_coord();
+		}
+	}
+}
+
+/*
+ * specific transition table initializations
+ */
+void init_trans_tables(void)
+{
+	init_trans(cp_trans, 5040, set_cp_coord,  get_cp_coord );
+	init_trans(co_trans,  729, set_co_coord,  get_co_coord );
+}
+
+/*
+ * solve
+ */
+int solve(int cp_coord, int co_coord, int depth, int last)
+{
+	int mv, i, cp_tmp, co_tmp, face;
+
+	if (cp_coord == 0 && co_coord == 0) return 1; // success!
+	if (depth == 0 || cp_prune[cp_coord] > depth || co_prune[co_coord] > depth) return 0;
+
+	for (mv = face = 0; mv < 9; mv += 3, face = mv / 3) {
+		// no two moves in a row on same face, no move on same axis after U, F, R
+		if (face == last)
+			continue;
+
+		cp_tmp  = cp_coord;
+		co_tmp  = co_coord;
+
+		for (i = 0; i < 3; i++) {
+			cp_tmp  = cp_trans[cp_tmp ][face];
+			co_tmp  = co_trans[co_tmp ][face];
+
+			if (solve(cp_tmp, co_tmp, depth - 1, face)) {
+				sol[depth] = mv + i;
+				return 1;
+			}
+		}
+	}
+	return 0;
+}
+
+void print_move(int mv)
+{
+	char *faces = "UFL", *num = " 2'";
+
+	printf("%c%c ", faces[mv / 3], num[mv % 3]);
+}
+
+/*
+ * set array cube from input
+ */
+void set_cube(char *cube)
+{
+	char *p, *t, i, j;
+
+	for (i = 0, p = strtok(cube, " \n"); p && i < 7; i++, p = strtok(NULL, " \n")) {
+		for (j = 0; (t = strstr(names[j], p)) == NULL; j++)
+			;
+		cp[i] = j;
+		co[i] = t - names[j];
+	}
+
+	if (strcmp(p, "DBR")) {
+		fprintf(stderr, "Must orient cube with DBR in DBR\n");
+		exit(EXIT_FAILURE);
+	}
+}
+
+int main(int argc, char **argv)
+{
+	char buf[128];
+	int i, md;
+
+	init_trans_tables();
+	init_prune_tables();
+
+	while (fgets(buf, sizeof(buf), stdin)) {
+		memset(sol, -1, sizeof(sol));
+		set_cube(buf);
+
+		for (i = 0; solve(get_cp_coord(), get_co_coord(), i, -1) == 0; i++)
+			;
+
+		for (i = 10; i >=0; i--)
+			if (sol[i] > -1)
+				print_move(sol[i]);
+
+		printf("\n");
+	}
+	return 0;
+}
+
+/* vim: set ts=4 sw=4 noexpandtab : */