solve.c (3268B)
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 == NULL ? 24 arg->current_alg : 25 solver->validate_solution(solver->param, arg->current_alg); 26 bool accepted = sol != NULL; 27 bool too_short = arg->current_alg->len != arg->d; 28 29 if (accepted && !too_short) { 30 /* TODO: arg->t got lost in refactoring */ 31 /* transform_alg(inverse_trans(arg->t), sol);*/ 32 if (arg->opts->verbose) 33 print_alg(sol, false); 34 threader->append_sol(sol, arg->threaddata); 35 } 36 return; 37 } 38 39 if (arg->current_alg->len == arg->d) 40 return; 41 42 /* TODO: do not alloc */ 43 newarg.cubedata = solver->alloc_cubedata(solver->param); 44 for (i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) { 45 m = solver->moveset->sorted_moves[i]; 46 if (solver->moveset->can_append(arg->current_alg, m, arg->niss) 47 && compare_last(arg->current_alg, m, arg->niss) >= 0) { 48 append_move(arg->current_alg, m, arg->niss); 49 50 solver->copy_cubedata( 51 solver->param, arg->cubedata, newarg.cubedata); 52 newarg.threaddata = arg->threaddata; 53 newarg.opts = arg->opts; 54 newarg.d = arg->d; 55 newarg.niss = arg->niss; 56 newarg.current_alg = arg->current_alg; 57 if (!solver->move_check_stop( 58 solver->param, &newarg, threader)) 59 dfs(&newarg, solver, threader); 60 61 remove_last_move(arg->current_alg); 62 } 63 } 64 solver->free_cubedata(solver->param, newarg.cubedata); 65 66 if (arg->opts->can_niss && !arg->niss && 67 solver->niss_makes_sense( 68 solver->param, arg->cubedata, arg->current_alg)) { 69 solver->invert_cube(solver->param, arg->cubedata); 70 arg->niss = true; 71 dfs(arg, solver, threader); 72 } 73 } 74 75 AlgList * 76 solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader) 77 { 78 int i, d, optimal; 79 bool ready[MAX_SOLVERS], stop, one_ready; 80 DfsArg arg[MAX_SOLVERS]; 81 AlgList *sols; 82 83 one_ready = false; 84 for (i = 0; solver[i] != NULL; i++) { 85 arg[i].cubedata = 86 solver[i]->prepare_cube(solver[i]->param, cube); 87 arg[i].opts = opts; 88 ready[i] = arg[i].cubedata != NULL; 89 one_ready = one_ready || ready[i]; 90 } 91 92 sols = new_alglist(); 93 if (!one_ready) { 94 fprintf(stderr, "Cube not ready for solving\n"); 95 return sols; 96 } 97 98 optimal = opts->max_moves; 99 stop = false; 100 for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) { 101 if (opts->verbose) 102 fprintf(stderr, "Searching depth %d\n", d); 103 104 for (i = 0; solver[i] != NULL && !stop; i++) { 105 if (!ready[i]) 106 continue; 107 108 arg[i].d = d; 109 threader->dispatch(&arg[i], sols, solver[i], threader); 110 111 if (sols->len > 0) 112 optimal = MIN(optimal, d); 113 114 stop = sols->len >= opts->max_solutions; 115 } 116 stop = stop || 117 (opts->optimal != -1 && d >= opts->optimal + optimal); 118 } 119 120 /* TODO: some cleanup (free cubedata) */ 121 /* TODO: actually, preparation should be done somewhere else */ 122 123 return sols; 124 }