aboutsummaryrefslogtreecommitdiff
path: root/old/2021-11-10-beforeremovingchecker/solve.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--old/2021-11-10-beforeremovingchecker/solve.c209
1 files changed, 0 insertions, 209 deletions
diff --git a/old/2021-11-10-beforeremovingchecker/solve.c b/old/2021-11-10-beforeremovingchecker/solve.c
deleted file mode 100644
index af685ec..0000000
--- a/old/2021-11-10-beforeremovingchecker/solve.c
+++ /dev/null
@@ -1,209 +0,0 @@
1#include "solve.h"
2
3/* Local functions ***********************************************************/
4
5static bool allowed_next(Move move, DfsData *dd);
6static void dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
7static void dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd);
8static bool dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd);
9static void dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
10static bool dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
11
12/* Local functions ***********************************************************/
13
14static bool
15allowed_next(Move move, DfsData *dd)
16{
17
18/* TODO: remove the commented part, was added to moves.c
19 static bool initialized = false;
20 static bool commute[NMOVES][NMOVES], pnext[NMOVES][NMOVES][NMOVES];
21
22 if (!initialized) {
23 Cube c1, c2;
24 int i, j, k;
25 bool p1, p2, cij;
26
27 for (i = 0; i < NMOVES; i++) {
28 for (j = 0; j < NMOVES; j++) {
29 c1 = apply_move(i, apply_move(j, (Cube){0}));
30 c2 = apply_move(j, apply_move(i, (Cube){0}));
31 commute[i][j] = equal(c1, c2) && i && j;
32 for (k = 0; k < NMOVES; k++) {
33 p1 = j && base_move(j) == base_move(k);
34 p2 = i && base_move(i) == base_move(k);
35 cij = commute[i][j];
36 pnext[i][j][k] = !(p1 || (cij && p2));
37 }
38 }
39 }
40
41 initialized = true;
42 }
43
44 if (!pnext[dd->last2][dd->last1][move])
45 return false;
46
47 if (commute[dd->last1][move])
48 return dd->move_position[dd->last1] < dd->move_position[move];
49
50 return true;
51*/
52
53 if (!possible_next(dd->last2, dd->last1, move))
54 return false;
55
56 if (commute(dd->last1, move))
57 return dd->move_position[dd->last1] < dd->move_position[move];
58
59 return true;
60}
61
62static void
63dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
64{
65 if (dfs_stop(c, s, opts, dd))
66 return;
67
68 if (dfs_check_solved(s, opts, dd))
69 return;
70
71 dfs_branch(c, s, opts, dd);
72
73 if (opts->can_niss && !dd->niss)
74 dfs_niss(c, s, opts, dd);
75}
76
77static void
78dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
79{
80 Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves;
81
82 int i, maxnsol = opts->max_solutions;
83
84 for (i = 0; moves[i] != NULLMOVE && dd->sols->len < maxnsol; i++) {
85 m = moves[i];
86 if (allowed_next(m, dd)) {
87 dd->last2 = dd->last1;
88 dd->last1 = m;
89 append_move(dd->current_alg, m, dd->niss);
90
91 dfs(apply_move(m, c), s, opts, dd);
92
93 dd->current_alg->len--;
94 dd->last2 = l2;
95 dd->last1 = l1;
96 }
97 }
98}
99
100static bool
101dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd)
102{
103 if (dd->lb != 0)
104 return false;
105
106 if (dd->current_alg->len == dd->d) {
107 if (s->is_valid(dd->current_alg) || opts->all)
108 append_alg(dd->sols, dd->current_alg);
109
110 if (opts->feedback)
111 print_alg(dd->current_alg, false);
112 }
113
114 return true;
115}
116
117static void
118dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
119{
120 Move l1 = dd->last1, l2 = dd->last2;
121 CubeTarget ct;
122
123 ct.cube = apply_move(inverse_move(l1), (Cube){0});
124 ct.target = 1;
125
126 if (dd->current_alg->len == 0 || s->estimate(ct)) {
127 dd->niss = true;
128 dd->last1 = NULLMOVE;
129 dd->last2 = NULLMOVE;
130
131 dfs(inverse_cube(c), s, opts, dd);
132
133 dd->last1 = l1;
134 dd->last2 = l2;
135 dd->niss = false;
136 }
137}
138
139static bool
140dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
141{
142 CubeTarget ct = {
143 .cube = c,
144 .target = dd->d - dd->current_alg->len
145 };
146
147 if (dd->sols->len >= opts->max_solutions)
148 return true;
149
150 dd->lb = s->estimate(ct);
151 if (opts->can_niss && !dd->niss)
152 dd->lb = MIN(1, dd->lb);
153
154 if (dd->current_alg->len + dd->lb > dd->d)
155 return true;
156
157 return false;
158}
159
160/* Public functions **********************************************************/
161
162AlgList *
163solve(Cube cube, Step *step, SolveOptions *opts)
164{
165 AlgListNode *node;
166 AlgList *sols = new_alglist();
167 Cube c;
168
169 if (step->detect != NULL)
170 step->pre_trans = step->detect(cube);
171 c = apply_trans(step->pre_trans, cube);
172
173 DfsData dd = {
174 .m = 0,
175 .niss = false,
176 .lb = -1,
177 .last1 = NULLMOVE,
178 .last2 = NULLMOVE,
179 .sols = sols,
180 .current_alg = new_alg("")
181 };
182
183 if (step->ready != NULL && !step->ready(c)) {
184 fprintf(stderr, "Cube not ready for solving step: ");
185 fprintf(stderr, "%s\n", step->ready_msg);
186 return sols;
187 }
188
189 moveset_to_list(step->moveset, dd.sorted_moves);
190 movelist_to_position(dd.sorted_moves, dd.move_position);
191
192 for (dd.d = opts->min_moves;
193 dd.d <= opts->max_moves &&
194 !(sols->len && opts->optimal_only) &&
195 sols->len < opts->max_solutions;
196 dd.d++) {
197 if (opts->feedback)
198 fprintf(stderr,
199 "Found %d solutions, searching depth %d...\n",
200 sols->len, dd.d);
201 dfs(c, step, opts, &dd);
202 }
203
204 for (node = sols->first; node != NULL; node = node->next)
205 transform_alg(inverse_trans(step->pre_trans), node->alg);
206
207 free_alg(dd.current_alg);
208 return sols;
209}

Generated with cgit - Back to sebastiano.tronto.net