map.c

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