singles.c

   1 /*
   2  * singles.c: implementation of Hitori ('let me alone') from Nikoli.
   3  *
   4  * Make single-get able to fetch a specific puzzle ID from menneske.no?
   5  *
   6  * www.menneske.no solving methods:
   7  *
   8  * Done:
   9  * SC: if you circle a cell, any cells in same row/col with same no --> black
  10  *  -- solver_op_circle
  11  * SB: if you make a cell black, any cells around it --> white
  12  *  -- solver_op_blacken
  13  * ST: 3 identical cells in row, centre is white and outer two black.
  14  * SP: 2 identical cells with single-cell gap, middle cell is white.
  15  *  -- solver_singlesep (both ST and SP)
  16  * PI: if you have a pair of same number in row/col, any other
  17  *      cells of same number must be black.
  18  *  -- solve_doubles
  19  * CC: if you have a black on edge one cell away from corner, cell
  20  *       on edge diag. adjacent must be white.
  21  * CE: if you have 2 black cells of triangle on edge, third cell must
  22  *      be white.
  23  * QM: if you have 3 black cells of diagonal square in middle, fourth
  24  *      cell must be white.
  25  *  -- solve_allblackbutone (CC, CE, and QM).
  26  * QC: a corner with 4 identical numbers (or 2 and 2) must have the
  27  *      corner cell (and cell diagonal to that) black.
  28  * TC: a corner with 3 identical numbers (with the L either way)
  29  *      must have the apex of L black, and other two white.
  30  * DC: a corner with 2 identical numbers in domino can set a white
  31  *      cell along wall.
  32  *  -- solve_corners (QC, TC, DC)
  33  * IP: pair with one-offset-pair force whites by offset pair
  34  *  -- solve_offsetpair
  35  * MC: any cells diag. adjacent to black cells that would split board
  36  *      into separate white regions must be white.
  37  *  -- solve_removesplits
  38  *
  39  * Still to do:
  40  *
  41  * TEP: 3 pairs of dominos parallel to side, can mark 4 white cells
  42  *       alongside.
  43  * DEP: 2 pairs of dominos parallel to side, can mark 2 white cells.
  44  * FI: if you have two sets of double-cells packed together, singles
  45  *      in that row/col must be white (qv. PI)
  46  * QuM: four identical cells (or 2 and 2) in middle of grid only have
  47  *       two possible solutions each.
  48  * FDE: doubles one row/column away from edge can force a white cell.
  49  * FDM: doubles in centre (next to bits of diag. square) can force a white cell.
  50  * MP: two pairs with same number between force number to black.
  51  * CnC: if circling a cell leads to impossible board, cell is black.
  52  * MC: if we have two possiblilities, can we force a white circle?
  53  *
  54  */
  55
  56 #include <stdio.h>
  57 #include <stdlib.h>
  58 #include <string.h>
  59 #include <assert.h>
  60 #include <ctype.h>
  61 #include <math.h>
  62
  63 #include "puzzles.h"
  64 #include "latin.h"
  65
  66 #ifdef STANDALONE_SOLVER
  67 int verbose = 0;
  68 #endif
  69
  70 #define PREFERRED_TILE_SIZE 32
  71 #define TILE_SIZE (ds->tilesize)
  72 #define BORDER    (TILE_SIZE / 2)
  73
  74 #define CRAD      ((TILE_SIZE / 2) - 1)
  75 #define TEXTSZ    ((14*CRAD/10) - 1) /* 2 * sqrt(2) of CRAD */
  76
  77 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  78 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  79
  80 #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
  81
  82 #define FLASH_TIME 0.7F
  83
  84 enum {
  85     COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT,
  86     COL_BLACK, COL_WHITE, COL_BLACKNUM, COL_GRID,
  87     COL_CURSOR, COL_ERROR,
  88     NCOLOURS
  89 };
  90
  91 struct game_params {
  92     int w, h, diff;
  93 };
  94
  95 #define F_BLACK         0x1
  96 #define F_CIRCLE        0x2
  97 #define F_ERROR         0x4
  98 #define F_SCRATCH       0x8
  99
 100 struct game_state {
 101     int w, h, n, o;             /* n = w*h; o = max(w, h) */
 102     int completed, used_solve, impossible;
 103     int *nums;                  /* size w*h */
 104     unsigned int *flags;        /* size w*h */
 105 };
 106
 107 /* top, right, bottom, left */
 108 static const int dxs[4] = { 0, 1, 0, -1 };
 109 static const int dys[4] = { -1, 0, 1, 0 };
 110
 111 /* --- Game parameters and preset functions --- */
 112
 113 #define DIFFLIST(A)             \
 114     A(EASY,Easy,e)              \
 115     A(TRICKY,Tricky,k)
 116
 117 #define ENUM(upper,title,lower) DIFF_ ## upper,
 118 #define TITLE(upper,title,lower) #title,
 119 #define ENCODE(upper,title,lower) #lower
 120 #define CONFIG(upper,title,lower) ":" #title
 121
 122 enum { DIFFLIST(ENUM) DIFF_MAX, DIFF_ANY };
 123 static char const *const singles_diffnames[] = { DIFFLIST(TITLE) };
 124 static char const singles_diffchars[] = DIFFLIST(ENCODE);
 125 #define DIFFCOUNT lenof(singles_diffchars)
 126 #define DIFFCONFIG DIFFLIST(CONFIG)
 127
 128 static game_params *default_params(void)
 129 {
 130     game_params *ret = snew(game_params);
 131     ret->w = ret->h = 5;
 132     ret->diff = DIFF_EASY;
 133
 134     return ret;
 135 }
 136
 137 static const struct game_params singles_presets[] = {
 138   {  5,  5, DIFF_EASY },
 139   {  5,  5, DIFF_TRICKY },
 140   {  6,  6, DIFF_EASY },
 141   {  6,  6, DIFF_TRICKY },
 142   {  8,  8, DIFF_EASY },
 143   {  8,  8, DIFF_TRICKY },
 144   { 10, 10, DIFF_EASY },
 145   { 10, 10, DIFF_TRICKY },
 146   { 12, 12, DIFF_EASY },
 147   { 12, 12, DIFF_TRICKY }
 148 };
 149
 150 static int game_fetch_preset(int i, char **name, game_params **params)
 151 {
 152     game_params *ret;
 153     char buf[80];
 154
 155     if (i < 0 || i >= lenof(singles_presets))
 156         return FALSE;
 157
 158     ret = default_params();
 159     *ret = singles_presets[i];
 160     *params = ret;
 161
 162     sprintf(buf, "%dx%d %s", ret->w, ret->h, singles_diffnames[ret->diff]);
 163     *name = dupstr(buf);
 164
 165     return TRUE;
 166 }
 167
 168 static void free_params(game_params *params)
 169 {
 170     sfree(params);
 171 }
 172
 173 static game_params *dup_params(const game_params *params)
 174 {
 175     game_params *ret = snew(game_params);
 176     *ret = *params;                    /* structure copy */
 177     return ret;
 178 }
 179
 180 static void decode_params(game_params *ret, char const *string)
 181 {
 182     char const *p = string;
 183     int i;
 184
 185     ret->w = ret->h = atoi(p);
 186     while (*p && isdigit((unsigned char)*p)) p++;
 187     if (*p == 'x') {
 188         p++;
 189         ret->h = atoi(p);
 190         while (*p && isdigit((unsigned char)*p)) p++;
 191     }
 192     if (*p == 'd') {
 193         ret->diff = DIFF_MAX; /* which is invalid */
 194         p++;
 195         for (i = 0; i < DIFFCOUNT; i++) {
 196             if (*p == singles_diffchars[i])
 197                 ret->diff = i;
 198         }
 199         p++;
 200     }
 201 }
 202
 203 static char *encode_params(const game_params *params, int full)
 204 {
 205     char data[256];
 206
 207     if (full)
 208         sprintf(data, "%dx%dd%c", params->w, params->h, singles_diffchars[params->diff]);
 209     else
 210         sprintf(data, "%dx%d", params->w, params->h);
 211
 212     return dupstr(data);
 213 }
 214
 215 static config_item *game_configure(const game_params *params)
 216 {
 217     config_item *ret;
 218     char buf[80];
 219
 220     ret = snewn(4, config_item);
 221
 222     ret[0].name = "Width";
 223     ret[0].type = C_STRING;
 224     sprintf(buf, "%d", params->w);
 225     ret[0].sval = dupstr(buf);
 226     ret[0].ival = 0;
 227
 228     ret[1].name = "Height";
 229     ret[1].type = C_STRING;
 230     sprintf(buf, "%d", params->h);
 231     ret[1].sval = dupstr(buf);
 232     ret[1].ival = 0;
 233
 234     ret[2].name = "Difficulty";
 235     ret[2].type = C_CHOICES;
 236     ret[2].sval = DIFFCONFIG;
 237     ret[2].ival = params->diff;
 238
 239     ret[3].name = NULL;
 240     ret[3].type = C_END;
 241     ret[3].sval = NULL;
 242     ret[3].ival = 0;
 243
 244     return ret;
 245 }
 246
 247 static game_params *custom_params(const config_item *cfg)
 248 {
 249     game_params *ret = snew(game_params);
 250
 251     ret->w = atoi(cfg[0].sval);
 252     ret->h = atoi(cfg[1].sval);
 253     ret->diff = cfg[2].ival;
 254
 255     return ret;
 256 }
 257
 258 static char *validate_params(const game_params *params, int full)
 259 {
 260     if (params->w < 2 || params->h < 2)
 261         return "Width and neight must be at least two";
 262     if (params->w > 10+26+26 || params->h > 10+26+26)
 263         return "Puzzle is too large";
 264     if (full) {
 265         if (params->diff < 0 || params->diff >= DIFF_MAX)
 266             return "Unknown difficulty rating";
 267     }
 268
 269     return NULL;
 270 }
 271
 272 /* --- Game description string generation and unpicking --- */
 273
 274 static game_state *blank_game(int w, int h)
 275 {
 276     game_state *state = snew(game_state);
 277
 278     memset(state, 0, sizeof(game_state));
 279     state->w = w;
 280     state->h = h;
 281     state->n = w*h;
 282     state->o = max(w,h);
 283
 284     state->completed = state->used_solve = state->impossible = 0;
 285
 286     state->nums  = snewn(state->n, int);
 287     state->flags = snewn(state->n, unsigned int);
 288
 289     memset(state->nums, 0, state->n*sizeof(int));
 290     memset(state->flags, 0, state->n*sizeof(unsigned int));
 291
 292     return state;
 293 }
 294
 295 static game_state *dup_game(const game_state *state)
 296 {
 297     game_state *ret = blank_game(state->w, state->h);
 298
 299     ret->completed = state->completed;
 300     ret->used_solve = state->used_solve;
 301     ret->impossible = state->impossible;
 302
 303     memcpy(ret->nums, state->nums, state->n*sizeof(int));
 304     memcpy(ret->flags, state->flags, state->n*sizeof(unsigned int));
 305
 306     return ret;
 307 }
 308
 309 static void free_game(game_state *state)
 310 {
 311     sfree(state->nums);
 312     sfree(state->flags);
 313     sfree(state);
 314 }
 315
 316 static char n2c(int num) {
 317     if (num < 10)
 318         return '0' + num;
 319     else if (num < 10+26)
 320         return 'a' + num - 10;
 321     else
 322         return 'A' + num - 10 - 26;
 323     return '?';
 324 }
 325
 326 static int c2n(char c) {
 327     if (isdigit((unsigned char)c))
 328         return (int)(c - '0');
 329     else if (c >= 'a' && c <= 'z')
 330         return (int)(c - 'a' + 10);
 331     else if (c >= 'A' && c <= 'Z')
 332         return (int)(c - 'A' + 10 + 26);
 333     return -1;
 334 }
 335
 336 static void unpick_desc(const game_params *params, const char *desc,
 337                         game_state **sout, char **mout)
 338 {
 339     game_state *state = blank_game(params->w, params->h);
 340     char *msg = NULL;
 341     int num = 0, i = 0;
 342
 343     if (strlen(desc) != state->n) {
 344         msg = "Game description is wrong length";
 345         goto done;
 346     }
 347     for (i = 0; i < state->n; i++) {
 348         num = c2n(desc[i]);
 349         if (num <= 0 || num > state->o) {
 350             msg = "Game description contains unexpected characters";
 351             goto done;
 352         }
 353         state->nums[i] = num;
 354     }
 355 done:
 356     if (msg) { /* sth went wrong. */
 357         if (mout) *mout = msg;
 358         free_game(state);
 359     } else {
 360         if (mout) *mout = NULL;
 361         if (sout) *sout = state;
 362         else free_game(state);
 363     }
 364 }
 365
 366 static char *generate_desc(game_state *state, int issolve)
 367 {
 368     char *ret = snewn(state->n+1+(issolve?1:0), char);
 369     int i, p=0;
 370
 371     if (issolve)
 372         ret[p++] = 'S';
 373     for (i = 0; i < state->n; i++)
 374         ret[p++] = n2c(state->nums[i]);
 375     ret[p] = '\0';
 376     return ret;
 377 }
 378
 379 /* --- Useful game functions (completion, etc.) --- */
 380
 381 static int game_can_format_as_text_now(const game_params *params)
 382 {
 383     return TRUE;
 384 }
 385
 386 static char *game_text_format(const game_state *state)
 387 {
 388     int len, x, y, i;
 389     char *ret, *p;
 390
 391     len = (state->w)*2;       /* one row ... */
 392     len = len * (state->h*2); /* ... h rows, including gaps ... */
 393     len += 1;              /* ... final NL */
 394     p = ret = snewn(len, char);
 395
 396     for (y = 0; y < state->h; y++) {
 397         for (x = 0; x < state->w; x++) {
 398             i = y*state->w + x;
 399             if (x > 0) *p++ = ' ';
 400             *p++ = (state->flags[i] & F_BLACK) ? '*' : n2c(state->nums[i]);
 401         }
 402         *p++ = '\n';
 403         for (x = 0; x < state->w; x++) {
 404             i = y*state->w + x;
 405             if (x > 0) *p++ = ' ';
 406             *p++ = (state->flags[i] & F_CIRCLE) ? '~' : ' ';
 407         }
 408         *p++ = '\n';
 409     }
 410     *p++ = '\0';
 411     assert(p - ret == len);
 412
 413     return ret;
 414 }
 415
 416 static void debug_state(const char *desc, game_state *state) {
 417     char *dbg = game_text_format(state);
 418     debug(("%s:\n%s", desc, dbg));
 419     sfree(dbg);
 420 }
 421
 422 static void connect_if_same(game_state *state, int *dsf, int i1, int i2)
 423 {
 424     int c1, c2;
 425
 426     if ((state->flags[i1] & F_BLACK) != (state->flags[i2] & F_BLACK))
 427         return;
 428
 429     c1 = dsf_canonify(dsf, i1);
 430     c2 = dsf_canonify(dsf, i2);
 431     dsf_merge(dsf, c1, c2);
 432 }
 433
 434 static void connect_dsf(game_state *state, int *dsf)
 435 {
 436     int x, y, i;
 437
 438     /* Construct a dsf array for connected blocks; connections
 439      * tracked to right and down. */
 440     dsf_init(dsf, state->n);
 441     for (x = 0; x < state->w; x++) {
 442         for (y = 0; y < state->h; y++) {
 443             i = y*state->w + x;
 444
 445             if (x < state->w-1)
 446                 connect_if_same(state, dsf, i, i+1); /* right */
 447             if (y < state->h-1)
 448                 connect_if_same(state, dsf, i, i+state->w); /* down */
 449         }
 450     }
 451 }
 452
 453 #define CC_MARK_ERRORS  1
 454 #define CC_MUST_FILL    2
 455
 456 static int check_rowcol(game_state *state, int starti, int di, int sz, unsigned flags)
 457 {
 458     int nerr = 0, n, m, i, j;
 459
 460     /* if any circled numbers have identical non-circled numbers on
 461      *     same row/column, error (non-circled)
 462      * if any circled numbers in same column are same number, highlight them.
 463      * if any rows/columns have >1 of same number, not complete. */
 464
 465     for (n = 0, i = starti; n < sz; n++, i += di) {
 466         if (state->flags[i] & F_BLACK) continue;
 467         for (m = n+1, j = i+di; m < sz; m++, j += di) {
 468             if (state->flags[j] & F_BLACK) continue;
 469             if (state->nums[i] != state->nums[j]) continue;
 470
 471             nerr++; /* ok, we have two numbers the same in a row. */
 472             if (!(flags & CC_MARK_ERRORS)) continue;
 473
 474             /* If we have two circles in the same row around
 475              * two identical numbers, they are _both_ wrong. */
 476             if ((state->flags[i] & F_CIRCLE) &&
 477                 (state->flags[j] & F_CIRCLE)) {
 478                 state->flags[i] |= F_ERROR;
 479                 state->flags[j] |= F_ERROR;
 480             }
 481             /* Otherwise, if we have a circle, any other identical
 482              * numbers in that row are obviously wrong. We don't
 483              * highlight this, however, since it makes the process
 484              * of solving the puzzle too easy (you circle a number
 485              * and it promptly tells you which numbers to blacken! */
 486 #if 0
 487             else if (state->flags[i] & F_CIRCLE)
 488                 state->flags[j] |= F_ERROR;
 489             else if (state->flags[j] & F_CIRCLE)
 490                 state->flags[i] |= F_ERROR;
 491 #endif
 492         }
 493     }
 494     return nerr;
 495 }
 496
 497 static int check_complete(game_state *state, unsigned flags)
 498 {
 499     int *dsf = snewn(state->n, int);
 500     int x, y, i, error = 0, nwhite, w = state->w, h = state->h;
 501
 502     if (flags & CC_MARK_ERRORS) {
 503         for (i = 0; i < state->n; i++)
 504             state->flags[i] &= ~F_ERROR;
 505     }
 506     connect_dsf(state, dsf);
 507
 508     /* If we're the solver we need the grid all to be definitively
 509      * black or definitively white (i.e. circled) otherwise the solver
 510      * has found an ambiguous grid. */
 511     if (flags & CC_MUST_FILL) {
 512         for (i = 0; i < state->n; i++) {
 513             if (!(state->flags[i] & F_BLACK) && !(state->flags[i] & F_CIRCLE))
 514                 error += 1;
 515         }
 516     }
 517
 518     /* Mark any black squares in groups of >1 as errors.
 519      * Count number of white squares. */
 520     nwhite = 0;
 521     for (i = 0; i < state->n; i++) {
 522         if (state->flags[i] & F_BLACK) {
 523             if (dsf_size(dsf, i) > 1) {
 524                 error += 1;
 525                 if (flags & CC_MARK_ERRORS)
 526                     state->flags[i] |= F_ERROR;
 527             }
 528         } else
 529             nwhite += 1;
 530     }
 531
 532     /* Check attributes of white squares, row- and column-wise. */
 533     for (x = 0; x < w; x++) /* check cols from (x,0) */
 534         error += check_rowcol(state, x,   w, h, flags);
 535     for (y = 0; y < h; y++) /* check rows from (0,y) */
 536         error += check_rowcol(state, y*w, 1, w, flags);
 537
 538     /* mark (all) white regions as an error if there is more than one.
 539      * may want to make this less in-your-face (by only marking
 540      * the smallest region as an error, for example -- but what if we
 541      * have two regions of identical size?) */
 542     for (i = 0; i < state->n; i++) {
 543         if (!(state->flags[i] & F_BLACK) &&
 544             dsf_size(dsf, i) < nwhite) {
 545             error += 1;
 546             if (flags & CC_MARK_ERRORS)
 547                 state->flags[i] |= F_ERROR;
 548         }
 549     }
 550
 551     sfree(dsf);
 552     return (error > 0) ? 0 : 1;
 553 }
 554
 555 static char *game_state_diff(const game_state *src, const game_state *dst,
 556                              int issolve)
 557 {
 558     char *ret = NULL, buf[80], c;
 559     int retlen = 0, x, y, i, k;
 560     unsigned int fmask = F_BLACK | F_CIRCLE;
 561
 562     assert(src->n == dst->n);
 563
 564     if (issolve) {
 565         ret = sresize(ret, 3, char);
 566         ret[0] = 'S'; ret[1] = ';'; ret[2] = '\0';
 567         retlen += 2;
 568     }
 569
 570     for (x = 0; x < dst->w; x++) {
 571         for (y = 0; y < dst->h; y++) {
 572             i = y*dst->w + x;
 573             if ((src->flags[i] & fmask) != (dst->flags[i] & fmask)) {
 574                 assert((dst->flags[i] & fmask) != fmask);
 575                 if (dst->flags[i] & F_BLACK)
 576                     c = 'B';
 577                 else if (dst->flags[i] & F_CIRCLE)
 578                     c = 'C';
 579                 else
 580                     c = 'E';
 581                 k = sprintf(buf, "%c%d,%d;", (int)c, x, y);
 582                 ret = sresize(ret, retlen + k + 1, char);
 583                 strcpy(ret + retlen, buf);
 584                 retlen += k;
 585             }
 586         }
 587     }
 588     return ret;
 589 }
 590
 591 /* --- Solver --- */
 592
 593 enum { BLACK, CIRCLE };
 594
 595 struct solver_op {
 596     int x, y, op; /* op one of BLACK or CIRCLE. */
 597     const char *desc; /* must be non-malloced. */
 598 };
 599
 600 struct solver_state {
 601     struct solver_op *ops;
 602     int n_ops, n_alloc;
 603     int *scratch;
 604 };
 605
 606 static struct solver_state *solver_state_new(game_state *state)
 607 {
 608     struct solver_state *ss = snew(struct solver_state);
 609
 610     ss->ops = NULL;
 611     ss->n_ops = ss->n_alloc = 0;
 612     ss->scratch = snewn(state->n, int);
 613
 614     return ss;
 615 }
 616
 617 static void solver_state_free(struct solver_state *ss)
 618 {
 619     sfree(ss->scratch);
 620     if (ss->ops) sfree(ss->ops);
 621     sfree(ss);
 622 }
 623
 624 static void solver_op_add(struct solver_state *ss, int x, int y, int op, const char *desc)
 625 {
 626     struct solver_op *sop;
 627
 628     if (ss->n_alloc < ss->n_ops + 1) {
 629         ss->n_alloc = (ss->n_alloc + 1) * 2;
 630         ss->ops = sresize(ss->ops, ss->n_alloc, struct solver_op);
 631     }
 632     sop = &(ss->ops[ss->n_ops++]);
 633     sop->x = x; sop->y = y; sop->op = op; sop->desc = desc;
 634     debug(("added solver op %s ('%s') at (%d,%d)\n",
 635            op == BLACK ? "BLACK" : "CIRCLE", desc, x, y));
 636 }
 637
 638 static void solver_op_circle(game_state *state, struct solver_state *ss,
 639                              int x, int y)
 640 {
 641     int i = y*state->w + x;
 642
 643     if (!INGRID(state, x, y)) return;
 644     if (state->flags[i] & F_BLACK) {
 645         debug(("... solver wants to add auto-circle on black (%d,%d)\n", x, y));
 646         state->impossible = 1;
 647         return;
 648     }
 649     /* Only add circle op if it's not already circled. */
 650     if (!(state->flags[i] & F_CIRCLE)) {
 651         solver_op_add(ss, x, y, CIRCLE, "SB - adjacent to black square");
 652     }
 653 }
 654
 655 static void solver_op_blacken(game_state *state, struct solver_state *ss,
 656                               int x, int y, int num)
 657 {
 658     int i = y*state->w + x;
 659
 660     if (!INGRID(state, x, y)) return;
 661     if (state->nums[i] != num) return;
 662     if (state->flags[i] & F_CIRCLE) {
 663         debug(("... solver wants to add auto-black on circled(%d,%d)\n", x, y));
 664         state->impossible = 1;
 665         return;
 666     }
 667     /* Only add black op if it's not already black. */
 668     if (!(state->flags[i] & F_BLACK)) {
 669         solver_op_add(ss, x, y, BLACK, "SC - number on same row/col as circled");
 670     }
 671 }
 672
 673 static int solver_ops_do(game_state *state, struct solver_state *ss)
 674 {
 675     int next_op = 0, i, x, y, n_ops = 0;
 676     struct solver_op op;
 677
 678     /* Care here: solver_op_* may call solver_op_add which may extend the
 679      * ss->n_ops. */
 680
 681     while (next_op < ss->n_ops) {
 682         op = ss->ops[next_op++]; /* copy this away, it may get reallocated. */
 683         i = op.y*state->w + op.x;
 684
 685         if (op.op == BLACK) {
 686             if (state->flags[i] & F_CIRCLE) {
 687                 debug(("Solver wants to blacken circled square (%d,%d)!\n", op.x, op.y));
 688                 state->impossible = 1;
 689                 return n_ops;
 690             }
 691             if (!(state->flags[i] & F_BLACK)) {
 692                 debug(("... solver adding black at (%d,%d): %s\n", op.x, op.y, op.desc));
 693 #ifdef STANDALONE_SOLVER
 694                 if (verbose)
 695                     printf("Adding black at (%d,%d): %s\n", op.x, op.y, op.desc);
 696 #endif
 697                 state->flags[i] |= F_BLACK;
 698                 /*debug_state("State after adding black", state);*/
 699                 n_ops++;
 700                 solver_op_circle(state, ss, op.x-1, op.y);
 701                 solver_op_circle(state, ss, op.x+1, op.y);
 702                 solver_op_circle(state, ss, op.x,   op.y-1);
 703                 solver_op_circle(state, ss, op.x,   op.y+1);
 704                 }
 705         } else {
 706             if (state->flags[i] & F_BLACK) {
 707                 debug(("Solver wants to circle blackened square (%d,%d)!\n", op.x, op.y));
 708                 state->impossible = 1;
 709                 return n_ops;
 710             }
 711             if (!(state->flags[i] & F_CIRCLE)) {
 712                 debug(("... solver adding circle at (%d,%d): %s\n", op.x, op.y, op.desc));
 713 #ifdef STANDALONE_SOLVER
 714                 if (verbose)
 715                     printf("Adding circle at (%d,%d): %s\n", op.x, op.y, op.desc);
 716 #endif
 717                 state->flags[i] |= F_CIRCLE;
 718                 /*debug_state("State after adding circle", state);*/
 719                 n_ops++;
 720                 for (x = 0; x < state->w; x++) {
 721                     if (x != op.x)
 722                         solver_op_blacken(state, ss, x, op.y, state->nums[i]);
 723                 }
 724                 for (y = 0; y < state->h; y++) {
 725                     if (y != op.y)
 726                         solver_op_blacken(state, ss, op.x, y, state->nums[i]);
 727                 }
 728             }
 729         }
 730     }
 731     ss->n_ops = 0;
 732     return n_ops;
 733 }
 734
 735 /* If the grid has two identical numbers with one cell between them, the inner
 736  * cell _must_ be white (and thus circled); (at least) one of the two must be
 737  * black (since they're in the same column or row) and thus the middle cell is
 738  * next to a black cell. */
 739 static int solve_singlesep(game_state *state, struct solver_state *ss)
 740 {
 741     int x, y, i, ir, irr, id, idd, n_ops = ss->n_ops;
 742
 743     for (x = 0; x < state->w; x++) {
 744         for (y = 0; y < state->h; y++) {
 745             i = y*state->w + x;
 746
 747             /* Cell two to our right? */
 748             ir = i + 1; irr = ir + 1;
 749             if (x < (state->w-2) &&
 750                 state->nums[i] == state->nums[irr] &&
 751                 !(state->flags[ir] & F_CIRCLE)) {
 752                 solver_op_add(ss, x+1, y, CIRCLE, "SP/ST - between identical nums");
 753             }
 754             /* Cell two below us? */
 755             id = i + state->w; idd = id + state->w;
 756             if (y < (state->h-2) &&
 757                 state->nums[i] == state->nums[idd] &&
 758                 !(state->flags[id] & F_CIRCLE)) {
 759                 solver_op_add(ss, x, y+1, CIRCLE, "SP/ST - between identical nums");
 760             }
 761         }
 762     }
 763     return ss->n_ops - n_ops;
 764 }
 765
 766 /* If we have two identical numbers next to each other (in a row or column),
 767  * any other identical numbers in that column must be black. */
 768 static int solve_doubles(game_state *state, struct solver_state *ss)
 769 {
 770     int x, y, i, ii, n_ops = ss->n_ops, xy;
 771
 772     for (y = 0, i = 0; y < state->h; y++) {
 773         for (x = 0; x < state->w; x++, i++) {
 774             assert(i == y*state->w+x);
 775             if (state->flags[i] & F_BLACK) continue;
 776
 777             ii = i+1; /* check cell to our right. */
 778             if (x < (state->w-1) &&
 779                 !(state->flags[ii] & F_BLACK) &&
 780                 state->nums[i] == state->nums[ii]) {
 781                 for (xy = 0; xy < state->w; xy++) {
 782                     if (xy == x || xy == (x+1)) continue;
 783                     if (state->nums[y*state->w + xy] == state->nums[i] &&
 784                         !(state->flags[y*state->w + xy] & F_BLACK))
 785                         solver_op_add(ss, xy, y, BLACK, "PI - same row as pair");
 786                 }
 787             }
 788
 789             ii = i+state->w; /* check cell below us */
 790             if (y < (state->h-1) &&
 791                 !(state->flags[ii] & F_BLACK) &&
 792                 state->nums[i] == state->nums[ii]) {
 793                 for (xy = 0; xy < state->h; xy++) {
 794                     if (xy == y || xy == (y+1)) continue;
 795                     if (state->nums[xy*state->w + x] == state->nums[i] &&
 796                         !(state->flags[xy*state->w + x] & F_BLACK))
 797                         solver_op_add(ss, x, xy, BLACK, "PI - same col as pair");
 798                 }
 799             }
 800         }
 801     }
 802     return ss->n_ops - n_ops;
 803 }
 804
 805 /* If a white square has all-but-one possible adjacent squares black, the
 806  * one square left over must be white. */
 807 static int solve_allblackbutone(game_state *state, struct solver_state *ss)
 808 {
 809     int x, y, i, n_ops = ss->n_ops, xd, yd, id, ifree;
 810     int dis[4], d;
 811
 812     dis[0] = -state->w;
 813     dis[1] = 1;
 814     dis[2] = state->w;
 815     dis[3] = -1;
 816
 817     for (y = 0, i = 0; y < state->h; y++) {
 818         for (x = 0; x < state->w; x++, i++) {
 819             assert(i == y*state->w+x);
 820             if (state->flags[i] & F_BLACK) continue;
 821
 822             ifree = -1;
 823             for (d = 0; d < 4; d++) {
 824                 xd = x + dxs[d]; yd = y + dys[d]; id = i + dis[d];
 825                 if (!INGRID(state, xd, yd)) continue;
 826
 827                 if (state->flags[id] & F_CIRCLE)
 828                     goto skip; /* this cell already has a way out */
 829                 if (!(state->flags[id] & F_BLACK)) {
 830                     if (ifree != -1)
 831                         goto skip; /* this cell has >1 white cell around it. */
 832                     ifree = id;
 833                 }
 834             }
 835             if (ifree != -1)
 836                 solver_op_add(ss, ifree%state->w, ifree/state->w, CIRCLE,
 837                               "CC/CE/QM: white cell with single non-black around it");
 838             else {
 839                 debug(("White cell with no escape at (%d,%d)\n", x, y));
 840                 state->impossible = 1;
 841                 return 0;
 842             }
 843 skip: ;
 844         }
 845     }
 846     return ss->n_ops - n_ops;
 847 }
 848
 849 /* If we have 4 numbers the same in a 2x2 corner, the far corner and the
 850  * diagonally-adjacent square must both be black.
 851  * If we have 3 numbers the same in a 2x2 corner, the apex of the L
 852  * thus formed must be black.
 853  * If we have 2 numbers the same in a 2x2 corner, the non-same cell
 854  * one away from the corner must be white. */
 855 static void solve_corner(game_state *state, struct solver_state *ss,
 856                         int x, int y, int dx, int dy)
 857 {
 858     int is[4], ns[4], xx, yy, w = state->w;
 859
 860     for (yy = 0; yy < 2; yy++) {
 861         for (xx = 0; xx < 2; xx++) {
 862             is[yy*2+xx] = (y + dy*yy) * w + (x + dx*xx);
 863             ns[yy*2+xx] = state->nums[is[yy*2+xx]];
 864         }
 865     } /* order is now (corner, side 1, side 2, inner) */
 866
 867     if (ns[0] == ns[1] && ns[0] == ns[2] && ns[0] == ns[3]) {
 868         solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "QC: corner with 4 matching");
 869         solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "QC: corner with 4 matching");
 870     } else if (ns[0] == ns[1] && ns[0] == ns[2]) {
 871         /* corner and 2 sides: apex is corner. */
 872         solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "TC: corner apex from 3 matching");
 873     } else if (ns[1] == ns[2] && ns[1] == ns[3]) {
 874         /* side, side, fourth: apex is fourth. */
 875         solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "TC: inside apex from 3 matching");
 876     } else if (ns[0] == ns[1] || ns[1] == ns[3]) {
 877         /* either way here we match the non-identical side. */
 878         solver_op_add(ss, is[2]%w, is[2]/w, CIRCLE, "DC: corner with 2 matching");
 879     } else if (ns[0] == ns[2] || ns[2] == ns[3]) {
 880         /* ditto */
 881         solver_op_add(ss, is[1]%w, is[1]/w, CIRCLE, "DC: corner with 2 matching");
 882     }
 883 }
 884
 885 static int solve_corners(game_state *state, struct solver_state *ss)
 886 {
 887     int n_ops = ss->n_ops;
 888
 889     solve_corner(state, ss, 0,          0,           1,  1);
 890     solve_corner(state, ss, state->w-1, 0,          -1,  1);
 891     solve_corner(state, ss, state->w-1, state->h-1, -1, -1);
 892     solve_corner(state, ss, 0,          state->h-1,  1, -1);
 893
 894     return ss->n_ops - n_ops;
 895 }
 896
 897 /* If you have the following situation:
 898  * ...
 899  * ...x A x x y A x...
 900  * ...x B x x B y x...
 901  * ...
 902  * then both squares marked 'y' must be white. One of the left-most A or B must
 903  * be white (since two side-by-side black cells are disallowed), which means
 904  * that the corresponding right-most A or B must be black (since you can't
 905  * have two of the same number on one line); thus, the adjacent squares
 906  * to that right-most A or B must be white, which include the two marked 'y'
 907  * in either case.
 908  * Obviously this works in any row or column. It also works if A == B.
 909  * It doesn't work for the degenerate case:
 910  * ...x A A x x
 911  * ...x B y x x
 912  * where the square marked 'y' isn't necessarily white (consider the left-most A
 913  * is black).
 914  *
 915  * */
 916 static void solve_offsetpair_pair(game_state *state, struct solver_state *ss,
 917                                   int x1, int y1, int x2, int y2)
 918 {
 919     int ox, oy, w = state->w, ax, ay, an, d, dx[2], dy[2], dn, xd, yd;
 920
 921     if (x1 == x2) { /* same column */
 922         ox = 1; oy = 0;
 923     } else {
 924         assert(y1 == y2);
 925         ox = 0; oy = 1;
 926     }
 927
 928     /* We try adjacent to (x1,y1) and the two diag. adjacent to (x2, y2).
 929      * We expect to be called twice, once each way around. */
 930     ax = x1+ox; ay = y1+oy;
 931     assert(INGRID(state, ax, ay));
 932     an = state->nums[ay*w + ax];
 933
 934     dx[0] = x2 + ox + oy; dx[1] = x2 + ox - oy;
 935     dy[0] = y2 + oy + ox; dy[1] = y2 + oy - ox;
 936
 937     for (d = 0; d < 2; d++) {
 938         if (INGRID(state, dx[d], dy[d]) && (dx[d] != ax || dy[d] != ay)) {
 939             /* The 'dx != ax || dy != ay' removes the degenerate case,
 940              * mentioned above. */
 941             dn = state->nums[dy[d]*w + dx[d]];
 942             if (an == dn) {
 943                 /* We have a match; so (WLOG) the 'A' marked above are at
 944                  * (x1,y1) and (x2,y2), and the 'B' are at (ax,ay) and (dx,dy). */
 945                 debug(("Found offset-pair: %d at (%d,%d) and (%d,%d)\n",
 946                        state->nums[y1*w + x1], x1, y1, x2, y2));
 947                 debug(("              and: %d at (%d,%d) and (%d,%d)\n",
 948                        an, ax, ay, dx[d], dy[d]));
 949
 950                 xd = dx[d] - x2; yd = dy[d] - y2;
 951                 solver_op_add(ss, x2 + xd, y2, CIRCLE, "IP: next to offset-pair");
 952                 solver_op_add(ss, x2, y2 + yd, CIRCLE, "IP: next to offset-pair");
 953             }
 954         }
 955     }
 956 }
 957
 958 static int solve_offsetpair(game_state *state, struct solver_state *ss)
 959 {
 960     int n_ops = ss->n_ops, x, xx, y, yy, n1, n2;
 961
 962     for (x = 0; x < state->w-1; x++) {
 963         for (y = 0; y < state->h; y++) {
 964             n1 = state->nums[y*state->w + x];
 965             for (yy = y+1; yy < state->h; yy++) {
 966                 n2 = state->nums[yy*state->w + x];
 967                 if (n1 == n2) {
 968                     solve_offsetpair_pair(state, ss, x,  y, x, yy);
 969                     solve_offsetpair_pair(state, ss, x, yy, x,  y);
 970                 }
 971             }
 972         }
 973     }
 974     for (y = 0; y < state->h-1; y++) {
 975         for (x = 0; x < state->w; x++) {
 976             n1 = state->nums[y*state->w + x];
 977             for (xx = x+1; xx < state->w; xx++) {
 978                 n2 = state->nums[y*state->w + xx];
 979                 if (n1 == n2) {
 980                     solve_offsetpair_pair(state, ss, x,  y, xx, y);
 981                     solve_offsetpair_pair(state, ss, xx, y,  x, y);
 982                 }
 983             }
 984         }
 985     }
 986     return ss->n_ops - n_ops;
 987 }
 988
 989 static int solve_hassinglewhiteregion(game_state *state, struct solver_state *ss)
 990 {
 991     int i, j, nwhite = 0, lwhite = -1, szwhite, start, end, next, a, d, x, y;
 992
 993     for (i = 0; i < state->n; i++) {
 994         if (!(state->flags[i] & F_BLACK)) {
 995             nwhite++;
 996             lwhite = i;
 997         }
 998         state->flags[i] &= ~F_SCRATCH;
 999     }
1000     if (lwhite == -1) {
1001         debug(("solve_hassinglewhite: no white squares found!\n"));
1002         state->impossible = 1;
1003         return 0;
1004     }
1005     /* We don't use connect_dsf here; it's too slow, and there's a quicker
1006      * algorithm if all we want is the size of one region. */
1007     /* Having written this, this algorithm is only about 5% faster than
1008      * using a dsf. */
1009     memset(ss->scratch, -1, state->n * sizeof(int));
1010     ss->scratch[0] = lwhite;
1011     state->flags[lwhite] |= F_SCRATCH;
1012     start = 0; end = next = 1;
1013     while (start < end) {
1014         for (a = start; a < end; a++) {
1015             i = ss->scratch[a]; assert(i != -1);
1016             for (d = 0; d < 4; d++) {
1017                 x = (i % state->w) + dxs[d];
1018                 y = (i / state->w) + dys[d];
1019                 j = y*state->w + x;
1020                 if (!INGRID(state, x, y)) continue;
1021                 if (state->flags[j] & (F_BLACK | F_SCRATCH)) continue;
1022                 ss->scratch[next++] = j;
1023                 state->flags[j] |= F_SCRATCH;
1024             }
1025         }
1026         start = end; end = next;
1027     }
1028     szwhite = next;
1029     return (szwhite == nwhite) ? 1 : 0;
1030 }
1031
1032 static void solve_removesplits_check(game_state *state, struct solver_state *ss,
1033                                      int x, int y)
1034 {
1035     int i = y*state->w + x, issingle;
1036
1037     if (!INGRID(state, x, y)) return;
1038     if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK))
1039         return;
1040
1041     /* If putting a black square at (x,y) would make the white region
1042      * non-contiguous, it must be circled. */
1043     state->flags[i] |= F_BLACK;
1044     issingle = solve_hassinglewhiteregion(state, ss);
1045     state->flags[i] &= ~F_BLACK;
1046
1047     if (!issingle)
1048         solver_op_add(ss, x, y, CIRCLE, "MC: black square here would split white region");
1049 }
1050
1051 /* For all black squares, search in squares diagonally adjacent to see if
1052  * we can rule out putting a black square there (because it would make the
1053  * white region non-contiguous). */
1054 /* This function is likely to be somewhat slow. */
1055 static int solve_removesplits(game_state *state, struct solver_state *ss)
1056 {
1057     int i, x, y, n_ops = ss->n_ops;
1058
1059     if (!solve_hassinglewhiteregion(state, ss)) {
1060         debug(("solve_removesplits: white region is not contiguous at start!\n"));
1061         state->impossible = 1;
1062         return 0;
1063     }
1064
1065     for (i = 0; i < state->n; i++) {
1066         if (!(state->flags[i] & F_BLACK)) continue;
1067
1068         x = i%state->w; y = i/state->w;
1069         solve_removesplits_check(state, ss, x-1, y-1);
1070         solve_removesplits_check(state, ss, x+1, y-1);
1071         solve_removesplits_check(state, ss, x+1, y+1);
1072         solve_removesplits_check(state, ss, x-1, y+1);
1073     }
1074     return ss->n_ops - n_ops;
1075 }
1076
1077 /*
1078  * This function performs a solver step that isn't implicit in the rules
1079  * of the game and is thus treated somewhat differently.
1080  *
1081  * It marks cells whose number does not exist elsewhere in its row/column
1082  * with circles. As it happens the game generator here does mean that this
1083  * is always correct, but it's a solving method that people should not have
1084  * to rely upon (except in the hidden 'sneaky' difficulty setting) and so
1085  * all grids at 'tricky' and above are checked to make sure that the grid
1086  * is no easier if this solving step is performed beforehand.
1087  *
1088  * Calling with ss=NULL just returns the number of sneaky deductions that
1089  * would have been made.
1090  */
1091 static int solve_sneaky(game_state *state, struct solver_state *ss)
1092 {
1093     int i, ii, x, xx, y, yy, nunique = 0;
1094
1095     /* Clear SCRATCH flags. */
1096     for (i = 0; i < state->n; i++) state->flags[i] &= ~F_SCRATCH;
1097
1098     for (x = 0; x < state->w; x++) {
1099         for (y = 0; y < state->h; y++) {
1100             i = y*state->w + x;
1101
1102             /* Check for duplicate numbers on our row, mark (both) if so */
1103             for (xx = x; xx < state->w; xx++) {
1104                 ii = y*state->w + xx;
1105                 if (i == ii) continue;
1106
1107                 if (state->nums[i] == state->nums[ii]) {
1108                     state->flags[i] |= F_SCRATCH;
1109                     state->flags[ii] |= F_SCRATCH;
1110                 }
1111             }
1112
1113             /* Check for duplicate numbers on our col, mark (both) if so */
1114             for (yy = y; yy < state->h; yy++) {
1115                 ii = yy*state->w + x;
1116                 if (i == ii) continue;
1117
1118                 if (state->nums[i] == state->nums[ii]) {
1119                     state->flags[i] |= F_SCRATCH;
1120                     state->flags[ii] |= F_SCRATCH;
1121                 }
1122             }
1123         }
1124     }
1125
1126     /* Any cell with no marking has no duplicates on its row or column:
1127      * set its CIRCLE. */
1128     for (i = 0; i < state->n; i++) {
1129         if (!(state->flags[i] & F_SCRATCH)) {
1130             if (ss) solver_op_add(ss, i%state->w, i/state->w, CIRCLE,
1131                                   "SNEAKY: only one of its number in row and col");
1132             nunique += 1;
1133         } else
1134             state->flags[i] &= ~F_SCRATCH;
1135     }
1136     return nunique;
1137 }
1138
1139 static int solve_specific(game_state *state, int diff, int sneaky)
1140 {
1141     struct solver_state *ss = solver_state_new(state);
1142
1143     if (sneaky) solve_sneaky(state, ss);
1144
1145     /* Some solver operations we only have to perform once --
1146      * they're only based on the numbers available, and not black
1147      * squares or circles which may be added later. */
1148
1149     solve_singlesep(state, ss);        /* never sets impossible */
1150     solve_doubles(state, ss);          /* ditto */
1151     solve_corners(state, ss);          /* ditto */
1152
1153     if (diff >= DIFF_TRICKY)
1154         solve_offsetpair(state, ss);       /* ditto */
1155
1156     while (1) {
1157         if (ss->n_ops > 0) solver_ops_do(state, ss);
1158         if (state->impossible) break;
1159
1160         if (solve_allblackbutone(state, ss) > 0) continue;
1161         if (state->impossible) break;
1162
1163         if (diff >= DIFF_TRICKY) {
1164             if (solve_removesplits(state, ss) > 0) continue;
1165             if (state->impossible) break;
1166         }
1167
1168         break;
1169     }
1170
1171     solver_state_free(ss);
1172     return state->impossible ? -1 : check_complete(state, CC_MUST_FILL);
1173 }
1174
1175 static char *solve_game(const game_state *state, const game_state *currstate,
1176                         const char *aux, char **error)
1177 {
1178     game_state *solved = dup_game(currstate);
1179     char *move = NULL;
1180
1181     if (solve_specific(solved, DIFF_ANY, 0) > 0) goto solved;
1182     free_game(solved);
1183
1184     solved = dup_game(state);
1185     if (solve_specific(solved, DIFF_ANY, 0) > 0) goto solved;
1186     free_game(solved);
1187
1188     *error = "Unable to solve puzzle.";
1189     return NULL;
1190
1191 solved:
1192     move = game_state_diff(currstate, solved, 1);
1193     free_game(solved);
1194     return move;
1195 }
1196
1197 /* --- Game generation --- */
1198
1199 /* A correctly completed Hitori board is essentially a latin square
1200  * (no duplicated numbers in any row or column) with black squares
1201  * added such that no black square touches another, and the white
1202  * squares make a contiguous region.
1203  *
1204  * So we can generate it by:
1205    * constructing a latin square
1206    * adding black squares at random (minding the constraints)
1207    * altering the numbers under the new black squares such that
1208       the solver gets a headstart working out where they are.
1209  */
1210
1211 static int new_game_is_good(const game_params *params,
1212                             game_state *state, game_state *tosolve)
1213 {
1214     int sret, sret_easy = 0;
1215
1216     memcpy(tosolve->nums, state->nums, state->n * sizeof(int));
1217     memset(tosolve->flags, 0, state->n * sizeof(unsigned int));
1218     tosolve->completed = tosolve->impossible = 0;
1219
1220     /*
1221      * We try and solve it twice, once at our requested difficulty level
1222      * (ensuring it's soluble at all) and once at the level below (if
1223      * it exists), which we hope to fail: if you can also solve it at
1224      * the level below then it's too easy and we have to try again.
1225      *
1226      * With this puzzle in particular there's an extra finesse, which is
1227      * that we check that the generated puzzle isn't too easy _with
1228      * an extra solver step first_, which is the 'sneaky' mode of deductions
1229      * (asserting that any number which fulfils the latin-square rules
1230      * on its row/column must be white). This is an artefact of the
1231      * generation process and not implicit in the rules, so we don't want
1232      * people to be able to use it to make the puzzle easier.
1233      */
1234
1235     assert(params->diff < DIFF_MAX);
1236     sret = solve_specific(tosolve, params->diff, 0);
1237     if (params->diff > DIFF_EASY) {
1238         memset(tosolve->flags, 0, state->n * sizeof(unsigned int));
1239         tosolve->completed = tosolve->impossible = 0;
1240
1241         /* this is the only time the 'sneaky' flag is set to 1. */
1242         sret_easy = solve_specific(tosolve, params->diff-1, 1);
1243     }
1244
1245     if (sret <= 0 || sret_easy > 0) {
1246         debug(("Generated puzzle %s at chosen difficulty %s\n",
1247                sret <= 0 ? "insoluble" : "too easy",
1248                singles_diffnames[params->diff]));
1249         return 0;
1250     }
1251     return 1;
1252 }
1253
1254 #define MAXTRIES 20
1255
1256 static int best_black_col(game_state *state, random_state *rs, int *scratch,
1257                           int i, int *rownums, int *colnums)
1258 {
1259     int w = state->w, x = i%w, y = i/w, j, o = state->o;
1260
1261     /* Randomise the list of numbers to try. */
1262     for (i = 0; i < o; i++) scratch[i] = i;
1263     shuffle(scratch, o, sizeof(int), rs);
1264
1265     /* Try each number in turn, first giving preference to removing
1266      * latin-square characteristics (i.e. those numbers which only
1267      * occur once in a row/column). The '&&' here, although intuitively
1268      * wrong, results in a smaller number of 'sneaky' deductions on
1269      * solvable boards. */
1270     for (i = 0; i < o; i++) {
1271         j = scratch[i] + 1;
1272         if (rownums[y*o + j-1] == 1 && colnums[x*o + j-1] == 1)
1273             goto found;
1274     }
1275
1276     /* Then try each number in turn returning the first one that's
1277      * not actually unique in its row/column (see comment below) */
1278     for (i = 0; i < o; i++) {
1279         j = scratch[i] + 1;
1280         if (rownums[y*o + j-1] != 0 || colnums[x*o + j-1] != 0)
1281             goto found;
1282     }
1283     assert(!"unable to place number under black cell.");
1284     return 0;
1285
1286 found:
1287     /* Update column and row counts assuming this number will be placed. */
1288     rownums[y*o + j-1] += 1;
1289     colnums[x*o + j-1] += 1;
1290     return j;
1291 }
1292
1293 static char *new_game_desc(const game_params *params, random_state *rs,
1294                            char **aux, int interactive)
1295 {
1296     game_state *state = blank_game(params->w, params->h);
1297     game_state *tosolve = blank_game(params->w, params->h);
1298     int i, j, *scratch, *rownums, *colnums, x, y, ntries;
1299     int w = state->w, h = state->h, o = state->o;
1300     char *ret;
1301     digit *latin;
1302     struct solver_state *ss = solver_state_new(state);
1303
1304     scratch = snewn(state->n, int);
1305     rownums = snewn(h*o, int);
1306     colnums = snewn(w*o, int);
1307
1308 generate:
1309     ss->n_ops = 0;
1310     debug(("Starting game generation, size %dx%d\n", w, h));
1311
1312     memset(state->flags, 0, state->n*sizeof(unsigned int));
1313
1314     /* First, generate the latin rectangle.
1315      * The order of this, o, is max(w,h). */
1316     latin = latin_generate_rect(w, h, rs);
1317     for (i = 0; i < state->n; i++)
1318         state->nums[i] = (int)latin[i];
1319     sfree(latin);
1320     debug_state("State after latin square", state);
1321
1322     /* Add black squares at random, using bits of solver as we go (to lay
1323      * white squares), until we can lay no more blacks. */
1324     for (i = 0; i < state->n; i++)
1325         scratch[i] = i;
1326     shuffle(scratch, state->n, sizeof(int), rs);
1327     for (j = 0; j < state->n; j++) {
1328         i = scratch[j];
1329         if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK)) {
1330             debug(("generator skipping (%d,%d): %s\n", i%w, i/w,
1331                    (state->flags[i] & F_CIRCLE) ? "CIRCLE" : "BLACK"));
1332             continue; /* solver knows this must be one or the other already. */
1333         }
1334
1335         /* Add a random black cell... */
1336         solver_op_add(ss, i%w, i/w, BLACK, "Generator: adding random black cell");
1337         solver_ops_do(state, ss);
1338
1339         /* ... and do as well as we know how to lay down whites that are now forced. */
1340         solve_allblackbutone(state, ss);
1341         solver_ops_do(state, ss);
1342
1343         solve_removesplits(state, ss);
1344         solver_ops_do(state, ss);
1345
1346         if (state->impossible) {
1347             debug(("generator made impossible, restarting...\n"));
1348             goto generate;
1349         }
1350     }
1351     debug_state("State after adding blacks", state);
1352
1353     /* Now we know which squares are white and which are black, we lay numbers
1354      * under black squares at random, except that the number must appear in
1355      * white cells at least once more in the same column or row as that [black]
1356      * square. That's necessary to avoid multiple solutions, where blackening
1357      * squares in the finished puzzle becomes optional. We use two arrays:
1358      *
1359      * rownums[ROW * o + NUM-1] is the no. of white cells containing NUM in y=ROW
1360      * colnums[COL * o + NUM-1] is the no. of white cells containing NUM in x=COL
1361      */
1362
1363     memset(rownums, 0, h*o * sizeof(int));
1364     memset(colnums, 0, w*o * sizeof(int));
1365     for (i = 0; i < state->n; i++) {
1366         if (state->flags[i] & F_BLACK) continue;
1367         j = state->nums[i];
1368         x = i%w; y = i/w;
1369         rownums[y * o + j-1] += 1;
1370         colnums[x * o + j-1] += 1;
1371     }
1372
1373     ntries = 0;
1374 randomise:
1375     for (i = 0; i < state->n; i++) {
1376         if (!(state->flags[i] & F_BLACK)) continue;
1377         state->nums[i] = best_black_col(state, rs, scratch, i, rownums, colnums);
1378     }
1379     debug_state("State after adding numbers", state);
1380
1381     /* DIFF_ANY just returns whatever we first generated, for testing purposes. */
1382     if (params->diff != DIFF_ANY &&
1383         !new_game_is_good(params, state, tosolve)) {
1384         ntries++;
1385         if (ntries > MAXTRIES) {
1386             debug(("Ran out of randomisation attempts, re-generating.\n"));
1387             goto generate;
1388         }
1389         debug(("Re-randomising numbers under black squares.\n"));
1390         goto randomise;
1391     }
1392
1393     ret = generate_desc(state, 0);
1394
1395     free_game(tosolve);
1396     free_game(state);
1397     solver_state_free(ss);
1398     sfree(scratch);
1399     sfree(rownums);
1400     sfree(colnums);
1401
1402     return ret;
1403 }
1404
1405 static char *validate_desc(const game_params *params, const char *desc)
1406 {
1407     char *ret = NULL;
1408
1409     unpick_desc(params, desc, NULL, &ret);
1410     return ret;
1411 }
1412
1413 static game_state *new_game(midend *me, const game_params *params,
1414                             const char *desc)
1415 {
1416     game_state *state = NULL;
1417
1418     unpick_desc(params, desc, &state, NULL);
1419     if (!state) assert(!"new_game failed to unpick");
1420     return state;
1421 }
1422
1423 /* --- Game UI and move routines --- */
1424
1425 struct game_ui {
1426     int cx, cy, cshow;
1427     int show_black_nums;
1428 };
1429
1430 static game_ui *new_ui(const game_state *state)
1431 {
1432     game_ui *ui = snew(game_ui);
1433
1434     ui->cx = ui->cy = ui->cshow = 0;
1435     ui->show_black_nums = 0;
1436
1437     return ui;
1438 }
1439
1440 static void free_ui(game_ui *ui)
1441 {
1442     sfree(ui);
1443 }
1444
1445 static char *encode_ui(const game_ui *ui)
1446 {
1447     return NULL;
1448 }
1449
1450 static void decode_ui(game_ui *ui, const char *encoding)
1451 {
1452 }
1453
1454 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1455                                const game_state *newstate)
1456 {
1457     if (!oldstate->completed && newstate->completed)
1458         ui->cshow = 0;
1459 }
1460
1461 #define DS_BLACK        0x1
1462 #define DS_CIRCLE       0x2
1463 #define DS_CURSOR       0x4
1464 #define DS_BLACK_NUM    0x8
1465 #define DS_ERROR        0x10
1466 #define DS_FLASH        0x20
1467 #define DS_IMPOSSIBLE   0x40
1468
1469 struct game_drawstate {
1470     int tilesize, started, solved;
1471     int w, h, n;
1472
1473     unsigned int *flags;
1474 };
1475
1476 static char *interpret_move(const game_state *state, game_ui *ui,
1477                             const game_drawstate *ds,
1478                             int mx, int my, int button)
1479 {
1480     char buf[80], c;
1481     int i, x = FROMCOORD(mx), y = FROMCOORD(my);
1482     enum { NONE, TOGGLE_BLACK, TOGGLE_CIRCLE, UI } action = NONE;
1483
1484     if (IS_CURSOR_MOVE(button)) {
1485         move_cursor(button, &ui->cx, &ui->cy, state->w, state->h, 1);
1486         ui->cshow = 1;
1487         action = UI;
1488     } else if (IS_CURSOR_SELECT(button)) {
1489         x = ui->cx; y = ui->cy;
1490         if (!ui->cshow) {
1491             action = UI;
1492             ui->cshow = 1;
1493         }
1494         if (button == CURSOR_SELECT) {
1495             action = TOGGLE_BLACK;
1496         } else if (button == CURSOR_SELECT2) {
1497             action = TOGGLE_CIRCLE;
1498         }
1499     } else if (IS_MOUSE_DOWN(button)) {
1500         if (ui->cshow) {
1501             ui->cshow = 0;
1502             action = UI;
1503         }
1504         if (!INGRID(state, x, y)) {
1505             ui->show_black_nums = 1 - ui->show_black_nums;
1506             action = UI; /* this wants to be a per-game option. */
1507         } else if (button == LEFT_BUTTON) {
1508             action = TOGGLE_BLACK;
1509         } else if (button == RIGHT_BUTTON) {
1510             action = TOGGLE_CIRCLE;
1511         }
1512     }
1513     if (action == UI) return "";
1514
1515     if (action == TOGGLE_BLACK || action == TOGGLE_CIRCLE) {
1516         i = y * state->w + x;
1517         if (state->flags[i] & (F_BLACK | F_CIRCLE))
1518             c = 'E';
1519         else
1520             c = (action == TOGGLE_BLACK) ? 'B' : 'C';
1521         sprintf(buf, "%c%d,%d", (int)c, x, y);
1522         return dupstr(buf);
1523     }
1524
1525     return NULL;
1526 }
1527
1528 static game_state *execute_move(const game_state *state, const char *move)
1529 {
1530     game_state *ret = dup_game(state);
1531     int x, y, i, n;
1532
1533     debug(("move: %s\n", move));
1534
1535     while (*move) {
1536         char c = *move;
1537         if (c == 'B' || c == 'C' || c == 'E') {
1538             move++;
1539             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1540                 !INGRID(state, x, y))
1541                 goto badmove;
1542
1543             i = y*ret->w + x;
1544             ret->flags[i] &= ~(F_CIRCLE | F_BLACK); /* empty first, always. */
1545             if (c == 'B')
1546                 ret->flags[i] |= F_BLACK;
1547             else if (c == 'C')
1548                 ret->flags[i] |= F_CIRCLE;
1549             move += n;
1550         } else if (c == 'S') {
1551             move++;
1552             ret->used_solve = 1;
1553         } else
1554             goto badmove;
1555
1556         if (*move == ';')
1557             move++;
1558         else if (*move)
1559             goto badmove;
1560     }
1561     if (check_complete(ret, CC_MARK_ERRORS)) ret->completed = 1;
1562     return ret;
1563
1564 badmove:
1565     free_game(ret);
1566     return NULL;
1567 }
1568
1569 /* ----------------------------------------------------------------------
1570  * Drawing routines.
1571  */
1572
1573 static void game_compute_size(const game_params *params, int tilesize,
1574                               int *x, int *y)
1575 {
1576     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1577     struct { int tilesize; } ads, *ds = &ads;
1578     ads.tilesize = tilesize;
1579
1580     *x = TILE_SIZE * params->w + 2 * BORDER;
1581     *y = TILE_SIZE * params->h + 2 * BORDER;
1582 }
1583
1584 static void game_set_size(drawing *dr, game_drawstate *ds,
1585                           const game_params *params, int tilesize)
1586 {
1587     ds->tilesize = tilesize;
1588 }
1589
1590 static float *game_colours(frontend *fe, int *ncolours)
1591 {
1592     float *ret = snewn(3 * NCOLOURS, float);
1593     int i;
1594
1595     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1596     for (i = 0; i < 3; i++) {
1597         ret[COL_BLACK * 3 + i] = 0.0F;
1598         ret[COL_BLACKNUM * 3 + i] = 0.4F;
1599         ret[COL_WHITE * 3 + i] = 1.0F;
1600         ret[COL_GRID * 3 + i] = ret[COL_LOWLIGHT * 3 + i];
1601     }
1602     ret[COL_CURSOR * 3 + 0] = 0.2F;
1603     ret[COL_CURSOR * 3 + 1] = 0.8F;
1604     ret[COL_CURSOR * 3 + 2] = 0.0F;
1605
1606     ret[COL_ERROR * 3 + 0] = 1.0F;
1607     ret[COL_ERROR * 3 + 1] = 0.0F;
1608     ret[COL_ERROR * 3 + 2] = 0.0F;
1609
1610     *ncolours = NCOLOURS;
1611     return ret;
1612 }
1613
1614 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1615 {
1616     struct game_drawstate *ds = snew(struct game_drawstate);
1617
1618     ds->tilesize = ds->started = ds->solved = 0;
1619     ds->w = state->w;
1620     ds->h = state->h;
1621     ds->n = state->n;
1622
1623     ds->flags = snewn(state->n, unsigned int);
1624
1625     memset(ds->flags, 0, state->n*sizeof(unsigned int));
1626
1627     return ds;
1628 }
1629
1630 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1631 {
1632     sfree(ds->flags);
1633     sfree(ds);
1634 }
1635
1636 static void tile_redraw(drawing *dr, game_drawstate *ds, int x, int y,
1637                         int num, unsigned int f)
1638 {
1639     int tcol, bg, dnum, cx, cy, tsz;
1640     char buf[32];
1641
1642     if (f & DS_BLACK) {
1643         bg = (f & DS_ERROR) ? COL_ERROR : COL_BLACK;
1644         tcol = COL_BLACKNUM;
1645         dnum = (f & DS_BLACK_NUM) ? 1 : 0;
1646     } else {
1647         bg = (f & DS_FLASH) ? COL_LOWLIGHT : COL_BACKGROUND;
1648         tcol = (f & DS_ERROR) ? COL_ERROR : COL_BLACK;
1649         dnum = 1;
1650     }
1651
1652     cx = x + TILE_SIZE/2; cy = y + TILE_SIZE/2;
1653
1654     draw_rect(dr, x,    y, TILE_SIZE, TILE_SIZE, bg);
1655     draw_rect_outline(dr, x, y, TILE_SIZE, TILE_SIZE,
1656                       (f & DS_IMPOSSIBLE) ? COL_ERROR : COL_GRID);
1657
1658     if (f & DS_CIRCLE) {
1659         draw_circle(dr, cx, cy, CRAD, tcol, tcol);
1660         draw_circle(dr, cx, cy, CRAD-1, bg, tcol);
1661     }
1662
1663     if (dnum) {
1664         sprintf(buf, "%d", num);
1665         if (strlen(buf) == 1)
1666             tsz = TEXTSZ;
1667         else
1668             tsz = (CRAD*2 - 1) / strlen(buf);
1669         draw_text(dr, cx, cy, FONT_VARIABLE, tsz,
1670                   ALIGN_VCENTRE | ALIGN_HCENTRE, tcol, buf);
1671     }
1672
1673     if (f & DS_CURSOR)
1674         draw_rect_corners(dr, cx, cy, TEXTSZ/2, COL_CURSOR);
1675
1676     draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
1677 }
1678
1679 static void game_redraw(drawing *dr, game_drawstate *ds,
1680                         const game_state *oldstate, const game_state *state,
1681                         int dir, const game_ui *ui,
1682                         float animtime, float flashtime)
1683 {
1684     int x, y, i, flash;
1685     unsigned int f;
1686
1687     flash = (int)(flashtime * 5 / FLASH_TIME) % 2;
1688
1689     if (!ds->started) {
1690         int wsz = TILE_SIZE * state->w + 2 * BORDER;
1691         int hsz = TILE_SIZE * state->h + 2 * BORDER;
1692         draw_rect(dr, 0, 0, wsz, hsz, COL_BACKGROUND);
1693         draw_rect_outline(dr, COORD(0)-1, COORD(0)-1,
1694                           TILE_SIZE * state->w + 2, TILE_SIZE * state->h + 2,
1695                           COL_GRID);
1696         draw_update(dr, 0, 0, wsz, hsz);
1697     }
1698     for (x = 0; x < state->w; x++) {
1699         for (y = 0; y < state->h; y++) {
1700             i = y*state->w + x;
1701             f = 0;
1702
1703             if (flash) f |= DS_FLASH;
1704             if (state->impossible) f |= DS_IMPOSSIBLE;
1705
1706             if (ui->cshow && x == ui->cx && y == ui->cy)
1707                 f |= DS_CURSOR;
1708             if (state->flags[i] & F_BLACK) {
1709                 f |= DS_BLACK;
1710                 if (ui->show_black_nums) f |= DS_BLACK_NUM;
1711             }
1712             if (state->flags[i] & F_CIRCLE)
1713                 f |= DS_CIRCLE;
1714             if (state->flags[i] & F_ERROR)
1715                 f |= DS_ERROR;
1716
1717             if (!ds->started || ds->flags[i] != f) {
1718                 tile_redraw(dr, ds, COORD(x), COORD(y),
1719                             state->nums[i], f);
1720                 ds->flags[i] = f;
1721             }
1722         }
1723     }
1724     ds->started = 1;
1725 }
1726
1727 static float game_anim_length(const game_state *oldstate,
1728                               const game_state *newstate, int dir, game_ui *ui)
1729 {
1730     return 0.0F;
1731 }
1732
1733 static float game_flash_length(const game_state *oldstate,
1734                                const game_state *newstate, int dir, game_ui *ui)
1735 {
1736     if (!oldstate->completed &&
1737         newstate->completed && !newstate->used_solve)
1738         return FLASH_TIME;
1739     return 0.0F;
1740 }
1741
1742 static int game_status(const game_state *state)
1743 {
1744     return state->completed ? +1 : 0;
1745 }
1746
1747 static int game_timing_state(const game_state *state, game_ui *ui)
1748 {
1749     return TRUE;
1750 }
1751
1752 static void game_print_size(const game_params *params, float *x, float *y)
1753 {
1754     int pw, ph;
1755
1756     /* 8mm squares by default. */
1757     game_compute_size(params, 800, &pw, &ph);
1758     *x = pw / 100.0F;
1759     *y = ph / 100.0F;
1760 }
1761
1762 static void game_print(drawing *dr, const game_state *state, int tilesize)
1763 {
1764     int ink = print_mono_colour(dr, 0);
1765     int paper = print_mono_colour(dr, 1);
1766     int x, y, ox, oy, i;
1767     char buf[32];
1768
1769     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1770     game_drawstate ads, *ds = &ads;
1771     game_set_size(dr, ds, NULL, tilesize);
1772
1773     print_line_width(dr, 2 * TILE_SIZE / 40);
1774
1775     for (x = 0; x < state->w; x++) {
1776         for (y = 0; y < state->h; y++) {
1777             ox = COORD(x); oy = COORD(y);
1778             i = y*state->w+x;
1779
1780             if (state->flags[i] & F_BLACK) {
1781                 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1782             } else {
1783                 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1784
1785                 if (state->flags[i] & DS_CIRCLE)
1786                     draw_circle(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, CRAD,
1787                                 paper, ink);
1788
1789                 sprintf(buf, "%d", state->nums[i]);
1790                 draw_text(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, FONT_VARIABLE,
1791                           TEXTSZ/strlen(buf), ALIGN_VCENTRE | ALIGN_HCENTRE,
1792                           ink, buf);
1793             }
1794         }
1795     }
1796 }
1797
1798 #ifdef COMBINED
1799 #define thegame singles
1800 #endif
1801
1802 const struct game thegame = {
1803     "Singles", "games.singles", "singles",
1804     default_params,
1805     game_fetch_preset,
1806     decode_params,
1807     encode_params,
1808     free_params,
1809     dup_params,
1810     TRUE, game_configure, custom_params,
1811     validate_params,
1812     new_game_desc,
1813     validate_desc,
1814     new_game,
1815     dup_game,
1816     free_game,
1817     TRUE, solve_game,
1818     TRUE, game_can_format_as_text_now, game_text_format,
1819     new_ui,
1820     free_ui,
1821     encode_ui,
1822     decode_ui,
1823     game_changed_state,
1824     interpret_move,
1825     execute_move,
1826     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1827     game_colours,
1828     game_new_drawstate,
1829     game_free_drawstate,
1830     game_redraw,
1831     game_anim_length,
1832     game_flash_length,
1833     game_status,
1834     TRUE, FALSE, game_print_size, game_print,
1835     FALSE,                             /* wants_statusbar */
1836     FALSE, game_timing_state,
1837     REQUIRE_RBUTTON,                   /* flags */
1838 };
1839
1840 #ifdef STANDALONE_SOLVER
1841
1842 #include <time.h>
1843 #include <stdarg.h>
1844
1845 static void start_soak(game_params *p, random_state *rs)
1846 {
1847     time_t tt_start, tt_now, tt_last;
1848     char *desc, *aux;
1849     game_state *s;
1850     int i, n = 0, ndiff[DIFF_MAX], diff, sret, nblack = 0, nsneaky = 0;
1851
1852     tt_start = tt_now = time(NULL);
1853
1854     printf("Soak-testing a %dx%d grid.\n", p->w, p->h);
1855     p->diff = DIFF_ANY;
1856
1857     memset(ndiff, 0, DIFF_MAX * sizeof(int));
1858
1859     while (1) {
1860         n++;
1861         desc = new_game_desc(p, rs, &aux, 0);
1862         s = new_game(NULL, p, desc);
1863         nsneaky += solve_sneaky(s, NULL);
1864
1865         for (diff = 0; diff < DIFF_MAX; diff++) {
1866             memset(s->flags, 0, s->n * sizeof(unsigned int));
1867             s->completed = s->impossible = 0;
1868             sret = solve_specific(s, diff, 0);
1869             if (sret > 0) {
1870                 ndiff[diff]++;
1871                 break;
1872             } else if (sret < 0)
1873                 fprintf(stderr, "Impossible! %s\n", desc);
1874         }
1875         for (i = 0; i < s->n; i++) {
1876             if (s->flags[i] & F_BLACK) nblack++;
1877         }
1878         free_game(s);
1879         sfree(desc);
1880
1881         tt_last = time(NULL);
1882         if (tt_last > tt_now) {
1883             tt_now = tt_last;
1884             printf("%d total, %3.1f/s, bl/sn %3.1f%%/%3.1f%%: ",
1885                    n, (double)n / ((double)tt_now - tt_start),
1886                    ((double)nblack * 100.0) / (double)(n * p->w * p->h),
1887                    ((double)nsneaky * 100.0) / (double)(n * p->w * p->h));
1888             for (diff = 0; diff < DIFF_MAX; diff++) {
1889                 if (diff > 0) printf(", ");
1890                 printf("%d (%3.1f%%) %s",
1891                        ndiff[diff], (double)ndiff[diff] * 100.0 / (double)n,
1892                        singles_diffnames[diff]);
1893             }
1894             printf("\n");
1895         }
1896     }
1897 }
1898
1899 int main(int argc, char **argv)
1900 {
1901     char *id = NULL, *desc, *desc_gen = NULL, *tgame, *err, *aux;
1902     game_state *s = NULL;
1903     game_params *p = NULL;
1904     int soln, soak = 0, ret = 1;
1905     time_t seed = time(NULL);
1906     random_state *rs = NULL;
1907
1908     setvbuf(stdout, NULL, _IONBF, 0);
1909
1910     while (--argc > 0) {
1911         char *p = *++argv;
1912         if (!strcmp(p, "-v")) {
1913             verbose = 1;
1914         } else if (!strcmp(p, "--soak")) {
1915             soak = 1;
1916         } else if (!strcmp(p, "--seed")) {
1917             if (argc == 0) {
1918                 fprintf(stderr, "%s: --seed needs an argument", argv[0]);
1919                 goto done;
1920             }
1921             seed = (time_t)atoi(*++argv);
1922             argc--;
1923         } else if (*p == '-') {
1924             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
1925             return 1;
1926         } else {
1927             id = p;
1928         }
1929     }
1930
1931     rs = random_new((void*)&seed, sizeof(time_t));
1932
1933     if (!id) {
1934         fprintf(stderr, "usage: %s [-v] [--soak] <params> | <game_id>\n", argv[0]);
1935         goto done;
1936     }
1937     desc = strchr(id, ':');
1938     if (desc) *desc++ = '\0';
1939
1940     p = default_params();
1941     decode_params(p, id);
1942     err = validate_params(p, 1);
1943     if (err) {
1944         fprintf(stderr, "%s: %s", argv[0], err);
1945         goto done;
1946     }
1947
1948     if (soak) {
1949         if (desc) {
1950             fprintf(stderr, "%s: --soak only needs params, not game desc.\n", argv[0]);
1951             goto done;
1952         }
1953         start_soak(p, rs);
1954     } else {
1955         if (!desc) desc = desc_gen = new_game_desc(p, rs, &aux, 0);
1956
1957         err = validate_desc(p, desc);
1958         if (err) {
1959             fprintf(stderr, "%s: %s\n", argv[0], err);
1960             free_params(p);
1961             goto done;
1962         }
1963         s = new_game(NULL, p, desc);
1964
1965         if (verbose) {
1966             tgame = game_text_format(s);
1967             fputs(tgame, stdout);
1968             sfree(tgame);
1969         }
1970
1971         soln = solve_specific(s, DIFF_ANY, 0);
1972         tgame = game_text_format(s);
1973         fputs(tgame, stdout);
1974         sfree(tgame);
1975         printf("Game was %s.\n\n",
1976                soln < 0 ? "impossible" : soln > 0 ? "solved" : "not solved");
1977     }
1978     ret = 0;
1979
1980 done:
1981     if (desc_gen) sfree(desc_gen);
1982     if (p) free_params(p);
1983     if (s) free_game(s);
1984     if (rs) random_free(rs);
1985
1986     return ret;
1987 }
1988
1989 #endif
1990
1991
1992 /* vim: set shiftwidth=4 tabstop=8: */