X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/2a27ffcf57125dbe29751964197982676ab1ef0e..HEAD:/tents.c diff --git a/tents.c b/tents.c index 4a433d9..ef5debc 100644 --- a/tents.c +++ b/tents.c @@ -3,7 +3,7 @@ * 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 @@ -259,6 +259,7 @@ enum { COL_TENT, COL_ERROR, COL_ERRTEXT, + COL_ERRTRUNK, NCOLOURS }; @@ -458,7 +459,7 @@ 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; + char *mrow, *trow, *trow1, *trow2; /* * Set up solver data. @@ -745,8 +746,6 @@ static int tents_solve(int w, int h, const char *grid, int *numbers, * 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; @@ -1209,6 +1208,10 @@ static char *validate_desc(game_params *params, char *desc) 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) @@ -1464,6 +1467,7 @@ static int drag_xform(game_ui *ui, int x, int y, int v) 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. @@ -1472,6 +1476,7 @@ static int drag_xform(game_ui *ui, int x, int y, int v) 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 */ @@ -1484,11 +1489,18 @@ static int drag_xform(game_ui *ui, int x, int y, int v) * 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. @@ -1498,13 +1510,17 @@ static int drag_xform(game_ui *ui, int x, int y, int v) 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; @@ -1879,6 +1895,10 @@ static float *game_colours(frontend *fe, int *ncolours) 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; } @@ -1922,7 +1942,7 @@ enum { 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); @@ -1930,6 +1950,147 @@ static int *find_errors(game_state *state) 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 @@ -1944,24 +2105,24 @@ static int *find_errors(game_state *state) 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; } @@ -1974,9 +2135,9 @@ static int *find_errors(game_state *state) 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] || @@ -1985,9 +2146,9 @@ static int *find_errors(game_state *state) 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] || @@ -2007,15 +2168,15 @@ static int *find_errors(game_state *state) /* 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); } } @@ -2024,16 +2185,16 @@ static int *find_errors(game_state *state) 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; } @@ -2050,15 +2211,15 @@ static int *find_errors(game_state *state) /* 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); } } @@ -2067,16 +2228,16 @@ static int *find_errors(game_state *state) 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 @@ -2140,7 +2301,7 @@ static void draw_tile(drawing *dr, game_drawstate *ds, (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<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. @@ -2288,7 +2463,7 @@ static void int_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, * 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); @@ -2297,11 +2472,12 @@ static void int_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, 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); @@ -2310,7 +2486,8 @@ static void int_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, 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]; } } @@ -2345,6 +2522,11 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, 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; @@ -2415,6 +2597,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, FALSE, game_print_size, game_print, FALSE, /* wants_statusbar */ FALSE, game_timing_state,