2 * map.c: Game involving four-colouring a map.
9 * - better four-colouring algorithm?
22 * In standalone solver mode, `verbose' is a variable which can be
23 * set by command-line option; in debugging mode it's simply always
26 #if defined STANDALONE_SOLVER
27 #define SOLVER_DIAGNOSTICS
29 #elif defined SOLVER_DIAGNOSTICS
34 * I don't seriously anticipate wanting to change the number of
35 * colours used in this game, but it doesn't cost much to use a
36 * #define just in case :-)
39 #define THREE (FOUR-1)
44 * Ghastly run-time configuration option, just for Gareth (again).
46 static int flash_type = -1;
47 static float flash_length;
50 * Difficulty levels. I do some macro ickery here to ensure that my
51 * enum and the various forms of my name list always match up.
57 A(RECURSE,Unreasonable,u)
58 #define ENUM(upper,title,lower) DIFF_ ## upper,
59 #define TITLE(upper,title,lower) #title,
60 #define ENCODE(upper,title,lower) #lower
61 #define CONFIG(upper,title,lower) ":" #title
62 enum { DIFFLIST(ENUM) DIFFCOUNT };
63 static char const *const map_diffnames[] = { DIFFLIST(TITLE) };
64 static char const map_diffchars[] = DIFFLIST(ENCODE);
65 #define DIFFCONFIG DIFFLIST(CONFIG)
67 enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */
72 COL_0, COL_1, COL_2, COL_3,
73 COL_ERROR, COL_ERRTEXT,
88 int *edgex, *edgey; /* position of a point on each edge */
89 int *regionx, *regiony; /* position of a point in each region */
95 int *colouring, *pencil;
96 int completed, cheated;
99 static game_params *default_params(void)
101 game_params *ret = snew(game_params);
103 #ifdef PORTRAIT_SCREEN
111 ret->diff = DIFF_NORMAL;
116 static const struct game_params map_presets[] = {
117 #ifdef PORTRAIT_SCREEN
118 {16, 18, 30, DIFF_EASY},
119 {16, 18, 30, DIFF_NORMAL},
120 {16, 18, 30, DIFF_HARD},
121 {16, 18, 30, DIFF_RECURSE},
122 {25, 30, 75, DIFF_NORMAL},
123 {25, 30, 75, DIFF_HARD},
125 {20, 15, 30, DIFF_EASY},
126 {20, 15, 30, DIFF_NORMAL},
127 {20, 15, 30, DIFF_HARD},
128 {20, 15, 30, DIFF_RECURSE},
129 {30, 25, 75, DIFF_NORMAL},
130 {30, 25, 75, DIFF_HARD},
134 static int game_fetch_preset(int i, char **name, game_params **params)
139 if (i < 0 || i >= lenof(map_presets))
142 ret = snew(game_params);
143 *ret = map_presets[i];
145 sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
146 map_diffnames[ret->diff]);
153 static void free_params(game_params *params)
158 static game_params *dup_params(const game_params *params)
160 game_params *ret = snew(game_params);
161 *ret = *params; /* structure copy */
165 static void decode_params(game_params *params, char const *string)
167 char const *p = string;
170 while (*p && isdigit((unsigned char)*p)) p++;
174 while (*p && isdigit((unsigned char)*p)) p++;
176 params->h = params->w;
181 while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
183 params->n = params->w * params->h / 8;
188 for (i = 0; i < DIFFCOUNT; i++)
189 if (*p == map_diffchars[i])
195 static char *encode_params(const game_params *params, int full)
199 sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
201 sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
206 static config_item *game_configure(const game_params *params)
211 ret = snewn(5, config_item);
213 ret[0].name = "Width";
214 ret[0].type = C_STRING;
215 sprintf(buf, "%d", params->w);
216 ret[0].u.string.sval = dupstr(buf);
218 ret[1].name = "Height";
219 ret[1].type = C_STRING;
220 sprintf(buf, "%d", params->h);
221 ret[1].u.string.sval = dupstr(buf);
223 ret[2].name = "Regions";
224 ret[2].type = C_STRING;
225 sprintf(buf, "%d", params->n);
226 ret[2].u.string.sval = dupstr(buf);
228 ret[3].name = "Difficulty";
229 ret[3].type = C_CHOICES;
230 ret[3].u.choices.choicenames = DIFFCONFIG;
231 ret[3].u.choices.selected = params->diff;
239 static game_params *custom_params(const config_item *cfg)
241 game_params *ret = snew(game_params);
243 ret->w = atoi(cfg[0].u.string.sval);
244 ret->h = atoi(cfg[1].u.string.sval);
245 ret->n = atoi(cfg[2].u.string.sval);
246 ret->diff = cfg[3].u.choices.selected;
251 static const char *validate_params(const game_params *params, int full)
253 if (params->w < 2 || params->h < 2)
254 return "Width and height must be at least two";
256 return "Must have at least five regions";
257 if (params->n > params->w * params->h)
258 return "Too many regions to fit in grid";
262 /* ----------------------------------------------------------------------
263 * Cumulative frequency table functions.
267 * Initialise a cumulative frequency table. (Hardly worth writing
268 * this function; all it does is to initialise everything in the
271 static void cf_init(int *table, int n)
275 for (i = 0; i < n; i++)
280 * Increment the count of symbol `sym' by `count'.
282 static void cf_add(int *table, int n, int sym, int count)
299 * Cumulative frequency lookup: return the total count of symbols
300 * with value less than `sym'.
302 static int cf_clookup(int *table, int n, int sym)
304 int bit, index, limit, count;
309 assert(0 < sym && sym <= n);
311 count = table[0]; /* start with the whole table size */
321 * Find the least number with its lowest set bit in this
322 * position which is greater than or equal to sym.
324 index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
327 count -= table[index];
338 * Single frequency lookup: return the count of symbol `sym'.
340 static int cf_slookup(int *table, int n, int sym)
344 assert(0 <= sym && sym < n);
348 for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
349 count -= table[sym+bit];
355 * Return the largest symbol index such that the cumulative
356 * frequency up to that symbol is less than _or equal to_ count.
358 static int cf_whichsym(int *table, int n, int count) {
361 assert(count >= 0 && count < table[0]);
372 if (count >= top - table[sym+bit])
375 top -= table[sym+bit];
384 /* ----------------------------------------------------------------------
387 * FIXME: this isn't entirely optimal at present, because it
388 * inherently prioritises growing the largest region since there
389 * are more squares adjacent to it. This acts as a destabilising
390 * influence leading to a few large regions and mostly small ones.
391 * It might be better to do it some other way.
394 #define WEIGHT_INCREASED 2 /* for increased perimeter */
395 #define WEIGHT_DECREASED 4 /* for decreased perimeter */
396 #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
399 * Look at a square and decide which colours can be extended into
402 * If called with index < 0, it adds together one of
403 * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
404 * colour that has a valid extension (according to the effect that
405 * it would have on the perimeter of the region being extended) and
406 * returns the overall total.
408 * If called with index >= 0, it returns one of the possible
409 * colours depending on the value of index, in such a way that the
410 * number of possible inputs which would give rise to a given
411 * return value correspond to the weight of that value.
413 static int extend_options(int w, int h, int n, int *map,
414 int x, int y, int index)
420 if (map[y*w+x] >= 0) {
422 return 0; /* can't do this square at all */
426 * Fetch the eight neighbours of this square, in order around
429 for (dy = -1; dy <= +1; dy++)
430 for (dx = -1; dx <= +1; dx++) {
431 int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx));
432 if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h)
433 col[index] = map[(y+dy)*w+(x+dx)];
439 * Iterate over each colour that might be feasible.
441 * FIXME: this routine currently has O(n) running time. We
442 * could turn it into O(FOUR) by only bothering to iterate over
443 * the colours mentioned in the four neighbouring squares.
446 for (c = 0; c < n; c++) {
447 int count, neighbours, runs;
450 * One of the even indices of col (representing the
451 * orthogonal neighbours of this square) must be equal to
452 * c, or else this square is not adjacent to region c and
453 * obviously cannot become an extension of it at this time.
456 for (i = 0; i < 8; i += 2)
463 * Now we know this square is adjacent to region c. The
464 * next question is, would extending it cause the region to
465 * become non-simply-connected? If so, we mustn't do it.
467 * We determine this by looking around col to see if we can
468 * find more than one separate run of colour c.
471 for (i = 0; i < 8; i++)
472 if (col[i] == c && col[(i+1) & 7] != c)
480 * This square is a possibility. Determine its effect on
481 * the region's perimeter (computed from the number of
482 * orthogonal neighbours - 1 means a perimeter increase, 3
483 * a decrease, 2 no change; 4 is impossible because the
484 * region would already not be simply connected) and we're
487 assert(neighbours > 0 && neighbours < 4);
488 count = (neighbours == 1 ? WEIGHT_INCREASED :
489 neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);
492 if (index >= 0 && index < count)
503 static void genmap(int w, int h, int n, int *map, random_state *rs)
510 tmp = snewn(wh, int);
513 * Clear the map, and set up `tmp' as a list of grid indices.
515 for (i = 0; i < wh; i++) {
521 * Place the region seeds by selecting n members from `tmp'.
524 for (i = 0; i < n; i++) {
525 int j = random_upto(rs, k);
531 * Re-initialise `tmp' as a cumulative frequency table. This
532 * will store the number of possible region colours we can
533 * extend into each square.
538 * Go through the grid and set up the initial cumulative
541 for (y = 0; y < h; y++)
542 for (x = 0; x < w; x++)
543 cf_add(tmp, wh, y*w+x,
544 extend_options(w, h, n, map, x, y, -1));
547 * Now repeatedly choose a square we can extend a region into,
551 int k = random_upto(rs, tmp[0]);
556 sq = cf_whichsym(tmp, wh, k);
557 k -= cf_clookup(tmp, wh, sq);
560 colour = extend_options(w, h, n, map, x, y, k);
565 * Re-scan the nine cells around the one we've just
568 for (yy = max(y-1, 0); yy < min(y+2, h); yy++)
569 for (xx = max(x-1, 0); xx < min(x+2, w); xx++) {
570 cf_add(tmp, wh, yy*w+xx,
571 -cf_slookup(tmp, wh, yy*w+xx) +
572 extend_options(w, h, n, map, xx, yy, -1));
577 * Finally, go through and normalise the region labels into
578 * order, meaning that indistinguishable maps are actually
581 for (i = 0; i < n; i++)
584 for (i = 0; i < wh; i++) {
588 map[i] = tmp[map[i]];
594 /* ----------------------------------------------------------------------
595 * Functions to handle graphs.
599 * Having got a map in a square grid, convert it into a graph
602 static int gengraph(int w, int h, int n, int *map, int *graph)
607 * Start by setting the graph up as an adjacency matrix. We'll
608 * turn it into a list later.
610 for (i = 0; i < n*n; i++)
614 * Iterate over the map looking for all adjacencies.
616 for (y = 0; y < h; y++)
617 for (x = 0; x < w; x++) {
620 if (x+1 < w && (vx = map[y*w+(x+1)]) != v)
621 graph[v*n+vx] = graph[vx*n+v] = 1;
622 if (y+1 < h && (vy = map[(y+1)*w+x]) != v)
623 graph[v*n+vy] = graph[vy*n+v] = 1;
627 * Turn the matrix into a list.
629 for (i = j = 0; i < n*n; i++)
636 static int graph_edge_index(int *graph, int n, int ngraph, int i, int j)
643 while (top - bot > 1) {
644 mid = (top + bot) / 2;
647 else if (graph[mid] < v)
655 #define graph_adjacent(graph, n, ngraph, i, j) \
656 (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)
658 static int graph_vertex_start(int *graph, int n, int ngraph, int i)
665 while (top - bot > 1) {
666 mid = (top + bot) / 2;
675 /* ----------------------------------------------------------------------
676 * Generate a four-colouring of a graph.
678 * FIXME: it would be nice if we could convert this recursion into
679 * pseudo-recursion using some sort of explicit stack array, for
680 * the sake of the Palm port and its limited stack.
683 static int fourcolour_recurse(int *graph, int n, int ngraph,
684 int *colouring, int *scratch, random_state *rs)
686 int nfree, nvert, start, i, j, k, c, ci;
690 * Find the smallest number of free colours in any uncoloured
691 * vertex, and count the number of such vertices.
694 nfree = FIVE; /* start off bigger than FOUR! */
696 for (i = 0; i < n; i++)
697 if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) {
698 if (nfree > scratch[i*FIVE+FOUR]) {
699 nfree = scratch[i*FIVE+FOUR];
706 * If there aren't any uncoloured vertices at all, we're done.
709 return TRUE; /* we've got a colouring! */
712 * Pick a random vertex in that set.
714 j = random_upto(rs, nvert);
715 for (i = 0; i < n; i++)
716 if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
720 start = graph_vertex_start(graph, n, ngraph, i);
723 * Loop over the possible colours for i, and recurse for each
727 for (c = 0; c < FOUR; c++)
728 if (scratch[i*FIVE+c] == 0)
730 shuffle(cs, ci, sizeof(*cs), rs);
736 * Fill in this colour.
741 * Update the scratch space to reflect a new neighbour
742 * of this colour for each neighbour of vertex i.
744 for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
746 if (scratch[k*FIVE+c] == 0)
747 scratch[k*FIVE+FOUR]--;
754 if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
755 return TRUE; /* got one! */
758 * If that didn't work, clean up and try again with a
761 for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
764 if (scratch[k*FIVE+c] == 0)
765 scratch[k*FIVE+FOUR]++;
771 * If we reach here, we were unable to find a colouring at all.
772 * (This doesn't necessarily mean the Four Colour Theorem is
773 * violated; it might just mean we've gone down a dead end and
774 * need to back up and look somewhere else. It's only an FCT
775 * violation if we get all the way back up to the top level and
781 static void fourcolour(int *graph, int n, int ngraph, int *colouring,
788 * For each vertex and each colour, we store the number of
789 * neighbours that have that colour. Also, we store the number
790 * of free colours for the vertex.
792 scratch = snewn(n * FIVE, int);
793 for (i = 0; i < n * FIVE; i++)
794 scratch[i] = (i % FIVE == FOUR ? FOUR : 0);
797 * Clear the colouring to start with.
799 for (i = 0; i < n; i++)
802 i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
803 assert(i); /* by the Four Colour Theorem :-) */
808 /* ----------------------------------------------------------------------
809 * Non-recursive solver.
812 struct solver_scratch {
813 unsigned char *possible; /* bitmap of colours for each region */
821 #ifdef SOLVER_DIAGNOSTICS
828 static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
830 struct solver_scratch *sc;
832 sc = snew(struct solver_scratch);
836 sc->possible = snewn(n, unsigned char);
838 sc->bfsqueue = snewn(n, int);
839 sc->bfscolour = snewn(n, int);
840 #ifdef SOLVER_DIAGNOSTICS
841 sc->bfsprev = snewn(n, int);
847 static void free_scratch(struct solver_scratch *sc)
851 sfree(sc->bfscolour);
852 #ifdef SOLVER_DIAGNOSTICS
859 * Count the bits in a word. Only needs to cope with FOUR bits.
861 static int bitcount(int word)
863 assert(FOUR <= 4); /* or this needs changing */
864 word = ((word & 0xA) >> 1) + (word & 0x5);
865 word = ((word & 0xC) >> 2) + (word & 0x3);
869 #ifdef SOLVER_DIAGNOSTICS
870 static const char colnames[FOUR] = { 'R', 'Y', 'G', 'B' };
873 static int place_colour(struct solver_scratch *sc,
874 int *colouring, int index, int colour
875 #ifdef SOLVER_DIAGNOSTICS
880 int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
883 if (!(sc->possible[index] & (1 << colour))) {
884 #ifdef SOLVER_DIAGNOSTICS
886 printf("%*scannot place %c in region %d\n", 2*sc->depth, "",
887 colnames[colour], index);
889 return FALSE; /* can't do it */
892 sc->possible[index] = 1 << colour;
893 colouring[index] = colour;
895 #ifdef SOLVER_DIAGNOSTICS
897 printf("%*s%s %c in region %d\n", 2*sc->depth, "",
898 verb, colnames[colour], index);
902 * Rule out this colour from all the region's neighbours.
904 for (j = graph_vertex_start(graph, n, ngraph, index);
905 j < ngraph && graph[j] < n*(index+1); j++) {
906 k = graph[j] - index*n;
907 #ifdef SOLVER_DIAGNOSTICS
908 if (verbose && (sc->possible[k] & (1 << colour)))
909 printf("%*s ruling out %c in region %d\n", 2*sc->depth, "",
910 colnames[colour], k);
912 sc->possible[k] &= ~(1 << colour);
918 #ifdef SOLVER_DIAGNOSTICS
919 static char *colourset(char *buf, int set)
923 const char *sep = "";
925 for (i = 0; i < FOUR; i++)
926 if (set & (1 << i)) {
927 p += sprintf(p, "%s%c", sep, colnames[i]);
936 * Returns 0 for impossible, 1 for success, 2 for failure to
937 * converge (i.e. puzzle is either ambiguous or just too
940 static int map_solver(struct solver_scratch *sc,
941 int *graph, int n, int ngraph, int *colouring,
946 if (sc->depth == 0) {
948 * Initialise scratch space.
950 for (i = 0; i < n; i++)
951 sc->possible[i] = (1 << FOUR) - 1;
956 for (i = 0; i < n; i++)
957 if (colouring[i] >= 0) {
958 if (!place_colour(sc, colouring, i, colouring[i]
959 #ifdef SOLVER_DIAGNOSTICS
963 #ifdef SOLVER_DIAGNOSTICS
965 printf("%*sinitial clue set is inconsistent\n",
968 return 0; /* the clues aren't even consistent! */
974 * Now repeatedly loop until we find nothing further to do.
977 int done_something = FALSE;
979 if (difficulty < DIFF_EASY)
980 break; /* can't do anything at all! */
983 * Simplest possible deduction: find a region with only one
986 for (i = 0; i < n; i++) if (colouring[i] < 0) {
987 int p = sc->possible[i];
990 #ifdef SOLVER_DIAGNOSTICS
992 printf("%*sregion %d has no possible colours left\n",
995 return 0; /* puzzle is inconsistent */
998 if ((p & (p-1)) == 0) { /* p is a power of two */
1000 for (c = 0; c < FOUR; c++)
1004 ret = place_colour(sc, colouring, i, c
1005 #ifdef SOLVER_DIAGNOSTICS
1010 * place_colour() can only fail if colour c was not
1011 * even a _possibility_ for region i, and we're
1012 * pretty sure it was because we checked before
1013 * calling place_colour(). So we can safely assert
1014 * here rather than having to return a nice
1015 * friendly error code.
1018 done_something = TRUE;
1025 if (difficulty < DIFF_NORMAL)
1026 break; /* can't do anything harder */
1029 * Failing that, go up one level. Look for pairs of regions
1030 * which (a) both have the same pair of possible colours,
1031 * (b) are adjacent to one another, (c) are adjacent to the
1032 * same region, and (d) that region still thinks it has one
1033 * or both of those possible colours.
1035 * Simplest way to do this is by going through the graph
1036 * edge by edge, so that we start with property (b) and
1037 * then look for (a) and finally (c) and (d).
1039 for (i = 0; i < ngraph; i++) {
1040 int j1 = graph[i] / n, j2 = graph[i] % n;
1042 #ifdef SOLVER_DIAGNOSTICS
1043 int started = FALSE;
1047 continue; /* done it already, other way round */
1049 if (colouring[j1] >= 0 || colouring[j2] >= 0)
1050 continue; /* they're not undecided */
1052 if (sc->possible[j1] != sc->possible[j2])
1053 continue; /* they don't have the same possibles */
1055 v = sc->possible[j1];
1057 * See if v contains exactly two set bits.
1059 v2 = v & -v; /* find lowest set bit */
1060 v2 = v & ~v2; /* clear it */
1061 if (v2 == 0 || (v2 & (v2-1)) != 0) /* not power of 2 */
1065 * We've found regions j1 and j2 satisfying properties
1066 * (a) and (b): they have two possible colours between
1067 * them, and since they're adjacent to one another they
1068 * must use _both_ those colours between them.
1069 * Therefore, if they are both adjacent to any other
1070 * region then that region cannot be either colour.
1072 * Go through the neighbours of j1 and see if any are
1075 for (j = graph_vertex_start(graph, n, ngraph, j1);
1076 j < ngraph && graph[j] < n*(j1+1); j++) {
1077 k = graph[j] - j1*n;
1078 if (graph_adjacent(graph, n, ngraph, k, j2) &&
1079 (sc->possible[k] & v)) {
1080 #ifdef SOLVER_DIAGNOSTICS
1084 printf("%*sadjacent regions %d,%d share colours"
1085 " %s\n", 2*sc->depth, "", j1, j2,
1088 printf("%*s ruling out %s in region %d\n",2*sc->depth,
1089 "", colourset(buf, sc->possible[k] & v), k);
1092 sc->possible[k] &= ~v;
1093 done_something = TRUE;
1101 if (difficulty < DIFF_HARD)
1102 break; /* can't do anything harder */
1105 * Right; now we get creative. Now we're going to look for
1106 * `forcing chains'. A forcing chain is a path through the
1107 * graph with the following properties:
1109 * (a) Each vertex on the path has precisely two possible
1112 * (b) Each pair of vertices which are adjacent on the
1113 * path share at least one possible colour in common.
1115 * (c) Each vertex in the middle of the path shares _both_
1116 * of its colours with at least one of its neighbours
1117 * (not the same one with both neighbours).
1119 * These together imply that at least one of the possible
1120 * colour choices at one end of the path forces _all_ the
1121 * rest of the colours along the path. In order to make
1122 * real use of this, we need further properties:
1124 * (c) Ruling out some colour C from the vertex at one end
1125 * of the path forces the vertex at the other end to
1128 * (d) The two end vertices are mutually adjacent to some
1131 * (e) That third vertex currently has C as a possibility.
1133 * If we can find all of that lot, we can deduce that at
1134 * least one of the two ends of the forcing chain has
1135 * colour C, and that therefore the mutually adjacent third
1138 * To find forcing chains, we're going to start a bfs at
1139 * each suitable vertex of the graph, once for each of its
1140 * two possible colours.
1142 for (i = 0; i < n; i++) {
1145 if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2)
1148 for (c = 0; c < FOUR; c++)
1149 if (sc->possible[i] & (1 << c)) {
1150 int j, k, gi, origc, currc, head, tail;
1152 * Try a bfs from this vertex, ruling out
1155 * Within this loop, we work in colour bitmaps
1156 * rather than actual colours, because
1157 * converting back and forth is a needless
1158 * computational expense.
1163 for (j = 0; j < n; j++) {
1164 sc->bfscolour[j] = -1;
1165 #ifdef SOLVER_DIAGNOSTICS
1166 sc->bfsprev[j] = -1;
1170 sc->bfsqueue[tail++] = i;
1171 sc->bfscolour[i] = sc->possible[i] &~ origc;
1173 while (head < tail) {
1174 j = sc->bfsqueue[head++];
1175 currc = sc->bfscolour[j];
1178 * Try neighbours of j.
1180 for (gi = graph_vertex_start(graph, n, ngraph, j);
1181 gi < ngraph && graph[gi] < n*(j+1); gi++) {
1182 k = graph[gi] - j*n;
1185 * To continue with the bfs in vertex
1186 * k, we need k to be
1187 * (a) not already visited
1188 * (b) have two possible colours
1189 * (c) those colours include currc.
1192 if (sc->bfscolour[k] < 0 &&
1194 bitcount(sc->possible[k]) == 2 &&
1195 (sc->possible[k] & currc)) {
1196 sc->bfsqueue[tail++] = k;
1198 sc->possible[k] &~ currc;
1199 #ifdef SOLVER_DIAGNOSTICS
1205 * One other possibility is that k
1206 * might be the region in which we can
1207 * make a real deduction: if it's
1208 * adjacent to i, contains currc as a
1209 * possibility, and currc is equal to
1210 * the original colour we ruled out.
1212 if (currc == origc &&
1213 graph_adjacent(graph, n, ngraph, k, i) &&
1214 (sc->possible[k] & currc)) {
1215 #ifdef SOLVER_DIAGNOSTICS
1218 const char *sep = "";
1221 printf("%*sforcing chain, colour %s, ",
1223 colourset(buf, origc));
1224 for (r = j; r != -1; r = sc->bfsprev[r]) {
1225 printf("%s%d", sep, r);
1228 printf("\n%*s ruling out %s in region"
1229 " %d\n", 2*sc->depth, "",
1230 colourset(buf, origc), k);
1233 sc->possible[k] &= ~origc;
1234 done_something = TRUE;
1243 if (!done_something)
1248 * See if we've got a complete solution, and return if so.
1250 for (i = 0; i < n; i++)
1251 if (colouring[i] < 0)
1254 #ifdef SOLVER_DIAGNOSTICS
1256 printf("%*sone solution found\n", 2*sc->depth, "");
1258 return 1; /* success! */
1262 * If recursion is not permissible, we now give up.
1264 if (difficulty < DIFF_RECURSE) {
1265 #ifdef SOLVER_DIAGNOSTICS
1267 printf("%*sunable to proceed further without recursion\n",
1270 return 2; /* unable to complete */
1274 * Now we've got to do something recursive. So first hunt for a
1275 * currently-most-constrained region.
1279 struct solver_scratch *rsc;
1280 int *subcolouring, *origcolouring;
1282 int we_already_got_one;
1287 for (i = 0; i < n; i++) if (colouring[i] < 0) {
1288 int p = sc->possible[i];
1289 enum { compile_time_assertion = 1 / (FOUR <= 4) };
1292 /* Count the set bits. */
1293 c = (p & 5) + ((p >> 1) & 5);
1294 c = (c & 3) + ((c >> 2) & 3);
1295 assert(c > 1); /* or colouring[i] would be >= 0 */
1303 assert(best >= 0); /* or we'd be solved already */
1305 #ifdef SOLVER_DIAGNOSTICS
1307 printf("%*srecursing on region %d\n", 2*sc->depth, "", best);
1311 * Now iterate over the possible colours for this region.
1313 rsc = new_scratch(graph, n, ngraph);
1314 rsc->depth = sc->depth + 1;
1315 origcolouring = snewn(n, int);
1316 memcpy(origcolouring, colouring, n * sizeof(int));
1317 subcolouring = snewn(n, int);
1318 we_already_got_one = FALSE;
1321 for (i = 0; i < FOUR; i++) {
1322 if (!(sc->possible[best] & (1 << i)))
1325 memcpy(rsc->possible, sc->possible, n);
1326 memcpy(subcolouring, origcolouring, n * sizeof(int));
1328 place_colour(rsc, subcolouring, best, i
1329 #ifdef SOLVER_DIAGNOSTICS
1334 subret = map_solver(rsc, graph, n, ngraph,
1335 subcolouring, difficulty);
1337 #ifdef SOLVER_DIAGNOSTICS
1339 printf("%*sretracting %c in region %d; found %s\n",
1340 2*sc->depth, "", colnames[i], best,
1341 subret == 0 ? "no solutions" :
1342 subret == 1 ? "one solution" : "multiple solutions");
1347 * If this possibility turned up more than one valid
1348 * solution, or if it turned up one and we already had
1349 * one, we're definitely ambiguous.
1351 if (subret == 2 || (subret == 1 && we_already_got_one)) {
1357 * If this possibility turned up one valid solution and
1358 * it's the first we've seen, copy it into the output.
1361 memcpy(colouring, subcolouring, n * sizeof(int));
1362 we_already_got_one = TRUE;
1367 * Otherwise, this guess led to a contradiction, so we
1372 sfree(origcolouring);
1373 sfree(subcolouring);
1376 #ifdef SOLVER_DIAGNOSTICS
1377 if (verbose && sc->depth == 0) {
1378 printf("%*s%s found\n",
1380 ret == 0 ? "no solutions" :
1381 ret == 1 ? "one solution" : "multiple solutions");
1388 /* ----------------------------------------------------------------------
1389 * Game generation main function.
1392 static char *new_game_desc(const game_params *params, random_state *rs,
1393 char **aux, int interactive)
1395 struct solver_scratch *sc = NULL;
1396 int *map, *graph, ngraph, *colouring, *colouring2, *regions;
1397 int i, j, w, h, n, solveret, cfreq[FOUR];
1400 #ifdef GENERATION_DIAGNOSTICS
1404 int retlen, retsize;
1413 map = snewn(wh, int);
1414 graph = snewn(n*n, int);
1415 colouring = snewn(n, int);
1416 colouring2 = snewn(n, int);
1417 regions = snewn(n, int);
1420 * This is the minimum difficulty below which we'll completely
1421 * reject a map design. Normally we set this to one below the
1422 * requested difficulty, ensuring that we have the right
1423 * result. However, for particularly dense maps or maps with
1424 * particularly few regions it might not be possible to get the
1425 * desired difficulty, so we will eventually drop this down to
1426 * -1 to indicate that any old map will do.
1428 mindiff = params->diff;
1436 genmap(w, h, n, map, rs);
1438 #ifdef GENERATION_DIAGNOSTICS
1439 for (y = 0; y < h; y++) {
1440 for (x = 0; x < w; x++) {
1445 putchar('a' + v-36);
1447 putchar('A' + v-10);
1456 * Convert the map into a graph.
1458 ngraph = gengraph(w, h, n, map, graph);
1460 #ifdef GENERATION_DIAGNOSTICS
1461 for (i = 0; i < ngraph; i++)
1462 printf("%d-%d\n", graph[i]/n, graph[i]%n);
1468 fourcolour(graph, n, ngraph, colouring, rs);
1470 #ifdef GENERATION_DIAGNOSTICS
1471 for (i = 0; i < n; i++)
1472 printf("%d: %d\n", i, colouring[i]);
1474 for (y = 0; y < h; y++) {
1475 for (x = 0; x < w; x++) {
1476 int v = colouring[map[y*w+x]];
1478 putchar('a' + v-36);
1480 putchar('A' + v-10);
1489 * Encode the solution as an aux string.
1491 if (*aux) /* in case we've come round again */
1493 retlen = retsize = 0;
1495 for (i = 0; i < n; i++) {
1498 if (colouring[i] < 0)
1501 len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i);
1502 if (retlen + len >= retsize) {
1503 retsize = retlen + len + 256;
1504 ret = sresize(ret, retsize, char);
1506 strcpy(ret + retlen, buf);
1512 * Remove the region colours one by one, keeping
1513 * solubility. Also ensure that there always remains at
1514 * least one region of every colour, so that the user can
1515 * drag from somewhere.
1517 for (i = 0; i < FOUR; i++)
1519 for (i = 0; i < n; i++) {
1521 cfreq[colouring[i]]++;
1523 for (i = 0; i < FOUR; i++)
1527 shuffle(regions, n, sizeof(*regions), rs);
1529 if (sc) free_scratch(sc);
1530 sc = new_scratch(graph, n, ngraph);
1532 for (i = 0; i < n; i++) {
1535 if (cfreq[colouring[j]] == 1)
1536 continue; /* can't remove last region of colour */
1538 memcpy(colouring2, colouring, n*sizeof(int));
1540 solveret = map_solver(sc, graph, n, ngraph, colouring2,
1542 assert(solveret >= 0); /* mustn't be impossible! */
1543 if (solveret == 1) {
1544 cfreq[colouring[j]]--;
1549 #ifdef GENERATION_DIAGNOSTICS
1550 for (i = 0; i < n; i++)
1551 if (colouring[i] >= 0) {
1555 putchar('a' + i-36);
1557 putchar('A' + i-10);
1560 printf(": %d\n", colouring[i]);
1565 * Finally, check that the puzzle is _at least_ as hard as
1566 * required, and indeed that it isn't already solved.
1567 * (Calling map_solver with negative difficulty ensures the
1568 * latter - if a solver which _does nothing_ can solve it,
1571 memcpy(colouring2, colouring, n*sizeof(int));
1572 if (map_solver(sc, graph, n, ngraph, colouring2,
1573 mindiff - 1) == 1) {
1575 * Drop minimum difficulty if necessary.
1577 if (mindiff > 0 && (n < 9 || n > 2*wh/3)) {
1579 mindiff = 0; /* give up and go for Easy */
1588 * Encode as a game ID. We do this by:
1590 * - first going along the horizontal edges row by row, and
1591 * then the vertical edges column by column
1592 * - encoding the lengths of runs of edges and runs of
1594 * - the decoder will reconstitute the region boundaries from
1595 * this and automatically number them the same way we did
1596 * - then we encode the initial region colours in a Slant-like
1597 * fashion (digits 0-3 interspersed with letters giving
1598 * lengths of runs of empty spaces).
1600 retlen = retsize = 0;
1607 * Start with a notional non-edge, so that there'll be an
1608 * explicit `a' to distinguish the case where we start with
1614 for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
1615 int x, y, dx, dy, v;
1618 /* Horizontal edge. */
1624 /* Vertical edge. */
1625 x = (i - w*(h-1)) / h;
1626 y = (i - w*(h-1)) % h;
1631 if (retlen + 10 >= retsize) {
1632 retsize = retlen + 256;
1633 ret = sresize(ret, retsize, char);
1636 v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);
1639 ret[retlen++] = 'a'-1 + run;
1644 * 'z' is a special case in this encoding. Rather
1645 * than meaning a run of 26 and a state switch, it
1646 * means a run of 25 and _no_ state switch, because
1647 * otherwise there'd be no way to encode runs of
1651 ret[retlen++] = 'z';
1658 ret[retlen++] = 'a'-1 + run;
1659 ret[retlen++] = ',';
1662 for (i = 0; i < n; i++) {
1663 if (retlen + 10 >= retsize) {
1664 retsize = retlen + 256;
1665 ret = sresize(ret, retsize, char);
1668 if (colouring[i] < 0) {
1670 * In _this_ encoding, 'z' is a run of 26, since
1671 * there's no implicit state switch after each run.
1672 * Confusingly different, but more compact.
1675 ret[retlen++] = 'z';
1681 ret[retlen++] = 'a'-1 + run;
1682 ret[retlen++] = '0' + colouring[i];
1687 ret[retlen++] = 'a'-1 + run;
1690 assert(retlen < retsize);
1703 static const char *parse_edge_list(const game_params *params,
1704 const char **desc, int *map)
1706 int w = params->w, h = params->h, wh = w*h, n = params->n;
1707 int i, k, pos, state;
1708 const char *p = *desc;
1710 dsf_init(map+wh, wh);
1716 * Parse the game description to get the list of edges, and
1717 * build up a disjoint set forest as we go (by identifying
1718 * pairs of squares whenever the edge list shows a non-edge).
1720 while (*p && *p != ',') {
1721 if (*p < 'a' || *p > 'z')
1722 return "Unexpected character in edge list";
1733 } else if (pos < w*(h-1)) {
1734 /* Horizontal edge. */
1739 } else if (pos < 2*wh-w-h) {
1740 /* Vertical edge. */
1741 x = (pos - w*(h-1)) / h;
1742 y = (pos - w*(h-1)) % h;
1746 return "Too much data in edge list";
1748 dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));
1756 assert(pos <= 2*wh-w-h);
1758 return "Too little data in edge list";
1761 * Now go through again and allocate region numbers.
1764 for (i = 0; i < wh; i++)
1766 for (i = 0; i < wh; i++) {
1767 k = dsf_canonify(map+wh, i);
1773 return "Edge list defines the wrong number of regions";
1780 static const char *validate_desc(const game_params *params, const char *desc)
1782 int w = params->w, h = params->h, wh = w*h, n = params->n;
1787 map = snewn(2*wh, int);
1788 ret = parse_edge_list(params, &desc, map);
1794 return "Expected comma before clue list";
1795 desc++; /* eat comma */
1799 if (*desc >= '0' && *desc < '0'+FOUR)
1801 else if (*desc >= 'a' && *desc <= 'z')
1802 area += *desc - 'a' + 1;
1804 return "Unexpected character in clue list";
1808 return "Too little data in clue list";
1810 return "Too much data in clue list";
1815 static game_state *new_game(midend *me, const game_params *params,
1818 int w = params->w, h = params->h, wh = w*h, n = params->n;
1821 game_state *state = snew(game_state);
1824 state->colouring = snewn(n, int);
1825 for (i = 0; i < n; i++)
1826 state->colouring[i] = -1;
1827 state->pencil = snewn(n, int);
1828 for (i = 0; i < n; i++)
1829 state->pencil[i] = 0;
1831 state->completed = state->cheated = FALSE;
1833 state->map = snew(struct map);
1834 state->map->refcount = 1;
1835 state->map->map = snewn(wh*4, int);
1836 state->map->graph = snewn(n*n, int);
1838 state->map->immutable = snewn(n, int);
1839 for (i = 0; i < n; i++)
1840 state->map->immutable[i] = FALSE;
1846 ret = parse_edge_list(params, &p, state->map->map);
1851 * Set up the other three quadrants in `map'.
1853 for (i = wh; i < 4*wh; i++)
1854 state->map->map[i] = state->map->map[i % wh];
1860 * Now process the clue list.
1864 if (*p >= '0' && *p < '0'+FOUR) {
1865 state->colouring[pos] = *p - '0';
1866 state->map->immutable[pos] = TRUE;
1869 assert(*p >= 'a' && *p <= 'z');
1870 pos += *p - 'a' + 1;
1876 state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);
1879 * Attempt to smooth out some of the more jagged region
1880 * outlines by the judicious use of diagonally divided squares.
1883 random_state *rs = random_new(desc, strlen(desc));
1884 int *squares = snewn(wh, int);
1887 for (i = 0; i < wh; i++)
1889 shuffle(squares, wh, sizeof(*squares), rs);
1892 done_something = FALSE;
1893 for (i = 0; i < wh; i++) {
1894 int y = squares[i] / w, x = squares[i] % w;
1895 int c = state->map->map[y*w+x];
1898 if (x == 0 || x == w-1 || y == 0 || y == h-1)
1901 if (state->map->map[TE * wh + y*w+x] !=
1902 state->map->map[BE * wh + y*w+x])
1905 tc = state->map->map[BE * wh + (y-1)*w+x];
1906 bc = state->map->map[TE * wh + (y+1)*w+x];
1907 lc = state->map->map[RE * wh + y*w+(x-1)];
1908 rc = state->map->map[LE * wh + y*w+(x+1)];
1911 * If this square is adjacent on two sides to one
1912 * region and on the other two sides to the other
1913 * region, and is itself one of the two regions, we can
1914 * adjust it so that it's a diagonal.
1916 if (tc != bc && (tc == c || bc == c)) {
1917 if ((lc == tc && rc == bc) ||
1918 (lc == bc && rc == tc)) {
1919 state->map->map[TE * wh + y*w+x] = tc;
1920 state->map->map[BE * wh + y*w+x] = bc;
1921 state->map->map[LE * wh + y*w+x] = lc;
1922 state->map->map[RE * wh + y*w+x] = rc;
1923 done_something = TRUE;
1927 } while (done_something);
1933 * Analyse the map to find a canonical line segment
1934 * corresponding to each edge, and a canonical point
1935 * corresponding to each region. The former are where we'll
1936 * eventually put error markers; the latter are where we'll put
1937 * per-region flags such as numbers (when in diagnostic mode).
1940 int *bestx, *besty, *an, pass;
1941 float *ax, *ay, *best;
1943 ax = snewn(state->map->ngraph + n, float);
1944 ay = snewn(state->map->ngraph + n, float);
1945 an = snewn(state->map->ngraph + n, int);
1946 bestx = snewn(state->map->ngraph + n, int);
1947 besty = snewn(state->map->ngraph + n, int);
1948 best = snewn(state->map->ngraph + n, float);
1950 for (i = 0; i < state->map->ngraph + n; i++) {
1951 bestx[i] = besty[i] = -1;
1952 best[i] = (float)(2*(w+h)+1);
1953 ax[i] = ay[i] = 0.0F;
1958 * We make two passes over the map, finding all the line
1959 * segments separating regions and all the suitable points
1960 * within regions. In the first pass, we compute the
1961 * _average_ x and y coordinate of all the points in a
1962 * given class; in the second pass, for each such average
1963 * point, we find the candidate closest to it and call that
1966 * Line segments are considered to have coordinates in
1967 * their centre. Thus, at least one coordinate for any line
1968 * segment is always something-and-a-half; so we store our
1969 * coordinates as twice their normal value.
1971 for (pass = 0; pass < 2; pass++) {
1974 for (y = 0; y < h; y++)
1975 for (x = 0; x < w; x++) {
1976 int ex[4], ey[4], ea[4], eb[4], en = 0;
1979 * Look for an edge to the right of this
1980 * square, an edge below it, and an edge in the
1981 * middle of it. Also look to see if the point
1982 * at the bottom right of this square is on an
1983 * edge (and isn't a place where more than two
1988 ea[en] = state->map->map[RE * wh + y*w+x];
1989 eb[en] = state->map->map[LE * wh + y*w+(x+1)];
1996 ea[en] = state->map->map[BE * wh + y*w+x];
1997 eb[en] = state->map->map[TE * wh + (y+1)*w+x];
2003 ea[en] = state->map->map[TE * wh + y*w+x];
2004 eb[en] = state->map->map[BE * wh + y*w+x];
2009 if (x+1 < w && y+1 < h) {
2010 /* bottom right corner */
2011 int oct[8], othercol, nchanges;
2012 oct[0] = state->map->map[RE * wh + y*w+x];
2013 oct[1] = state->map->map[LE * wh + y*w+(x+1)];
2014 oct[2] = state->map->map[BE * wh + y*w+(x+1)];
2015 oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)];
2016 oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)];
2017 oct[5] = state->map->map[RE * wh + (y+1)*w+x];
2018 oct[6] = state->map->map[TE * wh + (y+1)*w+x];
2019 oct[7] = state->map->map[BE * wh + y*w+x];
2023 for (i = 0; i < 8; i++) {
2024 if (oct[i] != oct[0]) {
2027 else if (othercol != oct[i])
2028 break; /* three colours at this point */
2030 if (oct[i] != oct[(i+1) & 7])
2035 * Now if there are exactly two regions at
2036 * this point (not one, and not three or
2037 * more), and only two changes around the
2038 * loop, then this is a valid place to put
2041 if (i == 8 && othercol >= 0 && nchanges == 2) {
2050 * If there's exactly _one_ region at this
2051 * point, on the other hand, it's a valid
2052 * place to put a region centre.
2055 ea[en] = eb[en] = oct[0];
2063 * Now process the points we've found, one by
2066 for (i = 0; i < en; i++) {
2067 int emin = min(ea[i], eb[i]);
2068 int emax = max(ea[i], eb[i]);
2074 graph_edge_index(state->map->graph, n,
2075 state->map->ngraph, emin,
2079 gindex = state->map->ngraph + emin;
2082 assert(gindex >= 0);
2086 * In pass 0, accumulate the values
2087 * we'll use to compute the average
2090 ax[gindex] += ex[i];
2091 ay[gindex] += ey[i];
2095 * In pass 1, work out whether this
2096 * point is closer to the average than
2097 * the last one we've seen.
2101 assert(an[gindex] > 0);
2102 dx = ex[i] - ax[gindex];
2103 dy = ey[i] - ay[gindex];
2104 d = (float)sqrt(dx*dx + dy*dy);
2105 if (d < best[gindex]) {
2107 bestx[gindex] = ex[i];
2108 besty[gindex] = ey[i];
2115 for (i = 0; i < state->map->ngraph + n; i++)
2123 state->map->edgex = snewn(state->map->ngraph, int);
2124 state->map->edgey = snewn(state->map->ngraph, int);
2125 memcpy(state->map->edgex, bestx, state->map->ngraph * sizeof(int));
2126 memcpy(state->map->edgey, besty, state->map->ngraph * sizeof(int));
2128 state->map->regionx = snewn(n, int);
2129 state->map->regiony = snewn(n, int);
2130 memcpy(state->map->regionx, bestx + state->map->ngraph, n*sizeof(int));
2131 memcpy(state->map->regiony, besty + state->map->ngraph, n*sizeof(int));
2133 for (i = 0; i < state->map->ngraph; i++)
2134 if (state->map->edgex[i] < 0) {
2135 /* Find the other representation of this edge. */
2136 int e = state->map->graph[i];
2137 int iprime = graph_edge_index(state->map->graph, n,
2138 state->map->ngraph, e%n, e/n);
2139 assert(state->map->edgex[iprime] >= 0);
2140 state->map->edgex[i] = state->map->edgex[iprime];
2141 state->map->edgey[i] = state->map->edgey[iprime];
2155 static game_state *dup_game(const game_state *state)
2157 game_state *ret = snew(game_state);
2160 ret->colouring = snewn(state->p.n, int);
2161 memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
2162 ret->pencil = snewn(state->p.n, int);
2163 memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int));
2164 ret->map = state->map;
2165 ret->map->refcount++;
2166 ret->completed = state->completed;
2167 ret->cheated = state->cheated;
2172 static void free_game(game_state *state)
2174 if (--state->map->refcount <= 0) {
2175 sfree(state->map->map);
2176 sfree(state->map->graph);
2177 sfree(state->map->immutable);
2178 sfree(state->map->edgex);
2179 sfree(state->map->edgey);
2180 sfree(state->map->regionx);
2181 sfree(state->map->regiony);
2184 sfree(state->pencil);
2185 sfree(state->colouring);
2189 static char *solve_game(const game_state *state, const game_state *currstate,
2190 const char *aux, const char **error)
2197 struct solver_scratch *sc;
2201 int retlen, retsize;
2203 colouring = snewn(state->map->n, int);
2204 memcpy(colouring, state->colouring, state->map->n * sizeof(int));
2206 sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
2207 sret = map_solver(sc, state->map->graph, state->map->n,
2208 state->map->ngraph, colouring, DIFFCOUNT-1);
2214 *error = "Puzzle is inconsistent";
2216 *error = "Unable to find a unique solution for this puzzle";
2221 ret = snewn(retsize, char);
2225 for (i = 0; i < state->map->n; i++) {
2228 assert(colouring[i] >= 0);
2229 if (colouring[i] == currstate->colouring[i])
2231 assert(!state->map->immutable[i]);
2233 len = sprintf(buf, ";%d:%d", colouring[i], i);
2234 if (retlen + len >= retsize) {
2235 retsize = retlen + len + 256;
2236 ret = sresize(ret, retsize, char);
2238 strcpy(ret + retlen, buf);
2249 static int game_can_format_as_text_now(const game_params *params)
2254 static char *game_text_format(const game_state *state)
2263 * - -2 means no drag currently active.
2264 * - >=0 means we're dragging a solid colour.
2265 * - -1 means we're dragging a blank space, and drag_pencil
2266 * might or might not add some pencil-mark stipples to that.
2273 int cur_x, cur_y, cur_visible, cur_moved, cur_lastmove;
2276 static game_ui *new_ui(const game_state *state)
2278 game_ui *ui = snew(game_ui);
2279 ui->dragx = ui->dragy = -1;
2280 ui->drag_colour = -2;
2281 ui->drag_pencil = 0;
2282 ui->show_numbers = FALSE;
2283 ui->cur_x = ui->cur_y = ui->cur_visible = ui->cur_moved = 0;
2284 ui->cur_lastmove = 0;
2288 static void free_ui(game_ui *ui)
2293 static char *encode_ui(const game_ui *ui)
2298 static void decode_ui(game_ui *ui, const char *encoding)
2302 static void game_changed_state(game_ui *ui, const game_state *oldstate,
2303 const game_state *newstate)
2307 struct game_drawstate {
2309 unsigned long *drawn, *todraw;
2311 int dragx, dragy, drag_visible;
2315 /* Flags in `drawn'. */
2316 #define ERR_BASE 0x00800000L
2317 #define ERR_MASK 0xFF800000L
2318 #define PENCIL_T_BASE 0x00080000L
2319 #define PENCIL_T_MASK 0x00780000L
2320 #define PENCIL_B_BASE 0x00008000L
2321 #define PENCIL_B_MASK 0x00078000L
2322 #define PENCIL_MASK 0x007F8000L
2323 #define SHOW_NUMBERS 0x00004000L
2325 #define TILESIZE (ds->tilesize)
2326 #define BORDER (TILESIZE)
2327 #define COORD(x) ( (x) * TILESIZE + BORDER )
2328 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
2331 * EPSILON_FOO are epsilons added to absolute cursor position by
2332 * cursor movement, such that in pathological cases (e.g. a very
2333 * small diamond-shaped area) it's relatively easy to select the
2334 * region you wanted.
2337 #define EPSILON_X(button) (((button) == CURSOR_RIGHT) ? +1 : \
2338 ((button) == CURSOR_LEFT) ? -1 : 0)
2339 #define EPSILON_Y(button) (((button) == CURSOR_DOWN) ? +1 : \
2340 ((button) == CURSOR_UP) ? -1 : 0)
2343 static int region_from_coords(const game_state *state,
2344 const game_drawstate *ds, int x, int y)
2346 int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
2347 int tx = FROMCOORD(x), ty = FROMCOORD(y);
2348 int dx = x - COORD(tx), dy = y - COORD(ty);
2351 if (tx < 0 || tx >= w || ty < 0 || ty >= h)
2352 return -1; /* border */
2354 quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
2355 quadrant = (quadrant == 0 ? BE :
2356 quadrant == 1 ? LE :
2357 quadrant == 2 ? RE : TE);
2359 return state->map->map[quadrant * wh + ty*w+tx];
2362 static char *interpret_move(const game_state *state, game_ui *ui,
2363 const game_drawstate *ds,
2364 int x, int y, int button)
2366 char *bufp, buf[256];
2370 * Enable or disable numeric labels on regions.
2372 if (button == 'l' || button == 'L') {
2373 ui->show_numbers = !ui->show_numbers;
2377 if (IS_CURSOR_MOVE(button)) {
2378 move_cursor(button, &ui->cur_x, &ui->cur_y, state->p.w, state->p.h, 0);
2379 ui->cur_visible = 1;
2381 ui->cur_lastmove = button;
2382 ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(button);
2383 ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(button);
2386 if (IS_CURSOR_SELECT(button)) {
2387 if (!ui->cur_visible) {
2388 ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove);
2389 ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove);
2390 ui->cur_visible = 1;
2393 if (ui->drag_colour == -2) { /* not currently cursor-dragging, start. */
2394 int r = region_from_coords(state, ds, ui->dragx, ui->dragy);
2396 ui->drag_colour = state->colouring[r];
2397 ui->drag_pencil = (ui->drag_colour >= 0) ? 0 : state->pencil[r];
2399 ui->drag_colour = -1;
2400 ui->drag_pencil = 0;
2404 } else { /* currently cursor-dragging; drop the colour in the new region. */
2405 x = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove);
2406 y = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove);
2407 alt_button = (button == CURSOR_SELECT2) ? 1 : 0;
2408 /* Double-select removes current colour. */
2409 if (!ui->cur_moved) ui->drag_colour = -1;
2414 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2415 int r = region_from_coords(state, ds, x, y);
2418 ui->drag_colour = state->colouring[r];
2419 ui->drag_pencil = state->pencil[r];
2420 if (ui->drag_colour >= 0)
2421 ui->drag_pencil = 0; /* should be already, but double-check */
2423 ui->drag_colour = -1;
2424 ui->drag_pencil = 0;
2428 ui->cur_visible = 0;
2432 if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
2433 ui->drag_colour > -2) {
2439 if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
2440 ui->drag_colour > -2) {
2441 alt_button = (button == RIGHT_RELEASE) ? 1 : 0;
2449 int r = region_from_coords(state, ds, x, y);
2450 int c = ui->drag_colour;
2451 int p = ui->drag_pencil;
2455 * Cancel the drag, whatever happens.
2457 ui->drag_colour = -2;
2460 return UI_UPDATE; /* drag into border; do nothing else */
2462 if (state->map->immutable[r])
2463 return UI_UPDATE; /* can't change this region */
2465 if (state->colouring[r] == c && state->pencil[r] == p)
2466 return UI_UPDATE; /* don't _need_ to change this region */
2469 if (state->colouring[r] >= 0) {
2470 /* Can't pencil on a coloured region */
2472 } else if (c >= 0) {
2473 /* Right-dragging from colour to blank toggles one pencil */
2474 p = state->pencil[r] ^ (1 << c);
2477 /* Otherwise, right-dragging from blank to blank is equivalent
2478 * to left-dragging. */
2482 oldp = state->pencil[r];
2483 if (c != state->colouring[r]) {
2484 bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
2490 for (i = 0; i < FOUR; i++)
2491 if ((oldp ^ p) & (1 << i))
2492 bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r);
2495 return dupstr(buf+1); /* ignore first semicolon */
2499 static game_state *execute_move(const game_state *state, const char *move)
2502 game_state *ret = dup_game(state);
2513 if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
2514 sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
2515 k >= 0 && k < state->p.n) {
2518 if (ret->colouring[k] >= 0) {
2525 ret->pencil[k] ^= 1 << (c - '0');
2527 ret->colouring[k] = (c == 'C' ? -1 : c - '0');
2530 } else if (*move == 'S') {
2532 ret->cheated = TRUE;
2538 if (*move && *move != ';') {
2547 * Check for completion.
2549 if (!ret->completed) {
2552 for (i = 0; i < n; i++)
2553 if (ret->colouring[i] < 0) {
2559 for (i = 0; i < ret->map->ngraph; i++) {
2560 int j = ret->map->graph[i] / n;
2561 int k = ret->map->graph[i] % n;
2562 if (ret->colouring[j] == ret->colouring[k]) {
2570 ret->completed = TRUE;
2576 /* ----------------------------------------------------------------------
2580 static void game_compute_size(const game_params *params, int tilesize,
2583 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2584 struct { int tilesize; } ads, *ds = &ads;
2585 ads.tilesize = tilesize;
2587 *x = params->w * TILESIZE + 2 * BORDER + 1;
2588 *y = params->h * TILESIZE + 2 * BORDER + 1;
2591 static void game_set_size(drawing *dr, game_drawstate *ds,
2592 const game_params *params, int tilesize)
2594 ds->tilesize = tilesize;
2596 assert(!ds->bl); /* set_size is never called twice */
2597 ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
2600 const float map_colours[FOUR][3] = {
2601 #ifdef VIVID_COLOURS
2602 /* Use more vivid colours (e.g. on the Pocket PC) */
2603 {0.75F, 0.25F, 0.25F},
2606 {0.85F, 0.85F, 0.1F},
2611 {0.55F, 0.45F, 0.35F},
2614 const int map_hatching[FOUR] = {
2615 HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
2618 static float *game_colours(frontend *fe, int *ncolours)
2620 float *ret = snewn(3 * NCOLOURS, float);
2622 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2624 ret[COL_GRID * 3 + 0] = 0.0F;
2625 ret[COL_GRID * 3 + 1] = 0.0F;
2626 ret[COL_GRID * 3 + 2] = 0.0F;
2628 memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
2629 memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
2630 memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
2631 memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
2633 ret[COL_ERROR * 3 + 0] = 1.0F;
2634 ret[COL_ERROR * 3 + 1] = 0.0F;
2635 ret[COL_ERROR * 3 + 2] = 0.0F;
2637 ret[COL_ERRTEXT * 3 + 0] = 1.0F;
2638 ret[COL_ERRTEXT * 3 + 1] = 1.0F;
2639 ret[COL_ERRTEXT * 3 + 2] = 1.0F;
2641 *ncolours = NCOLOURS;
2645 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2647 struct game_drawstate *ds = snew(struct game_drawstate);
2651 ds->drawn = snewn(state->p.w * state->p.h, unsigned long);
2652 for (i = 0; i < state->p.w * state->p.h; i++)
2653 ds->drawn[i] = 0xFFFFL;
2654 ds->todraw = snewn(state->p.w * state->p.h, unsigned long);
2655 ds->started = FALSE;
2657 ds->drag_visible = FALSE;
2658 ds->dragx = ds->dragy = -1;
2663 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2668 blitter_free(dr, ds->bl);
2672 static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
2680 coords[0] = x - TILESIZE*2/5;
2683 coords[3] = y - TILESIZE*2/5;
2684 coords[4] = x + TILESIZE*2/5;
2687 coords[7] = y + TILESIZE*2/5;
2688 draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
2691 * Draw an exclamation mark in the diamond. This turns out to
2692 * look unpleasantly off-centre if done via draw_text, so I do
2693 * it by hand on the basis that exclamation marks aren't that
2694 * difficult to draw...
2697 yext = TILESIZE*2/5 - (xext*2+2);
2698 draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
2700 draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
2703 static void draw_square(drawing *dr, game_drawstate *ds,
2704 const game_params *params, struct map *map,
2705 int x, int y, unsigned long v)
2707 int w = params->w, h = params->h, wh = w*h;
2708 int tv, bv, xo, yo, i, j, oldj;
2709 unsigned long errs, pencil, show_numbers;
2711 errs = v & ERR_MASK;
2713 pencil = v & PENCIL_MASK;
2715 show_numbers = v & SHOW_NUMBERS;
2720 clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2723 * Draw the region colour.
2725 draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
2726 (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
2728 * Draw the second region colour, if this is a diagonally
2731 if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
2733 coords[0] = COORD(x)-1;
2734 coords[1] = COORD(y+1)+1;
2735 if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
2736 coords[2] = COORD(x+1)+1;
2738 coords[2] = COORD(x)-1;
2739 coords[3] = COORD(y)-1;
2740 coords[4] = COORD(x+1)+1;
2741 coords[5] = COORD(y+1)+1;
2742 draw_polygon(dr, coords, 3,
2743 (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
2747 * Draw `pencil marks'. Currently we arrange these in a square
2748 * formation, which means we may be in trouble if the value of
2749 * FOUR changes later...
2752 for (yo = 0; yo < 4; yo++)
2753 for (xo = 0; xo < 4; xo++) {
2754 int te = map->map[TE * wh + y*w+x];
2757 e = (yo < xo && yo < 3-xo ? TE :
2758 yo > xo && yo > 3-xo ? BE :
2760 ee = map->map[e * wh + y*w+x];
2762 if (xo != (yo * 2 + 1) % 5)
2766 if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
2770 (map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x]))
2771 continue; /* avoid TL-BR diagonal line */
2773 (map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x]))
2774 continue; /* avoid BL-TR diagonal line */
2776 draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5,
2777 COORD(y) + (yo+1)*TILESIZE/5,
2778 TILESIZE/7, COL_0 + c, COL_0 + c);
2782 * Draw the grid lines, if required.
2784 if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
2785 draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
2786 if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
2787 draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
2788 if (x <= 0 || y <= 0 ||
2789 map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
2790 map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
2791 draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
2794 * Draw error markers.
2796 for (yo = 0; yo < 3; yo++)
2797 for (xo = 0; xo < 3; xo++)
2798 if (errs & (ERR_BASE << (yo*3+xo)))
2800 (COORD(x)*2+TILESIZE*xo)/2,
2801 (COORD(y)*2+TILESIZE*yo)/2);
2804 * Draw region numbers, if desired.
2808 for (i = 0; i < 2; i++) {
2809 j = map->map[(i?BE:TE)*wh+y*w+x];
2814 xo = map->regionx[j] - 2*x;
2815 yo = map->regiony[j] - 2*y;
2816 if (xo >= 0 && xo <= 2 && yo >= 0 && yo <= 2) {
2818 sprintf(buf, "%d", j);
2819 draw_text(dr, (COORD(x)*2+TILESIZE*xo)/2,
2820 (COORD(y)*2+TILESIZE*yo)/2,
2821 FONT_VARIABLE, 3*TILESIZE/5,
2822 ALIGN_HCENTRE|ALIGN_VCENTRE,
2830 draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2833 static void game_redraw(drawing *dr, game_drawstate *ds,
2834 const game_state *oldstate, const game_state *state,
2835 int dir, const game_ui *ui,
2836 float animtime, float flashtime)
2838 int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2842 if (ds->drag_visible) {
2843 blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
2844 draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
2845 ds->drag_visible = FALSE;
2849 * The initial contents of the window are not guaranteed and
2850 * can vary with front ends. To be on the safe side, all games
2851 * should start by drawing a big background-colour rectangle
2852 * covering the whole window.
2857 game_compute_size(&state->p, TILESIZE, &ww, &wh);
2858 draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
2859 draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
2862 draw_update(dr, 0, 0, ww, wh);
2867 if (flash_type == 1)
2868 flash = (int)(flashtime * FOUR / flash_length);
2870 flash = 1 + (int)(flashtime * THREE / flash_length);
2875 * Set up the `todraw' array.
2877 for (y = 0; y < h; y++)
2878 for (x = 0; x < w; x++) {
2879 int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
2880 int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
2889 if (flash_type == 1) {
2894 } else if (flash_type == 2) {
2899 tv = (tv + flash) % FOUR;
2901 bv = (bv + flash) % FOUR;
2910 for (i = 0; i < FOUR; i++) {
2911 if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 &&
2912 (state->pencil[state->map->map[TE * wh + y*w+x]] & (1<<i)))
2913 v |= PENCIL_T_BASE << i;
2914 if (state->colouring[state->map->map[BE * wh + y*w+x]] < 0 &&
2915 (state->pencil[state->map->map[BE * wh + y*w+x]] & (1<<i)))
2916 v |= PENCIL_B_BASE << i;
2919 if (ui->show_numbers)
2922 ds->todraw[y*w+x] = v;
2926 * Add error markers to the `todraw' array.
2928 for (i = 0; i < state->map->ngraph; i++) {
2929 int v1 = state->map->graph[i] / n;
2930 int v2 = state->map->graph[i] % n;
2933 if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
2935 if (state->colouring[v1] != state->colouring[v2])
2938 x = state->map->edgex[i];
2939 y = state->map->edgey[i];
2944 ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo);
2947 ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2);
2951 ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo);
2953 if (xo == 0 && yo == 0) {
2954 assert(x > 0 && y > 0);
2955 ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2);
2960 * Now actually draw everything.
2962 for (y = 0; y < h; y++)
2963 for (x = 0; x < w; x++) {
2964 unsigned long v = ds->todraw[y*w+x];
2965 if (ds->drawn[y*w+x] != v) {
2966 draw_square(dr, ds, &state->p, state->map, x, y, v);
2967 ds->drawn[y*w+x] = v;
2972 * Draw the dragged colour blob if any.
2974 if ((ui->drag_colour > -2) || ui->cur_visible) {
2976 if (ui->drag_colour >= 0)
2977 bg = COL_0 + ui->drag_colour;
2978 else if (ui->drag_colour == -1) {
2979 bg = COL_BACKGROUND;
2981 int r = region_from_coords(state, ds, ui->dragx, ui->dragy);
2982 int c = (r < 0) ? -1 : state->colouring[r];
2983 assert(ui->cur_visible);
2985 bg = (c < 0) ? COL_BACKGROUND : COL_0 + c;
2989 ds->dragx = ui->dragx - TILESIZE/2 - 2;
2990 ds->dragy = ui->dragy - TILESIZE/2 - 2;
2991 blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
2992 draw_circle(dr, ui->dragx, ui->dragy,
2993 iscur ? TILESIZE/4 : TILESIZE/2, bg, COL_GRID);
2994 for (i = 0; i < FOUR; i++)
2995 if (ui->drag_pencil & (1 << i))
2996 draw_circle(dr, ui->dragx + ((i*4+2)%10-3) * TILESIZE/10,
2997 ui->dragy + (i*2-3) * TILESIZE/10,
2998 TILESIZE/8, COL_0 + i, COL_0 + i);
2999 draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
3000 ds->drag_visible = TRUE;
3004 static float game_anim_length(const game_state *oldstate,
3005 const game_state *newstate, int dir, game_ui *ui)
3010 static float game_flash_length(const game_state *oldstate,
3011 const game_state *newstate, int dir, game_ui *ui)
3013 if (!oldstate->completed && newstate->completed &&
3014 !oldstate->cheated && !newstate->cheated) {
3015 if (flash_type < 0) {
3016 char *env = getenv("MAP_ALTERNATIVE_FLASH");
3018 flash_type = atoi(env);
3021 flash_length = (flash_type == 1 ? 0.50F : 0.30F);
3023 return flash_length;
3028 static int game_status(const game_state *state)
3030 return state->completed ? +1 : 0;
3033 static int game_timing_state(const game_state *state, game_ui *ui)
3038 static void game_print_size(const game_params *params, float *x, float *y)
3043 * I'll use 4mm squares by default, I think. Simplest way to
3044 * compute this size is to compute the pixel puzzle size at a
3045 * given tile size and then scale.
3047 game_compute_size(params, 400, &pw, &ph);
3052 static void game_print(drawing *dr, const game_state *state, int tilesize)
3054 int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
3055 int ink, c[FOUR], i;
3057 int *coords, ncoords, coordsize;
3059 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3060 struct { int tilesize; } ads, *ds = &ads;
3061 /* We can't call game_set_size() here because we don't want a blitter */
3062 ads.tilesize = tilesize;
3064 ink = print_mono_colour(dr, 0);
3065 for (i = 0; i < FOUR; i++)
3066 c[i] = print_rgb_hatched_colour(dr, map_colours[i][0],
3067 map_colours[i][1], map_colours[i][2],
3073 print_line_width(dr, TILESIZE / 16);
3076 * Draw a single filled polygon around each region.
3078 for (r = 0; r < n; r++) {
3079 int octants[8], lastdir, d1, d2, ox, oy;
3082 * Start by finding a point on the region boundary. Any
3083 * point will do. To do this, we'll search for a square
3084 * containing the region and then decide which corner of it
3088 for (y = 0; y < h; y++) {
3089 for (x = 0; x < w; x++) {
3090 if (state->map->map[wh*0+y*w+x] == r ||
3091 state->map->map[wh*1+y*w+x] == r ||
3092 state->map->map[wh*2+y*w+x] == r ||
3093 state->map->map[wh*3+y*w+x] == r)
3099 assert(y < h && x < w); /* we must have found one somewhere */
3101 * This is the first square in lexicographic order which
3102 * contains part of this region. Therefore, one of the top
3103 * two corners of the square must be what we're after. The
3104 * only case in which it isn't the top left one is if the
3105 * square is diagonally divided and the region is in the
3106 * bottom right half.
3108 if (state->map->map[wh*TE+y*w+x] != r &&
3109 state->map->map[wh*LE+y*w+x] != r)
3110 x++; /* could just as well have done y++ */
3113 * Now we have a point on the region boundary. Trace around
3114 * the region until we come back to this point,
3115 * accumulating coordinates for a polygon draw operation as
3125 * There are eight possible directions we could head in
3126 * from here. We identify them by octant numbers, and
3127 * we also use octant numbers to identify the spaces
3140 octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
3141 octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
3142 octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
3143 octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
3144 octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
3145 octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
3146 octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
3147 octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
3150 for (i = 0; i < 8; i++)
3151 if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
3159 assert(d1 != -1 && d2 != -1);
3164 * Now we're heading in direction d1. Save the current
3167 if (ncoords + 2 > coordsize) {
3169 coords = sresize(coords, coordsize, int);
3171 coords[ncoords++] = COORD(x);
3172 coords[ncoords++] = COORD(y);
3175 * Compute the new coordinates.
3177 x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
3178 y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
3179 assert(x >= 0 && x <= w && y >= 0 && y <= h);
3182 } while (x != ox || y != oy);
3184 draw_polygon(dr, coords, ncoords/2,
3185 state->colouring[r] >= 0 ?
3186 c[state->colouring[r]] : -1, ink);
3195 const struct game thegame = {
3196 "Map", "games.map", "map",
3198 game_fetch_preset, NULL,
3203 TRUE, game_configure, custom_params,
3211 FALSE, game_can_format_as_text_now, game_text_format,
3219 20, game_compute_size, game_set_size,
3222 game_free_drawstate,
3227 TRUE, TRUE, game_print_size, game_print,
3228 FALSE, /* wants_statusbar */
3229 FALSE, game_timing_state,
3233 #ifdef STANDALONE_SOLVER
3235 int main(int argc, char **argv)
3239 char *id = NULL, *desc;
3242 int ret, diff, really_verbose = FALSE;
3243 struct solver_scratch *sc;
3246 while (--argc > 0) {
3248 if (!strcmp(p, "-v")) {
3249 really_verbose = TRUE;
3250 } else if (!strcmp(p, "-g")) {
3252 } else if (*p == '-') {
3253 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
3261 fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
3265 desc = strchr(id, ':');
3267 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3272 p = default_params();
3273 decode_params(p, id);
3274 err = validate_desc(p, desc);
3276 fprintf(stderr, "%s: %s\n", argv[0], err);
3279 s = new_game(NULL, p, desc);
3281 sc = new_scratch(s->map->graph, s->map->n, s->map->ngraph);
3284 * When solving an Easy puzzle, we don't want to bother the
3285 * user with Hard-level deductions. For this reason, we grade
3286 * the puzzle internally before doing anything else.
3288 ret = -1; /* placate optimiser */
3289 for (diff = 0; diff < DIFFCOUNT; diff++) {
3290 for (i = 0; i < s->map->n; i++)
3291 if (!s->map->immutable[i])
3292 s->colouring[i] = -1;
3293 ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
3294 s->colouring, diff);
3299 if (diff == DIFFCOUNT) {
3301 printf("Difficulty rating: harder than Hard, or ambiguous\n");
3303 printf("Unable to find a unique solution\n");
3307 printf("Difficulty rating: impossible (no solution exists)\n");
3309 printf("Difficulty rating: %s\n", map_diffnames[diff]);
3311 verbose = really_verbose;
3312 for (i = 0; i < s->map->n; i++)
3313 if (!s->map->immutable[i])
3314 s->colouring[i] = -1;
3315 ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
3316 s->colouring, diff);
3318 printf("Puzzle is inconsistent\n");
3322 for (i = 0; i < s->map->n; i++) {
3323 printf("%5d <- %c%c", i, colnames[s->colouring[i]],
3324 (col < 6 && i+1 < s->map->n ? ' ' : '\n'));
3337 /* vim: set shiftwidth=4 tabstop=8: */