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