2 * tents.c: Puzzle involving placing tents next to trees subject to
3 * some confusing conditions.
7 * - my technique for highlighting errors in the tent/tree matching
8 * is not perfect. It currently works by finding the connected
9 * components of the bipartite adjacency graph between tents and
10 * trees, and highlighting red all the tents in such a component
11 * if they outnumber the trees (the red meaning "these tents have
12 * too few trees between them") and vice versa if the trees
13 * outnumber the tents (but this time considering BLANKs as
14 * potential tents as yet unplaced, to avoid highlighting
15 * 'errors' from the word go before the player has actually made
16 * any mistake). However, something more subtle can go wrong
17 * within a component: consider, for instance, the setup
23 * in which there is one connected component containing equal
24 * numbers of trees and tents, but nonetheless there is no
25 * perfect matching that can link the two sensibly. This will be
26 * rejected by the rigorous solution checker, but the error
27 * highlighter won't currently spot it.
29 * Well, the _matching_ error highlighter won't spot it, anyway.
30 * In that diagram, there are two pairs of diagonally adjacent
31 * tents, which will be flagged as erroneous because that's much
32 * easier. So if I could prove that _all_ such setups require
33 * diagonally adjacent tents, I could safely ignore this problem.
34 * If not, however, then a proper treatment will require running
35 * the maxflow matcher over each component once I've identified
38 * - it might be nice to make setter-provided tent/nontent clues
40 * * on the other hand, this would introduce considerable extra
41 * complexity and size into the game state; also inviolable
42 * clues would have to be marked as such somehow, in an
43 * intrusive and annoying manner. Since they're never
44 * generated by _my_ generator, I'm currently more inclined
47 * - more difficult levels at the top end?
48 * * for example, sometimes we can deduce that two BLANKs in
49 * the same row are each adjacent to the same unattached tree
50 * and to nothing else, implying that they can't both be
51 * tents; this enables us to rule out some extra combinations
52 * in the row-based deduction loop, and hence deduce more
53 * from the number in that row than we could otherwise do.
54 * * that by itself doesn't seem worth implementing a new
55 * difficulty level for, but if I can find a few more things
56 * like that then it might become worthwhile.
57 * * I wonder if there's a sensible heuristic for where to
58 * guess which would make a recursive solver viable?
75 * The rules of this puzzle as available on the WWW are poorly
76 * specified. The bits about tents having to be orthogonally
77 * adjacent to trees, tents not being even diagonally adjacent to
78 * one another, and the number of tents in each row and column
79 * being given are simple enough; the difficult bit is the
80 * tent-to-tree matching.
82 * Some sources use simplistic wordings such as `each tree is
83 * exactly connected to only one tent', which is extremely unclear:
84 * it's easy to read erroneously as `each tree is _orthogonally
85 * adjacent_ to exactly one tent', which is definitely incorrect.
86 * Even the most coherent sources I've found don't do a much better
87 * job of stating the rule.
89 * A more precise statement of the rule is that it must be possible
90 * to find a bijection f between tents and trees such that each
91 * tree T is orthogonally adjacent to the tent f(T), but that a
92 * tent is permitted to be adjacent to other trees in addition to
93 * its own. This slightly non-obvious criterion is what gives this
94 * puzzle most of its subtlety.
96 * However, there's a particularly subtle ambiguity left over. Is
97 * the bijection between tents and trees required to be _unique_?
98 * In other words, is that bijection conceptually something the
99 * player should be able to exhibit as part of the solution (even
100 * if they aren't actually required to do so)? Or is it sufficient
101 * to have a unique _placement_ of the tents which gives rise to at
102 * least one suitable bijection?
104 * The puzzle shown to the right of this .T. 2 *T* 2
105 * paragraph illustrates the problem. There T.T 0 -> T-T 0
106 * are two distinct bijections available. .T. 2 *T* 2
107 * The answer to the above question will
108 * determine whether it's a valid puzzle. 202 202
110 * This is an important question, because it affects both the
111 * player and the generator. Eventually I found all the instances
112 * of this puzzle I could Google up, solved them all by hand, and
113 * verified that in all cases the tree/tent matching was uniquely
114 * determined given the tree and tent positions. Therefore, the
115 * puzzle as implemented in this source file takes the following
118 * - When checking a user-supplied solution for correctness, only
119 * verify that there exists _at least_ one matching.
120 * - When generating a puzzle, enforce that there must be
123 * Algorithmic implications
124 * ------------------------
126 * Another way of phrasing the tree/tent matching criterion is to
127 * say that the bipartite adjacency graph between trees and tents
128 * has a perfect matching. That is, if you construct a graph which
129 * has a vertex per tree and a vertex per tent, and an edge between
130 * any tree and tent which are orthogonally adjacent, it is
131 * possible to find a set of N edges of that graph (where N is the
132 * number of trees and also the number of tents) which between them
133 * connect every tree to every tent.
135 * The most efficient known algorithms for finding such a matching
136 * given a graph, as far as I'm aware, are the Munkres assignment
137 * algorithm (also known as the Hungarian algorithm) and the
138 * Ford-Fulkerson algorithm (for finding optimal flows in
139 * networks). Each of these takes O(N^3) running time; so we're
140 * talking O(N^3) time to verify any candidate solution to this
141 * puzzle. That's just about OK if you're doing it once per mouse
142 * click (and in fact not even that, since the sensible thing to do
143 * is check all the _other_ puzzle criteria and only wade into this
144 * quagmire if none are violated); but if the solver had to keep
145 * doing N^3 work internally, then it would probably end up with
146 * more like N^5 or N^6 running time, and grid generation would
147 * become very clunky.
149 * Fortunately, I've been able to prove a very useful property of
150 * _unique_ perfect matchings, by adapting the proof of Hall's
151 * Marriage Theorem. For those unaware of Hall's Theorem, I'll
152 * recap it and its proof: it states that a bipartite graph
153 * contains a perfect matching iff every set of vertices on the
154 * left side of the graph have a neighbourhood _at least_ as big on
157 * This condition is obviously satisfied if a perfect matching does
158 * exist; each left-side node has a distinct right-side node which
159 * is the one assigned to it by the matching, and thus any set of n
160 * left vertices must have a combined neighbourhood containing at
161 * least the n corresponding right vertices, and possibly others
162 * too. Alternatively, imagine if you had (say) three left-side
163 * nodes all of which were connected to only two right-side nodes
164 * between them: any perfect matching would have to assign one of
165 * those two right nodes to each of the three left nodes, and still
166 * give the three left nodes a different right node each. This is
167 * of course impossible.
169 * To prove the converse (that if every subset of left vertices
170 * satisfies the Hall condition then a perfect matching exists),
171 * consider trying to find a proper subset of the left vertices
172 * which _exactly_ satisfies the Hall condition: that is, its right
173 * neighbourhood is precisely the same size as it. If we can find
174 * such a subset, then we can split the bipartite graph into two
175 * smaller ones: one consisting of the left subset and its right
176 * neighbourhood, the other consisting of everything else. Edges
177 * from the left side of the former graph to the right side of the
178 * latter do not exist, by construction; edges from the right side
179 * of the former to the left of the latter cannot be part of any
180 * perfect matching because otherwise the left subset would not be
181 * left with enough distinct right vertices to connect to (this is
182 * exactly the same deduction used in Solo's set analysis). You can
183 * then prove (left as an exercise) that both these smaller graphs
184 * still satisfy the Hall condition, and therefore the proof will
185 * follow by induction.
187 * There's one other possibility, which is the case where _no_
188 * proper subset of the left vertices has a right neighbourhood of
189 * exactly the same size. That is, every left subset has a strictly
190 * _larger_ right neighbourhood. In this situation, we can simply
191 * remove an _arbitrary_ edge from the graph. This cannot reduce
192 * the size of any left subset's right neighbourhood by more than
193 * one, so if all neighbourhoods were strictly bigger than they
194 * needed to be initially, they must now still be _at least as big_
195 * as they need to be. So we can keep throwing out arbitrary edges
196 * until we find a set which exactly satisfies the Hall condition,
197 * and then proceed as above. []
199 * That's Hall's theorem. I now build on this by examining the
200 * circumstances in which a bipartite graph can have a _unique_
201 * perfect matching. It is clear that in the second case, where no
202 * left subset exactly satisfies the Hall condition and so we can
203 * remove an arbitrary edge, there cannot be a unique perfect
204 * matching: given one perfect matching, we choose our arbitrary
205 * removed edge to be one of those contained in it, and then we can
206 * still find a perfect matching in the remaining graph, which will
207 * be a distinct perfect matching in the original.
209 * So it is a necessary condition for a unique perfect matching
210 * that there must be at least one proper left subset which
211 * _exactly_ satisfies the Hall condition. But now consider the
212 * smaller graph constructed by taking that left subset and its
213 * neighbourhood: if the graph as a whole had a unique perfect
214 * matching, then so must this smaller one, which means we can find
215 * a proper left subset _again_, and so on. Repeating this process
216 * must eventually reduce us to a graph with only one left-side
217 * vertex (so there are no proper subsets at all); this vertex must
218 * be connected to only one right-side vertex, and hence must be so
219 * in the original graph as well (by construction). So we can
220 * discard this vertex pair from the graph, and any other edges
221 * that involved it (which will by construction be from other left
222 * vertices only), and the resulting smaller graph still has a
223 * unique perfect matching which means we can do the same thing
226 * In other words, given any bipartite graph with a unique perfect
227 * matching, we can find that matching by the following extremely
230 * - Find a left-side vertex which is only connected to one
232 * - Assign those vertices to one another, and therefore discard
233 * any other edges connecting to that right vertex.
234 * - Repeat until all vertices have been matched.
236 * This algorithm can be run in O(V+E) time (where V is the number
237 * of vertices and E is the number of edges in the graph), and the
238 * only way it can fail is if there is not a unique perfect
239 * matching (either because there is no matching at all, or because
240 * it isn't unique; but it can't distinguish those cases).
242 * Thus, the internal solver in this source file can be confident
243 * that if the tree/tent matching is uniquely determined by the
244 * tree and tent positions, it can find it using only this kind of
245 * obvious and simple operation: assign a tree to a tent if it
246 * cannot possibly belong to any other tent, and vice versa. If the
247 * solver were _only_ trying to determine the matching, even that
248 * `vice versa' wouldn't be required; but it can come in handy when
249 * not all the tents have been placed yet. I can therefore be
250 * reasonably confident that as long as my solver doesn't need to
251 * cope with grids that have a non-unique matching, it will also
252 * not need to do anything complicated like set analysis between
257 * In standalone solver mode, `verbose' is a variable which can be
258 * set by command-line option; in debugging mode it's simply always
261 #if defined STANDALONE_SOLVER
262 #define SOLVER_DIAGNOSTICS
264 #elif defined SOLVER_DIAGNOSTICS
269 * Difficulty levels. I do some macro ickery here to ensure that my
270 * enum and the various forms of my name list always match up.
272 #define DIFFLIST(A) \
275 #define ENUM(upper,title,lower) DIFF_ ## upper,
276 #define TITLE(upper,title,lower) #title,
277 #define ENCODE(upper,title,lower) #lower
278 #define CONFIG(upper,title,lower) ":" #title
279 enum { DIFFLIST(ENUM) DIFFCOUNT };
280 static char const *const tents_diffnames[] = { DIFFLIST(TITLE) };
281 static char const tents_diffchars[] = DIFFLIST(ENCODE);
282 #define DIFFCONFIG DIFFLIST(CONFIG)
297 enum { BLANK, TREE, TENT, NONTENT, MAGIC };
312 struct numbers *numbers;
313 int completed, used_solve;
316 static game_params *default_params(void)
318 game_params *ret = snew(game_params);
321 ret->diff = DIFF_EASY;
326 static const struct game_params tents_presets[] = {
330 {10, 10, DIFF_TRICKY},
332 {15, 15, DIFF_TRICKY},
335 static int game_fetch_preset(int i, char **name, game_params **params)
340 if (i < 0 || i >= lenof(tents_presets))
343 ret = snew(game_params);
344 *ret = tents_presets[i];
346 sprintf(str, "%dx%d %s", ret->w, ret->h, tents_diffnames[ret->diff]);
353 static void free_params(game_params *params)
358 static game_params *dup_params(game_params *params)
360 game_params *ret = snew(game_params);
361 *ret = *params; /* structure copy */
365 static void decode_params(game_params *params, char const *string)
367 params->w = params->h = atoi(string);
368 while (*string && isdigit((unsigned char)*string)) string++;
369 if (*string == 'x') {
371 params->h = atoi(string);
372 while (*string && isdigit((unsigned char)*string)) string++;
374 if (*string == 'd') {
377 for (i = 0; i < DIFFCOUNT; i++)
378 if (*string == tents_diffchars[i])
380 if (*string) string++;
384 static char *encode_params(game_params *params, int full)
388 sprintf(buf, "%dx%d", params->w, params->h);
390 sprintf(buf + strlen(buf), "d%c",
391 tents_diffchars[params->diff]);
395 static config_item *game_configure(game_params *params)
400 ret = snewn(4, config_item);
402 ret[0].name = "Width";
403 ret[0].type = C_STRING;
404 sprintf(buf, "%d", params->w);
405 ret[0].sval = dupstr(buf);
408 ret[1].name = "Height";
409 ret[1].type = C_STRING;
410 sprintf(buf, "%d", params->h);
411 ret[1].sval = dupstr(buf);
414 ret[2].name = "Difficulty";
415 ret[2].type = C_CHOICES;
416 ret[2].sval = DIFFCONFIG;
417 ret[2].ival = params->diff;
427 static game_params *custom_params(config_item *cfg)
429 game_params *ret = snew(game_params);
431 ret->w = atoi(cfg[0].sval);
432 ret->h = atoi(cfg[1].sval);
433 ret->diff = cfg[2].ival;
438 static char *validate_params(game_params *params, int full)
441 * Generating anything under 4x4 runs into trouble of one kind
444 if (params->w < 4 || params->h < 4)
445 return "Width and height must both be at least four";
450 * Scratch space for solver.
452 enum { N, U, L, R, D, MAXDIR }; /* link directions */
453 #define dx(d) ( ((d)==R) - ((d)==L) )
454 #define dy(d) ( ((d)==D) - ((d)==U) )
455 #define F(d) ( U + D - (d) )
456 struct solver_scratch {
457 char *links; /* mapping between trees and tents */
459 char *place, *mrows, *trows;
462 static struct solver_scratch *new_scratch(int w, int h)
464 struct solver_scratch *ret = snew(struct solver_scratch);
466 ret->links = snewn(w*h, char);
467 ret->locs = snewn(max(w, h), int);
468 ret->place = snewn(max(w, h), char);
469 ret->mrows = snewn(3 * max(w, h), char);
470 ret->trows = snewn(3 * max(w, h), char);
475 static void free_scratch(struct solver_scratch *sc)
486 * Solver. Returns 0 for impossibility, 1 for success, 2 for
487 * ambiguity or failure to converge.
489 static int tents_solve(int w, int h, const char *grid, int *numbers,
490 char *soln, struct solver_scratch *sc, int diff)
493 char *mrow, *mrow1, *mrow2, *trow, *trow1, *trow2;
496 * Set up solver data.
498 memset(sc->links, N, w*h);
501 * Set up solution array.
503 memcpy(soln, grid, w*h);
509 int done_something = FALSE;
512 * Any tent which has only one unattached tree adjacent to
513 * it can be tied to that tree.
515 for (y = 0; y < h; y++)
516 for (x = 0; x < w; x++)
517 if (soln[y*w+x] == TENT && !sc->links[y*w+x]) {
520 for (d = 1; d < MAXDIR; d++) {
521 int x2 = x + dx(d), y2 = y + dy(d);
522 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
523 soln[y2*w+x2] == TREE &&
524 !sc->links[y2*w+x2]) {
526 break; /* found more than one */
532 if (d == MAXDIR && linkd == 0) {
533 #ifdef SOLVER_DIAGNOSTICS
535 printf("tent at %d,%d cannot link to anything\n",
538 return 0; /* no solution exists */
539 } else if (d == MAXDIR) {
540 int x2 = x + dx(linkd), y2 = y + dy(linkd);
542 #ifdef SOLVER_DIAGNOSTICS
544 printf("tent at %d,%d can only link to tree at"
545 " %d,%d\n", x, y, x2, y2);
548 sc->links[y*w+x] = linkd;
549 sc->links[y2*w+x2] = F(linkd);
550 done_something = TRUE;
557 break; /* don't do anything else! */
560 * Mark a blank square as NONTENT if it is not orthogonally
561 * adjacent to any unmatched tree.
563 for (y = 0; y < h; y++)
564 for (x = 0; x < w; x++)
565 if (soln[y*w+x] == BLANK) {
566 int can_be_tent = FALSE;
568 for (d = 1; d < MAXDIR; d++) {
569 int x2 = x + dx(d), y2 = y + dy(d);
570 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
571 soln[y2*w+x2] == TREE &&
577 #ifdef SOLVER_DIAGNOSTICS
579 printf("%d,%d cannot be a tent (no adjacent"
580 " unmatched tree)\n", x, y);
582 soln[y*w+x] = NONTENT;
583 done_something = TRUE;
591 * Mark a blank square as NONTENT if it is (perhaps
592 * diagonally) adjacent to any other tent.
594 for (y = 0; y < h; y++)
595 for (x = 0; x < w; x++)
596 if (soln[y*w+x] == BLANK) {
597 int dx, dy, imposs = FALSE;
599 for (dy = -1; dy <= +1; dy++)
600 for (dx = -1; dx <= +1; dx++)
602 int x2 = x + dx, y2 = y + dy;
603 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
604 soln[y2*w+x2] == TENT)
609 #ifdef SOLVER_DIAGNOSTICS
611 printf("%d,%d cannot be a tent (adjacent tent)\n",
614 soln[y*w+x] = NONTENT;
615 done_something = TRUE;
623 * Any tree which has exactly one {unattached tent, BLANK}
624 * adjacent to it must have its tent in that square.
626 for (y = 0; y < h; y++)
627 for (x = 0; x < w; x++)
628 if (soln[y*w+x] == TREE && !sc->links[y*w+x]) {
629 int linkd = 0, linkd2 = 0, nd = 0;
631 for (d = 1; d < MAXDIR; d++) {
632 int x2 = x + dx(d), y2 = y + dy(d);
633 if (!(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h))
635 if (soln[y2*w+x2] == BLANK ||
636 (soln[y2*w+x2] == TENT && !sc->links[y2*w+x2])) {
646 #ifdef SOLVER_DIAGNOSTICS
648 printf("tree at %d,%d cannot link to anything\n",
651 return 0; /* no solution exists */
652 } else if (nd == 1) {
653 int x2 = x + dx(linkd), y2 = y + dy(linkd);
655 #ifdef SOLVER_DIAGNOSTICS
657 printf("tree at %d,%d can only link to tent at"
658 " %d,%d\n", x, y, x2, y2);
660 soln[y2*w+x2] = TENT;
661 sc->links[y*w+x] = linkd;
662 sc->links[y2*w+x2] = F(linkd);
663 done_something = TRUE;
664 } else if (nd == 2 && (!dx(linkd) != !dx(linkd2)) &&
665 diff >= DIFF_TRICKY) {
667 * If there are two possible places where
668 * this tree's tent can go, and they are
669 * diagonally separated rather than being
670 * on opposite sides of the tree, then the
671 * square (other than the tree square)
672 * which is adjacent to both of them must
675 int x2 = x + dx(linkd) + dx(linkd2);
676 int y2 = y + dy(linkd) + dy(linkd2);
677 assert(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h);
678 if (soln[y2*w+x2] == BLANK) {
679 #ifdef SOLVER_DIAGNOSTICS
681 printf("possible tent locations for tree at"
682 " %d,%d rule out tent at %d,%d\n",
685 soln[y2*w+x2] = NONTENT;
686 done_something = TRUE;
695 * If localised deductions about the trees and tents
696 * themselves haven't helped us, it's time to resort to the
697 * numbers round the grid edge. For each row and column, we
698 * go through all possible combinations of locations for
699 * the unplaced tents, rule out any which have adjacent
700 * tents, and spot any square which is given the same state
701 * by all remaining combinations.
703 for (i = 0; i < w+h; i++) {
704 int start, step, len, start1, start2, n, k;
708 * This is the number for a column.
723 * This is the number for a row.
738 if (diff < DIFF_TRICKY) {
740 * In Easy mode, we don't look at the effect of one
741 * row on the next (i.e. ruling out a square if all
742 * possibilities for an adjacent row place a tent
745 start1 = start2 = -1;
751 * Count and store the locations of the free squares,
752 * and also count the number of tents already placed.
755 for (j = 0; j < len; j++) {
756 if (soln[start+j*step] == TENT)
757 k--; /* one fewer tent to place */
758 else if (soln[start+j*step] == BLANK)
763 continue; /* nothing left to do here */
766 * Now we know we're placing k tents in n squares. Set
767 * up the first possibility.
769 for (j = 0; j < n; j++)
770 sc->place[j] = (j < k ? TENT : NONTENT);
773 * We're aiming to find squares in this row which are
774 * invariant over all valid possibilities. Thus, we
775 * maintain the current state of that invariance. We
776 * start everything off at MAGIC to indicate that it
777 * hasn't been set up yet.
780 mrow1 = sc->mrows + len;
781 mrow2 = sc->mrows + 2*len;
783 trow1 = sc->trows + len;
784 trow2 = sc->trows + 2*len;
785 memset(mrow, MAGIC, 3*len);
788 * And iterate over all possibilities.
794 * See if this possibility is valid. The only way
795 * it can fail to be valid is if it contains two
796 * adjacent tents. (Other forms of invalidity, such
797 * as containing a tent adjacent to one already
798 * placed, will have been dealt with already by
799 * other parts of the solver.)
802 for (j = 0; j+1 < n; j++)
803 if (sc->place[j] == TENT &&
804 sc->place[j+1] == TENT &&
805 sc->locs[j+1] == sc->locs[j]+1) {
812 * Merge this valid combination into mrow.
814 memset(trow, MAGIC, len);
815 memset(trow+len, BLANK, 2*len);
816 for (j = 0; j < n; j++) {
817 trow[sc->locs[j]] = sc->place[j];
818 if (sc->place[j] == TENT) {
820 for (jj = sc->locs[j]-1; jj <= sc->locs[j]+1; jj++)
821 if (jj >= 0 && jj < len)
822 trow1[jj] = trow2[jj] = NONTENT;
826 for (j = 0; j < 3*len; j++) {
827 if (trow[j] == MAGIC)
829 if (mrow[j] == MAGIC || mrow[j] == trow[j]) {
831 * Either this is the first valid
832 * placement we've found at all, or
833 * this square's contents are
834 * consistent with every previous valid
840 * This square's contents fail to match
841 * what they were in a different
842 * combination, so we cannot deduce
843 * anything about this square.
851 * Find the next combination of k choices from n.
852 * We do this by finding the rightmost tent which
853 * can be moved one place right, doing so, and
854 * shunting all tents to the right of that as far
855 * left as they can go.
858 for (j = n-1; j > 0; j--) {
859 if (sc->place[j] == TENT)
861 if (sc->place[j] == NONTENT && sc->place[j-1] == TENT) {
862 sc->place[j-1] = NONTENT;
865 sc->place[++j] = TENT;
867 sc->place[j] = NONTENT;
872 break; /* we've finished */
876 * It's just possible that _no_ placement was valid, in
877 * which case we have an internally inconsistent
880 if (mrow[sc->locs[0]] == MAGIC)
881 return 0; /* inconsistent */
884 * Now go through mrow and see if there's anything
885 * we've deduced which wasn't already mentioned in soln.
887 for (j = 0; j < len; j++) {
890 for (whichrow = 0; whichrow < 3; whichrow++) {
891 char *mthis = mrow + whichrow * len;
892 int tstart = (whichrow == 0 ? start :
893 whichrow == 1 ? start1 : start2);
895 mthis[j] != MAGIC && mthis[j] != BLANK &&
896 soln[tstart+j*step] == BLANK) {
897 int pos = tstart+j*step;
899 #ifdef SOLVER_DIAGNOSTICS
901 printf("%s %d forces %s at %d,%d\n",
902 step==1 ? "row" : "column",
903 step==1 ? start/w : start,
904 mthis[j] == TENT ? "tent" : "non-tent",
907 soln[pos] = mthis[j];
908 done_something = TRUE;
922 * The solver has nothing further it can do. Return 1 if both
923 * soln and sc->links are completely filled in, or 2 otherwise.
925 for (y = 0; y < h; y++)
926 for (x = 0; x < w; x++) {
927 if (soln[y*w+x] == BLANK)
929 if (soln[y*w+x] != NONTENT && sc->links[y*w+x] == 0)
936 static char *new_game_desc(game_params *params, random_state *rs,
937 char **aux, int interactive)
939 int w = params->w, h = params->h;
940 int ntrees = w * h / 5;
941 char *grid = snewn(w*h, char);
942 char *puzzle = snewn(w*h, char);
943 int *numbers = snewn(w+h, int);
944 char *soln = snewn(w*h, char);
945 int *temp = snewn(2*w*h, int);
946 int maxedges = ntrees*4 + w*h;
947 int *edges = snewn(2*maxedges, int);
948 int *capacity = snewn(maxedges, int);
949 int *flow = snewn(maxedges, int);
950 struct solver_scratch *sc = new_scratch(w, h);
955 * Since this puzzle has many global deductions and doesn't
956 * permit limited clue sets, generating grids for this puzzle
957 * is hard enough that I see no better option than to simply
958 * generate a solution and see if it's unique and has the
959 * required difficulty. This turns out to be computationally
962 * We chose our tree count (hence also tent count) by dividing
963 * the total grid area by five above. Why five? Well, w*h/4 is
964 * the maximum number of tents you can _possibly_ fit into the
965 * grid without violating the separation criterion, and to
966 * achieve that you are constrained to a very small set of
967 * possible layouts (the obvious one with a tent at every
968 * (even,even) coordinate, and trivial variations thereon). So
969 * if we reduce the tent count a bit more, we enable more
970 * random-looking placement; 5 turns out to be a plausible
971 * figure which yields sensible puzzles. Increasing the tent
972 * count would give puzzles whose solutions were too regimented
973 * and could be solved by the use of that knowledge (and would
974 * also take longer to find a viable placement); decreasing it
975 * would make the grids emptier and more boring.
977 * Actually generating a grid is a matter of first placing the
978 * tents, and then placing the trees by the use of maxflow
979 * (finding a distinct square adjacent to every tent). We do it
980 * this way round because otherwise satisfying the tent
981 * separation condition would become onerous: most randomly
982 * chosen tent layouts do not satisfy this condition, so we'd
983 * have gone to a lot of work before finding that a candidate
984 * layout was unusable. Instead, we place the tents first and
985 * ensure they meet the separation criterion _before_ doing
986 * lots of computation; this works much better.
988 * The maxflow algorithm is not randomised, so employed naively
989 * it would give rise to grids with clear structure and
990 * directional bias. Hence, I assign the network nodes as seen
991 * by maxflow to be a _random_ permutation of the squares of
992 * the grid, so that any bias shown by maxflow towards
993 * low-numbered nodes is turned into a random bias.
995 * This generation strategy can fail at many points, including
996 * as early as tent placement (if you get a bad random order in
997 * which to greedily try the grid squares, you won't even
998 * manage to find enough mutually non-adjacent squares to put
999 * the tents in). Then it can fail if maxflow doesn't manage to
1000 * find a good enough matching (i.e. the tent placements don't
1001 * admit any adequate tree placements); and finally it can fail
1002 * if the solver finds that the problem has the wrong
1003 * difficulty (including being actually non-unique). All of
1004 * these, however, are insufficiently frequent to cause
1008 if (params->diff > DIFF_EASY && params->w <= 4 && params->h <= 4)
1009 params->diff = DIFF_EASY; /* downgrade to prevent tight loop */
1013 * Arrange the grid squares into a random order.
1015 for (i = 0; i < w*h; i++)
1017 shuffle(temp, w*h, sizeof(*temp), rs);
1020 * The first `ntrees' entries in temp which we can get
1021 * without making two tents adjacent will be the tent
1024 memset(grid, BLANK, w*h);
1026 for (i = 0; i < w*h && j > 0; i++) {
1027 int x = temp[i] % w, y = temp[i] / w;
1028 int dy, dx, ok = TRUE;
1030 for (dy = -1; dy <= +1; dy++)
1031 for (dx = -1; dx <= +1; dx++)
1032 if (x+dx >= 0 && x+dx < w &&
1033 y+dy >= 0 && y+dy < h &&
1034 grid[(y+dy)*w+(x+dx)] == TENT)
1038 grid[temp[i]] = TENT;
1043 continue; /* couldn't place all the tents */
1046 * Now we build up the list of graph edges.
1049 for (i = 0; i < w*h; i++) {
1050 if (grid[temp[i]] == TENT) {
1051 for (j = 0; j < w*h; j++) {
1052 if (grid[temp[j]] != TENT) {
1053 int xi = temp[i] % w, yi = temp[i] / w;
1054 int xj = temp[j] % w, yj = temp[j] / w;
1055 if (abs(xi-xj) + abs(yi-yj) == 1) {
1056 edges[nedges*2] = i;
1057 edges[nedges*2+1] = j;
1058 capacity[nedges] = 1;
1065 * Special node w*h is the sink node; any non-tent node
1066 * has an edge going to it.
1068 edges[nedges*2] = i;
1069 edges[nedges*2+1] = w*h;
1070 capacity[nedges] = 1;
1076 * Special node w*h+1 is the source node, with an edge going to
1079 for (i = 0; i < w*h; i++) {
1080 if (grid[temp[i]] == TENT) {
1081 edges[nedges*2] = w*h+1;
1082 edges[nedges*2+1] = i;
1083 capacity[nedges] = 1;
1088 assert(nedges <= maxedges);
1091 * Now we're ready to call the maxflow algorithm to place the
1094 j = maxflow(w*h+2, w*h+1, w*h, nedges, edges, capacity, flow, NULL);
1097 continue; /* couldn't place all the tents */
1100 * We've placed the trees. Now we need to work out _where_
1101 * we've placed them, which is a matter of reading back out
1102 * from the `flow' array.
1104 for (i = 0; i < nedges; i++) {
1105 if (edges[2*i] < w*h && edges[2*i+1] < w*h && flow[i] > 0)
1106 grid[temp[edges[2*i+1]]] = TREE;
1110 * I think it looks ugly if there isn't at least one of
1111 * _something_ (tent or tree) in each row and each column
1112 * of the grid. This doesn't give any information away
1113 * since a completely empty row/column is instantly obvious
1114 * from the clues (it has no trees and a zero).
1116 for (i = 0; i < w; i++) {
1117 for (j = 0; j < h; j++) {
1118 if (grid[j*w+i] != BLANK)
1119 break; /* found something in this column */
1122 break; /* found empty column */
1125 continue; /* a column was empty */
1127 for (j = 0; j < h; j++) {
1128 for (i = 0; i < w; i++) {
1129 if (grid[j*w+i] != BLANK)
1130 break; /* found something in this row */
1133 break; /* found empty row */
1136 continue; /* a row was empty */
1139 * Now set up the numbers round the edge.
1141 for (i = 0; i < w; i++) {
1143 for (j = 0; j < h; j++)
1144 if (grid[j*w+i] == TENT)
1148 for (i = 0; i < h; i++) {
1150 for (j = 0; j < w; j++)
1151 if (grid[i*w+j] == TENT)
1157 * And now actually solve the puzzle, to see whether it's
1158 * unique and has the required difficulty.
1160 for (i = 0; i < w*h; i++)
1161 puzzle[i] = grid[i] == TREE ? TREE : BLANK;
1162 i = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff-1);
1163 j = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff);
1166 * We expect solving with difficulty params->diff to have
1167 * succeeded (otherwise the problem is too hard), and
1168 * solving with diff-1 to have failed (otherwise it's too
1171 if (i == 2 && j == 1)
1176 * That's it. Encode as a game ID.
1178 ret = snewn((w+h)*40 + ntrees + (w*h)/26 + 1, char);
1181 for (i = 0; i <= w*h; i++) {
1182 int c = (i < w*h ? grid[i] == TREE : 1);
1184 *p++ = (j == 0 ? '_' : j-1 + 'a');
1194 for (i = 0; i < w+h; i++)
1195 p += sprintf(p, ",%d", numbers[i]);
1197 ret = sresize(ret, p - ret, char);
1200 * And encode the solution as an aux_info.
1202 *aux = snewn(ntrees * 40, char);
1205 for (i = 0; i < w*h; i++)
1206 if (grid[i] == TENT)
1207 p += sprintf(p, ";T%d,%d", i%w, i/w);
1209 *aux = sresize(*aux, p - *aux, char);
1224 static char *validate_desc(game_params *params, char *desc)
1226 int w = params->w, h = params->h;
1230 while (*desc && *desc != ',') {
1233 else if (*desc >= 'a' && *desc < 'z')
1234 area += *desc - 'a' + 2;
1235 else if (*desc == 'z')
1237 else if (*desc == '!' || *desc == '-')
1240 return "Invalid character in grid specification";
1245 for (i = 0; i < w+h; i++) {
1247 return "Not enough numbers given after grid specification";
1248 else if (*desc != ',')
1249 return "Invalid character in number list";
1251 while (*desc && isdigit((unsigned char)*desc)) desc++;
1255 return "Unexpected additional data at end of game description";
1259 static game_state *new_game(midend *me, game_params *params, char *desc)
1261 int w = params->w, h = params->h;
1262 game_state *state = snew(game_state);
1265 state->p = *params; /* structure copy */
1266 state->grid = snewn(w*h, char);
1267 state->numbers = snew(struct numbers);
1268 state->numbers->refcount = 1;
1269 state->numbers->numbers = snewn(w+h, int);
1270 state->completed = state->used_solve = FALSE;
1273 memset(state->grid, BLANK, w*h);
1282 else if (*desc >= 'a' && *desc < 'z')
1283 run = *desc - ('a'-1);
1284 else if (*desc == 'z') {
1288 assert(*desc == '!' || *desc == '-');
1290 type = (*desc == '!' ? TENT : NONTENT);
1296 assert(i >= 0 && i <= w*h);
1298 assert(type == TREE);
1302 state->grid[i++] = type;
1306 for (i = 0; i < w+h; i++) {
1307 assert(*desc == ',');
1309 state->numbers->numbers[i] = atoi(desc);
1310 while (*desc && isdigit((unsigned char)*desc)) desc++;
1318 static game_state *dup_game(game_state *state)
1320 int w = state->p.w, h = state->p.h;
1321 game_state *ret = snew(game_state);
1323 ret->p = state->p; /* structure copy */
1324 ret->grid = snewn(w*h, char);
1325 memcpy(ret->grid, state->grid, w*h);
1326 ret->numbers = state->numbers;
1327 state->numbers->refcount++;
1328 ret->completed = state->completed;
1329 ret->used_solve = state->used_solve;
1334 static void free_game(game_state *state)
1336 if (--state->numbers->refcount <= 0) {
1337 sfree(state->numbers->numbers);
1338 sfree(state->numbers);
1344 static char *solve_game(game_state *state, game_state *currstate,
1345 char *aux, char **error)
1347 int w = state->p.w, h = state->p.h;
1351 * If we already have the solution, save ourselves some
1356 struct solver_scratch *sc = new_scratch(w, h);
1362 soln = snewn(w*h, char);
1363 ret = tents_solve(w, h, state->grid, state->numbers->numbers,
1364 soln, sc, DIFFCOUNT-1);
1369 *error = "This puzzle is not self-consistent";
1371 *error = "Unable to find a unique solution for this puzzle";
1376 * Construct a move string which turns the current state
1377 * into the solved state.
1379 move = snewn(w*h * 40, char);
1382 for (i = 0; i < w*h; i++)
1383 if (soln[i] == TENT)
1384 p += sprintf(p, ";T%d,%d", i%w, i/w);
1386 move = sresize(move, p - move, char);
1394 static int game_can_format_as_text_now(game_params *params)
1399 static char *game_text_format(game_state *state)
1401 int w = state->p.w, h = state->p.h;
1406 * FIXME: We currently do not print the numbers round the edges
1407 * of the grid. I need to work out a sensible way of doing this
1408 * even when the column numbers exceed 9.
1410 * In the absence of those numbers, the result size is h lines
1411 * of w+1 characters each, plus a NUL.
1413 * This function is currently only used by the standalone
1414 * solver; until I make it look more sensible, I won't enable
1415 * it in the main game structure.
1417 ret = snewn(h*(w+1) + 1, char);
1419 for (y = 0; y < h; y++) {
1420 for (x = 0; x < w; x++) {
1421 *p = (state->grid[y*w+x] == BLANK ? '.' :
1422 state->grid[y*w+x] == TREE ? 'T' :
1423 state->grid[y*w+x] == TENT ? '*' :
1424 state->grid[y*w+x] == NONTENT ? '-' : '?');
1435 int dsx, dsy; /* coords of drag start */
1436 int dex, dey; /* coords of drag end */
1437 int drag_button; /* -1 for none, or a button code */
1438 int drag_ok; /* dragged off the window, to cancel */
1440 int cx, cy, cdisp; /* cursor position, and ?display. */
1443 static game_ui *new_ui(game_state *state)
1445 game_ui *ui = snew(game_ui);
1446 ui->dsx = ui->dsy = -1;
1447 ui->dex = ui->dey = -1;
1448 ui->drag_button = -1;
1449 ui->drag_ok = FALSE;
1450 ui->cx = ui->cy = ui->cdisp = 0;
1454 static void free_ui(game_ui *ui)
1459 static char *encode_ui(game_ui *ui)
1464 static void decode_ui(game_ui *ui, char *encoding)
1468 static void game_changed_state(game_ui *ui, game_state *oldstate,
1469 game_state *newstate)
1473 struct game_drawstate {
1477 int *drawn, *numbersdrawn;
1478 int cx, cy; /* last-drawn cursor pos, or (-1,-1) if absent. */
1481 #define PREFERRED_TILESIZE 32
1482 #define TILESIZE (ds->tilesize)
1483 #define TLBORDER (TILESIZE/2)
1484 #define BRBORDER (TILESIZE*3/2)
1485 #define COORD(x) ( (x) * TILESIZE + TLBORDER )
1486 #define FROMCOORD(x) ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 )
1488 #define FLASH_TIME 0.30F
1490 static int drag_xform(game_ui *ui, int x, int y, int v)
1492 int xmin, ymin, xmax, ymax;
1494 xmin = min(ui->dsx, ui->dex);
1495 xmax = max(ui->dsx, ui->dex);
1496 ymin = min(ui->dsy, ui->dey);
1497 ymax = max(ui->dsy, ui->dey);
1500 * Left-dragging has no effect, so we treat a left-drag as a
1501 * single click on dsx,dsy.
1503 if (ui->drag_button == LEFT_BUTTON) {
1504 xmin = xmax = ui->dsx;
1505 ymin = ymax = ui->dsy;
1508 if (x < xmin || x > xmax || y < ymin || y > ymax)
1509 return v; /* no change outside drag area */
1512 return v; /* trees are inviolate always */
1514 if (xmin == xmax && ymin == ymax) {
1516 * Results of a simple click. Left button sets blanks to
1517 * tents; right button sets blanks to non-tents; either
1518 * button clears a non-blank square.
1520 if (ui->drag_button == LEFT_BUTTON)
1521 v = (v == BLANK ? TENT : BLANK);
1523 v = (v == BLANK ? NONTENT : BLANK);
1526 * Results of a drag. Left-dragging has no effect.
1527 * Right-dragging sets all blank squares to non-tents and
1528 * has no effect on anything else.
1530 if (ui->drag_button == RIGHT_BUTTON)
1531 v = (v == BLANK ? NONTENT : v);
1539 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1540 int x, int y, int button)
1542 int w = state->p.w, h = state->p.h;
1545 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1548 if (x < 0 || y < 0 || x >= w || y >= h)
1551 ui->drag_button = button;
1552 ui->dsx = ui->dex = x;
1553 ui->dsy = ui->dey = y;
1556 return ""; /* ui updated */
1559 if ((IS_MOUSE_DRAG(button) || IS_MOUSE_RELEASE(button)) &&
1560 ui->drag_button > 0) {
1561 int xmin, ymin, xmax, ymax;
1563 int buflen, bufsize, tmplen;
1567 if (x < 0 || y < 0 || x >= w || y >= h) {
1568 ui->drag_ok = FALSE;
1571 * Drags are limited to one row or column. Hence, we
1572 * work out which coordinate is closer to the drag
1573 * start, and move it _to_ the drag start.
1575 if (abs(x - ui->dsx) < abs(y - ui->dsy))
1586 if (IS_MOUSE_DRAG(button))
1587 return ""; /* ui updated */
1590 * The drag has been released. Enact it.
1593 ui->drag_button = -1;
1594 return ""; /* drag was just cancelled */
1597 xmin = min(ui->dsx, ui->dex);
1598 xmax = max(ui->dsx, ui->dex);
1599 ymin = min(ui->dsy, ui->dey);
1600 ymax = max(ui->dsy, ui->dey);
1601 assert(0 <= xmin && xmin <= xmax && xmax < w);
1602 assert(0 <= ymin && ymin <= ymax && ymax < h);
1606 buf = snewn(bufsize, char);
1608 for (y = ymin; y <= ymax; y++)
1609 for (x = xmin; x <= xmax; x++) {
1610 int v = drag_xform(ui, x, y, state->grid[y*w+x]);
1611 if (state->grid[y*w+x] != v) {
1612 tmplen = sprintf(tmpbuf, "%s%c%d,%d", sep,
1613 (int)(v == BLANK ? 'B' :
1614 v == TENT ? 'T' : 'N'),
1618 if (buflen + tmplen >= bufsize) {
1619 bufsize = buflen + tmplen + 256;
1620 buf = sresize(buf, bufsize, char);
1623 strcpy(buf+buflen, tmpbuf);
1628 ui->drag_button = -1; /* drag is terminated */
1632 return ""; /* ui updated (drag was terminated) */
1639 if (IS_CURSOR_MOVE(button)) {
1640 move_cursor(button, &ui->cx, &ui->cy, w, h, 0);
1646 int v = state->grid[ui->cy*w+ui->cx];
1649 #ifdef SINGLE_CURSOR_SELECT
1650 if (button == CURSOR_SELECT)
1651 /* SELECT cycles T, N, B */
1652 rep = v == BLANK ? 'T' : v == TENT ? 'N' : 'B';
1654 if (button == CURSOR_SELECT)
1655 rep = v == BLANK ? 'T' : 'B';
1656 else if (button == CURSOR_SELECT2)
1657 rep = v == BLANK ? 'N' : 'B';
1658 else if (button == 'T' || button == 'N' || button == 'B')
1664 sprintf(tmpbuf, "%c%d,%d", (int)rep, ui->cx, ui->cy);
1665 return dupstr(tmpbuf);
1667 } else if (IS_CURSOR_SELECT(button)) {
1675 static game_state *execute_move(game_state *state, char *move)
1677 int w = state->p.w, h = state->p.h;
1679 int x, y, m, n, i, j;
1680 game_state *ret = dup_game(state);
1686 ret->used_solve = TRUE;
1688 * Set all non-tree squares to NONTENT. The rest of the
1689 * solve move will fill the tents in over the top.
1691 for (i = 0; i < w*h; i++)
1692 if (ret->grid[i] != TREE)
1693 ret->grid[i] = NONTENT;
1695 } else if (c == 'B' || c == 'T' || c == 'N') {
1697 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1698 x < 0 || y < 0 || x >= w || y >= h) {
1702 if (ret->grid[y*w+x] == TREE) {
1706 ret->grid[y*w+x] = (c == 'B' ? BLANK : c == 'T' ? TENT : NONTENT);
1721 * Check for completion.
1723 for (i = n = m = 0; i < w*h; i++) {
1724 if (ret->grid[i] == TENT)
1726 else if (ret->grid[i] == TREE)
1730 int nedges, maxedges, *edges, *capacity, *flow;
1733 * We have the right number of tents, which is a
1734 * precondition for the game being complete. Now check that
1735 * the numbers add up.
1737 for (i = 0; i < w; i++) {
1739 for (j = 0; j < h; j++)
1740 if (ret->grid[j*w+i] == TENT)
1742 if (ret->numbers->numbers[i] != n)
1743 goto completion_check_done;
1745 for (i = 0; i < h; i++) {
1747 for (j = 0; j < w; j++)
1748 if (ret->grid[i*w+j] == TENT)
1750 if (ret->numbers->numbers[w+i] != n)
1751 goto completion_check_done;
1754 * Also, check that no two tents are adjacent.
1756 for (y = 0; y < h; y++)
1757 for (x = 0; x < w; x++) {
1759 ret->grid[y*w+x] == TENT && ret->grid[y*w+x+1] == TENT)
1760 goto completion_check_done;
1762 ret->grid[y*w+x] == TENT && ret->grid[(y+1)*w+x] == TENT)
1763 goto completion_check_done;
1764 if (x+1 < w && y+1 < h) {
1765 if (ret->grid[y*w+x] == TENT &&
1766 ret->grid[(y+1)*w+(x+1)] == TENT)
1767 goto completion_check_done;
1768 if (ret->grid[(y+1)*w+x] == TENT &&
1769 ret->grid[y*w+(x+1)] == TENT)
1770 goto completion_check_done;
1775 * OK; we have the right number of tents, they match the
1776 * numeric clues, and they satisfy the non-adjacency
1777 * criterion. Finally, we need to verify that they can be
1778 * placed in a one-to-one matching with the trees such that
1779 * every tent is orthogonally adjacent to its tree.
1781 * This bit is where the hard work comes in: we have to do
1782 * it by finding such a matching using maxflow.
1784 * So we construct a network with one special source node,
1785 * one special sink node, one node per tent, and one node
1789 edges = snewn(2 * maxedges, int);
1790 capacity = snewn(maxedges, int);
1791 flow = snewn(maxedges, int);
1796 * 0..w*h trees/tents
1800 for (y = 0; y < h; y++)
1801 for (x = 0; x < w; x++)
1802 if (ret->grid[y*w+x] == TREE) {
1806 * Here we use the direction enum declared for
1807 * the solver. We make use of the fact that the
1808 * directions are declared in the order
1809 * U,L,R,D, meaning that we go through the four
1810 * neighbours of any square in numerically
1813 for (d = 1; d < MAXDIR; d++) {
1814 int x2 = x + dx(d), y2 = y + dy(d);
1815 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
1816 ret->grid[y2*w+x2] == TENT) {
1817 assert(nedges < maxedges);
1818 edges[nedges*2] = y*w+x;
1819 edges[nedges*2+1] = y2*w+x2;
1820 capacity[nedges] = 1;
1824 } else if (ret->grid[y*w+x] == TENT) {
1825 assert(nedges < maxedges);
1826 edges[nedges*2] = y*w+x;
1827 edges[nedges*2+1] = w*h+1; /* edge going to sink */
1828 capacity[nedges] = 1;
1831 for (y = 0; y < h; y++)
1832 for (x = 0; x < w; x++)
1833 if (ret->grid[y*w+x] == TREE) {
1834 assert(nedges < maxedges);
1835 edges[nedges*2] = w*h; /* edge coming from source */
1836 edges[nedges*2+1] = y*w+x;
1837 capacity[nedges] = 1;
1840 n = maxflow(w*h+2, w*h, w*h+1, nedges, edges, capacity, flow, NULL);
1847 goto completion_check_done;
1850 * We haven't managed to fault the grid on any count. Score!
1852 ret->completed = TRUE;
1854 completion_check_done:
1859 /* ----------------------------------------------------------------------
1863 static void game_compute_size(game_params *params, int tilesize,
1866 /* fool the macros */
1867 struct dummy { int tilesize; } dummy, *ds = &dummy;
1868 dummy.tilesize = tilesize;
1870 *x = TLBORDER + BRBORDER + TILESIZE * params->w;
1871 *y = TLBORDER + BRBORDER + TILESIZE * params->h;
1874 static void game_set_size(drawing *dr, game_drawstate *ds,
1875 game_params *params, int tilesize)
1877 ds->tilesize = tilesize;
1880 static float *game_colours(frontend *fe, int *ncolours)
1882 float *ret = snewn(3 * NCOLOURS, float);
1884 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1886 ret[COL_GRID * 3 + 0] = 0.0F;
1887 ret[COL_GRID * 3 + 1] = 0.0F;
1888 ret[COL_GRID * 3 + 2] = 0.0F;
1890 ret[COL_GRASS * 3 + 0] = 0.7F;
1891 ret[COL_GRASS * 3 + 1] = 1.0F;
1892 ret[COL_GRASS * 3 + 2] = 0.5F;
1894 ret[COL_TREETRUNK * 3 + 0] = 0.6F;
1895 ret[COL_TREETRUNK * 3 + 1] = 0.4F;
1896 ret[COL_TREETRUNK * 3 + 2] = 0.0F;
1898 ret[COL_TREELEAF * 3 + 0] = 0.0F;
1899 ret[COL_TREELEAF * 3 + 1] = 0.7F;
1900 ret[COL_TREELEAF * 3 + 2] = 0.0F;
1902 ret[COL_TENT * 3 + 0] = 0.8F;
1903 ret[COL_TENT * 3 + 1] = 0.7F;
1904 ret[COL_TENT * 3 + 2] = 0.0F;
1906 ret[COL_ERROR * 3 + 0] = 1.0F;
1907 ret[COL_ERROR * 3 + 1] = 0.0F;
1908 ret[COL_ERROR * 3 + 2] = 0.0F;
1910 ret[COL_ERRTEXT * 3 + 0] = 1.0F;
1911 ret[COL_ERRTEXT * 3 + 1] = 1.0F;
1912 ret[COL_ERRTEXT * 3 + 2] = 1.0F;
1914 ret[COL_ERRTRUNK * 3 + 0] = 0.6F;
1915 ret[COL_ERRTRUNK * 3 + 1] = 0.0F;
1916 ret[COL_ERRTRUNK * 3 + 2] = 0.0F;
1918 *ncolours = NCOLOURS;
1922 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1924 int w = state->p.w, h = state->p.h;
1925 struct game_drawstate *ds = snew(struct game_drawstate);
1929 ds->started = FALSE;
1930 ds->p = state->p; /* structure copy */
1931 ds->drawn = snewn(w*h, int);
1932 for (i = 0; i < w*h; i++)
1933 ds->drawn[i] = MAGIC;
1934 ds->numbersdrawn = snewn(w+h, int);
1935 for (i = 0; i < w+h; i++)
1936 ds->numbersdrawn[i] = 2;
1937 ds->cx = ds->cy = -1;
1942 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1945 sfree(ds->numbersdrawn);
1950 ERR_ADJ_TOPLEFT = 4,
1961 static int *find_errors(game_state *state, char *grid)
1963 int w = state->p.w, h = state->p.h;
1964 int *ret = snewn(w*h + w + h, int);
1965 int *tmp = snewn(w*h*2, int), *dsf = tmp + w*h;
1969 * ret[0] through to ret[w*h-1] give error markers for the grid
1970 * squares. After that, ret[w*h] to ret[w*h+w-1] give error
1971 * markers for the column numbers, and ret[w*h+w] to
1972 * ret[w*h+w+h-1] for the row numbers.
1976 * Spot tent-adjacency violations.
1978 for (x = 0; x < w*h; x++)
1980 for (y = 0; y < h; y++) {
1981 for (x = 0; x < w; x++) {
1982 if (y+1 < h && x+1 < w &&
1983 ((grid[y*w+x] == TENT &&
1984 grid[(y+1)*w+(x+1)] == TENT) ||
1985 (grid[(y+1)*w+x] == TENT &&
1986 grid[y*w+(x+1)] == TENT))) {
1987 ret[y*w+x] |= 1 << ERR_ADJ_BOTRIGHT;
1988 ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOPRIGHT;
1989 ret[y*w+(x+1)] |= 1 << ERR_ADJ_BOTLEFT;
1990 ret[(y+1)*w+(x+1)] |= 1 << ERR_ADJ_TOPLEFT;
1993 grid[y*w+x] == TENT &&
1994 grid[(y+1)*w+x] == TENT) {
1995 ret[y*w+x] |= 1 << ERR_ADJ_BOT;
1996 ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOP;
1999 grid[y*w+x] == TENT &&
2000 grid[y*w+(x+1)] == TENT) {
2001 ret[y*w+x] |= 1 << ERR_ADJ_RIGHT;
2002 ret[y*w+(x+1)] |= 1 << ERR_ADJ_LEFT;
2008 * Spot numeric clue violations.
2010 for (x = 0; x < w; x++) {
2011 int tents = 0, maybetents = 0;
2012 for (y = 0; y < h; y++) {
2013 if (grid[y*w+x] == TENT)
2015 else if (grid[y*w+x] == BLANK)
2018 ret[w*h+x] = (tents > state->numbers->numbers[x] ||
2019 tents + maybetents < state->numbers->numbers[x]);
2021 for (y = 0; y < h; y++) {
2022 int tents = 0, maybetents = 0;
2023 for (x = 0; x < w; x++) {
2024 if (grid[y*w+x] == TENT)
2026 else if (grid[y*w+x] == BLANK)
2029 ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] ||
2030 tents + maybetents < state->numbers->numbers[w+y]);
2034 * Identify groups of tents with too few trees between them,
2035 * which we do by constructing the connected components of the
2036 * bipartite adjacency graph between tents and trees
2037 * ('bipartite' in the sense that we deliberately ignore
2038 * adjacency between tents or between trees), and highlighting
2039 * all the tents in any component which has a smaller tree
2043 /* Construct the equivalence classes. */
2044 for (y = 0; y < h; y++) {
2045 for (x = 0; x < w-1; x++) {
2046 if ((grid[y*w+x] == TREE && grid[y*w+x+1] == TENT) ||
2047 (grid[y*w+x] == TENT && grid[y*w+x+1] == TREE))
2048 dsf_merge(dsf, y*w+x, y*w+x+1);
2051 for (y = 0; y < h-1; y++) {
2052 for (x = 0; x < w; x++) {
2053 if ((grid[y*w+x] == TREE && grid[(y+1)*w+x] == TENT) ||
2054 (grid[y*w+x] == TENT && grid[(y+1)*w+x] == TREE))
2055 dsf_merge(dsf, y*w+x, (y+1)*w+x);
2058 /* Count up the tent/tree difference in each one. */
2059 for (x = 0; x < w*h; x++)
2061 for (x = 0; x < w*h; x++) {
2062 y = dsf_canonify(dsf, x);
2063 if (grid[x] == TREE)
2065 else if (grid[x] == TENT)
2068 /* And highlight any tent belonging to an equivalence class with
2069 * a score less than zero. */
2070 for (x = 0; x < w*h; x++) {
2071 y = dsf_canonify(dsf, x);
2072 if (grid[x] == TENT && tmp[y] < 0)
2073 ret[x] |= 1 << ERR_OVERCOMMITTED;
2077 * Identify groups of trees with too few tents between them.
2078 * This is done similarly, except that we now count BLANK as
2079 * equivalent to TENT, i.e. we only highlight such trees when
2080 * the user hasn't even left _room_ to provide tents for them
2081 * all. (Otherwise, we'd highlight all trees red right at the
2082 * start of the game, before the user had done anything wrong!)
2084 #define TENT(x) ((x)==TENT || (x)==BLANK)
2086 /* Construct the equivalence classes. */
2087 for (y = 0; y < h; y++) {
2088 for (x = 0; x < w-1; x++) {
2089 if ((grid[y*w+x] == TREE && TENT(grid[y*w+x+1])) ||
2090 (TENT(grid[y*w+x]) && grid[y*w+x+1] == TREE))
2091 dsf_merge(dsf, y*w+x, y*w+x+1);
2094 for (y = 0; y < h-1; y++) {
2095 for (x = 0; x < w; x++) {
2096 if ((grid[y*w+x] == TREE && TENT(grid[(y+1)*w+x])) ||
2097 (TENT(grid[y*w+x]) && grid[(y+1)*w+x] == TREE))
2098 dsf_merge(dsf, y*w+x, (y+1)*w+x);
2101 /* Count up the tent/tree difference in each one. */
2102 for (x = 0; x < w*h; x++)
2104 for (x = 0; x < w*h; x++) {
2105 y = dsf_canonify(dsf, x);
2106 if (grid[x] == TREE)
2108 else if (TENT(grid[x]))
2111 /* And highlight any tree belonging to an equivalence class with
2112 * a score more than zero. */
2113 for (x = 0; x < w*h; x++) {
2114 y = dsf_canonify(dsf, x);
2115 if (grid[x] == TREE && tmp[y] > 0)
2116 ret[x] |= 1 << ERR_OVERCOMMITTED;
2124 static void draw_err_adj(drawing *dr, game_drawstate *ds, int x, int y)
2132 coords[0] = x - TILESIZE*2/5;
2135 coords[3] = y - TILESIZE*2/5;
2136 coords[4] = x + TILESIZE*2/5;
2139 coords[7] = y + TILESIZE*2/5;
2140 draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
2143 * Draw an exclamation mark in the diamond. This turns out to
2144 * look unpleasantly off-centre if done via draw_text, so I do
2145 * it by hand on the basis that exclamation marks aren't that
2146 * difficult to draw...
2149 yext = TILESIZE*2/5 - (xext*2+2);
2150 draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
2152 draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
2155 static void draw_tile(drawing *dr, game_drawstate *ds,
2156 int x, int y, int v, int cur, int printing)
2159 int tx = COORD(x), ty = COORD(y);
2160 int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2;
2165 clip(dr, tx, ty, TILESIZE, TILESIZE);
2168 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, COL_GRID);
2169 draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1,
2170 (v == BLANK ? COL_BACKGROUND : COL_GRASS));
2176 (printing ? draw_rect_outline : draw_rect)
2177 (dr, cx-TILESIZE/15, ty+TILESIZE*3/10,
2178 2*(TILESIZE/15)+1, (TILESIZE*9/10 - TILESIZE*3/10),
2179 (err & (1<<ERR_OVERCOMMITTED) ? COL_ERRTRUNK : COL_TREETRUNK));
2181 for (i = 0; i < (printing ? 2 : 1); i++) {
2182 int col = (i == 1 ? COL_BACKGROUND :
2183 (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR :
2185 int sub = i * (TILESIZE/32);
2186 draw_circle(dr, cx, ty+TILESIZE*4/10, TILESIZE/4 - sub,
2188 draw_circle(dr, cx+TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
2190 draw_circle(dr, cx-TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
2192 draw_circle(dr, cx+TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
2194 draw_circle(dr, cx-TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
2197 } else if (v == TENT) {
2200 coords[0] = cx - TILESIZE/3;
2201 coords[1] = cy + TILESIZE/3;
2202 coords[2] = cx + TILESIZE/3;
2203 coords[3] = cy + TILESIZE/3;
2205 coords[5] = cy - TILESIZE/3;
2206 col = (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : COL_TENT);
2207 draw_polygon(dr, coords, 3, (printing ? -1 : col), col);
2210 if (err & (1 << ERR_ADJ_TOPLEFT))
2211 draw_err_adj(dr, ds, tx, ty);
2212 if (err & (1 << ERR_ADJ_TOP))
2213 draw_err_adj(dr, ds, tx+TILESIZE/2, ty);
2214 if (err & (1 << ERR_ADJ_TOPRIGHT))
2215 draw_err_adj(dr, ds, tx+TILESIZE, ty);
2216 if (err & (1 << ERR_ADJ_LEFT))
2217 draw_err_adj(dr, ds, tx, ty+TILESIZE/2);
2218 if (err & (1 << ERR_ADJ_RIGHT))
2219 draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE/2);
2220 if (err & (1 << ERR_ADJ_BOTLEFT))
2221 draw_err_adj(dr, ds, tx, ty+TILESIZE);
2222 if (err & (1 << ERR_ADJ_BOT))
2223 draw_err_adj(dr, ds, tx+TILESIZE/2, ty+TILESIZE);
2224 if (err & (1 << ERR_ADJ_BOTRIGHT))
2225 draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE);
2228 int coff = TILESIZE/8;
2229 draw_rect_outline(dr, tx + coff, ty + coff,
2230 TILESIZE - coff*2 + 1, TILESIZE - coff*2 + 1,
2235 draw_update(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
2239 * Internal redraw function, used for printing as well as drawing.
2241 static void int_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2242 game_state *state, int dir, game_ui *ui,
2243 float animtime, float flashtime, int printing)
2245 int w = state->p.w, h = state->p.h;
2247 int cx = -1, cy = -1;
2253 if (ui->cdisp) { cx = ui->cx; cy = ui->cy; }
2254 if (cx != ds->cx || cy != ds->cy) cmoved = 1;
2257 if (printing || !ds->started) {
2260 game_compute_size(&state->p, TILESIZE, &ww, &wh);
2261 draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
2262 draw_update(dr, 0, 0, ww, wh);
2267 print_line_width(dr, TILESIZE/64);
2272 for (y = 0; y <= h; y++)
2273 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), COL_GRID);
2274 for (x = 0; x <= w; x++)
2275 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), COL_GRID);
2279 flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
2284 * Find errors. For this we use _part_ of the information from a
2285 * currently active drag: we transform dsx,dsy but not anything
2286 * else. (This seems to strike a good compromise between having
2287 * the error highlights respond instantly to single clicks, but
2288 * not give constant feedback during a right-drag.)
2290 if (ui && ui->drag_button >= 0) {
2291 tmpgrid = snewn(w*h, char);
2292 memcpy(tmpgrid, state->grid, w*h);
2293 tmpgrid[ui->dsy * w + ui->dsx] =
2294 drag_xform(ui, ui->dsx, ui->dsy, tmpgrid[ui->dsy * w + ui->dsx]);
2295 errors = find_errors(state, tmpgrid);
2298 errors = find_errors(state, state->grid);
2304 for (y = 0; y < h; y++) {
2305 for (x = 0; x < w; x++) {
2306 int v = state->grid[y*w+x];
2310 * We deliberately do not take drag_ok into account
2311 * here, because user feedback suggests that it's
2312 * marginally nicer not to have the drag effects
2313 * flickering on and off disconcertingly.
2315 if (ui && ui->drag_button >= 0)
2316 v = drag_xform(ui, x, y, v);
2318 if (flashing && (v == TREE || v == TENT))
2322 if ((x == cx && y == cy) ||
2323 (x == ds->cx && y == ds->cy)) credraw = 1;
2328 if (printing || ds->drawn[y*w+x] != v || credraw) {
2329 draw_tile(dr, ds, x, y, v, (x == cx && y == cy), printing);
2331 ds->drawn[y*w+x] = v;
2337 * Draw (or redraw, if their error-highlighted state has
2338 * changed) the numbers.
2340 for (x = 0; x < w; x++) {
2341 if (ds->numbersdrawn[x] != errors[w*h+x]) {
2343 draw_rect(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1,
2345 sprintf(buf, "%d", state->numbers->numbers[x]);
2346 draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1),
2347 FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL,
2348 (errors[w*h+x] ? COL_ERROR : COL_GRID), buf);
2349 draw_update(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1);
2350 ds->numbersdrawn[x] = errors[w*h+x];
2353 for (y = 0; y < h; y++) {
2354 if (ds->numbersdrawn[w+y] != errors[w*h+w+y]) {
2356 draw_rect(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE,
2358 sprintf(buf, "%d", state->numbers->numbers[w+y]);
2359 draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2,
2360 FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE,
2361 (errors[w*h+w+y] ? COL_ERROR : COL_GRID), buf);
2362 draw_update(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE);
2363 ds->numbersdrawn[w+y] = errors[w*h+w+y];
2375 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2376 game_state *state, int dir, game_ui *ui,
2377 float animtime, float flashtime)
2379 int_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, FALSE);
2382 static float game_anim_length(game_state *oldstate, game_state *newstate,
2383 int dir, game_ui *ui)
2388 static float game_flash_length(game_state *oldstate, game_state *newstate,
2389 int dir, game_ui *ui)
2391 if (!oldstate->completed && newstate->completed &&
2392 !oldstate->used_solve && !newstate->used_solve)
2398 static int game_timing_state(game_state *state, game_ui *ui)
2403 static void game_print_size(game_params *params, float *x, float *y)
2408 * I'll use 6mm squares by default.
2410 game_compute_size(params, 600, &pw, &ph);
2415 static void game_print(drawing *dr, game_state *state, int tilesize)
2419 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2420 game_drawstate ads, *ds = &ads;
2421 game_set_size(dr, ds, NULL, tilesize);
2423 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
2424 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
2425 c = print_mono_colour(dr, 1); assert(c == COL_GRASS);
2426 c = print_mono_colour(dr, 0); assert(c == COL_TREETRUNK);
2427 c = print_mono_colour(dr, 0); assert(c == COL_TREELEAF);
2428 c = print_mono_colour(dr, 0); assert(c == COL_TENT);
2430 int_redraw(dr, ds, NULL, state, +1, NULL, 0.0F, 0.0F, TRUE);
2434 #define thegame tents
2437 const struct game thegame = {
2438 "Tents", "games.tents", "tents",
2445 TRUE, game_configure, custom_params,
2453 FALSE, game_can_format_as_text_now, game_text_format,
2461 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2464 game_free_drawstate,
2468 TRUE, FALSE, game_print_size, game_print,
2469 FALSE, /* wants_statusbar */
2470 FALSE, game_timing_state,
2471 REQUIRE_RBUTTON, /* flags */
2474 #ifdef STANDALONE_SOLVER
2478 int main(int argc, char **argv)
2482 char *id = NULL, *desc, *err;
2484 int ret, diff, really_verbose = FALSE;
2485 struct solver_scratch *sc;
2487 while (--argc > 0) {
2489 if (!strcmp(p, "-v")) {
2490 really_verbose = TRUE;
2491 } else if (!strcmp(p, "-g")) {
2493 } else if (*p == '-') {
2494 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2502 fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2506 desc = strchr(id, ':');
2508 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2513 p = default_params();
2514 decode_params(p, id);
2515 err = validate_desc(p, desc);
2517 fprintf(stderr, "%s: %s\n", argv[0], err);
2520 s = new_game(NULL, p, desc);
2521 s2 = new_game(NULL, p, desc);
2523 sc = new_scratch(p->w, p->h);
2526 * When solving an Easy puzzle, we don't want to bother the
2527 * user with Hard-level deductions. For this reason, we grade
2528 * the puzzle internally before doing anything else.
2530 ret = -1; /* placate optimiser */
2531 for (diff = 0; diff < DIFFCOUNT; diff++) {
2532 ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
2533 s2->grid, sc, diff);
2538 if (diff == DIFFCOUNT) {
2540 printf("Difficulty rating: too hard to solve internally\n");
2542 printf("Unable to find a unique solution\n");
2546 printf("Difficulty rating: impossible (no solution exists)\n");
2548 printf("Difficulty rating: %s\n", tents_diffnames[diff]);
2550 verbose = really_verbose;
2551 ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
2552 s2->grid, sc, diff);
2554 printf("Puzzle is inconsistent\n");
2556 fputs(game_text_format(s2), stdout);
2565 /* vim: set shiftwidth=4 tabstop=8: */