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