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[3], ey[3], ea[3], eb[3], 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.
1649                      */
1650                     if (x+1 < w) {
1651                         /* right edge */
1652                         ea[en] = state->map->map[RE * wh + y*w+x];
1653                         eb[en] = state->map->map[LE * wh + y*w+(x+1)];
1654                         if (ea[en] != eb[en]) {
1655                             ex[en] = (x+1)*2;
1656                             ey[en] = y*2+1;
1657                             en++;
1658                         }
1659                     }
1660                     if (y+1 < h) {
1661                         /* bottom edge */
1662                         ea[en] = state->map->map[BE * wh + y*w+x];
1663                         eb[en] = state->map->map[TE * wh + (y+1)*w+x];
1664                         if (ea[en] != eb[en]) {
1665                             ex[en] = x*2+1;
1666                             ey[en] = (y+1)*2;
1667                             en++;
1668                         }
1669                     }
1670                     /* diagonal edge */
1671                     ea[en] = state->map->map[TE * wh + y*w+x];
1672                     eb[en] = state->map->map[BE * wh + y*w+x];
1673                     if (ea[en] != eb[en]) {
1674                         ex[en] = x*2+1;
1675                         ey[en] = y*2+1;
1676                         en++;
1677                     }
1678
1679                     /*
1680                      * Now process the edges we've found, one by
1681                      * one.
1682                      */
1683                     for (i = 0; i < en; i++) {
1684                         int emin = min(ea[i], eb[i]);
1685                         int emax = max(ea[i], eb[i]);
1686                         int gindex =
1687                             graph_edge_index(state->map->graph, n,
1688                                              state->map->ngraph, emin, emax);
1689
1690                         assert(gindex >= 0);
1691
1692                         if (pass == 0) {
1693                             /*
1694                              * In pass 0, accumulate the values
1695                              * we'll use to compute the average
1696                              * positions.
1697                              */
1698                             ax[gindex] += ex[i];
1699                             ay[gindex] += ey[i];
1700                             an[gindex] += 1.0F;
1701                         } else {
1702                             /*
1703                              * In pass 1, work out whether this
1704                              * point is closer to the average than
1705                              * the last one we've seen.
1706                              */
1707                             float dx, dy, d;
1708
1709                             assert(an[gindex] > 0);
1710                             dx = ex[i] - ax[gindex];
1711                             dy = ey[i] - ay[gindex];
1712                             d = sqrt(dx*dx + dy*dy);
1713                             if (d < best[gindex]) {
1714                                 best[gindex] = d;
1715                                 bestx[gindex] = ex[i];
1716                                 besty[gindex] = ey[i];
1717                             }
1718                         }
1719                     }
1720                 }
1721
1722             if (pass == 0) {
1723                 for (i = 0; i < state->map->ngraph; i++)
1724                     if (an[i] > 0) {
1725                         ax[i] /= an[i];
1726                         ay[i] /= an[i];
1727                     }
1728             }
1729         }
1730
1731         state->map->edgex = bestx;
1732         state->map->edgey = besty;
1733
1734         for (i = 0; i < state->map->ngraph; i++)
1735             if (state->map->edgex[i] < 0) {
1736                 /* Find the other representation of this edge. */
1737                 int e = state->map->graph[i];
1738                 int iprime = graph_edge_index(state->map->graph, n,
1739                                               state->map->ngraph, e%n, e/n);
1740                 assert(state->map->edgex[iprime] >= 0);
1741                 state->map->edgex[i] = state->map->edgex[iprime];
1742                 state->map->edgey[i] = state->map->edgey[iprime];
1743             }
1744
1745         sfree(ax);
1746         sfree(ay);
1747         sfree(an);
1748         sfree(best);
1749     }
1750
1751     return state;
1752 }
1753
1754 static game_state *dup_game(game_state *state)
1755 {
1756     game_state *ret = snew(game_state);
1757
1758     ret->p = state->p;
1759     ret->colouring = snewn(state->p.n, int);
1760     memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
1761     ret->map = state->map;
1762     ret->map->refcount++;
1763     ret->completed = state->completed;
1764     ret->cheated = state->cheated;
1765
1766     return ret;
1767 }
1768
1769 static void free_game(game_state *state)
1770 {
1771     if (--state->map->refcount <= 0) {
1772         sfree(state->map->map);
1773         sfree(state->map->graph);
1774         sfree(state->map->immutable);
1775         sfree(state->map->edgex);
1776         sfree(state->map->edgey);
1777         sfree(state->map);
1778     }
1779     sfree(state->colouring);
1780     sfree(state);
1781 }
1782
1783 static char *solve_game(game_state *state, game_state *currstate,
1784                         char *aux, char **error)
1785 {
1786     if (!aux) {
1787         /*
1788          * Use the solver.
1789          */
1790         int *colouring;
1791         struct solver_scratch *sc;
1792         int sret;
1793         int i;
1794         char *ret, buf[80];
1795         int retlen, retsize;
1796
1797         colouring = snewn(state->map->n, int);
1798         memcpy(colouring, state->colouring, state->map->n * sizeof(int));
1799
1800         sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
1801         sret = map_solver(sc, state->map->graph, state->map->n,
1802                          state->map->ngraph, colouring, DIFFCOUNT-1);
1803         free_scratch(sc);
1804
1805         if (sret != 1) {
1806             sfree(colouring);
1807             if (sret == 0)
1808                 *error = "Puzzle is inconsistent";
1809             else
1810                 *error = "Unable to find a unique solution for this puzzle";
1811             return NULL;
1812         }
1813
1814         retsize = 64;
1815         ret = snewn(retsize, char);
1816         strcpy(ret, "S");
1817         retlen = 1;
1818
1819         for (i = 0; i < state->map->n; i++) {
1820             int len;
1821
1822             assert(colouring[i] >= 0);
1823             if (colouring[i] == currstate->colouring[i])
1824                 continue;
1825             assert(!state->map->immutable[i]);
1826
1827             len = sprintf(buf, ";%d:%d", colouring[i], i);
1828             if (retlen + len >= retsize) {
1829                 retsize = retlen + len + 256;
1830                 ret = sresize(ret, retsize, char);
1831             }
1832             strcpy(ret + retlen, buf);
1833             retlen += len;
1834         }
1835
1836         sfree(colouring);
1837
1838         return ret;
1839     }
1840     return dupstr(aux);
1841 }
1842
1843 static char *game_text_format(game_state *state)
1844 {
1845     return NULL;
1846 }
1847
1848 struct game_ui {
1849     int drag_colour;                   /* -1 means no drag active */
1850     int dragx, dragy;
1851 };
1852
1853 static game_ui *new_ui(game_state *state)
1854 {
1855     game_ui *ui = snew(game_ui);
1856     ui->dragx = ui->dragy = -1;
1857     ui->drag_colour = -2;
1858     return ui;
1859 }
1860
1861 static void free_ui(game_ui *ui)
1862 {
1863     sfree(ui);
1864 }
1865
1866 static char *encode_ui(game_ui *ui)
1867 {
1868     return NULL;
1869 }
1870
1871 static void decode_ui(game_ui *ui, char *encoding)
1872 {
1873 }
1874
1875 static void game_changed_state(game_ui *ui, game_state *oldstate,
1876                                game_state *newstate)
1877 {
1878 }
1879
1880 struct game_drawstate {
1881     int tilesize;
1882     unsigned short *drawn, *todraw;
1883     int started;
1884     int dragx, dragy, drag_visible;
1885     blitter *bl;
1886 };
1887
1888 /* Flags in `drawn'. */
1889 #define ERR_T    0x0100
1890 #define ERR_B    0x0200
1891 #define ERR_L    0x0400
1892 #define ERR_R    0x0800
1893 #define ERR_C    0x1000
1894 #define ERR_MASK 0x1F00
1895
1896 #define TILESIZE (ds->tilesize)
1897 #define BORDER (TILESIZE)
1898 #define COORD(x)  ( (x) * TILESIZE + BORDER )
1899 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1900
1901 static int region_from_coords(game_state *state, game_drawstate *ds,
1902                               int x, int y)
1903 {
1904     int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
1905     int tx = FROMCOORD(x), ty = FROMCOORD(y);
1906     int dx = x - COORD(tx), dy = y - COORD(ty);
1907     int quadrant;
1908
1909     if (tx < 0 || tx >= w || ty < 0 || ty >= h)
1910         return -1;                     /* border */
1911
1912     quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
1913     quadrant = (quadrant == 0 ? BE :
1914                 quadrant == 1 ? LE :
1915                 quadrant == 2 ? RE : TE);
1916
1917     return state->map->map[quadrant * wh + ty*w+tx];
1918 }
1919
1920 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1921                             int x, int y, int button)
1922 {
1923     char buf[80];
1924
1925     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1926         int r = region_from_coords(state, ds, x, y);
1927
1928         if (r >= 0)
1929             ui->drag_colour = state->colouring[r];
1930         else
1931             ui->drag_colour = -1;
1932         ui->dragx = x;
1933         ui->dragy = y;
1934         return "";
1935     }
1936
1937     if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
1938         ui->drag_colour > -2) {
1939         ui->dragx = x;
1940         ui->dragy = y;
1941         return "";
1942     }
1943
1944     if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
1945         ui->drag_colour > -2) {
1946         int r = region_from_coords(state, ds, x, y);
1947         int c = ui->drag_colour;
1948
1949         /*
1950          * Cancel the drag, whatever happens.
1951          */
1952         ui->drag_colour = -2;
1953         ui->dragx = ui->dragy = -1;
1954
1955         if (r < 0)
1956             return "";                 /* drag into border; do nothing else */
1957
1958         if (state->map->immutable[r])
1959             return "";                 /* can't change this region */
1960
1961         if (state->colouring[r] == c)
1962             return "";                 /* don't _need_ to change this region */
1963
1964         sprintf(buf, "%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
1965         return dupstr(buf);
1966     }
1967
1968     return NULL;
1969 }
1970
1971 static game_state *execute_move(game_state *state, char *move)
1972 {
1973     int n = state->p.n;
1974     game_state *ret = dup_game(state);
1975     int c, k, adv, i;
1976
1977     while (*move) {
1978         c = *move;
1979         if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
1980             sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
1981             k >= 0 && k < state->p.n) {
1982             move += 1 + adv;
1983             ret->colouring[k] = (c == 'C' ? -1 : c - '0');
1984         } else if (*move == 'S') {
1985             move++;
1986             ret->cheated = TRUE;
1987         } else {
1988             free_game(ret);
1989             return NULL;
1990         }
1991
1992         if (*move && *move != ';') {
1993             free_game(ret);
1994             return NULL;
1995         }
1996         if (*move)
1997             move++;
1998     }
1999
2000     /*
2001      * Check for completion.
2002      */
2003     if (!ret->completed) {
2004         int ok = TRUE;
2005
2006         for (i = 0; i < n; i++)
2007             if (ret->colouring[i] < 0) {
2008                 ok = FALSE;
2009                 break;
2010             }
2011
2012         if (ok) {
2013             for (i = 0; i < ret->map->ngraph; i++) {
2014                 int j = ret->map->graph[i] / n;
2015                 int k = ret->map->graph[i] % n;
2016                 if (ret->colouring[j] == ret->colouring[k]) {
2017                     ok = FALSE;
2018                     break;
2019                 }
2020             }
2021         }
2022
2023         if (ok)
2024             ret->completed = TRUE;
2025     }
2026
2027     return ret;
2028 }
2029
2030 /* ----------------------------------------------------------------------
2031  * Drawing routines.
2032  */
2033
2034 static void game_compute_size(game_params *params, int tilesize,
2035                               int *x, int *y)
2036 {
2037     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2038     struct { int tilesize; } ads, *ds = &ads;
2039     ads.tilesize = tilesize;
2040
2041     *x = params->w * TILESIZE + 2 * BORDER + 1;
2042     *y = params->h * TILESIZE + 2 * BORDER + 1;
2043 }
2044
2045 static void game_set_size(drawing *dr, game_drawstate *ds,
2046                           game_params *params, int tilesize)
2047 {
2048     ds->tilesize = tilesize;
2049
2050     if (ds->bl)
2051         blitter_free(dr, ds->bl);
2052     ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
2053 }
2054
2055 const float map_colours[FOUR][3] = {
2056     {0.7F, 0.5F, 0.4F},
2057     {0.8F, 0.7F, 0.4F},
2058     {0.5F, 0.6F, 0.4F},
2059     {0.55F, 0.45F, 0.35F},
2060 };
2061 const int map_hatching[FOUR] = {
2062     HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
2063 };
2064
2065 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
2066 {
2067     float *ret = snewn(3 * NCOLOURS, float);
2068
2069     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2070
2071     ret[COL_GRID * 3 + 0] = 0.0F;
2072     ret[COL_GRID * 3 + 1] = 0.0F;
2073     ret[COL_GRID * 3 + 2] = 0.0F;
2074
2075     memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
2076     memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
2077     memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
2078     memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
2079
2080     ret[COL_ERROR * 3 + 0] = 1.0F;
2081     ret[COL_ERROR * 3 + 1] = 0.0F;
2082     ret[COL_ERROR * 3 + 2] = 0.0F;
2083
2084     ret[COL_ERRTEXT * 3 + 0] = 1.0F;
2085     ret[COL_ERRTEXT * 3 + 1] = 1.0F;
2086     ret[COL_ERRTEXT * 3 + 2] = 1.0F;
2087
2088     *ncolours = NCOLOURS;
2089     return ret;
2090 }
2091
2092 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
2093 {
2094     struct game_drawstate *ds = snew(struct game_drawstate);
2095     int i;
2096
2097     ds->tilesize = 0;
2098     ds->drawn = snewn(state->p.w * state->p.h, unsigned short);
2099     for (i = 0; i < state->p.w * state->p.h; i++)
2100         ds->drawn[i] = 0xFFFF;
2101     ds->todraw = snewn(state->p.w * state->p.h, unsigned short);
2102     ds->started = FALSE;
2103     ds->bl = NULL;
2104     ds->drag_visible = FALSE;
2105     ds->dragx = ds->dragy = -1;
2106
2107     return ds;
2108 }
2109
2110 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2111 {
2112     sfree(ds->drawn);
2113     sfree(ds->todraw);
2114     if (ds->bl)
2115         blitter_free(dr, ds->bl);
2116     sfree(ds);
2117 }
2118
2119 static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
2120 {
2121     int coords[8];
2122     int yext, xext;
2123
2124     /*
2125      * Draw a diamond.
2126      */
2127     coords[0] = x - TILESIZE*2/5;
2128     coords[1] = y;
2129     coords[2] = x;
2130     coords[3] = y - TILESIZE*2/5;
2131     coords[4] = x + TILESIZE*2/5;
2132     coords[5] = y;
2133     coords[6] = x;
2134     coords[7] = y + TILESIZE*2/5;
2135     draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
2136
2137     /*
2138      * Draw an exclamation mark in the diamond. This turns out to
2139      * look unpleasantly off-centre if done via draw_text, so I do
2140      * it by hand on the basis that exclamation marks aren't that
2141      * difficult to draw...
2142      */
2143     xext = TILESIZE/16;
2144     yext = TILESIZE*2/5 - (xext*2+2);
2145     draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3+1),
2146               COL_ERRTEXT);
2147     draw_rect(dr, x-xext, y+yext-xext*2, xext*2+1, xext*2+1, COL_ERRTEXT);
2148 }
2149
2150 static void draw_square(drawing *dr, game_drawstate *ds,
2151                         game_params *params, struct map *map,
2152                         int x, int y, int v)
2153 {
2154     int w = params->w, h = params->h, wh = w*h;
2155     int tv, bv, errs;
2156
2157     errs = v & ERR_MASK;
2158     v &= ~ERR_MASK;
2159     tv = v / FIVE;
2160     bv = v % FIVE;
2161
2162     clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2163
2164     /*
2165      * Draw the region colour.
2166      */
2167     draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
2168               (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
2169     /*
2170      * Draw the second region colour, if this is a diagonally
2171      * divided square.
2172      */
2173     if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
2174         int coords[6];
2175         coords[0] = COORD(x)-1;
2176         coords[1] = COORD(y+1)+1;
2177         if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
2178             coords[2] = COORD(x+1)+1;
2179         else
2180             coords[2] = COORD(x)-1;
2181         coords[3] = COORD(y)-1;
2182         coords[4] = COORD(x+1)+1;
2183         coords[5] = COORD(y+1)+1;
2184         draw_polygon(dr, coords, 3,
2185                      (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
2186     }
2187
2188     /*
2189      * Draw the grid lines, if required.
2190      */
2191     if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
2192         draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
2193     if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
2194         draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
2195     if (x <= 0 || y <= 0 ||
2196         map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
2197         map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
2198         draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
2199
2200     /*
2201      * Draw error markers.
2202      */
2203     if (errs & ERR_T)
2204         draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y));
2205     if (errs & ERR_L)
2206         draw_error(dr, ds, COORD(x), COORD(y)+TILESIZE/2);
2207     if (errs & ERR_B)
2208         draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y+1));
2209     if (errs & ERR_R)
2210         draw_error(dr, ds, COORD(x+1), COORD(y)+TILESIZE/2);
2211     if (errs & ERR_C)
2212         draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y)+TILESIZE/2);
2213
2214     unclip(dr);
2215
2216     draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2217 }
2218
2219 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2220                         game_state *state, int dir, game_ui *ui,
2221                         float animtime, float flashtime)
2222 {
2223     int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2224     int x, y, i;
2225     int flash;
2226
2227     if (ds->drag_visible) {
2228         blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
2229         draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
2230         ds->drag_visible = FALSE;
2231     }
2232
2233     /*
2234      * The initial contents of the window are not guaranteed and
2235      * can vary with front ends. To be on the safe side, all games
2236      * should start by drawing a big background-colour rectangle
2237      * covering the whole window.
2238      */
2239     if (!ds->started) {
2240         int ww, wh;
2241
2242         game_compute_size(&state->p, TILESIZE, &ww, &wh);
2243         draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
2244         draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
2245                   COL_GRID);
2246
2247         draw_update(dr, 0, 0, ww, wh);
2248         ds->started = TRUE;
2249     }
2250
2251     if (flashtime) {
2252         if (flash_type == 1)
2253             flash = (int)(flashtime * FOUR / flash_length);
2254         else
2255             flash = 1 + (int)(flashtime * THREE / flash_length);
2256     } else
2257         flash = -1;
2258
2259     /*
2260      * Set up the `todraw' array.
2261      */
2262     for (y = 0; y < h; y++)
2263         for (x = 0; x < w; x++) {
2264             int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
2265             int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
2266             int v;
2267
2268             if (tv < 0)
2269                 tv = FOUR;
2270             if (bv < 0)
2271                 bv = FOUR;
2272
2273             if (flash >= 0) {
2274                 if (flash_type == 1) {
2275                     if (tv == flash)
2276                         tv = FOUR;
2277                     if (bv == flash)
2278                         bv = FOUR;
2279                 } else if (flash_type == 2) {
2280                     if (flash % 2)
2281                         tv = bv = FOUR;
2282                 } else {
2283                     if (tv != FOUR)
2284                         tv = (tv + flash) % FOUR;
2285                     if (bv != FOUR)
2286                         bv = (bv + flash) % FOUR;
2287                 }
2288             }
2289
2290             v = tv * FIVE + bv;
2291
2292             ds->todraw[y*w+x] = v;
2293         }
2294
2295     /*
2296      * Add error markers to the `todraw' array.
2297      */
2298     for (i = 0; i < state->map->ngraph; i++) {
2299         int v1 = state->map->graph[i] / n;
2300         int v2 = state->map->graph[i] % n;
2301
2302         if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
2303             continue;
2304         if (state->colouring[v1] != state->colouring[v2])
2305             continue;
2306
2307         x = state->map->edgex[i];
2308         y = state->map->edgey[i];
2309
2310         if (x % 2 && y % 2) {
2311             ds->todraw[(y/2)*w+(x/2)] |= ERR_C;
2312         } else if (x % 2) {
2313             ds->todraw[(y/2-1)*w+(x/2)] |= ERR_B;
2314             ds->todraw[(y/2)*w+(x/2)] |= ERR_T;
2315         } else {
2316             assert(y % 2);
2317             ds->todraw[(y/2)*w+(x/2-1)] |= ERR_R;
2318             ds->todraw[(y/2)*w+(x/2)] |= ERR_L;
2319         }
2320     }
2321
2322     /*
2323      * Now actually draw everything.
2324      */
2325     for (y = 0; y < h; y++)
2326         for (x = 0; x < w; x++) {
2327             int v = ds->todraw[y*w+x];
2328             if (ds->drawn[y*w+x] != v) {
2329                 draw_square(dr, ds, &state->p, state->map, x, y, v);
2330                 ds->drawn[y*w+x] = v;
2331             }
2332         }
2333
2334     /*
2335      * Draw the dragged colour blob if any.
2336      */
2337     if (ui->drag_colour > -2) {
2338         ds->dragx = ui->dragx - TILESIZE/2 - 2;
2339         ds->dragy = ui->dragy - TILESIZE/2 - 2;
2340         blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
2341         draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2,
2342                     (ui->drag_colour < 0 ? COL_BACKGROUND :
2343                      COL_0 + ui->drag_colour), COL_GRID);
2344         draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
2345         ds->drag_visible = TRUE;
2346     }
2347 }
2348
2349 static float game_anim_length(game_state *oldstate, game_state *newstate,
2350                               int dir, game_ui *ui)
2351 {
2352     return 0.0F;
2353 }
2354
2355 static float game_flash_length(game_state *oldstate, game_state *newstate,
2356                                int dir, game_ui *ui)
2357 {
2358     if (!oldstate->completed && newstate->completed &&
2359         !oldstate->cheated && !newstate->cheated) {
2360         if (flash_type < 0) {
2361             char *env = getenv("MAP_ALTERNATIVE_FLASH");
2362             if (env)
2363                 flash_type = atoi(env);
2364             else
2365                 flash_type = 0;
2366             flash_length = (flash_type == 1 ? 0.50 : 0.30);
2367         }
2368         return flash_length;
2369     } else
2370         return 0.0F;
2371 }
2372
2373 static int game_wants_statusbar(void)
2374 {
2375     return FALSE;
2376 }
2377
2378 static int game_timing_state(game_state *state, game_ui *ui)
2379 {
2380     return TRUE;
2381 }
2382
2383 static void game_print_size(game_params *params, float *x, float *y)
2384 {
2385     int pw, ph;
2386
2387     /*
2388      * I'll use 4mm squares by default, I think. Simplest way to
2389      * compute this size is to compute the pixel puzzle size at a
2390      * given tile size and then scale.
2391      */
2392     game_compute_size(params, 400, &pw, &ph);
2393     *x = pw / 100.0;
2394     *y = ph / 100.0;
2395 }
2396
2397 static void game_print(drawing *dr, game_state *state, int tilesize)
2398 {
2399     int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2400     int ink, c[FOUR], i;
2401     int x, y, r;
2402     int *coords, ncoords, coordsize;
2403
2404     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2405     struct { int tilesize; } ads, *ds = &ads;
2406     ads.tilesize = tilesize;
2407
2408     ink = print_mono_colour(dr, 0);
2409     for (i = 0; i < FOUR; i++)
2410         c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0],
2411                                 map_colours[i][1], map_colours[i][2]);
2412
2413     coordsize = 0;
2414     coords = NULL;
2415
2416     print_line_width(dr, TILESIZE / 16);
2417
2418     /*
2419      * Draw a single filled polygon around each region.
2420      */
2421     for (r = 0; r < n; r++) {
2422         int octants[8], lastdir, d1, d2, ox, oy;
2423
2424         /*
2425          * Start by finding a point on the region boundary. Any
2426          * point will do. To do this, we'll search for a square
2427          * containing the region and then decide which corner of it
2428          * to use.
2429          */
2430         x = w;
2431         for (y = 0; y < h; y++) {
2432             for (x = 0; x < w; x++) {
2433                 if (state->map->map[wh*0+y*w+x] == r ||
2434                     state->map->map[wh*1+y*w+x] == r ||
2435                     state->map->map[wh*2+y*w+x] == r ||
2436                     state->map->map[wh*3+y*w+x] == r)
2437                     break;
2438             }
2439             if (x < w)
2440                 break;
2441         }
2442         assert(y < h && x < w);        /* we must have found one somewhere */
2443         /*
2444          * This is the first square in lexicographic order which
2445          * contains part of this region. Therefore, one of the top
2446          * two corners of the square must be what we're after. The
2447          * only case in which it isn't the top left one is if the
2448          * square is diagonally divided and the region is in the
2449          * bottom right half.
2450          */
2451         if (state->map->map[wh*TE+y*w+x] != r &&
2452             state->map->map[wh*LE+y*w+x] != r)
2453             x++;                       /* could just as well have done y++ */
2454
2455         /*
2456          * Now we have a point on the region boundary. Trace around
2457          * the region until we come back to this point,
2458          * accumulating coordinates for a polygon draw operation as
2459          * we go.
2460          */
2461         lastdir = -1;
2462         ox = x;
2463         oy = y;
2464         ncoords = 0;
2465
2466         do {
2467             /*
2468              * There are eight possible directions we could head in
2469              * from here. We identify them by octant numbers, and
2470              * we also use octant numbers to identify the spaces
2471              * between them:
2472              *
2473              *   6   7   0
2474              *    \ 7|0 /
2475              *     \ | /
2476              *    6 \|/ 1
2477              * 5-----+-----1
2478              *    5 /|\ 2
2479              *     / | \
2480              *    / 4|3 \
2481              *   4   3   2
2482              */
2483             octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
2484             octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
2485             octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
2486             octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
2487             octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
2488             octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
2489             octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
2490             octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
2491
2492             d1 = d2 = -1;
2493             for (i = 0; i < 8; i++)
2494                 if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
2495                     assert(d2 == -1);
2496                     if (d1 == -1)
2497                         d1 = i;
2498                     else
2499                         d2 = i;
2500                 }
2501 /* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */
2502             assert(d1 != -1 && d2 != -1);
2503             if (d1 == lastdir)
2504                 d1 = d2;
2505
2506             /*
2507              * Now we're heading in direction d1. Save the current
2508              * coordinates.
2509              */
2510             if (ncoords + 2 > coordsize) {
2511                 coordsize += 128;
2512                 coords = sresize(coords, coordsize, int);
2513             }
2514             coords[ncoords++] = COORD(x);
2515             coords[ncoords++] = COORD(y);
2516
2517             /*
2518              * Compute the new coordinates.
2519              */
2520             x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
2521             y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
2522             assert(x >= 0 && x <= w && y >= 0 && y <= h);
2523
2524             lastdir = d1 ^ 4;
2525         } while (x != ox || y != oy);
2526
2527         draw_polygon(dr, coords, ncoords/2,
2528                      state->colouring[r] >= 0 ?
2529                      c[state->colouring[r]] : -1, ink);
2530     }
2531     sfree(coords);
2532 }
2533
2534 #ifdef COMBINED
2535 #define thegame map
2536 #endif
2537
2538 const struct game thegame = {
2539     "Map", "games.map",
2540     default_params,
2541     game_fetch_preset,
2542     decode_params,
2543     encode_params,
2544     free_params,
2545     dup_params,
2546     TRUE, game_configure, custom_params,
2547     validate_params,
2548     new_game_desc,
2549     validate_desc,
2550     new_game,
2551     dup_game,
2552     free_game,
2553     TRUE, solve_game,
2554     FALSE, game_text_format,
2555     new_ui,
2556     free_ui,
2557     encode_ui,
2558     decode_ui,
2559     game_changed_state,
2560     interpret_move,
2561     execute_move,
2562     20, game_compute_size, game_set_size,
2563     game_colours,
2564     game_new_drawstate,
2565     game_free_drawstate,
2566     game_redraw,
2567     game_anim_length,
2568     game_flash_length,
2569     TRUE, TRUE, game_print_size, game_print,
2570     game_wants_statusbar,
2571     FALSE, game_timing_state,
2572     0,                                 /* mouse_priorities */
2573 };