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(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(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(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(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(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(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(game_params *params, 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(game_params *params)
 382 {
 383     return TRUE;
 384 }
 385
 386 static char *game_text_format(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(game_state *src, game_state *dst, int issolve)
 556 {
 557     char *ret = NULL, buf[80], c;
 558     int retlen = 0, x, y, i, k;
 559     unsigned int fmask = F_BLACK | F_CIRCLE;
 560
 561     assert(src->n == dst->n);
 562
 563     if (issolve) {
 564         ret = sresize(ret, 3, char);
 565         ret[0] = 'S'; ret[1] = ';'; ret[2] = '\0';
 566         retlen += 2;
 567     }
 568
 569     for (x = 0; x < dst->w; x++) {
 570         for (y = 0; y < dst->h; y++) {
 571             i = y*dst->w + x;
 572             if ((src->flags[i] & fmask) != (dst->flags[i] & fmask)) {
 573                 assert((dst->flags[i] & fmask) != fmask);
 574                 if (dst->flags[i] & F_BLACK)
 575                     c = 'B';
 576                 else if (dst->flags[i] & F_CIRCLE)
 577                     c = 'C';
 578                 else
 579                     c = 'E';
 580                 k = sprintf(buf, "%c%d,%d;", (int)c, x, y);
 581                 ret = sresize(ret, retlen + k + 1, char);
 582                 strcpy(ret + retlen, buf);
 583                 retlen += k;
 584             }
 585         }
 586     }
 587     return ret;
 588 }
 589
 590 /* --- Solver --- */
 591
 592 enum { BLACK, CIRCLE };
 593
 594 struct solver_op {
 595     int x, y, op; /* op one of BLACK or CIRCLE. */
 596     const char *desc; /* must be non-malloced. */
 597 };
 598
 599 struct solver_state {
 600     struct solver_op *ops;
 601     int n_ops, n_alloc;
 602     int *scratch;
 603 };
 604
 605 static struct solver_state *solver_state_new(game_state *state)
 606 {
 607     struct solver_state *ss = snew(struct solver_state);
 608
 609     ss->ops = NULL;
 610     ss->n_ops = ss->n_alloc = 0;
 611     ss->scratch = snewn(state->n, int);
 612
 613     return ss;
 614 }
 615
 616 static void solver_state_free(struct solver_state *ss)
 617 {
 618     sfree(ss->scratch);
 619     if (ss->ops) sfree(ss->ops);
 620     sfree(ss);
 621 }
 622
 623 static void solver_op_add(struct solver_state *ss, int x, int y, int op, const char *desc)
 624 {
 625     struct solver_op *sop;
 626
 627     if (ss->n_alloc < ss->n_ops + 1) {
 628         ss->n_alloc = (ss->n_alloc + 1) * 2;
 629         ss->ops = sresize(ss->ops, ss->n_alloc, struct solver_op);
 630     }
 631     sop = &(ss->ops[ss->n_ops++]);
 632     sop->x = x; sop->y = y; sop->op = op; sop->desc = desc;
 633     debug(("added solver op %s ('%s') at (%d,%d)\n",
 634            op == BLACK ? "BLACK" : "CIRCLE", desc, x, y));
 635 }
 636
 637 static void solver_op_circle(game_state *state, struct solver_state *ss,
 638                              int x, int y)
 639 {
 640     int i = y*state->w + x;
 641
 642     if (!INGRID(state, x, y)) return;
 643     if (state->flags[i] & F_BLACK) {
 644         debug(("... solver wants to add auto-circle on black (%d,%d)\n", x, y));
 645         state->impossible = 1;
 646         return;
 647     }
 648     /* Only add circle op if it's not already circled. */
 649     if (!(state->flags[i] & F_CIRCLE)) {
 650         solver_op_add(ss, x, y, CIRCLE, "SB - adjacent to black square");
 651     }
 652 }
 653
 654 static void solver_op_blacken(game_state *state, struct solver_state *ss,
 655                               int x, int y, int num)
 656 {
 657     int i = y*state->w + x;
 658
 659     if (!INGRID(state, x, y)) return;
 660     if (state->nums[i] != num) return;
 661     if (state->flags[i] & F_CIRCLE) {
 662         debug(("... solver wants to add auto-black on circled(%d,%d)\n", x, y));
 663         state->impossible = 1;
 664         return;
 665     }
 666     /* Only add black op if it's not already black. */
 667     if (!(state->flags[i] & F_BLACK)) {
 668         solver_op_add(ss, x, y, BLACK, "SC - number on same row/col as circled");
 669     }
 670 }
 671
 672 static int solver_ops_do(game_state *state, struct solver_state *ss)
 673 {
 674     int next_op = 0, i, x, y, n_ops = 0;
 675     struct solver_op op;
 676
 677     /* Care here: solver_op_* may call solver_op_add which may extend the
 678      * ss->n_ops. */
 679
 680     while (next_op < ss->n_ops) {
 681         op = ss->ops[next_op++]; /* copy this away, it may get reallocated. */
 682         i = op.y*state->w + op.x;
 683
 684         if (op.op == BLACK) {
 685             if (state->flags[i] & F_CIRCLE) {
 686                 debug(("Solver wants to blacken circled square (%d,%d)!\n", op.x, op.y));
 687                 state->impossible = 1;
 688                 return n_ops;
 689             }
 690             if (!(state->flags[i] & F_BLACK)) {
 691                 debug(("... solver adding black at (%d,%d): %s\n", op.x, op.y, op.desc));
 692 #ifdef STANDALONE_SOLVER
 693                 if (verbose)
 694                     printf("Adding black at (%d,%d): %s\n", op.x, op.y, op.desc);
 695 #endif
 696                 state->flags[i] |= F_BLACK;
 697                 /*debug_state("State after adding black", state);*/
 698                 n_ops++;
 699                 solver_op_circle(state, ss, op.x-1, op.y);
 700                 solver_op_circle(state, ss, op.x+1, op.y);
 701                 solver_op_circle(state, ss, op.x,   op.y-1);
 702                 solver_op_circle(state, ss, op.x,   op.y+1);
 703                 }
 704         } else {
 705             if (state->flags[i] & F_BLACK) {
 706                 debug(("Solver wants to circle blackened square (%d,%d)!\n", op.x, op.y));
 707                 state->impossible = 1;
 708                 return n_ops;
 709             }
 710             if (!(state->flags[i] & F_CIRCLE)) {
 711                 debug(("... solver adding circle at (%d,%d): %s\n", op.x, op.y, op.desc));
 712 #ifdef STANDALONE_SOLVER
 713                 if (verbose)
 714                     printf("Adding circle at (%d,%d): %s\n", op.x, op.y, op.desc);
 715 #endif
 716                 state->flags[i] |= F_CIRCLE;
 717                 /*debug_state("State after adding circle", state);*/
 718                 n_ops++;
 719                 for (x = 0; x < state->w; x++) {
 720                     if (x != op.x)
 721                         solver_op_blacken(state, ss, x, op.y, state->nums[i]);
 722                 }
 723                 for (y = 0; y < state->h; y++) {
 724                     if (y != op.y)
 725                         solver_op_blacken(state, ss, op.x, y, state->nums[i]);
 726                 }
 727             }
 728         }
 729     }
 730     ss->n_ops = 0;
 731     return n_ops;
 732 }
 733
 734 /* If the grid has two identical numbers with one cell between them, the inner
 735  * cell _must_ be white (and thus circled); (at least) one of the two must be
 736  * black (since they're in the same column or row) and thus the middle cell is
 737  * next to a black cell. */
 738 static int solve_singlesep(game_state *state, struct solver_state *ss)
 739 {
 740     int x, y, i, ir, irr, id, idd, n_ops = ss->n_ops;
 741
 742     for (x = 0; x < state->w; x++) {
 743         for (y = 0; y < state->h; y++) {
 744             i = y*state->w + x;
 745
 746             /* Cell two to our right? */
 747             ir = i + 1; irr = ir + 1;
 748             if (x < (state->w-2) &&
 749                 state->nums[i] == state->nums[irr] &&
 750                 !(state->flags[ir] & F_CIRCLE)) {
 751                 solver_op_add(ss, x+1, y, CIRCLE, "SP/ST - between identical nums");
 752             }
 753             /* Cell two below us? */
 754             id = i + state->w; idd = id + state->w;
 755             if (y < (state->h-2) &&
 756                 state->nums[i] == state->nums[idd] &&
 757                 !(state->flags[id] & F_CIRCLE)) {
 758                 solver_op_add(ss, x, y+1, CIRCLE, "SP/ST - between identical nums");
 759             }
 760         }
 761     }
 762     return ss->n_ops - n_ops;
 763 }
 764
 765 /* If we have two identical numbers next to each other (in a row or column),
 766  * any other identical numbers in that column must be black. */
 767 static int solve_doubles(game_state *state, struct solver_state *ss)
 768 {
 769     int x, y, i, ii, n_ops = ss->n_ops, xy;
 770
 771     for (y = 0, i = 0; y < state->h; y++) {
 772         for (x = 0; x < state->w; x++, i++) {
 773             assert(i == y*state->w+x);
 774             if (state->flags[i] & F_BLACK) continue;
 775
 776             ii = i+1; /* check cell to our right. */
 777             if (x < (state->w-1) &&
 778                 !(state->flags[ii] & F_BLACK) &&
 779                 state->nums[i] == state->nums[ii]) {
 780                 for (xy = 0; xy < state->w; xy++) {
 781                     if (xy == x || xy == (x+1)) continue;
 782                     if (state->nums[y*state->w + xy] == state->nums[i] &&
 783                         !(state->flags[y*state->w + xy] & F_BLACK))
 784                         solver_op_add(ss, xy, y, BLACK, "PI - same row as pair");
 785                 }
 786             }
 787
 788             ii = i+state->w; /* check cell below us */
 789             if (y < (state->h-1) &&
 790                 !(state->flags[ii] & F_BLACK) &&
 791                 state->nums[i] == state->nums[ii]) {
 792                 for (xy = 0; xy < state->h; xy++) {
 793                     if (xy == y || xy == (y+1)) continue;
 794                     if (state->nums[xy*state->w + x] == state->nums[i] &&
 795                         !(state->flags[xy*state->w + x] & F_BLACK))
 796                         solver_op_add(ss, x, xy, BLACK, "PI - same col as pair");
 797                 }
 798             }
 799         }
 800     }
 801     return ss->n_ops - n_ops;
 802 }
 803
 804 /* If a white square has all-but-one possible adjacent squares black, the
 805  * one square left over must be white. */
 806 static int solve_allblackbutone(game_state *state, struct solver_state *ss)
 807 {
 808     int x, y, i, n_ops = ss->n_ops, xd, yd, id, ifree;
 809     int dis[4], d;
 810
 811     dis[0] = -state->w;
 812     dis[1] = 1;
 813     dis[2] = state->w;
 814     dis[3] = -1;
 815
 816     for (y = 0, i = 0; y < state->h; y++) {
 817         for (x = 0; x < state->w; x++, i++) {
 818             assert(i == y*state->w+x);
 819             if (state->flags[i] & F_BLACK) continue;
 820
 821             ifree = -1;
 822             for (d = 0; d < 4; d++) {
 823                 xd = x + dxs[d]; yd = y + dys[d]; id = i + dis[d];
 824                 if (!INGRID(state, xd, yd)) continue;
 825
 826                 if (state->flags[id] & F_CIRCLE)
 827                     goto skip; /* this cell already has a way out */
 828                 if (!(state->flags[id] & F_BLACK)) {
 829                     if (ifree != -1)
 830                         goto skip; /* this cell has >1 white cell around it. */
 831                     ifree = id;
 832                 }
 833             }
 834             if (ifree != -1)
 835                 solver_op_add(ss, ifree%state->w, ifree/state->w, CIRCLE,
 836                               "CC/CE/QM: white cell with single non-black around it");
 837             else {
 838                 debug(("White cell with no escape at (%d,%d)\n", x, y));
 839                 state->impossible = 1;
 840                 return 0;
 841             }
 842 skip: ;
 843         }
 844     }
 845     return ss->n_ops - n_ops;
 846 }
 847
 848 /* If we have 4 numbers the same in a 2x2 corner, the far corner and the
 849  * diagonally-adjacent square must both be black.
 850  * If we have 3 numbers the same in a 2x2 corner, the apex of the L
 851  * thus formed must be black.
 852  * If we have 2 numbers the same in a 2x2 corner, the non-same cell
 853  * one away from the corner must be white. */
 854 static void solve_corner(game_state *state, struct solver_state *ss,
 855                         int x, int y, int dx, int dy)
 856 {
 857     int is[4], ns[4], xx, yy, w = state->w;
 858
 859     for (yy = 0; yy < 2; yy++) {
 860         for (xx = 0; xx < 2; xx++) {
 861             is[yy*2+xx] = (y + dy*yy) * w + (x + dx*xx);
 862             ns[yy*2+xx] = state->nums[is[yy*2+xx]];
 863         }
 864     } /* order is now (corner, side 1, side 2, inner) */
 865
 866     if (ns[0] == ns[1] && ns[0] == ns[2] && ns[0] == ns[3]) {
 867         solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "QC: corner with 4 matching");
 868         solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "QC: corner with 4 matching");
 869     } else if (ns[0] == ns[1] && ns[0] == ns[2]) {
 870         /* corner and 2 sides: apex is corner. */
 871         solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "TC: corner apex from 3 matching");
 872     } else if (ns[1] == ns[2] && ns[1] == ns[3]) {
 873         /* side, side, fourth: apex is fourth. */
 874         solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "TC: inside apex from 3 matching");
 875     } else if (ns[0] == ns[1] || ns[1] == ns[3]) {
 876         /* either way here we match the non-identical side. */
 877         solver_op_add(ss, is[2]%w, is[2]/w, CIRCLE, "DC: corner with 2 matching");
 878     } else if (ns[0] == ns[2] || ns[2] == ns[3]) {
 879         /* ditto */
 880         solver_op_add(ss, is[1]%w, is[1]/w, CIRCLE, "DC: corner with 2 matching");
 881     }
 882 }
 883
 884 static int solve_corners(game_state *state, struct solver_state *ss)
 885 {
 886     int n_ops = ss->n_ops;
 887
 888     solve_corner(state, ss, 0,          0,           1,  1);
 889     solve_corner(state, ss, state->w-1, 0,          -1,  1);
 890     solve_corner(state, ss, state->w-1, state->h-1, -1, -1);
 891     solve_corner(state, ss, 0,          state->h-1,  1, -1);
 892
 893     return ss->n_ops - n_ops;
 894 }
 895
 896 /* If you have the following situation:
 897  * ...
 898  * ...x A x x y A x...
 899  * ...x B x x B y x...
 900  * ...
 901  * then both squares marked 'y' must be white. One of the left-most A or B must
 902  * be white (since two side-by-side black cells are disallowed), which means
 903  * that the corresponding right-most A or B must be black (since you can't
 904  * have two of the same number on one line); thus, the adjacent squares
 905  * to that right-most A or B must be white, which include the two marked 'y'
 906  * in either case.
 907  * Obviously this works in any row or column. It also works if A == B.
 908  * It doesn't work for the degenerate case:
 909  * ...x A A x x
 910  * ...x B y x x
 911  * where the square marked 'y' isn't necessarily white (consider the left-most A
 912  * is black).
 913  *
 914  * */
 915 static void solve_offsetpair_pair(game_state *state, struct solver_state *ss,
 916                                   int x1, int y1, int x2, int y2)
 917 {
 918     int ox, oy, w = state->w, ax, ay, an, d, dx[2], dy[2], dn, xd, yd;
 919
 920     if (x1 == x2) { /* same column */
 921         ox = 1; oy = 0;
 922     } else {
 923         assert(y1 == y2);
 924         ox = 0; oy = 1;
 925     }
 926
 927     /* We try adjacent to (x1,y1) and the two diag. adjacent to (x2, y2).
 928      * We expect to be called twice, once each way around. */
 929     ax = x1+ox; ay = y1+oy;
 930     assert(INGRID(state, ax, ay));
 931     an = state->nums[ay*w + ax];
 932
 933     dx[0] = x2 + ox + oy; dx[1] = x2 + ox - oy;
 934     dy[0] = y2 + oy + ox; dy[1] = y2 + oy - ox;
 935
 936     for (d = 0; d < 2; d++) {
 937         if (INGRID(state, dx[d], dy[d]) && (dx[d] != ax || dy[d] != ay)) {
 938             /* The 'dx != ax || dy != ay' removes the degenerate case,
 939              * mentioned above. */
 940             dn = state->nums[dy[d]*w + dx[d]];
 941             if (an == dn) {
 942                 /* We have a match; so (WLOG) the 'A' marked above are at
 943                  * (x1,y1) and (x2,y2), and the 'B' are at (ax,ay) and (dx,dy). */
 944                 debug(("Found offset-pair: %d at (%d,%d) and (%d,%d)\n",
 945                        state->nums[y1*w + x1], x1, y1, x2, y2));
 946                 debug(("              and: %d at (%d,%d) and (%d,%d)\n",
 947                        an, ax, ay, dx[d], dy[d]));
 948
 949                 xd = dx[d] - x2; yd = dy[d] - y2;
 950                 solver_op_add(ss, x2 + xd, y2, CIRCLE, "IP: next to offset-pair");
 951                 solver_op_add(ss, x2, y2 + yd, CIRCLE, "IP: next to offset-pair");
 952             }
 953         }
 954     }
 955 }
 956
 957 static int solve_offsetpair(game_state *state, struct solver_state *ss)
 958 {
 959     int n_ops = ss->n_ops, x, xx, y, yy, n1, n2;
 960
 961     for (x = 0; x < state->w-1; x++) {
 962         for (y = 0; y < state->h; y++) {
 963             n1 = state->nums[y*state->w + x];
 964             for (yy = y+1; yy < state->h; yy++) {
 965                 n2 = state->nums[yy*state->w + x];
 966                 if (n1 == n2) {
 967                     solve_offsetpair_pair(state, ss, x,  y, x, yy);
 968                     solve_offsetpair_pair(state, ss, x, yy, x,  y);
 969                 }
 970             }
 971         }
 972     }
 973     for (y = 0; y < state->h-1; y++) {
 974         for (x = 0; x < state->w; x++) {
 975             n1 = state->nums[y*state->w + x];
 976             for (xx = x+1; xx < state->w; xx++) {
 977                 n2 = state->nums[y*state->w + xx];
 978                 if (n1 == n2) {
 979                     solve_offsetpair_pair(state, ss, x,  y, xx, y);
 980                     solve_offsetpair_pair(state, ss, xx, y,  x, y);
 981                 }
 982             }
 983         }
 984     }
 985     return ss->n_ops - n_ops;
 986 }
 987
 988 static int solve_hassinglewhiteregion(game_state *state, struct solver_state *ss)
 989 {
 990     int i, j, nwhite = 0, lwhite = -1, szwhite, start, end, next, a, d, x, y;
 991
 992     for (i = 0; i < state->n; i++) {
 993         if (!(state->flags[i] & F_BLACK)) {
 994             nwhite++;
 995             lwhite = i;
 996         }
 997         state->flags[i] &= ~F_SCRATCH;
 998     }
 999     if (lwhite == -1) {
1000         debug(("solve_hassinglewhite: no white squares found!\n"));
1001         state->impossible = 1;
1002         return 0;
1003     }
1004     /* We don't use connect_dsf here; it's too slow, and there's a quicker
1005      * algorithm if all we want is the size of one region. */
1006     /* Having written this, this algorithm is only about 5% faster than
1007      * using a dsf. */
1008     memset(ss->scratch, -1, state->n * sizeof(int));
1009     ss->scratch[0] = lwhite;
1010     state->flags[lwhite] |= F_SCRATCH;
1011     start = 0; end = next = 1;
1012     while (start < end) {
1013         for (a = start; a < end; a++) {
1014             i = ss->scratch[a]; assert(i != -1);
1015             for (d = 0; d < 4; d++) {
1016                 x = (i % state->w) + dxs[d];
1017                 y = (i / state->w) + dys[d];
1018                 j = y*state->w + x;
1019                 if (!INGRID(state, x, y)) continue;
1020                 if (state->flags[j] & (F_BLACK | F_SCRATCH)) continue;
1021                 ss->scratch[next++] = j;
1022                 state->flags[j] |= F_SCRATCH;
1023             }
1024         }
1025         start = end; end = next;
1026     }
1027     szwhite = next;
1028     return (szwhite == nwhite) ? 1 : 0;
1029 }
1030
1031 static void solve_removesplits_check(game_state *state, struct solver_state *ss,
1032                                      int x, int y)
1033 {
1034     int i = y*state->w + x, issingle;
1035
1036     if (!INGRID(state, x, y)) return;
1037     if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK))
1038         return;
1039
1040     /* If putting a black square at (x,y) would make the white region
1041      * non-contiguous, it must be circled. */
1042     state->flags[i] |= F_BLACK;
1043     issingle = solve_hassinglewhiteregion(state, ss);
1044     state->flags[i] &= ~F_BLACK;
1045
1046     if (!issingle)
1047         solver_op_add(ss, x, y, CIRCLE, "MC: black square here would split white region");
1048 }
1049
1050 /* For all black squares, search in squares diagonally adjacent to see if
1051  * we can rule out putting a black square there (because it would make the
1052  * white region non-contiguous). */
1053 /* This function is likely to be somewhat slow. */
1054 static int solve_removesplits(game_state *state, struct solver_state *ss)
1055 {
1056     int i, x, y, n_ops = ss->n_ops;
1057
1058     if (!solve_hassinglewhiteregion(state, ss)) {
1059         debug(("solve_removesplits: white region is not contiguous at start!\n"));
1060         state->impossible = 1;
1061         return 0;
1062     }
1063
1064     for (i = 0; i < state->n; i++) {
1065         if (!(state->flags[i] & F_BLACK)) continue;
1066
1067         x = i%state->w; y = i/state->w;
1068         solve_removesplits_check(state, ss, x-1, y-1);
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     }
1073     return ss->n_ops - n_ops;
1074 }
1075
1076 /*
1077  * This function performs a solver step that isn't implicit in the rules
1078  * of the game and is thus treated somewhat differently.
1079  *
1080  * It marks cells whose number does not exist elsewhere in its row/column
1081  * with circles. As it happens the game generator here does mean that this
1082  * is always correct, but it's a solving method that people should not have
1083  * to rely upon (except in the hidden 'sneaky' difficulty setting) and so
1084  * all grids at 'tricky' and above are checked to make sure that the grid
1085  * is no easier if this solving step is performed beforehand.
1086  *
1087  * Calling with ss=NULL just returns the number of sneaky deductions that
1088  * would have been made.
1089  */
1090 static int solve_sneaky(game_state *state, struct solver_state *ss)
1091 {
1092     int i, ii, x, xx, y, yy, nunique = 0;
1093
1094     /* Clear SCRATCH flags. */
1095     for (i = 0; i < state->n; i++) state->flags[i] &= ~F_SCRATCH;
1096
1097     for (x = 0; x < state->w; x++) {
1098         for (y = 0; y < state->h; y++) {
1099             i = y*state->w + x;
1100
1101             /* Check for duplicate numbers on our row, mark (both) if so */
1102             for (xx = x; xx < state->w; xx++) {
1103                 ii = y*state->w + xx;
1104                 if (i == ii) continue;
1105
1106                 if (state->nums[i] == state->nums[ii]) {
1107                     state->flags[i] |= F_SCRATCH;
1108                     state->flags[ii] |= F_SCRATCH;
1109                 }
1110             }
1111
1112             /* Check for duplicate numbers on our col, mark (both) if so */
1113             for (yy = y; yy < state->h; yy++) {
1114                 ii = yy*state->w + x;
1115                 if (i == ii) continue;
1116
1117                 if (state->nums[i] == state->nums[ii]) {
1118                     state->flags[i] |= F_SCRATCH;
1119                     state->flags[ii] |= F_SCRATCH;
1120                 }
1121             }
1122         }
1123     }
1124
1125     /* Any cell with no marking has no duplicates on its row or column:
1126      * set its CIRCLE. */
1127     for (i = 0; i < state->n; i++) {
1128         if (!(state->flags[i] & F_SCRATCH)) {
1129             if (ss) solver_op_add(ss, i%state->w, i/state->w, CIRCLE,
1130                                   "SNEAKY: only one of its number in row and col");
1131             nunique += 1;
1132         } else
1133             state->flags[i] &= ~F_SCRATCH;
1134     }
1135     return nunique;
1136 }
1137
1138 static int solve_specific(game_state *state, int diff, int sneaky)
1139 {
1140     struct solver_state *ss = solver_state_new(state);
1141
1142     if (sneaky) solve_sneaky(state, ss);
1143
1144     /* Some solver operations we only have to perform once --
1145      * they're only based on the numbers available, and not black
1146      * squares or circles which may be added later. */
1147
1148     solve_singlesep(state, ss);        /* never sets impossible */
1149     solve_doubles(state, ss);          /* ditto */
1150     solve_corners(state, ss);          /* ditto */
1151
1152     if (diff >= DIFF_TRICKY)
1153         solve_offsetpair(state, ss);       /* ditto */
1154
1155     while (1) {
1156         if (ss->n_ops > 0) solver_ops_do(state, ss);
1157         if (state->impossible) break;
1158
1159         if (solve_allblackbutone(state, ss) > 0) continue;
1160         if (state->impossible) break;
1161
1162         if (diff >= DIFF_TRICKY) {
1163             if (solve_removesplits(state, ss) > 0) continue;
1164             if (state->impossible) break;
1165         }
1166
1167         break;
1168     }
1169
1170     solver_state_free(ss);
1171     return state->impossible ? -1 : check_complete(state, CC_MUST_FILL);
1172 }
1173
1174 static char *solve_game(game_state *state, game_state *currstate,
1175                         char *aux, char **error)
1176 {
1177     game_state *solved = dup_game(currstate);
1178     char *move = NULL;
1179
1180     if (solve_specific(solved, DIFF_ANY, 0) > 0) goto solved;
1181     free_game(solved);
1182
1183     solved = dup_game(state);
1184     if (solve_specific(solved, DIFF_ANY, 0) > 0) goto solved;
1185     free_game(solved);
1186
1187     *error = "Unable to solve puzzle.";
1188     return NULL;
1189
1190 solved:
1191     move = game_state_diff(currstate, solved, 1);
1192     free_game(solved);
1193     return move;
1194 }
1195
1196 /* --- Game generation --- */
1197
1198 /* A correctly completed Hitori board is essentially a latin square
1199  * (no duplicated numbers in any row or column) with black squares
1200  * added such that no black square touches another, and the white
1201  * squares make a contiguous region.
1202  *
1203  * So we can generate it by:
1204    * constructing a latin square
1205    * adding black squares at random (minding the constraints)
1206    * altering the numbers under the new black squares such that
1207       the solver gets a headstart working out where they are.
1208  */
1209
1210 static int new_game_is_good(game_params *params,
1211                             game_state *state, game_state *tosolve)
1212 {
1213     int sret, sret_easy = 0;
1214
1215     memcpy(tosolve->nums, state->nums, state->n * sizeof(int));
1216     memset(tosolve->flags, 0, state->n * sizeof(unsigned int));
1217     tosolve->completed = tosolve->impossible = 0;
1218
1219     /*
1220      * We try and solve it twice, once at our requested difficulty level
1221      * (ensuring it's soluble at all) and once at the level below (if
1222      * it exists), which we hope to fail: if you can also solve it at
1223      * the level below then it's too easy and we have to try again.
1224      *
1225      * With this puzzle in particular there's an extra finesse, which is
1226      * that we check that the generated puzzle isn't too easy _with
1227      * an extra solver step first_, which is the 'sneaky' mode of deductions
1228      * (asserting that any number which fulfils the latin-square rules
1229      * on its row/column must be white). This is an artefact of the
1230      * generation process and not implicit in the rules, so we don't want
1231      * people to be able to use it to make the puzzle easier.
1232      */
1233
1234     assert(params->diff < DIFF_MAX);
1235     sret = solve_specific(tosolve, params->diff, 0);
1236     if (params->diff > DIFF_EASY) {
1237         memset(tosolve->flags, 0, state->n * sizeof(unsigned int));
1238         tosolve->completed = tosolve->impossible = 0;
1239
1240         /* this is the only time the 'sneaky' flag is set to 1. */
1241         sret_easy = solve_specific(tosolve, params->diff-1, 1);
1242     }
1243
1244     if (sret <= 0 || sret_easy > 0) {
1245         debug(("Generated puzzle %s at chosen difficulty %s\n",
1246                sret <= 0 ? "insoluble" : "too easy",
1247                singles_diffnames[params->diff]));
1248         return 0;
1249     }
1250     return 1;
1251 }
1252
1253 #define MAXTRIES 20
1254
1255 static int best_black_col(game_state *state, random_state *rs, int *scratch,
1256                           int i, int *rownums, int *colnums)
1257 {
1258     int w = state->w, x = i%w, y = i/w, j, o = state->o;
1259
1260     /* Randomise the list of numbers to try. */
1261     for (i = 0; i < o; i++) scratch[i] = i;
1262     shuffle(scratch, o, sizeof(int), rs);
1263
1264     /* Try each number in turn, first giving preference to removing
1265      * latin-square characteristics (i.e. those numbers which only
1266      * occur once in a row/column). The '&&' here, although intuitively
1267      * wrong, results in a smaller number of 'sneaky' deductions on
1268      * solvable boards. */
1269     for (i = 0; i < o; i++) {
1270         j = scratch[i] + 1;
1271         if (rownums[y*o + j-1] == 1 && colnums[x*o + j-1] == 1)
1272             goto found;
1273     }
1274
1275     /* Then try each number in turn returning the first one that's
1276      * not actually unique in its row/column (see comment below) */
1277     for (i = 0; i < o; i++) {
1278         j = scratch[i] + 1;
1279         if (rownums[y*o + j-1] != 0 || colnums[x*o + j-1] != 0)
1280             goto found;
1281     }
1282     assert(!"unable to place number under black cell.");
1283     return 0;
1284
1285 found:
1286     /* Update column and row counts assuming this number will be placed. */
1287     rownums[y*o + j-1] += 1;
1288     colnums[x*o + j-1] += 1;
1289     return j;
1290 }
1291
1292 static char *new_game_desc(game_params *params, random_state *rs,
1293                            char **aux, int interactive)
1294 {
1295     game_state *state = blank_game(params->w, params->h);
1296     game_state *tosolve = blank_game(params->w, params->h);
1297     int i, j, *scratch, *rownums, *colnums, x, y, ntries;
1298     int w = state->w, h = state->h, o = state->o;
1299     char *ret;
1300     digit *latin;
1301     struct solver_state *ss = solver_state_new(state);
1302
1303     scratch = snewn(state->n, int);
1304     rownums = snewn(h*o, int);
1305     colnums = snewn(w*o, int);
1306
1307 generate:
1308     ss->n_ops = 0;
1309     debug(("Starting game generation, size %dx%d\n", w, h));
1310
1311     memset(state->flags, 0, state->n*sizeof(unsigned int));
1312
1313     /* First, generate the latin rectangle.
1314      * The order of this, o, is max(w,h). */
1315     latin = latin_generate_rect(w, h, rs);
1316     for (i = 0; i < state->n; i++)
1317         state->nums[i] = (int)latin[i];
1318     sfree(latin);
1319     debug_state("State after latin square", state);
1320
1321     /* Add black squares at random, using bits of solver as we go (to lay
1322      * white squares), until we can lay no more blacks. */
1323     for (i = 0; i < state->n; i++)
1324         scratch[i] = i;
1325     shuffle(scratch, state->n, sizeof(int), rs);
1326     for (j = 0; j < state->n; j++) {
1327         i = scratch[j];
1328         if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK)) {
1329             debug(("generator skipping (%d,%d): %s\n", i%w, i/w,
1330                    (state->flags[i] & F_CIRCLE) ? "CIRCLE" : "BLACK"));
1331             continue; /* solver knows this must be one or the other already. */
1332         }
1333
1334         /* Add a random black cell... */
1335         solver_op_add(ss, i%w, i/w, BLACK, "Generator: adding random black cell");
1336         solver_ops_do(state, ss);
1337
1338         /* ... and do as well as we know how to lay down whites that are now forced. */
1339         solve_allblackbutone(state, ss);
1340         solver_ops_do(state, ss);
1341
1342         solve_removesplits(state, ss);
1343         solver_ops_do(state, ss);
1344
1345         if (state->impossible) {
1346             debug(("generator made impossible, restarting...\n"));
1347             goto generate;
1348         }
1349     }
1350     debug_state("State after adding blacks", state);
1351
1352     /* Now we know which squares are white and which are black, we lay numbers
1353      * under black squares at random, except that the number must appear in
1354      * white cells at least once more in the same column or row as that [black]
1355      * square. That's necessary to avoid multiple solutions, where blackening
1356      * squares in the finished puzzle becomes optional. We use two arrays:
1357      *
1358      * rownums[ROW * o + NUM-1] is the no. of white cells containing NUM in y=ROW
1359      * colnums[COL * o + NUM-1] is the no. of white cells containing NUM in x=COL
1360      */
1361
1362     memset(rownums, 0, h*o * sizeof(int));
1363     memset(colnums, 0, w*o * sizeof(int));
1364     for (i = 0; i < state->n; i++) {
1365         if (state->flags[i] & F_BLACK) continue;
1366         j = state->nums[i];
1367         x = i%w; y = i/w;
1368         rownums[y * o + j-1] += 1;
1369         colnums[x * o + j-1] += 1;
1370     }
1371
1372     ntries = 0;
1373 randomise:
1374     for (i = 0; i < state->n; i++) {
1375         if (!(state->flags[i] & F_BLACK)) continue;
1376         state->nums[i] = best_black_col(state, rs, scratch, i, rownums, colnums);
1377     }
1378     debug_state("State after adding numbers", state);
1379
1380     /* DIFF_ANY just returns whatever we first generated, for testing purposes. */
1381     if (params->diff != DIFF_ANY &&
1382         !new_game_is_good(params, state, tosolve)) {
1383         ntries++;
1384         if (ntries > MAXTRIES) {
1385             debug(("Ran out of randomisation attempts, re-generating.\n"));
1386             goto generate;
1387         }
1388         debug(("Re-randomising numbers under black squares.\n"));
1389         goto randomise;
1390     }
1391
1392     ret = generate_desc(state, 0);
1393
1394     free_game(tosolve);
1395     free_game(state);
1396     solver_state_free(ss);
1397     sfree(scratch);
1398     sfree(rownums);
1399     sfree(colnums);
1400
1401     return ret;
1402 }
1403
1404 static char *validate_desc(game_params *params, char *desc)
1405 {
1406     char *ret = NULL;
1407
1408     unpick_desc(params, desc, NULL, &ret);
1409     return ret;
1410 }
1411
1412 static game_state *new_game(midend *me, game_params *params, char *desc)
1413 {
1414     game_state *state = NULL;
1415
1416     unpick_desc(params, desc, &state, NULL);
1417     if (!state) assert(!"new_game failed to unpick");
1418     return state;
1419 }
1420
1421 /* --- Game UI and move routines --- */
1422
1423 struct game_ui {
1424     int cx, cy, cshow;
1425     int show_black_nums;
1426 };
1427
1428 static game_ui *new_ui(game_state *state)
1429 {
1430     game_ui *ui = snew(game_ui);
1431
1432     ui->cx = ui->cy = ui->cshow = 0;
1433     ui->show_black_nums = 0;
1434
1435     return ui;
1436 }
1437
1438 static void free_ui(game_ui *ui)
1439 {
1440     sfree(ui);
1441 }
1442
1443 static char *encode_ui(game_ui *ui)
1444 {
1445     return NULL;
1446 }
1447
1448 static void decode_ui(game_ui *ui, char *encoding)
1449 {
1450 }
1451
1452 static void game_changed_state(game_ui *ui, game_state *oldstate,
1453                                game_state *newstate)
1454 {
1455     if (!oldstate->completed && newstate->completed)
1456         ui->cshow = 0;
1457 }
1458
1459 #define DS_BLACK        0x1
1460 #define DS_CIRCLE       0x2
1461 #define DS_CURSOR       0x4
1462 #define DS_BLACK_NUM    0x8
1463 #define DS_ERROR        0x10
1464 #define DS_FLASH        0x20
1465 #define DS_IMPOSSIBLE   0x40
1466
1467 struct game_drawstate {
1468     int tilesize, started, solved;
1469     int w, h, n;
1470
1471     unsigned int *flags;
1472 };
1473
1474 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1475                             int mx, int my, int button)
1476 {
1477     char buf[80], c;
1478     int i, x = FROMCOORD(mx), y = FROMCOORD(my);
1479     enum { NONE, TOGGLE_BLACK, TOGGLE_CIRCLE, UI } action = NONE;
1480
1481     if (IS_CURSOR_MOVE(button)) {
1482         move_cursor(button, &ui->cx, &ui->cy, state->w, state->h, 1);
1483         ui->cshow = 1;
1484         action = UI;
1485     } else if (IS_CURSOR_SELECT(button)) {
1486         x = ui->cx; y = ui->cy;
1487         if (!ui->cshow) {
1488             action = UI;
1489             ui->cshow = 1;
1490         }
1491         if (button == CURSOR_SELECT) {
1492             action = TOGGLE_BLACK;
1493         } else if (button == CURSOR_SELECT2) {
1494             action = TOGGLE_CIRCLE;
1495         }
1496     } else if (IS_MOUSE_DOWN(button)) {
1497         if (ui->cshow) {
1498             ui->cshow = 0;
1499             action = UI;
1500         }
1501         if (!INGRID(state, x, y)) {
1502             ui->show_black_nums = 1 - ui->show_black_nums;
1503             action = UI; /* this wants to be a per-game option. */
1504         } else if (button == LEFT_BUTTON) {
1505             action = TOGGLE_BLACK;
1506         } else if (button == RIGHT_BUTTON) {
1507             action = TOGGLE_CIRCLE;
1508         }
1509     }
1510     if (action == UI) return "";
1511
1512     if (action == TOGGLE_BLACK || action == TOGGLE_CIRCLE) {
1513         i = y * state->w + x;
1514         if (state->flags[i] & (F_BLACK | F_CIRCLE))
1515             c = 'E';
1516         else
1517             c = (action == TOGGLE_BLACK) ? 'B' : 'C';
1518         sprintf(buf, "%c%d,%d", (int)c, x, y);
1519         return dupstr(buf);
1520     }
1521
1522     return NULL;
1523 }
1524
1525 static game_state *execute_move(game_state *state, char *move)
1526 {
1527     game_state *ret = dup_game(state);
1528     int x, y, i, n;
1529
1530     debug(("move: %s\n", move));
1531
1532     while (*move) {
1533         char c = *move;
1534         if (c == 'B' || c == 'C' || c == 'E') {
1535             move++;
1536             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1537                 !INGRID(state, x, y))
1538                 goto badmove;
1539
1540             i = y*ret->w + x;
1541             ret->flags[i] &= ~(F_CIRCLE | F_BLACK); /* empty first, always. */
1542             if (c == 'B')
1543                 ret->flags[i] |= F_BLACK;
1544             else if (c == 'C')
1545                 ret->flags[i] |= F_CIRCLE;
1546             move += n;
1547         } else if (c == 'S') {
1548             move++;
1549             ret->used_solve = 1;
1550         } else
1551             goto badmove;
1552
1553         if (*move == ';')
1554             move++;
1555         else if (*move)
1556             goto badmove;
1557     }
1558     if (check_complete(ret, CC_MARK_ERRORS)) ret->completed = 1;
1559     return ret;
1560
1561 badmove:
1562     free_game(ret);
1563     return NULL;
1564 }
1565
1566 /* ----------------------------------------------------------------------
1567  * Drawing routines.
1568  */
1569
1570 static void game_compute_size(game_params *params, int tilesize,
1571                               int *x, int *y)
1572 {
1573     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1574     struct { int tilesize; } ads, *ds = &ads;
1575     ads.tilesize = tilesize;
1576
1577     *x = TILE_SIZE * params->w + 2 * BORDER;
1578     *y = TILE_SIZE * params->h + 2 * BORDER;
1579 }
1580
1581 static void game_set_size(drawing *dr, game_drawstate *ds,
1582                           game_params *params, int tilesize)
1583 {
1584     ds->tilesize = tilesize;
1585 }
1586
1587 static float *game_colours(frontend *fe, int *ncolours)
1588 {
1589     float *ret = snewn(3 * NCOLOURS, float);
1590     int i;
1591
1592     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1593     for (i = 0; i < 3; i++) {
1594         ret[COL_BLACK * 3 + i] = 0.0F;
1595         ret[COL_BLACKNUM * 3 + i] = 0.4F;
1596         ret[COL_WHITE * 3 + i] = 1.0F;
1597         ret[COL_GRID * 3 + i] = ret[COL_LOWLIGHT * 3 + i];
1598     }
1599     ret[COL_CURSOR * 3 + 0] = 0.2F;
1600     ret[COL_CURSOR * 3 + 1] = 0.8F;
1601     ret[COL_CURSOR * 3 + 2] = 0.0F;
1602
1603     ret[COL_ERROR * 3 + 0] = 1.0F;
1604     ret[COL_ERROR * 3 + 1] = 0.0F;
1605     ret[COL_ERROR * 3 + 2] = 0.0F;
1606
1607     *ncolours = NCOLOURS;
1608     return ret;
1609 }
1610
1611 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1612 {
1613     struct game_drawstate *ds = snew(struct game_drawstate);
1614
1615     ds->tilesize = ds->started = ds->solved = 0;
1616     ds->w = state->w;
1617     ds->h = state->h;
1618     ds->n = state->n;
1619
1620     ds->flags = snewn(state->n, unsigned int);
1621
1622     memset(ds->flags, 0, state->n*sizeof(unsigned int));
1623
1624     return ds;
1625 }
1626
1627 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1628 {
1629     sfree(ds->flags);
1630     sfree(ds);
1631 }
1632
1633 static void tile_redraw(drawing *dr, game_drawstate *ds, int x, int y,
1634                         int num, unsigned int f)
1635 {
1636     int tcol, bg, dnum, cx, cy, tsz;
1637     char buf[32];
1638
1639     if (f & DS_BLACK) {
1640         bg = (f & DS_ERROR) ? COL_ERROR : COL_BLACK;
1641         tcol = COL_BLACKNUM;
1642         dnum = (f & DS_BLACK_NUM) ? 1 : 0;
1643     } else {
1644         bg = (f & DS_FLASH) ? COL_LOWLIGHT : COL_BACKGROUND;
1645         tcol = (f & DS_ERROR) ? COL_ERROR : COL_BLACK;
1646         dnum = 1;
1647     }
1648
1649     cx = x + TILE_SIZE/2; cy = y + TILE_SIZE/2;
1650
1651     draw_rect(dr, x,    y, TILE_SIZE, TILE_SIZE, bg);
1652     draw_rect_outline(dr, x, y, TILE_SIZE, TILE_SIZE,
1653                       (f & DS_IMPOSSIBLE) ? COL_ERROR : COL_GRID);
1654
1655     if (f & DS_CIRCLE) {
1656         draw_circle(dr, cx, cy, CRAD, tcol, tcol);
1657         draw_circle(dr, cx, cy, CRAD-1, bg, tcol);
1658     }
1659
1660     if (dnum) {
1661         sprintf(buf, "%d", num);
1662         if (strlen(buf) == 1)
1663             tsz = TEXTSZ;
1664         else
1665             tsz = (CRAD*2 - 1) / strlen(buf);
1666         draw_text(dr, cx, cy, FONT_VARIABLE, tsz,
1667                   ALIGN_VCENTRE | ALIGN_HCENTRE, tcol, buf);
1668     }
1669
1670     if (f & DS_CURSOR)
1671         draw_rect_corners(dr, cx, cy, TEXTSZ/2, COL_CURSOR);
1672
1673     draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
1674 }
1675
1676 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1677                         game_state *state, int dir, game_ui *ui,
1678                         float animtime, float flashtime)
1679 {
1680     int x, y, i, flash;
1681     unsigned int f;
1682
1683     flash = (int)(flashtime * 5 / FLASH_TIME) % 2;
1684
1685     if (!ds->started) {
1686         int wsz = TILE_SIZE * state->w + 2 * BORDER;
1687         int hsz = TILE_SIZE * state->h + 2 * BORDER;
1688         draw_rect(dr, 0, 0, wsz, hsz, COL_BACKGROUND);
1689         draw_rect_outline(dr, COORD(0)-1, COORD(0)-1,
1690                           TILE_SIZE * state->w + 2, TILE_SIZE * state->h + 2,
1691                           COL_GRID);
1692         draw_update(dr, 0, 0, wsz, hsz);
1693     }
1694     for (x = 0; x < state->w; x++) {
1695         for (y = 0; y < state->h; y++) {
1696             i = y*state->w + x;
1697             f = 0;
1698
1699             if (flash) f |= DS_FLASH;
1700             if (state->impossible) f |= DS_IMPOSSIBLE;
1701
1702             if (ui->cshow && x == ui->cx && y == ui->cy)
1703                 f |= DS_CURSOR;
1704             if (state->flags[i] & F_BLACK) {
1705                 f |= DS_BLACK;
1706                 if (ui->show_black_nums) f |= DS_BLACK_NUM;
1707             }
1708             if (state->flags[i] & F_CIRCLE)
1709                 f |= DS_CIRCLE;
1710             if (state->flags[i] & F_ERROR)
1711                 f |= DS_ERROR;
1712
1713             if (!ds->started || ds->flags[i] != f) {
1714                 tile_redraw(dr, ds, COORD(x), COORD(y),
1715                             state->nums[i], f);
1716                 ds->flags[i] = f;
1717             }
1718         }
1719     }
1720     ds->started = 1;
1721 }
1722
1723 static float game_anim_length(game_state *oldstate, game_state *newstate,
1724                               int dir, game_ui *ui)
1725 {
1726     return 0.0F;
1727 }
1728
1729 static float game_flash_length(game_state *oldstate, game_state *newstate,
1730                                int dir, game_ui *ui)
1731 {
1732     if (!oldstate->completed &&
1733         newstate->completed && !newstate->used_solve)
1734         return FLASH_TIME;
1735     return 0.0F;
1736 }
1737
1738 static int game_status(game_state *state)
1739 {
1740     return state->completed ? +1 : 0;
1741 }
1742
1743 static int game_timing_state(game_state *state, game_ui *ui)
1744 {
1745     return TRUE;
1746 }
1747
1748 static void game_print_size(game_params *params, float *x, float *y)
1749 {
1750     int pw, ph;
1751
1752     /* 8mm squares by default. */
1753     game_compute_size(params, 800, &pw, &ph);
1754     *x = pw / 100.0F;
1755     *y = ph / 100.0F;
1756 }
1757
1758 static void game_print(drawing *dr, game_state *state, int tilesize)
1759 {
1760     int ink = print_mono_colour(dr, 0);
1761     int paper = print_mono_colour(dr, 1);
1762     int x, y, ox, oy, i;
1763     char buf[32];
1764
1765     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1766     game_drawstate ads, *ds = &ads;
1767     game_set_size(dr, ds, NULL, tilesize);
1768
1769     print_line_width(dr, 2 * TILE_SIZE / 40);
1770
1771     for (x = 0; x < state->w; x++) {
1772         for (y = 0; y < state->h; y++) {
1773             ox = COORD(x); oy = COORD(y);
1774             i = y*state->w+x;
1775
1776             if (state->flags[i] & F_BLACK) {
1777                 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1778             } else {
1779                 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1780
1781                 if (state->flags[i] & DS_CIRCLE)
1782                     draw_circle(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, CRAD,
1783                                 paper, ink);
1784
1785                 sprintf(buf, "%d", state->nums[i]);
1786                 draw_text(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, FONT_VARIABLE,
1787                           TEXTSZ/strlen(buf), ALIGN_VCENTRE | ALIGN_HCENTRE,
1788                           ink, buf);
1789             }
1790         }
1791     }
1792 }
1793
1794 #ifdef COMBINED
1795 #define thegame singles
1796 #endif
1797
1798 const struct game thegame = {
1799     "Singles", "games.singles", "singles",
1800     default_params,
1801     game_fetch_preset,
1802     decode_params,
1803     encode_params,
1804     free_params,
1805     dup_params,
1806     TRUE, game_configure, custom_params,
1807     validate_params,
1808     new_game_desc,
1809     validate_desc,
1810     new_game,
1811     dup_game,
1812     free_game,
1813     TRUE, solve_game,
1814     TRUE, game_can_format_as_text_now, game_text_format,
1815     new_ui,
1816     free_ui,
1817     encode_ui,
1818     decode_ui,
1819     game_changed_state,
1820     interpret_move,
1821     execute_move,
1822     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1823     game_colours,
1824     game_new_drawstate,
1825     game_free_drawstate,
1826     game_redraw,
1827     game_anim_length,
1828     game_flash_length,
1829     game_status,
1830     TRUE, FALSE, game_print_size, game_print,
1831     FALSE,                             /* wants_statusbar */
1832     FALSE, game_timing_state,
1833     REQUIRE_RBUTTON,                   /* flags */
1834 };
1835
1836 #ifdef STANDALONE_SOLVER
1837
1838 #include <time.h>
1839 #include <stdarg.h>
1840
1841 static void start_soak(game_params *p, random_state *rs)
1842 {
1843     time_t tt_start, tt_now, tt_last;
1844     char *desc, *aux;
1845     game_state *s;
1846     int i, n = 0, ndiff[DIFF_MAX], diff, sret, nblack = 0, nsneaky = 0;
1847
1848     tt_start = tt_now = time(NULL);
1849
1850     printf("Soak-testing a %dx%d grid.\n", p->w, p->h);
1851     p->diff = DIFF_ANY;
1852
1853     memset(ndiff, 0, DIFF_MAX * sizeof(int));
1854
1855     while (1) {
1856         n++;
1857         desc = new_game_desc(p, rs, &aux, 0);
1858         s = new_game(NULL, p, desc);
1859         nsneaky += solve_sneaky(s, NULL);
1860
1861         for (diff = 0; diff < DIFF_MAX; diff++) {
1862             memset(s->flags, 0, s->n * sizeof(unsigned int));
1863             s->completed = s->impossible = 0;
1864             sret = solve_specific(s, diff, 0);
1865             if (sret > 0) {
1866                 ndiff[diff]++;
1867                 break;
1868             } else if (sret < 0)
1869                 fprintf(stderr, "Impossible! %s\n", desc);
1870         }
1871         for (i = 0; i < s->n; i++) {
1872             if (s->flags[i] & F_BLACK) nblack++;
1873         }
1874         free_game(s);
1875         sfree(desc);
1876
1877         tt_last = time(NULL);
1878         if (tt_last > tt_now) {
1879             tt_now = tt_last;
1880             printf("%d total, %3.1f/s, bl/sn %3.1f%%/%3.1f%%: ",
1881                    n, (double)n / ((double)tt_now - tt_start),
1882                    ((double)nblack * 100.0) / (double)(n * p->w * p->h),
1883                    ((double)nsneaky * 100.0) / (double)(n * p->w * p->h));
1884             for (diff = 0; diff < DIFF_MAX; diff++) {
1885                 if (diff > 0) printf(", ");
1886                 printf("%d (%3.1f%%) %s",
1887                        ndiff[diff], (double)ndiff[diff] * 100.0 / (double)n,
1888                        singles_diffnames[diff]);
1889             }
1890             printf("\n");
1891         }
1892     }
1893 }
1894
1895 int main(int argc, char **argv)
1896 {
1897     char *id = NULL, *desc, *desc_gen = NULL, *tgame, *err, *aux;
1898     game_state *s = NULL;
1899     game_params *p = NULL;
1900     int soln, soak = 0, ret = 1;
1901     time_t seed = time(NULL);
1902     random_state *rs = NULL;
1903
1904     setvbuf(stdout, NULL, _IONBF, 0);
1905
1906     while (--argc > 0) {
1907         char *p = *++argv;
1908         if (!strcmp(p, "-v")) {
1909             verbose = 1;
1910         } else if (!strcmp(p, "--soak")) {
1911             soak = 1;
1912         } else if (!strcmp(p, "--seed")) {
1913             if (argc == 0) {
1914                 fprintf(stderr, "%s: --seed needs an argument", argv[0]);
1915                 goto done;
1916             }
1917             seed = (time_t)atoi(*++argv);
1918             argc--;
1919         } else if (*p == '-') {
1920             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
1921             return 1;
1922         } else {
1923             id = p;
1924         }
1925     }
1926
1927     rs = random_new((void*)&seed, sizeof(time_t));
1928
1929     if (!id) {
1930         fprintf(stderr, "usage: %s [-v] [--soak] <params> | <game_id>\n", argv[0]);
1931         goto done;
1932     }
1933     desc = strchr(id, ':');
1934     if (desc) *desc++ = '\0';
1935
1936     p = default_params();
1937     decode_params(p, id);
1938     err = validate_params(p, 1);
1939     if (err) {
1940         fprintf(stderr, "%s: %s", argv[0], err);
1941         goto done;
1942     }
1943
1944     if (soak) {
1945         if (desc) {
1946             fprintf(stderr, "%s: --soak only needs params, not game desc.\n", argv[0]);
1947             goto done;
1948         }
1949         start_soak(p, rs);
1950     } else {
1951         if (!desc) desc = desc_gen = new_game_desc(p, rs, &aux, 0);
1952
1953         err = validate_desc(p, desc);
1954         if (err) {
1955             fprintf(stderr, "%s: %s\n", argv[0], err);
1956             free_params(p);
1957             goto done;
1958         }
1959         s = new_game(NULL, p, desc);
1960
1961         if (verbose) {
1962             tgame = game_text_format(s);
1963             fputs(tgame, stdout);
1964             sfree(tgame);
1965         }
1966
1967         soln = solve_specific(s, DIFF_ANY, 0);
1968         tgame = game_text_format(s);
1969         fputs(tgame, stdout);
1970         sfree(tgame);
1971         printf("Game was %s.\n\n",
1972                soln < 0 ? "impossible" : soln > 0 ? "solved" : "not solved");
1973     }
1974     ret = 0;
1975
1976 done:
1977     if (desc_gen) sfree(desc_gen);
1978     if (p) free_params(p);
1979     if (s) free_game(s);
1980     if (rs) random_free(rs);
1981
1982     return ret;
1983 }
1984
1985 #endif
1986
1987
1988 /* vim: set shiftwidth=4 tabstop=8: */