summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/map.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/map.c')
-rw-r--r--apps/plugins/puzzles/map.c3340
1 files changed, 0 insertions, 3340 deletions
diff --git a/apps/plugins/puzzles/map.c b/apps/plugins/puzzles/map.c
deleted file mode 100644
index 6e9c125..0000000
--- a/apps/plugins/puzzles/map.c
+++ /dev/null
@@ -1,3340 +0,0 @@
-/*
- * map.c: Game involving four-colouring a map.
- */
-
-/*
- * TODO:
- *
- * - clue marking
- * - better four-colouring algorithm?
- */
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include "rbassert.h"
-#include <ctype.h>
-#include <math.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 :-)
- */
-#define FOUR 4
-#define THREE (FOUR-1)
-#define FIVE (FOUR+1)
-#define SIX (FOUR+2)
-
-/*
- * Ghastly run-time configuration option, just for Gareth (again).
- */
-static int flash_type = -1;
-static float flash_length;
-
-/*
- * Difficulty levels. I do some macro ickery here to ensure that my
- * enum and the various forms of my name list always match up.
- */
-#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,
-#define ENCODE(upper,title,lower) #lower
-#define CONFIG(upper,title,lower) ":" #title
-enum { DIFFLIST(ENUM) DIFFCOUNT };
-static char const *const map_diffnames[] = { DIFFLIST(TITLE) };
-static char const map_diffchars[] = DIFFLIST(ENCODE);
-#define DIFFCONFIG DIFFLIST(CONFIG)
-
-enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */
-
-enum {
- COL_BACKGROUND,
- COL_GRID,
- COL_0, COL_1, COL_2, COL_3,
- COL_ERROR, COL_ERRTEXT,
- NCOLOURS
-};
-
-struct game_params {
- int w, h, n, diff;
-};
-
-struct map {
- int refcount;
- int *map;
- int *graph;
- int n;
- int ngraph;
- int *immutable;
- 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 p;
- struct map *map;
- int *colouring, *pencil;
- int completed, cheated;
-};
-
-static game_params *default_params(void)
-{
- 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;
-
- return ret;
-}
-
-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)
-{
- game_params *ret;
- char str[80];
-
- if (i < 0 || i >= lenof(map_presets))
- return FALSE;
-
- ret = snew(game_params);
- *ret = map_presets[i];
-
- sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
- map_diffnames[ret->diff]);
-
- *name = dupstr(str);
- *params = ret;
- return TRUE;
-}
-
-static void free_params(game_params *params)
-{
- sfree(params);
-}
-
-static game_params *dup_params(const game_params *params)
-{
- game_params *ret = snew(game_params);
- *ret = *params; /* structure copy */
- return ret;
-}
-
-static void decode_params(game_params *params, char const *string)
-{
- char const *p = string;
-
- params->w = atoi(p);
- while (*p && isdigit((unsigned char)*p)) p++;
- if (*p == 'x') {
- p++;
- params->h = atoi(p);
- while (*p && isdigit((unsigned char)*p)) p++;
- } else {
- params->h = params->w;
- }
- if (*p == 'n') {
- p++;
- params->n = atoi(p);
- while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
- } else {
- params->n = params->w * params->h / 8;
- }
- if (*p == 'd') {
- int i;
- p++;
- for (i = 0; i < DIFFCOUNT; i++)
- if (*p == map_diffchars[i])
- params->diff = i;
- if (*p) p++;
- }
-}
-
-static char *encode_params(const game_params *params, int full)
-{
- char ret[400];
-
- sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
- if (full)
- sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
-
- return dupstr(ret);
-}
-
-static config_item *game_configure(const game_params *params)
-{
- config_item *ret;
- char buf[80];
-
- ret = snewn(5, config_item);
-
- ret[0].name = "Width";
- ret[0].type = C_STRING;
- sprintf(buf, "%d", params->w);
- ret[0].sval = dupstr(buf);
- ret[0].ival = 0;
-
- ret[1].name = "Height";
- ret[1].type = C_STRING;
- sprintf(buf, "%d", params->h);
- ret[1].sval = dupstr(buf);
- ret[1].ival = 0;
-
- ret[2].name = "Regions";
- ret[2].type = C_STRING;
- sprintf(buf, "%d", params->n);
- ret[2].sval = dupstr(buf);
- ret[2].ival = 0;
-
- ret[3].name = "Difficulty";
- ret[3].type = C_CHOICES;
- ret[3].sval = DIFFCONFIG;
- ret[3].ival = params->diff;
-
- ret[4].name = NULL;
- ret[4].type = C_END;
- ret[4].sval = NULL;
- ret[4].ival = 0;
-
- return ret;
-}
-
-static game_params *custom_params(const config_item *cfg)
-{
- game_params *ret = snew(game_params);
-
- ret->w = atoi(cfg[0].sval);
- ret->h = atoi(cfg[1].sval);
- ret->n = atoi(cfg[2].sval);
- ret->diff = cfg[3].ival;
-
- return ret;
-}
-
-static char *validate_params(const game_params *params, int full)
-{
- if (params->w < 2 || params->h < 2)
- return "Width and height must be at least two";
- if (params->n < 5)
- return "Must have at least five regions";
- if (params->n > params->w * params->h)
- return "Too many regions to fit in grid";
- return NULL;
-}
-
-/* ----------------------------------------------------------------------
- * Cumulative frequency table functions.
- */
-
-/*
- * Initialise a cumulative frequency table. (Hardly worth writing
- * this function; all it does is to initialise everything in the
- * array to zero.)
- */
-static void cf_init(int *table, int n)
-{
- int i;
-
- for (i = 0; i < n; i++)
- table[i] = 0;
-}
-
-/*
- * Increment the count of symbol `sym' by `count'.
- */
-static void cf_add(int *table, int n, int sym, int count)
-{
- int bit;
-
- bit = 1;
- while (sym != 0) {
- if (sym & bit) {
- table[sym] += count;
- sym &= ~bit;
- }
- bit <<= 1;
- }
-
- table[0] += count;
-}
-
-/*
- * Cumulative frequency lookup: return the total count of symbols
- * with value less than `sym'.
- */
-static int cf_clookup(int *table, int n, int sym)
-{
- int bit, index, limit, count;
-
- if (sym == 0)
- return 0;
-
- assert(0 < sym && sym <= n);
-
- count = table[0]; /* start with the whole table size */
-
- bit = 1;
- while (bit < n)
- bit <<= 1;
-
- limit = n;
-
- while (bit > 0) {
- /*
- * Find the least number with its lowest set bit in this
- * position which is greater than or equal to sym.
- */
- index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
-
- if (index < limit) {
- count -= table[index];
- limit = index;
- }
-
- bit >>= 1;
- }
-
- return count;
-}
-
-/*
- * Single frequency lookup: return the count of symbol `sym'.
- */
-static int cf_slookup(int *table, int n, int sym)
-{
- int count, bit;
-
- assert(0 <= sym && sym < n);
-
- count = table[sym];
-
- for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
- count -= table[sym+bit];
-
- return count;
-}
-
-/*
- * Return the largest symbol index such that the cumulative
- * frequency up to that symbol is less than _or equal to_ count.
- */
-static int cf_whichsym(int *table, int n, int count) {
- int bit, sym, top;
-
- assert(count >= 0 && count < table[0]);
-
- bit = 1;
- while (bit < n)
- bit <<= 1;
-
- sym = 0;
- top = table[0];
-
- while (bit > 0) {
- if (sym+bit < n) {
- if (count >= top - table[sym+bit])
- sym += bit;
- else
- top -= table[sym+bit];
- }
-
- bit >>= 1;
- }
-
- return sym;
-}
-
-/* ----------------------------------------------------------------------
- * Map generation.
- *
- * FIXME: this isn't entirely optimal at present, because it
- * inherently prioritises growing the largest region since there
- * are more squares adjacent to it. This acts as a destabilising
- * influence leading to a few large regions and mostly small ones.
- * It might be better to do it some other way.
- */
-
-#define WEIGHT_INCREASED 2 /* for increased perimeter */
-#define WEIGHT_DECREASED 4 /* for decreased perimeter */
-#define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
-
-/*
- * Look at a square and decide which colours can be extended into
- * it.
- *
- * If called with index < 0, it adds together one of
- * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
- * colour that has a valid extension (according to the effect that
- * it would have on the perimeter of the region being extended) and
- * returns the overall total.
- *
- * If called with index >= 0, it returns one of the possible
- * colours depending on the value of index, in such a way that the
- * number of possible inputs which would give rise to a given
- * return value correspond to the weight of that value.
- */
-static int extend_options(int w, int h, int n, int *map,
- int x, int y, int index)
-{
- int c, i, dx, dy;
- int col[8];
- int total = 0;
-
- if (map[y*w+x] >= 0) {
- assert(index < 0);
- return 0; /* can't do this square at all */
- }
-
- /*
- * Fetch the eight neighbours of this square, in order around
- * the square.
- */
- for (dy = -1; dy <= +1; dy++)
- for (dx = -1; dx <= +1; dx++) {
- int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx));
- if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h)
- col[index] = map[(y+dy)*w+(x+dx)];
- else
- col[index] = -1;
- }
-
- /*
- * Iterate over each colour that might be feasible.
- *
- * FIXME: this routine currently has O(n) running time. We
- * could turn it into O(FOUR) by only bothering to iterate over
- * the colours mentioned in the four neighbouring squares.
- */
-
- for (c = 0; c < n; c++) {
- int count, neighbours, runs;
-
- /*
- * One of the even indices of col (representing the
- * orthogonal neighbours of this square) must be equal to
- * c, or else this square is not adjacent to region c and
- * obviously cannot become an extension of it at this time.
- */
- neighbours = 0;
- for (i = 0; i < 8; i += 2)
- if (col[i] == c)
- neighbours++;
- if (!neighbours)
- continue;
-
- /*
- * Now we know this square is adjacent to region c. The
- * next question is, would extending it cause the region to
- * become non-simply-connected? If so, we mustn't do it.
- *
- * We determine this by looking around col to see if we can
- * find more than one separate run of colour c.
- */
- runs = 0;
- for (i = 0; i < 8; i++)
- if (col[i] == c && col[(i+1) & 7] != c)
- runs++;
- if (runs > 1)
- continue;
-
- assert(runs == 1);
-
- /*
- * This square is a possibility. Determine its effect on
- * the region's perimeter (computed from the number of
- * orthogonal neighbours - 1 means a perimeter increase, 3
- * a decrease, 2 no change; 4 is impossible because the
- * region would already not be simply connected) and we're
- * done.
- */
- assert(neighbours > 0 && neighbours < 4);
- count = (neighbours == 1 ? WEIGHT_INCREASED :
- neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);
-
- total += count;
- if (index >= 0 && index < count)
- return c;
- else
- index -= count;
- }
-
- assert(index < 0);
-
- return total;
-}
-
-static void genmap(int w, int h, int n, int *map, random_state *rs)
-{
- int wh = w*h;
- int x, y, i, k;
- int *tmp;
-
- assert(n <= wh);
- tmp = snewn(wh, int);
-
- /*
- * Clear the map, and set up `tmp' as a list of grid indices.
- */
- for (i = 0; i < wh; i++) {
- map[i] = -1;
- tmp[i] = i;
- }
-
- /*
- * Place the region seeds by selecting n members from `tmp'.
- */
- k = wh;
- for (i = 0; i < n; i++) {
- int j = random_upto(rs, k);
- map[tmp[j]] = i;
- tmp[j] = tmp[--k];
- }
-
- /*
- * Re-initialise `tmp' as a cumulative frequency table. This
- * will store the number of possible region colours we can
- * extend into each square.
- */
- cf_init(tmp, wh);
-
- /*
- * Go through the grid and set up the initial cumulative
- * frequencies.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++)
- cf_add(tmp, wh, y*w+x,
- extend_options(w, h, n, map, x, y, -1));
-
- /*
- * Now repeatedly choose a square we can extend a region into,
- * and do so.
- */
- while (tmp[0] > 0) {
- int k = random_upto(rs, tmp[0]);
- int sq;
- int colour;
- int xx, yy;
-
- sq = cf_whichsym(tmp, wh, k);
- k -= cf_clookup(tmp, wh, sq);
- x = sq % w;
- y = sq / w;
- colour = extend_options(w, h, n, map, x, y, k);
-
- map[sq] = colour;
-
- /*
- * Re-scan the nine cells around the one we've just
- * modified.
- */
- for (yy = max(y-1, 0); yy < min(y+2, h); yy++)
- for (xx = max(x-1, 0); xx < min(x+2, w); xx++) {
- cf_add(tmp, wh, yy*w+xx,
- -cf_slookup(tmp, wh, yy*w+xx) +
- extend_options(w, h, n, map, xx, yy, -1));
- }
- }
-
- /*
- * Finally, go through and normalise the region labels into
- * order, meaning that indistinguishable maps are actually
- * identical.
- */
- for (i = 0; i < n; i++)
- tmp[i] = -1;
- k = 0;
- for (i = 0; i < wh; i++) {
- assert(map[i] >= 0);
- if (tmp[map[i]] < 0)
- tmp[map[i]] = k++;
- map[i] = tmp[map[i]];
- }
-
- sfree(tmp);
-}
-
-/* ----------------------------------------------------------------------
- * Functions to handle graphs.
- */
-
-/*
- * Having got a map in a square grid, convert it into a graph
- * representation.
- */
-static int gengraph(int w, int h, int n, int *map, int *graph)
-{
- int i, j, x, y;
-
- /*
- * Start by setting the graph up as an adjacency matrix. We'll
- * turn it into a list later.
- */
- for (i = 0; i < n*n; i++)
- graph[i] = 0;
-
- /*
- * Iterate over the map looking for all adjacencies.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- int v, vx, vy;
- v = map[y*w+x];
- if (x+1 < w && (vx = map[y*w+(x+1)]) != v)
- graph[v*n+vx] = graph[vx*n+v] = 1;
- if (y+1 < h && (vy = map[(y+1)*w+x]) != v)
- graph[v*n+vy] = graph[vy*n+v] = 1;
- }
-
- /*
- * Turn the matrix into a list.
- */
- for (i = j = 0; i < n*n; i++)
- if (graph[i])
- graph[j++] = i;
-
- return j;
-}
-
-static int graph_edge_index(int *graph, int n, int ngraph, int i, int j)
-{
- int v = i*n+j;
- int top, bot, mid;
-
- bot = -1;
- top = ngraph;
- while (top - bot > 1) {
- mid = (top + bot) / 2;
- if (graph[mid] == v)
- return mid;
- else if (graph[mid] < v)
- bot = mid;
- else
- top = mid;
- }
- return -1;
-}
-
-#define graph_adjacent(graph, n, ngraph, i, j) \
- (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)
-
-static int graph_vertex_start(int *graph, int n, int ngraph, int i)
-{
- int v = i*n;
- int top, bot, mid;
-
- bot = -1;
- top = ngraph;
- while (top - bot > 1) {
- mid = (top + bot) / 2;
- if (graph[mid] < v)
- bot = mid;
- else
- top = mid;
- }
- return top;
-}
-
-/* ----------------------------------------------------------------------
- * Generate a four-colouring of a graph.
- *
- * FIXME: it would be nice if we could convert this recursion into
- * pseudo-recursion using some sort of explicit stack array, for
- * the sake of the Palm port and its limited stack.
- */
-
-static int fourcolour_recurse(int *graph, int n, int ngraph,
- int *colouring, int *scratch, random_state *rs)
-{
- int nfree, nvert, start, i, j, k, c, ci;
- int cs[FOUR];
-
- /*
- * Find the smallest number of free colours in any uncoloured
- * vertex, and count the number of such vertices.
- */
-
- nfree = FIVE; /* start off bigger than FOUR! */
- nvert = 0;
- for (i = 0; i < n; i++)
- if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) {
- if (nfree > scratch[i*FIVE+FOUR]) {
- nfree = scratch[i*FIVE+FOUR];
- nvert = 0;
- }
- nvert++;
- }
-
- /*
- * If there aren't any uncoloured vertices at all, we're done.
- */
- if (nvert == 0)
- return TRUE; /* we've got a colouring! */
-
- /*
- * Pick a random vertex in that set.
- */
- j = random_upto(rs, nvert);
- for (i = 0; i < n; i++)
- if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
- if (j-- == 0)
- break;
- assert(i < n);
- start = graph_vertex_start(graph, n, ngraph, i);
-
- /*
- * Loop over the possible colours for i, and recurse for each
- * one.
- */
- ci = 0;
- for (c = 0; c < FOUR; c++)
- if (scratch[i*FIVE+c] == 0)
- cs[ci++] = c;
- shuffle(cs, ci, sizeof(*cs), rs);
-
- while (ci-- > 0) {
- c = cs[ci];
-
- /*
- * Fill in this colour.
- */
- colouring[i] = c;
-
- /*
- * Update the scratch space to reflect a new neighbour
- * of this colour for each neighbour of vertex i.
- */
- for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
- k = graph[j] - i*n;
- if (scratch[k*FIVE+c] == 0)
- scratch[k*FIVE+FOUR]--;
- scratch[k*FIVE+c]++;
- }
-
- /*
- * Recurse.
- */
- if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
- return TRUE; /* got one! */
-
- /*
- * If that didn't work, clean up and try again with a
- * different colour.
- */
- for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
- k = graph[j] - i*n;
- scratch[k*FIVE+c]--;
- if (scratch[k*FIVE+c] == 0)
- scratch[k*FIVE+FOUR]++;
- }
- colouring[i] = -1;
- }
-
- /*
- * If we reach here, we were unable to find a colouring at all.
- * (This doesn't necessarily mean the Four Colour Theorem is
- * violated; it might just mean we've gone down a dead end and
- * need to back up and look somewhere else. It's only an FCT
- * violation if we get all the way back up to the top level and
- * still fail.)
- */
- return FALSE;
-}
-
-static void fourcolour(int *graph, int n, int ngraph, int *colouring,
- random_state *rs)
-{
- int *scratch;
- int i;
-
- /*
- * For each vertex and each colour, we store the number of
- * neighbours that have that colour. Also, we store the number
- * of free colours for the vertex.
- */
- scratch = snewn(n * FIVE, int);
- for (i = 0; i < n * FIVE; i++)
- scratch[i] = (i % FIVE == FOUR ? FOUR : 0);
-
- /*
- * Clear the colouring to start with.
- */
- for (i = 0; i < n; i++)
- colouring[i] = -1;
-
- i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
- assert(i); /* by the Four Colour Theorem :-) */
-
- sfree(scratch);
-}
-
-/* ----------------------------------------------------------------------
- * Non-recursive solver.
- */
-
-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 depth;
-};
-
-static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
-{
- struct solver_scratch *sc;
-
- sc = snew(struct solver_scratch);
- sc->graph = graph;
- sc->n = n;
- sc->ngraph = ngraph;
- sc->possible = snewn(n, unsigned char);
- sc->depth = 0;
- sc->bfsqueue = snewn(n, int);
- sc->bfscolour = snewn(n, int);
-#ifdef SOLVER_DIAGNOSTICS
- sc->bfsprev = snewn(n, int);
-#endif
-
- return sc;
-}
-
-static void free_scratch(struct solver_scratch *sc)
-{
- sfree(sc->possible);
- sfree(sc->bfsqueue);
- sfree(sc->bfscolour);
-#ifdef SOLVER_DIAGNOSTICS
- sfree(sc->bfsprev);
-#endif
- 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;
-}
-
-#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
-#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))) {
-#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
- * difficult).
- */
-static int map_solver(struct solver_scratch *sc,
- int *graph, int n, int ngraph, int *colouring,
- int difficulty)
-{
- int i;
-
- 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]
-#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.
- */
- while (1) {
- int done_something = FALSE;
-
- if (difficulty < DIFF_EASY)
- break; /* can't do anything at all! */
-
- /*
- * Simplest possible deduction: find a region with only one
- * possible colour.
- */
- for (i = 0; i < n; i++) if (colouring[i] < 0) {
- int p = sc->possible[i];
-
- 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, ret;
- for (c = 0; c < FOUR; c++)
- if (p == (1 << c))
- break;
- assert(c < FOUR);
- 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;
- }
- }
-
- if (done_something)
- continue;
-
- if (difficulty < DIFF_NORMAL)
- break; /* can't do anything harder */
-
- /*
- * Failing that, go up one level. Look for pairs of regions
- * which (a) both have the same pair of possible colours,
- * (b) are adjacent to one another, (c) are adjacent to the
- * same region, and (d) that region still thinks it has one
- * or both of those possible colours.
- *
- * Simplest way to do this is by going through the graph
- * edge by edge, so that we start with property (b) and
- * then look for (a) and finally (c) and (d).
- */
- 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 */
-
- if (colouring[j1] >= 0 || colouring[j2] >= 0)
- continue; /* they're not undecided */
-
- if (sc->possible[j1] != sc->possible[j2])
- continue; /* they don't have the same possibles */
-
- v = sc->possible[j1];
- /*
- * See if v contains exactly two set bits.
- */
- v2 = v & -v; /* find lowest set bit */
- v2 = v & ~v2; /* clear it */
- if (v2 == 0 || (v2 & (v2-1)) != 0) /* not power of 2 */
- continue;
-
- /*
- * We've found regions j1 and j2 satisfying properties
- * (a) and (b): they have two possible colours between
- * them, and since they're adjacent to one another they
- * must use _both_ those colours between them.
- * Therefore, if they are both adjacent to any other
- * region then that region cannot be either colour.
- *
- * Go through the neighbours of j1 and see if any are
- * shared with j2.
- */
- for (j = graph_vertex_start(graph, n, ngraph, j1);
- j < ngraph && graph[j] < n*(j1+1); j++) {
- 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;
- }
- }
- }
-
- 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;
-#ifdef SOLVER_DIAGNOSTICS
- sc->bfsprev[j] = -1;
-#endif
- }
- 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;
-#ifdef SOLVER_DIAGNOSTICS
- sc->bfsprev[k] = j;
-#endif
- }
-
- /*
- * 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)) {
-#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;
- }
- }
- }
-
- assert(tail <= n);
- }
- }
-
- if (!done_something)
- break;
- }
-
- /*
- * See if we've got a complete solution, and return if so.
- */
- for (i = 0; i < n; i++)
- if (colouring[i] < 0)
- break;
- 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) {
-#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
- * currently-most-constrained region.
- */
- {
- int best, bestc;
- struct solver_scratch *rsc;
- int *subcolouring, *origcolouring;
- int ret, subret;
- int we_already_got_one;
-
- best = -1;
- bestc = FIVE;
-
- for (i = 0; i < n; i++) if (colouring[i] < 0) {
- int p = sc->possible[i];
- enum { compile_time_assertion = 1 / (FOUR <= 4) };
- int c;
-
- /* Count the set bits. */
- c = (p & 5) + ((p >> 1) & 5);
- c = (c & 3) + ((c >> 2) & 3);
- assert(c > 1); /* or colouring[i] would be >= 0 */
-
- if (c < bestc) {
- best = i;
- bestc = c;
- }
- }
-
- 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.
- */
- rsc = new_scratch(graph, n, ngraph);
- rsc->depth = sc->depth + 1;
- origcolouring = snewn(n, int);
- memcpy(origcolouring, colouring, n * sizeof(int));
- subcolouring = snewn(n, int);
- we_already_got_one = FALSE;
- ret = 0;
-
- for (i = 0; i < FOUR; i++) {
- if (!(sc->possible[best] & (1 << i)))
- continue;
-
- memcpy(rsc->possible, sc->possible, n);
- memcpy(subcolouring, origcolouring, n * sizeof(int));
-
- 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
- * one, we're definitely ambiguous.
- */
- if (subret == 2 || (subret == 1 && we_already_got_one)) {
- ret = 2;
- break;
- }
-
- /*
- * If this possibility turned up one valid solution and
- * it's the first we've seen, copy it into the output.
- */
- if (subret == 1) {
- memcpy(colouring, subcolouring, n * sizeof(int));
- we_already_got_one = TRUE;
- ret = 1;
- }
-
- /*
- * Otherwise, this guess led to a contradiction, so we
- * do nothing.
- */
- }
-
- 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;
- }
-}
-
-/* ----------------------------------------------------------------------
- * Game generation main function.
- */
-
-static char *new_game_desc(const game_params *params, random_state *rs,
- char **aux, int interactive)
-{
- struct solver_scratch *sc = NULL;
- int *map, *graph, ngraph, *colouring, *colouring2, *regions;
- int i, j, w, h, n, solveret, cfreq[FOUR];
- int wh;
- int mindiff, tries;
-#ifdef GENERATION_DIAGNOSTICS
- int x, y;
-#endif
- char *ret, buf[80];
- int retlen, retsize;
-
- w = params->w;
- h = params->h;
- n = params->n;
- wh = w*h;
-
- *aux = NULL;
-
- map = snewn(wh, int);
- graph = snewn(n*n, int);
- colouring = snewn(n, int);
- colouring2 = snewn(n, int);
- regions = snewn(n, int);
-
- /*
- * This is the minimum difficulty below which we'll completely
- * reject a map design. Normally we set this to one below the
- * requested difficulty, ensuring that we have the right
- * result. However, for particularly dense maps or maps with
- * particularly few regions it might not be possible to get the
- * desired difficulty, so we will eventually drop this down to
- * -1 to indicate that any old map will do.
- */
- mindiff = params->diff;
- tries = 50;
-
- while (1) {
-
- /*
- * Create the map.
- */
- genmap(w, h, n, map, rs);
-
-#ifdef GENERATION_DIAGNOSTICS
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- int v = map[y*w+x];
- if (v >= 62)
- putchar('!');
- else if (v >= 36)
- putchar('a' + v-36);
- else if (v >= 10)
- putchar('A' + v-10);
- else
- putchar('0' + v);
- }
- putchar('\n');
- }
-#endif
-
- /*
- * Convert the map into a graph.
- */
- ngraph = gengraph(w, h, n, map, graph);
-
-#ifdef GENERATION_DIAGNOSTICS
- for (i = 0; i < ngraph; i++)
- printf("%d-%d\n", graph[i]/n, graph[i]%n);
-#endif
-
- /*
- * Colour the map.
- */
- fourcolour(graph, n, ngraph, colouring, rs);
-
-#ifdef GENERATION_DIAGNOSTICS
- for (i = 0; i < n; i++)
- printf("%d: %d\n", i, colouring[i]);
-
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- int v = colouring[map[y*w+x]];
- if (v >= 36)
- putchar('a' + v-36);
- else if (v >= 10)
- putchar('A' + v-10);
- else
- putchar('0' + v);
- }
- putchar('\n');
- }
-#endif
-
- /*
- * Encode the solution as an aux string.
- */
- if (*aux) /* in case we've come round again */
- sfree(*aux);
- retlen = retsize = 0;
- ret = NULL;
- for (i = 0; i < n; i++) {
- int len;
-
- if (colouring[i] < 0)
- continue;
-
- len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i);
- if (retlen + len >= retsize) {
- retsize = retlen + len + 256;
- ret = sresize(ret, retsize, char);
- }
- strcpy(ret + retlen, buf);
- retlen += len;
- }
- *aux = ret;
-
- /*
- * Remove the region colours one by one, keeping
- * solubility. Also ensure that there always remains at
- * least one region of every colour, so that the user can
- * drag from somewhere.
- */
- for (i = 0; i < FOUR; i++)
- cfreq[i] = 0;
- for (i = 0; i < n; i++) {
- regions[i] = i;
- cfreq[colouring[i]]++;
- }
- for (i = 0; i < FOUR; i++)
- if (cfreq[i] == 0)
- continue;
-
- shuffle(regions, n, sizeof(*regions), rs);
-
- if (sc) free_scratch(sc);
- sc = new_scratch(graph, n, ngraph);
-
- for (i = 0; i < n; i++) {
- j = regions[i];
-
- if (cfreq[colouring[j]] == 1)
- continue; /* can't remove last region of colour */
-
- memcpy(colouring2, colouring, n*sizeof(int));
- colouring2[j] = -1;
- solveret = map_solver(sc, graph, n, ngraph, colouring2,
- params->diff);
- assert(solveret >= 0); /* mustn't be impossible! */
- if (solveret == 1) {
- cfreq[colouring[j]]--;
- colouring[j] = -1;
- }
- }
-
-#ifdef GENERATION_DIAGNOSTICS
- for (i = 0; i < n; i++)
- if (colouring[i] >= 0) {
- if (i >= 62)
- putchar('!');
- else if (i >= 36)
- putchar('a' + i-36);
- else if (i >= 10)
- putchar('A' + i-10);
- else
- putchar('0' + i);
- printf(": %d\n", colouring[i]);
- }
-#endif
-
- /*
- * Finally, check that the puzzle is _at least_ as hard as
- * required, and indeed that it isn't already solved.
- * (Calling map_solver with negative difficulty ensures the
- * latter - if a solver which _does nothing_ can solve it,
- * it's too easy!)
- */
- memcpy(colouring2, colouring, n*sizeof(int));
- if (map_solver(sc, graph, n, ngraph, colouring2,
- mindiff - 1) == 1) {
- /*
- * Drop minimum difficulty if necessary.
- */
- if (mindiff > 0 && (n < 9 || n > 2*wh/3)) {
- if (tries-- <= 0)
- mindiff = 0; /* give up and go for Easy */
- }
- continue;
- }
-
- break;
- }
-
- /*
- * Encode as a game ID. We do this by:
- *
- * - first going along the horizontal edges row by row, and
- * then the vertical edges column by column
- * - encoding the lengths of runs of edges and runs of
- * non-edges
- * - the decoder will reconstitute the region boundaries from
- * this and automatically number them the same way we did
- * - then we encode the initial region colours in a Slant-like
- * fashion (digits 0-3 interspersed with letters giving
- * lengths of runs of empty spaces).
- */
- retlen = retsize = 0;
- ret = NULL;
-
- {
- int run, pv;
-
- /*
- * Start with a notional non-edge, so that there'll be an
- * explicit `a' to distinguish the case where we start with
- * an edge.
- */
- run = 1;
- pv = 0;
-
- for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
- int x, y, dx, dy, v;
-
- if (i < w*(h-1)) {
- /* Horizontal edge. */
- y = i / w;
- x = i % w;
- dx = 0;
- dy = 1;
- } else {
- /* Vertical edge. */
- x = (i - w*(h-1)) / h;
- y = (i - w*(h-1)) % h;
- dx = 1;
- dy = 0;
- }
-
- if (retlen + 10 >= retsize) {
- retsize = retlen + 256;
- ret = sresize(ret, retsize, char);
- }
-
- v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);
-
- if (pv != v) {
- ret[retlen++] = 'a'-1 + run;
- run = 1;
- pv = v;
- } else {
- /*
- * 'z' is a special case in this encoding. Rather
- * than meaning a run of 26 and a state switch, it
- * means a run of 25 and _no_ state switch, because
- * otherwise there'd be no way to encode runs of
- * more than 26.
- */
- if (run == 25) {
- ret[retlen++] = 'z';
- run = 0;
- }
- run++;
- }
- }
-
- ret[retlen++] = 'a'-1 + run;
- ret[retlen++] = ',';
-
- run = 0;
- for (i = 0; i < n; i++) {
- if (retlen + 10 >= retsize) {
- retsize = retlen + 256;
- ret = sresize(ret, retsize, char);
- }
-
- if (colouring[i] < 0) {
- /*
- * In _this_ encoding, 'z' is a run of 26, since
- * there's no implicit state switch after each run.
- * Confusingly different, but more compact.
- */
- if (run == 26) {
- ret[retlen++] = 'z';
- run = 0;
- }
- run++;
- } else {
- if (run > 0)
- ret[retlen++] = 'a'-1 + run;
- ret[retlen++] = '0' + colouring[i];
- run = 0;
- }
- }
- if (run > 0)
- ret[retlen++] = 'a'-1 + run;
- ret[retlen] = '\0';
-
- assert(retlen < retsize);
- }
-
- free_scratch(sc);
- sfree(regions);
- sfree(colouring2);
- sfree(colouring);
- sfree(graph);
- sfree(map);
-
- return ret;
-}
-
-static char *parse_edge_list(const game_params *params, const char **desc,
- int *map)
-{
- int w = params->w, h = params->h, wh = w*h, n = params->n;
- int i, k, pos, state;
- const char *p = *desc;
-
- dsf_init(map+wh, wh);
-
- pos = -1;
- state = 0;
-
- /*
- * Parse the game description to get the list of edges, and
- * build up a disjoint set forest as we go (by identifying
- * pairs of squares whenever the edge list shows a non-edge).
- */
- while (*p && *p != ',') {
- if (*p < 'a' || *p > 'z')
- return "Unexpected character in edge list";
- if (*p == 'z')
- k = 25;
- else
- k = *p - 'a' + 1;
- while (k-- > 0) {
- int x, y, dx, dy;
-
- if (pos < 0) {
- pos++;
- continue;
- } else if (pos < w*(h-1)) {
- /* Horizontal edge. */
- y = pos / w;
- x = pos % w;
- dx = 0;
- dy = 1;
- } else if (pos < 2*wh-w-h) {
- /* Vertical edge. */
- x = (pos - w*(h-1)) / h;
- y = (pos - w*(h-1)) % h;
- dx = 1;
- dy = 0;
- } else
- return "Too much data in edge list";
- if (!state)
- dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));
-
- pos++;
- }
- if (*p != 'z')
- state = !state;
- p++;
- }
- assert(pos <= 2*wh-w-h);
- if (pos < 2*wh-w-h)
- return "Too little data in edge list";
-
- /*
- * Now go through again and allocate region numbers.
- */
- pos = 0;
- for (i = 0; i < wh; i++)
- map[i] = -1;
- for (i = 0; i < wh; i++) {
- k = dsf_canonify(map+wh, i);
- if (map[k] < 0)
- map[k] = pos++;
- map[i] = map[k];
- }
- if (pos != n)
- return "Edge list defines the wrong number of regions";
-
- *desc = p;
-
- return NULL;
-}
-
-static char *validate_desc(const game_params *params, const char *desc)
-{
- int w = params->w, h = params->h, wh = w*h, n = params->n;
- int area;
- int *map;
- char *ret;
-
- map = snewn(2*wh, int);
- ret = parse_edge_list(params, &desc, map);
- sfree(map);
- if (ret)
- return ret;
-
- if (*desc != ',')
- return "Expected comma before clue list";
- desc++; /* eat comma */
-
- area = 0;
- while (*desc) {
- if (*desc >= '0' && *desc < '0'+FOUR)
- area++;
- else if (*desc >= 'a' && *desc <= 'z')
- area += *desc - 'a' + 1;
- else
- return "Unexpected character in clue list";
- desc++;
- }
- if (area < n)
- return "Too little data in clue list";
- else if (area > n)
- return "Too much data in clue list";
-
- return NULL;
-}
-
-static game_state *new_game(midend *me, const game_params *params,
- const char *desc)
-{
- int w = params->w, h = params->h, wh = w*h, n = params->n;
- int i, pos;
- const char *p;
- game_state *state = snew(game_state);
-
- state->p = *params;
- 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;
-
- state->map = snew(struct map);
- state->map->refcount = 1;
- state->map->map = snewn(wh*4, int);
- state->map->graph = snewn(n*n, int);
- state->map->n = n;
- state->map->immutable = snewn(n, int);
- for (i = 0; i < n; i++)
- state->map->immutable[i] = FALSE;
-
- p = desc;
-
- {
- char *ret;
- ret = parse_edge_list(params, &p, state->map->map);
- assert(!ret);
- }
-
- /*
- * Set up the other three quadrants in `map'.
- */
- for (i = wh; i < 4*wh; i++)
- state->map->map[i] = state->map->map[i % wh];
-
- assert(*p == ',');
- p++;
-
- /*
- * Now process the clue list.
- */
- pos = 0;
- while (*p) {
- if (*p >= '0' && *p < '0'+FOUR) {
- state->colouring[pos] = *p - '0';
- state->map->immutable[pos] = TRUE;
- pos++;
- } else {
- assert(*p >= 'a' && *p <= 'z');
- pos += *p - 'a' + 1;
- }
- p++;
- }
- assert(pos == n);
-
- state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);
-
- /*
- * Attempt to smooth out some of the more jagged region
- * outlines by the judicious use of diagonally divided squares.
- */
- {
- random_state *rs = random_new(desc, strlen(desc));
- int *squares = snewn(wh, int);
- int done_something;
-
- for (i = 0; i < wh; i++)
- squares[i] = i;
- shuffle(squares, wh, sizeof(*squares), rs);
-
- do {
- done_something = FALSE;
- for (i = 0; i < wh; i++) {
- int y = squares[i] / w, x = squares[i] % w;
- int c = state->map->map[y*w+x];
- int tc, bc, lc, rc;
-
- if (x == 0 || x == w-1 || y == 0 || y == h-1)
- continue;
-
- if (state->map->map[TE * wh + y*w+x] !=
- state->map->map[BE * wh + y*w+x])
- continue;
-
- tc = state->map->map[BE * wh + (y-1)*w+x];
- bc = state->map->map[TE * wh + (y+1)*w+x];
- lc = state->map->map[RE * wh + y*w+(x-1)];
- rc = state->map->map[LE * wh + y*w+(x+1)];
-
- /*
- * If this square is adjacent on two sides to one
- * region and on the other two sides to the other
- * region, and is itself one of the two regions, we can
- * adjust it so that it's a diagonal.
- */
- if (tc != bc && (tc == c || bc == c)) {
- if ((lc == tc && rc == bc) ||
- (lc == bc && rc == tc)) {
- state->map->map[TE * wh + y*w+x] = tc;
- state->map->map[BE * wh + y*w+x] = bc;
- state->map->map[LE * wh + y*w+x] = lc;
- state->map->map[RE * wh + y*w+x] = rc;
- done_something = TRUE;
- }
- }
- }
- } while (done_something);
- sfree(squares);
- random_free(rs);
- }
-
- /*
- * Analyse the map to find a canonical line segment
- * 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 + 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 + n; i++) {
- bestx[i] = besty[i] = -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 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
- * segment is always something-and-a-half; so we store our
- * coordinates as twice their normal value.
- */
- for (pass = 0; pass < 2; pass++) {
- int x, y;
-
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- int ex[4], ey[4], ea[4], eb[4], en = 0;
-
- /*
- * Look for an edge to the right of this
- * square, an edge below it, and an edge in the
- * middle of it. Also look to see if the point
- * at the bottom right of this square is on an
- * edge (and isn't a place where more than two
- * regions meet).
- */
- if (x+1 < w) {
- /* right edge */
- ea[en] = state->map->map[RE * wh + y*w+x];
- eb[en] = state->map->map[LE * wh + y*w+(x+1)];
- 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];
- 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];
- 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;
- oct[0] = state->map->map[RE * wh + y*w+x];
- oct[1] = state->map->map[LE * wh + y*w+(x+1)];
- oct[2] = state->map->map[BE * wh + y*w+(x+1)];
- oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)];
- oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)];
- oct[5] = state->map->map[RE * wh + (y+1)*w+x];
- oct[6] = state->map->map[TE * wh + (y+1)*w+x];
- oct[7] = state->map->map[BE * wh + y*w+x];
-
- othercol = -1;
- nchanges = 0;
- for (i = 0; i < 8; i++) {
- if (oct[i] != oct[0]) {
- if (othercol < 0)
- othercol = oct[i];
- else if (othercol != oct[i])
- break; /* three colours at this point */
- }
- if (oct[i] != oct[(i+1) & 7])
- nchanges++;
- }
-
- /*
- * Now if there are exactly two regions at
- * this point (not one, and not three or
- * more), and only two changes around the
- * loop, then this is a valid place to put
- * an error marker.
- */
- if (i == 8 && othercol >= 0 && nchanges == 2) {
- ea[en] = oct[0];
- eb[en] = othercol;
- ex[en] = (x+1)*2;
- 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 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;
-
- 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);
-
- if (pass == 0) {
- /*
- * In pass 0, accumulate the values
- * we'll use to compute the average
- * positions.
- */
- ax[gindex] += ex[i];
- ay[gindex] += ey[i];
- an[gindex] += 1;
- } else {
- /*
- * In pass 1, work out whether this
- * point is closer to the average than
- * the last one we've seen.
- */
- float dx, dy, d;
-
- assert(an[gindex] > 0);
- dx = ex[i] - ax[gindex];
- dy = ey[i] - ay[gindex];
- d = (float)sqrt(dx*dx + dy*dy);
- if (d < best[gindex]) {
- best[gindex] = d;
- bestx[gindex] = ex[i];
- besty[gindex] = ey[i];
- }
- }
- }
- }
-
- if (pass == 0) {
- for (i = 0; i < state->map->ngraph + n; i++)
- if (an[i] > 0) {
- ax[i] /= an[i];
- ay[i] /= an[i];
- }
- }
- }
-
- 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) {
- /* Find the other representation of this edge. */
- int e = state->map->graph[i];
- int iprime = graph_edge_index(state->map->graph, n,
- state->map->ngraph, e%n, e/n);
- assert(state->map->edgex[iprime] >= 0);
- state->map->edgex[i] = state->map->edgex[iprime];
- state->map->edgey[i] = state->map->edgey[iprime];
- }
-
- sfree(ax);
- sfree(ay);
- sfree(an);
- sfree(best);
- sfree(bestx);
- sfree(besty);
- }
-
- return state;
-}
-
-static game_state *dup_game(const game_state *state)
-{
- game_state *ret = snew(game_state);
-
- 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;
- ret->cheated = state->cheated;
-
- return ret;
-}
-
-static void free_game(game_state *state)
-{
- if (--state->map->refcount <= 0) {
- sfree(state->map->map);
- sfree(state->map->graph);
- 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);
-}
-
-static char *solve_game(const game_state *state, const game_state *currstate,
- const char *aux, char **error)
-{
- if (!aux) {
- /*
- * Use the solver.
- */
- int *colouring;
- struct solver_scratch *sc;
- int sret;
- int i;
- char *ret, buf[80];
- int retlen, retsize;
-
- colouring = snewn(state->map->n, int);
- memcpy(colouring, state->colouring, state->map->n * sizeof(int));
-
- sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
- sret = map_solver(sc, state->map->graph, state->map->n,
- state->map->ngraph, colouring, DIFFCOUNT-1);
- free_scratch(sc);
-
- if (sret != 1) {
- sfree(colouring);
- if (sret == 0)
- *error = "Puzzle is inconsistent";
- else
- *error = "Unable to find a unique solution for this puzzle";
- return NULL;
- }
-
- retsize = 64;
- ret = snewn(retsize, char);
- strcpy(ret, "S");
- retlen = 1;
-
- for (i = 0; i < state->map->n; i++) {
- int len;
-
- assert(colouring[i] >= 0);
- if (colouring[i] == currstate->colouring[i])
- continue;
- assert(!state->map->immutable[i]);
-
- len = sprintf(buf, ";%d:%d", colouring[i], i);
- if (retlen + len >= retsize) {
- retsize = retlen + len + 256;
- ret = sresize(ret, retsize, char);
- }
- strcpy(ret + retlen, buf);
- retlen += len;
- }
-
- sfree(colouring);
-
- return ret;
- }
- return dupstr(aux);
-}
-
-static int game_can_format_as_text_now(const game_params *params)
-{
- return TRUE;
-}
-
-static char *game_text_format(const game_state *state)
-{
- return NULL;
-}
-
-struct game_ui {
- /*
- * 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(const 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;
-}
-
-static void free_ui(game_ui *ui)
-{
- sfree(ui);
-}
-
-static char *encode_ui(const game_ui *ui)
-{
- return NULL;
-}
-
-static void decode_ui(game_ui *ui, const char *encoding)
-{
-}
-
-static void game_changed_state(game_ui *ui, const game_state *oldstate,
- const game_state *newstate)
-{
-}
-
-struct game_drawstate {
- int tilesize;
- unsigned long *drawn, *todraw;
- int started;
- int dragx, dragy, drag_visible;
- blitter *bl;
-};
-
-/* Flags in `drawn'. */
-#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 )
-
- /*
- * 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(const 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 */;
- int tx = FROMCOORD(x), ty = FROMCOORD(y);
- int dx = x - COORD(tx), dy = y - COORD(ty);
- int quadrant;
-
- if (tx < 0 || tx >= w || ty < 0 || ty >= h)
- return -1; /* border */
-
- quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
- quadrant = (quadrant == 0 ? BE :
- quadrant == 1 ? LE :
- quadrant == 2 ? RE : TE);
-
- return state->map->map[quadrant * wh + ty*w+tx];
-}
-
-static char *interpret_move(const game_state *state, game_ui *ui,
- const game_drawstate *ds,
- int x, int y, int button)
-{
- 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) {
- ui->drag_colour = state->colouring[r];
- 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_DRAG || button == RIGHT_DRAG) &&
- ui->drag_colour > -2) {
- ui->dragx = x;
- ui->dragy = y;
- 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;
-
- 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 && state->pencil[r] == p)
- return ""; /* don't _need_ to change this 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. */
- }
-
- 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 dupstr(buf+1); /* ignore first semicolon */
- }
-}
-
-static game_state *execute_move(const game_state *state, const char *move)
-{
- int n = state->p.n;
- game_state *ret = dup_game(state);
- 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;
- 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;
- } else {
- free_game(ret);
- return NULL;
- }
-
- if (*move && *move != ';') {
- free_game(ret);
- return NULL;
- }
- if (*move)
- move++;
- }
-
- /*
- * Check for completion.
- */
- if (!ret->completed) {
- int ok = TRUE;
-
- for (i = 0; i < n; i++)
- if (ret->colouring[i] < 0) {
- ok = FALSE;
- break;
- }
-
- if (ok) {
- for (i = 0; i < ret->map->ngraph; i++) {
- int j = ret->map->graph[i] / n;
- int k = ret->map->graph[i] % n;
- if (ret->colouring[j] == ret->colouring[k]) {
- ok = FALSE;
- break;
- }
- }
- }
-
- if (ok)
- ret->completed = TRUE;
- }
-
- return ret;
-}
-
-/* ----------------------------------------------------------------------
- * Drawing routines.
- */
-
-static void game_compute_size(const game_params *params, int tilesize,
- int *x, int *y)
-{
- /* Ick: fake up `ds->tilesize' for macro expansion purposes */
- struct { int tilesize; } ads, *ds = &ads;
- ads.tilesize = tilesize;
-
- *x = params->w * TILESIZE + 2 * BORDER + 1;
- *y = params->h * TILESIZE + 2 * BORDER + 1;
-}
-
-static void game_set_size(drawing *dr, game_drawstate *ds,
- const game_params *params, int tilesize)
-{
- ds->tilesize = tilesize;
-
- 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, int *ncolours)
-{
- float *ret = snewn(3 * NCOLOURS, float);
-
- frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
-
- ret[COL_GRID * 3 + 0] = 0.0F;
- ret[COL_GRID * 3 + 1] = 0.0F;
- ret[COL_GRID * 3 + 2] = 0.0F;
-
- memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
- memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
- memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
- memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
-
- ret[COL_ERROR * 3 + 0] = 1.0F;
- ret[COL_ERROR * 3 + 1] = 0.0F;
- ret[COL_ERROR * 3 + 2] = 0.0F;
-
- ret[COL_ERRTEXT * 3 + 0] = 1.0F;
- ret[COL_ERRTEXT * 3 + 1] = 1.0F;
- ret[COL_ERRTEXT * 3 + 2] = 1.0F;
-
- *ncolours = NCOLOURS;
- return ret;
-}
-
-static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
-{
- struct game_drawstate *ds = snew(struct game_drawstate);
- int i;
-
- ds->tilesize = 0;
- 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] = 0xFFFFL;
- ds->todraw = snewn(state->p.w * state->p.h, unsigned long);
- ds->started = FALSE;
- ds->bl = NULL;
- ds->drag_visible = FALSE;
- ds->dragx = ds->dragy = -1;
-
- return ds;
-}
-
-static void game_free_drawstate(drawing *dr, game_drawstate *ds)
-{
- sfree(ds->drawn);
- sfree(ds->todraw);
- if (ds->bl)
- blitter_free(dr, ds->bl);
- sfree(ds);
-}
-
-static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
-{
- int coords[8];
- int yext, xext;
-
- /*
- * Draw a diamond.
- */
- coords[0] = x - TILESIZE*2/5;
- coords[1] = y;
- coords[2] = x;
- coords[3] = y - TILESIZE*2/5;
- coords[4] = x + TILESIZE*2/5;
- coords[5] = y;
- coords[6] = x;
- coords[7] = y + TILESIZE*2/5;
- draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
-
- /*
- * Draw an exclamation mark in the diamond. This turns out to
- * look unpleasantly off-centre if done via draw_text, so I do
- * it by hand on the basis that exclamation marks aren't that
- * difficult to draw...
- */
- xext = TILESIZE/16;
- yext = TILESIZE*2/5 - (xext*2+2);
- draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
- COL_ERRTEXT);
- draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
-}
-
-static void draw_square(drawing *dr, game_drawstate *ds,
- const game_params *params, struct map *map,
- int x, int y, unsigned long v)
-{
- int w = params->w, h = params->h, wh = w*h;
- 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;
-
- clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
-
- /*
- * Draw the region colour.
- */
- draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
- (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
- /*
- * Draw the second region colour, if this is a diagonally
- * divided square.
- */
- if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
- int coords[6];
- coords[0] = COORD(x)-1;
- coords[1] = COORD(y+1)+1;
- if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
- coords[2] = COORD(x+1)+1;
- else
- coords[2] = COORD(x)-1;
- coords[3] = COORD(y)-1;
- coords[4] = COORD(x+1)+1;
- coords[5] = COORD(y+1)+1;
- draw_polygon(dr, coords, 3,
- (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
- }
-
- /*
- * 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];
-
- if (xo != (yo * 2 + 1) % 5)
- continue;
- c = yo;
-
- 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_circle(dr, COORD(x) + (xo+1)*TILESIZE/5,
- COORD(y) + (yo+1)*TILESIZE/5,
- TILESIZE/7, COL_0 + c, 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])
- draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
- if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
- draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
- if (x <= 0 || y <= 0 ||
- map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
- map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
- draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
-
- /*
- * Draw error markers.
- */
- for (yo = 0; yo < 3; yo++)
- for (xo = 0; xo < 3; xo++)
- if (errs & (ERR_BASE << (yo*3+xo)))
- draw_error(dr, ds,
- (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);
-}
-
-static void game_redraw(drawing *dr, game_drawstate *ds,
- const game_state *oldstate, const game_state *state,
- int dir, const game_ui *ui,
- float animtime, float flashtime)
-{
- int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
- int x, y, i;
- int flash;
-
- if (ds->drag_visible) {
- blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
- draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
- ds->drag_visible = FALSE;
- }
-
- /*
- * The initial contents of the window are not guaranteed and
- * can vary with front ends. To be on the safe side, all games
- * should start by drawing a big background-colour rectangle
- * covering the whole window.
- */
- if (!ds->started) {
- int ww, wh;
-
- game_compute_size(&state->p, TILESIZE, &ww, &wh);
- draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
- draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
- COL_GRID);
-
- draw_update(dr, 0, 0, ww, wh);
- ds->started = TRUE;
- }
-
- if (flashtime) {
- if (flash_type == 1)
- flash = (int)(flashtime * FOUR / flash_length);
- else
- flash = 1 + (int)(flashtime * THREE / flash_length);
- } else
- flash = -1;
-
- /*
- * Set up the `todraw' array.
- */
- for (y = 0; y < h; y++)
- 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]];
- unsigned long v;
-
- if (tv < 0)
- tv = FOUR;
- if (bv < 0)
- bv = FOUR;
-
- if (flash >= 0) {
- if (flash_type == 1) {
- if (tv == flash)
- tv = FOUR;
- if (bv == flash)
- bv = FOUR;
- } else if (flash_type == 2) {
- if (flash % 2)
- tv = bv = FOUR;
- } else {
- if (tv != FOUR)
- tv = (tv + flash) % FOUR;
- if (bv != FOUR)
- bv = (bv + flash) % FOUR;
- }
- }
-
- 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;
- }
-
- if (ui->show_numbers)
- v |= SHOW_NUMBERS;
-
- ds->todraw[y*w+x] = v;
- }
-
- /*
- * Add error markers to the `todraw' array.
- */
- for (i = 0; i < state->map->ngraph; i++) {
- int v1 = state->map->graph[i] / n;
- int v2 = state->map->graph[i] % n;
- int xo, yo;
-
- if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
- continue;
- if (state->colouring[v1] != state->colouring[v2])
- continue;
-
- x = state->map->edgex[i];
- y = state->map->edgey[i];
-
- xo = x % 2; x /= 2;
- yo = y % 2; y /= 2;
-
- ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo);
- if (xo == 0) {
- assert(x > 0);
- ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2);
- }
- if (yo == 0) {
- assert(y > 0);
- ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo);
- }
- if (xo == 0 && yo == 0) {
- assert(x > 0 && y > 0);
- ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2);
- }
- }
-
- /*
- * Now actually draw everything.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < 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) || 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,
- 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;
- }
-}
-
-static float game_anim_length(const game_state *oldstate,
- const game_state *newstate, int dir, game_ui *ui)
-{
- return 0.0F;
-}
-
-static float game_flash_length(const game_state *oldstate,
- const game_state *newstate, int dir, game_ui *ui)
-{
- if (!oldstate->completed && newstate->completed &&
- !oldstate->cheated && !newstate->cheated) {
- if (flash_type < 0) {
- char *env = getenv("MAP_ALTERNATIVE_FLASH");
- if (env)
- flash_type = atoi(env);
- else
- flash_type = 0;
- flash_length = (flash_type == 1 ? 0.50F : 0.30F);
- }
- return flash_length;
- } else
- return 0.0F;
-}
-
-static int game_status(const game_state *state)
-{
- return state->completed ? +1 : 0;
-}
-
-static int game_timing_state(const game_state *state, game_ui *ui)
-{
- return TRUE;
-}
-
-static void game_print_size(const game_params *params, float *x, float *y)
-{
- int pw, ph;
-
- /*
- * I'll use 4mm squares by default, I think. Simplest way to
- * compute this size is to compute the pixel puzzle size at a
- * given tile size and then scale.
- */
- game_compute_size(params, 400, &pw, &ph);
- *x = pw / 100.0F;
- *y = ph / 100.0F;
-}
-
-static void game_print(drawing *dr, const game_state *state, int tilesize)
-{
- int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
- int ink, c[FOUR], i;
- int x, y, r;
- int *coords, ncoords, coordsize;
-
- /* 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_hatched_colour(dr, map_colours[i][0],
- map_colours[i][1], map_colours[i][2],
- map_hatching[i]);
-
- coordsize = 0;
- coords = NULL;
-
- print_line_width(dr, TILESIZE / 16);
-
- /*
- * Draw a single filled polygon around each region.
- */
- for (r = 0; r < n; r++) {
- int octants[8], lastdir, d1, d2, ox, oy;
-
- /*
- * Start by finding a point on the region boundary. Any
- * point will do. To do this, we'll search for a square
- * containing the region and then decide which corner of it
- * to use.
- */
- x = w;
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- if (state->map->map[wh*0+y*w+x] == r ||
- state->map->map[wh*1+y*w+x] == r ||
- state->map->map[wh*2+y*w+x] == r ||
- state->map->map[wh*3+y*w+x] == r)
- break;
- }
- if (x < w)
- break;
- }
- assert(y < h && x < w); /* we must have found one somewhere */
- /*
- * This is the first square in lexicographic order which
- * contains part of this region. Therefore, one of the top
- * two corners of the square must be what we're after. The
- * only case in which it isn't the top left one is if the
- * square is diagonally divided and the region is in the
- * bottom right half.
- */
- if (state->map->map[wh*TE+y*w+x] != r &&
- state->map->map[wh*LE+y*w+x] != r)
- x++; /* could just as well have done y++ */
-
- /*
- * Now we have a point on the region boundary. Trace around
- * the region until we come back to this point,
- * accumulating coordinates for a polygon draw operation as
- * we go.
- */
- lastdir = -1;
- ox = x;
- oy = y;
- ncoords = 0;
-
- do {
- /*
- * There are eight possible directions we could head in
- * from here. We identify them by octant numbers, and
- * we also use octant numbers to identify the spaces
- * between them:
- *
- * 6 7 0
- * \ 7|0 /
- * \ | /
- * 6 \|/ 1
- * 5-----+-----1
- * 5 /|\ 2
- * / | \
- * / 4|3 \
- * 4 3 2
- */
- octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
- octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
- octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
- octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
- octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
- octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
- octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
- octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
-
- d1 = d2 = -1;
- for (i = 0; i < 8; i++)
- if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
- assert(d2 == -1);
- if (d1 == -1)
- d1 = i;
- else
- d2 = i;
- }
-
- assert(d1 != -1 && d2 != -1);
- if (d1 == lastdir)
- d1 = d2;
-
- /*
- * Now we're heading in direction d1. Save the current
- * coordinates.
- */
- if (ncoords + 2 > coordsize) {
- coordsize += 128;
- coords = sresize(coords, coordsize, int);
- }
- coords[ncoords++] = COORD(x);
- coords[ncoords++] = COORD(y);
-
- /*
- * Compute the new coordinates.
- */
- x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
- y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
- assert(x >= 0 && x <= w && y >= 0 && y <= h);
-
- lastdir = d1 ^ 4;
- } while (x != ox || y != oy);
-
- draw_polygon(dr, coords, ncoords/2,
- state->colouring[r] >= 0 ?
- c[state->colouring[r]] : -1, ink);
- }
- sfree(coords);
-}
-
-#ifdef COMBINED
-#define thegame map
-#endif
-
-const struct game thegame = {
- "Map", "games.map", "map",
- default_params,
- game_fetch_preset,
- decode_params,
- encode_params,
- free_params,
- dup_params,
- TRUE, game_configure, custom_params,
- validate_params,
- new_game_desc,
- validate_desc,
- new_game,
- dup_game,
- free_game,
- TRUE, solve_game,
- FALSE, game_can_format_as_text_now, game_text_format,
- new_ui,
- free_ui,
- encode_ui,
- decode_ui,
- game_changed_state,
- interpret_move,
- execute_move,
- 20, game_compute_size, game_set_size,
- game_colours,
- game_new_drawstate,
- game_free_drawstate,
- game_redraw,
- game_anim_length,
- game_flash_length,
- game_status,
- TRUE, TRUE, game_print_size, game_print,
- FALSE, /* wants_statusbar */
- FALSE, game_timing_state,
- 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: */
generated by cgit v1.1 at 2026-04-25 19:02:57 +0000