aboutsummaryrefslogtreecommitdiff
path: root/src/solvers
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers')
-rw-r--r--src/solvers/coord/solve.h147
-rw-r--r--src/solvers/h48/solve.h237
-rw-r--r--src/solvers/solutions.h213
-rw-r--r--src/solvers/solutions_types_macros.h24
-rw-r--r--src/solvers/solvers.h2
-rw-r--r--src/solvers/tables.h3
6 files changed, 359 insertions, 267 deletions
diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h
index fa160f8..c056adc 100644
--- a/src/solvers/coord/solve.h
+++ b/src/solvers/coord/solve.h
@@ -1,71 +1,21 @@
1typedef struct { 1typedef struct {
2 cube_t cube; 2 cube_t cube;
3 uint8_t depth; 3 uint8_t target_depth;
4 uint8_t nmoves; 4 solution_moves_t *solution_moves;
5 uint8_t moves[MAXLEN]; 5 solution_settings_t *solution_settings;
6 coord_t *coord; 6 coord_t *coord;
7 const void *coord_data; 7 const void *coord_data;
8 const uint8_t *ptable; 8 const uint8_t *ptable;
9 uint8_t trans; 9 solution_list_t *solution_list;
10 int64_t *nsols;
11 int64_t maxsolutions;
12 int optimal;
13 uint8_t *shortest_sol;
14 size_t solutions_size;
15 size_t *solutions_used;
16 char **solutions;
17} dfsarg_solve_coord_t; 10} dfsarg_solve_coord_t;
18 11
19STATIC int64_t solve_coord(cube_t, coord_t *, uint8_t, uint8_t, uint8_t, 12STATIC int64_t solve_coord(cube_t, coord_t *, uint8_t, uint8_t, uint8_t,
20 uint8_t, uint64_t, int, int, uint64_t, const void *, size_t, char *); 13 uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_t, char *);
21STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t, 14STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t,
22 uint8_t, uint64_t, int, int, uint64_t, const void *, size_t, char *); 15 uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_t, char *);
23STATIC int64_t solve_coord_appendsolution(dfsarg_solve_coord_t *);
24STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *); 16STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *);
25 17
26STATIC int64_t 18STATIC int64_t
27solve_coord_appendsolution(dfsarg_solve_coord_t *arg)
28{
29 uint8_t i, t, tmoves[MAXLEN];
30 int64_t strl;
31 uint64_t l;
32 char *m;
33
34 if (*arg->nsols >= arg->maxsolutions ||
35 arg->nmoves > *arg->shortest_sol + arg->optimal ||
36 (arg->coord->is_admissible != NULL &&
37 !arg->coord->is_admissible(arg->nmoves, arg->moves)))
38 return 0;
39
40 t = inverse_trans(arg->trans);
41 for (i = 0; i < arg->nmoves; i++)
42 tmoves[i] = transform_move(arg->moves[i], t);
43
44 sortparallel(arg->nmoves, tmoves);
45
46 l = arg->solutions_size - *arg->solutions_used;
47 m = *arg->solutions + *arg->solutions_used;
48 strl = writemoves(arg->nmoves, tmoves, l, m);
49 if (strl < 0)
50 goto solve_coord_appendsolution_error;
51
52 *arg->solutions_used += MAX(0, strl-1);
53
54 if (!appendchar(
55 arg->solutions_size, *arg->solutions, arg->solutions_used, '\n'))
56 goto solve_coord_appendsolution_error;
57
58 (*arg->nsols)++;
59 *arg->shortest_sol = MIN(*arg->shortest_sol, arg->nmoves);
60
61 return 1;
62
63solve_coord_appendsolution_error:
64 LOG("Could not append solution to buffer: size too small\n");
65 return NISSY_ERROR_BUFFER_SIZE;
66}
67
68STATIC int64_t
69solve_coord_dfs(dfsarg_solve_coord_t *arg) 19solve_coord_dfs(dfsarg_solve_coord_t *arg)
70{ 20{
71 uint8_t m, pval; 21 uint8_t m, pval;
@@ -77,25 +27,30 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg)
77 coord = arg->coord->coord(arg->cube, arg->coord_data); 27 coord = arg->coord->coord(arg->cube, arg->coord_data);
78 28
79 if (coord == 0) { 29 if (coord == 0) {
80 if (arg->nmoves != arg->depth) 30 if (arg->solution_moves->nmoves != arg->target_depth ||
31 (arg->coord->is_admissible != NULL &&
32 !arg->coord->is_admissible(arg->solution_moves->nmoves,
33 arg->solution_moves->moves)))
81 return 0; 34 return 0;
82 return solve_coord_appendsolution(arg); 35 return appendsolution(arg->solution_moves,
36 arg->solution_settings, arg->solution_list);
83 } 37 }
84 38
85 pval = get_coord_pval(arg->coord, arg->ptable, coord); 39 pval = get_coord_pval(arg->coord, arg->ptable, coord);
86 if (arg->nmoves + pval > arg->depth) 40 if (arg->solution_moves->nmoves + pval > arg->target_depth)
87 return 0; 41 return 0;
88 42
89 backup_cube = arg->cube; 43 backup_cube = arg->cube;
90 44
91 ret = 0; 45 ret = 0;
92 mm = allowednextmove_mask(arg->nmoves, arg->moves); 46 mm = allowednextmove_mask(
93 arg->nmoves++; 47 arg->solution_moves->nmoves, arg->solution_moves->moves);
94 for (m = 0; m < 18; m++) { 48 arg->solution_moves->nmoves++;
49 for (m = 0; m < NMOVES; m++) {
95 if (!(mm & (1 << m))) 50 if (!(mm & (1 << m)))
96 continue; 51 continue;
97 52
98 arg->moves[arg->nmoves-1] = m; 53 arg->solution_moves->moves[arg->solution_moves->nmoves-1] = m;
99 arg->cube = move(backup_cube, m); 54 arg->cube = move(backup_cube, m);
100 n = solve_coord_dfs(arg); 55 n = solve_coord_dfs(arg);
101 if (n < 0) 56 if (n < 0)
@@ -103,7 +58,7 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg)
103 ret += n; 58 ret += n;
104 } 59 }
105 arg->cube = backup_cube; 60 arg->cube = backup_cube;
106 arg->nmoves--; 61 arg->solution_moves->nmoves--;
107 62
108 return 0; 63 return 0;
109} 64}
@@ -116,7 +71,7 @@ solve_coord_dispatch(
116 uint8_t minmoves, 71 uint8_t minmoves,
117 uint8_t maxmoves, 72 uint8_t maxmoves,
118 uint64_t maxsolutions, 73 uint64_t maxsolutions,
119 int optimal, 74 int8_t optimal,
120 int threads, 75 int threads,
121 uint64_t data_size, 76 uint64_t data_size,
122 const void *data, 77 const void *data,
@@ -154,7 +109,7 @@ solve_coord(
154 uint8_t minmoves, 109 uint8_t minmoves,
155 uint8_t maxmoves, 110 uint8_t maxmoves,
156 uint64_t maxsolutions, 111 uint64_t maxsolutions,
157 int optimal, 112 int8_t optimal,
158 int threads, 113 int threads,
159 uint64_t data_size, 114 uint64_t data_size,
160 const void *data, 115 const void *data,
@@ -163,14 +118,19 @@ solve_coord(
163) 118)
164{ 119{
165 int8_t d; 120 int8_t d;
166 uint8_t t, shortest_sol; 121 uint8_t t;
167 int64_t nsols, ndepth; 122 int64_t ndepth;
168 size_t solutions_used;
169 cube_t c; 123 cube_t c;
170 const void *coord_data; 124 const void *coord_data;
171 const uint8_t *ptable; 125 const uint8_t *ptable;
172 dfsarg_solve_coord_t arg; 126 dfsarg_solve_coord_t arg;
173 tableinfo_t info; 127 tableinfo_t info;
128 solution_moves_t solution_moves;
129 solution_settings_t solution_settings;
130 solution_list_t solution_list;
131
132 if (!solution_list_init(&solution_list, solutions_size, sols))
133 goto solve_coord_error_buffer;
174 134
175 if (readtableinfo(data_size, data, &info) != NISSY_OK) 135 if (readtableinfo(data_size, data, &info) != NISSY_OK)
176 goto solve_coord_error_data; 136 goto solve_coord_error_data;
@@ -185,64 +145,59 @@ solve_coord(
185 ptable = (uint8_t *)data + info.next + INFOSIZE; 145 ptable = (uint8_t *)data + info.next + INFOSIZE;
186 } 146 }
187 147
188 nsols = 0;
189 solutions_used = 0;
190 shortest_sol = MAXLEN + 1;
191 t = coord->axistrans[axis]; 148 t = coord->axistrans[axis];
192 c = transform(cube, t); 149 c = transform(cube, t);
193 150
151 solution_moves_reset(&solution_moves);
152
153 solution_settings = (solution_settings_t) {
154 .tmask = TM_SINGLE(inverse_trans(t)),
155 .unniss = false,
156 .maxmoves = maxmoves,
157 .maxsolutions = maxsolutions,
158 .optimal = optimal,
159 };
160
194 arg = (dfsarg_solve_coord_t) { 161 arg = (dfsarg_solve_coord_t) {
195 .cube = c, 162 .cube = c,
196 .coord = coord, 163 .coord = coord,
197 .coord_data = coord_data, 164 .coord_data = coord_data,
198 .ptable = ptable, 165 .ptable = ptable,
199 .trans = t, 166 .solution_moves = &solution_moves,
200 .nsols = &nsols, 167 .solution_settings = &solution_settings,
201 .maxsolutions = (int64_t)maxsolutions, 168 .solution_list = &solution_list,
202 .optimal = optimal,
203 .shortest_sol = &shortest_sol,
204 .solutions_size = solutions_size,
205 .solutions_used = &solutions_used,
206 .solutions = &sols,
207 }; 169 };
208 170
209 if (coord->coord(c, coord_data) == 0) { 171 if (coord->coord(c, coord_data) == 0) {
210 if (minmoves == 0) { 172 if (minmoves == 0 && !appendsolution(
211 nsols = 1; 173 &solution_moves, &solution_settings, &solution_list))
212 if (!appendchar(solutions_size, sols, &solutions_used, '\n'))
213 goto solve_coord_error_buffer; 174 goto solve_coord_error_buffer;
214 }
215 goto solve_coord_done; 175 goto solve_coord_done;
216 } 176 }
217 177
218 for ( 178 for (
219 d = MAX(minmoves, 1); 179 d = MAX(minmoves, 1);
220 d <= maxmoves && nsols < (int64_t)maxsolutions 180 !solutions_done(&solution_list, &solution_settings, d);
221 && !(nsols != 0 && d > shortest_sol + optimal);
222 d++ 181 d++
223 ) { 182 ) {
224 if (d >= 10) 183 if (d >= 10)
225 LOG("Found %" PRId64 " solutions, searching at depth %" 184 LOG("Found %" PRIu64 " solutions, searching at depth %"
226 PRId8 "\n", nsols, d); 185 PRId8 "\n", solution_list.nsols, d);
227 186
228 arg.depth = d; 187 arg.target_depth = d;
229 arg.nmoves = 0; 188 solution_moves_reset(arg.solution_moves);
230 ndepth = solve_coord_dfs(&arg); 189 ndepth = solve_coord_dfs(&arg);
231 190
232 /* TODO: improve error handling? */
233 if (ndepth < 0) { 191 if (ndepth < 0) {
234 LOG("Error %" PRId64 "\n", ndepth); 192 LOG("Error %" PRId64 "\n", ndepth);
235 return ndepth; 193 return ndepth;
236 } 194 }
237 195
238 nsols += ndepth; 196 solution_list.nsols += (uint64_t)ndepth;
239 } 197 }
240 198
241solve_coord_done: 199solve_coord_done:
242 if (!appendchar(solutions_size, sols, &solutions_used, '\0')) 200 return (int64_t)solution_list.nsols;
243 goto solve_coord_error_buffer;
244
245 return nsols;
246 201
247solve_coord_error_data: 202solve_coord_error_data:
248 LOG("solve_coord: error reading table\n"); 203 LOG("solve_coord: error reading table\n");
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index f7565d5..dbd15bb 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -4,27 +4,20 @@
4typedef struct { 4typedef struct {
5 cube_t cube; 5 cube_t cube;
6 uint8_t moves[STARTING_MOVES]; 6 uint8_t moves[STARTING_MOVES];
7 uint64_t symmask0;
8} solve_h48_task_t; 7} solve_h48_task_t;
9 8
10typedef struct { 9typedef struct {
11 cube_t start_cube; 10 cube_t start_cube;
12 uint64_t symmask0;
13 cube_t cube; 11 cube_t cube;
14 cube_t inverse; 12 cube_t inverse;
15 int8_t depth; 13 int8_t target_depth;
16 int8_t nmoves; 14 solution_moves_t *solution_moves;
17 uint8_t moves[MAXLEN]; 15 solution_settings_t *solution_settings;
18 int8_t npremoves; 16 solution_list_t *solution_list;
19 uint8_t premoves[MAXLEN];
20 int8_t lb_normal; 17 int8_t lb_normal;
21 int8_t lb_inverse; 18 int8_t lb_inverse;
22 bool use_lb_normal; 19 bool use_lb_normal;
23 bool use_lb_inverse; 20 bool use_lb_inverse;
24 _Atomic int64_t *nsols;
25 int64_t maxsolutions;
26 int8_t *shortest_sol;
27 int8_t optimal;
28 uint8_t h; 21 uint8_t h;
29 uint8_t k; 22 uint8_t k;
30 uint8_t base; 23 uint8_t base;
@@ -32,9 +25,6 @@ typedef struct {
32 const uint8_t *h48data; 25 const uint8_t *h48data;
33 const uint8_t *h48data_fallback_h0k4; 26 const uint8_t *h48data_fallback_h0k4;
34 const void *h48data_fallback_eoesep; 27 const void *h48data_fallback_eoesep;
35 size_t solutions_size;
36 size_t *solutions_used;
37 char **solutions;
38 uint32_t movemask_normal; 28 uint32_t movemask_normal;
39 uint32_t movemask_inverse; 29 uint32_t movemask_inverse;
40 int64_t nodes_visited; 30 int64_t nodes_visited;
@@ -56,8 +46,6 @@ typedef struct {
56 int8_t *shortest_sol; 46 int8_t *shortest_sol;
57} dfsarg_solve_h48_maketasks_t; 47} dfsarg_solve_h48_maketasks_t;
58 48
59STATIC int64_t solve_h48_appendsolution(dfsarg_solve_h48_t *);
60STATIC int64_t solve_h48_appendallsym(dfsarg_solve_h48_t *);
61STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *); 49STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *);
62STATIC int64_t solve_h48_maketasks( 50STATIC int64_t solve_h48_maketasks(
63 dfsarg_solve_h48_t *, dfsarg_solve_h48_maketasks_t *, 51 dfsarg_solve_h48_t *, dfsarg_solve_h48_maketasks_t *,
@@ -65,107 +53,21 @@ STATIC int64_t solve_h48_maketasks(
65STATIC void *solve_h48_runthread(void *); 53STATIC void *solve_h48_runthread(void *);
66STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t *); 54STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t *);
67STATIC int64_t solve_h48(cube_t, int8_t, int8_t, uint64_t, int8_t, int8_t, 55STATIC int64_t solve_h48(cube_t, int8_t, int8_t, uint64_t, int8_t, int8_t,
68 uint64_t, const void *, size_t, char *, 56 uint64_t, const void *, size_t n, char [n],
69 long long [static NISSY_SIZE_SOLVE_STATS]); 57 long long [static NISSY_SIZE_SOLVE_STATS]);
70 58
71STATIC int64_t
72solve_h48_appendsolution(dfsarg_solve_h48_t *arg)
73{
74 if (*arg->nsols >= arg->maxsolutions ||
75 arg->nmoves + arg->npremoves > *arg->shortest_sol + arg->optimal)
76 return 0;
77
78 invertmoves(arg->npremoves, arg->premoves, arg->moves + arg->nmoves);
79
80 /* Sort parallel moves for consistency */
81 sortparallel(arg->nmoves + arg->npremoves, arg->moves);
82
83 /* Do not append the solution in case premoves cancel with normal */
84 if (arg->npremoves > 0 && !allowednextmove(arg->nmoves+1, arg->moves))
85 return 0;
86 if (arg->npremoves > 1 && !allowednextmove(arg->nmoves+2, arg->moves))
87 return 0;
88
89 return solve_h48_appendallsym(arg);
90}
91
92STATIC int64_t
93solve_h48_appendallsym(dfsarg_solve_h48_t *arg)
94{
95 bool eq;
96 uint8_t t, i, j, k, n;
97 int64_t ret, strl, l;
98 char *m;
99 uint8_t all[NTRANS][MAXLEN];
100
101 n = arg->nmoves + arg->npremoves;
102
103 for (t = 0, j = 0; t < NTRANS; t++) {
104 if (!(arg->symmask0 & (UINT64_C(1) << (uint64_t)t)))
105 continue;
106
107 for (i = 0; i < n; i++)
108 all[j][i] = transform_move(arg->moves[i], t);
109
110 /* Sort parallel moves for consistency */
111 sortparallel(n, all[j]);
112
113 /* Check for duplicate solutions */
114 for (k = 0; k < j; k++) {
115 eq = true;
116 for (i = 0; i < n; i++)
117 if (all[k][i] != all[j][i])
118 eq = false;
119
120 /* If a solution was already found, we skip it */
121 if (eq) {
122 j--;
123 break;
124 }
125 }
126
127 j++;
128 }
129
130 /* The solutions are appended */
131 ret = 0;
132 for (k = 0; k < j && *arg->nsols < arg->maxsolutions; k++) {
133 l = arg->solutions_size - *arg->solutions_used;
134 m = *arg->solutions + *arg->solutions_used;
135 strl = writemoves(n, all[k], l, m);
136 if (strl < 0)
137 goto solve_h48_appendallsym_error;
138
139 LOG("Solution found: %s\n", m);
140
141 *arg->solutions_used += MAX(0, strl-1);
142
143 if (!appendchar(arg->solutions_size,
144 *arg->solutions, arg->solutions_used, '\n'))
145 goto solve_h48_appendallsym_error;
146
147 (*arg->nsols)++;
148 *arg->shortest_sol = MIN(*arg->shortest_sol, n);
149 ret++;
150 }
151
152 return ret;
153
154solve_h48_appendallsym_error:
155 LOG("Could not append solution to buffer: size too small\n");
156 return NISSY_ERROR_BUFFER_SIZE;
157}
158
159STATIC_INLINE bool 59STATIC_INLINE bool
160solve_h48_stop(dfsarg_solve_h48_t *arg) 60solve_h48_stop(dfsarg_solve_h48_t *arg)
161{ 61{
162 uint32_t data, data_inv; 62 uint32_t data, data_inv;
163 int64_t coord; 63 int64_t coord;
164 int8_t target, nh; 64 int8_t target, nh, n;
165 uint8_t pval_cocsep, pval_eoesep; 65 uint8_t pval_cocsep, pval_eoesep;
166 66
167 target = arg->depth - arg->nmoves - arg->npremoves; 67 n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
168 if (target <= 0 || *arg->nsols == arg->maxsolutions) 68 target = arg->target_depth - n;
69 if (target <= 0 ||
70 arg->solution_list->nsols == arg->solution_settings->maxsolutions)
169 return true; 71 return true;
170 72
171 arg->movemask_normal = arg->movemask_inverse = MM_ALLMOVES; 73 arg->movemask_normal = arg->movemask_inverse = MM_ALLMOVES;
@@ -246,16 +148,19 @@ STATIC int64_t
246solve_h48_dfs(dfsarg_solve_h48_t *arg) 148solve_h48_dfs(dfsarg_solve_h48_t *arg)
247{ 149{
248 int64_t ret, n; 150 int64_t ret, n;
249 uint8_t m, lbn, lbi; 151 uint8_t m, nm, lbn, lbi;
250 uint32_t mm_normal, mm_inverse; 152 uint32_t mm_normal, mm_inverse;
251 bool ulbi, ulbn; 153 bool ulbi, ulbn;
252 cube_t backup_cube, backup_inverse; 154 cube_t backup_cube, backup_inverse;
253 155
254 if (issolved(arg->cube)) { 156 if (issolved(arg->cube)) {
255 if (arg->nmoves + arg->npremoves != arg->depth) 157 nm = arg->solution_moves->nmoves
158 + arg->solution_moves->npremoves;
159 if (arg->target_depth != nm)
256 return 0; 160 return 0;
257 pthread_mutex_lock(arg->solutions_mutex); 161 pthread_mutex_lock(arg->solutions_mutex);
258 ret = solve_h48_appendsolution(arg); 162 ret = appendsolution(arg->solution_moves,
163 arg->solution_settings, arg->solution_list);
259 pthread_mutex_unlock(arg->solutions_mutex); 164 pthread_mutex_unlock(arg->solutions_mutex);
260 return ret; 165 return ret;
261 } 166 }
@@ -271,16 +176,17 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg)
271 ulbi = arg->use_lb_inverse; 176 ulbi = arg->use_lb_inverse;
272 177
273 ret = 0; 178 ret = 0;
274 mm_normal = allowednextmove_mask(arg->nmoves, arg->moves) & 179 mm_normal = allowednextmove_mask(arg->solution_moves->nmoves,
275 arg->movemask_normal; 180 arg->solution_moves->moves) & arg->movemask_normal;
276 mm_inverse = allowednextmove_mask(arg->npremoves, arg->premoves) & 181 mm_inverse = allowednextmove_mask(arg->solution_moves->npremoves,
277 arg->movemask_inverse; 182 arg->solution_moves->premoves) & arg->movemask_inverse;
278 if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) { 183 if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) {
279 arg->nmoves++; 184 arg->solution_moves->nmoves++;
280 for (m = 0; m < 18; m++) { 185 for (m = 0; m < 18; m++) {
281 if (!(mm_normal & (UINT32_C(1) << (uint32_t)m))) 186 if (!(mm_normal & (UINT32_C(1) << (uint32_t)m)))
282 continue; 187 continue;
283 arg->moves[arg->nmoves-1] = m; 188 arg->solution_moves->moves[
189 arg->solution_moves->nmoves-1] = m;
284 arg->cube = move(backup_cube, m); 190 arg->cube = move(backup_cube, m);
285 arg->inverse = premove(backup_inverse, m); 191 arg->inverse = premove(backup_inverse, m);
286 arg->lb_inverse = lbi; 192 arg->lb_inverse = lbi;
@@ -291,13 +197,14 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg)
291 return n; 197 return n;
292 ret += n; 198 ret += n;
293 } 199 }
294 arg->nmoves--; 200 arg->solution_moves->nmoves--;
295 } else { 201 } else {
296 arg->npremoves++; 202 arg->solution_moves->npremoves++;
297 for (m = 0; m < 18; m++) { 203 for (m = 0; m < 18; m++) {
298 if(!(mm_inverse & (UINT32_C(1) << (uint32_t)m))) 204 if(!(mm_inverse & (UINT32_C(1) << (uint32_t)m)))
299 continue; 205 continue;
300 arg->premoves[arg->npremoves-1] = m; 206 arg->solution_moves->premoves[
207 arg->solution_moves->npremoves-1] = m;
301 arg->inverse = move(backup_inverse, m); 208 arg->inverse = move(backup_inverse, m);
302 arg->cube = premove(backup_cube, m); 209 arg->cube = premove(backup_cube, m);
303 arg->lb_normal = lbn; 210 arg->lb_normal = lbn;
@@ -308,7 +215,7 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg)
308 return n; 215 return n;
309 ret += n; 216 ret += n;
310 } 217 }
311 arg->npremoves--; 218 arg->solution_moves->npremoves--;
312 } 219 }
313 220
314 arg->cube = backup_cube; 221 arg->cube = backup_cube;
@@ -322,22 +229,23 @@ solve_h48_runthread(void *arg)
322{ 229{
323 int i, j; 230 int i, j;
324 solve_h48_task_t task; 231 solve_h48_task_t task;
325 dfsarg_solve_h48_t * dfsarg; 232 dfsarg_solve_h48_t *dfsarg;
326 cube_t cube;
327 233
328 dfsarg = (dfsarg_solve_h48_t *)arg; 234 dfsarg = (dfsarg_solve_h48_t *)arg;
329 cube = dfsarg->start_cube;
330 235
331 for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += dfsarg->threads) { 236 for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += dfsarg->threads) {
332 task = dfsarg->tasks[i]; 237 task = dfsarg->tasks[i];
333 memcpy(dfsarg->moves, task.moves, STARTING_MOVES); 238
334 dfsarg->cube = cube; 239 solution_moves_reset(dfsarg->solution_moves);
240 memcpy(
241 dfsarg->solution_moves->moves, task.moves, STARTING_MOVES);
242 dfsarg->solution_moves->nmoves = STARTING_MOVES;
243
244 dfsarg->cube = dfsarg->start_cube;
335 for (j = 0; j < STARTING_MOVES; j++) 245 for (j = 0; j < STARTING_MOVES; j++)
336 dfsarg->cube = move( 246 dfsarg->cube = move(dfsarg->cube, task.moves[j]);
337 dfsarg->cube, dfsarg->moves[j]);
338 dfsarg->inverse = inverse(dfsarg->cube); 247 dfsarg->inverse = inverse(dfsarg->cube);
339 dfsarg->nmoves = STARTING_MOVES; 248
340 dfsarg->npremoves = 0;
341 dfsarg->lb_normal = 0; 249 dfsarg->lb_normal = 0;
342 dfsarg->lb_inverse = 0; 250 dfsarg->lb_inverse = 0;
343 dfsarg->use_lb_normal = false; 251 dfsarg->use_lb_normal = false;
@@ -364,16 +272,22 @@ solve_h48_maketasks(
364 uint8_t m, t; 272 uint8_t m, t;
365 uint32_t mm; 273 uint32_t mm;
366 cube_t backup_cube; 274 cube_t backup_cube;
275 solution_moves_t moves;
367 276
368 if (issolved(maketasks_arg->cube)) { 277 if (issolved(maketasks_arg->cube)) {
369 if (maketasks_arg->nmoves > maketasks_arg->maxmoves || 278 if (maketasks_arg->nmoves > maketasks_arg->maxmoves ||
370 maketasks_arg->nmoves < maketasks_arg->minmoves || 279 maketasks_arg->nmoves < maketasks_arg->minmoves ||
371 *solve_arg->nsols >= solve_arg->maxsolutions) 280 solve_arg->solution_list->nsols >=
281 solve_arg->solution_settings->maxsolutions)
372 return NISSY_OK; 282 return NISSY_OK;
373 memcpy(solve_arg->moves, 283
284 solution_moves_reset(&moves);
285 moves.nmoves = maketasks_arg->nmoves;
286 memcpy(moves.moves,
374 maketasks_arg->moves, maketasks_arg->nmoves); 287 maketasks_arg->moves, maketasks_arg->nmoves);
375 solve_arg->nmoves = maketasks_arg->nmoves; 288
376 appret = solve_h48_appendsolution(solve_arg); 289 appret = appendsolution(&moves,
290 solve_arg->solution_settings, solve_arg->solution_list);
377 return appret < 0 ? appret : NISSY_OK; 291 return appret < 0 ? appret : NISSY_OK;
378 } 292 }
379 293
@@ -402,7 +316,7 @@ solve_h48_maketasks(
402 /* Avoid symmetry-equivalent moves from the starting cube */ 316 /* Avoid symmetry-equivalent moves from the starting cube */
403 if (maketasks_arg->nmoves == 1) 317 if (maketasks_arg->nmoves == 1)
404 for (t = 0; t < NTRANS; t++) 318 for (t = 0; t < NTRANS; t++)
405 if (solve_arg->symmask0 & 319 if (solve_arg->solution_settings->tmask &
406 (UINT64_C(1) << (uint64_t)t)) 320 (UINT64_C(1) << (uint64_t)t))
407 mm &= ~(UINT32_C(1) << 321 mm &= ~(UINT32_C(1) <<
408 (uint32_t)transform_move(m, t)); 322 (uint32_t)transform_move(m, t));
@@ -424,27 +338,31 @@ solve_h48(
424 uint64_t data_size, 338 uint64_t data_size,
425 const void *data, 339 const void *data,
426 size_t solutions_size, 340 size_t solutions_size,
427 char *solutions, 341 char solutions[solutions_size],
428 long long stats[static NISSY_SIZE_SOLVE_STATS] 342 long long stats[static NISSY_SIZE_SOLVE_STATS]
429) 343)
430{ 344{
431 int i, ntasks, eoesep_table_index; 345 int i, ntasks, eoesep_table_index;
432 int8_t d, shortest_sol; 346 int8_t d;
433 _Atomic int64_t nsols;
434 dfsarg_solve_h48_t arg[THREADS]; 347 dfsarg_solve_h48_t arg[THREADS];
435 solve_h48_task_t tasks[STARTING_CUBES]; 348 solve_h48_task_t tasks[STARTING_CUBES];
436 dfsarg_solve_h48_maketasks_t maketasks_arg; 349 dfsarg_solve_h48_maketasks_t maketasks_arg;
437 long double fallback_rate, lookups_per_node; 350 long double fallback_rate, lookups_per_node;
438 uint64_t symmask, offset; 351 uint64_t offset;
439 size_t solutions_used;
440 int64_t nodes_visited, table_lookups, table_fallbacks; 352 int64_t nodes_visited, table_lookups, table_fallbacks;
441 tableinfo_t info, fbinfo, fbinfo2; 353 tableinfo_t info, fbinfo, fbinfo2;
442 const uint32_t *cocsepdata; 354 const uint32_t *cocsepdata;
443 const uint8_t *fallback, *h48data; 355 const uint8_t *fallback, *h48data;
444 const void *fallback2; 356 const void *fallback2;
357 solution_moves_t solution_moves[THREADS];
358 solution_settings_t settings;
359 solution_list_t sollist;
445 pthread_t thread[THREADS]; 360 pthread_t thread[THREADS];
446 pthread_mutex_t solutions_mutex; 361 pthread_mutex_t solutions_mutex;
447 362
363 if (!solution_list_init(&sollist, solutions_size, solutions))
364 goto solve_h48_error_solutions_buffer;
365
448 if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) 366 if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
449 goto solve_h48_error_data; 367 goto solve_h48_error_data;
450 368
@@ -475,17 +393,18 @@ solve_h48(
475 goto solve_h48_error_data; 393 goto solve_h48_error_data;
476 fallback2 = h48data + offset; 394 fallback2 = h48data + offset;
477 395
478 symmask = symmetry_mask(cube); 396 settings = (solution_settings_t) {
479 shortest_sol = MAXLEN+1; 397 .tmask = symmetry_mask(cube),
398 .unniss = true,
399 .maxmoves = maxmoves,
400 .maxsolutions = maxsolutions,
401 .optimal = optimal,
402 };
403
480 for (i = 0; i < threads; i++) { 404 for (i = 0; i < threads; i++) {
481 arg[i] = (dfsarg_solve_h48_t) { 405 arg[i] = (dfsarg_solve_h48_t) {
482 .start_cube = cube, 406 .start_cube = cube,
483 .cube = cube, 407 .cube = cube,
484 .symmask0 = symmask,
485 .nsols = &nsols,
486 .shortest_sol = &shortest_sol,
487 .optimal = optimal,
488 .maxsolutions = maxsolutions,
489 .h = info.h48h, 408 .h = info.h48h,
490 .k = info.bits, 409 .k = info.bits,
491 .base = info.base, 410 .base = info.base,
@@ -493,9 +412,9 @@ solve_h48(
493 .h48data = h48data, 412 .h48data = h48data,
494 .h48data_fallback_h0k4 = fallback, 413 .h48data_fallback_h0k4 = fallback,
495 .h48data_fallback_eoesep = fallback2, 414 .h48data_fallback_eoesep = fallback2,
496 .solutions_size = solutions_size, 415 .solution_moves = &solution_moves[i],
497 .solutions_used = &solutions_used, 416 .solution_settings = &settings,
498 .solutions = &solutions, 417 .solution_list = &sollist,
499 .nodes_visited = 0, 418 .nodes_visited = 0,
500 .table_fallbacks = 0, 419 .table_fallbacks = 0,
501 .table_lookups = 0, 420 .table_lookups = 0,
@@ -506,9 +425,6 @@ solve_h48(
506 425
507 } 426 }
508 427
509 nsols = 0;
510 solutions_used = 0;
511
512 pthread_mutex_init(&solutions_mutex, NULL); 428 pthread_mutex_init(&solutions_mutex, NULL);
513 429
514 maketasks_arg = (dfsarg_solve_h48_maketasks_t) { 430 maketasks_arg = (dfsarg_solve_h48_maketasks_t) {
@@ -521,7 +437,7 @@ solve_h48(
521 solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks); 437 solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks);
522 if (ntasks < 0) 438 if (ntasks < 0)
523 goto solve_h48_error_solutions_buffer; 439 goto solve_h48_error_solutions_buffer;
524 if (*arg[0].nsols >= (int64_t)maxsolutions) 440 if (sollist.nsols >= maxsolutions)
525 goto solve_h48_done; 441 goto solve_h48_done;
526 442
527 for (i = 0; i < threads; i++) { 443 for (i = 0; i < threads; i++) {
@@ -533,15 +449,14 @@ solve_h48(
533 449
534 for ( 450 for (
535 d = MAX(minmoves, STARTING_MOVES + 1); 451 d = MAX(minmoves, STARTING_MOVES + 1);
536 d <= maxmoves && nsols < (int64_t)maxsolutions 452 !solutions_done(&sollist, &settings, d);
537 && !(nsols != 0 && d > shortest_sol + optimal);
538 d++ 453 d++
539 ) { 454 ) {
540 if (d >= 10) 455 if (d >= 10)
541 LOG("Found %" PRId64 " solutions, searching at depth %" 456 LOG("Found %" PRId64 " solutions, searching at depth %"
542 PRId8 "\n", nsols, d); 457 PRId8 "\n", sollist.nsols, d);
543 for (i = 0; i < threads; i++) { 458 for (i = 0; i < threads; i++) {
544 arg[i].depth = d; 459 arg[i].target_depth = d;
545 pthread_create( 460 pthread_create(
546 &thread[i], NULL, solve_h48_runthread, &arg[i]); 461 &thread[i], NULL, solve_h48_runthread, &arg[i]);
547 } 462 }
@@ -550,10 +465,6 @@ solve_h48(
550 } 465 }
551 466
552solve_h48_done: 467solve_h48_done:
553 if (!appendchar(arg[0].solutions_size, *arg[0].solutions,
554 arg[0].solutions_used, '\0'))
555 goto solve_h48_error_solutions_buffer;
556
557 nodes_visited = table_lookups = table_fallbacks = 0; 468 nodes_visited = table_lookups = table_fallbacks = 0;
558 for (i = 0; i < threads; i++) { 469 for (i = 0; i < threads; i++) {
559 nodes_visited += arg[i].nodes_visited; 470 nodes_visited += arg[i].nodes_visited;
@@ -573,7 +484,7 @@ solve_h48_done:
573 LOG("Table fallbacks: %" PRId64 " (%.3Lf%%)\n", 484 LOG("Table fallbacks: %" PRId64 " (%.3Lf%%)\n",
574 table_fallbacks, fallback_rate); 485 table_fallbacks, fallback_rate);
575 486
576 return nsols; 487 return sollist.nsols;
577 488
578solve_h48_error_data: 489solve_h48_error_data:
579 LOG("solve_h48: error reading table\n"); 490 LOG("solve_h48: error reading table\n");
diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h
index 1396210..802075d 100644
--- a/src/solvers/solutions.h
+++ b/src/solvers/solutions.h
@@ -1,14 +1,217 @@
1#define MAXLEN 20 1STATIC void solution_moves_reset(solution_moves_t [static 1]);
2STATIC void solution_moves_transform(solution_moves_t [static 1], uint8_t t);
3STATIC bool solution_list_init(
4 solution_list_t [static 1], size_t n, char [n]);
5STATIC bool solution_moves_equal(
6 const solution_moves_t [static 1], const solution_moves_t [static 1]);
7STATIC bool solution_moves_is_duplicate(size_t n, const solution_moves_t[n]);
8STATIC bool appendchar(solution_list_t [static 1], char);
9STATIC int64_t appendsolution(const solution_moves_t [static 1],
10 const solution_settings_t [static 1], solution_list_t [static 1]);
11STATIC bool solutions_done(const solution_list_t [static 1],
12 const solution_settings_t [static 1], int8_t depth);
2 13
3STATIC bool appendchar(size_t n, char [n], size_t *, char); 14STATIC void
15solution_moves_reset(solution_moves_t sol[static 1])
16{
17 sol->nmoves = 0;
18 sol->npremoves = 0;
19}
20
21STATIC void
22solution_moves_transform(solution_moves_t moves[static 1], uint8_t t)
23{
24 uint8_t i;
25
26 for (i = 0; i < moves->nmoves; i++)
27 moves->moves[i] = transform_move(moves->moves[i], t);
28
29 for (i = 0; i < moves->npremoves; i++)
30 moves->premoves[i] = transform_move(moves->premoves[i], t);
31}
4 32
5STATIC bool 33STATIC bool
6appendchar(size_t n, char s[n], size_t *used, char c) 34solution_list_init(solution_list_t sols[static 1], size_t n, char buf[n])
7{ 35{
8 if (n <= *used) 36 if (n == 0) {
37 LOG("Cannot use solution buffer with size 0\n");
9 return false; 38 return false;
39 }
40
41 sols->nsols = 0;
42 sols->shortest_sol = MAXLEN + 1;
43 sols->size = n;
44 sols->used = 0;
45 sols->buf = buf;
10 46
11 s[(*used)++] = c; 47 /* Ensure string buffer is NULL-terminated */
48 sols->buf[0] = '\0';
12 49
13 return true; 50 return true;
14} 51}
52
53STATIC bool
54solution_moves_equal(
55 const solution_moves_t a[static 1],
56 const solution_moves_t b[static 1]
57)
58{
59 uint8_t i;
60
61 if (a->nmoves != b->nmoves || a->npremoves != b->npremoves)
62 return false;
63
64 for (i = 0; i < a->nmoves; i++)
65 if (a->moves[i] != b->moves[i])
66 return false;
67
68 for (i = 0; i < a->npremoves; i++)
69 if (a->premoves[i] != b->premoves[i])
70 return false;
71
72 return true;
73}
74
75STATIC bool
76solution_moves_is_duplicate(size_t r, const solution_moves_t s[r])
77{
78 size_t i;
79
80 for (i = 0; i < r; i++)
81 if (solution_moves_equal(&s[i], &s[r]))
82 return true;
83
84 return false;
85}
86
87STATIC bool
88appendchar(solution_list_t solutions[static 1], char c)
89{
90 if (solutions->size <= solutions->used)
91 return false;
92
93 solutions->buf[solutions->used++] = c;
94
95 return true;
96}
97
98STATIC int64_t
99appendsolution(
100 const solution_moves_t moves[static 1],
101 const solution_settings_t settings[static 1],
102 solution_list_t list[static 1]
103)
104{
105 int64_t r, strl;
106 int i;
107 uint8_t t;
108 solution_moves_t tsol[NTRANS];
109
110 if (moves->nmoves + moves->npremoves > MAXLEN)
111 goto appendsolution_error_solution_length;
112
113 for (
114 t = 0, r = 0;
115 t < NTRANS && list->nsols < settings->maxsolutions;
116 t++
117 ) {
118 if (!(settings->tmask & TM_SINGLE(t)))
119 continue;
120
121 tsol[r] = *moves;
122 if (settings->unniss) {
123 tsol[r].nmoves += moves->npremoves;
124 tsol[r].npremoves = 0;
125 for (i = moves->npremoves-1; i >= 0; i--)
126 tsol[r].moves[tsol[r].nmoves - i - 1] =
127 inverse_move(moves->premoves[i]);
128
129 /*
130 This is a bit ugly: we have to sort now and then again
131 later, because the allowednext check would fail with
132 improperly sorted parallel moves, but then transforming
133 could swap the pairs the wrong way around.
134 TODO: maybe fix this
135 */
136 sortparallel_moves(tsol[r].nmoves, tsol[r].moves);
137
138 /* Check if unnissed premoves cancel with normal. */
139 if (!allowedmoves(tsol[r].nmoves, tsol[r].moves))
140 continue;
141 }
142 solution_moves_transform(&tsol[r], t);
143 sortparallel_moves(tsol[r].nmoves, tsol[r].moves);
144 sortparallel_moves(tsol[r].npremoves, tsol[r].premoves);
145
146 /* Skip duplicates that may appear after transforming */
147 if (solution_moves_is_duplicate(r, tsol))
148 continue;
149
150 /* Write moves on normal */
151 strl = writemoves(tsol[r].nmoves, tsol[r].moves,
152 list->size - list->used, list->buf + list->used);
153 if (strl < 0)
154 goto appendsolution_error_buffer;
155 list->used += (size_t)(strl-1);
156
157 /* Write moves on inverse with NISS notation */
158 if (tsol[r].npremoves > 0) {
159 if (!appendchar(list, ' '))
160 goto appendsolution_error_buffer;
161 if (!appendchar(list, '('))
162 goto appendsolution_error_buffer;
163
164 strl = writemoves(tsol[r].npremoves, tsol[r].premoves,
165 list->size - list->used, list->buf + list->used);
166 if (strl < 0)
167 goto appendsolution_error_buffer;
168 list->used += (size_t)(strl-1);
169
170 if (!appendchar(list, ')'))
171 goto appendsolution_error_buffer;
172 }
173
174 if (!appendchar(list, '\n'))
175 goto appendsolution_error_buffer;
176
177 ++list->nsols;
178 list->shortest_sol = MIN(
179 list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves);
180 r++;
181 }
182
183 list->buf[list->used] = '\0';
184 return r;
185
186appendsolution_error_buffer:
187 LOG("Could not append solution to buffer: size too small\n");
188 list->buf[0] = '\0';
189 return NISSY_ERROR_BUFFER_SIZE;
190
191appendsolution_error_solution_length:
192 LOG("Error: solution is too long (%" PRIu8 ").\n"
193 "This is a bug, please report it.\n",
194 moves->nmoves + moves->npremoves);
195 list->buf[0] = '\0';
196 return NISSY_ERROR_UNKNOWN;
197}
198
199STATIC bool
200solutions_done(
201 const solution_list_t list[static 1],
202 const solution_settings_t settings[static 1],
203 int8_t depth
204)
205{
206 if (list->nsols >= settings->maxsolutions)
207 return true;
208
209 if (depth > settings->maxmoves)
210 return true;
211
212 if (list->nsols > 0 && settings->optimal >= 0 &&
213 depth > list->shortest_sol + settings->optimal)
214 return true;
215
216 return false;
217}
diff --git a/src/solvers/solutions_types_macros.h b/src/solvers/solutions_types_macros.h
new file mode 100644
index 0000000..06e099b
--- /dev/null
+++ b/src/solvers/solutions_types_macros.h
@@ -0,0 +1,24 @@
1#define MAXLEN 20
2
3typedef struct {
4 uint8_t nmoves;
5 uint8_t moves[MAXLEN];
6 uint8_t npremoves;
7 uint8_t premoves[MAXLEN];
8} solution_moves_t;
9
10typedef struct {
11 uint64_t tmask;
12 bool unniss;
13 uint8_t maxmoves;
14 uint64_t maxsolutions;
15 int8_t optimal;
16} solution_settings_t;
17
18typedef struct {
19 _Atomic uint64_t nsols;
20 uint8_t shortest_sol;
21 size_t size;
22 size_t used;
23 char *buf;
24} solution_list_t;
diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h
index 42184b9..4d6bbca 100644
--- a/src/solvers/solvers.h
+++ b/src/solvers/solvers.h
@@ -1,4 +1,6 @@
1#include "solutions_types_macros.h"
1#include "solutions.h" 2#include "solutions.h"
3#include "tables_types_macros.h"
2#include "tables.h" 4#include "tables.h"
3#include "h48/h48.h" 5#include "h48/h48.h"
4#include "coord/coord.h" 6#include "coord/coord.h"
diff --git a/src/solvers/tables.h b/src/solvers/tables.h
index 3147416..65e7606 100644
--- a/src/solvers/tables.h
+++ b/src/solvers/tables.h
@@ -1,6 +1,3 @@
1/* Type definitions and macros are in a separate file for easier testing */
2#include "tables_types_macros.h"
3
4STATIC uint64_t read_unaligned_u64(const char *); 1STATIC uint64_t read_unaligned_u64(const char *);
5STATIC void write_unaligned_u64(char *, uint64_t); 2STATIC void write_unaligned_u64(char *, uint64_t);
6STATIC int64_t readtableinfo(uint64_t, const char *, tableinfo_t *); 3STATIC int64_t readtableinfo(uint64_t, const char *, tableinfo_t *);

Generated with cgit - Back to sebastiano.tronto.net