map.c

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