pattern.c

   1 /*
   2  * pattern.c: the pattern-reconstruction game known as `nonograms'.
   3  *
   4  * TODO before checkin:
   5  *
   6  *  - make some sort of stab at number-of-numbers judgment
   7  */
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <assert.h>
  13 #include <ctype.h>
  14 #include <math.h>
  15
  16 #include "puzzles.h"
  17
  18 #define max(x,y) ( (x)>(y) ? (x):(y) )
  19 #define min(x,y) ( (x)<(y) ? (x):(y) )
  20
  21 enum {
  22     COL_BACKGROUND,
  23     COL_EMPTY,
  24     COL_FULL,
  25     COL_UNKNOWN,
  26     COL_GRID,
  27     NCOLOURS
  28 };
  29
  30 #define BORDER 18
  31 #define TLBORDER(d) ( (d) / 5 + 2 )
  32 #define GUTTER 12
  33 #define TILE_SIZE 24
  34
  35 #define FROMCOORD(d, x) \
  36         ( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE )
  37
  38 #define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d)))
  39
  40 #define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x)))
  41
  42 struct game_params {
  43     int w, h;
  44 };
  45
  46 #define GRID_UNKNOWN 2
  47 #define GRID_FULL 1
  48 #define GRID_EMPTY 0
  49
  50 struct game_state {
  51     int w, h;
  52     unsigned char *grid;
  53     int rowsize;
  54     int *rowdata, *rowlen;
  55     int completed;
  56 };
  57
  58 #define FLASH_TIME 0.13F
  59
  60 static game_params *default_params(void)
  61 {
  62     game_params *ret = snew(game_params);
  63
  64     ret->w = ret->h = 15;
  65
  66     return ret;
  67 }
  68
  69 static int game_fetch_preset(int i, char **name, game_params **params)
  70 {
  71     game_params *ret;
  72     char str[80];
  73     static const struct { int x, y; } values[] = {
  74         {10, 10},
  75         {15, 15},
  76         {20, 20},
  77         {25, 25},
  78         {30, 30},
  79     };
  80
  81     if (i < 0 || i >= lenof(values))
  82         return FALSE;
  83
  84     ret = snew(game_params);
  85     ret->w = values[i].x;
  86     ret->h = values[i].y;
  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 game_params *decode_params(char const *string)
 108 {
 109     game_params *ret = default_params();
 110     char const *p = string;
 111
 112     ret->w = atoi(p);
 113     while (*p && isdigit(*p)) p++;
 114     if (*p == 'x') {
 115         p++;
 116         ret->h = atoi(p);
 117         while (*p && isdigit(*p)) p++;
 118     } else {
 119         ret->h = ret->w;
 120     }
 121
 122     return ret;
 123 }
 124
 125 static char *encode_params(game_params *params)
 126 {
 127     char ret[400];
 128     int len;
 129
 130     len = sprintf(ret, "%dx%d", params->w, params->h);
 131     assert(len < lenof(ret));
 132     ret[len] = '\0';
 133
 134     return dupstr(ret);
 135 }
 136
 137 static config_item *game_configure(game_params *params)
 138 {
 139     config_item *ret;
 140     char buf[80];
 141
 142     ret = snewn(3, config_item);
 143
 144     ret[0].name = "Width";
 145     ret[0].type = C_STRING;
 146     sprintf(buf, "%d", params->w);
 147     ret[0].sval = dupstr(buf);
 148     ret[0].ival = 0;
 149
 150     ret[1].name = "Height";
 151     ret[1].type = C_STRING;
 152     sprintf(buf, "%d", params->h);
 153     ret[1].sval = dupstr(buf);
 154     ret[1].ival = 0;
 155
 156     ret[2].name = NULL;
 157     ret[2].type = C_END;
 158     ret[2].sval = NULL;
 159     ret[2].ival = 0;
 160
 161     return ret;
 162 }
 163
 164 static game_params *custom_params(config_item *cfg)
 165 {
 166     game_params *ret = snew(game_params);
 167
 168     ret->w = atoi(cfg[0].sval);
 169     ret->h = atoi(cfg[1].sval);
 170
 171     return ret;
 172 }
 173
 174 static char *validate_params(game_params *params)
 175 {
 176     if (params->w <= 0 && params->h <= 0)
 177         return "Width and height must both be greater than zero";
 178     if (params->w <= 0)
 179         return "Width must be greater than zero";
 180     if (params->h <= 0)
 181         return "Height must be greater than zero";
 182     return NULL;
 183 }
 184
 185 /* ----------------------------------------------------------------------
 186  * Puzzle generation code.
 187  *
 188  * For this particular puzzle, it seemed important to me to ensure
 189  * a unique solution. I do this the brute-force way, by having a
 190  * solver algorithm alongside the generator, and repeatedly
 191  * generating a random grid until I find one whose solution is
 192  * unique. It turns out that this isn't too onerous on a modern PC
 193  * provided you keep grid size below around 30. Any offers of
 194  * better algorithms, however, will be very gratefully received.
 195  *
 196  * Another annoyance of this approach is that it limits the
 197  * available puzzles to those solvable by the algorithm I've used.
 198  * My algorithm only ever considers a single row or column at any
 199  * one time, which means it's incapable of solving the following
 200  * difficult example (found by Bella Image around 1995/6, when she
 201  * and I were both doing maths degrees):
 202  *
 203  *        2  1  2  1
 204  *
 205  *      +--+--+--+--+
 206  * 1 1  |  |  |  |  |
 207  *      +--+--+--+--+
 208  *   2  |  |  |  |  |
 209  *      +--+--+--+--+
 210  *   1  |  |  |  |  |
 211  *      +--+--+--+--+
 212  *   1  |  |  |  |  |
 213  *      +--+--+--+--+
 214  *
 215  * Obviously this cannot be solved by a one-row-or-column-at-a-time
 216  * algorithm (it would require at least one row or column reading
 217  * `2 1', `1 2', `3' or `4' to get started). However, it can be
 218  * proved to have a unique solution: if the top left square were
 219  * empty, then the only option for the top row would be to fill the
 220  * two squares in the 1 columns, which would imply the squares
 221  * below those were empty, leaving no place for the 2 in the second
 222  * row. Contradiction. Hence the top left square is full, and the
 223  * unique solution follows easily from that starting point.
 224  *
 225  * (The game ID for this puzzle is 4x4:2/1/2/1/1.1/2/1/1 , in case
 226  * it's useful to anyone.)
 227  */
 228
 229 static int float_compare(const void *av, const void *bv)
 230 {
 231     const float *a = (const float *)av;
 232     const float *b = (const float *)bv;
 233     if (*a < *b)
 234         return -1;
 235     else if (*a > *b)
 236         return +1;
 237     else
 238         return 0;
 239 }
 240
 241 static void generate(random_state *rs, int w, int h, unsigned char *retgrid)
 242 {
 243     float *fgrid;
 244     float *fgrid2;
 245     int step, i, j;
 246     float threshold;
 247
 248     fgrid = snewn(w*h, float);
 249
 250     for (i = 0; i < h; i++) {
 251         for (j = 0; j < w; j++) {
 252             fgrid[i*w+j] = random_upto(rs, 100000000UL) / 100000000.F;
 253         }
 254     }
 255
 256     /*
 257      * The above gives a completely random splattering of black and
 258      * white cells. We want to gently bias this in favour of _some_
 259      * reasonably thick areas of white and black, while retaining
 260      * some randomness and fine detail.
 261      *
 262      * So we evolve the starting grid using a cellular automaton.
 263      * Currently, I'm doing something very simple indeed, which is
 264      * to set each square to the average of the surrounding nine
 265      * cells (or the average of fewer, if we're on a corner).
 266      */
 267     for (step = 0; step < 1; step++) {
 268         fgrid2 = snewn(w*h, float);
 269
 270         for (i = 0; i < h; i++) {
 271             for (j = 0; j < w; j++) {
 272                 float sx, xbar;
 273                 int n, p, q;
 274
 275                 /*
 276                  * Compute the average of the surrounding cells.
 277                  */
 278                 n = 0;
 279                 sx = 0.F;
 280                 for (p = -1; p <= +1; p++) {
 281                     for (q = -1; q <= +1; q++) {
 282                         if (i+p < 0 || i+p >= h || j+q < 0 || j+q >= w)
 283                             continue;
 284                         /*
 285                          * An additional special case not mentioned
 286                          * above: if a grid dimension is 2xn then
 287                          * we do not average across that dimension
 288                          * at all. Otherwise a 2x2 grid would
 289                          * contain four identical squares.
 290                          */
 291                         if ((h==2 && p!=0) || (w==2 && q!=0))
 292                             continue;
 293                         n++;
 294                         sx += fgrid[(i+p)*w+(j+q)];
 295                     }
 296                 }
 297                 xbar = sx / n;
 298
 299                 fgrid2[i*w+j] = xbar;
 300             }
 301         }
 302
 303         sfree(fgrid);
 304         fgrid = fgrid2;
 305     }
 306
 307     fgrid2 = snewn(w*h, float);
 308     memcpy(fgrid2, fgrid, w*h*sizeof(float));
 309     qsort(fgrid2, w*h, sizeof(float), float_compare);
 310     threshold = fgrid2[w*h/2];
 311     sfree(fgrid2);
 312
 313     for (i = 0; i < h; i++) {
 314         for (j = 0; j < w; j++) {
 315             retgrid[i*w+j] = (fgrid[i*w+j] >= threshold ? GRID_FULL :
 316                               GRID_EMPTY);
 317         }
 318     }
 319
 320     sfree(fgrid);
 321 }
 322
 323 static int compute_rowdata(int *ret, unsigned char *start, int len, int step)
 324 {
 325     int i, n;
 326
 327     n = 0;
 328
 329     for (i = 0; i < len; i++) {
 330         if (start[i*step] == GRID_FULL) {
 331             int runlen = 1;
 332             while (i+runlen < len && start[(i+runlen)*step] == GRID_FULL)
 333                 runlen++;
 334             ret[n++] = runlen;
 335             i += runlen;
 336         }
 337
 338         if (i < len && start[i*step] == GRID_UNKNOWN)
 339             return -1;
 340     }
 341
 342     return n;
 343 }
 344
 345 #define UNKNOWN 0
 346 #define BLOCK 1
 347 #define DOT 2
 348 #define STILL_UNKNOWN 3
 349
 350 static void do_recurse(unsigned char *known, unsigned char *deduced,
 351                        unsigned char *row, int *data, int len,
 352                        int freespace, int ndone, int lowest)
 353 {
 354     int i, j, k;
 355
 356     if (data[ndone]) {
 357         for (i=0; i<=freespace; i++) {
 358             j = lowest;
 359             for (k=0; k<i; k++) row[j++] = DOT;
 360             for (k=0; k<data[ndone]; k++) row[j++] = BLOCK;
 361             if (j < len) row[j++] = DOT;
 362             do_recurse(known, deduced, row, data, len,
 363                        freespace-i, ndone+1, j);
 364         }
 365     } else {
 366         for (i=lowest; i<len; i++)
 367             row[i] = DOT;
 368         for (i=0; i<len; i++)
 369             if (known[i] && known[i] != row[i])
 370                 return;
 371         for (i=0; i<len; i++)
 372             deduced[i] |= row[i];
 373     }
 374 }
 375
 376 static int do_row(unsigned char *known, unsigned char *deduced,
 377                   unsigned char *row,
 378                   unsigned char *start, int len, int step, int *data)
 379 {
 380     int rowlen, i, freespace, done_any;
 381
 382     freespace = len+1;
 383     for (rowlen = 0; data[rowlen]; rowlen++)
 384         freespace -= data[rowlen]+1;
 385
 386     for (i = 0; i < len; i++) {
 387         known[i] = start[i*step];
 388         deduced[i] = 0;
 389     }
 390
 391     do_recurse(known, deduced, row, data, len, freespace, 0, 0);
 392     done_any = FALSE;
 393     for (i=0; i<len; i++)
 394         if (deduced[i] && deduced[i] != STILL_UNKNOWN && !known[i]) {
 395             start[i*step] = deduced[i];
 396             done_any = TRUE;
 397         }
 398     return done_any;
 399 }
 400
 401 static unsigned char *generate_soluble(random_state *rs, int w, int h)
 402 {
 403     int i, j, done_any, ok, ntries, max;
 404     unsigned char *grid, *matrix, *workspace;
 405     int *rowdata;
 406
 407     grid = snewn(w*h, unsigned char);
 408     matrix = snewn(w*h, unsigned char);
 409     max = max(w, h);
 410     workspace = snewn(max*3, unsigned char);
 411     rowdata = snewn(max+1, int);
 412
 413     ntries = 0;
 414
 415     do {
 416         ntries++;
 417
 418         generate(rs, w, h, grid);
 419
 420         /*
 421          * The game is a bit too easy if any row or column is
 422          * completely black or completely white. An exception is
 423          * made for rows/columns that are under 3 squares,
 424          * otherwise nothing will ever be successfully generated.
 425          */
 426         ok = TRUE;
 427         if (w > 2) {
 428             for (i = 0; i < h; i++) {
 429                 int colours = 0;
 430                 for (j = 0; j < w; j++)
 431                     colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1);
 432                 if (colours != 3)
 433                     ok = FALSE;
 434             }
 435         }
 436         if (h > 2) {
 437             for (j = 0; j < w; j++) {
 438                 int colours = 0;
 439                 for (i = 0; i < h; i++)
 440                     colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1);
 441                 if (colours != 3)
 442                     ok = FALSE;
 443             }
 444         }
 445         if (!ok)
 446             continue;
 447
 448         memset(matrix, 0, w*h);
 449
 450         do {
 451             done_any = 0;
 452             for (i=0; i<h; i++) {
 453                 rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
 454                 done_any |= do_row(workspace, workspace+max, workspace+2*max,
 455                                    matrix+i*w, w, 1, rowdata);
 456             }
 457             for (i=0; i<w; i++) {
 458                 rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
 459                 done_any |= do_row(workspace, workspace+max, workspace+2*max,
 460                                    matrix+i, h, w, rowdata);
 461             }
 462         } while (done_any);
 463
 464         ok = TRUE;
 465         for (i=0; i<h; i++) {
 466             for (j=0; j<w; j++) {
 467                 if (matrix[i*w+j] == UNKNOWN)
 468                     ok = FALSE;
 469             }
 470         }
 471     } while (!ok);
 472
 473     sfree(matrix);
 474     sfree(workspace);
 475     sfree(rowdata);
 476     return grid;
 477 }
 478
 479 static char *new_game_seed(game_params *params, random_state *rs,
 480                            game_aux_info **aux)
 481 {
 482     unsigned char *grid;
 483     int i, j, max, rowlen, *rowdata;
 484     char intbuf[80], *seed;
 485     int seedlen, seedpos;
 486
 487     grid = generate_soluble(rs, params->w, params->h);
 488     max = max(params->w, params->h);
 489     rowdata = snewn(max, int);
 490
 491     /*
 492      * Seed is a slash-separated list of row contents; each row
 493      * contents section is a dot-separated list of integers. Row
 494      * contents are listed in the order (columns left to right,
 495      * then rows top to bottom).
 496      *
 497      * Simplest way to handle memory allocation is to make two
 498      * passes, first computing the seed size and then writing it
 499      * out.
 500      */
 501     seedlen = 0;
 502     for (i = 0; i < params->w + params->h; i++) {
 503         if (i < params->w)
 504             rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
 505         else
 506             rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w,
 507                                      params->w, 1);
 508         if (rowlen > 0) {
 509             for (j = 0; j < rowlen; j++) {
 510                 seedlen += 1 + sprintf(intbuf, "%d", rowdata[j]);
 511             }
 512         } else {
 513             seedlen++;
 514         }
 515     }
 516     seed = snewn(seedlen, char);
 517     seedpos = 0;
 518     for (i = 0; i < params->w + params->h; i++) {
 519         if (i < params->w)
 520             rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
 521         else
 522             rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w,
 523                                      params->w, 1);
 524         if (rowlen > 0) {
 525             for (j = 0; j < rowlen; j++) {
 526                 int len = sprintf(seed+seedpos, "%d", rowdata[j]);
 527                 if (j+1 < rowlen)
 528                     seed[seedpos + len] = '.';
 529                 else
 530                     seed[seedpos + len] = '/';
 531                 seedpos += len+1;
 532             }
 533         } else {
 534             seed[seedpos++] = '/';
 535         }
 536     }
 537     assert(seedpos == seedlen);
 538     assert(seed[seedlen-1] == '/');
 539     seed[seedlen-1] = '\0';
 540     sfree(rowdata);
 541     return seed;
 542 }
 543
 544 void game_free_aux_info(game_aux_info *aux)
 545 {
 546     assert(!"Shouldn't happen");
 547 }
 548
 549 static char *validate_seed(game_params *params, char *seed)
 550 {
 551     int i, n, rowspace;
 552     char *p;
 553
 554     for (i = 0; i < params->w + params->h; i++) {
 555         if (i < params->w)
 556             rowspace = params->h + 1;
 557         else
 558             rowspace = params->w + 1;
 559
 560         if (*seed && isdigit((unsigned char)*seed)) {
 561             do {
 562                 p = seed;
 563                 while (seed && isdigit((unsigned char)*seed)) seed++;
 564                 n = atoi(p);
 565                 rowspace -= n+1;
 566
 567                 if (rowspace < 0) {
 568                     if (i < params->w)
 569                         return "at least one column contains more numbers than will fit";
 570                     else
 571                         return "at least one row contains more numbers than will fit";
 572                 }
 573             } while (*seed++ == '.');
 574         } else {
 575             seed++;                    /* expect a slash immediately */
 576         }
 577
 578         if (seed[-1] == '/') {
 579             if (i+1 == params->w + params->h)
 580                 return "too many row/column specifications";
 581         } else if (seed[-1] == '\0') {
 582             if (i+1 < params->w + params->h)
 583                 return "too few row/column specifications";
 584         } else
 585             return "unrecognised character in game specification";
 586     }
 587
 588     return NULL;
 589 }
 590
 591 static game_state *new_game(game_params *params, char *seed)
 592 {
 593     int i;
 594     char *p;
 595     game_state *state = snew(game_state);
 596
 597     state->w = params->w;
 598     state->h = params->h;
 599
 600     state->grid = snewn(state->w * state->h, unsigned char);
 601     memset(state->grid, GRID_UNKNOWN, state->w * state->h);
 602
 603     state->rowsize = max(state->w, state->h);
 604     state->rowdata = snewn(state->rowsize * (state->w + state->h), int);
 605     state->rowlen = snewn(state->w + state->h, int);
 606
 607     state->completed = FALSE;
 608
 609     for (i = 0; i < params->w + params->h; i++) {
 610         state->rowlen[i] = 0;
 611         if (*seed && isdigit((unsigned char)*seed)) {
 612             do {
 613                 p = seed;
 614                 while (seed && isdigit((unsigned char)*seed)) seed++;
 615                 state->rowdata[state->rowsize * i + state->rowlen[i]++] =
 616                     atoi(p);
 617             } while (*seed++ == '.');
 618         } else {
 619             seed++;                    /* expect a slash immediately */
 620         }
 621     }
 622
 623     return state;
 624 }
 625
 626 static game_state *dup_game(game_state *state)
 627 {
 628     game_state *ret = snew(game_state);
 629
 630     ret->w = state->w;
 631     ret->h = state->h;
 632
 633     ret->grid = snewn(ret->w * ret->h, unsigned char);
 634     memcpy(ret->grid, state->grid, ret->w * ret->h);
 635
 636     ret->rowsize = state->rowsize;
 637     ret->rowdata = snewn(ret->rowsize * (ret->w + ret->h), int);
 638     ret->rowlen = snewn(ret->w + ret->h, int);
 639     memcpy(ret->rowdata, state->rowdata,
 640            ret->rowsize * (ret->w + ret->h) * sizeof(int));
 641     memcpy(ret->rowlen, state->rowlen,
 642            (ret->w + ret->h) * sizeof(int));
 643
 644     ret->completed = state->completed;
 645
 646     return ret;
 647 }
 648
 649 static void free_game(game_state *state)
 650 {
 651     sfree(state->rowdata);
 652     sfree(state->rowlen);
 653     sfree(state->grid);
 654     sfree(state);
 655 }
 656
 657 static char *game_text_format(game_state *state)
 658 {
 659     return NULL;
 660 }
 661
 662 struct game_ui {
 663     int dragging;
 664     int drag_start_x;
 665     int drag_start_y;
 666     int drag_end_x;
 667     int drag_end_y;
 668     int drag, release, state;
 669 };
 670
 671 static game_ui *new_ui(game_state *state)
 672 {
 673     game_ui *ret;
 674
 675     ret = snew(game_ui);
 676     ret->dragging = FALSE;
 677
 678     return ret;
 679 }
 680
 681 static void free_ui(game_ui *ui)
 682 {
 683     sfree(ui);
 684 }
 685
 686 static game_state *make_move(game_state *from, game_ui *ui,
 687                              int x, int y, int button)
 688 {
 689     game_state *ret;
 690
 691     x = FROMCOORD(from->w, x);
 692     y = FROMCOORD(from->h, y);
 693
 694     if (x >= 0 && x < from->w && y >= 0 && y < from->h &&
 695         (button == LEFT_BUTTON || button == RIGHT_BUTTON ||
 696          button == MIDDLE_BUTTON)) {
 697
 698         ui->dragging = TRUE;
 699
 700         if (button == LEFT_BUTTON) {
 701             ui->drag = LEFT_DRAG;
 702             ui->release = LEFT_RELEASE;
 703             ui->state = GRID_FULL;
 704         } else if (button == RIGHT_BUTTON) {
 705             ui->drag = RIGHT_DRAG;
 706             ui->release = RIGHT_RELEASE;
 707             ui->state = GRID_EMPTY;
 708         } else /* if (button == MIDDLE_BUTTON) */ {
 709             ui->drag = MIDDLE_DRAG;
 710             ui->release = MIDDLE_RELEASE;
 711             ui->state = GRID_UNKNOWN;
 712         }
 713
 714         ui->drag_start_x = ui->drag_end_x = x;
 715         ui->drag_start_y = ui->drag_end_y = y;
 716
 717         return from;                   /* UI activity occurred */
 718     }
 719
 720     if (ui->dragging && button == ui->drag) {
 721         /*
 722          * There doesn't seem much point in allowing a rectangle
 723          * drag; people will generally only want to drag a single
 724          * horizontal or vertical line, so we make that easy by
 725          * snapping to it.
 726          *
 727          * Exception: if we're _middle_-button dragging to tag
 728          * things as UNKNOWN, we may well want to trash an entire
 729          * area and start over!
 730          */
 731         if (ui->state != GRID_UNKNOWN) {
 732             if (abs(x - ui->drag_start_x) > abs(y - ui->drag_start_y))
 733                 y = ui->drag_start_y;
 734             else
 735                 x = ui->drag_start_x;
 736         }
 737
 738         if (x < 0) x = 0;
 739         if (y < 0) y = 0;
 740         if (x >= from->w) x = from->w - 1;
 741         if (y >= from->h) y = from->h - 1;
 742
 743         ui->drag_end_x = x;
 744         ui->drag_end_y = y;
 745
 746         return from;                   /* UI activity occurred */
 747     }
 748
 749     if (ui->dragging && button == ui->release) {
 750         int x1, x2, y1, y2, xx, yy;
 751         int move_needed = FALSE;
 752
 753         x1 = min(ui->drag_start_x, ui->drag_end_x);
 754         x2 = max(ui->drag_start_x, ui->drag_end_x);
 755         y1 = min(ui->drag_start_y, ui->drag_end_y);
 756         y2 = max(ui->drag_start_y, ui->drag_end_y);
 757
 758         for (yy = y1; yy <= y2; yy++)
 759             for (xx = x1; xx <= x2; xx++)
 760                 if (from->grid[yy * from->w + xx] != ui->state)
 761                     move_needed = TRUE;
 762
 763         ui->dragging = FALSE;
 764
 765         if (move_needed) {
 766             ret = dup_game(from);
 767             for (yy = y1; yy <= y2; yy++)
 768                 for (xx = x1; xx <= x2; xx++)
 769                     ret->grid[yy * ret->w + xx] = ui->state;
 770
 771             /*
 772              * An actual change, so check to see if we've completed
 773              * the game.
 774              */
 775             if (!ret->completed) {
 776                 int *rowdata = snewn(ret->rowsize, int);
 777                 int i, len;
 778
 779                 ret->completed = TRUE;
 780
 781                 for (i=0; i<ret->w; i++) {
 782                     len = compute_rowdata(rowdata,
 783                                           ret->grid+i, ret->h, ret->w);
 784                     if (len != ret->rowlen[i] ||
 785                         memcmp(ret->rowdata+i*ret->rowsize, rowdata,
 786                                len * sizeof(int))) {
 787                         ret->completed = FALSE;
 788                         break;
 789                     }
 790                 }
 791                 for (i=0; i<ret->h; i++) {
 792                     len = compute_rowdata(rowdata,
 793                                           ret->grid+i*ret->w, ret->w, 1);
 794                     if (len != ret->rowlen[i+ret->w] ||
 795                         memcmp(ret->rowdata+(i+ret->w)*ret->rowsize, rowdata,
 796                                len * sizeof(int))) {
 797                         ret->completed = FALSE;
 798                         break;
 799                     }
 800                 }
 801
 802                 sfree(rowdata);
 803             }
 804
 805             return ret;
 806         } else
 807             return from;               /* UI activity occurred */
 808     }
 809
 810     return NULL;
 811 }
 812
 813 /* ----------------------------------------------------------------------
 814  * Drawing routines.
 815  */
 816
 817 struct game_drawstate {
 818     int started;
 819     int w, h;
 820     unsigned char *visible;
 821 };
 822
 823 static void game_size(game_params *params, int *x, int *y)
 824 {
 825     *x = SIZE(params->w);
 826     *y = SIZE(params->h);
 827 }
 828
 829 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
 830 {
 831     float *ret = snewn(3 * NCOLOURS, float);
 832
 833     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 834
 835     ret[COL_GRID * 3 + 0] = 0.3F;
 836     ret[COL_GRID * 3 + 1] = 0.3F;
 837     ret[COL_GRID * 3 + 2] = 0.3F;
 838
 839     ret[COL_UNKNOWN * 3 + 0] = 0.5F;
 840     ret[COL_UNKNOWN * 3 + 1] = 0.5F;
 841     ret[COL_UNKNOWN * 3 + 2] = 0.5F;
 842
 843     ret[COL_FULL * 3 + 0] = 0.0F;
 844     ret[COL_FULL * 3 + 1] = 0.0F;
 845     ret[COL_FULL * 3 + 2] = 0.0F;
 846
 847     ret[COL_EMPTY * 3 + 0] = 1.0F;
 848     ret[COL_EMPTY * 3 + 1] = 1.0F;
 849     ret[COL_EMPTY * 3 + 2] = 1.0F;
 850
 851     *ncolours = NCOLOURS;
 852     return ret;
 853 }
 854
 855 static game_drawstate *game_new_drawstate(game_state *state)
 856 {
 857     struct game_drawstate *ds = snew(struct game_drawstate);
 858
 859     ds->started = FALSE;
 860     ds->w = state->w;
 861     ds->h = state->h;
 862     ds->visible = snewn(ds->w * ds->h, unsigned char);
 863     memset(ds->visible, 255, ds->w * ds->h);
 864
 865     return ds;
 866 }
 867
 868 static void game_free_drawstate(game_drawstate *ds)
 869 {
 870     sfree(ds->visible);
 871     sfree(ds);
 872 }
 873
 874 static void grid_square(frontend *fe, game_drawstate *ds,
 875                         int y, int x, int state)
 876 {
 877     int xl, xr, yt, yb;
 878
 879     draw_rect(fe, TOCOORD(ds->w, x), TOCOORD(ds->h, y),
 880               TILE_SIZE, TILE_SIZE, COL_GRID);
 881
 882     xl = (x % 5 == 0 ? 1 : 0);
 883     yt = (y % 5 == 0 ? 1 : 0);
 884     xr = (x % 5 == 4 || x == ds->w-1 ? 1 : 0);
 885     yb = (y % 5 == 4 || y == ds->h-1 ? 1 : 0);
 886
 887     draw_rect(fe, TOCOORD(ds->w, x) + 1 + xl, TOCOORD(ds->h, y) + 1 + yt,
 888               TILE_SIZE - xl - xr - 1, TILE_SIZE - yt - yb - 1,
 889               (state == GRID_FULL ? COL_FULL :
 890                state == GRID_EMPTY ? COL_EMPTY : COL_UNKNOWN));
 891
 892     draw_update(fe, TOCOORD(ds->w, x), TOCOORD(ds->h, y),
 893                 TILE_SIZE, TILE_SIZE);
 894 }
 895
 896 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 897                  game_state *state, int dir, game_ui *ui,
 898                  float animtime, float flashtime)
 899 {
 900     int i, j;
 901     int x1, x2, y1, y2;
 902
 903     if (!ds->started) {
 904         /*
 905          * The initial contents of the window are not guaranteed
 906          * and can vary with front ends. To be on the safe side,
 907          * all games should start by drawing a big background-
 908          * colour rectangle covering the whole window.
 909          */
 910         draw_rect(fe, 0, 0, SIZE(ds->w), SIZE(ds->h), COL_BACKGROUND);
 911
 912         /*
 913          * Draw the numbers.
 914          */
 915         for (i = 0; i < ds->w + ds->h; i++) {
 916             int rowlen = state->rowlen[i];
 917             int *rowdata = state->rowdata + state->rowsize * i;
 918             int nfit;
 919
 920             /*
 921              * Normally I space the numbers out by the same
 922              * distance as the tile size. However, if there are
 923              * more numbers than available spaces, I have to squash
 924              * them up a bit.
 925              */
 926             nfit = max(rowlen, TLBORDER(ds->h))-1;
 927             assert(nfit > 0);
 928
 929             for (j = 0; j < rowlen; j++) {
 930                 int x, y;
 931                 char str[80];
 932
 933                 if (i < ds->w) {
 934                     x = TOCOORD(ds->w, i);
 935                     y = BORDER + TILE_SIZE * (TLBORDER(ds->h)-1);
 936                     y -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(ds->h)-1) / nfit;
 937                 } else {
 938                     y = TOCOORD(ds->h, i - ds->w);
 939                     x = BORDER + TILE_SIZE * (TLBORDER(ds->w)-1);
 940                     x -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(ds->h)-1) / nfit;
 941                 }
 942
 943                 sprintf(str, "%d", rowdata[j]);
 944                 draw_text(fe, x+TILE_SIZE/2, y+TILE_SIZE/2, FONT_VARIABLE,
 945                           TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE,
 946                           COL_FULL, str);   /* FIXME: COL_TEXT */
 947             }
 948         }
 949
 950         /*
 951          * Draw the grid outline.
 952          */
 953         draw_rect(fe, TOCOORD(ds->w, 0) - 1, TOCOORD(ds->h, 0) - 1,
 954                   ds->w * TILE_SIZE + 3, ds->h * TILE_SIZE + 3,
 955                   COL_GRID);
 956
 957         ds->started = TRUE;
 958
 959         draw_update(fe, 0, 0, SIZE(ds->w), SIZE(ds->h));
 960     }
 961
 962     if (ui->dragging) {
 963         x1 = min(ui->drag_start_x, ui->drag_end_x);
 964         x2 = max(ui->drag_start_x, ui->drag_end_x);
 965         y1 = min(ui->drag_start_y, ui->drag_end_y);
 966         y2 = max(ui->drag_start_y, ui->drag_end_y);
 967     } else {
 968         x1 = x2 = y1 = y2 = -1;        /* placate gcc warnings */
 969     }
 970
 971     /*
 972      * Now draw any grid squares which have changed since last
 973      * redraw.
 974      */
 975     for (i = 0; i < ds->h; i++) {
 976         for (j = 0; j < ds->w; j++) {
 977             int val;
 978
 979             /*
 980              * Work out what state this square should be drawn in,
 981              * taking any current drag operation into account.
 982              */
 983             if (ui->dragging && x1 <= j && j <= x2 && y1 <= i && i <= y2)
 984                 val = ui->state;
 985             else
 986                 val = state->grid[i * state->w + j];
 987
 988             /*
 989              * Briefly invert everything twice during a completion
 990              * flash.
 991              */
 992             if (flashtime > 0 &&
 993                 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3) &&
 994                 val != GRID_UNKNOWN)
 995                 val = (GRID_FULL ^ GRID_EMPTY) ^ val;
 996
 997             if (ds->visible[i * ds->w + j] != val) {
 998                 grid_square(fe, ds, i, j, val);
 999                 ds->visible[i * ds->w + j] = val;
1000             }
1001         }
1002     }
1003 }
1004
1005 static float game_anim_length(game_state *oldstate,
1006                               game_state *newstate, int dir)
1007 {
1008     return 0.0F;
1009 }
1010
1011 static float game_flash_length(game_state *oldstate,
1012                                game_state *newstate, int dir)
1013 {
1014     if (!oldstate->completed && newstate->completed)
1015         return FLASH_TIME;
1016     return 0.0F;
1017 }
1018
1019 static int game_wants_statusbar(void)
1020 {
1021     return FALSE;
1022 }
1023
1024 #ifdef COMBINED
1025 #define thegame pattern
1026 #endif
1027
1028 const struct game thegame = {
1029     "Pattern", "games.pattern",
1030     default_params,
1031     game_fetch_preset,
1032     decode_params,
1033     encode_params,
1034     free_params,
1035     dup_params,
1036     TRUE, game_configure, custom_params,
1037     validate_params,
1038     new_game_seed,
1039     game_free_aux_info,
1040     validate_seed,
1041     new_game,
1042     dup_game,
1043     free_game,
1044     FALSE, game_text_format,
1045     new_ui,
1046     free_ui,
1047     make_move,
1048     game_size,
1049     game_colours,
1050     game_new_drawstate,
1051     game_free_drawstate,
1052     game_redraw,
1053     game_anim_length,
1054     game_flash_length,
1055     game_wants_statusbar,
1056 };
1057
1058 #ifdef STANDALONE_SOLVER
1059
1060 /*
1061  * gcc -DSTANDALONE_SOLVER -o patternsolver pattern.c malloc.c
1062  */
1063
1064 #include <stdarg.h>
1065
1066 void frontend_default_colour(frontend *fe, float *output) {}
1067 void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize,
1068                int align, int colour, char *text) {}
1069 void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {}
1070 void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {}
1071 void draw_polygon(frontend *fe, int *coords, int npoints,
1072                   int fill, int colour) {}
1073 void clip(frontend *fe, int x, int y, int w, int h) {}
1074 void unclip(frontend *fe) {}
1075 void start_draw(frontend *fe) {}
1076 void draw_update(frontend *fe, int x, int y, int w, int h) {}
1077 void end_draw(frontend *fe) {}
1078 unsigned long random_upto(random_state *state, unsigned long limit)
1079 { assert(!"Shouldn't get randomness"); return 0; }
1080
1081 void fatal(char *fmt, ...)
1082 {
1083     va_list ap;
1084
1085     fprintf(stderr, "fatal error: ");
1086
1087     va_start(ap, fmt);
1088     vfprintf(stderr, fmt, ap);
1089     va_end(ap);
1090
1091     fprintf(stderr, "\n");
1092     exit(1);
1093 }
1094
1095 int main(int argc, char **argv)
1096 {
1097     game_params *p;
1098     game_state *s;
1099     int recurse = TRUE;
1100     char *id = NULL, *seed, *err;
1101     int y, x;
1102     int grade = FALSE;
1103
1104     while (--argc > 0) {
1105         char *p = *++argv;
1106         if (*p == '-') {
1107             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0]);
1108             return 1;
1109         } else {
1110             id = p;
1111         }
1112     }
1113
1114     if (!id) {
1115         fprintf(stderr, "usage: %s <game_id>\n", argv[0]);
1116         return 1;
1117     }
1118
1119     seed = strchr(id, ':');
1120     if (!seed) {
1121         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
1122         return 1;
1123     }
1124     *seed++ = '\0';
1125
1126     p = decode_params(id);
1127     err = validate_seed(p, seed);
1128     if (err) {
1129         fprintf(stderr, "%s: %s\n", argv[0], err);
1130         return 1;
1131     }
1132     s = new_game(p, seed);
1133
1134     {
1135         int w = p->w, h = p->h, i, j, done_any, max;
1136         unsigned char *matrix, *workspace;
1137         int *rowdata;
1138
1139         matrix = snewn(w*h, unsigned char);
1140         max = max(w, h);
1141         workspace = snewn(max*3, unsigned char);
1142         rowdata = snewn(max+1, int);
1143
1144         memset(matrix, 0, w*h);
1145
1146         do {
1147             done_any = 0;
1148             for (i=0; i<h; i++) {
1149                 memcpy(rowdata, s->rowdata + s->rowsize*(w+i),
1150                        max*sizeof(int));
1151                 rowdata[s->rowlen[w+i]] = 0;
1152                 done_any |= do_row(workspace, workspace+max, workspace+2*max,
1153                                    matrix+i*w, w, 1, rowdata);
1154             }
1155             for (i=0; i<w; i++) {
1156                 memcpy(rowdata, s->rowdata + s->rowsize*i, max*sizeof(int));
1157                 rowdata[s->rowlen[i]] = 0;
1158                 done_any |= do_row(workspace, workspace+max, workspace+2*max,
1159                                    matrix+i, h, w, rowdata);
1160             }
1161         } while (done_any);
1162
1163         for (i = 0; i < h; i++) {
1164             for (j = 0; j < w; j++) {
1165                 int c = (matrix[i*w+j] == UNKNOWN ? '?' :
1166                          matrix[i*w+j] == BLOCK ? '#' :
1167                          matrix[i*w+j] == DOT ? '.' :
1168                          '!');
1169                 putchar(c);
1170             }
1171             printf("\n");
1172         }
1173     }
1174
1175     return 0;
1176 }
1177
1178 #endif