aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers/h48')
-rw-r--r--src/solvers/h48/coordinate_macros.h1
-rw-r--r--src/solvers/h48/gendata_cocsep.h34
-rw-r--r--src/solvers/h48/gendata_eoesep.h274
-rw-r--r--src/solvers/h48/gendata_h48.h62
-rw-r--r--src/solvers/h48/gendata_types_macros.h11
-rw-r--r--src/solvers/h48/h48.h3
-rw-r--r--src/solvers/h48/solve.h610
-rw-r--r--src/solvers/h48/solve_multithread.h350
-rw-r--r--src/solvers/h48/stats.h100
9 files changed, 790 insertions, 655 deletions
diff --git a/src/solvers/h48/coordinate_macros.h b/src/solvers/h48/coordinate_macros.h
index 5b67177..04462d6 100644
--- a/src/solvers/h48/coordinate_macros.h
+++ b/src/solvers/h48/coordinate_macros.h
@@ -2,5 +2,6 @@
2 2
3#define COCLASS_MASK (UINT32_C(0xFFFF) << UINT32_C(16)) 3#define COCLASS_MASK (UINT32_C(0xFFFF) << UINT32_C(16))
4#define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16)) 4#define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16))
5#define ECLASS(x) COCLASS(x)
5#define TTREP_MASK (UINT32_C(0xFF) << UINT32_C(8)) 6#define TTREP_MASK (UINT32_C(0xFF) << UINT32_C(8))
6#define TTREP(x) (((x) & TTREP_MASK) >> UINT32_C(8)) 7#define TTREP(x) (((x) & TTREP_MASK) >> UINT32_C(8))
diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h
index b46bcf3..291ae48 100644
--- a/src/solvers/h48/gendata_cocsep.h
+++ b/src/solvers/h48/gendata_cocsep.h
@@ -1,27 +1,16 @@
1STATIC_INLINE bool get_visited(const uint8_t *, int64_t); 1STATIC_INLINE bool gendata_cocsep_get_visited(const uint8_t *, int64_t);
2STATIC_INLINE void set_visited(uint8_t *, int64_t); 2STATIC_INLINE void gendata_cocsep_set_visited(uint8_t *, int64_t);
3 3
4STATIC size_t gendata_cocsep( 4STATIC size_t gendata_cocsep(
5 char [static COCSEP_FULLSIZE+INFOSIZE], uint64_t *, cube_t *); 5 char [static COCSEP_FULLSIZE], uint64_t *, cube_t *);
6STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *); 6STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *);
7STATIC void getdistribution_cocsep(const uint32_t *, uint64_t [static 21]); 7STATIC void getdistribution_cocsep(const uint32_t *, uint64_t [static 21]);
8 8
9STATIC_INLINE int8_t get_h48_cdata(cube_t, const uint32_t *, uint32_t *); 9STATIC_INLINE int8_t get_h48_cdata(cube_t, const uint32_t *, uint32_t *);
10 10
11/*
12Each element of the cocsep table is a uint32_t used as follows:
13 - Lowest 8-bit block: pruning value
14 - Second-lowest 8-bit block: "ttrep" (transformation to representative)
15 - Top 16-bit block: symcoord value
16After the data as described above, more auxiliary information is appended:
17 - A uint32_t representing the number of symmetry classes
18 - A uint32_t representing the highest value of the pruning table
19 - One uint32_t for each "line" of the pruning table, representing the number
20 of positions having that pruning value.
21*/
22STATIC size_t 11STATIC size_t
23gendata_cocsep( 12gendata_cocsep(
24 char buf[static COCSEP_FULLSIZE+INFOSIZE], 13 char buf[static COCSEP_FULLSIZE],
25 uint64_t *selfsim, 14 uint64_t *selfsim,
26 cube_t *rep 15 cube_t *rep
27) 16)
@@ -36,7 +25,7 @@ gendata_cocsep(
36 goto gendata_cocsep_return_size; 25 goto gendata_cocsep_return_size;
37 26
38 memset(buf, 0xFF, COCSEP_FULLSIZE); 27 memset(buf, 0xFF, COCSEP_FULLSIZE);
39 buf32 = (uint32_t *)((char *)buf + INFOSIZE); 28 buf32 = (uint32_t *)(buf + INFOSIZE);
40 if (selfsim != NULL) 29 if (selfsim != NULL)
41 memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); 30 memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES);
42 31
@@ -69,7 +58,7 @@ gendata_cocsep(
69 info.distribution[i] = cc; 58 info.distribution[i] = cc;
70 } 59 }
71 60
72 writetableinfo(&info, COCSEP_FULLSIZE+INFOSIZE, buf); 61 writetableinfo(&info, COCSEP_FULLSIZE, buf);
73 62
74 DBG_ASSERT(n == COCSEP_CLASSES, 0, 63 DBG_ASSERT(n == COCSEP_CLASSES, 0,
75 "cocsep: computed %" PRIu16 " symmetry classes, " 64 "cocsep: computed %" PRIu16 " symmetry classes, "
@@ -101,9 +90,10 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t *arg)
101 90
102 i = coord_cocsep(arg->cube); 91 i = coord_cocsep(arg->cube);
103 olddepth = (uint8_t)(arg->buf32[i] & 0xFF); 92 olddepth = (uint8_t)(arg->buf32[i] & 0xFF);
104 if (olddepth < arg->depth || get_visited(arg->visited, i)) 93 if (olddepth < arg->depth ||
94 gendata_cocsep_get_visited(arg->visited, i))
105 return 0; 95 return 0;
106 set_visited(arg->visited, i); 96 gendata_cocsep_set_visited(arg->visited, i);
107 97
108 if (arg->depth == arg->maxdepth) { 98 if (arg->depth == arg->maxdepth) {
109 if ((arg->buf32[i] & 0xFF) != 0xFF) 99 if ((arg->buf32[i] & 0xFF) != 0xFF)
@@ -118,7 +108,7 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t *arg)
118 arg->selfsim[*arg->n] |= UINT64_C(1) << t; 108 arg->selfsim[*arg->n] |= UINT64_C(1) << t;
119 if (COCLASS(arg->buf32[j]) != UINT32_C(0xFFFF)) 109 if (COCLASS(arg->buf32[j]) != UINT32_C(0xFFFF))
120 continue; 110 continue;
121 set_visited(arg->visited, j); 111 gendata_cocsep_set_visited(arg->visited, j);
122 tinv = inverse_trans(t); 112 tinv = inverse_trans(t);
123 olddepth = arg->buf32[j] & 0xFF; 113 olddepth = arg->buf32[j] & 0xFF;
124 cc += olddepth == 0xFF; 114 cc += olddepth == 0xFF;
@@ -155,13 +145,13 @@ getdistribution_cocsep(const uint32_t *table, uint64_t distr[static 21])
155} 145}
156 146
157STATIC_INLINE bool 147STATIC_INLINE bool
158get_visited(const uint8_t *a, int64_t i) 148gendata_cocsep_get_visited(const uint8_t *a, int64_t i)
159{ 149{
160 return a[VISITED_IND(i)] & VISITED_MASK(i); 150 return a[VISITED_IND(i)] & VISITED_MASK(i);
161} 151}
162 152
163STATIC_INLINE void 153STATIC_INLINE void
164set_visited(uint8_t *a, int64_t i) 154gendata_cocsep_set_visited(uint8_t *a, int64_t i)
165{ 155{
166 a[VISITED_IND(i)] |= VISITED_MASK(i); 156 a[VISITED_IND(i)] |= VISITED_MASK(i);
167} 157}
diff --git a/src/solvers/h48/gendata_eoesep.h b/src/solvers/h48/gendata_eoesep.h
new file mode 100644
index 0000000..d3b73ea
--- /dev/null
+++ b/src/solvers/h48/gendata_eoesep.h
@@ -0,0 +1,274 @@
1STATIC int64_t coord_eoesep_sym(cube_t, const uint32_t [static ESEP_MAX]);
2STATIC size_t gendata_esep_classes(
3 uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]);
4STATIC size_t gendata_eoesep(char [static EOESEP_FULLSIZE], uint8_t);
5STATIC uint32_t gendata_eoesep_bfs(uint8_t, uint8_t [static EOESEP_BUF],
6 uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]);
7STATIC uint32_t gendata_eoesep_fromnew(uint8_t, uint8_t [static EOESEP_BUF],
8 uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]);
9STATIC uint32_t gendata_eoesep_fromdone(uint8_t, uint8_t [static EOESEP_BUF],
10 uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]);
11STATIC uint32_t gendata_eoesep_marksim(int64_t, uint8_t,
12 uint8_t [static EOESEP_BUF], uint32_t [static ESEP_MAX]);
13STATIC bool gendata_eoesep_next(cube_t, uint8_t,
14 uint8_t [static EOESEP_BUF], uint32_t [static ESEP_MAX]);
15STATIC uint8_t get_eoesep_pval(const uint8_t *, int64_t);
16STATIC uint8_t get_eoesep_pval_cube(const void *, cube_t);
17STATIC void set_eoesep_pval(uint8_t *, int64_t, uint8_t);
18
19STATIC int64_t
20coord_eoesep_sym(cube_t c, const uint32_t esep_classes[static ESEP_MAX])
21{
22 uint8_t ttrep;
23 uint32_t edata, class;
24 int64_t esep, eo;
25
26 esep = coord_esep(c);
27 edata = esep_classes[esep];
28 class = ECLASS(edata);
29 ttrep = TTREP(edata);
30 eo = coord_eo(transform(c, ttrep));
31
32 return (class << UINT32_C(11)) + eo;
33}
34
35STATIC size_t
36gendata_esep_classes(
37 uint32_t esep_classes[static ESEP_MAX],
38 uint16_t rep[static ESEP_CLASSES]
39)
40{
41 bool visited[ESEP_MAX];
42 uint8_t t;
43 uint32_t class, cl, ti;
44 int64_t i, j;
45 cube_t c;
46
47 memset(visited, 0, ESEP_MAX * sizeof(bool));
48 class = 0;
49 for (i = 0; i < ESEP_MAX; i++) {
50 if (visited[i])
51 continue;
52 c = invcoord_esep(i);
53 for (t = 0; t < 48; t++) {
54 j = coord_esep(transform(c, t));
55 cl = class << UINT32_C(16);
56 ti = inverse_trans(t) << UINT32_C(8);
57 esep_classes[j] = cl | ti;
58 visited[j] = true;
59 }
60 rep[class] = i;
61 class++;
62 }
63
64 return class;
65}
66
67STATIC size_t
68gendata_eoesep(char buf[static EOESEP_FULLSIZE], uint8_t maxdepth)
69{
70 uint8_t *buf8, d;
71 uint16_t rep[ESEP_CLASSES];
72 uint32_t *esep_classes, done, level;
73 int64_t coord;
74 tableinfo_t info;
75
76 if (buf == NULL)
77 goto gendata_eoesep_return_size;
78
79 LOG("Computing eoesep data\n");
80 memset(buf, 0xFF, EOESEP_FULLSIZE);
81 esep_classes = (uint32_t *)(buf + INFOSIZE);
82 buf8 = (uint8_t *)(buf + INFOSIZE + 4*ESEP_MAX);
83 gendata_esep_classes(esep_classes, rep);
84
85 info = (tableinfo_t) {
86 .solver = "eoesep data for h48",
87 .type = TABLETYPE_SPECIAL,
88 .infosize = INFOSIZE,
89 .fullsize = EOESEP_FULLSIZE,
90 .hash = 0,
91 .entries = EOESEP_TABLESIZE,
92 .classes = ESEP_CLASSES,
93 .bits = 4,
94 .base = 0,
95 .maxvalue = 11,
96 .next = 0
97 };
98
99 coord = 0; /* Assumed coordinate of solved cube */
100 set_eoesep_pval(buf8, coord, 0);
101 done = 1;
102 info.distribution[0] = 1;
103 for (d = 1; d <= maxdepth && done < EOESEP_TABLESIZE; d++) {
104 level = gendata_eoesep_bfs(d, buf8, esep_classes, rep);
105 done += level;
106 info.distribution[d] = level;
107 }
108
109 writetableinfo(&info, EOESEP_FULLSIZE, buf);
110
111 LOG("eoesep data computed\n");
112
113gendata_eoesep_return_size:
114 return EOESEP_FULLSIZE;
115}
116
117STATIC uint32_t
118gendata_eoesep_bfs(
119 uint8_t d,
120 uint8_t buf8[EOESEP_BUF],
121 uint32_t esep_classes[static ESEP_MAX],
122 uint16_t rep[static ESEP_CLASSES]
123)
124{
125 if (d < 9)
126 return gendata_eoesep_fromdone(d, buf8, esep_classes, rep);
127 else
128 return gendata_eoesep_fromnew(d, buf8, esep_classes, rep);
129}
130
131STATIC uint32_t
132gendata_eoesep_fromdone(
133 uint8_t d,
134 uint8_t buf8[EOESEP_BUF],
135 uint32_t esep_classes[static ESEP_MAX],
136 uint16_t rep[static ESEP_CLASSES]
137)
138{
139 uint8_t pval;
140 int64_t i, esep, eo, coord, done;
141
142 done = 0;
143 for (i = 0; i < (int64_t)ESEP_CLASSES; i++) {
144 esep = rep[i];
145 for (eo = 0; eo < POW_2_11; eo++) {
146 coord = (i << INT64_C(11)) + eo;
147 pval = get_eoesep_pval(buf8, coord);
148 if (pval != d-1)
149 continue;
150
151 coord = (esep << INT64_C(11)) + eo;
152 done += gendata_eoesep_marksim(
153 coord, d, buf8, esep_classes);
154 }
155 }
156
157 return done;
158}
159
160STATIC uint32_t
161gendata_eoesep_fromnew(
162 uint8_t d,
163 uint8_t buf8[EOESEP_BUF],
164 uint32_t esep_classes[static ESEP_MAX],
165 uint16_t rep[static ESEP_CLASSES]
166)
167{
168 uint8_t pval;
169 int64_t i, esep, eo, coord, done;
170 cube_t c;
171
172 done = 0;
173 for (i = 0; i < (int64_t)ESEP_CLASSES; i++) {
174 esep = rep[i];
175 for (eo = 0; eo < POW_2_11; eo++) {
176 coord = (i << INT64_C(11)) + eo;
177 pval = get_eoesep_pval(buf8, coord);
178 if (pval != 15)
179 continue;
180
181 c = invcoord_eoesep((esep << INT64_C(11)) + eo);
182 if (gendata_eoesep_next(c, d, buf8, esep_classes)) {
183 set_eoesep_pval(buf8, coord, d);
184 done++;
185 }
186 }
187 }
188
189 return done;
190}
191
192STATIC uint32_t
193gendata_eoesep_marksim(
194 int64_t i,
195 uint8_t d,
196 uint8_t buf8[static EOESEP_BUF],
197 uint32_t esep_classes[static ESEP_MAX]
198)
199{
200 uint8_t t, m, pval;
201 cube_t c, moved, transformed;
202 uint32_t done;
203 int64_t coord;
204
205 done = 0;
206 c = invcoord_eoesep(i);
207 for (m = 0; m < 18; m++) {
208 moved = move(c, m);
209 for (t = 0; t < 48; t++) {
210 transformed = transform(moved, t);
211 coord = coord_eoesep_sym(transformed, esep_classes);
212 pval = get_eoesep_pval(buf8, coord);
213 if (pval > d) {
214 set_eoesep_pval(buf8, coord, d);
215 done++;
216 }
217 }
218 }
219
220 return done;
221}
222
223STATIC bool
224gendata_eoesep_next(
225 cube_t c,
226 uint8_t d,
227 uint8_t buf8[static EOESEP_BUF],
228 uint32_t esep_classes[static ESEP_MAX]
229)
230{
231 uint8_t m, t, pval;
232 int64_t coord;
233 cube_t moved, transformed;
234
235 for (t = 0; t < 48; t++) {
236 transformed = transform(c, t);
237 for (m = 0; m < 18; m++) {
238 moved = move(transformed, m);
239 coord = coord_eoesep_sym(moved, esep_classes);
240 pval = get_eoesep_pval(buf8, coord);
241 if (pval == d-1)
242 return true;
243 }
244 }
245
246 return false;
247}
248
249STATIC uint8_t
250get_eoesep_pval(const uint8_t *table, int64_t i)
251{
252 return (table[EOESEP_INDEX(i)] & EOESEP_MASK(i)) >> EOESEP_SHIFT(i);
253}
254
255STATIC uint8_t
256get_eoesep_pval_cube(const void *data, cube_t c)
257{
258 int64_t coord;
259 const uint8_t *table;
260 const uint32_t *esep_classes;
261
262 esep_classes = (const uint32_t *)data;
263 table = (const uint8_t *)data + 4*ESEP_MAX;
264 coord = coord_eoesep_sym(c, esep_classes);
265
266 return get_eoesep_pval(table, coord);
267}
268
269STATIC void
270set_eoesep_pval(uint8_t *table, int64_t i, uint8_t val)
271{
272 table[EOESEP_INDEX(i)] = (table[EOESEP_INDEX(i)] & (~EOESEP_MASK(i)))
273 | (val << EOESEP_SHIFT(i));
274}
diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
index 55c4f34..ae0b732 100644
--- a/src/solvers/h48/gendata_h48.h
+++ b/src/solvers/h48/gendata_h48.h
@@ -61,13 +61,13 @@ gendata_h48short(gendata_h48short_arg_t *arg)
61 return arg->map->n; 61 return arg->map->n;
62} 62}
63 63
64/* Generic function that dispatches to the data generators */
65STATIC int64_t 64STATIC int64_t
66gendata_h48(gendata_h48_arg_t *arg) 65gendata_h48(gendata_h48_arg_t *arg)
67{ 66{
68 uint64_t size, cocsepsize, h48size, fallbacksize; 67 uint64_t size, cocsepsize, h48size, fallbacksize, fallback2size, of;
68 long long r;
69 void *cocsepdata_offset; 69 void *cocsepdata_offset;
70 tableinfo_t cocsepinfo, h48info; 70 tableinfo_t cocsepinfo, h48info, fallbackinfo;
71 gendata_h48_arg_t arg_h0k4; 71 gendata_h48_arg_t arg_h0k4;
72 72
73 if (arg == NULL) { 73 if (arg == NULL) {
@@ -78,7 +78,8 @@ gendata_h48(gendata_h48_arg_t *arg)
78 cocsepsize = COCSEP_FULLSIZE; 78 cocsepsize = COCSEP_FULLSIZE;
79 h48size = INFOSIZE + H48_TABLESIZE(arg->h, arg->k); 79 h48size = INFOSIZE + H48_TABLESIZE(arg->h, arg->k);
80 fallbacksize = arg->k == 2 ? INFOSIZE + H48_TABLESIZE(0, 4) : 0; 80 fallbacksize = arg->k == 2 ? INFOSIZE + H48_TABLESIZE(0, 4) : 0;
81 size = cocsepsize + h48size + fallbacksize; 81 fallback2size = EOESEP_FULLSIZE;
82 size = cocsepsize + h48size + fallbacksize + fallback2size;
82 83
83 if (arg->buf == NULL) 84 if (arg->buf == NULL)
84 return size; /* Dry-run */ 85 return size; /* Dry-run */
@@ -110,18 +111,22 @@ gendata_h48(gendata_h48_arg_t *arg)
110 return NISSY_ERROR_INVALID_SOLVER; 111 return NISSY_ERROR_INVALID_SOLVER;
111 } 112 }
112 113
113 if (readtableinfo(arg->buf_size, arg->buf, &cocsepinfo) != NISSY_OK) { 114 r = readtableinfo(arg->buf_size, arg->buf, &cocsepinfo);
115 if (r != NISSY_OK) {
114 LOG("gendata_h48: could not read info for cocsep table\n"); 116 LOG("gendata_h48: could not read info for cocsep table\n");
115 return NISSY_ERROR_UNKNOWN; 117 return NISSY_ERROR_UNKNOWN;
116 } 118 }
117 119
118 cocsepinfo.next = cocsepsize; 120 cocsepinfo.next = cocsepsize;
119 if (writetableinfo(&cocsepinfo, arg->buf_size, arg->buf) != NISSY_OK) { 121 r = writetableinfo(&cocsepinfo, arg->buf_size, arg->buf);
122 if (r != NISSY_OK) {
120 LOG("gendata_h48: could not write info for cocsep table" 123 LOG("gendata_h48: could not write info for cocsep table"
121 " with updated 'next' value\n"); 124 " with updated 'next' value\n");
122 return NISSY_ERROR_UNKNOWN; 125 return NISSY_ERROR_UNKNOWN;
123 } 126 }
124 127
128 /* Add h0k4 fallback table */
129
125 if (arg->k == 2) { 130 if (arg->k == 2) {
126 arg_h0k4 = *arg; 131 arg_h0k4 = *arg;
127 arg_h0k4.h = 0; 132 arg_h0k4.h = 0;
@@ -134,16 +139,42 @@ gendata_h48(gendata_h48_arg_t *arg)
134 139
135 gendata_h48h0k4(&arg_h0k4); 140 gendata_h48h0k4(&arg_h0k4);
136 141
137 if (readtableinfo_n(arg->buf_size, arg->buf, 2, &h48info) 142 }
138 != NISSY_OK) { 143
139 LOG("gendata_h48: could not read info for h48 table\n"); 144 /* Add eoesep fallback table */
145
146 gendata_eoesep((char *)arg->buf + (size - fallback2size), 20);
147
148 /* Update tableinfo with correct next values */
149
150 r = readtableinfo_n(arg->buf_size, arg->buf, 2, &h48info);
151 if (r != NISSY_OK) {
152 LOG("gendata_h48: could not read info for h48 table\n");
153 return NISSY_ERROR_UNKNOWN;
154 }
155 h48info.next = h48size;
156 r = writetableinfo(&h48info,
157 arg->buf_size - cocsepsize, (char *)arg->buf + cocsepsize);
158 if (r != NISSY_OK) {
159 LOG("gendata_h48: could not write info for h48 table\n");
160 return NISSY_ERROR_UNKNOWN;
161 }
162
163 if (arg->k == 2) {
164 r = readtableinfo_n(arg->buf_size, arg->buf, 3, &fallbackinfo);
165 if (r != NISSY_OK) {
166 LOG("gendata_h48: could not read info for h48 "
167 "fallback table\n");
140 return NISSY_ERROR_UNKNOWN; 168 return NISSY_ERROR_UNKNOWN;
141 } 169 }
142 170
143 h48info.next = h48size; 171 of = cocsepsize + h48size;
144 if (writetableinfo(&h48info, arg->buf_size - cocsepsize, 172 fallbackinfo.next = fallbacksize;
145 (char *)arg->buf + cocsepsize) != NISSY_OK) { 173 r = writetableinfo(&fallbackinfo,
146 LOG("gendata_h48: could not write info for h48 table\n"); 174 arg->buf_size - of, (char *)arg->buf + of);
175 if (r != NISSY_OK) {
176 LOG("gendata_h48: could not write info for h48 "
177 "fallback table\n");
147 return NISSY_ERROR_UNKNOWN; 178 return NISSY_ERROR_UNKNOWN;
148 } 179 }
149 } 180 }
@@ -302,9 +333,8 @@ gendata_h48k2(gendata_h48_arg_t *arg)
302 * 333 *
303 * The following values for the base have been hand-picked. I first 334 * The following values for the base have been hand-picked. I first
304 * performed some statistics on the frequency of these values, but 335 * performed some statistics on the frequency of these values, but
305 * they turned out to be unreliable. I have not figured out why yet. 336 * they turned out to be unreliable. In the end I generated the same
306 * In the end I resorted to generating the same table with multiple 337 * table with multiple base value and see what was best.
307 * base value and see what was best.
308 * 338 *
309 * A curious case is h3, which has this distribution for base 8: 339 * A curious case is h3, which has this distribution for base 8:
310 * [0] = 6686828 340 * [0] = 6686828
diff --git a/src/solvers/h48/gendata_types_macros.h b/src/solvers/h48/gendata_types_macros.h
index 73a46ff..d7c88af 100644
--- a/src/solvers/h48/gendata_types_macros.h
+++ b/src/solvers/h48/gendata_types_macros.h
@@ -3,13 +3,22 @@
3#define COCSEP_VISITEDSIZE DIV_ROUND_UP(COCSEP_TABLESIZE, (size_t)8) 3#define COCSEP_VISITEDSIZE DIV_ROUND_UP(COCSEP_TABLESIZE, (size_t)8)
4#define COCSEP_FULLSIZE (INFOSIZE + (size_t)4 * COCSEP_TABLESIZE) 4#define COCSEP_FULLSIZE (INFOSIZE + (size_t)4 * COCSEP_TABLESIZE)
5 5
6#define ESEP_MAX (COMB_12_4 * COMB_8_4)
7#define ESEP_CLASSES ((size_t)782)
8#define EOESEP_TABLESIZE (ESEP_CLASSES << (size_t)11)
9#define EOESEP_BUF DIV_ROUND_UP(EOESEP_TABLESIZE, 2)
10#define EOESEP_FULLSIZE (INFOSIZE + EOESEP_BUF + (size_t)4 * ESEP_MAX)
11#define EOESEP_INDEX(i) ((i)/2)
12#define EOESEP_SHIFT(i) (UINT8_C(4) * (uint8_t)((i) % 2))
13#define EOESEP_MASK(i) (UINT8_C(0xF) << EOESEP_SHIFT(i))
14
6#define VISITED_IND(i) ((uint32_t)(i) / UINT32_C(8)) 15#define VISITED_IND(i) ((uint32_t)(i) / UINT32_C(8))
7#define VISITED_MASK(i) (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8))) 16#define VISITED_MASK(i) (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8)))
8 17
9#define CBOUND_MASK UINT32_C(0xFF) 18#define CBOUND_MASK UINT32_C(0xFF)
10#define CBOUND(x) ((x) & CBOUND_MASK) 19#define CBOUND(x) ((x) & CBOUND_MASK)
11 20
12#define H48_COORDMAX_NOEO ((int64_t)(COCSEP_CLASSES * COMB_12_4 * COMB_8_4)) 21#define H48_COORDMAX_NOEO ((int64_t)(COCSEP_CLASSES * ESEP_MAX))
13#define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (int64_t)(h)) 22#define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (int64_t)(h))
14#define H48_DIV(k) ((size_t)8 / (size_t)(k)) 23#define H48_DIV(k) ((size_t)8 / (size_t)(k))
15#define H48_TABLESIZE(h, k) DIV_ROUND_UP((size_t)H48_COORDMAX((h)), H48_DIV(k)) 24#define H48_TABLESIZE(h, k) DIV_ROUND_UP((size_t)H48_COORDMAX((h)), H48_DIV(k))
diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h
index 3cf02b7..d5a67ef 100644
--- a/src/solvers/h48/h48.h
+++ b/src/solvers/h48/h48.h
@@ -2,7 +2,6 @@
2#include "map.h" 2#include "map.h"
3#include "gendata_types_macros.h" 3#include "gendata_types_macros.h"
4#include "gendata_cocsep.h" 4#include "gendata_cocsep.h"
5#include "gendata_eoesep.h"
5#include "gendata_h48.h" 6#include "gendata_h48.h"
6#include "stats.h"
7#include "solve.h" 7#include "solve.h"
8#include "solve_multithread.h"
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index d506596..8666007 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -1,9 +1,26 @@
1#define STARTING_MOVES 3
2#define STARTING_CUBES 3240 /* Number of 3-move sequences */
3
4typedef struct {
5 cube_t cube;
6 uint8_t moves[STARTING_MOVES];
7 uint64_t symmask0;
8} solve_h48_task_t;
9
1typedef struct { 10typedef struct {
11 cube_t start_cube;
12 uint64_t symmask0;
2 cube_t cube; 13 cube_t cube;
3 cube_t inverse; 14 cube_t inverse;
4 int8_t nmoves;
5 int8_t depth; 15 int8_t depth;
16 int8_t nmoves;
6 uint8_t moves[MAXLEN]; 17 uint8_t moves[MAXLEN];
18 int8_t npremoves;
19 uint8_t premoves[MAXLEN];
20 int8_t lb_normal;
21 int8_t lb_inverse;
22 bool use_lb_normal;
23 bool use_lb_inverse;
7 _Atomic int64_t *nsols; 24 _Atomic int64_t *nsols;
8 int64_t maxsolutions; 25 int64_t maxsolutions;
9 uint8_t h; 26 uint8_t h;
@@ -11,209 +28,385 @@ typedef struct {
11 uint8_t base; 28 uint8_t base;
12 const uint32_t *cocsepdata; 29 const uint32_t *cocsepdata;
13 const uint8_t *h48data; 30 const uint8_t *h48data;
14 const uint8_t *h48data_fallback; 31 const uint8_t *h48data_fallback_h0k4;
32 const void *h48data_fallback_eoesep;
15 uint64_t solutions_size; 33 uint64_t solutions_size;
16 char **nextsol; 34 uint64_t *solutions_used;
17 uint8_t nissbranch; 35 char **solutions;
18 int8_t npremoves; 36 uint32_t movemask_normal;
19 uint8_t premoves[MAXLEN]; 37 uint32_t movemask_inverse;
20 long long nodes_visited; 38 int64_t nodes_visited;
21 long long table_fallbacks; 39 int64_t table_fallbacks;
22} dfsarg_solveh48_t; 40 int64_t table_lookups;
41 int ntasks;
42 solve_h48_task_t *tasks;
43 int thread_id;
44 pthread_mutex_t *solutions_mutex;
45} dfsarg_solve_h48_t;
23 46
24STATIC uint32_t allowednextmove_h48(uint8_t *, uint8_t, uint8_t); 47typedef struct {
48 cube_t cube;
49 int8_t nmoves;
50 uint8_t moves[STARTING_MOVES];
51 int8_t minmoves;
52 int8_t maxmoves;
53} dfsarg_solve_h48_maketasks_t;
25 54
26STATIC void solve_h48_appendsolution(dfsarg_solveh48_t *); 55STATIC int64_t solve_h48_appendsolution(dfsarg_solve_h48_t *);
27STATIC_INLINE bool solve_h48_stop(dfsarg_solveh48_t *); 56STATIC bool solve_h48_appendmoves(dfsarg_solve_h48_t *, int8_t,
28STATIC int64_t solve_h48_dfs(dfsarg_solveh48_t *); 57 uint8_t *, uint8_t);
29STATIC int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint64_t, 58STATIC bool solve_h48_appendchar(dfsarg_solve_h48_t *, char);
59STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *);
60STATIC int64_t solve_h48_maketasks(
61 dfsarg_solve_h48_t *, dfsarg_solve_h48_maketasks_t *,
62 solve_h48_task_t [static STARTING_CUBES], int *);
63STATIC void *solve_h48_runthread(void *);
64STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t *);
65STATIC int64_t solve_h48(cube_t, int8_t, int8_t, uint64_t, uint64_t,
30 const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]); 66 const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]);
31 67
32STATIC uint32_t 68STATIC int64_t
33allowednextmove_h48(uint8_t *moves, uint8_t n, uint8_t h48branch) 69solve_h48_appendsolution(dfsarg_solve_h48_t *arg)
34{ 70{
35 uint32_t result = MM_ALLMOVES; 71 uint8_t t;
36 if (h48branch & MM_NORMALBRANCH) 72 int64_t ret;
37 result &= MM_NOHALFTURNS; 73 uint64_t solstart;
38 if (n < 1)
39 return result;
40 74
41 uint8_t base1 = movebase(moves[n-1]); 75 if (*arg->nsols >= arg->maxsolutions)
42 uint8_t axis1 = moveaxis(moves[n-1]); 76 return 0;
43 77
44 result = disable_moves(result, base1 * 3); 78 solstart = *arg->solutions_used;
45 if (base1 % 2) 79 invertmoves(arg->premoves, arg->npremoves, arg->moves + arg->nmoves);
46 result = disable_moves(result, (base1 - 1) * 3);
47 80
48 if (n == 1) 81 /* Do not append the solution in case premoves cancel with normal */
49 return result; 82 if (arg->npremoves > 0 && !allowednextmove(arg->moves, arg->nmoves+1))
83 return 0;
84 if (arg->npremoves > 1 && !allowednextmove(arg->moves, arg->nmoves+2))
85 return 0;
50 86
51 uint8_t base2 = movebase(moves[n-2]); 87 for (t = 0, ret = 0; t < 48 && *arg->nsols < arg->maxsolutions; t++) {
52 uint8_t axis2 = moveaxis(moves[n-2]); 88 if (!(arg->symmask0 & (UINT64_C(1) << (uint64_t)t)))
89 continue;
53 90
54 if(axis1 == axis2) 91 if (!solve_h48_appendmoves(arg, arg->nmoves + arg->npremoves,
55 result = disable_moves(result, base2 * 3); 92 arg->moves, t))
93 goto solve_h48_appendsolution_error;
94
95 LOG("Solution found: %s\n", *arg->solutions + solstart);
56 96
57 return result; 97 if (!solve_h48_appendchar(arg, '\n'))
98 goto solve_h48_appendsolution_error;
99 (*arg->nsols)++;
100 ret++;
101 }
102
103 return ret;
104
105solve_h48_appendsolution_error:
106 LOG("Could not append solution to buffer: size too small\n");
107 return NISSY_ERROR_BUFFER_SIZE;
58} 108}
59 109
60STATIC void 110STATIC bool
61solve_h48_appendsolution(dfsarg_solveh48_t *arg) 111solve_h48_appendmoves(
112 dfsarg_solve_h48_t *arg,
113 int8_t n,
114 uint8_t *moves,
115 uint8_t t
116)
62{ 117{
118 int i;
63 int64_t strl; 119 int64_t strl;
64 uint8_t invertedpremoves[MAXLEN]; 120 uint8_t mm[MAXLEN];
65 char *solution = *arg->nextsol;
66 121
67 strl = writemoves( 122 for (i = 0; i < n; i++)
68 arg->moves, arg->nmoves, arg->solutions_size, *arg->nextsol); 123 mm[i] = transform_move(moves[i], t);
69 124
70 if (strl < 0) 125 strl = writemoves(mm, n, arg->solutions_size - *arg->solutions_used,
71 goto solve_h48_appendsolution_error; 126 *arg->solutions + *arg->solutions_used);
72 *arg->nextsol += strl-1;
73 arg->solutions_size -= strl-1;
74 127
75 if (arg->npremoves) { 128 if (strl < 0)
76 **arg->nextsol = ' '; 129 return false;
77 (*arg->nextsol)++;
78 arg->solutions_size--;
79 130
80 invertmoves(arg->premoves, arg->npremoves, invertedpremoves); 131 *arg->solutions_used += MAX(0, strl-1);
81 strl = writemoves(invertedpremoves, 132 return true;
82 arg->npremoves, arg->solutions_size, *arg->nextsol); 133}
83 134
84 if (strl < 0) 135STATIC bool
85 goto solve_h48_appendsolution_error; 136solve_h48_appendchar(dfsarg_solve_h48_t *arg, char c)
86 *arg->nextsol += strl-1; 137{
87 arg->solutions_size -= strl-1; 138 if (arg->solutions_size <= *arg->solutions_used)
88 } 139 return false;
89 LOG("Solution found: %s\n", solution);
90 140
91 **arg->nextsol = '\n'; 141 *(*arg->solutions + *arg->solutions_used) = c;
92 (*arg->nextsol)++; 142 (*arg->solutions_used)++;
93 arg->solutions_size--;
94 (*arg->nsols)++;
95 143
96solve_h48_appendsolution_error: 144 return true;
97 /* We could add some logging, but writemoves() already does */
98 return;
99} 145}
100 146
101STATIC_INLINE bool 147STATIC_INLINE bool
102solve_h48_stop(dfsarg_solveh48_t *arg) 148solve_h48_stop(dfsarg_solve_h48_t *arg)
103{ 149{
104 uint32_t data, data_inv; 150 uint32_t data, data_inv;
105 int8_t cbound, cbound_inv, h48bound, h48bound_inv; 151 int64_t coord;
106 int64_t coord, coord_inv; 152 int8_t target, nh;
153 uint8_t pval_cocsep, pval_eoesep;
107 154
155 target = arg->depth - arg->nmoves - arg->npremoves;
156 if (target <= 0 || *arg->nsols == arg->maxsolutions)
157 return true;
158
159 arg->movemask_normal = arg->movemask_inverse = MM_ALLMOVES;
108 arg->nodes_visited++; 160 arg->nodes_visited++;
109 161
110 arg->nissbranch = MM_NORMAL; 162 /* Preliminary probing using last computed bound, if possible */
111 cbound = get_h48_cdata(arg->cube, arg->cocsepdata, &data); 163
112 if (cbound + arg->nmoves + arg->npremoves > arg->depth) 164 if ((arg->use_lb_normal && arg->lb_normal > target) ||
165 (arg->use_lb_inverse && arg->lb_inverse > target))
113 return true; 166 return true;
114 167
115 cbound_inv = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv); 168 /* Preliminary corner probing */
116 if (cbound_inv + arg->nmoves + arg->npremoves > arg->depth) 169
170 if (get_h48_cdata(arg->cube, arg->cocsepdata, &data) > target ||
171 get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv) > target)
117 return true; 172 return true;
118 173
119 coord = coord_h48_edges(arg->cube, COCLASS(data), TTREP(data), arg->h); 174 /* Inverse probing */
120 h48bound = get_h48_pval(arg->h48data, coord, arg->k);
121 175
122 /* If the h48 bound is > 0, we add the base value. */ 176 if (!arg->use_lb_inverse) {
123 /* Otherwise, we use the fallback h0k4 value instead. */ 177 coord = coord_h48_edges(
178 arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h);
179 arg->lb_inverse = get_h48_pval(arg->h48data, coord, arg->k);
180 arg->table_lookups++;
124 181
125 if (arg->k == 2) { 182 if (arg->k == 2 && arg->lb_inverse == 0) {
126 if (h48bound == 0) {
127 arg->table_fallbacks++; 183 arg->table_fallbacks++;
128 h48bound = get_h48_pval( 184
129 arg->h48data_fallback, coord >> arg->h, 4); 185 pval_cocsep = get_h48_pval(
186 arg->h48data_fallback_h0k4, coord >> arg->h, 4);
187 pval_eoesep = get_eoesep_pval_cube(
188 arg->h48data_fallback_eoesep, arg->inverse);
189 arg->lb_inverse = MAX(pval_cocsep, pval_eoesep);
130 } else { 190 } else {
131 h48bound += arg->base; 191 arg->lb_inverse += arg->base;
132 } 192 }
193
194 arg->use_lb_inverse = true;
133 } 195 }
134 if (h48bound + arg->nmoves + arg->npremoves > arg->depth) 196
197 if (arg->lb_inverse > target)
135 return true; 198 return true;
136 if (h48bound + arg->nmoves + arg->npremoves == arg->depth) 199 nh = arg->lb_inverse == target;
137 arg->nissbranch = MM_INVERSEBRANCH; 200 arg->movemask_normal = nh * MM_NOHALFTURNS + (1-nh) * MM_ALLMOVES;
201
202 /* Normal probing */
138 203
139 coord_inv = coord_h48_edges( 204 if (!arg->use_lb_normal) {
140 arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h); 205 coord = coord_h48_edges(
141 h48bound_inv = get_h48_pval(arg->h48data, coord_inv, arg->k); 206 arg->cube, COCLASS(data), TTREP(data), arg->h);
142 if (arg->k == 2) { 207 arg->lb_normal = get_h48_pval(arg->h48data, coord, arg->k);
143 if (h48bound_inv == 0) { 208 arg->table_lookups++;
209
210 if (arg->k == 2 && arg->lb_normal == 0) {
144 arg->table_fallbacks++; 211 arg->table_fallbacks++;
145 h48bound_inv = get_h48_pval( 212
146 arg->h48data_fallback, coord_inv >> arg->h, 4); 213 pval_cocsep = get_h48_pval(
214 arg->h48data_fallback_h0k4, coord >> arg->h, 4);
215 pval_eoesep = get_eoesep_pval_cube(
216 arg->h48data_fallback_eoesep, arg->cube);
217 arg->lb_normal = MAX(pval_cocsep, pval_eoesep);
147 } else { 218 } else {
148 h48bound_inv += arg->base; 219 arg->lb_normal += arg->base;
149 } 220 }
221
222 arg->use_lb_normal = true;
150 } 223 }
151 if (h48bound_inv + arg->nmoves + arg->npremoves > arg->depth) 224
225 if (arg->lb_normal > target)
152 return true; 226 return true;
153 if (h48bound_inv + arg->nmoves + arg->npremoves == arg->depth) 227 nh = arg->lb_normal == target;
154 arg->nissbranch = MM_NORMALBRANCH; 228 arg->movemask_inverse = nh * MM_NOHALFTURNS + (1-nh) * MM_ALLMOVES;
155 229
156 return false; 230 return false;
157} 231}
158 232
159STATIC int64_t 233STATIC int64_t
160solve_h48_dfs(dfsarg_solveh48_t *arg) 234solve_h48_dfs(dfsarg_solve_h48_t *arg)
161{ 235{
162 dfsarg_solveh48_t nextarg; 236 int64_t ret, n;
163 int64_t ret; 237 uint8_t m, lbn, lbi;
164 uint8_t m; 238 uint32_t mm_normal, mm_inverse;
165 239 bool ulbi, ulbn;
166 if (*arg->nsols == arg->maxsolutions) 240 cube_t backup_cube, backup_inverse;
167 return 0;
168
169 if (solve_h48_stop(arg))
170 return 0;
171 241
172 if (issolved(arg->cube)) { 242 if (issolved(arg->cube)) {
173 if (arg->nmoves + arg->npremoves != arg->depth) 243 if (arg->nmoves + arg->npremoves != arg->depth)
174 return 0; 244 return 0;
175 solve_h48_appendsolution(arg); 245 pthread_mutex_lock(arg->solutions_mutex);
176 return 1; 246 ret = solve_h48_appendsolution(arg);
247 pthread_mutex_unlock(arg->solutions_mutex);
248 return ret;
177 } 249 }
178 250
179 nextarg = *arg; 251 if (solve_h48_stop(arg))
252 return 0;
253
254 backup_cube = arg->cube;
255 backup_inverse = arg->inverse;
256 lbn = arg->lb_normal;
257 lbi = arg->lb_inverse;
258 ulbn = arg->use_lb_normal;
259 ulbi = arg->use_lb_inverse;
260
180 ret = 0; 261 ret = 0;
181 uint32_t allowed; 262 mm_normal = allowednextmove_mask(arg->moves, arg->nmoves) &
182 if(arg->nissbranch & MM_INVERSE) { 263 arg->movemask_normal;
183 allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch); 264 mm_inverse = allowednextmove_mask(arg->premoves, arg->npremoves) &
265 arg->movemask_inverse;
266 if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) {
267 arg->nmoves++;
184 for (m = 0; m < 18; m++) { 268 for (m = 0; m < 18; m++) {
185 if(allowed & (1 << m)) { 269 if (!(mm_normal & (1 << m)))
186 nextarg.npremoves = arg->npremoves + 1; 270 continue;
187 nextarg.premoves[arg->npremoves] = m; 271 arg->moves[arg->nmoves-1] = m;
188 nextarg.inverse = move(arg->inverse, m); 272 arg->cube = move(backup_cube, m);
189 nextarg.cube = premove(arg->cube, m); 273 arg->inverse = premove(backup_inverse, m);
190 ret += solve_h48_dfs(&nextarg); 274 arg->lb_inverse = lbi;
191 } 275 arg->use_lb_normal = false;
276 arg->use_lb_inverse = ulbi && m % 3 == 1;
277 n = solve_h48_dfs(arg);
278 if (n < 0)
279 return n;
280 ret += n;
192 } 281 }
282 arg->nmoves--;
193 } else { 283 } else {
194 allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch); 284 arg->npremoves++;
195 for (m = 0; m < 18; m++) { 285 for (m = 0; m < 18; m++) {
196 if (allowed & (1 << m)) { 286 if(!(mm_inverse & (1 << m)))
197 nextarg.nmoves = arg->nmoves + 1; 287 continue;
198 nextarg.moves[arg->nmoves] = m; 288 arg->premoves[arg->npremoves-1] = m;
199 nextarg.cube = move(arg->cube, m); 289 arg->inverse = move(backup_inverse, m);
200 nextarg.inverse = premove(arg->inverse, m); 290 arg->cube = premove(backup_cube, m);
201 ret += solve_h48_dfs(&nextarg); 291 arg->lb_normal = lbn;
202 } 292 arg->use_lb_inverse = false;
293 arg->use_lb_normal = ulbn && m % 3 == 1;
294 n = solve_h48_dfs(arg);
295 if (n < 0)
296 return n;
297 ret += n;
203 } 298 }
299 arg->npremoves--;
204 } 300 }
205 301
206 arg->nodes_visited = nextarg.nodes_visited; 302 arg->cube = backup_cube;
207 arg->table_fallbacks = nextarg.table_fallbacks; 303 arg->inverse = backup_inverse;
304
208 return ret; 305 return ret;
209} 306}
210 307
308STATIC void *
309solve_h48_runthread(void *arg)
310{
311 int i, j;
312 solve_h48_task_t task;
313 dfsarg_solve_h48_t * dfsarg;
314 cube_t cube;
315
316 dfsarg = (dfsarg_solve_h48_t *)arg;
317 cube = dfsarg->start_cube;
318
319 for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += THREADS) {
320 task = dfsarg->tasks[i];
321 memcpy(dfsarg->moves, task.moves, STARTING_MOVES);
322 dfsarg->cube = cube;
323 for (j = 0; j < STARTING_MOVES; j++)
324 dfsarg->cube = move(
325 dfsarg->cube, dfsarg->moves[j]);
326 dfsarg->inverse = inverse(dfsarg->cube);
327 dfsarg->nmoves = STARTING_MOVES;
328 dfsarg->npremoves = 0;
329 dfsarg->lb_normal = 0;
330 dfsarg->lb_inverse = 0;
331 dfsarg->use_lb_normal = false;
332 dfsarg->use_lb_inverse = false;
333 dfsarg->movemask_normal = MM_ALLMOVES;
334 dfsarg->movemask_inverse = MM_ALLMOVES;
335
336 solve_h48_dfs(dfsarg);
337 }
338
339 return NULL;
340}
341
342STATIC int64_t
343solve_h48_maketasks(
344 dfsarg_solve_h48_t *solve_arg,
345 dfsarg_solve_h48_maketasks_t *maketasks_arg,
346 solve_h48_task_t tasks[static STARTING_CUBES],
347 int *ntasks
348)
349{
350 int r;
351 int64_t appret;
352 uint8_t m, t;
353 uint32_t mm;
354 cube_t backup_cube;
355
356 if (issolved(maketasks_arg->cube)) {
357 if (maketasks_arg->nmoves > maketasks_arg->maxmoves ||
358 maketasks_arg->nmoves < maketasks_arg->minmoves ||
359 *solve_arg->nsols >= solve_arg->maxsolutions)
360 return NISSY_OK;
361 memcpy(solve_arg->moves,
362 maketasks_arg->moves, maketasks_arg->nmoves);
363 solve_arg->nmoves = maketasks_arg->nmoves;
364 appret = solve_h48_appendsolution(solve_arg);
365 return appret < 0 ? appret : NISSY_OK;
366 }
367
368 if (maketasks_arg->nmoves == STARTING_MOVES) {
369 tasks[*ntasks].cube = maketasks_arg->cube;
370 memcpy(tasks[*ntasks].moves,
371 maketasks_arg->moves, STARTING_MOVES);
372 (*ntasks)++;
373 return NISSY_OK;
374 }
375
376 mm = allowednextmove_mask(maketasks_arg->moves, maketasks_arg->nmoves);
377
378 maketasks_arg->nmoves++;
379 backup_cube = maketasks_arg->cube;
380 for (m = 0; m < 18; m++) {
381 if (!(mm & (1 << m)))
382 continue;
383 maketasks_arg->moves[maketasks_arg->nmoves-1] = m;
384 maketasks_arg->cube = move(backup_cube, m);
385 r = solve_h48_maketasks(
386 solve_arg, maketasks_arg, tasks, ntasks);
387 if (r < 0)
388 return r;
389
390 /* Avoid symmetry-equivalent moves from the starting cube */
391 if (maketasks_arg->nmoves == 1)
392 for (t = 0; t < 48; t++)
393 if (solve_arg->symmask0 &
394 (UINT64_C(1) << (uint64_t)t))
395 mm &= ~(UINT32_C(1) <<
396 (uint32_t)transform_move(m, t));
397 }
398 maketasks_arg->nmoves--;
399 maketasks_arg->cube = backup_cube;
400
401 return NISSY_OK;
402}
403
211STATIC int64_t 404STATIC int64_t
212solve_h48( 405solve_h48(
213 cube_t cube, 406 cube_t cube,
214 int8_t minmoves, 407 int8_t minmoves,
215 int8_t maxmoves, 408 int8_t maxmoves,
216 int8_t maxsolutions, 409 uint64_t maxsolutions,
217 uint64_t data_size, 410 uint64_t data_size,
218 const void *data, 411 const void *data,
219 uint64_t solutions_size, 412 uint64_t solutions_size,
@@ -221,61 +414,150 @@ solve_h48(
221 long long stats[static NISSY_SIZE_SOLVE_STATS] 414 long long stats[static NISSY_SIZE_SOLVE_STATS]
222) 415)
223{ 416{
417 int i, ntasks, eoesep_table_index;
418 int8_t d;
224 _Atomic int64_t nsols; 419 _Atomic int64_t nsols;
225 dfsarg_solveh48_t arg; 420 dfsarg_solve_h48_t arg[THREADS];
226 tableinfo_t info, fbinfo; 421 solve_h48_task_t tasks[STARTING_CUBES];
422 dfsarg_solve_h48_maketasks_t maketasks_arg;
423 long double fallback_rate, lookups_per_node;
424 uint64_t solutions_used, symmask, offset;
425 int64_t nodes_visited, table_lookups, table_fallbacks;
426 tableinfo_t info, fbinfo, fbinfo2;
427 const uint32_t *cocsepdata;
428 const uint8_t *fallback, *h48data;
429 const void *fallback2;
430 pthread_t thread[THREADS];
431 pthread_mutex_t solutions_mutex;
227 432
228 if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) 433 if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
229 goto solve_h48_error_data; 434 goto solve_h48_error_data;
230 435
231 arg = (dfsarg_solveh48_t) { 436 cocsepdata = (uint32_t *)((char *)data + INFOSIZE);
232 .cube = cube, 437 h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE;
233 .inverse = inverse(cube),
234 .nsols = &nsols,
235 .maxsolutions = maxsolutions,
236 .h = info.h48h,
237 .k = info.bits,
238 .base = info.base,
239 .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
240 .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
241 .solutions_size = solutions_size,
242 .nextsol = &solutions,
243 .nodes_visited = 0,
244 .table_fallbacks = 0
245 };
246 438
439 /* Read fallback table(s) */
440 fallback = NULL;
441 if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
442 goto solve_h48_error_data;
443 offset = info.next;
444 eoesep_table_index = 3;
247 if (info.bits == 2) { 445 if (info.bits == 2) {
248 if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
249 goto solve_h48_error_data;
250 /* We only support h0k4 as fallback table */ 446 /* We only support h0k4 as fallback table */
251 if (fbinfo.h48h != 0 || fbinfo.bits != 4) 447 if (fbinfo.h48h != 0 || fbinfo.bits != 4)
252 goto solve_h48_error_data; 448 goto solve_h48_error_data;
253 arg.h48data_fallback = arg.h48data + info.next; 449 fallback = h48data + offset;
254 } else { 450 offset += fbinfo.next;
255 arg.h48data_fallback = NULL; 451 eoesep_table_index++;
452 }
453
454 if (readtableinfo_n(data_size, data, eoesep_table_index, &fbinfo2)
455 != NISSY_OK)
456 goto solve_h48_error_data;
457
458 /* Some heuristic check to see that it is eoesep */
459 if (fbinfo2.bits != 4 || fbinfo2.type != TABLETYPE_SPECIAL)
460 goto solve_h48_error_data;
461 fallback2 = h48data + offset;
462
463 symmask = symmetry_mask(cube);
464 for (i = 0; i < THREADS; i++) {
465 arg[i] = (dfsarg_solve_h48_t) {
466 .start_cube = cube,
467 .cube = cube,
468 .symmask0 = symmask,
469 .nsols = &nsols,
470 .maxsolutions = maxsolutions,
471 .h = info.h48h,
472 .k = info.bits,
473 .base = info.base,
474 .cocsepdata = cocsepdata,
475 .h48data = h48data,
476 .h48data_fallback_h0k4 = fallback,
477 .h48data_fallback_eoesep = fallback2,
478 .solutions_size = solutions_size,
479 .solutions_used = &solutions_used,
480 .solutions = &solutions,
481 .nodes_visited = 0,
482 .table_fallbacks = 0,
483 .table_lookups = 0,
484 .thread_id = i,
485 .solutions_mutex = &solutions_mutex,
486 };
487
256 } 488 }
257 489
258 nsols = 0; 490 nsols = 0;
259 for (arg.depth = minmoves; 491 solutions_used = 0;
260 arg.depth <= maxmoves && nsols < maxsolutions; 492
261 arg.depth++) 493 pthread_mutex_init(&solutions_mutex, NULL);
262 { 494
263 LOG("Found %" PRId64 " solutions, searching at depth %" 495 maketasks_arg = (dfsarg_solve_h48_maketasks_t) {
264 PRId8 "\n", nsols, arg.depth); 496 .cube = cube,
265 arg.nmoves = 0; 497 .nmoves = 0,
266 arg.npremoves = 0; 498 .minmoves = minmoves,
267 solve_h48_dfs(&arg); 499 .maxmoves = maxmoves,
500 };
501 ntasks = 0;
502 solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks);
503 if (ntasks < 0)
504 goto solve_h48_error_solutions_buffer;
505 if (*arg[0].nsols >= (int64_t)maxsolutions)
506 goto solve_h48_done;
507
508 for (i = 0; i < THREADS; i++) {
509 arg[i].ntasks = ntasks;
510 arg[i].tasks = tasks;
268 } 511 }
269 **arg.nextsol = '\0';
270 512
271 stats[0] = arg.nodes_visited; 513 LOG("Prepared %d tasks\n", ntasks);
272 stats[1] = arg.table_fallbacks; 514
273 LOG("Nodes visited: %lld\nTable fallbacks: %lld\n", 515 for (
274 arg.nodes_visited, arg.table_fallbacks); 516 d = MAX(minmoves, STARTING_MOVES + 1);
517 d <= maxmoves && nsols < (int64_t)maxsolutions;
518 d++
519 ) {
520 if (d >= 10)
521 LOG("Found %" PRId64 " solutions, searching at depth %"
522 PRId8 "\n", nsols, d);
523 for (i = 0; i < THREADS; i++) {
524 arg[i].depth = d;
525 pthread_create(
526 &thread[i], NULL, solve_h48_runthread, &arg[i]);
527 }
528 for (i = 0; i < THREADS; i++)
529 pthread_join(thread[i], NULL);
530 }
531
532solve_h48_done:
533 if (!solve_h48_appendchar(&arg[0], '\0'))
534 goto solve_h48_error_solutions_buffer;
535
536 nodes_visited = table_lookups = table_fallbacks = 0;
537 for (i = 0; i < THREADS; i++) {
538 nodes_visited += arg[i].nodes_visited;
539 table_fallbacks += arg[i].table_fallbacks;
540 table_lookups += arg[i].table_lookups;
541 }
542
543 stats[0] = nodes_visited;
544 stats[1] = table_lookups;
545 stats[2] = table_fallbacks;
546 lookups_per_node = table_lookups / (long double)nodes_visited;
547 fallback_rate = nodes_visited == 0 ? 0.0 :
548 (table_fallbacks * 100) / (long double)table_lookups;
549 LOG("Nodes visited: %" PRId64 "\n", nodes_visited);
550 LOG("Lookups: %" PRId64 " (%.3Lf per node)\n",
551 table_lookups, lookups_per_node);
552 LOG("Table fallbacks: %" PRId64 " (%.3Lf%%)\n",
553 table_fallbacks, fallback_rate);
275 554
276 return nsols; 555 return nsols;
277 556
278solve_h48_error_data: 557solve_h48_error_data:
279 LOG("solve_h48: error reading table\n"); 558 LOG("solve_h48: error reading table\n");
280 return NISSY_ERROR_DATA; 559 return NISSY_ERROR_DATA;
560
561solve_h48_error_solutions_buffer:
562 return NISSY_ERROR_BUFFER_SIZE;
281} 563}
diff --git a/src/solvers/h48/solve_multithread.h b/src/solvers/h48/solve_multithread.h
deleted file mode 100644
index 72f519e..0000000
--- a/src/solvers/h48/solve_multithread.h
+++ /dev/null
@@ -1,350 +0,0 @@
1#define MAX_QUEUE_SIZE 244
2#define BFS_DEPTH 2
3
4typedef struct {
5 dfsarg_solveh48_t tasks[MAX_QUEUE_SIZE];
6 int front;
7 int rear;
8 int tasks_count;
9 int active;
10 pthread_mutex_t mutex;
11 pthread_cond_t cond;
12 pthread_cond_t active_cond;
13 atomic_bool terminate;
14 _Atomic long long nodes_visited_global;
15 _Atomic long long table_fallbacks_global;
16} task_queue_t;
17
18STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *);
19STATIC void init_queue(task_queue_t *);
20STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t);
21STATIC void copy_queue(task_queue_t *, task_queue_t *, int, _Atomic int64_t *);
22STATIC void *start_thread(void *);
23STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *, int8_t);
24STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *);
25STATIC int64_t solve_h48_multithread(cube_t, int8_t, int8_t, int8_t, uint64_t,
26 const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]);
27
28STATIC void
29solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq)
30{
31 pthread_mutex_lock(&tq->mutex);
32 int64_t strl = 0;
33 uint8_t invertedpremoves[MAXLEN];
34 char *solution = *arg->nextsol;
35
36 strl = writemoves(
37 arg->moves, arg->nmoves, arg->solutions_size, *arg->nextsol);
38
39 if (strl < 0)
40 goto solve_h48_appendsolution_thread_error;
41 *arg->nextsol += strl-1;
42 arg->solutions_size -= strl-1;
43
44 if (arg->npremoves)
45 {
46 **arg->nextsol = ' ';
47 (*arg->nextsol)++;
48 arg->solutions_size--;
49
50 invertmoves(arg->premoves, arg->npremoves, invertedpremoves);
51 strl = writemoves(invertedpremoves,
52 arg->npremoves, arg->solutions_size, *arg->nextsol);
53
54 if (strl < 0)
55 goto solve_h48_appendsolution_thread_error;
56 *arg->nextsol += strl-1;
57 arg->solutions_size -= strl-1;
58 }
59 LOG("Solution found: %s\n", solution);
60
61 **arg->nextsol = '\n';
62 (*arg->nextsol)++;
63 arg->solutions_size--;
64 (*arg->nsols)++;
65
66solve_h48_appendsolution_thread_error:
67 /* We could add some logging, but writemoves() already does */
68 pthread_mutex_unlock(&tq->mutex);
69}
70
71STATIC void
72init_queue(task_queue_t *queue)
73{
74 queue->front = 0;
75 queue->rear = 0;
76 queue->tasks_count = 0;
77 queue->active = 0;
78 queue->terminate = ATOMIC_VAR_INIT(false);
79 pthread_mutex_init(&queue->mutex, NULL);
80 pthread_cond_init(&queue->cond, NULL);
81 pthread_cond_init(&queue->active_cond, NULL);
82}
83
84STATIC void
85submit_task(task_queue_t *queue, dfsarg_solveh48_t task)
86{
87 pthread_mutex_lock(&queue->mutex);
88 queue->tasks[queue->rear] = task;
89 queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
90 queue->tasks_count++;
91 pthread_cond_broadcast(&queue->cond);
92 pthread_mutex_unlock(&queue->mutex);
93}
94
95STATIC void
96copy_queue(task_queue_t *src, task_queue_t *dest, int depth, _Atomic int64_t *nsols)
97{
98 pthread_mutex_lock(&dest->mutex);
99 for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE)
100 {
101 dest->tasks[i] = src->tasks[i];
102 dest->tasks[i].depth = depth;
103 }
104 dest->front = src->front;
105 dest->rear = src->rear;
106 dest->tasks_count = src->tasks_count;
107 pthread_cond_broadcast(&dest->cond);
108 pthread_mutex_unlock(&dest->mutex);
109}
110
111STATIC void *
112start_thread(void *arg)
113{
114 task_queue_t *queue = (task_queue_t *)arg;
115 while (1) {
116 pthread_mutex_lock(&queue->mutex);
117 while (queue->tasks_count == 0 && !queue->terminate) {
118 pthread_cond_wait(&queue->cond, &queue->mutex);
119 }
120 if (queue->tasks_count == 0 && queue->terminate) {
121 pthread_mutex_unlock(&queue->mutex);
122 break;
123 }
124
125 if (queue->tasks_count > 0) {
126 dfsarg_solveh48_t task = queue->tasks[queue->front];
127 queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
128 queue->tasks_count--;
129 queue->active++;
130 pthread_mutex_unlock(&queue->mutex);
131
132 solve_h48_single(&task, queue);
133 queue->nodes_visited_global += task.nodes_visited;
134 queue->table_fallbacks_global += task.table_fallbacks;
135
136 pthread_mutex_lock(&queue->mutex);
137 queue->active--;
138
139 if(queue->tasks_count == 0 && queue->active == 0)
140 pthread_cond_signal(&queue->active_cond);
141 }
142 pthread_mutex_unlock(&queue->mutex);
143 }
144 return NULL;
145}
146
147STATIC int64_t
148solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq, int8_t maxmoves)
149{
150 dfsarg_solveh48_t queue[MAX_QUEUE_SIZE];
151 int front = 0, rear = 0;
152 dfsarg_solveh48_t nextarg;
153 int depth = 0;
154 int nodes_at_current_depth = 1;
155 int nodes_at_next_depth = 0;
156 queue[rear++] = *arg_zero;
157
158 dfsarg_solveh48_t task_pool[MAX_QUEUE_SIZE];
159
160 while (front < rear){
161 dfsarg_solveh48_t arg = queue[front++];
162 nodes_at_current_depth--;
163
164 if (*arg.nsols == arg.maxsolutions)
165 return 1;
166
167 if (issolved(arg.cube)){
168 if (arg.nmoves + arg.npremoves >= arg.depth && arg.nmoves + arg.npremoves <= maxmoves)
169 solve_h48_appendsolution(&arg);
170 continue;
171 }
172
173 arg.nissbranch = MM_NORMAL;
174 uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch);
175
176 for (uint8_t m = 0; m < 18; m++){
177 if (allowed & (1 << m)){
178 nextarg = arg;
179 nextarg.nmoves = arg.nmoves + 1;
180 nextarg.moves[arg.nmoves] = m;
181 nextarg.cube = move(arg.cube, m);
182 nextarg.inverse = premove(arg.inverse, m);
183
184 if (nextarg.nmoves == BFS_DEPTH){
185 dfsarg_solveh48_t *task = &task_pool[rear % MAX_QUEUE_SIZE];
186 *task = nextarg;
187 submit_task(tq, *task);
188 } else {
189 queue[rear++] = nextarg;
190 nodes_at_next_depth++;
191 }
192 }
193 }
194 if (nodes_at_current_depth == 0){
195 nodes_at_current_depth = nodes_at_next_depth;
196 nodes_at_next_depth = 0;
197 LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", *nextarg.nsols, depth++);
198 }
199 if (depth == BFS_DEPTH) return 0;
200 }
201 return 1;
202}
203
204STATIC int64_t
205solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq)
206{
207 dfsarg_solveh48_t nextarg;
208 int64_t ret;
209 uint8_t m;
210
211 if (*arg->nsols == arg->maxsolutions)
212 return 0;
213
214 if (solve_h48_stop(arg))
215 return 0;
216
217 if (issolved(arg->cube)){
218 if (arg->nmoves + arg->npremoves != arg->depth)
219 return 0;
220 solve_h48_appendsolution_thread(arg, tq);
221 return 1;
222 }
223
224 nextarg = *arg;
225 ret = 0;
226 uint32_t allowed;
227 if (arg->nissbranch & MM_INVERSE){
228 allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch);
229 for (m = 0; m < 18; m++){
230 if (allowed & (1 << m)){
231 nextarg.npremoves = arg->npremoves + 1;
232 nextarg.premoves[arg->npremoves] = m;
233 nextarg.inverse = move(arg->inverse, m);
234 nextarg.cube = premove(arg->cube, m);
235 ret += solve_h48_single(&nextarg, tq);
236 }
237 }
238 } else {
239 allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch);
240 for (m = 0; m < 18; m++){
241 if (allowed & (1 << m)){
242 nextarg.nmoves = arg->nmoves + 1;
243 nextarg.moves[arg->nmoves] = m;
244 nextarg.cube = move(arg->cube, m);
245 nextarg.inverse = premove(arg->inverse, m);
246 ret += solve_h48_single(&nextarg, tq);
247 }
248 }
249 }
250
251 arg->nodes_visited = nextarg.nodes_visited;
252 arg->table_fallbacks = nextarg.table_fallbacks;
253 return ret;
254}
255
256STATIC int64_t
257solve_h48_multithread(
258 cube_t cube,
259 int8_t minmoves,
260 int8_t maxmoves,
261 int8_t maxsolutions,
262 uint64_t data_size,
263 const void *data,
264 uint64_t solutions_size,
265 char *solutions,
266 long long stats[static NISSY_SIZE_SOLVE_STATS]
267)
268{
269 _Atomic int64_t nsols = 0;
270 int p_depth = 0;
271 dfsarg_solveh48_t arg;
272 tableinfo_t info, fbinfo;
273 pthread_t threads[THREADS];
274
275 if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
276 goto solve_h48_multithread_error_data;
277
278 arg = (dfsarg_solveh48_t){
279 .cube = cube,
280 .inverse = inverse(cube),
281 .nsols = &nsols,
282 .depth = minmoves,
283 .maxsolutions = maxsolutions,
284 .h = info.h48h,
285 .k = info.bits,
286 .base = info.base,
287 .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
288 .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
289 .solutions_size = solutions_size,
290 .nextsol = &solutions,
291 .nodes_visited = 0,
292 .table_fallbacks = 0
293 };
294
295 if (info.bits == 2) {
296 if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
297 goto solve_h48_multithread_error_data;
298 /* We only support h0k4 as fallback table */
299 if (fbinfo.h48h != 0 || fbinfo.bits != 4)
300 goto solve_h48_multithread_error_data;
301 arg.h48data_fallback = arg.h48data + info.next;
302 } else {
303 arg.h48data_fallback = NULL;
304 }
305
306 task_queue_t q;
307 init_queue(&q);
308 if (solve_h48_bfs(&arg, &q, maxmoves))
309 return nsols;
310
311 task_queue_t nq;
312 init_queue(&nq);
313
314 nq.nodes_visited_global = nq.table_fallbacks_global = 0;
315 for (int i = 0; i < THREADS; i++) {
316 pthread_create(&threads[i], NULL, &start_thread, &nq);
317 }
318
319 nsols = 0;
320 for (p_depth = minmoves > BFS_DEPTH ? minmoves : BFS_DEPTH;
321 p_depth <= maxmoves && nsols < maxsolutions;
322 p_depth++)
323 {
324 LOG("Found %" PRId64 " solutions, "
325 "searching at depth %" PRId8 "\n", nsols, p_depth);
326 copy_queue(&q, &nq, p_depth, &nsols);
327
328 pthread_mutex_lock(&nq.mutex);
329 while (nq.active > 0 || nq.tasks_count > 0)
330 pthread_cond_wait(&nq.active_cond, &nq.mutex);
331 pthread_mutex_unlock(&nq.mutex);
332 }
333
334 atomic_store(&nq.terminate, true);
335 pthread_cond_broadcast(&nq.cond);
336
337 for (int i = 0; i < THREADS; i++) {
338 pthread_join(threads[i], NULL);
339 }
340 **arg.nextsol = '\0';
341
342 stats[0] = nq.nodes_visited_global;
343 stats[1] = nq.table_fallbacks_global;
344 LOG("Nodes visited: %lld\nTable fallbacks: %lld\n",
345 nq.nodes_visited_global, nq.table_fallbacks_global);
346
347 return nsols;
348
349solve_h48_multithread_error_data: LOG("solve_h48: error reading table\n"); return NISSY_ERROR_DATA;
350}
diff --git a/src/solvers/h48/stats.h b/src/solvers/h48/stats.h
deleted file mode 100644
index 2a7e887..0000000
--- a/src/solvers/h48/stats.h
+++ /dev/null
@@ -1,100 +0,0 @@
1/*
2The h48stats solver computes how many moves it takes to solve to
3each of the 12 h48 coordinates, one for each value of h from 0 to 11.
4The solutions array is filled with the length of the solutions. The
5solutions array is therefore not a printable string.
6*/
7
8typedef struct {
9 cube_t cube;
10 int8_t nmoves;
11 int8_t depth;
12 uint8_t moves[MAXLEN];
13 const uint32_t *cocsepdata;
14 const uint8_t *h48data;
15 char *s;
16} dfsarg_solveh48stats_t;
17
18STATIC int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *);
19STATIC int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
20
21STATIC int64_t
22solve_h48stats_dfs(dfsarg_solveh48stats_t *arg)
23{
24 const int64_t limit = 11;
25
26 int8_t bound, u;
27 uint8_t m;
28 uint32_t d;
29 int64_t coord, h;
30 dfsarg_solveh48stats_t nextarg;
31
32 /* Check cocsep lower bound (corners only) */
33 bound = get_h48_cdata(arg->cube, arg->cocsepdata, &d);
34 if (bound + arg->nmoves > arg->depth)
35 return 0;
36
37 /* Check h48 lower bound for h=0 (esep, but no eo) */
38 coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0);
39 bound = get_h48_pval(arg->h48data, coord, 4);
40 if (bound + arg->nmoves > arg->depth)
41 return 0;
42
43 /* Update all other values, if solved */
44 coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 11);
45 for (h = 0; h <= limit; h++) {
46 u = coord >> (11-h) == 0 && arg->s[h] == 99;
47 arg->s[h] = u * arg->nmoves + (1-u) * arg->s[h];
48 }
49
50 if (arg->s[limit] != 99)
51 return 0;
52
53 nextarg = *arg;
54 nextarg.nmoves = arg->nmoves + 1;
55 for (m = 0; m < 18; m++) {
56 nextarg.moves[arg->nmoves] = m;
57 if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
58 /* If a move is not allowed, neither are its 180
59 * and 270 degree variations */
60 m += 2;
61 continue;
62 }
63 nextarg.cube = move(arg->cube, m);
64 solve_h48stats_dfs(&nextarg);
65 }
66
67 return 0;
68}
69
70STATIC int64_t
71solve_h48stats(
72 cube_t cube,
73 int8_t maxmoves,
74 const void *data,
75 char solutions[static 12]
76)
77{
78 int i;
79 dfsarg_solveh48stats_t arg;
80
81 arg = (dfsarg_solveh48stats_t) {
82 .cube = cube,
83 .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
84 .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
85 .s = solutions
86 };
87
88 for (i = 0; i < 12; i++)
89 solutions[i] = (char)99;
90
91 for (arg.depth = 0;
92 arg.depth <= maxmoves && solutions[11] == 99;
93 arg.depth++)
94 {
95 arg.nmoves = 0;
96 solve_h48stats_dfs(&arg);
97 }
98
99 return 0;
100}

Generated with cgit - Back to sebastiano.tronto.net