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

solve.h (8771B)


      1 typedef struct {
      2 	cube_t cube;
      3 	cube_t inverse;
      4 	uint8_t target_depth;
      5 	solution_moves_t *solution_moves;
      6 	solution_settings_t *solution_settings;
      7 	solution_list_t *solution_list;
      8 	uint8_t nissflag;
      9 	bool lastisnormal;
     10 	coord_t *coord;
     11 	const void *coord_data;
     12 	const uint8_t *ptable;
     13 } dfsarg_solve_coord_t;
     14 
     15 STATIC int64_t solve_coord(cube_t, coord_t [static 1], uint8_t, uint8_t,
     16     uint8_t, uint8_t, uint64_t, int8_t, int, uint64_t, const void *,
     17     size_t n, char [n]);
     18 STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t,
     19     uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_t n, char [n]);
     20 STATIC bool coord_solution_admissible(const dfsarg_solve_coord_t [static 1]);
     21 STATIC bool solve_coord_dfs_stop(const dfsarg_solve_coord_t [static 1]);
     22 STATIC bool coord_continue_onnormal(const dfsarg_solve_coord_t [static 1]);
     23 STATIC bool coord_continue_oninverse(const dfsarg_solve_coord_t [static 1]);
     24 STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t [static 1]);
     25 
     26 STATIC bool
     27 coord_solution_admissible(const dfsarg_solve_coord_t arg[static 1])
     28 {
     29 	uint8_t n;
     30 
     31 	n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
     32 	if (arg->target_depth != n)
     33 		return false;
     34 
     35 	return arg->coord->is_admissible == NULL ||
     36 	    arg->coord->is_admissible(arg->solution_moves);
     37 }
     38 
     39 STATIC bool
     40 solve_coord_dfs_stop(const dfsarg_solve_coord_t arg[static 1])
     41 {
     42 	bool hasnissed;
     43 	uint8_t n, pval;
     44 	uint64_t coord;
     45 	const cube_t *c;
     46 
     47 	n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
     48 	if (n >= arg->target_depth)
     49 		return true;
     50 
     51 	hasnissed = arg->solution_moves->nmoves > 0 &&
     52 	    arg->solution_moves->npremoves > 0;
     53 	if (!hasnissed && (arg->nissflag & NISSY_NISSFLAG_MIXED))
     54 		return false;
     55 
     56 	c = arg->lastisnormal ? &arg->cube : &arg->inverse;
     57 
     58 	coord = arg->coord->coord(*c, arg->coord_data);
     59 	pval = get_coord_pval(arg->coord, arg->ptable, coord);
     60 
     61 	return n + pval > arg->target_depth;
     62 }
     63 
     64 STATIC bool
     65 coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1])
     66 {
     67 	uint8_t f, nn, ni, th;
     68 
     69 	f = arg->nissflag;
     70 	nn = arg->solution_moves->nmoves;
     71 	ni = arg->solution_moves->npremoves;
     72 	th = DIV_ROUND_UP(arg->target_depth, 2);
     73 
     74 	if (nn + ni == 0)
     75 		return f & (NISSY_NISSFLAG_NORMAL | NISSY_NISSFLAG_MIXED);
     76 
     77 	if (arg->lastisnormal)
     78 		return (f & NISSY_NISSFLAG_NORMAL) ||
     79 		    ((f & NISSY_NISSFLAG_MIXED) && (ni > 0 || nn <= th));
     80 
     81 	return (f & NISSY_NISSFLAG_MIXED) && nn == 0 && ni < th &&
     82 	    coord_can_switch(arg->coord, arg->coord_data,
     83 	        ni, arg->solution_moves->premoves);
     84 }
     85 
     86 STATIC bool
     87 coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1])
     88 {
     89 	uint8_t f, nn, ni, th;
     90 
     91 	f = arg->nissflag;
     92 	nn = arg->solution_moves->nmoves;
     93 	ni = arg->solution_moves->npremoves;
     94 	th = DIV_ROUND_UP(arg->target_depth, 2);
     95 
     96 	if (nn + ni == 0)
     97 		return f & (NISSY_NISSFLAG_INVERSE | NISSY_NISSFLAG_MIXED);
     98 
     99 	if (!arg->lastisnormal)
    100 		return (f & NISSY_NISSFLAG_INVERSE) ||
    101 		    ((f & NISSY_NISSFLAG_MIXED) && (nn > 0 || ni < th));
    102 
    103 	return (f & NISSY_NISSFLAG_MIXED) && ni == 0 && nn <= th &&
    104 	    coord_can_switch(arg->coord, arg->coord_data,
    105 	        nn, arg->solution_moves->moves);
    106 }
    107 
    108 STATIC int64_t
    109 solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
    110 {
    111 	bool lastbackup;
    112 	uint8_t m, l, nnbackup, nibackup;
    113 	uint32_t mm;
    114 	uint64_t coord;
    115 	int64_t n, ret;
    116 	cube_t backup_cube, backup_inverse;
    117 
    118 	coord = arg->coord->coord(arg->cube, arg->coord_data);
    119 	if (coord == 0) {
    120 		if (!coord_solution_admissible(arg))
    121 			return 0;
    122 		return appendsolution(arg->solution_moves,
    123 		    arg->solution_settings, arg->solution_list);
    124 	}
    125 
    126 	if (solve_coord_dfs_stop(arg))
    127 		return 0;
    128 
    129 	backup_cube = arg->cube;
    130 	backup_inverse = arg->inverse;
    131 	lastbackup = arg->lastisnormal;
    132 	nnbackup = arg->solution_moves->nmoves;
    133 	nibackup = arg->solution_moves->npremoves;
    134 
    135 	ret = 0;
    136 	if (coord_continue_onnormal(arg)) {
    137 		l = arg->solution_moves->nmoves;
    138 		if (l == 0) {
    139 			mm = MM_ALLMOVES;
    140 		} else {
    141 			m = arg->solution_moves->moves[l-1];
    142 			mm = allowedmask[movebase(m)];
    143 		}
    144 		arg->solution_moves->nmoves++;
    145 		arg->lastisnormal = true;
    146 
    147 		for (m = 0; m < NMOVES; m++) {
    148 			if (!(mm & (UINT32_C(1) << (uint32_t)m)))
    149 				continue;
    150 
    151 			arg->solution_moves->moves[l] = m;
    152 			arg->cube = move(backup_cube, m);
    153 			arg->inverse = premove(backup_inverse, m);
    154 			n = solve_coord_dfs(arg);
    155 			if (n < 0)
    156 				return n;
    157 			ret += n;
    158 			arg->solution_moves->npremoves = nibackup;
    159 		}
    160 
    161 		arg->solution_moves->nmoves--;
    162 	}
    163 
    164 	arg->lastisnormal = lastbackup;
    165 
    166 	if (coord_continue_oninverse(arg)) {
    167 		l = arg->solution_moves->npremoves;
    168 		if (l == 0) {
    169 			mm = MM_ALLMOVES;
    170 		} else {
    171 			m = arg->solution_moves->premoves[l-1];
    172 			mm = allowedmask[movebase(m)];
    173 		}
    174 		arg->solution_moves->npremoves++;
    175 		arg->lastisnormal = false;
    176 		
    177 		for (m = 0; m < NMOVES; m++) {
    178 			if (!(mm & (UINT32_C(1) << (uint32_t)m)))
    179 				continue;
    180 
    181 			arg->solution_moves->premoves[l] = m;
    182 			arg->inverse = move(backup_inverse, m);
    183 			arg->cube = premove(backup_cube, m);
    184 			n = solve_coord_dfs(arg);
    185 			if (n < 0)
    186 				return n;
    187 			ret += n;
    188 			arg->solution_moves->nmoves = nnbackup;
    189 		}
    190 
    191 		arg->solution_moves->npremoves--;
    192 	}
    193 
    194 	arg->cube = backup_cube;
    195 	arg->inverse = backup_inverse;
    196 	arg->lastisnormal = lastbackup;
    197 
    198 	return ret;
    199 }
    200 
    201 STATIC int64_t
    202 solve_coord_dispatch(
    203 	cube_t cube,
    204 	const char *coord_and_axis,
    205 	uint8_t nissflag,
    206 	uint8_t minmoves,
    207 	uint8_t maxmoves,
    208 	uint64_t maxsolutions,
    209 	int8_t optimal,
    210 	int threads,
    211 	uint64_t data_size,
    212 	const void *data,
    213 	size_t solutions_size,
    214 	char sols[solutions_size]
    215 )
    216 {
    217 	coord_t *coord;
    218 	uint8_t axis;
    219 
    220 	parse_coord_and_axis(
    221 	    strlen(coord_and_axis), coord_and_axis, &coord, &axis);
    222 
    223 	if (coord == NULL) {
    224 		LOG("Could not parse coordinate from '%s'\n", coord_and_axis);
    225 		return NISSY_ERROR_INVALID_SOLVER;
    226 	}
    227 
    228 	if (axis == UINT8_ERROR) {
    229 		LOG("Could not parse axis from '%s'\n", coord_and_axis);
    230 		return NISSY_ERROR_INVALID_SOLVER;
    231 	}
    232 
    233 	return solve_coord(cube, coord, axis, nissflag, minmoves, maxmoves,
    234 	    maxsolutions, optimal, threads, data_size, data,
    235 	    solutions_size, sols);
    236 }
    237 
    238 STATIC int64_t
    239 solve_coord(
    240 	cube_t cube,
    241 	coord_t coord [static 1],
    242 	uint8_t axis,
    243 	uint8_t nissflag,
    244 	uint8_t minmoves,
    245 	uint8_t maxmoves,
    246 	uint64_t maxsolutions,
    247 	int8_t optimal,
    248 	int threads,
    249 	uint64_t data_size,
    250 	const void *data,
    251 	size_t solutions_size,
    252 	char sols[solutions_size]
    253 )
    254 {
    255 	int8_t d;
    256 	uint8_t t;
    257 	int64_t ndepth;
    258 	cube_t c;
    259 	const void *coord_data;
    260 	const uint8_t *ptable;
    261 	dfsarg_solve_coord_t arg;
    262 	tableinfo_t info;
    263 	solution_moves_t solution_moves;
    264 	solution_settings_t solution_settings;
    265 	solution_list_t solution_list;
    266 
    267 	if (!solution_list_init(&solution_list, solutions_size, sols))
    268 		goto solve_coord_error_buffer;
    269 
    270 	if (readtableinfo(data_size, data, &info) != NISSY_OK)
    271 		goto solve_coord_error_data;
    272 
    273 	if (info.type == TABLETYPE_PRUNING) {
    274 		/* Only the pruning table */
    275 		coord_data = NULL;
    276 		ptable = (uint8_t *)data + INFOSIZE;
    277 	} else {
    278 		/* Coordinate has extra data */
    279 		coord_data = (uint8_t *)data + INFOSIZE;
    280 		ptable = (uint8_t *)data + info.next + INFOSIZE;
    281 	}
    282 
    283 	t = coord->axistrans[axis];
    284 	c = transform(cube, t);
    285 
    286 	solution_moves_reset(&solution_moves);
    287 
    288 	solution_settings = (solution_settings_t) {
    289 		.tmask = TM_SINGLE(inverse_trans(t)),
    290 		.unniss = false,
    291 		.maxmoves = maxmoves,
    292 		.maxsolutions = maxsolutions,
    293 		.optimal = optimal,
    294 	};
    295 
    296 	arg = (dfsarg_solve_coord_t) {
    297 		.cube = c,
    298 		.inverse = inverse(c),
    299 		.coord = coord,
    300 		.coord_data = coord_data,
    301 		.ptable = ptable,
    302 		.solution_moves = &solution_moves,
    303 		.solution_settings = &solution_settings,
    304 		.solution_list = &solution_list,
    305 		.nissflag = nissflag,
    306 
    307 		/*
    308 		Since no move has been done yet, this field should be
    309 		neither true nor false; using its value now is logically
    310 		undefined behavior.
    311 		TODO: find a more elegant solution
    312 		*/
    313 		.lastisnormal = true,
    314 	};
    315 
    316 	if (coord->coord(c, coord_data) == 0) {
    317 		if (minmoves == 0 && !appendsolution(
    318 		    &solution_moves, &solution_settings, &solution_list))
    319 				goto solve_coord_error_buffer;
    320 		goto solve_coord_done;
    321 	}
    322 
    323 	for (
    324 	    d = MAX(minmoves, 1);
    325 	    !solutions_done(&solution_list, &solution_settings, d);
    326 	    d++
    327 	) {
    328 		if (d >= 10)
    329 			LOG("Found %" PRIu64 " solutions, searching at depth %"
    330 			    PRId8 "\n", solution_list.nsols, d);
    331 
    332 		arg.target_depth = d;
    333 		solution_moves_reset(arg.solution_moves);
    334 		ndepth = solve_coord_dfs(&arg);
    335 
    336 		if (ndepth < 0) {
    337 			LOG("Error %" PRId64 "\n", ndepth);
    338 			return ndepth;
    339 		}
    340 
    341 		solution_list.nsols += (uint64_t)ndepth;
    342 	}
    343 
    344 solve_coord_done:
    345 	return (int64_t)solution_list.nsols;
    346 
    347 solve_coord_error_data:
    348 	LOG("solve_coord: error reading table\n");
    349 	return NISSY_ERROR_DATA;
    350 
    351 solve_coord_error_buffer:
    352 	LOG("Could not append solution to buffer: size too small\n");
    353 	return NISSY_ERROR_BUFFER_SIZE;
    354 }