aboutsummaryrefslogtreecommitdiff
path: root/src/solve.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/solve.c')
-rw-r--r--src/solve.c314
1 files changed, 194 insertions, 120 deletions
diff --git a/src/solve.c b/src/solve.c
index ec16935..ea3b7ae 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -2,155 +2,208 @@
2 2
3/* Local functions ***********************************************************/ 3/* Local functions ***********************************************************/
4 4
5static bool allowed_next(Move move, DfsData *dd, uint64_t mm); 5static bool allowed_next(Move move, DfsArg *arg);
6static void dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd); 6static bool cancel_niss(DfsArg *arg);
7static void dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd); 7static void copy_dfsarg(DfsArg *src, DfsArg *dst);
8static bool dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd); 8static void dfs(DfsArg *arg);
9static void dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd); 9static void dfs_branch(DfsArg *arg);
10static bool dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd); 10static bool dfs_check_solved(DfsArg *arg);
11static bool dfs_switch_final(DfsArg *arg);
12static void dfs_niss(DfsArg *arg);
13static bool dfs_stop(DfsArg *arg);
11static void * instance_thread(void *arg); 14static void * instance_thread(void *arg);
15static void invert_branch(DfsArg *arg);
12static void multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d); 16static void multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d);
17static bool niss_makes_sense(DfsArg *arg);
13 18
14/* Local functions ***********************************************************/ 19/* Local functions ***********************************************************/
15 20
16static bool 21static bool
17allowed_next(Move move, DfsData *dd, uint64_t mm) 22allowed_next(Move m, DfsArg *arg)
18{ 23{
19 if ((1 << move) & mm) 24 if ((1 << m) & arg->badmoves)
20 return false; 25 return false;
21 26
22 if (!possible_next(dd->last2, dd->last1, move)) 27 if (!possible_next(arg->last2, arg->last1, m))
23 return false; 28 return false;
24 29
25 if (commute(dd->last1, move)) 30 if (commute(arg->last1, m))
26 return dd->move_position[dd->last1] < dd->move_position[move]; 31 return arg->move_position[arg->last1] < arg->move_position[m];
27 32
28 return true; 33 return true;
29} 34}
30 35
36static bool
37cancel_niss(DfsArg *arg)
38{
39 return !possible_next(arg->last2, arg->last1, arg->last1inv) &&
40 !(commute(arg->last1inv, arg->last2inv) &&
41 arg->last2inv != NULLMOVE &&
42 possible_next(arg->last2, arg->last1, arg->last2inv));
43}
44
31static void 45static void
32dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd) 46copy_dfsarg(DfsArg *src, DfsArg *dst)
33{ 47{
34 if (dfs_stop(c, s, opts, dd)) 48 dst->step = src->step;
49 dst->opts = src->opts;
50 dst->cube = src->cube;
51 dst->inverse = src->inverse;
52 dst->d = src->d;
53 dst->badmoves = src->badmoves;
54 dst->badmovesinv = src->badmovesinv;
55 dst->niss = src->niss;
56 dst->last1 = src->last1;
57 dst->last2 = src->last2;
58 dst->last1inv = src->last1inv;
59 dst->last2inv = src->last2inv;
60 dst->sols = src->sols;
61 dst->sols_mutex = src->sols_mutex;
62 dst->current_alg = src->current_alg;
63 dst->sorted_moves = src->sorted_moves;
64 dst->move_position = src->move_position;
65
66 copy_estimatedata(src->ed, dst->ed);
67}
68
69static void
70dfs(DfsArg *arg)
71{
72 bool sw = false;
73
74 if (dfs_stop(arg))
35 return; 75 return;
36 76
37 if (dfs_check_solved(s, opts, dd)) 77 if (dfs_check_solved(arg))
38 return; 78 return;
39 79
40 dfs_branch(c, s, opts, dd); 80 if (arg->step->final && (sw = dfs_switch_final(arg)))
81 invert_branch(arg);
82 dfs_branch(arg);
83
84 if (arg->opts->can_niss && !arg->niss && niss_makes_sense(arg))
85 dfs_niss(arg);
41 86
42 if (opts->can_niss && !dd->niss) 87 if (sw)
43 dfs_niss(c, s, opts, dd); 88 invert_branch(arg);
44} 89}
45 90
46static void 91static void
47dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd) 92dfs_branch(DfsArg *arg)
48{ 93{
49 bool b = false;
50 int i; 94 int i;
51 uint64_t mm; 95 Move m;
52 Move m, l1, l2; 96 DfsArg *newarg;
53 LocalInfo li;
54 97
55 l1 = dd->last1; 98 newarg = malloc(sizeof(DfsArg));
56 l2 = dd->last2; 99 newarg->ed = malloc(sizeof(EstimateData));
57 li = *(dd->ed->li);
58 mm = dd->ed->movebitmask;
59 100
60 for (i = 0; dd->sorted_moves[i] != NULLMOVE; i++) { 101 for (i = 0; arg->sorted_moves[i] != NULLMOVE; i++) {
61 if (b) 102 m = arg->sorted_moves[i];
62 break; 103 if (allowed_next(m, arg)) {
63 104 copy_dfsarg(arg, newarg);
64 m = dd->sorted_moves[i]; 105 newarg->last2 = arg->last1;
65 if (allowed_next(m, dd, mm)) { 106 newarg->last1 = m;
66 dd->last2 = dd->last1; 107 newarg->cube = apply_move(m, arg->cube);
67 dd->last1 = m; 108 append_move(arg->current_alg, m, newarg->niss);
68 append_move(dd->current_alg, m, dd->niss);
69 109
70 dfs(apply_move(m, c), s, opts, dd); 110 dfs(newarg);
71 111
72 dd->current_alg->len--; 112 arg->current_alg->len--;
73 dd->last2 = l2;
74 dd->last1 = l1;
75 *(dd->ed->li) = li;
76 } 113 }
77 } 114 }
115
116 free(newarg->ed);
117 free(newarg);
78} 118}
79 119
80static bool 120static bool
81dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd) 121dfs_check_solved(DfsArg *arg)
82{ 122{
83 if (dd->lb != 0) 123 if (!arg->step->is_done(arg->cube))
84 return false; 124 return false;
85 125
86 if (dd->current_alg->len == dd->d) { 126 if (arg->current_alg->len == arg->d) {
87 if (s->is_valid(dd->current_alg) || opts->all) { 127 if ((arg->step->is_valid(arg->current_alg) || arg->opts->all)
88 pthread_mutex_lock(dd->sols_mutex); 128 && (!arg->step->final || !cancel_niss(arg))) {
89 if (dd->sols->len < opts->max_solutions) 129 pthread_mutex_lock(arg->sols_mutex);
90 append_alg(dd->sols, dd->current_alg); 130 if (arg->sols->len < arg->opts->max_solutions)
91 pthread_mutex_unlock(dd->sols_mutex); 131 append_alg(arg->sols, arg->current_alg);
132 pthread_mutex_unlock(arg->sols_mutex);
92 } 133 }
93 134
94 if (opts->verbose) 135 if (arg->opts->verbose)
95 print_alg(dd->current_alg, false); 136 print_alg(arg->current_alg, false);
96 } 137 }
97 138
98 return true; 139 return true;
99} 140}
100 141
101static void 142static void
102dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd) 143dfs_niss(DfsArg *arg)
103{ 144{
104 Move l1, l2; 145 DfsArg *newarg;
105 EstimateData *ed;
106
107 l1 = dd->last1;
108 l2 = dd->last2;
109 146
110 ed = malloc(sizeof(EstimateData)); 147 newarg = malloc(sizeof(DfsArg));
111 ed->cube = apply_move(inverse_move(l1), (Cube){0}); 148 newarg->ed = malloc(sizeof(EstimateData));
112 ed->target = 1;
113 149
114 if (dd->current_alg->len == 0 || s->estimate(ed)) { 150 copy_dfsarg(arg, newarg);
115 dd->niss = true; 151 swapmove(&(newarg->last1), &(newarg->last1inv));
116 dd->last1 = NULLMOVE; 152 swapmove(&(newarg->last2), &(newarg->last2inv));
117 dd->last2 = NULLMOVE; 153 newarg->niss = !(arg->niss);
154 newarg->cube = inverse_cube(arg->cube);
118 155
119 dfs(inverse_cube(c), s, opts, dd); 156 dfs(newarg);
120 157
121 dd->last1 = l1; 158 free(newarg->ed);
122 dd->last2 = l2; 159 free(newarg);
123 dd->niss = false;
124 }
125
126 free(ed);
127} 160}
128 161
129static bool 162static bool
130dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd) 163dfs_stop(DfsArg *arg)
131{ 164{
165 int lowerbound;
132 bool b; 166 bool b;
133 167
134 dd->ed->cube = c; 168 lowerbound = arg->step->estimate(arg);
135 dd->ed->target = dd->d - dd->current_alg->len; 169 if (arg->opts->can_niss && !arg->niss)
136 dd->ed->lastmove = dd->last1; 170 lowerbound = MIN(1, lowerbound);
137 dd->ed->movebitmask = 0;
138
139 dd->lb = s->estimate(dd->ed);
140 if (opts->can_niss && !dd->niss)
141 dd->lb = MIN(1, dd->lb);
142 171
143 if (dd->current_alg->len + dd->lb > dd->d) { 172 if (arg->current_alg->len + lowerbound > arg->d) {
144 b = true; 173 b = true;
145 } else { 174 } else {
146 pthread_mutex_lock(dd->sols_mutex); 175 pthread_mutex_lock(arg->sols_mutex);
147 b = dd->sols->len >= opts->max_solutions; 176 b = arg->sols->len >= arg->opts->max_solutions;
148 pthread_mutex_unlock(dd->sols_mutex); 177 pthread_mutex_unlock(arg->sols_mutex);
149 } 178 }
150 179
151 return b; 180 return b;
152} 181}
153 182
183static bool
184dfs_switch_final(DfsArg *arg)
185{
186 int i, bn, bi;
187
188 for (bn = 0, i = 0; arg->sorted_moves[i] != NULLMOVE; i++)
189 if (allowed_next(arg->sorted_moves[i], arg))
190 bn++;
191
192 swapmove(&(arg->last1), &(arg->last1inv));
193 swapmove(&(arg->last2), &(arg->last2inv));
194 swapu64(&(arg->badmoves), &(arg->badmovesinv));
195
196 for (bi = 0, i = 0; arg->sorted_moves[i] != NULLMOVE; i++)
197 if (allowed_next(arg->sorted_moves[i], arg))
198 bi++;
199
200 swapmove(&(arg->last1), &(arg->last1inv));
201 swapmove(&(arg->last2), &(arg->last2inv));
202 swapu64(&(arg->badmoves), &(arg->badmovesinv));
203
204 return bi < bn;
205}
206
154static void * 207static void *
155instance_thread(void *arg) 208instance_thread(void *arg)
156{ 209{
@@ -158,7 +211,7 @@ instance_thread(void *arg)
158 Cube c; 211 Cube c;
159 ThreadDataSolve *td; 212 ThreadDataSolve *td;
160 AlgListNode *node; 213 AlgListNode *node;
161 DfsData dd; 214 DfsArg darg;
162 215
163 td = (ThreadDataSolve *)arg; 216 td = (ThreadDataSolve *)arg;
164 217
@@ -179,34 +232,53 @@ instance_thread(void *arg)
179 apply_move(node->alg->move[0], inverse_cube(td->cube)) : 232 apply_move(node->alg->move[0], inverse_cube(td->cube)) :
180 apply_move(node->alg->move[0], td->cube); 233 apply_move(node->alg->move[0], td->cube);
181 234
182 dd.d = td->depth; 235 darg.step = td->step;
183 dd.m = 1; 236 darg.opts = td->opts;
184 dd.niss = node->alg->inv[0]; 237 darg.cube = c;
185 dd.lb = -1; 238 darg.d = td->depth;
186 dd.last1 = node->alg->move[0]; 239 darg.niss = node->alg->inv[0];
187 dd.last2 = NULLMOVE; 240 darg.last1 = node->alg->move[0];
188 dd.sols = td->sols; 241 darg.last2 = NULLMOVE;
189 dd.sols_mutex = td->sols_mutex; 242 darg.last1inv = NULLMOVE;
190 dd.current_alg = new_alg(""); 243 darg.last2inv = NULLMOVE;
191 append_move(dd.current_alg, node->alg->move[0], 244 darg.sols = td->sols;
245 darg.sols_mutex = td->sols_mutex;
246 darg.current_alg = new_alg("");
247 append_move(darg.current_alg, node->alg->move[0],
192 node->alg->inv[0]); 248 node->alg->inv[0]);
193 dd.sorted_moves = td->sorted_moves; 249 darg.sorted_moves = td->sorted_moves;
194 dd.move_position = td->move_position; 250 darg.move_position = td->move_position;
195 dd.ed = malloc(sizeof(EstimateData)); 251 darg.ed = new_estimatedata();
196 dd.ed->movebitmask = 0; 252 darg.badmoves = 0;
197 dd.ed->li = new_localinfo(); 253 darg.badmovesinv = 0;
198 254
199 dfs(c, td->step, td->opts, &dd); 255 dfs(&darg);
200 256
201 free_alg(dd.current_alg); 257 free_alg(darg.current_alg);
202 free_localinfo(dd.ed->li); 258 free_estimatedata(darg.ed);
203 free(dd.ed);
204 } 259 }
205 260
206 return NULL; 261 return NULL;
207} 262}
208 263
209static void 264static void
265invert_branch(DfsArg *arg)
266{
267 Cube aux;
268
269 aux = arg->cube;
270 arg->cube = is_solved(arg->inverse) ?
271 inverse_cube(arg->cube) : arg->inverse;
272 arg->inverse = aux;
273
274 swapu64(&(arg->badmoves), &(arg->badmovesinv));
275 arg->niss = !(arg->niss);
276 swapmove(&(arg->last1), &(arg->last1inv));
277 swapmove(&(arg->last2), &(arg->last2inv));
278 invert_estimatedata(arg->ed);
279}
280
281static void
210multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d) 282multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
211{ 283{
212 int i, *move_position; 284 int i, *move_position;
@@ -233,6 +305,8 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
233 305
234 for (i = 0; sorted_moves[i] != NULLMOVE; i++) { 306 for (i = 0; sorted_moves[i] != NULLMOVE; i++) {
235 alg = new_alg(""); 307 alg = new_alg("");
308 /* TODO: start on inverse also in case of final step
309 and ed->sw true */
236 append_move(alg, sorted_moves[i], false); 310 append_move(alg, sorted_moves[i], false);
237 append_alg(start, alg); 311 append_alg(start, alg);
238 if (opts->can_niss) { 312 if (opts->can_niss) {
@@ -270,6 +344,15 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
270 free(sorted_moves); 344 free(sorted_moves);
271} 345}
272 346
347static bool
348niss_makes_sense(DfsArg *arg)
349{
350 Cube testcube;
351
352 testcube = apply_move(inverse_move(arg->last1), (Cube){0});
353 return arg->current_alg->len == 0 || arg->step->is_done(testcube);
354}
355
273/* Public functions **********************************************************/ 356/* Public functions **********************************************************/
274 357
275AlgList * 358AlgList *
@@ -279,10 +362,8 @@ solve(Cube cube, Step *step, SolveOptions *opts)
279 AlgList *sols; 362 AlgList *sols;
280 AlgListNode *node; 363 AlgListNode *node;
281 Cube c; 364 Cube c;
282 EstimateData *ed;
283 bool b;
284 365
285 prepare_step(step, opts->nthreads); 366 prepare_step(step, opts);
286 367
287 if (step->detect != NULL) 368 if (step->detect != NULL)
288 step->pre_trans = step->detect(cube); 369 step->pre_trans = step->detect(cube);
@@ -296,19 +377,9 @@ solve(Cube cube, Step *step, SolveOptions *opts)
296 return sols; 377 return sols;
297 } 378 }
298 379
299 if (opts->min_moves == 0) { 380 if (opts->min_moves == 0 && step->is_done(cube)) {
300 ed = malloc(sizeof(EstimateData)); 381 append_alg(sols, new_alg(""));
301 ed->cube = cube; 382 return sols;
302 ed->target = 0;
303 ed->li = new_localinfo();
304 b = step->estimate(ed) == 0;
305 free_localinfo(ed->li);
306 free(ed);
307
308 if (b) {
309 append_alg(sols, new_alg(""));
310 return sols;
311 }
312 } 383 }
313 384
314 for (d = opts->min_moves; 385 for (d = opts->min_moves;
@@ -323,8 +394,11 @@ solve(Cube cube, Step *step, SolveOptions *opts)
323 multidfs(c, step, opts, sols, d); 394 multidfs(c, step, opts, sols, d);
324 } 395 }
325 396
326 for (node = sols->first; node != NULL; node = node->next) 397 for (node = sols->first; node != NULL; node = node->next) {
327 transform_alg(inverse_trans(step->pre_trans), node->alg); 398 transform_alg(inverse_trans(step->pre_trans), node->alg);
399 if (step->final)
400 unniss(node->alg);
401 }
328 402
329 return sols; 403 return sols;
330} 404}

Generated with cgit - Back to sebastiano.tronto.net