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