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

solutions.h (6465B)


      1 STATIC void solution_moves_reset(solution_moves_t [static 1]);
      2 STATIC void solution_moves_transform(solution_moves_t [static 1], uint8_t t);
      3 STATIC bool solution_list_init(
      4     solution_list_t [static 1], size_t n, char [n]);
      5 STATIC bool solution_moves_equal(
      6     const solution_moves_t [static 1], const solution_moves_t [static 1]);
      7 STATIC bool solution_moves_is_duplicate(size_t n, const solution_moves_t[n+1]);
      8 STATIC bool appendchar(solution_list_t [static 1], char);
      9 STATIC bool appendnormal(
     10     const solution_moves_t [static 1], solution_list_t [static 1]);
     11 STATIC bool appendinverse(
     12     const solution_moves_t [static 1], solution_list_t [static 1]);
     13 STATIC int64_t appendsolution(const solution_moves_t [static 1],
     14     const solution_settings_t [static 1], solution_list_t [static 1], bool,
     15     const char *);
     16 STATIC bool solutions_done(const solution_list_t [static 1],
     17     const solution_settings_t [static 1], int8_t depth);
     18 
     19 STATIC void
     20 solution_moves_reset(solution_moves_t sol[static 1])
     21 {
     22 	sol->nmoves = 0;
     23 	sol->npremoves = 0;
     24 }
     25 
     26 STATIC void
     27 solution_moves_transform(solution_moves_t moves[static 1], uint8_t t)
     28 {
     29 	uint8_t i;
     30 
     31 	for (i = 0; i < moves->nmoves; i++)
     32 		moves->moves[i] = transform_move(moves->moves[i], t);
     33 
     34 	for (i = 0; i < moves->npremoves; i++)
     35 		moves->premoves[i] = transform_move(moves->premoves[i], t);
     36 }
     37 
     38 STATIC bool
     39 solution_list_init(solution_list_t sols[static 1], size_t n, char buf[n])
     40 {
     41 	if (n == 0) {
     42 		LOG("Error: cannot use solution buffer with size 0\n");
     43 		return false;
     44 	}
     45 
     46 	sols->nsols = 0;
     47 	sols->shortest_sol = MAXLEN + 1;
     48 	sols->size = n;
     49 	sols->used = 0;
     50 	sols->buf = buf;
     51 	sols->buf[0] = '\0';
     52 
     53 	return true;
     54 }
     55 
     56 STATIC bool
     57 solution_moves_equal(
     58 	const solution_moves_t a[static 1],
     59 	const solution_moves_t b[static 1]
     60 )
     61 {
     62 	uint8_t i;
     63 
     64 	if (a->nmoves != b->nmoves || a->npremoves != b->npremoves)
     65 		return false;
     66 
     67 	for (i = 0; i < a->nmoves; i++)
     68 		if (a->moves[i] != b->moves[i])
     69 			return false;
     70 
     71 	for (i = 0; i < a->npremoves; i++)
     72 		if (a->premoves[i] != b->premoves[i])
     73 			return false;
     74 
     75 	return true;
     76 }
     77 
     78 STATIC bool
     79 solution_moves_is_duplicate(size_t n, const solution_moves_t s[n+1])
     80 {
     81 	size_t i;
     82 
     83 	for (i = 0; i < n; i++)
     84 		if (solution_moves_equal(&s[i], &s[n]))
     85 			return true;
     86 
     87 	return false;
     88 }
     89 
     90 STATIC bool
     91 appendchar(solution_list_t solutions[static 1], char c)
     92 {
     93 	if (solutions->size <= solutions->used)
     94 		return false;
     95 
     96 	solutions->buf[solutions->used++] = c;
     97 
     98 	return true;
     99 }
    100 
    101 STATIC bool
    102 appendnormal(
    103 	const solution_moves_t moves[static 1],
    104 	solution_list_t list[static 1]
    105 )
    106 {
    107 	int64_t strl;
    108 
    109 	if (moves->nmoves == 0)
    110 		return true;
    111 
    112 	if ((strl = writemoves(moves->nmoves, moves->moves,
    113 	    list->size - list->used, list->buf + list->used)) < 0)
    114 		return false;
    115 	list->used += strl;
    116 
    117 	return true;
    118 }
    119 
    120 STATIC bool
    121 appendinverse(
    122 	const solution_moves_t moves[static 1],
    123 	solution_list_t list[static 1]
    124 )
    125 {
    126 	int64_t strl;
    127 
    128 	if (moves->npremoves == 0)
    129 		return true;
    130 
    131 	if (!appendchar(list, '('))
    132 		return false;
    133 
    134 	if ((strl = writemoves(moves->npremoves, moves->premoves,
    135 	    list->size - list->used, list->buf + list->used)) < 0)
    136 		return false;
    137 	list->used += strl;
    138 
    139 	return appendchar(list, ')');
    140 }
    141 
    142 STATIC int64_t
    143 appendsolution(
    144 	const solution_moves_t moves[static 1],
    145 	const solution_settings_t settings[static 1],
    146 	solution_list_t list[static 1],
    147 	bool log,
    148 	const char *solver_name
    149 )
    150 {
    151 	int64_t r;
    152 	int i;
    153 	uint8_t t;
    154 	solution_moves_t tsol[NTRANS];
    155 	char *last_start;
    156 
    157 	if (moves->nmoves + moves->npremoves > MAXLEN)
    158 		goto appendsolution_error_solution_length;
    159 
    160 	for (
    161 	    t = 0, r = 0;
    162 	    t < NTRANS && list->nsols < settings->maxsolutions;
    163 	    t++
    164 	) {
    165 		if (!(settings->tmask & TM_SINGLE(t)))
    166 			continue;
    167 
    168 		tsol[r] = *moves;
    169 		if (settings->unniss) {
    170 			tsol[r].nmoves += moves->npremoves;
    171 			tsol[r].npremoves = 0;
    172 			for (i = moves->npremoves-1; i >= 0; i--)
    173 				tsol[r].moves[tsol[r].nmoves - i - 1] =
    174 				    inverse_move(moves->premoves[i]);
    175 
    176 			/*
    177 			This is a bit ugly: we have to sort now and then again
    178 			later, because the allowedmoves check would fail with
    179 			improperly sorted parallel moves, but then transforming
    180 			could swap the pairs the wrong way around.
    181 			TODO: maybe fix this
    182 			*/
    183 			sortparallel_moves(tsol[r].nmoves, tsol[r].moves);
    184 
    185 			/* Check if unnissed premoves cancel with normal. */
    186 			if (!allowedmoves(tsol[r].nmoves, tsol[r].moves))
    187 				continue;
    188 		}
    189 		solution_moves_transform(&tsol[r], t);
    190 		sortparallel_moves(tsol[r].nmoves, tsol[r].moves);
    191 		sortparallel_moves(tsol[r].npremoves, tsol[r].premoves);
    192 
    193 		/* Skip duplicates that may appear after transforming */
    194 		if (solution_moves_is_duplicate(r, tsol))
    195 			continue;
    196 
    197 		last_start = list->buf + list->used;
    198 
    199 		/* Append first the moves on the side that has more */
    200 		/* E.g. write (U L F) B instead of B (U L F) */
    201 		if (tsol[r].nmoves >= tsol[r].npremoves) {
    202 			if (!appendnormal(&tsol[r], list))
    203 				goto appendsolution_error_buffer;
    204 
    205 			if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0)
    206 				if (!appendchar(list, ' '))
    207 					return false;
    208 
    209 			if (!appendinverse(&tsol[r], list))
    210 				goto appendsolution_error_buffer;
    211 		} else {
    212 			if (!appendinverse(&tsol[r], list))
    213 				goto appendsolution_error_buffer;
    214 
    215 			if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0)
    216 				if (!appendchar(list, ' '))
    217 					return false;
    218 
    219 			if (!appendnormal(&tsol[r], list))
    220 				goto appendsolution_error_buffer;
    221 		}
    222 
    223 		if (!appendchar(list, '\n'))
    224 			goto appendsolution_error_buffer;
    225 
    226 		++list->nsols;
    227 		list->shortest_sol = MIN(
    228 		    list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves);
    229 		r++;
    230 
    231 		if (log) {
    232 			list->buf[list->used-1] = '\0';
    233 			LOG("[%s solve] Found solution #%" PRIu64 ": %s\n",
    234 			    solver_name, list->nsols, last_start);
    235 			list->buf[list->used-1] = '\n';
    236 		}
    237 	}
    238 
    239 	list->buf[list->used] = '\0';
    240 	return r;
    241 
    242 appendsolution_error_buffer:
    243 	LOG("[%s solve] Error: buffer too small\n", solver_name);
    244 	list->buf[0] = '\0';
    245 	return NISSY_ERROR_BUFFER_SIZE;
    246 
    247 appendsolution_error_solution_length:
    248 	LOG("[%s solve] Error: solution is too long (%" PRIu8 ").\n"
    249 	    "This is a bug, please report it.\n",
    250 	    solver_name, moves->nmoves + moves->npremoves);
    251 	list->buf[0] = '\0';
    252 	return NISSY_ERROR_UNKNOWN;
    253 }
    254 
    255 STATIC bool
    256 solutions_done(
    257 	const solution_list_t list[static 1],
    258 	const solution_settings_t settings[static 1],
    259 	int8_t depth
    260 )
    261 {
    262 
    263 	return depth > settings->maxmoves ||
    264 	    depth > list->shortest_sol + settings->optimal ||
    265 	    list->nsols >= settings->maxsolutions;
    266 }