2 * map.c: Game involving four-colouring a map.
10 * - more solver brains?
11 * - better four-colouring algorithm?
25 * I don't seriously anticipate wanting to change the number of
26 * colours used in this game, but it doesn't cost much to use a
27 * #define just in case :-)
30 #define THREE (FOUR-1)
35 * Ghastly run-time configuration option, just for Gareth (again).
37 static int flash_type = -1;
38 static float flash_length;
41 * Difficulty levels. I do some macro ickery here to ensure that my
42 * enum and the various forms of my name list always match up.
47 #define ENUM(upper,title,lower) DIFF_ ## upper,
48 #define TITLE(upper,title,lower) #title,
49 #define ENCODE(upper,title,lower) #lower
50 #define CONFIG(upper,title,lower) ":" #title
51 enum { DIFFLIST(ENUM) DIFFCOUNT };
52 static char const *const map_diffnames[] = { DIFFLIST(TITLE) };
53 static char const map_diffchars[] = DIFFLIST(ENCODE);
54 #define DIFFCONFIG DIFFLIST(CONFIG)
56 enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */
61 COL_0, COL_1, COL_2, COL_3,
82 int completed, cheated;
85 static game_params *default_params(void)
87 game_params *ret = snew(game_params);
92 ret->diff = DIFF_NORMAL;
97 static const struct game_params map_presets[] = {
98 {20, 15, 30, DIFF_EASY},
99 {20, 15, 30, DIFF_NORMAL},
100 {30, 25, 75, DIFF_NORMAL},
103 static int game_fetch_preset(int i, char **name, game_params **params)
108 if (i < 0 || i >= lenof(map_presets))
111 ret = snew(game_params);
112 *ret = map_presets[i];
114 sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
115 map_diffnames[ret->diff]);
122 static void free_params(game_params *params)
127 static game_params *dup_params(game_params *params)
129 game_params *ret = snew(game_params);
130 *ret = *params; /* structure copy */
134 static void decode_params(game_params *params, char const *string)
136 char const *p = string;
139 while (*p && isdigit((unsigned char)*p)) p++;
143 while (*p && isdigit((unsigned char)*p)) p++;
145 params->h = params->w;
150 while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
152 params->n = params->w * params->h / 8;
157 for (i = 0; i < DIFFCOUNT; i++)
158 if (*p == map_diffchars[i])
164 static char *encode_params(game_params *params, int full)
168 sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
170 sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
175 static config_item *game_configure(game_params *params)
180 ret = snewn(5, config_item);
182 ret[0].name = "Width";
183 ret[0].type = C_STRING;
184 sprintf(buf, "%d", params->w);
185 ret[0].sval = dupstr(buf);
188 ret[1].name = "Height";
189 ret[1].type = C_STRING;
190 sprintf(buf, "%d", params->h);
191 ret[1].sval = dupstr(buf);
194 ret[2].name = "Regions";
195 ret[2].type = C_STRING;
196 sprintf(buf, "%d", params->n);
197 ret[2].sval = dupstr(buf);
200 ret[3].name = "Difficulty";
201 ret[3].type = C_CHOICES;
202 ret[3].sval = DIFFCONFIG;
203 ret[3].ival = params->diff;
213 static game_params *custom_params(config_item *cfg)
215 game_params *ret = snew(game_params);
217 ret->w = atoi(cfg[0].sval);
218 ret->h = atoi(cfg[1].sval);
219 ret->n = atoi(cfg[2].sval);
220 ret->diff = cfg[3].ival;
225 static char *validate_params(game_params *params, int full)
227 if (params->w < 2 || params->h < 2)
228 return "Width and height must be at least two";
230 return "Must have at least five regions";
231 if (params->n > params->w * params->h)
232 return "Too many regions to fit in grid";
236 /* ----------------------------------------------------------------------
237 * Cumulative frequency table functions.
241 * Initialise a cumulative frequency table. (Hardly worth writing
242 * this function; all it does is to initialise everything in the
245 static void cf_init(int *table, int n)
249 for (i = 0; i < n; i++)
254 * Increment the count of symbol `sym' by `count'.
256 static void cf_add(int *table, int n, int sym, int count)
273 * Cumulative frequency lookup: return the total count of symbols
274 * with value less than `sym'.
276 static int cf_clookup(int *table, int n, int sym)
278 int bit, index, limit, count;
283 assert(0 < sym && sym <= n);
285 count = table[0]; /* start with the whole table size */
295 * Find the least number with its lowest set bit in this
296 * position which is greater than or equal to sym.
298 index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
301 count -= table[index];
312 * Single frequency lookup: return the count of symbol `sym'.
314 static int cf_slookup(int *table, int n, int sym)
318 assert(0 <= sym && sym < n);
322 for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
323 count -= table[sym+bit];
329 * Return the largest symbol index such that the cumulative
330 * frequency up to that symbol is less than _or equal to_ count.
332 static int cf_whichsym(int *table, int n, int count) {
335 assert(count >= 0 && count < table[0]);
346 if (count >= top - table[sym+bit])
349 top -= table[sym+bit];
358 /* ----------------------------------------------------------------------
361 * FIXME: this isn't entirely optimal at present, because it
362 * inherently prioritises growing the largest region since there
363 * are more squares adjacent to it. This acts as a destabilising
364 * influence leading to a few large regions and mostly small ones.
365 * It might be better to do it some other way.
368 #define WEIGHT_INCREASED 2 /* for increased perimeter */
369 #define WEIGHT_DECREASED 4 /* for decreased perimeter */
370 #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
373 * Look at a square and decide which colours can be extended into
376 * If called with index < 0, it adds together one of
377 * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
378 * colour that has a valid extension (according to the effect that
379 * it would have on the perimeter of the region being extended) and
380 * returns the overall total.
382 * If called with index >= 0, it returns one of the possible
383 * colours depending on the value of index, in such a way that the
384 * number of possible inputs which would give rise to a given
385 * return value correspond to the weight of that value.
387 static int extend_options(int w, int h, int n, int *map,
388 int x, int y, int index)
394 if (map[y*w+x] >= 0) {
396 return 0; /* can't do this square at all */
400 * Fetch the eight neighbours of this square, in order around
403 for (dy = -1; dy <= +1; dy++)
404 for (dx = -1; dx <= +1; dx++) {
405 int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx));
406 if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h)
407 col[index] = map[(y+dy)*w+(x+dx)];
413 * Iterate over each colour that might be feasible.
415 * FIXME: this routine currently has O(n) running time. We
416 * could turn it into O(FOUR) by only bothering to iterate over
417 * the colours mentioned in the four neighbouring squares.
420 for (c = 0; c < n; c++) {
421 int count, neighbours, runs;
424 * One of the even indices of col (representing the
425 * orthogonal neighbours of this square) must be equal to
426 * c, or else this square is not adjacent to region c and
427 * obviously cannot become an extension of it at this time.
430 for (i = 0; i < 8; i += 2)
437 * Now we know this square is adjacent to region c. The
438 * next question is, would extending it cause the region to
439 * become non-simply-connected? If so, we mustn't do it.
441 * We determine this by looking around col to see if we can
442 * find more than one separate run of colour c.
445 for (i = 0; i < 8; i++)
446 if (col[i] == c && col[(i+1) & 7] != c)
454 * This square is a possibility. Determine its effect on
455 * the region's perimeter (computed from the number of
456 * orthogonal neighbours - 1 means a perimeter increase, 3
457 * a decrease, 2 no change; 4 is impossible because the
458 * region would already not be simply connected) and we're
461 assert(neighbours > 0 && neighbours < 4);
462 count = (neighbours == 1 ? WEIGHT_INCREASED :
463 neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);
466 if (index >= 0 && index < count)
477 static void genmap(int w, int h, int n, int *map, random_state *rs)
484 tmp = snewn(wh, int);
487 * Clear the map, and set up `tmp' as a list of grid indices.
489 for (i = 0; i < wh; i++) {
495 * Place the region seeds by selecting n members from `tmp'.
498 for (i = 0; i < n; i++) {
499 int j = random_upto(rs, k);
505 * Re-initialise `tmp' as a cumulative frequency table. This
506 * will store the number of possible region colours we can
507 * extend into each square.
512 * Go through the grid and set up the initial cumulative
515 for (y = 0; y < h; y++)
516 for (x = 0; x < w; x++)
517 cf_add(tmp, wh, y*w+x,
518 extend_options(w, h, n, map, x, y, -1));
521 * Now repeatedly choose a square we can extend a region into,
525 int k = random_upto(rs, tmp[0]);
530 sq = cf_whichsym(tmp, wh, k);
531 k -= cf_clookup(tmp, wh, sq);
534 colour = extend_options(w, h, n, map, x, y, k);
539 * Re-scan the nine cells around the one we've just
542 for (yy = max(y-1, 0); yy < min(y+2, h); yy++)
543 for (xx = max(x-1, 0); xx < min(x+2, w); xx++) {
544 cf_add(tmp, wh, yy*w+xx,
545 -cf_slookup(tmp, wh, yy*w+xx) +
546 extend_options(w, h, n, map, xx, yy, -1));
551 * Finally, go through and normalise the region labels into
552 * order, meaning that indistinguishable maps are actually
555 for (i = 0; i < n; i++)
558 for (i = 0; i < wh; i++) {
562 map[i] = tmp[map[i]];
568 /* ----------------------------------------------------------------------
569 * Functions to handle graphs.
573 * Having got a map in a square grid, convert it into a graph
576 static int gengraph(int w, int h, int n, int *map, int *graph)
581 * Start by setting the graph up as an adjacency matrix. We'll
582 * turn it into a list later.
584 for (i = 0; i < n*n; i++)
588 * Iterate over the map looking for all adjacencies.
590 for (y = 0; y < h; y++)
591 for (x = 0; x < w; x++) {
594 if (x+1 < w && (vx = map[y*w+(x+1)]) != v)
595 graph[v*n+vx] = graph[vx*n+v] = 1;
596 if (y+1 < h && (vy = map[(y+1)*w+x]) != v)
597 graph[v*n+vy] = graph[vy*n+v] = 1;
601 * Turn the matrix into a list.
603 for (i = j = 0; i < n*n; i++)
610 static int graph_adjacent(int *graph, int n, int ngraph, int i, int j)
617 while (top - bot > 1) {
618 mid = (top + bot) / 2;
621 else if (graph[mid] < v)
629 static int graph_vertex_start(int *graph, int n, int ngraph, int i)
636 while (top - bot > 1) {
637 mid = (top + bot) / 2;
646 /* ----------------------------------------------------------------------
647 * Generate a four-colouring of a graph.
649 * FIXME: it would be nice if we could convert this recursion into
650 * pseudo-recursion using some sort of explicit stack array, for
651 * the sake of the Palm port and its limited stack.
654 static int fourcolour_recurse(int *graph, int n, int ngraph,
655 int *colouring, int *scratch, random_state *rs)
657 int nfree, nvert, start, i, j, k, c, ci;
661 * Find the smallest number of free colours in any uncoloured
662 * vertex, and count the number of such vertices.
665 nfree = FIVE; /* start off bigger than FOUR! */
667 for (i = 0; i < n; i++)
668 if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) {
669 if (nfree > scratch[i*FIVE+FOUR]) {
670 nfree = scratch[i*FIVE+FOUR];
677 * If there aren't any uncoloured vertices at all, we're done.
680 return TRUE; /* we've got a colouring! */
683 * Pick a random vertex in that set.
685 j = random_upto(rs, nvert);
686 for (i = 0; i < n; i++)
687 if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
691 start = graph_vertex_start(graph, n, ngraph, i);
694 * Loop over the possible colours for i, and recurse for each
698 for (c = 0; c < FOUR; c++)
699 if (scratch[i*FIVE+c] == 0)
701 shuffle(cs, ci, sizeof(*cs), rs);
707 * Fill in this colour.
712 * Update the scratch space to reflect a new neighbour
713 * of this colour for each neighbour of vertex i.
715 for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
717 if (scratch[k*FIVE+c] == 0)
718 scratch[k*FIVE+FOUR]--;
725 if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
726 return TRUE; /* got one! */
729 * If that didn't work, clean up and try again with a
732 for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
735 if (scratch[k*FIVE+c] == 0)
736 scratch[k*FIVE+FOUR]++;
742 * If we reach here, we were unable to find a colouring at all.
743 * (This doesn't necessarily mean the Four Colour Theorem is
744 * violated; it might just mean we've gone down a dead end and
745 * need to back up and look somewhere else. It's only an FCT
746 * violation if we get all the way back up to the top level and
752 static void fourcolour(int *graph, int n, int ngraph, int *colouring,
759 * For each vertex and each colour, we store the number of
760 * neighbours that have that colour. Also, we store the number
761 * of free colours for the vertex.
763 scratch = snewn(n * FIVE, int);
764 for (i = 0; i < n * FIVE; i++)
765 scratch[i] = (i % FIVE == FOUR ? FOUR : 0);
768 * Clear the colouring to start with.
770 for (i = 0; i < n; i++)
773 i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
774 assert(i); /* by the Four Colour Theorem :-) */
779 /* ----------------------------------------------------------------------
780 * Non-recursive solver.
783 struct solver_scratch {
784 unsigned char *possible; /* bitmap of colours for each region */
790 static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
792 struct solver_scratch *sc;
794 sc = snew(struct solver_scratch);
798 sc->possible = snewn(n, unsigned char);
803 static void free_scratch(struct solver_scratch *sc)
809 static int place_colour(struct solver_scratch *sc,
810 int *colouring, int index, int colour)
812 int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
815 if (!(sc->possible[index] & (1 << colour)))
816 return FALSE; /* can't do it */
818 sc->possible[index] = 1 << colour;
819 colouring[index] = colour;
822 * Rule out this colour from all the region's neighbours.
824 for (j = graph_vertex_start(graph, n, ngraph, index);
825 j < ngraph && graph[j] < n*(index+1); j++) {
826 k = graph[j] - index*n;
827 sc->possible[k] &= ~(1 << colour);
834 * Returns 0 for impossible, 1 for success, 2 for failure to
835 * converge (i.e. puzzle is either ambiguous or just too
838 static int map_solver(struct solver_scratch *sc,
839 int *graph, int n, int ngraph, int *colouring,
845 * Initialise scratch space.
847 for (i = 0; i < n; i++)
848 sc->possible[i] = (1 << FOUR) - 1;
853 for (i = 0; i < n; i++)
854 if (colouring[i] >= 0) {
855 if (!place_colour(sc, colouring, i, colouring[i]))
856 return 0; /* the clues aren't even consistent! */
860 * Now repeatedly loop until we find nothing further to do.
863 int done_something = FALSE;
865 if (difficulty < DIFF_EASY)
866 break; /* can't do anything at all! */
869 * Simplest possible deduction: find a region with only one
872 for (i = 0; i < n; i++) if (colouring[i] < 0) {
873 int p = sc->possible[i];
876 return 0; /* puzzle is inconsistent */
878 if ((p & (p-1)) == 0) { /* p is a power of two */
880 for (c = 0; c < FOUR; c++)
884 if (!place_colour(sc, colouring, i, c))
885 return 0; /* found puzzle to be inconsistent */
886 done_something = TRUE;
893 if (difficulty < DIFF_NORMAL)
894 break; /* can't do anything harder */
897 * Failing that, go up one level. Look for pairs of regions
898 * which (a) both have the same pair of possible colours,
899 * (b) are adjacent to one another, (c) are adjacent to the
900 * same region, and (d) that region still thinks it has one
901 * or both of those possible colours.
903 * Simplest way to do this is by going through the graph
904 * edge by edge, so that we start with property (b) and
905 * then look for (a) and finally (c) and (d).
907 for (i = 0; i < ngraph; i++) {
908 int j1 = graph[i] / n, j2 = graph[i] % n;
912 continue; /* done it already, other way round */
914 if (colouring[j1] >= 0 || colouring[j2] >= 0)
915 continue; /* they're not undecided */
917 if (sc->possible[j1] != sc->possible[j2])
918 continue; /* they don't have the same possibles */
920 v = sc->possible[j1];
922 * See if v contains exactly two set bits.
924 v2 = v & -v; /* find lowest set bit */
925 v2 = v & ~v2; /* clear it */
926 if (v2 == 0 || (v2 & (v2-1)) != 0) /* not power of 2 */
930 * We've found regions j1 and j2 satisfying properties
931 * (a) and (b): they have two possible colours between
932 * them, and since they're adjacent to one another they
933 * must use _both_ those colours between them.
934 * Therefore, if they are both adjacent to any other
935 * region then that region cannot be either colour.
937 * Go through the neighbours of j1 and see if any are
940 for (j = graph_vertex_start(graph, n, ngraph, j1);
941 j < ngraph && graph[j] < n*(j1+1); j++) {
943 if (graph_adjacent(graph, n, ngraph, k, j2) &&
944 (sc->possible[k] & v)) {
945 sc->possible[k] &= ~v;
946 done_something = TRUE;
956 * We've run out of things to deduce. See if we've got the lot.
958 for (i = 0; i < n; i++)
959 if (colouring[i] < 0)
962 return 1; /* success! */
965 /* ----------------------------------------------------------------------
966 * Game generation main function.
969 static char *new_game_desc(game_params *params, random_state *rs,
970 char **aux, int interactive)
972 struct solver_scratch *sc = NULL;
973 int *map, *graph, ngraph, *colouring, *colouring2, *regions;
974 int i, j, w, h, n, solveret, cfreq[FOUR];
977 #ifdef GENERATION_DIAGNOSTICS
990 map = snewn(wh, int);
991 graph = snewn(n*n, int);
992 colouring = snewn(n, int);
993 colouring2 = snewn(n, int);
994 regions = snewn(n, int);
997 * This is the minimum difficulty below which we'll completely
998 * reject a map design. Normally we set this to one below the
999 * requested difficulty, ensuring that we have the right
1000 * result. However, for particularly dense maps or maps with
1001 * particularly few regions it might not be possible to get the
1002 * desired difficulty, so we will eventually drop this down to
1003 * -1 to indicate that any old map will do.
1005 mindiff = params->diff;
1013 genmap(w, h, n, map, rs);
1015 #ifdef GENERATION_DIAGNOSTICS
1016 for (y = 0; y < h; y++) {
1017 for (x = 0; x < w; x++) {
1022 putchar('a' + v-36);
1024 putchar('A' + v-10);
1033 * Convert the map into a graph.
1035 ngraph = gengraph(w, h, n, map, graph);
1037 #ifdef GENERATION_DIAGNOSTICS
1038 for (i = 0; i < ngraph; i++)
1039 printf("%d-%d\n", graph[i]/n, graph[i]%n);
1045 fourcolour(graph, n, ngraph, colouring, rs);
1047 #ifdef GENERATION_DIAGNOSTICS
1048 for (i = 0; i < n; i++)
1049 printf("%d: %d\n", i, colouring[i]);
1051 for (y = 0; y < h; y++) {
1052 for (x = 0; x < w; x++) {
1053 int v = colouring[map[y*w+x]];
1055 putchar('a' + v-36);
1057 putchar('A' + v-10);
1066 * Encode the solution as an aux string.
1068 if (*aux) /* in case we've come round again */
1070 retlen = retsize = 0;
1072 for (i = 0; i < n; i++) {
1075 if (colouring[i] < 0)
1078 len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i);
1079 if (retlen + len >= retsize) {
1080 retsize = retlen + len + 256;
1081 ret = sresize(ret, retsize, char);
1083 strcpy(ret + retlen, buf);
1089 * Remove the region colours one by one, keeping
1090 * solubility. Also ensure that there always remains at
1091 * least one region of every colour, so that the user can
1092 * drag from somewhere.
1094 for (i = 0; i < FOUR; i++)
1096 for (i = 0; i < n; i++) {
1098 cfreq[colouring[i]]++;
1100 for (i = 0; i < FOUR; i++)
1104 shuffle(regions, n, sizeof(*regions), rs);
1106 if (sc) free_scratch(sc);
1107 sc = new_scratch(graph, n, ngraph);
1109 for (i = 0; i < n; i++) {
1112 if (cfreq[colouring[j]] == 1)
1113 continue; /* can't remove last region of colour */
1115 memcpy(colouring2, colouring, n*sizeof(int));
1117 solveret = map_solver(sc, graph, n, ngraph, colouring2,
1119 assert(solveret >= 0); /* mustn't be impossible! */
1120 if (solveret == 1) {
1121 cfreq[colouring[j]]--;
1126 #ifdef GENERATION_DIAGNOSTICS
1127 for (i = 0; i < n; i++)
1128 if (colouring[i] >= 0) {
1132 putchar('a' + i-36);
1134 putchar('A' + i-10);
1137 printf(": %d\n", colouring[i]);
1142 * Finally, check that the puzzle is _at least_ as hard as
1143 * required, and indeed that it isn't already solved.
1144 * (Calling map_solver with negative difficulty ensures the
1145 * latter - if a solver which _does nothing_ can't solve
1146 * it, it's too easy!)
1148 memcpy(colouring2, colouring, n*sizeof(int));
1149 if (map_solver(sc, graph, n, ngraph, colouring2,
1150 mindiff - 1) == 1) {
1152 * Drop minimum difficulty if necessary.
1154 if (mindiff > 0 && (n < 9 || n > 3*wh/2)) {
1156 mindiff = 0; /* give up and go for Easy */
1165 * Encode as a game ID. We do this by:
1167 * - first going along the horizontal edges row by row, and
1168 * then the vertical edges column by column
1169 * - encoding the lengths of runs of edges and runs of
1171 * - the decoder will reconstitute the region boundaries from
1172 * this and automatically number them the same way we did
1173 * - then we encode the initial region colours in a Slant-like
1174 * fashion (digits 0-3 interspersed with letters giving
1175 * lengths of runs of empty spaces).
1177 retlen = retsize = 0;
1184 * Start with a notional non-edge, so that there'll be an
1185 * explicit `a' to distinguish the case where we start with
1191 for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
1192 int x, y, dx, dy, v;
1195 /* Horizontal edge. */
1201 /* Vertical edge. */
1202 x = (i - w*(h-1)) / h;
1203 y = (i - w*(h-1)) % h;
1208 if (retlen + 10 >= retsize) {
1209 retsize = retlen + 256;
1210 ret = sresize(ret, retsize, char);
1213 v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);
1216 ret[retlen++] = 'a'-1 + run;
1221 * 'z' is a special case in this encoding. Rather
1222 * than meaning a run of 26 and a state switch, it
1223 * means a run of 25 and _no_ state switch, because
1224 * otherwise there'd be no way to encode runs of
1228 ret[retlen++] = 'z';
1235 ret[retlen++] = 'a'-1 + run;
1236 ret[retlen++] = ',';
1239 for (i = 0; i < n; i++) {
1240 if (retlen + 10 >= retsize) {
1241 retsize = retlen + 256;
1242 ret = sresize(ret, retsize, char);
1245 if (colouring[i] < 0) {
1247 * In _this_ encoding, 'z' is a run of 26, since
1248 * there's no implicit state switch after each run.
1249 * Confusingly different, but more compact.
1252 ret[retlen++] = 'z';
1258 ret[retlen++] = 'a'-1 + run;
1259 ret[retlen++] = '0' + colouring[i];
1264 ret[retlen++] = 'a'-1 + run;
1267 assert(retlen < retsize);
1280 static char *parse_edge_list(game_params *params, char **desc, int *map)
1282 int w = params->w, h = params->h, wh = w*h, n = params->n;
1283 int i, k, pos, state;
1286 for (i = 0; i < wh; i++)
1293 * Parse the game description to get the list of edges, and
1294 * build up a disjoint set forest as we go (by identifying
1295 * pairs of squares whenever the edge list shows a non-edge).
1297 while (*p && *p != ',') {
1298 if (*p < 'a' || *p > 'z')
1299 return "Unexpected character in edge list";
1310 } else if (pos < w*(h-1)) {
1311 /* Horizontal edge. */
1316 } else if (pos < 2*wh-w-h) {
1317 /* Vertical edge. */
1318 x = (pos - w*(h-1)) / h;
1319 y = (pos - w*(h-1)) % h;
1323 return "Too much data in edge list";
1325 dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));
1333 assert(pos <= 2*wh-w-h);
1335 return "Too little data in edge list";
1338 * Now go through again and allocate region numbers.
1341 for (i = 0; i < wh; i++)
1343 for (i = 0; i < wh; i++) {
1344 k = dsf_canonify(map+wh, i);
1350 return "Edge list defines the wrong number of regions";
1357 static char *validate_desc(game_params *params, char *desc)
1359 int w = params->w, h = params->h, wh = w*h, n = params->n;
1364 map = snewn(2*wh, int);
1365 ret = parse_edge_list(params, &desc, map);
1371 return "Expected comma before clue list";
1372 desc++; /* eat comma */
1376 if (*desc >= '0' && *desc < '0'+FOUR)
1378 else if (*desc >= 'a' && *desc <= 'z')
1379 area += *desc - 'a' + 1;
1381 return "Unexpected character in clue list";
1385 return "Too little data in clue list";
1387 return "Too much data in clue list";
1392 static game_state *new_game(midend *me, game_params *params, char *desc)
1394 int w = params->w, h = params->h, wh = w*h, n = params->n;
1397 game_state *state = snew(game_state);
1400 state->colouring = snewn(n, int);
1401 for (i = 0; i < n; i++)
1402 state->colouring[i] = -1;
1404 state->completed = state->cheated = FALSE;
1406 state->map = snew(struct map);
1407 state->map->refcount = 1;
1408 state->map->map = snewn(wh*4, int);
1409 state->map->graph = snewn(n*n, int);
1411 state->map->immutable = snewn(n, int);
1412 for (i = 0; i < n; i++)
1413 state->map->immutable[i] = FALSE;
1419 ret = parse_edge_list(params, &p, state->map->map);
1424 * Set up the other three quadrants in `map'.
1426 for (i = wh; i < 4*wh; i++)
1427 state->map->map[i] = state->map->map[i % wh];
1433 * Now process the clue list.
1437 if (*p >= '0' && *p < '0'+FOUR) {
1438 state->colouring[pos] = *p - '0';
1439 state->map->immutable[pos] = TRUE;
1442 assert(*p >= 'a' && *p <= 'z');
1443 pos += *p - 'a' + 1;
1449 state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);
1452 * Attempt to smooth out some of the more jagged region
1453 * outlines by the judicious use of diagonally divided squares.
1456 random_state *rs = random_init(desc, strlen(desc));
1457 int *squares = snewn(wh, int);
1460 for (i = 0; i < wh; i++)
1462 shuffle(squares, wh, sizeof(*squares), rs);
1465 done_something = FALSE;
1466 for (i = 0; i < wh; i++) {
1467 int y = squares[i] / w, x = squares[i] % w;
1468 int c = state->map->map[y*w+x];
1471 if (x == 0 || x == w-1 || y == 0 || y == h-1)
1474 if (state->map->map[TE * wh + y*w+x] !=
1475 state->map->map[BE * wh + y*w+x])
1478 tc = state->map->map[BE * wh + (y-1)*w+x];
1479 bc = state->map->map[TE * wh + (y+1)*w+x];
1480 lc = state->map->map[RE * wh + y*w+(x-1)];
1481 rc = state->map->map[LE * wh + y*w+(x+1)];
1484 * If this square is adjacent on two sides to one
1485 * region and on the other two sides to the other
1486 * region, and is itself one of the two regions, we can
1487 * adjust it so that it's a diagonal.
1489 if (tc != bc && (tc == c || bc == c)) {
1490 if ((lc == tc && rc == bc) ||
1491 (lc == bc && rc == tc)) {
1492 state->map->map[TE * wh + y*w+x] = tc;
1493 state->map->map[BE * wh + y*w+x] = bc;
1494 state->map->map[LE * wh + y*w+x] = lc;
1495 state->map->map[RE * wh + y*w+x] = rc;
1496 done_something = TRUE;
1500 } while (done_something);
1508 static game_state *dup_game(game_state *state)
1510 game_state *ret = snew(game_state);
1513 ret->colouring = snewn(state->p.n, int);
1514 memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
1515 ret->map = state->map;
1516 ret->map->refcount++;
1517 ret->completed = state->completed;
1518 ret->cheated = state->cheated;
1523 static void free_game(game_state *state)
1525 if (--state->map->refcount <= 0) {
1526 sfree(state->map->map);
1527 sfree(state->map->graph);
1528 sfree(state->map->immutable);
1531 sfree(state->colouring);
1535 static char *solve_game(game_state *state, game_state *currstate,
1536 char *aux, char **error)
1543 struct solver_scratch *sc;
1547 int retlen, retsize;
1549 colouring = snewn(state->map->n, int);
1550 memcpy(colouring, state->colouring, state->map->n * sizeof(int));
1552 sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
1553 sret = map_solver(sc, state->map->graph, state->map->n,
1554 state->map->ngraph, colouring, DIFFCOUNT-1);
1560 *error = "Puzzle is inconsistent";
1562 *error = "Unable to find a unique solution for this puzzle";
1566 retlen = retsize = 0;
1569 for (i = 0; i < state->map->n; i++) {
1572 assert(colouring[i] >= 0);
1573 if (colouring[i] == currstate->colouring[i])
1575 assert(!state->map->immutable[i]);
1577 len = sprintf(buf, "%s%d:%d", retlen ? ";" : "S;",
1579 if (retlen + len >= retsize) {
1580 retsize = retlen + len + 256;
1581 ret = sresize(ret, retsize, char);
1583 strcpy(ret + retlen, buf);
1594 static char *game_text_format(game_state *state)
1600 int drag_colour; /* -1 means no drag active */
1604 static game_ui *new_ui(game_state *state)
1606 game_ui *ui = snew(game_ui);
1607 ui->dragx = ui->dragy = -1;
1608 ui->drag_colour = -2;
1612 static void free_ui(game_ui *ui)
1617 static char *encode_ui(game_ui *ui)
1622 static void decode_ui(game_ui *ui, char *encoding)
1626 static void game_changed_state(game_ui *ui, game_state *oldstate,
1627 game_state *newstate)
1631 struct game_drawstate {
1633 unsigned char *drawn;
1635 int dragx, dragy, drag_visible;
1639 #define TILESIZE (ds->tilesize)
1640 #define BORDER (TILESIZE)
1641 #define COORD(x) ( (x) * TILESIZE + BORDER )
1642 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1644 static int region_from_coords(game_state *state, game_drawstate *ds,
1647 int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
1648 int tx = FROMCOORD(x), ty = FROMCOORD(y);
1649 int dx = x - COORD(tx), dy = y - COORD(ty);
1652 if (tx < 0 || tx >= w || ty < 0 || ty >= h)
1653 return -1; /* border */
1655 quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
1656 quadrant = (quadrant == 0 ? BE :
1657 quadrant == 1 ? LE :
1658 quadrant == 2 ? RE : TE);
1660 return state->map->map[quadrant * wh + ty*w+tx];
1663 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1664 int x, int y, int button)
1668 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1669 int r = region_from_coords(state, ds, x, y);
1672 ui->drag_colour = state->colouring[r];
1674 ui->drag_colour = -1;
1680 if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
1681 ui->drag_colour > -2) {
1687 if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
1688 ui->drag_colour > -2) {
1689 int r = region_from_coords(state, ds, x, y);
1690 int c = ui->drag_colour;
1693 * Cancel the drag, whatever happens.
1695 ui->drag_colour = -2;
1696 ui->dragx = ui->dragy = -1;
1699 return ""; /* drag into border; do nothing else */
1701 if (state->map->immutable[r])
1702 return ""; /* can't change this region */
1704 if (state->colouring[r] == c)
1705 return ""; /* don't _need_ to change this region */
1707 sprintf(buf, "%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
1714 static game_state *execute_move(game_state *state, char *move)
1717 game_state *ret = dup_game(state);
1722 if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
1723 sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
1724 k >= 0 && k < state->p.n) {
1726 ret->colouring[k] = (c == 'C' ? -1 : c - '0');
1727 } else if (*move == 'S') {
1729 ret->cheated = TRUE;
1735 if (*move && *move != ';') {
1744 * Check for completion.
1746 if (!ret->completed) {
1749 for (i = 0; i < n; i++)
1750 if (ret->colouring[i] < 0) {
1756 for (i = 0; i < ret->map->ngraph; i++) {
1757 int j = ret->map->graph[i] / n;
1758 int k = ret->map->graph[i] % n;
1759 if (ret->colouring[j] == ret->colouring[k]) {
1767 ret->completed = TRUE;
1773 /* ----------------------------------------------------------------------
1777 static void game_compute_size(game_params *params, int tilesize,
1780 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1781 struct { int tilesize; } ads, *ds = &ads;
1782 ads.tilesize = tilesize;
1784 *x = params->w * TILESIZE + 2 * BORDER + 1;
1785 *y = params->h * TILESIZE + 2 * BORDER + 1;
1788 static void game_set_size(drawing *dr, game_drawstate *ds,
1789 game_params *params, int tilesize)
1791 ds->tilesize = tilesize;
1794 blitter_free(dr, ds->bl);
1795 ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
1798 const float map_colours[FOUR][3] = {
1802 {0.55F, 0.45F, 0.35F},
1804 const int map_hatching[FOUR] = {
1805 HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
1808 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1810 float *ret = snewn(3 * NCOLOURS, float);
1812 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1814 ret[COL_GRID * 3 + 0] = 0.0F;
1815 ret[COL_GRID * 3 + 1] = 0.0F;
1816 ret[COL_GRID * 3 + 2] = 0.0F;
1818 memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
1819 memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
1820 memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
1821 memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
1823 *ncolours = NCOLOURS;
1827 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1829 struct game_drawstate *ds = snew(struct game_drawstate);
1832 ds->drawn = snewn(state->p.w * state->p.h, unsigned char);
1833 memset(ds->drawn, 0xFF, state->p.w * state->p.h);
1834 ds->started = FALSE;
1836 ds->drag_visible = FALSE;
1837 ds->dragx = ds->dragy = -1;
1842 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1846 blitter_free(dr, ds->bl);
1850 static void draw_square(drawing *dr, game_drawstate *ds,
1851 game_params *params, struct map *map,
1852 int x, int y, int v)
1854 int w = params->w, h = params->h, wh = w*h;
1855 int tv = v / FIVE, bv = v % FIVE;
1857 clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1860 * Draw the region colour.
1862 draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
1863 (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
1865 * Draw the second region colour, if this is a diagonally
1868 if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
1870 coords[0] = COORD(x)-1;
1871 coords[1] = COORD(y+1)+1;
1872 if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
1873 coords[2] = COORD(x+1)+1;
1875 coords[2] = COORD(x)-1;
1876 coords[3] = COORD(y)-1;
1877 coords[4] = COORD(x+1)+1;
1878 coords[5] = COORD(y+1)+1;
1879 draw_polygon(dr, coords, 3,
1880 (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
1884 * Draw the grid lines, if required.
1886 if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
1887 draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
1888 if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
1889 draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
1890 if (x <= 0 || y <= 0 ||
1891 map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
1892 map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
1893 draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
1896 draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1899 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1900 game_state *state, int dir, game_ui *ui,
1901 float animtime, float flashtime)
1903 int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
1907 if (ds->drag_visible) {
1908 blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
1909 draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
1910 ds->drag_visible = FALSE;
1914 * The initial contents of the window are not guaranteed and
1915 * can vary with front ends. To be on the safe side, all games
1916 * should start by drawing a big background-colour rectangle
1917 * covering the whole window.
1922 game_compute_size(&state->p, TILESIZE, &ww, &wh);
1923 draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
1924 draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
1927 draw_update(dr, 0, 0, ww, wh);
1932 if (flash_type == 1)
1933 flash = (int)(flashtime * FOUR / flash_length);
1935 flash = 1 + (int)(flashtime * THREE / flash_length);
1939 for (y = 0; y < h; y++)
1940 for (x = 0; x < w; x++) {
1941 int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
1942 int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
1951 if (flash_type == 1) {
1956 } else if (flash_type == 2) {
1961 tv = (tv + flash) % FOUR;
1963 bv = (bv + flash) % FOUR;
1969 if (ds->drawn[y*w+x] != v) {
1970 draw_square(dr, ds, &state->p, state->map, x, y, v);
1971 ds->drawn[y*w+x] = v;
1976 * Draw the dragged colour blob if any.
1978 if (ui->drag_colour > -2) {
1979 ds->dragx = ui->dragx - TILESIZE/2 - 2;
1980 ds->dragy = ui->dragy - TILESIZE/2 - 2;
1981 blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
1982 draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2,
1983 (ui->drag_colour < 0 ? COL_BACKGROUND :
1984 COL_0 + ui->drag_colour), COL_GRID);
1985 draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
1986 ds->drag_visible = TRUE;
1990 static float game_anim_length(game_state *oldstate, game_state *newstate,
1991 int dir, game_ui *ui)
1996 static float game_flash_length(game_state *oldstate, game_state *newstate,
1997 int dir, game_ui *ui)
1999 if (!oldstate->completed && newstate->completed &&
2000 !oldstate->cheated && !newstate->cheated) {
2001 if (flash_type < 0) {
2002 char *env = getenv("MAP_ALTERNATIVE_FLASH");
2004 flash_type = atoi(env);
2007 flash_length = (flash_type == 1 ? 0.50 : 0.30);
2009 return flash_length;
2014 static int game_wants_statusbar(void)
2019 static int game_timing_state(game_state *state, game_ui *ui)
2024 static void game_print_size(game_params *params, float *x, float *y)
2029 * I'll use 4mm squares by default, I think. Simplest way to
2030 * compute this size is to compute the pixel puzzle size at a
2031 * given tile size and then scale.
2033 game_compute_size(params, 400, &pw, &ph);
2038 static void game_print(drawing *dr, game_state *state, int tilesize)
2040 int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2041 int ink, c[FOUR], i;
2043 int *coords, ncoords, coordsize;
2045 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2046 struct { int tilesize; } ads, *ds = &ads;
2047 ads.tilesize = tilesize;
2049 ink = print_mono_colour(dr, 0);
2050 for (i = 0; i < FOUR; i++)
2051 c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0],
2052 map_colours[i][1], map_colours[i][2]);
2057 print_line_width(dr, TILESIZE / 16);
2060 * Draw a single filled polygon around each region.
2062 for (r = 0; r < n; r++) {
2063 int octants[8], lastdir, d1, d2, ox, oy;
2066 * Start by finding a point on the region boundary. Any
2067 * point will do. To do this, we'll search for a square
2068 * containing the region and then decide which corner of it
2072 for (y = 0; y < h; y++) {
2073 for (x = 0; x < w; x++) {
2074 if (state->map->map[wh*0+y*w+x] == r ||
2075 state->map->map[wh*1+y*w+x] == r ||
2076 state->map->map[wh*2+y*w+x] == r ||
2077 state->map->map[wh*3+y*w+x] == r)
2083 assert(y < h && x < w); /* we must have found one somewhere */
2085 * This is the first square in lexicographic order which
2086 * contains part of this region. Therefore, one of the top
2087 * two corners of the square must be what we're after. The
2088 * only case in which it isn't the top left one is if the
2089 * square is diagonally divided and the region is in the
2090 * bottom right half.
2092 if (state->map->map[wh*TE+y*w+x] != r &&
2093 state->map->map[wh*LE+y*w+x] != r)
2094 x++; /* could just as well have done y++ */
2097 * Now we have a point on the region boundary. Trace around
2098 * the region until we come back to this point,
2099 * accumulating coordinates for a polygon draw operation as
2109 * There are eight possible directions we could head in
2110 * from here. We identify them by octant numbers, and
2111 * we also use octant numbers to identify the spaces
2124 octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
2125 octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
2126 octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
2127 octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
2128 octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
2129 octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
2130 octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
2131 octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
2134 for (i = 0; i < 8; i++)
2135 if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
2142 /* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */
2143 assert(d1 != -1 && d2 != -1);
2148 * Now we're heading in direction d1. Save the current
2151 if (ncoords + 2 > coordsize) {
2153 coords = sresize(coords, coordsize, int);
2155 coords[ncoords++] = COORD(x);
2156 coords[ncoords++] = COORD(y);
2159 * Compute the new coordinates.
2161 x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
2162 y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
2163 assert(x >= 0 && x <= w && y >= 0 && y <= h);
2166 } while (x != ox || y != oy);
2168 draw_polygon(dr, coords, ncoords/2,
2169 state->colouring[r] >= 0 ?
2170 c[state->colouring[r]] : -1, ink);
2179 const struct game thegame = {
2187 TRUE, game_configure, custom_params,
2195 FALSE, game_text_format,
2203 20, game_compute_size, game_set_size,
2206 game_free_drawstate,
2210 TRUE, TRUE, game_print_size, game_print,
2211 game_wants_statusbar,
2212 FALSE, game_timing_state,
2213 0, /* mouse_priorities */