2 * tents.c: Puzzle involving placing tents next to trees subject to
3 * some confusing conditions.
7 * - error highlighting?
8 * * highlighting adjacent tents is easy
9 * * highlighting violated numeric clues is almost as easy
10 * (might want to pay attention to NONTENTs here)
11 * * but how in hell do we highlight a failure of maxflow
12 * during completion checking?
13 * + well, the _obvious_ approach is to use maxflow's own
14 * error report: it will provide, via the `cut' parameter,
15 * a set of trees which have too few tents between them.
16 * It's unclear that this will be particularly obvious to
17 * a user, however. Is there any other way?
19 * - it might be nice to make setter-provided tent/nontent clues
21 * * on the other hand, this would introduce considerable extra
22 * complexity and size into the game state; also inviolable
23 * clues would have to be marked as such somehow, in an
24 * intrusive and annoying manner. Since they're never
25 * generated by _my_ generator, I'm currently more inclined
28 * - more difficult levels at the top end?
29 * * for example, sometimes we can deduce that two BLANKs in
30 * the same row are each adjacent to the same unattached tree
31 * and to nothing else, implying that they can't both be
32 * tents; this enables us to rule out some extra combinations
33 * in the row-based deduction loop, and hence deduce more
34 * from the number in that row than we could otherwise do.
35 * * that by itself doesn't seem worth implementing a new
36 * difficulty level for, but if I can find a few more things
37 * like that then it might become worthwhile.
38 * * I wonder if there's a sensible heuristic for where to
39 * guess which would make a recursive solver viable?
56 * The rules of this puzzle as available on the WWW are poorly
57 * specified. The bits about tents having to be orthogonally
58 * adjacent to trees, tents not being even diagonally adjacent to
59 * one another, and the number of tents in each row and column
60 * being given are simple enough; the difficult bit is the
61 * tent-to-tree matching.
63 * Some sources use simplistic wordings such as `each tree is
64 * exactly connected to only one tent', which is extremely unclear:
65 * it's easy to read erroneously as `each tree is _orthogonally
66 * adjacent_ to exactly one tent', which is definitely incorrect.
67 * Even the most coherent sources I've found don't do a much better
68 * job of stating the rule.
70 * A more precise statement of the rule is that it must be possible
71 * to find a bijection f between tents and trees such that each
72 * tree T is orthogonally adjacent to the tent f(T), but that a
73 * tent is permitted to be adjacent to other trees in addition to
74 * its own. This slightly non-obvious criterion is what gives this
75 * puzzle most of its subtlety.
77 * However, there's a particularly subtle ambiguity left over. Is
78 * the bijection between tents and trees required to be _unique_?
79 * In other words, is that bijection conceptually something the
80 * player should be able to exhibit as part of the solution (even
81 * if they aren't actually required to do so)? Or is it sufficient
82 * to have a unique _placement_ of the tents which gives rise to at
83 * least one suitable bijection?
85 * The puzzle shown to the right of this .T. 2 *T* 2
86 * paragraph illustrates the problem. There T.T 0 -> T-T 0
87 * are two distinct bijections available. .T. 2 *T* 2
88 * The answer to the above question will
89 * determine whether it's a valid puzzle. 202 202
91 * This is an important question, because it affects both the
92 * player and the generator. Eventually I found all the instances
93 * of this puzzle I could Google up, solved them all by hand, and
94 * verified that in all cases the tree/tent matching was uniquely
95 * determined given the tree and tent positions. Therefore, the
96 * puzzle as implemented in this source file takes the following
99 * - When checking a user-supplied solution for correctness, only
100 * verify that there exists _at least_ one matching.
101 * - When generating a puzzle, enforce that there must be
104 * Algorithmic implications
105 * ------------------------
107 * Another way of phrasing the tree/tent matching criterion is to
108 * say that the bipartite adjacency graph between trees and tents
109 * has a perfect matching. That is, if you construct a graph which
110 * has a vertex per tree and a vertex per tent, and an edge between
111 * any tree and tent which are orthogonally adjacent, it is
112 * possible to find a set of N edges of that graph (where N is the
113 * number of trees and also the number of tents) which between them
114 * connect every tree to every tent.
116 * The most efficient known algorithms for finding such a matching
117 * given a graph, as far as I'm aware, are the Munkres assignment
118 * algorithm (also known as the Hungarian algorithm) and the
119 * Ford-Fulkerson algorithm (for finding optimal flows in
120 * networks). Each of these takes O(N^3) running time; so we're
121 * talking O(N^3) time to verify any candidate solution to this
122 * puzzle. That's just about OK if you're doing it once per mouse
123 * click (and in fact not even that, since the sensible thing to do
124 * is check all the _other_ puzzle criteria and only wade into this
125 * quagmire if none are violated); but if the solver had to keep
126 * doing N^3 work internally, then it would probably end up with
127 * more like N^5 or N^6 running time, and grid generation would
128 * become very clunky.
130 * Fortunately, I've been able to prove a very useful property of
131 * _unique_ perfect matchings, by adapting the proof of Hall's
132 * Marriage Theorem. For those unaware of Hall's Theorem, I'll
133 * recap it and its proof: it states that a bipartite graph
134 * contains a perfect matching iff every set of vertices on the
135 * left side of the graph have a neighbourhood _at least_ as big on
138 * This condition is obviously satisfied if a perfect matching does
139 * exist; each left-side node has a distinct right-side node which
140 * is the one assigned to it by the matching, and thus any set of n
141 * left vertices must have a combined neighbourhood containing at
142 * least the n corresponding right vertices, and possibly others
143 * too. Alternatively, imagine if you had (say) three left-side
144 * nodes all of which were connected to only two right-side nodes
145 * between them: any perfect matching would have to assign one of
146 * those two right nodes to each of the three left nodes, and still
147 * give the three left nodes a different right node each. This is
148 * of course impossible.
150 * To prove the converse (that if every subset of left vertices
151 * satisfies the Hall condition then a perfect matching exists),
152 * consider trying to find a proper subset of the left vertices
153 * which _exactly_ satisfies the Hall condition: that is, its right
154 * neighbourhood is precisely the same size as it. If we can find
155 * such a subset, then we can split the bipartite graph into two
156 * smaller ones: one consisting of the left subset and its right
157 * neighbourhood, the other consisting of everything else. Edges
158 * from the left side of the former graph to the right side of the
159 * latter do not exist, by construction; edges from the right side
160 * of the former to the left of the latter cannot be part of any
161 * perfect matching because otherwise the left subset would not be
162 * left with enough distinct right vertices to connect to (this is
163 * exactly the same deduction used in Solo's set analysis). You can
164 * then prove (left as an exercise) that both these smaller graphs
165 * still satisfy the Hall condition, and therefore the proof will
166 * follow by induction.
168 * There's one other possibility, which is the case where _no_
169 * proper subset of the left vertices has a right neighbourhood of
170 * exactly the same size. That is, every left subset has a strictly
171 * _larger_ right neighbourhood. In this situation, we can simply
172 * remove an _arbitrary_ edge from the graph. This cannot reduce
173 * the size of any left subset's right neighbourhood by more than
174 * one, so if all neighbourhoods were strictly bigger than they
175 * needed to be initially, they must now still be _at least as big_
176 * as they need to be. So we can keep throwing out arbitrary edges
177 * until we find a set which exactly satisfies the Hall condition,
178 * and then proceed as above. []
180 * That's Hall's theorem. I now build on this by examining the
181 * circumstances in which a bipartite graph can have a _unique_
182 * perfect matching. It is clear that in the second case, where no
183 * left subset exactly satisfies the Hall condition and so we can
184 * remove an arbitrary edge, there cannot be a unique perfect
185 * matching: given one perfect matching, we choose our arbitrary
186 * removed edge to be one of those contained in it, and then we can
187 * still find a perfect matching in the remaining graph, which will
188 * be a distinct perfect matching in the original.
190 * So it is a necessary condition for a unique perfect matching
191 * that there must be at least one proper left subset which
192 * _exactly_ satisfies the Hall condition. But now consider the
193 * smaller graph constructed by taking that left subset and its
194 * neighbourhood: if the graph as a whole had a unique perfect
195 * matching, then so must this smaller one, which means we can find
196 * a proper left subset _again_, and so on. Repeating this process
197 * must eventually reduce us to a graph with only one left-side
198 * vertex (so there are no proper subsets at all); this vertex must
199 * be connected to only one right-side vertex, and hence must be so
200 * in the original graph as well (by construction). So we can
201 * discard this vertex pair from the graph, and any other edges
202 * that involved it (which will by construction be from other left
203 * vertices only), and the resulting smaller graph still has a
204 * unique perfect matching which means we can do the same thing
207 * In other words, given any bipartite graph with a unique perfect
208 * matching, we can find that matching by the following extremely
211 * - Find a left-side vertex which is only connected to one
213 * - Assign those vertices to one another, and therefore discard
214 * any other edges connecting to that right vertex.
215 * - Repeat until all vertices have been matched.
217 * This algorithm can be run in O(V+E) time (where V is the number
218 * of vertices and E is the number of edges in the graph), and the
219 * only way it can fail is if there is not a unique perfect
220 * matching (either because there is no matching at all, or because
221 * it isn't unique; but it can't distinguish those cases).
223 * Thus, the internal solver in this source file can be confident
224 * that if the tree/tent matching is uniquely determined by the
225 * tree and tent positions, it can find it using only this kind of
226 * obvious and simple operation: assign a tree to a tent if it
227 * cannot possibly belong to any other tent, and vice versa. If the
228 * solver were _only_ trying to determine the matching, even that
229 * `vice versa' wouldn't be required; but it can come in handy when
230 * not all the tents have been placed yet. I can therefore be
231 * reasonably confident that as long as my solver doesn't need to
232 * cope with grids that have a non-unique matching, it will also
233 * not need to do anything complicated like set analysis between
238 * In standalone solver mode, `verbose' is a variable which can be
239 * set by command-line option; in debugging mode it's simply always
242 #if defined STANDALONE_SOLVER
243 #define SOLVER_DIAGNOSTICS
245 #elif defined SOLVER_DIAGNOSTICS
250 * Difficulty levels. I do some macro ickery here to ensure that my
251 * enum and the various forms of my name list always match up.
253 #define DIFFLIST(A) \
256 #define ENUM(upper,title,lower) DIFF_ ## upper,
257 #define TITLE(upper,title,lower) #title,
258 #define ENCODE(upper,title,lower) #lower
259 #define CONFIG(upper,title,lower) ":" #title
260 enum { DIFFLIST(ENUM) DIFFCOUNT };
261 static char const *const tents_diffnames[] = { DIFFLIST(TITLE) };
262 static char const tents_diffchars[] = DIFFLIST(ENCODE);
263 #define DIFFCONFIG DIFFLIST(CONFIG)
275 enum { BLANK, TREE, TENT, NONTENT, MAGIC };
290 struct numbers *numbers;
291 int completed, used_solve;
294 static game_params *default_params(void)
296 game_params *ret = snew(game_params);
299 ret->diff = DIFF_EASY;
304 static const struct game_params tents_presets[] = {
308 {10, 10, DIFF_TRICKY},
310 {15, 15, DIFF_TRICKY},
313 static int game_fetch_preset(int i, char **name, game_params **params)
318 if (i < 0 || i >= lenof(tents_presets))
321 ret = snew(game_params);
322 *ret = tents_presets[i];
324 sprintf(str, "%dx%d %s", ret->w, ret->h, tents_diffnames[ret->diff]);
331 static void free_params(game_params *params)
336 static game_params *dup_params(game_params *params)
338 game_params *ret = snew(game_params);
339 *ret = *params; /* structure copy */
343 static void decode_params(game_params *params, char const *string)
345 params->w = params->h = atoi(string);
346 while (*string && isdigit((unsigned char)*string)) string++;
347 if (*string == 'x') {
349 params->h = atoi(string);
350 while (*string && isdigit((unsigned char)*string)) string++;
352 if (*string == 'd') {
355 for (i = 0; i < DIFFCOUNT; i++)
356 if (*string == tents_diffchars[i])
358 if (*string) string++;
362 static char *encode_params(game_params *params, int full)
366 sprintf(buf, "%dx%d", params->w, params->h);
368 sprintf(buf + strlen(buf), "d%c",
369 tents_diffchars[params->diff]);
373 static config_item *game_configure(game_params *params)
378 ret = snewn(4, config_item);
380 ret[0].name = "Width";
381 ret[0].type = C_STRING;
382 sprintf(buf, "%d", params->w);
383 ret[0].sval = dupstr(buf);
386 ret[1].name = "Height";
387 ret[1].type = C_STRING;
388 sprintf(buf, "%d", params->h);
389 ret[1].sval = dupstr(buf);
392 ret[2].name = "Difficulty";
393 ret[2].type = C_CHOICES;
394 ret[2].sval = DIFFCONFIG;
395 ret[2].ival = params->diff;
405 static game_params *custom_params(config_item *cfg)
407 game_params *ret = snew(game_params);
409 ret->w = atoi(cfg[0].sval);
410 ret->h = atoi(cfg[1].sval);
411 ret->diff = cfg[2].ival;
416 static char *validate_params(game_params *params, int full)
418 if (params->w < 2 || params->h < 2)
419 return "Width and height must both be at least two";
424 * Scratch space for solver.
426 enum { N, U, L, R, D, MAXDIR }; /* link directions */
427 #define dx(d) ( ((d)==R) - ((d)==L) )
428 #define dy(d) ( ((d)==D) - ((d)==U) )
429 #define F(d) ( U + D - (d) )
430 struct solver_scratch {
431 char *links; /* mapping between trees and tents */
433 char *place, *mrows, *trows;
436 static struct solver_scratch *new_scratch(int w, int h)
438 struct solver_scratch *ret = snew(struct solver_scratch);
440 ret->links = snewn(w*h, char);
441 ret->locs = snewn(max(w, h), int);
442 ret->place = snewn(max(w, h), char);
443 ret->mrows = snewn(3 * max(w, h), char);
444 ret->trows = snewn(3 * max(w, h), char);
449 static void free_scratch(struct solver_scratch *sc)
460 * Solver. Returns 0 for impossibility, 1 for success, 2 for
461 * ambiguity or failure to converge.
463 static int tents_solve(int w, int h, const char *grid, int *numbers,
464 char *soln, struct solver_scratch *sc, int diff)
467 char *mrow, *mrow1, *mrow2, *trow, *trow1, *trow2;
470 * Set up solver data.
472 memset(sc->links, N, w*h);
475 * Set up solution array.
477 memcpy(soln, grid, w*h);
483 int done_something = FALSE;
486 * Any tent which has only one unattached tree adjacent to
487 * it can be tied to that tree.
489 for (y = 0; y < h; y++)
490 for (x = 0; x < w; x++)
491 if (soln[y*w+x] == TENT && !sc->links[y*w+x]) {
494 for (d = 1; d < MAXDIR; d++) {
495 int x2 = x + dx(d), y2 = y + dy(d);
496 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
497 soln[y2*w+x2] == TREE &&
498 !sc->links[y2*w+x2]) {
500 break; /* found more than one */
506 if (d == MAXDIR && linkd == 0) {
507 #ifdef SOLVER_DIAGNOSTICS
509 printf("tent at %d,%d cannot link to anything\n",
512 return 0; /* no solution exists */
513 } else if (d == MAXDIR) {
514 int x2 = x + dx(linkd), y2 = y + dy(linkd);
516 #ifdef SOLVER_DIAGNOSTICS
518 printf("tent at %d,%d can only link to tree at"
519 " %d,%d\n", x, y, x2, y2);
522 sc->links[y*w+x] = linkd;
523 sc->links[y2*w+x2] = F(linkd);
524 done_something = TRUE;
531 break; /* don't do anything else! */
534 * Mark a blank square as NONTENT if it is not orthogonally
535 * adjacent to any unmatched tree.
537 for (y = 0; y < h; y++)
538 for (x = 0; x < w; x++)
539 if (soln[y*w+x] == BLANK) {
540 int can_be_tent = FALSE;
542 for (d = 1; d < MAXDIR; d++) {
543 int x2 = x + dx(d), y2 = y + dy(d);
544 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
545 soln[y2*w+x2] == TREE &&
551 #ifdef SOLVER_DIAGNOSTICS
553 printf("%d,%d cannot be a tent (no adjacent"
554 " unmatched tree)\n", x, y);
556 soln[y*w+x] = NONTENT;
557 done_something = TRUE;
565 * Mark a blank square as NONTENT if it is (perhaps
566 * diagonally) adjacent to any other tent.
568 for (y = 0; y < h; y++)
569 for (x = 0; x < w; x++)
570 if (soln[y*w+x] == BLANK) {
571 int dx, dy, imposs = FALSE;
573 for (dy = -1; dy <= +1; dy++)
574 for (dx = -1; dx <= +1; dx++)
576 int x2 = x + dx, y2 = y + dy;
577 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
578 soln[y2*w+x2] == TENT)
583 #ifdef SOLVER_DIAGNOSTICS
585 printf("%d,%d cannot be a tent (adjacent tent)\n",
588 soln[y*w+x] = NONTENT;
589 done_something = TRUE;
597 * Any tree which has exactly one {unattached tent, BLANK}
598 * adjacent to it must have its tent in that square.
600 for (y = 0; y < h; y++)
601 for (x = 0; x < w; x++)
602 if (soln[y*w+x] == TREE && !sc->links[y*w+x]) {
603 int linkd = 0, linkd2 = 0, nd = 0;
605 for (d = 1; d < MAXDIR; d++) {
606 int x2 = x + dx(d), y2 = y + dy(d);
607 if (!(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h))
609 if (soln[y2*w+x2] == BLANK ||
610 (soln[y2*w+x2] == TENT && !sc->links[y2*w+x2])) {
620 #ifdef SOLVER_DIAGNOSTICS
622 printf("tree at %d,%d cannot link to anything\n",
625 return 0; /* no solution exists */
626 } else if (nd == 1) {
627 int x2 = x + dx(linkd), y2 = y + dy(linkd);
629 #ifdef SOLVER_DIAGNOSTICS
631 printf("tree at %d,%d can only link to tent at"
632 " %d,%d\n", x, y, x2, y2);
634 soln[y2*w+x2] = TENT;
635 sc->links[y*w+x] = linkd;
636 sc->links[y2*w+x2] = F(linkd);
637 done_something = TRUE;
638 } else if (nd == 2 && (!dx(linkd) != !dx(linkd2)) &&
639 diff >= DIFF_TRICKY) {
641 * If there are two possible places where
642 * this tree's tent can go, and they are
643 * diagonally separated rather than being
644 * on opposite sides of the tree, then the
645 * square (other than the tree square)
646 * which is adjacent to both of them must
649 int x2 = x + dx(linkd) + dx(linkd2);
650 int y2 = y + dy(linkd) + dy(linkd2);
651 assert(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h);
652 if (soln[y2*w+x2] == BLANK) {
653 #ifdef SOLVER_DIAGNOSTICS
655 printf("possible tent locations for tree at"
656 " %d,%d rule out tent at %d,%d\n",
659 soln[y2*w+x2] = NONTENT;
660 done_something = TRUE;
669 * If localised deductions about the trees and tents
670 * themselves haven't helped us, it's time to resort to the
671 * numbers round the grid edge. For each row and column, we
672 * go through all possible combinations of locations for
673 * the unplaced tents, rule out any which have adjacent
674 * tents, and spot any square which is given the same state
675 * by all remaining combinations.
677 for (i = 0; i < w+h; i++) {
678 int start, step, len, start1, start2, n, k;
682 * This is the number for a column.
697 * This is the number for a row.
712 if (diff < DIFF_TRICKY) {
714 * In Easy mode, we don't look at the effect of one
715 * row on the next (i.e. ruling out a square if all
716 * possibilities for an adjacent row place a tent
719 start1 = start2 = -1;
725 * Count and store the locations of the free squares,
726 * and also count the number of tents already placed.
729 for (j = 0; j < len; j++) {
730 if (soln[start+j*step] == TENT)
731 k--; /* one fewer tent to place */
732 else if (soln[start+j*step] == BLANK)
737 continue; /* nothing left to do here */
740 * Now we know we're placing k tents in n squares. Set
741 * up the first possibility.
743 for (j = 0; j < n; j++)
744 sc->place[j] = (j < k ? TENT : NONTENT);
747 * We're aiming to find squares in this row which are
748 * invariant over all valid possibilities. Thus, we
749 * maintain the current state of that invariance. We
750 * start everything off at MAGIC to indicate that it
751 * hasn't been set up yet.
754 mrow1 = sc->mrows + len;
755 mrow2 = sc->mrows + 2*len;
757 trow1 = sc->trows + len;
758 trow2 = sc->trows + 2*len;
759 memset(mrow, MAGIC, 3*len);
762 * And iterate over all possibilities.
768 * See if this possibility is valid. The only way
769 * it can fail to be valid is if it contains two
770 * adjacent tents. (Other forms of invalidity, such
771 * as containing a tent adjacent to one already
772 * placed, will have been dealt with already by
773 * other parts of the solver.)
776 for (j = 0; j+1 < n; j++)
777 if (sc->place[j] == TENT &&
778 sc->place[j+1] == TENT &&
779 sc->locs[j+1] == sc->locs[j]+1) {
786 * Merge this valid combination into mrow.
788 memset(trow, MAGIC, len);
789 memset(trow+len, BLANK, 2*len);
790 for (j = 0; j < n; j++) {
791 trow[sc->locs[j]] = sc->place[j];
792 if (sc->place[j] == TENT) {
794 for (jj = sc->locs[j]-1; jj <= sc->locs[j]+1; jj++)
795 if (jj >= 0 && jj < len)
796 trow1[jj] = trow2[jj] = NONTENT;
800 for (j = 0; j < 3*len; j++) {
801 if (trow[j] == MAGIC)
803 if (mrow[j] == MAGIC || mrow[j] == trow[j]) {
805 * Either this is the first valid
806 * placement we've found at all, or
807 * this square's contents are
808 * consistent with every previous valid
814 * This square's contents fail to match
815 * what they were in a different
816 * combination, so we cannot deduce
817 * anything about this square.
825 * Find the next combination of k choices from n.
826 * We do this by finding the rightmost tent which
827 * can be moved one place right, doing so, and
828 * shunting all tents to the right of that as far
829 * left as they can go.
832 for (j = n-1; j > 0; j--) {
833 if (sc->place[j] == TENT)
835 if (sc->place[j] == NONTENT && sc->place[j-1] == TENT) {
836 sc->place[j-1] = NONTENT;
839 sc->place[++j] = TENT;
841 sc->place[j] = NONTENT;
846 break; /* we've finished */
850 * It's just possible that _no_ placement was valid, in
851 * which case we have an internally inconsistent
854 if (mrow[sc->locs[0]] == MAGIC)
855 return 0; /* inconsistent */
858 * Now go through mrow and see if there's anything
859 * we've deduced which wasn't already mentioned in soln.
861 for (j = 0; j < len; j++) {
864 for (whichrow = 0; whichrow < 3; whichrow++) {
865 char *mthis = mrow + whichrow * len;
866 int tstart = (whichrow == 0 ? start :
867 whichrow == 1 ? start1 : start2);
869 mthis[j] != MAGIC && mthis[j] != BLANK &&
870 soln[tstart+j*step] == BLANK) {
871 int pos = tstart+j*step;
873 #ifdef SOLVER_DIAGNOSTICS
875 printf("%s %d forces %s at %d,%d\n",
876 step==1 ? "row" : "column",
877 step==1 ? start/w : start,
878 mthis[j] == TENT ? "tent" : "non-tent",
881 soln[pos] = mthis[j];
882 done_something = TRUE;
896 * The solver has nothing further it can do. Return 1 if both
897 * soln and sc->links are completely filled in, or 2 otherwise.
899 for (y = 0; y < h; y++)
900 for (x = 0; x < w; x++) {
901 if (soln[y*w+x] == BLANK)
903 if (soln[y*w+x] != NONTENT && sc->links[y*w+x] == 0)
910 static char *new_game_desc(game_params *params, random_state *rs,
911 char **aux, int interactive)
913 int w = params->w, h = params->h;
914 int ntrees = w * h / 5;
915 char *grid = snewn(w*h, char);
916 char *puzzle = snewn(w*h, char);
917 int *numbers = snewn(w+h, int);
918 char *soln = snewn(w*h, char);
919 int *temp = snewn(2*w*h, int), *itemp = temp + w*h;
920 int maxedges = ntrees*4 + w*h;
921 int *edges = snewn(2*maxedges, int);
922 int *capacity = snewn(maxedges, int);
923 int *flow = snewn(maxedges, int);
924 struct solver_scratch *sc = new_scratch(w, h);
929 * Since this puzzle has many global deductions and doesn't
930 * permit limited clue sets, generating grids for this puzzle
931 * is hard enough that I see no better option than to simply
932 * generate a solution and see if it's unique and has the
933 * required difficulty. This turns out to be computationally
936 * We chose our tree count (hence also tent count) by dividing
937 * the total grid area by five above. Why five? Well, w*h/4 is
938 * the maximum number of tents you can _possibly_ fit into the
939 * grid without violating the separation criterion, and to
940 * achieve that you are constrained to a very small set of
941 * possible layouts (the obvious one with a tent at every
942 * (even,even) coordinate, and trivial variations thereon). So
943 * if we reduce the tent count a bit more, we enable more
944 * random-looking placement; 5 turns out to be a plausible
945 * figure which yields sensible puzzles. Increasing the tent
946 * count would give puzzles whose solutions were too regimented
947 * and could be solved by the use of that knowledge (and would
948 * also take longer to find a viable placement); decreasing it
949 * would make the grids emptier and more boring.
951 * Actually generating a grid is a matter of first placing the
952 * tents, and then placing the trees by the use of maxflow
953 * (finding a distinct square adjacent to every tent). We do it
954 * this way round because otherwise satisfying the tent
955 * separation condition would become onerous: most randomly
956 * chosen tent layouts do not satisfy this condition, so we'd
957 * have gone to a lot of work before finding that a candidate
958 * layout was unusable. Instead, we place the tents first and
959 * ensure they meet the separation criterion _before_ doing
960 * lots of computation; this works much better.
962 * The maxflow algorithm is not randomised, so employed naively
963 * it would give rise to grids with clear structure and
964 * directional bias. Hence, I assign the network nodes as seen
965 * by maxflow to be a _random_ permutation the squares of the
966 * grid, so that any bias shown by maxflow towards low-numbered
967 * nodes is turned into a random bias.
969 * This generation strategy can fail at many points, including
970 * as early as tent placement (if you get a bad random order in
971 * which to greedily try the grid squares, you won't even
972 * manage to find enough mutually non-adjacent squares to put
973 * the tents in). Then it can fail if maxflow doesn't manage to
974 * find a good enough matching (i.e. the tent placements don't
975 * admit any adequate tree placements); and finally it can fail
976 * if the solver finds that the problem has the wrong
977 * difficulty (including being actually non-unique). All of
978 * these, however, are insufficiently frequent to cause
984 * Arrange the grid squares into a random order, and invert
985 * that order so we can find a square's index as well.
987 for (i = 0; i < w*h; i++)
989 shuffle(temp, w*h, sizeof(*temp), rs);
990 for (i = 0; i < w*h; i++)
994 * The first `ntrees' entries in temp which we can get
995 * without making two tents adjacent will be the tent
998 memset(grid, BLANK, w*h);
1000 for (i = 0; i < w*h && j > 0; i++) {
1001 int x = temp[i] % w, y = temp[i] / w;
1002 int dy, dx, ok = TRUE;
1004 for (dy = -1; dy <= +1; dy++)
1005 for (dx = -1; dx <= +1; dx++)
1006 if (x+dx >= 0 && x+dx < w &&
1007 y+dy >= 0 && y+dy < h &&
1008 grid[(y+dy)*w+(x+dx)] == TENT)
1012 grid[temp[i]] = TENT;
1017 continue; /* couldn't place all the tents */
1020 * Now we build up the list of graph edges.
1023 for (i = 0; i < w*h; i++) {
1024 if (grid[temp[i]] == TENT) {
1025 for (j = 0; j < w*h; j++) {
1026 if (grid[temp[j]] != TENT) {
1027 int xi = temp[i] % w, yi = temp[i] / w;
1028 int xj = temp[j] % w, yj = temp[j] / w;
1029 if (abs(xi-xj) + abs(yi-yj) == 1) {
1030 edges[nedges*2] = i;
1031 edges[nedges*2+1] = j;
1032 capacity[nedges] = 1;
1039 * Special node w*h is the sink node; any non-tent node
1040 * has an edge going to it.
1042 edges[nedges*2] = i;
1043 edges[nedges*2+1] = w*h;
1044 capacity[nedges] = 1;
1050 * Special node w*h+1 is the source node, with an edge going to
1053 for (i = 0; i < w*h; i++) {
1054 if (grid[temp[i]] == TENT) {
1055 edges[nedges*2] = w*h+1;
1056 edges[nedges*2+1] = i;
1057 capacity[nedges] = 1;
1062 assert(nedges <= maxedges);
1065 * Now we're ready to call the maxflow algorithm to place the
1068 j = maxflow(w*h+2, w*h+1, w*h, nedges, edges, capacity, flow, NULL);
1071 continue; /* couldn't place all the tents */
1074 * We've placed the trees. Now we need to work out _where_
1075 * we've placed them, which is a matter of reading back out
1076 * from the `flow' array.
1078 for (i = 0; i < nedges; i++) {
1079 if (edges[2*i] < w*h && edges[2*i+1] < w*h && flow[i] > 0)
1080 grid[temp[edges[2*i+1]]] = TREE;
1084 * I think it looks ugly if there isn't at least one of
1085 * _something_ (tent or tree) in each row and each column
1086 * of the grid. This doesn't give any information away
1087 * since a completely empty row/column is instantly obvious
1088 * from the clues (it has no trees and a zero).
1090 for (i = 0; i < w; i++) {
1091 for (j = 0; j < h; j++) {
1092 if (grid[j*w+i] != BLANK)
1093 break; /* found something in this column */
1096 break; /* found empty column */
1099 continue; /* a column was empty */
1101 for (j = 0; j < h; j++) {
1102 for (i = 0; i < w; i++) {
1103 if (grid[j*w+i] != BLANK)
1104 break; /* found something in this row */
1107 break; /* found empty row */
1110 continue; /* a row was empty */
1113 * Now set up the numbers round the edge.
1115 for (i = 0; i < w; i++) {
1117 for (j = 0; j < h; j++)
1118 if (grid[j*w+i] == TENT)
1122 for (i = 0; i < h; i++) {
1124 for (j = 0; j < w; j++)
1125 if (grid[i*w+j] == TENT)
1131 * And now actually solve the puzzle, to see whether it's
1132 * unique and has the required difficulty.
1134 for (i = 0; i < w*h; i++)
1135 puzzle[i] = grid[i] == TREE ? TREE : BLANK;
1136 i = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff-1);
1137 j = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff);
1140 * We expect solving with difficulty params->diff to have
1141 * succeeded (otherwise the problem is too hard), and
1142 * solving with diff-1 to have failed (otherwise it's too
1145 if (i == 2 && j == 1)
1150 * That's it. Encode as a game ID.
1152 ret = snewn((w+h)*40 + ntrees + (w*h)/26 + 1, char);
1155 for (i = 0; i <= w*h; i++) {
1156 int c = (i < w*h ? grid[i] == TREE : 1);
1158 *p++ = (j == 0 ? '_' : j-1 + 'a');
1168 for (i = 0; i < w+h; i++)
1169 p += sprintf(p, ",%d", numbers[i]);
1171 ret = sresize(ret, p - ret, char);
1174 * And encode the solution as an aux_info.
1176 *aux = snewn(ntrees * 40, char);
1179 for (i = 0; i < w*h; i++)
1180 if (grid[i] == TENT)
1181 p += sprintf(p, ";T%d,%d", i%w, i/w);
1183 *aux = sresize(*aux, p - *aux, char);
1198 static char *validate_desc(game_params *params, char *desc)
1200 int w = params->w, h = params->h;
1204 while (*desc && *desc != ',') {
1207 else if (*desc >= 'a' && *desc < 'z')
1208 area += *desc - 'a' + 2;
1209 else if (*desc == 'z')
1211 else if (*desc == '!' || *desc == '-')
1214 return "Invalid character in grid specification";
1219 for (i = 0; i < w+h; i++) {
1221 return "Not enough numbers given after grid specification";
1222 else if (*desc != ',')
1223 return "Invalid character in number list";
1225 while (*desc && isdigit((unsigned char)*desc)) desc++;
1229 return "Unexpected additional data at end of game description";
1233 static game_state *new_game(midend *me, game_params *params, char *desc)
1235 int w = params->w, h = params->h;
1236 game_state *state = snew(game_state);
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;
1247 memset(state->grid, BLANK, w*h);
1256 else if (*desc >= 'a' && *desc < 'z')
1257 run = *desc - ('a'-1);
1258 else if (*desc == 'z') {
1262 assert(*desc == '!' || *desc == '-');
1264 type = (*desc == '!' ? TENT : NONTENT);
1270 assert(i >= 0 && i <= w*h);
1272 assert(type == TREE);
1276 state->grid[i++] = type;
1280 for (i = 0; i < w+h; i++) {
1281 assert(*desc == ',');
1283 state->numbers->numbers[i] = atoi(desc);
1284 while (*desc && isdigit((unsigned char)*desc)) desc++;
1292 static game_state *dup_game(game_state *state)
1294 int w = state->p.w, h = state->p.h;
1295 game_state *ret = snew(game_state);
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;
1308 static void free_game(game_state *state)
1310 if (--state->numbers->refcount <= 0) {
1311 sfree(state->numbers->numbers);
1312 sfree(state->numbers);
1318 static char *solve_game(game_state *state, game_state *currstate,
1319 char *aux, char **error)
1321 int w = state->p.w, h = state->p.h;
1325 * If we already have the solution, save ourselves some
1330 struct solver_scratch *sc = new_scratch(w, h);
1336 soln = snewn(w*h, char);
1337 ret = tents_solve(w, h, state->grid, state->numbers->numbers,
1338 soln, sc, DIFFCOUNT-1);
1343 *error = "This puzzle is not self-consistent";
1345 *error = "Unable to find a unique solution for this puzzle";
1350 * Construct a move string which turns the current state
1351 * into the solved state.
1353 move = snewn(w*h * 40, char);
1356 for (i = 0; i < w*h; i++)
1357 if (soln[i] == TENT)
1358 p += sprintf(p, ";T%d,%d", i%w, i/w);
1360 move = sresize(move, p - move, char);
1368 static char *game_text_format(game_state *state)
1370 int w = state->p.w, h = state->p.h;
1375 * FIXME: We currently do not print the numbers round the edges
1376 * of the grid. I need to work out a sensible way of doing this
1377 * even when the column numbers exceed 9.
1379 * In the absence of those numbers, the result size is h lines
1380 * of w+1 characters each, plus a NUL.
1382 * This function is currently only used by the standalone
1383 * solver; until I make it look more sensible, I won't enable
1384 * it in the main game structure.
1386 ret = snewn(h*(w+1) + 1, char);
1388 for (y = 0; y < h; y++) {
1389 for (x = 0; x < w; x++) {
1390 *p = (state->grid[y*w+x] == BLANK ? '.' :
1391 state->grid[y*w+x] == TREE ? 'T' :
1392 state->grid[y*w+x] == TENT ? '*' :
1393 state->grid[y*w+x] == NONTENT ? '-' : '?');
1404 int dsx, dsy; /* coords of drag start */
1405 int dex, dey; /* coords of drag end */
1406 int drag_button; /* -1 for none, or a button code */
1407 int drag_ok; /* dragged off the window, to cancel */
1410 static game_ui *new_ui(game_state *state)
1412 game_ui *ui = snew(game_ui);
1413 ui->dsx = ui->dsy = -1;
1414 ui->dex = ui->dey = -1;
1415 ui->drag_button = -1;
1416 ui->drag_ok = FALSE;
1420 static void free_ui(game_ui *ui)
1425 static char *encode_ui(game_ui *ui)
1430 static void decode_ui(game_ui *ui, char *encoding)
1434 static void game_changed_state(game_ui *ui, game_state *oldstate,
1435 game_state *newstate)
1439 struct game_drawstate {
1446 #define PREFERRED_TILESIZE 32
1447 #define TILESIZE (ds->tilesize)
1448 #define TLBORDER (TILESIZE/2)
1449 #define BRBORDER (TILESIZE*3/2)
1450 #define COORD(x) ( (x) * TILESIZE + TLBORDER )
1451 #define FROMCOORD(x) ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 )
1453 #define FLASH_TIME 0.30F
1455 static int drag_xform(game_ui *ui, int x, int y, int v)
1457 int xmin, ymin, xmax, ymax;
1459 xmin = min(ui->dsx, ui->dex);
1460 xmax = max(ui->dsx, ui->dex);
1461 ymin = min(ui->dsy, ui->dey);
1462 ymax = max(ui->dsy, ui->dey);
1465 * Left-dragging has no effect, so we treat a left-drag as a
1466 * single click on dsx,dsy.
1468 if (ui->drag_button == LEFT_BUTTON) {
1469 xmin = xmax = ui->dsx;
1470 ymin = ymax = ui->dsy;
1473 if (x < xmin || x > xmax || y < ymin || y > ymax)
1474 return v; /* no change outside drag area */
1477 return v; /* trees are inviolate always */
1479 if (xmin == xmax && ymin == ymax) {
1481 * Results of a simple click. Left button sets blanks to
1482 * tents; right button sets blanks to non-tents; either
1483 * button clears a non-blank square.
1485 if (ui->drag_button == LEFT_BUTTON)
1486 v = (v == BLANK ? TENT : BLANK);
1488 v = (v == BLANK ? NONTENT : BLANK);
1491 * Results of a drag. Left-dragging has no effect.
1492 * Right-dragging sets all blank squares to non-tents and
1493 * has no effect on anything else.
1495 if (ui->drag_button == RIGHT_BUTTON)
1496 v = (v == BLANK ? NONTENT : v);
1504 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1505 int x, int y, int button)
1507 int w = state->p.w, h = state->p.h;
1509 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1512 if (x < 0 || y < 0 || x >= w || y >= h)
1515 ui->drag_button = button;
1516 ui->dsx = ui->dex = x;
1517 ui->dsy = ui->dey = y;
1519 return ""; /* ui updated */
1522 if ((IS_MOUSE_DRAG(button) || IS_MOUSE_RELEASE(button)) &&
1523 ui->drag_button > 0) {
1524 int xmin, ymin, xmax, ymax;
1525 char *buf, *sep, tmpbuf[80];
1526 int buflen, bufsize, tmplen;
1530 if (x < 0 || y < 0 || x >= w || y >= h) {
1531 ui->drag_ok = FALSE;
1534 * Drags are limited to one row or column. Hence, we
1535 * work out which coordinate is closer to the drag
1536 * start, and move it _to_ the drag start.
1538 if (abs(x - ui->dsx) < abs(y - ui->dsy))
1549 if (IS_MOUSE_DRAG(button))
1550 return ""; /* ui updated */
1553 * The drag has been released. Enact it.
1556 ui->drag_button = -1;
1557 return ""; /* drag was just cancelled */
1560 xmin = min(ui->dsx, ui->dex);
1561 xmax = max(ui->dsx, ui->dex);
1562 ymin = min(ui->dsy, ui->dey);
1563 ymax = max(ui->dsy, ui->dey);
1564 assert(0 <= xmin && xmin <= xmax && xmax < w);
1565 assert(0 <= ymin && ymin <= ymax && ymax < w);
1569 buf = snewn(bufsize, char);
1571 for (y = ymin; y <= ymax; y++)
1572 for (x = xmin; x <= xmax; x++) {
1573 int v = drag_xform(ui, x, y, state->grid[y*w+x]);
1574 if (state->grid[y*w+x] != v) {
1575 tmplen = sprintf(tmpbuf, "%s%c%d,%d", sep,
1576 (int)(v == BLANK ? 'B' :
1577 v == TENT ? 'T' : 'N'),
1581 if (buflen + tmplen >= bufsize) {
1582 bufsize = buflen + tmplen + 256;
1583 buf = sresize(buf, bufsize, char);
1586 strcpy(buf+buflen, tmpbuf);
1591 ui->drag_button = -1; /* drag is terminated */
1595 return ""; /* ui updated (drag was terminated) */
1605 static game_state *execute_move(game_state *state, char *move)
1607 int w = state->p.w, h = state->p.h;
1609 int x, y, m, n, i, j;
1610 game_state *ret = dup_game(state);
1616 ret->used_solve = TRUE;
1618 * Set all non-tree squares to NONTENT. The rest of the
1619 * solve move will fill the tents in over the top.
1621 for (i = 0; i < w*h; i++)
1622 if (ret->grid[i] != TREE)
1623 ret->grid[i] = NONTENT;
1625 } else if (c == 'B' || c == 'T' || c == 'N') {
1627 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1628 x < 0 || y < 0 || x >= w || y >= h) {
1632 if (ret->grid[y*w+x] == TREE) {
1636 ret->grid[y*w+x] = (c == 'B' ? BLANK : c == 'T' ? TENT : NONTENT);
1651 * Check for completion.
1653 for (i = n = m = 0; i < w*h; i++) {
1654 if (ret->grid[i] == TENT)
1656 else if (ret->grid[i] == TREE)
1660 int nedges, maxedges, *edges, *capacity, *flow;
1663 * We have the right number of tents, which is a
1664 * precondition for the game being complete. Now check that
1665 * the numbers add up.
1667 for (i = 0; i < w; i++) {
1669 for (j = 0; j < h; j++)
1670 if (ret->grid[j*w+i] == TENT)
1672 if (ret->numbers->numbers[i] != n)
1673 goto completion_check_done;
1675 for (i = 0; i < h; i++) {
1677 for (j = 0; j < w; j++)
1678 if (ret->grid[i*w+j] == TENT)
1680 if (ret->numbers->numbers[w+i] != n)
1681 goto completion_check_done;
1684 * Also, check that no two tents are adjacent.
1686 for (y = 0; y < h; y++)
1687 for (x = 0; x < w; x++) {
1689 ret->grid[y*w+x] == TENT && ret->grid[y*w+x+1] == TENT)
1690 goto completion_check_done;
1692 ret->grid[y*w+x] == TENT && ret->grid[(y+1)*w+x] == TENT)
1693 goto completion_check_done;
1694 if (x+1 < w && y+1 < h) {
1695 if (ret->grid[y*w+x] == TENT &&
1696 ret->grid[(y+1)*w+(x+1)] == TENT)
1697 goto completion_check_done;
1698 if (ret->grid[(y+1)*w+x] == TENT &&
1699 ret->grid[y*w+(x+1)] == TENT)
1700 goto completion_check_done;
1705 * OK; we have the right number of tents, they match the
1706 * numeric clues, and they satisfy the non-adjacency
1707 * criterion. Finally, we need to verify that they can be
1708 * placed in a one-to-one matching with the trees such that
1709 * every tent is orthogonally adjacent to its tree.
1711 * This bit is where the hard work comes in: we have to do
1712 * it by finding such a matching using maxflow.
1714 * So we construct a network with one special source node,
1715 * one special sink node, one node per tent, and one node
1719 edges = snewn(2 * maxedges, int);
1720 capacity = snewn(maxedges, int);
1721 flow = snewn(maxedges, int);
1726 * 0..w*h trees/tents
1730 for (y = 0; y < h; y++)
1731 for (x = 0; x < w; x++)
1732 if (ret->grid[y*w+x] == TREE) {
1736 * Here we use the direction enum declared for
1737 * the solver. We make use of the fact that the
1738 * directions are declared in the order
1739 * U,L,R,D, meaning that we go through the four
1740 * neighbours of any square in numerically
1743 for (d = 1; d < MAXDIR; d++) {
1744 int x2 = x + dx(d), y2 = y + dy(d);
1745 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
1746 ret->grid[y2*w+x2] == TENT) {
1747 assert(nedges < maxedges);
1748 edges[nedges*2] = y*w+x;
1749 edges[nedges*2+1] = y2*w+x2;
1750 capacity[nedges] = 1;
1754 } else if (ret->grid[y*w+x] == TENT) {
1755 assert(nedges < maxedges);
1756 edges[nedges*2] = y*w+x;
1757 edges[nedges*2+1] = w*h+1; /* edge going to sink */
1758 capacity[nedges] = 1;
1761 for (y = 0; y < h; y++)
1762 for (x = 0; x < w; x++)
1763 if (ret->grid[y*w+x] == TREE) {
1764 assert(nedges < maxedges);
1765 edges[nedges*2] = w*h; /* edge coming from source */
1766 edges[nedges*2+1] = y*w+x;
1767 capacity[nedges] = 1;
1770 n = maxflow(w*h+2, w*h, w*h+1, nedges, edges, capacity, flow, NULL);
1777 goto completion_check_done;
1780 * We haven't managed to fault the grid on any count. Score!
1782 ret->completed = TRUE;
1784 completion_check_done:
1789 /* ----------------------------------------------------------------------
1793 static void game_compute_size(game_params *params, int tilesize,
1796 /* fool the macros */
1797 struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy;
1799 *x = TLBORDER + BRBORDER + TILESIZE * params->w;
1800 *y = TLBORDER + BRBORDER + TILESIZE * params->h;
1803 static void game_set_size(drawing *dr, game_drawstate *ds,
1804 game_params *params, int tilesize)
1806 ds->tilesize = tilesize;
1809 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1811 float *ret = snewn(3 * NCOLOURS, float);
1813 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1815 ret[COL_GRID * 3 + 0] = 0.0F;
1816 ret[COL_GRID * 3 + 1] = 0.0F;
1817 ret[COL_GRID * 3 + 2] = 0.0F;
1819 ret[COL_GRASS * 3 + 0] = 0.7F;
1820 ret[COL_GRASS * 3 + 1] = 1.0F;
1821 ret[COL_GRASS * 3 + 2] = 0.5F;
1823 ret[COL_TREETRUNK * 3 + 0] = 0.6F;
1824 ret[COL_TREETRUNK * 3 + 1] = 0.4F;
1825 ret[COL_TREETRUNK * 3 + 2] = 0.0F;
1827 ret[COL_TREELEAF * 3 + 0] = 0.0F;
1828 ret[COL_TREELEAF * 3 + 1] = 0.7F;
1829 ret[COL_TREELEAF * 3 + 2] = 0.0F;
1831 ret[COL_TENT * 3 + 0] = 0.8F;
1832 ret[COL_TENT * 3 + 1] = 0.7F;
1833 ret[COL_TENT * 3 + 2] = 0.0F;
1835 *ncolours = NCOLOURS;
1839 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1841 int w = state->p.w, h = state->p.h;
1842 struct game_drawstate *ds = snew(struct game_drawstate);
1845 ds->started = FALSE;
1846 ds->p = state->p; /* structure copy */
1847 ds->drawn = snewn(w*h, char);
1848 memset(ds->drawn, MAGIC, w*h);
1853 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1859 static void draw_tile(drawing *dr, game_drawstate *ds,
1860 int x, int y, int v, int printing)
1862 int tx = COORD(x), ty = COORD(y);
1863 int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2;
1865 clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1868 draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1,
1869 (v == BLANK ? COL_BACKGROUND : COL_GRASS));
1874 (printing ? draw_rect_outline : draw_rect)
1875 (dr, cx-TILESIZE/15, ty+TILESIZE*3/10,
1876 2*(TILESIZE/15)+1, (TILESIZE*9/10 - TILESIZE*3/10),
1879 for (i = 0; i < (printing ? 2 : 1); i++) {
1880 int col = (i == 1 ? COL_BACKGROUND : COL_TREELEAF);
1881 int sub = i * (TILESIZE/32);
1882 draw_circle(dr, cx, ty+TILESIZE*4/10, TILESIZE/4 - sub,
1884 draw_circle(dr, cx+TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
1886 draw_circle(dr, cx-TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
1888 draw_circle(dr, cx+TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
1890 draw_circle(dr, cx-TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
1893 } else if (v == TENT) {
1895 coords[0] = cx - TILESIZE/3;
1896 coords[1] = cy + TILESIZE/3;
1897 coords[2] = cx + TILESIZE/3;
1898 coords[3] = cy + TILESIZE/3;
1900 coords[5] = cy - TILESIZE/3;
1901 draw_polygon(dr, coords, 3, (printing ? -1 : COL_TENT), COL_TENT);
1905 draw_update(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1909 * Internal redraw function, used for printing as well as drawing.
1911 static void int_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1912 game_state *state, int dir, game_ui *ui,
1913 float animtime, float flashtime, int printing)
1915 int w = state->p.w, h = state->p.h;
1918 if (printing || !ds->started) {
1921 game_compute_size(&state->p, TILESIZE, &ww, &wh);
1922 draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
1923 draw_update(dr, 0, 0, ww, wh);
1928 print_line_width(dr, TILESIZE/64);
1933 for (y = 0; y <= h; y++)
1934 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), COL_GRID);
1935 for (x = 0; x <= w; x++)
1936 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), COL_GRID);
1941 for (y = 0; y < h; y++) {
1943 sprintf(buf, "%d", state->numbers->numbers[y+w]);
1944 draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2,
1945 FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE,
1948 for (x = 0; x < w; x++) {
1950 sprintf(buf, "%d", state->numbers->numbers[x]);
1951 draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1),
1952 FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL,
1958 flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
1965 for (y = 0; y < h; y++)
1966 for (x = 0; x < w; x++) {
1967 int v = state->grid[y*w+x];
1970 * We deliberately do not take drag_ok into account
1971 * here, because user feedback suggests that it's
1972 * marginally nicer not to have the drag effects
1973 * flickering on and off disconcertingly.
1975 if (ui->drag_button >= 0)
1976 v = drag_xform(ui, x, y, v);
1978 if (flashing && (v == TREE || v == TENT))
1981 if (printing || ds->drawn[y*w+x] != v) {
1982 draw_tile(dr, ds, x, y, v, printing);
1984 ds->drawn[y*w+x] = v;
1989 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1990 game_state *state, int dir, game_ui *ui,
1991 float animtime, float flashtime)
1993 int_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, FALSE);
1996 static float game_anim_length(game_state *oldstate, game_state *newstate,
1997 int dir, game_ui *ui)
2002 static float game_flash_length(game_state *oldstate, game_state *newstate,
2003 int dir, game_ui *ui)
2005 if (!oldstate->completed && newstate->completed &&
2006 !oldstate->used_solve && !newstate->used_solve)
2012 static int game_wants_statusbar(void)
2017 static int game_timing_state(game_state *state, game_ui *ui)
2022 static void game_print_size(game_params *params, float *x, float *y)
2027 * I'll use 6mm squares by default.
2029 game_compute_size(params, 600, &pw, &ph);
2034 static void game_print(drawing *dr, game_state *state, int tilesize)
2038 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2039 game_drawstate ads, *ds = &ads;
2040 game_set_size(dr, ds, NULL, tilesize);
2042 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
2043 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
2044 c = print_mono_colour(dr, 1); assert(c == COL_GRASS);
2045 c = print_mono_colour(dr, 0); assert(c == COL_TREETRUNK);
2046 c = print_mono_colour(dr, 0); assert(c == COL_TREELEAF);
2047 c = print_mono_colour(dr, 0); assert(c == COL_TENT);
2049 int_redraw(dr, ds, NULL, state, +1, NULL, 0.0F, 0.0F, TRUE);
2053 #define thegame tents
2056 const struct game thegame = {
2057 "Tents", "games.tents",
2064 TRUE, game_configure, custom_params,
2072 FALSE, game_text_format,
2080 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2083 game_free_drawstate,
2087 TRUE, FALSE, game_print_size, game_print,
2088 game_wants_statusbar,
2089 FALSE, game_timing_state,
2090 0, /* mouse_priorities */
2093 #ifdef STANDALONE_SOLVER
2097 int main(int argc, char **argv)
2101 char *id = NULL, *desc, *err;
2103 int ret, diff, really_verbose = FALSE;
2104 struct solver_scratch *sc;
2106 while (--argc > 0) {
2108 if (!strcmp(p, "-v")) {
2109 really_verbose = TRUE;
2110 } else if (!strcmp(p, "-g")) {
2112 } else if (*p == '-') {
2113 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2121 fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2125 desc = strchr(id, ':');
2127 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2132 p = default_params();
2133 decode_params(p, id);
2134 err = validate_desc(p, desc);
2136 fprintf(stderr, "%s: %s\n", argv[0], err);
2139 s = new_game(NULL, p, desc);
2140 s2 = new_game(NULL, p, desc);
2142 sc = new_scratch(p->w, p->h);
2145 * When solving an Easy puzzle, we don't want to bother the
2146 * user with Hard-level deductions. For this reason, we grade
2147 * the puzzle internally before doing anything else.
2149 ret = -1; /* placate optimiser */
2150 for (diff = 0; diff < DIFFCOUNT; diff++) {
2151 ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
2152 s2->grid, sc, diff);
2157 if (diff == DIFFCOUNT) {
2159 printf("Difficulty rating: too hard to solve internally\n");
2161 printf("Unable to find a unique solution\n");
2165 printf("Difficulty rating: impossible (no solution exists)\n");
2167 printf("Difficulty rating: %s\n", tents_diffnames[diff]);
2169 verbose = really_verbose;
2170 ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
2171 s2->grid, sc, diff);
2173 printf("Puzzle is inconsistent\n");
2175 fputs(game_text_format(s2), stdout);