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