*
* - 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>
{
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 n;
+ int ngraph;
+
int *bfsqueue;
int *bfscolour;
#ifdef SOLVER_DIAGNOSTICS
int *bfsprev;
#endif
- int n;
- int ngraph;
+
int depth;
};
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 %c in region %d\n", verb, colnames[colour], index);
+ printf("%*s%s %c in region %d\n", 2*sc->depth, "",
+ verb, colnames[colour], index);
#endif
/*
k = graph[j] - index*n;
#ifdef SOLVER_DIAGNOSTICS
if (verbose && (sc->possible[k] & (1 << colour)))
- printf(" ruling out %c in region %d\n", colnames[colour], k);
+ printf("%*s ruling out %c in region %d\n", 2*sc->depth, "",
+ colnames[colour], k);
#endif
sc->possible[k] &= ~(1 << colour);
}
{
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]
+ /*
+ * 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:"
+ , "initial clue:"
#endif
- ))
- return 0; /* the clues aren't even consistent! */
- }
+ )) {
+#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
+ ret = place_colour(sc, colouring, i, c
#ifdef SOLVER_DIAGNOSTICS
- , "placing"
+ , "placing"
#endif
- ))
- return 0; /* found puzzle to be inconsistent */
+ );
+ /*
+ * 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;
}
}
if (verbose) {
char buf[80];
if (!started)
- printf("adjacent regions %d,%d share colours %s\n",
- j1, j2, colourset(buf, v));
+ printf("%*sadjacent regions %d,%d share colours"
+ " %s\n", 2*sc->depth, "", j1, j2,
+ colourset(buf, v));
started = TRUE;
- printf(" ruling out %s in region %d\n",
- colourset(buf, sc->possible[k] & v), k);
+ printf("%*s ruling out %s in region %d\n",2*sc->depth,
+ "", colourset(buf, sc->possible[k] & v), k);
}
#endif
sc->possible[k] &= ~v;
char buf[80], *sep = "";
int r;
- printf("forcing chain, colour %s, ",
+ 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 ruling out %s in region %d\n",
+ printf("\n%*s ruling out %s in region"
+ " %d\n", 2*sc->depth, "",
colourset(buf, origc), k);
}
#endif
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(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;
* 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;
sfree(state->map->regiony);
sfree(state->map);
}
+ sfree(state->pencil);
sfree(state->colouring);
sfree(state);
}
}
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;
};
static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
int x, int y, int button)
{
- char buf[80];
+ char *bufp, buf[256];
/*
* Enable or disable numeric labels on regions.
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;
return "";
ui->drag_colour > -2) {
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.
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 (button == RIGHT_RELEASE) {
+ 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. */
+ }
+
+ 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);
+ }
- sprintf(buf, "%s%c:%d", (button == RIGHT_RELEASE ? "p" : ""),
- (int)(c < 0 ? 'C' : '0' + c), r);
- return dupstr(buf);
+ return dupstr(buf+1); /* ignore first semicolon */
}
return NULL;
{
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, i, j, oldj;
- int show_numbers;
+ int tv, bv, xo, yo, i, j, oldj;
+ unsigned long errs, pencil, show_numbers;
errs = v & ERR_MASK;
v &= ~ERR_MASK;
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);
}
/*
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;
*/
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_circle(dr, ui->dragx, ui->dragy, TILESIZE/2,
(ui->drag_colour < 0 ? COL_BACKGROUND :
COL_0 + ui->drag_colour), 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;
}
return 0.0F;
}
-static int game_wants_statusbar(void)
-{
- return FALSE;
-}
-
static int game_timing_state(game_state *state, game_ui *ui)
{
return TRUE;
/* 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);
#endif
const struct game thegame = {
- "Map", "games.map",
+ "Map", "games.map", "map",
default_params,
game_fetch_preset,
decode_params,
game_anim_length,
game_flash_length,
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
-#include <stdarg.h>
-
-void frontend_default_colour(frontend *fe, float *output) {}
-void draw_text(drawing *dr, int x, int y, int fonttype, int fontsize,
- int align, int colour, char *text) {}
-void draw_rect(drawing *dr, int x, int y, int w, int h, int colour) {}
-void draw_line(drawing *dr, int x1, int y1, int x2, int y2, int colour) {}
-void draw_polygon(drawing *dr, int *coords, int npoints,
- int fillcolour, int outlinecolour) {}
-void draw_circle(drawing *dr, int cx, int cy, int radius,
- int fillcolour, int outlinecolour) {}
-void clip(drawing *dr, int x, int y, int w, int h) {}
-void unclip(drawing *dr) {}
-void start_draw(drawing *dr) {}
-void draw_update(drawing *dr, int x, int y, int w, int h) {}
-void end_draw(drawing *dr) {}
-blitter *blitter_new(drawing *dr, int w, int h) {return NULL;}
-void blitter_free(drawing *dr, blitter *bl) {}
-void blitter_save(drawing *dr, blitter *bl, int x, int y) {}
-void blitter_load(drawing *dr, blitter *bl, int x, int y) {}
-int print_mono_colour(drawing *dr, int grey) { return 0; }
-int print_rgb_colour(drawing *dr, int hatch, float r, float g, float b)
-{ return 0; }
-void print_line_width(drawing *dr, int width) {}
-
-void fatal(char *fmt, ...)
-{
- va_list ap;
-
- fprintf(stderr, "fatal error: ");
-
- va_start(ap, fmt);
- vfprintf(stderr, fmt, ap);
- va_end(ap);
-
- fprintf(stderr, "\n");
- exit(1);
-}
-
int main(int argc, char **argv)
{
game_params *p;
~mdw / sgt / puzzles / blobdiff