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

cube.h (3923B)


      1 STATIC cube_t solvedcube(void);
      2 STATIC cube_t cubefromarray(uint8_t [static 8], uint8_t [static 12]);
      3 STATIC bool isconsistent(cube_t);
      4 STATIC bool issolvable(cube_t);
      5 STATIC bool issolved(cube_t);
      6 STATIC bool iserror(cube_t);
      7 STATIC void getcube_fix(long long *, long long *, long long *, long long *);
      8 STATIC cube_t getcube(int64_t, int64_t, int64_t, int64_t);
      9 
     10 /* This is used only in tests, use SOLVED_CUBE directly everywhere else */
     11 STATIC cube_t
     12 solvedcube(void)
     13 {
     14 	return SOLVED_CUBE;
     15 }
     16 
     17 STATIC cube_t
     18 cubefromarray(uint8_t c[static 8], uint8_t e[static 12])
     19 {
     20 	return STATIC_CUBE(
     21 	    c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7],
     22 	    e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7],
     23 	    e[8], e[9], e[10], e[11]);
     24 }
     25 
     26 STATIC bool
     27 isconsistent(cube_t cube)
     28 {
     29 	uint8_t i, p, e, piece, corner[8], edge[12];
     30 	bool found[12];
     31 
     32 	pieces(&cube, corner, edge);
     33 
     34 	for (i = 0; i < 12; i++)
     35 		found[i] = false;
     36 	for (i = 0; i < 12; i++) {
     37 		piece = edge[i];
     38 		p = piece & PBITS;
     39 		e = piece & EOBIT;
     40 		if (p >= 12)
     41 			goto inconsistent_ep;
     42 		if (e != 0 && e != EOBIT)
     43 			goto inconsistent_eo;
     44 		found[p] = true;
     45 	}
     46 	for (i = 0; i < 12; i++)
     47 		if (!found[i])
     48 			goto inconsistent_ep;
     49 
     50 	for (i = 0; i < 8; i++)
     51 		found[i] = false;
     52 	for (i = 0; i < 8; i++) {
     53 		piece = corner[i];
     54 		p = piece & PBITS;
     55 		e = piece & COBITS;
     56 		if (p >= 8)
     57 			goto inconsistent_cp;
     58 		if (e != 0 && e != CTWIST_CW && e != CTWIST_CCW)
     59 			goto inconsistent_co;
     60 		found[p] = true;
     61 	}
     62 	for (i = 0; i < 8; i++)
     63 		if (!found[i])
     64 			goto inconsistent_cp;
     65 
     66 	return true;
     67 
     68 inconsistent_ep:
     69 inconsistent_cp:
     70 inconsistent_eo:
     71 inconsistent_co:
     72 	/* We used to do more logging here, hence the 4 different labels */
     73 	return false;
     74 }
     75 
     76 STATIC bool
     77 issolvable(cube_t cube)
     78 {
     79 	uint8_t i, eo, co, piece, edge[12], corner[8], ep[12], cp[8];
     80 
     81 	DBG_ASSERT(isconsistent(cube), false,
     82 	    "issolvable: cube is inconsistent\n");
     83 
     84 	pieces(&cube, corner, edge);
     85 	for (i = 0; i < 12; i++)
     86 		ep[i] = edge[i] & PBITS;
     87 	for (i = 0; i < 8; i++)
     88 		cp[i] = corner[i] & PBITS;
     89 
     90 	if (permsign(12, ep) != permsign(8, cp))
     91 		goto issolvable_parity;
     92 
     93 	eo = 0;
     94 	for (i = 0; i < 12; i++) {
     95 		piece = edge[i];
     96 		eo += (piece & EOBIT) >> EOSHIFT;
     97 	}
     98 	if (eo % 2 != 0)
     99 		goto issolvable_eo;
    100 
    101 	co = 0;
    102 	for (i = 0; i < 8; i++) {
    103 		piece = corner[i];
    104 		co += (piece & COBITS) >> COSHIFT;
    105 	}
    106 	if (co % 3 != 0)
    107 		goto issolvable_co;
    108 
    109 	return true;
    110 
    111 issolvable_parity:
    112 	LOG("There is parity\n");
    113 	return false;
    114 issolvable_eo:
    115 	LOG("EO is not solvable\n");
    116 	return false;
    117 issolvable_co:
    118 	LOG("CO is not solvable\n");
    119 	return false;
    120 }
    121 
    122 bool
    123 issolved(cube_t cube)
    124 {
    125 	return equal(cube, SOLVED_CUBE);
    126 }
    127 
    128 bool
    129 iserror(cube_t cube)
    130 {
    131 	return equal(cube, ZERO_CUBE);
    132 }
    133 
    134 STATIC void
    135 getcube_fix(long long *ep, long long *eo, long long *cp, long long *co)
    136 {
    137 	uint8_t e[12], c[8], coarr[8];
    138 
    139         *ep = (*ep % FACT_12 + FACT_12) % FACT_12;
    140 	*eo = (*eo % POW_2_11 + POW_2_11) % POW_2_11;
    141 	*cp = (*cp % FACT_8 + FACT_8) % FACT_8;
    142 	*co = (*cp % POW_3_7 + POW_3_7) % POW_3_7;
    143 
    144 	indextoperm(*ep, 12, e);
    145 	indextoperm(*cp, 8, c);
    146 	if (permsign(12, e) != permsign(8, c)) {
    147 		SWAP(c[0], c[1]);
    148 		*cp = permtoindex(8, c);
    149 
    150 		sumzerotodigits(*co, 8, 3, coarr);
    151 		SWAP(coarr[0], coarr[1]);
    152 		*co = digitstosumzero(8, coarr, 3);
    153 	}
    154 }
    155 
    156 STATIC cube_t
    157 getcube(int64_t ep, int64_t eo, int64_t cp, int64_t co)
    158 {
    159 	uint8_t i, earr[12], carr[8], eoarr[12], coarr[8];
    160 
    161 	sumzerotodigits(eo, 12, 2, eoarr);
    162 	DBG_ASSERT(eoarr[0] != UINT8_ERROR, ZERO_CUBE, "Error making EO");
    163 	indextoperm(ep, 12, earr);
    164 	DBG_ASSERT(earr[0] != UINT8_ERROR, ZERO_CUBE, "Error making EP");
    165 	for (i = 0; i < 12; i++)
    166 		earr[i] |= eoarr[i] << EOSHIFT;
    167 
    168 	sumzerotodigits(co, 8, 3, coarr);
    169 	DBG_ASSERT(coarr[0] != UINT8_ERROR, ZERO_CUBE, "Error making CO");
    170 	indextoperm(cp, 8, carr);
    171 	DBG_ASSERT(carr[0] != UINT8_ERROR, ZERO_CUBE, "Error making CP");
    172 	for (i = 0; i < 8; i++)
    173 		carr[i] |= coarr[i] << COSHIFT;
    174 
    175 	return cubefromarray(carr, earr);
    176 }