*
* - clue marking
* - better four-colouring algorithm?
- * - can we make the pencil marks look nicer?
- * - ability to drag a set of pencil marks?
*/
#include <stdio.h>
#include "puzzles.h"
/*
+ * In standalone solver mode, `verbose' is a variable which can be
+ * set by command-line option; in debugging mode it's simply always
+ * true.
+ */
+#if defined STANDALONE_SOLVER
+#define SOLVER_DIAGNOSTICS
+int verbose = FALSE;
+#elif defined SOLVER_DIAGNOSTICS
+#define verbose TRUE
+#endif
+
+/*
* I don't seriously anticipate wanting to change the number of
* colours used in this game, but it doesn't cost much to use a
* #define just in case :-)
int n;
int ngraph;
int *immutable;
- int *edgex, *edgey; /* positions of a point on each edge */
+ int *edgex, *edgey; /* position of a point on each edge */
+ int *regionx, *regiony; /* position of a point in each region */
};
struct game_state {
{
game_params *ret = snew(game_params);
+#ifdef PORTRAIT_SCREEN
+ ret->w = 16;
+ ret->h = 18;
+#else
ret->w = 20;
ret->h = 15;
+#endif
ret->n = 30;
ret->diff = DIFF_NORMAL;
}
static const struct game_params map_presets[] = {
+#ifdef PORTRAIT_SCREEN
+ {16, 18, 30, DIFF_EASY},
+ {16, 18, 30, DIFF_NORMAL},
+ {16, 18, 30, DIFF_HARD},
+ {16, 18, 30, DIFF_RECURSE},
+ {25, 30, 75, DIFF_NORMAL},
+ {25, 30, 75, DIFF_HARD},
+#else
{20, 15, 30, DIFF_EASY},
{20, 15, 30, DIFF_NORMAL},
{20, 15, 30, DIFF_HARD},
{20, 15, 30, DIFF_RECURSE},
{30, 25, 75, DIFF_NORMAL},
{30, 25, 75, DIFF_HARD},
+#endif
};
static int game_fetch_preset(int i, char **name, game_params **params)
struct solver_scratch {
unsigned char *possible; /* bitmap of colours for each region */
+
int *graph;
- int *bfsqueue;
- int *bfscolour;
int n;
int ngraph;
+
+ int *bfsqueue;
+ int *bfscolour;
+#ifdef SOLVER_DIAGNOSTICS
+ int *bfsprev;
+#endif
+
int depth;
};
sc->depth = 0;
sc->bfsqueue = snewn(n, int);
sc->bfscolour = snewn(n, int);
+#ifdef SOLVER_DIAGNOSTICS
+ sc->bfsprev = snewn(n, int);
+#endif
return sc;
}
sfree(sc->possible);
sfree(sc->bfsqueue);
sfree(sc->bfscolour);
+#ifdef SOLVER_DIAGNOSTICS
+ sfree(sc->bfsprev);
+#endif
sfree(sc);
}
return word;
}
+#ifdef SOLVER_DIAGNOSTICS
+static const char colnames[FOUR] = { 'R', 'Y', 'G', 'B' };
+#endif
+
static int place_colour(struct solver_scratch *sc,
- int *colouring, int index, int colour)
+ int *colouring, int index, int colour
+#ifdef SOLVER_DIAGNOSTICS
+ , char *verb
+#endif
+ )
{
int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
int j, k;
- if (!(sc->possible[index] & (1 << colour)))
+ if (!(sc->possible[index] & (1 << colour))) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose)
+ printf("%*scannot place %c in region %d\n", 2*sc->depth, "",
+ colnames[colour], index);
+#endif
return FALSE; /* can't do it */
+ }
sc->possible[index] = 1 << colour;
colouring[index] = colour;
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose)
+ printf("%*s%s %c in region %d\n", 2*sc->depth, "",
+ verb, colnames[colour], index);
+#endif
+
/*
* Rule out this colour from all the region's neighbours.
*/
for (j = graph_vertex_start(graph, n, ngraph, index);
j < ngraph && graph[j] < n*(index+1); j++) {
k = graph[j] - index*n;
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose && (sc->possible[k] & (1 << colour)))
+ printf("%*s ruling out %c in region %d\n", 2*sc->depth, "",
+ colnames[colour], k);
+#endif
sc->possible[k] &= ~(1 << colour);
}
return TRUE;
}
+#ifdef SOLVER_DIAGNOSTICS
+static char *colourset(char *buf, int set)
+{
+ int i;
+ char *p = buf;
+ char *sep = "";
+
+ for (i = 0; i < FOUR; i++)
+ if (set & (1 << i)) {
+ p += sprintf(p, "%s%c", sep, colnames[i]);
+ sep = ",";
+ }
+
+ return buf;
+}
+#endif
+
/*
* Returns 0 for impossible, 1 for success, 2 for failure to
* converge (i.e. puzzle is either ambiguous or just too
{
int i;
- /*
- * Initialise scratch space.
- */
- for (i = 0; i < n; i++)
- sc->possible[i] = (1 << FOUR) - 1;
+ if (sc->depth == 0) {
+ /*
+ * Initialise scratch space.
+ */
+ for (i = 0; i < n; i++)
+ sc->possible[i] = (1 << FOUR) - 1;
- /*
- * Place clues.
- */
- for (i = 0; i < n; i++)
- if (colouring[i] >= 0) {
- if (!place_colour(sc, colouring, i, colouring[i]))
- return 0; /* the clues aren't even consistent! */
- }
+ /*
+ * Place clues.
+ */
+ for (i = 0; i < n; i++)
+ if (colouring[i] >= 0) {
+ if (!place_colour(sc, colouring, i, colouring[i]
+#ifdef SOLVER_DIAGNOSTICS
+ , "initial clue:"
+#endif
+ )) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose)
+ printf("%*sinitial clue set is inconsistent\n",
+ 2*sc->depth, "");
+#endif
+ return 0; /* the clues aren't even consistent! */
+ }
+ }
+ }
/*
* Now repeatedly loop until we find nothing further to do.
for (i = 0; i < n; i++) if (colouring[i] < 0) {
int p = sc->possible[i];
- if (p == 0)
+ if (p == 0) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose)
+ printf("%*sregion %d has no possible colours left\n",
+ 2*sc->depth, "", i);
+#endif
return 0; /* puzzle is inconsistent */
+ }
if ((p & (p-1)) == 0) { /* p is a power of two */
- int c;
+ int c, ret;
for (c = 0; c < FOUR; c++)
if (p == (1 << c))
break;
assert(c < FOUR);
- if (!place_colour(sc, colouring, i, c))
- return 0; /* found puzzle to be inconsistent */
+ ret = place_colour(sc, colouring, i, c
+#ifdef SOLVER_DIAGNOSTICS
+ , "placing"
+#endif
+ );
+ /*
+ * place_colour() can only fail if colour c was not
+ * even a _possibility_ for region i, and we're
+ * pretty sure it was because we checked before
+ * calling place_colour(). So we can safely assert
+ * here rather than having to return a nice
+ * friendly error code.
+ */
+ assert(ret);
done_something = TRUE;
}
}
for (i = 0; i < ngraph; i++) {
int j1 = graph[i] / n, j2 = graph[i] % n;
int j, k, v, v2;
+#ifdef SOLVER_DIAGNOSTICS
+ int started = FALSE;
+#endif
if (j1 > j2)
continue; /* done it already, other way round */
k = graph[j] - j1*n;
if (graph_adjacent(graph, n, ngraph, k, j2) &&
(sc->possible[k] & v)) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose) {
+ char buf[80];
+ if (!started)
+ printf("%*sadjacent regions %d,%d share colours"
+ " %s\n", 2*sc->depth, "", j1, j2,
+ colourset(buf, v));
+ started = TRUE;
+ printf("%*s ruling out %s in region %d\n",2*sc->depth,
+ "", colourset(buf, sc->possible[k] & v), k);
+ }
+#endif
sc->possible[k] &= ~v;
done_something = TRUE;
}
origc = 1 << c;
- for (j = 0; j < n; j++)
+ for (j = 0; j < n; j++) {
sc->bfscolour[j] = -1;
+#ifdef SOLVER_DIAGNOSTICS
+ sc->bfsprev[j] = -1;
+#endif
+ }
head = tail = 0;
sc->bfsqueue[tail++] = i;
sc->bfscolour[i] = sc->possible[i] &~ origc;
sc->bfsqueue[tail++] = k;
sc->bfscolour[k] =
sc->possible[k] &~ currc;
+#ifdef SOLVER_DIAGNOSTICS
+ sc->bfsprev[k] = j;
+#endif
}
/*
if (currc == origc &&
graph_adjacent(graph, n, ngraph, k, i) &&
(sc->possible[k] & currc)) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose) {
+ char buf[80], *sep = "";
+ int r;
+
+ printf("%*sforcing chain, colour %s, ",
+ 2*sc->depth, "",
+ colourset(buf, origc));
+ for (r = j; r != -1; r = sc->bfsprev[r]) {
+ printf("%s%d", sep, r);
+ sep = "-";
+ }
+ printf("\n%*s ruling out %s in region"
+ " %d\n", 2*sc->depth, "",
+ colourset(buf, origc), k);
+ }
+#endif
sc->possible[k] &= ~origc;
done_something = TRUE;
}
for (i = 0; i < n; i++)
if (colouring[i] < 0)
break;
- if (i == n)
+ if (i == n) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose)
+ printf("%*sone solution found\n", 2*sc->depth, "");
+#endif
return 1; /* success! */
+ }
/*
* If recursion is not permissible, we now give up.
*/
- if (difficulty < DIFF_RECURSE)
+ if (difficulty < DIFF_RECURSE) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose)
+ printf("%*sunable to proceed further without recursion\n",
+ 2*sc->depth, "");
+#endif
return 2; /* unable to complete */
+ }
/*
* Now we've got to do something recursive. So first hunt for a
assert(best >= 0); /* or we'd be solved already */
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose)
+ printf("%*srecursing on region %d\n", 2*sc->depth, "", best);
+#endif
+
/*
* Now iterate over the possible colours for this region.
*/
if (!(sc->possible[best] & (1 << i)))
continue;
+ memcpy(rsc->possible, sc->possible, n);
memcpy(subcolouring, origcolouring, n * sizeof(int));
- subcolouring[best] = i;
+
+ place_colour(rsc, subcolouring, best, i
+#ifdef SOLVER_DIAGNOSTICS
+ , "trying"
+#endif
+ );
+
subret = map_solver(rsc, graph, n, ngraph,
subcolouring, difficulty);
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose) {
+ printf("%*sretracting %c in region %d; found %s\n",
+ 2*sc->depth, "", colnames[i], best,
+ subret == 0 ? "no solutions" :
+ subret == 1 ? "one solution" : "multiple solutions");
+ }
+#endif
+
/*
* If this possibility turned up more than one valid
* solution, or if it turned up one and we already had
*/
}
+ sfree(origcolouring);
sfree(subcolouring);
free_scratch(rsc);
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose && sc->depth == 0) {
+ printf("%*s%s found\n",
+ 2*sc->depth, "",
+ ret == 0 ? "no solutions" :
+ ret == 1 ? "one solution" : "multiple solutions");
+ }
+#endif
return ret;
}
}
int i, k, pos, state;
char *p = *desc;
- for (i = 0; i < wh; i++)
- map[wh+i] = i;
+ dsf_init(map+wh, wh);
pos = -1;
state = 0;
map = snewn(2*wh, int);
ret = parse_edge_list(params, &desc, map);
+ sfree(map);
if (ret)
return ret;
- sfree(map);
if (*desc != ',')
return "Expected comma before clue list";
* outlines by the judicious use of diagonally divided squares.
*/
{
- random_state *rs = random_init(desc, strlen(desc));
+ random_state *rs = random_new(desc, strlen(desc));
int *squares = snewn(wh, int);
int done_something;
/*
* Analyse the map to find a canonical line segment
- * corresponding to each edge. These are where we'll eventually
- * put error markers.
+ * corresponding to each edge, and a canonical point
+ * corresponding to each region. The former are where we'll
+ * eventually put error markers; the latter are where we'll put
+ * per-region flags such as numbers (when in diagnostic mode).
*/
{
int *bestx, *besty, *an, pass;
float *ax, *ay, *best;
- ax = snewn(state->map->ngraph, float);
- ay = snewn(state->map->ngraph, float);
- an = snewn(state->map->ngraph, int);
- bestx = snewn(state->map->ngraph, int);
- besty = snewn(state->map->ngraph, int);
- best = snewn(state->map->ngraph, float);
+ ax = snewn(state->map->ngraph + n, float);
+ ay = snewn(state->map->ngraph + n, float);
+ an = snewn(state->map->ngraph + n, int);
+ bestx = snewn(state->map->ngraph + n, int);
+ besty = snewn(state->map->ngraph + n, int);
+ best = snewn(state->map->ngraph + n, float);
- for (i = 0; i < state->map->ngraph; i++) {
+ for (i = 0; i < state->map->ngraph + n; i++) {
bestx[i] = besty[i] = -1;
- best[i] = 2*(w+h)+1;
+ best[i] = (float)(2*(w+h)+1);
ax[i] = ay[i] = 0.0F;
an[i] = 0;
}
/*
* We make two passes over the map, finding all the line
- * segments separating regions. In the first pass, we
- * compute the _average_ x and y coordinate of all the line
- * segments separating each pair of regions; in the second
- * pass, for each such average point, we find the line
- * segment closest to it and call that canonical.
+ * segments separating regions and all the suitable points
+ * within regions. In the first pass, we compute the
+ * _average_ x and y coordinate of all the points in a
+ * given class; in the second pass, for each such average
+ * point, we find the candidate closest to it and call that
+ * canonical.
*
* Line segments are considered to have coordinates in
* their centre. Thus, at least one coordinate for any line
/* right edge */
ea[en] = state->map->map[RE * wh + y*w+x];
eb[en] = state->map->map[LE * wh + y*w+(x+1)];
- if (ea[en] != eb[en]) {
- ex[en] = (x+1)*2;
- ey[en] = y*2+1;
- en++;
- }
+ ex[en] = (x+1)*2;
+ ey[en] = y*2+1;
+ en++;
}
if (y+1 < h) {
/* bottom edge */
ea[en] = state->map->map[BE * wh + y*w+x];
eb[en] = state->map->map[TE * wh + (y+1)*w+x];
- if (ea[en] != eb[en]) {
- ex[en] = x*2+1;
- ey[en] = (y+1)*2;
- en++;
- }
+ ex[en] = x*2+1;
+ ey[en] = (y+1)*2;
+ en++;
}
/* diagonal edge */
ea[en] = state->map->map[TE * wh + y*w+x];
eb[en] = state->map->map[BE * wh + y*w+x];
- if (ea[en] != eb[en]) {
- ex[en] = x*2+1;
- ey[en] = y*2+1;
- en++;
- }
+ ex[en] = x*2+1;
+ ey[en] = y*2+1;
+ en++;
+
if (x+1 < w && y+1 < h) {
/* bottom right corner */
int oct[8], othercol, nchanges;
ey[en] = (y+1)*2;
en++;
}
+
+ /*
+ * If there's exactly _one_ region at this
+ * point, on the other hand, it's a valid
+ * place to put a region centre.
+ */
+ if (othercol < 0) {
+ ea[en] = eb[en] = oct[0];
+ ex[en] = (x+1)*2;
+ ey[en] = (y+1)*2;
+ en++;
+ }
}
/*
- * Now process the edges we've found, one by
+ * Now process the points we've found, one by
* one.
*/
for (i = 0; i < en; i++) {
int emin = min(ea[i], eb[i]);
int emax = max(ea[i], eb[i]);
- int gindex =
- graph_edge_index(state->map->graph, n,
- state->map->ngraph, emin, emax);
+ int gindex;
+
+ if (emin != emax) {
+ /* Graph edge */
+ gindex =
+ graph_edge_index(state->map->graph, n,
+ state->map->ngraph, emin,
+ emax);
+ } else {
+ /* Region number */
+ gindex = state->map->ngraph + emin;
+ }
assert(gindex >= 0);
*/
ax[gindex] += ex[i];
ay[gindex] += ey[i];
- an[gindex] += 1.0F;
+ an[gindex] += 1;
} else {
/*
* In pass 1, work out whether this
assert(an[gindex] > 0);
dx = ex[i] - ax[gindex];
dy = ey[i] - ay[gindex];
- d = sqrt(dx*dx + dy*dy);
+ d = (float)sqrt(dx*dx + dy*dy);
if (d < best[gindex]) {
best[gindex] = d;
bestx[gindex] = ex[i];
}
if (pass == 0) {
- for (i = 0; i < state->map->ngraph; i++)
+ for (i = 0; i < state->map->ngraph + n; i++)
if (an[i] > 0) {
ax[i] /= an[i];
ay[i] /= an[i];
}
}
- state->map->edgex = bestx;
- state->map->edgey = besty;
+ state->map->edgex = snewn(state->map->ngraph, int);
+ state->map->edgey = snewn(state->map->ngraph, int);
+ memcpy(state->map->edgex, bestx, state->map->ngraph * sizeof(int));
+ memcpy(state->map->edgey, besty, state->map->ngraph * sizeof(int));
+
+ state->map->regionx = snewn(n, int);
+ state->map->regiony = snewn(n, int);
+ memcpy(state->map->regionx, bestx + state->map->ngraph, n*sizeof(int));
+ memcpy(state->map->regiony, besty + state->map->ngraph, n*sizeof(int));
for (i = 0; i < state->map->ngraph; i++)
if (state->map->edgex[i] < 0) {
sfree(ay);
sfree(an);
sfree(best);
+ sfree(bestx);
+ sfree(besty);
}
return state;
sfree(state->map->immutable);
sfree(state->map->edgex);
sfree(state->map->edgey);
+ sfree(state->map->regionx);
+ sfree(state->map->regiony);
sfree(state->map);
}
+ sfree(state->pencil);
sfree(state->colouring);
sfree(state);
}
return dupstr(aux);
}
+static int game_can_format_as_text_now(game_params *params)
+{
+ return TRUE;
+}
+
static char *game_text_format(game_state *state)
{
return NULL;
}
struct game_ui {
- int drag_colour; /* -1 means no drag active */
+ /*
+ * drag_colour:
+ *
+ * - -2 means no drag currently active.
+ * - >=0 means we're dragging a solid colour.
+ * - -1 means we're dragging a blank space, and drag_pencil
+ * might or might not add some pencil-mark stipples to that.
+ */
+ int drag_colour;
+ int drag_pencil;
int dragx, dragy;
+ int show_numbers;
+
+ int cur_x, cur_y, cur_visible, cur_moved, cur_lastmove;
};
static game_ui *new_ui(game_state *state)
game_ui *ui = snew(game_ui);
ui->dragx = ui->dragy = -1;
ui->drag_colour = -2;
+ ui->drag_pencil = 0;
+ ui->show_numbers = FALSE;
+ ui->cur_x = ui->cur_y = ui->cur_visible = ui->cur_moved = 0;
+ ui->cur_lastmove = 0;
return ui;
}
};
/* Flags in `drawn'. */
-#define ERR_BASE 0x00800000L
-#define ERR_MASK 0xFF800000L
+#define ERR_BASE 0x00800000L
+#define ERR_MASK 0xFF800000L
#define PENCIL_T_BASE 0x00080000L
#define PENCIL_T_MASK 0x00780000L
#define PENCIL_B_BASE 0x00008000L
#define PENCIL_B_MASK 0x00078000L
#define PENCIL_MASK 0x007F8000L
+#define SHOW_NUMBERS 0x00004000L
#define TILESIZE (ds->tilesize)
#define BORDER (TILESIZE)
#define COORD(x) ( (x) * TILESIZE + BORDER )
#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
-static int region_from_coords(game_state *state, game_drawstate *ds,
+ /*
+ * EPSILON_FOO are epsilons added to absolute cursor position by
+ * cursor movement, such that in pathological cases (e.g. a very
+ * small diamond-shaped area) it's relatively easy to select the
+ * region you wanted.
+ */
+
+#define EPSILON_X(button) (((button) == CURSOR_RIGHT) ? +1 : \
+ ((button) == CURSOR_LEFT) ? -1 : 0)
+#define EPSILON_Y(button) (((button) == CURSOR_DOWN) ? +1 : \
+ ((button) == CURSOR_UP) ? -1 : 0)
+
+
+static int region_from_coords(game_state *state, const game_drawstate *ds,
int x, int y)
{
int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
return state->map->map[quadrant * wh + ty*w+tx];
}
-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)
{
- char buf[80];
+ char *bufp, buf[256];
+ int alt_button;
+
+ /*
+ * Enable or disable numeric labels on regions.
+ */
+ if (button == 'l' || button == 'L') {
+ ui->show_numbers = !ui->show_numbers;
+ return "";
+ }
+
+ if (IS_CURSOR_MOVE(button)) {
+ move_cursor(button, &ui->cur_x, &ui->cur_y, state->p.w, state->p.h, 0);
+ ui->cur_visible = 1;
+ ui->cur_moved = 1;
+ ui->cur_lastmove = button;
+ ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(button);
+ ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(button);
+ return "";
+ }
+ if (IS_CURSOR_SELECT(button)) {
+ if (!ui->cur_visible) {
+ ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove);
+ ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove);
+ ui->cur_visible = 1;
+ return "";
+ }
+ if (ui->drag_colour == -2) { /* not currently cursor-dragging, start. */
+ int r = region_from_coords(state, ds, ui->dragx, ui->dragy);
+ if (r >= 0) {
+ ui->drag_colour = state->colouring[r];
+ ui->drag_pencil = (ui->drag_colour >= 0) ? 0 : state->pencil[r];
+ } else {
+ ui->drag_colour = -1;
+ ui->drag_pencil = 0;
+ }
+ ui->cur_moved = 0;
+ return "";
+ } else { /* currently cursor-dragging; drop the colour in the new region. */
+ x = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove);
+ y = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove);
+ alt_button = (button == CURSOR_SELECT2) ? 1 : 0;
+ /* Double-select removes current colour. */
+ if (!ui->cur_moved) ui->drag_colour = -1;
+ goto drag_dropped;
+ }
+ }
if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
int r = region_from_coords(state, ds, x, y);
- if (r >= 0)
+ if (r >= 0) {
ui->drag_colour = state->colouring[r];
- else
+ ui->drag_pencil = state->pencil[r];
+ if (ui->drag_colour >= 0)
+ ui->drag_pencil = 0; /* should be already, but double-check */
+ } else {
ui->drag_colour = -1;
+ ui->drag_pencil = 0;
+ }
ui->dragx = x;
ui->dragy = y;
+ ui->cur_visible = 0;
return "";
}
if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
ui->drag_colour > -2) {
+ alt_button = (button == RIGHT_RELEASE) ? 1 : 0;
+ goto drag_dropped;
+ }
+
+ return NULL;
+
+drag_dropped:
+ {
int r = region_from_coords(state, ds, x, y);
int c = ui->drag_colour;
+ int p = ui->drag_pencil;
+ int oldp;
/*
* Cancel the drag, whatever happens.
*/
ui->drag_colour = -2;
- ui->dragx = ui->dragy = -1;
if (r < 0)
return ""; /* drag into border; do nothing else */
if (state->map->immutable[r])
return ""; /* can't change this region */
- if (state->colouring[r] == c)
+ if (state->colouring[r] == c && state->pencil[r] == p)
return ""; /* don't _need_ to change this region */
- if (button == RIGHT_RELEASE && state->colouring[r] >= 0)
- return ""; /* can't pencil on a coloured region */
+ if (alt_button) {
+ if (state->colouring[r] >= 0) {
+ /* Can't pencil on a coloured region */
+ return "";
+ } else if (c >= 0) {
+ /* Right-dragging from colour to blank toggles one pencil */
+ p = state->pencil[r] ^ (1 << c);
+ c = -1;
+ }
+ /* Otherwise, right-dragging from blank to blank is equivalent
+ * to left-dragging. */
+ }
- sprintf(buf, "%s%c:%d", (button == RIGHT_RELEASE ? "p" : ""),
- (int)(c < 0 ? 'C' : '0' + c), r);
- return dupstr(buf);
- }
+ bufp = buf;
+ oldp = state->pencil[r];
+ if (c != state->colouring[r]) {
+ bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
+ if (c >= 0)
+ oldp = 0;
+ }
+ if (p != oldp) {
+ int i;
+ for (i = 0; i < FOUR; i++)
+ if ((oldp ^ p) & (1 << i))
+ bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r);
+ }
- return NULL;
+ return dupstr(buf+1); /* ignore first semicolon */
+ }
}
static game_state *execute_move(game_state *state, char *move)
{
ds->tilesize = tilesize;
- if (ds->bl)
- blitter_free(dr, ds->bl);
+ assert(!ds->bl); /* set_size is never called twice */
ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
}
const float map_colours[FOUR][3] = {
+#ifdef VIVID_COLOURS
+ /* Use more vivid colours (e.g. on the Pocket PC) */
+ {0.75F, 0.25F, 0.25F},
+ {0.3F, 0.7F, 0.3F},
+ {0.3F, 0.3F, 0.7F},
+ {0.85F, 0.85F, 0.1F},
+#else
{0.7F, 0.5F, 0.4F},
{0.8F, 0.7F, 0.4F},
{0.5F, 0.6F, 0.4F},
{0.55F, 0.45F, 0.35F},
+#endif
};
const int map_hatching[FOUR] = {
HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
};
-static float *game_colours(frontend *fe, game_state *state, int *ncolours)
+static float *game_colours(frontend *fe, int *ncolours)
{
float *ret = snewn(3 * NCOLOURS, float);
static void draw_square(drawing *dr, game_drawstate *ds,
game_params *params, struct map *map,
- int x, int y, int v)
+ int x, int y, unsigned long v)
{
int w = params->w, h = params->h, wh = w*h;
- int tv, bv, xo, yo, errs, pencil;
+ int tv, bv, xo, yo, i, j, oldj;
+ unsigned long errs, pencil, show_numbers;
errs = v & ERR_MASK;
v &= ~ERR_MASK;
pencil = v & PENCIL_MASK;
v &= ~PENCIL_MASK;
+ show_numbers = v & SHOW_NUMBERS;
+ v &= ~SHOW_NUMBERS;
tv = v / FIVE;
bv = v % FIVE;
xo < 2 ? LE : RE);
ee = map->map[e * wh + y*w+x];
- c = (yo & 1) * 2 + (xo & 1);
+ if (xo != (yo * 2 + 1) % 5)
+ continue;
+ c = yo;
if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
continue;
(map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x]))
continue; /* avoid BL-TR diagonal line */
- draw_rect(dr, COORD(x) + (5*xo+1)*TILESIZE/20,
- COORD(y) + (5*yo+1)*TILESIZE/20,
- 4*TILESIZE/20, 4*TILESIZE/20, COL_0 + c);
+ draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5,
+ COORD(y) + (yo+1)*TILESIZE/5,
+ TILESIZE/7, COL_0 + c, COL_0 + c);
}
/*
(COORD(x)*2+TILESIZE*xo)/2,
(COORD(y)*2+TILESIZE*yo)/2);
+ /*
+ * Draw region numbers, if desired.
+ */
+ if (show_numbers) {
+ oldj = -1;
+ for (i = 0; i < 2; i++) {
+ j = map->map[(i?BE:TE)*wh+y*w+x];
+ if (oldj == j)
+ continue;
+ oldj = j;
+
+ xo = map->regionx[j] - 2*x;
+ yo = map->regiony[j] - 2*y;
+ if (xo >= 0 && xo <= 2 && yo >= 0 && yo <= 2) {
+ char buf[80];
+ sprintf(buf, "%d", j);
+ draw_text(dr, (COORD(x)*2+TILESIZE*xo)/2,
+ (COORD(y)*2+TILESIZE*yo)/2,
+ FONT_VARIABLE, 3*TILESIZE/5,
+ ALIGN_HCENTRE|ALIGN_VCENTRE,
+ COL_GRID, buf);
+ }
+ }
+ }
+
unclip(dr);
draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
for (x = 0; x < w; x++) {
int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
- int v;
+ unsigned long v;
if (tv < 0)
tv = FOUR;
v |= PENCIL_B_BASE << i;
}
+ if (ui->show_numbers)
+ v |= SHOW_NUMBERS;
+
ds->todraw[y*w+x] = v;
}
*/
for (y = 0; y < h; y++)
for (x = 0; x < w; x++) {
- int v = ds->todraw[y*w+x];
+ unsigned long v = ds->todraw[y*w+x];
if (ds->drawn[y*w+x] != v) {
draw_square(dr, ds, &state->p, state->map, x, y, v);
ds->drawn[y*w+x] = v;
/*
* Draw the dragged colour blob if any.
*/
- if (ui->drag_colour > -2) {
+ if ((ui->drag_colour > -2) || ui->cur_visible) {
+ int bg, iscur = 0;
+ if (ui->drag_colour >= 0)
+ bg = COL_0 + ui->drag_colour;
+ else if (ui->drag_colour == -1) {
+ bg = COL_BACKGROUND;
+ } else {
+ int r = region_from_coords(state, ds, ui->dragx, ui->dragy);
+ int c = (r < 0) ? -1 : state->colouring[r];
+ assert(ui->cur_visible);
+ /*bg = COL_GRID;*/
+ bg = (c < 0) ? COL_BACKGROUND : COL_0 + c;
+ iscur = 1;
+ }
+
ds->dragx = ui->dragx - TILESIZE/2 - 2;
ds->dragy = ui->dragy - TILESIZE/2 - 2;
blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
- draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2,
- (ui->drag_colour < 0 ? COL_BACKGROUND :
- COL_0 + ui->drag_colour), COL_GRID);
+ draw_circle(dr, ui->dragx, ui->dragy,
+ iscur ? TILESIZE/4 : TILESIZE/2, bg, COL_GRID);
+ for (i = 0; i < FOUR; i++)
+ if (ui->drag_pencil & (1 << i))
+ draw_circle(dr, ui->dragx + ((i*4+2)%10-3) * TILESIZE/10,
+ ui->dragy + (i*2-3) * TILESIZE/10,
+ TILESIZE/8, COL_0 + i, COL_0 + i);
draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
ds->drag_visible = TRUE;
}
flash_type = atoi(env);
else
flash_type = 0;
- flash_length = (flash_type == 1 ? 0.50 : 0.30);
+ flash_length = (flash_type == 1 ? 0.50F : 0.30F);
}
return flash_length;
} else
return 0.0F;
}
-static int game_wants_statusbar(void)
+static int game_status(game_state *state)
{
- return FALSE;
+ return state->completed ? +1 : 0;
}
static int game_timing_state(game_state *state, game_ui *ui)
* given tile size and then scale.
*/
game_compute_size(params, 400, &pw, &ph);
- *x = pw / 100.0;
- *y = ph / 100.0;
+ *x = pw / 100.0F;
+ *y = ph / 100.0F;
}
static void game_print(drawing *dr, game_state *state, int tilesize)
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
struct { int tilesize; } ads, *ds = &ads;
+ /* We can't call game_set_size() here because we don't want a blitter */
ads.tilesize = tilesize;
ink = print_mono_colour(dr, 0);
for (i = 0; i < FOUR; i++)
- c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0],
- map_colours[i][1], map_colours[i][2]);
+ c[i] = print_rgb_hatched_colour(dr, map_colours[i][0],
+ map_colours[i][1], map_colours[i][2],
+ map_hatching[i]);
coordsize = 0;
coords = NULL;
else
d2 = i;
}
-/* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */
+
assert(d1 != -1 && d2 != -1);
if (d1 == lastdir)
d1 = d2;
#endif
const struct game thegame = {
- "Map", "games.map",
+ "Map", "games.map", "map",
default_params,
game_fetch_preset,
decode_params,
dup_game,
free_game,
TRUE, solve_game,
- FALSE, game_text_format,
+ FALSE, game_can_format_as_text_now, game_text_format,
new_ui,
free_ui,
encode_ui,
game_redraw,
game_anim_length,
game_flash_length,
+ game_status,
TRUE, TRUE, game_print_size, game_print,
- game_wants_statusbar,
+ FALSE, /* wants_statusbar */
FALSE, game_timing_state,
- 0, /* mouse_priorities */
+ 0, /* flags */
};
+
+#ifdef STANDALONE_SOLVER
+
+int main(int argc, char **argv)
+{
+ game_params *p;
+ game_state *s;
+ char *id = NULL, *desc, *err;
+ int grade = FALSE;
+ int ret, diff, really_verbose = FALSE;
+ struct solver_scratch *sc;
+ int i;
+
+ 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);
+
+ sc = new_scratch(s->map->graph, s->map->n, s->map->ngraph);
+
+ /*
+ * 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++) {
+ for (i = 0; i < s->map->n; i++)
+ if (!s->map->immutable[i])
+ s->colouring[i] = -1;
+ ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
+ s->colouring, diff);
+ if (ret < 2)
+ break;
+ }
+
+ if (diff == DIFFCOUNT) {
+ if (grade)
+ printf("Difficulty rating: harder than Hard, or ambiguous\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", map_diffnames[diff]);
+ } else {
+ verbose = really_verbose;
+ for (i = 0; i < s->map->n; i++)
+ if (!s->map->immutable[i])
+ s->colouring[i] = -1;
+ ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
+ s->colouring, diff);
+ if (ret == 0)
+ printf("Puzzle is inconsistent\n");
+ else {
+ int col = 0;
+
+ for (i = 0; i < s->map->n; i++) {
+ printf("%5d <- %c%c", i, colnames[s->colouring[i]],
+ (col < 6 && i+1 < s->map->n ? ' ' : '\n'));
+ if (++col == 7)
+ col = 0;
+ }
+ }
+ }
+ }
+
+ return 0;
+}
+
+#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */
~mdw / sgt / puzzles / blobdiff