solve.c (4931B)
1 #include <stdbool.h> 2 #include <stddef.h> 3 #include <inttypes.h> 4 5 #include "cube.h" 6 #include "coord.h" 7 #include "solve.h" 8 9 static void append_sol(DfsArg *); 10 static bool allowed_next(Move m, Move l0, Move l1); 11 static void get_state(Coordinate *[], Cube *, CubeState *); 12 static int lower_bound(Coordinate *[], CubeState *); 13 static bool trivialshorten(DfsArg *); 14 static void dfs(DfsArg *); 15 static void dfs_niss(DfsArg *); 16 static void dfs_move(Move, DfsArg *); 17 static bool niss_makes_sense(DfsArg *); 18 19 static void 20 append_sol(DfsArg *arg) 21 { 22 Alg alg; 23 int i, n; 24 25 copy_alg(arg->current_alg, &alg); 26 transform_alg(inverse_trans(arg->t), &alg); 27 28 if (arg->st == INVERSE) 29 for (i = 0; i < alg.len; i++) 30 alg.inv[i] = true; 31 32 n = alg_string(&alg, *arg->sol); 33 (*arg->sol)[n] = '\n'; 34 (*arg->sol)[n+1] = 0; 35 *arg->sol += (n+1); 36 } 37 38 static bool 39 allowed_next(Move m, Move l0, Move l1) 40 { 41 bool p, q, allowed, order; 42 43 p = l0 != NULLMOVE && base_move(l0) == base_move(m); 44 q = l1 != NULLMOVE && base_move(l1) == base_move(m); 45 allowed = !(p || (commute(l0, l1) && q)); 46 order = !commute(l0, m) || l0 < m; 47 48 return allowed && order; 49 } 50 51 void 52 get_state(Coordinate *coord[], Cube *cube, CubeState *state) 53 { 54 int i; 55 56 for (i = 0; coord[i] != NULL; i++) 57 state[i].val = index_coord(coord[i], cube, &state[i].t); 58 } 59 60 static int 61 lower_bound(Coordinate *coord[], CubeState *state) 62 { 63 int i, ret; 64 65 ret = -1; 66 for (i = 0; coord[i] != NULL; i++) 67 ret = MAX(ret, ptableval(coord[i], state[i].val)); 68 69 return ret; 70 } 71 72 static bool 73 trivialshorten(DfsArg *arg) 74 { 75 int bound; 76 77 if (!commute(arg->last[0], arg->last[1])) 78 return false; 79 80 dfs_move(inverse_move(arg->last[1]), arg); 81 bound = lower_bound(arg->s->coord, arg->state); 82 dfs_move(arg->last[1], arg); 83 84 return bound == 0; 85 } 86 87 static void 88 dfs(DfsArg *arg) 89 { 90 Move m, last[2]; 91 bool len, niss; 92 int bound; 93 94 bound = lower_bound(arg->s->coord, arg->state); 95 if (arg->st == NISS && !arg->niss) 96 bound = MIN(1, bound); 97 98 if (bound + arg->current_alg->len > arg->d) 99 return; 100 101 if (bound == 0) { 102 len = arg->current_alg->len == arg->d; 103 niss = !(arg->st == NISS) || arg->has_nissed; 104 if (len && niss && !trivialshorten(arg)) 105 append_sol(arg); 106 return; 107 } 108 109 last[0] = arg->last[0]; 110 last[1] = arg->last[1]; 111 arg->last[1] = arg->last[0]; 112 for (m = U; m <= B3; m++) { 113 if (!arg->s->moveset(m)) 114 continue; 115 if (allowed_next(m, last[0], last[1])) { 116 arg->last[0] = m; 117 append_move(arg->current_alg, m, arg->niss); 118 dfs_move(m, arg); 119 dfs(arg); 120 dfs_move(inverse_move(m), arg); 121 arg->current_alg->len--; 122 } 123 } 124 arg->last[0] = last[0]; 125 arg->last[1] = last[1]; 126 127 if (niss_makes_sense(arg)) 128 dfs_niss(arg); 129 } 130 131 static void 132 dfs_niss(DfsArg *arg) 133 { 134 int i; 135 DfsArg newarg; 136 Cube c, newcube; 137 138 newarg.s = arg->s; 139 newarg.t = arg->t; 140 newarg.st = arg->st; 141 newarg.d = arg->d; 142 newarg.sol = arg->sol; 143 newarg.current_alg = arg->current_alg; 144 145 /* Invert current alg and scramble */ 146 newarg.cube = &newcube; 147 148 make_solved(newarg.cube); 149 apply_alg(arg->current_alg, newarg.cube); 150 invert_cube(newarg.cube); 151 152 copy_cube(arg->cube, &c); 153 invert_cube(&c); 154 compose(&c, newarg.cube); 155 156 /* New indexes */ 157 get_state(newarg.s->coord, newarg.cube, newarg.state); 158 159 /* Swap last moves */ 160 for (i = 0; i < 2; i++) { 161 newarg.last[i] = arg->lastinv[i]; 162 newarg.lastinv[i] = arg->last[i]; 163 } 164 165 newarg.niss = true; 166 newarg.has_nissed = true; 167 168 dfs(&newarg); 169 } 170 171 static void 172 dfs_move(Move m, DfsArg *arg) 173 { 174 int i; 175 Move mm; 176 Trans tt = uf; /* Avoid uninitialized warning */ 177 178 for (i = 0; arg->s->coord[i] != NULL; i++) { 179 mm = transform_move(arg->state[i].t, m); 180 arg->state[i].val = move_coord( 181 arg->s->coord[i], mm, arg->state[i].val, &tt); 182 arg->state[i].t = transform_trans(tt, arg->state[i].t); 183 } 184 } 185 186 static bool 187 niss_makes_sense(DfsArg *arg) 188 { 189 Cube testcube; 190 CubeState state[MAX_N_COORD]; 191 bool b1, b2, comm; 192 193 if (arg->niss || !(arg->st == NISS) || arg->current_alg->len == 0) 194 return false; 195 196 make_solved(&testcube); 197 apply_move(inverse_move(arg->last[0]), &testcube); 198 get_state(arg->s->coord, &testcube, state); 199 b1 = lower_bound(arg->s->coord, state) > 0; 200 201 make_solved(&testcube); 202 apply_move(inverse_move(arg->last[1]), &testcube); 203 get_state(arg->s->coord, &testcube, state); 204 b2 = lower_bound(arg->s->coord, state) > 0; 205 206 comm = commute(arg->last[0], arg->last[1]); 207 208 return b1 > 0 && !(comm && b2 == 0); 209 } 210 211 int 212 solve(Step *s, Trans t, int d, SolutionType st, Cube *c, char *sol) 213 { 214 Alg alg; 215 DfsArg arg; 216 217 arg.niss = false; 218 arg.has_nissed = false; 219 arg.last[0] = NULLMOVE; 220 arg.last[1] = NULLMOVE; 221 arg.lastinv[0] = NULLMOVE; 222 arg.lastinv[1] = NULLMOVE; 223 224 alg.len = 0; 225 arg.current_alg = &alg; 226 227 arg.cube = c; 228 arg.s = s; 229 arg.t = t; 230 arg.st = st; 231 232 arg.d = d; 233 arg.sol = / 234 235 if (arg.st == INVERSE) 236 invert_cube(c); 237 apply_trans(arg.t, c); 238 get_state(arg.s->coord, arg.cube, arg.state); 239 240 dfs(&arg); 241 return 0; 242 }