map.c

   1 /*
   2  * map.c: Game involving four-colouring a map.
   3  */
   4
   5 /*
   6  * TODO:
   7  *
   8  *  - error highlighting
   9  *  - clue marking
  10  *  - more solver brains?
  11  *  - better four-colouring algorithm?
  12  *  - pencil marks?
  13  */
  14
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <string.h>
  18 #include <assert.h>
  19 #include <ctype.h>
  20 #include <math.h>
  21
  22 #include "puzzles.h"
  23
  24 /*
  25  * I don't seriously anticipate wanting to change the number of
  26  * colours used in this game, but it doesn't cost much to use a
  27  * #define just in case :-)
  28  */
  29 #define FOUR 4
  30 #define THREE (FOUR-1)
  31 #define FIVE (FOUR+1)
  32 #define SIX (FOUR+2)
  33
  34 /*
  35  * Ghastly run-time configuration option, just for Gareth (again).
  36  */
  37 static int flash_type = -1;
  38 static float flash_length;
  39
  40 /*
  41  * Difficulty levels. I do some macro ickery here to ensure that my
  42  * enum and the various forms of my name list always match up.
  43  */
  44 #define DIFFLIST(A) \
  45     A(EASY,Easy,e) \
  46     A(NORMAL,Normal,n)
  47 #define ENUM(upper,title,lower) DIFF_ ## upper,
  48 #define TITLE(upper,title,lower) #title,
  49 #define ENCODE(upper,title,lower) #lower
  50 #define CONFIG(upper,title,lower) ":" #title
  51 enum { DIFFLIST(ENUM) DIFFCOUNT };
  52 static char const *const map_diffnames[] = { DIFFLIST(TITLE) };
  53 static char const map_diffchars[] = DIFFLIST(ENCODE);
  54 #define DIFFCONFIG DIFFLIST(CONFIG)
  55
  56 enum { TE, BE, LE, RE };               /* top/bottom/left/right edges */
  57
  58 enum {
  59     COL_BACKGROUND,
  60     COL_GRID,
  61     COL_0, COL_1, COL_2, COL_3,
  62     NCOLOURS
  63 };
  64
  65 struct game_params {
  66     int w, h, n, diff;
  67 };
  68
  69 struct map {
  70     int refcount;
  71     int *map;
  72     int *graph;
  73     int n;
  74     int ngraph;
  75     int *immutable;
  76 };
  77
  78 struct game_state {
  79     game_params p;
  80     struct map *map;
  81     int *colouring;
  82     int completed, cheated;
  83 };
  84
  85 static game_params *default_params(void)
  86 {
  87     game_params *ret = snew(game_params);
  88
  89     ret->w = 20;
  90     ret->h = 15;
  91     ret->n = 30;
  92     ret->diff = DIFF_NORMAL;
  93
  94     return ret;
  95 }
  96
  97 static const struct game_params map_presets[] = {
  98     {20, 15, 30, DIFF_EASY},
  99     {20, 15, 30, DIFF_NORMAL},
 100     {30, 25, 75, DIFF_NORMAL},
 101 };
 102
 103 static int game_fetch_preset(int i, char **name, game_params **params)
 104 {
 105     game_params *ret;
 106     char str[80];
 107
 108     if (i < 0 || i >= lenof(map_presets))
 109         return FALSE;
 110
 111     ret = snew(game_params);
 112     *ret = map_presets[i];
 113
 114     sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
 115             map_diffnames[ret->diff]);
 116
 117     *name = dupstr(str);
 118     *params = ret;
 119     return TRUE;
 120 }
 121
 122 static void free_params(game_params *params)
 123 {
 124     sfree(params);
 125 }
 126
 127 static game_params *dup_params(game_params *params)
 128 {
 129     game_params *ret = snew(game_params);
 130     *ret = *params;                    /* structure copy */
 131     return ret;
 132 }
 133
 134 static void decode_params(game_params *params, char const *string)
 135 {
 136     char const *p = string;
 137
 138     params->w = atoi(p);
 139     while (*p && isdigit((unsigned char)*p)) p++;
 140     if (*p == 'x') {
 141         p++;
 142         params->h = atoi(p);
 143         while (*p && isdigit((unsigned char)*p)) p++;
 144     } else {
 145         params->h = params->w;
 146     }
 147     if (*p == 'n') {
 148         p++;
 149         params->n = atoi(p);
 150         while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
 151     } else {
 152         params->n = params->w * params->h / 8;
 153     }
 154     if (*p == 'd') {
 155         int i;
 156         p++;
 157         for (i = 0; i < DIFFCOUNT; i++)
 158             if (*p == map_diffchars[i])
 159                 params->diff = i;
 160         if (*p) p++;
 161     }
 162 }
 163
 164 static char *encode_params(game_params *params, int full)
 165 {
 166     char ret[400];
 167
 168     sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
 169     if (full)
 170         sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
 171
 172     return dupstr(ret);
 173 }
 174
 175 static config_item *game_configure(game_params *params)
 176 {
 177     config_item *ret;
 178     char buf[80];
 179
 180     ret = snewn(5, config_item);
 181
 182     ret[0].name = "Width";
 183     ret[0].type = C_STRING;
 184     sprintf(buf, "%d", params->w);
 185     ret[0].sval = dupstr(buf);
 186     ret[0].ival = 0;
 187
 188     ret[1].name = "Height";
 189     ret[1].type = C_STRING;
 190     sprintf(buf, "%d", params->h);
 191     ret[1].sval = dupstr(buf);
 192     ret[1].ival = 0;
 193
 194     ret[2].name = "Regions";
 195     ret[2].type = C_STRING;
 196     sprintf(buf, "%d", params->n);
 197     ret[2].sval = dupstr(buf);
 198     ret[2].ival = 0;
 199
 200     ret[3].name = "Difficulty";
 201     ret[3].type = C_CHOICES;
 202     ret[3].sval = DIFFCONFIG;
 203     ret[3].ival = params->diff;
 204
 205     ret[4].name = NULL;
 206     ret[4].type = C_END;
 207     ret[4].sval = NULL;
 208     ret[4].ival = 0;
 209
 210     return ret;
 211 }
 212
 213 static game_params *custom_params(config_item *cfg)
 214 {
 215     game_params *ret = snew(game_params);
 216
 217     ret->w = atoi(cfg[0].sval);
 218     ret->h = atoi(cfg[1].sval);
 219     ret->n = atoi(cfg[2].sval);
 220     ret->diff = cfg[3].ival;
 221
 222     return ret;
 223 }
 224
 225 static char *validate_params(game_params *params, int full)
 226 {
 227     if (params->w < 2 || params->h < 2)
 228         return "Width and height must be at least two";
 229     if (params->n < 5)
 230         return "Must have at least five regions";
 231     if (params->n > params->w * params->h)
 232         return "Too many regions to fit in grid";
 233     return NULL;
 234 }
 235
 236 /* ----------------------------------------------------------------------
 237  * Cumulative frequency table functions.
 238  */
 239
 240 /*
 241  * Initialise a cumulative frequency table. (Hardly worth writing
 242  * this function; all it does is to initialise everything in the
 243  * array to zero.)
 244  */
 245 static void cf_init(int *table, int n)
 246 {
 247     int i;
 248
 249     for (i = 0; i < n; i++)
 250         table[i] = 0;
 251 }
 252
 253 /*
 254  * Increment the count of symbol `sym' by `count'.
 255  */
 256 static void cf_add(int *table, int n, int sym, int count)
 257 {
 258     int bit;
 259
 260     bit = 1;
 261     while (sym != 0) {
 262         if (sym & bit) {
 263             table[sym] += count;
 264             sym &= ~bit;
 265         }
 266         bit <<= 1;
 267     }
 268
 269     table[0] += count;
 270 }
 271
 272 /*
 273  * Cumulative frequency lookup: return the total count of symbols
 274  * with value less than `sym'.
 275  */
 276 static int cf_clookup(int *table, int n, int sym)
 277 {
 278     int bit, index, limit, count;
 279
 280     if (sym == 0)
 281         return 0;
 282
 283     assert(0 < sym && sym <= n);
 284
 285     count = table[0];                  /* start with the whole table size */
 286
 287     bit = 1;
 288     while (bit < n)
 289         bit <<= 1;
 290
 291     limit = n;
 292
 293     while (bit > 0) {
 294         /*
 295          * Find the least number with its lowest set bit in this
 296          * position which is greater than or equal to sym.
 297          */
 298         index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
 299
 300         if (index < limit) {
 301             count -= table[index];
 302             limit = index;
 303         }
 304
 305         bit >>= 1;
 306     }
 307
 308     return count;
 309 }
 310
 311 /*
 312  * Single frequency lookup: return the count of symbol `sym'.
 313  */
 314 static int cf_slookup(int *table, int n, int sym)
 315 {
 316     int count, bit;
 317
 318     assert(0 <= sym && sym < n);
 319
 320     count = table[sym];
 321
 322     for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
 323         count -= table[sym+bit];
 324
 325     return count;
 326 }
 327
 328 /*
 329  * Return the largest symbol index such that the cumulative
 330  * frequency up to that symbol is less than _or equal to_ count.
 331  */
 332 static int cf_whichsym(int *table, int n, int count) {
 333     int bit, sym, top;
 334
 335     assert(count >= 0 && count < table[0]);
 336
 337     bit = 1;
 338     while (bit < n)
 339         bit <<= 1;
 340
 341     sym = 0;
 342     top = table[0];
 343
 344     while (bit > 0) {
 345         if (sym+bit < n) {
 346             if (count >= top - table[sym+bit])
 347                 sym += bit;
 348             else
 349                 top -= table[sym+bit];
 350         }
 351
 352         bit >>= 1;
 353     }
 354
 355     return sym;
 356 }
 357
 358 /* ----------------------------------------------------------------------
 359  * Map generation.
 360  *
 361  * FIXME: this isn't entirely optimal at present, because it
 362  * inherently prioritises growing the largest region since there
 363  * are more squares adjacent to it. This acts as a destabilising
 364  * influence leading to a few large regions and mostly small ones.
 365  * It might be better to do it some other way.
 366  */
 367
 368 #define WEIGHT_INCREASED 2             /* for increased perimeter */
 369 #define WEIGHT_DECREASED 4             /* for decreased perimeter */
 370 #define WEIGHT_UNCHANGED 3             /* for unchanged perimeter */
 371
 372 /*
 373  * Look at a square and decide which colours can be extended into
 374  * it.
 375  *
 376  * If called with index < 0, it adds together one of
 377  * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
 378  * colour that has a valid extension (according to the effect that
 379  * it would have on the perimeter of the region being extended) and
 380  * returns the overall total.
 381  *
 382  * If called with index >= 0, it returns one of the possible
 383  * colours depending on the value of index, in such a way that the
 384  * number of possible inputs which would give rise to a given
 385  * return value correspond to the weight of that value.
 386  */
 387 static int extend_options(int w, int h, int n, int *map,
 388                           int x, int y, int index)
 389 {
 390     int c, i, dx, dy;
 391     int col[8];
 392     int total = 0;
 393
 394     if (map[y*w+x] >= 0) {
 395         assert(index < 0);
 396         return 0;                      /* can't do this square at all */
 397     }
 398
 399     /*
 400      * Fetch the eight neighbours of this square, in order around
 401      * the square.
 402      */
 403     for (dy = -1; dy <= +1; dy++)
 404         for (dx = -1; dx <= +1; dx++) {
 405             int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx));
 406             if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h)
 407                 col[index] = map[(y+dy)*w+(x+dx)];
 408             else
 409                 col[index] = -1;
 410         }
 411
 412     /*
 413      * Iterate over each colour that might be feasible.
 414      *
 415      * FIXME: this routine currently has O(n) running time. We
 416      * could turn it into O(FOUR) by only bothering to iterate over
 417      * the colours mentioned in the four neighbouring squares.
 418      */
 419
 420     for (c = 0; c < n; c++) {
 421         int count, neighbours, runs;
 422
 423         /*
 424          * One of the even indices of col (representing the
 425          * orthogonal neighbours of this square) must be equal to
 426          * c, or else this square is not adjacent to region c and
 427          * obviously cannot become an extension of it at this time.
 428          */
 429         neighbours = 0;
 430         for (i = 0; i < 8; i += 2)
 431             if (col[i] == c)
 432                 neighbours++;
 433         if (!neighbours)
 434             continue;
 435
 436         /*
 437          * Now we know this square is adjacent to region c. The
 438          * next question is, would extending it cause the region to
 439          * become non-simply-connected? If so, we mustn't do it.
 440          *
 441          * We determine this by looking around col to see if we can
 442          * find more than one separate run of colour c.
 443          */
 444         runs = 0;
 445         for (i = 0; i < 8; i++)
 446             if (col[i] == c && col[(i+1) & 7] != c)
 447                 runs++;
 448         if (runs > 1)
 449             continue;
 450
 451         assert(runs == 1);
 452
 453         /*
 454          * This square is a possibility. Determine its effect on
 455          * the region's perimeter (computed from the number of
 456          * orthogonal neighbours - 1 means a perimeter increase, 3
 457          * a decrease, 2 no change; 4 is impossible because the
 458          * region would already not be simply connected) and we're
 459          * done.
 460          */
 461         assert(neighbours > 0 && neighbours < 4);
 462         count = (neighbours == 1 ? WEIGHT_INCREASED :
 463                  neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);
 464
 465         total += count;
 466         if (index >= 0 && index < count)
 467             return c;
 468         else
 469             index -= count;
 470     }
 471
 472     assert(index < 0);
 473
 474     return total;
 475 }
 476
 477 static void genmap(int w, int h, int n, int *map, random_state *rs)
 478 {
 479     int wh = w*h;
 480     int x, y, i, k;
 481     int *tmp;
 482
 483     assert(n <= wh);
 484     tmp = snewn(wh, int);
 485
 486     /*
 487      * Clear the map, and set up `tmp' as a list of grid indices.
 488      */
 489     for (i = 0; i < wh; i++) {
 490         map[i] = -1;
 491         tmp[i] = i;
 492     }
 493
 494     /*
 495      * Place the region seeds by selecting n members from `tmp'.
 496      */
 497     k = wh;
 498     for (i = 0; i < n; i++) {
 499         int j = random_upto(rs, k);
 500         map[tmp[j]] = i;
 501         tmp[j] = tmp[--k];
 502     }
 503
 504     /*
 505      * Re-initialise `tmp' as a cumulative frequency table. This
 506      * will store the number of possible region colours we can
 507      * extend into each square.
 508      */
 509     cf_init(tmp, wh);
 510
 511     /*
 512      * Go through the grid and set up the initial cumulative
 513      * frequencies.
 514      */
 515     for (y = 0; y < h; y++)
 516         for (x = 0; x < w; x++)
 517             cf_add(tmp, wh, y*w+x,
 518                    extend_options(w, h, n, map, x, y, -1));
 519
 520     /*
 521      * Now repeatedly choose a square we can extend a region into,
 522      * and do so.
 523      */
 524     while (tmp[0] > 0) {
 525         int k = random_upto(rs, tmp[0]);
 526         int sq;
 527         int colour;
 528         int xx, yy;
 529
 530         sq = cf_whichsym(tmp, wh, k);
 531         k -= cf_clookup(tmp, wh, sq);
 532         x = sq % w;
 533         y = sq / w;
 534         colour = extend_options(w, h, n, map, x, y, k);
 535
 536         map[sq] = colour;
 537
 538         /*
 539          * Re-scan the nine cells around the one we've just
 540          * modified.
 541          */
 542         for (yy = max(y-1, 0); yy < min(y+2, h); yy++)
 543             for (xx = max(x-1, 0); xx < min(x+2, w); xx++) {
 544                 cf_add(tmp, wh, yy*w+xx,
 545                        -cf_slookup(tmp, wh, yy*w+xx) +
 546                        extend_options(w, h, n, map, xx, yy, -1));
 547             }
 548     }
 549
 550     /*
 551      * Finally, go through and normalise the region labels into
 552      * order, meaning that indistinguishable maps are actually
 553      * identical.
 554      */
 555     for (i = 0; i < n; i++)
 556         tmp[i] = -1;
 557     k = 0;
 558     for (i = 0; i < wh; i++) {
 559         assert(map[i] >= 0);
 560         if (tmp[map[i]] < 0)
 561             tmp[map[i]] = k++;
 562         map[i] = tmp[map[i]];
 563     }
 564
 565     sfree(tmp);
 566 }
 567
 568 /* ----------------------------------------------------------------------
 569  * Functions to handle graphs.
 570  */
 571
 572 /*
 573  * Having got a map in a square grid, convert it into a graph
 574  * representation.
 575  */
 576 static int gengraph(int w, int h, int n, int *map, int *graph)
 577 {
 578     int i, j, x, y;
 579
 580     /*
 581      * Start by setting the graph up as an adjacency matrix. We'll
 582      * turn it into a list later.
 583      */
 584     for (i = 0; i < n*n; i++)
 585         graph[i] = 0;
 586
 587     /*
 588      * Iterate over the map looking for all adjacencies.
 589      */
 590     for (y = 0; y < h; y++)
 591         for (x = 0; x < w; x++) {
 592             int v, vx, vy;
 593             v = map[y*w+x];
 594             if (x+1 < w && (vx = map[y*w+(x+1)]) != v)
 595                 graph[v*n+vx] = graph[vx*n+v] = 1;
 596             if (y+1 < h && (vy = map[(y+1)*w+x]) != v)
 597                 graph[v*n+vy] = graph[vy*n+v] = 1;
 598         }
 599
 600     /*
 601      * Turn the matrix into a list.
 602      */
 603     for (i = j = 0; i < n*n; i++)
 604         if (graph[i])
 605             graph[j++] = i;
 606
 607     return j;
 608 }
 609
 610 static int graph_adjacent(int *graph, int n, int ngraph, int i, int j)
 611 {
 612     int v = i*n+j;
 613     int top, bot, mid;
 614
 615     bot = -1;
 616     top = ngraph;
 617     while (top - bot > 1) {
 618         mid = (top + bot) / 2;
 619         if (graph[mid] == v)
 620             return TRUE;
 621         else if (graph[mid] < v)
 622             bot = mid;
 623         else
 624             top = mid;
 625     }
 626     return FALSE;
 627 }
 628
 629 static int graph_vertex_start(int *graph, int n, int ngraph, int i)
 630 {
 631     int v = i*n;
 632     int top, bot, mid;
 633
 634     bot = -1;
 635     top = ngraph;
 636     while (top - bot > 1) {
 637         mid = (top + bot) / 2;
 638         if (graph[mid] < v)
 639             bot = mid;
 640         else
 641             top = mid;
 642     }
 643     return top;
 644 }
 645
 646 /* ----------------------------------------------------------------------
 647  * Generate a four-colouring of a graph.
 648  *
 649  * FIXME: it would be nice if we could convert this recursion into
 650  * pseudo-recursion using some sort of explicit stack array, for
 651  * the sake of the Palm port and its limited stack.
 652  */
 653
 654 static int fourcolour_recurse(int *graph, int n, int ngraph,
 655                               int *colouring, int *scratch, random_state *rs)
 656 {
 657     int nfree, nvert, start, i, j, k, c, ci;
 658     int cs[FOUR];
 659
 660     /*
 661      * Find the smallest number of free colours in any uncoloured
 662      * vertex, and count the number of such vertices.
 663      */
 664
 665     nfree = FIVE;                      /* start off bigger than FOUR! */
 666     nvert = 0;
 667     for (i = 0; i < n; i++)
 668         if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) {
 669             if (nfree > scratch[i*FIVE+FOUR]) {
 670                 nfree = scratch[i*FIVE+FOUR];
 671                 nvert = 0;
 672             }
 673             nvert++;
 674         }
 675
 676     /*
 677      * If there aren't any uncoloured vertices at all, we're done.
 678      */
 679     if (nvert == 0)
 680         return TRUE;                   /* we've got a colouring! */
 681
 682     /*
 683      * Pick a random vertex in that set.
 684      */
 685     j = random_upto(rs, nvert);
 686     for (i = 0; i < n; i++)
 687         if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
 688             if (j-- == 0)
 689                 break;
 690     assert(i < n);
 691     start = graph_vertex_start(graph, n, ngraph, i);
 692
 693     /*
 694      * Loop over the possible colours for i, and recurse for each
 695      * one.
 696      */
 697     ci = 0;
 698     for (c = 0; c < FOUR; c++)
 699         if (scratch[i*FIVE+c] == 0)
 700             cs[ci++] = c;
 701     shuffle(cs, ci, sizeof(*cs), rs);
 702
 703     while (ci-- > 0) {
 704         c = cs[ci];
 705
 706         /*
 707          * Fill in this colour.
 708          */
 709         colouring[i] = c;
 710
 711         /*
 712          * Update the scratch space to reflect a new neighbour
 713          * of this colour for each neighbour of vertex i.
 714          */
 715         for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
 716             k = graph[j] - i*n;
 717             if (scratch[k*FIVE+c] == 0)
 718                 scratch[k*FIVE+FOUR]--;
 719             scratch[k*FIVE+c]++;
 720         }
 721
 722         /*
 723          * Recurse.
 724          */
 725         if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
 726             return TRUE;               /* got one! */
 727
 728         /*
 729          * If that didn't work, clean up and try again with a
 730          * different colour.
 731          */
 732         for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
 733             k = graph[j] - i*n;
 734             scratch[k*FIVE+c]--;
 735             if (scratch[k*FIVE+c] == 0)
 736                 scratch[k*FIVE+FOUR]++;
 737         }
 738         colouring[i] = -1;
 739     }
 740
 741     /*
 742      * If we reach here, we were unable to find a colouring at all.
 743      * (This doesn't necessarily mean the Four Colour Theorem is
 744      * violated; it might just mean we've gone down a dead end and
 745      * need to back up and look somewhere else. It's only an FCT
 746      * violation if we get all the way back up to the top level and
 747      * still fail.)
 748      */
 749     return FALSE;
 750 }
 751
 752 static void fourcolour(int *graph, int n, int ngraph, int *colouring,
 753                        random_state *rs)
 754 {
 755     int *scratch;
 756     int i;
 757
 758     /*
 759      * For each vertex and each colour, we store the number of
 760      * neighbours that have that colour. Also, we store the number
 761      * of free colours for the vertex.
 762      */
 763     scratch = snewn(n * FIVE, int);
 764     for (i = 0; i < n * FIVE; i++)
 765         scratch[i] = (i % FIVE == FOUR ? FOUR : 0);
 766
 767     /*
 768      * Clear the colouring to start with.
 769      */
 770     for (i = 0; i < n; i++)
 771         colouring[i] = -1;
 772
 773     i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
 774     assert(i);                         /* by the Four Colour Theorem :-) */
 775
 776     sfree(scratch);
 777 }
 778
 779 /* ----------------------------------------------------------------------
 780  * Non-recursive solver.
 781  */
 782
 783 struct solver_scratch {
 784     unsigned char *possible;           /* bitmap of colours for each region */
 785     int *graph;
 786     int n;
 787     int ngraph;
 788 };
 789
 790 static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
 791 {
 792     struct solver_scratch *sc;
 793
 794     sc = snew(struct solver_scratch);
 795     sc->graph = graph;
 796     sc->n = n;
 797     sc->ngraph = ngraph;
 798     sc->possible = snewn(n, unsigned char);
 799
 800     return sc;
 801 }
 802
 803 static void free_scratch(struct solver_scratch *sc)
 804 {
 805     sfree(sc->possible);
 806     sfree(sc);
 807 }
 808
 809 static int place_colour(struct solver_scratch *sc,
 810                         int *colouring, int index, int colour)
 811 {
 812     int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
 813     int j, k;
 814
 815     if (!(sc->possible[index] & (1 << colour)))
 816         return FALSE;                  /* can't do it */
 817
 818     sc->possible[index] = 1 << colour;
 819     colouring[index] = colour;
 820
 821     /*
 822      * Rule out this colour from all the region's neighbours.
 823      */
 824     for (j = graph_vertex_start(graph, n, ngraph, index);
 825          j < ngraph && graph[j] < n*(index+1); j++) {
 826         k = graph[j] - index*n;
 827         sc->possible[k] &= ~(1 << colour);
 828     }
 829
 830     return TRUE;
 831 }
 832
 833 /*
 834  * Returns 0 for impossible, 1 for success, 2 for failure to
 835  * converge (i.e. puzzle is either ambiguous or just too
 836  * difficult).
 837  */
 838 static int map_solver(struct solver_scratch *sc,
 839                       int *graph, int n, int ngraph, int *colouring,
 840                       int difficulty)
 841 {
 842     int i;
 843
 844     /*
 845      * Initialise scratch space.
 846      */
 847     for (i = 0; i < n; i++)
 848         sc->possible[i] = (1 << FOUR) - 1;
 849
 850     /*
 851      * Place clues.
 852      */
 853     for (i = 0; i < n; i++)
 854         if (colouring[i] >= 0) {
 855             if (!place_colour(sc, colouring, i, colouring[i]))
 856                 return 0;              /* the clues aren't even consistent! */
 857         }
 858
 859     /*
 860      * Now repeatedly loop until we find nothing further to do.
 861      */
 862     while (1) {
 863         int done_something = FALSE;
 864
 865         if (difficulty < DIFF_EASY)
 866             break;                     /* can't do anything at all! */
 867
 868         /*
 869          * Simplest possible deduction: find a region with only one
 870          * possible colour.
 871          */
 872         for (i = 0; i < n; i++) if (colouring[i] < 0) {
 873             int p = sc->possible[i];
 874
 875             if (p == 0)
 876                 return 0;              /* puzzle is inconsistent */
 877
 878             if ((p & (p-1)) == 0) {    /* p is a power of two */
 879                 int c;
 880                 for (c = 0; c < FOUR; c++)
 881                     if (p == (1 << c))
 882                         break;
 883                 assert(c < FOUR);
 884                 if (!place_colour(sc, colouring, i, c))
 885                     return 0;          /* found puzzle to be inconsistent */
 886                 done_something = TRUE;
 887             }
 888         }
 889
 890         if (done_something)
 891             continue;
 892
 893         if (difficulty < DIFF_NORMAL)
 894             break;                     /* can't do anything harder */
 895
 896         /*
 897          * Failing that, go up one level. Look for pairs of regions
 898          * which (a) both have the same pair of possible colours,
 899          * (b) are adjacent to one another, (c) are adjacent to the
 900          * same region, and (d) that region still thinks it has one
 901          * or both of those possible colours.
 902          *
 903          * Simplest way to do this is by going through the graph
 904          * edge by edge, so that we start with property (b) and
 905          * then look for (a) and finally (c) and (d).
 906          */
 907         for (i = 0; i < ngraph; i++) {
 908             int j1 = graph[i] / n, j2 = graph[i] % n;
 909             int j, k, v, v2;
 910
 911             if (j1 > j2)
 912                 continue;              /* done it already, other way round */
 913
 914             if (colouring[j1] >= 0 || colouring[j2] >= 0)
 915                 continue;              /* they're not undecided */
 916
 917             if (sc->possible[j1] != sc->possible[j2])
 918                 continue;              /* they don't have the same possibles */
 919
 920             v = sc->possible[j1];
 921             /*
 922              * See if v contains exactly two set bits.
 923              */
 924             v2 = v & -v;           /* find lowest set bit */
 925             v2 = v & ~v2;          /* clear it */
 926             if (v2 == 0 || (v2 & (v2-1)) != 0)   /* not power of 2 */
 927                 continue;
 928
 929             /*
 930              * We've found regions j1 and j2 satisfying properties
 931              * (a) and (b): they have two possible colours between
 932              * them, and since they're adjacent to one another they
 933              * must use _both_ those colours between them.
 934              * Therefore, if they are both adjacent to any other
 935              * region then that region cannot be either colour.
 936              *
 937              * Go through the neighbours of j1 and see if any are
 938              * shared with j2.
 939              */
 940             for (j = graph_vertex_start(graph, n, ngraph, j1);
 941                  j < ngraph && graph[j] < n*(j1+1); j++) {
 942                 k = graph[j] - j1*n;
 943                 if (graph_adjacent(graph, n, ngraph, k, j2) &&
 944                     (sc->possible[k] & v)) {
 945                     sc->possible[k] &= ~v;
 946                     done_something = TRUE;
 947                 }
 948             }
 949         }
 950
 951         if (!done_something)
 952             break;
 953     }
 954
 955     /*
 956      * We've run out of things to deduce. See if we've got the lot.
 957      */
 958     for (i = 0; i < n; i++)
 959         if (colouring[i] < 0)
 960             return 2;
 961
 962     return 1;                          /* success! */
 963 }
 964
 965 /* ----------------------------------------------------------------------
 966  * Game generation main function.
 967  */
 968
 969 static char *new_game_desc(game_params *params, random_state *rs,
 970                            char **aux, int interactive)
 971 {
 972     struct solver_scratch *sc = NULL;
 973     int *map, *graph, ngraph, *colouring, *colouring2, *regions;
 974     int i, j, w, h, n, solveret, cfreq[FOUR];
 975     int wh;
 976     int mindiff, tries;
 977 #ifdef GENERATION_DIAGNOSTICS
 978     int x, y;
 979 #endif
 980     char *ret, buf[80];
 981     int retlen, retsize;
 982
 983     w = params->w;
 984     h = params->h;
 985     n = params->n;
 986     wh = w*h;
 987
 988     *aux = NULL;
 989
 990     map = snewn(wh, int);
 991     graph = snewn(n*n, int);
 992     colouring = snewn(n, int);
 993     colouring2 = snewn(n, int);
 994     regions = snewn(n, int);
 995
 996     /*
 997      * This is the minimum difficulty below which we'll completely
 998      * reject a map design. Normally we set this to one below the
 999      * requested difficulty, ensuring that we have the right
1000      * result. However, for particularly dense maps or maps with
1001      * particularly few regions it might not be possible to get the
1002      * desired difficulty, so we will eventually drop this down to
1003      * -1 to indicate that any old map will do.
1004      */
1005     mindiff = params->diff;
1006     tries = 50;
1007
1008     while (1) {
1009
1010         /*
1011          * Create the map.
1012          */
1013         genmap(w, h, n, map, rs);
1014
1015 #ifdef GENERATION_DIAGNOSTICS
1016         for (y = 0; y < h; y++) {
1017             for (x = 0; x < w; x++) {
1018                 int v = map[y*w+x];
1019                 if (v >= 62)
1020                     putchar('!');
1021                 else if (v >= 36)
1022                     putchar('a' + v-36);
1023                 else if (v >= 10)
1024                     putchar('A' + v-10);
1025                 else
1026                     putchar('0' + v);
1027             }
1028             putchar('\n');
1029         }
1030 #endif
1031
1032         /*
1033          * Convert the map into a graph.
1034          */
1035         ngraph = gengraph(w, h, n, map, graph);
1036
1037 #ifdef GENERATION_DIAGNOSTICS
1038         for (i = 0; i < ngraph; i++)
1039             printf("%d-%d\n", graph[i]/n, graph[i]%n);
1040 #endif
1041
1042         /*
1043          * Colour the map.
1044          */
1045         fourcolour(graph, n, ngraph, colouring, rs);
1046
1047 #ifdef GENERATION_DIAGNOSTICS
1048         for (i = 0; i < n; i++)
1049             printf("%d: %d\n", i, colouring[i]);
1050
1051         for (y = 0; y < h; y++) {
1052             for (x = 0; x < w; x++) {
1053                 int v = colouring[map[y*w+x]];
1054                 if (v >= 36)
1055                     putchar('a' + v-36);
1056                 else if (v >= 10)
1057                     putchar('A' + v-10);
1058                 else
1059                     putchar('0' + v);
1060             }
1061             putchar('\n');
1062         }
1063 #endif
1064
1065         /*
1066          * Encode the solution as an aux string.
1067          */
1068         if (*aux)                      /* in case we've come round again */
1069             sfree(*aux);
1070         retlen = retsize = 0;
1071         ret = NULL;
1072         for (i = 0; i < n; i++) {
1073             int len;
1074
1075             if (colouring[i] < 0)
1076                 continue;
1077
1078             len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i);
1079             if (retlen + len >= retsize) {
1080                 retsize = retlen + len + 256;
1081                 ret = sresize(ret, retsize, char);
1082             }
1083             strcpy(ret + retlen, buf);
1084             retlen += len;
1085         }
1086         *aux = ret;
1087
1088         /*
1089          * Remove the region colours one by one, keeping
1090          * solubility. Also ensure that there always remains at
1091          * least one region of every colour, so that the user can
1092          * drag from somewhere.
1093          */
1094         for (i = 0; i < FOUR; i++)
1095             cfreq[i] = 0;
1096         for (i = 0; i < n; i++) {
1097             regions[i] = i;
1098             cfreq[colouring[i]]++;
1099         }
1100         for (i = 0; i < FOUR; i++)
1101             if (cfreq[i] == 0)
1102                 continue;
1103
1104         shuffle(regions, n, sizeof(*regions), rs);
1105
1106         if (sc) free_scratch(sc);
1107         sc = new_scratch(graph, n, ngraph);
1108
1109         for (i = 0; i < n; i++) {
1110             j = regions[i];
1111
1112             if (cfreq[colouring[j]] == 1)
1113                 continue;              /* can't remove last region of colour */
1114
1115             memcpy(colouring2, colouring, n*sizeof(int));
1116             colouring2[j] = -1;
1117             solveret = map_solver(sc, graph, n, ngraph, colouring2,
1118                                   params->diff);
1119             assert(solveret >= 0);             /* mustn't be impossible! */
1120             if (solveret == 1) {
1121                 cfreq[colouring[j]]--;
1122                 colouring[j] = -1;
1123             }
1124         }
1125
1126 #ifdef GENERATION_DIAGNOSTICS
1127         for (i = 0; i < n; i++)
1128             if (colouring[i] >= 0) {
1129                 if (i >= 62)
1130                     putchar('!');
1131                 else if (i >= 36)
1132                     putchar('a' + i-36);
1133                 else if (i >= 10)
1134                     putchar('A' + i-10);
1135                 else
1136                     putchar('0' + i);
1137                 printf(": %d\n", colouring[i]);
1138             }
1139 #endif
1140
1141         /*
1142          * Finally, check that the puzzle is _at least_ as hard as
1143          * required, and indeed that it isn't already solved.
1144          * (Calling map_solver with negative difficulty ensures the
1145          * latter - if a solver which _does nothing_ can't solve
1146          * it, it's too easy!)
1147          */
1148         memcpy(colouring2, colouring, n*sizeof(int));
1149         if (map_solver(sc, graph, n, ngraph, colouring2,
1150                        mindiff - 1) == 1) {
1151             /*
1152              * Drop minimum difficulty if necessary.
1153              */
1154             if (mindiff > 0 && (n < 9 || n > 3*wh/2)) {
1155                 if (tries-- <= 0)
1156                     mindiff = 0;       /* give up and go for Easy */
1157             }
1158             continue;
1159         }
1160
1161         break;
1162     }
1163
1164     /*
1165      * Encode as a game ID. We do this by:
1166      *
1167      *  - first going along the horizontal edges row by row, and
1168      *    then the vertical edges column by column
1169      *  - encoding the lengths of runs of edges and runs of
1170      *    non-edges
1171      *  - the decoder will reconstitute the region boundaries from
1172      *    this and automatically number them the same way we did
1173      *  - then we encode the initial region colours in a Slant-like
1174      *    fashion (digits 0-3 interspersed with letters giving
1175      *    lengths of runs of empty spaces).
1176      */
1177     retlen = retsize = 0;
1178     ret = NULL;
1179
1180     {
1181         int run, pv;
1182
1183         /*
1184          * Start with a notional non-edge, so that there'll be an
1185          * explicit `a' to distinguish the case where we start with
1186          * an edge.
1187          */
1188         run = 1;
1189         pv = 0;
1190
1191         for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
1192             int x, y, dx, dy, v;
1193
1194             if (i < w*(h-1)) {
1195                 /* Horizontal edge. */
1196                 y = i / w;
1197                 x = i % w;
1198                 dx = 0;
1199                 dy = 1;
1200             } else {
1201                 /* Vertical edge. */
1202                 x = (i - w*(h-1)) / h;
1203                 y = (i - w*(h-1)) % h;
1204                 dx = 1;
1205                 dy = 0;
1206             }
1207
1208             if (retlen + 10 >= retsize) {
1209                 retsize = retlen + 256;
1210                 ret = sresize(ret, retsize, char);
1211             }
1212
1213             v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);
1214
1215             if (pv != v) {
1216                 ret[retlen++] = 'a'-1 + run;
1217                 run = 1;
1218                 pv = v;
1219             } else {
1220                 /*
1221                  * 'z' is a special case in this encoding. Rather
1222                  * than meaning a run of 26 and a state switch, it
1223                  * means a run of 25 and _no_ state switch, because
1224                  * otherwise there'd be no way to encode runs of
1225                  * more than 26.
1226                  */
1227                 if (run == 25) {
1228                     ret[retlen++] = 'z';
1229                     run = 0;
1230                 }
1231                 run++;
1232             }
1233         }
1234
1235         ret[retlen++] = 'a'-1 + run;
1236         ret[retlen++] = ',';
1237
1238         run = 0;
1239         for (i = 0; i < n; i++) {
1240             if (retlen + 10 >= retsize) {
1241                 retsize = retlen + 256;
1242                 ret = sresize(ret, retsize, char);
1243             }
1244
1245             if (colouring[i] < 0) {
1246                 /*
1247                  * In _this_ encoding, 'z' is a run of 26, since
1248                  * there's no implicit state switch after each run.
1249                  * Confusingly different, but more compact.
1250                  */
1251                 if (run == 26) {
1252                     ret[retlen++] = 'z';
1253                     run = 0;
1254                 }
1255                 run++;
1256             } else {
1257                 if (run > 0)
1258                     ret[retlen++] = 'a'-1 + run;
1259                 ret[retlen++] = '0' + colouring[i];
1260                 run = 0;
1261             }
1262         }
1263         if (run > 0)
1264             ret[retlen++] = 'a'-1 + run;
1265         ret[retlen] = '\0';
1266
1267         assert(retlen < retsize);
1268     }
1269
1270     free_scratch(sc);
1271     sfree(regions);
1272     sfree(colouring2);
1273     sfree(colouring);
1274     sfree(graph);
1275     sfree(map);
1276
1277     return ret;
1278 }
1279
1280 static char *parse_edge_list(game_params *params, char **desc, int *map)
1281 {
1282     int w = params->w, h = params->h, wh = w*h, n = params->n;
1283     int i, k, pos, state;
1284     char *p = *desc;
1285
1286     for (i = 0; i < wh; i++)
1287         map[wh+i] = i;
1288
1289     pos = -1;
1290     state = 0;
1291
1292     /*
1293      * Parse the game description to get the list of edges, and
1294      * build up a disjoint set forest as we go (by identifying
1295      * pairs of squares whenever the edge list shows a non-edge).
1296      */
1297     while (*p && *p != ',') {
1298         if (*p < 'a' || *p > 'z')
1299             return "Unexpected character in edge list";
1300         if (*p == 'z')
1301             k = 25;
1302         else
1303             k = *p - 'a' + 1;
1304         while (k-- > 0) {
1305             int x, y, dx, dy;
1306
1307             if (pos < 0) {
1308                 pos++;
1309                 continue;
1310             } else if (pos < w*(h-1)) {
1311                 /* Horizontal edge. */
1312                 y = pos / w;
1313                 x = pos % w;
1314                 dx = 0;
1315                 dy = 1;
1316             } else if (pos < 2*wh-w-h) {
1317                 /* Vertical edge. */
1318                 x = (pos - w*(h-1)) / h;
1319                 y = (pos - w*(h-1)) % h;
1320                 dx = 1;
1321                 dy = 0;
1322             } else
1323                 return "Too much data in edge list";
1324             if (!state)
1325                 dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));
1326
1327             pos++;
1328         }
1329         if (*p != 'z')
1330             state = !state;
1331         p++;
1332     }
1333     assert(pos <= 2*wh-w-h);
1334     if (pos < 2*wh-w-h)
1335         return "Too little data in edge list";
1336
1337     /*
1338      * Now go through again and allocate region numbers.
1339      */
1340     pos = 0;
1341     for (i = 0; i < wh; i++)
1342         map[i] = -1;
1343     for (i = 0; i < wh; i++) {
1344         k = dsf_canonify(map+wh, i);
1345         if (map[k] < 0)
1346             map[k] = pos++;
1347         map[i] = map[k];
1348     }
1349     if (pos != n)
1350         return "Edge list defines the wrong number of regions";
1351
1352     *desc = p;
1353
1354     return NULL;
1355 }
1356
1357 static char *validate_desc(game_params *params, char *desc)
1358 {
1359     int w = params->w, h = params->h, wh = w*h, n = params->n;
1360     int area;
1361     int *map;
1362     char *ret;
1363
1364     map = snewn(2*wh, int);
1365     ret = parse_edge_list(params, &desc, map);
1366     if (ret)
1367         return ret;
1368     sfree(map);
1369
1370     if (*desc != ',')
1371         return "Expected comma before clue list";
1372     desc++;                            /* eat comma */
1373
1374     area = 0;
1375     while (*desc) {
1376         if (*desc >= '0' && *desc < '0'+FOUR)
1377             area++;
1378         else if (*desc >= 'a' && *desc <= 'z')
1379             area += *desc - 'a' + 1;
1380         else
1381             return "Unexpected character in clue list";
1382         desc++;
1383     }
1384     if (area < n)
1385         return "Too little data in clue list";
1386     else if (area > n)
1387         return "Too much data in clue list";
1388
1389     return NULL;
1390 }
1391
1392 static game_state *new_game(midend *me, game_params *params, char *desc)
1393 {
1394     int w = params->w, h = params->h, wh = w*h, n = params->n;
1395     int i, pos;
1396     char *p;
1397     game_state *state = snew(game_state);
1398
1399     state->p = *params;
1400     state->colouring = snewn(n, int);
1401     for (i = 0; i < n; i++)
1402         state->colouring[i] = -1;
1403
1404     state->completed = state->cheated = FALSE;
1405
1406     state->map = snew(struct map);
1407     state->map->refcount = 1;
1408     state->map->map = snewn(wh*4, int);
1409     state->map->graph = snewn(n*n, int);
1410     state->map->n = n;
1411     state->map->immutable = snewn(n, int);
1412     for (i = 0; i < n; i++)
1413         state->map->immutable[i] = FALSE;
1414
1415     p = desc;
1416
1417     {
1418         char *ret;
1419         ret = parse_edge_list(params, &p, state->map->map);
1420         assert(!ret);
1421     }
1422
1423     /*
1424      * Set up the other three quadrants in `map'.
1425      */
1426     for (i = wh; i < 4*wh; i++)
1427         state->map->map[i] = state->map->map[i % wh];
1428
1429     assert(*p == ',');
1430     p++;
1431
1432     /*
1433      * Now process the clue list.
1434      */
1435     pos = 0;
1436     while (*p) {
1437         if (*p >= '0' && *p < '0'+FOUR) {
1438             state->colouring[pos] = *p - '0';
1439             state->map->immutable[pos] = TRUE;
1440             pos++;
1441         } else {
1442             assert(*p >= 'a' && *p <= 'z');
1443             pos += *p - 'a' + 1;
1444         }
1445         p++;
1446     }
1447     assert(pos == n);
1448
1449     state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);
1450
1451     /*
1452      * Attempt to smooth out some of the more jagged region
1453      * outlines by the judicious use of diagonally divided squares.
1454      */
1455     {
1456         random_state *rs = random_init(desc, strlen(desc));
1457         int *squares = snewn(wh, int);
1458         int done_something;
1459
1460         for (i = 0; i < wh; i++)
1461             squares[i] = i;
1462         shuffle(squares, wh, sizeof(*squares), rs);
1463
1464         do {
1465             done_something = FALSE;
1466             for (i = 0; i < wh; i++) {
1467                 int y = squares[i] / w, x = squares[i] % w;
1468                 int c = state->map->map[y*w+x];
1469                 int tc, bc, lc, rc;
1470
1471                 if (x == 0 || x == w-1 || y == 0 || y == h-1)
1472                     continue;
1473
1474                 if (state->map->map[TE * wh + y*w+x] !=
1475                     state->map->map[BE * wh + y*w+x])
1476                     continue;
1477
1478                 tc = state->map->map[BE * wh + (y-1)*w+x];
1479                 bc = state->map->map[TE * wh + (y+1)*w+x];
1480                 lc = state->map->map[RE * wh + y*w+(x-1)];
1481                 rc = state->map->map[LE * wh + y*w+(x+1)];
1482
1483                 /*
1484                  * If this square is adjacent on two sides to one
1485                  * region and on the other two sides to the other
1486                  * region, and is itself one of the two regions, we can
1487                  * adjust it so that it's a diagonal.
1488                  */
1489                 if (tc != bc && (tc == c || bc == c)) {
1490                     if ((lc == tc && rc == bc) ||
1491                         (lc == bc && rc == tc)) {
1492                         state->map->map[TE * wh + y*w+x] = tc;
1493                         state->map->map[BE * wh + y*w+x] = bc;
1494                         state->map->map[LE * wh + y*w+x] = lc;
1495                         state->map->map[RE * wh + y*w+x] = rc;
1496                         done_something = TRUE;
1497                     }
1498                 }
1499             }
1500         } while (done_something);
1501         sfree(squares);
1502         random_free(rs);
1503     }
1504
1505     return state;
1506 }
1507
1508 static game_state *dup_game(game_state *state)
1509 {
1510     game_state *ret = snew(game_state);
1511
1512     ret->p = state->p;
1513     ret->colouring = snewn(state->p.n, int);
1514     memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
1515     ret->map = state->map;
1516     ret->map->refcount++;
1517     ret->completed = state->completed;
1518     ret->cheated = state->cheated;
1519
1520     return ret;
1521 }
1522
1523 static void free_game(game_state *state)
1524 {
1525     if (--state->map->refcount <= 0) {
1526         sfree(state->map->map);
1527         sfree(state->map->graph);
1528         sfree(state->map->immutable);
1529         sfree(state->map);
1530     }
1531     sfree(state->colouring);
1532     sfree(state);
1533 }
1534
1535 static char *solve_game(game_state *state, game_state *currstate,
1536                         char *aux, char **error)
1537 {
1538     if (!aux) {
1539         /*
1540          * Use the solver.
1541          */
1542         int *colouring;
1543         struct solver_scratch *sc;
1544         int sret;
1545         int i;
1546         char *ret, buf[80];
1547         int retlen, retsize;
1548
1549         colouring = snewn(state->map->n, int);
1550         memcpy(colouring, state->colouring, state->map->n * sizeof(int));
1551
1552         sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
1553         sret = map_solver(sc, state->map->graph, state->map->n,
1554                          state->map->ngraph, colouring, DIFFCOUNT-1);
1555         free_scratch(sc);
1556
1557         if (sret != 1) {
1558             sfree(colouring);
1559             if (sret == 0)
1560                 *error = "Puzzle is inconsistent";
1561             else
1562                 *error = "Unable to find a unique solution for this puzzle";
1563             return NULL;
1564         }
1565
1566         retlen = retsize = 0;
1567         ret = NULL;
1568
1569         for (i = 0; i < state->map->n; i++) {
1570             int len;
1571
1572             assert(colouring[i] >= 0);
1573             if (colouring[i] == currstate->colouring[i])
1574                 continue;
1575             assert(!state->map->immutable[i]);
1576
1577             len = sprintf(buf, "%s%d:%d", retlen ? ";" : "S;",
1578                           colouring[i], i);
1579             if (retlen + len >= retsize) {
1580                 retsize = retlen + len + 256;
1581                 ret = sresize(ret, retsize, char);
1582             }
1583             strcpy(ret + retlen, buf);
1584             retlen += len;
1585         }
1586
1587         sfree(colouring);
1588
1589         return ret;
1590     }
1591     return dupstr(aux);
1592 }
1593
1594 static char *game_text_format(game_state *state)
1595 {
1596     return NULL;
1597 }
1598
1599 struct game_ui {
1600     int drag_colour;                   /* -1 means no drag active */
1601     int dragx, dragy;
1602 };
1603
1604 static game_ui *new_ui(game_state *state)
1605 {
1606     game_ui *ui = snew(game_ui);
1607     ui->dragx = ui->dragy = -1;
1608     ui->drag_colour = -2;
1609     return ui;
1610 }
1611
1612 static void free_ui(game_ui *ui)
1613 {
1614     sfree(ui);
1615 }
1616
1617 static char *encode_ui(game_ui *ui)
1618 {
1619     return NULL;
1620 }
1621
1622 static void decode_ui(game_ui *ui, char *encoding)
1623 {
1624 }
1625
1626 static void game_changed_state(game_ui *ui, game_state *oldstate,
1627                                game_state *newstate)
1628 {
1629 }
1630
1631 struct game_drawstate {
1632     int tilesize;
1633     unsigned char *drawn;
1634     int started;
1635     int dragx, dragy, drag_visible;
1636     blitter *bl;
1637 };
1638
1639 #define TILESIZE (ds->tilesize)
1640 #define BORDER (TILESIZE)
1641 #define COORD(x)  ( (x) * TILESIZE + BORDER )
1642 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1643
1644 static int region_from_coords(game_state *state, game_drawstate *ds,
1645                               int x, int y)
1646 {
1647     int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
1648     int tx = FROMCOORD(x), ty = FROMCOORD(y);
1649     int dx = x - COORD(tx), dy = y - COORD(ty);
1650     int quadrant;
1651
1652     if (tx < 0 || tx >= w || ty < 0 || ty >= h)
1653         return -1;                     /* border */
1654
1655     quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
1656     quadrant = (quadrant == 0 ? BE :
1657                 quadrant == 1 ? LE :
1658                 quadrant == 2 ? RE : TE);
1659
1660     return state->map->map[quadrant * wh + ty*w+tx];
1661 }
1662
1663 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1664                             int x, int y, int button)
1665 {
1666     char buf[80];
1667
1668     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1669         int r = region_from_coords(state, ds, x, y);
1670
1671         if (r >= 0)
1672             ui->drag_colour = state->colouring[r];
1673         else
1674             ui->drag_colour = -1;
1675         ui->dragx = x;
1676         ui->dragy = y;
1677         return "";
1678     }
1679
1680     if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
1681         ui->drag_colour > -2) {
1682         ui->dragx = x;
1683         ui->dragy = y;
1684         return "";
1685     }
1686
1687     if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
1688         ui->drag_colour > -2) {
1689         int r = region_from_coords(state, ds, x, y);
1690         int c = ui->drag_colour;
1691
1692         /*
1693          * Cancel the drag, whatever happens.
1694          */
1695         ui->drag_colour = -2;
1696         ui->dragx = ui->dragy = -1;
1697
1698         if (r < 0)
1699             return "";                 /* drag into border; do nothing else */
1700
1701         if (state->map->immutable[r])
1702             return "";                 /* can't change this region */
1703
1704         if (state->colouring[r] == c)
1705             return "";                 /* don't _need_ to change this region */
1706
1707         sprintf(buf, "%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
1708         return dupstr(buf);
1709     }
1710
1711     return NULL;
1712 }
1713
1714 static game_state *execute_move(game_state *state, char *move)
1715 {
1716     int n = state->p.n;
1717     game_state *ret = dup_game(state);
1718     int c, k, adv, i;
1719
1720     while (*move) {
1721         c = *move;
1722         if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
1723             sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
1724             k >= 0 && k < state->p.n) {
1725             move += 1 + adv;
1726             ret->colouring[k] = (c == 'C' ? -1 : c - '0');
1727         } else if (*move == 'S') {
1728             move++;
1729             ret->cheated = TRUE;
1730         } else {
1731             free_game(ret);
1732             return NULL;
1733         }
1734
1735         if (*move && *move != ';') {
1736             free_game(ret);
1737             return NULL;
1738         }
1739         if (*move)
1740             move++;
1741     }
1742
1743     /*
1744      * Check for completion.
1745      */
1746     if (!ret->completed) {
1747         int ok = TRUE;
1748
1749         for (i = 0; i < n; i++)
1750             if (ret->colouring[i] < 0) {
1751                 ok = FALSE;
1752                 break;
1753             }
1754
1755         if (ok) {
1756             for (i = 0; i < ret->map->ngraph; i++) {
1757                 int j = ret->map->graph[i] / n;
1758                 int k = ret->map->graph[i] % n;
1759                 if (ret->colouring[j] == ret->colouring[k]) {
1760                     ok = FALSE;
1761                     break;
1762                 }
1763             }
1764         }
1765
1766         if (ok)
1767             ret->completed = TRUE;
1768     }
1769
1770     return ret;
1771 }
1772
1773 /* ----------------------------------------------------------------------
1774  * Drawing routines.
1775  */
1776
1777 static void game_compute_size(game_params *params, int tilesize,
1778                               int *x, int *y)
1779 {
1780     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1781     struct { int tilesize; } ads, *ds = &ads;
1782     ads.tilesize = tilesize;
1783
1784     *x = params->w * TILESIZE + 2 * BORDER + 1;
1785     *y = params->h * TILESIZE + 2 * BORDER + 1;
1786 }
1787
1788 static void game_set_size(drawing *dr, game_drawstate *ds,
1789                           game_params *params, int tilesize)
1790 {
1791     ds->tilesize = tilesize;
1792
1793     if (ds->bl)
1794         blitter_free(dr, ds->bl);
1795     ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
1796 }
1797
1798 const float map_colours[FOUR][3] = {
1799     {0.7F, 0.5F, 0.4F},
1800     {0.8F, 0.7F, 0.4F},
1801     {0.5F, 0.6F, 0.4F},
1802     {0.55F, 0.45F, 0.35F},
1803 };
1804 const int map_hatching[FOUR] = {
1805     HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
1806 };
1807
1808 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1809 {
1810     float *ret = snewn(3 * NCOLOURS, float);
1811
1812     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1813
1814     ret[COL_GRID * 3 + 0] = 0.0F;
1815     ret[COL_GRID * 3 + 1] = 0.0F;
1816     ret[COL_GRID * 3 + 2] = 0.0F;
1817
1818     memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
1819     memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
1820     memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
1821     memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
1822
1823     *ncolours = NCOLOURS;
1824     return ret;
1825 }
1826
1827 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1828 {
1829     struct game_drawstate *ds = snew(struct game_drawstate);
1830
1831     ds->tilesize = 0;
1832     ds->drawn = snewn(state->p.w * state->p.h, unsigned char);
1833     memset(ds->drawn, 0xFF, state->p.w * state->p.h);
1834     ds->started = FALSE;
1835     ds->bl = NULL;
1836     ds->drag_visible = FALSE;
1837     ds->dragx = ds->dragy = -1;
1838
1839     return ds;
1840 }
1841
1842 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1843 {
1844     sfree(ds->drawn);
1845     if (ds->bl)
1846         blitter_free(dr, ds->bl);
1847     sfree(ds);
1848 }
1849
1850 static void draw_square(drawing *dr, game_drawstate *ds,
1851                         game_params *params, struct map *map,
1852                         int x, int y, int v)
1853 {
1854     int w = params->w, h = params->h, wh = w*h;
1855     int tv = v / FIVE, bv = v % FIVE;
1856
1857     clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1858
1859     /*
1860      * Draw the region colour.
1861      */
1862     draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
1863               (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
1864     /*
1865      * Draw the second region colour, if this is a diagonally
1866      * divided square.
1867      */
1868     if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
1869         int coords[6];
1870         coords[0] = COORD(x)-1;
1871         coords[1] = COORD(y+1)+1;
1872         if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
1873             coords[2] = COORD(x+1)+1;
1874         else
1875             coords[2] = COORD(x)-1;
1876         coords[3] = COORD(y)-1;
1877         coords[4] = COORD(x+1)+1;
1878         coords[5] = COORD(y+1)+1;
1879         draw_polygon(dr, coords, 3,
1880                      (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
1881     }
1882
1883     /*
1884      * Draw the grid lines, if required.
1885      */
1886     if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
1887         draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
1888     if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
1889         draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
1890     if (x <= 0 || y <= 0 ||
1891         map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
1892         map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
1893         draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
1894
1895     unclip(dr);
1896     draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1897 }
1898
1899 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1900                         game_state *state, int dir, game_ui *ui,
1901                         float animtime, float flashtime)
1902 {
1903     int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
1904     int x, y;
1905     int flash;
1906
1907     if (ds->drag_visible) {
1908         blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
1909         draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
1910         ds->drag_visible = FALSE;
1911     }
1912
1913     /*
1914      * The initial contents of the window are not guaranteed and
1915      * can vary with front ends. To be on the safe side, all games
1916      * should start by drawing a big background-colour rectangle
1917      * covering the whole window.
1918      */
1919     if (!ds->started) {
1920         int ww, wh;
1921
1922         game_compute_size(&state->p, TILESIZE, &ww, &wh);
1923         draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
1924         draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
1925                   COL_GRID);
1926
1927         draw_update(dr, 0, 0, ww, wh);
1928         ds->started = TRUE;
1929     }
1930
1931     if (flashtime) {
1932         if (flash_type == 1)
1933             flash = (int)(flashtime * FOUR / flash_length);
1934         else
1935             flash = 1 + (int)(flashtime * THREE / flash_length);
1936     } else
1937         flash = -1;
1938
1939     for (y = 0; y < h; y++)
1940         for (x = 0; x < w; x++) {
1941             int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
1942             int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
1943             int v;
1944
1945             if (tv < 0)
1946                 tv = FOUR;
1947             if (bv < 0)
1948                 bv = FOUR;
1949
1950             if (flash >= 0) {
1951                 if (flash_type == 1) {
1952                     if (tv == flash)
1953                         tv = FOUR;
1954                     if (bv == flash)
1955                         bv = FOUR;
1956                 } else if (flash_type == 2) {
1957                     if (flash % 2)
1958                         tv = bv = FOUR;
1959                 } else {
1960                     if (tv != FOUR)
1961                         tv = (tv + flash) % FOUR;
1962                     if (bv != FOUR)
1963                         bv = (bv + flash) % FOUR;
1964                 }
1965             }
1966
1967             v = tv * FIVE + bv;
1968
1969             if (ds->drawn[y*w+x] != v) {
1970                 draw_square(dr, ds, &state->p, state->map, x, y, v);
1971                 ds->drawn[y*w+x] = v;
1972             }
1973         }
1974
1975     /*
1976      * Draw the dragged colour blob if any.
1977      */
1978     if (ui->drag_colour > -2) {
1979         ds->dragx = ui->dragx - TILESIZE/2 - 2;
1980         ds->dragy = ui->dragy - TILESIZE/2 - 2;
1981         blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
1982         draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2,
1983                     (ui->drag_colour < 0 ? COL_BACKGROUND :
1984                      COL_0 + ui->drag_colour), COL_GRID);
1985         draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
1986         ds->drag_visible = TRUE;
1987     }
1988 }
1989
1990 static float game_anim_length(game_state *oldstate, game_state *newstate,
1991                               int dir, game_ui *ui)
1992 {
1993     return 0.0F;
1994 }
1995
1996 static float game_flash_length(game_state *oldstate, game_state *newstate,
1997                                int dir, game_ui *ui)
1998 {
1999     if (!oldstate->completed && newstate->completed &&
2000         !oldstate->cheated && !newstate->cheated) {
2001         if (flash_type < 0) {
2002             char *env = getenv("MAP_ALTERNATIVE_FLASH");
2003             if (env)
2004                 flash_type = atoi(env);
2005             else
2006                 flash_type = 0;
2007             flash_length = (flash_type == 1 ? 0.50 : 0.30);
2008         }
2009         return flash_length;
2010     } else
2011         return 0.0F;
2012 }
2013
2014 static int game_wants_statusbar(void)
2015 {
2016     return FALSE;
2017 }
2018
2019 static int game_timing_state(game_state *state, game_ui *ui)
2020 {
2021     return TRUE;
2022 }
2023
2024 static void game_print_size(game_params *params, float *x, float *y)
2025 {
2026     int pw, ph;
2027
2028     /*
2029      * I'll use 4mm squares by default, I think. Simplest way to
2030      * compute this size is to compute the pixel puzzle size at a
2031      * given tile size and then scale.
2032      */
2033     game_compute_size(params, 400, &pw, &ph);
2034     *x = pw / 100.0;
2035     *y = ph / 100.0;
2036 }
2037
2038 static void game_print(drawing *dr, game_state *state, int tilesize)
2039 {
2040     int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2041     int ink, c[FOUR], i;
2042     int x, y, r;
2043     int *coords, ncoords, coordsize;
2044
2045     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2046     struct { int tilesize; } ads, *ds = &ads;
2047     ads.tilesize = tilesize;
2048
2049     ink = print_mono_colour(dr, 0);
2050     for (i = 0; i < FOUR; i++)
2051         c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0],
2052                                 map_colours[i][1], map_colours[i][2]);
2053
2054     coordsize = 0;
2055     coords = NULL;
2056
2057     print_line_width(dr, TILESIZE / 16);
2058
2059     /*
2060      * Draw a single filled polygon around each region.
2061      */
2062     for (r = 0; r < n; r++) {
2063         int octants[8], lastdir, d1, d2, ox, oy;
2064
2065         /*
2066          * Start by finding a point on the region boundary. Any
2067          * point will do. To do this, we'll search for a square
2068          * containing the region and then decide which corner of it
2069          * to use.
2070          */
2071         x = w;
2072         for (y = 0; y < h; y++) {
2073             for (x = 0; x < w; x++) {
2074                 if (state->map->map[wh*0+y*w+x] == r ||
2075                     state->map->map[wh*1+y*w+x] == r ||
2076                     state->map->map[wh*2+y*w+x] == r ||
2077                     state->map->map[wh*3+y*w+x] == r)
2078                     break;
2079             }
2080             if (x < w)
2081                 break;
2082         }
2083         assert(y < h && x < w);        /* we must have found one somewhere */
2084         /*
2085          * This is the first square in lexicographic order which
2086          * contains part of this region. Therefore, one of the top
2087          * two corners of the square must be what we're after. The
2088          * only case in which it isn't the top left one is if the
2089          * square is diagonally divided and the region is in the
2090          * bottom right half.
2091          */
2092         if (state->map->map[wh*TE+y*w+x] != r &&
2093             state->map->map[wh*LE+y*w+x] != r)
2094             x++;                       /* could just as well have done y++ */
2095
2096         /*
2097          * Now we have a point on the region boundary. Trace around
2098          * the region until we come back to this point,
2099          * accumulating coordinates for a polygon draw operation as
2100          * we go.
2101          */
2102         lastdir = -1;
2103         ox = x;
2104         oy = y;
2105         ncoords = 0;
2106
2107         do {
2108             /*
2109              * There are eight possible directions we could head in
2110              * from here. We identify them by octant numbers, and
2111              * we also use octant numbers to identify the spaces
2112              * between them:
2113              *
2114              *   6   7   0
2115              *    \ 7|0 /
2116              *     \ | /
2117              *    6 \|/ 1
2118              * 5-----+-----1
2119              *    5 /|\ 2
2120              *     / | \
2121              *    / 4|3 \
2122              *   4   3   2
2123              */
2124             octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
2125             octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
2126             octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
2127             octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
2128             octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
2129             octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
2130             octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
2131             octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
2132
2133             d1 = d2 = -1;
2134             for (i = 0; i < 8; i++)
2135                 if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
2136                     assert(d2 == -1);
2137                     if (d1 == -1)
2138                         d1 = i;
2139                     else
2140                         d2 = i;
2141                 }
2142 /* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */
2143             assert(d1 != -1 && d2 != -1);
2144             if (d1 == lastdir)
2145                 d1 = d2;
2146
2147             /*
2148              * Now we're heading in direction d1. Save the current
2149              * coordinates.
2150              */
2151             if (ncoords + 2 > coordsize) {
2152                 coordsize += 128;
2153                 coords = sresize(coords, coordsize, int);
2154             }
2155             coords[ncoords++] = COORD(x);
2156             coords[ncoords++] = COORD(y);
2157
2158             /*
2159              * Compute the new coordinates.
2160              */
2161             x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
2162             y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
2163             assert(x >= 0 && x <= w && y >= 0 && y <= h);
2164
2165             lastdir = d1 ^ 4;
2166         } while (x != ox || y != oy);
2167
2168         draw_polygon(dr, coords, ncoords/2,
2169                      state->colouring[r] >= 0 ?
2170                      c[state->colouring[r]] : -1, ink);
2171     }
2172     sfree(coords);
2173 }
2174
2175 #ifdef COMBINED
2176 #define thegame map
2177 #endif
2178
2179 const struct game thegame = {
2180     "Map", "games.map",
2181     default_params,
2182     game_fetch_preset,
2183     decode_params,
2184     encode_params,
2185     free_params,
2186     dup_params,
2187     TRUE, game_configure, custom_params,
2188     validate_params,
2189     new_game_desc,
2190     validate_desc,
2191     new_game,
2192     dup_game,
2193     free_game,
2194     TRUE, solve_game,
2195     FALSE, game_text_format,
2196     new_ui,
2197     free_ui,
2198     encode_ui,
2199     decode_ui,
2200     game_changed_state,
2201     interpret_move,
2202     execute_move,
2203     20, game_compute_size, game_set_size,
2204     game_colours,
2205     game_new_drawstate,
2206     game_free_drawstate,
2207     game_redraw,
2208     game_anim_length,
2209     game_flash_length,
2210     TRUE, TRUE, game_print_size, game_print,
2211     game_wants_statusbar,
2212     FALSE, game_timing_state,
2213     0,                                 /* mouse_priorities */
2214 };