From 78dd90e360865af2685c1bb291d7926415fc53bb Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Wed, 24 Dec 2025 11:43:24 +0100 Subject: First small improvements --- src/solvers/h48/solve.h | 245 ++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 235 insertions(+), 10 deletions(-) (limited to 'src/solvers') diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index 4aa3799..10b22b9 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h @@ -27,8 +27,8 @@ typedef struct { solution_list_t *solution_list; int8_t lb_normal; int8_t lb_inverse; - bool use_lb_normal; - bool use_lb_inverse; + bool use_lb_normal; /* TODO remove? */ + bool use_lb_inverse; /* TODO remove? */ uint8_t h; uint8_t base; const uint32_t *cocsepdata; @@ -58,11 +58,34 @@ typedef struct { uint64_t tmask[H48_STARTING_MOVES]; } dfsarg_solve_h48_maketasks_t; +typedef struct { + uint8_t stop; + uint8_t pn; + uint8_t pi; + uint8_t lookups; + uint8_t fallbacks; + uint8_t nohalf_normal; + uint8_t nohalf_inverse; +} solve_h48_prune_return_t; + +typedef struct { + cube_t cube; + cube_t inverse; + const uint32_t *cocsepdata; + const unsigned char *h48data; + const unsigned char *eoesepdata; + uint8_t target; + uint8_t h48base; + uint8_t h48h; + uint8_t lb_inverse; +} solve_h48_prune_arg_t; + STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long, const unsigned char *, unsigned, char *, long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t [static 1]); +STATIC_INLINE solve_h48_prune_return_t solve_h48_prune(solve_h48_prune_arg_t); STATIC int64_t solve_h48_maketasks( dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1], solve_h48_task_t [static H48_STARTING_CUBES], int [static 1]); @@ -113,7 +136,6 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) uint8_t pval, pval_min, pval_eoesep; arg->movemask_normal = arg->movemask_inverse = MM18_ALLMOVES; - arg->nodes_visited++; n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; target = arg->target_depth - n; @@ -123,13 +145,11 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) return false; /* Preliminary probing using last computed bound, if possible */ - if ((arg->use_lb_normal && arg->lb_normal > target) || (arg->use_lb_inverse && arg->lb_inverse > target)) return true; - /* Preliminary corner probing */ - + /* Get cdata and do preliminary corner probing */ if (get_h48_cdata(arg->cube, arg->cocsepdata, &data) > target || get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv) > target) return true; @@ -191,15 +211,218 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) return false; } +STATIC_INLINE solve_h48_prune_return_t +solve_h48_prune(solve_h48_prune_arg_t arg) +{ + solve_h48_prune_return_t ret = {0}; + uint64_t c; + uint32_t dn, di; + uint8_t pmin, pe; + + ret.pi = arg.lb_inverse; + + /* We'll never get a bound higher than base + 3 */ + if (arg.h48base + 3 <= arg.target) + goto solve_h48_prune_return_false; + + /* Preliminary probing using last computed bound, if possible */ + if (arg.lb_inverse > arg.target) + goto solve_h48_prune_return_true; + + /* Get cdata and do preliminary corner probing */ + if (get_h48_cdata(arg.inverse, arg.cocsepdata, &di) > arg.target || + get_h48_cdata(arg.cube, arg.cocsepdata, &dn) > arg.target) + goto solve_h48_prune_return_true; + + if (arg.lb_inverse == 0) { + ret.lookups++; + c = coord_h48_edges( + arg.inverse, COCLASS(di), TTREP(di), arg.h48h); + ret.pi = get_h48_pval_and_min(arg.h48data, c, &pmin); + + if (ret.pi == 0) { + ret.fallbacks++; + pe = get_eoesep_pval_cube(arg.eoesepdata, arg.inverse); + ret.pi = MAX(pmin, pe); + } else { + ret.pi += arg.h48base; + } + } + + if (ret.pi > arg.target) + goto solve_h48_prune_return_true; + + ret.nohalf_normal = ret.pi == arg.target; + + ret.lookups++; + c = coord_h48_edges(arg.cube, COCLASS(dn), TTREP(dn), arg.h48h); + ret.pn = get_h48_pval_and_min(arg.h48data, c, &pmin); + + if (ret.pn == 0) { + ret.fallbacks++; + pe = get_eoesep_pval_cube(arg.eoesepdata, arg.cube); + ret.pn = MAX(pmin, pe); + } else { + ret.pn += arg.h48base; + } + + if (ret.pn > arg.target) + goto solve_h48_prune_return_true; + + ret.nohalf_inverse = ret.pn == arg.target; + +solve_h48_prune_return_false: + ret.stop = false; + return ret; + +solve_h48_prune_return_true: + ret.stop = true; + return ret; +} + +#if 1 + STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) { int64_t ret, n; - uint8_t m, nm, lbn, lbi, t; + uint8_t m, nm, nn, ni, lbn, lbi; + uint64_t mm_normal, mm_inverse; + cube_t backup_cube, backup_inverse; + solve_h48_prune_arg_t prune_arg; + solve_h48_prune_return_t prune; + + nn = arg->solution_moves->nmoves; + ni = arg->solution_moves->npremoves; + nm = nn + ni; + if (equal(arg->cube, SOLVED_CUBE)) { + if (arg->target_depth != nm) + return 0; + wrapthread_mutex_lock(arg->solutions_mutex); + ret = appendsolution(arg->solution_moves, H48_STARTING_MOVES, + arg->tmask, arg->solution_settings, arg->solution_list); + wrapthread_mutex_unlock(arg->solutions_mutex); + return ret; + } + + if (nm + 1 > arg->target_depth || + arg->solution_list->nsols >= arg->solution_settings->maxsolutions) + return 0; + + backup_cube = arg->cube; + backup_inverse = arg->inverse; + lbn = arg->lb_normal; + lbi = arg->lb_inverse; + mm_normal = arg->movemask_normal; + mm_inverse = arg->movemask_inverse; + + ret = 0; + + prune_arg = (solve_h48_prune_arg_t){ + .cocsepdata = arg->cocsepdata, + .h48data = arg->h48data, + .eoesepdata = arg->h48data_fallback_eoesep, /* TODO rmove? */ + .target = arg->target_depth - (nm + 1), + .h48base = arg->base, + .h48h = arg->h, + .lb_inverse = 0, + }; + if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) { + arg->solution_moves->nmoves++; + for (m = 0; m < 18; m++) { + if (!(mm_normal & MM_SINGLE(m))) + continue; + + prune_arg.cube = move(backup_cube, m); + prune_arg.inverse = premove(backup_inverse, m); + prune_arg.lb_inverse = m % 3 == 1 ? lbi : 0; + + prune = solve_h48_prune(prune_arg); + + arg->nodes_visited++; + arg->table_lookups += prune.lookups; + arg->table_fallbacks += prune.fallbacks; + + if (prune.stop) + continue; + + arg->solution_moves->moves[nn] = m; + arg->cube = prune_arg.cube; + arg->inverse = prune_arg.inverse; + arg->lb_inverse = prune.pi; + arg->lb_normal = prune.pn; + arg->movemask_normal = allowedmask[movebase(m)]; + if (prune.nohalf_normal) + arg->movemask_normal &= MM18_NOHALFTURNS; + arg->movemask_inverse = mm_inverse; + if (prune.nohalf_inverse) + arg->movemask_inverse &= MM18_NOHALFTURNS; + + n = solve_h48_dfs(arg); + + if (n < 0) + return n; + ret += n; + } + arg->solution_moves->nmoves--; + } else { + arg->solution_moves->npremoves++; + for (m = 0; m < 18; m++) { + if(!(mm_inverse & MM_SINGLE(m))) + continue; + + prune_arg.cube = move(backup_inverse, m); + prune_arg.inverse = premove(backup_cube, m); + prune_arg.lb_inverse = m % 3 == 1 ? lbn : 0; + prune = solve_h48_prune(prune_arg); + + arg->nodes_visited++; + arg->table_lookups += prune.lookups; + arg->table_fallbacks += prune.fallbacks; + + if (prune.stop) + continue; + + arg->solution_moves->premoves[ni] = m; + arg->inverse = prune_arg.cube; + arg->cube = prune_arg.inverse; + arg->lb_normal = prune.pi; + arg->lb_inverse = prune.pn; + arg->movemask_normal = mm_normal; + if (prune.nohalf_inverse) + arg->movemask_normal &= MM18_NOHALFTURNS; + arg->movemask_inverse = allowedmask[movebase(m)]; + if (prune.nohalf_normal) + arg->movemask_inverse &= MM18_NOHALFTURNS; + + n = solve_h48_dfs(arg); + + if (n < 0) + return n; + ret += n; + } + arg->solution_moves->npremoves--; + } + + arg->cube = backup_cube; + arg->inverse = backup_inverse; + + return ret; +} + +#else + +STATIC int64_t +solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) +{ + int64_t ret, n; + uint8_t m, nm, lbn, lbi; uint64_t mm_normal, mm_inverse; bool ulbi, ulbn; cube_t backup_cube, backup_inverse; + arg->nodes_visited++; + nm = arg->solution_moves->nmoves + arg->solution_moves->npremoves; if (equal(arg->cube, SOLVED_CUBE)) { if (arg->target_depth != nm) @@ -214,8 +437,7 @@ solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) if (solve_h48_stop(arg)) return 0; - t = arg->solution_list->shortest_sol + arg->solution_settings->optimal; - if (nm + 1 > MIN(t, arg->target_depth) || + if (nm + 1 > arg->target_depth || arg->solution_list->nsols >= arg->solution_settings->maxsolutions) return 0; @@ -281,6 +503,8 @@ solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) return ret; } +#endif + STATIC void * solve_h48_runthread(void *arg) { @@ -313,7 +537,8 @@ solve_h48_runthread(void *arg) dfsarg->lb_inverse = 0; dfsarg->use_lb_normal = false; dfsarg->use_lb_inverse = false; - dfsarg->movemask_normal = MM18_ALLMOVES; + dfsarg->movemask_normal = allowedmask[ + movebase(dfsarg->tasks[i].moves[H48_STARTING_MOVES-1])]; dfsarg->movemask_inverse = MM18_ALLMOVES; dfsarg->tmask = dfsarg->tasks[i].tmask; -- cgit v1.3