diff options
Diffstat (limited to 'src/solve.c')
| -rw-r--r-- | src/solve.c | 122 |
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 | |||
| 5 | void | ||
| 6 | dfs(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 | ||
| 18 | validate to null */ | ||
| 19 | |||
| 20 | /* TODO: we also have to check if cancel with NISS; | ||
| 21 | we can't because we have no access to the s->final field | ||
| 22 | this 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 | |||
| 73 | AlgList * | ||
| 74 | solve(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 | } | ||
