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

constants.h (11382B)


      1 #define UINT8_BIT(i) (UINT8_C(1) << (uint8_t)(i))
      2 
      3 #define FACTORIAL_MAX INT64_C(12)
      4 
      5 #define POW_2_11   INT64_C(2048)
      6 #define POW_3_7    INT64_C(2187)
      7 #define FACT_12    INT64_C(479001600)
      8 #define FACT_8     INT64_C(40320)
      9 #define COMB_12_4  INT64_C(495)
     10 #define COMB_8_4   INT64_C(70)
     11 
     12 STATIC int64_t binomial[12][12] = {
     13 	{1,  0,  0,   0,   0,   0,   0,   0,   0,  0,  0, 0},
     14 	{1,  1,  0,   0,   0,   0,   0,   0,   0,  0,  0, 0},
     15 	{1,  2,  1,   0,   0,   0,   0,   0,   0,  0,  0, 0},
     16 	{1,  3,  3,   1,   0,   0,   0,   0,   0,  0,  0, 0},
     17 	{1,  4,  6,   4,   1,   0,   0,   0,   0,  0,  0, 0},
     18 	{1,  5, 10,  10,   5,   1,   0,   0,   0,  0,  0, 0},
     19 	{1,  6, 15,  20,  15,   6,   1,   0,   0,  0,  0, 0},
     20 	{1,  7, 21,  35,  35,  21,   7,   1,   0,  0,  0, 0},
     21 	{1,  8, 28,  56,  70,  56,  28,   8,   1,  0,  0, 0},
     22 	{1,  9, 36,  84, 126, 126,  84,  36,   9,  1,  0, 0},
     23 	{1, 10, 45, 120, 210, 252, 210, 120,  45, 10,  1, 0},
     24 	{1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
     25 };
     26 
     27 #define MOVE_U  UINT8_C(0)
     28 #define MOVE_U2 UINT8_C(1)
     29 #define MOVE_U3 UINT8_C(2)
     30 #define MOVE_D  UINT8_C(3)
     31 #define MOVE_D2 UINT8_C(4)
     32 #define MOVE_D3 UINT8_C(5)
     33 #define MOVE_R  UINT8_C(6)
     34 #define MOVE_R2 UINT8_C(7)
     35 #define MOVE_R3 UINT8_C(8)
     36 #define MOVE_L  UINT8_C(9)
     37 #define MOVE_L2 UINT8_C(10)
     38 #define MOVE_L3 UINT8_C(11)
     39 #define MOVE_F  UINT8_C(12)
     40 #define MOVE_F2 UINT8_C(13)
     41 #define MOVE_F3 UINT8_C(14)
     42 #define MOVE_B  UINT8_C(15)
     43 #define MOVE_B2 UINT8_C(16)
     44 #define MOVE_B3 UINT8_C(17)
     45 
     46 #define TRANS_UFr UINT8_C(0)
     47 #define TRANS_ULr UINT8_C(1)
     48 #define TRANS_UBr UINT8_C(2)
     49 #define TRANS_URr UINT8_C(3)
     50 #define TRANS_DFr UINT8_C(4)
     51 #define TRANS_DLr UINT8_C(5)
     52 #define TRANS_DBr UINT8_C(6)
     53 #define TRANS_DRr UINT8_C(7)
     54 #define TRANS_RUr UINT8_C(8)
     55 #define TRANS_RFr UINT8_C(9)
     56 #define TRANS_RDr UINT8_C(10)
     57 #define TRANS_RBr UINT8_C(11)
     58 #define TRANS_LUr UINT8_C(12)
     59 #define TRANS_LFr UINT8_C(13)
     60 #define TRANS_LDr UINT8_C(14)
     61 #define TRANS_LBr UINT8_C(15)
     62 #define TRANS_FUr UINT8_C(16)
     63 #define TRANS_FRr UINT8_C(17)
     64 #define TRANS_FDr UINT8_C(18)
     65 #define TRANS_FLr UINT8_C(19)
     66 #define TRANS_BUr UINT8_C(20)
     67 #define TRANS_BRr UINT8_C(21)
     68 #define TRANS_BDr UINT8_C(22)
     69 #define TRANS_BLr UINT8_C(23)
     70 
     71 #define TRANS_UFm UINT8_C(24)
     72 #define TRANS_ULm UINT8_C(25)
     73 #define TRANS_UBm UINT8_C(26)
     74 #define TRANS_URm UINT8_C(27)
     75 #define TRANS_DFm UINT8_C(28)
     76 #define TRANS_DLm UINT8_C(29)
     77 #define TRANS_DBm UINT8_C(30)
     78 #define TRANS_DRm UINT8_C(31)
     79 #define TRANS_RUm UINT8_C(32)
     80 #define TRANS_RFm UINT8_C(33)
     81 #define TRANS_RDm UINT8_C(34)
     82 #define TRANS_RBm UINT8_C(35)
     83 #define TRANS_LUm UINT8_C(36)
     84 #define TRANS_LFm UINT8_C(37)
     85 #define TRANS_LDm UINT8_C(38)
     86 #define TRANS_LBm UINT8_C(39)
     87 #define TRANS_FUm UINT8_C(40)
     88 #define TRANS_FRm UINT8_C(41)
     89 #define TRANS_FDm UINT8_C(42)
     90 #define TRANS_FLm UINT8_C(43)
     91 #define TRANS_BUm UINT8_C(44)
     92 #define TRANS_BRm UINT8_C(45)
     93 #define TRANS_BDm UINT8_C(46)
     94 #define TRANS_BLm UINT8_C(47)
     95 
     96 #define AXIS_UD   UINT8_C(0)
     97 #define AXIS_RL   UINT8_C(1)
     98 #define AXIS_FB   UINT8_C(2)
     99 
    100 #define NMOVES  (1+MOVE_B3)
    101 #define NTRANS  (1+TRANS_BLm)
    102 
    103 #define MM_ALLMOVES    UINT32_C(0x3FFFF)
    104 #define MM_NOHALFTURNS UINT32_C(0x2DB6D)
    105 #define MM_SINGLE(m)   (UINT32_C(1) << (uint32_t)(m))
    106 #define MM_FACE(m)     (UINT32_C(7) << (uint32_t)(m))
    107 #define MM_EO          (\
    108     MM_FACE(MOVE_U) | MM_FACE(MOVE_D) |\
    109     MM_FACE(MOVE_R) | MM_FACE(MOVE_L) |\
    110     MM_SINGLE(MOVE_F2) | MM_SINGLE(MOVE_B2))
    111 #define MM_DR          (\
    112     MM_FACE(MOVE_U) | MM_FACE(MOVE_D) |\
    113     MM_SINGLE(MOVE_R2) | MM_SINGLE(MOVE_L2) |\
    114     MM_SINGLE(MOVE_F2) | MM_SINGLE(MOVE_B2))
    115 #define MM_HTR (MM_ALLMOVES & ~MM_NOHALFTURNS)
    116 
    117 #define TM_ALLTRANS    UINT64_C(0xFFFFFFFFFFFF)
    118 #define TM_SINGLE(t)   (UINT64_C(1) << (uint64_t)(t))
    119 #define TM_UDFIX       (\
    120     TM_SINGLE(TRANS_UFr) | TM_SINGLE(TRANS_UBr) | TM_SINGLE(TRANS_URr) | \
    121     TM_SINGLE(TRANS_ULr) | TM_SINGLE(TRANS_UFm) | TM_SINGLE(TRANS_UBm) | \
    122     TM_SINGLE(TRANS_URm) | TM_SINGLE(TRANS_ULm) | TM_SINGLE(TRANS_DFr) | \
    123     TM_SINGLE(TRANS_DBr) | TM_SINGLE(TRANS_DRr) | TM_SINGLE(TRANS_DLr) | \
    124     TM_SINGLE(TRANS_DFm) | TM_SINGLE(TRANS_DBm) | TM_SINGLE(TRANS_DRm) | \
    125     TM_SINGLE(TRANS_DLm))
    126 
    127 #define CORNER_UFR      UINT8_C(0)
    128 #define CORNER_UBL      UINT8_C(1)
    129 #define CORNER_DFL      UINT8_C(2)
    130 #define CORNER_DBR      UINT8_C(3)
    131 #define CORNER_UFL      UINT8_C(4)
    132 #define CORNER_UBR      UINT8_C(5)
    133 #define CORNER_DFR      UINT8_C(6)
    134 #define CORNER_DBL      UINT8_C(7)
    135 
    136 #define EDGE_UF       UINT8_C(0)
    137 #define EDGE_UB       UINT8_C(1)
    138 #define EDGE_DB       UINT8_C(2)
    139 #define EDGE_DF       UINT8_C(3)
    140 #define EDGE_UR       UINT8_C(4)
    141 #define EDGE_UL       UINT8_C(5)
    142 #define EDGE_DL       UINT8_C(6)
    143 #define EDGE_DR       UINT8_C(7)
    144 #define EDGE_FR       UINT8_C(8)
    145 #define EDGE_FL       UINT8_C(9)
    146 #define EDGE_BL       UINT8_C(10)
    147 #define EDGE_BR       UINT8_C(11)
    148 
    149 #define EOSHIFT     UINT8_C(4)
    150 #define COSHIFT     UINT8_C(5)
    151 
    152 #define PBITS       UINT8_C(0xF)
    153 #define ESEPBIT_1   UINT8_C(0x4)
    154 #define ESEPBIT_2   UINT8_C(0x8)
    155 #define CSEPBIT     UINT8_C(0x4)
    156 #define EOBIT       UINT8_C(0x10)
    157 #define COBITS      UINT8_C(0xF0)
    158 #define COBITS_2    UINT8_C(0x60)
    159 #define CTWIST_CW   UINT8_C(0x20)
    160 #define CTWIST_CCW  UINT8_C(0x40)
    161 #define EFLIP       UINT8_C(0x10)
    162 #define UINT8_ERROR UINT8_MAX
    163 
    164 STATIC const uint32_t allowedmask[] = {
    165 	UINT32_C(0x3FFF8),
    166 	UINT32_C(0x3FFC0),
    167 	UINT32_C(0x3FE3F),
    168 	UINT32_C(0x3F03F),
    169 	UINT32_C(0x38FFF),
    170 	UINT32_C(0x00FFF)
    171 };
    172 
    173 STATIC const char *cornerstr[] = {
    174 	[CORNER_UFR] = "UFR",
    175 	[CORNER_UBL] = "UBL",
    176 	[CORNER_DFL] = "DFL",
    177 	[CORNER_DBR] = "DBR",
    178 	[CORNER_UFL] = "UFL",
    179 	[CORNER_UBR] = "UBR",
    180 	[CORNER_DFR] = "DFR",
    181 	[CORNER_DBL] = "DBL"
    182 };
    183 
    184 STATIC const char *cornerstralt[] = {
    185 	[CORNER_UFR] = "URF",
    186 	[CORNER_UBL] = "ULB",
    187 	[CORNER_DFL] = "DLF",
    188 	[CORNER_DBR] = "DRB",
    189 	[CORNER_UFL] = "ULF",
    190 	[CORNER_UBR] = "URB",
    191 	[CORNER_DFR] = "DRF",
    192 	[CORNER_DBL] = "DLB"
    193 };
    194 
    195 STATIC const char *edgestr[] = {
    196 	[EDGE_UF] = "UF",
    197 	[EDGE_UB] = "UB",
    198 	[EDGE_DB] = "DB",
    199 	[EDGE_DF] = "DF",
    200 	[EDGE_UR] = "UR",
    201 	[EDGE_UL] = "UL",
    202 	[EDGE_DL] = "DL",
    203 	[EDGE_DR] = "DR",
    204 	[EDGE_FR] = "FR",
    205 	[EDGE_FL] = "FL",
    206 	[EDGE_BL] = "BL",
    207 	[EDGE_BR] = "BR"
    208 };
    209 
    210 STATIC const char *movestr[] = {
    211 	[MOVE_U]  = "U",
    212 	[MOVE_U2] = "U2",
    213 	[MOVE_U3] = "U'",
    214 	[MOVE_D]  = "D",
    215 	[MOVE_D2] = "D2",
    216 	[MOVE_D3] = "D'",
    217 	[MOVE_R]  = "R",
    218 	[MOVE_R2] = "R2",
    219 	[MOVE_R3] = "R'",
    220 	[MOVE_L]  = "L",
    221 	[MOVE_L2] = "L2",
    222 	[MOVE_L3] = "L'",
    223 	[MOVE_F]  = "F",
    224 	[MOVE_F2] = "F2",
    225 	[MOVE_F3] = "F'",
    226 	[MOVE_B]  = "B",
    227 	[MOVE_B2] = "B2",
    228 	[MOVE_B3] = "B'",
    229 };
    230 
    231 STATIC const char *transstr[] = {
    232 	[TRANS_UFr] = "rotation UF",
    233 	[TRANS_UFm] = "mirrored UF",
    234 	[TRANS_ULr] = "rotation UL",
    235 	[TRANS_ULm] = "mirrored UL",
    236 	[TRANS_UBr] = "rotation UB",
    237 	[TRANS_UBm] = "mirrored UB",
    238 	[TRANS_URr] = "rotation UR",
    239 	[TRANS_URm] = "mirrored UR",
    240 	[TRANS_DFr] = "rotation DF",
    241 	[TRANS_DFm] = "mirrored DF",
    242 	[TRANS_DLr] = "rotation DL",
    243 	[TRANS_DLm] = "mirrored DL",
    244 	[TRANS_DBr] = "rotation DB",
    245 	[TRANS_DBm] = "mirrored DB",
    246 	[TRANS_DRr] = "rotation DR",
    247 	[TRANS_DRm] = "mirrored DR",
    248 	[TRANS_RUr] = "rotation RU",
    249 	[TRANS_RUm] = "mirrored RU",
    250 	[TRANS_RFr] = "rotation RF",
    251 	[TRANS_RFm] = "mirrored RF",
    252 	[TRANS_RDr] = "rotation RD",
    253 	[TRANS_RDm] = "mirrored RD",
    254 	[TRANS_RBr] = "rotation RB",
    255 	[TRANS_RBm] = "mirrored RB",
    256 	[TRANS_LUr] = "rotation LU",
    257 	[TRANS_LUm] = "mirrored LU",
    258 	[TRANS_LFr] = "rotation LF",
    259 	[TRANS_LFm] = "mirrored LF",
    260 	[TRANS_LDr] = "rotation LD",
    261 	[TRANS_LDm] = "mirrored LD",
    262 	[TRANS_LBr] = "rotation LB",
    263 	[TRANS_LBm] = "mirrored LB",
    264 	[TRANS_FUr] = "rotation FU",
    265 	[TRANS_FUm] = "mirrored FU",
    266 	[TRANS_FRr] = "rotation FR",
    267 	[TRANS_FRm] = "mirrored FR",
    268 	[TRANS_FDr] = "rotation FD",
    269 	[TRANS_FDm] = "mirrored FD",
    270 	[TRANS_FLr] = "rotation FL",
    271 	[TRANS_FLm] = "mirrored FL",
    272 	[TRANS_BUr] = "rotation BU",
    273 	[TRANS_BUm] = "mirrored BU",
    274 	[TRANS_BRr] = "rotation BR",
    275 	[TRANS_BRm] = "mirrored BR",
    276 	[TRANS_BDr] = "rotation BD",
    277 	[TRANS_BDm] = "mirrored BD",
    278 	[TRANS_BLr] = "rotation BL",
    279 	[TRANS_BLm] = "mirrored BL",
    280 };
    281 
    282 static uint8_t inverse_trans_table[48] = {
    283 	[TRANS_UFr] = TRANS_UFr,
    284 	[TRANS_UFm] = TRANS_UFm,
    285 	[TRANS_ULr] = TRANS_URr,
    286 	[TRANS_ULm] = TRANS_ULm,
    287 	[TRANS_UBr] = TRANS_UBr,
    288 	[TRANS_UBm] = TRANS_UBm,
    289 	[TRANS_URr] = TRANS_ULr,
    290 	[TRANS_URm] = TRANS_URm,
    291 	[TRANS_DFr] = TRANS_DFr,
    292 	[TRANS_DFm] = TRANS_DFm,
    293 	[TRANS_DLr] = TRANS_DLr,
    294 	[TRANS_DLm] = TRANS_DRm,
    295 	[TRANS_DBr] = TRANS_DBr,
    296 	[TRANS_DBm] = TRANS_DBm,
    297 	[TRANS_DRr] = TRANS_DRr,
    298 	[TRANS_DRm] = TRANS_DLm,
    299 	[TRANS_RUr] = TRANS_FRr,
    300 	[TRANS_RUm] = TRANS_FLm,
    301 	[TRANS_RFr] = TRANS_LFr,
    302 	[TRANS_RFm] = TRANS_RFm,
    303 	[TRANS_RDr] = TRANS_BLr,
    304 	[TRANS_RDm] = TRANS_BRm,
    305 	[TRANS_RBr] = TRANS_RBr,
    306 	[TRANS_RBm] = TRANS_LBm,
    307 	[TRANS_LUr] = TRANS_FLr,
    308 	[TRANS_LUm] = TRANS_FRm,
    309 	[TRANS_LFr] = TRANS_RFr,
    310 	[TRANS_LFm] = TRANS_LFm,
    311 	[TRANS_LDr] = TRANS_BRr,
    312 	[TRANS_LDm] = TRANS_BLm,
    313 	[TRANS_LBr] = TRANS_LBr,
    314 	[TRANS_LBm] = TRANS_RBm,
    315 	[TRANS_FUr] = TRANS_FUr,
    316 	[TRANS_FUm] = TRANS_FUm,
    317 	[TRANS_FRr] = TRANS_RUr,
    318 	[TRANS_FRm] = TRANS_LUm,
    319 	[TRANS_FDr] = TRANS_BUr,
    320 	[TRANS_FDm] = TRANS_BUm,
    321 	[TRANS_FLr] = TRANS_LUr,
    322 	[TRANS_FLm] = TRANS_RUm,
    323 	[TRANS_BUr] = TRANS_FDr,
    324 	[TRANS_BUm] = TRANS_FDm,
    325 	[TRANS_BRr] = TRANS_LDr,
    326 	[TRANS_BRm] = TRANS_RDm,
    327 	[TRANS_BDr] = TRANS_BDr,
    328 	[TRANS_BDm] = TRANS_BDm,
    329 	[TRANS_BLr] = TRANS_RDr,
    330 	[TRANS_BLm] = TRANS_LDm,
    331 };
    332 
    333 static uint8_t trans_move_table[48][3] = {
    334 	[TRANS_UFr] = { MOVE_U, MOVE_R, MOVE_F },
    335 	[TRANS_UFm] = { MOVE_U, MOVE_L, MOVE_F },
    336 	[TRANS_ULr] = { MOVE_U, MOVE_F, MOVE_L },
    337 	[TRANS_ULm] = { MOVE_U, MOVE_F, MOVE_R },
    338 	[TRANS_UBr] = { MOVE_U, MOVE_L, MOVE_B },
    339 	[TRANS_UBm] = { MOVE_U, MOVE_R, MOVE_B },
    340 	[TRANS_URr] = { MOVE_U, MOVE_B, MOVE_R },
    341 	[TRANS_URm] = { MOVE_U, MOVE_B, MOVE_L },
    342 	[TRANS_DFr] = { MOVE_D, MOVE_L, MOVE_F },
    343 	[TRANS_DFm] = { MOVE_D, MOVE_R, MOVE_F },
    344 	[TRANS_DLr] = { MOVE_D, MOVE_B, MOVE_L },
    345 	[TRANS_DLm] = { MOVE_D, MOVE_B, MOVE_R },
    346 	[TRANS_DBr] = { MOVE_D, MOVE_R, MOVE_B },
    347 	[TRANS_DBm] = { MOVE_D, MOVE_L, MOVE_B },
    348 	[TRANS_DRr] = { MOVE_D, MOVE_F, MOVE_R },
    349 	[TRANS_DRm] = { MOVE_D, MOVE_F, MOVE_L },
    350 	[TRANS_RUr] = { MOVE_R, MOVE_F, MOVE_U },
    351 	[TRANS_RUm] = { MOVE_L, MOVE_F, MOVE_U },
    352 	[TRANS_RFr] = { MOVE_R, MOVE_D, MOVE_F },
    353 	[TRANS_RFm] = { MOVE_L, MOVE_D, MOVE_F },
    354 	[TRANS_RDr] = { MOVE_R, MOVE_B, MOVE_D },
    355 	[TRANS_RDm] = { MOVE_L, MOVE_B, MOVE_D },
    356 	[TRANS_RBr] = { MOVE_R, MOVE_U, MOVE_B },
    357 	[TRANS_RBm] = { MOVE_L, MOVE_U, MOVE_B },
    358 	[TRANS_LUr] = { MOVE_L, MOVE_B, MOVE_U },
    359 	[TRANS_LUm] = { MOVE_R, MOVE_B, MOVE_U },
    360 	[TRANS_LFr] = { MOVE_L, MOVE_U, MOVE_F },
    361 	[TRANS_LFm] = { MOVE_R, MOVE_U, MOVE_F },
    362 	[TRANS_LDr] = { MOVE_L, MOVE_F, MOVE_D },
    363 	[TRANS_LDm] = { MOVE_R, MOVE_F, MOVE_D },
    364 	[TRANS_LBr] = { MOVE_L, MOVE_D, MOVE_B },
    365 	[TRANS_LBm] = { MOVE_R, MOVE_D, MOVE_B },
    366 	[TRANS_FUr] = { MOVE_F, MOVE_L, MOVE_U },
    367 	[TRANS_FUm] = { MOVE_F, MOVE_R, MOVE_U },
    368 	[TRANS_FRr] = { MOVE_F, MOVE_U, MOVE_R },
    369 	[TRANS_FRm] = { MOVE_F, MOVE_U, MOVE_L },
    370 	[TRANS_FDr] = { MOVE_F, MOVE_R, MOVE_D },
    371 	[TRANS_FDm] = { MOVE_F, MOVE_L, MOVE_D },
    372 	[TRANS_FLr] = { MOVE_F, MOVE_D, MOVE_L },
    373 	[TRANS_FLm] = { MOVE_F, MOVE_D, MOVE_R },
    374 	[TRANS_BUr] = { MOVE_B, MOVE_R, MOVE_U },
    375 	[TRANS_BUm] = { MOVE_B, MOVE_L, MOVE_U },
    376 	[TRANS_BRr] = { MOVE_B, MOVE_D, MOVE_R },
    377 	[TRANS_BRm] = { MOVE_B, MOVE_D, MOVE_L },
    378 	[TRANS_BDr] = { MOVE_B, MOVE_L, MOVE_D },
    379 	[TRANS_BDm] = { MOVE_B, MOVE_R, MOVE_D },
    380 	[TRANS_BLr] = { MOVE_B, MOVE_U, MOVE_L },
    381 	[TRANS_BLm] = { MOVE_B, MOVE_U, MOVE_R },
    382 };