h48

A prototype for an optimal Rubik's cube solver, work in progress.
git clone https://git.tronto.net/h48
Download | Log | Files | Refs | README | LICENSE

moves.h (4535B)


      1 #define MOVE(M, c) compose(c, MOVE_CUBE_ ## M)
      2 #define PREMOVE(M, c) compose(MOVE_CUBE_ ## M, c)
      3 
      4 STATIC_INLINE bool allowednextmove(uint8_t, uint8_t);
      5 STATIC bool allowedmoves(size_t n, const uint8_t [n]);
      6 
      7 STATIC_INLINE uint8_t movebase(uint8_t);
      8 STATIC_INLINE uint8_t moveaxis(uint8_t);
      9 STATIC_INLINE bool isbase(uint8_t);
     10 STATIC_INLINE bool parallel(uint8_t, uint8_t);
     11 
     12 STATIC cube_t move(cube_t, uint8_t);
     13 STATIC cube_t premove(cube_t, uint8_t);
     14 STATIC uint8_t inverse_move(uint8_t);
     15 STATIC void sortparallel_moves(size_t n, uint8_t [n]);
     16 STATIC bool are_lastmoves_singlecw(size_t n, const uint8_t [n]);
     17 
     18 STATIC cube_t applymoves(cube_t, const char *);
     19 
     20 #define FOREACH_READMOVE(ARG_BUF, ARG_MOVE, ARG_C, ARG_MAX, \
     21 	RET_ERROR, ARG_ACTION) \
     22 	const char *VAR_B; \
     23 	uint8_t VAR_MOVE_NOMOD, VAR_MOD; \
     24 	for (VAR_B = ARG_BUF, ARG_C = 0; *VAR_B != '\0'; VAR_B++, ARG_C++) { \
     25 		while (*VAR_B == ' ' || *VAR_B == '\t' || *VAR_B == '\n') \
     26 			VAR_B++; \
     27 		if (*VAR_B == '\0' || ARG_C == ARG_MAX) \
     28 			break; \
     29 		if ((VAR_MOVE_NOMOD = readmove(*VAR_B)) == UINT8_ERROR) { \
     30 			LOG("Error: unknown move '%c'\n", *VAR_B); \
     31 			return RET_ERROR; \
     32 		} \
     33 		if ((VAR_MOD = readmodifier(*(VAR_B+1))) != 0) \
     34 			VAR_B++; \
     35 		ARG_MOVE = VAR_MOVE_NOMOD + VAR_MOD; \
     36 		ARG_ACTION \
     37 	}
     38 
     39 STATIC_INLINE bool
     40 allowednextmove(uint8_t m1, uint8_t m2)
     41 {
     42 	return allowedmask[movebase(m1)] & (UINT32_C(1) << m2);
     43 }
     44 
     45 STATIC bool
     46 allowedmoves(size_t n, const uint8_t m[n])
     47 {
     48 	uint8_t j;
     49 
     50 	for (j = 1; j < n; j++)
     51 		if (!allowednextmove(m[j-1], m[j]))
     52 			return false;
     53 
     54 	return true;
     55 }
     56 
     57 STATIC_INLINE uint8_t
     58 movebase(uint8_t move)
     59 {
     60 	return move / 3;
     61 }
     62 
     63 STATIC_INLINE uint8_t
     64 moveaxis(uint8_t move)
     65 {
     66 	return move / 6;
     67 }
     68 
     69 STATIC_INLINE bool
     70 isbase(uint8_t move)
     71 {
     72 	return move == 3 * movebase(move);
     73 }
     74 
     75 STATIC_INLINE bool
     76 parallel(uint8_t m1, uint8_t m2)
     77 {
     78 	return moveaxis(m1) == moveaxis(m2);
     79 }
     80 
     81 STATIC_INLINE uint8_t
     82 moveopposite(uint8_t move)
     83 {
     84 	return movebase(move) == 2 * moveaxis(move) ? move + 3 : move - 3;
     85 }
     86 
     87 STATIC cube_t
     88 move(cube_t c, uint8_t m)
     89 {
     90 	switch (m) {
     91 	case MOVE_U:
     92 		return MOVE(U, c);
     93 	case MOVE_U2:
     94 		return MOVE(U2, c);
     95 	case MOVE_U3:
     96 		return MOVE(U3, c);
     97 	case MOVE_D:
     98 		return MOVE(D, c);
     99 	case MOVE_D2:
    100 		return MOVE(D2, c);
    101 	case MOVE_D3:
    102 		return MOVE(D3, c);
    103 	case MOVE_R:
    104 		return MOVE(R, c);
    105 	case MOVE_R2:
    106 		return MOVE(R2, c);
    107 	case MOVE_R3:
    108 		return MOVE(R3, c);
    109 	case MOVE_L:
    110 		return MOVE(L, c);
    111 	case MOVE_L2:
    112 		return MOVE(L2, c);
    113 	case MOVE_L3:
    114 		return MOVE(L3, c);
    115 	case MOVE_F:
    116 		return MOVE(F, c);
    117 	case MOVE_F2:
    118 		return MOVE(F2, c);
    119 	case MOVE_F3:
    120 		return MOVE(F3, c);
    121 	case MOVE_B:
    122 		return MOVE(B, c);
    123 	case MOVE_B2:
    124 		return MOVE(B2, c);
    125 	case MOVE_B3:
    126 		return MOVE(B3, c);
    127 	default:
    128 		LOG("move error: unknown move %" PRIu8 "\n", m);
    129 		return ZERO_CUBE;
    130 	}
    131 }
    132 
    133 /* Applies the INVERSE of m BEFORE the scramble corresponding to c */
    134 STATIC cube_t
    135 premove(cube_t c, uint8_t m)
    136 {
    137 	switch (m) {
    138 	case MOVE_U:
    139 		return PREMOVE(U3, c);
    140 	case MOVE_U2:
    141 		return PREMOVE(U2, c);
    142 	case MOVE_U3:
    143 		return PREMOVE(U, c);
    144 	case MOVE_D:
    145 		return PREMOVE(D3, c);
    146 	case MOVE_D2:
    147 		return PREMOVE(D2, c);
    148 	case MOVE_D3:
    149 		return PREMOVE(D, c);
    150 	case MOVE_R:
    151 		return PREMOVE(R3, c);
    152 	case MOVE_R2:
    153 		return PREMOVE(R2, c);
    154 	case MOVE_R3:
    155 		return PREMOVE(R, c);
    156 	case MOVE_L:
    157 		return PREMOVE(L3, c);
    158 	case MOVE_L2:
    159 		return PREMOVE(L2, c);
    160 	case MOVE_L3:
    161 		return PREMOVE(L, c);
    162 	case MOVE_F:
    163 		return PREMOVE(F3, c);
    164 	case MOVE_F2:
    165 		return PREMOVE(F2, c);
    166 	case MOVE_F3:
    167 		return PREMOVE(F, c);
    168 	case MOVE_B:
    169 		return PREMOVE(B3, c);
    170 	case MOVE_B2:
    171 		return PREMOVE(B2, c);
    172 	case MOVE_B3:
    173 		return PREMOVE(B, c);
    174 	default:
    175 		LOG("premove error: unknown move %" PRIu8 "\n", m);
    176 		return ZERO_CUBE;
    177 	}
    178 }
    179 
    180 STATIC uint8_t
    181 inverse_move(uint8_t m)
    182 {
    183 	return m - 2 * (m % 3) + 2;	
    184 }
    185 
    186 STATIC void
    187 sortparallel_moves(size_t n, uint8_t moves[n])
    188 {
    189 	uint8_t i;
    190 
    191 	if (n < 2)
    192 		return;
    193 
    194 	for (i = 0; i < n-1; i++)
    195 		if (moveaxis(moves[i]) == moveaxis(moves[i+1]) &&
    196 		    movebase(moves[i]) == movebase(moves[i+1]) + 1)
    197 			SWAP(moves[i], moves[i+1]);
    198 }
    199 
    200 STATIC bool
    201 are_lastmoves_singlecw(size_t n, const uint8_t moves[n])
    202 {
    203 	bool two;
    204 
    205 	if (n == 0)
    206 		return true;
    207 
    208 	two = n > 1 && parallel(moves[n-1], moves[n-2]);
    209 
    210 	return isbase(moves[n-1]) && (!two || isbase(moves[n-2]));
    211 }
    212 
    213 STATIC cube_t
    214 applymoves(cube_t cube, const char *buf)
    215 {
    216 	int c;
    217 	uint8_t m;
    218 
    219 	DBG_ASSERT(isconsistent(cube), ZERO_CUBE,
    220 	    "move error: inconsistent cube\n");
    221 
    222 	FOREACH_READMOVE(buf, m, c, -1, ZERO_CUBE,
    223 		cube = move(cube, m);
    224 	)
    225 
    226 	return cube;
    227 }