chiark / gitweb /
Enhance Filling's solver to handle large ghost regions.
[sgt-puzzles.git] / map.c
1 /*
2  * map.c: Game involving four-colouring a map.
3  */
4
5 /*
6  * TODO:
7  * 
8  *  - clue marking
9  *  - better four-colouring algorithm?
10  */
11
12 #include <stdio.h>
13 #include <stdlib.h>
14 #include <string.h>
15 #include <assert.h>
16 #include <ctype.h>
17 #include <math.h>
18
19 #include "puzzles.h"
20
21 /*
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
24  * true.
25  */
26 #if defined STANDALONE_SOLVER
27 #define SOLVER_DIAGNOSTICS
28 int verbose = FALSE;
29 #elif defined SOLVER_DIAGNOSTICS
30 #define verbose TRUE
31 #endif
32
33 /*
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 :-)
37  */
38 #define FOUR 4
39 #define THREE (FOUR-1)
40 #define FIVE (FOUR+1)
41 #define SIX (FOUR+2)
42
43 /*
44  * Ghastly run-time configuration option, just for Gareth (again).
45  */
46 static int flash_type = -1;
47 static float flash_length;
48
49 /*
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.
52  */
53 #define DIFFLIST(A) \
54     A(EASY,Easy,e) \
55     A(NORMAL,Normal,n) \
56     A(HARD,Hard,h) \
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)
66
67 enum { TE, BE, LE, RE };               /* top/bottom/left/right edges */
68
69 enum {
70     COL_BACKGROUND,
71     COL_GRID,
72     COL_0, COL_1, COL_2, COL_3,
73     COL_ERROR, COL_ERRTEXT,
74     NCOLOURS
75 };
76
77 struct game_params {
78     int w, h, n, diff;
79 };
80
81 struct map {
82     int refcount;
83     int *map;
84     int *graph;
85     int n;
86     int ngraph;
87     int *immutable;
88     int *edgex, *edgey;                /* position of a point on each edge */
89     int *regionx, *regiony;            /* position of a point in each region */
90 };
91
92 struct game_state {
93     game_params p;
94     struct map *map;
95     int *colouring, *pencil;
96     int completed, cheated;
97 };
98
99 static game_params *default_params(void)
100 {
101     game_params *ret = snew(game_params);
102
103 #ifdef PORTRAIT_SCREEN
104     ret->w = 16;
105     ret->h = 18;
106 #else
107     ret->w = 20;
108     ret->h = 15;
109 #endif
110     ret->n = 30;
111     ret->diff = DIFF_NORMAL;
112
113     return ret;
114 }
115
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},
124 #else
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},
131 #endif
132 };
133
134 static int game_fetch_preset(int i, char **name, game_params **params)
135 {
136     game_params *ret;
137     char str[80];
138
139     if (i < 0 || i >= lenof(map_presets))
140         return FALSE;
141
142     ret = snew(game_params);
143     *ret = map_presets[i];
144
145     sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
146             map_diffnames[ret->diff]);
147
148     *name = dupstr(str);
149     *params = ret;
150     return TRUE;
151 }
152
153 static void free_params(game_params *params)
154 {
155     sfree(params);
156 }
157
158 static game_params *dup_params(const game_params *params)
159 {
160     game_params *ret = snew(game_params);
161     *ret = *params;                    /* structure copy */
162     return ret;
163 }
164
165 static void decode_params(game_params *params, char const *string)
166 {
167     char const *p = string;
168
169     params->w = atoi(p);
170     while (*p && isdigit((unsigned char)*p)) p++;
171     if (*p == 'x') {
172         p++;
173         params->h = atoi(p);
174         while (*p && isdigit((unsigned char)*p)) p++;
175     } else {
176         params->h = params->w;
177     }
178     if (*p == 'n') {
179         p++;
180         params->n = atoi(p);
181         while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
182     } else {
183         params->n = params->w * params->h / 8;
184     }
185     if (*p == 'd') {
186         int i;
187         p++;
188         for (i = 0; i < DIFFCOUNT; i++)
189             if (*p == map_diffchars[i])
190                 params->diff = i;
191         if (*p) p++;
192     }
193 }
194
195 static char *encode_params(const game_params *params, int full)
196 {
197     char ret[400];
198
199     sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
200     if (full)
201         sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
202
203     return dupstr(ret);
204 }
205
206 static config_item *game_configure(const game_params *params)
207 {
208     config_item *ret;
209     char buf[80];
210
211     ret = snewn(5, config_item);
212
213     ret[0].name = "Width";
214     ret[0].type = C_STRING;
215     sprintf(buf, "%d", params->w);
216     ret[0].sval = dupstr(buf);
217     ret[0].ival = 0;
218
219     ret[1].name = "Height";
220     ret[1].type = C_STRING;
221     sprintf(buf, "%d", params->h);
222     ret[1].sval = dupstr(buf);
223     ret[1].ival = 0;
224
225     ret[2].name = "Regions";
226     ret[2].type = C_STRING;
227     sprintf(buf, "%d", params->n);
228     ret[2].sval = dupstr(buf);
229     ret[2].ival = 0;
230
231     ret[3].name = "Difficulty";
232     ret[3].type = C_CHOICES;
233     ret[3].sval = DIFFCONFIG;
234     ret[3].ival = params->diff;
235
236     ret[4].name = NULL;
237     ret[4].type = C_END;
238     ret[4].sval = NULL;
239     ret[4].ival = 0;
240
241     return ret;
242 }
243
244 static game_params *custom_params(const config_item *cfg)
245 {
246     game_params *ret = snew(game_params);
247
248     ret->w = atoi(cfg[0].sval);
249     ret->h = atoi(cfg[1].sval);
250     ret->n = atoi(cfg[2].sval);
251     ret->diff = cfg[3].ival;
252
253     return ret;
254 }
255
256 static char *validate_params(const game_params *params, int full)
257 {
258     if (params->w < 2 || params->h < 2)
259         return "Width and height must be at least two";
260     if (params->n < 5)
261         return "Must have at least five regions";
262     if (params->n > params->w * params->h)
263         return "Too many regions to fit in grid";
264     return NULL;
265 }
266
267 /* ----------------------------------------------------------------------
268  * Cumulative frequency table functions.
269  */
270
271 /*
272  * Initialise a cumulative frequency table. (Hardly worth writing
273  * this function; all it does is to initialise everything in the
274  * array to zero.)
275  */
276 static void cf_init(int *table, int n)
277 {
278     int i;
279
280     for (i = 0; i < n; i++)
281         table[i] = 0;
282 }
283
284 /*
285  * Increment the count of symbol `sym' by `count'.
286  */
287 static void cf_add(int *table, int n, int sym, int count)
288 {
289     int bit;
290
291     bit = 1;
292     while (sym != 0) {
293         if (sym & bit) {
294             table[sym] += count;
295             sym &= ~bit;
296         }
297         bit <<= 1;
298     }
299
300     table[0] += count;
301 }
302
303 /*
304  * Cumulative frequency lookup: return the total count of symbols
305  * with value less than `sym'.
306  */
307 static int cf_clookup(int *table, int n, int sym)
308 {
309     int bit, index, limit, count;
310
311     if (sym == 0)
312         return 0;
313
314     assert(0 < sym && sym <= n);
315
316     count = table[0];                  /* start with the whole table size */
317
318     bit = 1;
319     while (bit < n)
320         bit <<= 1;
321
322     limit = n;
323
324     while (bit > 0) {
325         /*
326          * Find the least number with its lowest set bit in this
327          * position which is greater than or equal to sym.
328          */
329         index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
330
331         if (index < limit) {
332             count -= table[index];
333             limit = index;
334         }
335
336         bit >>= 1;
337     }
338
339     return count;
340 }
341
342 /*
343  * Single frequency lookup: return the count of symbol `sym'.
344  */
345 static int cf_slookup(int *table, int n, int sym)
346 {
347     int count, bit;
348
349     assert(0 <= sym && sym < n);
350
351     count = table[sym];
352
353     for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
354         count -= table[sym+bit];
355
356     return count;
357 }
358
359 /*
360  * Return the largest symbol index such that the cumulative
361  * frequency up to that symbol is less than _or equal to_ count.
362  */
363 static int cf_whichsym(int *table, int n, int count) {
364     int bit, sym, top;
365
366     assert(count >= 0 && count < table[0]);
367
368     bit = 1;
369     while (bit < n)
370         bit <<= 1;
371
372     sym = 0;
373     top = table[0];
374
375     while (bit > 0) {
376         if (sym+bit < n) {
377             if (count >= top - table[sym+bit])
378                 sym += bit;
379             else
380                 top -= table[sym+bit];
381         }
382
383         bit >>= 1;
384     }
385
386     return sym;
387 }
388
389 /* ----------------------------------------------------------------------
390  * Map generation.
391  * 
392  * FIXME: this isn't entirely optimal at present, because it
393  * inherently prioritises growing the largest region since there
394  * are more squares adjacent to it. This acts as a destabilising
395  * influence leading to a few large regions and mostly small ones.
396  * It might be better to do it some other way.
397  */
398
399 #define WEIGHT_INCREASED 2             /* for increased perimeter */
400 #define WEIGHT_DECREASED 4             /* for decreased perimeter */
401 #define WEIGHT_UNCHANGED 3             /* for unchanged perimeter */
402
403 /*
404  * Look at a square and decide which colours can be extended into
405  * it.
406  * 
407  * If called with index < 0, it adds together one of
408  * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
409  * colour that has a valid extension (according to the effect that
410  * it would have on the perimeter of the region being extended) and
411  * returns the overall total.
412  * 
413  * If called with index >= 0, it returns one of the possible
414  * colours depending on the value of index, in such a way that the
415  * number of possible inputs which would give rise to a given
416  * return value correspond to the weight of that value.
417  */
418 static int extend_options(int w, int h, int n, int *map,
419                           int x, int y, int index)
420 {
421     int c, i, dx, dy;
422     int col[8];
423     int total = 0;
424
425     if (map[y*w+x] >= 0) {
426         assert(index < 0);
427         return 0;                      /* can't do this square at all */
428     }
429
430     /*
431      * Fetch the eight neighbours of this square, in order around
432      * the square.
433      */
434     for (dy = -1; dy <= +1; dy++)
435         for (dx = -1; dx <= +1; dx++) {
436             int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx));
437             if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h)
438                 col[index] = map[(y+dy)*w+(x+dx)];
439             else
440                 col[index] = -1;
441         }
442
443     /*
444      * Iterate over each colour that might be feasible.
445      * 
446      * FIXME: this routine currently has O(n) running time. We
447      * could turn it into O(FOUR) by only bothering to iterate over
448      * the colours mentioned in the four neighbouring squares.
449      */
450
451     for (c = 0; c < n; c++) {
452         int count, neighbours, runs;
453
454         /*
455          * One of the even indices of col (representing the
456          * orthogonal neighbours of this square) must be equal to
457          * c, or else this square is not adjacent to region c and
458          * obviously cannot become an extension of it at this time.
459          */
460         neighbours = 0;
461         for (i = 0; i < 8; i += 2)
462             if (col[i] == c)
463                 neighbours++;
464         if (!neighbours)
465             continue;
466
467         /*
468          * Now we know this square is adjacent to region c. The
469          * next question is, would extending it cause the region to
470          * become non-simply-connected? If so, we mustn't do it.
471          * 
472          * We determine this by looking around col to see if we can
473          * find more than one separate run of colour c.
474          */
475         runs = 0;
476         for (i = 0; i < 8; i++)
477             if (col[i] == c && col[(i+1) & 7] != c)
478                 runs++;
479         if (runs > 1)
480             continue;
481
482         assert(runs == 1);
483
484         /*
485          * This square is a possibility. Determine its effect on
486          * the region's perimeter (computed from the number of
487          * orthogonal neighbours - 1 means a perimeter increase, 3
488          * a decrease, 2 no change; 4 is impossible because the
489          * region would already not be simply connected) and we're
490          * done.
491          */
492         assert(neighbours > 0 && neighbours < 4);
493         count = (neighbours == 1 ? WEIGHT_INCREASED :
494                  neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);
495
496         total += count;
497         if (index >= 0 && index < count)
498             return c;
499         else
500             index -= count;
501     }
502
503     assert(index < 0);
504
505     return total;
506 }
507
508 static void genmap(int w, int h, int n, int *map, random_state *rs)
509 {
510     int wh = w*h;
511     int x, y, i, k;
512     int *tmp;
513
514     assert(n <= wh);
515     tmp = snewn(wh, int);
516
517     /*
518      * Clear the map, and set up `tmp' as a list of grid indices.
519      */
520     for (i = 0; i < wh; i++) {
521         map[i] = -1;
522         tmp[i] = i;
523     }
524
525     /*
526      * Place the region seeds by selecting n members from `tmp'.
527      */
528     k = wh;
529     for (i = 0; i < n; i++) {
530         int j = random_upto(rs, k);
531         map[tmp[j]] = i;
532         tmp[j] = tmp[--k];
533     }
534
535     /*
536      * Re-initialise `tmp' as a cumulative frequency table. This
537      * will store the number of possible region colours we can
538      * extend into each square.
539      */
540     cf_init(tmp, wh);
541
542     /*
543      * Go through the grid and set up the initial cumulative
544      * frequencies.
545      */
546     for (y = 0; y < h; y++)
547         for (x = 0; x < w; x++)
548             cf_add(tmp, wh, y*w+x,
549                    extend_options(w, h, n, map, x, y, -1));
550
551     /*
552      * Now repeatedly choose a square we can extend a region into,
553      * and do so.
554      */
555     while (tmp[0] > 0) {
556         int k = random_upto(rs, tmp[0]);
557         int sq;
558         int colour;
559         int xx, yy;
560
561         sq = cf_whichsym(tmp, wh, k);
562         k -= cf_clookup(tmp, wh, sq);
563         x = sq % w;
564         y = sq / w;
565         colour = extend_options(w, h, n, map, x, y, k);
566
567         map[sq] = colour;
568
569         /*
570          * Re-scan the nine cells around the one we've just
571          * modified.
572          */
573         for (yy = max(y-1, 0); yy < min(y+2, h); yy++)
574             for (xx = max(x-1, 0); xx < min(x+2, w); xx++) {
575                 cf_add(tmp, wh, yy*w+xx,
576                        -cf_slookup(tmp, wh, yy*w+xx) +
577                        extend_options(w, h, n, map, xx, yy, -1));
578             }
579     }
580
581     /*
582      * Finally, go through and normalise the region labels into
583      * order, meaning that indistinguishable maps are actually
584      * identical.
585      */
586     for (i = 0; i < n; i++)
587         tmp[i] = -1;
588     k = 0;
589     for (i = 0; i < wh; i++) {
590         assert(map[i] >= 0);
591         if (tmp[map[i]] < 0)
592             tmp[map[i]] = k++;
593         map[i] = tmp[map[i]];
594     }
595
596     sfree(tmp);
597 }
598
599 /* ----------------------------------------------------------------------
600  * Functions to handle graphs.
601  */
602
603 /*
604  * Having got a map in a square grid, convert it into a graph
605  * representation.
606  */
607 static int gengraph(int w, int h, int n, int *map, int *graph)
608 {
609     int i, j, x, y;
610
611     /*
612      * Start by setting the graph up as an adjacency matrix. We'll
613      * turn it into a list later.
614      */
615     for (i = 0; i < n*n; i++)
616         graph[i] = 0;
617
618     /*
619      * Iterate over the map looking for all adjacencies.
620      */
621     for (y = 0; y < h; y++)
622         for (x = 0; x < w; x++) {
623             int v, vx, vy;
624             v = map[y*w+x];
625             if (x+1 < w && (vx = map[y*w+(x+1)]) != v)
626                 graph[v*n+vx] = graph[vx*n+v] = 1;
627             if (y+1 < h && (vy = map[(y+1)*w+x]) != v)
628                 graph[v*n+vy] = graph[vy*n+v] = 1;
629         }
630
631     /*
632      * Turn the matrix into a list.
633      */
634     for (i = j = 0; i < n*n; i++)
635         if (graph[i])
636             graph[j++] = i;
637
638     return j;
639 }
640
641 static int graph_edge_index(int *graph, int n, int ngraph, int i, int j)
642 {
643     int v = i*n+j;
644     int top, bot, mid;
645
646     bot = -1;
647     top = ngraph;
648     while (top - bot > 1) {
649         mid = (top + bot) / 2;
650         if (graph[mid] == v)
651             return mid;
652         else if (graph[mid] < v)
653             bot = mid;
654         else
655             top = mid;
656     }
657     return -1;
658 }
659
660 #define graph_adjacent(graph, n, ngraph, i, j) \
661     (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)
662
663 static int graph_vertex_start(int *graph, int n, int ngraph, int i)
664 {
665     int v = i*n;
666     int top, bot, mid;
667
668     bot = -1;
669     top = ngraph;
670     while (top - bot > 1) {
671         mid = (top + bot) / 2;
672         if (graph[mid] < v)
673             bot = mid;
674         else
675             top = mid;
676     }
677     return top;
678 }
679
680 /* ----------------------------------------------------------------------
681  * Generate a four-colouring of a graph.
682  *
683  * FIXME: it would be nice if we could convert this recursion into
684  * pseudo-recursion using some sort of explicit stack array, for
685  * the sake of the Palm port and its limited stack.
686  */
687
688 static int fourcolour_recurse(int *graph, int n, int ngraph,
689                               int *colouring, int *scratch, random_state *rs)
690 {
691     int nfree, nvert, start, i, j, k, c, ci;
692     int cs[FOUR];
693
694     /*
695      * Find the smallest number of free colours in any uncoloured
696      * vertex, and count the number of such vertices.
697      */
698
699     nfree = FIVE;                      /* start off bigger than FOUR! */
700     nvert = 0;
701     for (i = 0; i < n; i++)
702         if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) {
703             if (nfree > scratch[i*FIVE+FOUR]) {
704                 nfree = scratch[i*FIVE+FOUR];
705                 nvert = 0;
706             }
707             nvert++;
708         }
709
710     /*
711      * If there aren't any uncoloured vertices at all, we're done.
712      */
713     if (nvert == 0)
714         return TRUE;                   /* we've got a colouring! */
715
716     /*
717      * Pick a random vertex in that set.
718      */
719     j = random_upto(rs, nvert);
720     for (i = 0; i < n; i++)
721         if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
722             if (j-- == 0)
723                 break;
724     assert(i < n);
725     start = graph_vertex_start(graph, n, ngraph, i);
726
727     /*
728      * Loop over the possible colours for i, and recurse for each
729      * one.
730      */
731     ci = 0;
732     for (c = 0; c < FOUR; c++)
733         if (scratch[i*FIVE+c] == 0)
734             cs[ci++] = c;
735     shuffle(cs, ci, sizeof(*cs), rs);
736
737     while (ci-- > 0) {
738         c = cs[ci];
739
740         /*
741          * Fill in this colour.
742          */
743         colouring[i] = c;
744
745         /*
746          * Update the scratch space to reflect a new neighbour
747          * of this colour for each neighbour of vertex i.
748          */
749         for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
750             k = graph[j] - i*n;
751             if (scratch[k*FIVE+c] == 0)
752                 scratch[k*FIVE+FOUR]--;
753             scratch[k*FIVE+c]++;
754         }
755
756         /*
757          * Recurse.
758          */
759         if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
760             return TRUE;               /* got one! */
761
762         /*
763          * If that didn't work, clean up and try again with a
764          * different colour.
765          */
766         for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
767             k = graph[j] - i*n;
768             scratch[k*FIVE+c]--;
769             if (scratch[k*FIVE+c] == 0)
770                 scratch[k*FIVE+FOUR]++;
771         }
772         colouring[i] = -1;
773     }
774
775     /*
776      * If we reach here, we were unable to find a colouring at all.
777      * (This doesn't necessarily mean the Four Colour Theorem is
778      * violated; it might just mean we've gone down a dead end and
779      * need to back up and look somewhere else. It's only an FCT
780      * violation if we get all the way back up to the top level and
781      * still fail.)
782      */
783     return FALSE;
784 }
785
786 static void fourcolour(int *graph, int n, int ngraph, int *colouring,
787                        random_state *rs)
788 {
789     int *scratch;
790     int i;
791
792     /*
793      * For each vertex and each colour, we store the number of
794      * neighbours that have that colour. Also, we store the number
795      * of free colours for the vertex.
796      */
797     scratch = snewn(n * FIVE, int);
798     for (i = 0; i < n * FIVE; i++)
799         scratch[i] = (i % FIVE == FOUR ? FOUR : 0);
800
801     /*
802      * Clear the colouring to start with.
803      */
804     for (i = 0; i < n; i++)
805         colouring[i] = -1;
806
807     i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
808     assert(i);                         /* by the Four Colour Theorem :-) */
809
810     sfree(scratch);
811 }
812
813 /* ----------------------------------------------------------------------
814  * Non-recursive solver.
815  */
816
817 struct solver_scratch {
818     unsigned char *possible;           /* bitmap of colours for each region */
819
820     int *graph;
821     int n;
822     int ngraph;
823
824     int *bfsqueue;
825     int *bfscolour;
826 #ifdef SOLVER_DIAGNOSTICS
827     int *bfsprev;
828 #endif
829
830     int depth;
831 };
832
833 static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
834 {
835     struct solver_scratch *sc;
836
837     sc = snew(struct solver_scratch);
838     sc->graph = graph;
839     sc->n = n;
840     sc->ngraph = ngraph;
841     sc->possible = snewn(n, unsigned char);
842     sc->depth = 0;
843     sc->bfsqueue = snewn(n, int);
844     sc->bfscolour = snewn(n, int);
845 #ifdef SOLVER_DIAGNOSTICS
846     sc->bfsprev = snewn(n, int);
847 #endif
848
849     return sc;
850 }
851
852 static void free_scratch(struct solver_scratch *sc)
853 {
854     sfree(sc->possible);
855     sfree(sc->bfsqueue);
856     sfree(sc->bfscolour);
857 #ifdef SOLVER_DIAGNOSTICS
858     sfree(sc->bfsprev);
859 #endif
860     sfree(sc);
861 }
862
863 /*
864  * Count the bits in a word. Only needs to cope with FOUR bits.
865  */
866 static int bitcount(int word)
867 {
868     assert(FOUR <= 4);                 /* or this needs changing */
869     word = ((word & 0xA) >> 1) + (word & 0x5);
870     word = ((word & 0xC) >> 2) + (word & 0x3);
871     return word;
872 }
873
874 #ifdef SOLVER_DIAGNOSTICS
875 static const char colnames[FOUR] = { 'R', 'Y', 'G', 'B' };
876 #endif
877
878 static int place_colour(struct solver_scratch *sc,
879                         int *colouring, int index, int colour
880 #ifdef SOLVER_DIAGNOSTICS
881                         , char *verb
882 #endif
883                         )
884 {
885     int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
886     int j, k;
887
888     if (!(sc->possible[index] & (1 << colour))) {
889 #ifdef SOLVER_DIAGNOSTICS
890         if (verbose)
891             printf("%*scannot place %c in region %d\n", 2*sc->depth, "",
892                    colnames[colour], index);
893 #endif
894         return FALSE;                  /* can't do it */
895     }
896
897     sc->possible[index] = 1 << colour;
898     colouring[index] = colour;
899
900 #ifdef SOLVER_DIAGNOSTICS
901     if (verbose)
902         printf("%*s%s %c in region %d\n", 2*sc->depth, "",
903                verb, colnames[colour], index);
904 #endif
905
906     /*
907      * Rule out this colour from all the region's neighbours.
908      */
909     for (j = graph_vertex_start(graph, n, ngraph, index);
910          j < ngraph && graph[j] < n*(index+1); j++) {
911         k = graph[j] - index*n;
912 #ifdef SOLVER_DIAGNOSTICS
913         if (verbose && (sc->possible[k] & (1 << colour)))
914             printf("%*s  ruling out %c in region %d\n", 2*sc->depth, "",
915                    colnames[colour], k);
916 #endif
917         sc->possible[k] &= ~(1 << colour);
918     }
919
920     return TRUE;
921 }
922
923 #ifdef SOLVER_DIAGNOSTICS
924 static char *colourset(char *buf, int set)
925 {
926     int i;
927     char *p = buf;
928     char *sep = "";
929
930     for (i = 0; i < FOUR; i++)
931         if (set & (1 << i)) {
932             p += sprintf(p, "%s%c", sep, colnames[i]);
933             sep = ",";
934         }
935
936     return buf;
937 }
938 #endif
939
940 /*
941  * Returns 0 for impossible, 1 for success, 2 for failure to
942  * converge (i.e. puzzle is either ambiguous or just too
943  * difficult).
944  */
945 static int map_solver(struct solver_scratch *sc,
946                       int *graph, int n, int ngraph, int *colouring,
947                       int difficulty)
948 {
949     int i;
950
951     if (sc->depth == 0) {
952         /*
953          * Initialise scratch space.
954          */
955         for (i = 0; i < n; i++)
956             sc->possible[i] = (1 << FOUR) - 1;
957
958         /*
959          * Place clues.
960          */
961         for (i = 0; i < n; i++)
962             if (colouring[i] >= 0) {
963                 if (!place_colour(sc, colouring, i, colouring[i]
964 #ifdef SOLVER_DIAGNOSTICS
965                                   , "initial clue:"
966 #endif
967                                   )) {
968 #ifdef SOLVER_DIAGNOSTICS
969                     if (verbose)
970                         printf("%*sinitial clue set is inconsistent\n",
971                                2*sc->depth, "");
972 #endif
973                     return 0;          /* the clues aren't even consistent! */
974                 }
975             }
976     }
977
978     /*
979      * Now repeatedly loop until we find nothing further to do.
980      */
981     while (1) {
982         int done_something = FALSE;
983
984         if (difficulty < DIFF_EASY)
985             break;                     /* can't do anything at all! */
986
987         /*
988          * Simplest possible deduction: find a region with only one
989          * possible colour.
990          */
991         for (i = 0; i < n; i++) if (colouring[i] < 0) {
992             int p = sc->possible[i];
993
994             if (p == 0) {
995 #ifdef SOLVER_DIAGNOSTICS
996                 if (verbose)
997                     printf("%*sregion %d has no possible colours left\n",
998                            2*sc->depth, "", i);
999 #endif
1000                 return 0;              /* puzzle is inconsistent */
1001             }
1002
1003             if ((p & (p-1)) == 0) {    /* p is a power of two */
1004                 int c, ret;
1005                 for (c = 0; c < FOUR; c++)
1006                     if (p == (1 << c))
1007                         break;
1008                 assert(c < FOUR);
1009                 ret = place_colour(sc, colouring, i, c
1010 #ifdef SOLVER_DIAGNOSTICS
1011                                    , "placing"
1012 #endif
1013                                    );
1014                 /*
1015                  * place_colour() can only fail if colour c was not
1016                  * even a _possibility_ for region i, and we're
1017                  * pretty sure it was because we checked before
1018                  * calling place_colour(). So we can safely assert
1019                  * here rather than having to return a nice
1020                  * friendly error code.
1021                  */
1022                 assert(ret);
1023                 done_something = TRUE;
1024             }
1025         }
1026
1027         if (done_something)
1028             continue;
1029
1030         if (difficulty < DIFF_NORMAL)
1031             break;                     /* can't do anything harder */
1032
1033         /*
1034          * Failing that, go up one level. Look for pairs of regions
1035          * which (a) both have the same pair of possible colours,
1036          * (b) are adjacent to one another, (c) are adjacent to the
1037          * same region, and (d) that region still thinks it has one
1038          * or both of those possible colours.
1039          * 
1040          * Simplest way to do this is by going through the graph
1041          * edge by edge, so that we start with property (b) and
1042          * then look for (a) and finally (c) and (d).
1043          */
1044         for (i = 0; i < ngraph; i++) {
1045             int j1 = graph[i] / n, j2 = graph[i] % n;
1046             int j, k, v, v2;
1047 #ifdef SOLVER_DIAGNOSTICS
1048             int started = FALSE;
1049 #endif
1050
1051             if (j1 > j2)
1052                 continue;              /* done it already, other way round */
1053
1054             if (colouring[j1] >= 0 || colouring[j2] >= 0)
1055                 continue;              /* they're not undecided */
1056
1057             if (sc->possible[j1] != sc->possible[j2])
1058                 continue;              /* they don't have the same possibles */
1059
1060             v = sc->possible[j1];
1061             /*
1062              * See if v contains exactly two set bits.
1063              */
1064             v2 = v & -v;           /* find lowest set bit */
1065             v2 = v & ~v2;          /* clear it */
1066             if (v2 == 0 || (v2 & (v2-1)) != 0)   /* not power of 2 */
1067                 continue;
1068
1069             /*
1070              * We've found regions j1 and j2 satisfying properties
1071              * (a) and (b): they have two possible colours between
1072              * them, and since they're adjacent to one another they
1073              * must use _both_ those colours between them.
1074              * Therefore, if they are both adjacent to any other
1075              * region then that region cannot be either colour.
1076              * 
1077              * Go through the neighbours of j1 and see if any are
1078              * shared with j2.
1079              */
1080             for (j = graph_vertex_start(graph, n, ngraph, j1);
1081                  j < ngraph && graph[j] < n*(j1+1); j++) {
1082                 k = graph[j] - j1*n;
1083                 if (graph_adjacent(graph, n, ngraph, k, j2) &&
1084                     (sc->possible[k] & v)) {
1085 #ifdef SOLVER_DIAGNOSTICS
1086                     if (verbose) {
1087                         char buf[80];
1088                         if (!started)
1089                             printf("%*sadjacent regions %d,%d share colours"
1090                                    " %s\n", 2*sc->depth, "", j1, j2,
1091                                    colourset(buf, v));
1092                         started = TRUE;
1093                         printf("%*s  ruling out %s in region %d\n",2*sc->depth,
1094                                "", colourset(buf, sc->possible[k] & v), k);
1095                     }
1096 #endif
1097                     sc->possible[k] &= ~v;
1098                     done_something = TRUE;
1099                 }
1100             }
1101         }
1102
1103         if (done_something)
1104             continue;
1105
1106         if (difficulty < DIFF_HARD)
1107             break;                     /* can't do anything harder */
1108
1109         /*
1110          * Right; now we get creative. Now we're going to look for
1111          * `forcing chains'. A forcing chain is a path through the
1112          * graph with the following properties:
1113          * 
1114          *  (a) Each vertex on the path has precisely two possible
1115          *      colours.
1116          * 
1117          *  (b) Each pair of vertices which are adjacent on the
1118          *      path share at least one possible colour in common.
1119          * 
1120          *  (c) Each vertex in the middle of the path shares _both_
1121          *      of its colours with at least one of its neighbours
1122          *      (not the same one with both neighbours).
1123          * 
1124          * These together imply that at least one of the possible
1125          * colour choices at one end of the path forces _all_ the
1126          * rest of the colours along the path. In order to make
1127          * real use of this, we need further properties:
1128          * 
1129          *  (c) Ruling out some colour C from the vertex at one end
1130          *      of the path forces the vertex at the other end to
1131          *      take colour C.
1132          * 
1133          *  (d) The two end vertices are mutually adjacent to some
1134          *      third vertex.
1135          * 
1136          *  (e) That third vertex currently has C as a possibility.
1137          * 
1138          * If we can find all of that lot, we can deduce that at
1139          * least one of the two ends of the forcing chain has
1140          * colour C, and that therefore the mutually adjacent third
1141          * vertex does not.
1142          * 
1143          * To find forcing chains, we're going to start a bfs at
1144          * each suitable vertex of the graph, once for each of its
1145          * two possible colours.
1146          */
1147         for (i = 0; i < n; i++) {
1148             int c;
1149
1150             if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2)
1151                 continue;
1152
1153             for (c = 0; c < FOUR; c++)
1154                 if (sc->possible[i] & (1 << c)) {
1155                     int j, k, gi, origc, currc, head, tail;
1156                     /*
1157                      * Try a bfs from this vertex, ruling out
1158                      * colour c.
1159                      * 
1160                      * Within this loop, we work in colour bitmaps
1161                      * rather than actual colours, because
1162                      * converting back and forth is a needless
1163                      * computational expense.
1164                      */
1165
1166                     origc = 1 << c;
1167
1168                     for (j = 0; j < n; j++) {
1169                         sc->bfscolour[j] = -1;
1170 #ifdef SOLVER_DIAGNOSTICS
1171                         sc->bfsprev[j] = -1;
1172 #endif
1173                     }
1174                     head = tail = 0;
1175                     sc->bfsqueue[tail++] = i;
1176                     sc->bfscolour[i] = sc->possible[i] &~ origc;
1177
1178                     while (head < tail) {
1179                         j = sc->bfsqueue[head++];
1180                         currc = sc->bfscolour[j];
1181
1182                         /*
1183                          * Try neighbours of j.
1184                          */
1185                         for (gi = graph_vertex_start(graph, n, ngraph, j);
1186                              gi < ngraph && graph[gi] < n*(j+1); gi++) {
1187                             k = graph[gi] - j*n;
1188
1189                             /*
1190                              * To continue with the bfs in vertex
1191                              * k, we need k to be
1192                              *  (a) not already visited
1193                              *  (b) have two possible colours
1194                              *  (c) those colours include currc.
1195                              */
1196
1197                             if (sc->bfscolour[k] < 0 &&
1198                                 colouring[k] < 0 &&
1199                                 bitcount(sc->possible[k]) == 2 &&
1200                                 (sc->possible[k] & currc)) {
1201                                 sc->bfsqueue[tail++] = k;
1202                                 sc->bfscolour[k] =
1203                                     sc->possible[k] &~ currc;
1204 #ifdef SOLVER_DIAGNOSTICS
1205                                 sc->bfsprev[k] = j;
1206 #endif
1207                             }
1208
1209                             /*
1210                              * One other possibility is that k
1211                              * might be the region in which we can
1212                              * make a real deduction: if it's
1213                              * adjacent to i, contains currc as a
1214                              * possibility, and currc is equal to
1215                              * the original colour we ruled out.
1216                              */
1217                             if (currc == origc &&
1218                                 graph_adjacent(graph, n, ngraph, k, i) &&
1219                                 (sc->possible[k] & currc)) {
1220 #ifdef SOLVER_DIAGNOSTICS
1221                                 if (verbose) {
1222                                     char buf[80], *sep = "";
1223                                     int r;
1224
1225                                     printf("%*sforcing chain, colour %s, ",
1226                                            2*sc->depth, "",
1227                                            colourset(buf, origc));
1228                                     for (r = j; r != -1; r = sc->bfsprev[r]) {
1229                                         printf("%s%d", sep, r);
1230                                         sep = "-";
1231                                     }
1232                                     printf("\n%*s  ruling out %s in region"
1233                                            " %d\n", 2*sc->depth, "",
1234                                            colourset(buf, origc), k);
1235                                 }
1236 #endif
1237                                 sc->possible[k] &= ~origc;
1238                                 done_something = TRUE;
1239                             }
1240                         }
1241                     }
1242
1243                     assert(tail <= n);
1244                 }
1245         }
1246
1247         if (!done_something)
1248             break;
1249     }
1250
1251     /*
1252      * See if we've got a complete solution, and return if so.
1253      */
1254     for (i = 0; i < n; i++)
1255         if (colouring[i] < 0)
1256             break;
1257     if (i == n) {
1258 #ifdef SOLVER_DIAGNOSTICS
1259         if (verbose)
1260             printf("%*sone solution found\n", 2*sc->depth, "");
1261 #endif
1262         return 1;                      /* success! */
1263     }
1264
1265     /*
1266      * If recursion is not permissible, we now give up.
1267      */
1268     if (difficulty < DIFF_RECURSE) {
1269 #ifdef SOLVER_DIAGNOSTICS
1270         if (verbose)
1271             printf("%*sunable to proceed further without recursion\n",
1272                    2*sc->depth, "");
1273 #endif
1274         return 2;                      /* unable to complete */
1275     }
1276
1277     /*
1278      * Now we've got to do something recursive. So first hunt for a
1279      * currently-most-constrained region.
1280      */
1281     {
1282         int best, bestc;
1283         struct solver_scratch *rsc;
1284         int *subcolouring, *origcolouring;
1285         int ret, subret;
1286         int we_already_got_one;
1287
1288         best = -1;
1289         bestc = FIVE;
1290
1291         for (i = 0; i < n; i++) if (colouring[i] < 0) {
1292             int p = sc->possible[i];
1293             enum { compile_time_assertion = 1 / (FOUR <= 4) };
1294             int c;
1295
1296             /* Count the set bits. */
1297             c = (p & 5) + ((p >> 1) & 5);
1298             c = (c & 3) + ((c >> 2) & 3);
1299             assert(c > 1);             /* or colouring[i] would be >= 0 */
1300
1301             if (c < bestc) {
1302                 best = i;
1303                 bestc = c;
1304             }
1305         }
1306
1307         assert(best >= 0);             /* or we'd be solved already */
1308
1309 #ifdef SOLVER_DIAGNOSTICS
1310         if (verbose)
1311             printf("%*srecursing on region %d\n", 2*sc->depth, "", best);
1312 #endif
1313
1314         /*
1315          * Now iterate over the possible colours for this region.
1316          */
1317         rsc = new_scratch(graph, n, ngraph);
1318         rsc->depth = sc->depth + 1;
1319         origcolouring = snewn(n, int);
1320         memcpy(origcolouring, colouring, n * sizeof(int));
1321         subcolouring = snewn(n, int);
1322         we_already_got_one = FALSE;
1323         ret = 0;
1324
1325         for (i = 0; i < FOUR; i++) {
1326             if (!(sc->possible[best] & (1 << i)))
1327                 continue;
1328
1329             memcpy(rsc->possible, sc->possible, n);
1330             memcpy(subcolouring, origcolouring, n * sizeof(int));
1331
1332             place_colour(rsc, subcolouring, best, i
1333 #ifdef SOLVER_DIAGNOSTICS
1334                          , "trying"
1335 #endif
1336                          );
1337
1338             subret = map_solver(rsc, graph, n, ngraph,
1339                                 subcolouring, difficulty);
1340
1341 #ifdef SOLVER_DIAGNOSTICS
1342             if (verbose) {
1343                 printf("%*sretracting %c in region %d; found %s\n",
1344                        2*sc->depth, "", colnames[i], best,
1345                        subret == 0 ? "no solutions" :
1346                        subret == 1 ? "one solution" : "multiple solutions");
1347             }
1348 #endif
1349
1350             /*
1351              * If this possibility turned up more than one valid
1352              * solution, or if it turned up one and we already had
1353              * one, we're definitely ambiguous.
1354              */
1355             if (subret == 2 || (subret == 1 && we_already_got_one)) {
1356                 ret = 2;
1357                 break;
1358             }
1359
1360             /*
1361              * If this possibility turned up one valid solution and
1362              * it's the first we've seen, copy it into the output.
1363              */
1364             if (subret == 1) {
1365                 memcpy(colouring, subcolouring, n * sizeof(int));
1366                 we_already_got_one = TRUE;
1367                 ret = 1;
1368             }
1369
1370             /*
1371              * Otherwise, this guess led to a contradiction, so we
1372              * do nothing.
1373              */
1374         }
1375
1376         sfree(origcolouring);
1377         sfree(subcolouring);
1378         free_scratch(rsc);
1379
1380 #ifdef SOLVER_DIAGNOSTICS
1381         if (verbose && sc->depth == 0) {
1382             printf("%*s%s found\n",
1383                    2*sc->depth, "",
1384                    ret == 0 ? "no solutions" :
1385                    ret == 1 ? "one solution" : "multiple solutions");
1386         }
1387 #endif
1388         return ret;
1389     }
1390 }
1391
1392 /* ----------------------------------------------------------------------
1393  * Game generation main function.
1394  */
1395
1396 static char *new_game_desc(const game_params *params, random_state *rs,
1397                            char **aux, int interactive)
1398 {
1399     struct solver_scratch *sc = NULL;
1400     int *map, *graph, ngraph, *colouring, *colouring2, *regions;
1401     int i, j, w, h, n, solveret, cfreq[FOUR];
1402     int wh;
1403     int mindiff, tries;
1404 #ifdef GENERATION_DIAGNOSTICS
1405     int x, y;
1406 #endif
1407     char *ret, buf[80];
1408     int retlen, retsize;
1409
1410     w = params->w;
1411     h = params->h;
1412     n = params->n;
1413     wh = w*h;
1414
1415     *aux = NULL;
1416
1417     map = snewn(wh, int);
1418     graph = snewn(n*n, int);
1419     colouring = snewn(n, int);
1420     colouring2 = snewn(n, int);
1421     regions = snewn(n, int);
1422
1423     /*
1424      * This is the minimum difficulty below which we'll completely
1425      * reject a map design. Normally we set this to one below the
1426      * requested difficulty, ensuring that we have the right
1427      * result. However, for particularly dense maps or maps with
1428      * particularly few regions it might not be possible to get the
1429      * desired difficulty, so we will eventually drop this down to
1430      * -1 to indicate that any old map will do.
1431      */
1432     mindiff = params->diff;
1433     tries = 50;
1434
1435     while (1) {
1436
1437         /*
1438          * Create the map.
1439          */
1440         genmap(w, h, n, map, rs);
1441
1442 #ifdef GENERATION_DIAGNOSTICS
1443         for (y = 0; y < h; y++) {
1444             for (x = 0; x < w; x++) {
1445                 int v = map[y*w+x];
1446                 if (v >= 62)
1447                     putchar('!');
1448                 else if (v >= 36)
1449                     putchar('a' + v-36);
1450                 else if (v >= 10)
1451                     putchar('A' + v-10);
1452                 else
1453                     putchar('0' + v);
1454             }
1455             putchar('\n');
1456         }
1457 #endif
1458
1459         /*
1460          * Convert the map into a graph.
1461          */
1462         ngraph = gengraph(w, h, n, map, graph);
1463
1464 #ifdef GENERATION_DIAGNOSTICS
1465         for (i = 0; i < ngraph; i++)
1466             printf("%d-%d\n", graph[i]/n, graph[i]%n);
1467 #endif
1468
1469         /*
1470          * Colour the map.
1471          */
1472         fourcolour(graph, n, ngraph, colouring, rs);
1473
1474 #ifdef GENERATION_DIAGNOSTICS
1475         for (i = 0; i < n; i++)
1476             printf("%d: %d\n", i, colouring[i]);
1477
1478         for (y = 0; y < h; y++) {
1479             for (x = 0; x < w; x++) {
1480                 int v = colouring[map[y*w+x]];
1481                 if (v >= 36)
1482                     putchar('a' + v-36);
1483                 else if (v >= 10)
1484                     putchar('A' + v-10);
1485                 else
1486                     putchar('0' + v);
1487             }
1488             putchar('\n');
1489         }
1490 #endif
1491
1492         /*
1493          * Encode the solution as an aux string.
1494          */
1495         if (*aux)                      /* in case we've come round again */
1496             sfree(*aux);
1497         retlen = retsize = 0;
1498         ret = NULL;
1499         for (i = 0; i < n; i++) {
1500             int len;
1501
1502             if (colouring[i] < 0)
1503                 continue;
1504
1505             len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i);
1506             if (retlen + len >= retsize) {
1507                 retsize = retlen + len + 256;
1508                 ret = sresize(ret, retsize, char);
1509             }
1510             strcpy(ret + retlen, buf);
1511             retlen += len;
1512         }
1513         *aux = ret;
1514
1515         /*
1516          * Remove the region colours one by one, keeping
1517          * solubility. Also ensure that there always remains at
1518          * least one region of every colour, so that the user can
1519          * drag from somewhere.
1520          */
1521         for (i = 0; i < FOUR; i++)
1522             cfreq[i] = 0;
1523         for (i = 0; i < n; i++) {
1524             regions[i] = i;
1525             cfreq[colouring[i]]++;
1526         }
1527         for (i = 0; i < FOUR; i++)
1528             if (cfreq[i] == 0)
1529                 continue;
1530
1531         shuffle(regions, n, sizeof(*regions), rs);
1532
1533         if (sc) free_scratch(sc);
1534         sc = new_scratch(graph, n, ngraph);
1535
1536         for (i = 0; i < n; i++) {
1537             j = regions[i];
1538
1539             if (cfreq[colouring[j]] == 1)
1540                 continue;              /* can't remove last region of colour */
1541
1542             memcpy(colouring2, colouring, n*sizeof(int));
1543             colouring2[j] = -1;
1544             solveret = map_solver(sc, graph, n, ngraph, colouring2,
1545                                   params->diff);
1546             assert(solveret >= 0);             /* mustn't be impossible! */
1547             if (solveret == 1) {
1548                 cfreq[colouring[j]]--;
1549                 colouring[j] = -1;
1550             }
1551         }
1552
1553 #ifdef GENERATION_DIAGNOSTICS
1554         for (i = 0; i < n; i++)
1555             if (colouring[i] >= 0) {
1556                 if (i >= 62)
1557                     putchar('!');
1558                 else if (i >= 36)
1559                     putchar('a' + i-36);
1560                 else if (i >= 10)
1561                     putchar('A' + i-10);
1562                 else
1563                     putchar('0' + i);
1564                 printf(": %d\n", colouring[i]);
1565             }
1566 #endif
1567
1568         /*
1569          * Finally, check that the puzzle is _at least_ as hard as
1570          * required, and indeed that it isn't already solved.
1571          * (Calling map_solver with negative difficulty ensures the
1572          * latter - if a solver which _does nothing_ can solve it,
1573          * it's too easy!)
1574          */
1575         memcpy(colouring2, colouring, n*sizeof(int));
1576         if (map_solver(sc, graph, n, ngraph, colouring2,
1577                        mindiff - 1) == 1) {
1578             /*
1579              * Drop minimum difficulty if necessary.
1580              */
1581             if (mindiff > 0 && (n < 9 || n > 2*wh/3)) {
1582                 if (tries-- <= 0)
1583                     mindiff = 0;       /* give up and go for Easy */
1584             }
1585             continue;
1586         }
1587
1588         break;
1589     }
1590
1591     /*
1592      * Encode as a game ID. We do this by:
1593      * 
1594      *  - first going along the horizontal edges row by row, and
1595      *    then the vertical edges column by column
1596      *  - encoding the lengths of runs of edges and runs of
1597      *    non-edges
1598      *  - the decoder will reconstitute the region boundaries from
1599      *    this and automatically number them the same way we did
1600      *  - then we encode the initial region colours in a Slant-like
1601      *    fashion (digits 0-3 interspersed with letters giving
1602      *    lengths of runs of empty spaces).
1603      */
1604     retlen = retsize = 0;
1605     ret = NULL;
1606
1607     {
1608         int run, pv;
1609
1610         /*
1611          * Start with a notional non-edge, so that there'll be an
1612          * explicit `a' to distinguish the case where we start with
1613          * an edge.
1614          */
1615         run = 1;
1616         pv = 0;
1617
1618         for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
1619             int x, y, dx, dy, v;
1620
1621             if (i < w*(h-1)) {
1622                 /* Horizontal edge. */
1623                 y = i / w;
1624                 x = i % w;
1625                 dx = 0;
1626                 dy = 1;
1627             } else {
1628                 /* Vertical edge. */
1629                 x = (i - w*(h-1)) / h;
1630                 y = (i - w*(h-1)) % h;
1631                 dx = 1;
1632                 dy = 0;
1633             }
1634
1635             if (retlen + 10 >= retsize) {
1636                 retsize = retlen + 256;
1637                 ret = sresize(ret, retsize, char);
1638             }
1639
1640             v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);
1641
1642             if (pv != v) {
1643                 ret[retlen++] = 'a'-1 + run;
1644                 run = 1;
1645                 pv = v;
1646             } else {
1647                 /*
1648                  * 'z' is a special case in this encoding. Rather
1649                  * than meaning a run of 26 and a state switch, it
1650                  * means a run of 25 and _no_ state switch, because
1651                  * otherwise there'd be no way to encode runs of
1652                  * more than 26.
1653                  */
1654                 if (run == 25) {
1655                     ret[retlen++] = 'z';
1656                     run = 0;
1657                 }
1658                 run++;
1659             }
1660         }
1661
1662         ret[retlen++] = 'a'-1 + run;
1663         ret[retlen++] = ',';
1664
1665         run = 0;
1666         for (i = 0; i < n; i++) {
1667             if (retlen + 10 >= retsize) {
1668                 retsize = retlen + 256;
1669                 ret = sresize(ret, retsize, char);
1670             }
1671
1672             if (colouring[i] < 0) {
1673                 /*
1674                  * In _this_ encoding, 'z' is a run of 26, since
1675                  * there's no implicit state switch after each run.
1676                  * Confusingly different, but more compact.
1677                  */
1678                 if (run == 26) {
1679                     ret[retlen++] = 'z';
1680                     run = 0;
1681                 }
1682                 run++;
1683             } else {
1684                 if (run > 0)
1685                     ret[retlen++] = 'a'-1 + run;
1686                 ret[retlen++] = '0' + colouring[i];
1687                 run = 0;
1688             }
1689         }
1690         if (run > 0)
1691             ret[retlen++] = 'a'-1 + run;
1692         ret[retlen] = '\0';
1693
1694         assert(retlen < retsize);
1695     }
1696
1697     free_scratch(sc);
1698     sfree(regions);
1699     sfree(colouring2);
1700     sfree(colouring);
1701     sfree(graph);
1702     sfree(map);
1703
1704     return ret;
1705 }
1706
1707 static char *parse_edge_list(const game_params *params, const char **desc,
1708                              int *map)
1709 {
1710     int w = params->w, h = params->h, wh = w*h, n = params->n;
1711     int i, k, pos, state;
1712     const char *p = *desc;
1713
1714     dsf_init(map+wh, wh);
1715
1716     pos = -1;
1717     state = 0;
1718
1719     /*
1720      * Parse the game description to get the list of edges, and
1721      * build up a disjoint set forest as we go (by identifying
1722      * pairs of squares whenever the edge list shows a non-edge).
1723      */
1724     while (*p && *p != ',') {
1725         if (*p < 'a' || *p > 'z')
1726             return "Unexpected character in edge list";
1727         if (*p == 'z')
1728             k = 25;
1729         else
1730             k = *p - 'a' + 1;
1731         while (k-- > 0) {
1732             int x, y, dx, dy;
1733
1734             if (pos < 0) {
1735                 pos++;
1736                 continue;
1737             } else if (pos < w*(h-1)) {
1738                 /* Horizontal edge. */
1739                 y = pos / w;
1740                 x = pos % w;
1741                 dx = 0;
1742                 dy = 1;
1743             } else if (pos < 2*wh-w-h) {
1744                 /* Vertical edge. */
1745                 x = (pos - w*(h-1)) / h;
1746                 y = (pos - w*(h-1)) % h;
1747                 dx = 1;
1748                 dy = 0;
1749             } else
1750                 return "Too much data in edge list";
1751             if (!state)
1752                 dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));
1753
1754             pos++;
1755         }
1756         if (*p != 'z')
1757             state = !state;
1758         p++;
1759     }
1760     assert(pos <= 2*wh-w-h);
1761     if (pos < 2*wh-w-h)
1762         return "Too little data in edge list";
1763
1764     /*
1765      * Now go through again and allocate region numbers.
1766      */
1767     pos = 0;
1768     for (i = 0; i < wh; i++)
1769         map[i] = -1;
1770     for (i = 0; i < wh; i++) {
1771         k = dsf_canonify(map+wh, i);
1772         if (map[k] < 0)
1773             map[k] = pos++;
1774         map[i] = map[k];
1775     }
1776     if (pos != n)
1777         return "Edge list defines the wrong number of regions";
1778
1779     *desc = p;
1780
1781     return NULL;
1782 }
1783
1784 static char *validate_desc(const game_params *params, const char *desc)
1785 {
1786     int w = params->w, h = params->h, wh = w*h, n = params->n;
1787     int area;
1788     int *map;
1789     char *ret;
1790
1791     map = snewn(2*wh, int);
1792     ret = parse_edge_list(params, &desc, map);
1793     sfree(map);
1794     if (ret)
1795         return ret;
1796
1797     if (*desc != ',')
1798         return "Expected comma before clue list";
1799     desc++;                            /* eat comma */
1800
1801     area = 0;
1802     while (*desc) {
1803         if (*desc >= '0' && *desc < '0'+FOUR)
1804             area++;
1805         else if (*desc >= 'a' && *desc <= 'z')
1806             area += *desc - 'a' + 1;
1807         else
1808             return "Unexpected character in clue list";
1809         desc++;
1810     }
1811     if (area < n)
1812         return "Too little data in clue list";
1813     else if (area > n)
1814         return "Too much data in clue list";
1815
1816     return NULL;
1817 }
1818
1819 static game_state *new_game(midend *me, const game_params *params,
1820                             const char *desc)
1821 {
1822     int w = params->w, h = params->h, wh = w*h, n = params->n;
1823     int i, pos;
1824     const char *p;
1825     game_state *state = snew(game_state);
1826
1827     state->p = *params;
1828     state->colouring = snewn(n, int);
1829     for (i = 0; i < n; i++)
1830         state->colouring[i] = -1;
1831     state->pencil = snewn(n, int);
1832     for (i = 0; i < n; i++)
1833         state->pencil[i] = 0;
1834
1835     state->completed = state->cheated = FALSE;
1836
1837     state->map = snew(struct map);
1838     state->map->refcount = 1;
1839     state->map->map = snewn(wh*4, int);
1840     state->map->graph = snewn(n*n, int);
1841     state->map->n = n;
1842     state->map->immutable = snewn(n, int);
1843     for (i = 0; i < n; i++)
1844         state->map->immutable[i] = FALSE;
1845
1846     p = desc;
1847
1848     {
1849         char *ret;
1850         ret = parse_edge_list(params, &p, state->map->map);
1851         assert(!ret);
1852     }
1853
1854     /*
1855      * Set up the other three quadrants in `map'.
1856      */
1857     for (i = wh; i < 4*wh; i++)
1858         state->map->map[i] = state->map->map[i % wh];
1859
1860     assert(*p == ',');
1861     p++;
1862
1863     /*
1864      * Now process the clue list.
1865      */
1866     pos = 0;
1867     while (*p) {
1868         if (*p >= '0' && *p < '0'+FOUR) {
1869             state->colouring[pos] = *p - '0';
1870             state->map->immutable[pos] = TRUE;
1871             pos++;
1872         } else {
1873             assert(*p >= 'a' && *p <= 'z');
1874             pos += *p - 'a' + 1;
1875         }
1876         p++;
1877     }
1878     assert(pos == n);
1879
1880     state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);
1881
1882     /*
1883      * Attempt to smooth out some of the more jagged region
1884      * outlines by the judicious use of diagonally divided squares.
1885      */
1886     {
1887         random_state *rs = random_new(desc, strlen(desc));
1888         int *squares = snewn(wh, int);
1889         int done_something;
1890
1891         for (i = 0; i < wh; i++)
1892             squares[i] = i;
1893         shuffle(squares, wh, sizeof(*squares), rs);
1894
1895         do {
1896             done_something = FALSE;
1897             for (i = 0; i < wh; i++) {
1898                 int y = squares[i] / w, x = squares[i] % w;
1899                 int c = state->map->map[y*w+x];
1900                 int tc, bc, lc, rc;
1901
1902                 if (x == 0 || x == w-1 || y == 0 || y == h-1)
1903                     continue;
1904
1905                 if (state->map->map[TE * wh + y*w+x] !=
1906                     state->map->map[BE * wh + y*w+x])
1907                     continue;
1908
1909                 tc = state->map->map[BE * wh + (y-1)*w+x];
1910                 bc = state->map->map[TE * wh + (y+1)*w+x];
1911                 lc = state->map->map[RE * wh + y*w+(x-1)];
1912                 rc = state->map->map[LE * wh + y*w+(x+1)];
1913
1914                 /*
1915                  * If this square is adjacent on two sides to one
1916                  * region and on the other two sides to the other
1917                  * region, and is itself one of the two regions, we can
1918                  * adjust it so that it's a diagonal.
1919                  */
1920                 if (tc != bc && (tc == c || bc == c)) {
1921                     if ((lc == tc && rc == bc) ||
1922                         (lc == bc && rc == tc)) {
1923                         state->map->map[TE * wh + y*w+x] = tc;
1924                         state->map->map[BE * wh + y*w+x] = bc;
1925                         state->map->map[LE * wh + y*w+x] = lc;
1926                         state->map->map[RE * wh + y*w+x] = rc;
1927                         done_something = TRUE;
1928                     }
1929                 }
1930             }
1931         } while (done_something);
1932         sfree(squares);
1933         random_free(rs);
1934     }
1935
1936     /*
1937      * Analyse the map to find a canonical line segment
1938      * corresponding to each edge, and a canonical point
1939      * corresponding to each region. The former are where we'll
1940      * eventually put error markers; the latter are where we'll put
1941      * per-region flags such as numbers (when in diagnostic mode).
1942      */
1943     {
1944         int *bestx, *besty, *an, pass;
1945         float *ax, *ay, *best;
1946
1947         ax = snewn(state->map->ngraph + n, float);
1948         ay = snewn(state->map->ngraph + n, float);
1949         an = snewn(state->map->ngraph + n, int);
1950         bestx = snewn(state->map->ngraph + n, int);
1951         besty = snewn(state->map->ngraph + n, int);
1952         best = snewn(state->map->ngraph + n, float);
1953
1954         for (i = 0; i < state->map->ngraph + n; i++) {
1955             bestx[i] = besty[i] = -1;
1956             best[i] = (float)(2*(w+h)+1);
1957             ax[i] = ay[i] = 0.0F;
1958             an[i] = 0;
1959         }
1960
1961         /*
1962          * We make two passes over the map, finding all the line
1963          * segments separating regions and all the suitable points
1964          * within regions. In the first pass, we compute the
1965          * _average_ x and y coordinate of all the points in a
1966          * given class; in the second pass, for each such average
1967          * point, we find the candidate closest to it and call that
1968          * canonical.
1969          * 
1970          * Line segments are considered to have coordinates in
1971          * their centre. Thus, at least one coordinate for any line
1972          * segment is always something-and-a-half; so we store our
1973          * coordinates as twice their normal value.
1974          */
1975         for (pass = 0; pass < 2; pass++) {
1976             int x, y;
1977
1978             for (y = 0; y < h; y++)
1979                 for (x = 0; x < w; x++) {
1980                     int ex[4], ey[4], ea[4], eb[4], en = 0;
1981
1982                     /*
1983                      * Look for an edge to the right of this
1984                      * square, an edge below it, and an edge in the
1985                      * middle of it. Also look to see if the point
1986                      * at the bottom right of this square is on an
1987                      * edge (and isn't a place where more than two
1988                      * regions meet).
1989                      */
1990                     if (x+1 < w) {
1991                         /* right edge */
1992                         ea[en] = state->map->map[RE * wh + y*w+x];
1993                         eb[en] = state->map->map[LE * wh + y*w+(x+1)];
1994                         ex[en] = (x+1)*2;
1995                         ey[en] = y*2+1;
1996                         en++;
1997                     }
1998                     if (y+1 < h) {
1999                         /* bottom edge */
2000                         ea[en] = state->map->map[BE * wh + y*w+x];
2001                         eb[en] = state->map->map[TE * wh + (y+1)*w+x];
2002                         ex[en] = x*2+1;
2003                         ey[en] = (y+1)*2;
2004                         en++;
2005                     }
2006                     /* diagonal edge */
2007                     ea[en] = state->map->map[TE * wh + y*w+x];
2008                     eb[en] = state->map->map[BE * wh + y*w+x];
2009                     ex[en] = x*2+1;
2010                     ey[en] = y*2+1;
2011                     en++;
2012
2013                     if (x+1 < w && y+1 < h) {
2014                         /* bottom right corner */
2015                         int oct[8], othercol, nchanges;
2016                         oct[0] = state->map->map[RE * wh + y*w+x];
2017                         oct[1] = state->map->map[LE * wh + y*w+(x+1)];
2018                         oct[2] = state->map->map[BE * wh + y*w+(x+1)];
2019                         oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)];
2020                         oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)];
2021                         oct[5] = state->map->map[RE * wh + (y+1)*w+x];
2022                         oct[6] = state->map->map[TE * wh + (y+1)*w+x];
2023                         oct[7] = state->map->map[BE * wh + y*w+x];
2024
2025                         othercol = -1;
2026                         nchanges = 0;
2027                         for (i = 0; i < 8; i++) {
2028                             if (oct[i] != oct[0]) {
2029                                 if (othercol < 0)
2030                                     othercol = oct[i];
2031                                 else if (othercol != oct[i])
2032                                     break;   /* three colours at this point */
2033                             }
2034                             if (oct[i] != oct[(i+1) & 7])
2035                                 nchanges++;
2036                         }
2037
2038                         /*
2039                          * Now if there are exactly two regions at
2040                          * this point (not one, and not three or
2041                          * more), and only two changes around the
2042                          * loop, then this is a valid place to put
2043                          * an error marker.
2044                          */
2045                         if (i == 8 && othercol >= 0 && nchanges == 2) {
2046                             ea[en] = oct[0];
2047                             eb[en] = othercol;
2048                             ex[en] = (x+1)*2;
2049                             ey[en] = (y+1)*2;
2050                             en++;
2051                         }
2052
2053                         /*
2054                          * If there's exactly _one_ region at this
2055                          * point, on the other hand, it's a valid
2056                          * place to put a region centre.
2057                          */
2058                         if (othercol < 0) {
2059                             ea[en] = eb[en] = oct[0];
2060                             ex[en] = (x+1)*2;
2061                             ey[en] = (y+1)*2;
2062                             en++;
2063                         }
2064                     }
2065
2066                     /*
2067                      * Now process the points we've found, one by
2068                      * one.
2069                      */
2070                     for (i = 0; i < en; i++) {
2071                         int emin = min(ea[i], eb[i]);
2072                         int emax = max(ea[i], eb[i]);
2073                         int gindex;
2074
2075                         if (emin != emax) {
2076                             /* Graph edge */
2077                             gindex =
2078                                 graph_edge_index(state->map->graph, n,
2079                                                  state->map->ngraph, emin,
2080                                                  emax);
2081                         } else {
2082                             /* Region number */
2083                             gindex = state->map->ngraph + emin;
2084                         }
2085
2086                         assert(gindex >= 0);
2087
2088                         if (pass == 0) {
2089                             /*
2090                              * In pass 0, accumulate the values
2091                              * we'll use to compute the average
2092                              * positions.
2093                              */
2094                             ax[gindex] += ex[i];
2095                             ay[gindex] += ey[i];
2096                             an[gindex] += 1;
2097                         } else {
2098                             /*
2099                              * In pass 1, work out whether this
2100                              * point is closer to the average than
2101                              * the last one we've seen.
2102                              */
2103                             float dx, dy, d;
2104
2105                             assert(an[gindex] > 0);
2106                             dx = ex[i] - ax[gindex];
2107                             dy = ey[i] - ay[gindex];
2108                             d = (float)sqrt(dx*dx + dy*dy);
2109                             if (d < best[gindex]) {
2110                                 best[gindex] = d;
2111                                 bestx[gindex] = ex[i];
2112                                 besty[gindex] = ey[i];
2113                             }
2114                         }
2115                     }
2116                 }
2117
2118             if (pass == 0) {
2119                 for (i = 0; i < state->map->ngraph + n; i++)
2120                     if (an[i] > 0) {
2121                         ax[i] /= an[i];
2122                         ay[i] /= an[i];
2123                     }
2124             }
2125         }
2126
2127         state->map->edgex = snewn(state->map->ngraph, int);
2128         state->map->edgey = snewn(state->map->ngraph, int);
2129         memcpy(state->map->edgex, bestx, state->map->ngraph * sizeof(int));
2130         memcpy(state->map->edgey, besty, state->map->ngraph * sizeof(int));
2131
2132         state->map->regionx = snewn(n, int);
2133         state->map->regiony = snewn(n, int);
2134         memcpy(state->map->regionx, bestx + state->map->ngraph, n*sizeof(int));
2135         memcpy(state->map->regiony, besty + state->map->ngraph, n*sizeof(int));
2136
2137         for (i = 0; i < state->map->ngraph; i++)
2138             if (state->map->edgex[i] < 0) {
2139                 /* Find the other representation of this edge. */
2140                 int e = state->map->graph[i];
2141                 int iprime = graph_edge_index(state->map->graph, n,
2142                                               state->map->ngraph, e%n, e/n);
2143                 assert(state->map->edgex[iprime] >= 0);
2144                 state->map->edgex[i] = state->map->edgex[iprime];
2145                 state->map->edgey[i] = state->map->edgey[iprime];
2146             }
2147
2148         sfree(ax);
2149         sfree(ay);
2150         sfree(an);
2151         sfree(best);
2152         sfree(bestx);
2153         sfree(besty);
2154     }
2155
2156     return state;
2157 }
2158
2159 static game_state *dup_game(const game_state *state)
2160 {
2161     game_state *ret = snew(game_state);
2162
2163     ret->p = state->p;
2164     ret->colouring = snewn(state->p.n, int);
2165     memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
2166     ret->pencil = snewn(state->p.n, int);
2167     memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int));
2168     ret->map = state->map;
2169     ret->map->refcount++;
2170     ret->completed = state->completed;
2171     ret->cheated = state->cheated;
2172
2173     return ret;
2174 }
2175
2176 static void free_game(game_state *state)
2177 {
2178     if (--state->map->refcount <= 0) {
2179         sfree(state->map->map);
2180         sfree(state->map->graph);
2181         sfree(state->map->immutable);
2182         sfree(state->map->edgex);
2183         sfree(state->map->edgey);
2184         sfree(state->map->regionx);
2185         sfree(state->map->regiony);
2186         sfree(state->map);
2187     }
2188     sfree(state->pencil);
2189     sfree(state->colouring);
2190     sfree(state);
2191 }
2192
2193 static char *solve_game(const game_state *state, const game_state *currstate,
2194                         const char *aux, char **error)
2195 {
2196     if (!aux) {
2197         /*
2198          * Use the solver.
2199          */
2200         int *colouring;
2201         struct solver_scratch *sc;
2202         int sret;
2203         int i;
2204         char *ret, buf[80];
2205         int retlen, retsize;
2206
2207         colouring = snewn(state->map->n, int);
2208         memcpy(colouring, state->colouring, state->map->n * sizeof(int));
2209
2210         sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
2211         sret = map_solver(sc, state->map->graph, state->map->n,
2212                          state->map->ngraph, colouring, DIFFCOUNT-1);
2213         free_scratch(sc);
2214
2215         if (sret != 1) {
2216             sfree(colouring);
2217             if (sret == 0)
2218                 *error = "Puzzle is inconsistent";
2219             else
2220                 *error = "Unable to find a unique solution for this puzzle";
2221             return NULL;
2222         }
2223
2224         retsize = 64;
2225         ret = snewn(retsize, char);
2226         strcpy(ret, "S");
2227         retlen = 1;
2228
2229         for (i = 0; i < state->map->n; i++) {
2230             int len;
2231
2232             assert(colouring[i] >= 0);
2233             if (colouring[i] == currstate->colouring[i])
2234                 continue;
2235             assert(!state->map->immutable[i]);
2236
2237             len = sprintf(buf, ";%d:%d", colouring[i], i);
2238             if (retlen + len >= retsize) {
2239                 retsize = retlen + len + 256;
2240                 ret = sresize(ret, retsize, char);
2241             }
2242             strcpy(ret + retlen, buf);
2243             retlen += len;
2244         }
2245
2246         sfree(colouring);
2247
2248         return ret;
2249     }
2250     return dupstr(aux);
2251 }
2252
2253 static int game_can_format_as_text_now(const game_params *params)
2254 {
2255     return TRUE;
2256 }
2257
2258 static char *game_text_format(const game_state *state)
2259 {
2260     return NULL;
2261 }
2262
2263 struct game_ui {
2264     /*
2265      * drag_colour:
2266      * 
2267      *  - -2 means no drag currently active.
2268      *  - >=0 means we're dragging a solid colour.
2269      *  - -1 means we're dragging a blank space, and drag_pencil
2270      *    might or might not add some pencil-mark stipples to that.
2271      */
2272     int drag_colour;
2273     int drag_pencil;
2274     int dragx, dragy;
2275     int show_numbers;
2276
2277     int cur_x, cur_y, cur_visible, cur_moved, cur_lastmove;
2278 };
2279
2280 static game_ui *new_ui(const game_state *state)
2281 {
2282     game_ui *ui = snew(game_ui);
2283     ui->dragx = ui->dragy = -1;
2284     ui->drag_colour = -2;
2285     ui->drag_pencil = 0;
2286     ui->show_numbers = FALSE;
2287     ui->cur_x = ui->cur_y = ui->cur_visible = ui->cur_moved = 0;
2288     ui->cur_lastmove = 0;
2289     return ui;
2290 }
2291
2292 static void free_ui(game_ui *ui)
2293 {
2294     sfree(ui);
2295 }
2296
2297 static char *encode_ui(const game_ui *ui)
2298 {
2299     return NULL;
2300 }
2301
2302 static void decode_ui(game_ui *ui, const char *encoding)
2303 {
2304 }
2305
2306 static void game_changed_state(game_ui *ui, const game_state *oldstate,
2307                                const game_state *newstate)
2308 {
2309 }
2310
2311 struct game_drawstate {
2312     int tilesize;
2313     unsigned long *drawn, *todraw;
2314     int started;
2315     int dragx, dragy, drag_visible;
2316     blitter *bl;
2317 };
2318
2319 /* Flags in `drawn'. */
2320 #define ERR_BASE      0x00800000L
2321 #define ERR_MASK      0xFF800000L
2322 #define PENCIL_T_BASE 0x00080000L
2323 #define PENCIL_T_MASK 0x00780000L
2324 #define PENCIL_B_BASE 0x00008000L
2325 #define PENCIL_B_MASK 0x00078000L
2326 #define PENCIL_MASK   0x007F8000L
2327 #define SHOW_NUMBERS  0x00004000L
2328
2329 #define TILESIZE (ds->tilesize)
2330 #define BORDER (TILESIZE)
2331 #define COORD(x)  ( (x) * TILESIZE + BORDER )
2332 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
2333
2334  /*
2335   * EPSILON_FOO are epsilons added to absolute cursor position by
2336   * cursor movement, such that in pathological cases (e.g. a very
2337   * small diamond-shaped area) it's relatively easy to select the
2338   * region you wanted.
2339   */
2340
2341 #define EPSILON_X(button) (((button) == CURSOR_RIGHT) ? +1 : \
2342                            ((button) == CURSOR_LEFT)  ? -1 : 0)
2343 #define EPSILON_Y(button) (((button) == CURSOR_DOWN)  ? +1 : \
2344                            ((button) == CURSOR_UP)    ? -1 : 0)
2345
2346
2347 static int region_from_coords(const game_state *state,
2348                               const game_drawstate *ds, int x, int y)
2349 {
2350     int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
2351     int tx = FROMCOORD(x), ty = FROMCOORD(y);
2352     int dx = x - COORD(tx), dy = y - COORD(ty);
2353     int quadrant;
2354
2355     if (tx < 0 || tx >= w || ty < 0 || ty >= h)
2356         return -1;                     /* border */
2357
2358     quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
2359     quadrant = (quadrant == 0 ? BE :
2360                 quadrant == 1 ? LE :
2361                 quadrant == 2 ? RE : TE);
2362
2363     return state->map->map[quadrant * wh + ty*w+tx];
2364 }
2365
2366 static char *interpret_move(const game_state *state, game_ui *ui,
2367                             const game_drawstate *ds,
2368                             int x, int y, int button)
2369 {
2370     char *bufp, buf[256];
2371     int alt_button;
2372
2373     /*
2374      * Enable or disable numeric labels on regions.
2375      */
2376     if (button == 'l' || button == 'L') {
2377         ui->show_numbers = !ui->show_numbers;
2378         return "";
2379     }
2380
2381     if (IS_CURSOR_MOVE(button)) {
2382         move_cursor(button, &ui->cur_x, &ui->cur_y, state->p.w, state->p.h, 0);
2383         ui->cur_visible = 1;
2384         ui->cur_moved = 1;
2385         ui->cur_lastmove = button;
2386         ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(button);
2387         ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(button);
2388         return "";
2389     }
2390     if (IS_CURSOR_SELECT(button)) {
2391         if (!ui->cur_visible) {
2392             ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove);
2393             ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove);
2394             ui->cur_visible = 1;
2395             return "";
2396         }
2397         if (ui->drag_colour == -2) { /* not currently cursor-dragging, start. */
2398             int r = region_from_coords(state, ds, ui->dragx, ui->dragy);
2399             if (r >= 0) {
2400                 ui->drag_colour = state->colouring[r];
2401                 ui->drag_pencil = (ui->drag_colour >= 0) ? 0 : state->pencil[r];
2402             } else {
2403                 ui->drag_colour = -1;
2404                 ui->drag_pencil = 0;
2405             }
2406             ui->cur_moved = 0;
2407             return "";
2408         } else { /* currently cursor-dragging; drop the colour in the new region. */
2409             x = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove);
2410             y = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove);
2411             alt_button = (button == CURSOR_SELECT2) ? 1 : 0;
2412             /* Double-select removes current colour. */
2413             if (!ui->cur_moved) ui->drag_colour = -1;
2414             goto drag_dropped;
2415         }
2416     }
2417
2418     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2419         int r = region_from_coords(state, ds, x, y);
2420
2421         if (r >= 0) {
2422             ui->drag_colour = state->colouring[r];
2423             ui->drag_pencil = state->pencil[r];
2424             if (ui->drag_colour >= 0)
2425                 ui->drag_pencil = 0;  /* should be already, but double-check */
2426         } else {
2427             ui->drag_colour = -1;
2428             ui->drag_pencil = 0;
2429         }
2430         ui->dragx = x;
2431         ui->dragy = y;
2432         ui->cur_visible = 0;
2433         return "";
2434     }
2435
2436     if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
2437         ui->drag_colour > -2) {
2438         ui->dragx = x;
2439         ui->dragy = y;
2440         return "";
2441     }
2442
2443     if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
2444         ui->drag_colour > -2) {
2445         alt_button = (button == RIGHT_RELEASE) ? 1 : 0;
2446         goto drag_dropped;
2447     }
2448
2449     return NULL;
2450
2451 drag_dropped:
2452     {
2453         int r = region_from_coords(state, ds, x, y);
2454         int c = ui->drag_colour;
2455         int p = ui->drag_pencil;
2456         int oldp;
2457
2458         /*
2459          * Cancel the drag, whatever happens.
2460          */
2461         ui->drag_colour = -2;
2462
2463         if (r < 0)
2464             return "";                 /* drag into border; do nothing else */
2465
2466         if (state->map->immutable[r])
2467             return "";                 /* can't change this region */
2468
2469         if (state->colouring[r] == c && state->pencil[r] == p)
2470             return "";                 /* don't _need_ to change this region */
2471
2472         if (alt_button) {
2473             if (state->colouring[r] >= 0) {
2474                 /* Can't pencil on a coloured region */
2475                 return "";
2476             } else if (c >= 0) {
2477                 /* Right-dragging from colour to blank toggles one pencil */
2478                 p = state->pencil[r] ^ (1 << c);
2479                 c = -1;
2480             }
2481             /* Otherwise, right-dragging from blank to blank is equivalent
2482              * to left-dragging. */
2483         }
2484
2485         bufp = buf;
2486         oldp = state->pencil[r];
2487         if (c != state->colouring[r]) {
2488             bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
2489             if (c >= 0)
2490                 oldp = 0;
2491         }
2492         if (p != oldp) {
2493             int i;
2494             for (i = 0; i < FOUR; i++)
2495                 if ((oldp ^ p) & (1 << i))
2496                     bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r);
2497         }
2498
2499         return dupstr(buf+1);          /* ignore first semicolon */
2500     }
2501 }
2502
2503 static game_state *execute_move(const game_state *state, const char *move)
2504 {
2505     int n = state->p.n;
2506     game_state *ret = dup_game(state);
2507     int c, k, adv, i;
2508
2509     while (*move) {
2510         int pencil = FALSE;
2511
2512         c = *move;
2513         if (c == 'p') {
2514             pencil = TRUE;
2515             c = *++move;
2516         }
2517         if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
2518             sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
2519             k >= 0 && k < state->p.n) {
2520             move += 1 + adv;
2521             if (pencil) {
2522                 if (ret->colouring[k] >= 0) {
2523                     free_game(ret);
2524                     return NULL;
2525                 }
2526                 if (c == 'C')
2527                     ret->pencil[k] = 0;
2528                 else
2529                     ret->pencil[k] ^= 1 << (c - '0');
2530             } else {
2531                 ret->colouring[k] = (c == 'C' ? -1 : c - '0');
2532                 ret->pencil[k] = 0;
2533             }
2534         } else if (*move == 'S') {
2535             move++;
2536             ret->cheated = TRUE;
2537         } else {
2538             free_game(ret);
2539             return NULL;
2540         }
2541
2542         if (*move && *move != ';') {
2543             free_game(ret);
2544             return NULL;
2545         }
2546         if (*move)
2547             move++;
2548     }
2549
2550     /*
2551      * Check for completion.
2552      */
2553     if (!ret->completed) {
2554         int ok = TRUE;
2555
2556         for (i = 0; i < n; i++)
2557             if (ret->colouring[i] < 0) {
2558                 ok = FALSE;
2559                 break;
2560             }
2561
2562         if (ok) {
2563             for (i = 0; i < ret->map->ngraph; i++) {
2564                 int j = ret->map->graph[i] / n;
2565                 int k = ret->map->graph[i] % n;
2566                 if (ret->colouring[j] == ret->colouring[k]) {
2567                     ok = FALSE;
2568                     break;
2569                 }
2570             }
2571         }
2572
2573         if (ok)
2574             ret->completed = TRUE;
2575     }
2576
2577     return ret;
2578 }
2579
2580 /* ----------------------------------------------------------------------
2581  * Drawing routines.
2582  */
2583
2584 static void game_compute_size(const game_params *params, int tilesize,
2585                               int *x, int *y)
2586 {
2587     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2588     struct { int tilesize; } ads, *ds = &ads;
2589     ads.tilesize = tilesize;
2590
2591     *x = params->w * TILESIZE + 2 * BORDER + 1;
2592     *y = params->h * TILESIZE + 2 * BORDER + 1;
2593 }
2594
2595 static void game_set_size(drawing *dr, game_drawstate *ds,
2596                           const game_params *params, int tilesize)
2597 {
2598     ds->tilesize = tilesize;
2599
2600     assert(!ds->bl);                   /* set_size is never called twice */
2601     ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
2602 }
2603
2604 const float map_colours[FOUR][3] = {
2605 #ifdef VIVID_COLOURS
2606     /* Use more vivid colours (e.g. on the Pocket PC) */
2607     {0.75F, 0.25F, 0.25F},
2608     {0.3F,  0.7F,  0.3F},
2609     {0.3F,  0.3F,  0.7F},
2610     {0.85F, 0.85F, 0.1F},
2611 #else
2612     {0.7F, 0.5F, 0.4F},
2613     {0.8F, 0.7F, 0.4F},
2614     {0.5F, 0.6F, 0.4F},
2615     {0.55F, 0.45F, 0.35F},
2616 #endif
2617 };
2618 const int map_hatching[FOUR] = {
2619     HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
2620 };
2621
2622 static float *game_colours(frontend *fe, int *ncolours)
2623 {
2624     float *ret = snewn(3 * NCOLOURS, float);
2625
2626     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2627
2628     ret[COL_GRID * 3 + 0] = 0.0F;
2629     ret[COL_GRID * 3 + 1] = 0.0F;
2630     ret[COL_GRID * 3 + 2] = 0.0F;
2631
2632     memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
2633     memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
2634     memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
2635     memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
2636
2637     ret[COL_ERROR * 3 + 0] = 1.0F;
2638     ret[COL_ERROR * 3 + 1] = 0.0F;
2639     ret[COL_ERROR * 3 + 2] = 0.0F;
2640
2641     ret[COL_ERRTEXT * 3 + 0] = 1.0F;
2642     ret[COL_ERRTEXT * 3 + 1] = 1.0F;
2643     ret[COL_ERRTEXT * 3 + 2] = 1.0F;
2644
2645     *ncolours = NCOLOURS;
2646     return ret;
2647 }
2648
2649 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2650 {
2651     struct game_drawstate *ds = snew(struct game_drawstate);
2652     int i;
2653
2654     ds->tilesize = 0;
2655     ds->drawn = snewn(state->p.w * state->p.h, unsigned long);
2656     for (i = 0; i < state->p.w * state->p.h; i++)
2657         ds->drawn[i] = 0xFFFFL;
2658     ds->todraw = snewn(state->p.w * state->p.h, unsigned long);
2659     ds->started = FALSE;
2660     ds->bl = NULL;
2661     ds->drag_visible = FALSE;
2662     ds->dragx = ds->dragy = -1;
2663
2664     return ds;
2665 }
2666
2667 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2668 {
2669     sfree(ds->drawn);
2670     sfree(ds->todraw);
2671     if (ds->bl)
2672         blitter_free(dr, ds->bl);
2673     sfree(ds);
2674 }
2675
2676 static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
2677 {
2678     int coords[8];
2679     int yext, xext;
2680
2681     /*
2682      * Draw a diamond.
2683      */
2684     coords[0] = x - TILESIZE*2/5;
2685     coords[1] = y;
2686     coords[2] = x;
2687     coords[3] = y - TILESIZE*2/5;
2688     coords[4] = x + TILESIZE*2/5;
2689     coords[5] = y;
2690     coords[6] = x;
2691     coords[7] = y + TILESIZE*2/5;
2692     draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
2693
2694     /*
2695      * Draw an exclamation mark in the diamond. This turns out to
2696      * look unpleasantly off-centre if done via draw_text, so I do
2697      * it by hand on the basis that exclamation marks aren't that
2698      * difficult to draw...
2699      */
2700     xext = TILESIZE/16;
2701     yext = TILESIZE*2/5 - (xext*2+2);
2702     draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
2703               COL_ERRTEXT);
2704     draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
2705 }
2706
2707 static void draw_square(drawing *dr, game_drawstate *ds,
2708                         const game_params *params, struct map *map,
2709                         int x, int y, unsigned long v)
2710 {
2711     int w = params->w, h = params->h, wh = w*h;
2712     int tv, bv, xo, yo, i, j, oldj;
2713     unsigned long errs, pencil, show_numbers;
2714
2715     errs = v & ERR_MASK;
2716     v &= ~ERR_MASK;
2717     pencil = v & PENCIL_MASK;
2718     v &= ~PENCIL_MASK;
2719     show_numbers = v & SHOW_NUMBERS;
2720     v &= ~SHOW_NUMBERS;
2721     tv = v / FIVE;
2722     bv = v % FIVE;
2723
2724     clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2725
2726     /*
2727      * Draw the region colour.
2728      */
2729     draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
2730               (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
2731     /*
2732      * Draw the second region colour, if this is a diagonally
2733      * divided square.
2734      */
2735     if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
2736         int coords[6];
2737         coords[0] = COORD(x)-1;
2738         coords[1] = COORD(y+1)+1;
2739         if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
2740             coords[2] = COORD(x+1)+1;
2741         else
2742             coords[2] = COORD(x)-1;
2743         coords[3] = COORD(y)-1;
2744         coords[4] = COORD(x+1)+1;
2745         coords[5] = COORD(y+1)+1;
2746         draw_polygon(dr, coords, 3,
2747                      (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
2748     }
2749
2750     /*
2751      * Draw `pencil marks'. Currently we arrange these in a square
2752      * formation, which means we may be in trouble if the value of
2753      * FOUR changes later...
2754      */
2755     assert(FOUR == 4);
2756     for (yo = 0; yo < 4; yo++)
2757         for (xo = 0; xo < 4; xo++) {
2758             int te = map->map[TE * wh + y*w+x];
2759             int e, ee, c;
2760
2761             e = (yo < xo && yo < 3-xo ? TE :
2762                  yo > xo && yo > 3-xo ? BE :
2763                  xo < 2 ? LE : RE);
2764             ee = map->map[e * wh + y*w+x];
2765
2766             if (xo != (yo * 2 + 1) % 5)
2767                 continue;
2768             c = yo;
2769
2770             if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
2771                 continue;
2772
2773             if (yo == xo &&
2774                 (map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x]))
2775                 continue;              /* avoid TL-BR diagonal line */
2776             if (yo == 3-xo &&
2777                 (map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x]))
2778                 continue;              /* avoid BL-TR diagonal line */
2779
2780             draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5,
2781                         COORD(y) + (yo+1)*TILESIZE/5,
2782                         TILESIZE/7, COL_0 + c, COL_0 + c);
2783         }
2784
2785     /*
2786      * Draw the grid lines, if required.
2787      */
2788     if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
2789         draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
2790     if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
2791         draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
2792     if (x <= 0 || y <= 0 ||
2793         map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
2794         map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
2795         draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
2796
2797     /*
2798      * Draw error markers.
2799      */
2800     for (yo = 0; yo < 3; yo++)
2801         for (xo = 0; xo < 3; xo++)
2802             if (errs & (ERR_BASE << (yo*3+xo)))
2803                 draw_error(dr, ds,
2804                            (COORD(x)*2+TILESIZE*xo)/2,
2805                            (COORD(y)*2+TILESIZE*yo)/2);
2806
2807     /*
2808      * Draw region numbers, if desired.
2809      */
2810     if (show_numbers) {
2811         oldj = -1;
2812         for (i = 0; i < 2; i++) {
2813             j = map->map[(i?BE:TE)*wh+y*w+x];
2814             if (oldj == j)
2815                 continue;
2816             oldj = j;
2817
2818             xo = map->regionx[j] - 2*x;
2819             yo = map->regiony[j] - 2*y;
2820             if (xo >= 0 && xo <= 2 && yo >= 0 && yo <= 2) {
2821                 char buf[80];
2822                 sprintf(buf, "%d", j);
2823                 draw_text(dr, (COORD(x)*2+TILESIZE*xo)/2,
2824                           (COORD(y)*2+TILESIZE*yo)/2,
2825                           FONT_VARIABLE, 3*TILESIZE/5,
2826                           ALIGN_HCENTRE|ALIGN_VCENTRE,
2827                           COL_GRID, buf);
2828             }
2829         }
2830     }
2831
2832     unclip(dr);
2833
2834     draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2835 }
2836
2837 static void game_redraw(drawing *dr, game_drawstate *ds,
2838                         const game_state *oldstate, const game_state *state,
2839                         int dir, const game_ui *ui,
2840                         float animtime, float flashtime)
2841 {
2842     int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2843     int x, y, i;
2844     int flash;
2845
2846     if (ds->drag_visible) {
2847         blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
2848         draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
2849         ds->drag_visible = FALSE;
2850     }
2851
2852     /*
2853      * The initial contents of the window are not guaranteed and
2854      * can vary with front ends. To be on the safe side, all games
2855      * should start by drawing a big background-colour rectangle
2856      * covering the whole window.
2857      */
2858     if (!ds->started) {
2859         int ww, wh;
2860
2861         game_compute_size(&state->p, TILESIZE, &ww, &wh);
2862         draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
2863         draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
2864                   COL_GRID);
2865
2866         draw_update(dr, 0, 0, ww, wh);
2867         ds->started = TRUE;
2868     }
2869
2870     if (flashtime) {
2871         if (flash_type == 1)
2872             flash = (int)(flashtime * FOUR / flash_length);
2873         else
2874             flash = 1 + (int)(flashtime * THREE / flash_length);
2875     } else
2876         flash = -1;
2877
2878     /*
2879      * Set up the `todraw' array.
2880      */
2881     for (y = 0; y < h; y++)
2882         for (x = 0; x < w; x++) {
2883             int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
2884             int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
2885             unsigned long v;
2886
2887             if (tv < 0)
2888                 tv = FOUR;
2889             if (bv < 0)
2890                 bv = FOUR;
2891
2892             if (flash >= 0) {
2893                 if (flash_type == 1) {
2894                     if (tv == flash)
2895                         tv = FOUR;
2896                     if (bv == flash)
2897                         bv = FOUR;
2898                 } else if (flash_type == 2) {
2899                     if (flash % 2)
2900                         tv = bv = FOUR;
2901                 } else {
2902                     if (tv != FOUR)
2903                         tv = (tv + flash) % FOUR;
2904                     if (bv != FOUR)
2905                         bv = (bv + flash) % FOUR;
2906                 }
2907             }
2908
2909             v = tv * FIVE + bv;
2910
2911             /*
2912              * Add pencil marks.
2913              */
2914             for (i = 0; i < FOUR; i++) {
2915                 if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 &&
2916                     (state->pencil[state->map->map[TE * wh + y*w+x]] & (1<<i)))
2917                     v |= PENCIL_T_BASE << i;
2918                 if (state->colouring[state->map->map[BE * wh + y*w+x]] < 0 &&
2919                     (state->pencil[state->map->map[BE * wh + y*w+x]] & (1<<i)))
2920                     v |= PENCIL_B_BASE << i;
2921             }
2922
2923             if (ui->show_numbers)
2924                 v |= SHOW_NUMBERS;
2925
2926             ds->todraw[y*w+x] = v;
2927         }
2928
2929     /*
2930      * Add error markers to the `todraw' array.
2931      */
2932     for (i = 0; i < state->map->ngraph; i++) {
2933         int v1 = state->map->graph[i] / n;
2934         int v2 = state->map->graph[i] % n;
2935         int xo, yo;
2936
2937         if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
2938             continue;
2939         if (state->colouring[v1] != state->colouring[v2])
2940             continue;
2941
2942         x = state->map->edgex[i];
2943         y = state->map->edgey[i];
2944
2945         xo = x % 2; x /= 2;
2946         yo = y % 2; y /= 2;
2947
2948         ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo);
2949         if (xo == 0) {
2950             assert(x > 0);
2951             ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2);
2952         }
2953         if (yo == 0) {
2954             assert(y > 0);
2955             ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo);
2956         }
2957         if (xo == 0 && yo == 0) {
2958             assert(x > 0 && y > 0);
2959             ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2);
2960         }
2961     }
2962
2963     /*
2964      * Now actually draw everything.
2965      */
2966     for (y = 0; y < h; y++)
2967         for (x = 0; x < w; x++) {
2968             unsigned long v = ds->todraw[y*w+x];
2969             if (ds->drawn[y*w+x] != v) {
2970                 draw_square(dr, ds, &state->p, state->map, x, y, v);
2971                 ds->drawn[y*w+x] = v;
2972             }
2973         }
2974
2975     /*
2976      * Draw the dragged colour blob if any.
2977      */
2978     if ((ui->drag_colour > -2) || ui->cur_visible) {
2979         int bg, iscur = 0;
2980         if (ui->drag_colour >= 0)
2981             bg = COL_0 + ui->drag_colour;
2982         else if (ui->drag_colour == -1) {
2983             bg = COL_BACKGROUND;
2984         } else {
2985             int r = region_from_coords(state, ds, ui->dragx, ui->dragy);
2986             int c = (r < 0) ? -1 : state->colouring[r];
2987             assert(ui->cur_visible);
2988             /*bg = COL_GRID;*/
2989             bg = (c < 0) ? COL_BACKGROUND : COL_0 + c;
2990             iscur = 1;
2991         }
2992
2993         ds->dragx = ui->dragx - TILESIZE/2 - 2;
2994         ds->dragy = ui->dragy - TILESIZE/2 - 2;
2995         blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
2996         draw_circle(dr, ui->dragx, ui->dragy,
2997                     iscur ? TILESIZE/4 : TILESIZE/2, bg, COL_GRID);
2998         for (i = 0; i < FOUR; i++)
2999             if (ui->drag_pencil & (1 << i))
3000                 draw_circle(dr, ui->dragx + ((i*4+2)%10-3) * TILESIZE/10,
3001                             ui->dragy + (i*2-3) * TILESIZE/10,
3002                             TILESIZE/8, COL_0 + i, COL_0 + i);
3003         draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
3004         ds->drag_visible = TRUE;
3005     }
3006 }
3007
3008 static float game_anim_length(const game_state *oldstate,
3009                               const game_state *newstate, int dir, game_ui *ui)
3010 {
3011     return 0.0F;
3012 }
3013
3014 static float game_flash_length(const game_state *oldstate,
3015                                const game_state *newstate, int dir, game_ui *ui)
3016 {
3017     if (!oldstate->completed && newstate->completed &&
3018         !oldstate->cheated && !newstate->cheated) {
3019         if (flash_type < 0) {
3020             char *env = getenv("MAP_ALTERNATIVE_FLASH");
3021             if (env)
3022                 flash_type = atoi(env);
3023             else
3024                 flash_type = 0;
3025             flash_length = (flash_type == 1 ? 0.50F : 0.30F);
3026         }
3027         return flash_length;
3028     } else
3029         return 0.0F;
3030 }
3031
3032 static int game_status(const game_state *state)
3033 {
3034     return state->completed ? +1 : 0;
3035 }
3036
3037 static int game_timing_state(const game_state *state, game_ui *ui)
3038 {
3039     return TRUE;
3040 }
3041
3042 static void game_print_size(const game_params *params, float *x, float *y)
3043 {
3044     int pw, ph;
3045
3046     /*
3047      * I'll use 4mm squares by default, I think. Simplest way to
3048      * compute this size is to compute the pixel puzzle size at a
3049      * given tile size and then scale.
3050      */
3051     game_compute_size(params, 400, &pw, &ph);
3052     *x = pw / 100.0F;
3053     *y = ph / 100.0F;
3054 }
3055
3056 static void game_print(drawing *dr, const game_state *state, int tilesize)
3057 {
3058     int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
3059     int ink, c[FOUR], i;
3060     int x, y, r;
3061     int *coords, ncoords, coordsize;
3062
3063     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3064     struct { int tilesize; } ads, *ds = &ads;
3065     /* We can't call game_set_size() here because we don't want a blitter */
3066     ads.tilesize = tilesize;
3067
3068     ink = print_mono_colour(dr, 0);
3069     for (i = 0; i < FOUR; i++)
3070         c[i] = print_rgb_hatched_colour(dr, map_colours[i][0],
3071                                         map_colours[i][1], map_colours[i][2],
3072                                         map_hatching[i]);
3073
3074     coordsize = 0;
3075     coords = NULL;
3076
3077     print_line_width(dr, TILESIZE / 16);
3078
3079     /*
3080      * Draw a single filled polygon around each region.
3081      */
3082     for (r = 0; r < n; r++) {
3083         int octants[8], lastdir, d1, d2, ox, oy;
3084
3085         /*
3086          * Start by finding a point on the region boundary. Any
3087          * point will do. To do this, we'll search for a square
3088          * containing the region and then decide which corner of it
3089          * to use.
3090          */
3091         x = w;
3092         for (y = 0; y < h; y++) {
3093             for (x = 0; x < w; x++) {
3094                 if (state->map->map[wh*0+y*w+x] == r ||
3095                     state->map->map[wh*1+y*w+x] == r ||
3096                     state->map->map[wh*2+y*w+x] == r ||
3097                     state->map->map[wh*3+y*w+x] == r)
3098                     break;
3099             }
3100             if (x < w)
3101                 break;
3102         }
3103         assert(y < h && x < w);        /* we must have found one somewhere */
3104         /*
3105          * This is the first square in lexicographic order which
3106          * contains part of this region. Therefore, one of the top
3107          * two corners of the square must be what we're after. The
3108          * only case in which it isn't the top left one is if the
3109          * square is diagonally divided and the region is in the
3110          * bottom right half.
3111          */
3112         if (state->map->map[wh*TE+y*w+x] != r &&
3113             state->map->map[wh*LE+y*w+x] != r)
3114             x++;                       /* could just as well have done y++ */
3115
3116         /*
3117          * Now we have a point on the region boundary. Trace around
3118          * the region until we come back to this point,
3119          * accumulating coordinates for a polygon draw operation as
3120          * we go.
3121          */
3122         lastdir = -1;
3123         ox = x;
3124         oy = y;
3125         ncoords = 0;
3126
3127         do {
3128             /*
3129              * There are eight possible directions we could head in
3130              * from here. We identify them by octant numbers, and
3131              * we also use octant numbers to identify the spaces
3132              * between them:
3133              * 
3134              *   6   7   0
3135              *    \ 7|0 /
3136              *     \ | /
3137              *    6 \|/ 1
3138              * 5-----+-----1
3139              *    5 /|\ 2
3140              *     / | \
3141              *    / 4|3 \
3142              *   4   3   2
3143              */
3144             octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
3145             octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
3146             octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
3147             octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
3148             octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
3149             octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
3150             octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
3151             octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
3152
3153             d1 = d2 = -1;
3154             for (i = 0; i < 8; i++)
3155                 if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
3156                     assert(d2 == -1);
3157                     if (d1 == -1)
3158                         d1 = i;
3159                     else
3160                         d2 = i;
3161                 }
3162
3163             assert(d1 != -1 && d2 != -1);
3164             if (d1 == lastdir)
3165                 d1 = d2;
3166
3167             /*
3168              * Now we're heading in direction d1. Save the current
3169              * coordinates.
3170              */
3171             if (ncoords + 2 > coordsize) {
3172                 coordsize += 128;
3173                 coords = sresize(coords, coordsize, int);
3174             }
3175             coords[ncoords++] = COORD(x);
3176             coords[ncoords++] = COORD(y);
3177
3178             /*
3179              * Compute the new coordinates.
3180              */
3181             x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
3182             y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
3183             assert(x >= 0 && x <= w && y >= 0 && y <= h);
3184
3185             lastdir = d1 ^ 4;
3186         } while (x != ox || y != oy);
3187
3188         draw_polygon(dr, coords, ncoords/2,
3189                      state->colouring[r] >= 0 ?
3190                      c[state->colouring[r]] : -1, ink);
3191     }
3192     sfree(coords);
3193 }
3194
3195 #ifdef COMBINED
3196 #define thegame map
3197 #endif
3198
3199 const struct game thegame = {
3200     "Map", "games.map", "map",
3201     default_params,
3202     game_fetch_preset,
3203     decode_params,
3204     encode_params,
3205     free_params,
3206     dup_params,
3207     TRUE, game_configure, custom_params,
3208     validate_params,
3209     new_game_desc,
3210     validate_desc,
3211     new_game,
3212     dup_game,
3213     free_game,
3214     TRUE, solve_game,
3215     FALSE, game_can_format_as_text_now, game_text_format,
3216     new_ui,
3217     free_ui,
3218     encode_ui,
3219     decode_ui,
3220     game_changed_state,
3221     interpret_move,
3222     execute_move,
3223     20, game_compute_size, game_set_size,
3224     game_colours,
3225     game_new_drawstate,
3226     game_free_drawstate,
3227     game_redraw,
3228     game_anim_length,
3229     game_flash_length,
3230     game_status,
3231     TRUE, TRUE, game_print_size, game_print,
3232     FALSE,                             /* wants_statusbar */
3233     FALSE, game_timing_state,
3234     0,                                 /* flags */
3235 };
3236
3237 #ifdef STANDALONE_SOLVER
3238
3239 int main(int argc, char **argv)
3240 {
3241     game_params *p;
3242     game_state *s;
3243     char *id = NULL, *desc, *err;
3244     int grade = FALSE;
3245     int ret, diff, really_verbose = FALSE;
3246     struct solver_scratch *sc;
3247     int i;
3248
3249     while (--argc > 0) {
3250         char *p = *++argv;
3251         if (!strcmp(p, "-v")) {
3252             really_verbose = TRUE;
3253         } else if (!strcmp(p, "-g")) {
3254             grade = TRUE;
3255         } else if (*p == '-') {
3256             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
3257             return 1;
3258         } else {
3259             id = p;
3260         }
3261     }
3262
3263     if (!id) {
3264         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
3265         return 1;
3266     }
3267
3268     desc = strchr(id, ':');
3269     if (!desc) {
3270         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3271         return 1;
3272     }
3273     *desc++ = '\0';
3274
3275     p = default_params();
3276     decode_params(p, id);
3277     err = validate_desc(p, desc);
3278     if (err) {
3279         fprintf(stderr, "%s: %s\n", argv[0], err);
3280         return 1;
3281     }
3282     s = new_game(NULL, p, desc);
3283
3284     sc = new_scratch(s->map->graph, s->map->n, s->map->ngraph);
3285
3286     /*
3287      * When solving an Easy puzzle, we don't want to bother the
3288      * user with Hard-level deductions. For this reason, we grade
3289      * the puzzle internally before doing anything else.
3290      */
3291     ret = -1;                          /* placate optimiser */
3292     for (diff = 0; diff < DIFFCOUNT; diff++) {
3293         for (i = 0; i < s->map->n; i++)
3294             if (!s->map->immutable[i])
3295                 s->colouring[i] = -1;
3296         ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
3297                          s->colouring, diff);
3298         if (ret < 2)
3299             break;
3300     }
3301
3302     if (diff == DIFFCOUNT) {
3303         if (grade)
3304             printf("Difficulty rating: harder than Hard, or ambiguous\n");
3305         else
3306             printf("Unable to find a unique solution\n");
3307     } else {
3308         if (grade) {
3309             if (ret == 0)
3310                 printf("Difficulty rating: impossible (no solution exists)\n");
3311             else if (ret == 1)
3312                 printf("Difficulty rating: %s\n", map_diffnames[diff]);
3313         } else {
3314             verbose = really_verbose;
3315             for (i = 0; i < s->map->n; i++)
3316                 if (!s->map->immutable[i])
3317                     s->colouring[i] = -1;
3318             ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
3319                              s->colouring, diff);
3320             if (ret == 0)
3321                 printf("Puzzle is inconsistent\n");
3322             else {
3323                 int col = 0;
3324
3325                 for (i = 0; i < s->map->n; i++) {
3326                     printf("%5d <- %c%c", i, colnames[s->colouring[i]],
3327                            (col < 6 && i+1 < s->map->n ? ' ' : '\n'));
3328                     if (++col == 7)
3329                         col = 0;
3330                 }
3331             }
3332         }
3333     }
3334
3335     return 0;
3336 }
3337
3338 #endif
3339
3340 /* vim: set shiftwidth=4 tabstop=8: */