map.c

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