nissy-nx

A Rubik's cube optimal solver
git clone https://git.tronto.net/nissy-nx
Download | Log | Files | Refs | README | LICENSE

solver_nxopt31.c (6029B)


      1 #include "solver_nxopt31.h"
      2 
      3 /* TODO: make generic for nxopt solvers */
      4 
      5 static void             apply_move_fst(void *, void *, Move);
      6 static void *           prepare_cube_fst(void *, Cube *);
      7 static bool             move_check_stop_nxopt31(void *, DfsArg *, Threader *);
      8 static bool             is_solved_fst(void *, void *);
      9 static void *           alloc_cubedata_fst(void *);
     10 static void             copy_cubedata_fst(void *, void *, void *);
     11 static void             free_cubedata_fst(void *, void *);
     12 static void             invert_cubedata_fst(void *, void *);
     13 static uint64_t         index_nxopt31(uint16_t, uint16_t, uint16_t, uint16_t, Trans);
     14 static int              update(PruneData*, uint16_t *, uint16_t *,
     15                                         uint16_t *, uint16_t, Move, Trans);
     16 
     17 static uint16_t cpudsep_table[FACTORIAL8];
     18 
     19 Solver solver_nxopt31 = {
     20 	.moveset           = &moveset_HTM,
     21 	.move_check_stop   = move_check_stop_nxopt31,
     22 	.validate_solution = NULL,
     23 	.niss_makes_sense  = NULL,
     24 	.param             = NULL, 
     25 	.alloc_cubedata    = alloc_cubedata_fst,
     26 	.copy_cubedata     = copy_cubedata_fst,
     27 	.free_cubedata     = free_cubedata_fst,
     28 	.invert_cube       = invert_cubedata_fst,
     29 	.is_solved         = is_solved_fst,
     30 	.apply_move        = apply_move_fst,
     31 	.prepare_cube      = prepare_cube_fst,
     32 };
     33 
     34 /* TODO: this is a bit weird because of realloc,
     35 	but we want to refactor this in any case */
     36 static void
     37 apply_move_fst(void *param, void *cubedata, Move m)
     38 {
     39 	FstCube *fst = (FstCube *)cubedata;
     40 
     41 	FstCube *moved = malloc(sizeof(FstCube));
     42 	*moved = fst_move(m, *fst);
     43 
     44 	free(fst);
     45 	cubedata = moved;
     46 }
     47 
     48 static void
     49 init_cpudsep_table()
     50 {
     51 	static bool generated = false;
     52 	uint64_t i;
     53 	Cube c;
     54 
     55 	if (generated)
     56 		return;
     57 
     58 	gen_coord(&coord_coud_cpudsep);
     59 	for (i = 0; i < FACTORIAL8; i++) {
     60 		index_to_perm(i, 8, c.cp);
     61 		cpudsep_table[i] = index_coord(&coord_cpudsep, &c, NULL);
     62 	}
     63 
     64 	generated = true;
     65 }
     66 
     67 /* TODO: ugly */
     68 void
     69 prepare_solver_nxopt31()
     70 {
     71 	init_fst();
     72 	gen_coord(&coord_eposepe);
     73 	gen_coord(&coord_eofbepos_sym16);
     74 	gen_coord(&coord_coud);
     75 	gen_coord(&coord_cp);
     76 
     77 	/* TODO: prepare also table cp pruning and 
     78 	   internal table for cpudsep from cp */
     79 	/* TODO: also check if ptables are already generated? */
     80 
     81 	init_cpudsep_table();
     82 
     83 	PruneData *pd = malloc(sizeof(PruneData));
     84 	pd->moveset = &moveset_HTM;
     85 	init_moveset(&moveset_HTM);
     86 	pd->coord   = &coord_nxopt31;
     87 	gen_coord(&coord_nxopt31);
     88 	pd->compact = true;
     89 	solver_nxopt31.param = genptable(pd, 4); /* TODO: threads */
     90 }
     91 
     92 static void *
     93 prepare_cube_fst(void *param, Cube *cube)
     94 {
     95 	FstCube *fst = malloc(sizeof(FstCube));
     96 
     97 	*fst = cube_to_fst(cube);
     98 
     99 	return fst;
    100 }
    101 
    102 static bool
    103 is_solved_fst(void *param, void *cubedata)
    104 {
    105 	return fst_is_solved(*(FstCube *)cubedata);
    106 }
    107 
    108 static void *
    109 alloc_cubedata_fst(void *param)
    110 {
    111 	return malloc(sizeof(FstCube));
    112 }
    113 
    114 static void
    115 copy_cubedata_fst(void *param, void *src, void *dst)
    116 {
    117 	memcpy(dst, src, sizeof(FstCube));
    118 }
    119 
    120 static void
    121 free_cubedata_fst(void *param, void *cubedata)
    122 {
    123 	free(cubedata);
    124 }
    125 
    126 /* TODO: again, weird reallocation */
    127 static void
    128 invert_cubedata_fst(void *param, void *cubedata)
    129 {
    130 	FstCube *inv = malloc(sizeof(FstCube));
    131 
    132 	*inv = fst_inverse(*(FstCube *)cubedata);
    133 	free(cubedata);
    134 
    135 	cubedata = inv;
    136 }
    137 
    138 static uint64_t
    139 index_nxopt31(uint16_t eofb, uint16_t eposepe, uint16_t coud, uint16_t cp, Trans t)
    140 {
    141 	uint64_t eofbepos = (eposepe / FACTORIAL4) * POW2TO11 + eofb;
    142 	uint64_t eofbepos_sym16 = coord_eofbepos_sym16.symclass[eofbepos];
    143 	Trans ttr = coord_eofbepos_sym16.transtorep[eofbepos];
    144 	if (t != uf)
    145 		cp = trans_coord(&coord_cp, t, cp);
    146 	uint64_t sep = cpudsep_table[cp];
    147 	uint64_t coud_cpudsep = coud * BINOM8ON4 + sep;
    148 	uint64_t cc = trans_coord(&coord_coud_cpudsep, ttr, coud_cpudsep);
    149 	uint64_t ind = eofbepos_sym16 * POW3TO7 * BINOM8ON4 + cc;
    150 
    151 	return ind;
    152 }
    153 
    154 static int
    155 update(PruneData *pd, uint16_t *eofb, uint16_t *eposepe,
    156     uint16_t *coud, uint16_t cp, Move m, Trans t)
    157 {
    158 	uint64_t ind;
    159 
    160 /* TODO fix
    161 	*eofb    = coord_eofb.mtable[m][*eofb];
    162 	*eposepe = coord_eposepe.mtable[m][*eposepe];
    163 	*coud    = coord_coud.mtable[m][*coud];
    164 */
    165 
    166 	ind = index_nxopt31(*eofb, *eposepe, *coud, cp, t);
    167 
    168 	return ptableval(pd, ind);
    169 }
    170 
    171 static bool
    172 move_check_stop_nxopt31(void *param, DfsArg *arg, Threader *threader)
    173 {
    174 /* TODO: implement nxopt trick, i.e. inverse probing + switching */
    175 /*       this means making the cube data structure more complex,
    176          because we need to memorize the values from last probing
    177          not hard, but it means we can't delegate everything to
    178 	 a cube structure (unless we change FstCube to also include
    179 	 tmhe probing values, but it does not make much sense) */
    180 
    181 	uint64_t ind;
    182 	PruneData *pd = (PruneData *)param;
    183 	FstCube *fst = (FstCube *)arg->cubedata;
    184 
    185 	int l = arg->current_alg->len;
    186 	int target = arg->d - l;
    187 
    188 	Move m = l > 0 ? arg->current_alg->move[l-1] : NULLMOVE;
    189 	/*fst->uf_cp = coord_cp.mtable[m][fst->uf_cp];*/
    190 	fst_move(m, *fst);
    191 
    192 	int nuf = update(pd, &fst->uf_eofb, &fst->uf_eposepe, &fst->uf_coud,
    193 	    fst->uf_cp, m, uf);
    194 	if (nuf > target)
    195 		return true;
    196 	int nfr = update(pd, &fst->fr_eofb, &fst->fr_eposepe, &fst->fr_coud,
    197 	    fst->uf_cp, m, fr);
    198 	if (nfr > target)
    199 		return true;
    200 	int nrd = update(pd, &fst->rd_eofb, &fst->rd_eposepe, &fst->rd_coud,
    201 	    fst->uf_cp, m, rd);
    202 	if (nrd > target)
    203 		return true;
    204 
    205 	if (nuf == nfr && nuf == nrd && nuf == target)
    206 		return true;
    207 
    208 	FstCube inv = fst_inverse(*fst);
    209 
    210 	ind = index_nxopt31(inv.uf_eofb, inv.uf_eposepe, inv.uf_coud, inv.uf_cp, uf);
    211 	int iuf = ptableval(pd, ind);
    212 	if (iuf > target)
    213 		return true;
    214 	ind = index_nxopt31(inv.fr_eofb, inv.fr_eposepe, inv.fr_coud, inv.uf_cp, fr);
    215 	int ifr = ptableval(pd, ind);
    216 	if (ifr > target)
    217 		return true;
    218 	ind = index_nxopt31(inv.rd_eofb, inv.rd_eposepe, inv.rd_coud, inv.uf_cp, rd);
    219 	int ird = ptableval(pd, ind);
    220 	if (ird > target)
    221 		return true;
    222 
    223 	if (iuf == ifr && iuf == ird && iuf == target)
    224 		return true;
    225 
    226 	fst->uf_cp = coord_cp.mtable[m][fst->uf_cp];
    227 
    228 /* TODO: check also pd_corners */
    229 	return false;
    230 }