nissy-fmc

A Rubik's cube FMC assistant
git clone https://git.tronto.net/nissy-fmc
Download | Log | Files | Refs | README | LICENSE

solve.c (4931B)


      1 #include <stdbool.h>
      2 #include <stddef.h>
      3 #include <inttypes.h>
      4 
      5 #include "cube.h"
      6 #include "coord.h"
      7 #include "solve.h"
      8 
      9 static void append_sol(DfsArg *);
     10 static bool allowed_next(Move m, Move l0, Move l1);
     11 static void get_state(Coordinate *[], Cube *, CubeState *);
     12 static int lower_bound(Coordinate *[], CubeState *);
     13 static bool trivialshorten(DfsArg *);
     14 static void dfs(DfsArg *);
     15 static void dfs_niss(DfsArg *);
     16 static void dfs_move(Move, DfsArg *);
     17 static bool niss_makes_sense(DfsArg *);
     18 
     19 static void
     20 append_sol(DfsArg *arg)
     21 {
     22 	Alg alg;
     23 	int i, n;
     24 
     25 	copy_alg(arg->current_alg, &alg);
     26 	transform_alg(inverse_trans(arg->t), &alg);
     27 
     28 	if (arg->st == INVERSE)
     29 		for (i = 0; i < alg.len; i++)
     30 			alg.inv[i] = true;
     31 
     32 	n = alg_string(&alg, *arg->sol);
     33 	(*arg->sol)[n] = '\n';
     34 	(*arg->sol)[n+1] = 0;
     35 	*arg->sol += (n+1);
     36 }
     37 
     38 static bool
     39 allowed_next(Move m, Move l0, Move l1)
     40 {
     41 	bool p, q, allowed, order;
     42 
     43 	p = l0 != NULLMOVE && base_move(l0) == base_move(m);
     44 	q = l1 != NULLMOVE && base_move(l1) == base_move(m);
     45 	allowed = !(p || (commute(l0, l1) && q));
     46 	order   = !commute(l0, m) || l0 < m;
     47 
     48 	return allowed && order;
     49 }
     50 
     51 void
     52 get_state(Coordinate *coord[], Cube *cube, CubeState *state)
     53 {
     54 	int i;
     55 
     56 	for (i = 0; coord[i] != NULL; i++)
     57 		state[i].val = index_coord(coord[i], cube, &state[i].t);
     58 }
     59 
     60 static int
     61 lower_bound(Coordinate *coord[], CubeState *state)
     62 {
     63 	int i, ret;
     64 
     65 	ret = -1;
     66 	for (i = 0; coord[i] != NULL; i++)
     67 		ret = MAX(ret, ptableval(coord[i], state[i].val));
     68 
     69 	return ret;
     70 }
     71 
     72 static bool
     73 trivialshorten(DfsArg *arg)
     74 {
     75 	int bound;
     76 
     77 	if (!commute(arg->last[0], arg->last[1]))
     78 		return false;
     79 
     80 	dfs_move(inverse_move(arg->last[1]), arg);
     81 	bound = lower_bound(arg->s->coord, arg->state);
     82 	dfs_move(arg->last[1], arg);
     83 
     84 	return bound == 0;
     85 }
     86 
     87 static void
     88 dfs(DfsArg *arg)
     89 {
     90 	Move m, last[2];
     91 	bool len, niss;
     92 	int bound;
     93 
     94 	bound = lower_bound(arg->s->coord, arg->state);
     95 	if (arg->st == NISS && !arg->niss)
     96 		bound = MIN(1, bound);
     97 
     98 	if (bound + arg->current_alg->len > arg->d)
     99 		return;
    100 
    101 	if (bound == 0) {
    102 		len = arg->current_alg->len == arg->d;
    103 		niss = !(arg->st == NISS) || arg->has_nissed;
    104 		if (len && niss && !trivialshorten(arg))
    105 			append_sol(arg);
    106 		return;
    107 	}
    108 
    109 	last[0] = arg->last[0];
    110 	last[1] = arg->last[1];
    111 	arg->last[1] = arg->last[0];
    112 	for (m = U; m <= B3; m++) {
    113 		if (!arg->s->moveset(m))
    114 			continue;
    115 		if (allowed_next(m, last[0], last[1])) {
    116 			arg->last[0] = m;
    117 			append_move(arg->current_alg, m, arg->niss);
    118 			dfs_move(m, arg);
    119 			dfs(arg);
    120 			dfs_move(inverse_move(m), arg);
    121 			arg->current_alg->len--;
    122 		}
    123 	}
    124 	arg->last[0] = last[0];
    125 	arg->last[1] = last[1];
    126 
    127 	if (niss_makes_sense(arg))
    128 		dfs_niss(arg);
    129 }
    130 
    131 static void
    132 dfs_niss(DfsArg *arg)
    133 {
    134 	int i;
    135 	DfsArg newarg;
    136 	Cube c, newcube;
    137 
    138 	newarg.s           = arg->s;
    139 	newarg.t           = arg->t;
    140 	newarg.st          = arg->st;
    141 	newarg.d           = arg->d;
    142 	newarg.sol         = arg->sol;
    143 	newarg.current_alg = arg->current_alg;
    144 
    145 	/* Invert current alg and scramble */
    146 	newarg.cube = &newcube;
    147 
    148 	make_solved(newarg.cube);
    149 	apply_alg(arg->current_alg, newarg.cube);
    150 	invert_cube(newarg.cube);
    151 
    152 	copy_cube(arg->cube, &c);
    153 	invert_cube(&c);
    154 	compose(&c, newarg.cube);
    155 
    156 	/* New indexes */
    157 	get_state(newarg.s->coord, newarg.cube, newarg.state);
    158 
    159 	/* Swap last moves */
    160 	for (i = 0; i < 2; i++) {
    161 		newarg.last[i] = arg->lastinv[i];
    162 		newarg.lastinv[i] = arg->last[i];
    163 	}
    164 
    165 	newarg.niss = true;
    166 	newarg.has_nissed = true;
    167 
    168 	dfs(&newarg);
    169 }
    170 
    171 static void
    172 dfs_move(Move m, DfsArg *arg)
    173 {
    174 	int i;
    175 	Move mm;
    176 	Trans tt = uf; /* Avoid uninitialized warning */
    177 
    178 	for (i = 0; arg->s->coord[i] != NULL; i++) {
    179 		mm = transform_move(arg->state[i].t, m);
    180 		arg->state[i].val = move_coord(
    181 		    arg->s->coord[i], mm, arg->state[i].val, &tt);
    182 		arg->state[i].t = transform_trans(tt, arg->state[i].t);
    183 	}
    184 }
    185 
    186 static bool
    187 niss_makes_sense(DfsArg *arg)
    188 {
    189 	Cube testcube;
    190 	CubeState state[MAX_N_COORD];
    191 	bool b1, b2, comm;
    192 
    193 	if (arg->niss || !(arg->st == NISS) || arg->current_alg->len == 0)
    194 		return false;
    195 
    196 	make_solved(&testcube);
    197 	apply_move(inverse_move(arg->last[0]), &testcube);
    198 	get_state(arg->s->coord, &testcube, state);
    199 	b1 = lower_bound(arg->s->coord, state) > 0;
    200 
    201 	make_solved(&testcube);
    202 	apply_move(inverse_move(arg->last[1]), &testcube);
    203 	get_state(arg->s->coord, &testcube, state);
    204 	b2 = lower_bound(arg->s->coord, state) > 0;
    205 
    206 	comm = commute(arg->last[0], arg->last[1]);
    207 
    208 	return b1 > 0 && !(comm && b2 == 0);
    209 }
    210 
    211 int
    212 solve(Step *s, Trans t, int d, SolutionType st, Cube *c, char *sol)
    213 {
    214 	Alg alg;
    215 	DfsArg arg;
    216 
    217 	arg.niss        = false;
    218 	arg.has_nissed  = false;
    219 	arg.last[0]     = NULLMOVE;
    220 	arg.last[1]     = NULLMOVE;
    221 	arg.lastinv[0]  = NULLMOVE;
    222 	arg.lastinv[1]  = NULLMOVE;
    223 
    224 	alg.len = 0;
    225 	arg.current_alg = &alg;
    226 
    227 	arg.cube = c;
    228 	arg.s = s;
    229 	arg.t = t;
    230 	arg.st = st;
    231 
    232 	arg.d = d;
    233 	arg.sol = &sol;
    234 
    235 	if (arg.st == INVERSE)
    236 		invert_cube(c);
    237 	apply_trans(arg.t, c);
    238 	get_state(arg.s->coord, arg.cube, arg.state);
    239 
    240 	dfs(&arg);
    241 	return 0;
    242 }