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