nissy-core

The "engine" of nissy, including the H48 optimal solver.
git clone https://git.tronto.net/nissy-core
Download | Log | Files | Refs | README | LICENSE

solve.h (10289B)


      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 unsigned char *coord_data;
     12 	const unsigned char *ptable;
     13 } dfsarg_solve_coord_t;
     14 
     15 STATIC int64_t solve_coord(oriented_cube_t, coord_t [static 1], uint8_t,
     16     uint8_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t,
     17     const unsigned char *, size_t, char *, int (*)(void *), void *);
     18 STATIC long long solve_coord_dispatch(oriented_cube_t, const char *, unsigned,
     19     unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long,
     20     const unsigned char *, unsigned, char *,
     21     long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *);
     22 STATIC bool coord_solution_admissible(const dfsarg_solve_coord_t [static 1]);
     23 STATIC bool coord_continue_onnormal(const dfsarg_solve_coord_t [static 1]);
     24 STATIC bool coord_continue_oninverse(const dfsarg_solve_coord_t [static 1]);
     25 STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t [static 1]);
     26 
     27 STATIC bool
     28 coord_solution_admissible(const dfsarg_solve_coord_t arg[static 1])
     29 {
     30 	uint8_t n;
     31 
     32 	n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
     33 	if (arg->target_depth != n)
     34 		return false;
     35 
     36 	return arg->coord->is_admissible == NULL ||
     37 	    arg->coord->is_admissible(arg->solution_moves);
     38 }
     39 
     40 STATIC bool
     41 coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1])
     42 {
     43 	uint8_t flag, nn, ni, swbound_n, swbound_i, pval;
     44 	uint64_t coord;
     45 
     46 	flag = arg->nissflag;
     47 	nn = arg->solution_moves->nmoves;
     48 	ni = arg->solution_moves->npremoves;
     49 	swbound_n = arg->target_depth / 2;
     50 	swbound_i = DIV_ROUND_UP(arg->target_depth, 2) - 1;
     51 
     52 	/* If only inverse moves are allowed */
     53 	if (flag == NISSY_NISSFLAG_INVERSE)
     54 		return false;
     55 
     56 	/* Pruning table check */
     57 	if (!(flag & NISSY_NISSFLAG_MIXED) || ni != 0) {
     58 		coord = arg->coord->coord(arg->cube, arg->coord_data);
     59 		pval = get_coord_pval(arg->coord, arg->ptable, coord);
     60 		if (nn + ni + pval > arg->target_depth)
     61 			return false;
     62 	}
     63 	
     64 	/* It's the first move */
     65 	if (nn + ni == 0)
     66 		return true;
     67 
     68 	if (arg->lastisnormal) {
     69 		/* Can continue if we have already switched */
     70 		if (ni > 0)
     71 			return true;
     72 
     73 		/* Check that we have enough moves left to switch */
     74 		return flag & NISSY_NISSFLAG_NORMAL || nn < swbound_n;
     75 	} else {
     76 		/* Don't switch if not allowed */
     77 		if (!(flag & NISSY_NISSFLAG_MIXED))
     78 			return false;
     79 
     80 		/* Forbid switching multiple times */
     81 		if (nn > 0)
     82 			return false;
     83 
     84 		/* Some coordinates are not allowed to switch */
     85 		if (!coord_can_switch(arg->coord, arg->coord_data,
     86 		    ni, arg->solution_moves->premoves))
     87 			return false;
     88 
     89 		/* Only switch before half solution is found */
     90 		return ni <= swbound_i;
     91 	}
     92 }
     93 
     94 STATIC bool
     95 coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1])
     96 {
     97 	uint8_t flag, nn, ni, swbound_n, swbound_i, pval;
     98 	uint64_t coord;
     99 
    100 	flag = arg->nissflag;
    101 	nn = arg->solution_moves->nmoves;
    102 	ni = arg->solution_moves->npremoves;
    103 	swbound_n = arg->target_depth / 2;
    104 	swbound_i = DIV_ROUND_UP(arg->target_depth, 2) - 1;
    105 
    106 	/* If only normal moves are allowed */
    107 	if (flag == NISSY_NISSFLAG_NORMAL)
    108 		return false;
    109 
    110 	/* Pruning table check */
    111 	if (!(flag & NISSY_NISSFLAG_MIXED) || nn != 0) {
    112 		coord = arg->coord->coord(arg->inverse, arg->coord_data);
    113 		pval = get_coord_pval(arg->coord, arg->ptable, coord);
    114 		if (nn + ni + pval > arg->target_depth)
    115 			return false;
    116 	}
    117 	
    118 	/* It's the first move */
    119 	if (nn + ni == 0)
    120 		return true;
    121 
    122 	if (!arg->lastisnormal) {
    123 		/* Can continue if we have already switched */
    124 		if (nn > 0)
    125 			return true;
    126 
    127 		/* Check that we have enough moves left to switch */
    128 		return flag & NISSY_NISSFLAG_INVERSE || ni < swbound_i;
    129 	} else {
    130 		/* Don't switch if not allowed */
    131 		if (!(flag & NISSY_NISSFLAG_MIXED))
    132 			return false;
    133 
    134 		/* Forbid switching multiple times */
    135 		if (ni > 0)
    136 			return false;
    137 
    138 		/* Some coordinates are not allowed to switch */
    139 		if (!coord_can_switch(arg->coord, arg->coord_data,
    140 		    nn, arg->solution_moves->moves))
    141 			return false;
    142 
    143 		/* Only switch before half solution is found */
    144 		return nn <= swbound_n;
    145 	}
    146 }
    147 
    148 STATIC int64_t
    149 solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
    150 {
    151 	bool lastbackup;
    152 	uint8_t m, l, nnbackup, nibackup, nmoves;
    153 	uint32_t mm;
    154 	uint64_t coord;
    155 	int64_t n, ret;
    156 	cube_t backup_cube, backup_inverse;
    157 
    158 	if (arg->coord->solution_prune != NULL &&
    159 	    arg->coord->solution_prune(arg->solution_moves))
    160 		return 0;
    161 
    162 	coord = arg->coord->coord(arg->cube, arg->coord_data);
    163 	if (coord_is_solved(arg->coord, coord, arg->coord_data)) {
    164 		if (!coord_solution_admissible(arg))
    165 			return 0;
    166 		return appendsolution(arg->solution_moves,
    167 		    arg->solution_settings, arg->solution_list);
    168 	}
    169 
    170 	backup_cube = arg->cube;
    171 	backup_inverse = arg->inverse;
    172 	lastbackup = arg->lastisnormal;
    173 	nnbackup = arg->solution_moves->nmoves;
    174 	nibackup = arg->solution_moves->npremoves;
    175 	nmoves = nnbackup + nibackup;
    176 
    177 	if (nmoves >= arg->target_depth)
    178 		return 0;
    179 
    180 	ret = 0;
    181 	if (coord_continue_onnormal(arg)) {
    182 		l = arg->solution_moves->nmoves;
    183 		mm = arg->coord->moves_mask_solve;
    184 		if (l != 0) {
    185 			m = arg->solution_moves->moves[l-1];
    186 			mm &= allowedmask[movebase(m)];
    187 		}
    188 		arg->solution_moves->nmoves++;
    189 		arg->lastisnormal = true;
    190 
    191 		for (m = 0; m < NMOVES; m++) {
    192 			if (!(mm & (UINT32_C(1) << (uint32_t)m)))
    193 				continue;
    194 
    195 			arg->solution_moves->moves[l] = m;
    196 			arg->cube = move(backup_cube, m);
    197 			arg->inverse = premove(backup_inverse, m);
    198 			n = solve_coord_dfs(arg);
    199 			if (n < 0)
    200 				return n;
    201 			ret += n;
    202 			arg->solution_moves->npremoves = nibackup;
    203 		}
    204 
    205 		arg->solution_moves->nmoves--;
    206 	}
    207 
    208 	arg->cube = backup_cube;
    209 	arg->inverse = backup_inverse;
    210 	arg->lastisnormal = lastbackup;
    211 
    212 	if (coord_continue_oninverse(arg)) {
    213 		l = arg->solution_moves->npremoves;
    214 		mm = arg->coord->moves_mask_solve;
    215 		if (l != 0) {
    216 			m = arg->solution_moves->premoves[l-1];
    217 			mm &= allowedmask[movebase(m)];
    218 		}
    219 		arg->solution_moves->npremoves++;
    220 		arg->lastisnormal = false;
    221 		
    222 		for (m = 0; m < NMOVES; m++) {
    223 			if (!(mm & (UINT32_C(1) << (uint32_t)m)))
    224 				continue;
    225 
    226 			arg->solution_moves->premoves[l] = m;
    227 			arg->inverse = move(backup_inverse, m);
    228 			arg->cube = premove(backup_cube, m);
    229 			n = solve_coord_dfs(arg);
    230 			if (n < 0)
    231 				return n;
    232 			ret += n;
    233 			arg->solution_moves->nmoves = nnbackup;
    234 		}
    235 
    236 		arg->solution_moves->npremoves--;
    237 	}
    238 
    239 	arg->cube = backup_cube;
    240 	arg->inverse = backup_inverse;
    241 	arg->lastisnormal = lastbackup;
    242 
    243 	return ret;
    244 }
    245 
    246 STATIC long long
    247 solve_coord_dispatch(
    248 	oriented_cube_t oc,
    249 	const char *coord_and_trans,
    250 	unsigned nissflag,
    251 	unsigned minmoves,
    252 	unsigned maxmoves,
    253 	unsigned maxsolutions,
    254 	unsigned optimal,
    255 	unsigned threads,
    256 	unsigned long long data_size,
    257 	const unsigned char *data,
    258 	unsigned solutions_size,
    259 	char *sols,
    260 	long long stats[static NISSY_SIZE_SOLVE_STATS],
    261 	int (*poll_status)(void *),
    262 	void *poll_status_data
    263 )
    264 {
    265 	coord_t *coord;
    266 	uint8_t trans;
    267 
    268 	parse_coord_and_trans(coord_and_trans, &coord, NULL, &trans);
    269 
    270 	if (coord == NULL) {
    271 		LOG("Error: could not parse coordinate from '%s'\n",
    272 		    coord_and_trans);
    273 		return NISSY_ERROR_INVALID_SOLVER;
    274 	}
    275 
    276 	if (trans == UINT8_ERROR) {
    277 		LOG("Error: could not parse transformation from '%s'\n",
    278 		    coord_and_trans);
    279 		return NISSY_ERROR_INVALID_SOLVER;
    280 	}
    281 
    282 	return solve_coord(oc, coord, trans, nissflag, minmoves, maxmoves,
    283 	    maxsolutions, optimal, threads, data_size, data,
    284 	    solutions_size, sols, poll_status, poll_status_data);
    285 }
    286 
    287 STATIC int64_t
    288 solve_coord(
    289 	oriented_cube_t oc,
    290 	coord_t coord [static 1],
    291 	uint8_t trans,
    292 	uint8_t nissflag,
    293 	uint8_t minmoves,
    294 	uint8_t maxmoves,
    295 	uint64_t maxsolutions,
    296 	uint8_t optimal,
    297 	uint8_t threads,
    298 	uint64_t data_size,
    299 	const unsigned char *data,
    300 	size_t solutions_size,
    301 	char *sols,
    302 	int (*poll_status)(void *),
    303 	void *poll_status_data
    304 )
    305 {
    306 	int8_t d;
    307 	uint64_t i;
    308 	int64_t err;
    309 	cube_t c;
    310 	const unsigned char *coord_data;
    311 	const unsigned char *ptable;
    312 	dfsarg_solve_coord_t arg;
    313 	tableinfo_t info;
    314 	solution_moves_t solution_moves;
    315 	solution_settings_t solution_settings;
    316 	solution_list_t solution_list;
    317 
    318 	c = transform(oc.cube, trans);
    319 
    320 	if (!coord->is_solvable(c))
    321 		goto solve_coord_error_unsolvable;
    322 
    323 	if (!solution_list_init(&solution_list, solutions_size, sols))
    324 		goto solve_coord_error_buffer;
    325 
    326 	if (readtableinfo(data_size, data, &info) != NISSY_OK)
    327 		goto solve_coord_error_data;
    328 
    329 	if (info.type == TABLETYPE_PRUNING) {
    330 		/* Only the pruning table */
    331 		coord_data = NULL;
    332 		ptable = data + INFOSIZE;
    333 	} else {
    334 		/* Coordinate has extra data */
    335 		coord_data = data + INFOSIZE;
    336 		ptable = data + info.next + INFOSIZE;
    337 	}
    338 
    339 	solution_moves_reset(&solution_moves);
    340 
    341 	solution_settings = (solution_settings_t) {
    342 		.tmask = TM_SINGLE(inverse_trans(trans)),
    343 		.unniss = false,
    344 		.maxmoves = maxmoves,
    345 		.maxsolutions = maxsolutions,
    346 		.optimal = optimal,
    347 		.orientation = oc.orientation,
    348 	};
    349 
    350 	arg = (dfsarg_solve_coord_t) {
    351 		.cube = c,
    352 		.inverse = inverse(c),
    353 		.coord = coord,
    354 		.coord_data = coord_data,
    355 		.ptable = ptable,
    356 		.solution_moves = &solution_moves,
    357 		.solution_settings = &solution_settings,
    358 		.solution_list = &solution_list,
    359 		.nissflag = nissflag,
    360 	};
    361 
    362 	i = coord->coord(c, coord_data);
    363 	if (coord_is_solved(coord, i, coord_data)) {
    364 		if (minmoves == 0 && !appendsolution(&solution_moves,
    365 		    &solution_settings, &solution_list))
    366 				goto solve_coord_error_buffer;
    367 		goto solve_coord_done;
    368 	}
    369 
    370 	for (
    371 	    d = MAX(minmoves, 1);
    372 	    !solutions_done(&solution_list, &solution_settings, d);
    373 	    d++
    374 	) {
    375 		if (d >= 12)
    376 			LOG("[%s solve] Found %" PRIu64 " solutions, "
    377 			    "searching at depth %" PRId8 "\n",
    378 			    coord->name, solution_list.nsols, d);
    379 
    380 		arg.target_depth = d;
    381 		solution_moves_reset(arg.solution_moves);
    382 		if ((err = solve_coord_dfs(&arg)) < 0)
    383 			return err;
    384 	}
    385 
    386 solve_coord_done:
    387 	return (int64_t)solution_list.nsols;
    388 
    389 solve_coord_error_data:
    390 	LOG("[%s solve] Error reading table\n", coord->name);
    391 	return NISSY_ERROR_DATA;
    392 
    393 solve_coord_error_buffer:
    394 	LOG("[%s solve] Error appending solution to buffer: size too small\n",
    395 	    coord->name);
    396 	return NISSY_ERROR_BUFFER_SIZE;
    397 
    398 solve_coord_error_unsolvable:
    399 	LOG("[%s solve] Error: cube not ready\n", coord->name);
    400 	return NISSY_ERROR_UNSOLVABLE_CUBE;
    401 }