Commits

Anonymous committed 7c7384b

faster iterative init_prune for 2x2x2 solver

Comments (0)

Files changed (1)

stand_alone/2_solve.c

 /*
  * generic pruning table initialization
  */
-void init_prune(int coordi, uint16_t trans_tablei[][3], int coordj, uint16_t trans_tablej[][3], int maxi, int maxj, uint8_t prune_table[maxi][maxj], int mdepth, int depth, int last)
+void init_prune(uint16_t trans_tablei[][3], uint16_t trans_tablej[][3], int maxi, int maxj, uint8_t prune_table[maxi][maxj], int mdepth)
 {
-	int k, face, oldi = coordi, oldj = coordj;
+	int d, i, j, k, face;
 
-	if (depth == mdepth + 1 || prune_table[coordi][coordj] <= depth)
-		return;
+	prune_table[0][0] = 0;
 
-	prune_table[coordi][coordj] = depth;
-
-	for (face = 0; face < 3; face++, coordi = oldi, coordj = oldj) {
-		if (face == last) /* don't include turns on the same face as last time */
-			continue;
-		for (k = 0; k < 3; k++) {
-			coordi = trans_tablei[coordi][face];
-			coordj = trans_tablej[coordj][face];
-			init_prune(coordi, trans_tablei, coordj, trans_tablej, maxi, maxj, prune_table, mdepth, depth + 1, last);
+	for (d = 0; d < mdepth; d++) {
+		for (i = 0; i < maxi; i++) {
+			for (j = 0; j < maxj; j++) {
+				if (prune_table[i][j] != d)
+					continue;
+				for (face = 0; face < 3; face++) {
+					int ni = i, nj = j;
+					for (k = 0; k < 3; k++) {
+						ni = trans_tablei[ni][face];
+						nj = trans_tablej[nj][face];
+						if (prune_table[ni][nj] == 0xff)
+							prune_table[ni][nj] = d + 1;
+					}
+				}
+			}
 		}
 	}
 }
 void init_prune_tables(void)
 {
 	memset(cpco_prune, 0xff, sizeof(cpco_prune));
-	init_prune(0, cp_trans, 0, co_trans, 5040, 729, cpco_prune, 11, 0, -1);
+	init_prune(cp_trans, co_trans, 5040, 729, cpco_prune, 11);
 }
 
 void print_move(int mv)