diff options
Diffstat (limited to 'apps/plugins/puzzles/src/tents.c')
-rw-r--r-- | apps/plugins/puzzles/src/tents.c | 2740 |
1 files changed, 2740 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/tents.c b/apps/plugins/puzzles/src/tents.c new file mode 100644 index 0000000000..4ffeb7be64 --- /dev/null +++ b/apps/plugins/puzzles/src/tents.c | |||
@@ -0,0 +1,2740 @@ | |||
1 | /* | ||
2 | * tents.c: Puzzle involving placing tents next to trees subject to | ||
3 | * some confusing conditions. | ||
4 | * | ||
5 | * TODO: | ||
6 | * | ||
7 | * - it might be nice to make setter-provided tent/nontent clues | ||
8 | * inviolable? | ||
9 | * * on the other hand, this would introduce considerable extra | ||
10 | * complexity and size into the game state; also inviolable | ||
11 | * clues would have to be marked as such somehow, in an | ||
12 | * intrusive and annoying manner. Since they're never | ||
13 | * generated by _my_ generator, I'm currently more inclined | ||
14 | * not to bother. | ||
15 | * | ||
16 | * - more difficult levels at the top end? | ||
17 | * * for example, sometimes we can deduce that two BLANKs in | ||
18 | * the same row are each adjacent to the same unattached tree | ||
19 | * and to nothing else, implying that they can't both be | ||
20 | * tents; this enables us to rule out some extra combinations | ||
21 | * in the row-based deduction loop, and hence deduce more | ||
22 | * from the number in that row than we could otherwise do. | ||
23 | * * that by itself doesn't seem worth implementing a new | ||
24 | * difficulty level for, but if I can find a few more things | ||
25 | * like that then it might become worthwhile. | ||
26 | * * I wonder if there's a sensible heuristic for where to | ||
27 | * guess which would make a recursive solver viable? | ||
28 | */ | ||
29 | |||
30 | #include <stdio.h> | ||
31 | #include <stdlib.h> | ||
32 | #include <string.h> | ||
33 | #include <assert.h> | ||
34 | #include <ctype.h> | ||
35 | #include <math.h> | ||
36 | |||
37 | #include "puzzles.h" | ||
38 | #include "maxflow.h" | ||
39 | |||
40 | /* | ||
41 | * Design discussion | ||
42 | * ----------------- | ||
43 | * | ||
44 | * The rules of this puzzle as available on the WWW are poorly | ||
45 | * specified. The bits about tents having to be orthogonally | ||
46 | * adjacent to trees, tents not being even diagonally adjacent to | ||
47 | * one another, and the number of tents in each row and column | ||
48 | * being given are simple enough; the difficult bit is the | ||
49 | * tent-to-tree matching. | ||
50 | * | ||
51 | * Some sources use simplistic wordings such as `each tree is | ||
52 | * exactly connected to only one tent', which is extremely unclear: | ||
53 | * it's easy to read erroneously as `each tree is _orthogonally | ||
54 | * adjacent_ to exactly one tent', which is definitely incorrect. | ||
55 | * Even the most coherent sources I've found don't do a much better | ||
56 | * job of stating the rule. | ||
57 | * | ||
58 | * A more precise statement of the rule is that it must be possible | ||
59 | * to find a bijection f between tents and trees such that each | ||
60 | * tree T is orthogonally adjacent to the tent f(T), but that a | ||
61 | * tent is permitted to be adjacent to other trees in addition to | ||
62 | * its own. This slightly non-obvious criterion is what gives this | ||
63 | * puzzle most of its subtlety. | ||
64 | * | ||
65 | * However, there's a particularly subtle ambiguity left over. Is | ||
66 | * the bijection between tents and trees required to be _unique_? | ||
67 | * In other words, is that bijection conceptually something the | ||
68 | * player should be able to exhibit as part of the solution (even | ||
69 | * if they aren't actually required to do so)? Or is it sufficient | ||
70 | * to have a unique _placement_ of the tents which gives rise to at | ||
71 | * least one suitable bijection? | ||
72 | * | ||
73 | * The puzzle shown to the right of this .T. 2 *T* 2 | ||
74 | * paragraph illustrates the problem. There T.T 0 -> T-T 0 | ||
75 | * are two distinct bijections available. .T. 2 *T* 2 | ||
76 | * The answer to the above question will | ||
77 | * determine whether it's a valid puzzle. 202 202 | ||
78 | * | ||
79 | * This is an important question, because it affects both the | ||
80 | * player and the generator. Eventually I found all the instances | ||
81 | * of this puzzle I could Google up, solved them all by hand, and | ||
82 | * verified that in all cases the tree/tent matching was uniquely | ||
83 | * determined given the tree and tent positions. Therefore, the | ||
84 | * puzzle as implemented in this source file takes the following | ||
85 | * policy: | ||
86 | * | ||
87 | * - When checking a user-supplied solution for correctness, only | ||
88 | * verify that there exists _at least_ one matching. | ||
89 | * - When generating a puzzle, enforce that there must be | ||
90 | * _exactly_ one. | ||
91 | * | ||
92 | * Algorithmic implications | ||
93 | * ------------------------ | ||
94 | * | ||
95 | * Another way of phrasing the tree/tent matching criterion is to | ||
96 | * say that the bipartite adjacency graph between trees and tents | ||
97 | * has a perfect matching. That is, if you construct a graph which | ||
98 | * has a vertex per tree and a vertex per tent, and an edge between | ||
99 | * any tree and tent which are orthogonally adjacent, it is | ||
100 | * possible to find a set of N edges of that graph (where N is the | ||
101 | * number of trees and also the number of tents) which between them | ||
102 | * connect every tree to every tent. | ||
103 | * | ||
104 | * The most efficient known algorithms for finding such a matching | ||
105 | * given a graph, as far as I'm aware, are the Munkres assignment | ||
106 | * algorithm (also known as the Hungarian algorithm) and the | ||
107 | * Ford-Fulkerson algorithm (for finding optimal flows in | ||
108 | * networks). Each of these takes O(N^3) running time; so we're | ||
109 | * talking O(N^3) time to verify any candidate solution to this | ||
110 | * puzzle. That's just about OK if you're doing it once per mouse | ||
111 | * click (and in fact not even that, since the sensible thing to do | ||
112 | * is check all the _other_ puzzle criteria and only wade into this | ||
113 | * quagmire if none are violated); but if the solver had to keep | ||
114 | * doing N^3 work internally, then it would probably end up with | ||
115 | * more like N^5 or N^6 running time, and grid generation would | ||
116 | * become very clunky. | ||
117 | * | ||
118 | * Fortunately, I've been able to prove a very useful property of | ||
119 | * _unique_ perfect matchings, by adapting the proof of Hall's | ||
120 | * Marriage Theorem. For those unaware of Hall's Theorem, I'll | ||
121 | * recap it and its proof: it states that a bipartite graph | ||
122 | * contains a perfect matching iff every set of vertices on the | ||
123 | * left side of the graph have a neighbourhood _at least_ as big on | ||
124 | * the right. | ||
125 | * | ||
126 | * This condition is obviously satisfied if a perfect matching does | ||
127 | * exist; each left-side node has a distinct right-side node which | ||
128 | * is the one assigned to it by the matching, and thus any set of n | ||
129 | * left vertices must have a combined neighbourhood containing at | ||
130 | * least the n corresponding right vertices, and possibly others | ||
131 | * too. Alternatively, imagine if you had (say) three left-side | ||
132 | * nodes all of which were connected to only two right-side nodes | ||
133 | * between them: any perfect matching would have to assign one of | ||
134 | * those two right nodes to each of the three left nodes, and still | ||
135 | * give the three left nodes a different right node each. This is | ||
136 | * of course impossible. | ||
137 | * | ||
138 | * To prove the converse (that if every subset of left vertices | ||
139 | * satisfies the Hall condition then a perfect matching exists), | ||
140 | * consider trying to find a proper subset of the left vertices | ||
141 | * which _exactly_ satisfies the Hall condition: that is, its right | ||
142 | * neighbourhood is precisely the same size as it. If we can find | ||
143 | * such a subset, then we can split the bipartite graph into two | ||
144 | * smaller ones: one consisting of the left subset and its right | ||
145 | * neighbourhood, the other consisting of everything else. Edges | ||
146 | * from the left side of the former graph to the right side of the | ||
147 | * latter do not exist, by construction; edges from the right side | ||
148 | * of the former to the left of the latter cannot be part of any | ||
149 | * perfect matching because otherwise the left subset would not be | ||
150 | * left with enough distinct right vertices to connect to (this is | ||
151 | * exactly the same deduction used in Solo's set analysis). You can | ||
152 | * then prove (left as an exercise) that both these smaller graphs | ||
153 | * still satisfy the Hall condition, and therefore the proof will | ||
154 | * follow by induction. | ||
155 | * | ||
156 | * There's one other possibility, which is the case where _no_ | ||
157 | * proper subset of the left vertices has a right neighbourhood of | ||
158 | * exactly the same size. That is, every left subset has a strictly | ||
159 | * _larger_ right neighbourhood. In this situation, we can simply | ||
160 | * remove an _arbitrary_ edge from the graph. This cannot reduce | ||
161 | * the size of any left subset's right neighbourhood by more than | ||
162 | * one, so if all neighbourhoods were strictly bigger than they | ||
163 | * needed to be initially, they must now still be _at least as big_ | ||
164 | * as they need to be. So we can keep throwing out arbitrary edges | ||
165 | * until we find a set which exactly satisfies the Hall condition, | ||
166 | * and then proceed as above. [] | ||
167 | * | ||
168 | * That's Hall's theorem. I now build on this by examining the | ||
169 | * circumstances in which a bipartite graph can have a _unique_ | ||
170 | * perfect matching. It is clear that in the second case, where no | ||
171 | * left subset exactly satisfies the Hall condition and so we can | ||
172 | * remove an arbitrary edge, there cannot be a unique perfect | ||
173 | * matching: given one perfect matching, we choose our arbitrary | ||
174 | * removed edge to be one of those contained in it, and then we can | ||
175 | * still find a perfect matching in the remaining graph, which will | ||
176 | * be a distinct perfect matching in the original. | ||
177 | * | ||
178 | * So it is a necessary condition for a unique perfect matching | ||
179 | * that there must be at least one proper left subset which | ||
180 | * _exactly_ satisfies the Hall condition. But now consider the | ||
181 | * smaller graph constructed by taking that left subset and its | ||
182 | * neighbourhood: if the graph as a whole had a unique perfect | ||
183 | * matching, then so must this smaller one, which means we can find | ||
184 | * a proper left subset _again_, and so on. Repeating this process | ||
185 | * must eventually reduce us to a graph with only one left-side | ||
186 | * vertex (so there are no proper subsets at all); this vertex must | ||
187 | * be connected to only one right-side vertex, and hence must be so | ||
188 | * in the original graph as well (by construction). So we can | ||
189 | * discard this vertex pair from the graph, and any other edges | ||
190 | * that involved it (which will by construction be from other left | ||
191 | * vertices only), and the resulting smaller graph still has a | ||
192 | * unique perfect matching which means we can do the same thing | ||
193 | * again. | ||
194 | * | ||
195 | * In other words, given any bipartite graph with a unique perfect | ||
196 | * matching, we can find that matching by the following extremely | ||
197 | * simple algorithm: | ||
198 | * | ||
199 | * - Find a left-side vertex which is only connected to one | ||
200 | * right-side vertex. | ||
201 | * - Assign those vertices to one another, and therefore discard | ||
202 | * any other edges connecting to that right vertex. | ||
203 | * - Repeat until all vertices have been matched. | ||
204 | * | ||
205 | * This algorithm can be run in O(V+E) time (where V is the number | ||
206 | * of vertices and E is the number of edges in the graph), and the | ||
207 | * only way it can fail is if there is not a unique perfect | ||
208 | * matching (either because there is no matching at all, or because | ||
209 | * it isn't unique; but it can't distinguish those cases). | ||
210 | * | ||
211 | * Thus, the internal solver in this source file can be confident | ||
212 | * that if the tree/tent matching is uniquely determined by the | ||
213 | * tree and tent positions, it can find it using only this kind of | ||
214 | * obvious and simple operation: assign a tree to a tent if it | ||
215 | * cannot possibly belong to any other tent, and vice versa. If the | ||
216 | * solver were _only_ trying to determine the matching, even that | ||
217 | * `vice versa' wouldn't be required; but it can come in handy when | ||
218 | * not all the tents have been placed yet. I can therefore be | ||
219 | * reasonably confident that as long as my solver doesn't need to | ||
220 | * cope with grids that have a non-unique matching, it will also | ||
221 | * not need to do anything complicated like set analysis between | ||
222 | * trees and tents. | ||
223 | */ | ||
224 | |||
225 | /* | ||
226 | * In standalone solver mode, `verbose' is a variable which can be | ||
227 | * set by command-line option; in debugging mode it's simply always | ||
228 | * true. | ||
229 | */ | ||
230 | #if defined STANDALONE_SOLVER | ||
231 | #define SOLVER_DIAGNOSTICS | ||
232 | int verbose = FALSE; | ||
233 | #elif defined SOLVER_DIAGNOSTICS | ||
234 | #define verbose TRUE | ||
235 | #endif | ||
236 | |||
237 | /* | ||
238 | * Difficulty levels. I do some macro ickery here to ensure that my | ||
239 | * enum and the various forms of my name list always match up. | ||
240 | */ | ||
241 | #define DIFFLIST(A) \ | ||
242 | A(EASY,Easy,e) \ | ||
243 | A(TRICKY,Tricky,t) | ||
244 | #define ENUM(upper,title,lower) DIFF_ ## upper, | ||
245 | #define TITLE(upper,title,lower) #title, | ||
246 | #define ENCODE(upper,title,lower) #lower | ||
247 | #define CONFIG(upper,title,lower) ":" #title | ||
248 | enum { DIFFLIST(ENUM) DIFFCOUNT }; | ||
249 | static char const *const tents_diffnames[] = { DIFFLIST(TITLE) }; | ||
250 | static char const tents_diffchars[] = DIFFLIST(ENCODE); | ||
251 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
252 | |||
253 | enum { | ||
254 | COL_BACKGROUND, | ||
255 | COL_GRID, | ||
256 | COL_GRASS, | ||
257 | COL_TREETRUNK, | ||
258 | COL_TREELEAF, | ||
259 | COL_TENT, | ||
260 | COL_ERROR, | ||
261 | COL_ERRTEXT, | ||
262 | COL_ERRTRUNK, | ||
263 | NCOLOURS | ||
264 | }; | ||
265 | |||
266 | enum { BLANK, TREE, TENT, NONTENT, MAGIC }; | ||
267 | |||
268 | struct game_params { | ||
269 | int w, h; | ||
270 | int diff; | ||
271 | }; | ||
272 | |||
273 | struct numbers { | ||
274 | int refcount; | ||
275 | int *numbers; | ||
276 | }; | ||
277 | |||
278 | struct game_state { | ||
279 | game_params p; | ||
280 | char *grid; | ||
281 | struct numbers *numbers; | ||
282 | int completed, used_solve; | ||
283 | }; | ||
284 | |||
285 | static game_params *default_params(void) | ||
286 | { | ||
287 | game_params *ret = snew(game_params); | ||
288 | |||
289 | ret->w = ret->h = 8; | ||
290 | ret->diff = DIFF_EASY; | ||
291 | |||
292 | return ret; | ||
293 | } | ||
294 | |||
295 | static const struct game_params tents_presets[] = { | ||
296 | {8, 8, DIFF_EASY}, | ||
297 | {8, 8, DIFF_TRICKY}, | ||
298 | {10, 10, DIFF_EASY}, | ||
299 | {10, 10, DIFF_TRICKY}, | ||
300 | {15, 15, DIFF_EASY}, | ||
301 | {15, 15, DIFF_TRICKY}, | ||
302 | }; | ||
303 | |||
304 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
305 | { | ||
306 | game_params *ret; | ||
307 | char str[80]; | ||
308 | |||
309 | if (i < 0 || i >= lenof(tents_presets)) | ||
310 | return FALSE; | ||
311 | |||
312 | ret = snew(game_params); | ||
313 | *ret = tents_presets[i]; | ||
314 | |||
315 | sprintf(str, "%dx%d %s", ret->w, ret->h, tents_diffnames[ret->diff]); | ||
316 | |||
317 | *name = dupstr(str); | ||
318 | *params = ret; | ||
319 | return TRUE; | ||
320 | } | ||
321 | |||
322 | static void free_params(game_params *params) | ||
323 | { | ||
324 | sfree(params); | ||
325 | } | ||
326 | |||
327 | static game_params *dup_params(const game_params *params) | ||
328 | { | ||
329 | game_params *ret = snew(game_params); | ||
330 | *ret = *params; /* structure copy */ | ||
331 | return ret; | ||
332 | } | ||
333 | |||
334 | static void decode_params(game_params *params, char const *string) | ||
335 | { | ||
336 | params->w = params->h = atoi(string); | ||
337 | while (*string && isdigit((unsigned char)*string)) string++; | ||
338 | if (*string == 'x') { | ||
339 | string++; | ||
340 | params->h = atoi(string); | ||
341 | while (*string && isdigit((unsigned char)*string)) string++; | ||
342 | } | ||
343 | if (*string == 'd') { | ||
344 | int i; | ||
345 | string++; | ||
346 | for (i = 0; i < DIFFCOUNT; i++) | ||
347 | if (*string == tents_diffchars[i]) | ||
348 | params->diff = i; | ||
349 | if (*string) string++; | ||
350 | } | ||
351 | } | ||
352 | |||
353 | static char *encode_params(const game_params *params, int full) | ||
354 | { | ||
355 | char buf[120]; | ||
356 | |||
357 | sprintf(buf, "%dx%d", params->w, params->h); | ||
358 | if (full) | ||
359 | sprintf(buf + strlen(buf), "d%c", | ||
360 | tents_diffchars[params->diff]); | ||
361 | return dupstr(buf); | ||
362 | } | ||
363 | |||
364 | static config_item *game_configure(const game_params *params) | ||
365 | { | ||
366 | config_item *ret; | ||
367 | char buf[80]; | ||
368 | |||
369 | ret = snewn(4, config_item); | ||
370 | |||
371 | ret[0].name = "Width"; | ||
372 | ret[0].type = C_STRING; | ||
373 | sprintf(buf, "%d", params->w); | ||
374 | ret[0].sval = dupstr(buf); | ||
375 | ret[0].ival = 0; | ||
376 | |||
377 | ret[1].name = "Height"; | ||
378 | ret[1].type = C_STRING; | ||
379 | sprintf(buf, "%d", params->h); | ||
380 | ret[1].sval = dupstr(buf); | ||
381 | ret[1].ival = 0; | ||
382 | |||
383 | ret[2].name = "Difficulty"; | ||
384 | ret[2].type = C_CHOICES; | ||
385 | ret[2].sval = DIFFCONFIG; | ||
386 | ret[2].ival = params->diff; | ||
387 | |||
388 | ret[3].name = NULL; | ||
389 | ret[3].type = C_END; | ||
390 | ret[3].sval = NULL; | ||
391 | ret[3].ival = 0; | ||
392 | |||
393 | return ret; | ||
394 | } | ||
395 | |||
396 | static game_params *custom_params(const config_item *cfg) | ||
397 | { | ||
398 | game_params *ret = snew(game_params); | ||
399 | |||
400 | ret->w = atoi(cfg[0].sval); | ||
401 | ret->h = atoi(cfg[1].sval); | ||
402 | ret->diff = cfg[2].ival; | ||
403 | |||
404 | return ret; | ||
405 | } | ||
406 | |||
407 | static char *validate_params(const game_params *params, int full) | ||
408 | { | ||
409 | /* | ||
410 | * Generating anything under 4x4 runs into trouble of one kind | ||
411 | * or another. | ||
412 | */ | ||
413 | if (params->w < 4 || params->h < 4) | ||
414 | return "Width and height must both be at least four"; | ||
415 | return NULL; | ||
416 | } | ||
417 | |||
418 | /* | ||
419 | * Scratch space for solver. | ||
420 | */ | ||
421 | enum { N, U, L, R, D, MAXDIR }; /* link directions */ | ||
422 | #define dx(d) ( ((d)==R) - ((d)==L) ) | ||
423 | #define dy(d) ( ((d)==D) - ((d)==U) ) | ||
424 | #define F(d) ( U + D - (d) ) | ||
425 | struct solver_scratch { | ||
426 | char *links; /* mapping between trees and tents */ | ||
427 | int *locs; | ||
428 | char *place, *mrows, *trows; | ||
429 | }; | ||
430 | |||
431 | static struct solver_scratch *new_scratch(int w, int h) | ||
432 | { | ||
433 | struct solver_scratch *ret = snew(struct solver_scratch); | ||
434 | |||
435 | ret->links = snewn(w*h, char); | ||
436 | ret->locs = snewn(max(w, h), int); | ||
437 | ret->place = snewn(max(w, h), char); | ||
438 | ret->mrows = snewn(3 * max(w, h), char); | ||
439 | ret->trows = snewn(3 * max(w, h), char); | ||
440 | |||
441 | return ret; | ||
442 | } | ||
443 | |||
444 | static void free_scratch(struct solver_scratch *sc) | ||
445 | { | ||
446 | sfree(sc->trows); | ||
447 | sfree(sc->mrows); | ||
448 | sfree(sc->place); | ||
449 | sfree(sc->locs); | ||
450 | sfree(sc->links); | ||
451 | sfree(sc); | ||
452 | } | ||
453 | |||
454 | /* | ||
455 | * Solver. Returns 0 for impossibility, 1 for success, 2 for | ||
456 | * ambiguity or failure to converge. | ||
457 | */ | ||
458 | static int tents_solve(int w, int h, const char *grid, int *numbers, | ||
459 | char *soln, struct solver_scratch *sc, int diff) | ||
460 | { | ||
461 | int x, y, d, i, j; | ||
462 | char *mrow, *trow, *trow1, *trow2; | ||
463 | |||
464 | /* | ||
465 | * Set up solver data. | ||
466 | */ | ||
467 | memset(sc->links, N, w*h); | ||
468 | |||
469 | /* | ||
470 | * Set up solution array. | ||
471 | */ | ||
472 | memcpy(soln, grid, w*h); | ||
473 | |||
474 | /* | ||
475 | * Main solver loop. | ||
476 | */ | ||
477 | while (1) { | ||
478 | int done_something = FALSE; | ||
479 | |||
480 | /* | ||
481 | * Any tent which has only one unattached tree adjacent to | ||
482 | * it can be tied to that tree. | ||
483 | */ | ||
484 | for (y = 0; y < h; y++) | ||
485 | for (x = 0; x < w; x++) | ||
486 | if (soln[y*w+x] == TENT && !sc->links[y*w+x]) { | ||
487 | int linkd = 0; | ||
488 | |||
489 | for (d = 1; d < MAXDIR; d++) { | ||
490 | int x2 = x + dx(d), y2 = y + dy(d); | ||
491 | if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && | ||
492 | soln[y2*w+x2] == TREE && | ||
493 | !sc->links[y2*w+x2]) { | ||
494 | if (linkd) | ||
495 | break; /* found more than one */ | ||
496 | else | ||
497 | linkd = d; | ||
498 | } | ||
499 | } | ||
500 | |||
501 | if (d == MAXDIR && linkd == 0) { | ||
502 | #ifdef SOLVER_DIAGNOSTICS | ||
503 | if (verbose) | ||
504 | printf("tent at %d,%d cannot link to anything\n", | ||
505 | x, y); | ||
506 | #endif | ||
507 | return 0; /* no solution exists */ | ||
508 | } else if (d == MAXDIR) { | ||
509 | int x2 = x + dx(linkd), y2 = y + dy(linkd); | ||
510 | |||
511 | #ifdef SOLVER_DIAGNOSTICS | ||
512 | if (verbose) | ||
513 | printf("tent at %d,%d can only link to tree at" | ||
514 | " %d,%d\n", x, y, x2, y2); | ||
515 | #endif | ||
516 | |||
517 | sc->links[y*w+x] = linkd; | ||
518 | sc->links[y2*w+x2] = F(linkd); | ||
519 | done_something = TRUE; | ||
520 | } | ||
521 | } | ||
522 | |||
523 | if (done_something) | ||
524 | continue; | ||
525 | if (diff < 0) | ||
526 | break; /* don't do anything else! */ | ||
527 | |||
528 | /* | ||
529 | * Mark a blank square as NONTENT if it is not orthogonally | ||
530 | * adjacent to any unmatched tree. | ||
531 | */ | ||
532 | for (y = 0; y < h; y++) | ||
533 | for (x = 0; x < w; x++) | ||
534 | if (soln[y*w+x] == BLANK) { | ||
535 | int can_be_tent = FALSE; | ||
536 | |||
537 | for (d = 1; d < MAXDIR; d++) { | ||
538 | int x2 = x + dx(d), y2 = y + dy(d); | ||
539 | if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && | ||
540 | soln[y2*w+x2] == TREE && | ||
541 | !sc->links[y2*w+x2]) | ||
542 | can_be_tent = TRUE; | ||
543 | } | ||
544 | |||
545 | if (!can_be_tent) { | ||
546 | #ifdef SOLVER_DIAGNOSTICS | ||
547 | if (verbose) | ||
548 | printf("%d,%d cannot be a tent (no adjacent" | ||
549 | " unmatched tree)\n", x, y); | ||
550 | #endif | ||
551 | soln[y*w+x] = NONTENT; | ||
552 | done_something = TRUE; | ||
553 | } | ||
554 | } | ||
555 | |||
556 | if (done_something) | ||
557 | continue; | ||
558 | |||
559 | /* | ||
560 | * Mark a blank square as NONTENT if it is (perhaps | ||
561 | * diagonally) adjacent to any other tent. | ||
562 | */ | ||
563 | for (y = 0; y < h; y++) | ||
564 | for (x = 0; x < w; x++) | ||
565 | if (soln[y*w+x] == BLANK) { | ||
566 | int dx, dy, imposs = FALSE; | ||
567 | |||
568 | for (dy = -1; dy <= +1; dy++) | ||
569 | for (dx = -1; dx <= +1; dx++) | ||
570 | if (dy || dx) { | ||
571 | int x2 = x + dx, y2 = y + dy; | ||
572 | if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && | ||
573 | soln[y2*w+x2] == TENT) | ||
574 | imposs = TRUE; | ||
575 | } | ||
576 | |||
577 | if (imposs) { | ||
578 | #ifdef SOLVER_DIAGNOSTICS | ||
579 | if (verbose) | ||
580 | printf("%d,%d cannot be a tent (adjacent tent)\n", | ||
581 | x, y); | ||
582 | #endif | ||
583 | soln[y*w+x] = NONTENT; | ||
584 | done_something = TRUE; | ||
585 | } | ||
586 | } | ||
587 | |||
588 | if (done_something) | ||
589 | continue; | ||
590 | |||
591 | /* | ||
592 | * Any tree which has exactly one {unattached tent, BLANK} | ||
593 | * adjacent to it must have its tent in that square. | ||
594 | */ | ||
595 | for (y = 0; y < h; y++) | ||
596 | for (x = 0; x < w; x++) | ||
597 | if (soln[y*w+x] == TREE && !sc->links[y*w+x]) { | ||
598 | int linkd = 0, linkd2 = 0, nd = 0; | ||
599 | |||
600 | for (d = 1; d < MAXDIR; d++) { | ||
601 | int x2 = x + dx(d), y2 = y + dy(d); | ||
602 | if (!(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h)) | ||
603 | continue; | ||
604 | if (soln[y2*w+x2] == BLANK || | ||
605 | (soln[y2*w+x2] == TENT && !sc->links[y2*w+x2])) { | ||
606 | if (linkd) | ||
607 | linkd2 = d; | ||
608 | else | ||
609 | linkd = d; | ||
610 | nd++; | ||
611 | } | ||
612 | } | ||
613 | |||
614 | if (nd == 0) { | ||
615 | #ifdef SOLVER_DIAGNOSTICS | ||
616 | if (verbose) | ||
617 | printf("tree at %d,%d cannot link to anything\n", | ||
618 | x, y); | ||
619 | #endif | ||
620 | return 0; /* no solution exists */ | ||
621 | } else if (nd == 1) { | ||
622 | int x2 = x + dx(linkd), y2 = y + dy(linkd); | ||
623 | |||
624 | #ifdef SOLVER_DIAGNOSTICS | ||
625 | if (verbose) | ||
626 | printf("tree at %d,%d can only link to tent at" | ||
627 | " %d,%d\n", x, y, x2, y2); | ||
628 | #endif | ||
629 | soln[y2*w+x2] = TENT; | ||
630 | sc->links[y*w+x] = linkd; | ||
631 | sc->links[y2*w+x2] = F(linkd); | ||
632 | done_something = TRUE; | ||
633 | } else if (nd == 2 && (!dx(linkd) != !dx(linkd2)) && | ||
634 | diff >= DIFF_TRICKY) { | ||
635 | /* | ||
636 | * If there are two possible places where | ||
637 | * this tree's tent can go, and they are | ||
638 | * diagonally separated rather than being | ||
639 | * on opposite sides of the tree, then the | ||
640 | * square (other than the tree square) | ||
641 | * which is adjacent to both of them must | ||
642 | * be a non-tent. | ||
643 | */ | ||
644 | int x2 = x + dx(linkd) + dx(linkd2); | ||
645 | int y2 = y + dy(linkd) + dy(linkd2); | ||
646 | assert(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h); | ||
647 | if (soln[y2*w+x2] == BLANK) { | ||
648 | #ifdef SOLVER_DIAGNOSTICS | ||
649 | if (verbose) | ||
650 | printf("possible tent locations for tree at" | ||
651 | " %d,%d rule out tent at %d,%d\n", | ||
652 | x, y, x2, y2); | ||
653 | #endif | ||
654 | soln[y2*w+x2] = NONTENT; | ||
655 | done_something = TRUE; | ||
656 | } | ||
657 | } | ||
658 | } | ||
659 | |||
660 | if (done_something) | ||
661 | continue; | ||
662 | |||
663 | /* | ||
664 | * If localised deductions about the trees and tents | ||
665 | * themselves haven't helped us, it's time to resort to the | ||
666 | * numbers round the grid edge. For each row and column, we | ||
667 | * go through all possible combinations of locations for | ||
668 | * the unplaced tents, rule out any which have adjacent | ||
669 | * tents, and spot any square which is given the same state | ||
670 | * by all remaining combinations. | ||
671 | */ | ||
672 | for (i = 0; i < w+h; i++) { | ||
673 | int start, step, len, start1, start2, n, k; | ||
674 | |||
675 | if (i < w) { | ||
676 | /* | ||
677 | * This is the number for a column. | ||
678 | */ | ||
679 | start = i; | ||
680 | step = w; | ||
681 | len = h; | ||
682 | if (i > 0) | ||
683 | start1 = start - 1; | ||
684 | else | ||
685 | start1 = -1; | ||
686 | if (i+1 < w) | ||
687 | start2 = start + 1; | ||
688 | else | ||
689 | start2 = -1; | ||
690 | } else { | ||
691 | /* | ||
692 | * This is the number for a row. | ||
693 | */ | ||
694 | start = (i-w)*w; | ||
695 | step = 1; | ||
696 | len = w; | ||
697 | if (i > w) | ||
698 | start1 = start - w; | ||
699 | else | ||
700 | start1 = -1; | ||
701 | if (i+1 < w+h) | ||
702 | start2 = start + w; | ||
703 | else | ||
704 | start2 = -1; | ||
705 | } | ||
706 | |||
707 | if (diff < DIFF_TRICKY) { | ||
708 | /* | ||
709 | * In Easy mode, we don't look at the effect of one | ||
710 | * row on the next (i.e. ruling out a square if all | ||
711 | * possibilities for an adjacent row place a tent | ||
712 | * next to it). | ||
713 | */ | ||
714 | start1 = start2 = -1; | ||
715 | } | ||
716 | |||
717 | k = numbers[i]; | ||
718 | |||
719 | /* | ||
720 | * Count and store the locations of the free squares, | ||
721 | * and also count the number of tents already placed. | ||
722 | */ | ||
723 | n = 0; | ||
724 | for (j = 0; j < len; j++) { | ||
725 | if (soln[start+j*step] == TENT) | ||
726 | k--; /* one fewer tent to place */ | ||
727 | else if (soln[start+j*step] == BLANK) | ||
728 | sc->locs[n++] = j; | ||
729 | } | ||
730 | |||
731 | if (n == 0) | ||
732 | continue; /* nothing left to do here */ | ||
733 | |||
734 | /* | ||
735 | * Now we know we're placing k tents in n squares. Set | ||
736 | * up the first possibility. | ||
737 | */ | ||
738 | for (j = 0; j < n; j++) | ||
739 | sc->place[j] = (j < k ? TENT : NONTENT); | ||
740 | |||
741 | /* | ||
742 | * We're aiming to find squares in this row which are | ||
743 | * invariant over all valid possibilities. Thus, we | ||
744 | * maintain the current state of that invariance. We | ||
745 | * start everything off at MAGIC to indicate that it | ||
746 | * hasn't been set up yet. | ||
747 | */ | ||
748 | mrow = sc->mrows; | ||
749 | trow = sc->trows; | ||
750 | trow1 = sc->trows + len; | ||
751 | trow2 = sc->trows + 2*len; | ||
752 | memset(mrow, MAGIC, 3*len); | ||
753 | |||
754 | /* | ||
755 | * And iterate over all possibilities. | ||
756 | */ | ||
757 | while (1) { | ||
758 | int p, valid; | ||
759 | |||
760 | /* | ||
761 | * See if this possibility is valid. The only way | ||
762 | * it can fail to be valid is if it contains two | ||
763 | * adjacent tents. (Other forms of invalidity, such | ||
764 | * as containing a tent adjacent to one already | ||
765 | * placed, will have been dealt with already by | ||
766 | * other parts of the solver.) | ||
767 | */ | ||
768 | valid = TRUE; | ||
769 | for (j = 0; j+1 < n; j++) | ||
770 | if (sc->place[j] == TENT && | ||
771 | sc->place[j+1] == TENT && | ||
772 | sc->locs[j+1] == sc->locs[j]+1) { | ||
773 | valid = FALSE; | ||
774 | break; | ||
775 | } | ||
776 | |||
777 | if (valid) { | ||
778 | /* | ||
779 | * Merge this valid combination into mrow. | ||
780 | */ | ||
781 | memset(trow, MAGIC, len); | ||
782 | memset(trow+len, BLANK, 2*len); | ||
783 | for (j = 0; j < n; j++) { | ||
784 | trow[sc->locs[j]] = sc->place[j]; | ||
785 | if (sc->place[j] == TENT) { | ||
786 | int jj; | ||
787 | for (jj = sc->locs[j]-1; jj <= sc->locs[j]+1; jj++) | ||
788 | if (jj >= 0 && jj < len) | ||
789 | trow1[jj] = trow2[jj] = NONTENT; | ||
790 | } | ||
791 | } | ||
792 | |||
793 | for (j = 0; j < 3*len; j++) { | ||
794 | if (trow[j] == MAGIC) | ||
795 | continue; | ||
796 | if (mrow[j] == MAGIC || mrow[j] == trow[j]) { | ||
797 | /* | ||
798 | * Either this is the first valid | ||
799 | * placement we've found at all, or | ||
800 | * this square's contents are | ||
801 | * consistent with every previous valid | ||
802 | * combination. | ||
803 | */ | ||
804 | mrow[j] = trow[j]; | ||
805 | } else { | ||
806 | /* | ||
807 | * This square's contents fail to match | ||
808 | * what they were in a different | ||
809 | * combination, so we cannot deduce | ||
810 | * anything about this square. | ||
811 | */ | ||
812 | mrow[j] = BLANK; | ||
813 | } | ||
814 | } | ||
815 | } | ||
816 | |||
817 | /* | ||
818 | * Find the next combination of k choices from n. | ||
819 | * We do this by finding the rightmost tent which | ||
820 | * can be moved one place right, doing so, and | ||
821 | * shunting all tents to the right of that as far | ||
822 | * left as they can go. | ||
823 | */ | ||
824 | p = 0; | ||
825 | for (j = n-1; j > 0; j--) { | ||
826 | if (sc->place[j] == TENT) | ||
827 | p++; | ||
828 | if (sc->place[j] == NONTENT && sc->place[j-1] == TENT) { | ||
829 | sc->place[j-1] = NONTENT; | ||
830 | sc->place[j] = TENT; | ||
831 | while (p--) | ||
832 | sc->place[++j] = TENT; | ||
833 | while (++j < n) | ||
834 | sc->place[j] = NONTENT; | ||
835 | break; | ||
836 | } | ||
837 | } | ||
838 | if (j <= 0) | ||
839 | break; /* we've finished */ | ||
840 | } | ||
841 | |||
842 | /* | ||
843 | * It's just possible that _no_ placement was valid, in | ||
844 | * which case we have an internally inconsistent | ||
845 | * puzzle. | ||
846 | */ | ||
847 | if (mrow[sc->locs[0]] == MAGIC) | ||
848 | return 0; /* inconsistent */ | ||
849 | |||
850 | /* | ||
851 | * Now go through mrow and see if there's anything | ||
852 | * we've deduced which wasn't already mentioned in soln. | ||
853 | */ | ||
854 | for (j = 0; j < len; j++) { | ||
855 | int whichrow; | ||
856 | |||
857 | for (whichrow = 0; whichrow < 3; whichrow++) { | ||
858 | char *mthis = mrow + whichrow * len; | ||
859 | int tstart = (whichrow == 0 ? start : | ||
860 | whichrow == 1 ? start1 : start2); | ||
861 | if (tstart >= 0 && | ||
862 | mthis[j] != MAGIC && mthis[j] != BLANK && | ||
863 | soln[tstart+j*step] == BLANK) { | ||
864 | int pos = tstart+j*step; | ||
865 | |||
866 | #ifdef SOLVER_DIAGNOSTICS | ||
867 | if (verbose) | ||
868 | printf("%s %d forces %s at %d,%d\n", | ||
869 | step==1 ? "row" : "column", | ||
870 | step==1 ? start/w : start, | ||
871 | mthis[j] == TENT ? "tent" : "non-tent", | ||
872 | pos % w, pos / w); | ||
873 | #endif | ||
874 | soln[pos] = mthis[j]; | ||
875 | done_something = TRUE; | ||
876 | } | ||
877 | } | ||
878 | } | ||
879 | } | ||
880 | |||
881 | if (done_something) | ||
882 | continue; | ||
883 | |||
884 | if (!done_something) | ||
885 | break; | ||
886 | } | ||
887 | |||
888 | /* | ||
889 | * The solver has nothing further it can do. Return 1 if both | ||
890 | * soln and sc->links are completely filled in, or 2 otherwise. | ||
891 | */ | ||
892 | for (y = 0; y < h; y++) | ||
893 | for (x = 0; x < w; x++) { | ||
894 | if (soln[y*w+x] == BLANK) | ||
895 | return 2; | ||
896 | if (soln[y*w+x] != NONTENT && sc->links[y*w+x] == 0) | ||
897 | return 2; | ||
898 | } | ||
899 | |||
900 | return 1; | ||
901 | } | ||
902 | |||
903 | static char *new_game_desc(const game_params *params_in, random_state *rs, | ||
904 | char **aux, int interactive) | ||
905 | { | ||
906 | game_params params_copy = *params_in; /* structure copy */ | ||
907 | game_params *params = ¶ms_copy; | ||
908 | int w = params->w, h = params->h; | ||
909 | int ntrees = w * h / 5; | ||
910 | char *grid = snewn(w*h, char); | ||
911 | char *puzzle = snewn(w*h, char); | ||
912 | int *numbers = snewn(w+h, int); | ||
913 | char *soln = snewn(w*h, char); | ||
914 | int *temp = snewn(2*w*h, int); | ||
915 | int maxedges = ntrees*4 + w*h; | ||
916 | int *edges = snewn(2*maxedges, int); | ||
917 | int *capacity = snewn(maxedges, int); | ||
918 | int *flow = snewn(maxedges, int); | ||
919 | struct solver_scratch *sc = new_scratch(w, h); | ||
920 | char *ret, *p; | ||
921 | int i, j, nedges; | ||
922 | |||
923 | /* | ||
924 | * Since this puzzle has many global deductions and doesn't | ||
925 | * permit limited clue sets, generating grids for this puzzle | ||
926 | * is hard enough that I see no better option than to simply | ||
927 | * generate a solution and see if it's unique and has the | ||
928 | * required difficulty. This turns out to be computationally | ||
929 | * plausible as well. | ||
930 | * | ||
931 | * We chose our tree count (hence also tent count) by dividing | ||
932 | * the total grid area by five above. Why five? Well, w*h/4 is | ||
933 | * the maximum number of tents you can _possibly_ fit into the | ||
934 | * grid without violating the separation criterion, and to | ||
935 | * achieve that you are constrained to a very small set of | ||
936 | * possible layouts (the obvious one with a tent at every | ||
937 | * (even,even) coordinate, and trivial variations thereon). So | ||
938 | * if we reduce the tent count a bit more, we enable more | ||
939 | * random-looking placement; 5 turns out to be a plausible | ||
940 | * figure which yields sensible puzzles. Increasing the tent | ||
941 | * count would give puzzles whose solutions were too regimented | ||
942 | * and could be solved by the use of that knowledge (and would | ||
943 | * also take longer to find a viable placement); decreasing it | ||
944 | * would make the grids emptier and more boring. | ||
945 | * | ||
946 | * Actually generating a grid is a matter of first placing the | ||
947 | * tents, and then placing the trees by the use of maxflow | ||
948 | * (finding a distinct square adjacent to every tent). We do it | ||
949 | * this way round because otherwise satisfying the tent | ||
950 | * separation condition would become onerous: most randomly | ||
951 | * chosen tent layouts do not satisfy this condition, so we'd | ||
952 | * have gone to a lot of work before finding that a candidate | ||
953 | * layout was unusable. Instead, we place the tents first and | ||
954 | * ensure they meet the separation criterion _before_ doing | ||
955 | * lots of computation; this works much better. | ||
956 | * | ||
957 | * The maxflow algorithm is not randomised, so employed naively | ||
958 | * it would give rise to grids with clear structure and | ||
959 | * directional bias. Hence, I assign the network nodes as seen | ||
960 | * by maxflow to be a _random_ permutation of the squares of | ||
961 | * the grid, so that any bias shown by maxflow towards | ||
962 | * low-numbered nodes is turned into a random bias. | ||
963 | * | ||
964 | * This generation strategy can fail at many points, including | ||
965 | * as early as tent placement (if you get a bad random order in | ||
966 | * which to greedily try the grid squares, you won't even | ||
967 | * manage to find enough mutually non-adjacent squares to put | ||
968 | * the tents in). Then it can fail if maxflow doesn't manage to | ||
969 | * find a good enough matching (i.e. the tent placements don't | ||
970 | * admit any adequate tree placements); and finally it can fail | ||
971 | * if the solver finds that the problem has the wrong | ||
972 | * difficulty (including being actually non-unique). All of | ||
973 | * these, however, are insufficiently frequent to cause | ||
974 | * trouble. | ||
975 | */ | ||
976 | |||
977 | if (params->diff > DIFF_EASY && params->w <= 4 && params->h <= 4) | ||
978 | params->diff = DIFF_EASY; /* downgrade to prevent tight loop */ | ||
979 | |||
980 | while (1) { | ||
981 | /* | ||
982 | * Arrange the grid squares into a random order. | ||
983 | */ | ||
984 | for (i = 0; i < w*h; i++) | ||
985 | temp[i] = i; | ||
986 | shuffle(temp, w*h, sizeof(*temp), rs); | ||
987 | |||
988 | /* | ||
989 | * The first `ntrees' entries in temp which we can get | ||
990 | * without making two tents adjacent will be the tent | ||
991 | * locations. | ||
992 | */ | ||
993 | memset(grid, BLANK, w*h); | ||
994 | j = ntrees; | ||
995 | for (i = 0; i < w*h && j > 0; i++) { | ||
996 | int x = temp[i] % w, y = temp[i] / w; | ||
997 | int dy, dx, ok = TRUE; | ||
998 | |||
999 | for (dy = -1; dy <= +1; dy++) | ||
1000 | for (dx = -1; dx <= +1; dx++) | ||
1001 | if (x+dx >= 0 && x+dx < w && | ||
1002 | y+dy >= 0 && y+dy < h && | ||
1003 | grid[(y+dy)*w+(x+dx)] == TENT) | ||
1004 | ok = FALSE; | ||
1005 | |||
1006 | if (ok) { | ||
1007 | grid[temp[i]] = TENT; | ||
1008 | j--; | ||
1009 | } | ||
1010 | } | ||
1011 | if (j > 0) | ||
1012 | continue; /* couldn't place all the tents */ | ||
1013 | |||
1014 | /* | ||
1015 | * Now we build up the list of graph edges. | ||
1016 | */ | ||
1017 | nedges = 0; | ||
1018 | for (i = 0; i < w*h; i++) { | ||
1019 | if (grid[temp[i]] == TENT) { | ||
1020 | for (j = 0; j < w*h; j++) { | ||
1021 | if (grid[temp[j]] != TENT) { | ||
1022 | int xi = temp[i] % w, yi = temp[i] / w; | ||
1023 | int xj = temp[j] % w, yj = temp[j] / w; | ||
1024 | if (abs(xi-xj) + abs(yi-yj) == 1) { | ||
1025 | edges[nedges*2] = i; | ||
1026 | edges[nedges*2+1] = j; | ||
1027 | capacity[nedges] = 1; | ||
1028 | nedges++; | ||
1029 | } | ||
1030 | } | ||
1031 | } | ||
1032 | } else { | ||
1033 | /* | ||
1034 | * Special node w*h is the sink node; any non-tent node | ||
1035 | * has an edge going to it. | ||
1036 | */ | ||
1037 | edges[nedges*2] = i; | ||
1038 | edges[nedges*2+1] = w*h; | ||
1039 | capacity[nedges] = 1; | ||
1040 | nedges++; | ||
1041 | } | ||
1042 | } | ||
1043 | |||
1044 | /* | ||
1045 | * Special node w*h+1 is the source node, with an edge going to | ||
1046 | * every tent. | ||
1047 | */ | ||
1048 | for (i = 0; i < w*h; i++) { | ||
1049 | if (grid[temp[i]] == TENT) { | ||
1050 | edges[nedges*2] = w*h+1; | ||
1051 | edges[nedges*2+1] = i; | ||
1052 | capacity[nedges] = 1; | ||
1053 | nedges++; | ||
1054 | } | ||
1055 | } | ||
1056 | |||
1057 | assert(nedges <= maxedges); | ||
1058 | |||
1059 | /* | ||
1060 | * Now we're ready to call the maxflow algorithm to place the | ||
1061 | * trees. | ||
1062 | */ | ||
1063 | j = maxflow(w*h+2, w*h+1, w*h, nedges, edges, capacity, flow, NULL); | ||
1064 | |||
1065 | if (j < ntrees) | ||
1066 | continue; /* couldn't place all the trees */ | ||
1067 | |||
1068 | /* | ||
1069 | * We've placed the trees. Now we need to work out _where_ | ||
1070 | * we've placed them, which is a matter of reading back out | ||
1071 | * from the `flow' array. | ||
1072 | */ | ||
1073 | for (i = 0; i < nedges; i++) { | ||
1074 | if (edges[2*i] < w*h && edges[2*i+1] < w*h && flow[i] > 0) | ||
1075 | grid[temp[edges[2*i+1]]] = TREE; | ||
1076 | } | ||
1077 | |||
1078 | /* | ||
1079 | * I think it looks ugly if there isn't at least one of | ||
1080 | * _something_ (tent or tree) in each row and each column | ||
1081 | * of the grid. This doesn't give any information away | ||
1082 | * since a completely empty row/column is instantly obvious | ||
1083 | * from the clues (it has no trees and a zero). | ||
1084 | */ | ||
1085 | for (i = 0; i < w; i++) { | ||
1086 | for (j = 0; j < h; j++) { | ||
1087 | if (grid[j*w+i] != BLANK) | ||
1088 | break; /* found something in this column */ | ||
1089 | } | ||
1090 | if (j == h) | ||
1091 | break; /* found empty column */ | ||
1092 | } | ||
1093 | if (i < w) | ||
1094 | continue; /* a column was empty */ | ||
1095 | |||
1096 | for (j = 0; j < h; j++) { | ||
1097 | for (i = 0; i < w; i++) { | ||
1098 | if (grid[j*w+i] != BLANK) | ||
1099 | break; /* found something in this row */ | ||
1100 | } | ||
1101 | if (i == w) | ||
1102 | break; /* found empty row */ | ||
1103 | } | ||
1104 | if (j < h) | ||
1105 | continue; /* a row was empty */ | ||
1106 | |||
1107 | /* | ||
1108 | * Now set up the numbers round the edge. | ||
1109 | */ | ||
1110 | for (i = 0; i < w; i++) { | ||
1111 | int n = 0; | ||
1112 | for (j = 0; j < h; j++) | ||
1113 | if (grid[j*w+i] == TENT) | ||
1114 | n++; | ||
1115 | numbers[i] = n; | ||
1116 | } | ||
1117 | for (i = 0; i < h; i++) { | ||
1118 | int n = 0; | ||
1119 | for (j = 0; j < w; j++) | ||
1120 | if (grid[i*w+j] == TENT) | ||
1121 | n++; | ||
1122 | numbers[w+i] = n; | ||
1123 | } | ||
1124 | |||
1125 | /* | ||
1126 | * And now actually solve the puzzle, to see whether it's | ||
1127 | * unique and has the required difficulty. | ||
1128 | */ | ||
1129 | for (i = 0; i < w*h; i++) | ||
1130 | puzzle[i] = grid[i] == TREE ? TREE : BLANK; | ||
1131 | i = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff-1); | ||
1132 | j = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff); | ||
1133 | |||
1134 | /* | ||
1135 | * We expect solving with difficulty params->diff to have | ||
1136 | * succeeded (otherwise the problem is too hard), and | ||
1137 | * solving with diff-1 to have failed (otherwise it's too | ||
1138 | * easy). | ||
1139 | */ | ||
1140 | if (i == 2 && j == 1) | ||
1141 | break; | ||
1142 | } | ||
1143 | |||
1144 | /* | ||
1145 | * That's it. Encode as a game ID. | ||
1146 | */ | ||
1147 | ret = snewn((w+h)*40 + ntrees + (w*h)/26 + 1, char); | ||
1148 | p = ret; | ||
1149 | j = 0; | ||
1150 | for (i = 0; i <= w*h; i++) { | ||
1151 | int c = (i < w*h ? grid[i] == TREE : 1); | ||
1152 | if (c) { | ||
1153 | *p++ = (j == 0 ? '_' : j-1 + 'a'); | ||
1154 | j = 0; | ||
1155 | } else { | ||
1156 | j++; | ||
1157 | while (j > 25) { | ||
1158 | *p++ = 'z'; | ||
1159 | j -= 25; | ||
1160 | } | ||
1161 | } | ||
1162 | } | ||
1163 | for (i = 0; i < w+h; i++) | ||
1164 | p += sprintf(p, ",%d", numbers[i]); | ||
1165 | *p++ = '\0'; | ||
1166 | ret = sresize(ret, p - ret, char); | ||
1167 | |||
1168 | /* | ||
1169 | * And encode the solution as an aux_info. | ||
1170 | */ | ||
1171 | *aux = snewn(ntrees * 40, char); | ||
1172 | p = *aux; | ||
1173 | *p++ = 'S'; | ||
1174 | for (i = 0; i < w*h; i++) | ||
1175 | if (grid[i] == TENT) | ||
1176 | p += sprintf(p, ";T%d,%d", i%w, i/w); | ||
1177 | *p++ = '\0'; | ||
1178 | *aux = sresize(*aux, p - *aux, char); | ||
1179 | |||
1180 | free_scratch(sc); | ||
1181 | sfree(flow); | ||
1182 | sfree(capacity); | ||
1183 | sfree(edges); | ||
1184 | sfree(temp); | ||
1185 | sfree(soln); | ||
1186 | sfree(numbers); | ||
1187 | sfree(puzzle); | ||
1188 | sfree(grid); | ||
1189 | |||
1190 | return ret; | ||
1191 | } | ||
1192 | |||
1193 | static char *validate_desc(const game_params *params, const char *desc) | ||
1194 | { | ||
1195 | int w = params->w, h = params->h; | ||
1196 | int area, i; | ||
1197 | |||
1198 | area = 0; | ||
1199 | while (*desc && *desc != ',') { | ||
1200 | if (*desc == '_') | ||
1201 | area++; | ||
1202 | else if (*desc >= 'a' && *desc < 'z') | ||
1203 | area += *desc - 'a' + 2; | ||
1204 | else if (*desc == 'z') | ||
1205 | area += 25; | ||
1206 | else if (*desc == '!' || *desc == '-') | ||
1207 | /* do nothing */; | ||
1208 | else | ||
1209 | return "Invalid character in grid specification"; | ||
1210 | |||
1211 | desc++; | ||
1212 | } | ||
1213 | if (area < w * h + 1) | ||
1214 | return "Not enough data to fill grid"; | ||
1215 | else if (area > w * h + 1) | ||
1216 | return "Too much data to fill grid"; | ||
1217 | |||
1218 | for (i = 0; i < w+h; i++) { | ||
1219 | if (!*desc) | ||
1220 | return "Not enough numbers given after grid specification"; | ||
1221 | else if (*desc != ',') | ||
1222 | return "Invalid character in number list"; | ||
1223 | desc++; | ||
1224 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
1225 | } | ||
1226 | |||
1227 | if (*desc) | ||
1228 | return "Unexpected additional data at end of game description"; | ||
1229 | return NULL; | ||
1230 | } | ||
1231 | |||
1232 | static game_state *new_game(midend *me, const game_params *params, | ||
1233 | const char *desc) | ||
1234 | { | ||
1235 | int w = params->w, h = params->h; | ||
1236 | game_state *state = snew(game_state); | ||
1237 | int i; | ||
1238 | |||
1239 | state->p = *params; /* structure copy */ | ||
1240 | state->grid = snewn(w*h, char); | ||
1241 | state->numbers = snew(struct numbers); | ||
1242 | state->numbers->refcount = 1; | ||
1243 | state->numbers->numbers = snewn(w+h, int); | ||
1244 | state->completed = state->used_solve = FALSE; | ||
1245 | |||
1246 | i = 0; | ||
1247 | memset(state->grid, BLANK, w*h); | ||
1248 | |||
1249 | while (*desc) { | ||
1250 | int run, type; | ||
1251 | |||
1252 | type = TREE; | ||
1253 | |||
1254 | if (*desc == '_') | ||
1255 | run = 0; | ||
1256 | else if (*desc >= 'a' && *desc < 'z') | ||
1257 | run = *desc - ('a'-1); | ||
1258 | else if (*desc == 'z') { | ||
1259 | run = 25; | ||
1260 | type = BLANK; | ||
1261 | } else { | ||
1262 | assert(*desc == '!' || *desc == '-'); | ||
1263 | run = -1; | ||
1264 | type = (*desc == '!' ? TENT : NONTENT); | ||
1265 | } | ||
1266 | |||
1267 | desc++; | ||
1268 | |||
1269 | i += run; | ||
1270 | assert(i >= 0 && i <= w*h); | ||
1271 | if (i == w*h) { | ||
1272 | assert(type == TREE); | ||
1273 | break; | ||
1274 | } else { | ||
1275 | if (type != BLANK) | ||
1276 | state->grid[i++] = type; | ||
1277 | } | ||
1278 | } | ||
1279 | |||
1280 | for (i = 0; i < w+h; i++) { | ||
1281 | assert(*desc == ','); | ||
1282 | desc++; | ||
1283 | state->numbers->numbers[i] = atoi(desc); | ||
1284 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
1285 | } | ||
1286 | |||
1287 | assert(!*desc); | ||
1288 | |||
1289 | return state; | ||
1290 | } | ||
1291 | |||
1292 | static game_state *dup_game(const game_state *state) | ||
1293 | { | ||
1294 | int w = state->p.w, h = state->p.h; | ||
1295 | game_state *ret = snew(game_state); | ||
1296 | |||
1297 | ret->p = state->p; /* structure copy */ | ||
1298 | ret->grid = snewn(w*h, char); | ||
1299 | memcpy(ret->grid, state->grid, w*h); | ||
1300 | ret->numbers = state->numbers; | ||
1301 | state->numbers->refcount++; | ||
1302 | ret->completed = state->completed; | ||
1303 | ret->used_solve = state->used_solve; | ||
1304 | |||
1305 | return ret; | ||
1306 | } | ||
1307 | |||
1308 | static void free_game(game_state *state) | ||
1309 | { | ||
1310 | if (--state->numbers->refcount <= 0) { | ||
1311 | sfree(state->numbers->numbers); | ||
1312 | sfree(state->numbers); | ||
1313 | } | ||
1314 | sfree(state->grid); | ||
1315 | sfree(state); | ||
1316 | } | ||
1317 | |||
1318 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1319 | const char *aux, char **error) | ||
1320 | { | ||
1321 | int w = state->p.w, h = state->p.h; | ||
1322 | |||
1323 | if (aux) { | ||
1324 | /* | ||
1325 | * If we already have the solution, save ourselves some | ||
1326 | * time. | ||
1327 | */ | ||
1328 | return dupstr(aux); | ||
1329 | } else { | ||
1330 | struct solver_scratch *sc = new_scratch(w, h); | ||
1331 | char *soln; | ||
1332 | int ret; | ||
1333 | char *move, *p; | ||
1334 | int i; | ||
1335 | |||
1336 | soln = snewn(w*h, char); | ||
1337 | ret = tents_solve(w, h, state->grid, state->numbers->numbers, | ||
1338 | soln, sc, DIFFCOUNT-1); | ||
1339 | free_scratch(sc); | ||
1340 | if (ret != 1) { | ||
1341 | sfree(soln); | ||
1342 | if (ret == 0) | ||
1343 | *error = "This puzzle is not self-consistent"; | ||
1344 | else | ||
1345 | *error = "Unable to find a unique solution for this puzzle"; | ||
1346 | return NULL; | ||
1347 | } | ||
1348 | |||
1349 | /* | ||
1350 | * Construct a move string which turns the current state | ||
1351 | * into the solved state. | ||
1352 | */ | ||
1353 | move = snewn(w*h * 40, char); | ||
1354 | p = move; | ||
1355 | *p++ = 'S'; | ||
1356 | for (i = 0; i < w*h; i++) | ||
1357 | if (soln[i] == TENT) | ||
1358 | p += sprintf(p, ";T%d,%d", i%w, i/w); | ||
1359 | *p++ = '\0'; | ||
1360 | move = sresize(move, p - move, char); | ||
1361 | |||
1362 | sfree(soln); | ||
1363 | |||
1364 | return move; | ||
1365 | } | ||
1366 | } | ||
1367 | |||
1368 | static int game_can_format_as_text_now(const game_params *params) | ||
1369 | { | ||
1370 | return params->w <= 1998 && params->h <= 1998; /* 999 tents */ | ||
1371 | } | ||
1372 | |||
1373 | static char *game_text_format(const game_state *state) | ||
1374 | { | ||
1375 | int w = state->p.w, h = state->p.h, r, c; | ||
1376 | int cw = 4, ch = 2, gw = (w+1)*cw + 2, gh = (h+1)*ch + 1, len = gw * gh; | ||
1377 | char *board = snewn(len + 1, char); | ||
1378 | |||
1379 | sprintf(board, "%*s\n", len - 2, ""); | ||
1380 | for (r = 0; r <= h; ++r) { | ||
1381 | for (c = 0; c <= w; ++c) { | ||
1382 | int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2; | ||
1383 | int i = r*w + c, n = 1000; | ||
1384 | |||
1385 | if (r == h && c == w) /* NOP */; | ||
1386 | else if (c == w) n = state->numbers->numbers[w + r]; | ||
1387 | else if (r == h) n = state->numbers->numbers[c]; | ||
1388 | else switch (state->grid[i]) { | ||
1389 | case BLANK: board[center] = '.'; break; | ||
1390 | case TREE: board[center] = 'T'; break; | ||
1391 | case TENT: memcpy(board + center - 1, "//\\", 3); break; | ||
1392 | case NONTENT: break; | ||
1393 | default: memcpy(board + center - 1, "wtf", 3); | ||
1394 | } | ||
1395 | |||
1396 | if (n < 100) { | ||
1397 | board[center] = '0' + n % 10; | ||
1398 | if (n >= 10) board[center - 1] = '0' + n / 10; | ||
1399 | } else if (n < 1000) { | ||
1400 | board[center + 1] = '0' + n % 10; | ||
1401 | board[center] = '0' + n / 10 % 10; | ||
1402 | board[center - 1] = '0' + n / 100; | ||
1403 | } | ||
1404 | |||
1405 | board[cell] = '+'; | ||
1406 | memset(board + cell + 1, '-', cw - 1); | ||
1407 | for (i = 1; i < ch; ++i) board[cell + i*gw] = '|'; | ||
1408 | } | ||
1409 | |||
1410 | for (c = 0; c < ch; ++c) { | ||
1411 | board[(r*ch+c)*gw + gw - 2] = | ||
1412 | c == 0 ? '+' : r < h ? '|' : ' '; | ||
1413 | board[(r*ch+c)*gw + gw - 1] = '\n'; | ||
1414 | } | ||
1415 | } | ||
1416 | |||
1417 | memset(board + len - gw, '-', gw - 2 - cw); | ||
1418 | for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+'; | ||
1419 | |||
1420 | return board; | ||
1421 | } | ||
1422 | |||
1423 | struct game_ui { | ||
1424 | int dsx, dsy; /* coords of drag start */ | ||
1425 | int dex, dey; /* coords of drag end */ | ||
1426 | int drag_button; /* -1 for none, or a button code */ | ||
1427 | int drag_ok; /* dragged off the window, to cancel */ | ||
1428 | |||
1429 | int cx, cy, cdisp; /* cursor position, and ?display. */ | ||
1430 | }; | ||
1431 | |||
1432 | static game_ui *new_ui(const game_state *state) | ||
1433 | { | ||
1434 | game_ui *ui = snew(game_ui); | ||
1435 | ui->dsx = ui->dsy = -1; | ||
1436 | ui->dex = ui->dey = -1; | ||
1437 | ui->drag_button = -1; | ||
1438 | ui->drag_ok = FALSE; | ||
1439 | ui->cx = ui->cy = ui->cdisp = 0; | ||
1440 | return ui; | ||
1441 | } | ||
1442 | |||
1443 | static void free_ui(game_ui *ui) | ||
1444 | { | ||
1445 | sfree(ui); | ||
1446 | } | ||
1447 | |||
1448 | static char *encode_ui(const game_ui *ui) | ||
1449 | { | ||
1450 | return NULL; | ||
1451 | } | ||
1452 | |||
1453 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1454 | { | ||
1455 | } | ||
1456 | |||
1457 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1458 | const game_state *newstate) | ||
1459 | { | ||
1460 | } | ||
1461 | |||
1462 | struct game_drawstate { | ||
1463 | int tilesize; | ||
1464 | int started; | ||
1465 | game_params p; | ||
1466 | int *drawn, *numbersdrawn; | ||
1467 | int cx, cy; /* last-drawn cursor pos, or (-1,-1) if absent. */ | ||
1468 | }; | ||
1469 | |||
1470 | #define PREFERRED_TILESIZE 32 | ||
1471 | #define TILESIZE (ds->tilesize) | ||
1472 | #define TLBORDER (TILESIZE/2) | ||
1473 | #define BRBORDER (TILESIZE*3/2) | ||
1474 | #define COORD(x) ( (x) * TILESIZE + TLBORDER ) | ||
1475 | #define FROMCOORD(x) ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 ) | ||
1476 | |||
1477 | #define FLASH_TIME 0.30F | ||
1478 | |||
1479 | static int drag_xform(const game_ui *ui, int x, int y, int v) | ||
1480 | { | ||
1481 | int xmin, ymin, xmax, ymax; | ||
1482 | |||
1483 | xmin = min(ui->dsx, ui->dex); | ||
1484 | xmax = max(ui->dsx, ui->dex); | ||
1485 | ymin = min(ui->dsy, ui->dey); | ||
1486 | ymax = max(ui->dsy, ui->dey); | ||
1487 | |||
1488 | #ifndef STYLUS_BASED | ||
1489 | /* | ||
1490 | * Left-dragging has no effect, so we treat a left-drag as a | ||
1491 | * single click on dsx,dsy. | ||
1492 | */ | ||
1493 | if (ui->drag_button == LEFT_BUTTON) { | ||
1494 | xmin = xmax = ui->dsx; | ||
1495 | ymin = ymax = ui->dsy; | ||
1496 | } | ||
1497 | #endif | ||
1498 | |||
1499 | if (x < xmin || x > xmax || y < ymin || y > ymax) | ||
1500 | return v; /* no change outside drag area */ | ||
1501 | |||
1502 | if (v == TREE) | ||
1503 | return v; /* trees are inviolate always */ | ||
1504 | |||
1505 | if (xmin == xmax && ymin == ymax) { | ||
1506 | /* | ||
1507 | * Results of a simple click. Left button sets blanks to | ||
1508 | * tents; right button sets blanks to non-tents; either | ||
1509 | * button clears a non-blank square. | ||
1510 | * If stylus-based however, it loops instead. | ||
1511 | */ | ||
1512 | if (ui->drag_button == LEFT_BUTTON) | ||
1513 | #ifdef STYLUS_BASED | ||
1514 | v = (v == BLANK ? TENT : (v == TENT ? NONTENT : BLANK)); | ||
1515 | else | ||
1516 | v = (v == BLANK ? NONTENT : (v == NONTENT ? TENT : BLANK)); | ||
1517 | #else | ||
1518 | v = (v == BLANK ? TENT : BLANK); | ||
1519 | else | ||
1520 | v = (v == BLANK ? NONTENT : BLANK); | ||
1521 | #endif | ||
1522 | } else { | ||
1523 | /* | ||
1524 | * Results of a drag. Left-dragging has no effect. | ||
1525 | * Right-dragging sets all blank squares to non-tents and | ||
1526 | * has no effect on anything else. | ||
1527 | */ | ||
1528 | if (ui->drag_button == RIGHT_BUTTON) | ||
1529 | v = (v == BLANK ? NONTENT : v); | ||
1530 | else | ||
1531 | #ifdef STYLUS_BASED | ||
1532 | v = (v == BLANK ? NONTENT : v); | ||
1533 | #else | ||
1534 | /* do nothing */; | ||
1535 | #endif | ||
1536 | } | ||
1537 | |||
1538 | return v; | ||
1539 | } | ||
1540 | |||
1541 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1542 | const game_drawstate *ds, | ||
1543 | int x, int y, int button) | ||
1544 | { | ||
1545 | int w = state->p.w, h = state->p.h; | ||
1546 | char tmpbuf[80]; | ||
1547 | int shift = button & MOD_SHFT, control = button & MOD_CTRL; | ||
1548 | |||
1549 | button &= ~MOD_MASK; | ||
1550 | |||
1551 | if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { | ||
1552 | x = FROMCOORD(x); | ||
1553 | y = FROMCOORD(y); | ||
1554 | if (x < 0 || y < 0 || x >= w || y >= h) | ||
1555 | return NULL; | ||
1556 | |||
1557 | ui->drag_button = button; | ||
1558 | ui->dsx = ui->dex = x; | ||
1559 | ui->dsy = ui->dey = y; | ||
1560 | ui->drag_ok = TRUE; | ||
1561 | ui->cdisp = 0; | ||
1562 | return ""; /* ui updated */ | ||
1563 | } | ||
1564 | |||
1565 | if ((IS_MOUSE_DRAG(button) || IS_MOUSE_RELEASE(button)) && | ||
1566 | ui->drag_button > 0) { | ||
1567 | int xmin, ymin, xmax, ymax; | ||
1568 | char *buf, *sep; | ||
1569 | int buflen, bufsize, tmplen; | ||
1570 | |||
1571 | x = FROMCOORD(x); | ||
1572 | y = FROMCOORD(y); | ||
1573 | if (x < 0 || y < 0 || x >= w || y >= h) { | ||
1574 | ui->drag_ok = FALSE; | ||
1575 | } else { | ||
1576 | /* | ||
1577 | * Drags are limited to one row or column. Hence, we | ||
1578 | * work out which coordinate is closer to the drag | ||
1579 | * start, and move it _to_ the drag start. | ||
1580 | */ | ||
1581 | if (abs(x - ui->dsx) < abs(y - ui->dsy)) | ||
1582 | x = ui->dsx; | ||
1583 | else | ||
1584 | y = ui->dsy; | ||
1585 | |||
1586 | ui->dex = x; | ||
1587 | ui->dey = y; | ||
1588 | |||
1589 | ui->drag_ok = TRUE; | ||
1590 | } | ||
1591 | |||
1592 | if (IS_MOUSE_DRAG(button)) | ||
1593 | return ""; /* ui updated */ | ||
1594 | |||
1595 | /* | ||
1596 | * The drag has been released. Enact it. | ||
1597 | */ | ||
1598 | if (!ui->drag_ok) { | ||
1599 | ui->drag_button = -1; | ||
1600 | return ""; /* drag was just cancelled */ | ||
1601 | } | ||
1602 | |||
1603 | xmin = min(ui->dsx, ui->dex); | ||
1604 | xmax = max(ui->dsx, ui->dex); | ||
1605 | ymin = min(ui->dsy, ui->dey); | ||
1606 | ymax = max(ui->dsy, ui->dey); | ||
1607 | assert(0 <= xmin && xmin <= xmax && xmax < w); | ||
1608 | assert(0 <= ymin && ymin <= ymax && ymax < h); | ||
1609 | |||
1610 | buflen = 0; | ||
1611 | bufsize = 256; | ||
1612 | buf = snewn(bufsize, char); | ||
1613 | sep = ""; | ||
1614 | for (y = ymin; y <= ymax; y++) | ||
1615 | for (x = xmin; x <= xmax; x++) { | ||
1616 | int v = drag_xform(ui, x, y, state->grid[y*w+x]); | ||
1617 | if (state->grid[y*w+x] != v) { | ||
1618 | tmplen = sprintf(tmpbuf, "%s%c%d,%d", sep, | ||
1619 | (int)(v == BLANK ? 'B' : | ||
1620 | v == TENT ? 'T' : 'N'), | ||
1621 | x, y); | ||
1622 | sep = ";"; | ||
1623 | |||
1624 | if (buflen + tmplen >= bufsize) { | ||
1625 | bufsize = buflen + tmplen + 256; | ||
1626 | buf = sresize(buf, bufsize, char); | ||
1627 | } | ||
1628 | |||
1629 | strcpy(buf+buflen, tmpbuf); | ||
1630 | buflen += tmplen; | ||
1631 | } | ||
1632 | } | ||
1633 | |||
1634 | ui->drag_button = -1; /* drag is terminated */ | ||
1635 | |||
1636 | if (buflen == 0) { | ||
1637 | sfree(buf); | ||
1638 | return ""; /* ui updated (drag was terminated) */ | ||
1639 | } else { | ||
1640 | buf[buflen] = '\0'; | ||
1641 | return buf; | ||
1642 | } | ||
1643 | } | ||
1644 | |||
1645 | if (IS_CURSOR_MOVE(button)) { | ||
1646 | ui->cdisp = 1; | ||
1647 | if (shift || control) { | ||
1648 | int len = 0, i, indices[2]; | ||
1649 | indices[0] = ui->cx + w * ui->cy; | ||
1650 | move_cursor(button, &ui->cx, &ui->cy, w, h, 0); | ||
1651 | indices[1] = ui->cx + w * ui->cy; | ||
1652 | |||
1653 | /* NONTENTify all unique traversed eligible squares */ | ||
1654 | for (i = 0; i <= (indices[0] != indices[1]); ++i) | ||
1655 | if (state->grid[indices[i]] == BLANK || | ||
1656 | (control && state->grid[indices[i]] == TENT)) { | ||
1657 | len += sprintf(tmpbuf + len, "%sN%d,%d", len ? ";" : "", | ||
1658 | indices[i] % w, indices[i] / w); | ||
1659 | assert(len < lenof(tmpbuf)); | ||
1660 | } | ||
1661 | |||
1662 | tmpbuf[len] = '\0'; | ||
1663 | if (len) return dupstr(tmpbuf); | ||
1664 | } else | ||
1665 | move_cursor(button, &ui->cx, &ui->cy, w, h, 0); | ||
1666 | return ""; | ||
1667 | } | ||
1668 | if (ui->cdisp) { | ||
1669 | char rep = 0; | ||
1670 | int v = state->grid[ui->cy*w+ui->cx]; | ||
1671 | |||
1672 | if (v != TREE) { | ||
1673 | #ifdef SINGLE_CURSOR_SELECT | ||
1674 | if (button == CURSOR_SELECT) | ||
1675 | /* SELECT cycles T, N, B */ | ||
1676 | rep = v == BLANK ? 'T' : v == TENT ? 'N' : 'B'; | ||
1677 | #else | ||
1678 | if (button == CURSOR_SELECT) | ||
1679 | rep = v == BLANK ? 'T' : 'B'; | ||
1680 | else if (button == CURSOR_SELECT2) | ||
1681 | rep = v == BLANK ? 'N' : 'B'; | ||
1682 | else if (button == 'T' || button == 'N' || button == 'B') | ||
1683 | rep = (char)button; | ||
1684 | #endif | ||
1685 | } | ||
1686 | |||
1687 | if (rep) { | ||
1688 | sprintf(tmpbuf, "%c%d,%d", (int)rep, ui->cx, ui->cy); | ||
1689 | return dupstr(tmpbuf); | ||
1690 | } | ||
1691 | } else if (IS_CURSOR_SELECT(button)) { | ||
1692 | ui->cdisp = 1; | ||
1693 | return ""; | ||
1694 | } | ||
1695 | |||
1696 | return NULL; | ||
1697 | } | ||
1698 | |||
1699 | static game_state *execute_move(const game_state *state, const char *move) | ||
1700 | { | ||
1701 | int w = state->p.w, h = state->p.h; | ||
1702 | char c; | ||
1703 | int x, y, m, n, i, j; | ||
1704 | game_state *ret = dup_game(state); | ||
1705 | |||
1706 | while (*move) { | ||
1707 | c = *move; | ||
1708 | if (c == 'S') { | ||
1709 | int i; | ||
1710 | ret->used_solve = TRUE; | ||
1711 | /* | ||
1712 | * Set all non-tree squares to NONTENT. The rest of the | ||
1713 | * solve move will fill the tents in over the top. | ||
1714 | */ | ||
1715 | for (i = 0; i < w*h; i++) | ||
1716 | if (ret->grid[i] != TREE) | ||
1717 | ret->grid[i] = NONTENT; | ||
1718 | move++; | ||
1719 | } else if (c == 'B' || c == 'T' || c == 'N') { | ||
1720 | move++; | ||
1721 | if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || | ||
1722 | x < 0 || y < 0 || x >= w || y >= h) { | ||
1723 | free_game(ret); | ||
1724 | return NULL; | ||
1725 | } | ||
1726 | if (ret->grid[y*w+x] == TREE) { | ||
1727 | free_game(ret); | ||
1728 | return NULL; | ||
1729 | } | ||
1730 | ret->grid[y*w+x] = (c == 'B' ? BLANK : c == 'T' ? TENT : NONTENT); | ||
1731 | move += n; | ||
1732 | } else { | ||
1733 | free_game(ret); | ||
1734 | return NULL; | ||
1735 | } | ||
1736 | if (*move == ';') | ||
1737 | move++; | ||
1738 | else if (*move) { | ||
1739 | free_game(ret); | ||
1740 | return NULL; | ||
1741 | } | ||
1742 | } | ||
1743 | |||
1744 | /* | ||
1745 | * Check for completion. | ||
1746 | */ | ||
1747 | for (i = n = m = 0; i < w*h; i++) { | ||
1748 | if (ret->grid[i] == TENT) | ||
1749 | n++; | ||
1750 | else if (ret->grid[i] == TREE) | ||
1751 | m++; | ||
1752 | } | ||
1753 | if (n == m) { | ||
1754 | int nedges, maxedges, *edges, *capacity, *flow; | ||
1755 | |||
1756 | /* | ||
1757 | * We have the right number of tents, which is a | ||
1758 | * precondition for the game being complete. Now check that | ||
1759 | * the numbers add up. | ||
1760 | */ | ||
1761 | for (i = 0; i < w; i++) { | ||
1762 | n = 0; | ||
1763 | for (j = 0; j < h; j++) | ||
1764 | if (ret->grid[j*w+i] == TENT) | ||
1765 | n++; | ||
1766 | if (ret->numbers->numbers[i] != n) | ||
1767 | goto completion_check_done; | ||
1768 | } | ||
1769 | for (i = 0; i < h; i++) { | ||
1770 | n = 0; | ||
1771 | for (j = 0; j < w; j++) | ||
1772 | if (ret->grid[i*w+j] == TENT) | ||
1773 | n++; | ||
1774 | if (ret->numbers->numbers[w+i] != n) | ||
1775 | goto completion_check_done; | ||
1776 | } | ||
1777 | /* | ||
1778 | * Also, check that no two tents are adjacent. | ||
1779 | */ | ||
1780 | for (y = 0; y < h; y++) | ||
1781 | for (x = 0; x < w; x++) { | ||
1782 | if (x+1 < w && | ||
1783 | ret->grid[y*w+x] == TENT && ret->grid[y*w+x+1] == TENT) | ||
1784 | goto completion_check_done; | ||
1785 | if (y+1 < h && | ||
1786 | ret->grid[y*w+x] == TENT && ret->grid[(y+1)*w+x] == TENT) | ||
1787 | goto completion_check_done; | ||
1788 | if (x+1 < w && y+1 < h) { | ||
1789 | if (ret->grid[y*w+x] == TENT && | ||
1790 | ret->grid[(y+1)*w+(x+1)] == TENT) | ||
1791 | goto completion_check_done; | ||
1792 | if (ret->grid[(y+1)*w+x] == TENT && | ||
1793 | ret->grid[y*w+(x+1)] == TENT) | ||
1794 | goto completion_check_done; | ||
1795 | } | ||
1796 | } | ||
1797 | |||
1798 | /* | ||
1799 | * OK; we have the right number of tents, they match the | ||
1800 | * numeric clues, and they satisfy the non-adjacency | ||
1801 | * criterion. Finally, we need to verify that they can be | ||
1802 | * placed in a one-to-one matching with the trees such that | ||
1803 | * every tent is orthogonally adjacent to its tree. | ||
1804 | * | ||
1805 | * This bit is where the hard work comes in: we have to do | ||
1806 | * it by finding such a matching using maxflow. | ||
1807 | * | ||
1808 | * So we construct a network with one special source node, | ||
1809 | * one special sink node, one node per tent, and one node | ||
1810 | * per tree. | ||
1811 | */ | ||
1812 | maxedges = 6 * m; | ||
1813 | edges = snewn(2 * maxedges, int); | ||
1814 | capacity = snewn(maxedges, int); | ||
1815 | flow = snewn(maxedges, int); | ||
1816 | nedges = 0; | ||
1817 | /* | ||
1818 | * Node numbering: | ||
1819 | * | ||
1820 | * 0..w*h trees/tents | ||
1821 | * w*h source | ||
1822 | * w*h+1 sink | ||
1823 | */ | ||
1824 | for (y = 0; y < h; y++) | ||
1825 | for (x = 0; x < w; x++) | ||
1826 | if (ret->grid[y*w+x] == TREE) { | ||
1827 | int d; | ||
1828 | |||
1829 | /* | ||
1830 | * Here we use the direction enum declared for | ||
1831 | * the solver. We make use of the fact that the | ||
1832 | * directions are declared in the order | ||
1833 | * U,L,R,D, meaning that we go through the four | ||
1834 | * neighbours of any square in numerically | ||
1835 | * increasing order. | ||
1836 | */ | ||
1837 | for (d = 1; d < MAXDIR; d++) { | ||
1838 | int x2 = x + dx(d), y2 = y + dy(d); | ||
1839 | if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && | ||
1840 | ret->grid[y2*w+x2] == TENT) { | ||
1841 | assert(nedges < maxedges); | ||
1842 | edges[nedges*2] = y*w+x; | ||
1843 | edges[nedges*2+1] = y2*w+x2; | ||
1844 | capacity[nedges] = 1; | ||
1845 | nedges++; | ||
1846 | } | ||
1847 | } | ||
1848 | } else if (ret->grid[y*w+x] == TENT) { | ||
1849 | assert(nedges < maxedges); | ||
1850 | edges[nedges*2] = y*w+x; | ||
1851 | edges[nedges*2+1] = w*h+1; /* edge going to sink */ | ||
1852 | capacity[nedges] = 1; | ||
1853 | nedges++; | ||
1854 | } | ||
1855 | for (y = 0; y < h; y++) | ||
1856 | for (x = 0; x < w; x++) | ||
1857 | if (ret->grid[y*w+x] == TREE) { | ||
1858 | assert(nedges < maxedges); | ||
1859 | edges[nedges*2] = w*h; /* edge coming from source */ | ||
1860 | edges[nedges*2+1] = y*w+x; | ||
1861 | capacity[nedges] = 1; | ||
1862 | nedges++; | ||
1863 | } | ||
1864 | n = maxflow(w*h+2, w*h, w*h+1, nedges, edges, capacity, flow, NULL); | ||
1865 | |||
1866 | sfree(flow); | ||
1867 | sfree(capacity); | ||
1868 | sfree(edges); | ||
1869 | |||
1870 | if (n != m) | ||
1871 | goto completion_check_done; | ||
1872 | |||
1873 | /* | ||
1874 | * We haven't managed to fault the grid on any count. Score! | ||
1875 | */ | ||
1876 | ret->completed = TRUE; | ||
1877 | } | ||
1878 | completion_check_done: | ||
1879 | |||
1880 | return ret; | ||
1881 | } | ||
1882 | |||
1883 | /* ---------------------------------------------------------------------- | ||
1884 | * Drawing routines. | ||
1885 | */ | ||
1886 | |||
1887 | static void game_compute_size(const game_params *params, int tilesize, | ||
1888 | int *x, int *y) | ||
1889 | { | ||
1890 | /* fool the macros */ | ||
1891 | struct dummy { int tilesize; } dummy, *ds = &dummy; | ||
1892 | dummy.tilesize = tilesize; | ||
1893 | |||
1894 | *x = TLBORDER + BRBORDER + TILESIZE * params->w; | ||
1895 | *y = TLBORDER + BRBORDER + TILESIZE * params->h; | ||
1896 | } | ||
1897 | |||
1898 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1899 | const game_params *params, int tilesize) | ||
1900 | { | ||
1901 | ds->tilesize = tilesize; | ||
1902 | } | ||
1903 | |||
1904 | static float *game_colours(frontend *fe, int *ncolours) | ||
1905 | { | ||
1906 | float *ret = snewn(3 * NCOLOURS, float); | ||
1907 | |||
1908 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
1909 | |||
1910 | ret[COL_GRID * 3 + 0] = 0.0F; | ||
1911 | ret[COL_GRID * 3 + 1] = 0.0F; | ||
1912 | ret[COL_GRID * 3 + 2] = 0.0F; | ||
1913 | |||
1914 | ret[COL_GRASS * 3 + 0] = 0.7F; | ||
1915 | ret[COL_GRASS * 3 + 1] = 1.0F; | ||
1916 | ret[COL_GRASS * 3 + 2] = 0.5F; | ||
1917 | |||
1918 | ret[COL_TREETRUNK * 3 + 0] = 0.6F; | ||
1919 | ret[COL_TREETRUNK * 3 + 1] = 0.4F; | ||
1920 | ret[COL_TREETRUNK * 3 + 2] = 0.0F; | ||
1921 | |||
1922 | ret[COL_TREELEAF * 3 + 0] = 0.0F; | ||
1923 | ret[COL_TREELEAF * 3 + 1] = 0.7F; | ||
1924 | ret[COL_TREELEAF * 3 + 2] = 0.0F; | ||
1925 | |||
1926 | ret[COL_TENT * 3 + 0] = 0.8F; | ||
1927 | ret[COL_TENT * 3 + 1] = 0.7F; | ||
1928 | ret[COL_TENT * 3 + 2] = 0.0F; | ||
1929 | |||
1930 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
1931 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
1932 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
1933 | |||
1934 | ret[COL_ERRTEXT * 3 + 0] = 1.0F; | ||
1935 | ret[COL_ERRTEXT * 3 + 1] = 1.0F; | ||
1936 | ret[COL_ERRTEXT * 3 + 2] = 1.0F; | ||
1937 | |||
1938 | ret[COL_ERRTRUNK * 3 + 0] = 0.6F; | ||
1939 | ret[COL_ERRTRUNK * 3 + 1] = 0.0F; | ||
1940 | ret[COL_ERRTRUNK * 3 + 2] = 0.0F; | ||
1941 | |||
1942 | *ncolours = NCOLOURS; | ||
1943 | return ret; | ||
1944 | } | ||
1945 | |||
1946 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1947 | { | ||
1948 | int w = state->p.w, h = state->p.h; | ||
1949 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1950 | int i; | ||
1951 | |||
1952 | ds->tilesize = 0; | ||
1953 | ds->started = FALSE; | ||
1954 | ds->p = state->p; /* structure copy */ | ||
1955 | ds->drawn = snewn(w*h, int); | ||
1956 | for (i = 0; i < w*h; i++) | ||
1957 | ds->drawn[i] = MAGIC; | ||
1958 | ds->numbersdrawn = snewn(w+h, int); | ||
1959 | for (i = 0; i < w+h; i++) | ||
1960 | ds->numbersdrawn[i] = 2; | ||
1961 | ds->cx = ds->cy = -1; | ||
1962 | |||
1963 | return ds; | ||
1964 | } | ||
1965 | |||
1966 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1967 | { | ||
1968 | sfree(ds->drawn); | ||
1969 | sfree(ds->numbersdrawn); | ||
1970 | sfree(ds); | ||
1971 | } | ||
1972 | |||
1973 | enum { | ||
1974 | ERR_ADJ_TOPLEFT = 4, | ||
1975 | ERR_ADJ_TOP, | ||
1976 | ERR_ADJ_TOPRIGHT, | ||
1977 | ERR_ADJ_LEFT, | ||
1978 | ERR_ADJ_RIGHT, | ||
1979 | ERR_ADJ_BOTLEFT, | ||
1980 | ERR_ADJ_BOT, | ||
1981 | ERR_ADJ_BOTRIGHT, | ||
1982 | ERR_OVERCOMMITTED | ||
1983 | }; | ||
1984 | |||
1985 | static int *find_errors(const game_state *state, char *grid) | ||
1986 | { | ||
1987 | int w = state->p.w, h = state->p.h; | ||
1988 | int *ret = snewn(w*h + w + h, int); | ||
1989 | int *tmp = snewn(w*h*2, int), *dsf = tmp + w*h; | ||
1990 | int x, y; | ||
1991 | |||
1992 | /* | ||
1993 | * This function goes through a grid and works out where to | ||
1994 | * highlight play errors in red. The aim is that it should | ||
1995 | * produce at least one error highlight for any complete grid | ||
1996 | * (or complete piece of grid) violating a puzzle constraint, so | ||
1997 | * that a grid containing no BLANK squares is either a win or is | ||
1998 | * marked up in some way that indicates why not. | ||
1999 | * | ||
2000 | * So it's easy enough to highlight errors in the numeric clues | ||
2001 | * - just light up any row or column number which is not | ||
2002 | * fulfilled - and it's just as easy to highlight adjacent | ||
2003 | * tents. The difficult bit is highlighting failures in the | ||
2004 | * tent/tree matching criterion. | ||
2005 | * | ||
2006 | * A natural approach would seem to be to apply the maxflow | ||
2007 | * algorithm to find the tent/tree matching; if this fails, it | ||
2008 | * must necessarily terminate with a min-cut which can be | ||
2009 | * reinterpreted as some set of trees which have too few tents | ||
2010 | * between them (or vice versa). However, it's bad for | ||
2011 | * localising errors, because it's not easy to make the | ||
2012 | * algorithm narrow down to the _smallest_ such set of trees: if | ||
2013 | * trees A and B have only one tent between them, for instance, | ||
2014 | * it might perfectly well highlight not only A and B but also | ||
2015 | * trees C and D which are correctly matched on the far side of | ||
2016 | * the grid, on the grounds that those four trees between them | ||
2017 | * have only three tents. | ||
2018 | * | ||
2019 | * Also, that approach fares badly when you introduce the | ||
2020 | * additional requirement that incomplete grids should have | ||
2021 | * errors highlighted only when they can be proved to be errors | ||
2022 | * - so that trees should not be marked as having too few tents | ||
2023 | * if there are enough BLANK squares remaining around them that | ||
2024 | * could be turned into the missing tents (to do so would be | ||
2025 | * patronising, since the overwhelming likelihood is not that | ||
2026 | * the player has forgotten to put a tree there but that they | ||
2027 | * have merely not put one there _yet_). However, tents with too | ||
2028 | * few trees can be marked immediately, since those are | ||
2029 | * definitely player error. | ||
2030 | * | ||
2031 | * So I adopt an alternative approach, which is to consider the | ||
2032 | * bipartite adjacency graph between trees and tents | ||
2033 | * ('bipartite' in the sense that for these purposes I | ||
2034 | * deliberately ignore two adjacent trees or two adjacent | ||
2035 | * tents), divide that graph up into its connected components | ||
2036 | * using a dsf, and look for components which contain different | ||
2037 | * numbers of trees and tents. This allows me to highlight | ||
2038 | * groups of tents with too few trees between them immediately, | ||
2039 | * and then in order to find groups of trees with too few tents | ||
2040 | * I redo the same process but counting BLANKs as potential | ||
2041 | * tents (so that the only trees highlighted are those | ||
2042 | * surrounded by enough NONTENTs to make it impossible to give | ||
2043 | * them enough tents). | ||
2044 | * | ||
2045 | * However, this technique is incomplete: it is not a sufficient | ||
2046 | * condition for the existence of a perfect matching that every | ||
2047 | * connected component of the graph has the same number of tents | ||
2048 | * and trees. An example of a graph which satisfies the latter | ||
2049 | * condition but still has no perfect matching is | ||
2050 | * | ||
2051 | * A B C | ||
2052 | * | / ,/| | ||
2053 | * | / ,'/ | | ||
2054 | * | / ,' / | | ||
2055 | * |/,' / | | ||
2056 | * 1 2 3 | ||
2057 | * | ||
2058 | * which can be realised in Tents as | ||
2059 | * | ||
2060 | * B | ||
2061 | * A 1 C 2 | ||
2062 | * 3 | ||
2063 | * | ||
2064 | * The matching-error highlighter described above will not mark | ||
2065 | * this construction as erroneous. However, something else will: | ||
2066 | * the three tents in the above diagram (let us suppose A,B,C | ||
2067 | * are the tents, though it doesn't matter which) contain two | ||
2068 | * diagonally adjacent pairs. So there will be _an_ error | ||
2069 | * highlighted for the above layout, even though not all types | ||
2070 | * of error will be highlighted. | ||
2071 | * | ||
2072 | * And in fact we can prove that this will always be the case: | ||
2073 | * that the shortcomings of the matching-error highlighter will | ||
2074 | * always be made up for by the easy tent adjacency highlighter. | ||
2075 | * | ||
2076 | * Lemma: Let G be a bipartite graph between n trees and n | ||
2077 | * tents, which is connected, and in which no tree has degree | ||
2078 | * more than two (but a tent may). Then G has a perfect matching. | ||
2079 | * | ||
2080 | * (Note: in the statement and proof of the Lemma I will | ||
2081 | * consistently use 'tree' to indicate a type of graph vertex as | ||
2082 | * opposed to a tent, and not to indicate a tree in the graph- | ||
2083 | * theoretic sense.) | ||
2084 | * | ||
2085 | * Proof: | ||
2086 | * | ||
2087 | * If we can find a tent of degree 1 joined to a tree of degree | ||
2088 | * 2, then any perfect matching must pair that tent with that | ||
2089 | * tree. Hence, we can remove both, leaving a smaller graph G' | ||
2090 | * which still satisfies all the conditions of the Lemma, and | ||
2091 | * which has a perfect matching iff G does. | ||
2092 | * | ||
2093 | * So, wlog, we may assume G contains no tent of degree 1 joined | ||
2094 | * to a tree of degree 2; if it does, we can reduce it as above. | ||
2095 | * | ||
2096 | * If G has no tent of degree 1 at all, then every tent has | ||
2097 | * degree at least two, so there are at least 2n edges in the | ||
2098 | * graph. But every tree has degree at most two, so there are at | ||
2099 | * most 2n edges. Hence there must be exactly 2n edges, so every | ||
2100 | * tree and every tent must have degree exactly two, which means | ||
2101 | * that the whole graph consists of a single loop (by | ||
2102 | * connectedness), and therefore certainly has a perfect | ||
2103 | * matching. | ||
2104 | * | ||
2105 | * Alternatively, if G does have a tent of degree 1 but it is | ||
2106 | * not connected to a tree of degree 2, then the tree it is | ||
2107 | * connected to must have degree 1 - and, by connectedness, that | ||
2108 | * must mean that that tent and that tree between them form the | ||
2109 | * entire graph. This trivial graph has a trivial perfect | ||
2110 | * matching. [] | ||
2111 | * | ||
2112 | * That proves the lemma. Hence, in any case where the matching- | ||
2113 | * error highlighter fails to highlight an erroneous component | ||
2114 | * (because it has the same number of tents as trees, but they | ||
2115 | * cannot be matched up), the above lemma tells us that there | ||
2116 | * must be a tree with degree more than 2, i.e. a tree | ||
2117 | * orthogonally adjacent to at least three tents. But in that | ||
2118 | * case, there must be some pair of those three tents which are | ||
2119 | * diagonally adjacent to each other, so the tent-adjacency | ||
2120 | * highlighter will necessarily show an error. So any filled | ||
2121 | * layout in Tents which is not a correct solution to the puzzle | ||
2122 | * must have _some_ error highlighted by the subroutine below. | ||
2123 | * | ||
2124 | * (Of course it would be nicer if we could highlight all | ||
2125 | * errors: in the above example layout, we would like to | ||
2126 | * highlight tents A,B as having too few trees between them, and | ||
2127 | * trees 2,3 as having too few tents, in addition to marking the | ||
2128 | * adjacency problems. But I can't immediately think of any way | ||
2129 | * to find the smallest sets of such tents and trees without an | ||
2130 | * O(2^N) loop over all subsets of a given component.) | ||
2131 | */ | ||
2132 | |||
2133 | /* | ||
2134 | * ret[0] through to ret[w*h-1] give error markers for the grid | ||
2135 | * squares. After that, ret[w*h] to ret[w*h+w-1] give error | ||
2136 | * markers for the column numbers, and ret[w*h+w] to | ||
2137 | * ret[w*h+w+h-1] for the row numbers. | ||
2138 | */ | ||
2139 | |||
2140 | /* | ||
2141 | * Spot tent-adjacency violations. | ||
2142 | */ | ||
2143 | for (x = 0; x < w*h; x++) | ||
2144 | ret[x] = 0; | ||
2145 | for (y = 0; y < h; y++) { | ||
2146 | for (x = 0; x < w; x++) { | ||
2147 | if (y+1 < h && x+1 < w && | ||
2148 | ((grid[y*w+x] == TENT && | ||
2149 | grid[(y+1)*w+(x+1)] == TENT) || | ||
2150 | (grid[(y+1)*w+x] == TENT && | ||
2151 | grid[y*w+(x+1)] == TENT))) { | ||
2152 | ret[y*w+x] |= 1 << ERR_ADJ_BOTRIGHT; | ||
2153 | ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOPRIGHT; | ||
2154 | ret[y*w+(x+1)] |= 1 << ERR_ADJ_BOTLEFT; | ||
2155 | ret[(y+1)*w+(x+1)] |= 1 << ERR_ADJ_TOPLEFT; | ||
2156 | } | ||
2157 | if (y+1 < h && | ||
2158 | grid[y*w+x] == TENT && | ||
2159 | grid[(y+1)*w+x] == TENT) { | ||
2160 | ret[y*w+x] |= 1 << ERR_ADJ_BOT; | ||
2161 | ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOP; | ||
2162 | } | ||
2163 | if (x+1 < w && | ||
2164 | grid[y*w+x] == TENT && | ||
2165 | grid[y*w+(x+1)] == TENT) { | ||
2166 | ret[y*w+x] |= 1 << ERR_ADJ_RIGHT; | ||
2167 | ret[y*w+(x+1)] |= 1 << ERR_ADJ_LEFT; | ||
2168 | } | ||
2169 | } | ||
2170 | } | ||
2171 | |||
2172 | /* | ||
2173 | * Spot numeric clue violations. | ||
2174 | */ | ||
2175 | for (x = 0; x < w; x++) { | ||
2176 | int tents = 0, maybetents = 0; | ||
2177 | for (y = 0; y < h; y++) { | ||
2178 | if (grid[y*w+x] == TENT) | ||
2179 | tents++; | ||
2180 | else if (grid[y*w+x] == BLANK) | ||
2181 | maybetents++; | ||
2182 | } | ||
2183 | ret[w*h+x] = (tents > state->numbers->numbers[x] || | ||
2184 | tents + maybetents < state->numbers->numbers[x]); | ||
2185 | } | ||
2186 | for (y = 0; y < h; y++) { | ||
2187 | int tents = 0, maybetents = 0; | ||
2188 | for (x = 0; x < w; x++) { | ||
2189 | if (grid[y*w+x] == TENT) | ||
2190 | tents++; | ||
2191 | else if (grid[y*w+x] == BLANK) | ||
2192 | maybetents++; | ||
2193 | } | ||
2194 | ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] || | ||
2195 | tents + maybetents < state->numbers->numbers[w+y]); | ||
2196 | } | ||
2197 | |||
2198 | /* | ||
2199 | * Identify groups of tents with too few trees between them, | ||
2200 | * which we do by constructing the connected components of the | ||
2201 | * bipartite adjacency graph between tents and trees | ||
2202 | * ('bipartite' in the sense that we deliberately ignore | ||
2203 | * adjacency between tents or between trees), and highlighting | ||
2204 | * all the tents in any component which has a smaller tree | ||
2205 | * count. | ||
2206 | */ | ||
2207 | dsf_init(dsf, w*h); | ||
2208 | /* Construct the equivalence classes. */ | ||
2209 | for (y = 0; y < h; y++) { | ||
2210 | for (x = 0; x < w-1; x++) { | ||
2211 | if ((grid[y*w+x] == TREE && grid[y*w+x+1] == TENT) || | ||
2212 | (grid[y*w+x] == TENT && grid[y*w+x+1] == TREE)) | ||
2213 | dsf_merge(dsf, y*w+x, y*w+x+1); | ||
2214 | } | ||
2215 | } | ||
2216 | for (y = 0; y < h-1; y++) { | ||
2217 | for (x = 0; x < w; x++) { | ||
2218 | if ((grid[y*w+x] == TREE && grid[(y+1)*w+x] == TENT) || | ||
2219 | (grid[y*w+x] == TENT && grid[(y+1)*w+x] == TREE)) | ||
2220 | dsf_merge(dsf, y*w+x, (y+1)*w+x); | ||
2221 | } | ||
2222 | } | ||
2223 | /* Count up the tent/tree difference in each one. */ | ||
2224 | for (x = 0; x < w*h; x++) | ||
2225 | tmp[x] = 0; | ||
2226 | for (x = 0; x < w*h; x++) { | ||
2227 | y = dsf_canonify(dsf, x); | ||
2228 | if (grid[x] == TREE) | ||
2229 | tmp[y]++; | ||
2230 | else if (grid[x] == TENT) | ||
2231 | tmp[y]--; | ||
2232 | } | ||
2233 | /* And highlight any tent belonging to an equivalence class with | ||
2234 | * a score less than zero. */ | ||
2235 | for (x = 0; x < w*h; x++) { | ||
2236 | y = dsf_canonify(dsf, x); | ||
2237 | if (grid[x] == TENT && tmp[y] < 0) | ||
2238 | ret[x] |= 1 << ERR_OVERCOMMITTED; | ||
2239 | } | ||
2240 | |||
2241 | /* | ||
2242 | * Identify groups of trees with too few tents between them. | ||
2243 | * This is done similarly, except that we now count BLANK as | ||
2244 | * equivalent to TENT, i.e. we only highlight such trees when | ||
2245 | * the user hasn't even left _room_ to provide tents for them | ||
2246 | * all. (Otherwise, we'd highlight all trees red right at the | ||
2247 | * start of the game, before the user had done anything wrong!) | ||
2248 | */ | ||
2249 | #define TENT(x) ((x)==TENT || (x)==BLANK) | ||
2250 | dsf_init(dsf, w*h); | ||
2251 | /* Construct the equivalence classes. */ | ||
2252 | for (y = 0; y < h; y++) { | ||
2253 | for (x = 0; x < w-1; x++) { | ||
2254 | if ((grid[y*w+x] == TREE && TENT(grid[y*w+x+1])) || | ||
2255 | (TENT(grid[y*w+x]) && grid[y*w+x+1] == TREE)) | ||
2256 | dsf_merge(dsf, y*w+x, y*w+x+1); | ||
2257 | } | ||
2258 | } | ||
2259 | for (y = 0; y < h-1; y++) { | ||
2260 | for (x = 0; x < w; x++) { | ||
2261 | if ((grid[y*w+x] == TREE && TENT(grid[(y+1)*w+x])) || | ||
2262 | (TENT(grid[y*w+x]) && grid[(y+1)*w+x] == TREE)) | ||
2263 | dsf_merge(dsf, y*w+x, (y+1)*w+x); | ||
2264 | } | ||
2265 | } | ||
2266 | /* Count up the tent/tree difference in each one. */ | ||
2267 | for (x = 0; x < w*h; x++) | ||
2268 | tmp[x] = 0; | ||
2269 | for (x = 0; x < w*h; x++) { | ||
2270 | y = dsf_canonify(dsf, x); | ||
2271 | if (grid[x] == TREE) | ||
2272 | tmp[y]++; | ||
2273 | else if (TENT(grid[x])) | ||
2274 | tmp[y]--; | ||
2275 | } | ||
2276 | /* And highlight any tree belonging to an equivalence class with | ||
2277 | * a score more than zero. */ | ||
2278 | for (x = 0; x < w*h; x++) { | ||
2279 | y = dsf_canonify(dsf, x); | ||
2280 | if (grid[x] == TREE && tmp[y] > 0) | ||
2281 | ret[x] |= 1 << ERR_OVERCOMMITTED; | ||
2282 | } | ||
2283 | #undef TENT | ||
2284 | |||
2285 | sfree(tmp); | ||
2286 | return ret; | ||
2287 | } | ||
2288 | |||
2289 | static void draw_err_adj(drawing *dr, game_drawstate *ds, int x, int y) | ||
2290 | { | ||
2291 | int coords[8]; | ||
2292 | int yext, xext; | ||
2293 | |||
2294 | /* | ||
2295 | * Draw a diamond. | ||
2296 | */ | ||
2297 | coords[0] = x - TILESIZE*2/5; | ||
2298 | coords[1] = y; | ||
2299 | coords[2] = x; | ||
2300 | coords[3] = y - TILESIZE*2/5; | ||
2301 | coords[4] = x + TILESIZE*2/5; | ||
2302 | coords[5] = y; | ||
2303 | coords[6] = x; | ||
2304 | coords[7] = y + TILESIZE*2/5; | ||
2305 | draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID); | ||
2306 | |||
2307 | /* | ||
2308 | * Draw an exclamation mark in the diamond. This turns out to | ||
2309 | * look unpleasantly off-centre if done via draw_text, so I do | ||
2310 | * it by hand on the basis that exclamation marks aren't that | ||
2311 | * difficult to draw... | ||
2312 | */ | ||
2313 | xext = TILESIZE/16; | ||
2314 | yext = TILESIZE*2/5 - (xext*2+2); | ||
2315 | draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3), | ||
2316 | COL_ERRTEXT); | ||
2317 | draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT); | ||
2318 | } | ||
2319 | |||
2320 | static void draw_tile(drawing *dr, game_drawstate *ds, | ||
2321 | int x, int y, int v, int cur, int printing) | ||
2322 | { | ||
2323 | int err; | ||
2324 | int tx = COORD(x), ty = COORD(y); | ||
2325 | int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2; | ||
2326 | |||
2327 | err = v & ~15; | ||
2328 | v &= 15; | ||
2329 | |||
2330 | clip(dr, tx, ty, TILESIZE, TILESIZE); | ||
2331 | |||
2332 | if (!printing) { | ||
2333 | draw_rect(dr, tx, ty, TILESIZE, TILESIZE, COL_GRID); | ||
2334 | draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, | ||
2335 | (v == BLANK ? COL_BACKGROUND : COL_GRASS)); | ||
2336 | } | ||
2337 | |||
2338 | if (v == TREE) { | ||
2339 | int i; | ||
2340 | |||
2341 | (printing ? draw_rect_outline : draw_rect) | ||
2342 | (dr, cx-TILESIZE/15, ty+TILESIZE*3/10, | ||
2343 | 2*(TILESIZE/15)+1, (TILESIZE*9/10 - TILESIZE*3/10), | ||
2344 | (err & (1<<ERR_OVERCOMMITTED) ? COL_ERRTRUNK : COL_TREETRUNK)); | ||
2345 | |||
2346 | for (i = 0; i < (printing ? 2 : 1); i++) { | ||
2347 | int col = (i == 1 ? COL_BACKGROUND : | ||
2348 | (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : | ||
2349 | COL_TREELEAF)); | ||
2350 | int sub = i * (TILESIZE/32); | ||
2351 | draw_circle(dr, cx, ty+TILESIZE*4/10, TILESIZE/4 - sub, | ||
2352 | col, col); | ||
2353 | draw_circle(dr, cx+TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub, | ||
2354 | col, col); | ||
2355 | draw_circle(dr, cx-TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub, | ||
2356 | col, col); | ||
2357 | draw_circle(dr, cx+TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub, | ||
2358 | col, col); | ||
2359 | draw_circle(dr, cx-TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub, | ||
2360 | col, col); | ||
2361 | } | ||
2362 | } else if (v == TENT) { | ||
2363 | int coords[6]; | ||
2364 | int col; | ||
2365 | coords[0] = cx - TILESIZE/3; | ||
2366 | coords[1] = cy + TILESIZE/3; | ||
2367 | coords[2] = cx + TILESIZE/3; | ||
2368 | coords[3] = cy + TILESIZE/3; | ||
2369 | coords[4] = cx; | ||
2370 | coords[5] = cy - TILESIZE/3; | ||
2371 | col = (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : COL_TENT); | ||
2372 | draw_polygon(dr, coords, 3, (printing ? -1 : col), col); | ||
2373 | } | ||
2374 | |||
2375 | if (err & (1 << ERR_ADJ_TOPLEFT)) | ||
2376 | draw_err_adj(dr, ds, tx, ty); | ||
2377 | if (err & (1 << ERR_ADJ_TOP)) | ||
2378 | draw_err_adj(dr, ds, tx+TILESIZE/2, ty); | ||
2379 | if (err & (1 << ERR_ADJ_TOPRIGHT)) | ||
2380 | draw_err_adj(dr, ds, tx+TILESIZE, ty); | ||
2381 | if (err & (1 << ERR_ADJ_LEFT)) | ||
2382 | draw_err_adj(dr, ds, tx, ty+TILESIZE/2); | ||
2383 | if (err & (1 << ERR_ADJ_RIGHT)) | ||
2384 | draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE/2); | ||
2385 | if (err & (1 << ERR_ADJ_BOTLEFT)) | ||
2386 | draw_err_adj(dr, ds, tx, ty+TILESIZE); | ||
2387 | if (err & (1 << ERR_ADJ_BOT)) | ||
2388 | draw_err_adj(dr, ds, tx+TILESIZE/2, ty+TILESIZE); | ||
2389 | if (err & (1 << ERR_ADJ_BOTRIGHT)) | ||
2390 | draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE); | ||
2391 | |||
2392 | if (cur) { | ||
2393 | int coff = TILESIZE/8; | ||
2394 | draw_rect_outline(dr, tx + coff, ty + coff, | ||
2395 | TILESIZE - coff*2 + 1, TILESIZE - coff*2 + 1, | ||
2396 | COL_GRID); | ||
2397 | } | ||
2398 | |||
2399 | unclip(dr); | ||
2400 | draw_update(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1); | ||
2401 | } | ||
2402 | |||
2403 | /* | ||
2404 | * Internal redraw function, used for printing as well as drawing. | ||
2405 | */ | ||
2406 | static void int_redraw(drawing *dr, game_drawstate *ds, | ||
2407 | const game_state *oldstate, const game_state *state, | ||
2408 | int dir, const game_ui *ui, | ||
2409 | float animtime, float flashtime, int printing) | ||
2410 | { | ||
2411 | int w = state->p.w, h = state->p.h; | ||
2412 | int x, y, flashing; | ||
2413 | int cx = -1, cy = -1; | ||
2414 | int cmoved = 0; | ||
2415 | char *tmpgrid; | ||
2416 | int *errors; | ||
2417 | |||
2418 | if (ui) { | ||
2419 | if (ui->cdisp) { cx = ui->cx; cy = ui->cy; } | ||
2420 | if (cx != ds->cx || cy != ds->cy) cmoved = 1; | ||
2421 | } | ||
2422 | |||
2423 | if (printing || !ds->started) { | ||
2424 | if (!printing) { | ||
2425 | int ww, wh; | ||
2426 | game_compute_size(&state->p, TILESIZE, &ww, &wh); | ||
2427 | draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND); | ||
2428 | draw_update(dr, 0, 0, ww, wh); | ||
2429 | ds->started = TRUE; | ||
2430 | } | ||
2431 | |||
2432 | if (printing) | ||
2433 | print_line_width(dr, TILESIZE/64); | ||
2434 | |||
2435 | /* | ||
2436 | * Draw the grid. | ||
2437 | */ | ||
2438 | for (y = 0; y <= h; y++) | ||
2439 | draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), COL_GRID); | ||
2440 | for (x = 0; x <= w; x++) | ||
2441 | draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), COL_GRID); | ||
2442 | } | ||
2443 | |||
2444 | if (flashtime > 0) | ||
2445 | flashing = (int)(flashtime * 3 / FLASH_TIME) != 1; | ||
2446 | else | ||
2447 | flashing = FALSE; | ||
2448 | |||
2449 | /* | ||
2450 | * Find errors. For this we use _part_ of the information from a | ||
2451 | * currently active drag: we transform dsx,dsy but not anything | ||
2452 | * else. (This seems to strike a good compromise between having | ||
2453 | * the error highlights respond instantly to single clicks, but | ||
2454 | * not giving constant feedback during a right-drag.) | ||
2455 | */ | ||
2456 | if (ui && ui->drag_button >= 0) { | ||
2457 | tmpgrid = snewn(w*h, char); | ||
2458 | memcpy(tmpgrid, state->grid, w*h); | ||
2459 | tmpgrid[ui->dsy * w + ui->dsx] = | ||
2460 | drag_xform(ui, ui->dsx, ui->dsy, tmpgrid[ui->dsy * w + ui->dsx]); | ||
2461 | errors = find_errors(state, tmpgrid); | ||
2462 | sfree(tmpgrid); | ||
2463 | } else { | ||
2464 | errors = find_errors(state, state->grid); | ||
2465 | } | ||
2466 | |||
2467 | /* | ||
2468 | * Draw the grid. | ||
2469 | */ | ||
2470 | for (y = 0; y < h; y++) { | ||
2471 | for (x = 0; x < w; x++) { | ||
2472 | int v = state->grid[y*w+x]; | ||
2473 | int credraw = 0; | ||
2474 | |||
2475 | /* | ||
2476 | * We deliberately do not take drag_ok into account | ||
2477 | * here, because user feedback suggests that it's | ||
2478 | * marginally nicer not to have the drag effects | ||
2479 | * flickering on and off disconcertingly. | ||
2480 | */ | ||
2481 | if (ui && ui->drag_button >= 0) | ||
2482 | v = drag_xform(ui, x, y, v); | ||
2483 | |||
2484 | if (flashing && (v == TREE || v == TENT)) | ||
2485 | v = NONTENT; | ||
2486 | |||
2487 | if (cmoved) { | ||
2488 | if ((x == cx && y == cy) || | ||
2489 | (x == ds->cx && y == ds->cy)) credraw = 1; | ||
2490 | } | ||
2491 | |||
2492 | v |= errors[y*w+x]; | ||
2493 | |||
2494 | if (printing || ds->drawn[y*w+x] != v || credraw) { | ||
2495 | draw_tile(dr, ds, x, y, v, (x == cx && y == cy), printing); | ||
2496 | if (!printing) | ||
2497 | ds->drawn[y*w+x] = v; | ||
2498 | } | ||
2499 | } | ||
2500 | } | ||
2501 | |||
2502 | /* | ||
2503 | * Draw (or redraw, if their error-highlighted state has | ||
2504 | * changed) the numbers. | ||
2505 | */ | ||
2506 | for (x = 0; x < w; x++) { | ||
2507 | if (printing || ds->numbersdrawn[x] != errors[w*h+x]) { | ||
2508 | char buf[80]; | ||
2509 | draw_rect(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1, | ||
2510 | COL_BACKGROUND); | ||
2511 | sprintf(buf, "%d", state->numbers->numbers[x]); | ||
2512 | draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1), | ||
2513 | FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL, | ||
2514 | (errors[w*h+x] ? COL_ERROR : COL_GRID), buf); | ||
2515 | draw_update(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1); | ||
2516 | if (!printing) | ||
2517 | ds->numbersdrawn[x] = errors[w*h+x]; | ||
2518 | } | ||
2519 | } | ||
2520 | for (y = 0; y < h; y++) { | ||
2521 | if (printing || ds->numbersdrawn[w+y] != errors[w*h+w+y]) { | ||
2522 | char buf[80]; | ||
2523 | draw_rect(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE, | ||
2524 | COL_BACKGROUND); | ||
2525 | sprintf(buf, "%d", state->numbers->numbers[w+y]); | ||
2526 | draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2, | ||
2527 | FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE, | ||
2528 | (errors[w*h+w+y] ? COL_ERROR : COL_GRID), buf); | ||
2529 | draw_update(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE); | ||
2530 | if (!printing) | ||
2531 | ds->numbersdrawn[w+y] = errors[w*h+w+y]; | ||
2532 | } | ||
2533 | } | ||
2534 | |||
2535 | if (cmoved) { | ||
2536 | ds->cx = cx; | ||
2537 | ds->cy = cy; | ||
2538 | } | ||
2539 | |||
2540 | sfree(errors); | ||
2541 | } | ||
2542 | |||
2543 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2544 | const game_state *oldstate, const game_state *state, | ||
2545 | int dir, const game_ui *ui, | ||
2546 | float animtime, float flashtime) | ||
2547 | { | ||
2548 | int_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, FALSE); | ||
2549 | } | ||
2550 | |||
2551 | static float game_anim_length(const game_state *oldstate, | ||
2552 | const game_state *newstate, int dir, game_ui *ui) | ||
2553 | { | ||
2554 | return 0.0F; | ||
2555 | } | ||
2556 | |||
2557 | static float game_flash_length(const game_state *oldstate, | ||
2558 | const game_state *newstate, int dir, game_ui *ui) | ||
2559 | { | ||
2560 | if (!oldstate->completed && newstate->completed && | ||
2561 | !oldstate->used_solve && !newstate->used_solve) | ||
2562 | return FLASH_TIME; | ||
2563 | |||
2564 | return 0.0F; | ||
2565 | } | ||
2566 | |||
2567 | static int game_status(const game_state *state) | ||
2568 | { | ||
2569 | return state->completed ? +1 : 0; | ||
2570 | } | ||
2571 | |||
2572 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
2573 | { | ||
2574 | return TRUE; | ||
2575 | } | ||
2576 | |||
2577 | static void game_print_size(const game_params *params, float *x, float *y) | ||
2578 | { | ||
2579 | int pw, ph; | ||
2580 | |||
2581 | /* | ||
2582 | * I'll use 6mm squares by default. | ||
2583 | */ | ||
2584 | game_compute_size(params, 600, &pw, &ph); | ||
2585 | *x = pw / 100.0F; | ||
2586 | *y = ph / 100.0F; | ||
2587 | } | ||
2588 | |||
2589 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
2590 | { | ||
2591 | int c; | ||
2592 | |||
2593 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2594 | game_drawstate ads, *ds = &ads; | ||
2595 | game_set_size(dr, ds, NULL, tilesize); | ||
2596 | |||
2597 | c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND); | ||
2598 | c = print_mono_colour(dr, 0); assert(c == COL_GRID); | ||
2599 | c = print_mono_colour(dr, 1); assert(c == COL_GRASS); | ||
2600 | c = print_mono_colour(dr, 0); assert(c == COL_TREETRUNK); | ||
2601 | c = print_mono_colour(dr, 0); assert(c == COL_TREELEAF); | ||
2602 | c = print_mono_colour(dr, 0); assert(c == COL_TENT); | ||
2603 | |||
2604 | int_redraw(dr, ds, NULL, state, +1, NULL, 0.0F, 0.0F, TRUE); | ||
2605 | } | ||
2606 | |||
2607 | #ifdef COMBINED | ||
2608 | #define thegame tents | ||
2609 | #endif | ||
2610 | |||
2611 | const struct game thegame = { | ||
2612 | "Tents", "games.tents", "tents", | ||
2613 | default_params, | ||
2614 | game_fetch_preset, NULL, | ||
2615 | decode_params, | ||
2616 | encode_params, | ||
2617 | free_params, | ||
2618 | dup_params, | ||
2619 | TRUE, game_configure, custom_params, | ||
2620 | validate_params, | ||
2621 | new_game_desc, | ||
2622 | validate_desc, | ||
2623 | new_game, | ||
2624 | dup_game, | ||
2625 | free_game, | ||
2626 | TRUE, solve_game, | ||
2627 | TRUE, game_can_format_as_text_now, game_text_format, | ||
2628 | new_ui, | ||
2629 | free_ui, | ||
2630 | encode_ui, | ||
2631 | decode_ui, | ||
2632 | game_changed_state, | ||
2633 | interpret_move, | ||
2634 | execute_move, | ||
2635 | PREFERRED_TILESIZE, game_compute_size, game_set_size, | ||
2636 | game_colours, | ||
2637 | game_new_drawstate, | ||
2638 | game_free_drawstate, | ||
2639 | game_redraw, | ||
2640 | game_anim_length, | ||
2641 | game_flash_length, | ||
2642 | game_status, | ||
2643 | TRUE, FALSE, game_print_size, game_print, | ||
2644 | FALSE, /* wants_statusbar */ | ||
2645 | FALSE, game_timing_state, | ||
2646 | REQUIRE_RBUTTON, /* flags */ | ||
2647 | }; | ||
2648 | |||
2649 | #ifdef STANDALONE_SOLVER | ||
2650 | |||
2651 | #include <stdarg.h> | ||
2652 | |||
2653 | int main(int argc, char **argv) | ||
2654 | { | ||
2655 | game_params *p; | ||
2656 | game_state *s, *s2; | ||
2657 | char *id = NULL, *desc, *err; | ||
2658 | int grade = FALSE; | ||
2659 | int ret, diff, really_verbose = FALSE; | ||
2660 | struct solver_scratch *sc; | ||
2661 | |||
2662 | while (--argc > 0) { | ||
2663 | char *p = *++argv; | ||
2664 | if (!strcmp(p, "-v")) { | ||
2665 | really_verbose = TRUE; | ||
2666 | } else if (!strcmp(p, "-g")) { | ||
2667 | grade = TRUE; | ||
2668 | } else if (*p == '-') { | ||
2669 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2670 | return 1; | ||
2671 | } else { | ||
2672 | id = p; | ||
2673 | } | ||
2674 | } | ||
2675 | |||
2676 | if (!id) { | ||
2677 | fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]); | ||
2678 | return 1; | ||
2679 | } | ||
2680 | |||
2681 | desc = strchr(id, ':'); | ||
2682 | if (!desc) { | ||
2683 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
2684 | return 1; | ||
2685 | } | ||
2686 | *desc++ = '\0'; | ||
2687 | |||
2688 | p = default_params(); | ||
2689 | decode_params(p, id); | ||
2690 | err = validate_desc(p, desc); | ||
2691 | if (err) { | ||
2692 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
2693 | return 1; | ||
2694 | } | ||
2695 | s = new_game(NULL, p, desc); | ||
2696 | s2 = new_game(NULL, p, desc); | ||
2697 | |||
2698 | sc = new_scratch(p->w, p->h); | ||
2699 | |||
2700 | /* | ||
2701 | * When solving an Easy puzzle, we don't want to bother the | ||
2702 | * user with Hard-level deductions. For this reason, we grade | ||
2703 | * the puzzle internally before doing anything else. | ||
2704 | */ | ||
2705 | ret = -1; /* placate optimiser */ | ||
2706 | for (diff = 0; diff < DIFFCOUNT; diff++) { | ||
2707 | ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers, | ||
2708 | s2->grid, sc, diff); | ||
2709 | if (ret < 2) | ||
2710 | break; | ||
2711 | } | ||
2712 | |||
2713 | if (diff == DIFFCOUNT) { | ||
2714 | if (grade) | ||
2715 | printf("Difficulty rating: too hard to solve internally\n"); | ||
2716 | else | ||
2717 | printf("Unable to find a unique solution\n"); | ||
2718 | } else { | ||
2719 | if (grade) { | ||
2720 | if (ret == 0) | ||
2721 | printf("Difficulty rating: impossible (no solution exists)\n"); | ||
2722 | else if (ret == 1) | ||
2723 | printf("Difficulty rating: %s\n", tents_diffnames[diff]); | ||
2724 | } else { | ||
2725 | verbose = really_verbose; | ||
2726 | ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers, | ||
2727 | s2->grid, sc, diff); | ||
2728 | if (ret == 0) | ||
2729 | printf("Puzzle is inconsistent\n"); | ||
2730 | else | ||
2731 | fputs(game_text_format(s2), stdout); | ||
2732 | } | ||
2733 | } | ||
2734 | |||
2735 | return 0; | ||
2736 | } | ||
2737 | |||
2738 | #endif | ||
2739 | |||
2740 | /* vim: set shiftwidth=4 tabstop=8: */ | ||