aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--TODO/2.1.md96
-rw-r--r--TODO/new-feature-ideas.md2
-rw-r--r--TODO/refactoring.md2
-rw-r--r--old/solve_old.c447
-rw-r--r--old/solve_old.h9
-rw-r--r--src/alg.c127
-rw-r--r--src/alg.h76
-rw-r--r--src/commands.c18
-rw-r--r--src/commands.h9
-rw-r--r--src/cubetypes.h36
-rw-r--r--src/movesets.c194
-rw-r--r--src/movesets.h15
-rw-r--r--src/pruning.h1
-rw-r--r--src/solve.c513
-rw-r--r--src/solve.h50
-rw-r--r--src/solver_step.c296
-rw-r--r--src/solver_step.h12
-rw-r--r--src/steps.c14
-rw-r--r--src/steps.h5
-rw-r--r--src/threader_eager.c162
-rw-r--r--src/threader_eager.h8
-rw-r--r--src/threader_single.c35
-rw-r--r--src/threader_single.h8
-rw-r--r--tests/alg_tests.h1
24 files changed, 1436 insertions, 700 deletions
diff --git a/TODO/2.1.md b/TODO/2.1.md
index d65eb93..7448094 100644
--- a/TODO/2.1.md
+++ b/TODO/2.1.md
@@ -1,89 +1,33 @@
1# TODO-list for version 2.1 (or is it 3.0 at this point?) 1# TODO-list for version 2.1 (or is it 3.0 at this point?)
2 2
3## Alg and moveset changes (prerequisite for solve.h)
4
5### moveset.h
6* split off from alg.h
7
8### alg.h
9* There is a (future) bug in the way the solver checks if a move can
10be appended (allowed_next and similar): the last two moves are not enough.
11* Example: using QTM we have last 3 moves U U D. Considering only last 2,
12U could be appended, but it cannot (cancel to U').
13* Solution: the per-moveset bool allowed_next() should take an alg as
14parameter. There are going to be basically two versions, one for QTM and
15one for HTM (but more may be added).
16* Alg should be extended to remember the list of moves on inverse / normal
17separately (without looping over moves).
18* Maybe another parameter to know if it can assume there has not been
19any double switching, i.e. if the last moves are the only ones to
20be checked and there is no need to go back further (e.g. if alg is
21U (... stuff on inverse ...) D I don't want to have to check back
22to the U, but in practice we can often assume this does not happen).
23* Then we can remove last and lastinv from dfsdata.
24* move also can_niss to alg.h
25* the check for the order of the moves (to avoid counting L R and R L as
26different) can be made separately. Maybe add a "compare" function for moves,
27such that non-commuting moves are not comparable (return -1 0 1).
28
29## Rework solver 3## Rework solver
30 4
31* The architecture is the following: solve.h contains a solve() public 5### 1. Implement minimum viable
32function that takes as parameters a set of solver methods (see below) 6
33and a thread manager (basically, multithreaded or single threaded). 7* Implement nxopt31 with fst_cube. Remember that the function
34It also has a dfs() public function with the same parameters. 8 move_check_solved() should do one axis at the time, so that we don't move
35* The solve() function, looping over the allowed depths, calls 9 everything before checking.
36the dispatcher provided by the thread manager, which takes care of 10* test?
37instantiating the threads. Each thread calls back to dfs(). The
38thread manager then takes case of re-assembling the solutions, and
39finally returns a list of solutions for the given depth.
40* The specifics of how dfs() works are implemented in a specific solver
41module.
42 11
43### solve.h 12### 2. Rework achitecture and file dependencies
44 13
45* Interface: define solve(), dfs() and the types dfsdata, solvermethods and 14* solve.h depends only on moves(alg?) (dependency on step and trans is removed).
46threadmanager. solve.h is included by specific thread managers and solvers. 15* Other modules have changed dependencies, might as well rework all.
47* DfsData: remove Cube *, Movable, Step and extra. Add Void * (containing 16* Make files smaller, do not include definition in .h, separate
48either cube, indexes or whatnot) and a moveset (extracted from step, 17data from abstract operations.
49necessary). Maybe cleanup solveoptions too (e.g. threads not necessary). 18* remove cubetypes.h
50* solve.h depends only on moves (dependency on step and trans is removed). 19* Create a module for multi-step (maybe wait?)
51* preparation step should be reworked, maybe removed or delegated to the 20* Possible changes: in step solver, copy cube only if niss; add cleanup function
52specific implementations. 21in solver (called by solve()) to free cube and perhaps pruning tables.
53* All dfs stuff in the same function. Maybe remove also solvestop. 22* see various TODO's in files
54* Move two-step solve to a different module
55 23
56### Specific thread managers 24### 4. More threading options
57 25
58* Single thread. Useful in low-resources environments or when solving multiple
59scrambles at the same time, or simply when asked to solve with one thread.
60* Lazy multithread: threads are as independent as possible and only 26* Lazy multithread: threads are as independent as possible and only
61merged at the end. Ideal when all solutions of a certain length are requested. 27merged at the end. Ideal when all solutions of a certain length are requested.
62* Eager multithread: current implementation, branches communicate the number 28* (Done) Eager multithread: current implementation, branches communicate the
63and list of solutions to stop as soon as possible. Good when only one solution 29number and list of solutions to stop as soon as possible. Good when only one
64of a certain depth is required. 30solution of a certain depth is required.
65
66### Solver methods
67
68* bool move_check_stop(DfsArg *, Move): applies the given move (possibly
69recovered from DfsData, but we avoid checking for niss by passing it
70directly) and at the same time checks if the branch should be pruned. Not
71elegant, but it is much more efficient to do the two things at the same time
72(e.g. when moving a fst_cube we can move one "orientation" at the time, check
73the pruning table and stop if possible).
74* void add_solution(DfsArg *, ThreadManager): add the solution to the list.
75Also checks if the solution is valid / acceptable (e.g. EO does not finish
76with F' instead of F and such) and cleans it up (rotation, cleanup, unniss).
77* void copy(void * src, void * dst): copy the cube-part of dfs_data. To be
78called by copy_dfsdata, which remains in solve.h (but merged into dfs).
79* void * invert_cube(void *): in preparation for niss.
80* bool niss_makes_sense(DfsArg *): maybe can be done generically in solve.h?
81
82## New optimal solver (use fst)
83
84* Implement nxopt31 with fst_cube. Remember that the function
85 move_check_solved() should do one axis at the time, so that we don't move
86 everything before checking.
87 31
88## Simplify steps 32## Simplify steps
89 33
diff --git a/TODO/new-feature-ideas.md b/TODO/new-feature-ideas.md
index b619e36..067d440 100644
--- a/TODO/new-feature-ideas.md
+++ b/TODO/new-feature-ideas.md
@@ -22,9 +22,11 @@ get its own file and more details.
22* Optimal solver: when asking only for one solution, scan for upper bound in 22* Optimal solver: when asking only for one solution, scan for upper bound in
23 parallel using a non-optimal (but fast) solver (e.g. twophase). 23 parallel using a non-optimal (but fast) solver (e.g. twophase).
24* Optimal solver: up to a small bound, try with a small pruning table. 24* Optimal solver: up to a small bound, try with a small pruning table.
25* Optimal solver: start at different depths in parallel
25* Multi-step solver: make more general 26* Multi-step solver: make more general
26 27
27## New features 28## New features
28 29
30* Allow user to specify moveset manually (see issue \#5 on github)
29* EO analysis (and also DR and HTR analysis): group similar EOs (Jay) 31* EO analysis (and also DR and HTR analysis): group similar EOs (Jay)
30* HTR "maze" analysis? 32* HTR "maze" analysis?
diff --git a/TODO/refactoring.md b/TODO/refactoring.md
index 206b402..eedbd20 100644
--- a/TODO/refactoring.md
+++ b/TODO/refactoring.md
@@ -25,6 +25,4 @@
25* Sort function implementations alphabetically, ignore static vs non static. 25* Sort function implementations alphabetically, ignore static vs non static.
26* Rename functions and variable to have a consistent naming scheme. 26* Rename functions and variable to have a consistent naming scheme.
27* Functions that copy data: swap src and dest, follow memcpy standard. 27* Functions that copy data: swap src and dest, follow memcpy standard.
28* The way coord uses define guards to organize the .h file is good, apply it
29 to other modules too - including tests.
30* Read style(9) and decide what to implement. 28* Read style(9) and decide what to implement.
diff --git a/old/solve_old.c b/old/solve_old.c
new file mode 100644
index 0000000..8662c9e
--- /dev/null
+++ b/old/solve_old.c
@@ -0,0 +1,447 @@
1#define SOLVE_C
2
3#include "solve.h"
4
5/* Local functions ***********************************************************/
6
7static void copy_dfsarg(DfsArg *src, DfsArg *dst);
8static void dfs(DfsArg *arg);
9static void dfs_add_sol(DfsArg *arg);
10static void dfs_niss(DfsArg *arg);
11static bool dfs_move_checkstop(DfsArg *arg);
12static void * instance_thread(void *arg);
13static void multidfs(DfsArg *arg);
14static bool niss_makes_sense(DfsArg *arg);
15static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols);
16
17/* Local functions ***********************************************************/
18
19static void
20copy_dfsarg(DfsArg *src, DfsArg *dst)
21{
22 int i;
23
24 dst->cube = src->cube;
25 dst->t = src->t;
26 dst->s = src->s;
27 dst->opts = src->opts;
28 dst->d = src->d;
29 dst->bound = src->bound; /* In theory not needed */
30 dst->niss = src->niss;
31 dst->sols = src->sols;
32 dst->sols_mutex = src->sols_mutex;
33 dst->current_alg = src->current_alg;
34
35 for (i = 0; i < src->s->n_coord; i++) {
36 dst->ind[i].val = src->ind[i].val;
37 dst->ind[i].t = src->ind[i].t;
38 }
39
40 src->s->copy_extra(src, dst);
41}
42
43static void
44dfs(DfsArg *arg)
45{
46 int i;
47 Move m, l0, l1;
48 DfsArg newarg;
49
50 if (dfs_move_checkstop(arg))
51 return;
52
53 if (arg->bound == 0) {
54 if (arg->current_alg->len == arg->d)
55 dfs_add_sol(arg);
56 return;
57 }
58
59 for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) {
60 m = arg->s->moveset->sorted_moves[i];
61 if (arg->s->moveset->can_append(arg->current_alg, m, arg->niss)
62 && compare_last(arg->current_alg, m, arg->niss) >= 0) {
63 copy_dfsarg(arg, &newarg);
64 append_move(arg->current_alg, m, newarg.niss);
65 dfs(&newarg);
66 remove_last_move(arg->current_alg);
67 }
68 }
69
70 if (niss_makes_sense(arg))
71 dfs_niss(arg);
72}
73
74static void
75dfs_add_sol(DfsArg *arg)
76{
77 bool valid, accepted, nisscanc;
78
79 valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg);
80 accepted = valid || arg->opts->all;
81 nisscanc = arg->s->final &&
82 arg->s->moveset->cancel_niss(arg->current_alg);
83
84 if (accepted && !nisscanc) {
85 pthread_mutex_lock(arg->sols_mutex);
86
87 if (arg->sols->len < arg->opts->max_solutions) {
88 append_alg(arg->sols, arg->current_alg);
89 transform_alg(
90 inverse_trans(arg->t), arg->sols->last->alg);
91 if (arg->opts->verbose)
92 print_alg(arg->sols->last->alg, false);
93 }
94
95 pthread_mutex_unlock(arg->sols_mutex);
96 }
97}
98
99static void
100dfs_niss(DfsArg *arg)
101{
102 DfsArg newarg;
103 Alg *inv;
104 Cube *c;
105
106 copy_dfsarg(arg, &newarg);
107
108 /* Invert current alg and scramble */
109 newarg.cube = malloc(sizeof(Cube));
110 inv = inverse_alg(arg->current_alg);
111 c = malloc(sizeof(Cube));
112 make_solved(newarg.cube);
113 apply_alg(inv, newarg.cube);
114 copy_cube(arg->cube, c);
115 invert_cube(c);
116 compose(c, newarg.cube);
117
118 /* New indexes */
119 compute_ind(newarg.s, newarg.cube, newarg.ind);
120
121 newarg.niss = !(arg->niss);
122
123 dfs(&newarg);
124
125 free_alg(inv);
126 free(c);
127 free(newarg.cube);
128}
129
130static bool
131dfs_move_checkstop(DfsArg *arg)
132{
133 int i, goal, nsols;
134 Move mm;
135 Trans tt = uf; /* Avoid uninitialized warning */
136
137 /* Moving and computing bound */
138 arg->bound = 0;
139 goal = arg->d - arg->current_alg->len;
140 for (i = 0; i < arg->s->n_coord; i++) {
141 if (arg->last[0] != NULLMOVE) {
142 mm = transform_move(arg->ind[i].t, arg->last[0]);
143 arg->ind[i].val = move_coord(arg->s->coord[i],
144 mm, arg->ind[i].val, &tt);
145 arg->ind[i].t = transform_trans(tt, arg->ind[i].t);
146 }
147
148 arg->bound =
149 MAX(arg->bound, ptableval(arg->s->pd[i], arg->ind[i].val));
150 if (arg->opts->can_niss && !arg->niss)
151 arg->bound = MIN(1, arg->bound);
152
153 if (arg->bound > goal)
154 return true;
155 }
156
157 pthread_mutex_lock(arg->sols_mutex);
158 nsols = arg->sols->len;
159 pthread_mutex_unlock(arg->sols_mutex);
160
161 return nsols >= arg->opts->max_solutions;
162}
163
164static void *
165instance_thread(void *arg)
166{
167 bool b, inv;
168 Cube c;
169 Move m;
170 ThreadDataSolve *td;
171 AlgListNode *node;
172 DfsArg darg;
173
174 td = (ThreadDataSolve *)arg;
175
176 while (1) {
177 b = false;
178
179 pthread_mutex_lock(td->start_mutex);
180 if ((node = *(td->node)) == NULL)
181 b = true;
182 else
183 *(td->node) = (*(td->node))->next;
184 pthread_mutex_unlock(td->start_mutex);
185
186 if (b)
187 break;
188
189 inv = node->alg->inv[0];
190 m = node->alg->move[0];
191
192 copy_cube(td->arg.cube, &c);
193 if (inv)
194 invert_cube(&c);
195
196 copy_dfsarg(&td->arg, &darg);
197 compute_ind(td->arg.s, &c, darg.ind);
198 darg.cube = &c;
199
200 darg.niss = inv;
201 darg.current_alg = new_alg("");
202 append_move(darg.current_alg, m, inv);
203
204 dfs(&darg);
205
206 free_alg(darg.current_alg);
207 }
208
209 return NULL;
210}
211
212static void
213multidfs(DfsArg *arg)
214{
215 int i;
216 Cube local_cube;
217 Alg *alg;
218 AlgList *start;
219 AlgListNode **node;
220 pthread_t t[arg->opts->nthreads];
221 ThreadDataSolve td[arg->opts->nthreads];
222 pthread_mutex_t *start_mutex, *sols_mutex;
223
224 node = malloc(sizeof(AlgListNode *));
225 start_mutex = malloc(sizeof(pthread_mutex_t));
226 sols_mutex = malloc(sizeof(pthread_mutex_t));
227
228 start = new_alglist();
229 pthread_mutex_init(start_mutex, NULL);
230 pthread_mutex_init(sols_mutex, NULL);
231
232 for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) {
233 alg = new_alg("");
234 append_move(alg, arg->s->moveset->sorted_moves[i], false);
235 append_alg(start, alg);
236 if (arg->opts->can_niss && !arg->s->final) {
237 alg->inv[0] = true;
238 append_alg(start, alg);
239 }
240 free_alg(alg);
241 }
242 *node = start->first;
243
244 copy_cube(arg->cube, &local_cube);
245
246 for (i = 0; i < arg->opts->nthreads; i++) {
247 copy_dfsarg(arg, &(td[i].arg));
248 td[i].arg.cube = &local_cube;
249 td[i].arg.sols_mutex = sols_mutex;
250
251 td[i].thid = i;
252 td[i].start = start;
253 td[i].node = node;
254 td[i].start_mutex = start_mutex;
255
256 pthread_create(&t[i], NULL, instance_thread, &td[i]);
257 }
258
259 for (i = 0; i < arg->opts->nthreads; i++)
260 pthread_join(t[i], NULL);
261
262 free_alglist(start);
263 free(node);
264 free(start_mutex);
265 free(sols_mutex);
266}
267
268static bool
269niss_makes_sense(DfsArg *arg)
270{
271 Move m, mm;
272 uint64_t u;
273 int i;
274
275 if (arg->s->final || arg->niss || !arg->opts->can_niss)
276 return false;
277
278 if (arg->current_alg->len_normal == 0)
279 return true;
280
281 m = inverse_move(arg->last[0]);
282 for (i = 0; i < arg->s->n_coord; i++) {
283 mm = transform_move(arg->ind[i].t, m);
284 u = move_coord(arg->s->coord[i], mm, 0, NULL);
285 if (ptableval(arg->s->pd[i], u) > 0)
286 return true;
287 }
288
289 return false;
290}
291
292static bool
293solvestop(int d, int op, SolveOptions *opts, AlgList *sols)
294{
295 bool opt_done, max_moves_exceeded, max_sols_exceeded;
296
297 opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op;
298 max_moves_exceeded = d > opts->max_moves;
299 max_sols_exceeded = sols->len >= opts->max_solutions;
300
301 return opt_done || max_moves_exceeded || max_sols_exceeded;
302}
303
304/* Public functions **********************************************************/
305
306AlgList *
307solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts)
308{
309 int i, j, d, op, est;
310 bool ready[99], one_ready, zerosol;
311 Movable ind[99][10];
312 AlgList *s;
313 Cube *c[99];
314 DfsArg arg[99];
315
316 prepare_cs(cs, opts);
317 s = new_alglist();
318
319 for (i = 0, one_ready = false; cs->step[i] != NULL; i++) {
320 c[i] = malloc(sizeof(Cube));
321 copy_cube(cube, c[i]);
322 apply_trans(cs->t[i], c[i]);
323
324 arg[i].cube = c[i];
325 arg[i].t = cs->t[i];
326 arg[i].s = cs->step[i];
327 arg[i].opts = opts;
328 arg[i].sols = s;
329
330 if ((ready[i] = cs->step[i]->ready(c[i]))) {
331 one_ready = true;
332 /* Only for local use for 0 moves solutions */
333 compute_ind(cs->step[i], c[i], ind[i]);
334 }
335 }
336 if (!one_ready) {
337 fprintf(stderr, "Cube not ready for solving step: ");
338 fprintf(stderr, "%s\n", cs->ready_msg);
339 return s;
340 }
341
342 /* If the empty moves sequence is a solution for one of the
343 * alternatives, all longer solutions will be discarded, so we may
344 * just set its ready[] value to false. If the solution is accepted
345 * we append it and start searching from d = 1. */
346 for (i = 0, zerosol = false; cs->step[i] != NULL; i++) {
347 if (ready[i]) {
348 est = 0;
349 for (j = 0; j < cs->step[i]->n_coord; j++)
350 est = MAX(est, ptableval(cs->step[i]->pd[j],
351 ind[i][j].val));
352 if (est == 0) {
353 ready[i] = false;
354 zerosol = true;
355 }
356 }
357 }
358 if (zerosol && opts->min_moves == 0) {
359 append_alg(s, new_alg(""));
360 opts->min_moves = 1;
361 if (opts->verbose)
362 printf("Step is already solved"
363 "(empty alg is a solution)\n");
364 }
365
366 for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) {
367 if (opts->verbose)
368 fprintf(stderr, "Searching depth %d\n", d);
369
370 for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) {
371 if (!ready[i])
372 continue;
373
374 arg[i].d = d;
375 multidfs(&arg[i]);
376
377 if (s->len > 0 && op == -1)
378 op = d;
379 }
380 }
381
382 for (i = 0; cs->step[i] != NULL; i++)
383 free(c[i]);
384
385 return s;
386}
387
388/* TODO: make more general! */
389Alg *
390solve_2phase(Cube *cube, int nthreads)
391{
392 int bestlen, newb;
393 Alg *bestalg, *ret;
394 AlgList *sols1, *sols2;
395 AlgListNode *i;
396 Cube c;
397 SolveOptions opts1, opts2;
398
399 opts1.min_moves = 0;
400 opts1.max_moves = 13;
401 opts1.max_solutions = 20;
402 opts1.nthreads = nthreads;
403 opts1.optimal = 3;
404 opts1.can_niss = false;
405 opts1.verbose = false;
406 opts1.all = true;
407
408 opts2.min_moves = 0;
409 opts2.max_moves = 19;
410 opts2.max_solutions = 1;
411 opts2.nthreads = nthreads;
412 opts2.can_niss = false;
413 opts2.verbose = false;
414
415 /* We skip step1 if it is solved on U/D */
416 if (check_drud(cube)) {
417 sols1 = new_alglist();
418 append_alg(sols1, new_alg(""));
419 } else {
420 sols1 = solve(cube, &drud_HTM, &opts1);
421 }
422 bestalg = new_alg("");
423 bestlen = 999;
424 for (i = sols1->first; i != NULL; i = i->next) {
425 copy_cube(cube, &c);
426 apply_alg(i->alg, &c);
427 sols2 = solve(&c, &dranyfin_DR, &opts2);
428
429 if (sols2->len > 0) {
430 newb = i->alg->len + sols2->first->alg->len;
431 if (newb < bestlen) {
432 bestlen = newb;
433 copy_alg(i->alg, bestalg);
434 compose_alg(bestalg, sols2->first->alg);
435 }
436 }
437
438 free_alglist(sols2);
439 }
440
441 free_alglist(sols1);
442
443 ret = cleanup(bestalg);
444 free_alg(bestalg);
445
446 return ret;
447}
diff --git a/old/solve_old.h b/old/solve_old.h
new file mode 100644
index 0000000..010389e
--- /dev/null
+++ b/old/solve_old.h
@@ -0,0 +1,9 @@
1#ifndef SOLVE_H
2#define SOLVE_H
3
4#include "movesets.h"
5
6AlgList * solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts);
7Alg * solve_2phase(Cube *cube, int nthreads);
8
9#endif
diff --git a/src/alg.c b/src/alg.c
index 2815599..d806178 100644
--- a/src/alg.c
+++ b/src/alg.c
@@ -6,57 +6,6 @@ static int axis(Move m);
6static void free_alglistnode(AlgListNode *aln); 6static void free_alglistnode(AlgListNode *aln);
7static void realloc_alg(Alg *alg, int n); 7static void realloc_alg(Alg *alg, int n);
8 8
9bool
10allowed_HTM(Move m)
11{
12 return m >= U && m <= B3;
13}
14
15bool
16allowed_URF(Move m)
17{
18 Move b = base_move(m);
19
20 return b == U || b == R || b == F;
21}
22
23bool
24allowed_eofb(Move m)
25{
26 Move b = base_move(m);
27
28 return b == U || b == D || b == R || b == L ||
29 ((b == F || b == B) && m == b+1);
30}
31
32bool
33allowed_drud(Move m)
34{
35 Move b = base_move(m);
36
37 return b == U || b == D ||
38 ((b == R || b == L || b == F || b == B) && m == b + 1);
39}
40
41bool
42allowed_htr(Move m)
43{
44 Move b = base_move(m);
45
46 return moveset_HTM.allowed(m) && m == b + 1;
47}
48
49bool
50allowed_next_all(Move l2, Move l1, Move m)
51{
52 bool p, q;
53
54 p = l1 != NULLMOVE && base_move(l1) == base_move(m);
55 q = l2 != NULLMOVE && base_move(l2) == base_move(m);
56
57 return !(p || (commute(l1, l2) && q));
58}
59
60void 9void
61append_alg(AlgList *l, Alg *alg) 10append_alg(AlgList *l, Alg *alg)
62{ 11{
@@ -137,6 +86,32 @@ commute(Move m1, Move m2)
137 return axis(m1) == axis(m2); 86 return axis(m1) == axis(m2);
138} 87}
139 88
89int
90compare(Move m1, Move m2)
91{
92 if (!commute(m1, m2))
93 return 0;
94
95 return m1 < m2 ? 1 : -1;
96}
97
98int
99compare_last(Alg *alg, Move m, bool inverse)
100{
101 Move last;
102 int n;
103
104 if (inverse) {
105 n = alg->len_inverse;
106 last = n > 0 ? alg->move_inverse[n-1] : NULLMOVE;
107 } else {
108 n = alg->len_normal;
109 last = n > 0 ? alg->move_normal[n-1] : NULLMOVE;
110 }
111
112 return compare(last, m);
113}
114
140void 115void
141compose_alg(Alg *alg1, Alg *alg2) 116compose_alg(Alg *alg1, Alg *alg2)
142{ 117{
@@ -355,19 +330,6 @@ on_inverse(Alg *alg)
355 return ret; 330 return ret;
356} 331}
357 332
358bool
359possible_next(Move m, Moveset *ms, Move l0, Move l1)
360{
361 bool allowed, order;
362 uint64_t mbit;
363
364 mbit = ((uint64_t)1) << m;
365 allowed = mbit & ms->mask[l1][l0];
366 order = !commute(l0, m) || l0 < m;
367
368 return allowed && order;
369}
370
371void 333void
372print_alg(Alg *alg, bool l) 334print_alg(Alg *alg, bool l)
373{ 335{
@@ -431,6 +393,17 @@ realloc_alg(Alg *alg, int n)
431} 393}
432 394
433void 395void
396remove_last_move(Alg *a)
397{
398 a->len--;
399
400 if (a->inv[a->len])
401 a->len_inverse--;
402 else
403 a->len_normal--;
404}
405
406void
434swapmove(Move *m1, Move *m2) 407swapmove(Move *m1, Move *m2)
435{ 408{
436 Move aux; 409 Move aux;
@@ -484,29 +457,3 @@ unniss(Alg *alg)
484 457
485 return ret; 458 return ret;
486} 459}
487
488void
489init_moveset(Moveset *ms)
490{
491 int j;
492 uint64_t l, one;
493 Move m, l2, l1;
494
495 one = 1;
496
497 for (j = 0, m = U; m < NMOVES; m++)
498 if (ms->allowed(m))
499 ms->sorted_moves[j++] = m;
500 ms->sorted_moves[j] = NULLMOVE;
501
502 for (l1 = 0; l1 < NMOVES; l1++) {
503 for (l2 = 0; l2 < NMOVES; l2++) {
504 ms->mask[l2][l1] = 0;
505 for (l = 0; ms->sorted_moves[l] != NULLMOVE; l++) {
506 m = ms->sorted_moves[l];
507 if (ms->allowed_next(l2, l1, m))
508 ms->mask[l2][l1] |= (one<<m);
509 }
510 }
511 }
512}
diff --git a/src/alg.h b/src/alg.h
index b65a55e..967cd92 100644
--- a/src/alg.h
+++ b/src/alg.h
@@ -8,21 +8,11 @@
8#include "cubetypes.h" 8#include "cubetypes.h"
9#include "utils.h" 9#include "utils.h"
10 10
11bool allowed_all(Move m);
12bool allowed_HTM(Move m);
13bool allowed_URF(Move m);
14bool allowed_eofb(Move m);
15bool allowed_drud(Move m);
16bool allowed_htr(Move m);
17bool allowed_next_all(Move l2, Move l1, Move m);
18
19void moveset_to_list(Moveset ms, Move *lst);
20void init_moveset(Moveset *ms);
21bool possible_next(Move m, Moveset *ms, Move l0, Move l1);
22
23void append_alg(AlgList *l, Alg *alg); 11void append_alg(AlgList *l, Alg *alg);
24void append_move(Alg *alg, Move m, bool inverse); 12void append_move(Alg *alg, Move m, bool inverse);
25Move base_move(Move m); 13Move base_move(Move m);
14int compare(Move m1, Move m2); /* Return 1 (m1<m2), 0 or -1 (m1>m2) */
15int compare_last(Alg *alg, Move m, bool inverse);
26void compose_alg(Alg *alg1, Alg *alg2); 16void compose_alg(Alg *alg1, Alg *alg2);
27bool commute(Move m1, Move m2); 17bool commute(Move m1, Move m2);
28void copy_alg(Alg *src, Alg *dst); 18void copy_alg(Alg *src, Alg *dst);
@@ -36,70 +26,10 @@ AlgList * new_alglist();
36Alg * on_inverse(Alg *alg); 26Alg * on_inverse(Alg *alg);
37void print_alg(Alg *alg, bool l); 27void print_alg(Alg *alg, bool l);
38void print_alglist(AlgList *al, bool l); 28void print_alglist(AlgList *al, bool l);
29void remove_last_move(Alg *alg);
39void swapmove(Move *m1, Move *m2); 30void swapmove(Move *m1, Move *m2);
40char * trans_string(Trans t); /* Here because similar to move_string, move? */ 31char * trans_string(Trans t); /* Here because similar to move_string, move? */
41Alg * unniss(Alg *alg); 32Alg * unniss(Alg *alg);
42 33
43/* Movesets ******************************************************************/
44
45#ifndef ALG_C
46
47extern Moveset moveset_HTM;
48extern Moveset moveset_URF;
49extern Moveset moveset_eofb;
50extern Moveset moveset_drud;
51extern Moveset moveset_htr;
52
53extern Moveset * all_ms[];
54
55#else
56
57Moveset
58moveset_HTM = {
59 .name = "HTM",
60 .allowed = allowed_HTM,
61 .allowed_next = allowed_next_all,
62};
63
64Moveset
65moveset_URF = {
66 .name = "URF",
67 .allowed = allowed_URF,
68 .allowed_next = allowed_next_all,
69};
70
71Moveset
72moveset_eofb = {
73 .name = "eofb",
74 .allowed = allowed_eofb,
75 .allowed_next = allowed_next_all,
76};
77
78Moveset
79moveset_drud = {
80 .name = "drud",
81 .allowed = allowed_drud,
82 .allowed_next = allowed_next_all,
83};
84
85Moveset
86moveset_htr = {
87 .name = "htr",
88 .allowed = allowed_htr,
89 .allowed_next = allowed_next_all,
90};
91
92Moveset *
93all_ms[] = {
94 &moveset_HTM,
95 &moveset_URF,
96 &moveset_eofb,
97 &moveset_drud,
98 &moveset_htr,
99 NULL
100};
101
102#endif
103
104#endif 34#endif
105 35
diff --git a/src/commands.c b/src/commands.c
index 9ac1ae6..a9e8fc9 100644
--- a/src/commands.c
+++ b/src/commands.c
@@ -215,10 +215,21 @@ solve_exec(CommandArgs *args)
215{ 215{
216 Cube c; 216 Cube c;
217 AlgList *sols; 217 AlgList *sols;
218 Solver *solver[99];
219 Threader *threader;
218 220
219 make_solved(&c); 221 make_solved(&c);
220 apply_alg(args->scramble, &c); 222 apply_alg(args->scramble, &c);
221 sols = solve(&c, args->cs, args->opts); 223/* TODO: adjust */
224/* threader = &threader_single;*/
225 threader = &threader_eager;
226
227/* TODO: adjust */
228 int i;
229 for (i = 0; args->cs->step[i] != NULL; i++)
230 solver[i] = new_stepsolver_lazy(args->cs->step[i]);
231 solver[i] = NULL;
232 sols = solve(&c, args->opts, solver, threader);
222 233
223 if (args->opts->count_only) 234 if (args->opts->count_only)
224 printf("%d\n", sols->len); 235 printf("%d\n", sols->len);
@@ -285,7 +296,10 @@ scramble_exec(CommandArgs *args)
285 } 296 }
286 297
287 /* TODO: can be optimized for htr and dr using htrfin, drfin */ 298 /* TODO: can be optimized for htr and dr using htrfin, drfin */
299 /*
300 TODO: solve_2phase was removed
288 scr = solve_2phase(&cube, 1); 301 scr = solve_2phase(&cube, 1);
302 */
289 303
290 if (!strcmp(args->scrtype, "fmc")) { 304 if (!strcmp(args->scrtype, "fmc")) {
291 aux = new_alg(""); 305 aux = new_alg("");
@@ -383,6 +397,7 @@ print_exec(CommandArgs *args)
383 print_cube(&c); 397 print_cube(&c);
384} 398}
385 399
400/*
386void 401void
387twophase_exec(CommandArgs *args) 402twophase_exec(CommandArgs *args)
388{ 403{
@@ -396,6 +411,7 @@ twophase_exec(CommandArgs *args)
396 print_alg(sol, false); 411 print_alg(sol, false);
397 free_alg(sol); 412 free_alg(sol);
398} 413}
414*/
399 415
400void 416void
401help_exec(CommandArgs *args) 417help_exec(CommandArgs *args)
diff --git a/src/commands.h b/src/commands.h
index 5d9f4ee..65708e0 100644
--- a/src/commands.h
+++ b/src/commands.h
@@ -5,6 +5,9 @@
5 5
6#include "solve.h" 6#include "solve.h"
7#include "steps.h" 7#include "steps.h"
8#include "solver_step.h"
9#include "threader_single.h"
10#include "threader_eager.h"
8 11
9void free_args(CommandArgs *args); 12void free_args(CommandArgs *args);
10CommandArgs * new_args(); 13CommandArgs * new_args();
@@ -29,7 +32,7 @@ void steps_exec(CommandArgs *args);
29void commands_exec(CommandArgs *args); 32void commands_exec(CommandArgs *args);
30void freemem_exec(CommandArgs *args); 33void freemem_exec(CommandArgs *args);
31void print_exec(CommandArgs *args); 34void print_exec(CommandArgs *args);
32void twophase_exec(CommandArgs *args); 35/*void twophase_exec(CommandArgs *args);*/
33void help_exec(CommandArgs *args); 36void help_exec(CommandArgs *args);
34void quit_exec(CommandArgs *args); 37void quit_exec(CommandArgs *args);
35void unniss_exec(CommandArgs *args); 38void unniss_exec(CommandArgs *args);
@@ -138,6 +141,7 @@ help_cmd = {
138 .exec = help_exec, 141 .exec = help_exec,
139}; 142};
140 143
144/*
141Command 145Command
142twophase_cmd = { 146twophase_cmd = {
143 .name = "twophase", 147 .name = "twophase",
@@ -146,6 +150,7 @@ twophase_cmd = {
146 .parse_args = parse_only_scramble, 150 .parse_args = parse_only_scramble,
147 .exec = twophase_exec, 151 .exec = twophase_exec,
148}; 152};
153*/
149 154
150Command 155Command
151quit_cmd = { 156quit_cmd = {
@@ -194,7 +199,7 @@ Command *commands[] = {
194 &solve_cmd, 199 &solve_cmd,
195 &scramble_cmd, 200 &scramble_cmd,
196 &steps_cmd, 201 &steps_cmd,
197 &twophase_cmd, 202/* &twophase_cmd,*/
198 &cleanup_cmd, 203 &cleanup_cmd,
199 &unniss_cmd, 204 &unniss_cmd,
200 &version_cmd, 205 &version_cmd,
diff --git a/src/cubetypes.h b/src/cubetypes.h
index 8d38904..3752019 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -89,7 +89,7 @@ typedef struct command Command;
89typedef struct commandargs CommandArgs; 89typedef struct commandargs CommandArgs;
90typedef struct coordinate Coordinate; 90typedef struct coordinate Coordinate;
91typedef struct cube Cube; 91typedef struct cube Cube;
92typedef struct dfsarg DfsArg; 92/*typedef struct dfsarg DfsArg;*/
93typedef struct fstcube FstCube; 93typedef struct fstcube FstCube;
94typedef struct indexer Indexer; 94typedef struct indexer Indexer;
95typedef struct movable Movable; 95typedef struct movable Movable;
@@ -104,9 +104,9 @@ typedef struct transgroup TransGroup;
104 104
105typedef bool (*Checker) (Cube *); 105typedef bool (*Checker) (Cube *);
106typedef bool (*CubeTester) (Cube *, Alg *); 106typedef bool (*CubeTester) (Cube *, Alg *);
107typedef bool (*DfsMover) (DfsArg *); 107/*typedef bool (*DfsMover) (DfsArg *);*/
108typedef void (*DfsExtraCopier) (void *, void *); 108typedef void (*DfsExtraCopier) (void *, void *);
109typedef bool (*Validator) (Alg *); 109typedef Alg * (*Validator) (Alg *);
110typedef void (*Exec) (CommandArgs *); 110typedef void (*Exec) (CommandArgs *);
111typedef CommandArgs * (*ArgParser) (int, char **); 111typedef CommandArgs * (*ArgParser) (int, char **);
112typedef bool (*Tester) (void); 112typedef bool (*Tester) (void);
@@ -206,13 +206,16 @@ cube
206 int xp[6]; 206 int xp[6];
207}; 207};
208 208
209/*
209struct 210struct
210movable 211movable
211{ 212{
212 uint64_t val; 213 uint64_t val;
213 Trans t; 214 Trans t;
214}; 215};
216*/
215 217
218/*
216struct 219struct
217dfsarg 220dfsarg
218{ 221{
@@ -224,13 +227,28 @@ dfsarg
224 int d; 227 int d;
225 int bound; 228 int bound;
226 bool niss; 229 bool niss;
227 Move last[2];
228 Move lastinv[2];
229 AlgList * sols; 230 AlgList * sols;
230 pthread_mutex_t * sols_mutex; 231 pthread_mutex_t * sols_mutex;
231 Alg * current_alg; 232 Alg * current_alg;
232 void * extra; 233 void * extra;
233}; 234};
235*/
236
237/*
238struct
239dfsarg
240{
241 void * cube_data;
242 SolveOptions * opts;
243 int d;
244 int bound;
245 bool niss;
246 AlgList * sols;
247 Alg * current_alg;
248 Solver * solver;
249 Threader * threader;
250};
251*/
234 252
235struct 253struct
236fstcube 254fstcube
@@ -260,9 +278,9 @@ moveset
260{ 278{
261 char * name; 279 char * name;
262 bool (*allowed)(Move); 280 bool (*allowed)(Move);
263 bool (*allowed_next)(Move, Move, Move); 281 bool (*can_append)(Alg *, Move, bool);
282 bool (*cancel_niss)(Alg *);
264 Move sorted_moves[NMOVES+1]; 283 Move sorted_moves[NMOVES+1];
265 uint64_t mask[NMOVES][NMOVES];
266}; 284};
267 285
268struct 286struct
@@ -304,10 +322,11 @@ step
304 PruneData * pd[MAX_N_COORD]; 322 PruneData * pd[MAX_N_COORD];
305 bool pd_compact[MAX_N_COORD]; 323 bool pd_compact[MAX_N_COORD];
306 Validator is_valid; 324 Validator is_valid;
307 DfsMover custom_move_checkstop; 325 /*DfsMover custom_move_checkstop;*/
308 DfsExtraCopier copy_extra; 326 DfsExtraCopier copy_extra;
309}; 327};
310 328
329/*
311struct 330struct
312threaddatasolve 331threaddatasolve
313{ 332{
@@ -317,6 +336,7 @@ threaddatasolve
317 AlgListNode ** node; 336 AlgListNode ** node;
318 pthread_mutex_t * start_mutex; 337 pthread_mutex_t * start_mutex;
319}; 338};
339*/
320 340
321struct 341struct
322threaddatagenpt 342threaddatagenpt
diff --git a/src/movesets.c b/src/movesets.c
new file mode 100644
index 0000000..d8f5bc1
--- /dev/null
+++ b/src/movesets.c
@@ -0,0 +1,194 @@
1#define MOVESETS_C
2
3#include "movesets.h"
4
5static bool allowed_HTM(Move m);
6static bool allowed_URF(Move m);
7static bool allowed_eofb(Move m);
8static bool allowed_drud(Move m);
9static bool allowed_htr(Move m);
10static bool can_append_HTM(Move l2, Move l1, Move m);
11static bool can_append_HTM_cached(Alg *alg, Move m, bool inverse);
12static bool cancel_niss_HTM_cached(Alg *alg);
13static void init_can_append_HTM();
14
15Moveset
16moveset_HTM = {
17 .name = "HTM",
18 .allowed = allowed_HTM,
19 .can_append = can_append_HTM_cached,
20 .cancel_niss = cancel_niss_HTM_cached,
21};
22
23Moveset
24moveset_URF = {
25 .name = "URF",
26 .allowed = allowed_URF,
27 .can_append = can_append_HTM_cached,
28 .cancel_niss = cancel_niss_HTM_cached,
29};
30
31Moveset
32moveset_eofb = {
33 .name = "eofb",
34 .allowed = allowed_eofb,
35 .can_append = can_append_HTM_cached,
36 .cancel_niss = cancel_niss_HTM_cached,
37};
38
39Moveset
40moveset_drud = {
41 .name = "drud",
42 .allowed = allowed_drud,
43 .can_append = can_append_HTM_cached,
44 .cancel_niss = cancel_niss_HTM_cached,
45};
46
47Moveset
48moveset_htr = {
49 .name = "htr",
50 .allowed = allowed_htr,
51 .can_append = can_append_HTM_cached,
52 .cancel_niss = cancel_niss_HTM_cached,
53};
54
55Moveset *
56all_movesets[] = {
57 &moveset_HTM,
58 &moveset_URF,
59 &moveset_eofb,
60 &moveset_drud,
61 &moveset_htr,
62 NULL
63};
64
65static uint64_t can_append_HTM_mask[NMOVES][NMOVES];
66
67static bool
68allowed_HTM(Move m)
69{
70 return m >= U && m <= B3;
71}
72
73static bool
74allowed_URF(Move m)
75{
76 Move b = base_move(m);
77
78 return b == U || b == R || b == F;
79}
80
81static bool
82allowed_eofb(Move m)
83{
84 Move b = base_move(m);
85
86 return b == U || b == D || b == R || b == L ||
87 ((b == F || b == B) && m == b+1);
88}
89
90static bool
91allowed_drud(Move m)
92{
93 Move b = base_move(m);
94
95 return b == U || b == D ||
96 ((b == R || b == L || b == F || b == B) && m == b + 1);
97}
98
99static bool
100allowed_htr(Move m)
101{
102 Move b = base_move(m);
103
104 return moveset_HTM.allowed(m) && m == b + 1;
105}
106
107static bool
108can_append_HTM(Move l2, Move l1, Move m)
109{
110 bool cancel, cancel_last, cancel_swap;
111
112 cancel_last = l1 != NULLMOVE && base_move(l1) == base_move(m);
113 cancel_swap = l2 != NULLMOVE && base_move(l2) == base_move(m);
114 cancel = cancel_last || (commute(l1, l2) && cancel_swap);
115
116 return !cancel;
117}
118
119static bool
120can_append_HTM_cached(Alg *alg, Move m, bool inverse)
121{
122 Move *moves, l1, l2;
123 uint64_t mbit;
124 int n;
125
126 if (inverse) {
127 moves = alg->move_inverse;
128 n = alg->len_inverse;
129 } else {
130 moves = alg->move_normal;
131 n = alg->len_normal;
132 }
133
134 l1 = n > 0 ? moves[n-1] : NULLMOVE;
135 l2 = n > 1 ? moves[n-2] : NULLMOVE;
136
137 mbit = ((uint64_t)1) << m;
138
139 return can_append_HTM_mask[l2][l1] & mbit;
140}
141
142static bool
143cancel_niss_HTM_cached(Alg *alg)
144{
145 Move i1, i2;
146 int n;
147 bool can_first, can_swap;
148
149 n = alg->len_inverse;
150 i1 = n > 0 ? alg->move_inverse[n-1] : NULLMOVE;
151 i2 = n > 1 ? alg->move_inverse[n-2] : NULLMOVE;
152
153 can_first = can_append_HTM_cached(alg, inverse_move(i1), false);
154 can_swap = can_append_HTM_cached(alg, inverse_move(i2), false);
155
156 return can_first && (!commute(i1, i2) || can_swap);
157}
158
159static void
160init_can_append_HTM()
161{
162 Move l2, l1, m;
163
164 for (l1 = 0; l1 < NMOVES; l1++)
165 for (l2 = 0; l2 < NMOVES; l2++)
166 for (m = 0; m < NMOVES; m++)
167 if (can_append_HTM(l2, l1, m))
168 can_append_HTM_mask[l2][l1]
169 |= (((uint64_t)1) << m);
170}
171
172void
173init_moveset(Moveset *ms)
174{
175 int j;
176 Move m;
177
178 for (j = 0, m = U; m < NMOVES; m++)
179 if (ms->allowed(m))
180 ms->sorted_moves[j++] = m;
181 ms->sorted_moves[j] = NULLMOVE;
182
183/* TODO: should be here? maybe just init all movesets together anyway... */
184 init_can_append_HTM();
185}
186
187void
188init_movesets()
189{
190 int i;
191
192 for (i = 0; all_movesets[i] != NULL; i++)
193 init_moveset(all_movesets[i]);
194}
diff --git a/src/movesets.h b/src/movesets.h
new file mode 100644
index 0000000..a02d171
--- /dev/null
+++ b/src/movesets.h
@@ -0,0 +1,15 @@
1#ifndef MOVESETS_H
2#define MOVESETS_H
3
4#include "alg.h"
5
6void init_moveset(Moveset *);
7void init_movesets();
8
9extern Moveset moveset_HTM;
10extern Moveset moveset_URF;
11extern Moveset moveset_eofb;
12extern Moveset moveset_drud;
13extern Moveset moveset_htr;
14
15#endif
diff --git a/src/pruning.h b/src/pruning.h
index 86691c1..93ae863 100644
--- a/src/pruning.h
+++ b/src/pruning.h
@@ -2,6 +2,7 @@
2#define PRUNING_H 2#define PRUNING_H
3 3
4#include "coord.h" 4#include "coord.h"
5#include "movesets.h"
5 6
6void free_pd(PruneData *pd); 7void free_pd(PruneData *pd);
7PruneData * genptable(PruneData *data, int nthreads); 8PruneData * genptable(PruneData *data, int nthreads);
diff --git a/src/solve.c b/src/solve.c
index d5a8f3d..41f99a2 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -2,485 +2,118 @@
2 2
3#include "solve.h" 3#include "solve.h"
4 4
5/* Local functions ***********************************************************/ 5void
6 6dfs(DfsArg *arg, Solver *solver, Threader *threader)
7static bool cancel_niss(DfsArg *arg);
8static void copy_dfsarg(DfsArg *src, DfsArg *dst);
9static void dfs(DfsArg *arg);
10static void dfs_add_sol(DfsArg *arg);
11static void dfs_niss(DfsArg *arg);
12static bool dfs_move_checkstop(DfsArg *arg);
13static void * instance_thread(void *arg);
14static void multidfs(DfsArg *arg);
15static bool niss_makes_sense(DfsArg *arg);
16static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols);
17
18/* Local functions ***********************************************************/
19
20static bool
21cancel_niss(DfsArg *arg)
22{
23 Moveset *ms;
24 Move i1, i2;
25 bool p, p1, p2, q, q1, q2;
26
27 if (arg->lastinv[0] == NULLMOVE)
28 return false;
29
30 ms = arg->s->moveset;
31 i1 = inverse_move(arg->lastinv[0]);
32 i2 = inverse_move(arg->lastinv[1]);
33
34 p1 = !ms->allowed_next(arg->last[1], arg->last[0], i1);
35 p2 = !ms->allowed_next(arg->last[1], i1, arg->last[0]);
36 p = p1 || (commute(i1, arg->last[0]) && p2);
37
38 q1 = !ms->allowed_next(arg->last[1], arg->last[0], i2);
39 q2 = !ms->allowed_next(arg->last[1], i2, arg->last[0]);
40 q = q1 || (commute(i2, arg->last[0]) && q2);
41
42 return p || (commute(i1, i2) && q);
43}
44
45static void
46copy_dfsarg(DfsArg *src, DfsArg *dst)
47{ 7{
48 int i; 8 int i;
49
50 dst->cube = src->cube;
51 dst->t = src->t;
52 dst->s = src->s;
53 dst->opts = src->opts;
54 dst->d = src->d;
55 dst->bound = src->bound; /* In theory not needed */
56 dst->niss = src->niss;
57 dst->sols = src->sols;
58 dst->sols_mutex = src->sols_mutex;
59 dst->current_alg = src->current_alg;
60
61 for (i = 0; i < 2; i++) {
62 dst->last[i] = src->last[i];
63 dst->lastinv[i] = src->lastinv[i];
64 }
65
66 for (i = 0; i < src->s->n_coord; i++) {
67 dst->ind[i].val = src->ind[i].val;
68 dst->ind[i].t = src->ind[i].t;
69 }
70
71 src->s->copy_extra(src, dst);
72}
73
74static void
75dfs(DfsArg *arg)
76{
77 int i;
78 Move m, l0, l1;
79 DfsArg newarg; 9 DfsArg newarg;
10 Alg *sol;
11 Move m;
80 12
81 if (dfs_move_checkstop(arg)) 13 if (arg->current_alg->len > arg->d)
82 return;
83
84 if (arg->bound == 0) {
85 if (arg->current_alg->len == arg->d)
86 dfs_add_sol(arg);
87 return; 14 return;
88 }
89
90 for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) {
91 m = arg->s->moveset->sorted_moves[i];
92 l0 = arg->last[0];
93 l1 = arg->last[1];
94 if (possible_next(m, arg->s->moveset, l0, l1)) {
95 copy_dfsarg(arg, &newarg);
96 newarg.last[1] = l0;
97 newarg.last[0] = m;
98 append_move(arg->current_alg, m, newarg.niss);
99 dfs(&newarg);
100 arg->current_alg->len--;
101 }
102 }
103
104 if (niss_makes_sense(arg))
105 dfs_niss(arg);
106}
107
108static void
109dfs_add_sol(DfsArg *arg)
110{
111 bool valid, accepted, nisscanc;
112 15
113 valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg); 16 if (solver->is_solved(solver->param, arg->cubedata)) {
114 accepted = valid || arg->opts->all; 17/* TODO: the "all" option should be re-implemented as setting
115 nisscanc = arg->s->final && cancel_niss(arg); 18validate to null */
116 19
117 if (accepted && !nisscanc) { 20/* TODO: we also have to check if cancel with NISS;
118 pthread_mutex_lock(arg->sols_mutex); 21we can't because we have no access to the s->final field
22this should be done by the step's validator? */
23 sol = solver->validate_solution(solver->param,arg->current_alg);
24 bool accepted = sol != NULL;
25 bool too_short = arg->current_alg->len != arg->d;
119 26
120 if (arg->sols->len < arg->opts->max_solutions) { 27 if (accepted && !too_short) {
121 append_alg(arg->sols, arg->current_alg); 28/* TODO: arg->t got lost in refactoring */
122 transform_alg( 29/* transform_alg(inverse_trans(arg->t), sol);*/
123 inverse_trans(arg->t), arg->sols->last->alg);
124 if (arg->opts->verbose) 30 if (arg->opts->verbose)
125 print_alg(arg->sols->last->alg, false); 31 print_alg(sol, false);
32 threader->append_sol(sol, arg->threaddata);
126 } 33 }
127 34 return;
128 pthread_mutex_unlock(arg->sols_mutex);
129 }
130}
131
132static void
133dfs_niss(DfsArg *arg)
134{
135 DfsArg newarg;
136 Alg *inv;
137 Cube *c;
138
139 copy_dfsarg(arg, &newarg);
140
141 /* Invert current alg and scramble */
142 newarg.cube = malloc(sizeof(Cube));
143 inv = inverse_alg(arg->current_alg);
144 c = malloc(sizeof(Cube));
145 make_solved(newarg.cube);
146 apply_alg(inv, newarg.cube);
147 copy_cube(arg->cube, c);
148 invert_cube(c);
149 compose(c, newarg.cube);
150
151 /* New indexes */
152 compute_ind(newarg.s, newarg.cube, newarg.ind);
153
154 swapmove(&(newarg.last[0]), &(newarg.lastinv[0]));
155 swapmove(&(newarg.last[1]), &(newarg.lastinv[1]));
156 newarg.niss = !(arg->niss);
157
158 dfs(&newarg);
159
160 free_alg(inv);
161 free(c);
162 free(newarg.cube);
163}
164
165static bool
166dfs_move_checkstop(DfsArg *arg)
167{
168 int i, goal, nsols;
169 Move mm;
170 Trans tt = uf; /* Avoid uninitialized warning */
171
172 /* Moving and computing bound */
173 arg->bound = 0;
174 goal = arg->d - arg->current_alg->len;
175 for (i = 0; i < arg->s->n_coord; i++) {
176 if (arg->last[0] != NULLMOVE) {
177 mm = transform_move(arg->ind[i].t, arg->last[0]);
178 arg->ind[i].val = move_coord(arg->s->coord[i],
179 mm, arg->ind[i].val, &tt);
180 arg->ind[i].t = transform_trans(tt, arg->ind[i].t);
181 }
182
183 arg->bound =
184 MAX(arg->bound, ptableval(arg->s->pd[i], arg->ind[i].val));
185 if (arg->opts->can_niss && !arg->niss)
186 arg->bound = MIN(1, arg->bound);
187
188 if (arg->bound > goal)
189 return true;
190 }
191
192 pthread_mutex_lock(arg->sols_mutex);
193 nsols = arg->sols->len;
194 pthread_mutex_unlock(arg->sols_mutex);
195
196 return nsols >= arg->opts->max_solutions;
197}
198
199static void *
200instance_thread(void *arg)
201{
202 bool b, inv;
203 Cube c;
204 Move m;
205 ThreadDataSolve *td;
206 AlgListNode *node;
207 DfsArg darg;
208
209 td = (ThreadDataSolve *)arg;
210
211 while (1) {
212 b = false;
213
214 pthread_mutex_lock(td->start_mutex);
215 if ((node = *(td->node)) == NULL)
216 b = true;
217 else
218 *(td->node) = (*(td->node))->next;
219 pthread_mutex_unlock(td->start_mutex);
220
221 if (b)
222 break;
223
224 inv = node->alg->inv[0];
225 m = node->alg->move[0];
226
227 copy_cube(td->arg.cube, &c);
228 if (inv)
229 invert_cube(&c);
230
231 copy_dfsarg(&td->arg, &darg);
232 compute_ind(td->arg.s, &c, darg.ind);
233 darg.cube = &c;
234
235 darg.niss = inv;
236 darg.last[0] = m;
237 darg.last[1] = NULLMOVE;
238 darg.lastinv[0] = NULLMOVE;
239 darg.lastinv[1] = NULLMOVE;
240 darg.current_alg = new_alg("");
241 append_move(darg.current_alg, m, inv);
242
243 dfs(&darg);
244
245 free_alg(darg.current_alg);
246 } 35 }
247 36
248 return NULL; 37 if (arg->current_alg->len == arg->d)
249} 38 return;
250
251static void
252multidfs(DfsArg *arg)
253{
254 int i;
255 Cube local_cube;
256 Alg *alg;
257 AlgList *start;
258 AlgListNode **node;
259 pthread_t t[arg->opts->nthreads];
260 ThreadDataSolve td[arg->opts->nthreads];
261 pthread_mutex_t *start_mutex, *sols_mutex;
262 39
263 node = malloc(sizeof(AlgListNode *)); 40/* TODO: do not alloc */
264 start_mutex = malloc(sizeof(pthread_mutex_t)); 41 newarg.cubedata = solver->alloc_cubedata(solver->param);
265 sols_mutex = malloc(sizeof(pthread_mutex_t)); 42 for (i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) {
43 m = solver->moveset->sorted_moves[i];
44 if (solver->moveset->can_append(arg->current_alg, m, arg->niss)
45 && compare_last(arg->current_alg, m, arg->niss) >= 0) {
46 append_move(arg->current_alg, m, arg->niss);
266 47
267 start = new_alglist(); 48 solver->copy_cubedata(
268 pthread_mutex_init(start_mutex, NULL); 49 solver->param, arg->cubedata, newarg.cubedata);
269 pthread_mutex_init(sols_mutex, NULL); 50 newarg.threaddata = arg->threaddata;
51 newarg.opts = arg->opts;
52 newarg.d = arg->d;
53 newarg.niss = arg->niss;
54 newarg.current_alg = arg->current_alg;
55 if (!solver->move_check_stop(
56 solver->param, &newarg, threader))
57 dfs(&newarg, solver, threader);
270 58
271 for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { 59 remove_last_move(arg->current_alg);
272 alg = new_alg("");
273 append_move(alg, arg->s->moveset->sorted_moves[i], false);
274 append_alg(start, alg);
275 if (arg->opts->can_niss && !arg->s->final) {
276 alg->inv[0] = true;
277 append_alg(start, alg);
278 } 60 }
279 free_alg(alg);
280 } 61 }
281 *node = start->first; 62 solver->free_cubedata(solver->param, newarg.cubedata);
282
283 copy_cube(arg->cube, &local_cube);
284
285 for (i = 0; i < arg->opts->nthreads; i++) {
286 copy_dfsarg(arg, &(td[i].arg));
287 td[i].arg.cube = &local_cube;
288 td[i].arg.sols_mutex = sols_mutex;
289
290 td[i].thid = i;
291 td[i].start = start;
292 td[i].node = node;
293 td[i].start_mutex = start_mutex;
294
295 pthread_create(&t[i], NULL, instance_thread, &td[i]);
296 }
297
298 for (i = 0; i < arg->opts->nthreads; i++)
299 pthread_join(t[i], NULL);
300
301 free_alglist(start);
302 free(node);
303 free(start_mutex);
304 free(sols_mutex);
305}
306
307static bool
308niss_makes_sense(DfsArg *arg)
309{
310 Move m, mm;
311 uint64_t u;
312 int i;
313
314 if (arg->s->final || arg->niss || !arg->opts->can_niss)
315 return false;
316
317 if (arg->last[0] == NULLMOVE)
318 return true;
319 63
320 m = inverse_move(arg->last[0]); 64 if (arg->opts->can_niss && !arg->niss &&
321 for (i = 0; i < arg->s->n_coord; i++) { 65 solver->niss_makes_sense(
322 mm = transform_move(arg->ind[i].t, m); 66 solver->param, arg->cubedata, arg->current_alg)) {
323 u = move_coord(arg->s->coord[i], mm, 0, NULL); 67 solver->invert_cube(solver->param, arg->cubedata);
324 if (ptableval(arg->s->pd[i], u) > 0) 68 arg->niss = true;
325 return true; 69 dfs(arg, solver, threader);
326 } 70 }
327
328 return false;
329} 71}
330 72
331static bool
332solvestop(int d, int op, SolveOptions *opts, AlgList *sols)
333{
334 bool opt_done, max_moves_exceeded, max_sols_exceeded;
335
336 opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op;
337 max_moves_exceeded = d > opts->max_moves;
338 max_sols_exceeded = sols->len >= opts->max_solutions;
339
340 return opt_done || max_moves_exceeded || max_sols_exceeded;
341}
342
343/* Public functions **********************************************************/
344
345AlgList * 73AlgList *
346solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts) 74solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader)
347{ 75{
348 int i, j, d, op, est; 76 int i, d, optimal;
349 bool ready[99], one_ready, zerosol; 77 bool ready[MAX_SOLVERS], stop, one_ready;
350 Movable ind[99][10]; 78 DfsArg arg[MAX_SOLVERS];
351 AlgList *s; 79 AlgList *sols;
352 Cube *c[99];
353 DfsArg arg[99];
354
355 prepare_cs(cs, opts);
356 s = new_alglist();
357
358 for (i = 0, one_ready = false; cs->step[i] != NULL; i++) {
359 c[i] = malloc(sizeof(Cube));
360 copy_cube(cube, c[i]);
361 apply_trans(cs->t[i], c[i]);
362 80
363 arg[i].cube = c[i]; 81 one_ready = false;
364 arg[i].t = cs->t[i]; 82 for (i = 0; solver[i] != NULL; i++) {
365 arg[i].s = cs->step[i]; 83 arg[i].cubedata =
84 solver[i]->prepare_cube(solver[i]->param, cube);
366 arg[i].opts = opts; 85 arg[i].opts = opts;
367 arg[i].sols = s; 86 ready[i] = arg[i].cubedata != NULL;
368 87 one_ready = one_ready || ready[i];
369 if ((ready[i] = cs->step[i]->ready(c[i]))) {
370 one_ready = true;
371 /* Only for local use for 0 moves solutions */
372 compute_ind(cs->step[i], c[i], ind[i]);
373 }
374 }
375 if (!one_ready) {
376 fprintf(stderr, "Cube not ready for solving step: ");
377 fprintf(stderr, "%s\n", cs->ready_msg);
378 return s;
379 } 88 }
380 89
381 /* If the empty moves sequence is a solution for one of the 90 sols = new_alglist();
382 * alternatives, all longer solutions will be discarded, so we may 91 if (!one_ready) {
383 * just set its ready[] value to false. If the solution is accepted 92 fprintf(stderr, "Cube not ready for solving\n");
384 * we append it and start searching from d = 1. */ 93 return sols;
385 for (i = 0, zerosol = false; cs->step[i] != NULL; i++) {
386 if (ready[i]) {
387 est = 0;
388 for (j = 0; j < cs->step[i]->n_coord; j++)
389 est = MAX(est, ptableval(cs->step[i]->pd[j],
390 ind[i][j].val));
391 if (est == 0) {
392 ready[i] = false;
393 zerosol = true;
394 }
395 }
396 }
397 if (zerosol && opts->min_moves == 0) {
398 append_alg(s, new_alg(""));
399 opts->min_moves = 1;
400 if (opts->verbose)
401 printf("Step is already solved"
402 "(empty alg is a solution)\n");
403 } 94 }
404 95
405 for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) { 96 optimal = opts->max_moves;
97 stop = false;
98 for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) {
406 if (opts->verbose) 99 if (opts->verbose)
407 fprintf(stderr, "Searching depth %d\n", d); 100 fprintf(stderr, "Searching depth %d\n", d);
408 101
409 for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) { 102 for (i = 0; solver[i] != NULL && !stop; i++) {
410 if (!ready[i]) 103 if (!ready[i])
411 continue; 104 continue;
412 105
413 arg[i].d = d; 106 arg[i].d = d;
414 multidfs(&arg[i]); 107 threader->dispatch(&arg[i], sols, solver[i], threader);
415
416 if (s->len > 0 && op == -1)
417 op = d;
418 }
419 }
420
421 for (i = 0; cs->step[i] != NULL; i++)
422 free(c[i]);
423
424 return s;
425}
426 108
427/* TODO: make more general! */ 109 if (sols->len > 0)
428Alg * 110 optimal = MIN(optimal, d);
429solve_2phase(Cube *cube, int nthreads)
430{
431 int bestlen, newb;
432 Alg *bestalg, *ret;
433 AlgList *sols1, *sols2;
434 AlgListNode *i;
435 Cube c;
436 SolveOptions opts1, opts2;
437
438 opts1.min_moves = 0;
439 opts1.max_moves = 13;
440 opts1.max_solutions = 20;
441 opts1.nthreads = nthreads;
442 opts1.optimal = 3;
443 opts1.can_niss = false;
444 opts1.verbose = false;
445 opts1.all = true;
446 111
447 opts2.min_moves = 0; 112 stop = sols->len >= opts->max_solutions;
448 opts2.max_moves = 19;
449 opts2.max_solutions = 1;
450 opts2.nthreads = nthreads;
451 opts2.can_niss = false;
452 opts2.verbose = false;
453
454 /* We skip step1 if it is solved on U/D */
455 if (check_drud(cube)) {
456 sols1 = new_alglist();
457 append_alg(sols1, new_alg(""));
458 } else {
459 sols1 = solve(cube, &drud_HTM, &opts1);
460 }
461 bestalg = new_alg("");
462 bestlen = 999;
463 for (i = sols1->first; i != NULL; i = i->next) {
464 copy_cube(cube, &c);
465 apply_alg(i->alg, &c);
466 sols2 = solve(&c, &dranyfin_DR, &opts2);
467
468 if (sols2->len > 0) {
469 newb = i->alg->len + sols2->first->alg->len;
470 if (newb < bestlen) {
471 bestlen = newb;
472 copy_alg(i->alg, bestalg);
473 compose_alg(bestalg, sols2->first->alg);
474 }
475 } 113 }
476 114 stop = stop ||
477 free_alglist(sols2); 115 (opts->optimal != -1 && d >= opts->optimal + optimal);
478 } 116 }
479 117
480 free_alglist(sols1); 118 return sols;
481
482 ret = cleanup(bestalg);
483 free_alg(bestalg);
484
485 return ret;
486} 119}
diff --git a/src/solve.h b/src/solve.h
index 9a284ff..b09c81b 100644
--- a/src/solve.h
+++ b/src/solve.h
@@ -2,10 +2,52 @@
2#define SOLVE_H 2#define SOLVE_H
3 3
4#include "moves.h" 4#include "moves.h"
5#include "steps.h"
6#include "trans.h"
7 5
8AlgList * solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts); 6#define MAX_SOLVERS 99
9Alg * solve_2phase(Cube *cube, int nthreads); 7
8typedef struct dfsarg DfsArg;
9typedef struct threader Threader;
10typedef struct solver Solver;
11
12/* TODO: add solver and threader in DfsData, remove from dispatch args and similar */
13
14struct dfsarg {
15 void * cubedata;
16 void * threaddata;
17 SolveOptions * opts;
18 int d;
19 bool niss;
20 Alg * current_alg;
21};
22
23struct threader {
24 void (*append_sol)(Alg *, void *);
25 void (*dispatch)(DfsArg *, AlgList *, Solver *, Threader *);
26 int (*get_nsol)(void *);
27/* TODO: threader should have param, like solver? */
28};
29
30struct solver {
31 Moveset * moveset;
32 bool (*move_check_stop)(void *, DfsArg *, Threader *);
33 Alg * (*validate_solution)(void *, Alg *);
34 bool (*niss_makes_sense)(void *, void *, Alg *);
35/* TODO: move param to somewhere where it makes more sense */
36 void * param;
37/* TODO: the following should be part of a generic cube description */
38/* TODO: remove alloc? */
39 void * (*alloc_cubedata)(void *);
40 void (*copy_cubedata)(void *, void *, void *);
41 void (*free_cubedata)(void *, void *);
42 void (*invert_cube)(void *, void *);
43 bool (*is_solved)(void *, void *);
44 void (*apply_alg)(void *, void *, Alg *);
45/* TODO: remove dependence on Cube, preparation should be done before */
46 void * (*prepare_cube)(void *, Cube *);
47};
48
49void dfs(DfsArg *, Solver *, Threader *);
50/* TODO: remove dependence on Cube, preparation should be done before */
51AlgList * solve(Cube *, SolveOptions *, Solver **, Threader *);
10 52
11#endif 53#endif
diff --git a/src/solver_step.c b/src/solver_step.c
new file mode 100644
index 0000000..5c9d149
--- /dev/null
+++ b/src/solver_step.c
@@ -0,0 +1,296 @@
1#include "solver_step.h"
2
3typedef struct {
4 Cube * cube;
5 uint64_t * val;
6 Trans * t;
7} CubeData;
8
9static void apply_alg_cubedata(void *, void *, Alg *);
10static void init_indexes(Step *, CubeData *);
11static void * prepare_cube(void *, Cube *);
12static bool move_check_stop_eager(void *, DfsArg *, Threader *);
13static bool move_check_stop_lazy(void *, DfsArg *, Threader *);
14static bool move_check_stop_nonsol(void *, DfsArg *, Threader *);
15static bool is_solved_step(void *, void *);
16static Alg * validate_solution(void *, Alg *);
17static void * alloc_cubedata(void *);
18static void copy_cubedata(void *, void *, void *);
19static void free_cubedata(void *, void *);
20static void invert_cubedata(void *, void *);
21static bool niss_makes_sense(void *, void *, Alg *);
22static Solver * new_stepsolver_nocheckstop(Step *step);
23
24static void
25apply_alg_cubedata(void *param, void *cubedata, Alg *alg)
26{
27 Step *s = (Step *)param;
28 CubeData *data = (CubeData *)cubedata;
29
30 apply_alg(alg, data->cube);
31 init_indexes(s, data);
32}
33
34static void
35init_indexes(Step *step, CubeData *data)
36{
37 int i;
38 Cube moved;
39 Trans t, tt;
40
41 for (i = 0; i < step->n_coord; i++) {
42 t = step->coord_trans[i];
43 copy_cube(data->cube, &moved);
44 apply_trans(t, &moved);
45 data->val[i] = index_coord(step->coord[i], &moved, &tt);
46 data->t[i] = transform_trans(tt, t);
47 }
48}
49
50static void *
51prepare_cube(void *param, Cube *cube)
52{
53 int i;
54 Step *s;
55 CubeData *data;
56
57 s = (Step *)param;
58
59 for (i = 0; i < s->n_coord; i++) {
60 s->pd[i] = malloc(sizeof(PruneData));
61 s->pd[i]->moveset = s->moveset;
62/* TODO: check if moveset initialization works fine,
63 e.g. if there is a variable to save the initialized status
64 or if it gets initialized multiple times */
65 init_moveset(s->moveset);
66 s->pd[i]->coord = s->coord[i];
67 gen_coord(s->coord[i]);
68 s->pd[i]->compact = s->pd_compact[i];
69 s->pd[i] = genptable(s->pd[i], 4); /* TODO: threads */
70 }
71
72 data = alloc_cubedata(param);
73 data->cube = malloc(sizeof(Cube));
74 copy_cube(cube, data->cube);
75 init_indexes(s, data);
76
77 return data;
78}
79
80static bool
81move_check_stop_eager(void *param, DfsArg *arg, Threader *threader)
82{
83 int nsol;
84
85 if (move_check_stop_nonsol(param, arg, threader))
86 return true;
87
88 nsol = threader->get_nsol(arg->threaddata);
89 return nsol >= arg->opts->max_solutions;
90}
91
92static bool
93move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader)
94{
95 int nsol;
96
97 nsol = threader->get_nsol(arg->threaddata);
98 if (nsol >= arg->opts->max_solutions)
99 return true;
100
101 return move_check_stop_nonsol(param, arg, threader);
102}
103
104static bool
105move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader)
106{
107 int i, goal, bound;
108 Move mm, lastmove;
109 Trans tt = uf;
110 CubeData *data;
111 Step *s;
112
113 s = (Step *)param;
114 data = (CubeData *)arg->cubedata;
115
116 bound = 0;
117 goal = arg->d - arg->current_alg->len;
118/* TODO: check if len is 0 */
119 lastmove = arg->current_alg->move[arg->current_alg->len-1];
120 for (i = 0; i < s->n_coord; i++) {
121 mm = transform_move(data->t[i], lastmove);
122 data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt);
123 data->t[i] = transform_trans(tt, data->t[i]);
124
125 bound = MAX(bound, ptableval(s->pd[i], data->val[i]));
126 if (arg->opts->can_niss && !arg->niss)
127 bound = MIN(1, bound);
128
129 if (bound > goal) {
130 return true;
131 }
132 }
133
134 return false;
135}
136
137static bool
138is_solved_step(void *param, void *cubedata)
139{
140 int i;
141 Step *s;
142 CubeData *data;
143
144 s = (Step *)param;
145 data = (CubeData *)cubedata;
146
147 for (i = 0; i < s->n_coord; i++)
148 if (data->val[i] != 0)
149 return false;
150
151 return true;
152}
153
154static Alg *
155validate_solution(void *param, Alg *alg)
156{
157 return ((Step *)param)->is_valid(alg);
158}
159
160static void *
161alloc_cubedata(void *param)
162{
163 Step *s;
164 CubeData *data;
165
166 s = (Step *)param;
167
168 data = malloc(sizeof(CubeData));
169 /* We do not need to allocate a cube */
170 data->val = malloc(s->n_coord * sizeof(uint64_t));
171 data->t = malloc(s->n_coord * sizeof(Trans));
172
173 return data;
174}
175
176static void
177copy_cubedata(void *param, void *src, void *dst)
178{
179 int i;
180 Step *s;
181 CubeData *newdata, *olddata;
182
183 s = (Step *)param;
184 olddata = (CubeData *)src;
185 newdata = (CubeData *)dst;
186
187 /* Copy reference: we never move the cube */
188 newdata->cube = olddata->cube;
189 for (i = 0; i < s->n_coord; i++) {
190 newdata->val[i] = olddata->val[i];
191 newdata->t[i] = olddata->t[i];
192 }
193}
194
195static void
196free_cubedata(void *param, void *cubedata)
197{
198 CubeData *data;
199
200 data = (CubeData *)cubedata;
201
202 free(data->t);
203 free(data->val);
204 /* We do not free the cube */
205 free(data);
206}
207
208static void
209invert_cubedata(void *param, void *cubedata)
210{
211 Step *s;
212 CubeData *data;
213
214 s = (Step *)param;
215 data = (CubeData *)cubedata;
216
217 invert_cube(data->cube);
218 init_indexes(s, data);
219}
220
221static bool
222niss_makes_sense(void *param, void *cubedata, Alg *alg)
223{
224 Step *s;
225 CubeData *data;
226
227 s = (Step *)param;
228 data = (CubeData *)cubedata;
229
230 if (s->final)
231 return false;
232
233 if (alg->len_normal == 0)
234 return true;
235
236 Move m = inverse_move(alg->move_normal[alg->len_normal-1]);
237 for (int i = 0; i < s->n_coord; i++) {
238 Move mm = transform_move(data->t[i], m);
239 uint64_t u = move_coord(s->coord[i], mm, 0, NULL);
240 if (ptableval(s->pd[i], u) > 0)
241 return true;
242 }
243
244 return false;
245}
246
247static Solver *
248new_stepsolver_nocheckstop(Step *step)
249{
250 Solver *solver;
251
252 solver = malloc(sizeof(Solver));
253
254 solver->moveset = step->moveset;
255 solver->param = step;
256
257 solver->apply_alg = apply_alg_cubedata;
258 solver->prepare_cube = prepare_cube;
259 solver->is_solved = is_solved_step;
260 solver->validate_solution = validate_solution;
261 solver->alloc_cubedata = alloc_cubedata;
262 solver->copy_cubedata = copy_cubedata;
263 solver->free_cubedata = free_cubedata;
264 solver->invert_cube = invert_cubedata;
265 solver->niss_makes_sense = niss_makes_sense;
266
267 return solver;
268}
269
270Solver *
271new_stepsolver_eager(Step *step)
272{
273 Solver *solver;
274
275 solver = new_stepsolver_nocheckstop(step);
276 solver->move_check_stop = move_check_stop_eager;
277
278 return solver;
279}
280
281Solver *
282new_stepsolver_lazy(Step *step)
283{
284 Solver *solver;
285
286 solver = new_stepsolver_nocheckstop(step);
287 solver->move_check_stop = move_check_stop_lazy;
288
289 return solver;
290}
291
292void
293free_stepsolver(Solver *solver)
294{
295 free(solver);
296}
diff --git a/src/solver_step.h b/src/solver_step.h
new file mode 100644
index 0000000..f68d077
--- /dev/null
+++ b/src/solver_step.h
@@ -0,0 +1,12 @@
1#ifndef SOLVER_STEP_H
2#define SOLVER_STEP_H
3
4#include "cube.h"
5#include "solve.h"
6#include "steps.h"
7
8Solver *new_stepsolver_eager(Step *);
9Solver *new_stepsolver_lazy(Step *);
10void free_stepsolver(Solver *);
11
12#endif
diff --git a/src/steps.c b/src/steps.c
index 2f5fd2c..cdba763 100644
--- a/src/steps.c
+++ b/src/steps.c
@@ -106,11 +106,12 @@ check_htr(Cube *cube)
106 return true; 106 return true;
107} 107}
108 108
109bool 109Alg *
110validate_singlecw_ending(Alg *alg) 110validate_singlecw_ending(Alg *alg)
111{ 111{
112 int i; 112 int i;
113 bool nor, inv; 113 bool nor, inv;
114 Alg *ret;
114 Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE; 115 Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE;
115 116
116 for (i = 0; i < alg->len; i++) { 117 for (i = 0; i < alg->len; i++) {
@@ -126,11 +127,19 @@ validate_singlecw_ending(Alg *alg)
126 nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2)); 127 nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2));
127 inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i)); 128 inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i));
128 129
129 return nor && inv; 130 if (nor && inv) {
131 ret = new_alg("");
132 copy_alg(alg, ret);
133 } else {
134 ret = NULL;
135 }
136
137 return ret;
130} 138}
131 139
132/* Public functions **********************************************************/ 140/* Public functions **********************************************************/
133 141
142/*
134void 143void
135compute_ind(Step *s, Cube *cube, Movable *ind) 144compute_ind(Step *s, Cube *cube, Movable *ind)
136{ 145{
@@ -147,6 +156,7 @@ compute_ind(Step *s, Cube *cube, Movable *ind)
147 ind[i].t = transform_trans(tt, t); 156 ind[i].t = transform_trans(tt, t);
148 } 157 }
149} 158}
159*/
150 160
151void 161void
152prepare_cs(ChoiceStep *cs, SolveOptions *opts) 162prepare_cs(ChoiceStep *cs, SolveOptions *opts)
diff --git a/src/steps.h b/src/steps.h
index 0511b27..206f8b4 100644
--- a/src/steps.h
+++ b/src/steps.h
@@ -2,6 +2,7 @@
2#define STEPS_H 2#define STEPS_H
3 3
4#include "pruning.h" 4#include "pruning.h"
5#include "movesets.h"
5 6
6bool check_centers(Cube *cube); 7bool check_centers(Cube *cube);
7bool check_coud_HTM(Cube *cube); 8bool check_coud_HTM(Cube *cube);
@@ -13,10 +14,10 @@ bool check_cornershtr(Cube *cube);
13bool check_eofb(Cube *cube); 14bool check_eofb(Cube *cube);
14bool check_drud(Cube *cube); 15bool check_drud(Cube *cube);
15bool check_htr(Cube *cube); 16bool check_htr(Cube *cube);
16void compute_ind(Step *a, Cube *cube, Movable *ind); 17/*void compute_ind(Step *a, Cube *cube, Movable *ind);*/
17void prepare_cs(ChoiceStep *cs, SolveOptions *opts); 18void prepare_cs(ChoiceStep *cs, SolveOptions *opts);
18bool always_valid(Alg *alg); 19bool always_valid(Alg *alg);
19bool validate_singlecw_ending(Alg *alg); 20Alg * validate_singlecw_ending(Alg *alg);
20 21
21#ifndef STEPS_C 22#ifndef STEPS_C
22 23
diff --git a/src/threader_eager.c b/src/threader_eager.c
new file mode 100644
index 0000000..7013518
--- /dev/null
+++ b/src/threader_eager.c
@@ -0,0 +1,162 @@
1#include <pthread.h>
2#include "threader_eager.h"
3
4typedef struct {
5 AlgList * sols;
6 pthread_mutex_t * sols_mutex;
7} ThreadData;
8
9typedef struct {
10 DfsArg * arg;
11 Solver * solver;
12 Threader * threader;
13 AlgList * starts;
14 AlgListNode ** node;
15 pthread_mutex_t * start_mutex;
16} ThreadInitData;
17
18static void append_sol(Alg *, void *);
19static void * instance_thread(void *);
20static void dispatch(DfsArg *, AlgList *, Solver *, Threader *);
21static AlgList * possible_starts(DfsArg *, Solver *);
22static int get_nsol(void *);
23
24Threader threader_eager = {
25 .append_sol = append_sol,
26 .dispatch = dispatch,
27 .get_nsol = get_nsol,
28};
29
30static void
31append_sol(Alg *alg, void *threaddata)
32{
33 ThreadData *td = (ThreadData *)threaddata;
34
35 pthread_mutex_lock(td->sols_mutex);
36 append_alg(td->sols, alg);
37 pthread_mutex_unlock(td->sols_mutex);
38}
39
40static AlgList *
41possible_starts(DfsArg *arg, Solver *solver)
42{
43 AlgList *ret = new_alglist();
44
45 if (solver->is_solved(solver->param, arg->cubedata)) {
46 if (arg->opts->min_moves == 0)
47 append_sol(new_alg(""), arg->threaddata);
48 return ret;
49 }
50
51 for (int i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) {
52 Move m = solver->moveset->sorted_moves[i];
53 Alg *alg = new_alg("");
54 append_move(alg, m, false);
55 append_alg(ret, alg);
56 free_alg(alg);
57
58/* TODO: check if step not final */
59 if (arg->opts->can_niss) {
60 alg = new_alg("");
61 append_move(alg, m, true);
62 append_alg(ret, alg);
63 free_alg(alg);
64 }
65 }
66
67 return ret;
68}
69
70static void *
71instance_thread(void *arg)
72{
73 ThreadInitData *tid = (ThreadInitData *)arg;
74
75 while (true) {
76 pthread_mutex_lock(tid->start_mutex);
77 AlgListNode *node = *(tid->node);
78 if (node == NULL) {
79 pthread_mutex_unlock(tid->start_mutex);
80 break;
81 }
82 *(tid->node) = (*(tid->node))->next;
83 pthread_mutex_unlock(tid->start_mutex);
84
85 void *data = tid->solver->alloc_cubedata(tid->solver->param);
86 tid->solver->copy_cubedata(
87 tid->solver->param, tid->arg->cubedata, data);
88 tid->solver->apply_alg(
89 tid->solver->param, data, node->alg);
90 bool inv = node->alg->inv[node->alg->len-1];
91 if (inv)
92 tid->solver->invert_cube(
93 tid->solver->param, data);
94
95 DfsArg newarg;
96 newarg.cubedata = data;
97 newarg.threaddata = tid->arg->threaddata;
98 newarg.opts = tid->arg->opts;
99 newarg.d = tid->arg->d;
100 newarg.niss = inv;
101 newarg.current_alg = new_alg("");
102 copy_alg(node->alg, newarg.current_alg);
103
104 dfs(&newarg, tid->solver, tid->threader);
105
106 tid->solver->free_cubedata(tid->solver->param, data);
107 free_alg(newarg.current_alg);
108 }
109
110 return NULL;
111}
112
113static void
114dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader)
115{
116 int nthreads = arg->opts->nthreads;
117 ThreadInitData tid[nthreads];
118 pthread_t t[nthreads];
119
120 pthread_mutex_t *sols_mutex = malloc(sizeof(pthread_mutex_t));
121 pthread_mutex_init(sols_mutex, NULL);
122
123 arg->threaddata = malloc(sizeof(ThreadData));
124 ThreadData *td = (ThreadData *)arg->threaddata;
125 td->sols = sols;
126 td->sols_mutex = sols_mutex;
127
128 AlgList *starts = possible_starts(arg, solver);
129 AlgListNode *node = starts->first;
130 pthread_mutex_t *start_mutex = malloc(sizeof(pthread_mutex_t));
131 pthread_mutex_init(start_mutex, NULL);
132 for (int i = 0; i < nthreads; i++) {
133 tid[i].arg = arg;
134 tid[i].solver = solver;
135 tid[i].threader = threader;
136 tid[i].starts = starts;
137 tid[i].node = &node;
138 tid[i].start_mutex = start_mutex;
139
140 pthread_create(&t[i], NULL, instance_thread, &tid[i]);
141 }
142
143 for (int i = 0; i < nthreads; i++)
144 pthread_join(t[i], NULL);
145
146 free(td);
147 free(sols_mutex);
148 free_alglist(starts);
149 free(start_mutex);
150}
151
152static int
153get_nsol(void *threaddata)
154{
155 ThreadData *td = (ThreadData *)threaddata;
156
157 pthread_mutex_lock(td->sols_mutex);
158 int n = td->sols->len;
159 pthread_mutex_unlock(td->sols_mutex);
160
161 return n;
162}
diff --git a/src/threader_eager.h b/src/threader_eager.h
new file mode 100644
index 0000000..e39b27f
--- /dev/null
+++ b/src/threader_eager.h
@@ -0,0 +1,8 @@
1#ifndef THREADER_EAGER_H
2#define THREADER_EAGER_H
3
4#include "solve.h"
5
6extern Threader threader_eager;
7
8#endif
diff --git a/src/threader_single.c b/src/threader_single.c
new file mode 100644
index 0000000..232835d
--- /dev/null
+++ b/src/threader_single.c
@@ -0,0 +1,35 @@
1#include "threader_single.h"
2
3static void append_sol(Alg *, void *);
4static void dispatch(DfsArg *, AlgList *, Solver *, Threader *);
5static int get_nsol(void *);
6
7Threader threader_single = {
8 .append_sol = append_sol,
9 .dispatch = dispatch,
10 .get_nsol = get_nsol,
11};
12
13static void
14append_sol(Alg *alg, void *threaddata)
15{
16 append_alg((AlgList *)threaddata, alg);
17}
18
19static void
20dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader)
21{
22 arg->threaddata = sols;
23 arg->niss = false;
24 arg->current_alg = new_alg("");
25
26 dfs(arg, solver, threader);
27
28 free_alg(arg->current_alg);
29}
30
31static int
32get_nsol(void *threaddata)
33{
34 return ((AlgList *)threaddata)->len;
35}
diff --git a/src/threader_single.h b/src/threader_single.h
new file mode 100644
index 0000000..2c0bfab
--- /dev/null
+++ b/src/threader_single.h
@@ -0,0 +1,8 @@
1#ifndef THREADER_SINGLE_H
2#define THREADER_SINGLE_H
3
4#include "solve.h"
5
6extern Threader threader_single;
7
8#endif
diff --git a/tests/alg_tests.h b/tests/alg_tests.h
index 518b33e..a24b51f 100644
--- a/tests/alg_tests.h
+++ b/tests/alg_tests.h
@@ -7,6 +7,7 @@
7extern Test test_append_move; 7extern Test test_append_move;
8extern Test test_new_alg; 8extern Test test_new_alg;
9/* 9/*
10extern Test remove_last_move;
10extern Test test_compose_alg; 11extern Test test_compose_alg;
11extern Test test_inverse_alg; 12extern Test test_inverse_alg;
12extern Test test_on_inverse; 13extern Test test_on_inverse;

Generated with cgit - Back to sebastiano.tronto.net