* 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
COL_TENT,
COL_ERROR,
COL_ERRTEXT,
+ COL_ERRTRUNK,
NCOLOURS
};
char *soln, struct solver_scratch *sc, int diff)
{
int x, y, d, i, j;
- char *mrow, *mrow1, *mrow2, *trow, *trow1, *trow2;
+ char *mrow, *trow, *trow1, *trow2;
/*
* Set up solver data.
* 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;
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)
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.
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 */
* 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.
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(game_state *state, game_ui *ui, game_drawstate *ds,
+static char *interpret_move(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;
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;
}
ERR_OVERCOMMITTED
};
-static int *find_errors(game_state *state)
+static int *find_errors(game_state *state, char *grid)
{
int w = state->p.w, h = state->p.h;
int *ret = snewn(w*h + w + h, int);
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 maxflow
+ * algorithm to find the tent/tree matching; if this fails, it
+ * must necessarily terminate with a min-cut which can be
+ * reinterpreted as 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
for (y = 0; y < h; y++) {
for (x = 0; x < w; x++) {
if (y+1 < h && x+1 < w &&
- ((state->grid[y*w+x] == TENT &&
- state->grid[(y+1)*w+(x+1)] == TENT) ||
- (state->grid[(y+1)*w+x] == TENT &&
- state->grid[y*w+(x+1)] == TENT))) {
+ ((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 &&
- state->grid[y*w+x] == TENT &&
- state->grid[(y+1)*w+x] == TENT) {
+ 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 &&
- state->grid[y*w+x] == TENT &&
- state->grid[y*w+(x+1)] == TENT) {
+ 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;
}
for (x = 0; x < w; x++) {
int tents = 0, maybetents = 0;
for (y = 0; y < h; y++) {
- if (state->grid[y*w+x] == TENT)
+ if (grid[y*w+x] == TENT)
tents++;
- else if (state->grid[y*w+x] == BLANK)
+ else if (grid[y*w+x] == BLANK)
maybetents++;
}
ret[w*h+x] = (tents > state->numbers->numbers[x] ||
for (y = 0; y < h; y++) {
int tents = 0, maybetents = 0;
for (x = 0; x < w; x++) {
- if (state->grid[y*w+x] == TENT)
+ if (grid[y*w+x] == TENT)
tents++;
- else if (state->grid[y*w+x] == BLANK)
+ else if (grid[y*w+x] == BLANK)
maybetents++;
}
ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] ||
/* Construct the equivalence classes. */
for (y = 0; y < h; y++) {
for (x = 0; x < w-1; x++) {
- if ((state->grid[y*w+x]==TREE && state->grid[y*w+x+1]==TENT) ||
- (state->grid[y*w+x]==TENT && state->grid[y*w+x+1]==TREE))
+ 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 ((state->grid[y*w+x]==TREE && state->grid[(y+1)*w+x]==TENT) ||
- (state->grid[y*w+x]==TENT && state->grid[(y+1)*w+x]==TREE))
+ 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);
}
}
tmp[x] = 0;
for (x = 0; x < w*h; x++) {
y = dsf_canonify(dsf, x);
- if (state->grid[x] == TREE)
+ if (grid[x] == TREE)
tmp[y]++;
- else if (state->grid[x] == TENT)
+ 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 (state->grid[x] == TENT && tmp[y] < 0)
+ if (grid[x] == TENT && tmp[y] < 0)
ret[x] |= 1 << ERR_OVERCOMMITTED;
}
/* Construct the equivalence classes. */
for (y = 0; y < h; y++) {
for (x = 0; x < w-1; x++) {
- if ((state->grid[y*w+x]==TREE && TENT(state->grid[y*w+x+1])) ||
- (TENT(state->grid[y*w+x]) && state->grid[y*w+x+1]==TREE))
+ 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 ((state->grid[y*w+x]==TREE && TENT(state->grid[(y+1)*w+x])) ||
- (TENT(state->grid[y*w+x]) && state->grid[(y+1)*w+x]==TREE))
+ 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);
}
}
tmp[x] = 0;
for (x = 0; x < w*h; x++) {
y = dsf_canonify(dsf, x);
- if (state->grid[x] == TREE)
+ if (grid[x] == TREE)
tmp[y]++;
- else if (TENT(state->grid[x]))
+ 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 (state->grid[x] == TREE && tmp[y] > 0)
+ if (grid[x] == TREE && tmp[y] > 0)
ret[x] |= 1 << ERR_OVERCOMMITTED;
}
#undef TENT
(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_ERROR : COL_TREETRUNK));
+ (err & (1<<ERR_OVERCOMMITTED) ? COL_ERRTRUNK : COL_TREETRUNK));
for (i = 0; i < (printing ? 2 : 1); i++) {
int col = (i == 1 ? COL_BACKGROUND :
int x, y, flashing;
int cx = -1, cy = -1;
int cmoved = 0;
+ char *tmpgrid;
int *errors;
if (ui) {
flashing = FALSE;
/*
- * Find errors.
+ * 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.)
*/
- errors = find_errors(state);
+ 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.
* changed) the numbers.
*/
for (x = 0; x < w; x++) {
- if (ds->numbersdrawn[x] != errors[w*h+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);
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);
- ds->numbersdrawn[x] = errors[w*h+x];
+ if (!printing)
+ ds->numbersdrawn[x] = errors[w*h+x];
}
}
for (y = 0; y < h; y++) {
- if (ds->numbersdrawn[w+y] != errors[w*h+w+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);
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);
- ds->numbersdrawn[w+y] = errors[w*h+w+y];
+ if (!printing)
+ ds->numbersdrawn[w+y] = errors[w*h+w+y];
}
}
return 0.0F;
}
+static int game_status(game_state *state)
+{
+ return state->completed ? +1 : 0;
+}
+
static int game_timing_state(game_state *state, game_ui *ui)
{
return TRUE;
game_redraw,
game_anim_length,
game_flash_length,
+ game_status,
TRUE, FALSE, game_print_size, game_print,
FALSE, /* wants_statusbar */
FALSE, game_timing_state,
~mdw / sgt / puzzles / blobdiff