generic.h (3062B)
1 typedef struct { 2 cube_t cube; 3 uint8_t depth; 4 int64_t maxsols; 5 char **nextsol; 6 int64_t *nsols; 7 uint8_t nmoves; 8 uint8_t moves[20]; 9 uint8_t (*estimate)(cube_t); 10 } dfsarg_generic_t; 11 12 STATIC void solve_generic_appendsolution(dfsarg_generic_t *); 13 STATIC int solve_generic_dfs(dfsarg_generic_t *); 14 STATIC int64_t solve_generic(cube_t, const char *, int8_t, int8_t, int64_t, 15 int8_t, char *, uint8_t (*)(cube_t)); 16 STATIC uint8_t estimate_simple(cube_t); 17 STATIC int64_t solve_simple(cube_t, int8_t, int8_t, int64_t, int8_t, char *); 18 19 STATIC void 20 solve_generic_appendsolution(dfsarg_generic_t *arg) 21 { 22 int strl; 23 24 strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); 25 LOG("Solution found: %s\n", *arg->nextsol); 26 *arg->nextsol += strl; 27 **arg->nextsol = '\n'; 28 (*arg->nextsol)++; 29 (*arg->nsols)++; 30 } 31 32 STATIC int 33 solve_generic_dfs(dfsarg_generic_t *arg) 34 { 35 dfsarg_generic_t nextarg; 36 uint8_t m, bound; 37 int64_t ret; 38 39 if (!allowednextmove(arg->moves, arg->nmoves)) 40 return 0; 41 42 if (arg->nmoves > 0) 43 arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]); 44 45 bound = arg->estimate(arg->cube); 46 if (*arg->nsols == arg->maxsols || bound + arg->nmoves > arg->depth) 47 return 0; 48 49 if (bound == 0) { 50 if (arg->nmoves != arg->depth) 51 return 0; 52 solve_generic_appendsolution(arg); 53 return 1; 54 } 55 56 nextarg = *arg; 57 nextarg.nmoves = arg->nmoves + 1; 58 for (m = 0, ret = 0; m < 18; m++) { 59 nextarg.cube = arg->cube; 60 nextarg.moves[arg->nmoves] = m; 61 ret += solve_generic_dfs(&nextarg); 62 } 63 64 return ret; 65 } 66 67 STATIC int64_t 68 solve_generic( 69 cube_t cube, 70 const char *nisstype, 71 /* TODO: handle NISS */ 72 int8_t minmoves, 73 int8_t maxmoves, 74 int64_t maxsols, 75 int8_t optimal, 76 char *sols, 77 uint8_t (*estimate)(cube_t) 78 /* TODO: add validator */ 79 /* TODO: maybe add data for estimate */ 80 /* TODO: add moveset (and allowednext?) */ 81 ) 82 { 83 dfsarg_generic_t arg; 84 int64_t ret, tmp, first; 85 86 if (issolved(cube)) { 87 LOG("solve: cube is already solved\n"); 88 sols[0] = '\n'; 89 sols[1] = 0; 90 return 1; 91 } 92 93 if (estimate == NULL) { 94 LOG("solve: 'estimate' is NULL\n"); 95 return -1; 96 } 97 98 arg = (dfsarg_generic_t) { 99 .cube = cube, 100 .maxsols = maxsols, 101 .nextsol = &sols, 102 .nsols = &ret, 103 .nmoves = 0, 104 .moves = {0}, 105 .estimate = estimate, 106 }; 107 108 ret = 0; 109 first = -1; 110 for (arg.depth = minmoves; arg.depth <= maxmoves; arg.depth++) { 111 tmp = solve_generic_dfs(&arg); 112 if (tmp != 0) 113 first = arg.depth; 114 115 LOG("Found %" PRId64 " solution%s at depth %" PRIu8 "\n", 116 tmp, tmp == 1 ? "" : "s", arg.depth); 117 118 if (ret >= maxsols) 119 break; 120 121 if (optimal >= 0 && first >= 0 && arg.depth - first == optimal) 122 break; 123 } 124 125 DBG_ASSERT(ret <= maxsols, ret, 126 "solve: found more than 'maxsols' solutions\n"); 127 128 return ret; 129 } 130 131 STATIC uint8_t 132 estimate_simple(cube_t cube) 133 { 134 return issolved(cube) ? 0 : 1; 135 } 136 137 STATIC int64_t 138 solve_simple( 139 cube_t cube, 140 int8_t minmoves, 141 int8_t maxmoves, 142 int64_t maxsols, 143 int8_t optimal, 144 char *solutions 145 ) 146 { 147 return solve_generic( 148 cube, 149 "", 150 minmoves, 151 maxmoves, 152 maxsols, 153 optimal, 154 solutions, 155 &estimate_simple 156 ); 157 }