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


      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 int64_t appendsolution(const solution_moves_t [static 1],
     10     const solution_settings_t [static 1], solution_list_t [static 1]);
     11 STATIC bool solutions_done(const solution_list_t [static 1],
     12     const solution_settings_t [static 1], int8_t depth);
     13 
     14 STATIC void
     15 solution_moves_reset(solution_moves_t sol[static 1])
     16 {
     17 	sol->nmoves = 0;
     18 	sol->npremoves = 0;
     19 }
     20 
     21 STATIC void
     22 solution_moves_transform(solution_moves_t moves[static 1], uint8_t t)
     23 {
     24 	uint8_t i;
     25 
     26 	for (i = 0; i < moves->nmoves; i++)
     27 		moves->moves[i] = transform_move(moves->moves[i], t);
     28 
     29 	for (i = 0; i < moves->npremoves; i++)
     30 		moves->premoves[i] = transform_move(moves->premoves[i], t);
     31 }
     32 
     33 STATIC bool
     34 solution_list_init(solution_list_t sols[static 1], size_t n, char buf[n])
     35 {
     36 	if (n == 0) {
     37 		LOG("Cannot use solution buffer with size 0\n");
     38 		return false;
     39 	}
     40 
     41 	sols->nsols = 0;
     42 	sols->shortest_sol = MAXLEN + 1;
     43 	sols->size = n;
     44 	sols->used = 0;
     45 	sols->buf = buf;
     46 
     47 	/* Ensure string buffer is NULL-terminated */
     48 	sols->buf[0] = '\0';
     49 
     50 	return true;
     51 }
     52 
     53 STATIC bool
     54 solution_moves_equal(
     55 	const solution_moves_t a[static 1],
     56 	const solution_moves_t b[static 1]
     57 )
     58 {
     59 	uint8_t i;
     60 
     61 	if (a->nmoves != b->nmoves || a->npremoves != b->npremoves)
     62 		return false;
     63 
     64 	for (i = 0; i < a->nmoves; i++)
     65 		if (a->moves[i] != b->moves[i])
     66 			return false;
     67 
     68 	for (i = 0; i < a->npremoves; i++)
     69 		if (a->premoves[i] != b->premoves[i])
     70 			return false;
     71 
     72 	return true;
     73 }
     74 
     75 STATIC bool
     76 solution_moves_is_duplicate(size_t n, const solution_moves_t s[n+1])
     77 {
     78 	size_t i;
     79 
     80 	for (i = 0; i < n; i++)
     81 		if (solution_moves_equal(&s[i], &s[n]))
     82 			return true;
     83 
     84 	return false;
     85 }
     86 
     87 STATIC bool
     88 appendchar(solution_list_t solutions[static 1], char c)
     89 {
     90 	if (solutions->size <= solutions->used)
     91 		return false;
     92 
     93 	solutions->buf[solutions->used++] = c;
     94 
     95 	return true;
     96 }
     97 
     98 STATIC int64_t
     99 appendsolution(
    100 	const solution_moves_t moves[static 1],
    101 	const solution_settings_t settings[static 1],
    102 	solution_list_t list[static 1]
    103 )
    104 {
    105 	int64_t r, strl;
    106 	int i;
    107 	uint8_t t;
    108 	solution_moves_t tsol[NTRANS];
    109 
    110 	if (moves->nmoves + moves->npremoves > MAXLEN)
    111 		goto appendsolution_error_solution_length;
    112 
    113 	for (
    114 	    t = 0, r = 0;
    115 	    t < NTRANS && list->nsols < settings->maxsolutions;
    116 	    t++
    117 	) {
    118 		if (!(settings->tmask & TM_SINGLE(t)))
    119 			continue;
    120 
    121 		tsol[r] = *moves;
    122 		if (settings->unniss) {
    123 			tsol[r].nmoves += moves->npremoves;
    124 			tsol[r].npremoves = 0;
    125 			for (i = moves->npremoves-1; i >= 0; i--)
    126 				tsol[r].moves[tsol[r].nmoves - i - 1] =
    127 				    inverse_move(moves->premoves[i]);
    128 
    129 			/*
    130 			This is a bit ugly: we have to sort now and then again
    131 			later, because the allowedmoves check would fail with
    132 			improperly sorted parallel moves, but then transforming
    133 			could swap the pairs the wrong way around.
    134 			TODO: maybe fix this
    135 			*/
    136 			sortparallel_moves(tsol[r].nmoves, tsol[r].moves);
    137 
    138 			/* Check if unnissed premoves cancel with normal. */
    139 			if (!allowedmoves(tsol[r].nmoves, tsol[r].moves))
    140 				continue;
    141 		}
    142 		solution_moves_transform(&tsol[r], t);
    143 		sortparallel_moves(tsol[r].nmoves, tsol[r].moves);
    144 		sortparallel_moves(tsol[r].npremoves, tsol[r].premoves);
    145 
    146 		/* Skip duplicates that may appear after transforming */
    147 		if (solution_moves_is_duplicate(r, tsol))
    148 			continue;
    149 
    150 		/* Write moves on normal */
    151 		strl = writemoves(tsol[r].nmoves, tsol[r].moves,
    152 		    list->size - list->used, list->buf + list->used);
    153 		if (strl < 0)
    154 			goto appendsolution_error_buffer;
    155 		list->used += strl;
    156 
    157 		/* Write moves on inverse with NISS notation */
    158 		if (tsol[r].npremoves > 0) {
    159 			if (strl > 0)
    160 				if (!appendchar(list, ' '))
    161 					goto appendsolution_error_buffer;
    162 			if (!appendchar(list, '('))
    163 				goto appendsolution_error_buffer;
    164 
    165 			strl = writemoves(tsol[r].npremoves, tsol[r].premoves,
    166 			    list->size - list->used, list->buf + list->used);
    167 			if (strl < 0)
    168 				goto appendsolution_error_buffer;
    169 			list->used += strl;
    170 
    171 			if (!appendchar(list, ')'))
    172 				goto appendsolution_error_buffer;
    173 		}
    174 
    175 		if (!appendchar(list, '\n'))
    176 			goto appendsolution_error_buffer;
    177 
    178 		++list->nsols;
    179 		list->shortest_sol = MIN(
    180 		    list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves);
    181 		r++;
    182 	}
    183 
    184 	list->buf[list->used] = '\0';
    185 	return r;
    186 
    187 appendsolution_error_buffer:
    188 	LOG("Could not append solution to buffer: size too small\n");
    189 	list->buf[0] = '\0';
    190 	return NISSY_ERROR_BUFFER_SIZE;
    191 
    192 appendsolution_error_solution_length:
    193 	LOG("Error: solution is too long (%" PRIu8 ").\n"
    194 	    "This is a bug, please report it.\n",
    195 	    moves->nmoves + moves->npremoves);
    196 	list->buf[0] = '\0';
    197 	return NISSY_ERROR_UNKNOWN;
    198 }
    199 
    200 STATIC bool
    201 solutions_done(
    202 	const solution_list_t list[static 1],
    203 	const solution_settings_t settings[static 1],
    204 	int8_t depth
    205 )
    206 {
    207 	if (list->nsols >= settings->maxsolutions)
    208 		return true;
    209 
    210 	if (depth > settings->maxmoves)
    211 		return true;
    212 
    213 	if (list->nsols > 0 && settings->optimal >= 0 &&
    214 	    depth > list->shortest_sol + settings->optimal)
    215 		return true;
    216 
    217 	return false;
    218 }