2 * tents.c: Puzzle involving placing tents next to trees subject to
3 * some confusing conditions.
7 * - it might be nice to make setter-provided tent/nontent clues
9 * * on the other hand, this would introduce considerable extra
10 * complexity and size into the game state; also inviolable
11 * clues would have to be marked as such somehow, in an
12 * intrusive and annoying manner. Since they're never
13 * generated by _my_ generator, I'm currently more inclined
16 * - more difficult levels at the top end?
17 * * for example, sometimes we can deduce that two BLANKs in
18 * the same row are each adjacent to the same unattached tree
19 * and to nothing else, implying that they can't both be
20 * tents; this enables us to rule out some extra combinations
21 * in the row-based deduction loop, and hence deduce more
22 * from the number in that row than we could otherwise do.
23 * * that by itself doesn't seem worth implementing a new
24 * difficulty level for, but if I can find a few more things
25 * like that then it might become worthwhile.
26 * * I wonder if there's a sensible heuristic for where to
27 * guess which would make a recursive solver viable?
44 * The rules of this puzzle as available on the WWW are poorly
45 * specified. The bits about tents having to be orthogonally
46 * adjacent to trees, tents not being even diagonally adjacent to
47 * one another, and the number of tents in each row and column
48 * being given are simple enough; the difficult bit is the
49 * tent-to-tree matching.
51 * Some sources use simplistic wordings such as `each tree is
52 * exactly connected to only one tent', which is extremely unclear:
53 * it's easy to read erroneously as `each tree is _orthogonally
54 * adjacent_ to exactly one tent', which is definitely incorrect.
55 * Even the most coherent sources I've found don't do a much better
56 * job of stating the rule.
58 * A more precise statement of the rule is that it must be possible
59 * to find a bijection f between tents and trees such that each
60 * tree T is orthogonally adjacent to the tent f(T), but that a
61 * tent is permitted to be adjacent to other trees in addition to
62 * its own. This slightly non-obvious criterion is what gives this
63 * puzzle most of its subtlety.
65 * However, there's a particularly subtle ambiguity left over. Is
66 * the bijection between tents and trees required to be _unique_?
67 * In other words, is that bijection conceptually something the
68 * player should be able to exhibit as part of the solution (even
69 * if they aren't actually required to do so)? Or is it sufficient
70 * to have a unique _placement_ of the tents which gives rise to at
71 * least one suitable bijection?
73 * The puzzle shown to the right of this .T. 2 *T* 2
74 * paragraph illustrates the problem. There T.T 0 -> T-T 0
75 * are two distinct bijections available. .T. 2 *T* 2
76 * The answer to the above question will
77 * determine whether it's a valid puzzle. 202 202
79 * This is an important question, because it affects both the
80 * player and the generator. Eventually I found all the instances
81 * of this puzzle I could Google up, solved them all by hand, and
82 * verified that in all cases the tree/tent matching was uniquely
83 * determined given the tree and tent positions. Therefore, the
84 * puzzle as implemented in this source file takes the following
87 * - When checking a user-supplied solution for correctness, only
88 * verify that there exists _at least_ one matching.
89 * - When generating a puzzle, enforce that there must be
92 * Algorithmic implications
93 * ------------------------
95 * Another way of phrasing the tree/tent matching criterion is to
96 * say that the bipartite adjacency graph between trees and tents
97 * has a perfect matching. That is, if you construct a graph which
98 * has a vertex per tree and a vertex per tent, and an edge between
99 * any tree and tent which are orthogonally adjacent, it is
100 * possible to find a set of N edges of that graph (where N is the
101 * number of trees and also the number of tents) which between them
102 * connect every tree to every tent.
104 * The most efficient known algorithms for finding such a matching
105 * given a graph, as far as I'm aware, are the Munkres assignment
106 * algorithm (also known as the Hungarian algorithm) and the
107 * Ford-Fulkerson algorithm (for finding optimal flows in
108 * networks). Each of these takes O(N^3) running time; so we're
109 * talking O(N^3) time to verify any candidate solution to this
110 * puzzle. That's just about OK if you're doing it once per mouse
111 * click (and in fact not even that, since the sensible thing to do
112 * is check all the _other_ puzzle criteria and only wade into this
113 * quagmire if none are violated); but if the solver had to keep
114 * doing N^3 work internally, then it would probably end up with
115 * more like N^5 or N^6 running time, and grid generation would
116 * become very clunky.
118 * Fortunately, I've been able to prove a very useful property of
119 * _unique_ perfect matchings, by adapting the proof of Hall's
120 * Marriage Theorem. For those unaware of Hall's Theorem, I'll
121 * recap it and its proof: it states that a bipartite graph
122 * contains a perfect matching iff every set of vertices on the
123 * left side of the graph have a neighbourhood _at least_ as big on
126 * This condition is obviously satisfied if a perfect matching does
127 * exist; each left-side node has a distinct right-side node which
128 * is the one assigned to it by the matching, and thus any set of n
129 * left vertices must have a combined neighbourhood containing at
130 * least the n corresponding right vertices, and possibly others
131 * too. Alternatively, imagine if you had (say) three left-side
132 * nodes all of which were connected to only two right-side nodes
133 * between them: any perfect matching would have to assign one of
134 * those two right nodes to each of the three left nodes, and still
135 * give the three left nodes a different right node each. This is
136 * of course impossible.
138 * To prove the converse (that if every subset of left vertices
139 * satisfies the Hall condition then a perfect matching exists),
140 * consider trying to find a proper subset of the left vertices
141 * which _exactly_ satisfies the Hall condition: that is, its right
142 * neighbourhood is precisely the same size as it. If we can find
143 * such a subset, then we can split the bipartite graph into two
144 * smaller ones: one consisting of the left subset and its right
145 * neighbourhood, the other consisting of everything else. Edges
146 * from the left side of the former graph to the right side of the
147 * latter do not exist, by construction; edges from the right side
148 * of the former to the left of the latter cannot be part of any
149 * perfect matching because otherwise the left subset would not be
150 * left with enough distinct right vertices to connect to (this is
151 * exactly the same deduction used in Solo's set analysis). You can
152 * then prove (left as an exercise) that both these smaller graphs
153 * still satisfy the Hall condition, and therefore the proof will
154 * follow by induction.
156 * There's one other possibility, which is the case where _no_
157 * proper subset of the left vertices has a right neighbourhood of
158 * exactly the same size. That is, every left subset has a strictly
159 * _larger_ right neighbourhood. In this situation, we can simply
160 * remove an _arbitrary_ edge from the graph. This cannot reduce
161 * the size of any left subset's right neighbourhood by more than
162 * one, so if all neighbourhoods were strictly bigger than they
163 * needed to be initially, they must now still be _at least as big_
164 * as they need to be. So we can keep throwing out arbitrary edges
165 * until we find a set which exactly satisfies the Hall condition,
166 * and then proceed as above. []
168 * That's Hall's theorem. I now build on this by examining the
169 * circumstances in which a bipartite graph can have a _unique_
170 * perfect matching. It is clear that in the second case, where no
171 * left subset exactly satisfies the Hall condition and so we can
172 * remove an arbitrary edge, there cannot be a unique perfect
173 * matching: given one perfect matching, we choose our arbitrary
174 * removed edge to be one of those contained in it, and then we can
175 * still find a perfect matching in the remaining graph, which will
176 * be a distinct perfect matching in the original.
178 * So it is a necessary condition for a unique perfect matching
179 * that there must be at least one proper left subset which
180 * _exactly_ satisfies the Hall condition. But now consider the
181 * smaller graph constructed by taking that left subset and its
182 * neighbourhood: if the graph as a whole had a unique perfect
183 * matching, then so must this smaller one, which means we can find
184 * a proper left subset _again_, and so on. Repeating this process
185 * must eventually reduce us to a graph with only one left-side
186 * vertex (so there are no proper subsets at all); this vertex must
187 * be connected to only one right-side vertex, and hence must be so
188 * in the original graph as well (by construction). So we can
189 * discard this vertex pair from the graph, and any other edges
190 * that involved it (which will by construction be from other left
191 * vertices only), and the resulting smaller graph still has a
192 * unique perfect matching which means we can do the same thing
195 * In other words, given any bipartite graph with a unique perfect
196 * matching, we can find that matching by the following extremely
199 * - Find a left-side vertex which is only connected to one
201 * - Assign those vertices to one another, and therefore discard
202 * any other edges connecting to that right vertex.
203 * - Repeat until all vertices have been matched.
205 * This algorithm can be run in O(V+E) time (where V is the number
206 * of vertices and E is the number of edges in the graph), and the
207 * only way it can fail is if there is not a unique perfect
208 * matching (either because there is no matching at all, or because
209 * it isn't unique; but it can't distinguish those cases).
211 * Thus, the internal solver in this source file can be confident
212 * that if the tree/tent matching is uniquely determined by the
213 * tree and tent positions, it can find it using only this kind of
214 * obvious and simple operation: assign a tree to a tent if it
215 * cannot possibly belong to any other tent, and vice versa. If the
216 * solver were _only_ trying to determine the matching, even that
217 * `vice versa' wouldn't be required; but it can come in handy when
218 * not all the tents have been placed yet. I can therefore be
219 * reasonably confident that as long as my solver doesn't need to
220 * cope with grids that have a non-unique matching, it will also
221 * not need to do anything complicated like set analysis between
226 * In standalone solver mode, `verbose' is a variable which can be
227 * set by command-line option; in debugging mode it's simply always
230 #if defined STANDALONE_SOLVER
231 #define SOLVER_DIAGNOSTICS
233 #elif defined SOLVER_DIAGNOSTICS
238 * Difficulty levels. I do some macro ickery here to ensure that my
239 * enum and the various forms of my name list always match up.
241 #define DIFFLIST(A) \
244 #define ENUM(upper,title,lower) DIFF_ ## upper,
245 #define TITLE(upper,title,lower) #title,
246 #define ENCODE(upper,title,lower) #lower
247 #define CONFIG(upper,title,lower) ":" #title
248 enum { DIFFLIST(ENUM
) DIFFCOUNT
};
249 static char const *const tents_diffnames
[] = { DIFFLIST(TITLE
) };
250 static char const tents_diffchars
[] = DIFFLIST(ENCODE
);
251 #define DIFFCONFIG DIFFLIST(CONFIG)
266 enum { BLANK
, TREE
, TENT
, NONTENT
, MAGIC
};
281 struct numbers
*numbers
;
282 int completed
, used_solve
;
285 static game_params
*default_params(void)
287 game_params
*ret
= snew(game_params
);
290 ret
->diff
= DIFF_EASY
;
295 static const struct game_params tents_presets
[] = {
299 {10, 10, DIFF_TRICKY
},
301 {15, 15, DIFF_TRICKY
},
304 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
309 if (i
< 0 || i
>= lenof(tents_presets
))
312 ret
= snew(game_params
);
313 *ret
= tents_presets
[i
];
315 sprintf(str
, "%dx%d %s", ret
->w
, ret
->h
, tents_diffnames
[ret
->diff
]);
322 static void free_params(game_params
*params
)
327 static game_params
*dup_params(game_params
*params
)
329 game_params
*ret
= snew(game_params
);
330 *ret
= *params
; /* structure copy */
334 static void decode_params(game_params
*params
, char const *string
)
336 params
->w
= params
->h
= atoi(string
);
337 while (*string
&& isdigit((unsigned char)*string
)) string
++;
338 if (*string
== 'x') {
340 params
->h
= atoi(string
);
341 while (*string
&& isdigit((unsigned char)*string
)) string
++;
343 if (*string
== 'd') {
346 for (i
= 0; i
< DIFFCOUNT
; i
++)
347 if (*string
== tents_diffchars
[i
])
349 if (*string
) string
++;
353 static char *encode_params(game_params
*params
, int full
)
357 sprintf(buf
, "%dx%d", params
->w
, params
->h
);
359 sprintf(buf
+ strlen(buf
), "d%c",
360 tents_diffchars
[params
->diff
]);
364 static config_item
*game_configure(game_params
*params
)
369 ret
= snewn(4, config_item
);
371 ret
[0].name
= "Width";
372 ret
[0].type
= C_STRING
;
373 sprintf(buf
, "%d", params
->w
);
374 ret
[0].sval
= dupstr(buf
);
377 ret
[1].name
= "Height";
378 ret
[1].type
= C_STRING
;
379 sprintf(buf
, "%d", params
->h
);
380 ret
[1].sval
= dupstr(buf
);
383 ret
[2].name
= "Difficulty";
384 ret
[2].type
= C_CHOICES
;
385 ret
[2].sval
= DIFFCONFIG
;
386 ret
[2].ival
= params
->diff
;
396 static game_params
*custom_params(config_item
*cfg
)
398 game_params
*ret
= snew(game_params
);
400 ret
->w
= atoi(cfg
[0].sval
);
401 ret
->h
= atoi(cfg
[1].sval
);
402 ret
->diff
= cfg
[2].ival
;
407 static char *validate_params(game_params
*params
, int full
)
410 * Generating anything under 4x4 runs into trouble of one kind
413 if (params
->w
< 4 || params
->h
< 4)
414 return "Width and height must both be at least four";
419 * Scratch space for solver.
421 enum { N
, U
, L
, R
, D
, MAXDIR
}; /* link directions */
422 #define dx(d) ( ((d)==R) - ((d)==L) )
423 #define dy(d) ( ((d)==D) - ((d)==U) )
424 #define F(d) ( U + D - (d) )
425 struct solver_scratch
{
426 char *links
; /* mapping between trees and tents */
428 char *place
, *mrows
, *trows
;
431 static struct solver_scratch
*new_scratch(int w
, int h
)
433 struct solver_scratch
*ret
= snew(struct solver_scratch
);
435 ret
->links
= snewn(w
*h
, char);
436 ret
->locs
= snewn(max(w
, h
), int);
437 ret
->place
= snewn(max(w
, h
), char);
438 ret
->mrows
= snewn(3 * max(w
, h
), char);
439 ret
->trows
= snewn(3 * max(w
, h
), char);
444 static void free_scratch(struct solver_scratch
*sc
)
455 * Solver. Returns 0 for impossibility, 1 for success, 2 for
456 * ambiguity or failure to converge.
458 static int tents_solve(int w
, int h
, const char *grid
, int *numbers
,
459 char *soln
, struct solver_scratch
*sc
, int diff
)
462 char *mrow
, *mrow1
, *mrow2
, *trow
, *trow1
, *trow2
;
465 * Set up solver data.
467 memset(sc
->links
, N
, w
*h
);
470 * Set up solution array.
472 memcpy(soln
, grid
, w
*h
);
478 int done_something
= FALSE
;
481 * Any tent which has only one unattached tree adjacent to
482 * it can be tied to that tree.
484 for (y
= 0; y
< h
; y
++)
485 for (x
= 0; x
< w
; x
++)
486 if (soln
[y
*w
+x
] == TENT
&& !sc
->links
[y
*w
+x
]) {
489 for (d
= 1; d
< MAXDIR
; d
++) {
490 int x2
= x
+ dx(d
), y2
= y
+ dy(d
);
491 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
&&
492 soln
[y2
*w
+x2
] == TREE
&&
493 !sc
->links
[y2
*w
+x2
]) {
495 break; /* found more than one */
501 if (d
== MAXDIR
&& linkd
== 0) {
502 #ifdef SOLVER_DIAGNOSTICS
504 printf("tent at %d,%d cannot link to anything\n",
507 return 0; /* no solution exists */
508 } else if (d
== MAXDIR
) {
509 int x2
= x
+ dx(linkd
), y2
= y
+ dy(linkd
);
511 #ifdef SOLVER_DIAGNOSTICS
513 printf("tent at %d,%d can only link to tree at"
514 " %d,%d\n", x
, y
, x2
, y2
);
517 sc
->links
[y
*w
+x
] = linkd
;
518 sc
->links
[y2
*w
+x2
] = F(linkd
);
519 done_something
= TRUE
;
526 break; /* don't do anything else! */
529 * Mark a blank square as NONTENT if it is not orthogonally
530 * adjacent to any unmatched tree.
532 for (y
= 0; y
< h
; y
++)
533 for (x
= 0; x
< w
; x
++)
534 if (soln
[y
*w
+x
] == BLANK
) {
535 int can_be_tent
= FALSE
;
537 for (d
= 1; d
< MAXDIR
; d
++) {
538 int x2
= x
+ dx(d
), y2
= y
+ dy(d
);
539 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
&&
540 soln
[y2
*w
+x2
] == TREE
&&
546 #ifdef SOLVER_DIAGNOSTICS
548 printf("%d,%d cannot be a tent (no adjacent"
549 " unmatched tree)\n", x
, y
);
551 soln
[y
*w
+x
] = NONTENT
;
552 done_something
= TRUE
;
560 * Mark a blank square as NONTENT if it is (perhaps
561 * diagonally) adjacent to any other tent.
563 for (y
= 0; y
< h
; y
++)
564 for (x
= 0; x
< w
; x
++)
565 if (soln
[y
*w
+x
] == BLANK
) {
566 int dx
, dy
, imposs
= FALSE
;
568 for (dy
= -1; dy
<= +1; dy
++)
569 for (dx
= -1; dx
<= +1; dx
++)
571 int x2
= x
+ dx
, y2
= y
+ dy
;
572 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
&&
573 soln
[y2
*w
+x2
] == TENT
)
578 #ifdef SOLVER_DIAGNOSTICS
580 printf("%d,%d cannot be a tent (adjacent tent)\n",
583 soln
[y
*w
+x
] = NONTENT
;
584 done_something
= TRUE
;
592 * Any tree which has exactly one {unattached tent, BLANK}
593 * adjacent to it must have its tent in that square.
595 for (y
= 0; y
< h
; y
++)
596 for (x
= 0; x
< w
; x
++)
597 if (soln
[y
*w
+x
] == TREE
&& !sc
->links
[y
*w
+x
]) {
598 int linkd
= 0, linkd2
= 0, nd
= 0;
600 for (d
= 1; d
< MAXDIR
; d
++) {
601 int x2
= x
+ dx(d
), y2
= y
+ dy(d
);
602 if (!(x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
))
604 if (soln
[y2
*w
+x2
] == BLANK
||
605 (soln
[y2
*w
+x2
] == TENT
&& !sc
->links
[y2
*w
+x2
])) {
615 #ifdef SOLVER_DIAGNOSTICS
617 printf("tree at %d,%d cannot link to anything\n",
620 return 0; /* no solution exists */
621 } else if (nd
== 1) {
622 int x2
= x
+ dx(linkd
), y2
= y
+ dy(linkd
);
624 #ifdef SOLVER_DIAGNOSTICS
626 printf("tree at %d,%d can only link to tent at"
627 " %d,%d\n", x
, y
, x2
, y2
);
629 soln
[y2
*w
+x2
] = TENT
;
630 sc
->links
[y
*w
+x
] = linkd
;
631 sc
->links
[y2
*w
+x2
] = F(linkd
);
632 done_something
= TRUE
;
633 } else if (nd
== 2 && (!dx(linkd
) != !dx(linkd2
)) &&
634 diff
>= DIFF_TRICKY
) {
636 * If there are two possible places where
637 * this tree's tent can go, and they are
638 * diagonally separated rather than being
639 * on opposite sides of the tree, then the
640 * square (other than the tree square)
641 * which is adjacent to both of them must
644 int x2
= x
+ dx(linkd
) + dx(linkd2
);
645 int y2
= y
+ dy(linkd
) + dy(linkd2
);
646 assert(x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
);
647 if (soln
[y2
*w
+x2
] == BLANK
) {
648 #ifdef SOLVER_DIAGNOSTICS
650 printf("possible tent locations for tree at"
651 " %d,%d rule out tent at %d,%d\n",
654 soln
[y2
*w
+x2
] = NONTENT
;
655 done_something
= TRUE
;
664 * If localised deductions about the trees and tents
665 * themselves haven't helped us, it's time to resort to the
666 * numbers round the grid edge. For each row and column, we
667 * go through all possible combinations of locations for
668 * the unplaced tents, rule out any which have adjacent
669 * tents, and spot any square which is given the same state
670 * by all remaining combinations.
672 for (i
= 0; i
< w
+h
; i
++) {
673 int start
, step
, len
, start1
, start2
, n
, k
;
677 * This is the number for a column.
692 * This is the number for a row.
707 if (diff
< DIFF_TRICKY
) {
709 * In Easy mode, we don't look at the effect of one
710 * row on the next (i.e. ruling out a square if all
711 * possibilities for an adjacent row place a tent
714 start1
= start2
= -1;
720 * Count and store the locations of the free squares,
721 * and also count the number of tents already placed.
724 for (j
= 0; j
< len
; j
++) {
725 if (soln
[start
+j
*step
] == TENT
)
726 k
--; /* one fewer tent to place */
727 else if (soln
[start
+j
*step
] == BLANK
)
732 continue; /* nothing left to do here */
735 * Now we know we're placing k tents in n squares. Set
736 * up the first possibility.
738 for (j
= 0; j
< n
; j
++)
739 sc
->place
[j
] = (j
< k ? TENT
: NONTENT
);
742 * We're aiming to find squares in this row which are
743 * invariant over all valid possibilities. Thus, we
744 * maintain the current state of that invariance. We
745 * start everything off at MAGIC to indicate that it
746 * hasn't been set up yet.
749 mrow1
= sc
->mrows
+ len
;
750 mrow2
= sc
->mrows
+ 2*len
;
752 trow1
= sc
->trows
+ len
;
753 trow2
= sc
->trows
+ 2*len
;
754 memset(mrow
, MAGIC
, 3*len
);
757 * And iterate over all possibilities.
763 * See if this possibility is valid. The only way
764 * it can fail to be valid is if it contains two
765 * adjacent tents. (Other forms of invalidity, such
766 * as containing a tent adjacent to one already
767 * placed, will have been dealt with already by
768 * other parts of the solver.)
771 for (j
= 0; j
+1 < n
; j
++)
772 if (sc
->place
[j
] == TENT
&&
773 sc
->place
[j
+1] == TENT
&&
774 sc
->locs
[j
+1] == sc
->locs
[j
]+1) {
781 * Merge this valid combination into mrow.
783 memset(trow
, MAGIC
, len
);
784 memset(trow
+len
, BLANK
, 2*len
);
785 for (j
= 0; j
< n
; j
++) {
786 trow
[sc
->locs
[j
]] = sc
->place
[j
];
787 if (sc
->place
[j
] == TENT
) {
789 for (jj
= sc
->locs
[j
]-1; jj
<= sc
->locs
[j
]+1; jj
++)
790 if (jj
>= 0 && jj
< len
)
791 trow1
[jj
] = trow2
[jj
] = NONTENT
;
795 for (j
= 0; j
< 3*len
; j
++) {
796 if (trow
[j
] == MAGIC
)
798 if (mrow
[j
] == MAGIC
|| mrow
[j
] == trow
[j
]) {
800 * Either this is the first valid
801 * placement we've found at all, or
802 * this square's contents are
803 * consistent with every previous valid
809 * This square's contents fail to match
810 * what they were in a different
811 * combination, so we cannot deduce
812 * anything about this square.
820 * Find the next combination of k choices from n.
821 * We do this by finding the rightmost tent which
822 * can be moved one place right, doing so, and
823 * shunting all tents to the right of that as far
824 * left as they can go.
827 for (j
= n
-1; j
> 0; j
--) {
828 if (sc
->place
[j
] == TENT
)
830 if (sc
->place
[j
] == NONTENT
&& sc
->place
[j
-1] == TENT
) {
831 sc
->place
[j
-1] = NONTENT
;
834 sc
->place
[++j
] = TENT
;
836 sc
->place
[j
] = NONTENT
;
841 break; /* we've finished */
845 * It's just possible that _no_ placement was valid, in
846 * which case we have an internally inconsistent
849 if (mrow
[sc
->locs
[0]] == MAGIC
)
850 return 0; /* inconsistent */
853 * Now go through mrow and see if there's anything
854 * we've deduced which wasn't already mentioned in soln.
856 for (j
= 0; j
< len
; j
++) {
859 for (whichrow
= 0; whichrow
< 3; whichrow
++) {
860 char *mthis
= mrow
+ whichrow
* len
;
861 int tstart
= (whichrow
== 0 ? start
:
862 whichrow
== 1 ? start1
: start2
);
864 mthis
[j
] != MAGIC
&& mthis
[j
] != BLANK
&&
865 soln
[tstart
+j
*step
] == BLANK
) {
866 int pos
= tstart
+j
*step
;
868 #ifdef SOLVER_DIAGNOSTICS
870 printf("%s %d forces %s at %d,%d\n",
871 step
==1 ?
"row" : "column",
872 step
==1 ? start
/w
: start
,
873 mthis
[j
] == TENT ?
"tent" : "non-tent",
876 soln
[pos
] = mthis
[j
];
877 done_something
= TRUE
;
891 * The solver has nothing further it can do. Return 1 if both
892 * soln and sc->links are completely filled in, or 2 otherwise.
894 for (y
= 0; y
< h
; y
++)
895 for (x
= 0; x
< w
; x
++) {
896 if (soln
[y
*w
+x
] == BLANK
)
898 if (soln
[y
*w
+x
] != NONTENT
&& sc
->links
[y
*w
+x
] == 0)
905 static char *new_game_desc(game_params
*params
, random_state
*rs
,
906 char **aux
, int interactive
)
908 int w
= params
->w
, h
= params
->h
;
909 int ntrees
= w
* h
/ 5;
910 char *grid
= snewn(w
*h
, char);
911 char *puzzle
= snewn(w
*h
, char);
912 int *numbers
= snewn(w
+h
, int);
913 char *soln
= snewn(w
*h
, char);
914 int *temp
= snewn(2*w
*h
, int);
915 int maxedges
= ntrees
*4 + w
*h
;
916 int *edges
= snewn(2*maxedges
, int);
917 int *capacity
= snewn(maxedges
, int);
918 int *flow
= snewn(maxedges
, int);
919 struct solver_scratch
*sc
= new_scratch(w
, h
);
924 * Since this puzzle has many global deductions and doesn't
925 * permit limited clue sets, generating grids for this puzzle
926 * is hard enough that I see no better option than to simply
927 * generate a solution and see if it's unique and has the
928 * required difficulty. This turns out to be computationally
931 * We chose our tree count (hence also tent count) by dividing
932 * the total grid area by five above. Why five? Well, w*h/4 is
933 * the maximum number of tents you can _possibly_ fit into the
934 * grid without violating the separation criterion, and to
935 * achieve that you are constrained to a very small set of
936 * possible layouts (the obvious one with a tent at every
937 * (even,even) coordinate, and trivial variations thereon). So
938 * if we reduce the tent count a bit more, we enable more
939 * random-looking placement; 5 turns out to be a plausible
940 * figure which yields sensible puzzles. Increasing the tent
941 * count would give puzzles whose solutions were too regimented
942 * and could be solved by the use of that knowledge (and would
943 * also take longer to find a viable placement); decreasing it
944 * would make the grids emptier and more boring.
946 * Actually generating a grid is a matter of first placing the
947 * tents, and then placing the trees by the use of maxflow
948 * (finding a distinct square adjacent to every tent). We do it
949 * this way round because otherwise satisfying the tent
950 * separation condition would become onerous: most randomly
951 * chosen tent layouts do not satisfy this condition, so we'd
952 * have gone to a lot of work before finding that a candidate
953 * layout was unusable. Instead, we place the tents first and
954 * ensure they meet the separation criterion _before_ doing
955 * lots of computation; this works much better.
957 * The maxflow algorithm is not randomised, so employed naively
958 * it would give rise to grids with clear structure and
959 * directional bias. Hence, I assign the network nodes as seen
960 * by maxflow to be a _random_ permutation of the squares of
961 * the grid, so that any bias shown by maxflow towards
962 * low-numbered nodes is turned into a random bias.
964 * This generation strategy can fail at many points, including
965 * as early as tent placement (if you get a bad random order in
966 * which to greedily try the grid squares, you won't even
967 * manage to find enough mutually non-adjacent squares to put
968 * the tents in). Then it can fail if maxflow doesn't manage to
969 * find a good enough matching (i.e. the tent placements don't
970 * admit any adequate tree placements); and finally it can fail
971 * if the solver finds that the problem has the wrong
972 * difficulty (including being actually non-unique). All of
973 * these, however, are insufficiently frequent to cause
977 if (params
->diff
> DIFF_EASY
&& params
->w
<= 4 && params
->h
<= 4)
978 params
->diff
= DIFF_EASY
; /* downgrade to prevent tight loop */
982 * Arrange the grid squares into a random order.
984 for (i
= 0; i
< w
*h
; i
++)
986 shuffle(temp
, w
*h
, sizeof(*temp
), rs
);
989 * The first `ntrees' entries in temp which we can get
990 * without making two tents adjacent will be the tent
993 memset(grid
, BLANK
, w
*h
);
995 for (i
= 0; i
< w
*h
&& j
> 0; i
++) {
996 int x
= temp
[i
] % w
, y
= temp
[i
] / w
;
997 int dy
, dx
, ok
= TRUE
;
999 for (dy
= -1; dy
<= +1; dy
++)
1000 for (dx
= -1; dx
<= +1; dx
++)
1001 if (x
+dx
>= 0 && x
+dx
< w
&&
1002 y
+dy
>= 0 && y
+dy
< h
&&
1003 grid
[(y
+dy
)*w
+(x
+dx
)] == TENT
)
1007 grid
[temp
[i
]] = TENT
;
1012 continue; /* couldn't place all the tents */
1015 * Now we build up the list of graph edges.
1018 for (i
= 0; i
< w
*h
; i
++) {
1019 if (grid
[temp
[i
]] == TENT
) {
1020 for (j
= 0; j
< w
*h
; j
++) {
1021 if (grid
[temp
[j
]] != TENT
) {
1022 int xi
= temp
[i
] % w
, yi
= temp
[i
] / w
;
1023 int xj
= temp
[j
] % w
, yj
= temp
[j
] / w
;
1024 if (abs(xi
-xj
) + abs(yi
-yj
) == 1) {
1025 edges
[nedges
*2] = i
;
1026 edges
[nedges
*2+1] = j
;
1027 capacity
[nedges
] = 1;
1034 * Special node w*h is the sink node; any non-tent node
1035 * has an edge going to it.
1037 edges
[nedges
*2] = i
;
1038 edges
[nedges
*2+1] = w
*h
;
1039 capacity
[nedges
] = 1;
1045 * Special node w*h+1 is the source node, with an edge going to
1048 for (i
= 0; i
< w
*h
; i
++) {
1049 if (grid
[temp
[i
]] == TENT
) {
1050 edges
[nedges
*2] = w
*h
+1;
1051 edges
[nedges
*2+1] = i
;
1052 capacity
[nedges
] = 1;
1057 assert(nedges
<= maxedges
);
1060 * Now we're ready to call the maxflow algorithm to place the
1063 j
= maxflow(w
*h
+2, w
*h
+1, w
*h
, nedges
, edges
, capacity
, flow
, NULL
);
1066 continue; /* couldn't place all the tents */
1069 * We've placed the trees. Now we need to work out _where_
1070 * we've placed them, which is a matter of reading back out
1071 * from the `flow' array.
1073 for (i
= 0; i
< nedges
; i
++) {
1074 if (edges
[2*i
] < w
*h
&& edges
[2*i
+1] < w
*h
&& flow
[i
] > 0)
1075 grid
[temp
[edges
[2*i
+1]]] = TREE
;
1079 * I think it looks ugly if there isn't at least one of
1080 * _something_ (tent or tree) in each row and each column
1081 * of the grid. This doesn't give any information away
1082 * since a completely empty row/column is instantly obvious
1083 * from the clues (it has no trees and a zero).
1085 for (i
= 0; i
< w
; i
++) {
1086 for (j
= 0; j
< h
; j
++) {
1087 if (grid
[j
*w
+i
] != BLANK
)
1088 break; /* found something in this column */
1091 break; /* found empty column */
1094 continue; /* a column was empty */
1096 for (j
= 0; j
< h
; j
++) {
1097 for (i
= 0; i
< w
; i
++) {
1098 if (grid
[j
*w
+i
] != BLANK
)
1099 break; /* found something in this row */
1102 break; /* found empty row */
1105 continue; /* a row was empty */
1108 * Now set up the numbers round the edge.
1110 for (i
= 0; i
< w
; i
++) {
1112 for (j
= 0; j
< h
; j
++)
1113 if (grid
[j
*w
+i
] == TENT
)
1117 for (i
= 0; i
< h
; i
++) {
1119 for (j
= 0; j
< w
; j
++)
1120 if (grid
[i
*w
+j
] == TENT
)
1126 * And now actually solve the puzzle, to see whether it's
1127 * unique and has the required difficulty.
1129 for (i
= 0; i
< w
*h
; i
++)
1130 puzzle
[i
] = grid
[i
] == TREE ? TREE
: BLANK
;
1131 i
= tents_solve(w
, h
, puzzle
, numbers
, soln
, sc
, params
->diff
-1);
1132 j
= tents_solve(w
, h
, puzzle
, numbers
, soln
, sc
, params
->diff
);
1135 * We expect solving with difficulty params->diff to have
1136 * succeeded (otherwise the problem is too hard), and
1137 * solving with diff-1 to have failed (otherwise it's too
1140 if (i
== 2 && j
== 1)
1145 * That's it. Encode as a game ID.
1147 ret
= snewn((w
+h
)*40 + ntrees
+ (w
*h
)/26 + 1, char);
1150 for (i
= 0; i
<= w
*h
; i
++) {
1151 int c
= (i
< w
*h ? grid
[i
] == TREE
: 1);
1153 *p
++ = (j
== 0 ?
'_' : j
-1 + 'a');
1163 for (i
= 0; i
< w
+h
; i
++)
1164 p
+= sprintf(p
, ",%d", numbers
[i
]);
1166 ret
= sresize(ret
, p
- ret
, char);
1169 * And encode the solution as an aux_info.
1171 *aux
= snewn(ntrees
* 40, char);
1174 for (i
= 0; i
< w
*h
; i
++)
1175 if (grid
[i
] == TENT
)
1176 p
+= sprintf(p
, ";T%d,%d", i
%w
, i
/w
);
1178 *aux
= sresize(*aux
, p
- *aux
, char);
1193 static char *validate_desc(game_params
*params
, char *desc
)
1195 int w
= params
->w
, h
= params
->h
;
1199 while (*desc
&& *desc
!= ',') {
1202 else if (*desc
>= 'a' && *desc
< 'z')
1203 area
+= *desc
- 'a' + 2;
1204 else if (*desc
== 'z')
1206 else if (*desc
== '!' || *desc
== '-')
1209 return "Invalid character in grid specification";
1213 if (area
< w
* h
+ 1)
1214 return "Not enough data to fill grid";
1215 else if (area
> w
* h
+ 1)
1216 return "Too much data to fill grid";
1218 for (i
= 0; i
< w
+h
; i
++) {
1220 return "Not enough numbers given after grid specification";
1221 else if (*desc
!= ',')
1222 return "Invalid character in number list";
1224 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1228 return "Unexpected additional data at end of game description";
1232 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1234 int w
= params
->w
, h
= params
->h
;
1235 game_state
*state
= snew(game_state
);
1238 state
->p
= *params
; /* structure copy */
1239 state
->grid
= snewn(w
*h
, char);
1240 state
->numbers
= snew(struct numbers
);
1241 state
->numbers
->refcount
= 1;
1242 state
->numbers
->numbers
= snewn(w
+h
, int);
1243 state
->completed
= state
->used_solve
= FALSE
;
1246 memset(state
->grid
, BLANK
, w
*h
);
1255 else if (*desc
>= 'a' && *desc
< 'z')
1256 run
= *desc
- ('a'-1);
1257 else if (*desc
== 'z') {
1261 assert(*desc
== '!' || *desc
== '-');
1263 type
= (*desc
== '!' ? TENT
: NONTENT
);
1269 assert(i
>= 0 && i
<= w
*h
);
1271 assert(type
== TREE
);
1275 state
->grid
[i
++] = type
;
1279 for (i
= 0; i
< w
+h
; i
++) {
1280 assert(*desc
== ',');
1282 state
->numbers
->numbers
[i
] = atoi(desc
);
1283 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1291 static game_state
*dup_game(game_state
*state
)
1293 int w
= state
->p
.w
, h
= state
->p
.h
;
1294 game_state
*ret
= snew(game_state
);
1296 ret
->p
= state
->p
; /* structure copy */
1297 ret
->grid
= snewn(w
*h
, char);
1298 memcpy(ret
->grid
, state
->grid
, w
*h
);
1299 ret
->numbers
= state
->numbers
;
1300 state
->numbers
->refcount
++;
1301 ret
->completed
= state
->completed
;
1302 ret
->used_solve
= state
->used_solve
;
1307 static void free_game(game_state
*state
)
1309 if (--state
->numbers
->refcount
<= 0) {
1310 sfree(state
->numbers
->numbers
);
1311 sfree(state
->numbers
);
1317 static char *solve_game(game_state
*state
, game_state
*currstate
,
1318 char *aux
, char **error
)
1320 int w
= state
->p
.w
, h
= state
->p
.h
;
1324 * If we already have the solution, save ourselves some
1329 struct solver_scratch
*sc
= new_scratch(w
, h
);
1335 soln
= snewn(w
*h
, char);
1336 ret
= tents_solve(w
, h
, state
->grid
, state
->numbers
->numbers
,
1337 soln
, sc
, DIFFCOUNT
-1);
1342 *error
= "This puzzle is not self-consistent";
1344 *error
= "Unable to find a unique solution for this puzzle";
1349 * Construct a move string which turns the current state
1350 * into the solved state.
1352 move
= snewn(w
*h
* 40, char);
1355 for (i
= 0; i
< w
*h
; i
++)
1356 if (soln
[i
] == TENT
)
1357 p
+= sprintf(p
, ";T%d,%d", i
%w
, i
/w
);
1359 move
= sresize(move
, p
- move
, char);
1367 static int game_can_format_as_text_now(game_params
*params
)
1372 static char *game_text_format(game_state
*state
)
1374 int w
= state
->p
.w
, h
= state
->p
.h
;
1379 * FIXME: We currently do not print the numbers round the edges
1380 * of the grid. I need to work out a sensible way of doing this
1381 * even when the column numbers exceed 9.
1383 * In the absence of those numbers, the result size is h lines
1384 * of w+1 characters each, plus a NUL.
1386 * This function is currently only used by the standalone
1387 * solver; until I make it look more sensible, I won't enable
1388 * it in the main game structure.
1390 ret
= snewn(h
*(w
+1) + 1, char);
1392 for (y
= 0; y
< h
; y
++) {
1393 for (x
= 0; x
< w
; x
++) {
1394 *p
= (state
->grid
[y
*w
+x
] == BLANK ?
'.' :
1395 state
->grid
[y
*w
+x
] == TREE ?
'T' :
1396 state
->grid
[y
*w
+x
] == TENT ?
'*' :
1397 state
->grid
[y
*w
+x
] == NONTENT ?
'-' : '?');
1408 int dsx
, dsy
; /* coords of drag start */
1409 int dex
, dey
; /* coords of drag end */
1410 int drag_button
; /* -1 for none, or a button code */
1411 int drag_ok
; /* dragged off the window, to cancel */
1413 int cx
, cy
, cdisp
; /* cursor position, and ?display. */
1416 static game_ui
*new_ui(game_state
*state
)
1418 game_ui
*ui
= snew(game_ui
);
1419 ui
->dsx
= ui
->dsy
= -1;
1420 ui
->dex
= ui
->dey
= -1;
1421 ui
->drag_button
= -1;
1422 ui
->drag_ok
= FALSE
;
1423 ui
->cx
= ui
->cy
= ui
->cdisp
= 0;
1427 static void free_ui(game_ui
*ui
)
1432 static char *encode_ui(game_ui
*ui
)
1437 static void decode_ui(game_ui
*ui
, char *encoding
)
1441 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1442 game_state
*newstate
)
1446 struct game_drawstate
{
1450 int *drawn
, *numbersdrawn
;
1451 int cx
, cy
; /* last-drawn cursor pos, or (-1,-1) if absent. */
1454 #define PREFERRED_TILESIZE 32
1455 #define TILESIZE (ds->tilesize)
1456 #define TLBORDER (TILESIZE/2)
1457 #define BRBORDER (TILESIZE*3/2)
1458 #define COORD(x) ( (x) * TILESIZE + TLBORDER )
1459 #define FROMCOORD(x) ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 )
1461 #define FLASH_TIME 0.30F
1463 static int drag_xform(game_ui
*ui
, int x
, int y
, int v
)
1465 int xmin
, ymin
, xmax
, ymax
;
1467 xmin
= min(ui
->dsx
, ui
->dex
);
1468 xmax
= max(ui
->dsx
, ui
->dex
);
1469 ymin
= min(ui
->dsy
, ui
->dey
);
1470 ymax
= max(ui
->dsy
, ui
->dey
);
1473 * Left-dragging has no effect, so we treat a left-drag as a
1474 * single click on dsx,dsy.
1476 if (ui
->drag_button
== LEFT_BUTTON
) {
1477 xmin
= xmax
= ui
->dsx
;
1478 ymin
= ymax
= ui
->dsy
;
1481 if (x
< xmin
|| x
> xmax
|| y
< ymin
|| y
> ymax
)
1482 return v
; /* no change outside drag area */
1485 return v
; /* trees are inviolate always */
1487 if (xmin
== xmax
&& ymin
== ymax
) {
1489 * Results of a simple click. Left button sets blanks to
1490 * tents; right button sets blanks to non-tents; either
1491 * button clears a non-blank square.
1493 if (ui
->drag_button
== LEFT_BUTTON
)
1494 v
= (v
== BLANK ? TENT
: BLANK
);
1496 v
= (v
== BLANK ? NONTENT
: BLANK
);
1499 * Results of a drag. Left-dragging has no effect.
1500 * Right-dragging sets all blank squares to non-tents and
1501 * has no effect on anything else.
1503 if (ui
->drag_button
== RIGHT_BUTTON
)
1504 v
= (v
== BLANK ? NONTENT
: v
);
1512 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1513 int x
, int y
, int button
)
1515 int w
= state
->p
.w
, h
= state
->p
.h
;
1518 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
1521 if (x
< 0 || y
< 0 || x
>= w
|| y
>= h
)
1524 ui
->drag_button
= button
;
1525 ui
->dsx
= ui
->dex
= x
;
1526 ui
->dsy
= ui
->dey
= y
;
1529 return ""; /* ui updated */
1532 if ((IS_MOUSE_DRAG(button
) || IS_MOUSE_RELEASE(button
)) &&
1533 ui
->drag_button
> 0) {
1534 int xmin
, ymin
, xmax
, ymax
;
1536 int buflen
, bufsize
, tmplen
;
1540 if (x
< 0 || y
< 0 || x
>= w
|| y
>= h
) {
1541 ui
->drag_ok
= FALSE
;
1544 * Drags are limited to one row or column. Hence, we
1545 * work out which coordinate is closer to the drag
1546 * start, and move it _to_ the drag start.
1548 if (abs(x
- ui
->dsx
) < abs(y
- ui
->dsy
))
1559 if (IS_MOUSE_DRAG(button
))
1560 return ""; /* ui updated */
1563 * The drag has been released. Enact it.
1566 ui
->drag_button
= -1;
1567 return ""; /* drag was just cancelled */
1570 xmin
= min(ui
->dsx
, ui
->dex
);
1571 xmax
= max(ui
->dsx
, ui
->dex
);
1572 ymin
= min(ui
->dsy
, ui
->dey
);
1573 ymax
= max(ui
->dsy
, ui
->dey
);
1574 assert(0 <= xmin
&& xmin
<= xmax
&& xmax
< w
);
1575 assert(0 <= ymin
&& ymin
<= ymax
&& ymax
< h
);
1579 buf
= snewn(bufsize
, char);
1581 for (y
= ymin
; y
<= ymax
; y
++)
1582 for (x
= xmin
; x
<= xmax
; x
++) {
1583 int v
= drag_xform(ui
, x
, y
, state
->grid
[y
*w
+x
]);
1584 if (state
->grid
[y
*w
+x
] != v
) {
1585 tmplen
= sprintf(tmpbuf
, "%s%c%d,%d", sep
,
1586 (int)(v
== BLANK ?
'B' :
1587 v
== TENT ?
'T' : 'N'),
1591 if (buflen
+ tmplen
>= bufsize
) {
1592 bufsize
= buflen
+ tmplen
+ 256;
1593 buf
= sresize(buf
, bufsize
, char);
1596 strcpy(buf
+buflen
, tmpbuf
);
1601 ui
->drag_button
= -1; /* drag is terminated */
1605 return ""; /* ui updated (drag was terminated) */
1612 if (IS_CURSOR_MOVE(button
)) {
1613 move_cursor(button
, &ui
->cx
, &ui
->cy
, w
, h
, 0);
1619 int v
= state
->grid
[ui
->cy
*w
+ui
->cx
];
1622 #ifdef SINGLE_CURSOR_SELECT
1623 if (button
== CURSOR_SELECT
)
1624 /* SELECT cycles T, N, B */
1625 rep
= v
== BLANK ?
'T' : v
== TENT ?
'N' : 'B';
1627 if (button
== CURSOR_SELECT
)
1628 rep
= v
== BLANK ?
'T' : 'B';
1629 else if (button
== CURSOR_SELECT2
)
1630 rep
= v
== BLANK ?
'N' : 'B';
1631 else if (button
== 'T' || button
== 'N' || button
== 'B')
1637 sprintf(tmpbuf
, "%c%d,%d", (int)rep
, ui
->cx
, ui
->cy
);
1638 return dupstr(tmpbuf
);
1640 } else if (IS_CURSOR_SELECT(button
)) {
1648 static game_state
*execute_move(game_state
*state
, char *move
)
1650 int w
= state
->p
.w
, h
= state
->p
.h
;
1652 int x
, y
, m
, n
, i
, j
;
1653 game_state
*ret
= dup_game(state
);
1659 ret
->used_solve
= TRUE
;
1661 * Set all non-tree squares to NONTENT. The rest of the
1662 * solve move will fill the tents in over the top.
1664 for (i
= 0; i
< w
*h
; i
++)
1665 if (ret
->grid
[i
] != TREE
)
1666 ret
->grid
[i
] = NONTENT
;
1668 } else if (c
== 'B' || c
== 'T' || c
== 'N') {
1670 if (sscanf(move
, "%d,%d%n", &x
, &y
, &n
) != 2 ||
1671 x
< 0 || y
< 0 || x
>= w
|| y
>= h
) {
1675 if (ret
->grid
[y
*w
+x
] == TREE
) {
1679 ret
->grid
[y
*w
+x
] = (c
== 'B' ? BLANK
: c
== 'T' ? TENT
: NONTENT
);
1694 * Check for completion.
1696 for (i
= n
= m
= 0; i
< w
*h
; i
++) {
1697 if (ret
->grid
[i
] == TENT
)
1699 else if (ret
->grid
[i
] == TREE
)
1703 int nedges
, maxedges
, *edges
, *capacity
, *flow
;
1706 * We have the right number of tents, which is a
1707 * precondition for the game being complete. Now check that
1708 * the numbers add up.
1710 for (i
= 0; i
< w
; i
++) {
1712 for (j
= 0; j
< h
; j
++)
1713 if (ret
->grid
[j
*w
+i
] == TENT
)
1715 if (ret
->numbers
->numbers
[i
] != n
)
1716 goto completion_check_done
;
1718 for (i
= 0; i
< h
; i
++) {
1720 for (j
= 0; j
< w
; j
++)
1721 if (ret
->grid
[i
*w
+j
] == TENT
)
1723 if (ret
->numbers
->numbers
[w
+i
] != n
)
1724 goto completion_check_done
;
1727 * Also, check that no two tents are adjacent.
1729 for (y
= 0; y
< h
; y
++)
1730 for (x
= 0; x
< w
; x
++) {
1732 ret
->grid
[y
*w
+x
] == TENT
&& ret
->grid
[y
*w
+x
+1] == TENT
)
1733 goto completion_check_done
;
1735 ret
->grid
[y
*w
+x
] == TENT
&& ret
->grid
[(y
+1)*w
+x
] == TENT
)
1736 goto completion_check_done
;
1737 if (x
+1 < w
&& y
+1 < h
) {
1738 if (ret
->grid
[y
*w
+x
] == TENT
&&
1739 ret
->grid
[(y
+1)*w
+(x
+1)] == TENT
)
1740 goto completion_check_done
;
1741 if (ret
->grid
[(y
+1)*w
+x
] == TENT
&&
1742 ret
->grid
[y
*w
+(x
+1)] == TENT
)
1743 goto completion_check_done
;
1748 * OK; we have the right number of tents, they match the
1749 * numeric clues, and they satisfy the non-adjacency
1750 * criterion. Finally, we need to verify that they can be
1751 * placed in a one-to-one matching with the trees such that
1752 * every tent is orthogonally adjacent to its tree.
1754 * This bit is where the hard work comes in: we have to do
1755 * it by finding such a matching using maxflow.
1757 * So we construct a network with one special source node,
1758 * one special sink node, one node per tent, and one node
1762 edges
= snewn(2 * maxedges
, int);
1763 capacity
= snewn(maxedges
, int);
1764 flow
= snewn(maxedges
, int);
1769 * 0..w*h trees/tents
1773 for (y
= 0; y
< h
; y
++)
1774 for (x
= 0; x
< w
; x
++)
1775 if (ret
->grid
[y
*w
+x
] == TREE
) {
1779 * Here we use the direction enum declared for
1780 * the solver. We make use of the fact that the
1781 * directions are declared in the order
1782 * U,L,R,D, meaning that we go through the four
1783 * neighbours of any square in numerically
1786 for (d
= 1; d
< MAXDIR
; d
++) {
1787 int x2
= x
+ dx(d
), y2
= y
+ dy(d
);
1788 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
&&
1789 ret
->grid
[y2
*w
+x2
] == TENT
) {
1790 assert(nedges
< maxedges
);
1791 edges
[nedges
*2] = y
*w
+x
;
1792 edges
[nedges
*2+1] = y2
*w
+x2
;
1793 capacity
[nedges
] = 1;
1797 } else if (ret
->grid
[y
*w
+x
] == TENT
) {
1798 assert(nedges
< maxedges
);
1799 edges
[nedges
*2] = y
*w
+x
;
1800 edges
[nedges
*2+1] = w
*h
+1; /* edge going to sink */
1801 capacity
[nedges
] = 1;
1804 for (y
= 0; y
< h
; y
++)
1805 for (x
= 0; x
< w
; x
++)
1806 if (ret
->grid
[y
*w
+x
] == TREE
) {
1807 assert(nedges
< maxedges
);
1808 edges
[nedges
*2] = w
*h
; /* edge coming from source */
1809 edges
[nedges
*2+1] = y
*w
+x
;
1810 capacity
[nedges
] = 1;
1813 n
= maxflow(w
*h
+2, w
*h
, w
*h
+1, nedges
, edges
, capacity
, flow
, NULL
);
1820 goto completion_check_done
;
1823 * We haven't managed to fault the grid on any count. Score!
1825 ret
->completed
= TRUE
;
1827 completion_check_done
:
1832 /* ----------------------------------------------------------------------
1836 static void game_compute_size(game_params
*params
, int tilesize
,
1839 /* fool the macros */
1840 struct dummy
{ int tilesize
; } dummy
, *ds
= &dummy
;
1841 dummy
.tilesize
= tilesize
;
1843 *x
= TLBORDER
+ BRBORDER
+ TILESIZE
* params
->w
;
1844 *y
= TLBORDER
+ BRBORDER
+ TILESIZE
* params
->h
;
1847 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1848 game_params
*params
, int tilesize
)
1850 ds
->tilesize
= tilesize
;
1853 static float *game_colours(frontend
*fe
, int *ncolours
)
1855 float *ret
= snewn(3 * NCOLOURS
, float);
1857 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1859 ret
[COL_GRID
* 3 + 0] = 0.0F
;
1860 ret
[COL_GRID
* 3 + 1] = 0.0F
;
1861 ret
[COL_GRID
* 3 + 2] = 0.0F
;
1863 ret
[COL_GRASS
* 3 + 0] = 0.7F
;
1864 ret
[COL_GRASS
* 3 + 1] = 1.0F
;
1865 ret
[COL_GRASS
* 3 + 2] = 0.5F
;
1867 ret
[COL_TREETRUNK
* 3 + 0] = 0.6F
;
1868 ret
[COL_TREETRUNK
* 3 + 1] = 0.4F
;
1869 ret
[COL_TREETRUNK
* 3 + 2] = 0.0F
;
1871 ret
[COL_TREELEAF
* 3 + 0] = 0.0F
;
1872 ret
[COL_TREELEAF
* 3 + 1] = 0.7F
;
1873 ret
[COL_TREELEAF
* 3 + 2] = 0.0F
;
1875 ret
[COL_TENT
* 3 + 0] = 0.8F
;
1876 ret
[COL_TENT
* 3 + 1] = 0.7F
;
1877 ret
[COL_TENT
* 3 + 2] = 0.0F
;
1879 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1880 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
1881 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
1883 ret
[COL_ERRTEXT
* 3 + 0] = 1.0F
;
1884 ret
[COL_ERRTEXT
* 3 + 1] = 1.0F
;
1885 ret
[COL_ERRTEXT
* 3 + 2] = 1.0F
;
1887 ret
[COL_ERRTRUNK
* 3 + 0] = 0.6F
;
1888 ret
[COL_ERRTRUNK
* 3 + 1] = 0.0F
;
1889 ret
[COL_ERRTRUNK
* 3 + 2] = 0.0F
;
1891 *ncolours
= NCOLOURS
;
1895 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1897 int w
= state
->p
.w
, h
= state
->p
.h
;
1898 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1902 ds
->started
= FALSE
;
1903 ds
->p
= state
->p
; /* structure copy */
1904 ds
->drawn
= snewn(w
*h
, int);
1905 for (i
= 0; i
< w
*h
; i
++)
1906 ds
->drawn
[i
] = MAGIC
;
1907 ds
->numbersdrawn
= snewn(w
+h
, int);
1908 for (i
= 0; i
< w
+h
; i
++)
1909 ds
->numbersdrawn
[i
] = 2;
1910 ds
->cx
= ds
->cy
= -1;
1915 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1918 sfree(ds
->numbersdrawn
);
1923 ERR_ADJ_TOPLEFT
= 4,
1934 static int *find_errors(game_state
*state
, char *grid
)
1936 int w
= state
->p
.w
, h
= state
->p
.h
;
1937 int *ret
= snewn(w
*h
+ w
+ h
, int);
1938 int *tmp
= snewn(w
*h
*2, int), *dsf
= tmp
+ w
*h
;
1942 * This function goes through a grid and works out where to
1943 * highlight play errors in red. The aim is that it should
1944 * produce at least one error highlight for any complete grid
1945 * (or complete piece of grid) violating a puzzle constraint, so
1946 * that a grid containing no BLANK squares is either a win or is
1947 * marked up in some way that indicates why not.
1949 * So it's easy enough to highlight errors in the numeric clues
1950 * - just light up any row or column number which is not
1951 * fulfilled - and it's just as easy to highlight adjacent
1952 * tents. The difficult bit is highlighting failures in the
1953 * tent/tree matching criterion.
1955 * A natural approach would seem to be to apply the maxflow
1956 * algorithm to find the tent/tree matching; if this fails, it
1957 * must necessarily terminate with a min-cut which can be
1958 * reinterpreted as some set of trees which have too few tents
1959 * between them (or vice versa). However, it's bad for
1960 * localising errors, because it's not easy to make the
1961 * algorithm narrow down to the _smallest_ such set of trees: if
1962 * trees A and B have only one tent between them, for instance,
1963 * it might perfectly well highlight not only A and B but also
1964 * trees C and D which are correctly matched on the far side of
1965 * the grid, on the grounds that those four trees between them
1966 * have only three tents.
1968 * Also, that approach fares badly when you introduce the
1969 * additional requirement that incomplete grids should have
1970 * errors highlighted only when they can be proved to be errors
1971 * - so that trees should not be marked as having too few tents
1972 * if there are enough BLANK squares remaining around them that
1973 * could be turned into the missing tents (to do so would be
1974 * patronising, since the overwhelming likelihood is not that
1975 * the player has forgotten to put a tree there but that they
1976 * have merely not put one there _yet_). However, tents with too
1977 * few trees can be marked immediately, since those are
1978 * definitely player error.
1980 * So I adopt an alternative approach, which is to consider the
1981 * bipartite adjacency graph between trees and tents
1982 * ('bipartite' in the sense that for these purposes I
1983 * deliberately ignore two adjacent trees or two adjacent
1984 * tents), divide that graph up into its connected components
1985 * using a dsf, and look for components which contain different
1986 * numbers of trees and tents. This allows me to highlight
1987 * groups of tents with too few trees between them immediately,
1988 * and then in order to find groups of trees with too few tents
1989 * I redo the same process but counting BLANKs as potential
1990 * tents (so that the only trees highlighted are those
1991 * surrounded by enough NONTENTs to make it impossible to give
1992 * them enough tents).
1994 * However, this technique is incomplete: it is not a sufficient
1995 * condition for the existence of a perfect matching that every
1996 * connected component of the graph has the same number of tents
1997 * and trees. An example of a graph which satisfies the latter
1998 * condition but still has no perfect matching is
2007 * which can be realised in Tents as
2013 * The matching-error highlighter described above will not mark
2014 * this construction as erroneous. However, something else will:
2015 * the three tents in the above diagram (let us suppose A,B,C
2016 * are the tents, though it doesn't matter which) contain two
2017 * diagonally adjacent pairs. So there will be _an_ error
2018 * highlighted for the above layout, even though not all types
2019 * of error will be highlighted.
2021 * And in fact we can prove that this will always be the case:
2022 * that the shortcomings of the matching-error highlighter will
2023 * always be made up for by the easy tent adjacency highlighter.
2025 * Lemma: Let G be a bipartite graph between n trees and n
2026 * tents, which is connected, and in which no tree has degree
2027 * more than two (but a tent may). Then G has a perfect matching.
2029 * (Note: in the statement and proof of the Lemma I will
2030 * consistently use 'tree' to indicate a type of graph vertex as
2031 * opposed to a tent, and not to indicate a tree in the graph-
2036 * If we can find a tent of degree 1 joined to a tree of degree
2037 * 2, then any perfect matching must pair that tent with that
2038 * tree. Hence, we can remove both, leaving a smaller graph G'
2039 * which still satisfies all the conditions of the Lemma, and
2040 * which has a perfect matching iff G does.
2042 * So, wlog, we may assume G contains no tent of degree 1 joined
2043 * to a tree of degree 2; if it does, we can reduce it as above.
2045 * If G has no tent of degree 1 at all, then every tent has
2046 * degree at least two, so there are at least 2n edges in the
2047 * graph. But every tree has degree at most two, so there are at
2048 * most 2n edges. Hence there must be exactly 2n edges, so every
2049 * tree and every tent must have degree exactly two, which means
2050 * that the whole graph consists of a single loop (by
2051 * connectedness), and therefore certainly has a perfect
2054 * Alternatively, if G does have a tent of degree 1 but it is
2055 * not connected to a tree of degree 2, then the tree it is
2056 * connected to must have degree 1 - and, by connectedness, that
2057 * must mean that that tent and that tree between them form the
2058 * entire graph. This trivial graph has a trivial perfect
2061 * That proves the lemma. Hence, in any case where the matching-
2062 * error highlighter fails to highlight an erroneous component
2063 * (because it has the same number of tents as trees, but they
2064 * cannot be matched up), the above lemma tells us that there
2065 * must be a tree with degree more than 2, i.e. a tree
2066 * orthogonally adjacent to at least three tents. But in that
2067 * case, there must be some pair of those three tents which are
2068 * diagonally adjacent to each other, so the tent-adjacency
2069 * highlighter will necessarily show an error. So any filled
2070 * layout in Tents which is not a correct solution to the puzzle
2071 * must have _some_ error highlighted by the subroutine below.
2073 * (Of course it would be nicer if we could highlight all
2074 * errors: in the above example layout, we would like to
2075 * highlight tents A,B as having too few trees between them, and
2076 * trees 2,3 as having too few tents, in addition to marking the
2077 * adjacency problems. But I can't immediately think of any way
2078 * to find the smallest sets of such tents and trees without an
2079 * O(2^N) loop over all subsets of a given component.)
2083 * ret[0] through to ret[w*h-1] give error markers for the grid
2084 * squares. After that, ret[w*h] to ret[w*h+w-1] give error
2085 * markers for the column numbers, and ret[w*h+w] to
2086 * ret[w*h+w+h-1] for the row numbers.
2090 * Spot tent-adjacency violations.
2092 for (x
= 0; x
< w
*h
; x
++)
2094 for (y
= 0; y
< h
; y
++) {
2095 for (x
= 0; x
< w
; x
++) {
2096 if (y
+1 < h
&& x
+1 < w
&&
2097 ((grid
[y
*w
+x
] == TENT
&&
2098 grid
[(y
+1)*w
+(x
+1)] == TENT
) ||
2099 (grid
[(y
+1)*w
+x
] == TENT
&&
2100 grid
[y
*w
+(x
+1)] == TENT
))) {
2101 ret
[y
*w
+x
] |= 1 << ERR_ADJ_BOTRIGHT
;
2102 ret
[(y
+1)*w
+x
] |= 1 << ERR_ADJ_TOPRIGHT
;
2103 ret
[y
*w
+(x
+1)] |= 1 << ERR_ADJ_BOTLEFT
;
2104 ret
[(y
+1)*w
+(x
+1)] |= 1 << ERR_ADJ_TOPLEFT
;
2107 grid
[y
*w
+x
] == TENT
&&
2108 grid
[(y
+1)*w
+x
] == TENT
) {
2109 ret
[y
*w
+x
] |= 1 << ERR_ADJ_BOT
;
2110 ret
[(y
+1)*w
+x
] |= 1 << ERR_ADJ_TOP
;
2113 grid
[y
*w
+x
] == TENT
&&
2114 grid
[y
*w
+(x
+1)] == TENT
) {
2115 ret
[y
*w
+x
] |= 1 << ERR_ADJ_RIGHT
;
2116 ret
[y
*w
+(x
+1)] |= 1 << ERR_ADJ_LEFT
;
2122 * Spot numeric clue violations.
2124 for (x
= 0; x
< w
; x
++) {
2125 int tents
= 0, maybetents
= 0;
2126 for (y
= 0; y
< h
; y
++) {
2127 if (grid
[y
*w
+x
] == TENT
)
2129 else if (grid
[y
*w
+x
] == BLANK
)
2132 ret
[w
*h
+x
] = (tents
> state
->numbers
->numbers
[x
] ||
2133 tents
+ maybetents
< state
->numbers
->numbers
[x
]);
2135 for (y
= 0; y
< h
; y
++) {
2136 int tents
= 0, maybetents
= 0;
2137 for (x
= 0; x
< w
; x
++) {
2138 if (grid
[y
*w
+x
] == TENT
)
2140 else if (grid
[y
*w
+x
] == BLANK
)
2143 ret
[w
*h
+w
+y
] = (tents
> state
->numbers
->numbers
[w
+y
] ||
2144 tents
+ maybetents
< state
->numbers
->numbers
[w
+y
]);
2148 * Identify groups of tents with too few trees between them,
2149 * which we do by constructing the connected components of the
2150 * bipartite adjacency graph between tents and trees
2151 * ('bipartite' in the sense that we deliberately ignore
2152 * adjacency between tents or between trees), and highlighting
2153 * all the tents in any component which has a smaller tree
2157 /* Construct the equivalence classes. */
2158 for (y
= 0; y
< h
; y
++) {
2159 for (x
= 0; x
< w
-1; x
++) {
2160 if ((grid
[y
*w
+x
] == TREE
&& grid
[y
*w
+x
+1] == TENT
) ||
2161 (grid
[y
*w
+x
] == TENT
&& grid
[y
*w
+x
+1] == TREE
))
2162 dsf_merge(dsf
, y
*w
+x
, y
*w
+x
+1);
2165 for (y
= 0; y
< h
-1; y
++) {
2166 for (x
= 0; x
< w
; x
++) {
2167 if ((grid
[y
*w
+x
] == TREE
&& grid
[(y
+1)*w
+x
] == TENT
) ||
2168 (grid
[y
*w
+x
] == TENT
&& grid
[(y
+1)*w
+x
] == TREE
))
2169 dsf_merge(dsf
, y
*w
+x
, (y
+1)*w
+x
);
2172 /* Count up the tent/tree difference in each one. */
2173 for (x
= 0; x
< w
*h
; x
++)
2175 for (x
= 0; x
< w
*h
; x
++) {
2176 y
= dsf_canonify(dsf
, x
);
2177 if (grid
[x
] == TREE
)
2179 else if (grid
[x
] == TENT
)
2182 /* And highlight any tent belonging to an equivalence class with
2183 * a score less than zero. */
2184 for (x
= 0; x
< w
*h
; x
++) {
2185 y
= dsf_canonify(dsf
, x
);
2186 if (grid
[x
] == TENT
&& tmp
[y
] < 0)
2187 ret
[x
] |= 1 << ERR_OVERCOMMITTED
;
2191 * Identify groups of trees with too few tents between them.
2192 * This is done similarly, except that we now count BLANK as
2193 * equivalent to TENT, i.e. we only highlight such trees when
2194 * the user hasn't even left _room_ to provide tents for them
2195 * all. (Otherwise, we'd highlight all trees red right at the
2196 * start of the game, before the user had done anything wrong!)
2198 #define TENT(x) ((x)==TENT || (x)==BLANK)
2200 /* Construct the equivalence classes. */
2201 for (y
= 0; y
< h
; y
++) {
2202 for (x
= 0; x
< w
-1; x
++) {
2203 if ((grid
[y
*w
+x
] == TREE
&& TENT(grid
[y
*w
+x
+1])) ||
2204 (TENT(grid
[y
*w
+x
]) && grid
[y
*w
+x
+1] == TREE
))
2205 dsf_merge(dsf
, y
*w
+x
, y
*w
+x
+1);
2208 for (y
= 0; y
< h
-1; y
++) {
2209 for (x
= 0; x
< w
; x
++) {
2210 if ((grid
[y
*w
+x
] == TREE
&& TENT(grid
[(y
+1)*w
+x
])) ||
2211 (TENT(grid
[y
*w
+x
]) && grid
[(y
+1)*w
+x
] == TREE
))
2212 dsf_merge(dsf
, y
*w
+x
, (y
+1)*w
+x
);
2215 /* Count up the tent/tree difference in each one. */
2216 for (x
= 0; x
< w
*h
; x
++)
2218 for (x
= 0; x
< w
*h
; x
++) {
2219 y
= dsf_canonify(dsf
, x
);
2220 if (grid
[x
] == TREE
)
2222 else if (TENT(grid
[x
]))
2225 /* And highlight any tree belonging to an equivalence class with
2226 * a score more than zero. */
2227 for (x
= 0; x
< w
*h
; x
++) {
2228 y
= dsf_canonify(dsf
, x
);
2229 if (grid
[x
] == TREE
&& tmp
[y
] > 0)
2230 ret
[x
] |= 1 << ERR_OVERCOMMITTED
;
2238 static void draw_err_adj(drawing
*dr
, game_drawstate
*ds
, int x
, int y
)
2246 coords
[0] = x
- TILESIZE
*2/5;
2249 coords
[3] = y
- TILESIZE
*2/5;
2250 coords
[4] = x
+ TILESIZE
*2/5;
2253 coords
[7] = y
+ TILESIZE
*2/5;
2254 draw_polygon(dr
, coords
, 4, COL_ERROR
, COL_GRID
);
2257 * Draw an exclamation mark in the diamond. This turns out to
2258 * look unpleasantly off-centre if done via draw_text, so I do
2259 * it by hand on the basis that exclamation marks aren't that
2260 * difficult to draw...
2263 yext
= TILESIZE
*2/5 - (xext
*2+2);
2264 draw_rect(dr
, x
-xext
, y
-yext
, xext
*2+1, yext
*2+1 - (xext
*3),
2266 draw_rect(dr
, x
-xext
, y
+yext
-xext
*2+1, xext
*2+1, xext
*2, COL_ERRTEXT
);
2269 static void draw_tile(drawing
*dr
, game_drawstate
*ds
,
2270 int x
, int y
, int v
, int cur
, int printing
)
2273 int tx
= COORD(x
), ty
= COORD(y
);
2274 int cx
= tx
+ TILESIZE
/2, cy
= ty
+ TILESIZE
/2;
2279 clip(dr
, tx
, ty
, TILESIZE
, TILESIZE
);
2282 draw_rect(dr
, tx
, ty
, TILESIZE
, TILESIZE
, COL_GRID
);
2283 draw_rect(dr
, tx
+1, ty
+1, TILESIZE
-1, TILESIZE
-1,
2284 (v
== BLANK ? COL_BACKGROUND
: COL_GRASS
));
2290 (printing ? draw_rect_outline
: draw_rect
)
2291 (dr
, cx
-TILESIZE
/15, ty
+TILESIZE
*3/10,
2292 2*(TILESIZE
/15)+1, (TILESIZE
*9/10 - TILESIZE
*3/10),
2293 (err
& (1<<ERR_OVERCOMMITTED
) ? COL_ERRTRUNK
: COL_TREETRUNK
));
2295 for (i
= 0; i
< (printing ?
2 : 1); i
++) {
2296 int col
= (i
== 1 ? COL_BACKGROUND
:
2297 (err
& (1<<ERR_OVERCOMMITTED
) ? COL_ERROR
:
2299 int sub
= i
* (TILESIZE
/32);
2300 draw_circle(dr
, cx
, ty
+TILESIZE
*4/10, TILESIZE
/4 - sub
,
2302 draw_circle(dr
, cx
+TILESIZE
/5, ty
+TILESIZE
/4, TILESIZE
/8 - sub
,
2304 draw_circle(dr
, cx
-TILESIZE
/5, ty
+TILESIZE
/4, TILESIZE
/8 - sub
,
2306 draw_circle(dr
, cx
+TILESIZE
/4, ty
+TILESIZE
*6/13, TILESIZE
/8 - sub
,
2308 draw_circle(dr
, cx
-TILESIZE
/4, ty
+TILESIZE
*6/13, TILESIZE
/8 - sub
,
2311 } else if (v
== TENT
) {
2314 coords
[0] = cx
- TILESIZE
/3;
2315 coords
[1] = cy
+ TILESIZE
/3;
2316 coords
[2] = cx
+ TILESIZE
/3;
2317 coords
[3] = cy
+ TILESIZE
/3;
2319 coords
[5] = cy
- TILESIZE
/3;
2320 col
= (err
& (1<<ERR_OVERCOMMITTED
) ? COL_ERROR
: COL_TENT
);
2321 draw_polygon(dr
, coords
, 3, (printing ?
-1 : col
), col
);
2324 if (err
& (1 << ERR_ADJ_TOPLEFT
))
2325 draw_err_adj(dr
, ds
, tx
, ty
);
2326 if (err
& (1 << ERR_ADJ_TOP
))
2327 draw_err_adj(dr
, ds
, tx
+TILESIZE
/2, ty
);
2328 if (err
& (1 << ERR_ADJ_TOPRIGHT
))
2329 draw_err_adj(dr
, ds
, tx
+TILESIZE
, ty
);
2330 if (err
& (1 << ERR_ADJ_LEFT
))
2331 draw_err_adj(dr
, ds
, tx
, ty
+TILESIZE
/2);
2332 if (err
& (1 << ERR_ADJ_RIGHT
))
2333 draw_err_adj(dr
, ds
, tx
+TILESIZE
, ty
+TILESIZE
/2);
2334 if (err
& (1 << ERR_ADJ_BOTLEFT
))
2335 draw_err_adj(dr
, ds
, tx
, ty
+TILESIZE
);
2336 if (err
& (1 << ERR_ADJ_BOT
))
2337 draw_err_adj(dr
, ds
, tx
+TILESIZE
/2, ty
+TILESIZE
);
2338 if (err
& (1 << ERR_ADJ_BOTRIGHT
))
2339 draw_err_adj(dr
, ds
, tx
+TILESIZE
, ty
+TILESIZE
);
2342 int coff
= TILESIZE
/8;
2343 draw_rect_outline(dr
, tx
+ coff
, ty
+ coff
,
2344 TILESIZE
- coff
*2 + 1, TILESIZE
- coff
*2 + 1,
2349 draw_update(dr
, tx
+1, ty
+1, TILESIZE
-1, TILESIZE
-1);
2353 * Internal redraw function, used for printing as well as drawing.
2355 static void int_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2356 game_state
*state
, int dir
, game_ui
*ui
,
2357 float animtime
, float flashtime
, int printing
)
2359 int w
= state
->p
.w
, h
= state
->p
.h
;
2361 int cx
= -1, cy
= -1;
2367 if (ui
->cdisp
) { cx
= ui
->cx
; cy
= ui
->cy
; }
2368 if (cx
!= ds
->cx
|| cy
!= ds
->cy
) cmoved
= 1;
2371 if (printing
|| !ds
->started
) {
2374 game_compute_size(&state
->p
, TILESIZE
, &ww
, &wh
);
2375 draw_rect(dr
, 0, 0, ww
, wh
, COL_BACKGROUND
);
2376 draw_update(dr
, 0, 0, ww
, wh
);
2381 print_line_width(dr
, TILESIZE
/64);
2386 for (y
= 0; y
<= h
; y
++)
2387 draw_line(dr
, COORD(0), COORD(y
), COORD(w
), COORD(y
), COL_GRID
);
2388 for (x
= 0; x
<= w
; x
++)
2389 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(h
), COL_GRID
);
2393 flashing
= (int)(flashtime
* 3 / FLASH_TIME
) != 1;
2398 * Find errors. For this we use _part_ of the information from a
2399 * currently active drag: we transform dsx,dsy but not anything
2400 * else. (This seems to strike a good compromise between having
2401 * the error highlights respond instantly to single clicks, but
2402 * not giving constant feedback during a right-drag.)
2404 if (ui
&& ui
->drag_button
>= 0) {
2405 tmpgrid
= snewn(w
*h
, char);
2406 memcpy(tmpgrid
, state
->grid
, w
*h
);
2407 tmpgrid
[ui
->dsy
* w
+ ui
->dsx
] =
2408 drag_xform(ui
, ui
->dsx
, ui
->dsy
, tmpgrid
[ui
->dsy
* w
+ ui
->dsx
]);
2409 errors
= find_errors(state
, tmpgrid
);
2412 errors
= find_errors(state
, state
->grid
);
2418 for (y
= 0; y
< h
; y
++) {
2419 for (x
= 0; x
< w
; x
++) {
2420 int v
= state
->grid
[y
*w
+x
];
2424 * We deliberately do not take drag_ok into account
2425 * here, because user feedback suggests that it's
2426 * marginally nicer not to have the drag effects
2427 * flickering on and off disconcertingly.
2429 if (ui
&& ui
->drag_button
>= 0)
2430 v
= drag_xform(ui
, x
, y
, v
);
2432 if (flashing
&& (v
== TREE
|| v
== TENT
))
2436 if ((x
== cx
&& y
== cy
) ||
2437 (x
== ds
->cx
&& y
== ds
->cy
)) credraw
= 1;
2442 if (printing
|| ds
->drawn
[y
*w
+x
] != v
|| credraw
) {
2443 draw_tile(dr
, ds
, x
, y
, v
, (x
== cx
&& y
== cy
), printing
);
2445 ds
->drawn
[y
*w
+x
] = v
;
2451 * Draw (or redraw, if their error-highlighted state has
2452 * changed) the numbers.
2454 for (x
= 0; x
< w
; x
++) {
2455 if (ds
->numbersdrawn
[x
] != errors
[w
*h
+x
]) {
2457 draw_rect(dr
, COORD(x
), COORD(h
)+1, TILESIZE
, BRBORDER
-1,
2459 sprintf(buf
, "%d", state
->numbers
->numbers
[x
]);
2460 draw_text(dr
, COORD(x
) + TILESIZE
/2, COORD(h
+1),
2461 FONT_VARIABLE
, TILESIZE
/2, ALIGN_HCENTRE
|ALIGN_VNORMAL
,
2462 (errors
[w
*h
+x
] ? COL_ERROR
: COL_GRID
), buf
);
2463 draw_update(dr
, COORD(x
), COORD(h
)+1, TILESIZE
, BRBORDER
-1);
2464 ds
->numbersdrawn
[x
] = errors
[w
*h
+x
];
2467 for (y
= 0; y
< h
; y
++) {
2468 if (ds
->numbersdrawn
[w
+y
] != errors
[w
*h
+w
+y
]) {
2470 draw_rect(dr
, COORD(w
)+1, COORD(y
), BRBORDER
-1, TILESIZE
,
2472 sprintf(buf
, "%d", state
->numbers
->numbers
[w
+y
]);
2473 draw_text(dr
, COORD(w
+1), COORD(y
) + TILESIZE
/2,
2474 FONT_VARIABLE
, TILESIZE
/2, ALIGN_HRIGHT
|ALIGN_VCENTRE
,
2475 (errors
[w
*h
+w
+y
] ? COL_ERROR
: COL_GRID
), buf
);
2476 draw_update(dr
, COORD(w
)+1, COORD(y
), BRBORDER
-1, TILESIZE
);
2477 ds
->numbersdrawn
[w
+y
] = errors
[w
*h
+w
+y
];
2489 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2490 game_state
*state
, int dir
, game_ui
*ui
,
2491 float animtime
, float flashtime
)
2493 int_redraw(dr
, ds
, oldstate
, state
, dir
, ui
, animtime
, flashtime
, FALSE
);
2496 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2497 int dir
, game_ui
*ui
)
2502 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2503 int dir
, game_ui
*ui
)
2505 if (!oldstate
->completed
&& newstate
->completed
&&
2506 !oldstate
->used_solve
&& !newstate
->used_solve
)
2512 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2517 static void game_print_size(game_params
*params
, float *x
, float *y
)
2522 * I'll use 6mm squares by default.
2524 game_compute_size(params
, 600, &pw
, &ph
);
2529 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2533 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2534 game_drawstate ads
, *ds
= &ads
;
2535 game_set_size(dr
, ds
, NULL
, tilesize
);
2537 c
= print_mono_colour(dr
, 1); assert(c
== COL_BACKGROUND
);
2538 c
= print_mono_colour(dr
, 0); assert(c
== COL_GRID
);
2539 c
= print_mono_colour(dr
, 1); assert(c
== COL_GRASS
);
2540 c
= print_mono_colour(dr
, 0); assert(c
== COL_TREETRUNK
);
2541 c
= print_mono_colour(dr
, 0); assert(c
== COL_TREELEAF
);
2542 c
= print_mono_colour(dr
, 0); assert(c
== COL_TENT
);
2544 int_redraw(dr
, ds
, NULL
, state
, +1, NULL
, 0.0F
, 0.0F
, TRUE
);
2548 #define thegame tents
2551 const struct game thegame
= {
2552 "Tents", "games.tents", "tents",
2559 TRUE
, game_configure
, custom_params
,
2567 FALSE
, game_can_format_as_text_now
, game_text_format
,
2575 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
2578 game_free_drawstate
,
2582 TRUE
, FALSE
, game_print_size
, game_print
,
2583 FALSE
, /* wants_statusbar */
2584 FALSE
, game_timing_state
,
2585 REQUIRE_RBUTTON
, /* flags */
2588 #ifdef STANDALONE_SOLVER
2592 int main(int argc
, char **argv
)
2596 char *id
= NULL
, *desc
, *err
;
2598 int ret
, diff
, really_verbose
= FALSE
;
2599 struct solver_scratch
*sc
;
2601 while (--argc
> 0) {
2603 if (!strcmp(p
, "-v")) {
2604 really_verbose
= TRUE
;
2605 } else if (!strcmp(p
, "-g")) {
2607 } else if (*p
== '-') {
2608 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
2616 fprintf(stderr
, "usage: %s [-g | -v] <game_id>\n", argv
[0]);
2620 desc
= strchr(id
, ':');
2622 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
2627 p
= default_params();
2628 decode_params(p
, id
);
2629 err
= validate_desc(p
, desc
);
2631 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
2634 s
= new_game(NULL
, p
, desc
);
2635 s2
= new_game(NULL
, p
, desc
);
2637 sc
= new_scratch(p
->w
, p
->h
);
2640 * When solving an Easy puzzle, we don't want to bother the
2641 * user with Hard-level deductions. For this reason, we grade
2642 * the puzzle internally before doing anything else.
2644 ret
= -1; /* placate optimiser */
2645 for (diff
= 0; diff
< DIFFCOUNT
; diff
++) {
2646 ret
= tents_solve(p
->w
, p
->h
, s
->grid
, s
->numbers
->numbers
,
2647 s2
->grid
, sc
, diff
);
2652 if (diff
== DIFFCOUNT
) {
2654 printf("Difficulty rating: too hard to solve internally\n");
2656 printf("Unable to find a unique solution\n");
2660 printf("Difficulty rating: impossible (no solution exists)\n");
2662 printf("Difficulty rating: %s\n", tents_diffnames
[diff
]);
2664 verbose
= really_verbose
;
2665 ret
= tents_solve(p
->w
, p
->h
, s
->grid
, s
->numbers
->numbers
,
2666 s2
->grid
, sc
, diff
);
2668 printf("Puzzle is inconsistent\n");
2670 fputs(game_text_format(s2
), stdout
);
2679 /* vim: set shiftwidth=4 tabstop=8: */