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