2 * tents.c: Puzzle involving placing tents next to trees subject to
3 * some confusing conditions.
7 * - it might be nice to make setter-provided tent/nontent clues
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
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?
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.
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.
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.
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?
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
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
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
92 * Algorithmic implications
93 * ------------------------
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.
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.
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
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.
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.
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. []
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.
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
195 * In other words, given any bipartite graph with a unique perfect
196 * matching, we can find that matching by the following extremely
199 * - Find a left-side vertex which is only connected to one
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.
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).
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
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
230 #if defined STANDALONE_SOLVER
231 #define SOLVER_DIAGNOSTICS
233 #elif defined SOLVER_DIAGNOSTICS
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.
241 #define DIFFLIST(A) \
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)
266 enum { BLANK, TREE, TENT, NONTENT, MAGIC };
281 struct numbers *numbers;
282 int completed, used_solve;
285 static game_params *default_params(void)
287 game_params *ret = snew(game_params);
290 ret->diff = DIFF_EASY;
295 static const struct game_params tents_presets[] = {
299 {10, 10, DIFF_TRICKY},
301 {15, 15, DIFF_TRICKY},
304 static int game_fetch_preset(int i, char **name, game_params **params)
309 if (i < 0 || i >= lenof(tents_presets))
312 ret = snew(game_params);
313 *ret = tents_presets[i];
315 sprintf(str, "%dx%d %s", ret->w, ret->h, tents_diffnames[ret->diff]);
322 static void free_params(game_params *params)
327 static game_params *dup_params(const game_params *params)
329 game_params *ret = snew(game_params);
330 *ret = *params; /* structure copy */
334 static void decode_params(game_params *params, char const *string)
336 params->w = params->h = atoi(string);
337 while (*string && isdigit((unsigned char)*string)) string++;
338 if (*string == 'x') {
340 params->h = atoi(string);
341 while (*string && isdigit((unsigned char)*string)) string++;
343 if (*string == 'd') {
346 for (i = 0; i < DIFFCOUNT; i++)
347 if (*string == tents_diffchars[i])
349 if (*string) string++;
353 static char *encode_params(const game_params *params, int full)
357 sprintf(buf, "%dx%d", params->w, params->h);
359 sprintf(buf + strlen(buf), "d%c",
360 tents_diffchars[params->diff]);
364 static config_item *game_configure(const game_params *params)
369 ret = snewn(4, config_item);
371 ret[0].name = "Width";
372 ret[0].type = C_STRING;
373 sprintf(buf, "%d", params->w);
374 ret[0].u.string.sval = dupstr(buf);
376 ret[1].name = "Height";
377 ret[1].type = C_STRING;
378 sprintf(buf, "%d", params->h);
379 ret[1].u.string.sval = dupstr(buf);
381 ret[2].name = "Difficulty";
382 ret[2].type = C_CHOICES;
383 ret[2].u.choices.choicenames = DIFFCONFIG;
384 ret[2].u.choices.selected = params->diff;
392 static game_params *custom_params(const config_item *cfg)
394 game_params *ret = snew(game_params);
396 ret->w = atoi(cfg[0].u.string.sval);
397 ret->h = atoi(cfg[1].u.string.sval);
398 ret->diff = cfg[2].u.choices.selected;
403 static const char *validate_params(const game_params *params, int full)
406 * Generating anything under 4x4 runs into trouble of one kind
409 if (params->w < 4 || params->h < 4)
410 return "Width and height must both be at least four";
415 * Scratch space for solver.
417 enum { N, U, L, R, D, MAXDIR }; /* link directions */
418 #define dx(d) ( ((d)==R) - ((d)==L) )
419 #define dy(d) ( ((d)==D) - ((d)==U) )
420 #define F(d) ( U + D - (d) )
421 struct solver_scratch {
422 char *links; /* mapping between trees and tents */
424 char *place, *mrows, *trows;
427 static struct solver_scratch *new_scratch(int w, int h)
429 struct solver_scratch *ret = snew(struct solver_scratch);
431 ret->links = snewn(w*h, char);
432 ret->locs = snewn(max(w, h), int);
433 ret->place = snewn(max(w, h), char);
434 ret->mrows = snewn(3 * max(w, h), char);
435 ret->trows = snewn(3 * max(w, h), char);
440 static void free_scratch(struct solver_scratch *sc)
451 * Solver. Returns 0 for impossibility, 1 for success, 2 for
452 * ambiguity or failure to converge.
454 static int tents_solve(int w, int h, const char *grid, int *numbers,
455 char *soln, struct solver_scratch *sc, int diff)
458 char *mrow, *trow, *trow1, *trow2;
461 * Set up solver data.
463 memset(sc->links, N, w*h);
466 * Set up solution array.
468 memcpy(soln, grid, w*h);
474 int done_something = FALSE;
477 * Any tent which has only one unattached tree adjacent to
478 * it can be tied to that tree.
480 for (y = 0; y < h; y++)
481 for (x = 0; x < w; x++)
482 if (soln[y*w+x] == TENT && !sc->links[y*w+x]) {
485 for (d = 1; d < MAXDIR; d++) {
486 int x2 = x + dx(d), y2 = y + dy(d);
487 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
488 soln[y2*w+x2] == TREE &&
489 !sc->links[y2*w+x2]) {
491 break; /* found more than one */
497 if (d == MAXDIR && linkd == 0) {
498 #ifdef SOLVER_DIAGNOSTICS
500 printf("tent at %d,%d cannot link to anything\n",
503 return 0; /* no solution exists */
504 } else if (d == MAXDIR) {
505 int x2 = x + dx(linkd), y2 = y + dy(linkd);
507 #ifdef SOLVER_DIAGNOSTICS
509 printf("tent at %d,%d can only link to tree at"
510 " %d,%d\n", x, y, x2, y2);
513 sc->links[y*w+x] = linkd;
514 sc->links[y2*w+x2] = F(linkd);
515 done_something = TRUE;
522 break; /* don't do anything else! */
525 * Mark a blank square as NONTENT if it is not orthogonally
526 * adjacent to any unmatched tree.
528 for (y = 0; y < h; y++)
529 for (x = 0; x < w; x++)
530 if (soln[y*w+x] == BLANK) {
531 int can_be_tent = FALSE;
533 for (d = 1; d < MAXDIR; d++) {
534 int x2 = x + dx(d), y2 = y + dy(d);
535 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
536 soln[y2*w+x2] == TREE &&
542 #ifdef SOLVER_DIAGNOSTICS
544 printf("%d,%d cannot be a tent (no adjacent"
545 " unmatched tree)\n", x, y);
547 soln[y*w+x] = NONTENT;
548 done_something = TRUE;
556 * Mark a blank square as NONTENT if it is (perhaps
557 * diagonally) adjacent to any other tent.
559 for (y = 0; y < h; y++)
560 for (x = 0; x < w; x++)
561 if (soln[y*w+x] == BLANK) {
562 int dx, dy, imposs = FALSE;
564 for (dy = -1; dy <= +1; dy++)
565 for (dx = -1; dx <= +1; dx++)
567 int x2 = x + dx, y2 = y + dy;
568 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
569 soln[y2*w+x2] == TENT)
574 #ifdef SOLVER_DIAGNOSTICS
576 printf("%d,%d cannot be a tent (adjacent tent)\n",
579 soln[y*w+x] = NONTENT;
580 done_something = TRUE;
588 * Any tree which has exactly one {unattached tent, BLANK}
589 * adjacent to it must have its tent in that square.
591 for (y = 0; y < h; y++)
592 for (x = 0; x < w; x++)
593 if (soln[y*w+x] == TREE && !sc->links[y*w+x]) {
594 int linkd = 0, linkd2 = 0, nd = 0;
596 for (d = 1; d < MAXDIR; d++) {
597 int x2 = x + dx(d), y2 = y + dy(d);
598 if (!(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h))
600 if (soln[y2*w+x2] == BLANK ||
601 (soln[y2*w+x2] == TENT && !sc->links[y2*w+x2])) {
611 #ifdef SOLVER_DIAGNOSTICS
613 printf("tree at %d,%d cannot link to anything\n",
616 return 0; /* no solution exists */
617 } else if (nd == 1) {
618 int x2 = x + dx(linkd), y2 = y + dy(linkd);
620 #ifdef SOLVER_DIAGNOSTICS
622 printf("tree at %d,%d can only link to tent at"
623 " %d,%d\n", x, y, x2, y2);
625 soln[y2*w+x2] = TENT;
626 sc->links[y*w+x] = linkd;
627 sc->links[y2*w+x2] = F(linkd);
628 done_something = TRUE;
629 } else if (nd == 2 && (!dx(linkd) != !dx(linkd2)) &&
630 diff >= DIFF_TRICKY) {
632 * If there are two possible places where
633 * this tree's tent can go, and they are
634 * diagonally separated rather than being
635 * on opposite sides of the tree, then the
636 * square (other than the tree square)
637 * which is adjacent to both of them must
640 int x2 = x + dx(linkd) + dx(linkd2);
641 int y2 = y + dy(linkd) + dy(linkd2);
642 assert(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h);
643 if (soln[y2*w+x2] == BLANK) {
644 #ifdef SOLVER_DIAGNOSTICS
646 printf("possible tent locations for tree at"
647 " %d,%d rule out tent at %d,%d\n",
650 soln[y2*w+x2] = NONTENT;
651 done_something = TRUE;
660 * If localised deductions about the trees and tents
661 * themselves haven't helped us, it's time to resort to the
662 * numbers round the grid edge. For each row and column, we
663 * go through all possible combinations of locations for
664 * the unplaced tents, rule out any which have adjacent
665 * tents, and spot any square which is given the same state
666 * by all remaining combinations.
668 for (i = 0; i < w+h; i++) {
669 int start, step, len, start1, start2, n, k;
673 * This is the number for a column.
688 * This is the number for a row.
703 if (diff < DIFF_TRICKY) {
705 * In Easy mode, we don't look at the effect of one
706 * row on the next (i.e. ruling out a square if all
707 * possibilities for an adjacent row place a tent
710 start1 = start2 = -1;
716 * Count and store the locations of the free squares,
717 * and also count the number of tents already placed.
720 for (j = 0; j < len; j++) {
721 if (soln[start+j*step] == TENT)
722 k--; /* one fewer tent to place */
723 else if (soln[start+j*step] == BLANK)
728 continue; /* nothing left to do here */
731 * Now we know we're placing k tents in n squares. Set
732 * up the first possibility.
734 for (j = 0; j < n; j++)
735 sc->place[j] = (j < k ? TENT : NONTENT);
738 * We're aiming to find squares in this row which are
739 * invariant over all valid possibilities. Thus, we
740 * maintain the current state of that invariance. We
741 * start everything off at MAGIC to indicate that it
742 * hasn't been set up yet.
746 trow1 = sc->trows + len;
747 trow2 = sc->trows + 2*len;
748 memset(mrow, MAGIC, 3*len);
751 * And iterate over all possibilities.
757 * See if this possibility is valid. The only way
758 * it can fail to be valid is if it contains two
759 * adjacent tents. (Other forms of invalidity, such
760 * as containing a tent adjacent to one already
761 * placed, will have been dealt with already by
762 * other parts of the solver.)
765 for (j = 0; j+1 < n; j++)
766 if (sc->place[j] == TENT &&
767 sc->place[j+1] == TENT &&
768 sc->locs[j+1] == sc->locs[j]+1) {
775 * Merge this valid combination into mrow.
777 memset(trow, MAGIC, len);
778 memset(trow+len, BLANK, 2*len);
779 for (j = 0; j < n; j++) {
780 trow[sc->locs[j]] = sc->place[j];
781 if (sc->place[j] == TENT) {
783 for (jj = sc->locs[j]-1; jj <= sc->locs[j]+1; jj++)
784 if (jj >= 0 && jj < len)
785 trow1[jj] = trow2[jj] = NONTENT;
789 for (j = 0; j < 3*len; j++) {
790 if (trow[j] == MAGIC)
792 if (mrow[j] == MAGIC || mrow[j] == trow[j]) {
794 * Either this is the first valid
795 * placement we've found at all, or
796 * this square's contents are
797 * consistent with every previous valid
803 * This square's contents fail to match
804 * what they were in a different
805 * combination, so we cannot deduce
806 * anything about this square.
814 * Find the next combination of k choices from n.
815 * We do this by finding the rightmost tent which
816 * can be moved one place right, doing so, and
817 * shunting all tents to the right of that as far
818 * left as they can go.
821 for (j = n-1; j > 0; j--) {
822 if (sc->place[j] == TENT)
824 if (sc->place[j] == NONTENT && sc->place[j-1] == TENT) {
825 sc->place[j-1] = NONTENT;
828 sc->place[++j] = TENT;
830 sc->place[j] = NONTENT;
835 break; /* we've finished */
839 * It's just possible that _no_ placement was valid, in
840 * which case we have an internally inconsistent
843 if (mrow[sc->locs[0]] == MAGIC)
844 return 0; /* inconsistent */
847 * Now go through mrow and see if there's anything
848 * we've deduced which wasn't already mentioned in soln.
850 for (j = 0; j < len; j++) {
853 for (whichrow = 0; whichrow < 3; whichrow++) {
854 char *mthis = mrow + whichrow * len;
855 int tstart = (whichrow == 0 ? start :
856 whichrow == 1 ? start1 : start2);
858 mthis[j] != MAGIC && mthis[j] != BLANK &&
859 soln[tstart+j*step] == BLANK) {
860 int pos = tstart+j*step;
862 #ifdef SOLVER_DIAGNOSTICS
864 printf("%s %d forces %s at %d,%d\n",
865 step==1 ? "row" : "column",
866 step==1 ? start/w : start,
867 mthis[j] == TENT ? "tent" : "non-tent",
870 soln[pos] = mthis[j];
871 done_something = TRUE;
885 * The solver has nothing further it can do. Return 1 if both
886 * soln and sc->links are completely filled in, or 2 otherwise.
888 for (y = 0; y < h; y++)
889 for (x = 0; x < w; x++) {
890 if (soln[y*w+x] == BLANK)
892 if (soln[y*w+x] != NONTENT && sc->links[y*w+x] == 0)
899 static char *new_game_desc(const game_params *params_in, random_state *rs,
900 char **aux, int interactive)
902 game_params params_copy = *params_in; /* structure copy */
903 game_params *params = ¶ms_copy;
904 int w = params->w, h = params->h;
905 int ntrees = w * h / 5;
906 char *grid = snewn(w*h, char);
907 char *puzzle = snewn(w*h, char);
908 int *numbers = snewn(w+h, int);
909 char *soln = snewn(w*h, char);
910 int *temp = snewn(2*w*h, int);
911 int maxedges = ntrees*4 + w*h;
912 int *edges = snewn(2*maxedges, int);
913 int *capacity = snewn(maxedges, int);
914 int *flow = snewn(maxedges, int);
915 struct solver_scratch *sc = new_scratch(w, h);
920 * Since this puzzle has many global deductions and doesn't
921 * permit limited clue sets, generating grids for this puzzle
922 * is hard enough that I see no better option than to simply
923 * generate a solution and see if it's unique and has the
924 * required difficulty. This turns out to be computationally
927 * We chose our tree count (hence also tent count) by dividing
928 * the total grid area by five above. Why five? Well, w*h/4 is
929 * the maximum number of tents you can _possibly_ fit into the
930 * grid without violating the separation criterion, and to
931 * achieve that you are constrained to a very small set of
932 * possible layouts (the obvious one with a tent at every
933 * (even,even) coordinate, and trivial variations thereon). So
934 * if we reduce the tent count a bit more, we enable more
935 * random-looking placement; 5 turns out to be a plausible
936 * figure which yields sensible puzzles. Increasing the tent
937 * count would give puzzles whose solutions were too regimented
938 * and could be solved by the use of that knowledge (and would
939 * also take longer to find a viable placement); decreasing it
940 * would make the grids emptier and more boring.
942 * Actually generating a grid is a matter of first placing the
943 * tents, and then placing the trees by the use of maxflow
944 * (finding a distinct square adjacent to every tent). We do it
945 * this way round because otherwise satisfying the tent
946 * separation condition would become onerous: most randomly
947 * chosen tent layouts do not satisfy this condition, so we'd
948 * have gone to a lot of work before finding that a candidate
949 * layout was unusable. Instead, we place the tents first and
950 * ensure they meet the separation criterion _before_ doing
951 * lots of computation; this works much better.
953 * The maxflow algorithm is not randomised, so employed naively
954 * it would give rise to grids with clear structure and
955 * directional bias. Hence, I assign the network nodes as seen
956 * by maxflow to be a _random_ permutation of the squares of
957 * the grid, so that any bias shown by maxflow towards
958 * low-numbered nodes is turned into a random bias.
960 * This generation strategy can fail at many points, including
961 * as early as tent placement (if you get a bad random order in
962 * which to greedily try the grid squares, you won't even
963 * manage to find enough mutually non-adjacent squares to put
964 * the tents in). Then it can fail if maxflow doesn't manage to
965 * find a good enough matching (i.e. the tent placements don't
966 * admit any adequate tree placements); and finally it can fail
967 * if the solver finds that the problem has the wrong
968 * difficulty (including being actually non-unique). All of
969 * these, however, are insufficiently frequent to cause
973 if (params->diff > DIFF_EASY && params->w <= 4 && params->h <= 4)
974 params->diff = DIFF_EASY; /* downgrade to prevent tight loop */
978 * Arrange the grid squares into a random order.
980 for (i = 0; i < w*h; i++)
982 shuffle(temp, w*h, sizeof(*temp), rs);
985 * The first `ntrees' entries in temp which we can get
986 * without making two tents adjacent will be the tent
989 memset(grid, BLANK, w*h);
991 for (i = 0; i < w*h && j > 0; i++) {
992 int x = temp[i] % w, y = temp[i] / w;
993 int dy, dx, ok = TRUE;
995 for (dy = -1; dy <= +1; dy++)
996 for (dx = -1; dx <= +1; dx++)
997 if (x+dx >= 0 && x+dx < w &&
998 y+dy >= 0 && y+dy < h &&
999 grid[(y+dy)*w+(x+dx)] == TENT)
1003 grid[temp[i]] = TENT;
1008 continue; /* couldn't place all the tents */
1011 * Now we build up the list of graph edges.
1014 for (i = 0; i < w*h; i++) {
1015 if (grid[temp[i]] == TENT) {
1016 for (j = 0; j < w*h; j++) {
1017 if (grid[temp[j]] != TENT) {
1018 int xi = temp[i] % w, yi = temp[i] / w;
1019 int xj = temp[j] % w, yj = temp[j] / w;
1020 if (abs(xi-xj) + abs(yi-yj) == 1) {
1021 edges[nedges*2] = i;
1022 edges[nedges*2+1] = j;
1023 capacity[nedges] = 1;
1030 * Special node w*h is the sink node; any non-tent node
1031 * has an edge going to it.
1033 edges[nedges*2] = i;
1034 edges[nedges*2+1] = w*h;
1035 capacity[nedges] = 1;
1041 * Special node w*h+1 is the source node, with an edge going to
1044 for (i = 0; i < w*h; i++) {
1045 if (grid[temp[i]] == TENT) {
1046 edges[nedges*2] = w*h+1;
1047 edges[nedges*2+1] = i;
1048 capacity[nedges] = 1;
1053 assert(nedges <= maxedges);
1056 * Now we're ready to call the maxflow algorithm to place the
1059 j = maxflow(w*h+2, w*h+1, w*h, nedges, edges, capacity, flow, NULL);
1062 continue; /* couldn't place all the trees */
1065 * We've placed the trees. Now we need to work out _where_
1066 * we've placed them, which is a matter of reading back out
1067 * from the `flow' array.
1069 for (i = 0; i < nedges; i++) {
1070 if (edges[2*i] < w*h && edges[2*i+1] < w*h && flow[i] > 0)
1071 grid[temp[edges[2*i+1]]] = TREE;
1075 * I think it looks ugly if there isn't at least one of
1076 * _something_ (tent or tree) in each row and each column
1077 * of the grid. This doesn't give any information away
1078 * since a completely empty row/column is instantly obvious
1079 * from the clues (it has no trees and a zero).
1081 for (i = 0; i < w; i++) {
1082 for (j = 0; j < h; j++) {
1083 if (grid[j*w+i] != BLANK)
1084 break; /* found something in this column */
1087 break; /* found empty column */
1090 continue; /* a column was empty */
1092 for (j = 0; j < h; j++) {
1093 for (i = 0; i < w; i++) {
1094 if (grid[j*w+i] != BLANK)
1095 break; /* found something in this row */
1098 break; /* found empty row */
1101 continue; /* a row was empty */
1104 * Now set up the numbers round the edge.
1106 for (i = 0; i < w; i++) {
1108 for (j = 0; j < h; j++)
1109 if (grid[j*w+i] == TENT)
1113 for (i = 0; i < h; i++) {
1115 for (j = 0; j < w; j++)
1116 if (grid[i*w+j] == TENT)
1122 * And now actually solve the puzzle, to see whether it's
1123 * unique and has the required difficulty.
1125 for (i = 0; i < w*h; i++)
1126 puzzle[i] = grid[i] == TREE ? TREE : BLANK;
1127 i = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff-1);
1128 j = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff);
1131 * We expect solving with difficulty params->diff to have
1132 * succeeded (otherwise the problem is too hard), and
1133 * solving with diff-1 to have failed (otherwise it's too
1136 if (i == 2 && j == 1)
1141 * That's it. Encode as a game ID.
1143 ret = snewn((w+h)*40 + ntrees + (w*h)/26 + 1, char);
1146 for (i = 0; i <= w*h; i++) {
1147 int c = (i < w*h ? grid[i] == TREE : 1);
1149 *p++ = (j == 0 ? '_' : j-1 + 'a');
1159 for (i = 0; i < w+h; i++)
1160 p += sprintf(p, ",%d", numbers[i]);
1162 ret = sresize(ret, p - ret, char);
1165 * And encode the solution as an aux_info.
1167 *aux = snewn(ntrees * 40, char);
1170 for (i = 0; i < w*h; i++)
1171 if (grid[i] == TENT)
1172 p += sprintf(p, ";T%d,%d", i%w, i/w);
1174 *aux = sresize(*aux, p - *aux, char);
1189 static const char *validate_desc(const game_params *params, const char *desc)
1191 int w = params->w, h = params->h;
1195 while (*desc && *desc != ',') {
1198 else if (*desc >= 'a' && *desc < 'z')
1199 area += *desc - 'a' + 2;
1200 else if (*desc == 'z')
1202 else if (*desc == '!' || *desc == '-')
1205 return "Invalid character in grid specification";
1209 if (area < w * h + 1)
1210 return "Not enough data to fill grid";
1211 else if (area > w * h + 1)
1212 return "Too much data to fill grid";
1214 for (i = 0; i < w+h; i++) {
1216 return "Not enough numbers given after grid specification";
1217 else if (*desc != ',')
1218 return "Invalid character in number list";
1220 while (*desc && isdigit((unsigned char)*desc)) desc++;
1224 return "Unexpected additional data at end of game description";
1228 static game_state *new_game(midend *me, const game_params *params,
1231 int w = params->w, h = params->h;
1232 game_state *state = snew(game_state);
1235 state->p = *params; /* structure copy */
1236 state->grid = snewn(w*h, char);
1237 state->numbers = snew(struct numbers);
1238 state->numbers->refcount = 1;
1239 state->numbers->numbers = snewn(w+h, int);
1240 state->completed = state->used_solve = FALSE;
1243 memset(state->grid, BLANK, w*h);
1252 else if (*desc >= 'a' && *desc < 'z')
1253 run = *desc - ('a'-1);
1254 else if (*desc == 'z') {
1258 assert(*desc == '!' || *desc == '-');
1260 type = (*desc == '!' ? TENT : NONTENT);
1266 assert(i >= 0 && i <= w*h);
1268 assert(type == TREE);
1272 state->grid[i++] = type;
1276 for (i = 0; i < w+h; i++) {
1277 assert(*desc == ',');
1279 state->numbers->numbers[i] = atoi(desc);
1280 while (*desc && isdigit((unsigned char)*desc)) desc++;
1288 static game_state *dup_game(const game_state *state)
1290 int w = state->p.w, h = state->p.h;
1291 game_state *ret = snew(game_state);
1293 ret->p = state->p; /* structure copy */
1294 ret->grid = snewn(w*h, char);
1295 memcpy(ret->grid, state->grid, w*h);
1296 ret->numbers = state->numbers;
1297 state->numbers->refcount++;
1298 ret->completed = state->completed;
1299 ret->used_solve = state->used_solve;
1304 static void free_game(game_state *state)
1306 if (--state->numbers->refcount <= 0) {
1307 sfree(state->numbers->numbers);
1308 sfree(state->numbers);
1314 static char *solve_game(const game_state *state, const game_state *currstate,
1315 const char *aux, const char **error)
1317 int w = state->p.w, h = state->p.h;
1321 * If we already have the solution, save ourselves some
1326 struct solver_scratch *sc = new_scratch(w, h);
1332 soln = snewn(w*h, char);
1333 ret = tents_solve(w, h, state->grid, state->numbers->numbers,
1334 soln, sc, DIFFCOUNT-1);
1339 *error = "This puzzle is not self-consistent";
1341 *error = "Unable to find a unique solution for this puzzle";
1346 * Construct a move string which turns the current state
1347 * into the solved state.
1349 move = snewn(w*h * 40, char);
1352 for (i = 0; i < w*h; i++)
1353 if (soln[i] == TENT)
1354 p += sprintf(p, ";T%d,%d", i%w, i/w);
1356 move = sresize(move, p - move, char);
1364 static int game_can_format_as_text_now(const game_params *params)
1366 return params->w <= 1998 && params->h <= 1998; /* 999 tents */
1369 static char *game_text_format(const game_state *state)
1371 int w = state->p.w, h = state->p.h, r, c;
1372 int cw = 4, ch = 2, gw = (w+1)*cw + 2, gh = (h+1)*ch + 1, len = gw * gh;
1373 char *board = snewn(len + 1, char);
1375 sprintf(board, "%*s\n", len - 2, "");
1376 for (r = 0; r <= h; ++r) {
1377 for (c = 0; c <= w; ++c) {
1378 int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
1379 int i = r*w + c, n = 1000;
1381 if (r == h && c == w) /* NOP */;
1382 else if (c == w) n = state->numbers->numbers[w + r];
1383 else if (r == h) n = state->numbers->numbers[c];
1384 else switch (state->grid[i]) {
1385 case BLANK: board[center] = '.'; break;
1386 case TREE: board[center] = 'T'; break;
1387 case TENT: memcpy(board + center - 1, "//\\", 3); break;
1388 case NONTENT: break;
1389 default: memcpy(board + center - 1, "wtf", 3);
1393 board[center] = '0' + n % 10;
1394 if (n >= 10) board[center - 1] = '0' + n / 10;
1395 } else if (n < 1000) {
1396 board[center + 1] = '0' + n % 10;
1397 board[center] = '0' + n / 10 % 10;
1398 board[center - 1] = '0' + n / 100;
1402 memset(board + cell + 1, '-', cw - 1);
1403 for (i = 1; i < ch; ++i) board[cell + i*gw] = '|';
1406 for (c = 0; c < ch; ++c) {
1407 board[(r*ch+c)*gw + gw - 2] =
1408 c == 0 ? '+' : r < h ? '|' : ' ';
1409 board[(r*ch+c)*gw + gw - 1] = '\n';
1413 memset(board + len - gw, '-', gw - 2 - cw);
1414 for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+';
1420 int dsx, dsy; /* coords of drag start */
1421 int dex, dey; /* coords of drag end */
1422 int drag_button; /* -1 for none, or a button code */
1423 int drag_ok; /* dragged off the window, to cancel */
1425 int cx, cy, cdisp; /* cursor position, and ?display. */
1428 static game_ui *new_ui(const game_state *state)
1430 game_ui *ui = snew(game_ui);
1431 ui->dsx = ui->dsy = -1;
1432 ui->dex = ui->dey = -1;
1433 ui->drag_button = -1;
1434 ui->drag_ok = FALSE;
1435 ui->cx = ui->cy = ui->cdisp = 0;
1439 static void free_ui(game_ui *ui)
1444 static char *encode_ui(const game_ui *ui)
1449 static void decode_ui(game_ui *ui, const char *encoding)
1453 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1454 const game_state *newstate)
1458 struct game_drawstate {
1462 int *drawn, *numbersdrawn;
1463 int cx, cy; /* last-drawn cursor pos, or (-1,-1) if absent. */
1466 #define PREFERRED_TILESIZE 32
1467 #define TILESIZE (ds->tilesize)
1468 #define TLBORDER (TILESIZE/2)
1469 #define BRBORDER (TILESIZE*3/2)
1470 #define COORD(x) ( (x) * TILESIZE + TLBORDER )
1471 #define FROMCOORD(x) ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 )
1473 #define FLASH_TIME 0.30F
1475 static int drag_xform(const game_ui *ui, int x, int y, int v)
1477 int xmin, ymin, xmax, ymax;
1479 xmin = min(ui->dsx, ui->dex);
1480 xmax = max(ui->dsx, ui->dex);
1481 ymin = min(ui->dsy, ui->dey);
1482 ymax = max(ui->dsy, ui->dey);
1484 #ifndef STYLUS_BASED
1486 * Left-dragging has no effect, so we treat a left-drag as a
1487 * single click on dsx,dsy.
1489 if (ui->drag_button == LEFT_BUTTON) {
1490 xmin = xmax = ui->dsx;
1491 ymin = ymax = ui->dsy;
1495 if (x < xmin || x > xmax || y < ymin || y > ymax)
1496 return v; /* no change outside drag area */
1499 return v; /* trees are inviolate always */
1501 if (xmin == xmax && ymin == ymax) {
1503 * Results of a simple click. Left button sets blanks to
1504 * tents; right button sets blanks to non-tents; either
1505 * button clears a non-blank square.
1506 * If stylus-based however, it loops instead.
1508 if (ui->drag_button == LEFT_BUTTON)
1510 v = (v == BLANK ? TENT : (v == TENT ? NONTENT : BLANK));
1512 v = (v == BLANK ? NONTENT : (v == NONTENT ? TENT : BLANK));
1514 v = (v == BLANK ? TENT : BLANK);
1516 v = (v == BLANK ? NONTENT : BLANK);
1520 * Results of a drag. Left-dragging has no effect.
1521 * Right-dragging sets all blank squares to non-tents and
1522 * has no effect on anything else.
1524 if (ui->drag_button == RIGHT_BUTTON)
1525 v = (v == BLANK ? NONTENT : v);
1528 v = (v == BLANK ? NONTENT : v);
1537 static char *interpret_move(const game_state *state, game_ui *ui,
1538 const game_drawstate *ds,
1539 int x, int y, int button)
1541 int w = state->p.w, h = state->p.h;
1543 int shift = button & MOD_SHFT, control = button & MOD_CTRL;
1545 button &= ~MOD_MASK;
1547 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1550 if (x < 0 || y < 0 || x >= w || y >= h)
1553 ui->drag_button = button;
1554 ui->dsx = ui->dex = x;
1555 ui->dsy = ui->dey = y;
1561 if ((IS_MOUSE_DRAG(button) || IS_MOUSE_RELEASE(button)) &&
1562 ui->drag_button > 0) {
1563 int xmin, ymin, xmax, ymax;
1566 int buflen, bufsize, tmplen;
1570 if (x < 0 || y < 0 || x >= w || y >= h) {
1571 ui->drag_ok = FALSE;
1574 * Drags are limited to one row or column. Hence, we
1575 * work out which coordinate is closer to the drag
1576 * start, and move it _to_ the drag start.
1578 if (abs(x - ui->dsx) < abs(y - ui->dsy))
1589 if (IS_MOUSE_DRAG(button))
1593 * The drag has been released. Enact it.
1596 ui->drag_button = -1;
1597 return UI_UPDATE; /* drag was just cancelled */
1600 xmin = min(ui->dsx, ui->dex);
1601 xmax = max(ui->dsx, ui->dex);
1602 ymin = min(ui->dsy, ui->dey);
1603 ymax = max(ui->dsy, ui->dey);
1604 assert(0 <= xmin && xmin <= xmax && xmax < w);
1605 assert(0 <= ymin && ymin <= ymax && ymax < h);
1609 buf = snewn(bufsize, char);
1611 for (y = ymin; y <= ymax; y++)
1612 for (x = xmin; x <= xmax; x++) {
1613 int v = drag_xform(ui, x, y, state->grid[y*w+x]);
1614 if (state->grid[y*w+x] != v) {
1615 tmplen = sprintf(tmpbuf, "%s%c%d,%d", sep,
1616 (int)(v == BLANK ? 'B' :
1617 v == TENT ? 'T' : 'N'),
1621 if (buflen + tmplen >= bufsize) {
1622 bufsize = buflen + tmplen + 256;
1623 buf = sresize(buf, bufsize, char);
1626 strcpy(buf+buflen, tmpbuf);
1631 ui->drag_button = -1; /* drag is terminated */
1635 return UI_UPDATE; /* drag was terminated */
1642 if (IS_CURSOR_MOVE(button)) {
1644 if (shift || control) {
1645 int len = 0, i, indices[2];
1646 indices[0] = ui->cx + w * ui->cy;
1647 move_cursor(button, &ui->cx, &ui->cy, w, h, 0);
1648 indices[1] = ui->cx + w * ui->cy;
1650 /* NONTENTify all unique traversed eligible squares */
1651 for (i = 0; i <= (indices[0] != indices[1]); ++i)
1652 if (state->grid[indices[i]] == BLANK ||
1653 (control && state->grid[indices[i]] == TENT)) {
1654 len += sprintf(tmpbuf + len, "%sN%d,%d", len ? ";" : "",
1655 indices[i] % w, indices[i] / w);
1656 assert(len < lenof(tmpbuf));
1660 if (len) return dupstr(tmpbuf);
1662 move_cursor(button, &ui->cx, &ui->cy, w, h, 0);
1667 int v = state->grid[ui->cy*w+ui->cx];
1670 #ifdef SINGLE_CURSOR_SELECT
1671 if (button == CURSOR_SELECT)
1672 /* SELECT cycles T, N, B */
1673 rep = v == BLANK ? 'T' : v == TENT ? 'N' : 'B';
1675 if (button == CURSOR_SELECT)
1676 rep = v == BLANK ? 'T' : 'B';
1677 else if (button == CURSOR_SELECT2)
1678 rep = v == BLANK ? 'N' : 'B';
1679 else if (button == 'T' || button == 'N' || button == 'B')
1685 sprintf(tmpbuf, "%c%d,%d", (int)rep, ui->cx, ui->cy);
1686 return dupstr(tmpbuf);
1688 } else if (IS_CURSOR_SELECT(button)) {
1696 static game_state *execute_move(const game_state *state, const char *move)
1698 int w = state->p.w, h = state->p.h;
1700 int x, y, m, n, i, j;
1701 game_state *ret = dup_game(state);
1707 ret->used_solve = TRUE;
1709 * Set all non-tree squares to NONTENT. The rest of the
1710 * solve move will fill the tents in over the top.
1712 for (i = 0; i < w*h; i++)
1713 if (ret->grid[i] != TREE)
1714 ret->grid[i] = NONTENT;
1716 } else if (c == 'B' || c == 'T' || c == 'N') {
1718 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1719 x < 0 || y < 0 || x >= w || y >= h) {
1723 if (ret->grid[y*w+x] == TREE) {
1727 ret->grid[y*w+x] = (c == 'B' ? BLANK : c == 'T' ? TENT : NONTENT);
1742 * Check for completion.
1744 for (i = n = m = 0; i < w*h; i++) {
1745 if (ret->grid[i] == TENT)
1747 else if (ret->grid[i] == TREE)
1751 int nedges, maxedges, *edges, *capacity, *flow;
1754 * We have the right number of tents, which is a
1755 * precondition for the game being complete. Now check that
1756 * the numbers add up.
1758 for (i = 0; i < w; i++) {
1760 for (j = 0; j < h; j++)
1761 if (ret->grid[j*w+i] == TENT)
1763 if (ret->numbers->numbers[i] != n)
1764 goto completion_check_done;
1766 for (i = 0; i < h; i++) {
1768 for (j = 0; j < w; j++)
1769 if (ret->grid[i*w+j] == TENT)
1771 if (ret->numbers->numbers[w+i] != n)
1772 goto completion_check_done;
1775 * Also, check that no two tents are adjacent.
1777 for (y = 0; y < h; y++)
1778 for (x = 0; x < w; x++) {
1780 ret->grid[y*w+x] == TENT && ret->grid[y*w+x+1] == TENT)
1781 goto completion_check_done;
1783 ret->grid[y*w+x] == TENT && ret->grid[(y+1)*w+x] == TENT)
1784 goto completion_check_done;
1785 if (x+1 < w && y+1 < h) {
1786 if (ret->grid[y*w+x] == TENT &&
1787 ret->grid[(y+1)*w+(x+1)] == TENT)
1788 goto completion_check_done;
1789 if (ret->grid[(y+1)*w+x] == TENT &&
1790 ret->grid[y*w+(x+1)] == TENT)
1791 goto completion_check_done;
1796 * OK; we have the right number of tents, they match the
1797 * numeric clues, and they satisfy the non-adjacency
1798 * criterion. Finally, we need to verify that they can be
1799 * placed in a one-to-one matching with the trees such that
1800 * every tent is orthogonally adjacent to its tree.
1802 * This bit is where the hard work comes in: we have to do
1803 * it by finding such a matching using maxflow.
1805 * So we construct a network with one special source node,
1806 * one special sink node, one node per tent, and one node
1810 edges = snewn(2 * maxedges, int);
1811 capacity = snewn(maxedges, int);
1812 flow = snewn(maxedges, int);
1817 * 0..w*h trees/tents
1821 for (y = 0; y < h; y++)
1822 for (x = 0; x < w; x++)
1823 if (ret->grid[y*w+x] == TREE) {
1827 * Here we use the direction enum declared for
1828 * the solver. We make use of the fact that the
1829 * directions are declared in the order
1830 * U,L,R,D, meaning that we go through the four
1831 * neighbours of any square in numerically
1834 for (d = 1; d < MAXDIR; d++) {
1835 int x2 = x + dx(d), y2 = y + dy(d);
1836 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
1837 ret->grid[y2*w+x2] == TENT) {
1838 assert(nedges < maxedges);
1839 edges[nedges*2] = y*w+x;
1840 edges[nedges*2+1] = y2*w+x2;
1841 capacity[nedges] = 1;
1845 } else if (ret->grid[y*w+x] == TENT) {
1846 assert(nedges < maxedges);
1847 edges[nedges*2] = y*w+x;
1848 edges[nedges*2+1] = w*h+1; /* edge going to sink */
1849 capacity[nedges] = 1;
1852 for (y = 0; y < h; y++)
1853 for (x = 0; x < w; x++)
1854 if (ret->grid[y*w+x] == TREE) {
1855 assert(nedges < maxedges);
1856 edges[nedges*2] = w*h; /* edge coming from source */
1857 edges[nedges*2+1] = y*w+x;
1858 capacity[nedges] = 1;
1861 n = maxflow(w*h+2, w*h, w*h+1, nedges, edges, capacity, flow, NULL);
1868 goto completion_check_done;
1871 * We haven't managed to fault the grid on any count. Score!
1873 ret->completed = TRUE;
1875 completion_check_done:
1880 /* ----------------------------------------------------------------------
1884 static void game_compute_size(const game_params *params, int tilesize,
1887 /* fool the macros */
1888 struct dummy { int tilesize; } dummy, *ds = &dummy;
1889 dummy.tilesize = tilesize;
1891 *x = TLBORDER + BRBORDER + TILESIZE * params->w;
1892 *y = TLBORDER + BRBORDER + TILESIZE * params->h;
1895 static void game_set_size(drawing *dr, game_drawstate *ds,
1896 const game_params *params, int tilesize)
1898 ds->tilesize = tilesize;
1901 static float *game_colours(frontend *fe, int *ncolours)
1903 float *ret = snewn(3 * NCOLOURS, float);
1905 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1907 ret[COL_GRID * 3 + 0] = 0.0F;
1908 ret[COL_GRID * 3 + 1] = 0.0F;
1909 ret[COL_GRID * 3 + 2] = 0.0F;
1911 ret[COL_GRASS * 3 + 0] = 0.7F;
1912 ret[COL_GRASS * 3 + 1] = 1.0F;
1913 ret[COL_GRASS * 3 + 2] = 0.5F;
1915 ret[COL_TREETRUNK * 3 + 0] = 0.6F;
1916 ret[COL_TREETRUNK * 3 + 1] = 0.4F;
1917 ret[COL_TREETRUNK * 3 + 2] = 0.0F;
1919 ret[COL_TREELEAF * 3 + 0] = 0.0F;
1920 ret[COL_TREELEAF * 3 + 1] = 0.7F;
1921 ret[COL_TREELEAF * 3 + 2] = 0.0F;
1923 ret[COL_TENT * 3 + 0] = 0.8F;
1924 ret[COL_TENT * 3 + 1] = 0.7F;
1925 ret[COL_TENT * 3 + 2] = 0.0F;
1927 ret[COL_ERROR * 3 + 0] = 1.0F;
1928 ret[COL_ERROR * 3 + 1] = 0.0F;
1929 ret[COL_ERROR * 3 + 2] = 0.0F;
1931 ret[COL_ERRTEXT * 3 + 0] = 1.0F;
1932 ret[COL_ERRTEXT * 3 + 1] = 1.0F;
1933 ret[COL_ERRTEXT * 3 + 2] = 1.0F;
1935 ret[COL_ERRTRUNK * 3 + 0] = 0.6F;
1936 ret[COL_ERRTRUNK * 3 + 1] = 0.0F;
1937 ret[COL_ERRTRUNK * 3 + 2] = 0.0F;
1939 *ncolours = NCOLOURS;
1943 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1945 int w = state->p.w, h = state->p.h;
1946 struct game_drawstate *ds = snew(struct game_drawstate);
1950 ds->started = FALSE;
1951 ds->p = state->p; /* structure copy */
1952 ds->drawn = snewn(w*h, int);
1953 for (i = 0; i < w*h; i++)
1954 ds->drawn[i] = MAGIC;
1955 ds->numbersdrawn = snewn(w+h, int);
1956 for (i = 0; i < w+h; i++)
1957 ds->numbersdrawn[i] = 2;
1958 ds->cx = ds->cy = -1;
1963 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1966 sfree(ds->numbersdrawn);
1971 ERR_ADJ_TOPLEFT = 4,
1982 static int *find_errors(const game_state *state, char *grid)
1984 int w = state->p.w, h = state->p.h;
1985 int *ret = snewn(w*h + w + h, int);
1986 int *tmp = snewn(w*h*2, int), *dsf = tmp + w*h;
1990 * This function goes through a grid and works out where to
1991 * highlight play errors in red. The aim is that it should
1992 * produce at least one error highlight for any complete grid
1993 * (or complete piece of grid) violating a puzzle constraint, so
1994 * that a grid containing no BLANK squares is either a win or is
1995 * marked up in some way that indicates why not.
1997 * So it's easy enough to highlight errors in the numeric clues
1998 * - just light up any row or column number which is not
1999 * fulfilled - and it's just as easy to highlight adjacent
2000 * tents. The difficult bit is highlighting failures in the
2001 * tent/tree matching criterion.
2003 * A natural approach would seem to be to apply the maxflow
2004 * algorithm to find the tent/tree matching; if this fails, it
2005 * must necessarily terminate with a min-cut which can be
2006 * reinterpreted as some set of trees which have too few tents
2007 * between them (or vice versa). However, it's bad for
2008 * localising errors, because it's not easy to make the
2009 * algorithm narrow down to the _smallest_ such set of trees: if
2010 * trees A and B have only one tent between them, for instance,
2011 * it might perfectly well highlight not only A and B but also
2012 * trees C and D which are correctly matched on the far side of
2013 * the grid, on the grounds that those four trees between them
2014 * have only three tents.
2016 * Also, that approach fares badly when you introduce the
2017 * additional requirement that incomplete grids should have
2018 * errors highlighted only when they can be proved to be errors
2019 * - so that trees should not be marked as having too few tents
2020 * if there are enough BLANK squares remaining around them that
2021 * could be turned into the missing tents (to do so would be
2022 * patronising, since the overwhelming likelihood is not that
2023 * the player has forgotten to put a tree there but that they
2024 * have merely not put one there _yet_). However, tents with too
2025 * few trees can be marked immediately, since those are
2026 * definitely player error.
2028 * So I adopt an alternative approach, which is to consider the
2029 * bipartite adjacency graph between trees and tents
2030 * ('bipartite' in the sense that for these purposes I
2031 * deliberately ignore two adjacent trees or two adjacent
2032 * tents), divide that graph up into its connected components
2033 * using a dsf, and look for components which contain different
2034 * numbers of trees and tents. This allows me to highlight
2035 * groups of tents with too few trees between them immediately,
2036 * and then in order to find groups of trees with too few tents
2037 * I redo the same process but counting BLANKs as potential
2038 * tents (so that the only trees highlighted are those
2039 * surrounded by enough NONTENTs to make it impossible to give
2040 * them enough tents).
2042 * However, this technique is incomplete: it is not a sufficient
2043 * condition for the existence of a perfect matching that every
2044 * connected component of the graph has the same number of tents
2045 * and trees. An example of a graph which satisfies the latter
2046 * condition but still has no perfect matching is
2055 * which can be realised in Tents as
2061 * The matching-error highlighter described above will not mark
2062 * this construction as erroneous. However, something else will:
2063 * the three tents in the above diagram (let us suppose A,B,C
2064 * are the tents, though it doesn't matter which) contain two
2065 * diagonally adjacent pairs. So there will be _an_ error
2066 * highlighted for the above layout, even though not all types
2067 * of error will be highlighted.
2069 * And in fact we can prove that this will always be the case:
2070 * that the shortcomings of the matching-error highlighter will
2071 * always be made up for by the easy tent adjacency highlighter.
2073 * Lemma: Let G be a bipartite graph between n trees and n
2074 * tents, which is connected, and in which no tree has degree
2075 * more than two (but a tent may). Then G has a perfect matching.
2077 * (Note: in the statement and proof of the Lemma I will
2078 * consistently use 'tree' to indicate a type of graph vertex as
2079 * opposed to a tent, and not to indicate a tree in the graph-
2084 * If we can find a tent of degree 1 joined to a tree of degree
2085 * 2, then any perfect matching must pair that tent with that
2086 * tree. Hence, we can remove both, leaving a smaller graph G'
2087 * which still satisfies all the conditions of the Lemma, and
2088 * which has a perfect matching iff G does.
2090 * So, wlog, we may assume G contains no tent of degree 1 joined
2091 * to a tree of degree 2; if it does, we can reduce it as above.
2093 * If G has no tent of degree 1 at all, then every tent has
2094 * degree at least two, so there are at least 2n edges in the
2095 * graph. But every tree has degree at most two, so there are at
2096 * most 2n edges. Hence there must be exactly 2n edges, so every
2097 * tree and every tent must have degree exactly two, which means
2098 * that the whole graph consists of a single loop (by
2099 * connectedness), and therefore certainly has a perfect
2102 * Alternatively, if G does have a tent of degree 1 but it is
2103 * not connected to a tree of degree 2, then the tree it is
2104 * connected to must have degree 1 - and, by connectedness, that
2105 * must mean that that tent and that tree between them form the
2106 * entire graph. This trivial graph has a trivial perfect
2109 * That proves the lemma. Hence, in any case where the matching-
2110 * error highlighter fails to highlight an erroneous component
2111 * (because it has the same number of tents as trees, but they
2112 * cannot be matched up), the above lemma tells us that there
2113 * must be a tree with degree more than 2, i.e. a tree
2114 * orthogonally adjacent to at least three tents. But in that
2115 * case, there must be some pair of those three tents which are
2116 * diagonally adjacent to each other, so the tent-adjacency
2117 * highlighter will necessarily show an error. So any filled
2118 * layout in Tents which is not a correct solution to the puzzle
2119 * must have _some_ error highlighted by the subroutine below.
2121 * (Of course it would be nicer if we could highlight all
2122 * errors: in the above example layout, we would like to
2123 * highlight tents A,B as having too few trees between them, and
2124 * trees 2,3 as having too few tents, in addition to marking the
2125 * adjacency problems. But I can't immediately think of any way
2126 * to find the smallest sets of such tents and trees without an
2127 * O(2^N) loop over all subsets of a given component.)
2131 * ret[0] through to ret[w*h-1] give error markers for the grid
2132 * squares. After that, ret[w*h] to ret[w*h+w-1] give error
2133 * markers for the column numbers, and ret[w*h+w] to
2134 * ret[w*h+w+h-1] for the row numbers.
2138 * Spot tent-adjacency violations.
2140 for (x = 0; x < w*h; x++)
2142 for (y = 0; y < h; y++) {
2143 for (x = 0; x < w; x++) {
2144 if (y+1 < h && x+1 < w &&
2145 ((grid[y*w+x] == TENT &&
2146 grid[(y+1)*w+(x+1)] == TENT) ||
2147 (grid[(y+1)*w+x] == TENT &&
2148 grid[y*w+(x+1)] == TENT))) {
2149 ret[y*w+x] |= 1 << ERR_ADJ_BOTRIGHT;
2150 ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOPRIGHT;
2151 ret[y*w+(x+1)] |= 1 << ERR_ADJ_BOTLEFT;
2152 ret[(y+1)*w+(x+1)] |= 1 << ERR_ADJ_TOPLEFT;
2155 grid[y*w+x] == TENT &&
2156 grid[(y+1)*w+x] == TENT) {
2157 ret[y*w+x] |= 1 << ERR_ADJ_BOT;
2158 ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOP;
2161 grid[y*w+x] == TENT &&
2162 grid[y*w+(x+1)] == TENT) {
2163 ret[y*w+x] |= 1 << ERR_ADJ_RIGHT;
2164 ret[y*w+(x+1)] |= 1 << ERR_ADJ_LEFT;
2170 * Spot numeric clue violations.
2172 for (x = 0; x < w; x++) {
2173 int tents = 0, maybetents = 0;
2174 for (y = 0; y < h; y++) {
2175 if (grid[y*w+x] == TENT)
2177 else if (grid[y*w+x] == BLANK)
2180 ret[w*h+x] = (tents > state->numbers->numbers[x] ||
2181 tents + maybetents < state->numbers->numbers[x]);
2183 for (y = 0; y < h; y++) {
2184 int tents = 0, maybetents = 0;
2185 for (x = 0; x < w; x++) {
2186 if (grid[y*w+x] == TENT)
2188 else if (grid[y*w+x] == BLANK)
2191 ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] ||
2192 tents + maybetents < state->numbers->numbers[w+y]);
2196 * Identify groups of tents with too few trees between them,
2197 * which we do by constructing the connected components of the
2198 * bipartite adjacency graph between tents and trees
2199 * ('bipartite' in the sense that we deliberately ignore
2200 * adjacency between tents or between trees), and highlighting
2201 * all the tents in any component which has a smaller tree
2205 /* Construct the equivalence classes. */
2206 for (y = 0; y < h; y++) {
2207 for (x = 0; x < w-1; x++) {
2208 if ((grid[y*w+x] == TREE && grid[y*w+x+1] == TENT) ||
2209 (grid[y*w+x] == TENT && grid[y*w+x+1] == TREE))
2210 dsf_merge(dsf, y*w+x, y*w+x+1);
2213 for (y = 0; y < h-1; y++) {
2214 for (x = 0; x < w; x++) {
2215 if ((grid[y*w+x] == TREE && grid[(y+1)*w+x] == TENT) ||
2216 (grid[y*w+x] == TENT && grid[(y+1)*w+x] == TREE))
2217 dsf_merge(dsf, y*w+x, (y+1)*w+x);
2220 /* Count up the tent/tree difference in each one. */
2221 for (x = 0; x < w*h; x++)
2223 for (x = 0; x < w*h; x++) {
2224 y = dsf_canonify(dsf, x);
2225 if (grid[x] == TREE)
2227 else if (grid[x] == TENT)
2230 /* And highlight any tent belonging to an equivalence class with
2231 * a score less than zero. */
2232 for (x = 0; x < w*h; x++) {
2233 y = dsf_canonify(dsf, x);
2234 if (grid[x] == TENT && tmp[y] < 0)
2235 ret[x] |= 1 << ERR_OVERCOMMITTED;
2239 * Identify groups of trees with too few tents between them.
2240 * This is done similarly, except that we now count BLANK as
2241 * equivalent to TENT, i.e. we only highlight such trees when
2242 * the user hasn't even left _room_ to provide tents for them
2243 * all. (Otherwise, we'd highlight all trees red right at the
2244 * start of the game, before the user had done anything wrong!)
2246 #define TENT(x) ((x)==TENT || (x)==BLANK)
2248 /* Construct the equivalence classes. */
2249 for (y = 0; y < h; y++) {
2250 for (x = 0; x < w-1; x++) {
2251 if ((grid[y*w+x] == TREE && TENT(grid[y*w+x+1])) ||
2252 (TENT(grid[y*w+x]) && grid[y*w+x+1] == TREE))
2253 dsf_merge(dsf, y*w+x, y*w+x+1);
2256 for (y = 0; y < h-1; y++) {
2257 for (x = 0; x < w; x++) {
2258 if ((grid[y*w+x] == TREE && TENT(grid[(y+1)*w+x])) ||
2259 (TENT(grid[y*w+x]) && grid[(y+1)*w+x] == TREE))
2260 dsf_merge(dsf, y*w+x, (y+1)*w+x);
2263 /* Count up the tent/tree difference in each one. */
2264 for (x = 0; x < w*h; x++)
2266 for (x = 0; x < w*h; x++) {
2267 y = dsf_canonify(dsf, x);
2268 if (grid[x] == TREE)
2270 else if (TENT(grid[x]))
2273 /* And highlight any tree belonging to an equivalence class with
2274 * a score more than zero. */
2275 for (x = 0; x < w*h; x++) {
2276 y = dsf_canonify(dsf, x);
2277 if (grid[x] == TREE && tmp[y] > 0)
2278 ret[x] |= 1 << ERR_OVERCOMMITTED;
2286 static void draw_err_adj(drawing *dr, game_drawstate *ds, int x, int y)
2294 coords[0] = x - TILESIZE*2/5;
2297 coords[3] = y - TILESIZE*2/5;
2298 coords[4] = x + TILESIZE*2/5;
2301 coords[7] = y + TILESIZE*2/5;
2302 draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
2305 * Draw an exclamation mark in the diamond. This turns out to
2306 * look unpleasantly off-centre if done via draw_text, so I do
2307 * it by hand on the basis that exclamation marks aren't that
2308 * difficult to draw...
2311 yext = TILESIZE*2/5 - (xext*2+2);
2312 draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
2314 draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
2317 static void draw_tile(drawing *dr, game_drawstate *ds,
2318 int x, int y, int v, int cur, int printing)
2321 int tx = COORD(x), ty = COORD(y);
2322 int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2;
2327 clip(dr, tx, ty, TILESIZE, TILESIZE);
2330 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, COL_GRID);
2331 draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1,
2332 (v == BLANK ? COL_BACKGROUND : COL_GRASS));
2338 (printing ? draw_rect_outline : draw_rect)
2339 (dr, cx-TILESIZE/15, ty+TILESIZE*3/10,
2340 2*(TILESIZE/15)+1, (TILESIZE*9/10 - TILESIZE*3/10),
2341 (err & (1<<ERR_OVERCOMMITTED) ? COL_ERRTRUNK : COL_TREETRUNK));
2343 for (i = 0; i < (printing ? 2 : 1); i++) {
2344 int col = (i == 1 ? COL_BACKGROUND :
2345 (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR :
2347 int sub = i * (TILESIZE/32);
2348 draw_circle(dr, cx, ty+TILESIZE*4/10, TILESIZE/4 - sub,
2350 draw_circle(dr, cx+TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
2352 draw_circle(dr, cx-TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
2354 draw_circle(dr, cx+TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
2356 draw_circle(dr, cx-TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
2359 } else if (v == TENT) {
2362 coords[0] = cx - TILESIZE/3;
2363 coords[1] = cy + TILESIZE/3;
2364 coords[2] = cx + TILESIZE/3;
2365 coords[3] = cy + TILESIZE/3;
2367 coords[5] = cy - TILESIZE/3;
2368 col = (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : COL_TENT);
2369 draw_polygon(dr, coords, 3, (printing ? -1 : col), col);
2372 if (err & (1 << ERR_ADJ_TOPLEFT))
2373 draw_err_adj(dr, ds, tx, ty);
2374 if (err & (1 << ERR_ADJ_TOP))
2375 draw_err_adj(dr, ds, tx+TILESIZE/2, ty);
2376 if (err & (1 << ERR_ADJ_TOPRIGHT))
2377 draw_err_adj(dr, ds, tx+TILESIZE, ty);
2378 if (err & (1 << ERR_ADJ_LEFT))
2379 draw_err_adj(dr, ds, tx, ty+TILESIZE/2);
2380 if (err & (1 << ERR_ADJ_RIGHT))
2381 draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE/2);
2382 if (err & (1 << ERR_ADJ_BOTLEFT))
2383 draw_err_adj(dr, ds, tx, ty+TILESIZE);
2384 if (err & (1 << ERR_ADJ_BOT))
2385 draw_err_adj(dr, ds, tx+TILESIZE/2, ty+TILESIZE);
2386 if (err & (1 << ERR_ADJ_BOTRIGHT))
2387 draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE);
2390 int coff = TILESIZE/8;
2391 draw_rect_outline(dr, tx + coff, ty + coff,
2392 TILESIZE - coff*2 + 1, TILESIZE - coff*2 + 1,
2397 draw_update(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
2401 * Internal redraw function, used for printing as well as drawing.
2403 static void int_redraw(drawing *dr, game_drawstate *ds,
2404 const game_state *oldstate, const game_state *state,
2405 int dir, const game_ui *ui,
2406 float animtime, float flashtime, int printing)
2408 int w = state->p.w, h = state->p.h;
2410 int cx = -1, cy = -1;
2416 if (ui->cdisp) { cx = ui->cx; cy = ui->cy; }
2417 if (cx != ds->cx || cy != ds->cy) cmoved = 1;
2420 if (printing || !ds->started) {
2423 game_compute_size(&state->p, TILESIZE, &ww, &wh);
2424 draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
2425 draw_update(dr, 0, 0, ww, wh);
2430 print_line_width(dr, TILESIZE/64);
2435 for (y = 0; y <= h; y++)
2436 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), COL_GRID);
2437 for (x = 0; x <= w; x++)
2438 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), COL_GRID);
2442 flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
2447 * Find errors. For this we use _part_ of the information from a
2448 * currently active drag: we transform dsx,dsy but not anything
2449 * else. (This seems to strike a good compromise between having
2450 * the error highlights respond instantly to single clicks, but
2451 * not giving constant feedback during a right-drag.)
2453 if (ui && ui->drag_button >= 0) {
2454 tmpgrid = snewn(w*h, char);
2455 memcpy(tmpgrid, state->grid, w*h);
2456 tmpgrid[ui->dsy * w + ui->dsx] =
2457 drag_xform(ui, ui->dsx, ui->dsy, tmpgrid[ui->dsy * w + ui->dsx]);
2458 errors = find_errors(state, tmpgrid);
2461 errors = find_errors(state, state->grid);
2467 for (y = 0; y < h; y++) {
2468 for (x = 0; x < w; x++) {
2469 int v = state->grid[y*w+x];
2473 * We deliberately do not take drag_ok into account
2474 * here, because user feedback suggests that it's
2475 * marginally nicer not to have the drag effects
2476 * flickering on and off disconcertingly.
2478 if (ui && ui->drag_button >= 0)
2479 v = drag_xform(ui, x, y, v);
2481 if (flashing && (v == TREE || v == TENT))
2485 if ((x == cx && y == cy) ||
2486 (x == ds->cx && y == ds->cy)) credraw = 1;
2491 if (printing || ds->drawn[y*w+x] != v || credraw) {
2492 draw_tile(dr, ds, x, y, v, (x == cx && y == cy), printing);
2494 ds->drawn[y*w+x] = v;
2500 * Draw (or redraw, if their error-highlighted state has
2501 * changed) the numbers.
2503 for (x = 0; x < w; x++) {
2504 if (printing || ds->numbersdrawn[x] != errors[w*h+x]) {
2506 draw_rect(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1,
2508 sprintf(buf, "%d", state->numbers->numbers[x]);
2509 draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1),
2510 FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL,
2511 (errors[w*h+x] ? COL_ERROR : COL_GRID), buf);
2512 draw_update(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1);
2514 ds->numbersdrawn[x] = errors[w*h+x];
2517 for (y = 0; y < h; y++) {
2518 if (printing || ds->numbersdrawn[w+y] != errors[w*h+w+y]) {
2520 draw_rect(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE,
2522 sprintf(buf, "%d", state->numbers->numbers[w+y]);
2523 draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2,
2524 FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE,
2525 (errors[w*h+w+y] ? COL_ERROR : COL_GRID), buf);
2526 draw_update(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE);
2528 ds->numbersdrawn[w+y] = errors[w*h+w+y];
2540 static void game_redraw(drawing *dr, game_drawstate *ds,
2541 const game_state *oldstate, const game_state *state,
2542 int dir, const game_ui *ui,
2543 float animtime, float flashtime)
2545 int_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, FALSE);
2548 static float game_anim_length(const game_state *oldstate,
2549 const game_state *newstate, int dir, game_ui *ui)
2554 static float game_flash_length(const game_state *oldstate,
2555 const game_state *newstate, int dir, game_ui *ui)
2557 if (!oldstate->completed && newstate->completed &&
2558 !oldstate->used_solve && !newstate->used_solve)
2564 static int game_status(const game_state *state)
2566 return state->completed ? +1 : 0;
2569 static int game_timing_state(const game_state *state, game_ui *ui)
2574 static void game_print_size(const game_params *params, float *x, float *y)
2579 * I'll use 6mm squares by default.
2581 game_compute_size(params, 600, &pw, &ph);
2586 static void game_print(drawing *dr, const game_state *state, int tilesize)
2590 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2591 game_drawstate ads, *ds = &ads;
2592 game_set_size(dr, ds, NULL, tilesize);
2594 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
2595 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
2596 c = print_mono_colour(dr, 1); assert(c == COL_GRASS);
2597 c = print_mono_colour(dr, 0); assert(c == COL_TREETRUNK);
2598 c = print_mono_colour(dr, 0); assert(c == COL_TREELEAF);
2599 c = print_mono_colour(dr, 0); assert(c == COL_TENT);
2601 int_redraw(dr, ds, NULL, state, +1, NULL, 0.0F, 0.0F, TRUE);
2605 #define thegame tents
2608 const struct game thegame = {
2609 "Tents", "games.tents", "tents",
2611 game_fetch_preset, NULL,
2616 TRUE, game_configure, custom_params,
2624 TRUE, game_can_format_as_text_now, game_text_format,
2632 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2635 game_free_drawstate,
2640 TRUE, FALSE, game_print_size, game_print,
2641 FALSE, /* wants_statusbar */
2642 FALSE, game_timing_state,
2643 REQUIRE_RBUTTON, /* flags */
2646 #ifdef STANDALONE_SOLVER
2650 int main(int argc, char **argv)
2654 char *id = NULL, *desc;
2657 int ret, diff, really_verbose = FALSE;
2658 struct solver_scratch *sc;
2660 while (--argc > 0) {
2662 if (!strcmp(p, "-v")) {
2663 really_verbose = TRUE;
2664 } else if (!strcmp(p, "-g")) {
2666 } else if (*p == '-') {
2667 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2675 fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2679 desc = strchr(id, ':');
2681 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2686 p = default_params();
2687 decode_params(p, id);
2688 err = validate_desc(p, desc);
2690 fprintf(stderr, "%s: %s\n", argv[0], err);
2693 s = new_game(NULL, p, desc);
2694 s2 = new_game(NULL, p, desc);
2696 sc = new_scratch(p->w, p->h);
2699 * When solving an Easy puzzle, we don't want to bother the
2700 * user with Hard-level deductions. For this reason, we grade
2701 * the puzzle internally before doing anything else.
2703 ret = -1; /* placate optimiser */
2704 for (diff = 0; diff < DIFFCOUNT; diff++) {
2705 ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
2706 s2->grid, sc, diff);
2711 if (diff == DIFFCOUNT) {
2713 printf("Difficulty rating: too hard to solve internally\n");
2715 printf("Unable to find a unique solution\n");
2719 printf("Difficulty rating: impossible (no solution exists)\n");
2721 printf("Difficulty rating: %s\n", tents_diffnames[diff]);
2723 verbose = really_verbose;
2724 ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
2725 s2->grid, sc, diff);
2727 printf("Puzzle is inconsistent\n");
2729 fputs(game_text_format(s2), stdout);
2738 /* vim: set shiftwidth=4 tabstop=8: */