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

multisolve.h (7815B)


      1 /*
      2 For now the only multicoordinate is DRFIN, and this solver reflects this.
      3 For example, NISS is not available.
      4 */
      5 
      6 typedef struct {
      7 	cube_t cube;
      8 	cube_t inverse;
      9 	uint8_t target_depth;
     10 	solution_moves_t *solution_moves;
     11 	solution_settings_t *solution_settings;
     12 	solution_list_t *solution_list;
     13 	multicoord_t *mcoord;
     14 	const unsigned char *coord_data[MAX_MULTICOORD_NCOORDS];
     15 	const unsigned char *ptable[MAX_MULTICOORD_NCOORDS];
     16 } dfsarg_solve_multicoord_t;
     17 
     18 STATIC int64_t solve_multicoord(oriented_cube_t, multicoord_t [static 1],
     19     uint8_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t,
     20     const unsigned char *, size_t, char *, int (*)(void *), void *);
     21 STATIC long long solve_multicoord_dispatch(oriented_cube_t, const char *,
     22     unsigned, unsigned, unsigned, unsigned, unsigned, unsigned,
     23     unsigned long long, const unsigned char *, unsigned, char *,
     24     long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *);
     25 STATIC bool multicoord_solution_admissible(
     26     const dfsarg_solve_multicoord_t [static 1]);
     27 STATIC bool multicoord_dfs_stop(const dfsarg_solve_multicoord_t [static 1]);
     28 STATIC int64_t solve_multicoord_dfs(dfsarg_solve_multicoord_t [static 1]);
     29 
     30 STATIC bool
     31 multicoord_solution_admissible(const dfsarg_solve_multicoord_t arg[static 1])
     32 {
     33 	uint8_t n, i;
     34 	const coord_t *c;
     35 
     36 	n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
     37 	if (arg->target_depth != n)
     38 		return false;
     39 
     40 	for (i = 0; arg->mcoord->coordinates[i] != NULL; i++) {
     41 		c = arg->mcoord->coordinates[i];
     42 		if (c->is_admissible != NULL &&
     43 		    !c->is_admissible(arg->solution_moves))
     44 			return false;
     45 	}
     46 
     47 	return true;
     48 }
     49 
     50 STATIC bool
     51 multicoord_dfs_stop(const dfsarg_solve_multicoord_t arg[static 1])
     52 {
     53 	uint8_t pval, i;
     54 	uint64_t cval;
     55 	const coord_t *c;
     56 
     57 	for (i = 0, pval = 0; arg->mcoord->coordinates[i] != NULL; i++) {
     58 		c = arg->mcoord->coordinates[i];
     59 
     60 		cval = c->coord(arg->cube, arg->coord_data[i]);
     61 		pval = MAX(pval, get_coord_pval(c, arg->ptable[i], cval));
     62 
     63 		cval = c->coord(arg->inverse, arg->coord_data[i]);
     64 		pval = MAX(pval, get_coord_pval(c, arg->ptable[i], cval));
     65 	}
     66 
     67 	return arg->solution_moves->nmoves + pval > arg->target_depth;
     68 }
     69 
     70 STATIC int64_t
     71 solve_multicoord_dfs(dfsarg_solve_multicoord_t arg[static 1])
     72 {
     73 	uint8_t m, l, i;
     74 	uint32_t mm;
     75 	uint64_t coord;
     76 	int64_t n, ret;
     77 	const coord_t *c;
     78 	cube_t backup_cube, backup_inverse;
     79 
     80 	for (i = 0; arg->mcoord->coordinates[i] != NULL; i++) {
     81 		c = arg->mcoord->coordinates[i];
     82 		coord = c->coord(arg->cube, arg->coord_data[i]);
     83 		if (!coord_is_solved(c, coord, arg->coord_data[i]))
     84 			goto solve_multicoord_dfs_notsolved;
     85 	}
     86 
     87 	/* All coordinates are solved */
     88 	if (!multicoord_solution_admissible(arg))
     89 		return 0;
     90 	return appendsolution(arg->solution_moves,
     91 	    arg->solution_settings, arg->solution_list);
     92 
     93 solve_multicoord_dfs_notsolved:
     94 	if (multicoord_dfs_stop(arg))
     95 		return 0;
     96 
     97 	backup_cube = arg->cube;
     98 	backup_inverse = arg->inverse;
     99 	ret = 0;
    100 
    101 	l = arg->solution_moves->nmoves;
    102 	mm = arg->mcoord->moves_mask;
    103 	if (l != 0) {
    104 		m = arg->solution_moves->moves[l-1];
    105 		mm &= allowedmask[movebase(m)];
    106 	}
    107 	arg->solution_moves->nmoves++;
    108 
    109 	for (m = 0; m < NMOVES; m++) {
    110 		if (!(mm & (UINT32_C(1) << (uint32_t)m)))
    111 			continue;
    112 
    113 		arg->solution_moves->moves[l] = m;
    114 		arg->cube = move(backup_cube, m);
    115 		arg->inverse = premove(backup_inverse, m);
    116 		n = solve_multicoord_dfs(arg);
    117 		if (n < 0)
    118 			return n;
    119 		ret += n;
    120 	}
    121 
    122 	arg->solution_moves->nmoves--;
    123 	arg->cube = backup_cube;
    124 	arg->inverse = backup_inverse;
    125 
    126 	return ret;
    127 }
    128 
    129 STATIC long long
    130 solve_multicoord_dispatch(
    131 	oriented_cube_t oc,
    132 	const char *coord_and_trans,
    133 	unsigned nissflag,
    134 	unsigned minmoves,
    135 	unsigned maxmoves,
    136 	unsigned maxsolutions,
    137 	unsigned optimal,
    138 	unsigned threads,
    139 	unsigned long long data_size,
    140 	const unsigned char *data,
    141 	unsigned solutions_size,
    142 	char *sols,
    143 	long long stats[static NISSY_SIZE_SOLVE_STATS],
    144 	int (*poll_status)(void *),
    145 	void *poll_status_data
    146 )
    147 {
    148 	multicoord_t *mcoord;
    149 	uint8_t trans;
    150 
    151 	parse_coord_and_trans(coord_and_trans, NULL, &mcoord, &trans);
    152 
    153 	if (mcoord == NULL) {
    154 		LOG("Error: could not parse coordinate from '%s'\n",
    155 		    coord_and_trans);
    156 		return NISSY_ERROR_INVALID_SOLVER;
    157 	}
    158 
    159 	if (trans == UINT8_ERROR) {
    160 		LOG("Error: could not parse transformation from '%s'\n",
    161 		    coord_and_trans);
    162 		return NISSY_ERROR_INVALID_SOLVER;
    163 	}
    164 
    165 	return solve_multicoord(oc, mcoord, trans, minmoves,
    166 	    maxmoves, maxsolutions, optimal, threads, data_size, data,
    167 	    solutions_size, sols, poll_status, poll_status_data);
    168 }
    169 
    170 STATIC int64_t
    171 solve_multicoord(
    172 	oriented_cube_t oc,
    173 	multicoord_t mcoord [static 1],
    174 	uint8_t trans,
    175 	uint8_t minmoves,
    176 	uint8_t maxmoves,
    177 	uint64_t maxsolutions,
    178 	uint8_t optimal,
    179 	uint8_t threads,
    180 	uint64_t data_size,
    181 	const unsigned char *data,
    182 	size_t solutions_size,
    183 	char *sols,
    184 	int (*poll_status)(void *),
    185 	void *poll_status_data
    186 )
    187 {
    188 	int8_t d;
    189 	size_t j, of;
    190 	uint64_t i;
    191 	int64_t err;
    192 	cube_t c;
    193 	const coord_t *coord;
    194 	dfsarg_solve_multicoord_t arg;
    195 	tableinfo_t info;
    196 	solution_moves_t solution_moves;
    197 	solution_settings_t solution_settings;
    198 	solution_list_t solution_list;
    199 
    200 	c = transform(oc.cube, trans);
    201 
    202 	if (!mcoord->is_solvable(c))
    203 		goto solve_multicoord_error_unsolvable;
    204 
    205 	if (!solution_list_init(&solution_list, solutions_size, sols))
    206 		goto solve_multicoord_error_buffer;
    207 
    208 	solution_moves_reset(&solution_moves);
    209 
    210 	solution_settings = (solution_settings_t) {
    211 		.tmask = TM_SINGLE(inverse_trans(trans)),
    212 		.unniss = false,
    213 		.maxmoves = maxmoves,
    214 		.maxsolutions = maxsolutions,
    215 		.optimal = optimal,
    216 		.orientation = oc.orientation,
    217 	};
    218 
    219 	arg = (dfsarg_solve_multicoord_t) {
    220 		.cube = c,
    221 		.inverse = inverse(c),
    222 		.mcoord = mcoord,
    223 		.solution_moves = &solution_moves,
    224 		.solution_settings = &solution_settings,
    225 		.solution_list = &solution_list,
    226 	};
    227 
    228 	for (j = 0, of = INFOSIZE; mcoord->coordinates[j] != NULL; j++) {
    229 		if (readtableinfo(data_size-of, data+of, &info) != NISSY_OK)
    230 			goto solve_multicoord_error_data;
    231 
    232 		if (info.type == TABLETYPE_PRUNING) {
    233 			/* Only the pruning table */
    234 			arg.coord_data[j] = NULL;
    235 			arg.ptable[j] = data + of + INFOSIZE;
    236 			of += info.fullsize;
    237 		} else {
    238 			/* Coordinate has extra data */
    239 			arg.coord_data[j] = data + of + INFOSIZE;
    240 			arg.ptable[j] = data + of + info.next + INFOSIZE;
    241 			of += info.fullsize;
    242 			if (readtableinfo(data_size-of, data+of, &info)
    243 			    != NISSY_OK)
    244 				goto solve_multicoord_error_data;
    245 			of += info.fullsize;
    246 		}
    247 
    248 		/* Skip padding */
    249 		while (of % 8 != 0)
    250 			of++;
    251 	}
    252 
    253 	for (j = 0; mcoord->coordinates[j] != NULL; j++) {
    254 		coord = mcoord->coordinates[j];
    255 		i = coord->coord(c, arg.coord_data[j]);
    256 		if (!coord_is_solved(coord, i, arg.coord_data[j]))
    257 			goto solve_multicoord_notsolved;
    258 	}
    259 
    260 	/* All coordinates are solved */
    261 	if (minmoves == 0 && !appendsolution(&solution_moves,
    262 	    &solution_settings, &solution_list))
    263 		goto solve_multicoord_error_buffer;
    264 	goto solve_multicoord_done;
    265 
    266 solve_multicoord_notsolved:
    267 	for (
    268 	    d = MAX(minmoves, 1);
    269 	    !solutions_done(&solution_list, &solution_settings, d);
    270 	    d++
    271 	) {
    272 		if (d >= 12)
    273 			LOG("[%s solve] Found %" PRIu64 " solutions, "
    274 			    "searching at depth %" PRId8 "\n",
    275 			    mcoord->name, solution_list.nsols, d);
    276 
    277 		arg.target_depth = d;
    278 		solution_moves_reset(arg.solution_moves);
    279 		if ((err = solve_multicoord_dfs(&arg)) < 0)
    280 			return err;
    281 	}
    282 
    283 solve_multicoord_done:
    284 	return (int64_t)solution_list.nsols;
    285 
    286 solve_multicoord_error_data:
    287 	LOG("[%s solve] Error reading table\n", mcoord->name);
    288 	return NISSY_ERROR_DATA;
    289 
    290 solve_multicoord_error_buffer:
    291 	LOG("[%s solve] Error appending solution to buffer: size too small\n",
    292 	    mcoord->name);
    293 	return NISSY_ERROR_BUFFER_SIZE;
    294 
    295 solve_multicoord_error_unsolvable:
    296 	LOG("[%s solve] Error: cube not ready\n", mcoord->name);
    297 	return NISSY_ERROR_UNSOLVABLE_CUBE;
    298 }