singles.c

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