aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/core/cube.h157
-rw-r--r--src/core/moves.h162
-rw-r--r--src/solvers/h48/solve.h83
3 files changed, 200 insertions, 202 deletions
diff --git a/src/core/cube.h b/src/core/cube.h
index b24fb5c..4b28103 100644
--- a/src/core/cube.h
+++ b/src/core/cube.h
@@ -13,11 +13,13 @@ _static cube_t frommoves(const char *);
13_static void getcube_fix(int64_t *, int64_t *, int64_t *, int64_t *); 13_static void getcube_fix(int64_t *, int64_t *, int64_t *, int64_t *);
14_static cube_t getcube(int64_t, int64_t, int64_t, int64_t); 14_static cube_t getcube(int64_t, int64_t, int64_t, int64_t);
15 15
16_static cube_t move(cube_t, uint8_t);
17_static cube_t transform_edges(cube_t, uint8_t); 16_static cube_t transform_edges(cube_t, uint8_t);
18_static cube_t transform_corners(cube_t, uint8_t); 17_static cube_t transform_corners(cube_t, uint8_t);
19_static cube_t transform(cube_t, uint8_t); 18_static cube_t transform(cube_t, uint8_t);
20 19
20/* declared in moves.h */
21_static cube_t move(cube_t, uint8_t);
22
21_static cube_t 23_static cube_t
22cubefromarray(uint8_t c[static 8], uint8_t e[static 12]) 24cubefromarray(uint8_t c[static 8], uint8_t e[static 12])
23{ 25{
@@ -239,159 +241,6 @@ applytrans(cube_t cube, const char *buf)
239 return transform(cube, t); 241 return transform(cube, t);
240} 242}
241 243
242_static cube_t
243move(cube_t c, uint8_t m)
244{
245 switch (m) {
246 case _move_U:
247 return _move(U, c);
248 case _move_U2:
249 return _move(U2, c);
250 case _move_U3:
251 return _move(U3, c);
252 case _move_D:
253 return _move(D, c);
254 case _move_D2:
255 return _move(D2, c);
256 case _move_D3:
257 return _move(D3, c);
258 case _move_R:
259 return _move(R, c);
260 case _move_R2:
261 return _move(R2, c);
262 case _move_R3:
263 return _move(R3, c);
264 case _move_L:
265 return _move(L, c);
266 case _move_L2:
267 return _move(L2, c);
268 case _move_L3:
269 return _move(L3, c);
270 case _move_F:
271 return _move(F, c);
272 case _move_F2:
273 return _move(F2, c);
274 case _move_F3:
275 return _move(F3, c);
276 case _move_B:
277 return _move(B, c);
278 case _move_B2:
279 return _move(B2, c);
280 case _move_B3:
281 return _move(B3, c);
282 default:
283 LOG("move error, unknown move\n");
284 return zero;
285 }
286}
287
288_static cube_t
289premove(cube_t c, uint8_t m){
290 switch (m) {
291 case _move_U:
292 return _premove(U3, c);
293 case _move_U2:
294 return _premove(U2, c);
295 case _move_U3:
296 return _premove(U, c);
297 case _move_D:
298 return _premove(D3, c);
299 case _move_D2:
300 return _premove(D2, c);
301 case _move_D3:
302 return _premove(D, c);
303 case _move_R:
304 return _premove(R3, c);
305 case _move_R2:
306 return _premove(R2, c);
307 case _move_R3:
308 return _premove(R, c);
309 case _move_L:
310 return _premove(L3, c);
311 case _move_L2:
312 return _premove(L2, c);
313 case _move_L3:
314 return _premove(L, c);
315 case _move_F:
316 return _premove(F3, c);
317 case _move_F2:
318 return _premove(F2, c);
319 case _move_F3:
320 return _premove(F, c);
321 case _move_B:
322 return _premove(B3, c);
323 case _move_B2:
324 return _premove(B2, c);
325 case _move_B3:
326 return _premove(B, c);
327 default:
328 LOG("move error, unknown move\n");
329 return zero;
330 }
331}
332_static uint8_t
333invertmove(uint8_t m)
334{
335 switch (m) {
336 case _move_U:
337 return _move_U3;
338 case _move_U2:
339 return _move_U2;
340 case _move_U3:
341 return _move_U;
342 case _move_D:
343 return _move_D3;
344 case _move_D2:
345 return _move_D2;
346 case _move_D3:
347 return _move_D;
348 case _move_R:
349 return _move_R3;
350 case _move_R2:
351 return _move_R2;
352 case _move_R3:
353 return _move_R;
354 case _move_L:
355 return _move_L3;
356 case _move_L2:
357 return _move_L2;
358 case _move_L3:
359 return _move_L;
360 case _move_F:
361 return _move_F3;
362 case _move_F2:
363 return _move_F2;
364 case _move_F3:
365 return _move_F;
366 case _move_B:
367 return _move_B3;
368 case _move_B2:
369 return _move_B2;
370 case _move_B3:
371 return _move_B;
372 default:
373 LOG("invertmove error, unknown move\n");
374 return _error;
375 }
376}
377
378_static uint8_t*
379invertpremoves(uint8_t *moves, uint8_t nmoves)
380{
381 uint8_t i;
382 uint8_t *ret = malloc(nmoves * sizeof(uint8_t));
383
384 for (i = 0; i < nmoves; i++)
385 ret[i] = invertmove(moves[i]);
386
387 // invert elements in the array
388 for (i = 0; i < nmoves / 2; i++)
389 _swap(ret[i], ret[nmoves - i - 1]);
390 return ret;
391}
392
393
394
395/* 244/*
396TODO transform is now relegated to a separated file because it is too long. 245TODO transform is now relegated to a separated file because it is too long.
397It would be nice to make it shorter without loosing performance. 246It would be nice to make it shorter without loosing performance.
diff --git a/src/core/moves.h b/src/core/moves.h
index 7da6405..726a452 100644
--- a/src/core/moves.h
+++ b/src/core/moves.h
@@ -1,8 +1,23 @@
1/* probably these can be placed in constants file */
2#define NONISS 0x00
3#define NISS 0x01
4#define INVERSEBRANCH 0x03
5#define BRANCH 0x02
6#define ALLMOVES 0x3FFFF
7#define NOHALFTURNS 0x2DB6D
8
1_static_inline bool allowednextmove(uint8_t *, uint8_t); 9_static_inline bool allowednextmove(uint8_t *, uint8_t);
10_static uint32_t allowednextmoveH48(uint8_t *, uint8_t, uint32_t);
11
2_static_inline uint8_t inverse_trans(uint8_t); 12_static_inline uint8_t inverse_trans(uint8_t);
3_static_inline uint8_t movebase(uint8_t); 13_static_inline uint8_t movebase(uint8_t);
4_static_inline uint8_t moveaxis(uint8_t); 14_static_inline uint8_t moveaxis(uint8_t);
5 15
16_static cube_t move(cube_t, uint8_t);
17_static cube_t premove(cube_t, uint8_t);
18_static uint8_t inverse_move(uint8_t);
19_static uint8_t* invertpremoves(uint8_t *, uint8_t);
20
6_static bool 21_static bool
7allowednextmove(uint8_t *moves, uint8_t n) 22allowednextmove(uint8_t *moves, uint8_t n)
8{ 23{
@@ -28,6 +43,40 @@ allowednextmove(uint8_t *moves, uint8_t n)
28 return axis[1] != axis[2] || base[0] != base[2]; 43 return axis[1] != axis[2] || base[0] != base[2];
29} 44}
30 45
46static uint32_t
47disable_moves(uint32_t current_result, uint8_t base_index)
48{
49 return current_result & ~((1 << base_index) | (1 << (base_index + 1)) | (1 << (base_index + 2)));
50}
51
52_static uint32_t
53allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch)
54{
55 uint32_t result = ALLMOVES;
56 if (h48branch & BRANCH)
57 result &= NOHALFTURNS;
58 if (n < 1)
59 return result;
60
61 uint8_t base1 = movebase(moves[n-1]);
62 uint8_t axis1 = moveaxis(moves[n-1]);
63
64 result = disable_moves(result, base1 * 3);
65 if (base1 >= 9)
66 result = disable_moves(result, (base1 * 3) - 9);
67
68 if (n == 1)
69 return result;
70
71 uint8_t base2 = movebase(moves[n-2]);
72 uint8_t axis2 = moveaxis(moves[n-2]);
73
74 if(axis1 == axis2)
75 result = disable_moves(result, base2 * 3);
76
77 return result;
78}
79
31_static_inline uint8_t 80_static_inline uint8_t
32inverse_trans(uint8_t t) 81inverse_trans(uint8_t t)
33{ 82{
@@ -45,3 +94,116 @@ moveaxis(uint8_t move)
45{ 94{
46 return move / 6; 95 return move / 6;
47} 96}
97
98_static cube_t
99move(cube_t c, uint8_t m)
100{
101 switch (m) {
102 case _move_U:
103 return _move(U, c);
104 case _move_U2:
105 return _move(U2, c);
106 case _move_U3:
107 return _move(U3, c);
108 case _move_D:
109 return _move(D, c);
110 case _move_D2:
111 return _move(D2, c);
112 case _move_D3:
113 return _move(D3, c);
114 case _move_R:
115 return _move(R, c);
116 case _move_R2:
117 return _move(R2, c);
118 case _move_R3:
119 return _move(R3, c);
120 case _move_L:
121 return _move(L, c);
122 case _move_L2:
123 return _move(L2, c);
124 case _move_L3:
125 return _move(L3, c);
126 case _move_F:
127 return _move(F, c);
128 case _move_F2:
129 return _move(F2, c);
130 case _move_F3:
131 return _move(F3, c);
132 case _move_B:
133 return _move(B, c);
134 case _move_B2:
135 return _move(B2, c);
136 case _move_B3:
137 return _move(B3, c);
138 default:
139 LOG("move error, unknown move\n");
140 return zero;
141 }
142}
143
144_static cube_t
145premove(cube_t c, uint8_t m)
146{
147 switch (m) {
148 case _move_U:
149 return _premove(U3, c);
150 case _move_U2:
151 return _premove(U2, c);
152 case _move_U3:
153 return _premove(U, c);
154 case _move_D:
155 return _premove(D3, c);
156 case _move_D2:
157 return _premove(D2, c);
158 case _move_D3:
159 return _premove(D, c);
160 case _move_R:
161 return _premove(R3, c);
162 case _move_R2:
163 return _premove(R2, c);
164 case _move_R3:
165 return _premove(R, c);
166 case _move_L:
167 return _premove(L3, c);
168 case _move_L2:
169 return _premove(L2, c);
170 case _move_L3:
171 return _premove(L, c);
172 case _move_F:
173 return _premove(F3, c);
174 case _move_F2:
175 return _premove(F2, c);
176 case _move_F3:
177 return _premove(F, c);
178 case _move_B:
179 return _premove(B3, c);
180 case _move_B2:
181 return _premove(B2, c);
182 case _move_B3:
183 return _premove(B, c);
184 default:
185 LOG("move error, unknown move\n");
186 return zero;
187 }
188}
189
190_static uint8_t
191inverse_move(uint8_t m)
192{
193 return m - 2 * (m % 3) + 2;
194}
195
196_static uint8_t*
197invertpremoves(uint8_t *moves, uint8_t nmoves)
198{
199 uint8_t i;
200 uint8_t *ret = malloc(nmoves * sizeof(uint8_t));
201
202 for (i = 0; i < nmoves; i++)
203 ret[i] = inverse_move(moves[i]);
204
205 // invert elements in the array
206 for (i = 0; i < nmoves / 2; i++)
207 _swap(ret[i], ret[nmoves - i - 1]);
208 return ret;
209}
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 7430228..751df8f 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -11,10 +11,9 @@ typedef struct {
11 uint32_t *cocsepdata; 11 uint32_t *cocsepdata;
12 uint32_t *h48data; 12 uint32_t *h48data;
13 char **nextsol; 13 char **nextsol;
14 bool niss; 14 uint8_t nissbranch;
15 int8_t npremoves; 15 int8_t npremoves;
16 uint8_t premoves[MAXLEN]; 16 uint8_t premoves[MAXLEN];
17 int8_t totmoves;
18} dfsarg_solveh48_t; 17} dfsarg_solveh48_t;
19 18
20typedef struct { 19typedef struct {
@@ -65,37 +64,30 @@ _static_inline bool
65solve_h48_stop(dfsarg_solveh48_t *arg) 64solve_h48_stop(dfsarg_solveh48_t *arg)
66{ 65{
67 uint32_t data, data_inv; 66 uint32_t data, data_inv;
68 int8_t bound, newbound; 67 int8_t bound;
69 bool niss = false;
70 68
69 arg->nissbranch = NONISS;
71 bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data); 70 bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
72 if (bound + arg->totmoves > arg->depth) 71 if (bound + arg->nmoves + arg->npremoves > arg->depth)
73 return true; 72 return true;
74 73
75 newbound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv); 74 bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
76 if (newbound + arg->totmoves > arg->depth) 75 if (bound + arg->nmoves + arg->npremoves > arg->depth)
77 return true; 76 return true;
78 if (newbound < bound) {
79 bound = newbound;
80 niss = true;
81 }
82 77
83 newbound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data); 78 bound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
84 // LOG("Using pval %" PRId8 "\n", bound); 79 // LOG("Using pval %" PRId8 "\n", bound);
85 if (newbound + arg->totmoves > arg->depth) 80 if (bound + arg->nmoves + arg->npremoves > arg->depth)
86 return true; 81 return true;
87 if (newbound < bound) { 82 if (bound + arg->nmoves + arg->npremoves == arg->depth)
88 bound = newbound; 83 arg->nissbranch = INVERSEBRANCH;
89 niss = false; 84
90 } 85 bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data);
91 newbound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data); 86 if (bound + arg->nmoves + arg->npremoves > arg->depth)
92 if (newbound + arg->totmoves > arg->depth)
93 return true; 87 return true;
94 if (newbound < bound) { 88 if (bound + arg->nmoves + arg->npremoves == arg->depth)
95 bound = newbound; 89 arg->nissbranch = BRANCH;
96 niss = true; 90
97 }
98 arg->niss = niss;
99 return false; 91 return false;
100} 92}
101 93
@@ -113,7 +105,7 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
113 return 0; 105 return 0;
114 106
115 if (issolved(arg->cube)) { 107 if (issolved(arg->cube)) {
116 if (arg->totmoves != arg->depth) 108 if (arg->nmoves + arg->npremoves != arg->depth)
117 return 0; 109 return 0;
118 solve_h48_appendsolution(arg); 110 solve_h48_appendsolution(arg);
119 return 1; 111 return 1;
@@ -122,34 +114,28 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
122 /* TODO: avoid copy, change arg and undo changes after recursion */ 114 /* TODO: avoid copy, change arg and undo changes after recursion */
123 nextarg = *arg; 115 nextarg = *arg;
124 ret = 0; 116 ret = 0;
125 nextarg.totmoves = arg->totmoves + 1; 117 uint32_t allowed;
126 if(arg->niss) { 118 if(arg->nissbranch & 0x01) {
127 nextarg.npremoves = arg->npremoves + 1; 119 allowed = allowednextmoveH48(arg->premoves, arg->npremoves, arg->nissbranch);
128 for (m = 0; m < 18; m++) { 120 for (m = 0; m < 18; m++) {
129 nextarg.premoves[arg->npremoves] = m; 121 if(allowed & (1 << m)) {
130 if (!allowednextmove(nextarg.premoves, nextarg.npremoves)) { 122 nextarg.npremoves = arg->npremoves + 1;
131 /* If a move is not allowed, neither are its 180 123 nextarg.premoves[arg->npremoves] = m;
132 * and 270 degree variations */ 124 nextarg.inverse = move(arg->inverse, m);
133 m += 2; 125 nextarg.cube = premove(arg->cube, m);
134 continue; 126 ret += solve_h48_dfs(&nextarg);
135 } 127 }
136 nextarg.cube = premove(arg->cube, m);
137 nextarg.inverse = move(arg->inverse, m);
138 ret += solve_h48_dfs(&nextarg);
139 } 128 }
140 } else { 129 } else {
141 nextarg.nmoves = arg->nmoves + 1; 130 allowed = allowednextmoveH48(arg->moves, arg->nmoves, arg->nissbranch);
142 for (m = 0; m < 18; m++) { 131 for (m = 0; m < 18; m++) {
143 nextarg.moves[arg->nmoves] = m; 132 if (allowed & (1 << m)) {
144 if (!allowednextmove(nextarg.moves, nextarg.nmoves)) { 133 nextarg.nmoves = arg->nmoves + 1;
145 /* If a move is not allowed, neither are its 180 134 nextarg.moves[arg->nmoves] = m;
146 * and 270 degree variations */ 135 nextarg.cube = move(arg->cube, m);
147 m += 2; 136 nextarg.inverse = premove(arg->inverse, m);
148 continue; 137 ret += solve_h48_dfs(&nextarg);
149 } 138 }
150 nextarg.cube = move(arg->cube, m);
151 nextarg.inverse = premove(arg->inverse, m);
152 ret += solve_h48_dfs(&nextarg);
153 } 139 }
154 } 140 }
155 141
@@ -192,6 +178,7 @@ solve_h48(
192 LOG("Found %" PRId64 " solutions, searching at depth %" 178 LOG("Found %" PRId64 " solutions, searching at depth %"
193 PRId8 "\n", nsols, arg.depth); 179 PRId8 "\n", nsols, arg.depth);
194 arg.nmoves = 0; 180 arg.nmoves = 0;
181 arg.npremoves = 0;
195 solve_h48_dfs(&arg); 182 solve_h48_dfs(&arg);
196 } 183 }
197 184

Generated with cgit - Back to sebastiano.tronto.net