diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/solvers/generic/generic.h | 157 | ||||
| -rw-r--r-- | src/solvers/solvers.h | 1 |
2 files changed, 0 insertions, 158 deletions
diff --git a/src/solvers/generic/generic.h b/src/solvers/generic/generic.h deleted file mode 100644 index 1e0299b..0000000 --- a/src/solvers/generic/generic.h +++ /dev/null | |||
| @@ -1,157 +0,0 @@ | |||
| 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 | } | ||
diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h index 00a28c1..7b7f355 100644 --- a/src/solvers/solvers.h +++ b/src/solvers/solvers.h | |||
| @@ -1,3 +1,2 @@ | |||
| 1 | #include "tables.h" | 1 | #include "tables.h" |
| 2 | #include "generic/generic.h" | ||
| 3 | #include "h48/h48.h" | 2 | #include "h48/h48.h" |
