ref: 1470c9530b1cff33d11170b9b891d94be62c4194
dir: /tents.c/
/* * tents.c: Puzzle involving placing tents next to trees subject to * some confusing conditions. * * TODO: * * - 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 <limits.h> #include <math.h> #include "puzzles.h" #include "matching.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 static bool 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, COL_ERROR, COL_ERRTEXT, COL_ERRTRUNK, 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; bool 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 bool 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(const 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(const game_params *params, bool 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(const 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].u.string.sval = dupstr(buf); ret[1].name = "Height"; ret[1].type = C_STRING; sprintf(buf, "%d", params->h); ret[1].u.string.sval = dupstr(buf); ret[2].name = "Difficulty"; ret[2].type = C_CHOICES; ret[2].u.choices.choicenames = DIFFCONFIG; ret[2].u.choices.selected = params->diff; ret[3].name = NULL; ret[3].type = C_END; return ret; } static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); ret->w = atoi(cfg[0].u.string.sval); ret->h = atoi(cfg[1].u.string.sval); ret->diff = cfg[2].u.choices.selected; return ret; } static const char *validate_params(const game_params *params, bool full) { /* * Generating anything under 4x4 runs into trouble of one kind * or another. */ if (params->w < 4 || params->h < 4) return "Width and height must both be at least four"; if (params->w > (INT_MAX - 1) / params->h) return "Width times height must not be unreasonably large"; 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, *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) { bool 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) { bool 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; bool 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; 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; bool 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, mthis[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(const game_params *params_in, random_state *rs, char **aux, bool interactive) { game_params params_copy = *params_in; /* structure copy */ game_params *params = ¶ms_copy; 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 *order = snewn(w*h, int); int *treemap = snewn(w*h, int); int maxedges = ntrees*4 + w*h; int *adjdata = snewn(maxedges, int); int **adjlists = snewn(ntrees, int *); int *adjsizes = snewn(ntrees, int); int *outr = snewn(4*ntrees, int); struct solver_scratch *sc = new_scratch(w, h); char *ret, *p; int i, j, nl, nr; int *adjptr; /* * 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 matching.c * (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. * * 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 matching.c 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. */ if (params->diff > DIFF_EASY && params->w <= 4 && params->h <= 4) params->diff = DIFF_EASY; /* downgrade to prevent tight loop */ while (1) { /* * Make a list of grid squares which we'll permute as we pick * the tent locations. * * We'll also need to index all the potential tree squares, * i.e. the ones adjacent to the tents. */ for (i = 0; i < w*h; i++) { order[i] = i; treemap[i] = -1; } /* * Place tents at random without making any two adjacent. */ memset(grid, BLANK, w*h); j = ntrees; nr = 0; /* Loop end condition: either j==0 (we've placed all the * tents), or the number of grid squares we have yet to try * is too few to fit the remaining tents into. */ for (i = 0; j > 0 && i+j <= w*h; i++) { int which, x, y, d, tmp; int dy, dx; bool ok = true; which = i + random_upto(rs, w*h - i); tmp = order[which]; order[which] = order[i]; order[i] = tmp; x = order[i] % w; y = order[i] / w; 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[order[i]] = TENT; for (d = 1; d < MAXDIR; d++) { int x2 = x + dx(d), y2 = y + dy(d); if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h && treemap[y2*w+x2] == -1) { treemap[y2*w+x2] = nr++; } } j--; } } if (j > 0) continue; /* couldn't place all the tents */ /* * Build up the graph for matching.c. */ adjptr = adjdata; nl = 0; for (i = 0; i < w*h; i++) { if (grid[i] == TENT) { int d, x = i % w, y = i / w; adjlists[nl] = adjptr; for (d = 1; d < MAXDIR; d++) { int x2 = x + dx(d), y2 = y + dy(d); if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h) { assert(treemap[y2*w+x2] != -1); *adjptr++ = treemap[y2*w+x2]; } } adjsizes[nl] = adjptr - adjlists[nl]; nl++; } } /* * Call the matching algorithm to actually place the trees. */ j = matching(ntrees, nr, adjlists, adjsizes, rs, NULL, outr); if (j < ntrees) continue; /* couldn't place all the trees */ /* * Fill in the trees in the grid, by cross-referencing treemap * (which maps a grid square to its index as known to * matching()) against the output from matching(). * * Note that for these purposes we don't actually care _which_ * tent each potential tree square is assigned to - we only * care whether it was assigned to any tent at all, in order * to decide whether to put a tree in it. */ for (i = 0; i < w*h; i++) if (treemap[i] != -1 && outr[treemap[i]] != -1) grid[i] = 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++) { bool c = (i < w*h ? grid[i] == TREE : true); 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(outr); sfree(adjdata); sfree(adjlists); sfree(adjsizes); sfree(treemap); sfree(order); sfree(soln); sfree(numbers); sfree(puzzle); sfree(grid); return ret; } /* * Grid description format: * * _ = tree * a = 1 BLANK then TREE * ... * y = 25 BLANKs then TREE * z = 25 BLANKs * ! = set previous square to TENT * - = set previous square to NONTENT * * Last character must be one that would insert a tree as the first * square after the grid. */ static const char *validate_desc(const game_params *params, const 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 == '-') { if (area == 0 || area > w * h) return "Tent or non-tent placed off the grid"; } else return "Invalid character in grid specification"; desc++; } if (area < w * h + 1) return "Not enough data to fill grid"; else if (area > w * h + 1) return "Too much data to fill grid"; 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, const game_params *params, const 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(const 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(const game_state *state, const game_state *currstate, const char *aux, const 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 bool game_can_format_as_text_now(const game_params *params) { return params->w <= 1998 && params->h <= 1998; /* 999 tents */ } static char *game_text_format(const game_state *state) { int w = state->p.w, h = state->p.h, r, c; int cw = 4, ch = 2, gw = (w+1)*cw + 2, gh = (h+1)*ch + 1, len = gw * gh; char *board = snewn(len + 1, char); sprintf(board, "%*s\n", len - 2, ""); for (r = 0; r <= h; ++r) { for (c = 0; c <= w; ++c) { int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2; int i = r*w + c, n = 1000; if (r == h && c == w) /* NOP */; else if (c == w) n = state->numbers->numbers[w + r]; else if (r == h) n = state->numbers->numbers[c]; else switch (state->grid[i]) { case BLANK: board[center] = '.'; break; case TREE: board[center] = 'T'; break; case TENT: memcpy(board + center - 1, "//\\", 3); break; case NONTENT: break; default: memcpy(board + center - 1, "wtf", 3); } if (n < 100) { board[center] = '0' + n % 10; if (n >= 10) board[center - 1] = '0' + n / 10; } else if (n < 1000) { board[center + 1] = '0' + n % 10; board[center] = '0' + n / 10 % 10; board[center - 1] = '0' + n / 100; } board[cell] = '+'; memset(board + cell + 1, '-', cw - 1); for (i = 1; i < ch; ++i) board[cell + i*gw] = '|'; } for (c = 0; c < ch; ++c) { board[(r*ch+c)*gw + gw - 2] = c == 0 ? '+' : r < h ? '|' : ' '; board[(r*ch+c)*gw + gw - 1] = '\n'; } } memset(board + len - gw, '-', gw - 2 - cw); for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+'; return board; } struct game_ui { int dsx, dsy; /* coords of drag start */ int dex, dey; /* coords of drag end */ int drag_button; /* -1 for none, or a button code */ bool drag_ok; /* dragged off the window, to cancel */ int cx, cy; /* cursor position. */ bool cdisp; /* is cursor displayed? */ }; static game_ui *new_ui(const game_state *state) { game_ui *ui = snew(game_ui); ui->dsx = ui->dsy = -1; ui->dex = ui->dey = -1; ui->drag_button = -1; ui->drag_ok = false; ui->cx = ui->cy = 0; ui->cdisp = false; return ui; } static void free_ui(game_ui *ui) { sfree(ui); } static char *encode_ui(const game_ui *ui) { return NULL; } static void decode_ui(game_ui *ui, const char *encoding) { } static void game_changed_state(game_ui *ui, const game_state *oldstate, const game_state *newstate) { } static const char *current_key_label(const game_ui *ui, const game_state *state, int button) { int w = state->p.w; int v = state->grid[ui->cy*w+ui->cx]; if (IS_CURSOR_SELECT(button) && ui->cdisp) { switch (v) { case BLANK: return button == CURSOR_SELECT ? "Tent" : "Green"; case TENT: case NONTENT: return "Clear"; } } return ""; } struct game_drawstate { int tilesize; bool started; game_params p; int *drawn, *numbersdrawn; int cx, cy; /* last-drawn cursor pos, or (-1,-1) if absent. */ }; #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 int drag_xform(const game_ui *ui, int x, int y, int v) { int xmin, ymin, xmax, ymax; xmin = min(ui->dsx, ui->dex); xmax = max(ui->dsx, ui->dex); ymin = min(ui->dsy, ui->dey); ymax = max(ui->dsy, ui->dey); #ifndef STYLUS_BASED /* * Left-dragging has no effect, so we treat a left-drag as a * single click on dsx,dsy. */ if (ui->drag_button == LEFT_BUTTON) { xmin = xmax = ui->dsx; ymin = ymax = ui->dsy; } #endif if (x < xmin || x > xmax || y < ymin || y > ymax) return v; /* no change outside drag area */ if (v == TREE) return v; /* trees are inviolate always */ if (xmin == xmax && ymin == ymax) { /* * Results of a simple click. Left button sets blanks to * tents; right button sets blanks to non-tents; either * button clears a non-blank square. * If stylus-based however, it loops instead. */ if (ui->drag_button == LEFT_BUTTON) #ifdef STYLUS_BASED v = (v == BLANK ? TENT : (v == TENT ? NONTENT : BLANK)); else v = (v == BLANK ? NONTENT : (v == NONTENT ? TENT : BLANK)); #else v = (v == BLANK ? TENT : BLANK); else v = (v == BLANK ? NONTENT : BLANK); #endif } else { /* * Results of a drag. Left-dragging has no effect. * Right-dragging sets all blank squares to non-tents and * has no effect on anything else. */ if (ui->drag_button == RIGHT_BUTTON) v = (v == BLANK ? NONTENT : v); else #ifdef STYLUS_BASED v = (v == BLANK ? NONTENT : v); #else /* do nothing */; #endif } return v; } static char *interpret_move(const game_state *state, game_ui *ui, const game_drawstate *ds, int x, int y, int button) { int w = state->p.w, h = state->p.h; char tmpbuf[80]; bool shift = button & MOD_SHFT, control = button & MOD_CTRL; button &= ~MOD_MASK; if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { x = FROMCOORD(x); y = FROMCOORD(y); if (x < 0 || y < 0 || x >= w || y >= h) return NULL; ui->drag_button = button; ui->dsx = ui->dex = x; ui->dsy = ui->dey = y; ui->drag_ok = true; ui->cdisp = false; return UI_UPDATE; } if ((IS_MOUSE_DRAG(button) || IS_MOUSE_RELEASE(button)) && ui->drag_button > 0) { int xmin, ymin, xmax, ymax; char *buf; const char *sep; int buflen, bufsize, tmplen; x = FROMCOORD(x); y = FROMCOORD(y); if (x < 0 || y < 0 || x >= w || y >= h) { ui->drag_ok = false; } else { /* * Drags are limited to one row or column. Hence, we * work out which coordinate is closer to the drag * start, and move it _to_ the drag start. */ if (abs(x - ui->dsx) < abs(y - ui->dsy)) x = ui->dsx; else y = ui->dsy; ui->dex = x; ui->dey = y; ui->drag_ok = true; } if (IS_MOUSE_DRAG(button)) return UI_UPDATE; /* * The drag has been released. Enact it. */ if (!ui->drag_ok) { ui->drag_button = -1; return UI_UPDATE; /* drag was just cancelled */ } xmin = min(ui->dsx, ui->dex); xmax = max(ui->dsx, ui->dex); ymin = min(ui->dsy, ui->dey); ymax = max(ui->dsy, ui->dey); assert(0 <= xmin && xmin <= xmax && xmax < w); assert(0 <= ymin && ymin <= ymax && ymax < h); buflen = 0; bufsize = 256; buf = snewn(bufsize, char); sep = ""; for (y = ymin; y <= ymax; y++) for (x = xmin; x <= xmax; x++) { int v = drag_xform(ui, x, y, state->grid[y*w+x]); if (state->grid[y*w+x] != v) { tmplen = sprintf(tmpbuf, "%s%c%d,%d", sep, (int)(v == BLANK ? 'B' : v == TENT ? 'T' : 'N'), x, y); sep = ";"; if (buflen + tmplen >= bufsize) { bufsize = buflen + tmplen + 256; buf = sresize(buf, bufsize, char); } strcpy(buf+buflen, tmpbuf); buflen += tmplen; } } ui->drag_button = -1; /* drag is terminated */ if (buflen == 0) { sfree(buf); return UI_UPDATE; /* drag was terminated */ } else { buf[buflen] = '\0'; return buf; } } if (IS_CURSOR_MOVE(button)) { ui->cdisp = true; if (shift || control) { int len = 0, i, indices[2]; indices[0] = ui->cx + w * ui->cy; move_cursor(button, &ui->cx, &ui->cy, w, h, false); indices[1] = ui->cx + w * ui->cy; /* NONTENTify all unique traversed eligible squares */ for (i = 0; i <= (indices[0] != indices[1]); ++i) if (state->grid[indices[i]] == BLANK || (control && state->grid[indices[i]] == TENT)) { len += sprintf(tmpbuf + len, "%sN%d,%d", len ? ";" : "", indices[i] % w, indices[i] / w); assert(len < lenof(tmpbuf)); } tmpbuf[len] = '\0'; if (len) return dupstr(tmpbuf); } else move_cursor(button, &ui->cx, &ui->cy, w, h, false); return UI_UPDATE; } if (ui->cdisp) { char rep = 0; int v = state->grid[ui->cy*w+ui->cx]; if (v != TREE) { #ifdef SINGLE_CURSOR_SELECT if (button == CURSOR_SELECT) /* SELECT cycles T, N, B */ rep = v == BLANK ? 'T' : v == TENT ? 'N' : 'B'; #else if (button == CURSOR_SELECT) rep = v == BLANK ? 'T' : 'B'; else if (button == CURSOR_SELECT2) rep = v == BLANK ? 'N' : 'B'; else if (button == 'T' || button == 'N' || button == 'B') rep = (char)button; #endif } if (rep) { sprintf(tmpbuf, "%c%d,%d", (int)rep, ui->cx, ui->cy); return dupstr(tmpbuf); } } else if (IS_CURSOR_SELECT(button)) { ui->cdisp = true; return UI_UPDATE; } return NULL; } static game_state *execute_move(const game_state *state, const 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 *gridids, *adjdata, **adjlists, *adjsizes, *adjptr; /* * 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 matching.c. */ gridids = snewn(w*h, int); adjdata = snewn(m*4, int); adjlists = snewn(m, int *); adjsizes = snewn(m, int); /* Assign each tent and tree a consecutive vertex id for * matching(). */ for (i = n = 0; i < w*h; i++) { if (ret->grid[i] == TENT) gridids[i] = n++; } assert(n == m); for (i = n = 0; i < w*h; i++) { if (ret->grid[i] == TREE) gridids[i] = n++; } assert(n == m); /* Build the vertices' adjacency lists. */ adjptr = adjdata; for (y = 0; y < h; y++) for (x = 0; x < w; x++) if (ret->grid[y*w+x] == TREE) { int d, treeid = gridids[y*w+x]; adjlists[treeid] = adjptr; /* * 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) { *adjptr++ = gridids[y2*w+x2]; } } adjsizes[treeid] = adjptr - adjlists[treeid]; } n = matching(m, m, adjlists, adjsizes, NULL, NULL, NULL); sfree(gridids); sfree(adjdata); sfree(adjlists); sfree(adjsizes); 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(const game_params *params, int tilesize, int *x, int *y) { /* fool the macros */ struct dummy { int tilesize; } dummy, *ds = &dummy; dummy.tilesize = tilesize; *x = TLBORDER + BRBORDER + TILESIZE * params->w; *y = TLBORDER + BRBORDER + TILESIZE * params->h; } static void game_set_size(drawing *dr, game_drawstate *ds, const game_params *params, int tilesize) { ds->tilesize = tilesize; } static float *game_colours(frontend *fe, 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; ret[COL_ERROR * 3 + 0] = 1.0F; ret[COL_ERROR * 3 + 1] = 0.0F; ret[COL_ERROR * 3 + 2] = 0.0F; ret[COL_ERRTEXT * 3 + 0] = 1.0F; ret[COL_ERRTEXT * 3 + 1] = 1.0F; ret[COL_ERRTEXT * 3 + 2] = 1.0F; ret[COL_ERRTRUNK * 3 + 0] = 0.6F; ret[COL_ERRTRUNK * 3 + 1] = 0.0F; ret[COL_ERRTRUNK * 3 + 2] = 0.0F; *ncolours = NCOLOURS; return ret; } static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { int w = state->p.w, h = state->p.h; struct game_drawstate *ds = snew(struct game_drawstate); int i; ds->tilesize = 0; ds->started = false; ds->p = state->p; /* structure copy */ ds->drawn = snewn(w*h, int); for (i = 0; i < w*h; i++) ds->drawn[i] = MAGIC; ds->numbersdrawn = snewn(w+h, int); for (i = 0; i < w+h; i++) ds->numbersdrawn[i] = 2; ds->cx = ds->cy = -1; return ds; } static void game_free_drawstate(drawing *dr, game_drawstate *ds) { sfree(ds->drawn); sfree(ds->numbersdrawn); sfree(ds); } enum { ERR_ADJ_TOPLEFT = 4, ERR_ADJ_TOP, ERR_ADJ_TOPRIGHT, ERR_ADJ_LEFT, ERR_ADJ_RIGHT, ERR_ADJ_BOTLEFT, ERR_ADJ_BOT, ERR_ADJ_BOTRIGHT, ERR_OVERCOMMITTED }; static int *find_errors(const game_state *state, char *grid) { int w = state->p.w, h = state->p.h; int *ret = snewn(w*h + w + h, int); int *tmp = snewn(w*h*2, int), *dsf = tmp + w*h; int x, y; /* * This function goes through a grid and works out where to * highlight play errors in red. The aim is that it should * produce at least one error highlight for any complete grid * (or complete piece of grid) violating a puzzle constraint, so * that a grid containing no BLANK squares is either a win or is * marked up in some way that indicates why not. * * So it's easy enough to highlight errors in the numeric clues * - just light up any row or column number which is not * fulfilled - and it's just as easy to highlight adjacent * tents. The difficult bit is highlighting failures in the * tent/tree matching criterion. * * A natural approach would seem to be to apply the matching.c * algorithm to find the tent/tree matching; if this fails, it * could be made to produce as a by-product some set of trees * which have too few tents between them (or vice versa). However, * it's bad for localising errors, because it's not easy to make * the algorithm narrow down to the _smallest_ such set of trees: * if trees A and B have only one tent between them, for instance, * it might perfectly well highlight not only A and B but also * trees C and D which are correctly matched on the far side of * the grid, on the grounds that those four trees between them * have only three tents. * * Also, that approach fares badly when you introduce the * additional requirement that incomplete grids should have * errors highlighted only when they can be proved to be errors * - so that trees should not be marked as having too few tents * if there are enough BLANK squares remaining around them that * could be turned into the missing tents (to do so would be * patronising, since the overwhelming likelihood is not that * the player has forgotten to put a tree there but that they * have merely not put one there _yet_). However, tents with too * few trees can be marked immediately, since those are * definitely player error. * * So I adopt an alternative approach, which is to consider the * bipartite adjacency graph between trees and tents * ('bipartite' in the sense that for these purposes I * deliberately ignore two adjacent trees or two adjacent * tents), divide that graph up into its connected components * using a dsf, and look for components which contain different * numbers of trees and tents. This allows me to highlight * groups of tents with too few trees between them immediately, * and then in order to find groups of trees with too few tents * I redo the same process but counting BLANKs as potential * tents (so that the only trees highlighted are those * surrounded by enough NONTENTs to make it impossible to give * them enough tents). * * However, this technique is incomplete: it is not a sufficient * condition for the existence of a perfect matching that every * connected component of the graph has the same number of tents * and trees. An example of a graph which satisfies the latter * condition but still has no perfect matching is * * A B C * | / ,/| * | / ,'/ | * | / ,' / | * |/,' / | * 1 2 3 * * which can be realised in Tents as * * B * A 1 C 2 * 3 * * The matching-error highlighter described above will not mark * this construction as erroneous. However, something else will: * the three tents in the above diagram (let us suppose A,B,C * are the tents, though it doesn't matter which) contain two * diagonally adjacent pairs. So there will be _an_ error * highlighted for the above layout, even though not all types * of error will be highlighted. * * And in fact we can prove that this will always be the case: * that the shortcomings of the matching-error highlighter will * always be made up for by the easy tent adjacency highlighter. * * Lemma: Let G be a bipartite graph between n trees and n * tents, which is connected, and in which no tree has degree * more than two (but a tent may). Then G has a perfect matching. * * (Note: in the statement and proof of the Lemma I will * consistently use 'tree' to indicate a type of graph vertex as * opposed to a tent, and not to indicate a tree in the graph- * theoretic sense.) * * Proof: * * If we can find a tent of degree 1 joined to a tree of degree * 2, then any perfect matching must pair that tent with that * tree. Hence, we can remove both, leaving a smaller graph G' * which still satisfies all the conditions of the Lemma, and * which has a perfect matching iff G does. * * So, wlog, we may assume G contains no tent of degree 1 joined * to a tree of degree 2; if it does, we can reduce it as above. * * If G has no tent of degree 1 at all, then every tent has * degree at least two, so there are at least 2n edges in the * graph. But every tree has degree at most two, so there are at * most 2n edges. Hence there must be exactly 2n edges, so every * tree and every tent must have degree exactly two, which means * that the whole graph consists of a single loop (by * connectedness), and therefore certainly has a perfect * matching. * * Alternatively, if G does have a tent of degree 1 but it is * not connected to a tree of degree 2, then the tree it is * connected to must have degree 1 - and, by connectedness, that * must mean that that tent and that tree between them form the * entire graph. This trivial graph has a trivial perfect * matching. [] * * That proves the lemma. Hence, in any case where the matching- * error highlighter fails to highlight an erroneous component * (because it has the same number of tents as trees, but they * cannot be matched up), the above lemma tells us that there * must be a tree with degree more than 2, i.e. a tree * orthogonally adjacent to at least three tents. But in that * case, there must be some pair of those three tents which are * diagonally adjacent to each other, so the tent-adjacency * highlighter will necessarily show an error. So any filled * layout in Tents which is not a correct solution to the puzzle * must have _some_ error highlighted by the subroutine below. * * (Of course it would be nicer if we could highlight all * errors: in the above example layout, we would like to * highlight tents A,B as having too few trees between them, and * trees 2,3 as having too few tents, in addition to marking the * adjacency problems. But I can't immediately think of any way * to find the smallest sets of such tents and trees without an * O(2^N) loop over all subsets of a given component.) */ /* * ret[0] through to ret[w*h-1] give error markers for the grid * squares. After that, ret[w*h] to ret[w*h+w-1] give error * markers for the column numbers, and ret[w*h+w] to * ret[w*h+w+h-1] for the row numbers. */ /* * Spot tent-adjacency violations. */ for (x = 0; x < w*h; x++) ret[x] = 0; for (y = 0; y < h; y++) { for (x = 0; x < w; x++) { if (y+1 < h && x+1 < w && ((grid[y*w+x] == TENT && grid[(y+1)*w+(x+1)] == TENT) || (grid[(y+1)*w+x] == TENT && grid[y*w+(x+1)] == TENT))) { ret[y*w+x] |= 1 << ERR_ADJ_BOTRIGHT; ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOPRIGHT; ret[y*w+(x+1)] |= 1 << ERR_ADJ_BOTLEFT; ret[(y+1)*w+(x+1)] |= 1 << ERR_ADJ_TOPLEFT; } if (y+1 < h && grid[y*w+x] == TENT && grid[(y+1)*w+x] == TENT) { ret[y*w+x] |= 1 << ERR_ADJ_BOT; ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOP; } if (x+1 < w && grid[y*w+x] == TENT && grid[y*w+(x+1)] == TENT) { ret[y*w+x] |= 1 << ERR_ADJ_RIGHT; ret[y*w+(x+1)] |= 1 << ERR_ADJ_LEFT; } } } /* * Spot numeric clue violations. */ for (x = 0; x < w; x++) { int tents = 0, maybetents = 0; for (y = 0; y < h; y++) { if (grid[y*w+x] == TENT) tents++; else if (grid[y*w+x] == BLANK) maybetents++; } ret[w*h+x] = (tents > state->numbers->numbers[x] || tents + maybetents < state->numbers->numbers[x]); } for (y = 0; y < h; y++) { int tents = 0, maybetents = 0; for (x = 0; x < w; x++) { if (grid[y*w+x] == TENT) tents++; else if (grid[y*w+x] == BLANK) maybetents++; } ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] || tents + maybetents < state->numbers->numbers[w+y]); } /* * Identify groups of tents with too few trees between them, * which we do by constructing the connected components of the * bipartite adjacency graph between tents and trees * ('bipartite' in the sense that we deliberately ignore * adjacency between tents or between trees), and highlighting * all the tents in any component which has a smaller tree * count. */ dsf_init(dsf, w*h); /* Construct the equivalence classes. */ for (y = 0; y < h; y++) { for (x = 0; x < w-1; x++) { if ((grid[y*w+x] == TREE && grid[y*w+x+1] == TENT) || (grid[y*w+x] == TENT && grid[y*w+x+1] == TREE)) dsf_merge(dsf, y*w+x, y*w+x+1); } } for (y = 0; y < h-1; y++) { for (x = 0; x < w; x++) { if ((grid[y*w+x] == TREE && grid[(y+1)*w+x] == TENT) || (grid[y*w+x] == TENT && grid[(y+1)*w+x] == TREE)) dsf_merge(dsf, y*w+x, (y+1)*w+x); } } /* Count up the tent/tree difference in each one. */ for (x = 0; x < w*h; x++) tmp[x] = 0; for (x = 0; x < w*h; x++) { y = dsf_canonify(dsf, x); if (grid[x] == TREE) tmp[y]++; else if (grid[x] == TENT) tmp[y]--; } /* And highlight any tent belonging to an equivalence class with * a score less than zero. */ for (x = 0; x < w*h; x++) { y = dsf_canonify(dsf, x); if (grid[x] == TENT && tmp[y] < 0) ret[x] |= 1 << ERR_OVERCOMMITTED; } /* * Identify groups of trees with too few tents between them. * This is done similarly, except that we now count BLANK as * equivalent to TENT, i.e. we only highlight such trees when * the user hasn't even left _room_ to provide tents for them * all. (Otherwise, we'd highlight all trees red right at the * start of the game, before the user had done anything wrong!) */ #define TENT(x) ((x)==TENT || (x)==BLANK) dsf_init(dsf, w*h); /* Construct the equivalence classes. */ for (y = 0; y < h; y++) { for (x = 0; x < w-1; x++) { if ((grid[y*w+x] == TREE && TENT(grid[y*w+x+1])) || (TENT(grid[y*w+x]) && grid[y*w+x+1] == TREE)) dsf_merge(dsf, y*w+x, y*w+x+1); } } for (y = 0; y < h-1; y++) { for (x = 0; x < w; x++) { if ((grid[y*w+x] == TREE && TENT(grid[(y+1)*w+x])) || (TENT(grid[y*w+x]) && grid[(y+1)*w+x] == TREE)) dsf_merge(dsf, y*w+x, (y+1)*w+x); } } /* Count up the tent/tree difference in each one. */ for (x = 0; x < w*h; x++) tmp[x] = 0; for (x = 0; x < w*h; x++) { y = dsf_canonify(dsf, x); if (grid[x] == TREE) tmp[y]++; else if (TENT(grid[x])) tmp[y]--; } /* And highlight any tree belonging to an equivalence class with * a score more than zero. */ for (x = 0; x < w*h; x++) { y = dsf_canonify(dsf, x); if (grid[x] == TREE && tmp[y] > 0) ret[x] |= 1 << ERR_OVERCOMMITTED; } #undef TENT sfree(tmp); return ret; } static void draw_err_adj(drawing *dr, game_drawstate *ds, int x, int y) { int coords[8]; int yext, xext; /* * Draw a diamond. */ coords[0] = x - TILESIZE*2/5; coords[1] = y; coords[2] = x; coords[3] = y - TILESIZE*2/5; coords[4] = x + TILESIZE*2/5; coords[5] = y; coords[6] = x; coords[7] = y + TILESIZE*2/5; draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID); /* * Draw an exclamation mark in the diamond. This turns out to * look unpleasantly off-centre if done via draw_text, so I do * it by hand on the basis that exclamation marks aren't that * difficult to draw... */ xext = TILESIZE/16; yext = TILESIZE*2/5 - (xext*2+2); draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3), COL_ERRTEXT); draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT); } static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v, bool cur, bool printing) { int err; int tx = COORD(x), ty = COORD(y); int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2; err = v & ~15; v &= 15; clip(dr, tx, ty, TILESIZE, TILESIZE); if (!printing) { draw_rect(dr, tx, ty, TILESIZE, TILESIZE, COL_GRID); 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), (err & (1<<ERR_OVERCOMMITTED) ? COL_ERRTRUNK : COL_TREETRUNK)); for (i = 0; i < (printing ? 2 : 1); i++) { int col = (i == 1 ? COL_BACKGROUND : (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : 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]; int col; 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; col = (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : COL_TENT); draw_polygon(dr, coords, 3, (printing ? -1 : col), col); } if (err & (1 << ERR_ADJ_TOPLEFT)) draw_err_adj(dr, ds, tx, ty); if (err & (1 << ERR_ADJ_TOP)) draw_err_adj(dr, ds, tx+TILESIZE/2, ty); if (err & (1 << ERR_ADJ_TOPRIGHT)) draw_err_adj(dr, ds, tx+TILESIZE, ty); if (err & (1 << ERR_ADJ_LEFT)) draw_err_adj(dr, ds, tx, ty+TILESIZE/2); if (err & (1 << ERR_ADJ_RIGHT)) draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE/2); if (err & (1 << ERR_ADJ_BOTLEFT)) draw_err_adj(dr, ds, tx, ty+TILESIZE); if (err & (1 << ERR_ADJ_BOT)) draw_err_adj(dr, ds, tx+TILESIZE/2, ty+TILESIZE); if (err & (1 << ERR_ADJ_BOTRIGHT)) draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE); if (cur) { int coff = TILESIZE/8; draw_rect_outline(dr, tx + coff, ty + coff, TILESIZE - coff*2 + 1, TILESIZE - coff*2 + 1, COL_GRID); } 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, const game_state *oldstate, const game_state *state, int dir, const game_ui *ui, float animtime, float flashtime, bool printing) { int w = state->p.w, h = state->p.h; int x, y; bool flashing; int cx = -1, cy = -1; bool cmoved = false; char *tmpgrid; int *errors; if (ui) { if (ui->cdisp) { cx = ui->cx; cy = ui->cy; } if (cx != ds->cx || cy != ds->cy) cmoved = true; } if (printing || !ds->started) { 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); } if (flashtime > 0) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1; else flashing = false; /* * Find errors. For this we use _part_ of the information from a * currently active drag: we transform dsx,dsy but not anything * else. (This seems to strike a good compromise between having * the error highlights respond instantly to single clicks, but * not giving constant feedback during a right-drag.) */ if (ui && ui->drag_button >= 0) { tmpgrid = snewn(w*h, char); memcpy(tmpgrid, state->grid, w*h); tmpgrid[ui->dsy * w + ui->dsx] = drag_xform(ui, ui->dsx, ui->dsy, tmpgrid[ui->dsy * w + ui->dsx]); errors = find_errors(state, tmpgrid); sfree(tmpgrid); } else { errors = find_errors(state, state->grid); } /* * Draw the grid. */ for (y = 0; y < h; y++) { for (x = 0; x < w; x++) { int v = state->grid[y*w+x]; bool credraw = false; /* * We deliberately do not take drag_ok into account * here, because user feedback suggests that it's * marginally nicer not to have the drag effects * flickering on and off disconcertingly. */ if (ui && ui->drag_button >= 0) v = drag_xform(ui, x, y, v); if (flashing && (v == TREE || v == TENT)) v = NONTENT; if (cmoved) { if ((x == cx && y == cy) || (x == ds->cx && y == ds->cy)) credraw = true; } v |= errors[y*w+x]; if (printing || ds->drawn[y*w+x] != v || credraw) { draw_tile(dr, ds, x, y, v, (x == cx && y == cy), printing); if (!printing) ds->drawn[y*w+x] = v; } } } /* * Draw (or redraw, if their error-highlighted state has * changed) the numbers. */ for (x = 0; x < w; x++) { if (printing || ds->numbersdrawn[x] != errors[w*h+x]) { char buf[80]; draw_rect(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1, COL_BACKGROUND); 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, (errors[w*h+x] ? COL_ERROR : COL_GRID), buf); draw_update(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1); if (!printing) ds->numbersdrawn[x] = errors[w*h+x]; } } for (y = 0; y < h; y++) { if (printing || ds->numbersdrawn[w+y] != errors[w*h+w+y]) { char buf[80]; draw_rect(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE, COL_BACKGROUND); sprintf(buf, "%d", state->numbers->numbers[w+y]); draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2, FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE, (errors[w*h+w+y] ? COL_ERROR : COL_GRID), buf); draw_update(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE); if (!printing) ds->numbersdrawn[w+y] = errors[w*h+w+y]; } } if (cmoved) { ds->cx = cx; ds->cy = cy; } sfree(errors); } static void game_redraw(drawing *dr, game_drawstate *ds, const game_state *oldstate, const game_state *state, int dir, const game_ui *ui, float animtime, float flashtime) { int_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, false); } static float game_anim_length(const game_state *oldstate, const game_state *newstate, int dir, game_ui *ui) { return 0.0F; } static float game_flash_length(const game_state *oldstate, const 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 void game_get_cursor_location(const game_ui *ui, const game_drawstate *ds, const game_state *state, const game_params *params, int *x, int *y, int *w, int *h) { if(ui->cdisp) { *x = COORD(ui->cx); *y = COORD(ui->cy); *w = *h = TILESIZE; } } static int game_status(const game_state *state) { return state->completed ? +1 : 0; } static void game_print_size(const 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.0F; *y = ph / 100.0F; } static void game_print(drawing *dr, const 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", "tents", default_params, game_fetch_preset, NULL, 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, true, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, decode_ui, NULL, /* game_request_keys */ game_changed_state, current_key_label, 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, game_get_cursor_location, game_status, true, false, game_print_size, game_print, false, /* wants_statusbar */ false, NULL, /* timing_state */ REQUIRE_RBUTTON, /* flags */ }; #ifdef STANDALONE_SOLVER #include <stdarg.h> int main(int argc, char **argv) { game_params *p; game_state *s, *s2; char *id = NULL, *desc; const char *err; bool grade = false; int ret, diff; bool 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 /* vim: set shiftwidth=4 tabstop=8: */