pattern.c

   1 /*
   2  * pattern.c: the pattern-reconstruction game known as `nonograms'.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10 #include <math.h>
  11
  12 #include "puzzles.h"
  13
  14 enum {
  15     COL_BACKGROUND,
  16     COL_EMPTY,
  17     COL_FULL,
  18     COL_TEXT,
  19     COL_UNKNOWN,
  20     COL_GRID,
  21     COL_CURSOR,
  22     COL_ERROR,
  23     NCOLOURS
  24 };
  25
  26 #define PREFERRED_TILE_SIZE 24
  27 #define TILE_SIZE (ds->tilesize)
  28 #define BORDER (3 * TILE_SIZE / 4)
  29 #define TLBORDER(d) ( (d) / 5 + 2 )
  30 #define GUTTER (TILE_SIZE / 2)
  31
  32 #define FROMCOORD(d, x) \
  33         ( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE )
  34
  35 #define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d)))
  36 #define GETTILESIZE(d, w) ((double)w / (2.0 + (double)TLBORDER(d) + (double)(d)))
  37
  38 #define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x)))
  39
  40 struct game_params {
  41     int w, h;
  42 };
  43
  44 #define GRID_UNKNOWN 2
  45 #define GRID_FULL 1
  46 #define GRID_EMPTY 0
  47
  48 typedef struct game_state_common {
  49     /* Parts of the game state that don't change during play. */
  50     int w, h;
  51     int rowsize;
  52     int *rowdata, *rowlen;
  53     int refcount;
  54 } game_state_common;
  55
  56 struct game_state {
  57     game_state_common *common;
  58     unsigned char *grid;
  59     int completed, cheated;
  60 };
  61
  62 #define FLASH_TIME 0.13F
  63
  64 static game_params *default_params(void)
  65 {
  66     game_params *ret = snew(game_params);
  67
  68     ret->w = ret->h = 15;
  69
  70     return ret;
  71 }
  72
  73 static const struct game_params pattern_presets[] = {
  74     {10, 10},
  75     {15, 15},
  76     {20, 20},
  77 #ifndef SLOW_SYSTEM
  78     {25, 25},
  79     {30, 30},
  80 #endif
  81 };
  82
  83 static int game_fetch_preset(int i, char **name, game_params **params)
  84 {
  85     game_params *ret;
  86     char str[80];
  87
  88     if (i < 0 || i >= lenof(pattern_presets))
  89         return FALSE;
  90
  91     ret = snew(game_params);
  92     *ret = pattern_presets[i];
  93
  94     sprintf(str, "%dx%d", ret->w, ret->h);
  95
  96     *name = dupstr(str);
  97     *params = ret;
  98     return TRUE;
  99 }
 100
 101 static void free_params(game_params *params)
 102 {
 103     sfree(params);
 104 }
 105
 106 static game_params *dup_params(const game_params *params)
 107 {
 108     game_params *ret = snew(game_params);
 109     *ret = *params;                    /* structure copy */
 110     return ret;
 111 }
 112
 113 static void decode_params(game_params *ret, char const *string)
 114 {
 115     char const *p = string;
 116
 117     ret->w = atoi(p);
 118     while (*p && isdigit((unsigned char)*p)) p++;
 119     if (*p == 'x') {
 120         p++;
 121         ret->h = atoi(p);
 122         while (*p && isdigit((unsigned char)*p)) p++;
 123     } else {
 124         ret->h = ret->w;
 125     }
 126 }
 127
 128 static char *encode_params(const game_params *params, int full)
 129 {
 130     char ret[400];
 131     int len;
 132
 133     len = sprintf(ret, "%dx%d", params->w, params->h);
 134     assert(len < lenof(ret));
 135     ret[len] = '\0';
 136
 137     return dupstr(ret);
 138 }
 139
 140 static config_item *game_configure(const game_params *params)
 141 {
 142     config_item *ret;
 143     char buf[80];
 144
 145     ret = snewn(3, config_item);
 146
 147     ret[0].name = "Width";
 148     ret[0].type = C_STRING;
 149     sprintf(buf, "%d", params->w);
 150     ret[0].sval = dupstr(buf);
 151     ret[0].ival = 0;
 152
 153     ret[1].name = "Height";
 154     ret[1].type = C_STRING;
 155     sprintf(buf, "%d", params->h);
 156     ret[1].sval = dupstr(buf);
 157     ret[1].ival = 0;
 158
 159     ret[2].name = NULL;
 160     ret[2].type = C_END;
 161     ret[2].sval = NULL;
 162     ret[2].ival = 0;
 163
 164     return ret;
 165 }
 166
 167 static game_params *custom_params(const config_item *cfg)
 168 {
 169     game_params *ret = snew(game_params);
 170
 171     ret->w = atoi(cfg[0].sval);
 172     ret->h = atoi(cfg[1].sval);
 173
 174     return ret;
 175 }
 176
 177 static char *validate_params(const game_params *params, int full)
 178 {
 179     if (params->w <= 0 || params->h <= 0)
 180         return "Width and height must both be greater than zero";
 181     return NULL;
 182 }
 183
 184 /* ----------------------------------------------------------------------
 185  * Puzzle generation code.
 186  *
 187  * For this particular puzzle, it seemed important to me to ensure
 188  * a unique solution. I do this the brute-force way, by having a
 189  * solver algorithm alongside the generator, and repeatedly
 190  * generating a random grid until I find one whose solution is
 191  * unique. It turns out that this isn't too onerous on a modern PC
 192  * provided you keep grid size below around 30. Any offers of
 193  * better algorithms, however, will be very gratefully received.
 194  *
 195  * Another annoyance of this approach is that it limits the
 196  * available puzzles to those solvable by the algorithm I've used.
 197  * My algorithm only ever considers a single row or column at any
 198  * one time, which means it's incapable of solving the following
 199  * difficult example (found by Bella Image around 1995/6, when she
 200  * and I were both doing maths degrees):
 201  *
 202  *        2  1  2  1
 203  *
 204  *      +--+--+--+--+
 205  * 1 1  |  |  |  |  |
 206  *      +--+--+--+--+
 207  *   2  |  |  |  |  |
 208  *      +--+--+--+--+
 209  *   1  |  |  |  |  |
 210  *      +--+--+--+--+
 211  *   1  |  |  |  |  |
 212  *      +--+--+--+--+
 213  *
 214  * Obviously this cannot be solved by a one-row-or-column-at-a-time
 215  * algorithm (it would require at least one row or column reading
 216  * `2 1', `1 2', `3' or `4' to get started). However, it can be
 217  * proved to have a unique solution: if the top left square were
 218  * empty, then the only option for the top row would be to fill the
 219  * two squares in the 1 columns, which would imply the squares
 220  * below those were empty, leaving no place for the 2 in the second
 221  * row. Contradiction. Hence the top left square is full, and the
 222  * unique solution follows easily from that starting point.
 223  *
 224  * (The game ID for this puzzle is 4x4:2/1/2/1/1.1/2/1/1 , in case
 225  * it's useful to anyone.)
 226  */
 227
 228 static int float_compare(const void *av, const void *bv)
 229 {
 230     const float *a = (const float *)av;
 231     const float *b = (const float *)bv;
 232     if (*a < *b)
 233         return -1;
 234     else if (*a > *b)
 235         return +1;
 236     else
 237         return 0;
 238 }
 239
 240 static void generate(random_state *rs, int w, int h, unsigned char *retgrid)
 241 {
 242     float *fgrid;
 243     float *fgrid2;
 244     int step, i, j;
 245     float threshold;
 246
 247     fgrid = snewn(w*h, float);
 248
 249     for (i = 0; i < h; i++) {
 250         for (j = 0; j < w; j++) {
 251             fgrid[i*w+j] = random_upto(rs, 100000000UL) / 100000000.F;
 252         }
 253     }
 254
 255     /*
 256      * The above gives a completely random splattering of black and
 257      * white cells. We want to gently bias this in favour of _some_
 258      * reasonably thick areas of white and black, while retaining
 259      * some randomness and fine detail.
 260      *
 261      * So we evolve the starting grid using a cellular automaton.
 262      * Currently, I'm doing something very simple indeed, which is
 263      * to set each square to the average of the surrounding nine
 264      * cells (or the average of fewer, if we're on a corner).
 265      */
 266     for (step = 0; step < 1; step++) {
 267         fgrid2 = snewn(w*h, float);
 268
 269         for (i = 0; i < h; i++) {
 270             for (j = 0; j < w; j++) {
 271                 float sx, xbar;
 272                 int n, p, q;
 273
 274                 /*
 275                  * Compute the average of the surrounding cells.
 276                  */
 277                 n = 0;
 278                 sx = 0.F;
 279                 for (p = -1; p <= +1; p++) {
 280                     for (q = -1; q <= +1; q++) {
 281                         if (i+p < 0 || i+p >= h || j+q < 0 || j+q >= w)
 282                             continue;
 283                         /*
 284                          * An additional special case not mentioned
 285                          * above: if a grid dimension is 2xn then
 286                          * we do not average across that dimension
 287                          * at all. Otherwise a 2x2 grid would
 288                          * contain four identical squares.
 289                          */
 290                         if ((h==2 && p!=0) || (w==2 && q!=0))
 291                             continue;
 292                         n++;
 293                         sx += fgrid[(i+p)*w+(j+q)];
 294                     }
 295                 }
 296                 xbar = sx / n;
 297
 298                 fgrid2[i*w+j] = xbar;
 299             }
 300         }
 301
 302         sfree(fgrid);
 303         fgrid = fgrid2;
 304     }
 305
 306     fgrid2 = snewn(w*h, float);
 307     memcpy(fgrid2, fgrid, w*h*sizeof(float));
 308     qsort(fgrid2, w*h, sizeof(float), float_compare);
 309     threshold = fgrid2[w*h/2];
 310     sfree(fgrid2);
 311
 312     for (i = 0; i < h; i++) {
 313         for (j = 0; j < w; j++) {
 314             retgrid[i*w+j] = (fgrid[i*w+j] >= threshold ? GRID_FULL :
 315                               GRID_EMPTY);
 316         }
 317     }
 318
 319     sfree(fgrid);
 320 }
 321
 322 static int compute_rowdata(int *ret, unsigned char *start, int len, int step)
 323 {
 324     int i, n;
 325
 326     n = 0;
 327
 328     for (i = 0; i < len; i++) {
 329         if (start[i*step] == GRID_FULL) {
 330             int runlen = 1;
 331             while (i+runlen < len && start[(i+runlen)*step] == GRID_FULL)
 332                 runlen++;
 333             ret[n++] = runlen;
 334             i += runlen;
 335         }
 336
 337         if (i < len && start[i*step] == GRID_UNKNOWN)
 338             return -1;
 339     }
 340
 341     return n;
 342 }
 343
 344 #define UNKNOWN 0
 345 #define BLOCK 1
 346 #define DOT 2
 347 #define STILL_UNKNOWN 3
 348
 349 #ifdef STANDALONE_SOLVER
 350 int verbose = FALSE;
 351 #endif
 352
 353 static int do_recurse(unsigned char *known, unsigned char *deduced,
 354                        unsigned char *row,
 355                        unsigned char *minpos_done, unsigned char *maxpos_done,
 356                        unsigned char *minpos_ok, unsigned char *maxpos_ok,
 357                        int *data, int len,
 358                        int freespace, int ndone, int lowest)
 359 {
 360     int i, j, k;
 361
 362
 363     /* This algorithm basically tries all possible ways the given rows of
 364      * black blocks can be laid out in the row/column being examined.
 365      * Special care is taken to avoid checking the tail of a row/column
 366      * if the same conditions have already been checked during this recursion
 367      * The algorithm also takes care to cut its losses as soon as an
 368      * invalid (partial) solution is detected.
 369      */
 370     if (data[ndone]) {
 371         if (lowest >= minpos_done[ndone] && lowest <= maxpos_done[ndone]) {
 372             if (lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone]) {
 373                 for (i=0; i<lowest; i++)
 374                     deduced[i] |= row[i];
 375             }
 376             return lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone];
 377         } else {
 378             if (lowest < minpos_done[ndone]) minpos_done[ndone] = lowest;
 379             if (lowest > maxpos_done[ndone]) maxpos_done[ndone] = lowest;
 380         }
 381         for (i=0; i<=freespace; i++) {
 382             j = lowest;
 383             for (k=0; k<i; k++) {
 384                 if (known[j] == BLOCK) goto next_iter;
 385                 row[j++] = DOT;
 386             }
 387             for (k=0; k<data[ndone]; k++) {
 388                 if (known[j] == DOT) goto next_iter;
 389                 row[j++] = BLOCK;
 390             }
 391             if (j < len) {
 392                 if (known[j] == BLOCK) goto next_iter;
 393                 row[j++] = DOT;
 394             }
 395             if (do_recurse(known, deduced, row, minpos_done, maxpos_done,
 396                            minpos_ok, maxpos_ok, data, len, freespace-i, ndone+1, j)) {
 397                 if (lowest < minpos_ok[ndone]) minpos_ok[ndone] = lowest;
 398                 if (lowest + i > maxpos_ok[ndone]) maxpos_ok[ndone] = lowest + i;
 399                 if (lowest + i > maxpos_done[ndone]) maxpos_done[ndone] = lowest + i;
 400             }
 401             next_iter:
 402             j++;
 403         }
 404         return lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone];
 405     } else {
 406         for (i=lowest; i<len; i++) {
 407             if (known[i] == BLOCK) return FALSE;
 408             row[i] = DOT;
 409             }
 410         for (i=0; i<len; i++)
 411             deduced[i] |= row[i];
 412         return TRUE;
 413     }
 414 }
 415
 416
 417 static int do_row(unsigned char *known, unsigned char *deduced,
 418                   unsigned char *row,
 419                   unsigned char *minpos_done, unsigned char *maxpos_done,
 420                   unsigned char *minpos_ok, unsigned char *maxpos_ok,
 421                   unsigned char *start, int len, int step, int *data,
 422                   unsigned int *changed
 423 #ifdef STANDALONE_SOLVER
 424                   , const char *rowcol, int index, int cluewid
 425 #endif
 426                   )
 427 {
 428     int rowlen, i, freespace, done_any;
 429
 430     freespace = len+1;
 431     for (rowlen = 0; data[rowlen]; rowlen++) {
 432         minpos_done[rowlen] = minpos_ok[rowlen] = len - 1;
 433         maxpos_done[rowlen] = maxpos_ok[rowlen] = 0;
 434         freespace -= data[rowlen]+1;
 435     }
 436
 437     for (i = 0; i < len; i++) {
 438         known[i] = start[i*step];
 439         deduced[i] = 0;
 440     }
 441     for (i = len - 1; i >= 0 && known[i] == DOT; i--)
 442         freespace--;
 443
 444     do_recurse(known, deduced, row, minpos_done, maxpos_done, minpos_ok, maxpos_ok, data, len, freespace, 0, 0);
 445
 446     done_any = FALSE;
 447     for (i=0; i<len; i++)
 448         if (deduced[i] && deduced[i] != STILL_UNKNOWN && !known[i]) {
 449             start[i*step] = deduced[i];
 450             if (changed) changed[i]++;
 451             done_any = TRUE;
 452         }
 453 #ifdef STANDALONE_SOLVER
 454     if (verbose && done_any) {
 455         char buf[80];
 456         int thiscluewid;
 457         printf("%s %2d: [", rowcol, index);
 458         for (thiscluewid = -1, i = 0; data[i]; i++)
 459             thiscluewid += sprintf(buf, " %d", data[i]);
 460         printf("%*s", cluewid - thiscluewid, "");
 461         for (i = 0; data[i]; i++)
 462             printf(" %d", data[i]);
 463         printf(" ] ");
 464         for (i = 0; i < len; i++)
 465             putchar(known[i] == BLOCK ? '#' :
 466                     known[i] == DOT ? '.' : '?');
 467         printf(" -> ");
 468         for (i = 0; i < len; i++)
 469             putchar(start[i*step] == BLOCK ? '#' :
 470                     start[i*step] == DOT ? '.' : '?');
 471         putchar('\n');
 472     }
 473 #endif
 474     return done_any;
 475 }
 476
 477 static int solve_puzzle(const game_state *state, unsigned char *grid,
 478                         int w, int h,
 479                         unsigned char *matrix, unsigned char *workspace,
 480                         unsigned int *changed_h, unsigned int *changed_w,
 481                         int *rowdata
 482 #ifdef STANDALONE_SOLVER
 483                         , int cluewid
 484 #else
 485                         , int dummy
 486 #endif
 487                         )
 488 {
 489     int i, j, ok, max;
 490     int max_h, max_w;
 491
 492     assert((state!=NULL) ^ (grid!=NULL));
 493
 494     max = max(w, h);
 495
 496     memset(matrix, 0, w*h);
 497
 498     /* For each column, compute how many squares can be deduced
 499      * from just the row-data.
 500      * Later, changed_* will hold how many squares were changed
 501      * in every row/column in the previous iteration
 502      * Changed_* is used to choose the next rows / cols to re-examine
 503      */
 504     for (i=0; i<h; i++) {
 505         int freespace;
 506         if (state) {
 507             memcpy(rowdata, state->common->rowdata + state->common->rowsize*(w+i), max*sizeof(int));
 508             rowdata[state->common->rowlen[w+i]] = 0;
 509         } else {
 510             rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
 511         }
 512         for (j=0, freespace=w+1; rowdata[j]; j++) freespace -= rowdata[j] + 1;
 513         for (j=0, changed_h[i]=0; rowdata[j]; j++)
 514             if (rowdata[j] > freespace)
 515                 changed_h[i] += rowdata[j] - freespace;
 516     }
 517     for (i=0,max_h=0; i<h; i++)
 518         if (changed_h[i] > max_h)
 519             max_h = changed_h[i];
 520     for (i=0; i<w; i++) {
 521         int freespace;
 522         if (state) {
 523             memcpy(rowdata, state->common->rowdata + state->common->rowsize*i, max*sizeof(int));
 524             rowdata[state->common->rowlen[i]] = 0;
 525         } else {
 526             rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
 527         }
 528         for (j=0, freespace=h+1; rowdata[j]; j++) freespace -= rowdata[j] + 1;
 529         for (j=0, changed_w[i]=0; rowdata[j]; j++)
 530             if (rowdata[j] > freespace)
 531                 changed_w[i] += rowdata[j] - freespace;
 532     }
 533     for (i=0,max_w=0; i<w; i++)
 534         if (changed_w[i] > max_w)
 535             max_w = changed_w[i];
 536
 537     /* Solve the puzzle.
 538      * Process rows/columns individually. Deductions involving more than one
 539      * row and/or column at a time are not supported.
 540      * Take care to only process rows/columns which have been changed since they
 541      * were previously processed.
 542      * Also, prioritize rows/columns which have had the most changes since their
 543      * previous processing, as they promise the greatest benefit.
 544      * Extremely rectangular grids (e.g. 10x20, 15x40, etc.) are not treated specially.
 545      */
 546     do {
 547         for (; max_h && max_h >= max_w; max_h--) {
 548             for (i=0; i<h; i++) {
 549                 if (changed_h[i] >= max_h) {
 550                     if (state) {
 551                         memcpy(rowdata, state->common->rowdata + state->common->rowsize*(w+i), max*sizeof(int));
 552                         rowdata[state->common->rowlen[w+i]] = 0;
 553                     } else {
 554                         rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
 555                     }
 556                     do_row(workspace, workspace+max, workspace+2*max,
 557                            workspace+3*max, workspace+4*max,
 558                            workspace+5*max, workspace+6*max,
 559                            matrix+i*w, w, 1, rowdata, changed_w
 560 #ifdef STANDALONE_SOLVER
 561                            , "row", i+1, cluewid
 562 #endif
 563                            );
 564                     changed_h[i] = 0;
 565                 }
 566             }
 567             for (i=0,max_w=0; i<w; i++)
 568                 if (changed_w[i] > max_w)
 569                     max_w = changed_w[i];
 570         }
 571         for (; max_w && max_w >= max_h; max_w--) {
 572             for (i=0; i<w; i++) {
 573                 if (changed_w[i] >= max_w) {
 574                     if (state) {
 575                         memcpy(rowdata, state->common->rowdata + state->common->rowsize*i, max*sizeof(int));
 576                         rowdata[state->common->rowlen[i]] = 0;
 577                     } else {
 578                         rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
 579                     }
 580                     do_row(workspace, workspace+max, workspace+2*max,
 581                            workspace+3*max, workspace+4*max,
 582                            workspace+5*max, workspace+6*max,
 583                            matrix+i, h, w, rowdata, changed_h
 584 #ifdef STANDALONE_SOLVER
 585                            , "col", i+1, cluewid
 586 #endif
 587                            );
 588                     changed_w[i] = 0;
 589                 }
 590             }
 591             for (i=0,max_h=0; i<h; i++)
 592                 if (changed_h[i] > max_h)
 593                     max_h = changed_h[i];
 594         }
 595     } while (max_h>0 || max_w>0);
 596
 597     ok = TRUE;
 598     for (i=0; i<h; i++) {
 599         for (j=0; j<w; j++) {
 600             if (matrix[i*w+j] == UNKNOWN)
 601                 ok = FALSE;
 602         }
 603     }
 604
 605     return ok;
 606 }
 607
 608 static unsigned char *generate_soluble(random_state *rs, int w, int h)
 609 {
 610     int i, j, ok, ntries, max;
 611     unsigned char *grid, *matrix, *workspace;
 612     unsigned int *changed_h, *changed_w;
 613     int *rowdata;
 614
 615     max = max(w, h);
 616
 617     grid = snewn(w*h, unsigned char);
 618     /* Allocate this here, to avoid having to reallocate it again for every geneerated grid */
 619     matrix = snewn(w*h, unsigned char);
 620     workspace = snewn(max*7, unsigned char);
 621     changed_h = snewn(max+1, unsigned int);
 622     changed_w = snewn(max+1, unsigned int);
 623     rowdata = snewn(max+1, int);
 624
 625     ntries = 0;
 626
 627     do {
 628         ntries++;
 629
 630         generate(rs, w, h, grid);
 631
 632         /*
 633          * The game is a bit too easy if any row or column is
 634          * completely black or completely white. An exception is
 635          * made for rows/columns that are under 3 squares,
 636          * otherwise nothing will ever be successfully generated.
 637          */
 638         ok = TRUE;
 639         if (w > 2) {
 640             for (i = 0; i < h; i++) {
 641                 int colours = 0;
 642                 for (j = 0; j < w; j++)
 643                     colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1);
 644                 if (colours != 3)
 645                     ok = FALSE;
 646             }
 647         }
 648         if (h > 2) {
 649             for (j = 0; j < w; j++) {
 650                 int colours = 0;
 651                 for (i = 0; i < h; i++)
 652                     colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1);
 653                 if (colours != 3)
 654                     ok = FALSE;
 655             }
 656         }
 657         if (!ok)
 658             continue;
 659
 660         ok = solve_puzzle(NULL, grid, w, h, matrix, workspace,
 661                           changed_h, changed_w, rowdata, 0);
 662     } while (!ok);
 663
 664     sfree(matrix);
 665     sfree(workspace);
 666     sfree(changed_h);
 667     sfree(changed_w);
 668     sfree(rowdata);
 669     return grid;
 670 }
 671
 672 static char *new_game_desc(const game_params *params, random_state *rs,
 673                            char **aux, int interactive)
 674 {
 675     unsigned char *grid;
 676     int i, j, max, rowlen, *rowdata;
 677     char intbuf[80], *desc;
 678     int desclen, descpos;
 679
 680     grid = generate_soluble(rs, params->w, params->h);
 681     max = max(params->w, params->h);
 682     rowdata = snewn(max, int);
 683
 684     /*
 685      * Save the solved game in aux.
 686      */
 687     {
 688         char *ai = snewn(params->w * params->h + 2, char);
 689
 690         /*
 691          * String format is exactly the same as a solve move, so we
 692          * can just dupstr this in solve_game().
 693          */
 694
 695         ai[0] = 'S';
 696
 697         for (i = 0; i < params->w * params->h; i++)
 698             ai[i+1] = grid[i] ? '1' : '0';
 699
 700         ai[params->w * params->h + 1] = '\0';
 701
 702         *aux = ai;
 703     }
 704
 705     /*
 706      * Seed is a slash-separated list of row contents; each row
 707      * contents section is a dot-separated list of integers. Row
 708      * contents are listed in the order (columns left to right,
 709      * then rows top to bottom).
 710      *
 711      * Simplest way to handle memory allocation is to make two
 712      * passes, first computing the seed size and then writing it
 713      * out.
 714      */
 715     desclen = 0;
 716     for (i = 0; i < params->w + params->h; i++) {
 717         if (i < params->w)
 718             rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
 719         else
 720             rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w,
 721                                      params->w, 1);
 722         if (rowlen > 0) {
 723             for (j = 0; j < rowlen; j++) {
 724                 desclen += 1 + sprintf(intbuf, "%d", rowdata[j]);
 725             }
 726         } else {
 727             desclen++;
 728         }
 729     }
 730     desc = snewn(desclen, char);
 731     descpos = 0;
 732     for (i = 0; i < params->w + params->h; i++) {
 733         if (i < params->w)
 734             rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
 735         else
 736             rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w,
 737                                      params->w, 1);
 738         if (rowlen > 0) {
 739             for (j = 0; j < rowlen; j++) {
 740                 int len = sprintf(desc+descpos, "%d", rowdata[j]);
 741                 if (j+1 < rowlen)
 742                     desc[descpos + len] = '.';
 743                 else
 744                     desc[descpos + len] = '/';
 745                 descpos += len+1;
 746             }
 747         } else {
 748             desc[descpos++] = '/';
 749         }
 750     }
 751     assert(descpos == desclen);
 752     assert(desc[desclen-1] == '/');
 753     desc[desclen-1] = '\0';
 754     sfree(rowdata);
 755     sfree(grid);
 756     return desc;
 757 }
 758
 759 static char *validate_desc(const game_params *params, const char *desc)
 760 {
 761     int i, n, rowspace;
 762     const char *p;
 763
 764     for (i = 0; i < params->w + params->h; i++) {
 765         if (i < params->w)
 766             rowspace = params->h + 1;
 767         else
 768             rowspace = params->w + 1;
 769
 770         if (*desc && isdigit((unsigned char)*desc)) {
 771             do {
 772                 p = desc;
 773                 while (*desc && isdigit((unsigned char)*desc)) desc++;
 774                 n = atoi(p);
 775                 rowspace -= n+1;
 776
 777                 if (rowspace < 0) {
 778                     if (i < params->w)
 779                         return "at least one column contains more numbers than will fit";
 780                     else
 781                         return "at least one row contains more numbers than will fit";
 782                 }
 783             } while (*desc++ == '.');
 784         } else {
 785             desc++;                    /* expect a slash immediately */
 786         }
 787
 788         if (desc[-1] == '/') {
 789             if (i+1 == params->w + params->h)
 790                 return "too many row/column specifications";
 791         } else if (desc[-1] == '\0') {
 792             if (i+1 < params->w + params->h)
 793                 return "too few row/column specifications";
 794         } else
 795             return "unrecognised character in game specification";
 796     }
 797
 798     return NULL;
 799 }
 800
 801 static game_state *new_game(midend *me, const game_params *params,
 802                             const char *desc)
 803 {
 804     int i;
 805     const char *p;
 806     game_state *state = snew(game_state);
 807
 808     state->common = snew(game_state_common);
 809     state->common->refcount = 1;
 810
 811     state->common->w = params->w;
 812     state->common->h = params->h;
 813
 814     state->grid = snewn(state->common->w * state->common->h, unsigned char);
 815     memset(state->grid, GRID_UNKNOWN, state->common->w * state->common->h);
 816
 817     state->common->rowsize = max(state->common->w, state->common->h);
 818     state->common->rowdata = snewn(state->common->rowsize * (state->common->w + state->common->h), int);
 819     state->common->rowlen = snewn(state->common->w + state->common->h, int);
 820
 821     state->completed = state->cheated = FALSE;
 822
 823     for (i = 0; i < params->w + params->h; i++) {
 824         state->common->rowlen[i] = 0;
 825         if (*desc && isdigit((unsigned char)*desc)) {
 826             do {
 827                 p = desc;
 828                 while (*desc && isdigit((unsigned char)*desc)) desc++;
 829                 state->common->rowdata[state->common->rowsize * i + state->common->rowlen[i]++] =
 830                     atoi(p);
 831             } while (*desc++ == '.');
 832         } else {
 833             desc++;                    /* expect a slash immediately */
 834         }
 835     }
 836
 837     return state;
 838 }
 839
 840 static game_state *dup_game(const game_state *state)
 841 {
 842     game_state *ret = snew(game_state);
 843
 844     ret->common = state->common;
 845     ret->common->refcount++;
 846
 847     ret->grid = snewn(ret->common->w * ret->common->h, unsigned char);
 848     memcpy(ret->grid, state->grid, ret->common->w * ret->common->h);
 849
 850     ret->completed = state->completed;
 851     ret->cheated = state->cheated;
 852
 853     return ret;
 854 }
 855
 856 static void free_game(game_state *state)
 857 {
 858     if (--state->common->refcount == 0) {
 859         sfree(state->common->rowdata);
 860         sfree(state->common->rowlen);
 861         sfree(state->common);
 862     }
 863     sfree(state->grid);
 864     sfree(state);
 865 }
 866
 867 static char *solve_game(const game_state *state, const game_state *currstate,
 868                         const char *ai, char **error)
 869 {
 870     unsigned char *matrix;
 871     int w = state->common->w, h = state->common->h;
 872     int i;
 873     char *ret;
 874     int max, ok;
 875     unsigned char *workspace;
 876     unsigned int *changed_h, *changed_w;
 877     int *rowdata;
 878
 879     /*
 880      * If we already have the solved state in ai, copy it out.
 881      */
 882     if (ai)
 883         return dupstr(ai);
 884
 885     max = max(w, h);
 886     matrix = snewn(w*h, unsigned char);
 887     workspace = snewn(max*7, unsigned char);
 888     changed_h = snewn(max+1, unsigned int);
 889     changed_w = snewn(max+1, unsigned int);
 890     rowdata = snewn(max+1, int);
 891
 892     ok = solve_puzzle(state, NULL, w, h, matrix, workspace,
 893                       changed_h, changed_w, rowdata, 0);
 894
 895     sfree(workspace);
 896     sfree(changed_h);
 897     sfree(changed_w);
 898     sfree(rowdata);
 899
 900     if (!ok) {
 901         sfree(matrix);
 902         *error = "Solving algorithm cannot complete this puzzle";
 903         return NULL;
 904     }
 905
 906     ret = snewn(w*h+2, char);
 907     ret[0] = 'S';
 908     for (i = 0; i < w*h; i++) {
 909         assert(matrix[i] == BLOCK || matrix[i] == DOT);
 910         ret[i+1] = (matrix[i] == BLOCK ? '1' : '0');
 911     }
 912     ret[w*h+1] = '\0';
 913
 914     sfree(matrix);
 915
 916     return ret;
 917 }
 918
 919 static int game_can_format_as_text_now(const game_params *params)
 920 {
 921     return TRUE;
 922 }
 923
 924 static char *game_text_format(const game_state *state)
 925 {
 926     int w = state->common->w, h = state->common->h, i, j;
 927     int left_gap = 0, top_gap = 0, ch = 2, cw = 1, limit = 1;
 928
 929     int len, topleft, lw, lh, gw, gh; /* {line,grid}_{width,height} */
 930     char *board, *buf;
 931
 932     for (i = 0; i < w; ++i) {
 933         top_gap = max(top_gap, state->common->rowlen[i]);
 934         for (j = 0; j < state->common->rowlen[i]; ++j)
 935             while (state->common->rowdata[i*state->common->rowsize + j] >= limit) {
 936                 ++cw;
 937                 limit *= 10;
 938             }
 939     }
 940     for (i = 0; i < h; ++i) {
 941         int rowlen = 0, predecessors = FALSE;
 942         for (j = 0; j < state->common->rowlen[i+w]; ++j) {
 943             int copy = state->common->rowdata[(i+w)*state->common->rowsize + j];
 944             rowlen += predecessors;
 945             predecessors = TRUE;
 946             do ++rowlen; while (copy /= 10);
 947         }
 948         left_gap = max(left_gap, rowlen);
 949     }
 950
 951     cw = max(cw, 3);
 952
 953     gw = w*cw + 2;
 954     gh = h*ch + 1;
 955     lw = gw + left_gap;
 956     lh = gh + top_gap;
 957     len = lw * lh;
 958     topleft = lw * top_gap + left_gap;
 959
 960     board = snewn(len + 1, char);
 961     sprintf(board, "%*s\n", len - 2, "");
 962
 963     for (i = 0; i < lh; ++i) {
 964         board[lw - 1 + i*lw] = '\n';
 965         if (i < top_gap) continue;
 966         board[lw - 2 + i*lw] = ((i - top_gap) % ch ? '|' : '+');
 967     }
 968
 969     for (i = 0; i < w; ++i) {
 970         for (j = 0; j < state->common->rowlen[i]; ++j) {
 971             int cell = topleft + i*cw + 1 + lw*(j - state->common->rowlen[i]);
 972             int nch = sprintf(board + cell, "%*d", cw - 1,
 973                               state->common->rowdata[i*state->common->rowsize + j]);
 974             board[cell + nch] = ' '; /* de-NUL-ify */
 975         }
 976     }
 977
 978     buf = snewn(left_gap, char);
 979     for (i = 0; i < h; ++i) {
 980         char *p = buf, *start = board + top_gap*lw + left_gap + (i*ch+1)*lw;
 981         for (j = 0; j < state->common->rowlen[i+w]; ++j) {
 982             if (p > buf) *p++ = ' ';
 983             p += sprintf(p, "%d", state->common->rowdata[(i+w)*state->common->rowsize + j]);
 984         }
 985         memcpy(start - (p - buf), buf, p - buf);
 986     }
 987
 988     for (i = 0; i < w; ++i) {
 989         for (j = 0; j < h; ++j) {
 990             int cell = topleft + i*cw + j*ch*lw;
 991             int center = cell + cw/2 + (ch/2)*lw;
 992             int dx, dy;
 993             board[cell] = 0 ? center : '+';
 994             for (dx = 1; dx < cw; ++dx) board[cell + dx] = '-';
 995             for (dy = 1; dy < ch; ++dy) board[cell + dy*lw] = '|';
 996             if (state->grid[i*w+j] == GRID_UNKNOWN) continue;
 997             for (dx = 1; dx < cw; ++dx)
 998                 for (dy = 1; dy < ch; ++dy)
 999                     board[cell + dx + dy*lw] =
1000                         state->grid[i*w+j] == GRID_FULL ? '#' : '.';
1001         }
1002     }
1003
1004     memcpy(board + topleft + h*ch*lw, board + topleft, gw - 1);
1005
1006     sfree(buf);
1007
1008     return board;
1009 }
1010
1011 struct game_ui {
1012     int dragging;
1013     int drag_start_x;
1014     int drag_start_y;
1015     int drag_end_x;
1016     int drag_end_y;
1017     int drag, release, state;
1018     int cur_x, cur_y, cur_visible;
1019 };
1020
1021 static game_ui *new_ui(const game_state *state)
1022 {
1023     game_ui *ret;
1024
1025     ret = snew(game_ui);
1026     ret->dragging = FALSE;
1027     ret->cur_x = ret->cur_y = ret->cur_visible = 0;
1028
1029     return ret;
1030 }
1031
1032 static void free_ui(game_ui *ui)
1033 {
1034     sfree(ui);
1035 }
1036
1037 static char *encode_ui(const game_ui *ui)
1038 {
1039     return NULL;
1040 }
1041
1042 static void decode_ui(game_ui *ui, const char *encoding)
1043 {
1044 }
1045
1046 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1047                                const game_state *newstate)
1048 {
1049 }
1050
1051 struct game_drawstate {
1052     int started;
1053     int w, h;
1054     int tilesize;
1055     unsigned char *visible, *numcolours;
1056     int cur_x, cur_y;
1057 };
1058
1059 static char *interpret_move(const game_state *state, game_ui *ui,
1060                             const game_drawstate *ds,
1061                             int x, int y, int button)
1062 {
1063     int control = button & MOD_CTRL, shift = button & MOD_SHFT;
1064     button &= ~MOD_MASK;
1065
1066     x = FROMCOORD(state->common->w, x);
1067     y = FROMCOORD(state->common->h, y);
1068
1069     if (x >= 0 && x < state->common->w && y >= 0 && y < state->common->h &&
1070         (button == LEFT_BUTTON || button == RIGHT_BUTTON ||
1071          button == MIDDLE_BUTTON)) {
1072 #ifdef STYLUS_BASED
1073         int currstate = state->grid[y * state->common->w + x];
1074 #endif
1075
1076         ui->dragging = TRUE;
1077
1078         if (button == LEFT_BUTTON) {
1079             ui->drag = LEFT_DRAG;
1080             ui->release = LEFT_RELEASE;
1081 #ifdef STYLUS_BASED
1082             ui->state = (currstate + 2) % 3; /* FULL -> EMPTY -> UNKNOWN */
1083 #else
1084             ui->state = GRID_FULL;
1085 #endif
1086         } else if (button == RIGHT_BUTTON) {
1087             ui->drag = RIGHT_DRAG;
1088             ui->release = RIGHT_RELEASE;
1089 #ifdef STYLUS_BASED
1090             ui->state = (currstate + 1) % 3; /* EMPTY -> FULL -> UNKNOWN */
1091 #else
1092             ui->state = GRID_EMPTY;
1093 #endif
1094         } else /* if (button == MIDDLE_BUTTON) */ {
1095             ui->drag = MIDDLE_DRAG;
1096             ui->release = MIDDLE_RELEASE;
1097             ui->state = GRID_UNKNOWN;
1098         }
1099
1100         ui->drag_start_x = ui->drag_end_x = x;
1101         ui->drag_start_y = ui->drag_end_y = y;
1102         ui->cur_visible = 0;
1103
1104         return "";                     /* UI activity occurred */
1105     }
1106
1107     if (ui->dragging && button == ui->drag) {
1108         /*
1109          * There doesn't seem much point in allowing a rectangle
1110          * drag; people will generally only want to drag a single
1111          * horizontal or vertical line, so we make that easy by
1112          * snapping to it.
1113          *
1114          * Exception: if we're _middle_-button dragging to tag
1115          * things as UNKNOWN, we may well want to trash an entire
1116          * area and start over!
1117          */
1118         if (ui->state != GRID_UNKNOWN) {
1119             if (abs(x - ui->drag_start_x) > abs(y - ui->drag_start_y))
1120                 y = ui->drag_start_y;
1121             else
1122                 x = ui->drag_start_x;
1123         }
1124
1125         if (x < 0) x = 0;
1126         if (y < 0) y = 0;
1127         if (x >= state->common->w) x = state->common->w - 1;
1128         if (y >= state->common->h) y = state->common->h - 1;
1129
1130         ui->drag_end_x = x;
1131         ui->drag_end_y = y;
1132
1133         return "";                     /* UI activity occurred */
1134     }
1135
1136     if (ui->dragging && button == ui->release) {
1137         int x1, x2, y1, y2, xx, yy;
1138         int move_needed = FALSE;
1139
1140         x1 = min(ui->drag_start_x, ui->drag_end_x);
1141         x2 = max(ui->drag_start_x, ui->drag_end_x);
1142         y1 = min(ui->drag_start_y, ui->drag_end_y);
1143         y2 = max(ui->drag_start_y, ui->drag_end_y);
1144
1145         for (yy = y1; yy <= y2; yy++)
1146             for (xx = x1; xx <= x2; xx++)
1147                 if (state->grid[yy * state->common->w + xx] != ui->state)
1148                     move_needed = TRUE;
1149
1150         ui->dragging = FALSE;
1151
1152         if (move_needed) {
1153             char buf[80];
1154             sprintf(buf, "%c%d,%d,%d,%d",
1155                     (char)(ui->state == GRID_FULL ? 'F' :
1156                            ui->state == GRID_EMPTY ? 'E' : 'U'),
1157                     x1, y1, x2-x1+1, y2-y1+1);
1158             return dupstr(buf);
1159         } else
1160             return "";                 /* UI activity occurred */
1161     }
1162
1163     if (IS_CURSOR_MOVE(button)) {
1164         int x = ui->cur_x, y = ui->cur_y, newstate;
1165         char buf[80];
1166         move_cursor(button, &ui->cur_x, &ui->cur_y, state->common->w, state->common->h, 0);
1167         ui->cur_visible = 1;
1168         if (!control && !shift) return "";
1169
1170         newstate = control ? shift ? GRID_UNKNOWN : GRID_FULL : GRID_EMPTY;
1171         if (state->grid[y * state->common->w + x] == newstate &&
1172             state->grid[ui->cur_y * state->common->w + ui->cur_x] == newstate)
1173             return "";
1174
1175         sprintf(buf, "%c%d,%d,%d,%d", control ? shift ? 'U' : 'F' : 'E',
1176                 min(x, ui->cur_x), min(y, ui->cur_y),
1177                 abs(x - ui->cur_x) + 1, abs(y - ui->cur_y) + 1);
1178         return dupstr(buf);
1179     }
1180
1181     if (IS_CURSOR_SELECT(button)) {
1182         int currstate = state->grid[ui->cur_y * state->common->w + ui->cur_x];
1183         int newstate;
1184         char buf[80];
1185
1186         if (!ui->cur_visible) {
1187             ui->cur_visible = 1;
1188             return "";
1189         }
1190
1191         if (button == CURSOR_SELECT2)
1192             newstate = currstate == GRID_UNKNOWN ? GRID_EMPTY :
1193                 currstate == GRID_EMPTY ? GRID_FULL : GRID_UNKNOWN;
1194         else
1195             newstate = currstate == GRID_UNKNOWN ? GRID_FULL :
1196                 currstate == GRID_FULL ? GRID_EMPTY : GRID_UNKNOWN;
1197
1198         sprintf(buf, "%c%d,%d,%d,%d",
1199                 (char)(newstate == GRID_FULL ? 'F' :
1200                        newstate == GRID_EMPTY ? 'E' : 'U'),
1201                 ui->cur_x, ui->cur_y, 1, 1);
1202         return dupstr(buf);
1203     }
1204
1205     return NULL;
1206 }
1207
1208 static game_state *execute_move(const game_state *from, const char *move)
1209 {
1210     game_state *ret;
1211     int x1, x2, y1, y2, xx, yy;
1212     int val;
1213
1214     if (move[0] == 'S' &&
1215         strlen(move) == from->common->w * from->common->h + 1) {
1216         int i;
1217
1218         ret = dup_game(from);
1219
1220         for (i = 0; i < ret->common->w * ret->common->h; i++)
1221             ret->grid[i] = (move[i+1] == '1' ? GRID_FULL : GRID_EMPTY);
1222
1223         ret->completed = ret->cheated = TRUE;
1224
1225         return ret;
1226     } else if ((move[0] == 'F' || move[0] == 'E' || move[0] == 'U') &&
1227         sscanf(move+1, "%d,%d,%d,%d", &x1, &y1, &x2, &y2) == 4 &&
1228         x1 >= 0 && x2 >= 0 && x1+x2 <= from->common->w &&
1229         y1 >= 0 && y2 >= 0 && y1+y2 <= from->common->h) {
1230
1231         x2 += x1;
1232         y2 += y1;
1233         val = (move[0] == 'F' ? GRID_FULL :
1234                  move[0] == 'E' ? GRID_EMPTY : GRID_UNKNOWN);
1235
1236         ret = dup_game(from);
1237         for (yy = y1; yy < y2; yy++)
1238             for (xx = x1; xx < x2; xx++)
1239                 ret->grid[yy * ret->common->w + xx] = val;
1240
1241         /*
1242          * An actual change, so check to see if we've completed the
1243          * game.
1244          */
1245         if (!ret->completed) {
1246             int *rowdata = snewn(ret->common->rowsize, int);
1247             int i, len;
1248
1249             ret->completed = TRUE;
1250
1251             for (i=0; i<ret->common->w; i++) {
1252                 len = compute_rowdata(rowdata, ret->grid+i,
1253                                       ret->common->h, ret->common->w);
1254                 if (len != ret->common->rowlen[i] ||
1255                     memcmp(ret->common->rowdata+i*ret->common->rowsize,
1256                            rowdata, len * sizeof(int))) {
1257                     ret->completed = FALSE;
1258                     break;
1259                 }
1260             }
1261             for (i=0; i<ret->common->h; i++) {
1262                 len = compute_rowdata(rowdata, ret->grid+i*ret->common->w,
1263                                       ret->common->w, 1);
1264                 if (len != ret->common->rowlen[i+ret->common->w] ||
1265                     memcmp(ret->common->rowdata +
1266                            (i+ret->common->w)*ret->common->rowsize,
1267                            rowdata, len * sizeof(int))) {
1268                     ret->completed = FALSE;
1269                     break;
1270                 }
1271             }
1272
1273             sfree(rowdata);
1274         }
1275
1276         return ret;
1277     } else
1278         return NULL;
1279 }
1280
1281 /* ----------------------------------------------------------------------
1282  * Error-checking during gameplay.
1283  */
1284
1285 /*
1286  * The difficulty in error-checking Pattern is to make the error check
1287  * _weak_ enough. The most obvious way would be to check each row and
1288  * column by calling (a modified form of) do_row() to recursively
1289  * analyse the row contents against the clue set and see if the
1290  * GRID_UNKNOWNs could be filled in in any way that would end up
1291  * correct. However, this turns out to be such a strong error check as
1292  * to constitute a spoiler in many situations: you make a typo while
1293  * trying to fill in one row, and not only does the row light up to
1294  * indicate an error, but several columns crossed by the move also
1295  * light up and draw your attention to deductions you hadn't even
1296  * noticed you could make.
1297  *
1298  * So instead I restrict error-checking to 'complete runs' within a
1299  * row, by which I mean contiguous sequences of GRID_FULL bounded at
1300  * both ends by either GRID_EMPTY or the ends of the row. We identify
1301  * all the complete runs in a row, and verify that _those_ are
1302  * consistent with the row's clue list. Sequences of complete runs
1303  * separated by solid GRID_EMPTY are required to match contiguous
1304  * sequences in the clue list, whereas if there's at least one
1305  * GRID_UNKNOWN between any two complete runs then those two need not
1306  * be contiguous in the clue list.
1307  *
1308  * To simplify the edge cases, I pretend that the clue list for the
1309  * row is extended with a 0 at each end, and I also pretend that the
1310  * grid data for the row is extended with a GRID_EMPTY and a
1311  * zero-length run at each end. This permits the contiguity checker to
1312  * handle the fiddly end effects (e.g. if the first contiguous
1313  * sequence of complete runs in the grid matches _something_ in the
1314  * clue list but not at the beginning, this is allowable iff there's a
1315  * GRID_UNKNOWN before the first one) with minimal faff, since the end
1316  * effects just drop out as special cases of the normal inter-run
1317  * handling (in this code the above case is not 'at the end of the
1318  * clue list' at all, but between the implicit initial zero run and
1319  * the first nonzero one).
1320  *
1321  * We must also be a little careful about how we search for a
1322  * contiguous sequence of runs. In the clue list (1 1 2 1 2 3),
1323  * suppose we see a GRID_UNKNOWN and then a length-1 run. We search
1324  * for 1 in the clue list and find it at the very beginning. But now
1325  * suppose we find a length-2 run with no GRID_UNKNOWN before it. We
1326  * can't naively look at the next clue from the 1 we found, because
1327  * that'll be the second 1 and won't match. Instead, we must backtrack
1328  * by observing that the 2 we've just found must be contiguous with
1329  * the 1 we've already seen, so we search for the sequence (1 2) and
1330  * find it starting at the second 1. Now if we see a 3, we must
1331  * rethink again and search for (1 2 3).
1332  */
1333
1334 struct errcheck_state {
1335     /*
1336      * rowdata and rowlen point at the clue data for this row in the
1337      * game state.
1338      */
1339     int *rowdata;
1340     int rowlen;
1341     /*
1342      * rowpos indicates the lowest position where it would be valid to
1343      * see our next run length. It might be equal to rowlen,
1344      * indicating that the next run would have to be the terminating 0.
1345      */
1346     int rowpos;
1347     /*
1348      * ncontig indicates how many runs we've seen in a contiguous
1349      * block. This is taken into account when searching for the next
1350      * run we find, unless ncontig is zeroed out first by encountering
1351      * a GRID_UNKNOWN.
1352      */
1353     int ncontig;
1354 };
1355
1356 static int errcheck_found_run(struct errcheck_state *es, int r)
1357 {
1358 /* Macro to handle the pretence that rowdata has a 0 at each end */
1359 #define ROWDATA(k) ((k)<0 || (k)>=es->rowlen ? 0 : es->rowdata[(k)])
1360
1361     /*
1362      * See if we can find this new run length at a position where it
1363      * also matches the last 'ncontig' runs we've seen.
1364      */
1365     int i, newpos;
1366     for (newpos = es->rowpos; newpos <= es->rowlen; newpos++) {
1367
1368         if (ROWDATA(newpos) != r)
1369             goto notfound;
1370
1371         for (i = 1; i <= es->ncontig; i++)
1372             if (ROWDATA(newpos - i) != ROWDATA(es->rowpos - i))
1373                 goto notfound;
1374
1375         es->rowpos = newpos+1;
1376         es->ncontig++;
1377         return TRUE;
1378
1379       notfound:;
1380     }
1381
1382     return FALSE;
1383
1384 #undef ROWDATA
1385 }
1386
1387 static int check_errors(const game_state *state, int i)
1388 {
1389     int start, step, end, j;
1390     int val, runlen;
1391     struct errcheck_state aes, *es = &aes;
1392
1393     es->rowlen = state->common->rowlen[i];
1394     es->rowdata = state->common->rowdata + state->common->rowsize * i;
1395     /* Pretend that we've already encountered the initial zero run */
1396     es->ncontig = 1;
1397     es->rowpos = 0;
1398
1399     if (i < state->common->w) {
1400         start = i;
1401         step = state->common->w;
1402         end = start + step * state->common->h;
1403     } else {
1404         start = (i - state->common->w) * state->common->w;
1405         step = 1;
1406         end = start + step * state->common->w;
1407     }
1408
1409     runlen = -1;
1410     for (j = start - step; j <= end; j += step) {
1411         if (j < start || j == end)
1412             val = GRID_EMPTY;
1413         else
1414             val = state->grid[j];
1415
1416         if (val == GRID_UNKNOWN) {
1417             runlen = -1;
1418             es->ncontig = 0;
1419         } else if (val == GRID_FULL) {
1420             if (runlen >= 0)
1421                 runlen++;
1422         } else if (val == GRID_EMPTY) {
1423             if (runlen > 0) {
1424                 if (!errcheck_found_run(es, runlen))
1425                     return TRUE;       /* error! */
1426             }
1427             runlen = 0;
1428         }
1429     }
1430
1431     /* Signal end-of-row by sending errcheck_found_run the terminating
1432      * zero run, which will be marked as contiguous with the previous
1433      * run if and only if there hasn't been a GRID_UNKNOWN before. */
1434     if (!errcheck_found_run(es, 0))
1435         return TRUE;                   /* error at the last minute! */
1436
1437     return FALSE;                      /* no error */
1438 }
1439
1440 /* ----------------------------------------------------------------------
1441  * Drawing routines.
1442  */
1443
1444 static void game_compute_size(const game_params *params, int tilesize,
1445                               int *x, int *y)
1446 {
1447     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1448     struct { int tilesize; } ads, *ds = &ads;
1449     ads.tilesize = tilesize;
1450
1451     *x = SIZE(params->w);
1452     *y = SIZE(params->h);
1453 }
1454
1455 static void game_set_size(drawing *dr, game_drawstate *ds,
1456                           const game_params *params, int tilesize)
1457 {
1458     ds->tilesize = tilesize;
1459 }
1460
1461 static float *game_colours(frontend *fe, int *ncolours)
1462 {
1463     float *ret = snewn(3 * NCOLOURS, float);
1464     int i;
1465
1466     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1467
1468     for (i = 0; i < 3; i++) {
1469         ret[COL_GRID    * 3 + i] = 0.3F;
1470         ret[COL_UNKNOWN * 3 + i] = 0.5F;
1471         ret[COL_TEXT    * 3 + i] = 0.0F;
1472         ret[COL_FULL    * 3 + i] = 0.0F;
1473         ret[COL_EMPTY   * 3 + i] = 1.0F;
1474     }
1475     ret[COL_CURSOR * 3 + 0] = 1.0F;
1476     ret[COL_CURSOR * 3 + 1] = 0.25F;
1477     ret[COL_CURSOR * 3 + 2] = 0.25F;
1478     ret[COL_ERROR * 3 + 0] = 1.0F;
1479     ret[COL_ERROR * 3 + 1] = 0.0F;
1480     ret[COL_ERROR * 3 + 2] = 0.0F;
1481
1482     *ncolours = NCOLOURS;
1483     return ret;
1484 }
1485
1486 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1487 {
1488     struct game_drawstate *ds = snew(struct game_drawstate);
1489
1490     ds->started = FALSE;
1491     ds->w = state->common->w;
1492     ds->h = state->common->h;
1493     ds->visible = snewn(ds->w * ds->h, unsigned char);
1494     ds->tilesize = 0;                  /* not decided yet */
1495     memset(ds->visible, 255, ds->w * ds->h);
1496     ds->numcolours = snewn(ds->w + ds->h, unsigned char);
1497     memset(ds->numcolours, 255, ds->w + ds->h);
1498     ds->cur_x = ds->cur_y = 0;
1499
1500     return ds;
1501 }
1502
1503 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1504 {
1505     sfree(ds->visible);
1506     sfree(ds);
1507 }
1508
1509 static void grid_square(drawing *dr, game_drawstate *ds,
1510                         int y, int x, int state, int cur)
1511 {
1512     int xl, xr, yt, yb, dx, dy, dw, dh;
1513
1514     draw_rect(dr, TOCOORD(ds->w, x), TOCOORD(ds->h, y),
1515               TILE_SIZE, TILE_SIZE, COL_GRID);
1516
1517     xl = (x % 5 == 0 ? 1 : 0);
1518     yt = (y % 5 == 0 ? 1 : 0);
1519     xr = (x % 5 == 4 || x == ds->w-1 ? 1 : 0);
1520     yb = (y % 5 == 4 || y == ds->h-1 ? 1 : 0);
1521
1522     dx = TOCOORD(ds->w, x) + 1 + xl;
1523     dy = TOCOORD(ds->h, y) + 1 + yt;
1524     dw = TILE_SIZE - xl - xr - 1;
1525     dh = TILE_SIZE - yt - yb - 1;
1526
1527     draw_rect(dr, dx, dy, dw, dh,
1528               (state == GRID_FULL ? COL_FULL :
1529                state == GRID_EMPTY ? COL_EMPTY : COL_UNKNOWN));
1530     if (cur) {
1531         draw_rect_outline(dr, dx, dy, dw, dh, COL_CURSOR);
1532         draw_rect_outline(dr, dx+1, dy+1, dw-2, dh-2, COL_CURSOR);
1533     }
1534
1535     draw_update(dr, TOCOORD(ds->w, x), TOCOORD(ds->h, y),
1536                 TILE_SIZE, TILE_SIZE);
1537 }
1538
1539 /*
1540  * Draw the numbers for a single row or column.
1541  */
1542 static void draw_numbers(drawing *dr, game_drawstate *ds,
1543                          const game_state *state, int i, int erase, int colour)
1544 {
1545     int rowlen = state->common->rowlen[i];
1546     int *rowdata = state->common->rowdata + state->common->rowsize * i;
1547     int nfit;
1548     int j;
1549
1550     if (erase) {
1551         if (i < state->common->w) {
1552             draw_rect(dr, TOCOORD(state->common->w, i), 0,
1553                       TILE_SIZE, BORDER + TLBORDER(state->common->h) * TILE_SIZE,
1554                       COL_BACKGROUND);
1555         } else {
1556             draw_rect(dr, 0, TOCOORD(state->common->h, i - state->common->w),
1557                       BORDER + TLBORDER(state->common->w) * TILE_SIZE, TILE_SIZE,
1558                       COL_BACKGROUND);
1559         }
1560     }
1561
1562     /*
1563      * Normally I space the numbers out by the same distance as the
1564      * tile size. However, if there are more numbers than available
1565      * spaces, I have to squash them up a bit.
1566      */
1567     if (i < state->common->w)
1568         nfit = TLBORDER(state->common->h);
1569     else
1570         nfit = TLBORDER(state->common->w);
1571     nfit = max(rowlen, nfit) - 1;
1572     assert(nfit > 0);
1573
1574     for (j = 0; j < rowlen; j++) {
1575         int x, y;
1576         char str[80];
1577
1578         if (i < state->common->w) {
1579             x = TOCOORD(state->common->w, i);
1580             y = BORDER + TILE_SIZE * (TLBORDER(state->common->h)-1);
1581             y -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(state->common->h)-1) / nfit;
1582         } else {
1583             y = TOCOORD(state->common->h, i - state->common->w);
1584             x = BORDER + TILE_SIZE * (TLBORDER(state->common->w)-1);
1585             x -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(state->common->w)-1) / nfit;
1586         }
1587
1588         sprintf(str, "%d", rowdata[j]);
1589         draw_text(dr, x+TILE_SIZE/2, y+TILE_SIZE/2, FONT_VARIABLE,
1590                   TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, colour, str);
1591     }
1592
1593     if (i < state->common->w) {
1594         draw_update(dr, TOCOORD(state->common->w, i), 0,
1595                     TILE_SIZE, BORDER + TLBORDER(state->common->h) * TILE_SIZE);
1596     } else {
1597         draw_update(dr, 0, TOCOORD(state->common->h, i - state->common->w),
1598                     BORDER + TLBORDER(state->common->w) * TILE_SIZE, TILE_SIZE);
1599     }
1600 }
1601
1602 static void game_redraw(drawing *dr, game_drawstate *ds,
1603                         const game_state *oldstate, const game_state *state,
1604                         int dir, const game_ui *ui,
1605                         float animtime, float flashtime)
1606 {
1607     int i, j;
1608     int x1, x2, y1, y2;
1609     int cx, cy, cmoved;
1610
1611     if (!ds->started) {
1612         /*
1613          * The initial contents of the window are not guaranteed
1614          * and can vary with front ends. To be on the safe side,
1615          * all games should start by drawing a big background-
1616          * colour rectangle covering the whole window.
1617          */
1618         draw_rect(dr, 0, 0, SIZE(ds->w), SIZE(ds->h), COL_BACKGROUND);
1619
1620         /*
1621          * Draw the grid outline.
1622          */
1623         draw_rect(dr, TOCOORD(ds->w, 0) - 1, TOCOORD(ds->h, 0) - 1,
1624                   ds->w * TILE_SIZE + 3, ds->h * TILE_SIZE + 3,
1625                   COL_GRID);
1626
1627         ds->started = TRUE;
1628
1629         draw_update(dr, 0, 0, SIZE(ds->w), SIZE(ds->h));
1630     }
1631
1632     if (ui->dragging) {
1633         x1 = min(ui->drag_start_x, ui->drag_end_x);
1634         x2 = max(ui->drag_start_x, ui->drag_end_x);
1635         y1 = min(ui->drag_start_y, ui->drag_end_y);
1636         y2 = max(ui->drag_start_y, ui->drag_end_y);
1637     } else {
1638         x1 = x2 = y1 = y2 = -1;        /* placate gcc warnings */
1639     }
1640
1641     if (ui->cur_visible) {
1642         cx = ui->cur_x; cy = ui->cur_y;
1643     } else {
1644         cx = cy = -1;
1645     }
1646     cmoved = (cx != ds->cur_x || cy != ds->cur_y);
1647
1648     /*
1649      * Now draw any grid squares which have changed since last
1650      * redraw.
1651      */
1652     for (i = 0; i < ds->h; i++) {
1653         for (j = 0; j < ds->w; j++) {
1654             int val, cc = 0;
1655
1656             /*
1657              * Work out what state this square should be drawn in,
1658              * taking any current drag operation into account.
1659              */
1660             if (ui->dragging && x1 <= j && j <= x2 && y1 <= i && i <= y2)
1661                 val = ui->state;
1662             else
1663                 val = state->grid[i * state->common->w + j];
1664
1665             if (cmoved) {
1666                 /* the cursor has moved; if we were the old or
1667                  * the new cursor position we need to redraw. */
1668                 if (j == cx && i == cy) cc = 1;
1669                 if (j == ds->cur_x && i == ds->cur_y) cc = 1;
1670             }
1671
1672             /*
1673              * Briefly invert everything twice during a completion
1674              * flash.
1675              */
1676             if (flashtime > 0 &&
1677                 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3) &&
1678                 val != GRID_UNKNOWN)
1679                 val = (GRID_FULL ^ GRID_EMPTY) ^ val;
1680
1681             if (ds->visible[i * ds->w + j] != val || cc) {
1682                 grid_square(dr, ds, i, j, val,
1683                             (j == cx && i == cy));
1684                 ds->visible[i * ds->w + j] = val;
1685             }
1686         }
1687     }
1688     ds->cur_x = cx; ds->cur_y = cy;
1689
1690     /*
1691      * Redraw any numbers which have changed their colour due to error
1692      * indication.
1693      */
1694     for (i = 0; i < state->common->w + state->common->h; i++) {
1695         int colour = check_errors(state, i) ? COL_ERROR : COL_TEXT;
1696         if (ds->numcolours[i] != colour) {
1697             draw_numbers(dr, ds, state, i, TRUE, colour);
1698             ds->numcolours[i] = colour;
1699         }
1700     }
1701 }
1702
1703 static float game_anim_length(const game_state *oldstate,
1704                               const game_state *newstate, int dir, game_ui *ui)
1705 {
1706     return 0.0F;
1707 }
1708
1709 static float game_flash_length(const game_state *oldstate,
1710                                const game_state *newstate, int dir, game_ui *ui)
1711 {
1712     if (!oldstate->completed && newstate->completed &&
1713         !oldstate->cheated && !newstate->cheated)
1714         return FLASH_TIME;
1715     return 0.0F;
1716 }
1717
1718 static int game_status(const game_state *state)
1719 {
1720     return state->completed ? +1 : 0;
1721 }
1722
1723 static int game_timing_state(const game_state *state, game_ui *ui)
1724 {
1725     return TRUE;
1726 }
1727
1728 static void game_print_size(const game_params *params, float *x, float *y)
1729 {
1730     int pw, ph;
1731
1732     /*
1733      * I'll use 5mm squares by default.
1734      */
1735     game_compute_size(params, 500, &pw, &ph);
1736     *x = pw / 100.0F;
1737     *y = ph / 100.0F;
1738 }
1739
1740 static void game_print(drawing *dr, const game_state *state, int tilesize)
1741 {
1742     int w = state->common->w, h = state->common->h;
1743     int ink = print_mono_colour(dr, 0);
1744     int x, y, i;
1745
1746     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1747     game_drawstate ads, *ds = &ads;
1748     game_set_size(dr, ds, NULL, tilesize);
1749
1750     /*
1751      * Border.
1752      */
1753     print_line_width(dr, TILE_SIZE / 16);
1754     draw_rect_outline(dr, TOCOORD(w, 0), TOCOORD(h, 0),
1755                       w*TILE_SIZE, h*TILE_SIZE, ink);
1756
1757     /*
1758      * Grid.
1759      */
1760     for (x = 1; x < w; x++) {
1761         print_line_width(dr, TILE_SIZE / (x % 5 ? 128 : 24));
1762         draw_line(dr, TOCOORD(w, x), TOCOORD(h, 0),
1763                   TOCOORD(w, x), TOCOORD(h, h), ink);
1764     }
1765     for (y = 1; y < h; y++) {
1766         print_line_width(dr, TILE_SIZE / (y % 5 ? 128 : 24));
1767         draw_line(dr, TOCOORD(w, 0), TOCOORD(h, y),
1768                   TOCOORD(w, w), TOCOORD(h, y), ink);
1769     }
1770
1771     /*
1772      * Clues.
1773      */
1774     for (i = 0; i < state->common->w + state->common->h; i++)
1775         draw_numbers(dr, ds, state, i, FALSE, ink);
1776
1777     /*
1778      * Solution.
1779      */
1780     print_line_width(dr, TILE_SIZE / 128);
1781     for (y = 0; y < h; y++)
1782         for (x = 0; x < w; x++) {
1783             if (state->grid[y*w+x] == GRID_FULL)
1784                 draw_rect(dr, TOCOORD(w, x), TOCOORD(h, y),
1785                           TILE_SIZE, TILE_SIZE, ink);
1786             else if (state->grid[y*w+x] == GRID_EMPTY)
1787                 draw_circle(dr, TOCOORD(w, x) + TILE_SIZE/2,
1788                             TOCOORD(h, y) + TILE_SIZE/2,
1789                             TILE_SIZE/12, ink, ink);
1790         }
1791 }
1792
1793 #ifdef COMBINED
1794 #define thegame pattern
1795 #endif
1796
1797 const struct game thegame = {
1798     "Pattern", "games.pattern", "pattern",
1799     default_params,
1800     game_fetch_preset,
1801     decode_params,
1802     encode_params,
1803     free_params,
1804     dup_params,
1805     TRUE, game_configure, custom_params,
1806     validate_params,
1807     new_game_desc,
1808     validate_desc,
1809     new_game,
1810     dup_game,
1811     free_game,
1812     TRUE, solve_game,
1813     TRUE, game_can_format_as_text_now, game_text_format,
1814     new_ui,
1815     free_ui,
1816     encode_ui,
1817     decode_ui,
1818     game_changed_state,
1819     interpret_move,
1820     execute_move,
1821     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1822     game_colours,
1823     game_new_drawstate,
1824     game_free_drawstate,
1825     game_redraw,
1826     game_anim_length,
1827     game_flash_length,
1828     game_status,
1829     TRUE, FALSE, game_print_size, game_print,
1830     FALSE,                             /* wants_statusbar */
1831     FALSE, game_timing_state,
1832     REQUIRE_RBUTTON,                   /* flags */
1833 };
1834
1835 #ifdef STANDALONE_SOLVER
1836
1837 int main(int argc, char **argv)
1838 {
1839     game_params *p;
1840     game_state *s;
1841     char *id = NULL, *desc, *err;
1842
1843     while (--argc > 0) {
1844         char *p = *++argv;
1845         if (*p == '-') {
1846             if (!strcmp(p, "-v")) {
1847                 verbose = TRUE;
1848             } else {
1849                 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
1850                 return 1;
1851             }
1852         } else {
1853             id = p;
1854         }
1855     }
1856
1857     if (!id) {
1858         fprintf(stderr, "usage: %s <game_id>\n", argv[0]);
1859         return 1;
1860     }
1861
1862     desc = strchr(id, ':');
1863     if (!desc) {
1864         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
1865         return 1;
1866     }
1867     *desc++ = '\0';
1868
1869     p = default_params();
1870     decode_params(p, id);
1871     err = validate_desc(p, desc);
1872     if (err) {
1873         fprintf(stderr, "%s: %s\n", argv[0], err);
1874         return 1;
1875     }
1876     s = new_game(NULL, p, desc);
1877
1878     {
1879         int w = p->w, h = p->h, i, j, max, cluewid = 0;
1880         unsigned char *matrix, *workspace;
1881         unsigned int *changed_h, *changed_w;
1882         int *rowdata;
1883
1884         matrix = snewn(w*h, unsigned char);
1885         max = max(w, h);
1886         workspace = snewn(max*7, unsigned char);
1887         changed_h = snewn(max+1, unsigned int);
1888         changed_w = snewn(max+1, unsigned int);
1889         rowdata = snewn(max+1, int);
1890
1891         if (verbose) {
1892             int thiswid;
1893             /*
1894              * Work out the maximum text width of the clue numbers
1895              * in a row or column, so we can print the solver's
1896              * working in a nicely lined up way.
1897              */
1898             for (i = 0; i < (w+h); i++) {
1899                 char buf[80];
1900                 for (thiswid = -1, j = 0; j < s->rowlen[i]; j++)
1901                     thiswid += sprintf(buf, " %d", s->rowdata[s->rowsize*i+j]);
1902                 if (cluewid < thiswid)
1903                     cluewid = thiswid;
1904             }
1905         }
1906
1907         solve_puzzle(s, NULL, w, h, matrix, workspace,
1908                      changed_h, changed_w, rowdata, cluewid);
1909
1910         for (i = 0; i < h; i++) {
1911             for (j = 0; j < w; j++) {
1912                 int c = (matrix[i*w+j] == UNKNOWN ? '?' :
1913                          matrix[i*w+j] == BLOCK ? '#' :
1914                          matrix[i*w+j] == DOT ? '.' :
1915                          '!');
1916                 putchar(c);
1917             }
1918             printf("\n");
1919         }
1920     }
1921
1922     return 0;
1923 }
1924
1925 #endif
1926
1927 /* vim: set shiftwidth=4 tabstop=8: */