2 * tents.c: Puzzle involving placing tents next to trees subject to
3 * some confusing conditions.
7 * - error highlighting?
8 * * highlighting adjacent tents is easy
9 * * highlighting violated numeric clues is almost as easy
10 * (might want to pay attention to NONTENTs here)
11 * * but how in hell do we highlight a failure of maxflow
12 * during completion checking?
13 * + well, the _obvious_ approach is to use maxflow's own
14 * error report: it will provide, via the `cut' parameter,
15 * a set of trees which have too few tents between them.
16 * It's unclear that this will be particularly obvious to
17 * a user, however. Is there any other way?
19 * - it might be nice to make setter-provided tent/nontent clues
21 * * on the other hand, this would introduce considerable extra
22 * complexity and size into the game state; also inviolable
23 * clues would have to be marked as such somehow, in an
24 * intrusive and annoying manner. Since they're never
25 * generated by _my_ generator, I'm currently more inclined
28 * - more difficult levels at the top end?
29 * * for example, sometimes we can deduce that two BLANKs in
30 * the same row are each adjacent to the same unattached tree
31 * and to nothing else, implying that they can't both be
32 * tents; this enables us to rule out some extra combinations
33 * in the row-based deduction loop, and hence deduce more
34 * from the number in that row than we could otherwise do.
35 * * that by itself doesn't seem worth implementing a new
36 * difficulty level for, but if I can find a few more things
37 * like that then it might become worthwhile.
38 * * I wonder if there's a sensible heuristic for where to
39 * guess which would make a recursive solver viable?
56 * The rules of this puzzle as available on the WWW are poorly
57 * specified. The bits about tents having to be orthogonally
58 * adjacent to trees, tents not being even diagonally adjacent to
59 * one another, and the number of tents in each row and column
60 * being given are simple enough; the difficult bit is the
61 * tent-to-tree matching.
63 * Some sources use simplistic wordings such as `each tree is
64 * exactly connected to only one tent', which is extremely unclear:
65 * it's easy to read erroneously as `each tree is _orthogonally
66 * adjacent_ to exactly one tent', which is definitely incorrect.
67 * Even the most coherent sources I've found don't do a much better
68 * job of stating the rule.
70 * A more precise statement of the rule is that it must be possible
71 * to find a bijection f between tents and trees such that each
72 * tree T is orthogonally adjacent to the tent f(T), but that a
73 * tent is permitted to be adjacent to other trees in addition to
74 * its own. This slightly non-obvious criterion is what gives this
75 * puzzle most of its subtlety.
77 * However, there's a particularly subtle ambiguity left over. Is
78 * the bijection between tents and trees required to be _unique_?
79 * In other words, is that bijection conceptually something the
80 * player should be able to exhibit as part of the solution (even
81 * if they aren't actually required to do so)? Or is it sufficient
82 * to have a unique _placement_ of the tents which gives rise to at
83 * least one suitable bijection?
85 * The puzzle shown to the right of this .T. 2 *T* 2
86 * paragraph illustrates the problem. There T.T 0 -> T-T 0
87 * are two distinct bijections available. .T. 2 *T* 2
88 * The answer to the above question will
89 * determine whether it's a valid puzzle. 202 202
91 * This is an important question, because it affects both the
92 * player and the generator. Eventually I found all the instances
93 * of this puzzle I could Google up, solved them all by hand, and
94 * verified that in all cases the tree/tent matching was uniquely
95 * determined given the tree and tent positions. Therefore, the
96 * puzzle as implemented in this source file takes the following
99 * - When checking a user-supplied solution for correctness, only
100 * verify that there exists _at least_ one matching.
101 * - When generating a puzzle, enforce that there must be
104 * Algorithmic implications
105 * ------------------------
107 * Another way of phrasing the tree/tent matching criterion is to
108 * say that the bipartite adjacency graph between trees and tents
109 * has a perfect matching. That is, if you construct a graph which
110 * has a vertex per tree and a vertex per tent, and an edge between
111 * any tree and tent which are orthogonally adjacent, it is
112 * possible to find a set of N edges of that graph (where N is the
113 * number of trees and also the number of tents) which between them
114 * connect every tree to every tent.
116 * The most efficient known algorithms for finding such a matching
117 * given a graph, as far as I'm aware, are the Munkres assignment
118 * algorithm (also known as the Hungarian algorithm) and the
119 * Ford-Fulkerson algorithm (for finding optimal flows in
120 * networks). Each of these takes O(N^3) running time; so we're
121 * talking O(N^3) time to verify any candidate solution to this
122 * puzzle. That's just about OK if you're doing it once per mouse
123 * click (and in fact not even that, since the sensible thing to do
124 * is check all the _other_ puzzle criteria and only wade into this
125 * quagmire if none are violated); but if the solver had to keep
126 * doing N^3 work internally, then it would probably end up with
127 * more like N^5 or N^6 running time, and grid generation would
128 * become very clunky.
130 * Fortunately, I've been able to prove a very useful property of
131 * _unique_ perfect matchings, by adapting the proof of Hall's
132 * Marriage Theorem. For those unaware of Hall's Theorem, I'll
133 * recap it and its proof: it states that a bipartite graph
134 * contains a perfect matching iff every set of vertices on the
135 * left side of the graph have a neighbourhood _at least_ as big on
138 * This condition is obviously satisfied if a perfect matching does
139 * exist; each left-side node has a distinct right-side node which
140 * is the one assigned to it by the matching, and thus any set of n
141 * left vertices must have a combined neighbourhood containing at
142 * least the n corresponding right vertices, and possibly others
143 * too. Alternatively, imagine if you had (say) three left-side
144 * nodes all of which were connected to only two right-side nodes
145 * between them: any perfect matching would have to assign one of
146 * those two right nodes to each of the three left nodes, and still
147 * give the three left nodes a different right node each. This is
148 * of course impossible.
150 * To prove the converse (that if every subset of left vertices
151 * satisfies the Hall condition then a perfect matching exists),
152 * consider trying to find a proper subset of the left vertices
153 * which _exactly_ satisfies the Hall condition: that is, its right
154 * neighbourhood is precisely the same size as it. If we can find
155 * such a subset, then we can split the bipartite graph into two
156 * smaller ones: one consisting of the left subset and its right
157 * neighbourhood, the other consisting of everything else. Edges
158 * from the left side of the former graph to the right side of the
159 * latter do not exist, by construction; edges from the right side
160 * of the former to the left of the latter cannot be part of any
161 * perfect matching because otherwise the left subset would not be
162 * left with enough distinct right vertices to connect to (this is
163 * exactly the same deduction used in Solo's set analysis). You can
164 * then prove (left as an exercise) that both these smaller graphs
165 * still satisfy the Hall condition, and therefore the proof will
166 * follow by induction.
168 * There's one other possibility, which is the case where _no_
169 * proper subset of the left vertices has a right neighbourhood of
170 * exactly the same size. That is, every left subset has a strictly
171 * _larger_ right neighbourhood. In this situation, we can simply
172 * remove an _arbitrary_ edge from the graph. This cannot reduce
173 * the size of any left subset's right neighbourhood by more than
174 * one, so if all neighbourhoods were strictly bigger than they
175 * needed to be initially, they must now still be _at least as big_
176 * as they need to be. So we can keep throwing out arbitrary edges
177 * until we find a set which exactly satisfies the Hall condition,
178 * and then proceed as above. []
180 * That's Hall's theorem. I now build on this by examining the
181 * circumstances in which a bipartite graph can have a _unique_
182 * perfect matching. It is clear that in the second case, where no
183 * left subset exactly satisfies the Hall condition and so we can
184 * remove an arbitrary edge, there cannot be a unique perfect
185 * matching: given one perfect matching, we choose our arbitrary
186 * removed edge to be one of those contained in it, and then we can
187 * still find a perfect matching in the remaining graph, which will
188 * be a distinct perfect matching in the original.
190 * So it is a necessary condition for a unique perfect matching
191 * that there must be at least one proper left subset which
192 * _exactly_ satisfies the Hall condition. But now consider the
193 * smaller graph constructed by taking that left subset and its
194 * neighbourhood: if the graph as a whole had a unique perfect
195 * matching, then so must this smaller one, which means we can find
196 * a proper left subset _again_, and so on. Repeating this process
197 * must eventually reduce us to a graph with only one left-side
198 * vertex (so there are no proper subsets at all); this vertex must
199 * be connected to only one right-side vertex, and hence must be so
200 * in the original graph as well (by construction). So we can
201 * discard this vertex pair from the graph, and any other edges
202 * that involved it (which will by construction be from other left
203 * vertices only), and the resulting smaller graph still has a
204 * unique perfect matching which means we can do the same thing
207 * In other words, given any bipartite graph with a unique perfect
208 * matching, we can find that matching by the following extremely
211 * - Find a left-side vertex which is only connected to one
213 * - Assign those vertices to one another, and therefore discard
214 * any other edges connecting to that right vertex.
215 * - Repeat until all vertices have been matched.
217 * This algorithm can be run in O(V+E) time (where V is the number
218 * of vertices and E is the number of edges in the graph), and the
219 * only way it can fail is if there is not a unique perfect
220 * matching (either because there is no matching at all, or because
221 * it isn't unique; but it can't distinguish those cases).
223 * Thus, the internal solver in this source file can be confident
224 * that if the tree/tent matching is uniquely determined by the
225 * tree and tent positions, it can find it using only this kind of
226 * obvious and simple operation: assign a tree to a tent if it
227 * cannot possibly belong to any other tent, and vice versa. If the
228 * solver were _only_ trying to determine the matching, even that
229 * `vice versa' wouldn't be required; but it can come in handy when
230 * not all the tents have been placed yet. I can therefore be
231 * reasonably confident that as long as my solver doesn't need to
232 * cope with grids that have a non-unique matching, it will also
233 * not need to do anything complicated like set analysis between
238 * In standalone solver mode, `verbose' is a variable which can be
239 * set by command-line option; in debugging mode it's simply always
242 #if defined STANDALONE_SOLVER
243 #define SOLVER_DIAGNOSTICS
245 #elif defined SOLVER_DIAGNOSTICS
250 * Difficulty levels. I do some macro ickery here to ensure that my
251 * enum and the various forms of my name list always match up.
253 #define DIFFLIST(A) \
256 #define ENUM(upper,title,lower) DIFF_ ## upper,
257 #define TITLE(upper,title,lower) #title,
258 #define ENCODE(upper,title,lower) #lower
259 #define CONFIG(upper,title,lower) ":" #title
260 enum { DIFFLIST(ENUM
) DIFFCOUNT
};
261 static char const *const tents_diffnames
[] = { DIFFLIST(TITLE
) };
262 static char const tents_diffchars
[] = DIFFLIST(ENCODE
);
263 #define DIFFCONFIG DIFFLIST(CONFIG)
275 enum { BLANK
, TREE
, TENT
, NONTENT
, MAGIC
};
290 struct numbers
*numbers
;
291 int completed
, used_solve
;
294 static game_params
*default_params(void)
296 game_params
*ret
= snew(game_params
);
299 ret
->diff
= DIFF_EASY
;
304 static const struct game_params tents_presets
[] = {
308 {10, 10, DIFF_TRICKY
},
310 {15, 15, DIFF_TRICKY
},
313 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
318 if (i
< 0 || i
>= lenof(tents_presets
))
321 ret
= snew(game_params
);
322 *ret
= tents_presets
[i
];
324 sprintf(str
, "%dx%d %s", ret
->w
, ret
->h
, tents_diffnames
[ret
->diff
]);
331 static void free_params(game_params
*params
)
336 static game_params
*dup_params(game_params
*params
)
338 game_params
*ret
= snew(game_params
);
339 *ret
= *params
; /* structure copy */
343 static void decode_params(game_params
*params
, char const *string
)
345 params
->w
= params
->h
= atoi(string
);
346 while (*string
&& isdigit((unsigned char)*string
)) string
++;
347 if (*string
== 'x') {
349 params
->h
= atoi(string
);
350 while (*string
&& isdigit((unsigned char)*string
)) string
++;
352 if (*string
== 'd') {
355 for (i
= 0; i
< DIFFCOUNT
; i
++)
356 if (*string
== tents_diffchars
[i
])
358 if (*string
) string
++;
362 static char *encode_params(game_params
*params
, int full
)
366 sprintf(buf
, "%dx%d", params
->w
, params
->h
);
368 sprintf(buf
+ strlen(buf
), "d%c",
369 tents_diffchars
[params
->diff
]);
373 static config_item
*game_configure(game_params
*params
)
378 ret
= snewn(4, config_item
);
380 ret
[0].name
= "Width";
381 ret
[0].type
= C_STRING
;
382 sprintf(buf
, "%d", params
->w
);
383 ret
[0].sval
= dupstr(buf
);
386 ret
[1].name
= "Height";
387 ret
[1].type
= C_STRING
;
388 sprintf(buf
, "%d", params
->h
);
389 ret
[1].sval
= dupstr(buf
);
392 ret
[2].name
= "Difficulty";
393 ret
[2].type
= C_CHOICES
;
394 ret
[2].sval
= DIFFCONFIG
;
395 ret
[2].ival
= params
->diff
;
405 static game_params
*custom_params(config_item
*cfg
)
407 game_params
*ret
= snew(game_params
);
409 ret
->w
= atoi(cfg
[0].sval
);
410 ret
->h
= atoi(cfg
[1].sval
);
411 ret
->diff
= cfg
[2].ival
;
416 static char *validate_params(game_params
*params
, int full
)
419 * Generating anything under 4x4 runs into trouble of one kind
422 if (params
->w
< 4 || params
->h
< 4)
423 return "Width and height must both be at least four";
428 * Scratch space for solver.
430 enum { N
, U
, L
, R
, D
, MAXDIR
}; /* link directions */
431 #define dx(d) ( ((d)==R) - ((d)==L) )
432 #define dy(d) ( ((d)==D) - ((d)==U) )
433 #define F(d) ( U + D - (d) )
434 struct solver_scratch
{
435 char *links
; /* mapping between trees and tents */
437 char *place
, *mrows
, *trows
;
440 static struct solver_scratch
*new_scratch(int w
, int h
)
442 struct solver_scratch
*ret
= snew(struct solver_scratch
);
444 ret
->links
= snewn(w
*h
, char);
445 ret
->locs
= snewn(max(w
, h
), int);
446 ret
->place
= snewn(max(w
, h
), char);
447 ret
->mrows
= snewn(3 * max(w
, h
), char);
448 ret
->trows
= snewn(3 * max(w
, h
), char);
453 static void free_scratch(struct solver_scratch
*sc
)
464 * Solver. Returns 0 for impossibility, 1 for success, 2 for
465 * ambiguity or failure to converge.
467 static int tents_solve(int w
, int h
, const char *grid
, int *numbers
,
468 char *soln
, struct solver_scratch
*sc
, int diff
)
471 char *mrow
, *mrow1
, *mrow2
, *trow
, *trow1
, *trow2
;
474 * Set up solver data.
476 memset(sc
->links
, N
, w
*h
);
479 * Set up solution array.
481 memcpy(soln
, grid
, w
*h
);
487 int done_something
= FALSE
;
490 * Any tent which has only one unattached tree adjacent to
491 * it can be tied to that tree.
493 for (y
= 0; y
< h
; y
++)
494 for (x
= 0; x
< w
; x
++)
495 if (soln
[y
*w
+x
] == TENT
&& !sc
->links
[y
*w
+x
]) {
498 for (d
= 1; d
< MAXDIR
; d
++) {
499 int x2
= x
+ dx(d
), y2
= y
+ dy(d
);
500 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
&&
501 soln
[y2
*w
+x2
] == TREE
&&
502 !sc
->links
[y2
*w
+x2
]) {
504 break; /* found more than one */
510 if (d
== MAXDIR
&& linkd
== 0) {
511 #ifdef SOLVER_DIAGNOSTICS
513 printf("tent at %d,%d cannot link to anything\n",
516 return 0; /* no solution exists */
517 } else if (d
== MAXDIR
) {
518 int x2
= x
+ dx(linkd
), y2
= y
+ dy(linkd
);
520 #ifdef SOLVER_DIAGNOSTICS
522 printf("tent at %d,%d can only link to tree at"
523 " %d,%d\n", x
, y
, x2
, y2
);
526 sc
->links
[y
*w
+x
] = linkd
;
527 sc
->links
[y2
*w
+x2
] = F(linkd
);
528 done_something
= TRUE
;
535 break; /* don't do anything else! */
538 * Mark a blank square as NONTENT if it is not orthogonally
539 * adjacent to any unmatched tree.
541 for (y
= 0; y
< h
; y
++)
542 for (x
= 0; x
< w
; x
++)
543 if (soln
[y
*w
+x
] == BLANK
) {
544 int can_be_tent
= FALSE
;
546 for (d
= 1; d
< MAXDIR
; d
++) {
547 int x2
= x
+ dx(d
), y2
= y
+ dy(d
);
548 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
&&
549 soln
[y2
*w
+x2
] == TREE
&&
555 #ifdef SOLVER_DIAGNOSTICS
557 printf("%d,%d cannot be a tent (no adjacent"
558 " unmatched tree)\n", x
, y
);
560 soln
[y
*w
+x
] = NONTENT
;
561 done_something
= TRUE
;
569 * Mark a blank square as NONTENT if it is (perhaps
570 * diagonally) adjacent to any other tent.
572 for (y
= 0; y
< h
; y
++)
573 for (x
= 0; x
< w
; x
++)
574 if (soln
[y
*w
+x
] == BLANK
) {
575 int dx
, dy
, imposs
= FALSE
;
577 for (dy
= -1; dy
<= +1; dy
++)
578 for (dx
= -1; dx
<= +1; dx
++)
580 int x2
= x
+ dx
, y2
= y
+ dy
;
581 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
&&
582 soln
[y2
*w
+x2
] == TENT
)
587 #ifdef SOLVER_DIAGNOSTICS
589 printf("%d,%d cannot be a tent (adjacent tent)\n",
592 soln
[y
*w
+x
] = NONTENT
;
593 done_something
= TRUE
;
601 * Any tree which has exactly one {unattached tent, BLANK}
602 * adjacent to it must have its tent in that square.
604 for (y
= 0; y
< h
; y
++)
605 for (x
= 0; x
< w
; x
++)
606 if (soln
[y
*w
+x
] == TREE
&& !sc
->links
[y
*w
+x
]) {
607 int linkd
= 0, linkd2
= 0, nd
= 0;
609 for (d
= 1; d
< MAXDIR
; d
++) {
610 int x2
= x
+ dx(d
), y2
= y
+ dy(d
);
611 if (!(x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
))
613 if (soln
[y2
*w
+x2
] == BLANK
||
614 (soln
[y2
*w
+x2
] == TENT
&& !sc
->links
[y2
*w
+x2
])) {
624 #ifdef SOLVER_DIAGNOSTICS
626 printf("tree at %d,%d cannot link to anything\n",
629 return 0; /* no solution exists */
630 } else if (nd
== 1) {
631 int x2
= x
+ dx(linkd
), y2
= y
+ dy(linkd
);
633 #ifdef SOLVER_DIAGNOSTICS
635 printf("tree at %d,%d can only link to tent at"
636 " %d,%d\n", x
, y
, x2
, y2
);
638 soln
[y2
*w
+x2
] = TENT
;
639 sc
->links
[y
*w
+x
] = linkd
;
640 sc
->links
[y2
*w
+x2
] = F(linkd
);
641 done_something
= TRUE
;
642 } else if (nd
== 2 && (!dx(linkd
) != !dx(linkd2
)) &&
643 diff
>= DIFF_TRICKY
) {
645 * If there are two possible places where
646 * this tree's tent can go, and they are
647 * diagonally separated rather than being
648 * on opposite sides of the tree, then the
649 * square (other than the tree square)
650 * which is adjacent to both of them must
653 int x2
= x
+ dx(linkd
) + dx(linkd2
);
654 int y2
= y
+ dy(linkd
) + dy(linkd2
);
655 assert(x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
);
656 if (soln
[y2
*w
+x2
] == BLANK
) {
657 #ifdef SOLVER_DIAGNOSTICS
659 printf("possible tent locations for tree at"
660 " %d,%d rule out tent at %d,%d\n",
663 soln
[y2
*w
+x2
] = NONTENT
;
664 done_something
= TRUE
;
673 * If localised deductions about the trees and tents
674 * themselves haven't helped us, it's time to resort to the
675 * numbers round the grid edge. For each row and column, we
676 * go through all possible combinations of locations for
677 * the unplaced tents, rule out any which have adjacent
678 * tents, and spot any square which is given the same state
679 * by all remaining combinations.
681 for (i
= 0; i
< w
+h
; i
++) {
682 int start
, step
, len
, start1
, start2
, n
, k
;
686 * This is the number for a column.
701 * This is the number for a row.
716 if (diff
< DIFF_TRICKY
) {
718 * In Easy mode, we don't look at the effect of one
719 * row on the next (i.e. ruling out a square if all
720 * possibilities for an adjacent row place a tent
723 start1
= start2
= -1;
729 * Count and store the locations of the free squares,
730 * and also count the number of tents already placed.
733 for (j
= 0; j
< len
; j
++) {
734 if (soln
[start
+j
*step
] == TENT
)
735 k
--; /* one fewer tent to place */
736 else if (soln
[start
+j
*step
] == BLANK
)
741 continue; /* nothing left to do here */
744 * Now we know we're placing k tents in n squares. Set
745 * up the first possibility.
747 for (j
= 0; j
< n
; j
++)
748 sc
->place
[j
] = (j
< k ? TENT
: NONTENT
);
751 * We're aiming to find squares in this row which are
752 * invariant over all valid possibilities. Thus, we
753 * maintain the current state of that invariance. We
754 * start everything off at MAGIC to indicate that it
755 * hasn't been set up yet.
758 mrow1
= sc
->mrows
+ len
;
759 mrow2
= sc
->mrows
+ 2*len
;
761 trow1
= sc
->trows
+ len
;
762 trow2
= sc
->trows
+ 2*len
;
763 memset(mrow
, MAGIC
, 3*len
);
766 * And iterate over all possibilities.
772 * See if this possibility is valid. The only way
773 * it can fail to be valid is if it contains two
774 * adjacent tents. (Other forms of invalidity, such
775 * as containing a tent adjacent to one already
776 * placed, will have been dealt with already by
777 * other parts of the solver.)
780 for (j
= 0; j
+1 < n
; j
++)
781 if (sc
->place
[j
] == TENT
&&
782 sc
->place
[j
+1] == TENT
&&
783 sc
->locs
[j
+1] == sc
->locs
[j
]+1) {
790 * Merge this valid combination into mrow.
792 memset(trow
, MAGIC
, len
);
793 memset(trow
+len
, BLANK
, 2*len
);
794 for (j
= 0; j
< n
; j
++) {
795 trow
[sc
->locs
[j
]] = sc
->place
[j
];
796 if (sc
->place
[j
] == TENT
) {
798 for (jj
= sc
->locs
[j
]-1; jj
<= sc
->locs
[j
]+1; jj
++)
799 if (jj
>= 0 && jj
< len
)
800 trow1
[jj
] = trow2
[jj
] = NONTENT
;
804 for (j
= 0; j
< 3*len
; j
++) {
805 if (trow
[j
] == MAGIC
)
807 if (mrow
[j
] == MAGIC
|| mrow
[j
] == trow
[j
]) {
809 * Either this is the first valid
810 * placement we've found at all, or
811 * this square's contents are
812 * consistent with every previous valid
818 * This square's contents fail to match
819 * what they were in a different
820 * combination, so we cannot deduce
821 * anything about this square.
829 * Find the next combination of k choices from n.
830 * We do this by finding the rightmost tent which
831 * can be moved one place right, doing so, and
832 * shunting all tents to the right of that as far
833 * left as they can go.
836 for (j
= n
-1; j
> 0; j
--) {
837 if (sc
->place
[j
] == TENT
)
839 if (sc
->place
[j
] == NONTENT
&& sc
->place
[j
-1] == TENT
) {
840 sc
->place
[j
-1] = NONTENT
;
843 sc
->place
[++j
] = TENT
;
845 sc
->place
[j
] = NONTENT
;
850 break; /* we've finished */
854 * It's just possible that _no_ placement was valid, in
855 * which case we have an internally inconsistent
858 if (mrow
[sc
->locs
[0]] == MAGIC
)
859 return 0; /* inconsistent */
862 * Now go through mrow and see if there's anything
863 * we've deduced which wasn't already mentioned in soln.
865 for (j
= 0; j
< len
; j
++) {
868 for (whichrow
= 0; whichrow
< 3; whichrow
++) {
869 char *mthis
= mrow
+ whichrow
* len
;
870 int tstart
= (whichrow
== 0 ? start
:
871 whichrow
== 1 ? start1
: start2
);
873 mthis
[j
] != MAGIC
&& mthis
[j
] != BLANK
&&
874 soln
[tstart
+j
*step
] == BLANK
) {
875 int pos
= tstart
+j
*step
;
877 #ifdef SOLVER_DIAGNOSTICS
879 printf("%s %d forces %s at %d,%d\n",
880 step
==1 ?
"row" : "column",
881 step
==1 ? start
/w
: start
,
882 mthis
[j
] == TENT ?
"tent" : "non-tent",
885 soln
[pos
] = mthis
[j
];
886 done_something
= TRUE
;
900 * The solver has nothing further it can do. Return 1 if both
901 * soln and sc->links are completely filled in, or 2 otherwise.
903 for (y
= 0; y
< h
; y
++)
904 for (x
= 0; x
< w
; x
++) {
905 if (soln
[y
*w
+x
] == BLANK
)
907 if (soln
[y
*w
+x
] != NONTENT
&& sc
->links
[y
*w
+x
] == 0)
914 static char *new_game_desc(game_params
*params
, random_state
*rs
,
915 char **aux
, int interactive
)
917 int w
= params
->w
, h
= params
->h
;
918 int ntrees
= w
* h
/ 5;
919 char *grid
= snewn(w
*h
, char);
920 char *puzzle
= snewn(w
*h
, char);
921 int *numbers
= snewn(w
+h
, int);
922 char *soln
= snewn(w
*h
, char);
923 int *temp
= snewn(2*w
*h
, int);
924 int maxedges
= ntrees
*4 + w
*h
;
925 int *edges
= snewn(2*maxedges
, int);
926 int *capacity
= snewn(maxedges
, int);
927 int *flow
= snewn(maxedges
, int);
928 struct solver_scratch
*sc
= new_scratch(w
, h
);
933 * Since this puzzle has many global deductions and doesn't
934 * permit limited clue sets, generating grids for this puzzle
935 * is hard enough that I see no better option than to simply
936 * generate a solution and see if it's unique and has the
937 * required difficulty. This turns out to be computationally
940 * We chose our tree count (hence also tent count) by dividing
941 * the total grid area by five above. Why five? Well, w*h/4 is
942 * the maximum number of tents you can _possibly_ fit into the
943 * grid without violating the separation criterion, and to
944 * achieve that you are constrained to a very small set of
945 * possible layouts (the obvious one with a tent at every
946 * (even,even) coordinate, and trivial variations thereon). So
947 * if we reduce the tent count a bit more, we enable more
948 * random-looking placement; 5 turns out to be a plausible
949 * figure which yields sensible puzzles. Increasing the tent
950 * count would give puzzles whose solutions were too regimented
951 * and could be solved by the use of that knowledge (and would
952 * also take longer to find a viable placement); decreasing it
953 * would make the grids emptier and more boring.
955 * Actually generating a grid is a matter of first placing the
956 * tents, and then placing the trees by the use of maxflow
957 * (finding a distinct square adjacent to every tent). We do it
958 * this way round because otherwise satisfying the tent
959 * separation condition would become onerous: most randomly
960 * chosen tent layouts do not satisfy this condition, so we'd
961 * have gone to a lot of work before finding that a candidate
962 * layout was unusable. Instead, we place the tents first and
963 * ensure they meet the separation criterion _before_ doing
964 * lots of computation; this works much better.
966 * The maxflow algorithm is not randomised, so employed naively
967 * it would give rise to grids with clear structure and
968 * directional bias. Hence, I assign the network nodes as seen
969 * by maxflow to be a _random_ permutation of the squares of
970 * the grid, so that any bias shown by maxflow towards
971 * low-numbered nodes is turned into a random bias.
973 * This generation strategy can fail at many points, including
974 * as early as tent placement (if you get a bad random order in
975 * which to greedily try the grid squares, you won't even
976 * manage to find enough mutually non-adjacent squares to put
977 * the tents in). Then it can fail if maxflow doesn't manage to
978 * find a good enough matching (i.e. the tent placements don't
979 * admit any adequate tree placements); and finally it can fail
980 * if the solver finds that the problem has the wrong
981 * difficulty (including being actually non-unique). All of
982 * these, however, are insufficiently frequent to cause
986 if (params
->diff
> DIFF_EASY
&& params
->w
<= 4 && params
->h
<= 4)
987 params
->diff
= DIFF_EASY
; /* downgrade to prevent tight loop */
991 * Arrange the grid squares into a random order.
993 for (i
= 0; i
< w
*h
; i
++)
995 shuffle(temp
, w
*h
, sizeof(*temp
), rs
);
998 * The first `ntrees' entries in temp which we can get
999 * without making two tents adjacent will be the tent
1002 memset(grid
, BLANK
, w
*h
);
1004 for (i
= 0; i
< w
*h
&& j
> 0; i
++) {
1005 int x
= temp
[i
] % w
, y
= temp
[i
] / w
;
1006 int dy
, dx
, ok
= TRUE
;
1008 for (dy
= -1; dy
<= +1; dy
++)
1009 for (dx
= -1; dx
<= +1; dx
++)
1010 if (x
+dx
>= 0 && x
+dx
< w
&&
1011 y
+dy
>= 0 && y
+dy
< h
&&
1012 grid
[(y
+dy
)*w
+(x
+dx
)] == TENT
)
1016 grid
[temp
[i
]] = TENT
;
1021 continue; /* couldn't place all the tents */
1024 * Now we build up the list of graph edges.
1027 for (i
= 0; i
< w
*h
; i
++) {
1028 if (grid
[temp
[i
]] == TENT
) {
1029 for (j
= 0; j
< w
*h
; j
++) {
1030 if (grid
[temp
[j
]] != TENT
) {
1031 int xi
= temp
[i
] % w
, yi
= temp
[i
] / w
;
1032 int xj
= temp
[j
] % w
, yj
= temp
[j
] / w
;
1033 if (abs(xi
-xj
) + abs(yi
-yj
) == 1) {
1034 edges
[nedges
*2] = i
;
1035 edges
[nedges
*2+1] = j
;
1036 capacity
[nedges
] = 1;
1043 * Special node w*h is the sink node; any non-tent node
1044 * has an edge going to it.
1046 edges
[nedges
*2] = i
;
1047 edges
[nedges
*2+1] = w
*h
;
1048 capacity
[nedges
] = 1;
1054 * Special node w*h+1 is the source node, with an edge going to
1057 for (i
= 0; i
< w
*h
; i
++) {
1058 if (grid
[temp
[i
]] == TENT
) {
1059 edges
[nedges
*2] = w
*h
+1;
1060 edges
[nedges
*2+1] = i
;
1061 capacity
[nedges
] = 1;
1066 assert(nedges
<= maxedges
);
1069 * Now we're ready to call the maxflow algorithm to place the
1072 j
= maxflow(w
*h
+2, w
*h
+1, w
*h
, nedges
, edges
, capacity
, flow
, NULL
);
1075 continue; /* couldn't place all the tents */
1078 * We've placed the trees. Now we need to work out _where_
1079 * we've placed them, which is a matter of reading back out
1080 * from the `flow' array.
1082 for (i
= 0; i
< nedges
; i
++) {
1083 if (edges
[2*i
] < w
*h
&& edges
[2*i
+1] < w
*h
&& flow
[i
] > 0)
1084 grid
[temp
[edges
[2*i
+1]]] = TREE
;
1088 * I think it looks ugly if there isn't at least one of
1089 * _something_ (tent or tree) in each row and each column
1090 * of the grid. This doesn't give any information away
1091 * since a completely empty row/column is instantly obvious
1092 * from the clues (it has no trees and a zero).
1094 for (i
= 0; i
< w
; i
++) {
1095 for (j
= 0; j
< h
; j
++) {
1096 if (grid
[j
*w
+i
] != BLANK
)
1097 break; /* found something in this column */
1100 break; /* found empty column */
1103 continue; /* a column was empty */
1105 for (j
= 0; j
< h
; j
++) {
1106 for (i
= 0; i
< w
; i
++) {
1107 if (grid
[j
*w
+i
] != BLANK
)
1108 break; /* found something in this row */
1111 break; /* found empty row */
1114 continue; /* a row was empty */
1117 * Now set up the numbers round the edge.
1119 for (i
= 0; i
< w
; i
++) {
1121 for (j
= 0; j
< h
; j
++)
1122 if (grid
[j
*w
+i
] == TENT
)
1126 for (i
= 0; i
< h
; i
++) {
1128 for (j
= 0; j
< w
; j
++)
1129 if (grid
[i
*w
+j
] == TENT
)
1135 * And now actually solve the puzzle, to see whether it's
1136 * unique and has the required difficulty.
1138 for (i
= 0; i
< w
*h
; i
++)
1139 puzzle
[i
] = grid
[i
] == TREE ? TREE
: BLANK
;
1140 i
= tents_solve(w
, h
, puzzle
, numbers
, soln
, sc
, params
->diff
-1);
1141 j
= tents_solve(w
, h
, puzzle
, numbers
, soln
, sc
, params
->diff
);
1144 * We expect solving with difficulty params->diff to have
1145 * succeeded (otherwise the problem is too hard), and
1146 * solving with diff-1 to have failed (otherwise it's too
1149 if (i
== 2 && j
== 1)
1154 * That's it. Encode as a game ID.
1156 ret
= snewn((w
+h
)*40 + ntrees
+ (w
*h
)/26 + 1, char);
1159 for (i
= 0; i
<= w
*h
; i
++) {
1160 int c
= (i
< w
*h ? grid
[i
] == TREE
: 1);
1162 *p
++ = (j
== 0 ?
'_' : j
-1 + 'a');
1172 for (i
= 0; i
< w
+h
; i
++)
1173 p
+= sprintf(p
, ",%d", numbers
[i
]);
1175 ret
= sresize(ret
, p
- ret
, char);
1178 * And encode the solution as an aux_info.
1180 *aux
= snewn(ntrees
* 40, char);
1183 for (i
= 0; i
< w
*h
; i
++)
1184 if (grid
[i
] == TENT
)
1185 p
+= sprintf(p
, ";T%d,%d", i
%w
, i
/w
);
1187 *aux
= sresize(*aux
, p
- *aux
, char);
1202 static char *validate_desc(game_params
*params
, char *desc
)
1204 int w
= params
->w
, h
= params
->h
;
1208 while (*desc
&& *desc
!= ',') {
1211 else if (*desc
>= 'a' && *desc
< 'z')
1212 area
+= *desc
- 'a' + 2;
1213 else if (*desc
== 'z')
1215 else if (*desc
== '!' || *desc
== '-')
1218 return "Invalid character in grid specification";
1223 for (i
= 0; i
< w
+h
; i
++) {
1225 return "Not enough numbers given after grid specification";
1226 else if (*desc
!= ',')
1227 return "Invalid character in number list";
1229 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1233 return "Unexpected additional data at end of game description";
1237 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1239 int w
= params
->w
, h
= params
->h
;
1240 game_state
*state
= snew(game_state
);
1243 state
->p
= *params
; /* structure copy */
1244 state
->grid
= snewn(w
*h
, char);
1245 state
->numbers
= snew(struct numbers
);
1246 state
->numbers
->refcount
= 1;
1247 state
->numbers
->numbers
= snewn(w
+h
, int);
1248 state
->completed
= state
->used_solve
= FALSE
;
1251 memset(state
->grid
, BLANK
, w
*h
);
1260 else if (*desc
>= 'a' && *desc
< 'z')
1261 run
= *desc
- ('a'-1);
1262 else if (*desc
== 'z') {
1266 assert(*desc
== '!' || *desc
== '-');
1268 type
= (*desc
== '!' ? TENT
: NONTENT
);
1274 assert(i
>= 0 && i
<= w
*h
);
1276 assert(type
== TREE
);
1280 state
->grid
[i
++] = type
;
1284 for (i
= 0; i
< w
+h
; i
++) {
1285 assert(*desc
== ',');
1287 state
->numbers
->numbers
[i
] = atoi(desc
);
1288 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1296 static game_state
*dup_game(game_state
*state
)
1298 int w
= state
->p
.w
, h
= state
->p
.h
;
1299 game_state
*ret
= snew(game_state
);
1301 ret
->p
= state
->p
; /* structure copy */
1302 ret
->grid
= snewn(w
*h
, char);
1303 memcpy(ret
->grid
, state
->grid
, w
*h
);
1304 ret
->numbers
= state
->numbers
;
1305 state
->numbers
->refcount
++;
1306 ret
->completed
= state
->completed
;
1307 ret
->used_solve
= state
->used_solve
;
1312 static void free_game(game_state
*state
)
1314 if (--state
->numbers
->refcount
<= 0) {
1315 sfree(state
->numbers
->numbers
);
1316 sfree(state
->numbers
);
1322 static char *solve_game(game_state
*state
, game_state
*currstate
,
1323 char *aux
, char **error
)
1325 int w
= state
->p
.w
, h
= state
->p
.h
;
1329 * If we already have the solution, save ourselves some
1334 struct solver_scratch
*sc
= new_scratch(w
, h
);
1340 soln
= snewn(w
*h
, char);
1341 ret
= tents_solve(w
, h
, state
->grid
, state
->numbers
->numbers
,
1342 soln
, sc
, DIFFCOUNT
-1);
1347 *error
= "This puzzle is not self-consistent";
1349 *error
= "Unable to find a unique solution for this puzzle";
1354 * Construct a move string which turns the current state
1355 * into the solved state.
1357 move
= snewn(w
*h
* 40, char);
1360 for (i
= 0; i
< w
*h
; i
++)
1361 if (soln
[i
] == TENT
)
1362 p
+= sprintf(p
, ";T%d,%d", i
%w
, i
/w
);
1364 move
= sresize(move
, p
- move
, char);
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 */
1414 static game_ui
*new_ui(game_state
*state
)
1416 game_ui
*ui
= snew(game_ui
);
1417 ui
->dsx
= ui
->dsy
= -1;
1418 ui
->dex
= ui
->dey
= -1;
1419 ui
->drag_button
= -1;
1420 ui
->drag_ok
= FALSE
;
1424 static void free_ui(game_ui
*ui
)
1429 static char *encode_ui(game_ui
*ui
)
1434 static void decode_ui(game_ui
*ui
, char *encoding
)
1438 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1439 game_state
*newstate
)
1443 struct game_drawstate
{
1450 #define PREFERRED_TILESIZE 32
1451 #define TILESIZE (ds->tilesize)
1452 #define TLBORDER (TILESIZE/2)
1453 #define BRBORDER (TILESIZE*3/2)
1454 #define COORD(x) ( (x) * TILESIZE + TLBORDER )
1455 #define FROMCOORD(x) ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 )
1457 #define FLASH_TIME 0.30F
1459 static int drag_xform(game_ui
*ui
, int x
, int y
, int v
)
1461 int xmin
, ymin
, xmax
, ymax
;
1463 xmin
= min(ui
->dsx
, ui
->dex
);
1464 xmax
= max(ui
->dsx
, ui
->dex
);
1465 ymin
= min(ui
->dsy
, ui
->dey
);
1466 ymax
= max(ui
->dsy
, ui
->dey
);
1469 * Left-dragging has no effect, so we treat a left-drag as a
1470 * single click on dsx,dsy.
1472 if (ui
->drag_button
== LEFT_BUTTON
) {
1473 xmin
= xmax
= ui
->dsx
;
1474 ymin
= ymax
= ui
->dsy
;
1477 if (x
< xmin
|| x
> xmax
|| y
< ymin
|| y
> ymax
)
1478 return v
; /* no change outside drag area */
1481 return v
; /* trees are inviolate always */
1483 if (xmin
== xmax
&& ymin
== ymax
) {
1485 * Results of a simple click. Left button sets blanks to
1486 * tents; right button sets blanks to non-tents; either
1487 * button clears a non-blank square.
1489 if (ui
->drag_button
== LEFT_BUTTON
)
1490 v
= (v
== BLANK ? TENT
: BLANK
);
1492 v
= (v
== BLANK ? NONTENT
: BLANK
);
1495 * Results of a drag. Left-dragging has no effect.
1496 * Right-dragging sets all blank squares to non-tents and
1497 * has no effect on anything else.
1499 if (ui
->drag_button
== RIGHT_BUTTON
)
1500 v
= (v
== BLANK ? NONTENT
: v
);
1508 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1509 int x
, int y
, int button
)
1511 int w
= state
->p
.w
, h
= state
->p
.h
;
1513 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
1516 if (x
< 0 || y
< 0 || x
>= w
|| y
>= h
)
1519 ui
->drag_button
= button
;
1520 ui
->dsx
= ui
->dex
= x
;
1521 ui
->dsy
= ui
->dey
= y
;
1523 return ""; /* ui updated */
1526 if ((IS_MOUSE_DRAG(button
) || IS_MOUSE_RELEASE(button
)) &&
1527 ui
->drag_button
> 0) {
1528 int xmin
, ymin
, xmax
, ymax
;
1529 char *buf
, *sep
, tmpbuf
[80];
1530 int buflen
, bufsize
, tmplen
;
1534 if (x
< 0 || y
< 0 || x
>= w
|| y
>= h
) {
1535 ui
->drag_ok
= FALSE
;
1538 * Drags are limited to one row or column. Hence, we
1539 * work out which coordinate is closer to the drag
1540 * start, and move it _to_ the drag start.
1542 if (abs(x
- ui
->dsx
) < abs(y
- ui
->dsy
))
1553 if (IS_MOUSE_DRAG(button
))
1554 return ""; /* ui updated */
1557 * The drag has been released. Enact it.
1560 ui
->drag_button
= -1;
1561 return ""; /* drag was just cancelled */
1564 xmin
= min(ui
->dsx
, ui
->dex
);
1565 xmax
= max(ui
->dsx
, ui
->dex
);
1566 ymin
= min(ui
->dsy
, ui
->dey
);
1567 ymax
= max(ui
->dsy
, ui
->dey
);
1568 assert(0 <= xmin
&& xmin
<= xmax
&& xmax
< w
);
1569 assert(0 <= ymin
&& ymin
<= ymax
&& ymax
< h
);
1573 buf
= snewn(bufsize
, char);
1575 for (y
= ymin
; y
<= ymax
; y
++)
1576 for (x
= xmin
; x
<= xmax
; x
++) {
1577 int v
= drag_xform(ui
, x
, y
, state
->grid
[y
*w
+x
]);
1578 if (state
->grid
[y
*w
+x
] != v
) {
1579 tmplen
= sprintf(tmpbuf
, "%s%c%d,%d", sep
,
1580 (int)(v
== BLANK ?
'B' :
1581 v
== TENT ?
'T' : 'N'),
1585 if (buflen
+ tmplen
>= bufsize
) {
1586 bufsize
= buflen
+ tmplen
+ 256;
1587 buf
= sresize(buf
, bufsize
, char);
1590 strcpy(buf
+buflen
, tmpbuf
);
1595 ui
->drag_button
= -1; /* drag is terminated */
1599 return ""; /* ui updated (drag was terminated) */
1609 static game_state
*execute_move(game_state
*state
, char *move
)
1611 int w
= state
->p
.w
, h
= state
->p
.h
;
1613 int x
, y
, m
, n
, i
, j
;
1614 game_state
*ret
= dup_game(state
);
1620 ret
->used_solve
= TRUE
;
1622 * Set all non-tree squares to NONTENT. The rest of the
1623 * solve move will fill the tents in over the top.
1625 for (i
= 0; i
< w
*h
; i
++)
1626 if (ret
->grid
[i
] != TREE
)
1627 ret
->grid
[i
] = NONTENT
;
1629 } else if (c
== 'B' || c
== 'T' || c
== 'N') {
1631 if (sscanf(move
, "%d,%d%n", &x
, &y
, &n
) != 2 ||
1632 x
< 0 || y
< 0 || x
>= w
|| y
>= h
) {
1636 if (ret
->grid
[y
*w
+x
] == TREE
) {
1640 ret
->grid
[y
*w
+x
] = (c
== 'B' ? BLANK
: c
== 'T' ? TENT
: NONTENT
);
1655 * Check for completion.
1657 for (i
= n
= m
= 0; i
< w
*h
; i
++) {
1658 if (ret
->grid
[i
] == TENT
)
1660 else if (ret
->grid
[i
] == TREE
)
1664 int nedges
, maxedges
, *edges
, *capacity
, *flow
;
1667 * We have the right number of tents, which is a
1668 * precondition for the game being complete. Now check that
1669 * the numbers add up.
1671 for (i
= 0; i
< w
; i
++) {
1673 for (j
= 0; j
< h
; j
++)
1674 if (ret
->grid
[j
*w
+i
] == TENT
)
1676 if (ret
->numbers
->numbers
[i
] != n
)
1677 goto completion_check_done
;
1679 for (i
= 0; i
< h
; i
++) {
1681 for (j
= 0; j
< w
; j
++)
1682 if (ret
->grid
[i
*w
+j
] == TENT
)
1684 if (ret
->numbers
->numbers
[w
+i
] != n
)
1685 goto completion_check_done
;
1688 * Also, check that no two tents are adjacent.
1690 for (y
= 0; y
< h
; y
++)
1691 for (x
= 0; x
< w
; x
++) {
1693 ret
->grid
[y
*w
+x
] == TENT
&& ret
->grid
[y
*w
+x
+1] == TENT
)
1694 goto completion_check_done
;
1696 ret
->grid
[y
*w
+x
] == TENT
&& ret
->grid
[(y
+1)*w
+x
] == TENT
)
1697 goto completion_check_done
;
1698 if (x
+1 < w
&& y
+1 < h
) {
1699 if (ret
->grid
[y
*w
+x
] == TENT
&&
1700 ret
->grid
[(y
+1)*w
+(x
+1)] == TENT
)
1701 goto completion_check_done
;
1702 if (ret
->grid
[(y
+1)*w
+x
] == TENT
&&
1703 ret
->grid
[y
*w
+(x
+1)] == TENT
)
1704 goto completion_check_done
;
1709 * OK; we have the right number of tents, they match the
1710 * numeric clues, and they satisfy the non-adjacency
1711 * criterion. Finally, we need to verify that they can be
1712 * placed in a one-to-one matching with the trees such that
1713 * every tent is orthogonally adjacent to its tree.
1715 * This bit is where the hard work comes in: we have to do
1716 * it by finding such a matching using maxflow.
1718 * So we construct a network with one special source node,
1719 * one special sink node, one node per tent, and one node
1723 edges
= snewn(2 * maxedges
, int);
1724 capacity
= snewn(maxedges
, int);
1725 flow
= snewn(maxedges
, int);
1730 * 0..w*h trees/tents
1734 for (y
= 0; y
< h
; y
++)
1735 for (x
= 0; x
< w
; x
++)
1736 if (ret
->grid
[y
*w
+x
] == TREE
) {
1740 * Here we use the direction enum declared for
1741 * the solver. We make use of the fact that the
1742 * directions are declared in the order
1743 * U,L,R,D, meaning that we go through the four
1744 * neighbours of any square in numerically
1747 for (d
= 1; d
< MAXDIR
; d
++) {
1748 int x2
= x
+ dx(d
), y2
= y
+ dy(d
);
1749 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
&&
1750 ret
->grid
[y2
*w
+x2
] == TENT
) {
1751 assert(nedges
< maxedges
);
1752 edges
[nedges
*2] = y
*w
+x
;
1753 edges
[nedges
*2+1] = y2
*w
+x2
;
1754 capacity
[nedges
] = 1;
1758 } else if (ret
->grid
[y
*w
+x
] == TENT
) {
1759 assert(nedges
< maxedges
);
1760 edges
[nedges
*2] = y
*w
+x
;
1761 edges
[nedges
*2+1] = w
*h
+1; /* edge going to sink */
1762 capacity
[nedges
] = 1;
1765 for (y
= 0; y
< h
; y
++)
1766 for (x
= 0; x
< w
; x
++)
1767 if (ret
->grid
[y
*w
+x
] == TREE
) {
1768 assert(nedges
< maxedges
);
1769 edges
[nedges
*2] = w
*h
; /* edge coming from source */
1770 edges
[nedges
*2+1] = y
*w
+x
;
1771 capacity
[nedges
] = 1;
1774 n
= maxflow(w
*h
+2, w
*h
, w
*h
+1, nedges
, edges
, capacity
, flow
, NULL
);
1781 goto completion_check_done
;
1784 * We haven't managed to fault the grid on any count. Score!
1786 ret
->completed
= TRUE
;
1788 completion_check_done
:
1793 /* ----------------------------------------------------------------------
1797 static void game_compute_size(game_params
*params
, int tilesize
,
1800 /* fool the macros */
1801 struct dummy
{ int tilesize
; } dummy
= { tilesize
}, *ds
= &dummy
;
1803 *x
= TLBORDER
+ BRBORDER
+ TILESIZE
* params
->w
;
1804 *y
= TLBORDER
+ BRBORDER
+ TILESIZE
* params
->h
;
1807 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1808 game_params
*params
, int tilesize
)
1810 ds
->tilesize
= tilesize
;
1813 static float *game_colours(frontend
*fe
, int *ncolours
)
1815 float *ret
= snewn(3 * NCOLOURS
, float);
1817 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1819 ret
[COL_GRID
* 3 + 0] = 0.0F
;
1820 ret
[COL_GRID
* 3 + 1] = 0.0F
;
1821 ret
[COL_GRID
* 3 + 2] = 0.0F
;
1823 ret
[COL_GRASS
* 3 + 0] = 0.7F
;
1824 ret
[COL_GRASS
* 3 + 1] = 1.0F
;
1825 ret
[COL_GRASS
* 3 + 2] = 0.5F
;
1827 ret
[COL_TREETRUNK
* 3 + 0] = 0.6F
;
1828 ret
[COL_TREETRUNK
* 3 + 1] = 0.4F
;
1829 ret
[COL_TREETRUNK
* 3 + 2] = 0.0F
;
1831 ret
[COL_TREELEAF
* 3 + 0] = 0.0F
;
1832 ret
[COL_TREELEAF
* 3 + 1] = 0.7F
;
1833 ret
[COL_TREELEAF
* 3 + 2] = 0.0F
;
1835 ret
[COL_TENT
* 3 + 0] = 0.8F
;
1836 ret
[COL_TENT
* 3 + 1] = 0.7F
;
1837 ret
[COL_TENT
* 3 + 2] = 0.0F
;
1839 *ncolours
= NCOLOURS
;
1843 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1845 int w
= state
->p
.w
, h
= state
->p
.h
;
1846 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1849 ds
->started
= FALSE
;
1850 ds
->p
= state
->p
; /* structure copy */
1851 ds
->drawn
= snewn(w
*h
, char);
1852 memset(ds
->drawn
, MAGIC
, w
*h
);
1857 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1863 static void draw_tile(drawing
*dr
, game_drawstate
*ds
,
1864 int x
, int y
, int v
, int printing
)
1866 int tx
= COORD(x
), ty
= COORD(y
);
1867 int cx
= tx
+ TILESIZE
/2, cy
= ty
+ TILESIZE
/2;
1869 clip(dr
, tx
+1, ty
+1, TILESIZE
-1, TILESIZE
-1);
1872 draw_rect(dr
, tx
+1, ty
+1, TILESIZE
-1, TILESIZE
-1,
1873 (v
== BLANK ? COL_BACKGROUND
: COL_GRASS
));
1878 (printing ? draw_rect_outline
: draw_rect
)
1879 (dr
, cx
-TILESIZE
/15, ty
+TILESIZE
*3/10,
1880 2*(TILESIZE
/15)+1, (TILESIZE
*9/10 - TILESIZE
*3/10),
1883 for (i
= 0; i
< (printing ?
2 : 1); i
++) {
1884 int col
= (i
== 1 ? COL_BACKGROUND
: COL_TREELEAF
);
1885 int sub
= i
* (TILESIZE
/32);
1886 draw_circle(dr
, cx
, ty
+TILESIZE
*4/10, TILESIZE
/4 - sub
,
1888 draw_circle(dr
, cx
+TILESIZE
/5, ty
+TILESIZE
/4, TILESIZE
/8 - sub
,
1890 draw_circle(dr
, cx
-TILESIZE
/5, ty
+TILESIZE
/4, TILESIZE
/8 - sub
,
1892 draw_circle(dr
, cx
+TILESIZE
/4, ty
+TILESIZE
*6/13, TILESIZE
/8 - sub
,
1894 draw_circle(dr
, cx
-TILESIZE
/4, ty
+TILESIZE
*6/13, TILESIZE
/8 - sub
,
1897 } else if (v
== TENT
) {
1899 coords
[0] = cx
- TILESIZE
/3;
1900 coords
[1] = cy
+ TILESIZE
/3;
1901 coords
[2] = cx
+ TILESIZE
/3;
1902 coords
[3] = cy
+ TILESIZE
/3;
1904 coords
[5] = cy
- TILESIZE
/3;
1905 draw_polygon(dr
, coords
, 3, (printing ?
-1 : COL_TENT
), COL_TENT
);
1909 draw_update(dr
, tx
+1, ty
+1, TILESIZE
-1, TILESIZE
-1);
1913 * Internal redraw function, used for printing as well as drawing.
1915 static void int_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1916 game_state
*state
, int dir
, game_ui
*ui
,
1917 float animtime
, float flashtime
, int printing
)
1919 int w
= state
->p
.w
, h
= state
->p
.h
;
1922 if (printing
|| !ds
->started
) {
1925 game_compute_size(&state
->p
, TILESIZE
, &ww
, &wh
);
1926 draw_rect(dr
, 0, 0, ww
, wh
, COL_BACKGROUND
);
1927 draw_update(dr
, 0, 0, ww
, wh
);
1932 print_line_width(dr
, TILESIZE
/64);
1937 for (y
= 0; y
<= h
; y
++)
1938 draw_line(dr
, COORD(0), COORD(y
), COORD(w
), COORD(y
), COL_GRID
);
1939 for (x
= 0; x
<= w
; x
++)
1940 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(h
), COL_GRID
);
1945 for (y
= 0; y
< h
; y
++) {
1947 sprintf(buf
, "%d", state
->numbers
->numbers
[y
+w
]);
1948 draw_text(dr
, COORD(w
+1), COORD(y
) + TILESIZE
/2,
1949 FONT_VARIABLE
, TILESIZE
/2, ALIGN_HRIGHT
|ALIGN_VCENTRE
,
1952 for (x
= 0; x
< w
; x
++) {
1954 sprintf(buf
, "%d", state
->numbers
->numbers
[x
]);
1955 draw_text(dr
, COORD(x
) + TILESIZE
/2, COORD(h
+1),
1956 FONT_VARIABLE
, TILESIZE
/2, ALIGN_HCENTRE
|ALIGN_VNORMAL
,
1962 flashing
= (int)(flashtime
* 3 / FLASH_TIME
) != 1;
1969 for (y
= 0; y
< h
; y
++)
1970 for (x
= 0; x
< w
; x
++) {
1971 int v
= state
->grid
[y
*w
+x
];
1974 * We deliberately do not take drag_ok into account
1975 * here, because user feedback suggests that it's
1976 * marginally nicer not to have the drag effects
1977 * flickering on and off disconcertingly.
1979 if (ui
&& ui
->drag_button
>= 0)
1980 v
= drag_xform(ui
, x
, y
, v
);
1982 if (flashing
&& (v
== TREE
|| v
== TENT
))
1985 if (printing
|| ds
->drawn
[y
*w
+x
] != v
) {
1986 draw_tile(dr
, ds
, x
, y
, v
, printing
);
1988 ds
->drawn
[y
*w
+x
] = v
;
1993 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1994 game_state
*state
, int dir
, game_ui
*ui
,
1995 float animtime
, float flashtime
)
1997 int_redraw(dr
, ds
, oldstate
, state
, dir
, ui
, animtime
, flashtime
, FALSE
);
2000 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2001 int dir
, game_ui
*ui
)
2006 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2007 int dir
, game_ui
*ui
)
2009 if (!oldstate
->completed
&& newstate
->completed
&&
2010 !oldstate
->used_solve
&& !newstate
->used_solve
)
2016 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2021 static void game_print_size(game_params
*params
, float *x
, float *y
)
2026 * I'll use 6mm squares by default.
2028 game_compute_size(params
, 600, &pw
, &ph
);
2033 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2037 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2038 game_drawstate ads
, *ds
= &ads
;
2039 game_set_size(dr
, ds
, NULL
, tilesize
);
2041 c
= print_mono_colour(dr
, 1); assert(c
== COL_BACKGROUND
);
2042 c
= print_mono_colour(dr
, 0); assert(c
== COL_GRID
);
2043 c
= print_mono_colour(dr
, 1); assert(c
== COL_GRASS
);
2044 c
= print_mono_colour(dr
, 0); assert(c
== COL_TREETRUNK
);
2045 c
= print_mono_colour(dr
, 0); assert(c
== COL_TREELEAF
);
2046 c
= print_mono_colour(dr
, 0); assert(c
== COL_TENT
);
2048 int_redraw(dr
, ds
, NULL
, state
, +1, NULL
, 0.0F
, 0.0F
, TRUE
);
2052 #define thegame tents
2055 const struct game thegame
= {
2056 "Tents", "games.tents", "tents",
2063 TRUE
, game_configure
, custom_params
,
2071 FALSE
, game_text_format
,
2079 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
2082 game_free_drawstate
,
2086 TRUE
, FALSE
, game_print_size
, game_print
,
2087 FALSE
, /* wants_statusbar */
2088 FALSE
, game_timing_state
,
2089 REQUIRE_RBUTTON
, /* flags */
2092 #ifdef STANDALONE_SOLVER
2096 int main(int argc
, char **argv
)
2100 char *id
= NULL
, *desc
, *err
;
2102 int ret
, diff
, really_verbose
= FALSE
;
2103 struct solver_scratch
*sc
;
2105 while (--argc
> 0) {
2107 if (!strcmp(p
, "-v")) {
2108 really_verbose
= TRUE
;
2109 } else if (!strcmp(p
, "-g")) {
2111 } else if (*p
== '-') {
2112 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
2120 fprintf(stderr
, "usage: %s [-g | -v] <game_id>\n", argv
[0]);
2124 desc
= strchr(id
, ':');
2126 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
2131 p
= default_params();
2132 decode_params(p
, id
);
2133 err
= validate_desc(p
, desc
);
2135 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
2138 s
= new_game(NULL
, p
, desc
);
2139 s2
= new_game(NULL
, p
, desc
);
2141 sc
= new_scratch(p
->w
, p
->h
);
2144 * When solving an Easy puzzle, we don't want to bother the
2145 * user with Hard-level deductions. For this reason, we grade
2146 * the puzzle internally before doing anything else.
2148 ret
= -1; /* placate optimiser */
2149 for (diff
= 0; diff
< DIFFCOUNT
; diff
++) {
2150 ret
= tents_solve(p
->w
, p
->h
, s
->grid
, s
->numbers
->numbers
,
2151 s2
->grid
, sc
, diff
);
2156 if (diff
== DIFFCOUNT
) {
2158 printf("Difficulty rating: too hard to solve internally\n");
2160 printf("Unable to find a unique solution\n");
2164 printf("Difficulty rating: impossible (no solution exists)\n");
2166 printf("Difficulty rating: %s\n", tents_diffnames
[diff
]);
2168 verbose
= really_verbose
;
2169 ret
= tents_solve(p
->w
, p
->h
, s
->grid
, s
->numbers
->numbers
,
2170 s2
->grid
, sc
, diff
);
2172 printf("Puzzle is inconsistent\n");
2174 fputs(game_text_format(s2
), stdout
);