summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/src/tents.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/src/tents.c')
-rw-r--r--apps/plugins/puzzles/src/tents.c2740
1 files changed, 2740 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/tents.c b/apps/plugins/puzzles/src/tents.c
new file mode 100644
index 0000000000..4ffeb7be64
--- /dev/null
+++ b/apps/plugins/puzzles/src/tents.c
@@ -0,0 +1,2740 @@
1/*
2 * tents.c: Puzzle involving placing tents next to trees subject to
3 * some confusing conditions.
4 *
5 * TODO:
6 *
7 * - it might be nice to make setter-provided tent/nontent clues
8 * inviolable?
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
14 * not to bother.
15 *
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?
28 */
29
30#include <stdio.h>
31#include <stdlib.h>
32#include <string.h>
33#include <assert.h>
34#include <ctype.h>
35#include <math.h>
36
37#include "puzzles.h"
38#include "maxflow.h"
39
40/*
41 * Design discussion
42 * -----------------
43 *
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.
50 *
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.
57 *
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.
64 *
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?
72 *
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
78 *
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
85 * policy:
86 *
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
90 * _exactly_ one.
91 *
92 * Algorithmic implications
93 * ------------------------
94 *
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.
103 *
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.
117 *
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
124 * the right.
125 *
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.
137 *
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.
155 *
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. []
167 *
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.
177 *
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
193 * again.
194 *
195 * In other words, given any bipartite graph with a unique perfect
196 * matching, we can find that matching by the following extremely
197 * simple algorithm:
198 *
199 * - Find a left-side vertex which is only connected to one
200 * right-side vertex.
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.
204 *
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).
210 *
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
222 * trees and tents.
223 */
224
225/*
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
228 * true.
229 */
230#if defined STANDALONE_SOLVER
231#define SOLVER_DIAGNOSTICS
232int verbose = FALSE;
233#elif defined SOLVER_DIAGNOSTICS
234#define verbose TRUE
235#endif
236
237/*
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.
240 */
241#define DIFFLIST(A) \
242 A(EASY,Easy,e) \
243 A(TRICKY,Tricky,t)
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
248enum { DIFFLIST(ENUM) DIFFCOUNT };
249static char const *const tents_diffnames[] = { DIFFLIST(TITLE) };
250static char const tents_diffchars[] = DIFFLIST(ENCODE);
251#define DIFFCONFIG DIFFLIST(CONFIG)
252
253enum {
254 COL_BACKGROUND,
255 COL_GRID,
256 COL_GRASS,
257 COL_TREETRUNK,
258 COL_TREELEAF,
259 COL_TENT,
260 COL_ERROR,
261 COL_ERRTEXT,
262 COL_ERRTRUNK,
263 NCOLOURS
264};
265
266enum { BLANK, TREE, TENT, NONTENT, MAGIC };
267
268struct game_params {
269 int w, h;
270 int diff;
271};
272
273struct numbers {
274 int refcount;
275 int *numbers;
276};
277
278struct game_state {
279 game_params p;
280 char *grid;
281 struct numbers *numbers;
282 int completed, used_solve;
283};
284
285static game_params *default_params(void)
286{
287 game_params *ret = snew(game_params);
288
289 ret->w = ret->h = 8;
290 ret->diff = DIFF_EASY;
291
292 return ret;
293}
294
295static const struct game_params tents_presets[] = {
296 {8, 8, DIFF_EASY},
297 {8, 8, DIFF_TRICKY},
298 {10, 10, DIFF_EASY},
299 {10, 10, DIFF_TRICKY},
300 {15, 15, DIFF_EASY},
301 {15, 15, DIFF_TRICKY},
302};
303
304static int game_fetch_preset(int i, char **name, game_params **params)
305{
306 game_params *ret;
307 char str[80];
308
309 if (i < 0 || i >= lenof(tents_presets))
310 return FALSE;
311
312 ret = snew(game_params);
313 *ret = tents_presets[i];
314
315 sprintf(str, "%dx%d %s", ret->w, ret->h, tents_diffnames[ret->diff]);
316
317 *name = dupstr(str);
318 *params = ret;
319 return TRUE;
320}
321
322static void free_params(game_params *params)
323{
324 sfree(params);
325}
326
327static game_params *dup_params(const game_params *params)
328{
329 game_params *ret = snew(game_params);
330 *ret = *params; /* structure copy */
331 return ret;
332}
333
334static void decode_params(game_params *params, char const *string)
335{
336 params->w = params->h = atoi(string);
337 while (*string && isdigit((unsigned char)*string)) string++;
338 if (*string == 'x') {
339 string++;
340 params->h = atoi(string);
341 while (*string && isdigit((unsigned char)*string)) string++;
342 }
343 if (*string == 'd') {
344 int i;
345 string++;
346 for (i = 0; i < DIFFCOUNT; i++)
347 if (*string == tents_diffchars[i])
348 params->diff = i;
349 if (*string) string++;
350 }
351}
352
353static char *encode_params(const game_params *params, int full)
354{
355 char buf[120];
356
357 sprintf(buf, "%dx%d", params->w, params->h);
358 if (full)
359 sprintf(buf + strlen(buf), "d%c",
360 tents_diffchars[params->diff]);
361 return dupstr(buf);
362}
363
364static config_item *game_configure(const game_params *params)
365{
366 config_item *ret;
367 char buf[80];
368
369 ret = snewn(4, config_item);
370
371 ret[0].name = "Width";
372 ret[0].type = C_STRING;
373 sprintf(buf, "%d", params->w);
374 ret[0].sval = dupstr(buf);
375 ret[0].ival = 0;
376
377 ret[1].name = "Height";
378 ret[1].type = C_STRING;
379 sprintf(buf, "%d", params->h);
380 ret[1].sval = dupstr(buf);
381 ret[1].ival = 0;
382
383 ret[2].name = "Difficulty";
384 ret[2].type = C_CHOICES;
385 ret[2].sval = DIFFCONFIG;
386 ret[2].ival = params->diff;
387
388 ret[3].name = NULL;
389 ret[3].type = C_END;
390 ret[3].sval = NULL;
391 ret[3].ival = 0;
392
393 return ret;
394}
395
396static game_params *custom_params(const config_item *cfg)
397{
398 game_params *ret = snew(game_params);
399
400 ret->w = atoi(cfg[0].sval);
401 ret->h = atoi(cfg[1].sval);
402 ret->diff = cfg[2].ival;
403
404 return ret;
405}
406
407static char *validate_params(const game_params *params, int full)
408{
409 /*
410 * Generating anything under 4x4 runs into trouble of one kind
411 * or another.
412 */
413 if (params->w < 4 || params->h < 4)
414 return "Width and height must both be at least four";
415 return NULL;
416}
417
418/*
419 * Scratch space for solver.
420 */
421enum { 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) )
425struct solver_scratch {
426 char *links; /* mapping between trees and tents */
427 int *locs;
428 char *place, *mrows, *trows;
429};
430
431static struct solver_scratch *new_scratch(int w, int h)
432{
433 struct solver_scratch *ret = snew(struct solver_scratch);
434
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);
440
441 return ret;
442}
443
444static void free_scratch(struct solver_scratch *sc)
445{
446 sfree(sc->trows);
447 sfree(sc->mrows);
448 sfree(sc->place);
449 sfree(sc->locs);
450 sfree(sc->links);
451 sfree(sc);
452}
453
454/*
455 * Solver. Returns 0 for impossibility, 1 for success, 2 for
456 * ambiguity or failure to converge.
457 */
458static int tents_solve(int w, int h, const char *grid, int *numbers,
459 char *soln, struct solver_scratch *sc, int diff)
460{
461 int x, y, d, i, j;
462 char *mrow, *trow, *trow1, *trow2;
463
464 /*
465 * Set up solver data.
466 */
467 memset(sc->links, N, w*h);
468
469 /*
470 * Set up solution array.
471 */
472 memcpy(soln, grid, w*h);
473
474 /*
475 * Main solver loop.
476 */
477 while (1) {
478 int done_something = FALSE;
479
480 /*
481 * Any tent which has only one unattached tree adjacent to
482 * it can be tied to that tree.
483 */
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]) {
487 int linkd = 0;
488
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]) {
494 if (linkd)
495 break; /* found more than one */
496 else
497 linkd = d;
498 }
499 }
500
501 if (d == MAXDIR && linkd == 0) {
502#ifdef SOLVER_DIAGNOSTICS
503 if (verbose)
504 printf("tent at %d,%d cannot link to anything\n",
505 x, y);
506#endif
507 return 0; /* no solution exists */
508 } else if (d == MAXDIR) {
509 int x2 = x + dx(linkd), y2 = y + dy(linkd);
510
511#ifdef SOLVER_DIAGNOSTICS
512 if (verbose)
513 printf("tent at %d,%d can only link to tree at"
514 " %d,%d\n", x, y, x2, y2);
515#endif
516
517 sc->links[y*w+x] = linkd;
518 sc->links[y2*w+x2] = F(linkd);
519 done_something = TRUE;
520 }
521 }
522
523 if (done_something)
524 continue;
525 if (diff < 0)
526 break; /* don't do anything else! */
527
528 /*
529 * Mark a blank square as NONTENT if it is not orthogonally
530 * adjacent to any unmatched tree.
531 */
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;
536
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 &&
541 !sc->links[y2*w+x2])
542 can_be_tent = TRUE;
543 }
544
545 if (!can_be_tent) {
546#ifdef SOLVER_DIAGNOSTICS
547 if (verbose)
548 printf("%d,%d cannot be a tent (no adjacent"
549 " unmatched tree)\n", x, y);
550#endif
551 soln[y*w+x] = NONTENT;
552 done_something = TRUE;
553 }
554 }
555
556 if (done_something)
557 continue;
558
559 /*
560 * Mark a blank square as NONTENT if it is (perhaps
561 * diagonally) adjacent to any other tent.
562 */
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;
567
568 for (dy = -1; dy <= +1; dy++)
569 for (dx = -1; dx <= +1; dx++)
570 if (dy || 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)
574 imposs = TRUE;
575 }
576
577 if (imposs) {
578#ifdef SOLVER_DIAGNOSTICS
579 if (verbose)
580 printf("%d,%d cannot be a tent (adjacent tent)\n",
581 x, y);
582#endif
583 soln[y*w+x] = NONTENT;
584 done_something = TRUE;
585 }
586 }
587
588 if (done_something)
589 continue;
590
591 /*
592 * Any tree which has exactly one {unattached tent, BLANK}
593 * adjacent to it must have its tent in that square.
594 */
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;
599
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))
603 continue;
604 if (soln[y2*w+x2] == BLANK ||
605 (soln[y2*w+x2] == TENT && !sc->links[y2*w+x2])) {
606 if (linkd)
607 linkd2 = d;
608 else
609 linkd = d;
610 nd++;
611 }
612 }
613
614 if (nd == 0) {
615#ifdef SOLVER_DIAGNOSTICS
616 if (verbose)
617 printf("tree at %d,%d cannot link to anything\n",
618 x, y);
619#endif
620 return 0; /* no solution exists */
621 } else if (nd == 1) {
622 int x2 = x + dx(linkd), y2 = y + dy(linkd);
623
624#ifdef SOLVER_DIAGNOSTICS
625 if (verbose)
626 printf("tree at %d,%d can only link to tent at"
627 " %d,%d\n", x, y, x2, y2);
628#endif
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) {
635 /*
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
642 * be a non-tent.
643 */
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
649 if (verbose)
650 printf("possible tent locations for tree at"
651 " %d,%d rule out tent at %d,%d\n",
652 x, y, x2, y2);
653#endif
654 soln[y2*w+x2] = NONTENT;
655 done_something = TRUE;
656 }
657 }
658 }
659
660 if (done_something)
661 continue;
662
663 /*
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.
671 */
672 for (i = 0; i < w+h; i++) {
673 int start, step, len, start1, start2, n, k;
674
675 if (i < w) {
676 /*
677 * This is the number for a column.
678 */
679 start = i;
680 step = w;
681 len = h;
682 if (i > 0)
683 start1 = start - 1;
684 else
685 start1 = -1;
686 if (i+1 < w)
687 start2 = start + 1;
688 else
689 start2 = -1;
690 } else {
691 /*
692 * This is the number for a row.
693 */
694 start = (i-w)*w;
695 step = 1;
696 len = w;
697 if (i > w)
698 start1 = start - w;
699 else
700 start1 = -1;
701 if (i+1 < w+h)
702 start2 = start + w;
703 else
704 start2 = -1;
705 }
706
707 if (diff < DIFF_TRICKY) {
708 /*
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
712 * next to it).
713 */
714 start1 = start2 = -1;
715 }
716
717 k = numbers[i];
718
719 /*
720 * Count and store the locations of the free squares,
721 * and also count the number of tents already placed.
722 */
723 n = 0;
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)
728 sc->locs[n++] = j;
729 }
730
731 if (n == 0)
732 continue; /* nothing left to do here */
733
734 /*
735 * Now we know we're placing k tents in n squares. Set
736 * up the first possibility.
737 */
738 for (j = 0; j < n; j++)
739 sc->place[j] = (j < k ? TENT : NONTENT);
740
741 /*
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.
747 */
748 mrow = sc->mrows;
749 trow = sc->trows;
750 trow1 = sc->trows + len;
751 trow2 = sc->trows + 2*len;
752 memset(mrow, MAGIC, 3*len);
753
754 /*
755 * And iterate over all possibilities.
756 */
757 while (1) {
758 int p, valid;
759
760 /*
761 * See if this possibility is valid. The only way
762 * it can fail to be valid is if it contains two
763 * adjacent tents. (Other forms of invalidity, such
764 * as containing a tent adjacent to one already
765 * placed, will have been dealt with already by
766 * other parts of the solver.)
767 */
768 valid = TRUE;
769 for (j = 0; j+1 < n; j++)
770 if (sc->place[j] == TENT &&
771 sc->place[j+1] == TENT &&
772 sc->locs[j+1] == sc->locs[j]+1) {
773 valid = FALSE;
774 break;
775 }
776
777 if (valid) {
778 /*
779 * Merge this valid combination into mrow.
780 */
781 memset(trow, MAGIC, len);
782 memset(trow+len, BLANK, 2*len);
783 for (j = 0; j < n; j++) {
784 trow[sc->locs[j]] = sc->place[j];
785 if (sc->place[j] == TENT) {
786 int jj;
787 for (jj = sc->locs[j]-1; jj <= sc->locs[j]+1; jj++)
788 if (jj >= 0 && jj < len)
789 trow1[jj] = trow2[jj] = NONTENT;
790 }
791 }
792
793 for (j = 0; j < 3*len; j++) {
794 if (trow[j] == MAGIC)
795 continue;
796 if (mrow[j] == MAGIC || mrow[j] == trow[j]) {
797 /*
798 * Either this is the first valid
799 * placement we've found at all, or
800 * this square's contents are
801 * consistent with every previous valid
802 * combination.
803 */
804 mrow[j] = trow[j];
805 } else {
806 /*
807 * This square's contents fail to match
808 * what they were in a different
809 * combination, so we cannot deduce
810 * anything about this square.
811 */
812 mrow[j] = BLANK;
813 }
814 }
815 }
816
817 /*
818 * Find the next combination of k choices from n.
819 * We do this by finding the rightmost tent which
820 * can be moved one place right, doing so, and
821 * shunting all tents to the right of that as far
822 * left as they can go.
823 */
824 p = 0;
825 for (j = n-1; j > 0; j--) {
826 if (sc->place[j] == TENT)
827 p++;
828 if (sc->place[j] == NONTENT && sc->place[j-1] == TENT) {
829 sc->place[j-1] = NONTENT;
830 sc->place[j] = TENT;
831 while (p--)
832 sc->place[++j] = TENT;
833 while (++j < n)
834 sc->place[j] = NONTENT;
835 break;
836 }
837 }
838 if (j <= 0)
839 break; /* we've finished */
840 }
841
842 /*
843 * It's just possible that _no_ placement was valid, in
844 * which case we have an internally inconsistent
845 * puzzle.
846 */
847 if (mrow[sc->locs[0]] == MAGIC)
848 return 0; /* inconsistent */
849
850 /*
851 * Now go through mrow and see if there's anything
852 * we've deduced which wasn't already mentioned in soln.
853 */
854 for (j = 0; j < len; j++) {
855 int whichrow;
856
857 for (whichrow = 0; whichrow < 3; whichrow++) {
858 char *mthis = mrow + whichrow * len;
859 int tstart = (whichrow == 0 ? start :
860 whichrow == 1 ? start1 : start2);
861 if (tstart >= 0 &&
862 mthis[j] != MAGIC && mthis[j] != BLANK &&
863 soln[tstart+j*step] == BLANK) {
864 int pos = tstart+j*step;
865
866#ifdef SOLVER_DIAGNOSTICS
867 if (verbose)
868 printf("%s %d forces %s at %d,%d\n",
869 step==1 ? "row" : "column",
870 step==1 ? start/w : start,
871 mthis[j] == TENT ? "tent" : "non-tent",
872 pos % w, pos / w);
873#endif
874 soln[pos] = mthis[j];
875 done_something = TRUE;
876 }
877 }
878 }
879 }
880
881 if (done_something)
882 continue;
883
884 if (!done_something)
885 break;
886 }
887
888 /*
889 * The solver has nothing further it can do. Return 1 if both
890 * soln and sc->links are completely filled in, or 2 otherwise.
891 */
892 for (y = 0; y < h; y++)
893 for (x = 0; x < w; x++) {
894 if (soln[y*w+x] == BLANK)
895 return 2;
896 if (soln[y*w+x] != NONTENT && sc->links[y*w+x] == 0)
897 return 2;
898 }
899
900 return 1;
901}
902
903static char *new_game_desc(const game_params *params_in, random_state *rs,
904 char **aux, int interactive)
905{
906 game_params params_copy = *params_in; /* structure copy */
907 game_params *params = &params_copy;
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);
920 char *ret, *p;
921 int i, j, nedges;
922
923 /*
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
929 * plausible as well.
930 *
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.
945 *
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.
956 *
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.
963 *
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
974 * trouble.
975 */
976
977 if (params->diff > DIFF_EASY && params->w <= 4 && params->h <= 4)
978 params->diff = DIFF_EASY; /* downgrade to prevent tight loop */
979
980 while (1) {
981 /*
982 * Arrange the grid squares into a random order.
983 */
984 for (i = 0; i < w*h; i++)
985 temp[i] = i;
986 shuffle(temp, w*h, sizeof(*temp), rs);
987
988 /*
989 * The first `ntrees' entries in temp which we can get
990 * without making two tents adjacent will be the tent
991 * locations.
992 */
993 memset(grid, BLANK, w*h);
994 j = ntrees;
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;
998
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)
1004 ok = FALSE;
1005
1006 if (ok) {
1007 grid[temp[i]] = TENT;
1008 j--;
1009 }
1010 }
1011 if (j > 0)
1012 continue; /* couldn't place all the tents */
1013
1014 /*
1015 * Now we build up the list of graph edges.
1016 */
1017 nedges = 0;
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;
1028 nedges++;
1029 }
1030 }
1031 }
1032 } else {
1033 /*
1034 * Special node w*h is the sink node; any non-tent node
1035 * has an edge going to it.
1036 */
1037 edges[nedges*2] = i;
1038 edges[nedges*2+1] = w*h;
1039 capacity[nedges] = 1;
1040 nedges++;
1041 }
1042 }
1043
1044 /*
1045 * Special node w*h+1 is the source node, with an edge going to
1046 * every tent.
1047 */
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;
1053 nedges++;
1054 }
1055 }
1056
1057 assert(nedges <= maxedges);
1058
1059 /*
1060 * Now we're ready to call the maxflow algorithm to place the
1061 * trees.
1062 */
1063 j = maxflow(w*h+2, w*h+1, w*h, nedges, edges, capacity, flow, NULL);
1064
1065 if (j < ntrees)
1066 continue; /* couldn't place all the trees */
1067
1068 /*
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.
1072 */
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;
1076 }
1077
1078 /*
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).
1084 */
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 */
1089 }
1090 if (j == h)
1091 break; /* found empty column */
1092 }
1093 if (i < w)
1094 continue; /* a column was empty */
1095
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 */
1100 }
1101 if (i == w)
1102 break; /* found empty row */
1103 }
1104 if (j < h)
1105 continue; /* a row was empty */
1106
1107 /*
1108 * Now set up the numbers round the edge.
1109 */
1110 for (i = 0; i < w; i++) {
1111 int n = 0;
1112 for (j = 0; j < h; j++)
1113 if (grid[j*w+i] == TENT)
1114 n++;
1115 numbers[i] = n;
1116 }
1117 for (i = 0; i < h; i++) {
1118 int n = 0;
1119 for (j = 0; j < w; j++)
1120 if (grid[i*w+j] == TENT)
1121 n++;
1122 numbers[w+i] = n;
1123 }
1124
1125 /*
1126 * And now actually solve the puzzle, to see whether it's
1127 * unique and has the required difficulty.
1128 */
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);
1133
1134 /*
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
1138 * easy).
1139 */
1140 if (i == 2 && j == 1)
1141 break;
1142 }
1143
1144 /*
1145 * That's it. Encode as a game ID.
1146 */
1147 ret = snewn((w+h)*40 + ntrees + (w*h)/26 + 1, char);
1148 p = ret;
1149 j = 0;
1150 for (i = 0; i <= w*h; i++) {
1151 int c = (i < w*h ? grid[i] == TREE : 1);
1152 if (c) {
1153 *p++ = (j == 0 ? '_' : j-1 + 'a');
1154 j = 0;
1155 } else {
1156 j++;
1157 while (j > 25) {
1158 *p++ = 'z';
1159 j -= 25;
1160 }
1161 }
1162 }
1163 for (i = 0; i < w+h; i++)
1164 p += sprintf(p, ",%d", numbers[i]);
1165 *p++ = '\0';
1166 ret = sresize(ret, p - ret, char);
1167
1168 /*
1169 * And encode the solution as an aux_info.
1170 */
1171 *aux = snewn(ntrees * 40, char);
1172 p = *aux;
1173 *p++ = 'S';
1174 for (i = 0; i < w*h; i++)
1175 if (grid[i] == TENT)
1176 p += sprintf(p, ";T%d,%d", i%w, i/w);
1177 *p++ = '\0';
1178 *aux = sresize(*aux, p - *aux, char);
1179
1180 free_scratch(sc);
1181 sfree(flow);
1182 sfree(capacity);
1183 sfree(edges);
1184 sfree(temp);
1185 sfree(soln);
1186 sfree(numbers);
1187 sfree(puzzle);
1188 sfree(grid);
1189
1190 return ret;
1191}
1192
1193static char *validate_desc(const game_params *params, const char *desc)
1194{
1195 int w = params->w, h = params->h;
1196 int area, i;
1197
1198 area = 0;
1199 while (*desc && *desc != ',') {
1200 if (*desc == '_')
1201 area++;
1202 else if (*desc >= 'a' && *desc < 'z')
1203 area += *desc - 'a' + 2;
1204 else if (*desc == 'z')
1205 area += 25;
1206 else if (*desc == '!' || *desc == '-')
1207 /* do nothing */;
1208 else
1209 return "Invalid character in grid specification";
1210
1211 desc++;
1212 }
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";
1217
1218 for (i = 0; i < w+h; i++) {
1219 if (!*desc)
1220 return "Not enough numbers given after grid specification";
1221 else if (*desc != ',')
1222 return "Invalid character in number list";
1223 desc++;
1224 while (*desc && isdigit((unsigned char)*desc)) desc++;
1225 }
1226
1227 if (*desc)
1228 return "Unexpected additional data at end of game description";
1229 return NULL;
1230}
1231
1232static game_state *new_game(midend *me, const game_params *params,
1233 const char *desc)
1234{
1235 int w = params->w, h = params->h;
1236 game_state *state = snew(game_state);
1237 int i;
1238
1239 state->p = *params; /* structure copy */
1240 state->grid = snewn(w*h, char);
1241 state->numbers = snew(struct numbers);
1242 state->numbers->refcount = 1;
1243 state->numbers->numbers = snewn(w+h, int);
1244 state->completed = state->used_solve = FALSE;
1245
1246 i = 0;
1247 memset(state->grid, BLANK, w*h);
1248
1249 while (*desc) {
1250 int run, type;
1251
1252 type = TREE;
1253
1254 if (*desc == '_')
1255 run = 0;
1256 else if (*desc >= 'a' && *desc < 'z')
1257 run = *desc - ('a'-1);
1258 else if (*desc == 'z') {
1259 run = 25;
1260 type = BLANK;
1261 } else {
1262 assert(*desc == '!' || *desc == '-');
1263 run = -1;
1264 type = (*desc == '!' ? TENT : NONTENT);
1265 }
1266
1267 desc++;
1268
1269 i += run;
1270 assert(i >= 0 && i <= w*h);
1271 if (i == w*h) {
1272 assert(type == TREE);
1273 break;
1274 } else {
1275 if (type != BLANK)
1276 state->grid[i++] = type;
1277 }
1278 }
1279
1280 for (i = 0; i < w+h; i++) {
1281 assert(*desc == ',');
1282 desc++;
1283 state->numbers->numbers[i] = atoi(desc);
1284 while (*desc && isdigit((unsigned char)*desc)) desc++;
1285 }
1286
1287 assert(!*desc);
1288
1289 return state;
1290}
1291
1292static game_state *dup_game(const game_state *state)
1293{
1294 int w = state->p.w, h = state->p.h;
1295 game_state *ret = snew(game_state);
1296
1297 ret->p = state->p; /* structure copy */
1298 ret->grid = snewn(w*h, char);
1299 memcpy(ret->grid, state->grid, w*h);
1300 ret->numbers = state->numbers;
1301 state->numbers->refcount++;
1302 ret->completed = state->completed;
1303 ret->used_solve = state->used_solve;
1304
1305 return ret;
1306}
1307
1308static void free_game(game_state *state)
1309{
1310 if (--state->numbers->refcount <= 0) {
1311 sfree(state->numbers->numbers);
1312 sfree(state->numbers);
1313 }
1314 sfree(state->grid);
1315 sfree(state);
1316}
1317
1318static char *solve_game(const game_state *state, const game_state *currstate,
1319 const char *aux, char **error)
1320{
1321 int w = state->p.w, h = state->p.h;
1322
1323 if (aux) {
1324 /*
1325 * If we already have the solution, save ourselves some
1326 * time.
1327 */
1328 return dupstr(aux);
1329 } else {
1330 struct solver_scratch *sc = new_scratch(w, h);
1331 char *soln;
1332 int ret;
1333 char *move, *p;
1334 int i;
1335
1336 soln = snewn(w*h, char);
1337 ret = tents_solve(w, h, state->grid, state->numbers->numbers,
1338 soln, sc, DIFFCOUNT-1);
1339 free_scratch(sc);
1340 if (ret != 1) {
1341 sfree(soln);
1342 if (ret == 0)
1343 *error = "This puzzle is not self-consistent";
1344 else
1345 *error = "Unable to find a unique solution for this puzzle";
1346 return NULL;
1347 }
1348
1349 /*
1350 * Construct a move string which turns the current state
1351 * into the solved state.
1352 */
1353 move = snewn(w*h * 40, char);
1354 p = move;
1355 *p++ = 'S';
1356 for (i = 0; i < w*h; i++)
1357 if (soln[i] == TENT)
1358 p += sprintf(p, ";T%d,%d", i%w, i/w);
1359 *p++ = '\0';
1360 move = sresize(move, p - move, char);
1361
1362 sfree(soln);
1363
1364 return move;
1365 }
1366}
1367
1368static int game_can_format_as_text_now(const game_params *params)
1369{
1370 return params->w <= 1998 && params->h <= 1998; /* 999 tents */
1371}
1372
1373static char *game_text_format(const game_state *state)
1374{
1375 int w = state->p.w, h = state->p.h, r, c;
1376 int cw = 4, ch = 2, gw = (w+1)*cw + 2, gh = (h+1)*ch + 1, len = gw * gh;
1377 char *board = snewn(len + 1, char);
1378
1379 sprintf(board, "%*s\n", len - 2, "");
1380 for (r = 0; r <= h; ++r) {
1381 for (c = 0; c <= w; ++c) {
1382 int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
1383 int i = r*w + c, n = 1000;
1384
1385 if (r == h && c == w) /* NOP */;
1386 else if (c == w) n = state->numbers->numbers[w + r];
1387 else if (r == h) n = state->numbers->numbers[c];
1388 else switch (state->grid[i]) {
1389 case BLANK: board[center] = '.'; break;
1390 case TREE: board[center] = 'T'; break;
1391 case TENT: memcpy(board + center - 1, "//\\", 3); break;
1392 case NONTENT: break;
1393 default: memcpy(board + center - 1, "wtf", 3);
1394 }
1395
1396 if (n < 100) {
1397 board[center] = '0' + n % 10;
1398 if (n >= 10) board[center - 1] = '0' + n / 10;
1399 } else if (n < 1000) {
1400 board[center + 1] = '0' + n % 10;
1401 board[center] = '0' + n / 10 % 10;
1402 board[center - 1] = '0' + n / 100;
1403 }
1404
1405 board[cell] = '+';
1406 memset(board + cell + 1, '-', cw - 1);
1407 for (i = 1; i < ch; ++i) board[cell + i*gw] = '|';
1408 }
1409
1410 for (c = 0; c < ch; ++c) {
1411 board[(r*ch+c)*gw + gw - 2] =
1412 c == 0 ? '+' : r < h ? '|' : ' ';
1413 board[(r*ch+c)*gw + gw - 1] = '\n';
1414 }
1415 }
1416
1417 memset(board + len - gw, '-', gw - 2 - cw);
1418 for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+';
1419
1420 return board;
1421}
1422
1423struct game_ui {
1424 int dsx, dsy; /* coords of drag start */
1425 int dex, dey; /* coords of drag end */
1426 int drag_button; /* -1 for none, or a button code */
1427 int drag_ok; /* dragged off the window, to cancel */
1428
1429 int cx, cy, cdisp; /* cursor position, and ?display. */
1430};
1431
1432static game_ui *new_ui(const game_state *state)
1433{
1434 game_ui *ui = snew(game_ui);
1435 ui->dsx = ui->dsy = -1;
1436 ui->dex = ui->dey = -1;
1437 ui->drag_button = -1;
1438 ui->drag_ok = FALSE;
1439 ui->cx = ui->cy = ui->cdisp = 0;
1440 return ui;
1441}
1442
1443static void free_ui(game_ui *ui)
1444{
1445 sfree(ui);
1446}
1447
1448static char *encode_ui(const game_ui *ui)
1449{
1450 return NULL;
1451}
1452
1453static void decode_ui(game_ui *ui, const char *encoding)
1454{
1455}
1456
1457static void game_changed_state(game_ui *ui, const game_state *oldstate,
1458 const game_state *newstate)
1459{
1460}
1461
1462struct game_drawstate {
1463 int tilesize;
1464 int started;
1465 game_params p;
1466 int *drawn, *numbersdrawn;
1467 int cx, cy; /* last-drawn cursor pos, or (-1,-1) if absent. */
1468};
1469
1470#define PREFERRED_TILESIZE 32
1471#define TILESIZE (ds->tilesize)
1472#define TLBORDER (TILESIZE/2)
1473#define BRBORDER (TILESIZE*3/2)
1474#define COORD(x) ( (x) * TILESIZE + TLBORDER )
1475#define FROMCOORD(x) ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 )
1476
1477#define FLASH_TIME 0.30F
1478
1479static int drag_xform(const game_ui *ui, int x, int y, int v)
1480{
1481 int xmin, ymin, xmax, ymax;
1482
1483 xmin = min(ui->dsx, ui->dex);
1484 xmax = max(ui->dsx, ui->dex);
1485 ymin = min(ui->dsy, ui->dey);
1486 ymax = max(ui->dsy, ui->dey);
1487
1488#ifndef STYLUS_BASED
1489 /*
1490 * Left-dragging has no effect, so we treat a left-drag as a
1491 * single click on dsx,dsy.
1492 */
1493 if (ui->drag_button == LEFT_BUTTON) {
1494 xmin = xmax = ui->dsx;
1495 ymin = ymax = ui->dsy;
1496 }
1497#endif
1498
1499 if (x < xmin || x > xmax || y < ymin || y > ymax)
1500 return v; /* no change outside drag area */
1501
1502 if (v == TREE)
1503 return v; /* trees are inviolate always */
1504
1505 if (xmin == xmax && ymin == ymax) {
1506 /*
1507 * Results of a simple click. Left button sets blanks to
1508 * tents; right button sets blanks to non-tents; either
1509 * button clears a non-blank square.
1510 * If stylus-based however, it loops instead.
1511 */
1512 if (ui->drag_button == LEFT_BUTTON)
1513#ifdef STYLUS_BASED
1514 v = (v == BLANK ? TENT : (v == TENT ? NONTENT : BLANK));
1515 else
1516 v = (v == BLANK ? NONTENT : (v == NONTENT ? TENT : BLANK));
1517#else
1518 v = (v == BLANK ? TENT : BLANK);
1519 else
1520 v = (v == BLANK ? NONTENT : BLANK);
1521#endif
1522 } else {
1523 /*
1524 * Results of a drag. Left-dragging has no effect.
1525 * Right-dragging sets all blank squares to non-tents and
1526 * has no effect on anything else.
1527 */
1528 if (ui->drag_button == RIGHT_BUTTON)
1529 v = (v == BLANK ? NONTENT : v);
1530 else
1531#ifdef STYLUS_BASED
1532 v = (v == BLANK ? NONTENT : v);
1533#else
1534 /* do nothing */;
1535#endif
1536 }
1537
1538 return v;
1539}
1540
1541static char *interpret_move(const game_state *state, game_ui *ui,
1542 const game_drawstate *ds,
1543 int x, int y, int button)
1544{
1545 int w = state->p.w, h = state->p.h;
1546 char tmpbuf[80];
1547 int shift = button & MOD_SHFT, control = button & MOD_CTRL;
1548
1549 button &= ~MOD_MASK;
1550
1551 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1552 x = FROMCOORD(x);
1553 y = FROMCOORD(y);
1554 if (x < 0 || y < 0 || x >= w || y >= h)
1555 return NULL;
1556
1557 ui->drag_button = button;
1558 ui->dsx = ui->dex = x;
1559 ui->dsy = ui->dey = y;
1560 ui->drag_ok = TRUE;
1561 ui->cdisp = 0;
1562 return ""; /* ui updated */
1563 }
1564
1565 if ((IS_MOUSE_DRAG(button) || IS_MOUSE_RELEASE(button)) &&
1566 ui->drag_button > 0) {
1567 int xmin, ymin, xmax, ymax;
1568 char *buf, *sep;
1569 int buflen, bufsize, tmplen;
1570
1571 x = FROMCOORD(x);
1572 y = FROMCOORD(y);
1573 if (x < 0 || y < 0 || x >= w || y >= h) {
1574 ui->drag_ok = FALSE;
1575 } else {
1576 /*
1577 * Drags are limited to one row or column. Hence, we
1578 * work out which coordinate is closer to the drag
1579 * start, and move it _to_ the drag start.
1580 */
1581 if (abs(x - ui->dsx) < abs(y - ui->dsy))
1582 x = ui->dsx;
1583 else
1584 y = ui->dsy;
1585
1586 ui->dex = x;
1587 ui->dey = y;
1588
1589 ui->drag_ok = TRUE;
1590 }
1591
1592 if (IS_MOUSE_DRAG(button))
1593 return ""; /* ui updated */
1594
1595 /*
1596 * The drag has been released. Enact it.
1597 */
1598 if (!ui->drag_ok) {
1599 ui->drag_button = -1;
1600 return ""; /* drag was just cancelled */
1601 }
1602
1603 xmin = min(ui->dsx, ui->dex);
1604 xmax = max(ui->dsx, ui->dex);
1605 ymin = min(ui->dsy, ui->dey);
1606 ymax = max(ui->dsy, ui->dey);
1607 assert(0 <= xmin && xmin <= xmax && xmax < w);
1608 assert(0 <= ymin && ymin <= ymax && ymax < h);
1609
1610 buflen = 0;
1611 bufsize = 256;
1612 buf = snewn(bufsize, char);
1613 sep = "";
1614 for (y = ymin; y <= ymax; y++)
1615 for (x = xmin; x <= xmax; x++) {
1616 int v = drag_xform(ui, x, y, state->grid[y*w+x]);
1617 if (state->grid[y*w+x] != v) {
1618 tmplen = sprintf(tmpbuf, "%s%c%d,%d", sep,
1619 (int)(v == BLANK ? 'B' :
1620 v == TENT ? 'T' : 'N'),
1621 x, y);
1622 sep = ";";
1623
1624 if (buflen + tmplen >= bufsize) {
1625 bufsize = buflen + tmplen + 256;
1626 buf = sresize(buf, bufsize, char);
1627 }
1628
1629 strcpy(buf+buflen, tmpbuf);
1630 buflen += tmplen;
1631 }
1632 }
1633
1634 ui->drag_button = -1; /* drag is terminated */
1635
1636 if (buflen == 0) {
1637 sfree(buf);
1638 return ""; /* ui updated (drag was terminated) */
1639 } else {
1640 buf[buflen] = '\0';
1641 return buf;
1642 }
1643 }
1644
1645 if (IS_CURSOR_MOVE(button)) {
1646 ui->cdisp = 1;
1647 if (shift || control) {
1648 int len = 0, i, indices[2];
1649 indices[0] = ui->cx + w * ui->cy;
1650 move_cursor(button, &ui->cx, &ui->cy, w, h, 0);
1651 indices[1] = ui->cx + w * ui->cy;
1652
1653 /* NONTENTify all unique traversed eligible squares */
1654 for (i = 0; i <= (indices[0] != indices[1]); ++i)
1655 if (state->grid[indices[i]] == BLANK ||
1656 (control && state->grid[indices[i]] == TENT)) {
1657 len += sprintf(tmpbuf + len, "%sN%d,%d", len ? ";" : "",
1658 indices[i] % w, indices[i] / w);
1659 assert(len < lenof(tmpbuf));
1660 }
1661
1662 tmpbuf[len] = '\0';
1663 if (len) return dupstr(tmpbuf);
1664 } else
1665 move_cursor(button, &ui->cx, &ui->cy, w, h, 0);
1666 return "";
1667 }
1668 if (ui->cdisp) {
1669 char rep = 0;
1670 int v = state->grid[ui->cy*w+ui->cx];
1671
1672 if (v != TREE) {
1673#ifdef SINGLE_CURSOR_SELECT
1674 if (button == CURSOR_SELECT)
1675 /* SELECT cycles T, N, B */
1676 rep = v == BLANK ? 'T' : v == TENT ? 'N' : 'B';
1677#else
1678 if (button == CURSOR_SELECT)
1679 rep = v == BLANK ? 'T' : 'B';
1680 else if (button == CURSOR_SELECT2)
1681 rep = v == BLANK ? 'N' : 'B';
1682 else if (button == 'T' || button == 'N' || button == 'B')
1683 rep = (char)button;
1684#endif
1685 }
1686
1687 if (rep) {
1688 sprintf(tmpbuf, "%c%d,%d", (int)rep, ui->cx, ui->cy);
1689 return dupstr(tmpbuf);
1690 }
1691 } else if (IS_CURSOR_SELECT(button)) {
1692 ui->cdisp = 1;
1693 return "";
1694 }
1695
1696 return NULL;
1697}
1698
1699static game_state *execute_move(const game_state *state, const char *move)
1700{
1701 int w = state->p.w, h = state->p.h;
1702 char c;
1703 int x, y, m, n, i, j;
1704 game_state *ret = dup_game(state);
1705
1706 while (*move) {
1707 c = *move;
1708 if (c == 'S') {
1709 int i;
1710 ret->used_solve = TRUE;
1711 /*
1712 * Set all non-tree squares to NONTENT. The rest of the
1713 * solve move will fill the tents in over the top.
1714 */
1715 for (i = 0; i < w*h; i++)
1716 if (ret->grid[i] != TREE)
1717 ret->grid[i] = NONTENT;
1718 move++;
1719 } else if (c == 'B' || c == 'T' || c == 'N') {
1720 move++;
1721 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1722 x < 0 || y < 0 || x >= w || y >= h) {
1723 free_game(ret);
1724 return NULL;
1725 }
1726 if (ret->grid[y*w+x] == TREE) {
1727 free_game(ret);
1728 return NULL;
1729 }
1730 ret->grid[y*w+x] = (c == 'B' ? BLANK : c == 'T' ? TENT : NONTENT);
1731 move += n;
1732 } else {
1733 free_game(ret);
1734 return NULL;
1735 }
1736 if (*move == ';')
1737 move++;
1738 else if (*move) {
1739 free_game(ret);
1740 return NULL;
1741 }
1742 }
1743
1744 /*
1745 * Check for completion.
1746 */
1747 for (i = n = m = 0; i < w*h; i++) {
1748 if (ret->grid[i] == TENT)
1749 n++;
1750 else if (ret->grid[i] == TREE)
1751 m++;
1752 }
1753 if (n == m) {
1754 int nedges, maxedges, *edges, *capacity, *flow;
1755
1756 /*
1757 * We have the right number of tents, which is a
1758 * precondition for the game being complete. Now check that
1759 * the numbers add up.
1760 */
1761 for (i = 0; i < w; i++) {
1762 n = 0;
1763 for (j = 0; j < h; j++)
1764 if (ret->grid[j*w+i] == TENT)
1765 n++;
1766 if (ret->numbers->numbers[i] != n)
1767 goto completion_check_done;
1768 }
1769 for (i = 0; i < h; i++) {
1770 n = 0;
1771 for (j = 0; j < w; j++)
1772 if (ret->grid[i*w+j] == TENT)
1773 n++;
1774 if (ret->numbers->numbers[w+i] != n)
1775 goto completion_check_done;
1776 }
1777 /*
1778 * Also, check that no two tents are adjacent.
1779 */
1780 for (y = 0; y < h; y++)
1781 for (x = 0; x < w; x++) {
1782 if (x+1 < w &&
1783 ret->grid[y*w+x] == TENT && ret->grid[y*w+x+1] == TENT)
1784 goto completion_check_done;
1785 if (y+1 < h &&
1786 ret->grid[y*w+x] == TENT && ret->grid[(y+1)*w+x] == TENT)
1787 goto completion_check_done;
1788 if (x+1 < w && y+1 < h) {
1789 if (ret->grid[y*w+x] == TENT &&
1790 ret->grid[(y+1)*w+(x+1)] == TENT)
1791 goto completion_check_done;
1792 if (ret->grid[(y+1)*w+x] == TENT &&
1793 ret->grid[y*w+(x+1)] == TENT)
1794 goto completion_check_done;
1795 }
1796 }
1797
1798 /*
1799 * OK; we have the right number of tents, they match the
1800 * numeric clues, and they satisfy the non-adjacency
1801 * criterion. Finally, we need to verify that they can be
1802 * placed in a one-to-one matching with the trees such that
1803 * every tent is orthogonally adjacent to its tree.
1804 *
1805 * This bit is where the hard work comes in: we have to do
1806 * it by finding such a matching using maxflow.
1807 *
1808 * So we construct a network with one special source node,
1809 * one special sink node, one node per tent, and one node
1810 * per tree.
1811 */
1812 maxedges = 6 * m;
1813 edges = snewn(2 * maxedges, int);
1814 capacity = snewn(maxedges, int);
1815 flow = snewn(maxedges, int);
1816 nedges = 0;
1817 /*
1818 * Node numbering:
1819 *
1820 * 0..w*h trees/tents
1821 * w*h source
1822 * w*h+1 sink
1823 */
1824 for (y = 0; y < h; y++)
1825 for (x = 0; x < w; x++)
1826 if (ret->grid[y*w+x] == TREE) {
1827 int d;
1828
1829 /*
1830 * Here we use the direction enum declared for
1831 * the solver. We make use of the fact that the
1832 * directions are declared in the order
1833 * U,L,R,D, meaning that we go through the four
1834 * neighbours of any square in numerically
1835 * increasing order.
1836 */
1837 for (d = 1; d < MAXDIR; d++) {
1838 int x2 = x + dx(d), y2 = y + dy(d);
1839 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
1840 ret->grid[y2*w+x2] == TENT) {
1841 assert(nedges < maxedges);
1842 edges[nedges*2] = y*w+x;
1843 edges[nedges*2+1] = y2*w+x2;
1844 capacity[nedges] = 1;
1845 nedges++;
1846 }
1847 }
1848 } else if (ret->grid[y*w+x] == TENT) {
1849 assert(nedges < maxedges);
1850 edges[nedges*2] = y*w+x;
1851 edges[nedges*2+1] = w*h+1; /* edge going to sink */
1852 capacity[nedges] = 1;
1853 nedges++;
1854 }
1855 for (y = 0; y < h; y++)
1856 for (x = 0; x < w; x++)
1857 if (ret->grid[y*w+x] == TREE) {
1858 assert(nedges < maxedges);
1859 edges[nedges*2] = w*h; /* edge coming from source */
1860 edges[nedges*2+1] = y*w+x;
1861 capacity[nedges] = 1;
1862 nedges++;
1863 }
1864 n = maxflow(w*h+2, w*h, w*h+1, nedges, edges, capacity, flow, NULL);
1865
1866 sfree(flow);
1867 sfree(capacity);
1868 sfree(edges);
1869
1870 if (n != m)
1871 goto completion_check_done;
1872
1873 /*
1874 * We haven't managed to fault the grid on any count. Score!
1875 */
1876 ret->completed = TRUE;
1877 }
1878 completion_check_done:
1879
1880 return ret;
1881}
1882
1883/* ----------------------------------------------------------------------
1884 * Drawing routines.
1885 */
1886
1887static void game_compute_size(const game_params *params, int tilesize,
1888 int *x, int *y)
1889{
1890 /* fool the macros */
1891 struct dummy { int tilesize; } dummy, *ds = &dummy;
1892 dummy.tilesize = tilesize;
1893
1894 *x = TLBORDER + BRBORDER + TILESIZE * params->w;
1895 *y = TLBORDER + BRBORDER + TILESIZE * params->h;
1896}
1897
1898static void game_set_size(drawing *dr, game_drawstate *ds,
1899 const game_params *params, int tilesize)
1900{
1901 ds->tilesize = tilesize;
1902}
1903
1904static float *game_colours(frontend *fe, int *ncolours)
1905{
1906 float *ret = snewn(3 * NCOLOURS, float);
1907
1908 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1909
1910 ret[COL_GRID * 3 + 0] = 0.0F;
1911 ret[COL_GRID * 3 + 1] = 0.0F;
1912 ret[COL_GRID * 3 + 2] = 0.0F;
1913
1914 ret[COL_GRASS * 3 + 0] = 0.7F;
1915 ret[COL_GRASS * 3 + 1] = 1.0F;
1916 ret[COL_GRASS * 3 + 2] = 0.5F;
1917
1918 ret[COL_TREETRUNK * 3 + 0] = 0.6F;
1919 ret[COL_TREETRUNK * 3 + 1] = 0.4F;
1920 ret[COL_TREETRUNK * 3 + 2] = 0.0F;
1921
1922 ret[COL_TREELEAF * 3 + 0] = 0.0F;
1923 ret[COL_TREELEAF * 3 + 1] = 0.7F;
1924 ret[COL_TREELEAF * 3 + 2] = 0.0F;
1925
1926 ret[COL_TENT * 3 + 0] = 0.8F;
1927 ret[COL_TENT * 3 + 1] = 0.7F;
1928 ret[COL_TENT * 3 + 2] = 0.0F;
1929
1930 ret[COL_ERROR * 3 + 0] = 1.0F;
1931 ret[COL_ERROR * 3 + 1] = 0.0F;
1932 ret[COL_ERROR * 3 + 2] = 0.0F;
1933
1934 ret[COL_ERRTEXT * 3 + 0] = 1.0F;
1935 ret[COL_ERRTEXT * 3 + 1] = 1.0F;
1936 ret[COL_ERRTEXT * 3 + 2] = 1.0F;
1937
1938 ret[COL_ERRTRUNK * 3 + 0] = 0.6F;
1939 ret[COL_ERRTRUNK * 3 + 1] = 0.0F;
1940 ret[COL_ERRTRUNK * 3 + 2] = 0.0F;
1941
1942 *ncolours = NCOLOURS;
1943 return ret;
1944}
1945
1946static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1947{
1948 int w = state->p.w, h = state->p.h;
1949 struct game_drawstate *ds = snew(struct game_drawstate);
1950 int i;
1951
1952 ds->tilesize = 0;
1953 ds->started = FALSE;
1954 ds->p = state->p; /* structure copy */
1955 ds->drawn = snewn(w*h, int);
1956 for (i = 0; i < w*h; i++)
1957 ds->drawn[i] = MAGIC;
1958 ds->numbersdrawn = snewn(w+h, int);
1959 for (i = 0; i < w+h; i++)
1960 ds->numbersdrawn[i] = 2;
1961 ds->cx = ds->cy = -1;
1962
1963 return ds;
1964}
1965
1966static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1967{
1968 sfree(ds->drawn);
1969 sfree(ds->numbersdrawn);
1970 sfree(ds);
1971}
1972
1973enum {
1974 ERR_ADJ_TOPLEFT = 4,
1975 ERR_ADJ_TOP,
1976 ERR_ADJ_TOPRIGHT,
1977 ERR_ADJ_LEFT,
1978 ERR_ADJ_RIGHT,
1979 ERR_ADJ_BOTLEFT,
1980 ERR_ADJ_BOT,
1981 ERR_ADJ_BOTRIGHT,
1982 ERR_OVERCOMMITTED
1983};
1984
1985static int *find_errors(const game_state *state, char *grid)
1986{
1987 int w = state->p.w, h = state->p.h;
1988 int *ret = snewn(w*h + w + h, int);
1989 int *tmp = snewn(w*h*2, int), *dsf = tmp + w*h;
1990 int x, y;
1991
1992 /*
1993 * This function goes through a grid and works out where to
1994 * highlight play errors in red. The aim is that it should
1995 * produce at least one error highlight for any complete grid
1996 * (or complete piece of grid) violating a puzzle constraint, so
1997 * that a grid containing no BLANK squares is either a win or is
1998 * marked up in some way that indicates why not.
1999 *
2000 * So it's easy enough to highlight errors in the numeric clues
2001 * - just light up any row or column number which is not
2002 * fulfilled - and it's just as easy to highlight adjacent
2003 * tents. The difficult bit is highlighting failures in the
2004 * tent/tree matching criterion.
2005 *
2006 * A natural approach would seem to be to apply the maxflow
2007 * algorithm to find the tent/tree matching; if this fails, it
2008 * must necessarily terminate with a min-cut which can be
2009 * reinterpreted as some set of trees which have too few tents
2010 * between them (or vice versa). However, it's bad for
2011 * localising errors, because it's not easy to make the
2012 * algorithm narrow down to the _smallest_ such set of trees: if
2013 * trees A and B have only one tent between them, for instance,
2014 * it might perfectly well highlight not only A and B but also
2015 * trees C and D which are correctly matched on the far side of
2016 * the grid, on the grounds that those four trees between them
2017 * have only three tents.
2018 *
2019 * Also, that approach fares badly when you introduce the
2020 * additional requirement that incomplete grids should have
2021 * errors highlighted only when they can be proved to be errors
2022 * - so that trees should not be marked as having too few tents
2023 * if there are enough BLANK squares remaining around them that
2024 * could be turned into the missing tents (to do so would be
2025 * patronising, since the overwhelming likelihood is not that
2026 * the player has forgotten to put a tree there but that they
2027 * have merely not put one there _yet_). However, tents with too
2028 * few trees can be marked immediately, since those are
2029 * definitely player error.
2030 *
2031 * So I adopt an alternative approach, which is to consider the
2032 * bipartite adjacency graph between trees and tents
2033 * ('bipartite' in the sense that for these purposes I
2034 * deliberately ignore two adjacent trees or two adjacent
2035 * tents), divide that graph up into its connected components
2036 * using a dsf, and look for components which contain different
2037 * numbers of trees and tents. This allows me to highlight
2038 * groups of tents with too few trees between them immediately,
2039 * and then in order to find groups of trees with too few tents
2040 * I redo the same process but counting BLANKs as potential
2041 * tents (so that the only trees highlighted are those
2042 * surrounded by enough NONTENTs to make it impossible to give
2043 * them enough tents).
2044 *
2045 * However, this technique is incomplete: it is not a sufficient
2046 * condition for the existence of a perfect matching that every
2047 * connected component of the graph has the same number of tents
2048 * and trees. An example of a graph which satisfies the latter
2049 * condition but still has no perfect matching is
2050 *
2051 * A B C
2052 * | / ,/|
2053 * | / ,'/ |
2054 * | / ,' / |
2055 * |/,' / |
2056 * 1 2 3
2057 *
2058 * which can be realised in Tents as
2059 *
2060 * B
2061 * A 1 C 2
2062 * 3
2063 *
2064 * The matching-error highlighter described above will not mark
2065 * this construction as erroneous. However, something else will:
2066 * the three tents in the above diagram (let us suppose A,B,C
2067 * are the tents, though it doesn't matter which) contain two
2068 * diagonally adjacent pairs. So there will be _an_ error
2069 * highlighted for the above layout, even though not all types
2070 * of error will be highlighted.
2071 *
2072 * And in fact we can prove that this will always be the case:
2073 * that the shortcomings of the matching-error highlighter will
2074 * always be made up for by the easy tent adjacency highlighter.
2075 *
2076 * Lemma: Let G be a bipartite graph between n trees and n
2077 * tents, which is connected, and in which no tree has degree
2078 * more than two (but a tent may). Then G has a perfect matching.
2079 *
2080 * (Note: in the statement and proof of the Lemma I will
2081 * consistently use 'tree' to indicate a type of graph vertex as
2082 * opposed to a tent, and not to indicate a tree in the graph-
2083 * theoretic sense.)
2084 *
2085 * Proof:
2086 *
2087 * If we can find a tent of degree 1 joined to a tree of degree
2088 * 2, then any perfect matching must pair that tent with that
2089 * tree. Hence, we can remove both, leaving a smaller graph G'
2090 * which still satisfies all the conditions of the Lemma, and
2091 * which has a perfect matching iff G does.
2092 *
2093 * So, wlog, we may assume G contains no tent of degree 1 joined
2094 * to a tree of degree 2; if it does, we can reduce it as above.
2095 *
2096 * If G has no tent of degree 1 at all, then every tent has
2097 * degree at least two, so there are at least 2n edges in the
2098 * graph. But every tree has degree at most two, so there are at
2099 * most 2n edges. Hence there must be exactly 2n edges, so every
2100 * tree and every tent must have degree exactly two, which means
2101 * that the whole graph consists of a single loop (by
2102 * connectedness), and therefore certainly has a perfect
2103 * matching.
2104 *
2105 * Alternatively, if G does have a tent of degree 1 but it is
2106 * not connected to a tree of degree 2, then the tree it is
2107 * connected to must have degree 1 - and, by connectedness, that
2108 * must mean that that tent and that tree between them form the
2109 * entire graph. This trivial graph has a trivial perfect
2110 * matching. []
2111 *
2112 * That proves the lemma. Hence, in any case where the matching-
2113 * error highlighter fails to highlight an erroneous component
2114 * (because it has the same number of tents as trees, but they
2115 * cannot be matched up), the above lemma tells us that there
2116 * must be a tree with degree more than 2, i.e. a tree
2117 * orthogonally adjacent to at least three tents. But in that
2118 * case, there must be some pair of those three tents which are
2119 * diagonally adjacent to each other, so the tent-adjacency
2120 * highlighter will necessarily show an error. So any filled
2121 * layout in Tents which is not a correct solution to the puzzle
2122 * must have _some_ error highlighted by the subroutine below.
2123 *
2124 * (Of course it would be nicer if we could highlight all
2125 * errors: in the above example layout, we would like to
2126 * highlight tents A,B as having too few trees between them, and
2127 * trees 2,3 as having too few tents, in addition to marking the
2128 * adjacency problems. But I can't immediately think of any way
2129 * to find the smallest sets of such tents and trees without an
2130 * O(2^N) loop over all subsets of a given component.)
2131 */
2132
2133 /*
2134 * ret[0] through to ret[w*h-1] give error markers for the grid
2135 * squares. After that, ret[w*h] to ret[w*h+w-1] give error
2136 * markers for the column numbers, and ret[w*h+w] to
2137 * ret[w*h+w+h-1] for the row numbers.
2138 */
2139
2140 /*
2141 * Spot tent-adjacency violations.
2142 */
2143 for (x = 0; x < w*h; x++)
2144 ret[x] = 0;
2145 for (y = 0; y < h; y++) {
2146 for (x = 0; x < w; x++) {
2147 if (y+1 < h && x+1 < w &&
2148 ((grid[y*w+x] == TENT &&
2149 grid[(y+1)*w+(x+1)] == TENT) ||
2150 (grid[(y+1)*w+x] == TENT &&
2151 grid[y*w+(x+1)] == TENT))) {
2152 ret[y*w+x] |= 1 << ERR_ADJ_BOTRIGHT;
2153 ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOPRIGHT;
2154 ret[y*w+(x+1)] |= 1 << ERR_ADJ_BOTLEFT;
2155 ret[(y+1)*w+(x+1)] |= 1 << ERR_ADJ_TOPLEFT;
2156 }
2157 if (y+1 < h &&
2158 grid[y*w+x] == TENT &&
2159 grid[(y+1)*w+x] == TENT) {
2160 ret[y*w+x] |= 1 << ERR_ADJ_BOT;
2161 ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOP;
2162 }
2163 if (x+1 < w &&
2164 grid[y*w+x] == TENT &&
2165 grid[y*w+(x+1)] == TENT) {
2166 ret[y*w+x] |= 1 << ERR_ADJ_RIGHT;
2167 ret[y*w+(x+1)] |= 1 << ERR_ADJ_LEFT;
2168 }
2169 }
2170 }
2171
2172 /*
2173 * Spot numeric clue violations.
2174 */
2175 for (x = 0; x < w; x++) {
2176 int tents = 0, maybetents = 0;
2177 for (y = 0; y < h; y++) {
2178 if (grid[y*w+x] == TENT)
2179 tents++;
2180 else if (grid[y*w+x] == BLANK)
2181 maybetents++;
2182 }
2183 ret[w*h+x] = (tents > state->numbers->numbers[x] ||
2184 tents + maybetents < state->numbers->numbers[x]);
2185 }
2186 for (y = 0; y < h; y++) {
2187 int tents = 0, maybetents = 0;
2188 for (x = 0; x < w; x++) {
2189 if (grid[y*w+x] == TENT)
2190 tents++;
2191 else if (grid[y*w+x] == BLANK)
2192 maybetents++;
2193 }
2194 ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] ||
2195 tents + maybetents < state->numbers->numbers[w+y]);
2196 }
2197
2198 /*
2199 * Identify groups of tents with too few trees between them,
2200 * which we do by constructing the connected components of the
2201 * bipartite adjacency graph between tents and trees
2202 * ('bipartite' in the sense that we deliberately ignore
2203 * adjacency between tents or between trees), and highlighting
2204 * all the tents in any component which has a smaller tree
2205 * count.
2206 */
2207 dsf_init(dsf, w*h);
2208 /* Construct the equivalence classes. */
2209 for (y = 0; y < h; y++) {
2210 for (x = 0; x < w-1; x++) {
2211 if ((grid[y*w+x] == TREE && grid[y*w+x+1] == TENT) ||
2212 (grid[y*w+x] == TENT && grid[y*w+x+1] == TREE))
2213 dsf_merge(dsf, y*w+x, y*w+x+1);
2214 }
2215 }
2216 for (y = 0; y < h-1; y++) {
2217 for (x = 0; x < w; x++) {
2218 if ((grid[y*w+x] == TREE && grid[(y+1)*w+x] == TENT) ||
2219 (grid[y*w+x] == TENT && grid[(y+1)*w+x] == TREE))
2220 dsf_merge(dsf, y*w+x, (y+1)*w+x);
2221 }
2222 }
2223 /* Count up the tent/tree difference in each one. */
2224 for (x = 0; x < w*h; x++)
2225 tmp[x] = 0;
2226 for (x = 0; x < w*h; x++) {
2227 y = dsf_canonify(dsf, x);
2228 if (grid[x] == TREE)
2229 tmp[y]++;
2230 else if (grid[x] == TENT)
2231 tmp[y]--;
2232 }
2233 /* And highlight any tent belonging to an equivalence class with
2234 * a score less than zero. */
2235 for (x = 0; x < w*h; x++) {
2236 y = dsf_canonify(dsf, x);
2237 if (grid[x] == TENT && tmp[y] < 0)
2238 ret[x] |= 1 << ERR_OVERCOMMITTED;
2239 }
2240
2241 /*
2242 * Identify groups of trees with too few tents between them.
2243 * This is done similarly, except that we now count BLANK as
2244 * equivalent to TENT, i.e. we only highlight such trees when
2245 * the user hasn't even left _room_ to provide tents for them
2246 * all. (Otherwise, we'd highlight all trees red right at the
2247 * start of the game, before the user had done anything wrong!)
2248 */
2249#define TENT(x) ((x)==TENT || (x)==BLANK)
2250 dsf_init(dsf, w*h);
2251 /* Construct the equivalence classes. */
2252 for (y = 0; y < h; y++) {
2253 for (x = 0; x < w-1; x++) {
2254 if ((grid[y*w+x] == TREE && TENT(grid[y*w+x+1])) ||
2255 (TENT(grid[y*w+x]) && grid[y*w+x+1] == TREE))
2256 dsf_merge(dsf, y*w+x, y*w+x+1);
2257 }
2258 }
2259 for (y = 0; y < h-1; y++) {
2260 for (x = 0; x < w; x++) {
2261 if ((grid[y*w+x] == TREE && TENT(grid[(y+1)*w+x])) ||
2262 (TENT(grid[y*w+x]) && grid[(y+1)*w+x] == TREE))
2263 dsf_merge(dsf, y*w+x, (y+1)*w+x);
2264 }
2265 }
2266 /* Count up the tent/tree difference in each one. */
2267 for (x = 0; x < w*h; x++)
2268 tmp[x] = 0;
2269 for (x = 0; x < w*h; x++) {
2270 y = dsf_canonify(dsf, x);
2271 if (grid[x] == TREE)
2272 tmp[y]++;
2273 else if (TENT(grid[x]))
2274 tmp[y]--;
2275 }
2276 /* And highlight any tree belonging to an equivalence class with
2277 * a score more than zero. */
2278 for (x = 0; x < w*h; x++) {
2279 y = dsf_canonify(dsf, x);
2280 if (grid[x] == TREE && tmp[y] > 0)
2281 ret[x] |= 1 << ERR_OVERCOMMITTED;
2282 }
2283#undef TENT
2284
2285 sfree(tmp);
2286 return ret;
2287}
2288
2289static void draw_err_adj(drawing *dr, game_drawstate *ds, int x, int y)
2290{
2291 int coords[8];
2292 int yext, xext;
2293
2294 /*
2295 * Draw a diamond.
2296 */
2297 coords[0] = x - TILESIZE*2/5;
2298 coords[1] = y;
2299 coords[2] = x;
2300 coords[3] = y - TILESIZE*2/5;
2301 coords[4] = x + TILESIZE*2/5;
2302 coords[5] = y;
2303 coords[6] = x;
2304 coords[7] = y + TILESIZE*2/5;
2305 draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
2306
2307 /*
2308 * Draw an exclamation mark in the diamond. This turns out to
2309 * look unpleasantly off-centre if done via draw_text, so I do
2310 * it by hand on the basis that exclamation marks aren't that
2311 * difficult to draw...
2312 */
2313 xext = TILESIZE/16;
2314 yext = TILESIZE*2/5 - (xext*2+2);
2315 draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
2316 COL_ERRTEXT);
2317 draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
2318}
2319
2320static void draw_tile(drawing *dr, game_drawstate *ds,
2321 int x, int y, int v, int cur, int printing)
2322{
2323 int err;
2324 int tx = COORD(x), ty = COORD(y);
2325 int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2;
2326
2327 err = v & ~15;
2328 v &= 15;
2329
2330 clip(dr, tx, ty, TILESIZE, TILESIZE);
2331
2332 if (!printing) {
2333 draw_rect(dr, tx, ty, TILESIZE, TILESIZE, COL_GRID);
2334 draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1,
2335 (v == BLANK ? COL_BACKGROUND : COL_GRASS));
2336 }
2337
2338 if (v == TREE) {
2339 int i;
2340
2341 (printing ? draw_rect_outline : draw_rect)
2342 (dr, cx-TILESIZE/15, ty+TILESIZE*3/10,
2343 2*(TILESIZE/15)+1, (TILESIZE*9/10 - TILESIZE*3/10),
2344 (err & (1<<ERR_OVERCOMMITTED) ? COL_ERRTRUNK : COL_TREETRUNK));
2345
2346 for (i = 0; i < (printing ? 2 : 1); i++) {
2347 int col = (i == 1 ? COL_BACKGROUND :
2348 (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR :
2349 COL_TREELEAF));
2350 int sub = i * (TILESIZE/32);
2351 draw_circle(dr, cx, ty+TILESIZE*4/10, TILESIZE/4 - sub,
2352 col, col);
2353 draw_circle(dr, cx+TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
2354 col, col);
2355 draw_circle(dr, cx-TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
2356 col, col);
2357 draw_circle(dr, cx+TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
2358 col, col);
2359 draw_circle(dr, cx-TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
2360 col, col);
2361 }
2362 } else if (v == TENT) {
2363 int coords[6];
2364 int col;
2365 coords[0] = cx - TILESIZE/3;
2366 coords[1] = cy + TILESIZE/3;
2367 coords[2] = cx + TILESIZE/3;
2368 coords[3] = cy + TILESIZE/3;
2369 coords[4] = cx;
2370 coords[5] = cy - TILESIZE/3;
2371 col = (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : COL_TENT);
2372 draw_polygon(dr, coords, 3, (printing ? -1 : col), col);
2373 }
2374
2375 if (err & (1 << ERR_ADJ_TOPLEFT))
2376 draw_err_adj(dr, ds, tx, ty);
2377 if (err & (1 << ERR_ADJ_TOP))
2378 draw_err_adj(dr, ds, tx+TILESIZE/2, ty);
2379 if (err & (1 << ERR_ADJ_TOPRIGHT))
2380 draw_err_adj(dr, ds, tx+TILESIZE, ty);
2381 if (err & (1 << ERR_ADJ_LEFT))
2382 draw_err_adj(dr, ds, tx, ty+TILESIZE/2);
2383 if (err & (1 << ERR_ADJ_RIGHT))
2384 draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE/2);
2385 if (err & (1 << ERR_ADJ_BOTLEFT))
2386 draw_err_adj(dr, ds, tx, ty+TILESIZE);
2387 if (err & (1 << ERR_ADJ_BOT))
2388 draw_err_adj(dr, ds, tx+TILESIZE/2, ty+TILESIZE);
2389 if (err & (1 << ERR_ADJ_BOTRIGHT))
2390 draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE);
2391
2392 if (cur) {
2393 int coff = TILESIZE/8;
2394 draw_rect_outline(dr, tx + coff, ty + coff,
2395 TILESIZE - coff*2 + 1, TILESIZE - coff*2 + 1,
2396 COL_GRID);
2397 }
2398
2399 unclip(dr);
2400 draw_update(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
2401}
2402
2403/*
2404 * Internal redraw function, used for printing as well as drawing.
2405 */
2406static void int_redraw(drawing *dr, game_drawstate *ds,
2407 const game_state *oldstate, const game_state *state,
2408 int dir, const game_ui *ui,
2409 float animtime, float flashtime, int printing)
2410{
2411 int w = state->p.w, h = state->p.h;
2412 int x, y, flashing;
2413 int cx = -1, cy = -1;
2414 int cmoved = 0;
2415 char *tmpgrid;
2416 int *errors;
2417
2418 if (ui) {
2419 if (ui->cdisp) { cx = ui->cx; cy = ui->cy; }
2420 if (cx != ds->cx || cy != ds->cy) cmoved = 1;
2421 }
2422
2423 if (printing || !ds->started) {
2424 if (!printing) {
2425 int ww, wh;
2426 game_compute_size(&state->p, TILESIZE, &ww, &wh);
2427 draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
2428 draw_update(dr, 0, 0, ww, wh);
2429 ds->started = TRUE;
2430 }
2431
2432 if (printing)
2433 print_line_width(dr, TILESIZE/64);
2434
2435 /*
2436 * Draw the grid.
2437 */
2438 for (y = 0; y <= h; y++)
2439 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), COL_GRID);
2440 for (x = 0; x <= w; x++)
2441 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), COL_GRID);
2442 }
2443
2444 if (flashtime > 0)
2445 flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
2446 else
2447 flashing = FALSE;
2448
2449 /*
2450 * Find errors. For this we use _part_ of the information from a
2451 * currently active drag: we transform dsx,dsy but not anything
2452 * else. (This seems to strike a good compromise between having
2453 * the error highlights respond instantly to single clicks, but
2454 * not giving constant feedback during a right-drag.)
2455 */
2456 if (ui && ui->drag_button >= 0) {
2457 tmpgrid = snewn(w*h, char);
2458 memcpy(tmpgrid, state->grid, w*h);
2459 tmpgrid[ui->dsy * w + ui->dsx] =
2460 drag_xform(ui, ui->dsx, ui->dsy, tmpgrid[ui->dsy * w + ui->dsx]);
2461 errors = find_errors(state, tmpgrid);
2462 sfree(tmpgrid);
2463 } else {
2464 errors = find_errors(state, state->grid);
2465 }
2466
2467 /*
2468 * Draw the grid.
2469 */
2470 for (y = 0; y < h; y++) {
2471 for (x = 0; x < w; x++) {
2472 int v = state->grid[y*w+x];
2473 int credraw = 0;
2474
2475 /*
2476 * We deliberately do not take drag_ok into account
2477 * here, because user feedback suggests that it's
2478 * marginally nicer not to have the drag effects
2479 * flickering on and off disconcertingly.
2480 */
2481 if (ui && ui->drag_button >= 0)
2482 v = drag_xform(ui, x, y, v);
2483
2484 if (flashing && (v == TREE || v == TENT))
2485 v = NONTENT;
2486
2487 if (cmoved) {
2488 if ((x == cx && y == cy) ||
2489 (x == ds->cx && y == ds->cy)) credraw = 1;
2490 }
2491
2492 v |= errors[y*w+x];
2493
2494 if (printing || ds->drawn[y*w+x] != v || credraw) {
2495 draw_tile(dr, ds, x, y, v, (x == cx && y == cy), printing);
2496 if (!printing)
2497 ds->drawn[y*w+x] = v;
2498 }
2499 }
2500 }
2501
2502 /*
2503 * Draw (or redraw, if their error-highlighted state has
2504 * changed) the numbers.
2505 */
2506 for (x = 0; x < w; x++) {
2507 if (printing || ds->numbersdrawn[x] != errors[w*h+x]) {
2508 char buf[80];
2509 draw_rect(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1,
2510 COL_BACKGROUND);
2511 sprintf(buf, "%d", state->numbers->numbers[x]);
2512 draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1),
2513 FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL,
2514 (errors[w*h+x] ? COL_ERROR : COL_GRID), buf);
2515 draw_update(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1);
2516 if (!printing)
2517 ds->numbersdrawn[x] = errors[w*h+x];
2518 }
2519 }
2520 for (y = 0; y < h; y++) {
2521 if (printing || ds->numbersdrawn[w+y] != errors[w*h+w+y]) {
2522 char buf[80];
2523 draw_rect(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE,
2524 COL_BACKGROUND);
2525 sprintf(buf, "%d", state->numbers->numbers[w+y]);
2526 draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2,
2527 FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE,
2528 (errors[w*h+w+y] ? COL_ERROR : COL_GRID), buf);
2529 draw_update(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE);
2530 if (!printing)
2531 ds->numbersdrawn[w+y] = errors[w*h+w+y];
2532 }
2533 }
2534
2535 if (cmoved) {
2536 ds->cx = cx;
2537 ds->cy = cy;
2538 }
2539
2540 sfree(errors);
2541}
2542
2543static void game_redraw(drawing *dr, game_drawstate *ds,
2544 const game_state *oldstate, const game_state *state,
2545 int dir, const game_ui *ui,
2546 float animtime, float flashtime)
2547{
2548 int_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, FALSE);
2549}
2550
2551static float game_anim_length(const game_state *oldstate,
2552 const game_state *newstate, int dir, game_ui *ui)
2553{
2554 return 0.0F;
2555}
2556
2557static float game_flash_length(const game_state *oldstate,
2558 const game_state *newstate, int dir, game_ui *ui)
2559{
2560 if (!oldstate->completed && newstate->completed &&
2561 !oldstate->used_solve && !newstate->used_solve)
2562 return FLASH_TIME;
2563
2564 return 0.0F;
2565}
2566
2567static int game_status(const game_state *state)
2568{
2569 return state->completed ? +1 : 0;
2570}
2571
2572static int game_timing_state(const game_state *state, game_ui *ui)
2573{
2574 return TRUE;
2575}
2576
2577static void game_print_size(const game_params *params, float *x, float *y)
2578{
2579 int pw, ph;
2580
2581 /*
2582 * I'll use 6mm squares by default.
2583 */
2584 game_compute_size(params, 600, &pw, &ph);
2585 *x = pw / 100.0F;
2586 *y = ph / 100.0F;
2587}
2588
2589static void game_print(drawing *dr, const game_state *state, int tilesize)
2590{
2591 int c;
2592
2593 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2594 game_drawstate ads, *ds = &ads;
2595 game_set_size(dr, ds, NULL, tilesize);
2596
2597 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
2598 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
2599 c = print_mono_colour(dr, 1); assert(c == COL_GRASS);
2600 c = print_mono_colour(dr, 0); assert(c == COL_TREETRUNK);
2601 c = print_mono_colour(dr, 0); assert(c == COL_TREELEAF);
2602 c = print_mono_colour(dr, 0); assert(c == COL_TENT);
2603
2604 int_redraw(dr, ds, NULL, state, +1, NULL, 0.0F, 0.0F, TRUE);
2605}
2606
2607#ifdef COMBINED
2608#define thegame tents
2609#endif
2610
2611const struct game thegame = {
2612 "Tents", "games.tents", "tents",
2613 default_params,
2614 game_fetch_preset, NULL,
2615 decode_params,
2616 encode_params,
2617 free_params,
2618 dup_params,
2619 TRUE, game_configure, custom_params,
2620 validate_params,
2621 new_game_desc,
2622 validate_desc,
2623 new_game,
2624 dup_game,
2625 free_game,
2626 TRUE, solve_game,
2627 TRUE, game_can_format_as_text_now, game_text_format,
2628 new_ui,
2629 free_ui,
2630 encode_ui,
2631 decode_ui,
2632 game_changed_state,
2633 interpret_move,
2634 execute_move,
2635 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2636 game_colours,
2637 game_new_drawstate,
2638 game_free_drawstate,
2639 game_redraw,
2640 game_anim_length,
2641 game_flash_length,
2642 game_status,
2643 TRUE, FALSE, game_print_size, game_print,
2644 FALSE, /* wants_statusbar */
2645 FALSE, game_timing_state,
2646 REQUIRE_RBUTTON, /* flags */
2647};
2648
2649#ifdef STANDALONE_SOLVER
2650
2651#include <stdarg.h>
2652
2653int main(int argc, char **argv)
2654{
2655 game_params *p;
2656 game_state *s, *s2;
2657 char *id = NULL, *desc, *err;
2658 int grade = FALSE;
2659 int ret, diff, really_verbose = FALSE;
2660 struct solver_scratch *sc;
2661
2662 while (--argc > 0) {
2663 char *p = *++argv;
2664 if (!strcmp(p, "-v")) {
2665 really_verbose = TRUE;
2666 } else if (!strcmp(p, "-g")) {
2667 grade = TRUE;
2668 } else if (*p == '-') {
2669 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2670 return 1;
2671 } else {
2672 id = p;
2673 }
2674 }
2675
2676 if (!id) {
2677 fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2678 return 1;
2679 }
2680
2681 desc = strchr(id, ':');
2682 if (!desc) {
2683 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2684 return 1;
2685 }
2686 *desc++ = '\0';
2687
2688 p = default_params();
2689 decode_params(p, id);
2690 err = validate_desc(p, desc);
2691 if (err) {
2692 fprintf(stderr, "%s: %s\n", argv[0], err);
2693 return 1;
2694 }
2695 s = new_game(NULL, p, desc);
2696 s2 = new_game(NULL, p, desc);
2697
2698 sc = new_scratch(p->w, p->h);
2699
2700 /*
2701 * When solving an Easy puzzle, we don't want to bother the
2702 * user with Hard-level deductions. For this reason, we grade
2703 * the puzzle internally before doing anything else.
2704 */
2705 ret = -1; /* placate optimiser */
2706 for (diff = 0; diff < DIFFCOUNT; diff++) {
2707 ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
2708 s2->grid, sc, diff);
2709 if (ret < 2)
2710 break;
2711 }
2712
2713 if (diff == DIFFCOUNT) {
2714 if (grade)
2715 printf("Difficulty rating: too hard to solve internally\n");
2716 else
2717 printf("Unable to find a unique solution\n");
2718 } else {
2719 if (grade) {
2720 if (ret == 0)
2721 printf("Difficulty rating: impossible (no solution exists)\n");
2722 else if (ret == 1)
2723 printf("Difficulty rating: %s\n", tents_diffnames[diff]);
2724 } else {
2725 verbose = really_verbose;
2726 ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
2727 s2->grid, sc, diff);
2728 if (ret == 0)
2729 printf("Puzzle is inconsistent\n");
2730 else
2731 fputs(game_text_format(s2), stdout);
2732 }
2733 }
2734
2735 return 0;
2736}
2737
2738#endif
2739
2740/* vim: set shiftwidth=4 tabstop=8: */
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-17 22:47:27 +0000