aboutsummaryrefslogtreecommitdiff
path: root/src/solve.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/solve.c')
-rw-r--r--src/solve.c122
1 files changed, 0 insertions, 122 deletions
diff --git a/src/solve.c b/src/solve.c
deleted file mode 100644
index 2d0c94d..0000000
--- a/src/solve.c
+++ /dev/null
@@ -1,122 +0,0 @@
1#define SOLVE_C
2
3#include "solve.h"
4
5void
6dfs(DfsArg *arg, Solver *solver, Threader *threader)
7{
8 int i;
9 DfsArg newarg;
10 Alg *sol;
11 Move m;
12
13 if (arg->current_alg->len > arg->d)
14 return;
15
16 if (solver->is_solved(solver->param, arg->cubedata)) {
17/* TODO: the "all" option should be re-implemented as setting
18validate to null */
19
20/* TODO: we also have to check if cancel with NISS;
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;
26
27 if (accepted && !too_short) {
28/* TODO: arg->t got lost in refactoring */
29/* transform_alg(inverse_trans(arg->t), sol);*/
30 if (arg->opts->verbose)
31 print_alg(sol, false);
32 threader->append_sol(sol, arg->threaddata);
33 }
34 return;
35 }
36
37 if (arg->current_alg->len == arg->d)
38 return;
39
40/* TODO: do not alloc */
41 newarg.cubedata = solver->alloc_cubedata(solver->param);
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);
47
48 solver->copy_cubedata(
49 solver->param, arg->cubedata, newarg.cubedata);
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);
58
59 remove_last_move(arg->current_alg);
60 }
61 }
62 solver->free_cubedata(solver->param, newarg.cubedata);
63
64 if (arg->opts->can_niss && !arg->niss &&
65 solver->niss_makes_sense(
66 solver->param, arg->cubedata, arg->current_alg)) {
67 solver->invert_cube(solver->param, arg->cubedata);
68 arg->niss = true;
69 dfs(arg, solver, threader);
70 }
71}
72
73AlgList *
74solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader)
75{
76 int i, d, optimal;
77 bool ready[MAX_SOLVERS], stop, one_ready;
78 DfsArg arg[MAX_SOLVERS];
79 AlgList *sols;
80
81 one_ready = false;
82 for (i = 0; solver[i] != NULL; i++) {
83 arg[i].cubedata =
84 solver[i]->prepare_cube(solver[i]->param, cube);
85 arg[i].opts = opts;
86 ready[i] = arg[i].cubedata != NULL;
87 one_ready = one_ready || ready[i];
88 }
89
90 sols = new_alglist();
91 if (!one_ready) {
92 fprintf(stderr, "Cube not ready for solving\n");
93 return sols;
94 }
95
96 optimal = opts->max_moves;
97 stop = false;
98 for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) {
99 if (opts->verbose)
100 fprintf(stderr, "Searching depth %d\n", d);
101
102 for (i = 0; solver[i] != NULL && !stop; i++) {
103 if (!ready[i])
104 continue;
105
106 arg[i].d = d;
107 threader->dispatch(&arg[i], sols, solver[i], threader);
108
109 if (sols->len > 0)
110 optimal = MIN(optimal, d);
111
112 stop = sols->len >= opts->max_solutions;
113 }
114 stop = stop ||
115 (opts->optimal != -1 && d >= opts->optimal + optimal);
116 }
117
118/* TODO: some cleanup (free cubedata) */
119/* TODO: actually, preparation should be done somewhere else */
120
121 return sols;
122}

Generated with cgit - Back to sebastiano.tronto.net