diff options
Diffstat (limited to 'apps/plugins/puzzles/src/dominosa.c')
-rw-r--r-- | apps/plugins/puzzles/src/dominosa.c | 2688 |
1 files changed, 2220 insertions, 468 deletions
diff --git a/apps/plugins/puzzles/src/dominosa.c b/apps/plugins/puzzles/src/dominosa.c index 5f035e9250..67a1d69c91 100644 --- a/apps/plugins/puzzles/src/dominosa.c +++ b/apps/plugins/puzzles/src/dominosa.c | |||
@@ -5,65 +5,41 @@ | |||
5 | */ | 5 | */ |
6 | 6 | ||
7 | /* | 7 | /* |
8 | * TODO: | 8 | * Further possible deduction types in the solver: |
9 | * | ||
10 | * - improve solver so as to use more interesting forms of | ||
11 | * deduction | ||
12 | * | 9 | * |
13 | * * rule out a domino placement if it would divide an unfilled | 10 | * * possibly an advanced form of deduce_parity via 2-connectedness. |
14 | * region such that at least one resulting region had an odd | 11 | * We currently deal with areas of the graph with exactly one way |
15 | * area | 12 | * in and out; but if you have an area with exactly _two_ routes in |
16 | * + Tarjan's bridge-finding algorithm would be a way to find | 13 | * and out of it, then you can at least decide on the _relative_ |
17 | * domino placements that split a connected region in two: | 14 | * parity of the two (either 'these two edges both bisect dominoes |
18 | * form the graph whose vertices are unpaired squares and | 15 | * or neither do', or 'exactly one of these edges bisects a |
19 | * whose edges are potential (not placed but also not ruled | 16 | * domino'). And occasionally that can be enough to let you rule |
20 | * out) dominoes covering two of them, and any bridge in that | 17 | * out one of the two remaining choices. |
21 | * graph is a candidate. | 18 | * + For example, if both those edges bisect a domino, then those |
22 | * + Then, finding any old spanning forest of the unfilled | 19 | * two dominoes would also be both the same. |
23 | * squares should be sufficient to determine the area parity | 20 | * + Or perhaps between them they rule out all possibilities for |
24 | * of the region that any such placement would cut off. | 21 | * some other square. |
22 | * + Or perhaps they themselves would be duplicates! | ||
23 | * + Or perhaps, on purely geometric grounds, they would box in a | ||
24 | * square to the point where it ended up having to be an | ||
25 | * isolated singleton. | ||
26 | * + The tricky part of this is how you do the graph theory. | ||
27 | * Perhaps a modified form of Tarjan's bridge-finding algorithm | ||
28 | * would work, but I haven't thought through the details. | ||
25 | * | 29 | * |
26 | * * set analysis | 30 | * * possibly an advanced version of set analysis which doesn't have |
27 | * + look at all unclaimed squares containing a given number | 31 | * to start from squares all having the same number? For example, |
28 | * + for each one, find the set of possible numbers that it | 32 | * if you have three mutually non-adjacent squares labelled 1,2,3 |
29 | * can connect to (i.e. each neighbouring tile such that | 33 | * such that the numbers adjacent to each are precisely the other |
30 | * the placement between it and that neighbour has not yet | 34 | * two, then set analysis can work just fine in principle, and |
31 | * been ruled out) | 35 | * tells you that those three squares must overlap the three |
32 | * + now proceed similarly to Solo set analysis: try to find | 36 | * dominoes 1-2, 2-3 and 1-3 in some order, so you can rule out any |
33 | * a subset of the squares such that the union of their | 37 | * placements of those elsewhere. |
34 | * possible numbers is the same size as the subset. If so, | 38 | * + the difficulty with this is how you avoid it going painfully |
35 | * rule out those possible numbers for all other squares. | 39 | * exponential-time. You can't iterate over all the subsets, so |
36 | * * important wrinkle: the double dominoes complicate | 40 | * you'd need some kind of more sophisticated directed search. |
37 | * matters. Connecting a number to itself uses up _two_ | 41 | * + and the adjacency allowance has to be similarly accounted |
38 | * of the unclaimed squares containing a number. Thus, | 42 | * for, which could get tricky to keep track of. |
39 | * when finding the initial subset we must never | ||
40 | * include two adjacent squares; and also, when ruling | ||
41 | * things out after finding the subset, we must be | ||
42 | * careful that we don't rule out precisely the domino | ||
43 | * placement that was _included_ in our set! | ||
44 | * | ||
45 | * * playing off the two ends of one potential domino, by | ||
46 | * considering the alternatives to that domino that each end | ||
47 | * might otherwise be part of. | ||
48 | * + if not playing this domino would require each end to be | ||
49 | * part of an identical domino, play it. (e.g. the middle of | ||
50 | * 5-4-4-5) | ||
51 | * + if not playing this domino would guarantee that the two | ||
52 | * ends between them used up all of some other square's | ||
53 | * choices, play it. (e.g. the middle of 2-3-3-1 if another 3 | ||
54 | * cell can only link to a 2 or a 1) | ||
55 | * | ||
56 | * * identify 'forcing chains', in the sense of any path of cells | ||
57 | * each of which has only two possible dominoes to be part of, | ||
58 | * and each of those rules out one of the choices for the next | ||
59 | * cell. Such a chain has the property that either all the odd | ||
60 | * dominoes are placed, or all the even ones are placed; so if | ||
61 | * either set of those introduces a conflict (e.g. a dupe within | ||
62 | * the chain, or using up all of some other square's choices), | ||
63 | * then the whole set can be ruled out, and the other set played | ||
64 | * immediately. | ||
65 | * + this is of course a generalisation of the previous idea, | ||
66 | * which is simply a forcing chain of length 3. | ||
67 | */ | 43 | */ |
68 | 44 | ||
69 | #include <stdio.h> | 45 | #include <stdio.h> |
@@ -84,6 +60,26 @@ | |||
84 | 60 | ||
85 | #define FLASH_TIME 0.13F | 61 | #define FLASH_TIME 0.13F |
86 | 62 | ||
63 | /* | ||
64 | * Difficulty levels. I do some macro ickery here to ensure that my | ||
65 | * enum and the various forms of my name list always match up. | ||
66 | */ | ||
67 | #define DIFFLIST(X) \ | ||
68 | X(TRIVIAL,Trivial,t) \ | ||
69 | X(BASIC,Basic,b) \ | ||
70 | X(HARD,Hard,h) \ | ||
71 | X(EXTREME,Extreme,e) \ | ||
72 | X(AMBIGUOUS,Ambiguous,a) \ | ||
73 | /* end of list */ | ||
74 | #define ENUM(upper,title,lower) DIFF_ ## upper, | ||
75 | #define TITLE(upper,title,lower) #title, | ||
76 | #define ENCODE(upper,title,lower) #lower | ||
77 | #define CONFIG(upper,title,lower) ":" #title | ||
78 | enum { DIFFLIST(ENUM) DIFFCOUNT }; | ||
79 | static char const *const dominosa_diffnames[] = { DIFFLIST(TITLE) }; | ||
80 | static char const dominosa_diffchars[] = DIFFLIST(ENCODE); | ||
81 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
82 | |||
87 | enum { | 83 | enum { |
88 | COL_BACKGROUND, | 84 | COL_BACKGROUND, |
89 | COL_TEXT, | 85 | COL_TEXT, |
@@ -98,7 +94,7 @@ enum { | |||
98 | 94 | ||
99 | struct game_params { | 95 | struct game_params { |
100 | int n; | 96 | int n; |
101 | bool unique; | 97 | int diff; |
102 | }; | 98 | }; |
103 | 99 | ||
104 | struct game_numbers { | 100 | struct game_numbers { |
@@ -125,35 +121,41 @@ static game_params *default_params(void) | |||
125 | game_params *ret = snew(game_params); | 121 | game_params *ret = snew(game_params); |
126 | 122 | ||
127 | ret->n = 6; | 123 | ret->n = 6; |
128 | ret->unique = true; | 124 | ret->diff = DIFF_BASIC; |
129 | 125 | ||
130 | return ret; | 126 | return ret; |
131 | } | 127 | } |
132 | 128 | ||
133 | static bool game_fetch_preset(int i, char **name, game_params **params) | 129 | static const struct game_params dominosa_presets[] = { |
130 | { 3, DIFF_TRIVIAL }, | ||
131 | { 4, DIFF_TRIVIAL }, | ||
132 | { 5, DIFF_TRIVIAL }, | ||
133 | { 6, DIFF_TRIVIAL }, | ||
134 | { 4, DIFF_BASIC }, | ||
135 | { 5, DIFF_BASIC }, | ||
136 | { 6, DIFF_BASIC }, | ||
137 | { 7, DIFF_BASIC }, | ||
138 | { 8, DIFF_BASIC }, | ||
139 | { 9, DIFF_BASIC }, | ||
140 | { 6, DIFF_HARD }, | ||
141 | { 6, DIFF_EXTREME }, | ||
142 | }; | ||
143 | |||
144 | static bool game_fetch_preset(int i, char **name, game_params **params_out) | ||
134 | { | 145 | { |
135 | game_params *ret; | 146 | game_params *params; |
136 | int n; | ||
137 | char buf[80]; | 147 | char buf[80]; |
138 | 148 | ||
139 | switch (i) { | 149 | if (i < 0 || i >= lenof(dominosa_presets)) |
140 | case 0: n = 3; break; | 150 | return false; |
141 | case 1: n = 4; break; | ||
142 | case 2: n = 5; break; | ||
143 | case 3: n = 6; break; | ||
144 | case 4: n = 7; break; | ||
145 | case 5: n = 8; break; | ||
146 | case 6: n = 9; break; | ||
147 | default: return false; | ||
148 | } | ||
149 | 151 | ||
150 | sprintf(buf, "Up to double-%d", n); | 152 | params = snew(game_params); |
151 | *name = dupstr(buf); | 153 | *params = dominosa_presets[i]; /* structure copy */ |
152 | 154 | ||
153 | *params = ret = snew(game_params); | 155 | sprintf(buf, "Order %d, %s", params->n, dominosa_diffnames[params->diff]); |
154 | ret->n = n; | ||
155 | ret->unique = true; | ||
156 | 156 | ||
157 | *name = dupstr(buf); | ||
158 | *params_out = params; | ||
157 | return true; | 159 | return true; |
158 | } | 160 | } |
159 | 161 | ||
@@ -171,18 +173,36 @@ static game_params *dup_params(const game_params *params) | |||
171 | 173 | ||
172 | static void decode_params(game_params *params, char const *string) | 174 | static void decode_params(game_params *params, char const *string) |
173 | { | 175 | { |
174 | params->n = atoi(string); | 176 | const char *p = string; |
175 | while (*string && isdigit((unsigned char)*string)) string++; | 177 | |
176 | if (*string == 'a') | 178 | params->n = atoi(p); |
177 | params->unique = false; | 179 | while (*p && isdigit((unsigned char)*p)) p++; |
180 | |||
181 | while (*p) { | ||
182 | char c = *p++; | ||
183 | if (c == 'a') { | ||
184 | /* Legacy encoding from before the difficulty system */ | ||
185 | params->diff = DIFF_AMBIGUOUS; | ||
186 | } else if (c == 'd') { | ||
187 | int i; | ||
188 | params->diff = DIFFCOUNT+1; /* ...which is invalid */ | ||
189 | if (*p) { | ||
190 | for (i = 0; i < DIFFCOUNT; i++) { | ||
191 | if (*p == dominosa_diffchars[i]) | ||
192 | params->diff = i; | ||
193 | } | ||
194 | p++; | ||
195 | } | ||
196 | } | ||
197 | } | ||
178 | } | 198 | } |
179 | 199 | ||
180 | static char *encode_params(const game_params *params, bool full) | 200 | static char *encode_params(const game_params *params, bool full) |
181 | { | 201 | { |
182 | char buf[80]; | 202 | char buf[80]; |
183 | sprintf(buf, "%d", params->n); | 203 | int len = sprintf(buf, "%d", params->n); |
184 | if (full && !params->unique) | 204 | if (full) |
185 | strcat(buf, "a"); | 205 | len += sprintf(buf + len, "d%c", dominosa_diffchars[params->diff]); |
186 | return dupstr(buf); | 206 | return dupstr(buf); |
187 | } | 207 | } |
188 | 208 | ||
@@ -198,9 +218,10 @@ static config_item *game_configure(const game_params *params) | |||
198 | sprintf(buf, "%d", params->n); | 218 | sprintf(buf, "%d", params->n); |
199 | ret[0].u.string.sval = dupstr(buf); | 219 | ret[0].u.string.sval = dupstr(buf); |
200 | 220 | ||
201 | ret[1].name = "Ensure unique solution"; | 221 | ret[1].name = "Difficulty"; |
202 | ret[1].type = C_BOOLEAN; | 222 | ret[1].type = C_CHOICES; |
203 | ret[1].u.boolean.bval = params->unique; | 223 | ret[1].u.choices.choicenames = DIFFCONFIG; |
224 | ret[1].u.choices.selected = params->diff; | ||
204 | 225 | ||
205 | ret[2].name = NULL; | 226 | ret[2].name = NULL; |
206 | ret[2].type = C_END; | 227 | ret[2].type = C_END; |
@@ -213,7 +234,7 @@ static game_params *custom_params(const config_item *cfg) | |||
213 | game_params *ret = snew(game_params); | 234 | game_params *ret = snew(game_params); |
214 | 235 | ||
215 | ret->n = atoi(cfg[0].u.string.sval); | 236 | ret->n = atoi(cfg[0].u.string.sval); |
216 | ret->unique = cfg[1].u.boolean.bval; | 237 | ret->diff = cfg[1].u.choices.selected; |
217 | 238 | ||
218 | return ret; | 239 | return ret; |
219 | } | 240 | } |
@@ -222,6 +243,8 @@ static const char *validate_params(const game_params *params, bool full) | |||
222 | { | 243 | { |
223 | if (params->n < 1) | 244 | if (params->n < 1) |
224 | return "Maximum face number must be at least one"; | 245 | return "Maximum face number must be at least one"; |
246 | if (params->diff >= DIFFCOUNT) | ||
247 | return "Unknown difficulty rating"; | ||
225 | return NULL; | 248 | return NULL; |
226 | } | 249 | } |
227 | 250 | ||
@@ -229,361 +252,1993 @@ static const char *validate_params(const game_params *params, bool full) | |||
229 | * Solver. | 252 | * Solver. |
230 | */ | 253 | */ |
231 | 254 | ||
232 | static int find_overlaps(int w, int h, int placement, int *set) | 255 | #ifdef STANDALONE_SOLVER |
256 | #define SOLVER_DIAGNOSTICS | ||
257 | bool solver_diagnostics = false; | ||
258 | #elif defined SOLVER_DIAGNOSTICS | ||
259 | const bool solver_diagnostics = true; | ||
260 | #endif | ||
261 | |||
262 | struct solver_domino; | ||
263 | struct solver_placement; | ||
264 | |||
265 | /* | ||
266 | * Information about a particular domino. | ||
267 | */ | ||
268 | struct solver_domino { | ||
269 | /* The numbers on the domino, and its index in the dominoes array. */ | ||
270 | int lo, hi, index; | ||
271 | |||
272 | /* List of placements not yet ruled out for this domino. */ | ||
273 | int nplacements; | ||
274 | struct solver_placement **placements; | ||
275 | |||
276 | #ifdef SOLVER_DIAGNOSTICS | ||
277 | /* A textual name we can easily reuse in solver diagnostics. */ | ||
278 | char *name; | ||
279 | #endif | ||
280 | }; | ||
281 | |||
282 | /* | ||
283 | * Information about a particular 'placement' (i.e. specific location | ||
284 | * that a domino might go in). | ||
285 | */ | ||
286 | struct solver_placement { | ||
287 | /* The index of this placement in sc->placements. */ | ||
288 | int index; | ||
289 | |||
290 | /* The two squares that make up this placement. */ | ||
291 | struct solver_square *squares[2]; | ||
292 | |||
293 | /* The domino that has to go in this position, if any. */ | ||
294 | struct solver_domino *domino; | ||
295 | |||
296 | /* The index of this placement in each square's placements array, | ||
297 | * and in that of the domino. */ | ||
298 | int spi[2], dpi; | ||
299 | |||
300 | /* Whether this is still considered a possible placement. */ | ||
301 | bool active; | ||
302 | |||
303 | /* Other domino placements that overlap with this one. (Maximum 6: | ||
304 | * three overlapping each square of the placement.) */ | ||
305 | int noverlaps; | ||
306 | struct solver_placement *overlaps[6]; | ||
307 | |||
308 | #ifdef SOLVER_DIAGNOSTICS | ||
309 | /* A textual name we can easily reuse in solver diagnostics. */ | ||
310 | char *name; | ||
311 | #endif | ||
312 | }; | ||
313 | |||
314 | /* | ||
315 | * Information about a particular solver square. | ||
316 | */ | ||
317 | struct solver_square { | ||
318 | /* The coordinates of the square, and its index in a normal grid array. */ | ||
319 | int x, y, index; | ||
320 | |||
321 | /* List of domino placements not yet ruled out for this square. */ | ||
322 | int nplacements; | ||
323 | struct solver_placement *placements[4]; | ||
324 | |||
325 | /* The number in the square. */ | ||
326 | int number; | ||
327 | |||
328 | #ifdef SOLVER_DIAGNOSTICS | ||
329 | /* A textual name we can easily reuse in solver diagnostics. */ | ||
330 | char *name; | ||
331 | #endif | ||
332 | }; | ||
333 | |||
334 | struct solver_scratch { | ||
335 | int n, dc, pc, w, h, wh; | ||
336 | int max_diff_used; | ||
337 | struct solver_domino *dominoes; | ||
338 | struct solver_placement *placements; | ||
339 | struct solver_square *squares; | ||
340 | struct solver_placement **domino_placement_lists; | ||
341 | struct solver_square **squares_by_number; | ||
342 | struct findloopstate *fls; | ||
343 | bool squares_by_number_initialised; | ||
344 | int *wh_scratch, *pc_scratch, *pc_scratch2, *dc_scratch; | ||
345 | }; | ||
346 | |||
347 | static struct solver_scratch *solver_make_scratch(int n) | ||
233 | { | 348 | { |
234 | int x, y, n; | 349 | int dc = DCOUNT(n), w = n+2, h = n+1, wh = w*h; |
350 | int pc = (w-1)*h + w*(h-1); | ||
351 | struct solver_scratch *sc = snew(struct solver_scratch); | ||
352 | int hi, lo, di, x, y, pi, si; | ||
353 | |||
354 | sc->n = n; | ||
355 | sc->dc = dc; | ||
356 | sc->pc = pc; | ||
357 | sc->w = w; | ||
358 | sc->h = h; | ||
359 | sc->wh = wh; | ||
360 | |||
361 | sc->dominoes = snewn(dc, struct solver_domino); | ||
362 | sc->placements = snewn(pc, struct solver_placement); | ||
363 | sc->squares = snewn(wh, struct solver_square); | ||
364 | sc->domino_placement_lists = snewn(pc, struct solver_placement *); | ||
365 | sc->fls = findloop_new_state(wh); | ||
366 | |||
367 | for (di = hi = 0; hi <= n; hi++) { | ||
368 | for (lo = 0; lo <= hi; lo++) { | ||
369 | assert(di == DINDEX(hi, lo)); | ||
370 | sc->dominoes[di].hi = hi; | ||
371 | sc->dominoes[di].lo = lo; | ||
372 | sc->dominoes[di].index = di; | ||
235 | 373 | ||
236 | n = 0; /* number of returned placements */ | 374 | #ifdef SOLVER_DIAGNOSTICS |
375 | { | ||
376 | char buf[128]; | ||
377 | sprintf(buf, "%d-%d", hi, lo); | ||
378 | sc->dominoes[di].name = dupstr(buf); | ||
379 | } | ||
380 | #endif | ||
237 | 381 | ||
238 | x = placement / 2; | 382 | di++; |
239 | y = x / w; | 383 | } |
240 | x %= w; | 384 | } |
241 | 385 | ||
242 | if (placement & 1) { | 386 | for (y = 0; y < h; y++) { |
243 | /* | 387 | for (x = 0; x < w; x++) { |
244 | * Horizontal domino, indexed by its left end. | 388 | struct solver_square *sq = &sc->squares[y*w+x]; |
245 | */ | 389 | sq->x = x; |
246 | if (x > 0) | 390 | sq->y = y; |
247 | set[n++] = placement-2; /* horizontal domino to the left */ | 391 | sq->index = y * w + x; |
248 | if (y > 0) | 392 | sq->nplacements = 0; |
249 | set[n++] = placement-2*w-1;/* vertical domino above left side */ | 393 | |
250 | if (y+1 < h) | 394 | #ifdef SOLVER_DIAGNOSTICS |
251 | set[n++] = placement-1; /* vertical domino below left side */ | 395 | { |
252 | if (x+2 < w) | 396 | char buf[128]; |
253 | set[n++] = placement+2; /* horizontal domino to the right */ | 397 | sprintf(buf, "(%d,%d)", x, y); |
254 | if (y > 0) | 398 | sq->name = dupstr(buf); |
255 | set[n++] = placement-2*w+2-1;/* vertical domino above right side */ | 399 | } |
256 | if (y+1 < h) | 400 | #endif |
257 | set[n++] = placement+2-1; /* vertical domino below right side */ | 401 | } |
258 | } else { | ||
259 | /* | ||
260 | * Vertical domino, indexed by its top end. | ||
261 | */ | ||
262 | if (y > 0) | ||
263 | set[n++] = placement-2*w; /* vertical domino above */ | ||
264 | if (x > 0) | ||
265 | set[n++] = placement-2+1; /* horizontal domino left of top */ | ||
266 | if (x+1 < w) | ||
267 | set[n++] = placement+1; /* horizontal domino right of top */ | ||
268 | if (y+2 < h) | ||
269 | set[n++] = placement+2*w; /* vertical domino below */ | ||
270 | if (x > 0) | ||
271 | set[n++] = placement-2+2*w+1;/* horizontal domino left of bottom */ | ||
272 | if (x+1 < w) | ||
273 | set[n++] = placement+2*w+1;/* horizontal domino right of bottom */ | ||
274 | } | 402 | } |
275 | 403 | ||
276 | return n; | 404 | pi = 0; |
405 | for (y = 0; y < h-1; y++) { | ||
406 | for (x = 0; x < w; x++) { | ||
407 | assert(pi < pc); | ||
408 | sc->placements[pi].squares[0] = &sc->squares[y*w+x]; | ||
409 | sc->placements[pi].squares[1] = &sc->squares[(y+1)*w+x]; | ||
410 | #ifdef SOLVER_DIAGNOSTICS | ||
411 | { | ||
412 | char buf[128]; | ||
413 | sprintf(buf, "(%d,%d-%d)", x, y, y+1); | ||
414 | sc->placements[pi].name = dupstr(buf); | ||
415 | } | ||
416 | #endif | ||
417 | pi++; | ||
418 | } | ||
419 | } | ||
420 | for (y = 0; y < h; y++) { | ||
421 | for (x = 0; x < w-1; x++) { | ||
422 | assert(pi < pc); | ||
423 | sc->placements[pi].squares[0] = &sc->squares[y*w+x]; | ||
424 | sc->placements[pi].squares[1] = &sc->squares[y*w+(x+1)]; | ||
425 | #ifdef SOLVER_DIAGNOSTICS | ||
426 | { | ||
427 | char buf[128]; | ||
428 | sprintf(buf, "(%d-%d,%d)", x, x+1, y); | ||
429 | sc->placements[pi].name = dupstr(buf); | ||
430 | } | ||
431 | #endif | ||
432 | pi++; | ||
433 | } | ||
434 | } | ||
435 | assert(pi == pc); | ||
436 | |||
437 | /* Set up the full placement lists for all squares, temporarily, | ||
438 | * so as to use them to calculate the overlap lists */ | ||
439 | for (si = 0; si < wh; si++) | ||
440 | sc->squares[si].nplacements = 0; | ||
441 | for (pi = 0; pi < pc; pi++) { | ||
442 | struct solver_placement *p = &sc->placements[pi]; | ||
443 | for (si = 0; si < 2; si++) { | ||
444 | struct solver_square *sq = p->squares[si]; | ||
445 | p->spi[si] = sq->nplacements; | ||
446 | sq->placements[sq->nplacements++] = p; | ||
447 | } | ||
448 | } | ||
449 | |||
450 | /* Actually calculate the overlap lists */ | ||
451 | for (pi = 0; pi < pc; pi++) { | ||
452 | struct solver_placement *p = &sc->placements[pi]; | ||
453 | p->noverlaps = 0; | ||
454 | for (si = 0; si < 2; si++) { | ||
455 | struct solver_square *sq = p->squares[si]; | ||
456 | int j; | ||
457 | for (j = 0; j < sq->nplacements; j++) { | ||
458 | struct solver_placement *q = sq->placements[j]; | ||
459 | if (q != p) | ||
460 | p->overlaps[p->noverlaps++] = q; | ||
461 | } | ||
462 | } | ||
463 | } | ||
464 | |||
465 | /* Fill in the index field of the placements */ | ||
466 | for (pi = 0; pi < pc; pi++) | ||
467 | sc->placements[pi].index = pi; | ||
468 | |||
469 | /* Lazily initialised by particular solver techniques that might | ||
470 | * never be needed */ | ||
471 | sc->squares_by_number = NULL; | ||
472 | sc->squares_by_number_initialised = false; | ||
473 | sc->wh_scratch = NULL; | ||
474 | sc->pc_scratch = sc->pc_scratch2 = NULL; | ||
475 | sc->dc_scratch = NULL; | ||
476 | |||
477 | return sc; | ||
478 | } | ||
479 | |||
480 | static void solver_free_scratch(struct solver_scratch *sc) | ||
481 | { | ||
482 | #ifdef SOLVER_DIAGNOSTICS | ||
483 | { | ||
484 | int i; | ||
485 | for (i = 0; i < sc->dc; i++) | ||
486 | sfree(sc->dominoes[i].name); | ||
487 | for (i = 0; i < sc->pc; i++) | ||
488 | sfree(sc->placements[i].name); | ||
489 | for (i = 0; i < sc->wh; i++) | ||
490 | sfree(sc->squares[i].name); | ||
491 | } | ||
492 | #endif | ||
493 | sfree(sc->dominoes); | ||
494 | sfree(sc->placements); | ||
495 | sfree(sc->squares); | ||
496 | sfree(sc->domino_placement_lists); | ||
497 | sfree(sc->squares_by_number); | ||
498 | findloop_free_state(sc->fls); | ||
499 | sfree(sc->wh_scratch); | ||
500 | sfree(sc->pc_scratch); | ||
501 | sfree(sc->pc_scratch2); | ||
502 | sfree(sc->dc_scratch); | ||
503 | sfree(sc); | ||
504 | } | ||
505 | |||
506 | static void solver_setup_grid(struct solver_scratch *sc, const int *numbers) | ||
507 | { | ||
508 | int i, j; | ||
509 | |||
510 | for (i = 0; i < sc->wh; i++) { | ||
511 | sc->squares[i].nplacements = 0; | ||
512 | sc->squares[i].number = numbers[sc->squares[i].index]; | ||
513 | } | ||
514 | |||
515 | for (i = 0; i < sc->pc; i++) { | ||
516 | struct solver_placement *p = &sc->placements[i]; | ||
517 | int di = DINDEX(p->squares[0]->number, p->squares[1]->number); | ||
518 | p->domino = &sc->dominoes[di]; | ||
519 | } | ||
520 | |||
521 | for (i = 0; i < sc->dc; i++) | ||
522 | sc->dominoes[i].nplacements = 0; | ||
523 | for (i = 0; i < sc->pc; i++) | ||
524 | sc->placements[i].domino->nplacements++; | ||
525 | for (i = j = 0; i < sc->dc; i++) { | ||
526 | sc->dominoes[i].placements = sc->domino_placement_lists + j; | ||
527 | j += sc->dominoes[i].nplacements; | ||
528 | sc->dominoes[i].nplacements = 0; | ||
529 | } | ||
530 | for (i = 0; i < sc->pc; i++) { | ||
531 | struct solver_placement *p = &sc->placements[i]; | ||
532 | p->dpi = p->domino->nplacements; | ||
533 | p->domino->placements[p->domino->nplacements++] = p; | ||
534 | p->active = true; | ||
535 | } | ||
536 | |||
537 | for (i = 0; i < sc->wh; i++) | ||
538 | sc->squares[i].nplacements = 0; | ||
539 | for (i = 0; i < sc->pc; i++) { | ||
540 | struct solver_placement *p = &sc->placements[i]; | ||
541 | for (j = 0; j < 2; j++) { | ||
542 | struct solver_square *sq = p->squares[j]; | ||
543 | p->spi[j] = sq->nplacements; | ||
544 | sq->placements[sq->nplacements++] = p; | ||
545 | } | ||
546 | } | ||
547 | |||
548 | sc->max_diff_used = DIFF_TRIVIAL; | ||
549 | sc->squares_by_number_initialised = false; | ||
550 | } | ||
551 | |||
552 | /* Given two placements p,q that overlap, returns si such that | ||
553 | * p->squares[si] is the square also in q */ | ||
554 | static int common_square_index(struct solver_placement *p, | ||
555 | struct solver_placement *q) | ||
556 | { | ||
557 | return (p->squares[0] == q->squares[0] || | ||
558 | p->squares[0] == q->squares[1]) ? 0 : 1; | ||
559 | } | ||
560 | |||
561 | /* Sort function used to set up squares_by_number */ | ||
562 | static int squares_by_number_cmpfn(const void *av, const void *bv) | ||
563 | { | ||
564 | struct solver_square *a = *(struct solver_square *const *)av; | ||
565 | struct solver_square *b = *(struct solver_square *const *)bv; | ||
566 | return (a->number < b->number ? -1 : a->number > b->number ? +1 : | ||
567 | a->index < b->index ? -1 : a->index > b->index ? +1 : 0); | ||
568 | } | ||
569 | |||
570 | static void rule_out_placement( | ||
571 | struct solver_scratch *sc, struct solver_placement *p) | ||
572 | { | ||
573 | struct solver_domino *d = p->domino; | ||
574 | int i, j, si; | ||
575 | |||
576 | #ifdef SOLVER_DIAGNOSTICS | ||
577 | if (solver_diagnostics) | ||
578 | printf(" ruling out placement %s for domino %s\n", p->name, d->name); | ||
579 | #endif | ||
580 | |||
581 | p->active = false; | ||
582 | |||
583 | i = p->dpi; | ||
584 | assert(d->placements[i] == p); | ||
585 | if (--d->nplacements != i) { | ||
586 | d->placements[i] = d->placements[d->nplacements]; | ||
587 | d->placements[i]->dpi = i; | ||
588 | } | ||
589 | |||
590 | for (si = 0; si < 2; si++) { | ||
591 | struct solver_square *sq = p->squares[si]; | ||
592 | i = p->spi[si]; | ||
593 | assert(sq->placements[i] == p); | ||
594 | if (--sq->nplacements != i) { | ||
595 | sq->placements[i] = sq->placements[sq->nplacements]; | ||
596 | j = (sq->placements[i]->squares[0] == sq ? 0 : 1); | ||
597 | sq->placements[i]->spi[j] = i; | ||
598 | } | ||
599 | } | ||
277 | } | 600 | } |
278 | 601 | ||
279 | /* | 602 | /* |
280 | * Returns 0, 1 or 2 for number of solutions. 2 means `any number | 603 | * If a domino has only one placement remaining, rule out all other |
281 | * more than one', or more accurately `we were unable to prove | 604 | * placements that overlap it. |
282 | * there was only one'. | ||
283 | * | ||
284 | * Outputs in a `placements' array, indexed the same way as the one | ||
285 | * within this function (see below); entries in there are <0 for a | ||
286 | * placement ruled out, 0 for an uncertain placement, and 1 for a | ||
287 | * definite one. | ||
288 | */ | 605 | */ |
289 | static int solver(int w, int h, int n, int *grid, int *output) | 606 | static bool deduce_domino_single_placement(struct solver_scratch *sc, int di) |
290 | { | 607 | { |
291 | int wh = w*h, dc = DCOUNT(n); | 608 | struct solver_domino *d = &sc->dominoes[di]; |
292 | int *placements, *heads; | 609 | struct solver_placement *p, *q; |
293 | int i, j, x, y, ret; | 610 | int oi; |
611 | bool done_something = false; | ||
612 | |||
613 | if (d->nplacements != 1) | ||
614 | return false; | ||
615 | p = d->placements[0]; | ||
616 | |||
617 | for (oi = 0; oi < p->noverlaps; oi++) { | ||
618 | q = p->overlaps[oi]; | ||
619 | if (q->active) { | ||
620 | if (!done_something) { | ||
621 | done_something = true; | ||
622 | #ifdef SOLVER_DIAGNOSTICS | ||
623 | if (solver_diagnostics) | ||
624 | printf("domino %s has unique placement %s\n", | ||
625 | d->name, p->name); | ||
626 | #endif | ||
627 | } | ||
628 | rule_out_placement(sc, q); | ||
629 | } | ||
630 | } | ||
631 | |||
632 | return done_something; | ||
633 | } | ||
634 | |||
635 | /* | ||
636 | * If a square has only one placement remaining, rule out all other | ||
637 | * placements of its domino. | ||
638 | */ | ||
639 | static bool deduce_square_single_placement(struct solver_scratch *sc, int si) | ||
640 | { | ||
641 | struct solver_square *sq = &sc->squares[si]; | ||
642 | struct solver_placement *p; | ||
643 | struct solver_domino *d; | ||
644 | |||
645 | if (sq->nplacements != 1) | ||
646 | return false; | ||
647 | p = sq->placements[0]; | ||
648 | d = p->domino; | ||
649 | |||
650 | if (d->nplacements <= 1) | ||
651 | return false; /* we already knew everything this would tell us */ | ||
652 | |||
653 | #ifdef SOLVER_DIAGNOSTICS | ||
654 | if (solver_diagnostics) | ||
655 | printf("square %s has unique placement %s (domino %s)\n", | ||
656 | sq->name, p->name, p->domino->name); | ||
657 | #endif | ||
658 | |||
659 | while (d->nplacements > 1) | ||
660 | rule_out_placement( | ||
661 | sc, d->placements[0] == p ? d->placements[1] : d->placements[0]); | ||
662 | |||
663 | return true; | ||
664 | } | ||
665 | |||
666 | /* | ||
667 | * If all placements for a square involve the same domino, rule out | ||
668 | * all other placements of that domino. | ||
669 | */ | ||
670 | static bool deduce_square_single_domino(struct solver_scratch *sc, int si) | ||
671 | { | ||
672 | struct solver_square *sq = &sc->squares[si]; | ||
673 | struct solver_domino *d; | ||
674 | int i; | ||
294 | 675 | ||
295 | /* | 676 | /* |
296 | * This array has one entry for every possible domino | 677 | * We only bother with this if the square has at least _two_ |
297 | * placement. Vertical placements are indexed by their top | 678 | * placements. If it only has one, then a simpler deduction will |
298 | * half, at (y*w+x)*2; horizontal placements are indexed by | 679 | * have handled it already, or will do so the next time round the |
299 | * their left half at (y*w+x)*2+1. | 680 | * main solver loop - and we should let the simpler deduction do |
300 | * | 681 | * it, because that will give a less overblown diagnostic. |
301 | * This array is used to link domino placements together into | ||
302 | * linked lists, so that we can track all the possible | ||
303 | * placements of each different domino. It's also used as a | ||
304 | * quick means of looking up an individual placement to see | ||
305 | * whether we still think it's possible. Actual values stored | ||
306 | * in this array are -2 (placement not possible at all), -1 | ||
307 | * (end of list), or the array index of the next item. | ||
308 | * | ||
309 | * Oh, and -3 for `not even valid', used for array indices | ||
310 | * which don't even represent a plausible placement. | ||
311 | */ | 682 | */ |
312 | placements = snewn(2*wh, int); | 683 | if (sq->nplacements < 2) |
313 | for (i = 0; i < 2*wh; i++) | 684 | return false; |
314 | placements[i] = -3; /* not even valid */ | 685 | |
686 | d = sq->placements[0]->domino; | ||
687 | for (i = 1; i < sq->nplacements; i++) | ||
688 | if (sq->placements[i]->domino != d) | ||
689 | return false; /* not all the same domino */ | ||
690 | |||
691 | if (d->nplacements <= sq->nplacements) | ||
692 | return false; /* no other placements of d to rule out */ | ||
693 | |||
694 | #ifdef SOLVER_DIAGNOSTICS | ||
695 | if (solver_diagnostics) | ||
696 | printf("square %s can only contain domino %s\n", sq->name, d->name); | ||
697 | #endif | ||
698 | |||
699 | for (i = d->nplacements; i-- > 0 ;) { | ||
700 | struct solver_placement *p = d->placements[i]; | ||
701 | if (p->squares[0] != sq && p->squares[1] != sq) | ||
702 | rule_out_placement(sc, p); | ||
703 | } | ||
704 | |||
705 | return true; | ||
706 | } | ||
707 | |||
708 | /* | ||
709 | * If any placement is overlapped by _all_ possible placements of a | ||
710 | * given domino, rule that placement out. | ||
711 | */ | ||
712 | static bool deduce_domino_must_overlap(struct solver_scratch *sc, int di) | ||
713 | { | ||
714 | struct solver_domino *d = &sc->dominoes[di]; | ||
715 | struct solver_placement *intersection[6], *p; | ||
716 | int nintersection = 0; | ||
717 | int i, j, k; | ||
315 | 718 | ||
316 | /* | 719 | /* |
317 | * This array has one entry for every domino, and it is an | 720 | * As in deduce_square_single_domino, we only bother with this |
318 | * index into `placements' denoting the head of the placement | 721 | * deduction if the domino has at least two placements. |
319 | * list for that domino. | ||
320 | */ | 722 | */ |
321 | heads = snewn(dc, int); | 723 | if (d->nplacements < 2) |
322 | for (i = 0; i < dc; i++) | 724 | return false; |
323 | heads[i] = -1; | 725 | |
726 | /* Initialise our set of overlapped placements with all the active | ||
727 | * ones overlapped by placements[0]. */ | ||
728 | p = d->placements[0]; | ||
729 | for (i = 0; i < p->noverlaps; i++) | ||
730 | if (p->overlaps[i]->active) | ||
731 | intersection[nintersection++] = p->overlaps[i]; | ||
732 | |||
733 | /* Now loop over the other placements of d, winnowing that set. */ | ||
734 | for (j = 1; j < d->nplacements; j++) { | ||
735 | int old_n; | ||
736 | |||
737 | p = d->placements[j]; | ||
738 | |||
739 | old_n = nintersection; | ||
740 | nintersection = 0; | ||
741 | |||
742 | for (k = 0; k < old_n; k++) { | ||
743 | for (i = 0; i < p->noverlaps; i++) | ||
744 | if (p->overlaps[i] == intersection[k]) | ||
745 | goto found; | ||
746 | /* If intersection[k] isn't in p->overlaps, exclude it | ||
747 | * from our set of placements overlapped by everything */ | ||
748 | continue; | ||
749 | found: | ||
750 | intersection[nintersection++] = intersection[k]; | ||
751 | } | ||
752 | } | ||
753 | |||
754 | if (nintersection == 0) | ||
755 | return false; /* no new exclusions */ | ||
756 | |||
757 | for (i = 0; i < nintersection; i++) { | ||
758 | p = intersection[i]; | ||
759 | |||
760 | #ifdef SOLVER_DIAGNOSTICS | ||
761 | if (solver_diagnostics) { | ||
762 | printf("placement %s of domino %s overlaps all placements " | ||
763 | "of domino %s:", p->name, p->domino->name, d->name); | ||
764 | for (j = 0; j < d->nplacements; j++) | ||
765 | printf(" %s", d->placements[j]->name); | ||
766 | printf("\n"); | ||
767 | } | ||
768 | #endif | ||
769 | rule_out_placement(sc, p); | ||
770 | } | ||
771 | |||
772 | return true; | ||
773 | } | ||
774 | |||
775 | /* | ||
776 | * If a placement of domino D overlaps the only remaining placement | ||
777 | * for some square S which is not also for domino D, then placing D | ||
778 | * here would require another copy of it in S, so we can rule it out. | ||
779 | */ | ||
780 | static bool deduce_local_duplicate(struct solver_scratch *sc, int pi) | ||
781 | { | ||
782 | struct solver_placement *p = &sc->placements[pi]; | ||
783 | struct solver_domino *d = p->domino; | ||
784 | int i, j; | ||
785 | |||
786 | if (!p->active) | ||
787 | return false; | ||
788 | |||
789 | for (i = 0; i < p->noverlaps; i++) { | ||
790 | struct solver_placement *q = p->overlaps[i]; | ||
791 | struct solver_square *sq; | ||
792 | |||
793 | if (!q->active) | ||
794 | continue; | ||
795 | |||
796 | /* Find the square of q that _isn't_ part of p */ | ||
797 | sq = q->squares[1 - common_square_index(q, p)]; | ||
798 | |||
799 | for (j = 0; j < sq->nplacements; j++) | ||
800 | if (sq->placements[j] != q && sq->placements[j]->domino != d) | ||
801 | goto no; | ||
802 | |||
803 | /* If we get here, every possible placement for sq is either q | ||
804 | * itself, or another copy of d. Success! We can rule out p. */ | ||
805 | #ifdef SOLVER_DIAGNOSTICS | ||
806 | if (solver_diagnostics) { | ||
807 | printf("placement %s of domino %s would force another copy of %s " | ||
808 | "in square %s\n", p->name, d->name, d->name, sq->name); | ||
809 | } | ||
810 | #endif | ||
811 | |||
812 | rule_out_placement(sc, p); | ||
813 | return true; | ||
814 | |||
815 | no:; | ||
816 | } | ||
817 | |||
818 | return false; | ||
819 | } | ||
820 | |||
821 | /* | ||
822 | * If placement P overlaps one placement for each of two squares S,T | ||
823 | * such that all the remaining placements for both S and T are the | ||
824 | * same domino D (and none of those placements joins S and T to each | ||
825 | * other), then P can't be placed, because it would leave S,T each | ||
826 | * having to be a copy of D, i.e. duplicates. | ||
827 | */ | ||
828 | static bool deduce_local_duplicate_2(struct solver_scratch *sc, int pi) | ||
829 | { | ||
830 | struct solver_placement *p = &sc->placements[pi]; | ||
831 | int i, j, k; | ||
832 | |||
833 | if (!p->active) | ||
834 | return false; | ||
324 | 835 | ||
325 | /* | 836 | /* |
326 | * Set up the initial possibility lists by scanning the grid. | 837 | * Iterate over pairs of placements qi,qj overlapping p. |
327 | */ | 838 | */ |
328 | for (y = 0; y < h-1; y++) | 839 | for (i = 0; i < p->noverlaps; i++) { |
329 | for (x = 0; x < w; x++) { | 840 | struct solver_placement *qi = p->overlaps[i]; |
330 | int di = DINDEX(grid[y*w+x], grid[(y+1)*w+x]); | 841 | struct solver_square *sqi; |
331 | placements[(y*w+x)*2] = heads[di]; | 842 | struct solver_domino *di = NULL; |
332 | heads[di] = (y*w+x)*2; | 843 | |
844 | if (!qi->active) | ||
845 | continue; | ||
846 | |||
847 | /* Find the square of qi that _isn't_ part of p */ | ||
848 | sqi = qi->squares[1 - common_square_index(qi, p)]; | ||
849 | |||
850 | /* | ||
851 | * Identify the unique domino involved in all possible | ||
852 | * placements of sqi other than qi. If there isn't a unique | ||
853 | * one (either too many or too few), move on and try the next | ||
854 | * qi. | ||
855 | */ | ||
856 | for (k = 0; k < sqi->nplacements; k++) { | ||
857 | struct solver_placement *pk = sqi->placements[k]; | ||
858 | if (sqi->placements[k] == qi) | ||
859 | continue; /* not counting qi itself */ | ||
860 | if (!di) | ||
861 | di = pk->domino; | ||
862 | else if (di != pk->domino) | ||
863 | goto done_qi; | ||
333 | } | 864 | } |
334 | for (y = 0; y < h; y++) | 865 | if (!di) |
335 | for (x = 0; x < w-1; x++) { | 866 | goto done_qi; |
336 | int di = DINDEX(grid[y*w+x], grid[y*w+(x+1)]); | 867 | |
337 | placements[(y*w+x)*2+1] = heads[di]; | 868 | /* |
338 | heads[di] = (y*w+x)*2+1; | 869 | * Now find an appropriate qj != qi. |
870 | */ | ||
871 | for (j = 0; j < p->noverlaps; j++) { | ||
872 | struct solver_placement *qj = p->overlaps[j]; | ||
873 | struct solver_square *sqj; | ||
874 | bool found_di = false; | ||
875 | |||
876 | if (j == i || !qj->active) | ||
877 | continue; | ||
878 | |||
879 | sqj = qj->squares[1 - common_square_index(qj, p)]; | ||
880 | |||
881 | /* | ||
882 | * As above, we want the same domino di to be the only one | ||
883 | * sqj can be if placement qj is ruled out. But also we | ||
884 | * need no placement of sqj to overlap sqi. | ||
885 | */ | ||
886 | for (k = 0; k < sqj->nplacements; k++) { | ||
887 | struct solver_placement *pk = sqj->placements[k]; | ||
888 | if (pk == qj) | ||
889 | continue; /* not counting qj itself */ | ||
890 | if (pk->domino != di) | ||
891 | goto done_qj; /* found a different domino */ | ||
892 | if (pk->squares[0] == sqi || pk->squares[1] == sqi) | ||
893 | goto done_qj; /* sqi,sqj can be joined to each other */ | ||
894 | found_di = true; | ||
895 | } | ||
896 | if (!found_di) | ||
897 | goto done_qj; | ||
898 | |||
899 | /* If we get here, then every placement for either of sqi | ||
900 | * and sqj is a copy of di, except for the ones that | ||
901 | * overlap p. Success! We can rule out p. */ | ||
902 | #ifdef SOLVER_DIAGNOSTICS | ||
903 | if (solver_diagnostics) { | ||
904 | printf("placement %s of domino %s would force squares " | ||
905 | "%s and %s to both be domino %s\n", | ||
906 | p->name, p->domino->name, | ||
907 | sqi->name, sqj->name, di->name); | ||
908 | } | ||
909 | #endif | ||
910 | rule_out_placement(sc, p); | ||
911 | return true; | ||
912 | |||
913 | done_qj:; | ||
339 | } | 914 | } |
340 | 915 | ||
916 | done_qi:; | ||
917 | } | ||
918 | |||
919 | return false; | ||
920 | } | ||
921 | |||
922 | struct parity_findloop_ctx { | ||
923 | struct solver_scratch *sc; | ||
924 | struct solver_square *sq; | ||
925 | int i; | ||
926 | }; | ||
927 | |||
928 | int parity_neighbour(int vertex, void *vctx) | ||
929 | { | ||
930 | struct parity_findloop_ctx *ctx = (struct parity_findloop_ctx *)vctx; | ||
931 | struct solver_placement *p; | ||
932 | |||
933 | if (vertex >= 0) { | ||
934 | ctx->sq = &ctx->sc->squares[vertex]; | ||
935 | ctx->i = 0; | ||
936 | } else { | ||
937 | assert(ctx->sq); | ||
938 | } | ||
939 | |||
940 | if (ctx->i >= ctx->sq->nplacements) { | ||
941 | ctx->sq = NULL; | ||
942 | return -1; | ||
943 | } | ||
944 | |||
945 | p = ctx->sq->placements[ctx->i++]; | ||
946 | return p->squares[0]->index + p->squares[1]->index - ctx->sq->index; | ||
947 | } | ||
948 | |||
949 | /* | ||
950 | * Look for dominoes whose placement would disconnect the unfilled | ||
951 | * area of the grid into pieces with odd area. Such a domino can't be | ||
952 | * placed, because then the area on each side of it would be | ||
953 | * untileable. | ||
954 | */ | ||
955 | static bool deduce_parity(struct solver_scratch *sc) | ||
956 | { | ||
957 | struct parity_findloop_ctx pflctx; | ||
958 | bool done_something = false; | ||
959 | int pi; | ||
960 | |||
961 | /* | ||
962 | * Run findloop, aka Tarjan's bridge-finding algorithm, on the | ||
963 | * graph whose vertices are squares, with two vertices separated | ||
964 | * by an edge iff some not-yet-ruled-out domino placement covers | ||
965 | * them both. (So each edge itself corresponds to a domino | ||
966 | * placement.) | ||
967 | * | ||
968 | * The effect is that any bridge in this graph is a domino whose | ||
969 | * placement would separate two previously connected areas of the | ||
970 | * unfilled squares of the grid. | ||
971 | * | ||
972 | * Placing that domino would not just disconnect those areas from | ||
973 | * each other, but also use up one square of each. So if we want | ||
974 | * to avoid leaving two odd areas after placing the domino, it | ||
975 | * follows that we want to avoid the bridge having an _even_ | ||
976 | * number of vertices on each side. | ||
977 | */ | ||
978 | pflctx.sc = sc; | ||
979 | findloop_run(sc->fls, sc->wh, parity_neighbour, &pflctx); | ||
980 | |||
981 | for (pi = 0; pi < sc->pc; pi++) { | ||
982 | struct solver_placement *p = &sc->placements[pi]; | ||
983 | int size0, size1; | ||
984 | |||
985 | if (!p->active) | ||
986 | continue; | ||
987 | if (!findloop_is_bridge( | ||
988 | sc->fls, p->squares[0]->index, p->squares[1]->index, | ||
989 | &size0, &size1)) | ||
990 | continue; | ||
991 | /* To make a deduction, size0 and size1 must both be even, | ||
992 | * i.e. after placing this domino decrements each by 1 they | ||
993 | * would both become odd and untileable areas. */ | ||
994 | if ((size0 | size1) & 1) | ||
995 | continue; | ||
996 | |||
341 | #ifdef SOLVER_DIAGNOSTICS | 997 | #ifdef SOLVER_DIAGNOSTICS |
342 | printf("before solver:\n"); | 998 | if (solver_diagnostics) { |
343 | for (i = 0; i <= n; i++) | 999 | printf("placement %s of domino %s would create two odd-sized " |
344 | for (j = 0; j <= i; j++) { | 1000 | "areas\n", p->name, p->domino->name); |
345 | int k, m; | ||
346 | m = 0; | ||
347 | printf("%2d [%d %d]:", DINDEX(i, j), i, j); | ||
348 | for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k]) | ||
349 | printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v'); | ||
350 | printf("\n"); | ||
351 | } | 1001 | } |
352 | #endif | 1002 | #endif |
1003 | rule_out_placement(sc, p); | ||
1004 | done_something = true; | ||
1005 | } | ||
353 | 1006 | ||
354 | while (1) { | 1007 | return done_something; |
355 | bool done_something = false; | 1008 | } |
356 | 1009 | ||
1010 | /* | ||
1011 | * Try to find a set of squares all containing the same number, such | ||
1012 | * that the set of possible dominoes for all the squares in that set | ||
1013 | * is small enough to let us rule out placements of those dominoes | ||
1014 | * elsewhere. | ||
1015 | */ | ||
1016 | static bool deduce_set(struct solver_scratch *sc, bool doubles) | ||
1017 | { | ||
1018 | struct solver_square **sqs, **sqp, **sqe; | ||
1019 | int num, nsq, i, j; | ||
1020 | unsigned long domino_sets[16], adjacent[16]; | ||
1021 | struct solver_domino *ds[16]; | ||
1022 | bool done_something = false; | ||
1023 | |||
1024 | if (!sc->squares_by_number) | ||
1025 | sc->squares_by_number = snewn(sc->wh, struct solver_square *); | ||
1026 | if (!sc->wh_scratch) | ||
1027 | sc->wh_scratch = snewn(sc->wh, int); | ||
1028 | |||
1029 | if (!sc->squares_by_number_initialised) { | ||
357 | /* | 1030 | /* |
358 | * For each domino, look at its possible placements, and | 1031 | * If this is the first call to this function for a given |
359 | * for each placement consider the placements (of any | 1032 | * grid, start by sorting the squares by their containing |
360 | * domino) it overlaps. Any placement overlapped by all | 1033 | * number. |
361 | * placements of this domino can be ruled out. | ||
362 | * | ||
363 | * Each domino placement overlaps only six others, so we | ||
364 | * need not do serious set theory to work this out. | ||
365 | */ | 1034 | */ |
366 | for (i = 0; i < dc; i++) { | 1035 | for (i = 0; i < sc->wh; i++) |
367 | int permset[6], permlen = 0, p; | 1036 | sc->squares_by_number[i] = &sc->squares[i]; |
368 | 1037 | qsort(sc->squares_by_number, sc->wh, sizeof(*sc->squares_by_number), | |
1038 | squares_by_number_cmpfn); | ||
1039 | } | ||
369 | 1040 | ||
370 | if (heads[i] == -1) { /* no placement for this domino */ | 1041 | sqp = sc->squares_by_number; |
371 | ret = 0; /* therefore puzzle is impossible */ | 1042 | sqe = sc->squares_by_number + sc->wh; |
372 | goto done; | 1043 | for (num = 0; num <= sc->n; num++) { |
373 | } | 1044 | unsigned long squares; |
374 | for (j = heads[i]; j >= 0; j = placements[j]) { | 1045 | unsigned long squares_done; |
375 | assert(placements[j] != -2); | ||
376 | 1046 | ||
377 | if (j == heads[i]) { | 1047 | /* Find the bounds of the subinterval of squares_by_number |
378 | permlen = find_overlaps(w, h, j, permset); | 1048 | * containing squares with this particular number. */ |
379 | } else { | 1049 | sqs = sqp; |
380 | int tempset[6], templen, m, n, k; | 1050 | while (sqp < sqe && (*sqp)->number == num) |
1051 | sqp++; | ||
1052 | nsq = sqp - sqs; | ||
1053 | |||
1054 | /* | ||
1055 | * Now sqs[0], ..., sqs[nsq-1] are the squares containing 'num'. | ||
1056 | */ | ||
1057 | |||
1058 | if (nsq > lenof(domino_sets)) { | ||
1059 | /* | ||
1060 | * Abort this analysis if we're trying to enumerate all | ||
1061 | * the subsets of a too-large base set. | ||
1062 | * | ||
1063 | * This _shouldn't_ happen, at the time of writing this | ||
1064 | * code, because the largest puzzle we support is only | ||
1065 | * supposed to have 10 instances of each number, and part | ||
1066 | * of our input grid validation checks that each number | ||
1067 | * does appear the right number of times. But just in case | ||
1068 | * weird test input makes its way to this function, or the | ||
1069 | * puzzle sizes are expanded later, it's easy enough to | ||
1070 | * just rule out doing this analysis for overlarge sets of | ||
1071 | * numbers. | ||
1072 | */ | ||
1073 | continue; | ||
1074 | } | ||
1075 | |||
1076 | /* | ||
1077 | * Index the squares in wh_scratch, which we're using as a | ||
1078 | * lookup table to map the official index of a square back to | ||
1079 | * its value in our local indexing scheme. | ||
1080 | */ | ||
1081 | for (i = 0; i < nsq; i++) | ||
1082 | sc->wh_scratch[sqs[i]->index] = i; | ||
1083 | |||
1084 | /* | ||
1085 | * For each square, make a bit mask of the dominoes that can | ||
1086 | * overlap it, by finding the number at the other end of each | ||
1087 | * one. | ||
1088 | * | ||
1089 | * Also, for each square, make a bit mask of other squares in | ||
1090 | * the current list that might occupy the _same_ domino | ||
1091 | * (because a possible placement of a double overlaps both). | ||
1092 | * We'll need that for evaluating whether sets are properly | ||
1093 | * exhaustive. | ||
1094 | */ | ||
1095 | for (i = 0; i < nsq; i++) | ||
1096 | adjacent[i] = 0; | ||
381 | 1097 | ||
382 | templen = find_overlaps(w, h, j, tempset); | 1098 | for (i = 0; i < nsq; i++) { |
1099 | struct solver_square *sq = sqs[i]; | ||
1100 | unsigned long mask = 0; | ||
383 | 1101 | ||
1102 | for (j = 0; j < sq->nplacements; j++) { | ||
1103 | struct solver_placement *p = sq->placements[j]; | ||
1104 | int othernum = p->domino->lo + p->domino->hi - num; | ||
1105 | mask |= 1UL << othernum; | ||
1106 | ds[othernum] = p->domino; /* so we can find them later */ | ||
1107 | |||
1108 | if (othernum == num) { | ||
384 | /* | 1109 | /* |
385 | * Pathetically primitive set intersection | 1110 | * Special case: this is a double, so it gives |
386 | * algorithm, which I'm only getting away with | 1111 | * rise to entries in adjacent[]. |
387 | * because I know my sets are bounded by a very | ||
388 | * small size. | ||
389 | */ | 1112 | */ |
390 | for (m = n = 0; m < permlen; m++) { | 1113 | int i2 = sc->wh_scratch[p->squares[0]->index + |
391 | for (k = 0; k < templen; k++) | 1114 | p->squares[1]->index - sq->index]; |
392 | if (tempset[k] == permset[m]) | 1115 | adjacent[i] |= 1UL << i2; |
393 | break; | 1116 | adjacent[i2] |= 1UL << i; |
394 | if (k < templen) | ||
395 | permset[n++] = permset[m]; | ||
396 | } | ||
397 | permlen = n; | ||
398 | } | 1117 | } |
399 | } | 1118 | } |
400 | for (p = 0; p < permlen; p++) { | ||
401 | j = permset[p]; | ||
402 | if (placements[j] != -2) { | ||
403 | int p1, p2, di; | ||
404 | 1119 | ||
405 | done_something = true; | 1120 | domino_sets[i] = mask; |
1121 | |||
1122 | } | ||
1123 | |||
1124 | squares_done = 0; | ||
1125 | |||
1126 | for (squares = 0; squares < (1UL << nsq); squares++) { | ||
1127 | unsigned long dominoes = 0; | ||
1128 | int bitpos, nsquares, ndominoes; | ||
1129 | bool got_adj_squares = false; | ||
1130 | bool reported = false; | ||
1131 | bool rule_out_nondoubles; | ||
1132 | int min_nused_for_double; | ||
1133 | #ifdef SOLVER_DIAGNOSTICS | ||
1134 | const char *rule_out_text; | ||
1135 | #endif | ||
1136 | |||
1137 | /* | ||
1138 | * We don't do set analysis on the same square of the grid | ||
1139 | * more than once in this loop. Otherwise you generate | ||
1140 | * pointlessly overcomplicated diagnostics for simpler | ||
1141 | * follow-up deductions. For example, suppose squares | ||
1142 | * {A,B} must go with dominoes {X,Y}. So you rule out X,Y | ||
1143 | * elsewhere, and then it turns out square C (from which | ||
1144 | * one of those was eliminated) has only one remaining | ||
1145 | * possibility Z. What you _don't_ want to do is | ||
1146 | * triumphantly report a second case of set elimination | ||
1147 | * where you say 'And also, squares {A,B,C} have to be | ||
1148 | * {X,Y,Z}!' You'd prefer to give 'now C has to be Z' as a | ||
1149 | * separate deduction later, more simply phrased. | ||
1150 | */ | ||
1151 | if (squares & squares_done) | ||
1152 | continue; | ||
1153 | |||
1154 | nsquares = 0; | ||
1155 | |||
1156 | /* Make the set of dominoes that these squares can inhabit. */ | ||
1157 | for (bitpos = 0; bitpos < nsq; bitpos++) { | ||
1158 | if (!(1 & (squares >> bitpos))) | ||
1159 | continue; /* this bit isn't set in the mask */ | ||
1160 | |||
1161 | if (adjacent[bitpos] & squares) | ||
1162 | got_adj_squares = true; | ||
406 | 1163 | ||
1164 | dominoes |= domino_sets[bitpos]; | ||
1165 | nsquares++; | ||
1166 | } | ||
1167 | |||
1168 | /* Count them. */ | ||
1169 | ndominoes = 0; | ||
1170 | for (bitpos = 0; bitpos < nsq; bitpos++) | ||
1171 | ndominoes += 1 & (dominoes >> bitpos); | ||
1172 | |||
1173 | /* | ||
1174 | * Do the two sets have the right relative size? | ||
1175 | */ | ||
1176 | if (!got_adj_squares) { | ||
1177 | /* | ||
1178 | * The normal case, in which every possible domino | ||
1179 | * placement involves at most _one_ of these squares. | ||
1180 | * | ||
1181 | * This is exactly analogous to the set analysis | ||
1182 | * deductions in many other puzzles: if our N squares | ||
1183 | * between them have to account for N distinct | ||
1184 | * dominoes, with exactly one of those dominoes to | ||
1185 | * each square, then all those dominoes correspond to | ||
1186 | * all those squares and we can rule out any | ||
1187 | * placements of the same dominoes appearing | ||
1188 | * elsewhere. | ||
1189 | */ | ||
1190 | if (ndominoes != nsquares) | ||
1191 | continue; | ||
1192 | rule_out_nondoubles = true; | ||
1193 | min_nused_for_double = 1; | ||
1194 | #ifdef SOLVER_DIAGNOSTICS | ||
1195 | rule_out_text = "all of them elsewhere"; | ||
1196 | #endif | ||
1197 | } else { | ||
1198 | if (!doubles) | ||
1199 | continue; /* not at this difficulty level */ | ||
1200 | |||
1201 | /* | ||
1202 | * But in Dominosa, there's a special case if _two_ | ||
1203 | * squares in this set can possibly both be covered by | ||
1204 | * the same double domino. (I.e. if they are adjacent, | ||
1205 | * and moreover, the double-domino placement | ||
1206 | * containing both is not yet ruled out.) | ||
1207 | * | ||
1208 | * In that situation, the simple argument doesn't hold | ||
1209 | * up, because the N squares might be covered by N-1 | ||
1210 | * dominoes - or, put another way, if you list the | ||
1211 | * containing domino for each of the squares, they | ||
1212 | * might not be all distinct. | ||
1213 | * | ||
1214 | * In that situation, we can still do something, but | ||
1215 | * the details vary, and there are two further cases. | ||
1216 | */ | ||
1217 | if (ndominoes == nsquares-1) { | ||
407 | /* | 1218 | /* |
408 | * Rule out this placement. First find what | 1219 | * Suppose there is one _more_ square in our set |
409 | * domino it is... | 1220 | * than there are dominoes it can involve. For |
1221 | * example, suppose we had four '0' squares which | ||
1222 | * between them could contain only the 0-0, 0-1 | ||
1223 | * and 0-2 dominoes. | ||
1224 | * | ||
1225 | * Then that can only work at all if the 0-0 | ||
1226 | * covers two of those squares - and in that | ||
1227 | * situation that _must_ be what's happened. | ||
1228 | * | ||
1229 | * So we can rule out the 0-1 and 0-2 dominoes (in | ||
1230 | * this example) in any placement that doesn't use | ||
1231 | * one of the squares in this set. And we can rule | ||
1232 | * out a placement of the 0-0 even if it uses | ||
1233 | * _one_ square from this set: in this situation, | ||
1234 | * we have to insist on it using _two_. | ||
410 | */ | 1235 | */ |
411 | p1 = j / 2; | 1236 | rule_out_nondoubles = true; |
412 | p2 = (j & 1) ? p1 + 1 : p1 + w; | 1237 | min_nused_for_double = 2; |
413 | di = DINDEX(grid[p1], grid[p2]); | ||
414 | #ifdef SOLVER_DIAGNOSTICS | 1238 | #ifdef SOLVER_DIAGNOSTICS |
415 | printf("considering domino %d: ruling out placement %d" | 1239 | rule_out_text = "all of them elsewhere " |
416 | " for %d\n", i, j, di); | 1240 | "(including the double if it fails to use both)"; |
417 | #endif | 1241 | #endif |
418 | 1242 | } else if (ndominoes == nsquares) { | |
1243 | /* | ||
1244 | * A restricted form of the deduction is still | ||
1245 | * possible if we have the same number of dominoes | ||
1246 | * as squares. | ||
1247 | * | ||
1248 | * If we have _three_ '0' squares none of which | ||
1249 | * can be any domino other than 0-0, 0-1 and 0-2, | ||
1250 | * and there's still a possibility of an 0-0 | ||
1251 | * domino using up two of them, then we can't rule | ||
1252 | * out 0-1 or 0-2 anywhere else, because it's | ||
1253 | * possible that these three squares only use two | ||
1254 | * of the dominoes between them. | ||
1255 | * | ||
1256 | * But we _can_ rule out the double 0-0, in any | ||
1257 | * placement that uses _none_ of our three | ||
1258 | * squares. Because we do know that _at least one_ | ||
1259 | * of our squares must be involved in the 0-0, or | ||
1260 | * else the three of them would only have the | ||
1261 | * other two dominoes left. | ||
1262 | */ | ||
1263 | rule_out_nondoubles = false; | ||
1264 | min_nused_for_double = 1; | ||
1265 | #ifdef SOLVER_DIAGNOSTICS | ||
1266 | rule_out_text = "the double elsewhere"; | ||
1267 | #endif | ||
1268 | } else { | ||
419 | /* | 1269 | /* |
420 | * ... then walk that domino's placement list, | 1270 | * If none of those cases has happened, then our |
421 | * removing this placement when we find it. | 1271 | * set admits no deductions at all. |
422 | */ | 1272 | */ |
423 | if (heads[di] == j) | 1273 | continue; |
424 | heads[di] = placements[j]; | 1274 | } |
425 | else { | 1275 | } |
426 | int k = heads[di]; | 1276 | |
427 | while (placements[k] != -1 && placements[k] != j) | 1277 | /* Skip sets of size 1, or whose complement has size 1. |
428 | k = placements[k]; | 1278 | * Those can be handled by a simpler analysis, and should |
429 | assert(placements[k] == j); | 1279 | * be, for more sensible solver diagnostics. */ |
430 | placements[k] = placements[j]; | 1280 | if (ndominoes <= 1 || ndominoes >= nsq-1) |
1281 | continue; | ||
1282 | |||
1283 | /* | ||
1284 | * We've found a set! That means we can rule out any | ||
1285 | * placement of any domino in that set which would leave | ||
1286 | * the squares in the set with too few dominoes between | ||
1287 | * them. | ||
1288 | * | ||
1289 | * We may or may not actually end up ruling anything out | ||
1290 | * here. But even if we don't, we should record that these | ||
1291 | * squares form a self-contained set, so that we don't | ||
1292 | * pointlessly report a superset of them later which could | ||
1293 | * instead be reported as just the other ones. | ||
1294 | * | ||
1295 | * Or rather, we do that for the main cases that let us | ||
1296 | * rule out lots of dominoes. We only do this with the | ||
1297 | * borderline case where we can only rule out a double if | ||
1298 | * we _actually_ rule something out. Otherwise we'll never | ||
1299 | * even _find_ a larger set with the same number of | ||
1300 | * dominoes! | ||
1301 | */ | ||
1302 | if (rule_out_nondoubles) | ||
1303 | squares_done |= squares; | ||
1304 | |||
1305 | for (bitpos = 0; bitpos < nsq; bitpos++) { | ||
1306 | struct solver_domino *d; | ||
1307 | |||
1308 | if (!(1 & (dominoes >> bitpos))) | ||
1309 | continue; | ||
1310 | d = ds[bitpos]; | ||
1311 | |||
1312 | for (i = d->nplacements; i-- > 0 ;) { | ||
1313 | struct solver_placement *p = d->placements[i]; | ||
1314 | int si, nused; | ||
1315 | |||
1316 | /* Count how many of our squares this placement uses. */ | ||
1317 | for (si = nused = 0; si < 2; si++) { | ||
1318 | struct solver_square *sq2 = p->squares[si]; | ||
1319 | if (sq2->number == num && | ||
1320 | (1 & (squares >> sc->wh_scratch[sq2->index]))) | ||
1321 | nused++; | ||
1322 | } | ||
1323 | |||
1324 | /* See if that's too many to rule it out. */ | ||
1325 | if (d->lo == d->hi) { | ||
1326 | if (nused >= min_nused_for_double) | ||
1327 | continue; | ||
1328 | } else { | ||
1329 | if (nused > 0 || !rule_out_nondoubles) | ||
1330 | continue; | ||
1331 | } | ||
1332 | |||
1333 | if (!reported) { | ||
1334 | reported = true; | ||
1335 | done_something = true; | ||
1336 | |||
1337 | /* In case we didn't do this above */ | ||
1338 | squares_done |= squares; | ||
1339 | |||
1340 | #ifdef SOLVER_DIAGNOSTICS | ||
1341 | if (solver_diagnostics) { | ||
1342 | int b; | ||
1343 | const char *sep; | ||
1344 | printf("squares {"); | ||
1345 | for (sep = "", b = 0; b < nsq; b++) | ||
1346 | if (1 & (squares >> b)) { | ||
1347 | printf("%s%s", sep, sqs[b]->name); | ||
1348 | sep = ","; | ||
1349 | } | ||
1350 | printf("} can contain only dominoes {"); | ||
1351 | for (sep = "", b = 0; b < nsq; b++) | ||
1352 | if (1 & (dominoes >> b)) { | ||
1353 | printf("%s%s", sep, ds[b]->name); | ||
1354 | sep = ","; | ||
1355 | } | ||
1356 | printf("}, so rule out %s", rule_out_text); | ||
1357 | printf("\n"); | ||
1358 | } | ||
1359 | #endif | ||
431 | } | 1360 | } |
432 | placements[j] = -2; | 1361 | |
1362 | rule_out_placement(sc, p); | ||
433 | } | 1363 | } |
434 | } | 1364 | } |
435 | } | 1365 | } |
436 | 1366 | ||
1367 | } | ||
1368 | |||
1369 | return done_something; | ||
1370 | } | ||
1371 | |||
1372 | static int forcing_chain_dup_cmp(const void *av, const void *bv, void *ctx) | ||
1373 | { | ||
1374 | struct solver_scratch *sc = (struct solver_scratch *)ctx; | ||
1375 | int a = *(const int *)av, b = *(const int *)bv; | ||
1376 | int ac, bc; | ||
1377 | |||
1378 | ac = sc->pc_scratch[a]; | ||
1379 | bc = sc->pc_scratch[b]; | ||
1380 | if (ac != bc) return ac > bc ? +1 : -1; | ||
1381 | |||
1382 | ac = sc->placements[a].domino->index; | ||
1383 | bc = sc->placements[b].domino->index; | ||
1384 | if (ac != bc) return ac > bc ? +1 : -1; | ||
1385 | |||
1386 | return 0; | ||
1387 | } | ||
1388 | |||
1389 | static int forcing_chain_sq_cmp(const void *av, const void *bv, void *ctx) | ||
1390 | { | ||
1391 | struct solver_scratch *sc = (struct solver_scratch *)ctx; | ||
1392 | int a = *(const int *)av, b = *(const int *)bv; | ||
1393 | int ac, bc; | ||
1394 | |||
1395 | ac = sc->placements[a].domino->index; | ||
1396 | bc = sc->placements[b].domino->index; | ||
1397 | if (ac != bc) return ac > bc ? +1 : -1; | ||
1398 | |||
1399 | ac = sc->pc_scratch[a]; | ||
1400 | bc = sc->pc_scratch[b]; | ||
1401 | if (ac != bc) return ac > bc ? +1 : -1; | ||
1402 | |||
1403 | return 0; | ||
1404 | } | ||
1405 | |||
1406 | static bool deduce_forcing_chain(struct solver_scratch *sc) | ||
1407 | { | ||
1408 | int si, pi, di, j, k, m; | ||
1409 | bool done_something = false; | ||
1410 | |||
1411 | if (!sc->wh_scratch) | ||
1412 | sc->wh_scratch = snewn(sc->wh, int); | ||
1413 | if (!sc->pc_scratch) | ||
1414 | sc->pc_scratch = snewn(sc->pc, int); | ||
1415 | if (!sc->pc_scratch2) | ||
1416 | sc->pc_scratch2 = snewn(sc->pc, int); | ||
1417 | if (!sc->dc_scratch) | ||
1418 | sc->dc_scratch = snewn(sc->dc, int); | ||
1419 | |||
1420 | /* | ||
1421 | * Start by identifying chains of placements which must all occur | ||
1422 | * together if any of them occurs. We do this by making | ||
1423 | * pc_scratch2 an edsf binding the placements into an equivalence | ||
1424 | * class for each entire forcing chain, with the two possible sets | ||
1425 | * of dominoes for the chain listed as inverses. | ||
1426 | */ | ||
1427 | dsf_init(sc->pc_scratch2, sc->pc); | ||
1428 | for (si = 0; si < sc->wh; si++) { | ||
1429 | struct solver_square *sq = &sc->squares[si]; | ||
1430 | if (sq->nplacements == 2) | ||
1431 | edsf_merge(sc->pc_scratch2, | ||
1432 | sq->placements[0]->index, | ||
1433 | sq->placements[1]->index, true); | ||
1434 | } | ||
1435 | /* | ||
1436 | * Now read out the whole dsf into pc_scratch, flattening its | ||
1437 | * structured data into a simple integer id per chain of dominoes | ||
1438 | * that must occur together. | ||
1439 | * | ||
1440 | * The integer ids have the property that any two that differ only | ||
1441 | * in the lowest bit (i.e. of the form {2n,2n+1}) represent | ||
1442 | * complementary chains, each of which rules out the other. | ||
1443 | */ | ||
1444 | for (pi = 0; pi < sc->pc; pi++) { | ||
1445 | bool inv; | ||
1446 | int c = edsf_canonify(sc->pc_scratch2, pi, &inv); | ||
1447 | sc->pc_scratch[pi] = c * 2 + (inv ? 1 : 0); | ||
1448 | } | ||
1449 | |||
1450 | /* | ||
1451 | * Identify chains that contain a duplicate domino, and rule them | ||
1452 | * out. We do this by making a list of the placement indices in | ||
1453 | * pc_scratch2, sorted by (chain id, domino id), so that dupes | ||
1454 | * become adjacent. | ||
1455 | */ | ||
1456 | for (pi = 0; pi < sc->pc; pi++) | ||
1457 | sc->pc_scratch2[pi] = pi; | ||
1458 | arraysort(sc->pc_scratch2, sc->pc, forcing_chain_dup_cmp, sc); | ||
1459 | |||
1460 | for (j = 0; j < sc->pc ;) { | ||
1461 | struct solver_domino *duplicated_domino = NULL; | ||
1462 | |||
437 | /* | 1463 | /* |
438 | * For each square, look at the available placements | 1464 | * This loop iterates once per contiguous segment of the same |
439 | * involving that square. If all of them are for the same | 1465 | * value in pc_scratch2, i.e. once per chain. |
440 | * domino, then rule out any placements for that domino | ||
441 | * _not_ involving this square. | ||
442 | */ | 1466 | */ |
443 | for (i = 0; i < wh; i++) { | 1467 | int ci = sc->pc_scratch[sc->pc_scratch2[j]]; |
444 | int list[4], k, n, adi; | 1468 | int climit, cstart = j; |
445 | 1469 | while (j < sc->pc && sc->pc_scratch[sc->pc_scratch2[j]] == ci) | |
446 | x = i % w; | 1470 | j++; |
447 | y = i / w; | 1471 | climit = j; |
448 | 1472 | ||
449 | j = 0; | 1473 | /* |
450 | if (x > 0) | 1474 | * Now look for a duplicate domino within that chain. |
451 | list[j++] = 2*(i-1)+1; | 1475 | */ |
452 | if (x+1 < w) | 1476 | for (k = cstart; k + 1 < climit; k++) { |
453 | list[j++] = 2*i+1; | 1477 | struct solver_placement *p = &sc->placements[sc->pc_scratch2[k]]; |
454 | if (y > 0) | 1478 | struct solver_placement *q = &sc->placements[sc->pc_scratch2[k+1]]; |
455 | list[j++] = 2*(i-w); | 1479 | if (p->domino == q->domino) { |
456 | if (y+1 < h) | 1480 | duplicated_domino = p->domino; |
457 | list[j++] = 2*i; | 1481 | break; |
458 | |||
459 | for (n = k = 0; k < j; k++) | ||
460 | if (placements[list[k]] >= -1) | ||
461 | list[n++] = list[k]; | ||
462 | |||
463 | adi = -1; | ||
464 | |||
465 | for (j = 0; j < n; j++) { | ||
466 | int p1, p2, di; | ||
467 | k = list[j]; | ||
468 | |||
469 | p1 = k / 2; | ||
470 | p2 = (k & 1) ? p1 + 1 : p1 + w; | ||
471 | di = DINDEX(grid[p1], grid[p2]); | ||
472 | |||
473 | if (adi == -1) | ||
474 | adi = di; | ||
475 | if (adi != di) | ||
476 | break; | ||
477 | } | 1482 | } |
1483 | } | ||
478 | 1484 | ||
479 | if (j == n) { | 1485 | if (!duplicated_domino) |
480 | int nn; | 1486 | continue; |
481 | 1487 | ||
482 | assert(adi >= 0); | ||
483 | /* | ||
484 | * We've found something. All viable placements | ||
485 | * involving this square are for domino `adi'. If | ||
486 | * the current placement list for that domino is | ||
487 | * longer than n, reduce it to precisely this | ||
488 | * placement list and we've done something. | ||
489 | */ | ||
490 | nn = 0; | ||
491 | for (k = heads[adi]; k >= 0; k = placements[k]) | ||
492 | nn++; | ||
493 | if (nn > n) { | ||
494 | done_something = true; | ||
495 | #ifdef SOLVER_DIAGNOSTICS | 1488 | #ifdef SOLVER_DIAGNOSTICS |
496 | printf("considering square %d,%d: reducing placements " | 1489 | if (solver_diagnostics) { |
497 | "of domino %d\n", x, y, adi); | 1490 | printf("domino %s occurs more than once in forced chain:", |
1491 | duplicated_domino->name); | ||
1492 | for (k = cstart; k < climit; k++) | ||
1493 | printf(" %s", sc->placements[sc->pc_scratch2[k]].name); | ||
1494 | printf("\n"); | ||
1495 | } | ||
498 | #endif | 1496 | #endif |
1497 | |||
1498 | for (k = cstart; k < climit; k++) | ||
1499 | rule_out_placement(sc, &sc->placements[sc->pc_scratch2[k]]); | ||
1500 | |||
1501 | done_something = true; | ||
1502 | } | ||
1503 | |||
1504 | if (done_something) | ||
1505 | return true; | ||
1506 | |||
1507 | /* | ||
1508 | * A second way in which a whole forcing chain can be ruled out is | ||
1509 | * if it contains all the dominoes that can occupy some other | ||
1510 | * square, so that if the domnioes in the chain were all laid, the | ||
1511 | * other square would be left without any choices. | ||
1512 | * | ||
1513 | * To detect this, we sort the placements again, this time by | ||
1514 | * (domino index, chain index), so that we can easily find a | ||
1515 | * sorted list of chains per domino. That allows us to iterate | ||
1516 | * over the squares and check for a chain id common to all the | ||
1517 | * placements of that square. | ||
1518 | */ | ||
1519 | for (pi = 0; pi < sc->pc; pi++) | ||
1520 | sc->pc_scratch2[pi] = pi; | ||
1521 | arraysort(sc->pc_scratch2, sc->pc, forcing_chain_sq_cmp, sc); | ||
1522 | |||
1523 | /* Store a lookup table of the first entry in pc_scratch2 | ||
1524 | * corresponding to each domino. */ | ||
1525 | for (di = j = 0; j < sc->pc; j++) { | ||
1526 | while (di <= sc->placements[sc->pc_scratch2[j]].domino->index) { | ||
1527 | assert(di < sc->dc); | ||
1528 | sc->dc_scratch[di++] = j; | ||
1529 | } | ||
1530 | } | ||
1531 | assert(di == sc->dc); | ||
1532 | |||
1533 | for (si = 0; si < sc->wh; si++) { | ||
1534 | struct solver_square *sq = &sc->squares[si]; | ||
1535 | int listpos = 0, listsize = 0, listout = 0; | ||
1536 | int exclude[4]; | ||
1537 | int n_exclude; | ||
1538 | |||
1539 | if (sq->nplacements < 2) | ||
1540 | continue; /* too simple to be worth trying */ | ||
1541 | |||
1542 | /* | ||
1543 | * Start by checking for chains this square can actually form | ||
1544 | * part of. We won't consider those. (The aim is to find a | ||
1545 | * completely _different_ square whose placements are all | ||
1546 | * ruled out by a chain.) | ||
1547 | */ | ||
1548 | assert(sq->nplacements <= lenof(exclude)); | ||
1549 | for (j = n_exclude = 0; j < sq->nplacements; j++) | ||
1550 | exclude[n_exclude++] = sc->pc_scratch[sq->placements[j]->index]; | ||
1551 | |||
1552 | for (j = 0; j < sq->nplacements; j++) { | ||
1553 | struct solver_domino *d = sq->placements[j]->domino; | ||
1554 | |||
1555 | listout = listpos = 0; | ||
1556 | |||
1557 | for (k = sc->dc_scratch[d->index]; | ||
1558 | k < sc->pc && sc->placements[sc->pc_scratch2[k]].domino == d; | ||
1559 | k++) { | ||
1560 | int chain = sc->pc_scratch[sc->pc_scratch2[k]]; | ||
1561 | bool keep; | ||
1562 | |||
1563 | if (!sc->placements[sc->pc_scratch2[k]].active) | ||
1564 | continue; | ||
1565 | |||
1566 | if (j == 0) { | ||
1567 | keep = true; | ||
1568 | } else { | ||
1569 | while (listpos < listsize && | ||
1570 | sc->wh_scratch[listpos] < chain) | ||
1571 | listpos++; | ||
1572 | keep = (listpos < listsize && | ||
1573 | sc->wh_scratch[listpos] == chain); | ||
1574 | } | ||
1575 | |||
1576 | for (m = 0; m < n_exclude; m++) | ||
1577 | if (chain == exclude[m]) | ||
1578 | keep = false; | ||
1579 | |||
1580 | if (keep) | ||
1581 | sc->wh_scratch[listout++] = chain; | ||
1582 | } | ||
1583 | |||
1584 | listsize = listout; | ||
1585 | if (listsize == 0) | ||
1586 | break; /* ruled out all chains; terminate loop early */ | ||
1587 | } | ||
1588 | |||
1589 | for (listpos = 0; listpos < listsize; listpos++) { | ||
1590 | int chain = sc->wh_scratch[listpos]; | ||
1591 | |||
1592 | /* | ||
1593 | * We've found a chain we can rule out. | ||
1594 | */ | ||
1595 | #ifdef SOLVER_DIAGNOSTICS | ||
1596 | if (solver_diagnostics) { | ||
1597 | printf("all choices for square %s would be ruled out " | ||
1598 | "by forced chain:", sq->name); | ||
1599 | for (pi = 0; pi < sc->pc; pi++) | ||
1600 | if (sc->pc_scratch[pi] == chain) | ||
1601 | printf(" %s", sc->placements[pi].name); | ||
1602 | printf("\n"); | ||
1603 | } | ||
1604 | #endif | ||
1605 | |||
1606 | for (pi = 0; pi < sc->pc; pi++) | ||
1607 | if (sc->pc_scratch[pi] == chain) | ||
1608 | rule_out_placement(sc, &sc->placements[pi]); | ||
1609 | |||
1610 | done_something = true; | ||
1611 | } | ||
1612 | } | ||
1613 | |||
1614 | /* | ||
1615 | * Another thing you can do with forcing chains, besides ruling | ||
1616 | * out a whole one at a time, is to look at each pair of chains | ||
1617 | * that overlap each other. Each such pair gives you two sets of | ||
1618 | * domino placements, such that if either set is not placed, then | ||
1619 | * the other one must be. | ||
1620 | * | ||
1621 | * This means that any domino which has a placement in _both_ | ||
1622 | * chains of a pair must occupy one of those two placements, i.e. | ||
1623 | * we can rule that domino out anywhere else it might appear. | ||
1624 | */ | ||
1625 | for (di = 0; di < sc->dc; di++) { | ||
1626 | struct solver_domino *d = &sc->dominoes[di]; | ||
1627 | |||
1628 | if (d->nplacements <= 2) | ||
1629 | continue; /* not enough placements to rule one out */ | ||
1630 | |||
1631 | for (j = 0; j+1 < d->nplacements; j++) { | ||
1632 | int ij = d->placements[j]->index; | ||
1633 | int cj = sc->pc_scratch[ij]; | ||
1634 | for (k = j+1; k < d->nplacements; k++) { | ||
1635 | int ik = d->placements[k]->index; | ||
1636 | int ck = sc->pc_scratch[ik]; | ||
1637 | if ((cj ^ ck) == 1) { | ||
499 | /* | 1638 | /* |
500 | * Set all other placements on the list to | 1639 | * Placements j,k of domino d are in complementary |
501 | * impossible. | 1640 | * chains, so we can rule out all the others. |
502 | */ | 1641 | */ |
503 | k = heads[adi]; | 1642 | int i; |
504 | while (k >= 0) { | 1643 | |
505 | int tmp = placements[k]; | 1644 | #ifdef SOLVER_DIAGNOSTICS |
506 | placements[k] = -2; | 1645 | if (solver_diagnostics) { |
507 | k = tmp; | 1646 | printf("domino %s occurs in both complementary " |
1647 | "forced chains:", d->name); | ||
1648 | for (i = 0; i < sc->pc; i++) | ||
1649 | if (sc->pc_scratch[i] == cj) | ||
1650 | printf(" %s", sc->placements[i].name); | ||
1651 | printf(" and"); | ||
1652 | for (i = 0; i < sc->pc; i++) | ||
1653 | if (sc->pc_scratch[i] == ck) | ||
1654 | printf(" %s", sc->placements[i].name); | ||
1655 | printf("\n"); | ||
508 | } | 1656 | } |
509 | /* | 1657 | #endif |
510 | * Set up the new list. | 1658 | |
511 | */ | 1659 | for (i = d->nplacements; i-- > 0 ;) |
512 | heads[adi] = list[0]; | 1660 | if (i != j && i != k) |
513 | for (k = 0; k < n; k++) | 1661 | rule_out_placement(sc, d->placements[i]); |
514 | placements[list[k]] = (k+1 == n ? -1 : list[k+1]); | 1662 | |
1663 | done_something = true; | ||
1664 | goto done_this_domino; | ||
515 | } | 1665 | } |
516 | } | 1666 | } |
517 | } | 1667 | } |
518 | 1668 | ||
519 | if (!done_something) | 1669 | done_this_domino:; |
520 | break; | ||
521 | } | 1670 | } |
522 | 1671 | ||
1672 | return done_something; | ||
1673 | } | ||
1674 | |||
1675 | /* | ||
1676 | * Run the solver until it can't make any more progress. | ||
1677 | * | ||
1678 | * Return value is: | ||
1679 | * 0 = no solution exists (puzzle clues are unsatisfiable) | ||
1680 | * 1 = unique solution found (success!) | ||
1681 | * 2 = multiple possibilities remain (puzzle is ambiguous or solver is not | ||
1682 | * smart enough) | ||
1683 | */ | ||
1684 | static int run_solver(struct solver_scratch *sc, int max_diff_allowed) | ||
1685 | { | ||
1686 | int di, si, pi; | ||
1687 | bool done_something; | ||
1688 | |||
523 | #ifdef SOLVER_DIAGNOSTICS | 1689 | #ifdef SOLVER_DIAGNOSTICS |
524 | printf("after solver:\n"); | 1690 | if (solver_diagnostics) { |
525 | for (i = 0; i <= n; i++) | 1691 | int di, j; |
526 | for (j = 0; j <= i; j++) { | 1692 | printf("Initial possible placements:\n"); |
527 | int k, m; | 1693 | for (di = 0; di < sc->dc; di++) { |
528 | m = 0; | 1694 | struct solver_domino *d = &sc->dominoes[di]; |
529 | printf("%2d [%d %d]:", DINDEX(i, j), i, j); | 1695 | printf(" %s:", d->name); |
530 | for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k]) | 1696 | for (j = 0; j < d->nplacements; j++) |
531 | printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v'); | 1697 | printf(" %s", d->placements[j]->name); |
532 | printf("\n"); | 1698 | printf("\n"); |
533 | } | 1699 | } |
1700 | } | ||
534 | #endif | 1701 | #endif |
535 | 1702 | ||
536 | ret = 1; | 1703 | do { |
537 | for (i = 0; i < wh*2; i++) { | 1704 | done_something = false; |
538 | if (placements[i] == -2) { | 1705 | |
539 | if (output) | 1706 | for (di = 0; di < sc->dc; di++) |
540 | output[i] = -1; /* ruled out */ | 1707 | if (deduce_domino_single_placement(sc, di)) |
541 | } else if (placements[i] != -3) { | 1708 | done_something = true; |
542 | int p1, p2, di; | 1709 | if (done_something) { |
543 | 1710 | sc->max_diff_used = max(sc->max_diff_used, DIFF_TRIVIAL); | |
544 | p1 = i / 2; | 1711 | continue; |
545 | p2 = (i & 1) ? p1 + 1 : p1 + w; | 1712 | } |
546 | di = DINDEX(grid[p1], grid[p2]); | 1713 | |
547 | 1714 | for (si = 0; si < sc->wh; si++) | |
548 | if (i == heads[di] && placements[i] == -1) { | 1715 | if (deduce_square_single_placement(sc, si)) |
549 | if (output) | 1716 | done_something = true; |
550 | output[i] = 1; /* certain */ | 1717 | if (done_something) { |
551 | } else { | 1718 | sc->max_diff_used = max(sc->max_diff_used, DIFF_TRIVIAL); |
552 | if (output) | 1719 | continue; |
553 | output[i] = 0; /* uncertain */ | 1720 | } |
554 | ret = 2; | 1721 | |
1722 | if (max_diff_allowed <= DIFF_TRIVIAL) | ||
1723 | continue; | ||
1724 | |||
1725 | for (si = 0; si < sc->wh; si++) | ||
1726 | if (deduce_square_single_domino(sc, si)) | ||
1727 | done_something = true; | ||
1728 | if (done_something) { | ||
1729 | sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC); | ||
1730 | continue; | ||
1731 | } | ||
1732 | |||
1733 | for (di = 0; di < sc->dc; di++) | ||
1734 | if (deduce_domino_must_overlap(sc, di)) | ||
1735 | done_something = true; | ||
1736 | if (done_something) { | ||
1737 | sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC); | ||
1738 | continue; | ||
1739 | } | ||
1740 | |||
1741 | for (pi = 0; pi < sc->pc; pi++) | ||
1742 | if (deduce_local_duplicate(sc, pi)) | ||
1743 | done_something = true; | ||
1744 | if (done_something) { | ||
1745 | sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC); | ||
1746 | continue; | ||
1747 | } | ||
1748 | |||
1749 | for (pi = 0; pi < sc->pc; pi++) | ||
1750 | if (deduce_local_duplicate_2(sc, pi)) | ||
1751 | done_something = true; | ||
1752 | if (done_something) { | ||
1753 | sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC); | ||
1754 | continue; | ||
1755 | } | ||
1756 | |||
1757 | if (deduce_parity(sc)) | ||
1758 | done_something = true; | ||
1759 | if (done_something) { | ||
1760 | sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC); | ||
1761 | continue; | ||
1762 | } | ||
1763 | |||
1764 | if (max_diff_allowed <= DIFF_BASIC) | ||
1765 | continue; | ||
1766 | |||
1767 | if (deduce_set(sc, false)) | ||
1768 | done_something = true; | ||
1769 | if (done_something) { | ||
1770 | sc->max_diff_used = max(sc->max_diff_used, DIFF_HARD); | ||
1771 | continue; | ||
1772 | } | ||
1773 | |||
1774 | if (max_diff_allowed <= DIFF_HARD) | ||
1775 | continue; | ||
1776 | |||
1777 | if (deduce_set(sc, true)) | ||
1778 | done_something = true; | ||
1779 | if (done_something) { | ||
1780 | sc->max_diff_used = max(sc->max_diff_used, DIFF_EXTREME); | ||
1781 | continue; | ||
1782 | } | ||
1783 | |||
1784 | if (deduce_forcing_chain(sc)) | ||
1785 | done_something = true; | ||
1786 | if (done_something) { | ||
1787 | sc->max_diff_used = max(sc->max_diff_used, DIFF_EXTREME); | ||
1788 | continue; | ||
1789 | } | ||
1790 | |||
1791 | } while (done_something); | ||
1792 | |||
1793 | #ifdef SOLVER_DIAGNOSTICS | ||
1794 | if (solver_diagnostics) { | ||
1795 | int di, j; | ||
1796 | printf("Final possible placements:\n"); | ||
1797 | for (di = 0; di < sc->dc; di++) { | ||
1798 | struct solver_domino *d = &sc->dominoes[di]; | ||
1799 | printf(" %s:", d->name); | ||
1800 | for (j = 0; j < d->nplacements; j++) | ||
1801 | printf(" %s", d->placements[j]->name); | ||
1802 | printf("\n"); | ||
1803 | } | ||
1804 | } | ||
1805 | #endif | ||
1806 | |||
1807 | for (di = 0; di < sc->dc; di++) | ||
1808 | if (sc->dominoes[di].nplacements == 0) | ||
1809 | return 0; | ||
1810 | for (di = 0; di < sc->dc; di++) | ||
1811 | if (sc->dominoes[di].nplacements > 1) | ||
1812 | return 2; | ||
1813 | return 1; | ||
1814 | } | ||
1815 | |||
1816 | /* ---------------------------------------------------------------------- | ||
1817 | * Functions for generating a candidate puzzle (before we run the | ||
1818 | * solver to check it's soluble at the right difficulty level). | ||
1819 | */ | ||
1820 | |||
1821 | struct alloc_val; | ||
1822 | struct alloc_loc; | ||
1823 | |||
1824 | struct alloc_scratch { | ||
1825 | /* Game parameters. */ | ||
1826 | int n, w, h, wh, dc; | ||
1827 | |||
1828 | /* The domino layout. Indexed by squares in the usual y*w+x raster | ||
1829 | * order: layout[i] gives the index of the other square in the | ||
1830 | * same domino as square i. */ | ||
1831 | int *layout; | ||
1832 | |||
1833 | /* The output array, containing a number in every square. */ | ||
1834 | int *numbers; | ||
1835 | |||
1836 | /* List of domino values (i.e. number pairs), indexed by DINDEX. */ | ||
1837 | struct alloc_val *vals; | ||
1838 | |||
1839 | /* List of domino locations, indexed arbitrarily. */ | ||
1840 | struct alloc_loc *locs; | ||
1841 | |||
1842 | /* Preallocated scratch spaces. */ | ||
1843 | int *wh_scratch; /* size wh */ | ||
1844 | int *wh2_scratch; /* size 2*wh */ | ||
1845 | }; | ||
1846 | |||
1847 | struct alloc_val { | ||
1848 | int lo, hi; | ||
1849 | bool confounder; | ||
1850 | }; | ||
1851 | |||
1852 | struct alloc_loc { | ||
1853 | int sq[2]; | ||
1854 | }; | ||
1855 | |||
1856 | static struct alloc_scratch *alloc_make_scratch(int n) | ||
1857 | { | ||
1858 | struct alloc_scratch *as = snew(struct alloc_scratch); | ||
1859 | int lo, hi; | ||
1860 | |||
1861 | as->n = n; | ||
1862 | as->w = n+2; | ||
1863 | as->h = n+1; | ||
1864 | as->wh = as->w * as->h; | ||
1865 | as->dc = DCOUNT(n); | ||
1866 | |||
1867 | as->layout = snewn(as->wh, int); | ||
1868 | as->numbers = snewn(as->wh, int); | ||
1869 | as->vals = snewn(as->dc, struct alloc_val); | ||
1870 | as->locs = snewn(as->dc, struct alloc_loc); | ||
1871 | as->wh_scratch = snewn(as->wh, int); | ||
1872 | as->wh2_scratch = snewn(as->wh * 2, int); | ||
1873 | |||
1874 | for (hi = 0; hi <= n; hi++) | ||
1875 | for (lo = 0; lo <= hi; lo++) { | ||
1876 | struct alloc_val *v = &as->vals[DINDEX(hi, lo)]; | ||
1877 | v->lo = lo; | ||
1878 | v->hi = hi; | ||
1879 | } | ||
1880 | |||
1881 | return as; | ||
1882 | } | ||
1883 | |||
1884 | static void alloc_free_scratch(struct alloc_scratch *as) | ||
1885 | { | ||
1886 | sfree(as->layout); | ||
1887 | sfree(as->numbers); | ||
1888 | sfree(as->vals); | ||
1889 | sfree(as->locs); | ||
1890 | sfree(as->wh_scratch); | ||
1891 | sfree(as->wh2_scratch); | ||
1892 | sfree(as); | ||
1893 | } | ||
1894 | |||
1895 | static void alloc_make_layout(struct alloc_scratch *as, random_state *rs) | ||
1896 | { | ||
1897 | int i, pos; | ||
1898 | |||
1899 | domino_layout_prealloc(as->w, as->h, rs, | ||
1900 | as->layout, as->wh_scratch, as->wh2_scratch); | ||
1901 | |||
1902 | for (i = pos = 0; i < as->wh; i++) { | ||
1903 | if (as->layout[i] > i) { | ||
1904 | struct alloc_loc *loc; | ||
1905 | assert(pos < as->dc); | ||
1906 | |||
1907 | loc = &as->locs[pos++]; | ||
1908 | loc->sq[0] = i; | ||
1909 | loc->sq[1] = as->layout[i]; | ||
1910 | } | ||
1911 | } | ||
1912 | assert(pos == as->dc); | ||
1913 | } | ||
1914 | |||
1915 | static void alloc_trivial(struct alloc_scratch *as, random_state *rs) | ||
1916 | { | ||
1917 | int i; | ||
1918 | for (i = 0; i < as->dc; i++) | ||
1919 | as->wh_scratch[i] = i; | ||
1920 | shuffle(as->wh_scratch, as->dc, sizeof(*as->wh_scratch), rs); | ||
1921 | |||
1922 | for (i = 0; i < as->dc; i++) { | ||
1923 | struct alloc_val *val = &as->vals[as->wh_scratch[i]]; | ||
1924 | struct alloc_loc *loc = &as->locs[i]; | ||
1925 | int which_lo = random_upto(rs, 2), which_hi = 1 - which_lo; | ||
1926 | as->numbers[loc->sq[which_lo]] = val->lo; | ||
1927 | as->numbers[loc->sq[which_hi]] = val->hi; | ||
1928 | } | ||
1929 | } | ||
1930 | |||
1931 | /* | ||
1932 | * Given a domino location in the form of two square indices, compute | ||
1933 | * the square indices of the domino location that would lie on one | ||
1934 | * side of it. Returns false if the location would be outside the | ||
1935 | * grid, or if it isn't actually a domino in the layout. | ||
1936 | */ | ||
1937 | static bool alloc_find_neighbour( | ||
1938 | struct alloc_scratch *as, int p0, int p1, int *n0, int *n1) | ||
1939 | { | ||
1940 | int x0 = p0 % as->w, y0 = p0 / as->w, x1 = p1 % as->w, y1 = p1 / as->w; | ||
1941 | int dy = y1-y0, dx = x1-x0; | ||
1942 | int nx0 = x0 + dy, ny0 = y0 - dx, nx1 = x1 + dy, ny1 = y1 - dx; | ||
1943 | int np0, np1; | ||
1944 | |||
1945 | if (!(nx0 >= 0 && nx0 < as->w && ny0 >= 0 && ny0 < as->h && | ||
1946 | nx1 >= 1 && nx1 < as->w && ny1 >= 1 && ny1 < as->h)) | ||
1947 | return false; /* out of bounds */ | ||
1948 | |||
1949 | np0 = ny0 * as->w + nx0; | ||
1950 | np1 = ny1 * as->w + nx1; | ||
1951 | if (as->layout[np0] != np1) | ||
1952 | return false; /* not a domino */ | ||
1953 | |||
1954 | *n0 = np0; | ||
1955 | *n1 = np1; | ||
1956 | return true; | ||
1957 | } | ||
1958 | |||
1959 | static bool alloc_try_unique(struct alloc_scratch *as, random_state *rs) | ||
1960 | { | ||
1961 | int i; | ||
1962 | for (i = 0; i < as->dc; i++) | ||
1963 | as->wh_scratch[i] = i; | ||
1964 | shuffle(as->wh_scratch, as->dc, sizeof(*as->wh_scratch), rs); | ||
1965 | for (i = 0; i < as->dc; i++) | ||
1966 | as->wh2_scratch[i] = i; | ||
1967 | shuffle(as->wh2_scratch, as->dc, sizeof(*as->wh2_scratch), rs); | ||
1968 | |||
1969 | for (i = 0; i < as->wh; i++) | ||
1970 | as->numbers[i] = -1; | ||
1971 | |||
1972 | for (i = 0; i < as->dc; i++) { | ||
1973 | struct alloc_val *val = &as->vals[as->wh_scratch[i]]; | ||
1974 | struct alloc_loc *loc = &as->locs[as->wh2_scratch[i]]; | ||
1975 | int which_lo, which_hi; | ||
1976 | bool can_lo_0 = true, can_lo_1 = true; | ||
1977 | int n0, n1; | ||
1978 | |||
1979 | /* | ||
1980 | * This is basically the same strategy as alloc_trivial: | ||
1981 | * simply iterate through the locations and values in random | ||
1982 | * relative order and pair them up. But we make sure to avoid | ||
1983 | * the most common, and also simplest, cause of a non-unique | ||
1984 | * solution:two dominoes side by side, sharing a number at | ||
1985 | * opposite ends. Any section of that form automatically leads | ||
1986 | * to an alternative solution: | ||
1987 | * | ||
1988 | * +-------+ +---+---+ | ||
1989 | * | 1 2 | | 1 | 2 | | ||
1990 | * +-------+ <-> | | | | ||
1991 | * | 2 3 | | 2 | 3 | | ||
1992 | * +-------+ +---+---+ | ||
1993 | * | ||
1994 | * So as we place each domino, we check for a neighbouring | ||
1995 | * domino on each side, and if there is one, rule out any | ||
1996 | * placement of _this_ domino that places a number diagonally | ||
1997 | * opposite the same number in the neighbour. | ||
1998 | * | ||
1999 | * Sometimes this can fail completely, if a domino on each | ||
2000 | * side is already placed and between them they rule out all | ||
2001 | * placements of this one. But it happens rarely enough that | ||
2002 | * it's fine to just abort and try the layout again. | ||
2003 | */ | ||
2004 | |||
2005 | if (alloc_find_neighbour(as, loc->sq[0], loc->sq[1], &n0, &n1) && | ||
2006 | (as->numbers[n0] == val->hi || as->numbers[n1] == val->lo)) | ||
2007 | can_lo_0 = false; | ||
2008 | if (alloc_find_neighbour(as, loc->sq[1], loc->sq[0], &n0, &n1) && | ||
2009 | (as->numbers[n0] == val->hi || as->numbers[n1] == val->lo)) | ||
2010 | can_lo_1 = false; | ||
2011 | |||
2012 | if (!can_lo_0 && !can_lo_1) | ||
2013 | return false; /* layout failed */ | ||
2014 | else if (can_lo_0 && can_lo_1) | ||
2015 | which_lo = random_upto(rs, 2); | ||
2016 | else | ||
2017 | which_lo = can_lo_0 ? 0 : 1; | ||
2018 | |||
2019 | which_hi = 1 - which_lo; | ||
2020 | as->numbers[loc->sq[which_lo]] = val->lo; | ||
2021 | as->numbers[loc->sq[which_hi]] = val->hi; | ||
2022 | } | ||
2023 | |||
2024 | return true; | ||
2025 | } | ||
2026 | |||
2027 | static bool alloc_try_hard(struct alloc_scratch *as, random_state *rs) | ||
2028 | { | ||
2029 | int i, x, y, hi, lo, vals, locs, confounders_needed; | ||
2030 | bool ok; | ||
2031 | |||
2032 | for (i = 0; i < as->wh; i++) | ||
2033 | as->numbers[i] = -1; | ||
2034 | |||
2035 | /* | ||
2036 | * Shuffle the location indices. | ||
2037 | */ | ||
2038 | for (i = 0; i < as->dc; i++) | ||
2039 | as->wh2_scratch[i] = i; | ||
2040 | shuffle(as->wh2_scratch, as->dc, sizeof(*as->wh2_scratch), rs); | ||
2041 | |||
2042 | /* | ||
2043 | * Start by randomly placing the double dominoes, to give a | ||
2044 | * starting instance of every number to try to put other things | ||
2045 | * next to. | ||
2046 | */ | ||
2047 | for (i = 0; i <= as->n; i++) | ||
2048 | as->wh_scratch[i] = DINDEX(i, i); | ||
2049 | shuffle(as->wh_scratch, i, sizeof(*as->wh_scratch), rs); | ||
2050 | for (i = 0; i <= as->n; i++) { | ||
2051 | struct alloc_loc *loc = &as->locs[as->wh2_scratch[i]]; | ||
2052 | as->numbers[loc->sq[0]] = as->numbers[loc->sq[1]] = i; | ||
2053 | } | ||
2054 | |||
2055 | /* | ||
2056 | * Find all the dominoes that don't yet have a _wrong_ placement | ||
2057 | * somewhere in the grid. | ||
2058 | */ | ||
2059 | for (i = 0; i < as->dc; i++) | ||
2060 | as->vals[i].confounder = false; | ||
2061 | for (y = 0; y < as->h; y++) { | ||
2062 | for (x = 0; x < as->w; x++) { | ||
2063 | int p = y * as->w + x; | ||
2064 | if (as->numbers[p] == -1) | ||
2065 | continue; | ||
2066 | |||
2067 | if (x+1 < as->w) { | ||
2068 | int p1 = y * as->w + (x+1); | ||
2069 | if (as->layout[p] != p1 && as->numbers[p1] != -1) | ||
2070 | as->vals[DINDEX(as->numbers[p], as->numbers[p1])] | ||
2071 | .confounder = true; | ||
2072 | } | ||
2073 | if (y+1 < as->h) { | ||
2074 | int p1 = (y+1) * as->w + x; | ||
2075 | if (as->layout[p] != p1 && as->numbers[p1] != -1) | ||
2076 | as->vals[DINDEX(as->numbers[p], as->numbers[p1])] | ||
2077 | .confounder = true; | ||
555 | } | 2078 | } |
556 | } | 2079 | } |
557 | } | 2080 | } |
558 | 2081 | ||
559 | done: | 2082 | for (i = confounders_needed = 0; i < as->dc; i++) |
2083 | if (!as->vals[i].confounder) | ||
2084 | confounders_needed++; | ||
2085 | |||
560 | /* | 2086 | /* |
561 | * Free working data. | 2087 | * Make a shuffled list of all the unplaced dominoes, and go |
2088 | * through it trying to find a placement for each one that also | ||
2089 | * fills in at least one of the needed confounders. | ||
562 | */ | 2090 | */ |
563 | sfree(placements); | 2091 | vals = 0; |
564 | sfree(heads); | 2092 | for (hi = 0; hi <= as->n; hi++) |
2093 | for (lo = 0; lo < hi; lo++) | ||
2094 | as->wh_scratch[vals++] = DINDEX(hi, lo); | ||
2095 | shuffle(as->wh_scratch, vals, sizeof(*as->wh_scratch), rs); | ||
2096 | |||
2097 | locs = as->dc; | ||
2098 | |||
2099 | while (vals > 0) { | ||
2100 | int valpos, valout, oldvals = vals; | ||
2101 | |||
2102 | for (valpos = valout = 0; valpos < vals; valpos++) { | ||
2103 | int validx = as->wh_scratch[valpos]; | ||
2104 | struct alloc_val *val = &as->vals[validx]; | ||
2105 | struct alloc_loc *loc; | ||
2106 | int locpos, si, which_lo; | ||
2107 | |||
2108 | for (locpos = 0; locpos < locs; locpos++) { | ||
2109 | int locidx = as->wh2_scratch[locpos]; | ||
2110 | int wi, flip; | ||
2111 | |||
2112 | loc = &as->locs[locidx]; | ||
2113 | if (as->numbers[loc->sq[0]] != -1) | ||
2114 | continue; /* this location is already filled */ | ||
2115 | |||
2116 | flip = random_upto(rs, 2); | ||
2117 | |||
2118 | /* Try this location both ways round. */ | ||
2119 | for (wi = 0; wi < 2; wi++) { | ||
2120 | int n0, n1; | ||
2121 | |||
2122 | which_lo = wi ^ flip; | ||
2123 | |||
2124 | /* First, do the same check as in alloc_try_unique, to | ||
2125 | * avoid making an obviously insoluble puzzle. */ | ||
2126 | if (alloc_find_neighbour(as, loc->sq[which_lo], | ||
2127 | loc->sq[1-which_lo], &n0, &n1) && | ||
2128 | (as->numbers[n0] == val->hi || | ||
2129 | as->numbers[n1] == val->lo)) | ||
2130 | break; /* can't place it this way round */ | ||
2131 | |||
2132 | if (confounders_needed == 0) | ||
2133 | goto place_ok; | ||
2134 | |||
2135 | /* Look to see if we're adding at least one | ||
2136 | * previously absent confounder. */ | ||
2137 | for (si = 0; si < 2; si++) { | ||
2138 | int x = loc->sq[si] % as->w, y = loc->sq[si] / as->w; | ||
2139 | int n = (si == which_lo ? val->lo : val->hi); | ||
2140 | int d; | ||
2141 | for (d = 0; d < 4; d++) { | ||
2142 | int dx = d==0 ? +1 : d==2 ? -1 : 0; | ||
2143 | int dy = d==1 ? +1 : d==3 ? -1 : 0; | ||
2144 | int x1 = x+dx, y1 = y+dy, p1 = y1 * as->w + x1; | ||
2145 | if (x1 >= 0 && x1 < as->w && | ||
2146 | y1 >= 0 && y1 < as->h && | ||
2147 | as->numbers[p1] != -1 && | ||
2148 | !(as->vals[DINDEX(n, as->numbers[p1])] | ||
2149 | .confounder)) { | ||
2150 | /* | ||
2151 | * Place this domino. | ||
2152 | */ | ||
2153 | goto place_ok; | ||
2154 | } | ||
2155 | } | ||
2156 | } | ||
2157 | } | ||
2158 | } | ||
565 | 2159 | ||
566 | return ret; | 2160 | /* If we get here without executing 'goto place_ok', we |
567 | } | 2161 | * didn't find anywhere useful to put this domino. Put it |
2162 | * back on the list for the next pass. */ | ||
2163 | as->wh_scratch[valout++] = validx; | ||
2164 | continue; | ||
2165 | |||
2166 | place_ok:; | ||
2167 | |||
2168 | /* We've found a domino to place. Place it, and fill in | ||
2169 | * all the confounders it adds. */ | ||
2170 | as->numbers[loc->sq[which_lo]] = val->lo; | ||
2171 | as->numbers[loc->sq[1 - which_lo]] = val->hi; | ||
2172 | |||
2173 | for (si = 0; si < 2; si++) { | ||
2174 | int p = loc->sq[si]; | ||
2175 | int n = as->numbers[p]; | ||
2176 | int x = p % as->w, y = p / as->w; | ||
2177 | int d; | ||
2178 | for (d = 0; d < 4; d++) { | ||
2179 | int dx = d==0 ? +1 : d==2 ? -1 : 0; | ||
2180 | int dy = d==1 ? +1 : d==3 ? -1 : 0; | ||
2181 | int x1 = x+dx, y1 = y+dy, p1 = y1 * as->w + x1; | ||
2182 | |||
2183 | if (x1 >= 0 && x1 < as->w && y1 >= 0 && y1 < as->h && | ||
2184 | p1 != loc->sq[1-si] && as->numbers[p1] != -1) { | ||
2185 | int di = DINDEX(n, as->numbers[p1]); | ||
2186 | if (!as->vals[di].confounder) | ||
2187 | confounders_needed--; | ||
2188 | as->vals[di].confounder = true; | ||
2189 | } | ||
2190 | } | ||
2191 | } | ||
2192 | } | ||
568 | 2193 | ||
569 | /* ---------------------------------------------------------------------- | 2194 | vals = valout; |
570 | * End of solver code. | 2195 | |
571 | */ | 2196 | if (oldvals == vals) |
2197 | break; | ||
2198 | } | ||
2199 | |||
2200 | ok = true; | ||
2201 | |||
2202 | for (i = 0; i < as->dc; i++) | ||
2203 | if (!as->vals[i].confounder) | ||
2204 | ok = false; | ||
2205 | for (i = 0; i < as->wh; i++) | ||
2206 | if (as->numbers[i] == -1) | ||
2207 | ok = false; | ||
2208 | |||
2209 | return ok; | ||
2210 | } | ||
572 | 2211 | ||
573 | static char *new_game_desc(const game_params *params, random_state *rs, | 2212 | static char *new_game_desc(const game_params *params, random_state *rs, |
574 | char **aux, bool interactive) | 2213 | char **aux, bool interactive) |
575 | { | 2214 | { |
576 | int n = params->n, w = n+2, h = n+1, wh = w*h; | 2215 | int n = params->n, w = n+2, h = n+1, wh = w*h, diff = params->diff; |
577 | int *grid, *grid2, *list; | 2216 | struct solver_scratch *sc; |
2217 | struct alloc_scratch *as; | ||
578 | int i, j, k, len; | 2218 | int i, j, k, len; |
579 | char *ret; | 2219 | char *ret; |
580 | 2220 | ||
2221 | #ifndef OMIT_DIFFICULTY_CAP | ||
2222 | /* | ||
2223 | * Cap the difficulty level for small puzzles which would | ||
2224 | * otherwise become impossible to generate. | ||
2225 | * | ||
2226 | * Under an #ifndef, to make it easy to remove this cap for the | ||
2227 | * purpose of re-testing what it ought to be. | ||
2228 | */ | ||
2229 | if (diff != DIFF_AMBIGUOUS) { | ||
2230 | if (n == 1 && diff > DIFF_TRIVIAL) | ||
2231 | diff = DIFF_TRIVIAL; | ||
2232 | if (n == 2 && diff > DIFF_BASIC) | ||
2233 | diff = DIFF_BASIC; | ||
2234 | } | ||
2235 | #endif /* OMIT_DIFFICULTY_CAP */ | ||
2236 | |||
581 | /* | 2237 | /* |
582 | * Allocate space in which to lay the grid out. | 2238 | * Allocate space in which to lay the grid out. |
583 | */ | 2239 | */ |
584 | grid = snewn(wh, int); | 2240 | sc = solver_make_scratch(n); |
585 | grid2 = snewn(wh, int); | 2241 | as = alloc_make_scratch(n); |
586 | list = snewn(2*wh, int); | ||
587 | 2242 | ||
588 | /* | 2243 | /* |
589 | * I haven't been able to think of any particularly clever | 2244 | * I haven't been able to think of any particularly clever |
@@ -614,91 +2269,75 @@ static char *new_game_desc(const game_params *params, random_state *rs, | |||
614 | * and 26 respectively, which is a lot more sensible. | 2269 | * and 26 respectively, which is a lot more sensible. |
615 | */ | 2270 | */ |
616 | 2271 | ||
617 | do { | 2272 | while (1) { |
618 | domino_layout_prealloc(w, h, rs, grid, grid2, list); | 2273 | alloc_make_layout(as, rs); |
2274 | |||
2275 | if (diff == DIFF_AMBIGUOUS) { | ||
2276 | /* Just assign numbers to each domino completely at random. */ | ||
2277 | alloc_trivial(as, rs); | ||
2278 | } else if (diff < DIFF_HARD) { | ||
2279 | /* Try to rule out the most common case of a non-unique solution */ | ||
2280 | if (!alloc_try_unique(as, rs)) | ||
2281 | continue; | ||
2282 | } else { | ||
2283 | /* | ||
2284 | * For Hard puzzles and above, we'd like there not to be | ||
2285 | * any easy toehold to start with. | ||
2286 | * | ||
2287 | * Mostly, that's arranged by alloc_try_hard, which will | ||
2288 | * ensure that no domino starts off with only one | ||
2289 | * potential placement. But a few other deductions | ||
2290 | * possible at Basic level can still sneak through the | ||
2291 | * cracks - for example, if the only two placements of one | ||
2292 | * domino overlap in a square, and you therefore rule out | ||
2293 | * some other domino that can use that square, you might | ||
2294 | * then find that _that_ domino now has only one | ||
2295 | * placement, and you've made a start. | ||
2296 | * | ||
2297 | * Of course, the main difficulty-level check will still | ||
2298 | * guarantee that you have to do a harder deduction | ||
2299 | * _somewhere_ in the grid. But it's more elegant if | ||
2300 | * there's nowhere obvious to get started at all. | ||
2301 | */ | ||
2302 | int di; | ||
2303 | bool ok; | ||
619 | 2304 | ||
620 | /* | 2305 | if (!alloc_try_hard(as, rs)) |
621 | * Now we have a complete layout covering the whole | 2306 | continue; |
622 | * rectangle with dominoes. So shuffle the actual domino | ||
623 | * values and fill the rectangle with numbers. | ||
624 | */ | ||
625 | k = 0; | ||
626 | for (i = 0; i <= params->n; i++) | ||
627 | for (j = 0; j <= i; j++) { | ||
628 | list[k++] = i; | ||
629 | list[k++] = j; | ||
630 | } | ||
631 | shuffle(list, k/2, 2*sizeof(*list), rs); | ||
632 | j = 0; | ||
633 | for (i = 0; i < wh; i++) | ||
634 | if (grid[i] > i) { | ||
635 | /* Optionally flip the domino round. */ | ||
636 | int flip = -1; | ||
637 | 2307 | ||
638 | if (params->unique) { | 2308 | solver_setup_grid(sc, as->numbers); |
639 | int t1, t2; | 2309 | if (run_solver(sc, DIFF_BASIC) < 2) |
640 | /* | 2310 | continue; |
641 | * If we're after a unique solution, we can do | ||
642 | * something here to improve the chances. If | ||
643 | * we're placing a domino so that it forms a | ||
644 | * 2x2 rectangle with one we've already placed, | ||
645 | * and if that domino and this one share a | ||
646 | * number, we can try not to put them so that | ||
647 | * the identical numbers are diagonally | ||
648 | * separated, because that automatically causes | ||
649 | * non-uniqueness: | ||
650 | * | ||
651 | * +---+ +-+-+ | ||
652 | * |2 3| |2|3| | ||
653 | * +---+ -> | | | | ||
654 | * |4 2| |4|2| | ||
655 | * +---+ +-+-+ | ||
656 | */ | ||
657 | t1 = i; | ||
658 | t2 = grid[i]; | ||
659 | if (t2 == t1 + w) { /* this domino is vertical */ | ||
660 | if (t1 % w > 0 &&/* and not on the left hand edge */ | ||
661 | grid[t1-1] == t2-1 &&/* alongside one to left */ | ||
662 | (grid2[t1-1] == list[j] || /* and has a number */ | ||
663 | grid2[t1-1] == list[j+1] || /* in common */ | ||
664 | grid2[t2-1] == list[j] || | ||
665 | grid2[t2-1] == list[j+1])) { | ||
666 | if (grid2[t1-1] == list[j] || | ||
667 | grid2[t2-1] == list[j+1]) | ||
668 | flip = 0; | ||
669 | else | ||
670 | flip = 1; | ||
671 | } | ||
672 | } else { /* this domino is horizontal */ | ||
673 | if (t1 / w > 0 &&/* and not on the top edge */ | ||
674 | grid[t1-w] == t2-w &&/* alongside one above */ | ||
675 | (grid2[t1-w] == list[j] || /* and has a number */ | ||
676 | grid2[t1-w] == list[j+1] || /* in common */ | ||
677 | grid2[t2-w] == list[j] || | ||
678 | grid2[t2-w] == list[j+1])) { | ||
679 | if (grid2[t1-w] == list[j] || | ||
680 | grid2[t2-w] == list[j+1]) | ||
681 | flip = 0; | ||
682 | else | ||
683 | flip = 1; | ||
684 | } | ||
685 | } | ||
686 | } | ||
687 | 2311 | ||
688 | if (flip < 0) | 2312 | ok = true; |
689 | flip = random_upto(rs, 2); | 2313 | for (di = 0; di < sc->dc; di++) |
2314 | if (sc->dominoes[di].nplacements <= 1) { | ||
2315 | ok = false; | ||
2316 | break; | ||
2317 | } | ||
690 | 2318 | ||
691 | grid2[i] = list[j + flip]; | 2319 | if (!ok) { |
692 | grid2[grid[i]] = list[j + 1 - flip]; | 2320 | continue; |
693 | j += 2; | ||
694 | } | 2321 | } |
695 | assert(j == k); | 2322 | } |
696 | } while (params->unique && solver(w, h, n, grid2, NULL) > 1); | 2323 | |
2324 | if (diff != DIFF_AMBIGUOUS) { | ||
2325 | int solver_result; | ||
2326 | solver_setup_grid(sc, as->numbers); | ||
2327 | solver_result = run_solver(sc, diff); | ||
2328 | if (solver_result > 1) | ||
2329 | continue; /* puzzle couldn't be solved at this difficulty */ | ||
2330 | if (sc->max_diff_used < diff) | ||
2331 | continue; /* puzzle _could_ be solved at easier difficulty */ | ||
2332 | } | ||
2333 | |||
2334 | break; | ||
2335 | } | ||
697 | 2336 | ||
698 | #ifdef GENERATION_DIAGNOSTICS | 2337 | #ifdef GENERATION_DIAGNOSTICS |
699 | for (j = 0; j < h; j++) { | 2338 | for (j = 0; j < h; j++) { |
700 | for (i = 0; i < w; i++) { | 2339 | for (i = 0; i < w; i++) { |
701 | putchar('0' + grid2[j*w+i]); | 2340 | putchar('0' + as->numbers[j*w+i]); |
702 | } | 2341 | } |
703 | putchar('\n'); | 2342 | putchar('\n'); |
704 | } | 2343 | } |
@@ -738,7 +2377,7 @@ static char *new_game_desc(const game_params *params, random_state *rs, | |||
738 | ret = snewn(len+1, char); | 2377 | ret = snewn(len+1, char); |
739 | j = 0; | 2378 | j = 0; |
740 | for (i = 0; i < wh; i++) { | 2379 | for (i = 0; i < wh; i++) { |
741 | k = grid2[i]; | 2380 | k = as->numbers[i]; |
742 | if (k < 10) | 2381 | if (k < 10) |
743 | ret[j++] = '0' + k; | 2382 | ret[j++] = '0' + k; |
744 | else | 2383 | else |
@@ -755,7 +2394,7 @@ static char *new_game_desc(const game_params *params, random_state *rs, | |||
755 | char *auxinfo = snewn(wh+1, char); | 2394 | char *auxinfo = snewn(wh+1, char); |
756 | 2395 | ||
757 | for (i = 0; i < wh; i++) { | 2396 | for (i = 0; i < wh; i++) { |
758 | int v = grid[i]; | 2397 | int v = as->layout[i]; |
759 | auxinfo[i] = (v == i+1 ? 'L' : v == i-1 ? 'R' : | 2398 | auxinfo[i] = (v == i+1 ? 'L' : v == i-1 ? 'R' : |
760 | v == i+w ? 'T' : v == i-w ? 'B' : '.'); | 2399 | v == i+w ? 'T' : v == i-w ? 'B' : '.'); |
761 | } | 2400 | } |
@@ -764,9 +2403,8 @@ static char *new_game_desc(const game_params *params, random_state *rs, | |||
764 | *aux = auxinfo; | 2403 | *aux = auxinfo; |
765 | } | 2404 | } |
766 | 2405 | ||
767 | sfree(list); | 2406 | solver_free_scratch(sc); |
768 | sfree(grid2); | 2407 | alloc_free_scratch(as); |
769 | sfree(grid); | ||
770 | 2408 | ||
771 | return ret; | 2409 | return ret; |
772 | } | 2410 | } |
@@ -898,14 +2536,62 @@ static void free_game(game_state *state) | |||
898 | sfree(state); | 2536 | sfree(state); |
899 | } | 2537 | } |
900 | 2538 | ||
2539 | static char *solution_move_string(struct solver_scratch *sc) | ||
2540 | { | ||
2541 | char *ret; | ||
2542 | int retlen, retsize; | ||
2543 | int i, pass; | ||
2544 | |||
2545 | /* | ||
2546 | * First make a pass putting in edges for -1, then make a pass | ||
2547 | * putting in dominoes for +1. | ||
2548 | */ | ||
2549 | retsize = 256; | ||
2550 | ret = snewn(retsize, char); | ||
2551 | retlen = sprintf(ret, "S"); | ||
2552 | |||
2553 | for (pass = 0; pass < 2; pass++) { | ||
2554 | char type = "ED"[pass]; | ||
2555 | |||
2556 | for (i = 0; i < sc->pc; i++) { | ||
2557 | struct solver_placement *p = &sc->placements[i]; | ||
2558 | char buf[80]; | ||
2559 | int extra; | ||
2560 | |||
2561 | if (pass == 0) { | ||
2562 | /* Emit a barrier if this placement is ruled out for | ||
2563 | * the domino. */ | ||
2564 | if (p->active) | ||
2565 | continue; | ||
2566 | } else { | ||
2567 | /* Emit a domino if this placement is the only one not | ||
2568 | * ruled out. */ | ||
2569 | if (!p->active || p->domino->nplacements > 1) | ||
2570 | continue; | ||
2571 | } | ||
2572 | |||
2573 | extra = sprintf(buf, ";%c%d,%d", type, | ||
2574 | p->squares[0]->index, p->squares[1]->index); | ||
2575 | |||
2576 | if (retlen + extra + 1 >= retsize) { | ||
2577 | retsize = retlen + extra + 256; | ||
2578 | ret = sresize(ret, retsize, char); | ||
2579 | } | ||
2580 | strcpy(ret + retlen, buf); | ||
2581 | retlen += extra; | ||
2582 | } | ||
2583 | } | ||
2584 | |||
2585 | return ret; | ||
2586 | } | ||
2587 | |||
901 | static char *solve_game(const game_state *state, const game_state *currstate, | 2588 | static char *solve_game(const game_state *state, const game_state *currstate, |
902 | const char *aux, const char **error) | 2589 | const char *aux, const char **error) |
903 | { | 2590 | { |
904 | int n = state->params.n, w = n+2, h = n+1, wh = w*h; | 2591 | int n = state->params.n, w = n+2, h = n+1, wh = w*h; |
905 | int *placements; | ||
906 | char *ret; | 2592 | char *ret; |
907 | int retlen, retsize; | 2593 | int retlen, retsize; |
908 | int i, v; | 2594 | int i; |
909 | char buf[80]; | 2595 | char buf[80]; |
910 | int extra; | 2596 | int extra; |
911 | 2597 | ||
@@ -931,38 +2617,11 @@ static char *solve_game(const game_state *state, const game_state *currstate, | |||
931 | } | 2617 | } |
932 | 2618 | ||
933 | } else { | 2619 | } else { |
934 | 2620 | struct solver_scratch *sc = solver_make_scratch(n); | |
935 | placements = snewn(wh*2, int); | 2621 | solver_setup_grid(sc, state->numbers->numbers); |
936 | for (i = 0; i < wh*2; i++) | 2622 | run_solver(sc, DIFFCOUNT); |
937 | placements[i] = -3; | 2623 | ret = solution_move_string(sc); |
938 | solver(w, h, n, state->numbers->numbers, placements); | 2624 | solver_free_scratch(sc); |
939 | |||
940 | /* | ||
941 | * First make a pass putting in edges for -1, then make a pass | ||
942 | * putting in dominoes for +1. | ||
943 | */ | ||
944 | retsize = 256; | ||
945 | ret = snewn(retsize, char); | ||
946 | retlen = sprintf(ret, "S"); | ||
947 | |||
948 | for (v = -1; v <= +1; v += 2) | ||
949 | for (i = 0; i < wh*2; i++) | ||
950 | if (placements[i] == v) { | ||
951 | int p1 = i / 2; | ||
952 | int p2 = (i & 1) ? p1+1 : p1+w; | ||
953 | |||
954 | extra = sprintf(buf, ";%c%d,%d", | ||
955 | (int)(v==-1 ? 'E' : 'D'), p1, p2); | ||
956 | |||
957 | if (retlen + extra + 1 >= retsize) { | ||
958 | retsize = retlen + extra + 256; | ||
959 | ret = sresize(ret, retsize, char); | ||
960 | } | ||
961 | strcpy(ret + retlen, buf); | ||
962 | retlen += extra; | ||
963 | } | ||
964 | |||
965 | sfree(placements); | ||
966 | } | 2625 | } |
967 | 2626 | ||
968 | return ret; | 2627 | return ret; |
@@ -1770,5 +3429,98 @@ const struct game thegame = { | |||
1770 | 0, /* flags */ | 3429 | 0, /* flags */ |
1771 | }; | 3430 | }; |
1772 | 3431 | ||
3432 | #ifdef STANDALONE_SOLVER | ||
3433 | |||
3434 | int main(int argc, char **argv) | ||
3435 | { | ||
3436 | game_params *p; | ||
3437 | game_state *s, *s2; | ||
3438 | char *id = NULL, *desc; | ||
3439 | int maxdiff = DIFFCOUNT; | ||
3440 | const char *err; | ||
3441 | bool grade = false, diagnostics = false; | ||
3442 | struct solver_scratch *sc; | ||
3443 | int retd; | ||
3444 | |||
3445 | while (--argc > 0) { | ||
3446 | char *p = *++argv; | ||
3447 | if (!strcmp(p, "-v")) { | ||
3448 | diagnostics = true; | ||
3449 | } else if (!strcmp(p, "-g")) { | ||
3450 | grade = true; | ||
3451 | } else if (!strncmp(p, "-d", 2) && p[2] && !p[3]) { | ||
3452 | int i; | ||
3453 | bool bad = true; | ||
3454 | for (i = 0; i < lenof(dominosa_diffchars); i++) | ||
3455 | if (dominosa_diffchars[i] != DIFF_AMBIGUOUS && | ||
3456 | dominosa_diffchars[i] == p[2]) { | ||
3457 | bad = false; | ||
3458 | maxdiff = i; | ||
3459 | break; | ||
3460 | } | ||
3461 | if (bad) { | ||
3462 | fprintf(stderr, "%s: unrecognised difficulty `%c'\n", | ||
3463 | argv[0], p[2]); | ||
3464 | return 1; | ||
3465 | } | ||
3466 | } else if (*p == '-') { | ||
3467 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
3468 | return 1; | ||
3469 | } else { | ||
3470 | id = p; | ||
3471 | } | ||
3472 | } | ||
3473 | |||
3474 | if (!id) { | ||
3475 | fprintf(stderr, "usage: %s [-v | -g] <game_id>\n", argv[0]); | ||
3476 | return 1; | ||
3477 | } | ||
3478 | |||
3479 | desc = strchr(id, ':'); | ||
3480 | if (!desc) { | ||
3481 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
3482 | return 1; | ||
3483 | } | ||
3484 | *desc++ = '\0'; | ||
3485 | |||
3486 | p = default_params(); | ||
3487 | decode_params(p, id); | ||
3488 | err = validate_desc(p, desc); | ||
3489 | if (err) { | ||
3490 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
3491 | return 1; | ||
3492 | } | ||
3493 | s = new_game(NULL, p, desc); | ||
3494 | |||
3495 | solver_diagnostics = diagnostics; | ||
3496 | sc = solver_make_scratch(p->n); | ||
3497 | solver_setup_grid(sc, s->numbers->numbers); | ||
3498 | retd = run_solver(sc, maxdiff); | ||
3499 | if (retd == 0) { | ||
3500 | printf("Puzzle is inconsistent\n"); | ||
3501 | } else if (grade) { | ||
3502 | printf("Difficulty rating: %s\n", | ||
3503 | dominosa_diffnames[sc->max_diff_used]); | ||
3504 | } else { | ||
3505 | char *move, *text; | ||
3506 | move = solution_move_string(sc); | ||
3507 | s2 = execute_move(s, move); | ||
3508 | text = game_text_format(s2); | ||
3509 | sfree(move); | ||
3510 | fputs(text, stdout); | ||
3511 | sfree(text); | ||
3512 | free_game(s2); | ||
3513 | if (retd > 1) | ||
3514 | printf("Could not deduce a unique solution\n"); | ||
3515 | } | ||
3516 | solver_free_scratch(sc); | ||
3517 | free_game(s); | ||
3518 | free_params(p); | ||
3519 | |||
3520 | return 0; | ||
3521 | } | ||
3522 | |||
3523 | #endif | ||
3524 | |||
1773 | /* vim: set shiftwidth=4 :set textwidth=80: */ | 3525 | /* vim: set shiftwidth=4 :set textwidth=80: */ |
1774 | 3526 | ||