From 86e60e3d907db72ccb60783b2bdab4fc3890f169 Mon Sep 17 00:00:00 2001 From: simon Date: Thu, 13 Oct 2005 18:30:24 +0000 Subject: [PATCH] New puzzle: `Tents'. Requires a potentially shared algorithms module maxflow.c. Also in this checkin, fixes to the OS X and GTK back ends to get ALIGN_VNORMAL right. This is the first time I've used it! :-) git-svn-id: svn://svn.tartarus.org/sgt/puzzles@6390 cda61777-01e9-0310-a592-d414129be87e --- Recipe | 9 +- gtk.c | 4 + list.c | 2 + maxflow.c | 461 ++++++++++++++ maxflow.h | 95 +++ osx.m | 2 + puzzles.but | 52 ++ tents.c | 2041 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 2664 insertions(+), 2 deletions(-) create mode 100644 maxflow.c create mode 100644 maxflow.h create mode 100644 tents.c diff --git a/Recipe b/Recipe index 5907519..31885ca 100644 --- a/Recipe +++ b/Recipe @@ -26,10 +26,11 @@ SLANT = slant dsf MAP = map dsf LOOPY = loopy tree234 dsf LIGHTUP = lightup combi +TENTS = tents maxflow ALL = list NET NETSLIDE cube fifteen sixteen rect pattern solo twiddle + MINES samegame FLIP guess PEGS dominosa UNTANGLE blackbox SLANT - + LIGHTUP MAP LOOPY inertia + + LIGHTUP MAP LOOPY inertia TENTS GTK = gtk printing ps @@ -55,6 +56,7 @@ lightup : [X] GTK COMMON LIGHTUP map : [X] GTK COMMON MAP loopy : [X] GTK COMMON LOOPY inertia : [X] GTK COMMON inertia +tents : [X] GTK COMMON TENTS # Auxiliary command-line programs. STANDALONE = nullfe random misc malloc @@ -65,6 +67,7 @@ mineobfusc : [U] mines[STANDALONE_OBFUSCATOR] tree234 STANDALONE slantsolver : [U] slant[STANDALONE_SOLVER] dsf STANDALONE mapsolver : [U] map[STANDALONE_SOLVER] dsf STANDALONE m.lib lightupsolver : [U] lightup[STANDALONE_SOLVER] combi STANDALONE +tentssolver : [U] tents[STANDALONE_SOLVER] maxflow STANDALONE solosolver : [C] solo[STANDALONE_SOLVER] STANDALONE patternsolver : [C] pattern[STANDALONE_SOLVER] STANDALONE @@ -72,6 +75,7 @@ mineobfusc : [C] mines[STANDALONE_OBFUSCATOR] tree234 STANDALONE slantsolver : [C] slant[STANDALONE_SOLVER] dsf STANDALONE mapsolver : [C] map[STANDALONE_SOLVER] dsf STANDALONE lightupsolver : [C] lightup[STANDALONE_SOLVER] combi STANDALONE +tentssolver : [C] tents[STANDALONE_SOLVER] maxflow STANDALONE # The Windows Net shouldn't be called `net.exe' since Windows # already has a reasonably important utility program by that name! @@ -97,6 +101,7 @@ lightup : [G] WINDOWS COMMON LIGHTUP map : [G] WINDOWS COMMON MAP loopy : [G] WINDOWS COMMON LOOPY inertia : [G] WINDOWS COMMON inertia +tents : [G] WINDOWS COMMON TENTS # Mac OS X unified application containing all the puzzles. Puzzles : [MX] osx osx.icns osx-info.plist COMMON ALL @@ -189,7 +194,7 @@ install: for i in cube net netslide fifteen sixteen twiddle \ pattern rect solo mines samegame flip guess \ pegs dominosa untangle blackbox slant lightup \ - map loopy inertia; do \ + map loopy inertia tents; do \ $(INSTALL_PROGRAM) -m 755 $$i $(DESTDIR)$(gamesdir)/$$i \ || exit 1; \ done diff --git a/gtk.c b/gtk.c index 802c42e..528300e 100644 --- a/gtk.c +++ b/gtk.c @@ -290,6 +290,8 @@ void gtk_draw_text(void *handle, int x, int y, int fonttype, int fontsize, if (align & ALIGN_VCENTRE) rect.y -= rect.height / 2; + else + rect.y -= rect.height; if (align & ALIGN_HCENTRE) rect.x -= rect.width / 2; @@ -317,6 +319,8 @@ void gtk_draw_text(void *handle, int x, int y, int fonttype, int fontsize, &lb, &rb, &wid, &asc, &desc); if (align & ALIGN_VCENTRE) y += asc - (asc+desc)/2; + else + y += asc; /* * ... but horizontal extents with respect to the provided diff --git a/list.c b/list.c index 7b57c4f..71b1673 100644 --- a/list.c +++ b/list.c @@ -37,6 +37,7 @@ extern const game samegame; extern const game sixteen; extern const game slant; extern const game solo; +extern const game tents; extern const game twiddle; extern const game untangle; @@ -61,6 +62,7 @@ const game *gamelist[] = { &sixteen, &slant, &solo, + &tents, &twiddle, &untangle, }; diff --git a/maxflow.c b/maxflow.c new file mode 100644 index 0000000..028946b --- /dev/null +++ b/maxflow.c @@ -0,0 +1,461 @@ +/* + * Edmonds-Karp algorithm for finding a maximum flow and minimum + * cut in a network. Almost identical to the Ford-Fulkerson + * algorithm, but apparently using breadth-first search to find the + * _shortest_ augmenting path is a good way to guarantee + * termination and ensure the time complexity is not dependent on + * the actual value of the maximum flow. I don't understand why + * that should be, but it's claimed on the Internet that it's been + * proved, and that's good enough for me. I prefer BFS to DFS + * anyway :-) + */ + +#include +#include +#include + +#include "maxflow.h" + +#include "puzzles.h" /* for snewn/sfree */ + +int maxflow_with_scratch(void *scratch, int nv, int source, int sink, + int ne, const int *edges, const int *backedges, + const int *capacity, int *flow, int *cut) +{ + int *todo = (int *)scratch; + int *prev = todo + nv; + int *firstedge = todo + 2*nv; + int *firstbackedge = todo + 3*nv; + int i, j, head, tail, from, to; + int totalflow; + + /* + * Scan the edges array to find the index of the first edge + * from each node. + */ + j = 0; + for (i = 0; i < ne; i++) + while (j <= edges[2*i]) + firstedge[j++] = i; + while (j < nv) + firstedge[j++] = ne; + assert(j == nv); + + /* + * Scan the backedges array to find the index of the first edge + * _to_ each node. + */ + j = 0; + for (i = 0; i < ne; i++) + while (j <= edges[2*backedges[i]+1]) + firstbackedge[j++] = i; + while (j < nv) + firstbackedge[j++] = ne; + assert(j == nv); + + /* + * Start the flow off at zero on every edge. + */ + for (i = 0; i < ne; i++) + flow[i] = 0; + totalflow = 0; + + /* + * Repeatedly look for an augmenting path, and follow it. + */ + while (1) { + + /* + * Set up the prev array. + */ + for (i = 0; i < nv; i++) + prev[i] = -1; + + /* + * Initialise the to-do list for BFS. + */ + head = tail = 0; + todo[tail++] = source; + + /* + * Now do the BFS loop. + */ + while (head < tail && prev[sink] <= 0) { + from = todo[head++]; + + /* + * Try all the forward edges out of node `from'. For a + * forward edge to be valid, it must have flow + * currently less than its capacity. + */ + for (i = firstedge[from]; i < ne && edges[2*i] == from; i++) { + to = edges[2*i+1]; + if (to == source || prev[to] >= 0) + continue; + if (capacity[i] >= 0 && flow[i] >= capacity[i]) + continue; + /* + * This is a valid augmenting edge. Visit node `to'. + */ + prev[to] = 2*i; + todo[tail++] = to; + } + + /* + * Try all the backward edges into node `from'. For a + * backward edge to be valid, it must have flow + * currently greater than zero. + */ + for (i = firstbackedge[from]; + j = backedges[i], i < ne && edges[2*j+1]==from; i++) { + to = edges[2*j]; + if (to == source || prev[to] >= 0) + continue; + if (flow[j] <= 0) + continue; + /* + * This is a valid augmenting edge. Visit node `to'. + */ + prev[to] = 2*j+1; + todo[tail++] = to; + } + } + + /* + * If prev[sink] is non-null, we have found an augmenting + * path. + */ + if (prev[sink] >= 0) { + int max; + + /* + * Work backwards along the path figuring out the + * maximum flow we can add. + */ + to = sink; + max = -1; + while (to != source) { + int spare; + + /* + * Find the edge we're currently moving along. + */ + i = prev[to]; + from = edges[i]; + assert(from != to); + + /* + * Determine the spare capacity of this edge. + */ + if (i & 1) + spare = flow[i / 2]; /* backward edge */ + else if (capacity[i / 2] >= 0) + spare = capacity[i / 2] - flow[i / 2]; /* forward edge */ + else + spare = -1; /* unlimited forward edge */ + + assert(spare != 0); + + if (max < 0 || (spare >= 0 && spare < max)) + max = spare; + + to = from; + } + /* + * Fail an assertion if max is still < 0, i.e. there is + * an entirely unlimited path from source to sink. Also + * max should not _be_ zero, because by construction + * this _should_ be an augmenting path. + */ + assert(max > 0); + + /* + * Now work backwards along the path again, this time + * actually adjusting the flow. + */ + to = sink; + while (to != source) { + /* + * Find the edge we're currently moving along. + */ + i = prev[to]; + from = edges[i]; + assert(from != to); + + /* + * Adjust the edge. + */ + if (i & 1) + flow[i / 2] -= max; /* backward edge */ + else + flow[i / 2] += max; /* forward edge */ + + to = from; + } + + /* + * And adjust the overall flow counter. + */ + totalflow += max; + + continue; + } + + /* + * If we reach here, we have failed to find an augmenting + * path, which means we're done. Output the `cut' array if + * required, and leave. + */ + if (cut) { + for (i = 0; i < nv; i++) { + if (i == source || prev[i] >= 0) + cut[i] = 0; + else + cut[i] = 1; + } + } + return totalflow; + } +} + +int maxflow_scratch_size(int nv) +{ + return (nv * 4) * sizeof(int); +} + +void maxflow_setup_backedges(int ne, const int *edges, int *backedges) +{ + int i, n; + + for (i = 0; i < ne; i++) + backedges[i] = i; + + /* + * We actually can't use the C qsort() function, because we'd + * need to pass `edges' as a context parameter to its + * comparator function. So instead I'm forced to implement my + * own sorting algorithm internally, which is a pest. I'll use + * heapsort, because I like it. + */ + +#define LESS(i,j) ( (edges[2*(i)+1] < edges[2*(j)+1]) || \ + (edges[2*(i)+1] == edges[2*(j)+1] && \ + edges[2*(i)] < edges[2*(j)]) ) +#define PARENT(n) ( ((n)-1)/2 ) +#define LCHILD(n) ( 2*(n)+1 ) +#define RCHILD(n) ( 2*(n)+2 ) +#define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0) + + /* + * Phase 1: build the heap. We want the _largest_ element at + * the top. + */ + n = 0; + while (n < ne) { + n++; + + /* + * Swap element n with its parent repeatedly to preserve + * the heap property. + */ + i = n-1; + + while (i > 0) { + int p = PARENT(i); + + if (LESS(backedges[p], backedges[i])) { + SWAP(backedges[p], backedges[i]); + i = p; + } else + break; + } + } + + /* + * Phase 2: repeatedly remove the largest element and stick it + * at the top of the array. + */ + while (n > 0) { + /* + * The largest element is at position 0. Put it at the top, + * and swap the arbitrary element from that position into + * position 0. + */ + n--; + SWAP(backedges[0], backedges[n]); + + /* + * Now repeatedly move that arbitrary element down the heap + * by swapping it with the more suitable of its children. + */ + i = 0; + while (1) { + int lc, rc; + + lc = LCHILD(i); + rc = RCHILD(i); + + if (lc >= n) + break; /* we've hit bottom */ + + if (rc >= n) { + /* + * Special case: there is only one child to check. + */ + if (LESS(backedges[i], backedges[lc])) + SWAP(backedges[i], backedges[lc]); + + /* _Now_ we've hit bottom. */ + break; + } else { + /* + * The common case: there are two children and we + * must check them both. + */ + if (LESS(backedges[i], backedges[lc]) || + LESS(backedges[i], backedges[rc])) { + /* + * Pick the more appropriate child to swap with + * (i.e. the one which would want to be the + * parent if one were above the other - as one + * is about to be). + */ + if (LESS(backedges[lc], backedges[rc])) { + SWAP(backedges[i], backedges[rc]); + i = rc; + } else { + SWAP(backedges[i], backedges[lc]); + i = lc; + } + } else { + /* This element is in the right place; we're done. */ + break; + } + } + } + } + +#undef LESS +#undef PARENT +#undef LCHILD +#undef RCHILD +#undef SWAP + +} + +int maxflow(int nv, int source, int sink, + int ne, const int *edges, const int *capacity, + int *flow, int *cut) +{ + void *scratch; + int *backedges; + int size; + int ret; + + /* + * Allocate the space. + */ + size = ne * sizeof(int) + maxflow_scratch_size(nv); + backedges = smalloc(size); + if (!backedges) + return -1; + scratch = backedges + ne; + + /* + * Set up the backedges array. + */ + maxflow_setup_backedges(ne, edges, backedges); + + /* + * Call the main function. + */ + ret = maxflow_with_scratch(scratch, nv, source, sink, ne, edges, + backedges, capacity, flow, cut); + + /* + * Free the scratch space. + */ + sfree(backedges); + + /* + * And we're done. + */ + return ret; +} + +#ifdef TESTMODE + +#define MAXEDGES 256 +#define MAXVERTICES 128 +#define ADDEDGE(i,j) do{edges[ne*2] = (i); edges[ne*2+1] = (j); ne++;}while(0) + +int compare_edge(const void *av, const void *bv) +{ + const int *a = (const int *)av; + const int *b = (const int *)bv; + + if (a[0] < b[0]) + return -1; + else if (a[0] > b[0]) + return +1; + else if (a[1] < b[1]) + return -1; + else if (a[1] > b[1]) + return +1; + else + return 0; +} + +int main(void) +{ + int edges[MAXEDGES*2], ne, nv; + int capacity[MAXEDGES], flow[MAXEDGES], cut[MAXVERTICES]; + int source, sink, p, q, i, j, ret; + + /* + * Use this algorithm to find a maximal complete matching in a + * bipartite graph. + */ + ne = 0; + nv = 0; + source = nv++; + p = nv; + nv += 5; + q = nv; + nv += 5; + sink = nv++; + for (i = 0; i < 5; i++) { + capacity[ne] = 1; + ADDEDGE(source, p+i); + } + for (i = 0; i < 5; i++) { + capacity[ne] = 1; + ADDEDGE(q+i, sink); + } + j = ne; + capacity[ne] = 1; ADDEDGE(p+0,q+0); + capacity[ne] = 1; ADDEDGE(p+1,q+0); + capacity[ne] = 1; ADDEDGE(p+1,q+1); + capacity[ne] = 1; ADDEDGE(p+2,q+1); + capacity[ne] = 1; ADDEDGE(p+2,q+2); + capacity[ne] = 1; ADDEDGE(p+3,q+2); + capacity[ne] = 1; ADDEDGE(p+3,q+3); + capacity[ne] = 1; ADDEDGE(p+4,q+3); + /* capacity[ne] = 1; ADDEDGE(p+2,q+4); */ + qsort(edges, ne, 2*sizeof(int), compare_edge); + + ret = maxflow(nv, source, sink, ne, edges, capacity, flow, cut); + + printf("ret = %d\n", ret); + + for (i = 0; i < ne; i++) + printf("flow %d: %d -> %d\n", flow[i], edges[2*i], edges[2*i+1]); + + for (i = 0; i < nv; i++) + if (cut[i] == 0) + printf("difficult set includes %d\n", i); + + return 0; +} + +#endif diff --git a/maxflow.h b/maxflow.h new file mode 100644 index 0000000..d490f45 --- /dev/null +++ b/maxflow.h @@ -0,0 +1,95 @@ +/* + * Edmonds-Karp algorithm for finding a maximum flow and minimum + * cut in a network. Almost identical to the Ford-Fulkerson + * algorithm, but apparently using breadth-first search to find the + * _shortest_ augmenting path is a good way to guarantee + * termination and ensure the time complexity is not dependent on + * the actual value of the maximum flow. I don't understand why + * that should be, but it's claimed on the Internet that it's been + * proved, and that's good enough for me. I prefer BFS to DFS + * anyway :-) + */ + +#ifndef MAXFLOW_MAXFLOW_H +#define MAXFLOW_MAXFLOW_H + +/* + * The actual algorithm. + * + * Inputs: + * + * - `scratch' is previously allocated scratch space of a size + * previously determined by calling `maxflow_scratch_size'. + * + * - `nv' is the number of vertices. Vertices are assumed to be + * numbered from 0 to nv-1. + * + * - `source' and `sink' are the distinguished source and sink + * vertices. + * + * - `ne' is the number of edges in the graph. + * + * - `edges' is an array of 2*ne integers, giving a (source, dest) + * pair for each network edge. Edge pairs are expected to be + * sorted in lexicographic order. + * + * - `backedges' is an array of `ne' integers, each a distinct + * index into `edges'. The edges in `edges', if permuted as + * specified by this array, should end up sorted in the _other_ + * lexicographic order, i.e. dest taking priority over source. + * + * - `capacity' is an array of `ne' integers, giving a maximum + * flow capacity for each edge. A negative value is taken to + * indicate unlimited capacity on that edge, but note that there + * may not be any unlimited-capacity _path_ from source to sink + * or an assertion will be failed. + * + * Output: + * + * - `flow' must be non-NULL. It is an array of `ne' integers, + * each giving the final flow along each edge. + * + * - `cut' may be NULL. If non-NULL, it is an array of `nv' + * integers, which will be set to zero or one on output, in such + * a way that: + * + the set of zero vertices includes the source + * + the set of one vertices includes the sink + * + the maximum flow capacity between the zero and one vertex + * sets is achieved (i.e. all edges from a zero vertex to a + * one vertex are at full capacity, while all edges from a + * one vertex to a zero vertex have no flow at all). + * + * - the returned value from the function is the total flow + * achieved. + */ +int maxflow_with_scratch(void *scratch, int nv, int source, int sink, + int ne, const int *edges, const int *backedges, + const int *capacity, int *flow, int *cut); + +/* + * The above function expects its `scratch' and `backedges' + * parameters to have already been set up. This allows you to set + * them up once and use them in multiple invocates of the + * algorithm. Now I provide functions to actually do the setting + * up. + */ +int maxflow_scratch_size(int nv); +void maxflow_setup_backedges(int ne, const int *edges, int *backedges); + +/* + * Simplified version of the above function. All parameters are the + * same, except that `scratch' and `backedges' are constructed + * internally. This is the simplest way to call the algorithm as a + * one-off; however, if you need to call it multiple times on the + * same network, it is probably better to call the above version + * directly so that you only construct `scratch' and `backedges' + * once. + * + * Additional return value is now -1, meaning that scratch space + * could not be allocated. + */ +int maxflow(int nv, int source, int sink, + int ne, const int *edges, const int *capacity, + int *flow, int *cut); + +#endif /* MAXFLOW_MAXFLOW_H */ diff --git a/osx.m b/osx.m index 101dfe4..e19db27 100644 --- a/osx.m +++ b/osx.m @@ -1341,6 +1341,8 @@ static void osx_draw_text(void *handle, int x, int y, int fonttype, point.x -= size.width / 2; if (align & ALIGN_VCENTRE) point.y -= size.height / 2; + else + point.y -= size.height; [string drawAtPoint:point withAttributes:attr]; } diff --git a/puzzles.but b/puzzles.but index 00dfef5..34f876c 100644 --- a/puzzles.but +++ b/puzzles.but @@ -1802,6 +1802,58 @@ These parameters are available from the \q{Custom...} option on the \dd Size of grid in squares. +\C{tents} \i{Tents} + +\cfg{winhelp-topic}{games.tents} + +You have a grid of squares, some of which contain trees. Your aim is +to place tents in some of the remaining squares, in such a way that +the following conditions are met: + +\b There are exactly as many tents as trees. + +\b The tents and trees can be matched up in such a way that each +tent is directly adjacent (horizontally or vertically, but not +diagonally) to its own tree. However, a tent may be adjacent to +other trees as well as its own. + +\b No two tents are adjacent horizontally, vertically \e{or +diagonally}. + +\b The number of tents in each row, and in each column, matches the +numbers given round the sides of the grid. + +This puzzle can be found in several places on the Internet, and was +brought to my attention by e-mail. I don't know who I should credit +for inventing it. + +\H{tents-controls} \i{Tents controls} + +\IM{Tents controls} controls, for Tents + +Left-clicking in a blank square will place a tent in it. +Right-clicking in a blank square will colour it green, indicating +that you are sure it \e{isn't} a tent. Clicking either button in an +occupied square will clear it. + +(All the actions described in \k{common-actions} are also available.) + +\H{tents-parameters} \I{parameters, for Tents}Tents parameters + +These parameters are available from the \q{Custom...} option on the +\q{Type} menu. + +\dt \e{Width}, \e{Height} + +\dd Size of grid in squares. + +\dt \e{Difficulty} + +\dd Controls the difficulty of the generated puzzle. More difficult +puzzles require more complex deductions, but at present none of the +available difficulty levels requires guesswork or backtracking. + + \A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2005 Simon Tatham. diff --git a/tents.c b/tents.c new file mode 100644 index 0000000..113fa17 --- /dev/null +++ b/tents.c @@ -0,0 +1,2041 @@ +/* + * tents.c: Puzzle involving placing tents next to trees subject to + * some confusing conditions. + * + * TODO: + * + * - error highlighting? + * * highlighting adjacent tents is easy + * * highlighting violated numeric clues is almost as easy + * (might want to pay attention to NONTENTs here) + * * but how in hell do we highlight a failure of maxflow + * during completion checking? + * + well, the _obvious_ approach is to use maxflow's own + * error report: it will provide, via the `cut' parameter, + * a set of trees which have too few tents between them. + * It's unclear that this will be particularly obvious to + * a user, however. Is there any other way? + * + * - it might be nice to make setter-provided tent/nontent clues + * inviolable? + * * on the other hand, this would introduce considerable extra + * complexity and size into the game state; also inviolable + * clues would have to be marked as such somehow, in an + * intrusive and annoying manner. Since they're never + * generated by _my_ generator, I'm currently more inclined + * not to bother. + * + * - more difficult levels at the top end? + * * for example, sometimes we can deduce that two BLANKs in + * the same row are each adjacent to the same unattached tree + * and to nothing else, implying that they can't both be + * tents; this enables us to rule out some extra combinations + * in the row-based deduction loop, and hence deduce more + * from the number in that row than we could otherwise do. + * * that by itself doesn't seem worth implementing a new + * difficulty level for, but if I can find a few more things + * like that then it might become worthwhile. + * * I wonder if there's a sensible heuristic for where to + * guess which would make a recursive solver viable? + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" +#include "maxflow.h" + +/* + * Design discussion + * ----------------- + * + * The rules of this puzzle as available on the WWW are poorly + * specified. The bits about tents having to be orthogonally + * adjacent to trees, tents not being even diagonally adjacent to + * one another, and the number of tents in each row and column + * being given are simple enough; the difficult bit is the + * tent-to-tree matching. + * + * Some sources use simplistic wordings such as `each tree is + * exactly connected to only one tent', which is extremely unclear: + * it's easy to read erroneously as `each tree is _orthogonally + * adjacent_ to exactly one tent', which is definitely incorrect. + * Even the most coherent sources I've found don't do a much better + * job of stating the rule. + * + * A more precise statement of the rule is that it must be possible + * to find a bijection f between tents and trees such that each + * tree T is orthogonally adjacent to the tent f(T), but that a + * tent is permitted to be adjacent to other trees in addition to + * its own. This slightly non-obvious criterion is what gives this + * puzzle most of its subtlety. + * + * However, there's a particularly subtle ambiguity left over. Is + * the bijection between tents and trees required to be _unique_? + * In other words, is that bijection conceptually something the + * player should be able to exhibit as part of the solution (even + * if they aren't actually required to do so)? Or is it sufficient + * to have a unique _placement_ of the tents which gives rise to at + * least one suitable bijection? + * + * The puzzle shown to the right of this .T. 2 *T* 2 + * paragraph illustrates the problem. There T.T 0 -> T-T 0 + * are two distinct bijections available. .T. 2 *T* 2 + * The answer to the above question will + * determine whether it's a valid puzzle. 202 202 + * + * This is an important question, because it affects both the + * player and the generator. Eventually I found all the instances + * of this puzzle I could Google up, solved them all by hand, and + * verified that in all cases the tree/tent matching was uniquely + * determined given the tree and tent positions. Therefore, the + * puzzle as implemented in this source file takes the following + * policy: + * + * - When checking a user-supplied solution for correctness, only + * verify that there exists _at least_ one matching. + * - When generating a puzzle, enforce that there must be + * _exactly_ one. + * + * Algorithmic implications + * ------------------------ + * + * Another way of phrasing the tree/tent matching criterion is to + * say that the bipartite adjacency graph between trees and tents + * has a perfect matching. That is, if you construct a graph which + * has a vertex per tree and a vertex per tent, and an edge between + * any tree and tent which are orthogonally adjacent, it is + * possible to find a set of N edges of that graph (where N is the + * number of trees and also the number of tents) which between them + * connect every tree to every tent. + * + * The most efficient known algorithms for finding such a matching + * given a graph, as far as I'm aware, are the Munkres assignment + * algorithm (also known as the Hungarian algorithm) and the + * Ford-Fulkerson algorithm (for finding optimal flows in + * networks). Each of these takes O(N^3) running time; so we're + * talking O(N^3) time to verify any candidate solution to this + * puzzle. That's just about OK if you're doing it once per mouse + * click (and in fact not even that, since the sensible thing to do + * is check all the _other_ puzzle criteria and only wade into this + * quagmire if none are violated); but if the solver had to keep + * doing N^3 work internally, then it would probably end up with + * more like N^5 or N^6 running time, and grid generation would + * become very clunky. + * + * Fortunately, I've been able to prove a very useful property of + * _unique_ perfect matchings, by adapting the proof of Hall's + * Marriage Theorem. For those unaware of Hall's Theorem, I'll + * recap it and its proof: it states that a bipartite graph + * contains a perfect matching iff every set of vertices on the + * left side of the graph have a neighbourhood _at least_ as big on + * the right. + * + * This condition is obviously satisfied if a perfect matching does + * exist; each left-side node has a distinct right-side node which + * is the one assigned to it by the matching, and thus any set of n + * left vertices must have a combined neighbourhood containing at + * least the n corresponding right vertices, and possibly others + * too. Alternatively, imagine if you had (say) three left-side + * nodes all of which were connected to only two right-side nodes + * between them: any perfect matching would have to assign one of + * those two right nodes to each of the three left nodes, and still + * give the three left nodes a different right node each. This is + * of course impossible. + * + * To prove the converse (that if every subset of left vertices + * satisfies the Hall condition then a perfect matching exists), + * consider trying to find a proper subset of the left vertices + * which _exactly_ satisfies the Hall condition: that is, its right + * neighbourhood is precisely the same size as it. If we can find + * such a subset, then we can split the bipartite graph into two + * smaller ones: one consisting of the left subset and its right + * neighbourhood, the other consisting of everything else. Edges + * from the left side of the former graph to the right side of the + * latter do not exist, by construction; edges from the right side + * of the former to the left of the latter cannot be part of any + * perfect matching because otherwise the left subset would not be + * left with enough distinct right vertices to connect to (this is + * exactly the same deduction used in Solo's set analysis). You can + * then prove (left as an exercise) that both these smaller graphs + * still satisfy the Hall condition, and therefore the proof will + * follow by induction. + * + * There's one other possibility, which is the case where _no_ + * proper subset of the left vertices has a right neighbourhood of + * exactly the same size. That is, every left subset has a strictly + * _larger_ right neighbourhood. In this situation, we can simply + * remove an _arbitrary_ edge from the graph. This cannot reduce + * the size of any left subset's right neighbourhood by more than + * one, so if all neighbourhoods were strictly bigger than they + * needed to be initially, they must now still be _at least as big_ + * as they need to be. So we can keep throwing out arbitrary edges + * until we find a set which exactly satisfies the Hall condition, + * and then proceed as above. [] + * + * That's Hall's theorem. I now build on this by examining the + * circumstances in which a bipartite graph can have a _unique_ + * perfect matching. It is clear that in the second case, where no + * left subset exactly satisfies the Hall condition and so we can + * remove an arbitrary edge, there cannot be a unique perfect + * matching: given one perfect matching, we choose our arbitrary + * removed edge to be one of those contained in it, and then we can + * still find a perfect matching in the remaining graph, which will + * be a distinct perfect matching in the original. + * + * So it is a necessary condition for a unique perfect matching + * that there must be at least one proper left subset which + * _exactly_ satisfies the Hall condition. But now consider the + * smaller graph constructed by taking that left subset and its + * neighbourhood: if the graph as a whole had a unique perfect + * matching, then so must this smaller one, which means we can find + * a proper left subset _again_, and so on. Repeating this process + * must eventually reduce us to a graph with only one left-side + * vertex (so there are no proper subsets at all); this vertex must + * be connected to only one right-side vertex, and hence must be so + * in the original graph as well (by construction). So we can + * discard this vertex pair from the graph, and any other edges + * that involved it (which will by construction be from other left + * vertices only), and the resulting smaller graph still has a + * unique perfect matching which means we can do the same thing + * again. + * + * In other words, given any bipartite graph with a unique perfect + * matching, we can find that matching by the following extremely + * simple algorithm: + * + * - Find a left-side vertex which is only connected to one + * right-side vertex. + * - Assign those vertices to one another, and therefore discard + * any other edges connecting to that right vertex. + * - Repeat until all vertices have been matched. + * + * This algorithm can be run in O(V+E) time (where V is the number + * of vertices and E is the number of edges in the graph), and the + * only way it can fail is if there is not a unique perfect + * matching (either because there is no matching at all, or because + * it isn't unique; but it can't distinguish those cases). + * + * Thus, the internal solver in this source file can be confident + * that if the tree/tent matching is uniquely determined by the + * tree and tent positions, it can find it using only this kind of + * obvious and simple operation: assign a tree to a tent if it + * cannot possibly belong to any other tent, and vice versa. If the + * solver were _only_ trying to determine the matching, even that + * `vice versa' wouldn't be required; but it can come in handy when + * not all the tents have been placed yet. I can therefore be + * reasonably confident that as long as my solver doesn't need to + * cope with grids that have a non-unique matching, it will also + * not need to do anything complicated like set analysis between + * trees and tents. + */ + +/* + * In standalone solver mode, `verbose' is a variable which can be + * set by command-line option; in debugging mode it's simply always + * true. + */ +#if defined STANDALONE_SOLVER +#define SOLVER_DIAGNOSTICS +int verbose = FALSE; +#elif defined SOLVER_DIAGNOSTICS +#define verbose TRUE +#endif + +/* + * Difficulty levels. I do some macro ickery here to ensure that my + * enum and the various forms of my name list always match up. + */ +#define DIFFLIST(A) \ + A(EASY,Easy,e) \ + A(TRICKY,Tricky,t) +#define ENUM(upper,title,lower) DIFF_ ## upper, +#define TITLE(upper,title,lower) #title, +#define ENCODE(upper,title,lower) #lower +#define CONFIG(upper,title,lower) ":" #title +enum { DIFFLIST(ENUM) DIFFCOUNT }; +static char const *const tents_diffnames[] = { DIFFLIST(TITLE) }; +static char const tents_diffchars[] = DIFFLIST(ENCODE); +#define DIFFCONFIG DIFFLIST(CONFIG) + +enum { + COL_BACKGROUND, + COL_GRID, + COL_GRASS, + COL_TREETRUNK, + COL_TREELEAF, + COL_TENT, + NCOLOURS +}; + +enum { BLANK, TREE, TENT, NONTENT, MAGIC }; + +struct game_params { + int w, h; + int diff; +}; + +struct numbers { + int refcount; + int *numbers; +}; + +struct game_state { + game_params p; + char *grid; + struct numbers *numbers; + int completed, used_solve; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = ret->h = 8; + ret->diff = DIFF_EASY; + + return ret; +} + +static const struct game_params tents_presets[] = { + {8, 8, DIFF_EASY}, + {8, 8, DIFF_TRICKY}, + {10, 10, DIFF_EASY}, + {10, 10, DIFF_TRICKY}, + {15, 15, DIFF_EASY}, + {15, 15, DIFF_TRICKY}, +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char str[80]; + + if (i < 0 || i >= lenof(tents_presets)) + return FALSE; + + ret = snew(game_params); + *ret = tents_presets[i]; + + sprintf(str, "%dx%d %s", ret->w, ret->h, tents_diffnames[ret->diff]); + + *name = dupstr(str); + *params = ret; + return TRUE; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *params, char const *string) +{ + params->w = params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } + if (*string == 'd') { + int i; + string++; + for (i = 0; i < DIFFCOUNT; i++) + if (*string == tents_diffchars[i]) + params->diff = i; + if (*string) string++; + } +} + +static char *encode_params(game_params *params, int full) +{ + char buf[120]; + + sprintf(buf, "%dx%d", params->w, params->h); + if (full) + sprintf(buf + strlen(buf), "d%c", + tents_diffchars[params->diff]); + return dupstr(buf); +} + +static config_item *game_configure(game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(4, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].sval = dupstr(buf); + ret[1].ival = 0; + + ret[2].name = "Difficulty"; + ret[2].type = C_CHOICES; + ret[2].sval = DIFFCONFIG; + ret[2].ival = params->diff; + + ret[3].name = NULL; + ret[3].type = C_END; + ret[3].sval = NULL; + ret[3].ival = 0; + + return ret; +} + +static game_params *custom_params(config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].sval); + ret->h = atoi(cfg[1].sval); + ret->diff = cfg[2].ival; + + return ret; +} + +static char *validate_params(game_params *params, int full) +{ + if (params->w < 2 || params->h < 2) + return "Width and height must both be at least two"; + return NULL; +} + +/* + * Scratch space for solver. + */ +enum { N, U, L, R, D, MAXDIR }; /* link directions */ +#define dx(d) ( ((d)==R) - ((d)==L) ) +#define dy(d) ( ((d)==D) - ((d)==U) ) +#define F(d) ( U + D - (d) ) +struct solver_scratch { + char *links; /* mapping between trees and tents */ + int *locs; + char *place, *mrows, *trows; +}; + +static struct solver_scratch *new_scratch(int w, int h) +{ + struct solver_scratch *ret = snew(struct solver_scratch); + + ret->links = snewn(w*h, char); + ret->locs = snewn(max(w, h), int); + ret->place = snewn(max(w, h), char); + ret->mrows = snewn(3 * max(w, h), char); + ret->trows = snewn(3 * max(w, h), char); + + return ret; +} + +static void free_scratch(struct solver_scratch *sc) +{ + sfree(sc->trows); + sfree(sc->mrows); + sfree(sc->place); + sfree(sc->locs); + sfree(sc->links); + sfree(sc); +} + +/* + * Solver. Returns 0 for impossibility, 1 for success, 2 for + * ambiguity or failure to converge. + */ +static int tents_solve(int w, int h, const char *grid, int *numbers, + char *soln, struct solver_scratch *sc, int diff) +{ + int x, y, d, i, j; + char *mrow, *mrow1, *mrow2, *trow, *trow1, *trow2; + + /* + * Set up solver data. + */ + memset(sc->links, N, w*h); + + /* + * Set up solution array. + */ + memcpy(soln, grid, w*h); + + /* + * Main solver loop. + */ + while (1) { + int done_something = FALSE; + + /* + * Any tent which has only one unattached tree adjacent to + * it can be tied to that tree. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + if (soln[y*w+x] == TENT && !sc->links[y*w+x]) { + int linkd = 0; + + for (d = 1; d < MAXDIR; d++) { + int x2 = x + dx(d), y2 = y + dy(d); + if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && + soln[y2*w+x2] == TREE && + !sc->links[y2*w+x2]) { + if (linkd) + break; /* found more than one */ + else + linkd = d; + } + } + + if (d == MAXDIR && linkd == 0) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("tent at %d,%d cannot link to anything\n", + x, y); +#endif + return 0; /* no solution exists */ + } else if (d == MAXDIR) { + int x2 = x + dx(linkd), y2 = y + dy(linkd); + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("tent at %d,%d can only link to tree at" + " %d,%d\n", x, y, x2, y2); +#endif + + sc->links[y*w+x] = linkd; + sc->links[y2*w+x2] = F(linkd); + done_something = TRUE; + } + } + + if (done_something) + continue; + if (diff < 0) + break; /* don't do anything else! */ + + /* + * Mark a blank square as NONTENT if it is not orthogonally + * adjacent to any unmatched tree. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + if (soln[y*w+x] == BLANK) { + int can_be_tent = FALSE; + + for (d = 1; d < MAXDIR; d++) { + int x2 = x + dx(d), y2 = y + dy(d); + if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && + soln[y2*w+x2] == TREE && + !sc->links[y2*w+x2]) + can_be_tent = TRUE; + } + + if (!can_be_tent) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%d,%d cannot be a tent (no adjacent" + " unmatched tree)\n", x, y); +#endif + soln[y*w+x] = NONTENT; + done_something = TRUE; + } + } + + if (done_something) + continue; + + /* + * Mark a blank square as NONTENT if it is (perhaps + * diagonally) adjacent to any other tent. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + if (soln[y*w+x] == BLANK) { + int dx, dy, imposs = FALSE; + + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) + if (dy || dx) { + int x2 = x + dx, y2 = y + dy; + if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && + soln[y2*w+x2] == TENT) + imposs = TRUE; + } + + if (imposs) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%d,%d cannot be a tent (adjacent tent)\n", + x, y); +#endif + soln[y*w+x] = NONTENT; + done_something = TRUE; + } + } + + if (done_something) + continue; + + /* + * Any tree which has exactly one {unattached tent, BLANK} + * adjacent to it must have its tent in that square. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + if (soln[y*w+x] == TREE && !sc->links[y*w+x]) { + int linkd = 0, linkd2 = 0, nd = 0; + + for (d = 1; d < MAXDIR; d++) { + int x2 = x + dx(d), y2 = y + dy(d); + if (!(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h)) + continue; + if (soln[y2*w+x2] == BLANK || + (soln[y2*w+x2] == TENT && !sc->links[y2*w+x2])) { + if (linkd) + linkd2 = d; + else + linkd = d; + nd++; + } + } + + if (nd == 0) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("tree at %d,%d cannot link to anything\n", + x, y); +#endif + return 0; /* no solution exists */ + } else if (nd == 1) { + int x2 = x + dx(linkd), y2 = y + dy(linkd); + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("tree at %d,%d can only link to tent at" + " %d,%d\n", x, y, x2, y2); +#endif + soln[y2*w+x2] = TENT; + sc->links[y*w+x] = linkd; + sc->links[y2*w+x2] = F(linkd); + done_something = TRUE; + } else if (nd == 2 && (!dx(linkd) != !dx(linkd2)) && + diff >= DIFF_TRICKY) { + /* + * If there are two possible places where + * this tree's tent can go, and they are + * diagonally separated rather than being + * on opposite sides of the tree, then the + * square (other than the tree square) + * which is adjacent to both of them must + * be a non-tent. + */ + int x2 = x + dx(linkd) + dx(linkd2); + int y2 = y + dy(linkd) + dy(linkd2); + assert(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h); + if (soln[y2*w+x2] == BLANK) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("possible tent locations for tree at" + " %d,%d rule out tent at %d,%d\n", + x, y, x2, y2); +#endif + soln[y2*w+x2] = NONTENT; + done_something = TRUE; + } + } + } + + if (done_something) + continue; + + /* + * If localised deductions about the trees and tents + * themselves haven't helped us, it's time to resort to the + * numbers round the grid edge. For each row and column, we + * go through all possible combinations of locations for + * the unplaced tents, rule out any which have adjacent + * tents, and spot any square which is given the same state + * by all remaining combinations. + */ + for (i = 0; i < w+h; i++) { + int start, step, len, start1, start2, n, k; + + if (i < w) { + /* + * This is the number for a column. + */ + start = i; + step = w; + len = h; + if (i > 0) + start1 = start - 1; + else + start1 = -1; + if (i+1 < w) + start2 = start + 1; + else + start2 = -1; + } else { + /* + * This is the number for a row. + */ + start = (i-w)*w; + step = 1; + len = w; + if (i > w) + start1 = start - w; + else + start1 = -1; + if (i+1 < w+h) + start2 = start + w; + else + start2 = -1; + } + + if (diff < DIFF_TRICKY) { + /* + * In Easy mode, we don't look at the effect of one + * row on the next (i.e. ruling out a square if all + * possibilities for an adjacent row place a tent + * next to it). + */ + start1 = start2 = -1; + } + + k = numbers[i]; + + /* + * Count and store the locations of the free squares, + * and also count the number of tents already placed. + */ + n = 0; + for (j = 0; j < len; j++) { + if (soln[start+j*step] == TENT) + k--; /* one fewer tent to place */ + else if (soln[start+j*step] == BLANK) + sc->locs[n++] = j; + } + + if (n == 0) + continue; /* nothing left to do here */ + + /* + * Now we know we're placing k tents in n squares. Set + * up the first possibility. + */ + for (j = 0; j < n; j++) + sc->place[j] = (j < k ? TENT : NONTENT); + + /* + * We're aiming to find squares in this row which are + * invariant over all valid possibilities. Thus, we + * maintain the current state of that invariance. We + * start everything off at MAGIC to indicate that it + * hasn't been set up yet. + */ + mrow = sc->mrows; + mrow1 = sc->mrows + len; + mrow2 = sc->mrows + 2*len; + trow = sc->trows; + trow1 = sc->trows + len; + trow2 = sc->trows + 2*len; + memset(mrow, MAGIC, 3*len); + + /* + * And iterate over all possibilities. + */ + while (1) { + int p, valid; + + /* + * See if this possibility is valid. The only way + * it can fail to be valid is if it contains two + * adjacent tents. (Other forms of invalidity, such + * as containing a tent adjacent to one already + * placed, will have been dealt with already by + * other parts of the solver.) + */ + valid = TRUE; + for (j = 0; j+1 < n; j++) + if (sc->place[j] == TENT && + sc->place[j+1] == TENT && + sc->locs[j+1] == sc->locs[j]+1) { + valid = FALSE; + break; + } + + if (valid) { + /* + * Merge this valid combination into mrow. + */ + memset(trow, MAGIC, len); + memset(trow+len, BLANK, 2*len); + for (j = 0; j < n; j++) { + trow[sc->locs[j]] = sc->place[j]; + if (sc->place[j] == TENT) { + int jj; + for (jj = sc->locs[j]-1; jj <= sc->locs[j]+1; jj++) + if (jj >= 0 && jj < len) + trow1[jj] = trow2[jj] = NONTENT; + } + } + + for (j = 0; j < 3*len; j++) { + if (trow[j] == MAGIC) + continue; + if (mrow[j] == MAGIC || mrow[j] == trow[j]) { + /* + * Either this is the first valid + * placement we've found at all, or + * this square's contents are + * consistent with every previous valid + * combination. + */ + mrow[j] = trow[j]; + } else { + /* + * This square's contents fail to match + * what they were in a different + * combination, so we cannot deduce + * anything about this square. + */ + mrow[j] = BLANK; + } + } + } + + /* + * Find the next combination of k choices from n. + * We do this by finding the rightmost tent which + * can be moved one place right, doing so, and + * shunting all tents to the right of that as far + * left as they can go. + */ + p = 0; + for (j = n-1; j > 0; j--) { + if (sc->place[j] == TENT) + p++; + if (sc->place[j] == NONTENT && sc->place[j-1] == TENT) { + sc->place[j-1] = NONTENT; + sc->place[j] = TENT; + while (p--) + sc->place[++j] = TENT; + while (++j < n) + sc->place[j] = NONTENT; + break; + } + } + if (j <= 0) + break; /* we've finished */ + } + + /* + * It's just possible that _no_ placement was valid, in + * which case we have an internally inconsistent + * puzzle. + */ + if (mrow[sc->locs[0]] == MAGIC) + return 0; /* inconsistent */ + + /* + * Now go through mrow and see if there's anything + * we've deduced which wasn't already mentioned in soln. + */ + for (j = 0; j < len; j++) { + int whichrow; + + for (whichrow = 0; whichrow < 3; whichrow++) { + char *mthis = mrow + whichrow * len; + int tstart = (whichrow == 0 ? start : + whichrow == 1 ? start1 : start2); + if (tstart >= 0 && + mthis[j] != MAGIC && mthis[j] != BLANK && + soln[tstart+j*step] == BLANK) { + int pos = tstart+j*step; + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%s %d forces %s at %d,%d\n", + step==1 ? "row" : "column", + step==1 ? start/w : start, + mrow[j] == TENT ? "tent" : "non-tent", + pos % w, pos / w); +#endif + soln[pos] = mthis[j]; + done_something = TRUE; + } + } + } + } + + if (done_something) + continue; + + if (!done_something) + break; + } + + /* + * The solver has nothing further it can do. Return 1 if both + * soln and sc->links are completely filled in, or 2 otherwise. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + if (soln[y*w+x] == BLANK) + return 2; + if (soln[y*w+x] != NONTENT && sc->links[y*w+x] == 0) + return 2; + } + + return 1; +} + +static char *new_game_desc(game_params *params, random_state *rs, + char **aux, int interactive) +{ + int w = params->w, h = params->h; + int ntrees = w * h / 5; + char *grid = snewn(w*h, char); + char *puzzle = snewn(w*h, char); + int *numbers = snewn(w+h, int); + char *soln = snewn(w*h, char); + int *temp = snewn(2*w*h, int), *itemp = temp + w*h; + int maxedges = ntrees*4 + w*h; + int *edges = snewn(2*maxedges, int); + int *capacity = snewn(maxedges, int); + int *flow = snewn(maxedges, int); + struct solver_scratch *sc = new_scratch(w, h); + char *ret, *p; + int i, j, nedges; + + /* + * Since this puzzle has many global deductions and doesn't + * permit limited clue sets, generating grids for this puzzle + * is hard enough that I see no better option than to simply + * generate a solution and see if it's unique and has the + * required difficulty. This turns out to be computationally + * plausible as well. + * + * We chose our tree count (hence also tent count) by dividing + * the total grid area by five above. Why five? Well, w*h/4 is + * the maximum number of tents you can _possibly_ fit into the + * grid without violating the separation criterion, and to + * achieve that you are constrained to a very small set of + * possible layouts (the obvious one with a tent at every + * (even,even) coordinate, and trivial variations thereon). So + * if we reduce the tent count a bit more, we enable more + * random-looking placement; 5 turns out to be a plausible + * figure which yields sensible puzzles. Increasing the tent + * count would give puzzles whose solutions were too regimented + * and could be solved by the use of that knowledge (and would + * also take longer to find a viable placement); decreasing it + * would make the grids emptier and more boring. + * + * Actually generating a grid is a matter of first placing the + * tents, and then placing the trees by the use of maxflow + * (finding a distinct square adjacent to every tent). We do it + * this way round because otherwise satisfying the tent + * separation condition would become onerous: most randomly + * chosen tent layouts do not satisfy this condition, so we'd + * have gone to a lot of work before finding that a candidate + * layout was unusable. Instead, we place the tents first and + * ensure they meet the separation criterion _before_ doing + * lots of computation; this works much better. + * + * The maxflow algorithm is not randomised, so employed naively + * it would give rise to grids with clear structure and + * directional bias. Hence, I assign the network nodes as seen + * by maxflow to be a _random_ permutation the squares of the + * grid, so that any bias shown by maxflow towards low-numbered + * nodes is turned into a random bias. + * + * This generation strategy can fail at many points, including + * as early as tent placement (if you get a bad random order in + * which to greedily try the grid squares, you won't even + * manage to find enough mutually non-adjacent squares to put + * the tents in). Then it can fail if maxflow doesn't manage to + * find a good enough matching (i.e. the tent placements don't + * admit any adequate tree placements); and finally it can fail + * if the solver finds that the problem has the wrong + * difficulty (including being actually non-unique). All of + * these, however, are insufficiently frequent to cause + * trouble. + */ + + while (1) { + /* + * Arrange the grid squares into a random order, and invert + * that order so we can find a square's index as well. + */ + for (i = 0; i < w*h; i++) + temp[i] = i; + shuffle(temp, w*h, sizeof(*temp), rs); + for (i = 0; i < w*h; i++) + itemp[temp[i]] = i; + + /* + * The first `ntrees' entries in temp which we can get + * without making two tents adjacent will be the tent + * locations. + */ + memset(grid, BLANK, w*h); + j = ntrees; + for (i = 0; i < w*h && j > 0; i++) { + int x = temp[i] % w, y = temp[i] / w; + int dy, dx, ok = TRUE; + + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) + if (x+dx >= 0 && x+dx < w && + y+dy >= 0 && y+dy < h && + grid[(y+dy)*w+(x+dx)] == TENT) + ok = FALSE; + + if (ok) { + grid[temp[i]] = TENT; + j--; + } + } + if (j > 0) + continue; /* couldn't place all the tents */ + + /* + * Now we build up the list of graph edges. + */ + nedges = 0; + for (i = 0; i < w*h; i++) { + if (grid[temp[i]] == TENT) { + for (j = 0; j < w*h; j++) { + if (grid[temp[j]] != TENT) { + int xi = temp[i] % w, yi = temp[i] / w; + int xj = temp[j] % w, yj = temp[j] / w; + if (abs(xi-xj) + abs(yi-yj) == 1) { + edges[nedges*2] = i; + edges[nedges*2+1] = j; + capacity[nedges] = 1; + nedges++; + } + } + } + } else { + /* + * Special node w*h is the sink node; any non-tent node + * has an edge going to it. + */ + edges[nedges*2] = i; + edges[nedges*2+1] = w*h; + capacity[nedges] = 1; + nedges++; + } + } + + /* + * Special node w*h+1 is the source node, with an edge going to + * every tent. + */ + for (i = 0; i < w*h; i++) { + if (grid[temp[i]] == TENT) { + edges[nedges*2] = w*h+1; + edges[nedges*2+1] = i; + capacity[nedges] = 1; + nedges++; + } + } + + assert(nedges <= maxedges); + + /* + * Now we're ready to call the maxflow algorithm to place the + * trees. + */ + j = maxflow(w*h+2, w*h+1, w*h, nedges, edges, capacity, flow, NULL); + + if (j < ntrees) + continue; /* couldn't place all the tents */ + + /* + * We've placed the trees. Now we need to work out _where_ + * we've placed them, which is a matter of reading back out + * from the `flow' array. + */ + for (i = 0; i < nedges; i++) { + if (edges[2*i] < w*h && edges[2*i+1] < w*h && flow[i] > 0) + grid[temp[edges[2*i+1]]] = TREE; + } + + /* + * I think it looks ugly if there isn't at least one of + * _something_ (tent or tree) in each row and each column + * of the grid. This doesn't give any information away + * since a completely empty row/column is instantly obvious + * from the clues (it has no trees and a zero). + */ + for (i = 0; i < w; i++) { + for (j = 0; j < h; j++) { + if (grid[j*w+i] != BLANK) + break; /* found something in this column */ + } + if (j == h) + break; /* found empty column */ + } + if (i < w) + continue; /* a column was empty */ + + for (j = 0; j < h; j++) { + for (i = 0; i < w; i++) { + if (grid[j*w+i] != BLANK) + break; /* found something in this row */ + } + if (i == w) + break; /* found empty row */ + } + if (j < h) + continue; /* a row was empty */ + + /* + * Now set up the numbers round the edge. + */ + for (i = 0; i < w; i++) { + int n = 0; + for (j = 0; j < h; j++) + if (grid[j*w+i] == TENT) + n++; + numbers[i] = n; + } + for (i = 0; i < h; i++) { + int n = 0; + for (j = 0; j < w; j++) + if (grid[i*w+j] == TENT) + n++; + numbers[w+i] = n; + } + + /* + * And now actually solve the puzzle, to see whether it's + * unique and has the required difficulty. + */ + for (i = 0; i < w*h; i++) + puzzle[i] = grid[i] == TREE ? TREE : BLANK; + i = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff-1); + j = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff); + + /* + * We expect solving with difficulty params->diff to have + * succeeded (otherwise the problem is too hard), and + * solving with diff-1 to have failed (otherwise it's too + * easy). + */ + if (i == 2 && j == 1) + break; + } + + /* + * That's it. Encode as a game ID. + */ + ret = snewn((w+h)*40 + ntrees + (w*h)/26 + 1, char); + p = ret; + j = 0; + for (i = 0; i <= w*h; i++) { + int c = (i < w*h ? grid[i] == TREE : 1); + if (c) { + *p++ = (j == 0 ? '_' : j-1 + 'a'); + j = 0; + } else { + j++; + while (j > 25) { + *p++ = 'z'; + j -= 25; + } + } + } + for (i = 0; i < w+h; i++) + p += sprintf(p, ",%d", numbers[i]); + *p++ = '\0'; + ret = sresize(ret, p - ret, char); + + /* + * And encode the solution as an aux_info. + */ + *aux = snewn(ntrees * 40, char); + p = *aux; + *p++ = 'S'; + for (i = 0; i < w*h; i++) + if (grid[i] == TENT) + p += sprintf(p, ";T%d,%d", i%w, i/w); + *p++ = '\0'; + *aux = sresize(*aux, p - *aux, char); + + free_scratch(sc); + sfree(flow); + sfree(capacity); + sfree(edges); + sfree(temp); + sfree(soln); + sfree(numbers); + sfree(puzzle); + sfree(grid); + + return ret; +} + +static char *validate_desc(game_params *params, char *desc) +{ + int w = params->w, h = params->h; + int area, i; + + area = 0; + while (*desc && *desc != ',') { + if (*desc == '_') + area++; + else if (*desc >= 'a' && *desc < 'z') + area += *desc - 'a' + 2; + else if (*desc == 'z') + area += 25; + else if (*desc == '!' || *desc == '-') + /* do nothing */; + else + return "Invalid character in grid specification"; + + desc++; + } + + for (i = 0; i < w+h; i++) { + if (!*desc) + return "Not enough numbers given after grid specification"; + else if (*desc != ',') + return "Invalid character in number list"; + desc++; + while (*desc && isdigit((unsigned char)*desc)) desc++; + } + + if (*desc) + return "Unexpected additional data at end of game description"; + return NULL; +} + +static game_state *new_game(midend *me, game_params *params, char *desc) +{ + int w = params->w, h = params->h; + game_state *state = snew(game_state); + int i; + + state->p = *params; /* structure copy */ + state->grid = snewn(w*h, char); + state->numbers = snew(struct numbers); + state->numbers->refcount = 1; + state->numbers->numbers = snewn(w+h, int); + state->completed = state->used_solve = FALSE; + + i = 0; + memset(state->grid, BLANK, w*h); + + while (*desc) { + int run, type; + + type = TREE; + + if (*desc == '_') + run = 0; + else if (*desc >= 'a' && *desc < 'z') + run = *desc - ('a'-1); + else if (*desc == 'z') { + run = 25; + type = BLANK; + } else { + assert(*desc == '!' || *desc == '-'); + run = -1; + type = (*desc == '!' ? TENT : NONTENT); + } + + desc++; + + i += run; + assert(i >= 0 && i <= w*h); + if (i == w*h) { + assert(type == TREE); + break; + } else { + if (type != BLANK) + state->grid[i++] = type; + } + } + + for (i = 0; i < w+h; i++) { + assert(*desc == ','); + desc++; + state->numbers->numbers[i] = atoi(desc); + while (*desc && isdigit((unsigned char)*desc)) desc++; + } + + assert(!*desc); + + return state; +} + +static game_state *dup_game(game_state *state) +{ + int w = state->p.w, h = state->p.h; + game_state *ret = snew(game_state); + + ret->p = state->p; /* structure copy */ + ret->grid = snewn(w*h, char); + memcpy(ret->grid, state->grid, w*h); + ret->numbers = state->numbers; + state->numbers->refcount++; + ret->completed = state->completed; + ret->used_solve = state->used_solve; + + return ret; +} + +static void free_game(game_state *state) +{ + if (--state->numbers->refcount <= 0) { + sfree(state->numbers->numbers); + sfree(state->numbers); + } + sfree(state->grid); + sfree(state); +} + +static char *solve_game(game_state *state, game_state *currstate, + char *aux, char **error) +{ + int w = state->p.w, h = state->p.h; + + if (aux) { + /* + * If we already have the solution, save ourselves some + * time. + */ + return dupstr(aux); + } else { + struct solver_scratch *sc = new_scratch(w, h); + char *soln; + int ret; + char *move, *p; + int i; + + soln = snewn(w*h, char); + ret = tents_solve(w, h, state->grid, state->numbers->numbers, + soln, sc, DIFFCOUNT-1); + free_scratch(sc); + if (ret != 1) { + sfree(soln); + if (ret == 0) + *error = "This puzzle is not self-consistent"; + else + *error = "Unable to find a unique solution for this puzzle"; + return NULL; + } + + /* + * Construct a move string which turns the current state + * into the solved state. + */ + move = snewn(w*h * 40, char); + p = move; + *p++ = 'S'; + for (i = 0; i < w*h; i++) + if (soln[i] == TENT) + p += sprintf(p, ";T%d,%d", i%w, i/w); + *p++ = '\0'; + move = sresize(move, p - move, char); + + sfree(soln); + + return move; + } +} + +static char *game_text_format(game_state *state) +{ + int w = state->p.w, h = state->p.h; + char *ret, *p; + int x, y; + + /* + * FIXME: We currently do not print the numbers round the edges + * of the grid. I need to work out a sensible way of doing this + * even when the column numbers exceed 9. + * + * In the absence of those numbers, the result size is h lines + * of w+1 characters each, plus a NUL. + * + * This function is currently only used by the standalone + * solver; until I make it look more sensible, I won't enable + * it in the main game structure. + */ + ret = snewn(h*(w+1) + 1, char); + p = ret; + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + *p = (state->grid[y*w+x] == BLANK ? '.' : + state->grid[y*w+x] == TREE ? 'T' : + state->grid[y*w+x] == TENT ? '*' : + state->grid[y*w+x] == NONTENT ? '-' : '?'); + p++; + } + *p++ = '\n'; + } + *p++ = '\0'; + + return ret; +} + +static game_ui *new_ui(game_state *state) +{ + return NULL; +} + +static void free_ui(game_ui *ui) +{ +} + +static char *encode_ui(game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, char *encoding) +{ +} + +static void game_changed_state(game_ui *ui, game_state *oldstate, + game_state *newstate) +{ +} + +struct game_drawstate { + int tilesize; + int started; + game_params p; + char *drawn; +}; + +#define PREFERRED_TILESIZE 32 +#define TILESIZE (ds->tilesize) +#define TLBORDER (TILESIZE/2) +#define BRBORDER (TILESIZE*3/2) +#define COORD(x) ( (x) * TILESIZE + TLBORDER ) +#define FROMCOORD(x) ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 ) + +#define FLASH_TIME 0.30F + +static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, + int x, int y, int button) +{ + int w = state->p.w, h = state->p.h; + + if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { + int v; + char buf[80]; + + x = FROMCOORD(x); + y = FROMCOORD(y); + if (x < 0 || y < 0 || x >= w || y >= h) + return NULL; + + if (state->grid[y*w+x] == TREE) + return NULL; + + if (button == LEFT_BUTTON) { + v = (state->grid[y*w+x] == BLANK ? TENT : BLANK); + } else { + v = (state->grid[y*w+x] == BLANK ? NONTENT : BLANK); + } + + sprintf(buf, "%c%d,%d", (int)(v==BLANK ? 'B' : + v==TENT ? 'T' : 'N'), x, y); + return dupstr(buf); + } + + return NULL; +} + +static game_state *execute_move(game_state *state, char *move) +{ + int w = state->p.w, h = state->p.h; + char c; + int x, y, m, n, i, j; + game_state *ret = dup_game(state); + + while (*move) { + c = *move; + if (c == 'S') { + int i; + ret->used_solve = TRUE; + /* + * Set all non-tree squares to NONTENT. The rest of the + * solve move will fill the tents in over the top. + */ + for (i = 0; i < w*h; i++) + if (ret->grid[i] != TREE) + ret->grid[i] = NONTENT; + move++; + } else if (c == 'B' || c == 'T' || c == 'N') { + move++; + if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || + x < 0 || y < 0 || x >= w || y >= h) { + free_game(ret); + return NULL; + } + if (ret->grid[y*w+x] == TREE) { + free_game(ret); + return NULL; + } + ret->grid[y*w+x] = (c == 'B' ? BLANK : c == 'T' ? TENT : NONTENT); + move += n; + } else { + free_game(ret); + return NULL; + } + if (*move == ';') + move++; + else if (*move) { + free_game(ret); + return NULL; + } + } + + /* + * Check for completion. + */ + for (i = n = m = 0; i < w*h; i++) { + if (ret->grid[i] == TENT) + n++; + else if (ret->grid[i] == TREE) + m++; + } + if (n == m) { + int nedges, maxedges, *edges, *capacity, *flow; + + /* + * We have the right number of tents, which is a + * precondition for the game being complete. Now check that + * the numbers add up. + */ + for (i = 0; i < w; i++) { + n = 0; + for (j = 0; j < h; j++) + if (ret->grid[j*w+i] == TENT) + n++; + if (ret->numbers->numbers[i] != n) + goto completion_check_done; + } + for (i = 0; i < h; i++) { + n = 0; + for (j = 0; j < w; j++) + if (ret->grid[i*w+j] == TENT) + n++; + if (ret->numbers->numbers[w+i] != n) + goto completion_check_done; + } + /* + * Also, check that no two tents are adjacent. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + if (x+1 < w && + ret->grid[y*w+x] == TENT && ret->grid[y*w+x+1] == TENT) + goto completion_check_done; + if (y+1 < h && + ret->grid[y*w+x] == TENT && ret->grid[(y+1)*w+x] == TENT) + goto completion_check_done; + if (x+1 < w && y+1 < h) { + if (ret->grid[y*w+x] == TENT && + ret->grid[(y+1)*w+(x+1)] == TENT) + goto completion_check_done; + if (ret->grid[(y+1)*w+x] == TENT && + ret->grid[y*w+(x+1)] == TENT) + goto completion_check_done; + } + } + + /* + * OK; we have the right number of tents, they match the + * numeric clues, and they satisfy the non-adjacency + * criterion. Finally, we need to verify that they can be + * placed in a one-to-one matching with the trees such that + * every tent is orthogonally adjacent to its tree. + * + * This bit is where the hard work comes in: we have to do + * it by finding such a matching using maxflow. + * + * So we construct a network with one special source node, + * one special sink node, one node per tent, and one node + * per tree. + */ + maxedges = 6 * m; + edges = snewn(2 * maxedges, int); + capacity = snewn(maxedges, int); + flow = snewn(maxedges, int); + nedges = 0; + /* + * Node numbering: + * + * 0..w*h trees/tents + * w*h source + * w*h+1 sink + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + if (ret->grid[y*w+x] == TREE) { + int d; + + /* + * Here we use the direction enum declared for + * the solver. We make use of the fact that the + * directions are declared in the order + * U,L,R,D, meaning that we go through the four + * neighbours of any square in numerically + * increasing order. + */ + for (d = 1; d < MAXDIR; d++) { + int x2 = x + dx(d), y2 = y + dy(d); + if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && + ret->grid[y2*w+x2] == TENT) { + assert(nedges < maxedges); + edges[nedges*2] = y*w+x; + edges[nedges*2+1] = y2*w+x2; + capacity[nedges] = 1; + nedges++; + } + } + } else if (ret->grid[y*w+x] == TENT) { + assert(nedges < maxedges); + edges[nedges*2] = y*w+x; + edges[nedges*2+1] = w*h+1; /* edge going to sink */ + capacity[nedges] = 1; + nedges++; + } + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + if (ret->grid[y*w+x] == TREE) { + assert(nedges < maxedges); + edges[nedges*2] = w*h; /* edge coming from source */ + edges[nedges*2+1] = y*w+x; + capacity[nedges] = 1; + nedges++; + } + n = maxflow(w*h+2, w*h, w*h+1, nedges, edges, capacity, flow, NULL); + + sfree(flow); + sfree(capacity); + sfree(edges); + + if (n != m) + goto completion_check_done; + + /* + * We haven't managed to fault the grid on any count. Score! + */ + ret->completed = TRUE; + } + completion_check_done: + + return ret; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_compute_size(game_params *params, int tilesize, + int *x, int *y) +{ + /* fool the macros */ + struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy; + + *x = TLBORDER + BRBORDER + TILESIZE * params->w; + *y = TLBORDER + BRBORDER + TILESIZE * params->h; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, game_state *state, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + ret[COL_GRID * 3 + 0] = 0.0F; + ret[COL_GRID * 3 + 1] = 0.0F; + ret[COL_GRID * 3 + 2] = 0.0F; + + ret[COL_GRASS * 3 + 0] = 0.7F; + ret[COL_GRASS * 3 + 1] = 1.0F; + ret[COL_GRASS * 3 + 2] = 0.5F; + + ret[COL_TREETRUNK * 3 + 0] = 0.6F; + ret[COL_TREETRUNK * 3 + 1] = 0.4F; + ret[COL_TREETRUNK * 3 + 2] = 0.0F; + + ret[COL_TREELEAF * 3 + 0] = 0.0F; + ret[COL_TREELEAF * 3 + 1] = 0.7F; + ret[COL_TREELEAF * 3 + 2] = 0.0F; + + ret[COL_TENT * 3 + 0] = 0.8F; + ret[COL_TENT * 3 + 1] = 0.7F; + ret[COL_TENT * 3 + 2] = 0.0F; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +{ + int w = state->p.w, h = state->p.h; + struct game_drawstate *ds = snew(struct game_drawstate); + + ds->tilesize = 0; + ds->started = FALSE; + ds->p = state->p; /* structure copy */ + ds->drawn = snewn(w*h, char); + memset(ds->drawn, MAGIC, w*h); + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->drawn); + sfree(ds); +} + +static void draw_tile(drawing *dr, game_drawstate *ds, + int x, int y, int v, int printing) +{ + int tx = COORD(x), ty = COORD(y); + int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2; + + clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1); + + if (!printing) + draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, + (v == BLANK ? COL_BACKGROUND : COL_GRASS)); + + if (v == TREE) { + int i; + + (printing ? draw_rect_outline : draw_rect) + (dr, cx-TILESIZE/15, ty+TILESIZE*3/10, + 2*(TILESIZE/15)+1, (TILESIZE*9/10 - TILESIZE*3/10), + COL_TREETRUNK); + + for (i = 0; i < (printing ? 2 : 1); i++) { + int col = (i == 1 ? COL_BACKGROUND : COL_TREELEAF); + int sub = i * (TILESIZE/32); + draw_circle(dr, cx, ty+TILESIZE*4/10, TILESIZE/4 - sub, + col, col); + draw_circle(dr, cx+TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub, + col, col); + draw_circle(dr, cx-TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub, + col, col); + draw_circle(dr, cx+TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub, + col, col); + draw_circle(dr, cx-TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub, + col, col); + } + } else if (v == TENT) { + int coords[6]; + coords[0] = cx - TILESIZE/3; + coords[1] = cy + TILESIZE/3; + coords[2] = cx + TILESIZE/3; + coords[3] = cy + TILESIZE/3; + coords[4] = cx; + coords[5] = cy - TILESIZE/3; + draw_polygon(dr, coords, 3, (printing ? -1 : COL_TENT), COL_TENT); + } + + unclip(dr); + draw_update(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1); +} + +/* + * Internal redraw function, used for printing as well as drawing. + */ +static void int_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, + game_state *state, int dir, game_ui *ui, + float animtime, float flashtime, int printing) +{ + int w = state->p.w, h = state->p.h; + int x, y, flashing; + + if (printing || !ds->started) { + if (!printing) { + int ww, wh; + game_compute_size(&state->p, TILESIZE, &ww, &wh); + draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND); + draw_update(dr, 0, 0, ww, wh); + ds->started = TRUE; + } + + if (printing) + print_line_width(dr, TILESIZE/64); + + /* + * Draw the grid. + */ + for (y = 0; y <= h; y++) + draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), COL_GRID); + for (x = 0; x <= w; x++) + draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), COL_GRID); + + /* + * Draw the numbers. + */ + for (y = 0; y < h; y++) { + char buf[80]; + sprintf(buf, "%d", state->numbers->numbers[y+w]); + draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2, + FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE, + COL_GRID, buf); + } + for (x = 0; x < w; x++) { + char buf[80]; + sprintf(buf, "%d", state->numbers->numbers[x]); + draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1), + FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL, + COL_GRID, buf); + } + } + + if (flashtime > 0) + flashing = (int)(flashtime * 3 / FLASH_TIME) != 1; + else + flashing = FALSE; + + /* + * Draw the grid. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int v = state->grid[y*w+x]; + + if (flashing && (v == TREE || v == TENT)) + v = NONTENT; + + if (printing || ds->drawn[y*w+x] != v) { + draw_tile(dr, ds, x, y, v, printing); + if (!printing) + ds->drawn[y*w+x] = v; + } + } +} + +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, + game_state *state, int dir, game_ui *ui, + float animtime, float flashtime) +{ + int_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, FALSE); +} + +static float game_anim_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + if (!oldstate->completed && newstate->completed && + !oldstate->used_solve && !newstate->used_solve) + return FLASH_TIME; + + return 0.0F; +} + +static int game_wants_statusbar(void) +{ + return FALSE; +} + +static int game_timing_state(game_state *state, game_ui *ui) +{ + return TRUE; +} + +static void game_print_size(game_params *params, float *x, float *y) +{ + int pw, ph; + + /* + * I'll use 6mm squares by default. + */ + game_compute_size(params, 600, &pw, &ph); + *x = pw / 100.0; + *y = ph / 100.0; +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ + int c; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(dr, ds, NULL, tilesize); + + c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND); + c = print_mono_colour(dr, 0); assert(c == COL_GRID); + c = print_mono_colour(dr, 1); assert(c == COL_GRASS); + c = print_mono_colour(dr, 0); assert(c == COL_TREETRUNK); + c = print_mono_colour(dr, 0); assert(c == COL_TREELEAF); + c = print_mono_colour(dr, 0); assert(c == COL_TENT); + + int_redraw(dr, ds, NULL, state, +1, NULL, 0.0F, 0.0F, TRUE); +} + +#ifdef COMBINED +#define thegame tents +#endif + +const struct game thegame = { + "Tents", "games.tents", + default_params, + game_fetch_preset, + decode_params, + encode_params, + free_params, + dup_params, + TRUE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + TRUE, solve_game, + FALSE, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + PREFERRED_TILESIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + TRUE, FALSE, game_print_size, game_print, + game_wants_statusbar, + FALSE, game_timing_state, + 0, /* mouse_priorities */ +}; + +#ifdef STANDALONE_SOLVER + +#include + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s, *s2; + char *id = NULL, *desc, *err; + int grade = FALSE; + int ret, diff, really_verbose = FALSE; + struct solver_scratch *sc; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + really_verbose = TRUE; + } else if (!strcmp(p, "-g")) { + grade = TRUE; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-g | -v] \n", argv[0]); + return 1; + } + + desc = strchr(id, ':'); + if (!desc) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(NULL, p, desc); + s2 = new_game(NULL, p, desc); + + sc = new_scratch(p->w, p->h); + + /* + * When solving an Easy puzzle, we don't want to bother the + * user with Hard-level deductions. For this reason, we grade + * the puzzle internally before doing anything else. + */ + ret = -1; /* placate optimiser */ + for (diff = 0; diff < DIFFCOUNT; diff++) { + ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers, + s2->grid, sc, diff); + if (ret < 2) + break; + } + + if (diff == DIFFCOUNT) { + if (grade) + printf("Difficulty rating: too hard to solve internally\n"); + else + printf("Unable to find a unique solution\n"); + } else { + if (grade) { + if (ret == 0) + printf("Difficulty rating: impossible (no solution exists)\n"); + else if (ret == 1) + printf("Difficulty rating: %s\n", tents_diffnames[diff]); + } else { + verbose = really_verbose; + ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers, + s2->grid, sc, diff); + if (ret == 0) + printf("Puzzle is inconsistent\n"); + else + fputs(game_text_format(s2), stdout); + } + } + + return 0; +} + +#endif -- 2.11.0