1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#define SOLVE_C
#include "solve.h"
void
dfs(DfsArg *arg, Solver *solver, Threader *threader)
{
int i;
DfsArg newarg;
Alg *sol;
Move m;
if (arg->current_alg->len > arg->d)
return;
if (solver->is_solved(solver->param, arg->cubedata)) {
/* TODO: the "all" option should be re-implemented as setting
validate to null */
/* TODO: we also have to check if cancel with NISS;
we can't because we have no access to the s->final field
this should be done by the step's validator? */
sol = solver->validate_solution(solver->param,arg->current_alg);
bool accepted = sol != NULL;
bool too_short = arg->current_alg->len != arg->d;
if (accepted && !too_short) {
/* TODO: arg->t got lost in refactoring */
/* transform_alg(inverse_trans(arg->t), sol);*/
if (arg->opts->verbose)
print_alg(sol, false);
threader->append_sol(sol, arg->threaddata);
}
return;
}
if (arg->current_alg->len == arg->d)
return;
/* TODO: do not alloc */
newarg.cubedata = solver->alloc_cubedata(solver->param);
for (i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) {
m = solver->moveset->sorted_moves[i];
if (solver->moveset->can_append(arg->current_alg, m, arg->niss)
&& compare_last(arg->current_alg, m, arg->niss) >= 0) {
append_move(arg->current_alg, m, arg->niss);
solver->copy_cubedata(
solver->param, arg->cubedata, newarg.cubedata);
newarg.threaddata = arg->threaddata;
newarg.opts = arg->opts;
newarg.d = arg->d;
newarg.niss = arg->niss;
newarg.current_alg = arg->current_alg;
if (!solver->move_check_stop(
solver->param, &newarg, threader))
dfs(&newarg, solver, threader);
remove_last_move(arg->current_alg);
}
}
solver->free_cubedata(solver->param, newarg.cubedata);
if (arg->opts->can_niss && !arg->niss &&
solver->niss_makes_sense(
solver->param, arg->cubedata, arg->current_alg)) {
solver->invert_cube(solver->param, arg->cubedata);
arg->niss = true;
dfs(arg, solver, threader);
}
}
AlgList *
solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader)
{
int i, d, optimal;
bool ready[MAX_SOLVERS], stop, one_ready;
DfsArg arg[MAX_SOLVERS];
AlgList *sols;
one_ready = false;
for (i = 0; solver[i] != NULL; i++) {
arg[i].cubedata =
solver[i]->prepare_cube(solver[i]->param, cube);
arg[i].opts = opts;
ready[i] = arg[i].cubedata != NULL;
one_ready = one_ready || ready[i];
}
sols = new_alglist();
if (!one_ready) {
fprintf(stderr, "Cube not ready for solving\n");
return sols;
}
optimal = opts->max_moves;
stop = false;
for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) {
if (opts->verbose)
fprintf(stderr, "Searching depth %d\n", d);
for (i = 0; solver[i] != NULL && !stop; i++) {
if (!ready[i])
continue;
arg[i].d = d;
threader->dispatch(&arg[i], sols, solver[i], threader);
if (sols->len > 0)
optimal = MIN(optimal, d);
stop = sols->len >= opts->max_solutions;
}
stop = stop ||
(opts->optimal != -1 && d >= opts->optimal + optimal);
}
return sols;
}
|
