ref: 669bb81f084191d0163de43c8e1631e30d913b00
parent: 29afca3ef95151bfeb35555ff192836d472370ad
author: Simon Tatham <anakin@pobox.com>
date: Thu Oct 13 14:30:24 EDT 2005
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! :-) [originally from svn r6390]
--- a/Recipe
+++ b/Recipe
@@ -26,10 +26,11 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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
--- a/gtk.c
+++ b/gtk.c
@@ -290,6 +290,8 @@
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 @@
&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
--- a/list.c
+++ b/list.c
@@ -37,6 +37,7 @@
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 @@
&sixteen,
&slant,
&solo,
+ &tents,
&twiddle,
&untangle,
};
--- /dev/null
+++ b/maxflow.c
@@ -1,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 <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#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
--- /dev/null
+++ b/maxflow.h
@@ -1,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 */
--- a/osx.m
+++ b/osx.m
@@ -1341,6 +1341,8 @@
point.x -= size.width / 2;
if (align & ALIGN_VCENTRE)
point.y -= size.height / 2;
+ else
+ point.y -= size.height;
[string drawAtPoint:point withAttributes:attr];
}
--- a/puzzles.but
+++ b/puzzles.but
@@ -1802,6 +1802,58 @@
\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.--- /dev/null
+++ b/tents.c
@@ -1,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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#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 <stdarg.h>
+
+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] <game_id>\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