# Commits

committed 134e4ec

add PHASE enums, move some code from solve() to begin_phase2()

• Participants
• Parent commits aa8e012

# File solve.c

` #include "cubeutils.h"`
` `
` #define TABLES_PATH ".tables"`
`-`
`+enum { PHASE1 = 0, PHASE2 = 1 };`
` /*`
`  * index  : 0   1   2   3   4   5   6   7   8    9  10  11`
`  * value  : 1   2   3   4   5   6   7   8   9   10  11  12`
` 		for (face = 0; face < 6; face++) {`
` 			set_coord(i);`
` 			do_move(face * 3);`
`-			if (phase && face > 1) /* only want double turns on F, B, R, L in G1 */`
`+			if (phase == PHASE2 && face > 1) /* only want double turns on F, B, R, L in G1 */`
` 				do_move(face * 3);`
` 			trans_table[i][face] = get_coord();`
` 		}`
` void init_trans_tables(void)`
` {`
` 	if (verbose) { printf("Initializing phase 1 transition tables..."); fflush(stdout); }`
`-	init_trans(0, eo_trans,  2048,  set_eo_coord,  get_eo_coord );`
`-	init_trans(0, co_trans,  2187,  set_co_coord,  get_co_coord );`
`-	init_trans(0, ud1_trans,  495,  set_ud1_coord, get_ud1_coord);`
`+	init_trans(PHASE1, eo_trans,  2048,  set_eo_coord,  get_eo_coord );`
`+	init_trans(PHASE1, co_trans,  2187,  set_co_coord,  get_co_coord );`
`+	init_trans(PHASE1, ud1_trans,  495,  set_ud1_coord, get_ud1_coord);`
` 	if (verbose) printf("done\n");`
` `
` 	if (verbose) { printf("Initializing phase 2 transition tables..."); fflush(stdout); }`
`-	init_trans(1, cp_trans,  40320, set_cp_coord,  get_cp_coord );`
`-	init_trans(1, ep_trans,  40320, set_ep_coord,  get_ep_coord );`
`-	init_trans(1, ud2_trans,    24, set_ud2_coord, get_ud2_coord);`
`+	init_trans(PHASE2, cp_trans,  40320, set_cp_coord,  get_cp_coord );`
`+	init_trans(PHASE2, ep_trans,  40320, set_ep_coord,  get_ep_coord );`
`+	init_trans(PHASE2, ud2_trans,    24, set_ud2_coord, get_ud2_coord);`
` 	if (verbose) printf("done\n");`
` }`
` `
` 			coordi = trans_tablei[coordi][face];`
` 			coordj = trans_tablej[coordj][face];`
` 			init_prune(phase, coordi, trans_tablei, coordj, trans_tablej, maxi, maxj, prune_table, mdepth, depth + 1, last);`
`-			if (phase && face > 1) /* only want double turns on F, B, R, L in G1 */`
`+			if (phase == PHASE2 && face > 1) /* only want double turns on F, B, R, L in G1 */`
` 				break;`
` 		}`
` 	}`
` 	memset(epud2_prune, 0xff, sizeof(epud2_prune));`
` `
` 	if (verbose) { printf("Initializing phase 1 pruning tables..."); fflush(stdout); }`
`-	init_prune(0, 0, co_trans, 0, eo_trans, 2187, 2048, coeo_prune, 10, 0, -1);`
`-	init_prune(0, 0, co_trans, 0, ud1_trans, 2187, 495, coud1_prune, 10, 0, -1);`
`-	init_prune(0, 0, eo_trans, 0, ud1_trans, 2048, 495, eoud1_prune, 10, 0, -1);`
`+	init_prune(PHASE1, 0, co_trans, 0, eo_trans, 2187, 2048, coeo_prune, 10, 0, -1);`
`+	init_prune(PHASE1, 0, co_trans, 0, ud1_trans, 2187, 495, coud1_prune, 10, 0, -1);`
`+	init_prune(PHASE1, 0, eo_trans, 0, ud1_trans, 2048, 495, eoud1_prune, 10, 0, -1);`
` 	if (verbose) printf("done\n");`
` `
` 	if (verbose) { printf("Initializing phase 2 pruning tables..."); fflush(stdout); }`
`-	init_prune(1, 0, cp_trans, 0, ud2_trans, 40320, 24, cpud2_prune, 15, 0, -1);`
`-	init_prune(1, 0, ep_trans, 0, ud2_trans, 40320, 24, epud2_prune, 13, 0, -1);`
`+	init_prune(PHASE2, 0, cp_trans, 0, ud2_trans, 40320, 24, cpud2_prune, 15, 0, -1);`
`+	init_prune(PHASE2, 0, ep_trans, 0, ud2_trans, 40320, 24, epud2_prune, 13, 0, -1);`
` 	if (verbose) printf("done\n");`
` }`
` `
` 	fflush(stdout);`
` }`
` `
`+int begin_phase2(int last)`
`+{`
`+	int i, success;`
`+`
`+	copy_cube(1, co_, eo_, cp_, ep_);`
`+	for (i = 20 - p1_len; i < 20; i++)`
`+		do_move(sol[i]);`
`+`
`+	for (p2_len = 0; (!all_sol && p2_len + p1_len < len) || (all_sol && p2_len + p1_len <= len); p2_len++)`
`+		if ((success = solve(PHASE2, get_ep_coord(), get_cp_coord(), get_ud2_coord(), p2_len, last)))`
`+			break;`
`+	if ((!all_sol && p2_len + p1_len < len) || (all_sol && success && p2_len + p1_len <= len)) {`
`+		len = p2_len + p1_len;`
`+		print_solution();`
`+		num++;`
`+		return (p2_len == 0 || len <= end_len || (num >= num_sol && num_sol));`
`+	}`
`+	return 0;`
`+}`
` /*`
`  * phase solver`
`  */`
` int solve(int phase, int e_coord, int c_coord, int ud_coord, int depth, int last)`
` {`
`-	int i, e_tmp, c_tmp, ud_tmp, face, success;`
`+	int i, e_tmp, c_tmp, ud_tmp, face;`
` `
` 	if (sigtstp || (timeout && num)) return 1;`
`-	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) {// && depth == 0) { /* found a solution at the desired depth */`
`-		if (!phase) { /* we are in the first phase, let's do the second phase */`
`-			if (depth != 0) return 0;`
`-			copy_cube(1, co_, eo_, cp_, ep_);`
`-			for (i = 20 - p1_len; i < 20; i++)`
`-				do_move(sol[i]);`
`-`
`-			for (p2_len = 0; (!all_sol && p2_len + p1_len < len) || (all_sol && p2_len + p1_len <= len); p2_len++)`
`-				if ((success = solve(1, get_ep_coord(), get_cp_coord(), get_ud2_coord(), p2_len, last)))`
`-					break;`
`-			if ((!all_sol && p2_len + p1_len < len) || (all_sol && success && p2_len + p1_len <= len)) {`
`-				len = p2_len + p1_len;`
`-				print_solution();`
`-				num++;`
`-				return (p2_len == 0 || len <= end_len || (num >= num_sol && num_sol));`
`-			}`
`-			return 0;`
`-		} else { /* we are in the second phase, we have a full solution, success! */`
`-			return 1;`
`-		}`
`+	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) { /* found a solution */`
`+		if (phase == PHASE2) return 1;`
`+		else if (depth != 0) return 0;`
`+		else return begin_phase2(last);`
` 	}`
`-	if (!phase && (depth == 0 || coeo_prune[c_coord][e_coord] > depth || coud1_prune[c_coord][ud_coord] > depth || eoud1_prune[e_coord][ud_coord] > depth)) return 0;`
`-	if ( phase && (depth == 0 || cpud2_prune[c_coord][ud_coord] > depth || epud2_prune[e_coord][ud_coord] > depth)) return 0;`
`+	if (phase == PHASE1 && (depth == 0 || coeo_prune [c_coord][e_coord ] > depth || coud1_prune[c_coord][ud_coord] > depth || eoud1_prune[e_coord][ud_coord] > depth)) return 0;`
`+	if (phase == PHASE2 && (depth == 0 || cpud2_prune[c_coord][ud_coord] > depth || epud2_prune[e_coord][ud_coord] > depth)) return 0;`
` `
` 	for (face = 0; face < 6; face++) {`
` 		/* no two moves in a row on same face, no move on same axis after U, F, R */`
` 		ud_tmp = ud_coord;`
` `
` 		for (i = 0; i < 3; i++) {`
`-			e_tmp  = phase ? ep_trans [e_tmp ][face] : eo_trans [e_tmp ][face];`
`-			c_tmp  = phase ? cp_trans [c_tmp ][face] : co_trans [c_tmp ][face];`
`-			ud_tmp = phase ? ud2_trans[ud_tmp][face] : ud1_trans[ud_tmp][face];`
`+			e_tmp  = (phase == PHASE1) ? eo_trans [e_tmp ][face] : ep_trans [e_tmp ][face];`
`+			c_tmp  = (phase == PHASE1) ? co_trans [c_tmp ][face] : cp_trans [c_tmp ][face];`
`+			ud_tmp = (phase == PHASE1) ? ud1_trans[ud_tmp][face] : ud2_trans[ud_tmp][face];`
` `
`-			if (!phase) sol[20 - depth] = face * 3 + i;`
`-			else        sol[38 - depth] = face * 3 + ((face > 1) ? 1 : i);`
`+			if (phase == PHASE1) sol[20 - depth] = face * 3 + i;`
`+			else                 sol[38 - depth] = face * 3 + ((face > 1) ? 1 : i);`
` `
` 			if (solve(phase, e_tmp, c_tmp, ud_tmp, depth - 1, face)) return 1;`
`-			if (phase && face > 1) break;`
`+			if (phase == PHASE2 && face > 1) break;`
` 		}`
` 	}`
` 	return 0;`
` 		if (iv.it_value.tv_sec || iv.it_value.tv_usec)`
` 			setitimer(ITIMER_VIRTUAL, &iv, NULL);`
` `
`-		for (p1_len = 0; p1_len <= len && solve(0, get_eo_coord(), get_co_coord(), get_ud1_coord(), p1_len, -1) == 0; p1_len++) {`
`+		for (p1_len = 0; p1_len <= len; p1_len++) {`
`+			if (solve(PHASE1, get_eo_coord(), get_co_coord(), get_ud1_coord(), p1_len, -1))`
`+				break;`
` 			if (verbose) printf("finished phase 1 search depth %d\n", p1_len);`
` 			copy_cube(1, co_, eo_, cp_, ep_);`
` 		}`