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