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 (10179B)


      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 	coord = arg->coord->coord(arg->cube, arg->coord_data);
    159 	if (coord_is_solved(arg->coord, coord, arg->coord_data)) {
    160 		if (!coord_solution_admissible(arg))
    161 			return 0;
    162 		return appendsolution(arg->solution_moves,
    163 		    arg->solution_settings, arg->solution_list);
    164 	}
    165 
    166 	backup_cube = arg->cube;
    167 	backup_inverse = arg->inverse;
    168 	lastbackup = arg->lastisnormal;
    169 	nnbackup = arg->solution_moves->nmoves;
    170 	nibackup = arg->solution_moves->npremoves;
    171 	nmoves = nnbackup + nibackup;
    172 
    173 	if (nmoves >= arg->target_depth)
    174 		return 0;
    175 
    176 	ret = 0;
    177 	if (coord_continue_onnormal(arg)) {
    178 		l = arg->solution_moves->nmoves;
    179 		mm = arg->coord->moves_mask_solve;
    180 		if (l != 0) {
    181 			m = arg->solution_moves->moves[l-1];
    182 			mm &= allowedmask[movebase(m)];
    183 		}
    184 		arg->solution_moves->nmoves++;
    185 		arg->lastisnormal = true;
    186 
    187 		for (m = 0; m < NMOVES; m++) {
    188 			if (!(mm & (UINT32_C(1) << (uint32_t)m)))
    189 				continue;
    190 
    191 			arg->solution_moves->moves[l] = m;
    192 			arg->cube = move(backup_cube, m);
    193 			arg->inverse = premove(backup_inverse, m);
    194 			n = solve_coord_dfs(arg);
    195 			if (n < 0)
    196 				return n;
    197 			ret += n;
    198 			arg->solution_moves->npremoves = nibackup;
    199 		}
    200 
    201 		arg->solution_moves->nmoves--;
    202 	}
    203 
    204 	arg->cube = backup_cube;
    205 	arg->inverse = backup_inverse;
    206 	arg->lastisnormal = lastbackup;
    207 
    208 	if (coord_continue_oninverse(arg)) {
    209 		l = arg->solution_moves->npremoves;
    210 		mm = arg->coord->moves_mask_solve;
    211 		if (l != 0) {
    212 			m = arg->solution_moves->premoves[l-1];
    213 			mm &= allowedmask[movebase(m)];
    214 		}
    215 		arg->solution_moves->npremoves++;
    216 		arg->lastisnormal = false;
    217 		
    218 		for (m = 0; m < NMOVES; m++) {
    219 			if (!(mm & (UINT32_C(1) << (uint32_t)m)))
    220 				continue;
    221 
    222 			arg->solution_moves->premoves[l] = m;
    223 			arg->inverse = move(backup_inverse, m);
    224 			arg->cube = premove(backup_cube, m);
    225 			n = solve_coord_dfs(arg);
    226 			if (n < 0)
    227 				return n;
    228 			ret += n;
    229 			arg->solution_moves->nmoves = nnbackup;
    230 		}
    231 
    232 		arg->solution_moves->npremoves--;
    233 	}
    234 
    235 	arg->cube = backup_cube;
    236 	arg->inverse = backup_inverse;
    237 	arg->lastisnormal = lastbackup;
    238 
    239 	return ret;
    240 }
    241 
    242 STATIC long long
    243 solve_coord_dispatch(
    244 	oriented_cube_t oc,
    245 	const char *coord_and_trans,
    246 	unsigned nissflag,
    247 	unsigned minmoves,
    248 	unsigned maxmoves,
    249 	unsigned maxsolutions,
    250 	unsigned optimal,
    251 	unsigned threads,
    252 	unsigned long long data_size,
    253 	const unsigned char *data,
    254 	unsigned solutions_size,
    255 	char *sols,
    256 	long long stats[static NISSY_SIZE_SOLVE_STATS],
    257 	int (*poll_status)(void *),
    258 	void *poll_status_data
    259 )
    260 {
    261 	coord_t *coord;
    262 	uint8_t trans;
    263 
    264 	parse_coord_and_trans(coord_and_trans, &coord, NULL, &trans);
    265 
    266 	if (coord == NULL) {
    267 		LOG("Error: could not parse coordinate from '%s'\n",
    268 		    coord_and_trans);
    269 		return NISSY_ERROR_INVALID_SOLVER;
    270 	}
    271 
    272 	if (trans == UINT8_ERROR) {
    273 		LOG("Error: could not parse transformation from '%s'\n",
    274 		    coord_and_trans);
    275 		return NISSY_ERROR_INVALID_SOLVER;
    276 	}
    277 
    278 	return solve_coord(oc, coord, trans, nissflag, minmoves, maxmoves,
    279 	    maxsolutions, optimal, threads, data_size, data,
    280 	    solutions_size, sols, poll_status, poll_status_data);
    281 }
    282 
    283 STATIC int64_t
    284 solve_coord(
    285 	oriented_cube_t oc,
    286 	coord_t coord [static 1],
    287 	uint8_t trans,
    288 	uint8_t nissflag,
    289 	uint8_t minmoves,
    290 	uint8_t maxmoves,
    291 	uint64_t maxsolutions,
    292 	uint8_t optimal,
    293 	uint8_t threads,
    294 	uint64_t data_size,
    295 	const unsigned char *data,
    296 	size_t solutions_size,
    297 	char *sols,
    298 	int (*poll_status)(void *),
    299 	void *poll_status_data
    300 )
    301 {
    302 	int8_t d;
    303 	uint64_t i;
    304 	int64_t err;
    305 	cube_t c;
    306 	const unsigned char *coord_data;
    307 	const unsigned char *ptable;
    308 	dfsarg_solve_coord_t arg;
    309 	tableinfo_t info;
    310 	solution_moves_t solution_moves;
    311 	solution_settings_t solution_settings;
    312 	solution_list_t solution_list;
    313 
    314 	c = transform(oc.cube, trans);
    315 
    316 	if (!coord->is_solvable(c))
    317 		goto solve_coord_error_unsolvable;
    318 
    319 	if (!solution_list_init(&solution_list, solutions_size, sols))
    320 		goto solve_coord_error_buffer;
    321 
    322 	if (readtableinfo(data_size, data, &info) != NISSY_OK)
    323 		goto solve_coord_error_data;
    324 
    325 	if (info.type == TABLETYPE_PRUNING) {
    326 		/* Only the pruning table */
    327 		coord_data = NULL;
    328 		ptable = data + INFOSIZE;
    329 	} else {
    330 		/* Coordinate has extra data */
    331 		coord_data = data + INFOSIZE;
    332 		ptable = data + info.next + INFOSIZE;
    333 	}
    334 
    335 	solution_moves_reset(&solution_moves);
    336 
    337 	solution_settings = (solution_settings_t) {
    338 		.tmask = TM_SINGLE(inverse_trans(trans)),
    339 		.unniss = false,
    340 		.maxmoves = maxmoves,
    341 		.maxsolutions = maxsolutions,
    342 		.optimal = optimal,
    343 		.orientation = oc.orientation,
    344 	};
    345 
    346 	arg = (dfsarg_solve_coord_t) {
    347 		.cube = c,
    348 		.inverse = inverse(c),
    349 		.coord = coord,
    350 		.coord_data = coord_data,
    351 		.ptable = ptable,
    352 		.solution_moves = &solution_moves,
    353 		.solution_settings = &solution_settings,
    354 		.solution_list = &solution_list,
    355 		.nissflag = nissflag,
    356 	};
    357 
    358 	i = coord->coord(c, coord_data);
    359 	if (coord_is_solved(coord, i, coord_data)) {
    360 		if (minmoves == 0 && !appendsolution(&solution_moves,
    361 		    &solution_settings, &solution_list))
    362 				goto solve_coord_error_buffer;
    363 		goto solve_coord_done;
    364 	}
    365 
    366 	for (
    367 	    d = MAX(minmoves, 1);
    368 	    !solutions_done(&solution_list, &solution_settings, d);
    369 	    d++
    370 	) {
    371 		if (d >= 12)
    372 			LOG("[%s solve] Found %" PRIu64 " solutions, "
    373 			    "searching at depth %" PRId8 "\n",
    374 			    coord->name, solution_list.nsols, d);
    375 
    376 		arg.target_depth = d;
    377 		solution_moves_reset(arg.solution_moves);
    378 		if ((err = solve_coord_dfs(&arg)) < 0)
    379 			return err;
    380 	}
    381 
    382 solve_coord_done:
    383 	return (int64_t)solution_list.nsols;
    384 
    385 solve_coord_error_data:
    386 	LOG("[%s solve] Error reading table\n", coord->name);
    387 	return NISSY_ERROR_DATA;
    388 
    389 solve_coord_error_buffer:
    390 	LOG("[%s solve] Error appending solution to buffer: size too small\n",
    391 	    coord->name);
    392 	return NISSY_ERROR_BUFFER_SIZE;
    393 
    394 solve_coord_error_unsolvable:
    395 	LOG("[%s solve] Error: cube not ready\n", coord->name);
    396 	return NISSY_ERROR_UNSOLVABLE_CUBE;
    397 }