ref: 121f664b628c4c1d434cad6950526e5dd469f5ea
parent: e7a02ae3330d9d7f6d81d35985efee47e26f57be
author: Simon Tatham <anakin@pobox.com>
date: Tue Aug 30 15:42:45 EDT 2005
Forcing chains in Map give rise to a new `Hard' difficulty level. Also implemented the Map analogue of Solo's pencil marks, to make this mode more playable. [originally from svn r6240]
--- a/map.c
+++ b/map.c
@@ -6,9 +6,9 @@
* TODO:
*
* - clue marking
- * - more solver brains?
* - better four-colouring algorithm?
- * - pencil marks?
+ * - can we make the pencil marks look nicer?
+ * - ability to drag a set of pencil marks?
*/
#include <stdio.h>
@@ -43,6 +43,7 @@
#define DIFFLIST(A) \
A(EASY,Easy,e) \
A(NORMAL,Normal,n) \
+ A(HARD,Hard,h) \
A(RECURSE,Unreasonable,u)
#define ENUM(upper,title,lower) DIFF_ ## upper,
#define TITLE(upper,title,lower) #title,
@@ -80,7 +81,7 @@
struct game_state {game_params p;
struct map *map;
- int *colouring;
+ int *colouring, *pencil;
int completed, cheated;
};
@@ -99,7 +100,10 @@
static const struct game_params map_presets[] = { {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},};
static int game_fetch_preset(int i, char **name, game_params **params)
@@ -788,6 +792,8 @@
struct solver_scratch {unsigned char *possible; /* bitmap of colours for each region */
int *graph;
+ int *bfsqueue;
+ int *bfscolour;
int n;
int ngraph;
int depth;
@@ -803,6 +809,8 @@
sc->ngraph = ngraph;
sc->possible = snewn(n, unsigned char);
sc->depth = 0;
+ sc->bfsqueue = snewn(n, int);
+ sc->bfscolour = snewn(n, int);
return sc;
}
@@ -810,9 +818,22 @@
static void free_scratch(struct solver_scratch *sc)
{sfree(sc->possible);
+ sfree(sc->bfsqueue);
+ sfree(sc->bfscolour);
sfree(sc);
}
+/*
+ * Count the bits in a word. Only needs to cope with FOUR bits.
+ */
+static int bitcount(int word)
+{+ assert(FOUR <= 4); /* or this needs changing */
+ word = ((word & 0xA) >> 1) + (word & 0x5);
+ word = ((word & 0xC) >> 2) + (word & 0x3);
+ return word;
+}
+
static int place_colour(struct solver_scratch *sc,
int *colouring, int index, int colour)
{@@ -955,6 +976,126 @@
}
}
+ if (done_something)
+ continue;
+
+ if (difficulty < DIFF_HARD)
+ break; /* can't do anything harder */
+
+ /*
+ * Right; now we get creative. Now we're going to look for
+ * `forcing chains'. A forcing chain is a path through the
+ * graph with the following properties:
+ *
+ * (a) Each vertex on the path has precisely two possible
+ * colours.
+ *
+ * (b) Each pair of vertices which are adjacent on the
+ * path share at least one possible colour in common.
+ *
+ * (c) Each vertex in the middle of the path shares _both_
+ * of its colours with at least one of its neighbours
+ * (not the same one with both neighbours).
+ *
+ * These together imply that at least one of the possible
+ * colour choices at one end of the path forces _all_ the
+ * rest of the colours along the path. In order to make
+ * real use of this, we need further properties:
+ *
+ * (c) Ruling out some colour C from the vertex at one end
+ * of the path forces the vertex at the other end to
+ * take colour C.
+ *
+ * (d) The two end vertices are mutually adjacent to some
+ * third vertex.
+ *
+ * (e) That third vertex currently has C as a possibility.
+ *
+ * If we can find all of that lot, we can deduce that at
+ * least one of the two ends of the forcing chain has
+ * colour C, and that therefore the mutually adjacent third
+ * vertex does not.
+ *
+ * To find forcing chains, we're going to start a bfs at
+ * each suitable vertex of the graph, once for each of its
+ * two possible colours.
+ */
+ for (i = 0; i < n; i++) {+ int c;
+
+ if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2)
+ continue;
+
+ for (c = 0; c < FOUR; c++)
+ if (sc->possible[i] & (1 << c)) {+ int j, k, gi, origc, currc, head, tail;
+ /*
+ * Try a bfs from this vertex, ruling out
+ * colour c.
+ *
+ * Within this loop, we work in colour bitmaps
+ * rather than actual colours, because
+ * converting back and forth is a needless
+ * computational expense.
+ */
+
+ origc = 1 << c;
+
+ for (j = 0; j < n; j++)
+ sc->bfscolour[j] = -1;
+ head = tail = 0;
+ sc->bfsqueue[tail++] = i;
+ sc->bfscolour[i] = sc->possible[i] &~ origc;
+
+ while (head < tail) {+ j = sc->bfsqueue[head++];
+ currc = sc->bfscolour[j];
+
+ /*
+ * Try neighbours of j.
+ */
+ for (gi = graph_vertex_start(graph, n, ngraph, j);
+ gi < ngraph && graph[gi] < n*(j+1); gi++) {+ k = graph[gi] - j*n;
+
+ /*
+ * To continue with the bfs in vertex
+ * k, we need k to be
+ * (a) not already visited
+ * (b) have two possible colours
+ * (c) those colours include currc.
+ */
+
+ if (sc->bfscolour[k] < 0 &&
+ colouring[k] < 0 &&
+ bitcount(sc->possible[k]) == 2 &&
+ (sc->possible[k] & currc)) {+ sc->bfsqueue[tail++] = k;
+ sc->bfscolour[k] =
+ sc->possible[k] &~ currc;
+ }
+
+ /*
+ * One other possibility is that k
+ * might be the region in which we can
+ * make a real deduction: if it's
+ * adjacent to i, contains currc as a
+ * possibility, and currc is equal to
+ * the original colour we ruled out.
+ */
+ if (currc == origc &&
+ graph_adjacent(graph, n, ngraph, k, i) &&
+ (sc->possible[k] & currc)) {+ sc->possible[k] &= ~origc;
+ done_something = TRUE;
+ }
+ }
+ }
+
+ assert(tail <= n);
+ }
+ }
+
if (!done_something)
break;
}
@@ -1497,6 +1638,9 @@
state->colouring = snewn(n, int);
for (i = 0; i < n; i++)
state->colouring[i] = -1;
+ state->pencil = snewn(n, int);
+ for (i = 0; i < n; i++)
+ state->pencil[i] = 0;
state->completed = state->cheated = FALSE;
@@ -1801,6 +1945,8 @@
ret->p = state->p;
ret->colouring = snewn(state->p.n, int);
memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
+ ret->pencil = snewn(state->p.n, int);
+ memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int));
ret->map = state->map;
ret->map->refcount++;
ret->completed = state->completed;
@@ -1922,7 +2068,7 @@
struct game_drawstate {int tilesize;
- unsigned short *drawn, *todraw;
+ unsigned long *drawn, *todraw;
int started;
int dragx, dragy, drag_visible;
blitter *bl;
@@ -1929,8 +2075,13 @@
};
/* Flags in `drawn'. */
-#define ERR_BASE 0x0080
-#define ERR_MASK 0xFF80
+#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 TILESIZE (ds->tilesize)
#define BORDER (TILESIZE)
@@ -2000,7 +2151,11 @@
if (state->colouring[r] == c)
return ""; /* don't _need_ to change this region */
- sprintf(buf, "%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
+ if (button == RIGHT_RELEASE && state->colouring[r] >= 0)
+ return ""; /* can't pencil on a coloured region */
+
+ sprintf(buf, "%s%c:%d", (button == RIGHT_RELEASE ? "p" : ""),
+ (int)(c < 0 ? 'C' : '0' + c), r);
return dupstr(buf);
}
@@ -2014,12 +2169,30 @@
int c, k, adv, i;
while (*move) {+ int pencil = FALSE;
+
c = *move;
+ if (c == 'p') {+ pencil = TRUE;
+ c = *++move;
+ }
if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
k >= 0 && k < state->p.n) {move += 1 + adv;
- ret->colouring[k] = (c == 'C' ? -1 : c - '0');
+ if (pencil) {+ if (ret->colouring[k] >= 0) {+ free_game(ret);
+ return NULL;
+ }
+ if (c == 'C')
+ ret->pencil[k] = 0;
+ else
+ ret->pencil[k] ^= 1 << (c - '0');
+ } else {+ ret->colouring[k] = (c == 'C' ? -1 : c - '0');
+ ret->pencil[k] = 0;
+ }
} else if (*move == 'S') {move++;
ret->cheated = TRUE;
@@ -2134,10 +2307,10 @@
int i;
ds->tilesize = 0;
- ds->drawn = snewn(state->p.w * state->p.h, unsigned short);
+ ds->drawn = snewn(state->p.w * state->p.h, unsigned long);
for (i = 0; i < state->p.w * state->p.h; i++)
- ds->drawn[i] = 0xFFFF;
- ds->todraw = snewn(state->p.w * state->p.h, unsigned short);
+ ds->drawn[i] = 0xFFFFL;
+ ds->todraw = snewn(state->p.w * state->p.h, unsigned long);
ds->started = FALSE;
ds->bl = NULL;
ds->drag_visible = FALSE;
@@ -2191,10 +2364,12 @@
int x, int y, int v)
{int w = params->w, h = params->h, wh = w*h;
- int tv, bv, xo, yo, errs;
+ int tv, bv, xo, yo, errs, pencil;
errs = v & ERR_MASK;
v &= ~ERR_MASK;
+ pencil = v & PENCIL_MASK;
+ v &= ~PENCIL_MASK;
tv = v / FIVE;
bv = v % FIVE;
@@ -2225,6 +2400,39 @@
}
/*
+ * Draw `pencil marks'. Currently we arrange these in a square
+ * formation, which means we may be in trouble if the value of
+ * FOUR changes later...
+ */
+ assert(FOUR == 4);
+ for (yo = 0; yo < 4; yo++)
+ for (xo = 0; xo < 4; xo++) {+ int te = map->map[TE * wh + y*w+x];
+ int e, ee, c;
+
+ e = (yo < xo && yo < 3-xo ? TE :
+ yo > xo && yo > 3-xo ? BE :
+ xo < 2 ? LE : RE);
+ ee = map->map[e * wh + y*w+x];
+
+ c = (yo & 1) * 2 + (xo & 1);
+
+ if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
+ continue;
+
+ if (yo == xo &&
+ (map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x]))
+ continue; /* avoid TL-BR diagonal line */
+ if (yo == 3-xo &&
+ (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 the grid lines, if required.
*/
if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
@@ -2323,6 +2531,18 @@
}
v = tv * FIVE + bv;
+
+ /*
+ * Add pencil marks.
+ */
+ for (i = 0; i < FOUR; i++) {+ if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 &&
+ (state->pencil[state->map->map[TE * wh + y*w+x]] & (1<<i)))
+ v |= PENCIL_T_BASE << i;
+ if (state->colouring[state->map->map[BE * wh + y*w+x]] < 0 &&
+ (state->pencil[state->map->map[BE * wh + y*w+x]] & (1<<i)))
+ v |= PENCIL_B_BASE << i;
+ }
ds->todraw[y*w+x] = v;
}
--- a/puzzles.but
+++ b/puzzles.but
@@ -1624,8 +1624,9 @@
\IM{Map controls} controls, for Map-To colour a region, click on an existing region of the desired
-colour and drag that colour into the new region.
+To colour a region, click the left mouse button on an existing
+region of the desired colour and drag that colour into the new
+region.
(The program will always ensure the starting puzzle has at least one
region of each colour, so that this is always possible!)
@@ -1633,6 +1634,12 @@
If you need to clear a region, you can drag from an empty region, or
from the puzzle boundary if there are no empty regions left.
+Dragging a colour using the \e{right} mouse button will stipple the+region in that colour, which you can use as a note to yourself that
+you think the region \e{might} be that colour. A region can contain+stipples in multiple colours at once. (This is often useful at the
+harder difficulty levels.)
+
(All the actions described in \k{common-actions} are also available.) \H{map-parameters} \I{parameters, for Map}Map parameters@@ -1651,10 +1658,10 @@
\dt \e{Difficulty} \dd In \q{Easy} mode, there should always be at least one region-whose colour can be determined trivially. In \q{Normal} mode, you-will have to use more complex logic to deduce the colour of some
-regions. However, it will always be possible without having to
-guess or backtrack.
+whose colour can be determined trivially. In \q{Normal} and \q{Hard}+modes, you will have to use increasingly complex logic to deduce the
+colour of some regions. However, it will always be possible without
+having to guess or backtrack.
\lcont{--
⑨