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) > 0) goto solved;
1168     free_game(solved);
1169
1170     solved = dup_game(state);
1171     if (solve_specific(solved, DIFF_ANY, 0) > 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             goto found;
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             goto found;
1268     }
1269     assert(!"unable to place number under black cell.");
1270     return 0;
1271
1272 found:
1273     /* Update column and row counts assuming this number will be placed. */
1274     rownums[y*o + j-1] += 1;
1275     colnums[x*o + j-1] += 1;
1276     return j;
1277 }
1278
1279 static char *new_game_desc(game_params *params, random_state *rs,
1280                            char **aux, int interactive)
1281 {
1282     game_state *state = blank_game(params->w, params->h);
1283     game_state *tosolve = blank_game(params->w, params->h);
1284     int i, j, *scratch, *rownums, *colnums, x, y, ntries;
1285     int w = state->w, h = state->h, o = state->o;
1286     char *ret;
1287     digit *latin;
1288     struct solver_state *ss = solver_state_new(state);
1289
1290     scratch = snewn(state->n, int);
1291     rownums = snewn(h*o, int);
1292     colnums = snewn(w*o, int);
1293
1294 generate:
1295     ss->n_ops = 0;
1296     debug(("Starting game generation, size %dx%d", w, h));
1297
1298     memset(state->flags, 0, state->n*sizeof(unsigned int));
1299
1300     /* First, generate the latin rectangle.
1301      * The order of this, o, is max(w,h). */
1302     latin = latin_generate_rect(w, h, rs);
1303     for (i = 0; i < state->n; i++)
1304         state->nums[i] = (int)latin[i];
1305     sfree(latin);
1306     debug_state("State after latin square", state);
1307
1308     /* Add black squares at random, using bits of solver as we go (to lay
1309      * white squares), until we can lay no more blacks. */
1310     for (i = 0; i < state->n; i++)
1311         scratch[i] = i;
1312     shuffle(scratch, state->n, sizeof(int), rs);
1313     for (j = 0; j < state->n; j++) {
1314         i = scratch[j];
1315         if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK)) {
1316             debug(("generator skipping (%d,%d): %s", i%w, i/w,
1317                    (state->flags[i] & F_CIRCLE) ? "CIRCLE" : "BLACK"));
1318             continue; /* solver knows this must be one or the other already. */
1319         }
1320
1321         /* Add a random black cell... */
1322         solver_op_add(ss, i%w, i/w, BLACK, "Generator: adding random black cell");
1323         solver_ops_do(state, ss);
1324
1325         /* ... and do as well as we know how to lay down whites that are now forced. */
1326         solve_allblackbutone(state, ss);
1327         solver_ops_do(state, ss);
1328
1329         solve_removesplits(state, ss);
1330         solver_ops_do(state, ss);
1331
1332         if (state->impossible) {
1333             debug(("generator made impossible, restarting..."));
1334             goto generate;
1335         }
1336     }
1337     debug_state("State after adding blacks", state);
1338
1339     /* Now we know which squares are white and which are black, we lay numbers
1340      * under black squares at random, except that the number must appear in
1341      * white cells at least once more in the same column or row as that [black]
1342      * square. That's necessary to avoid multiple solutions, where blackening
1343      * squares in the finished puzzle becomes optional. We use two arrays:
1344      *
1345      * rownums[ROW * o + NUM-1] is the no. of white cells containing NUM in y=ROW
1346      * colnums[COL * o + NUM-1] is the no. of white cells containing NUM in x=COL
1347      */
1348
1349     memset(rownums, 0, h*o * sizeof(int));
1350     memset(colnums, 0, w*o * sizeof(int));
1351     for (i = 0; i < state->n; i++) {
1352         if (state->flags[i] & F_BLACK) continue;
1353         j = state->nums[i];
1354         x = i%w; y = i/w;
1355         rownums[y * o + j-1] += 1;
1356         colnums[x * o + j-1] += 1;
1357     }
1358
1359     ntries = 0;
1360 randomise:
1361     for (i = 0; i < state->n; i++) {
1362         if (!(state->flags[i] & F_BLACK)) continue;
1363         state->nums[i] = best_black_col(state, rs, scratch, i, rownums, colnums);
1364     }
1365     debug_state("State after adding numbers", state);
1366
1367     /* DIFF_ANY just returns whatever we first generated, for testing purposes. */
1368     if (params->diff != DIFF_ANY &&
1369         !new_game_is_good(params, state, tosolve)) {
1370         ntries++;
1371         if (ntries > MAXTRIES) {
1372             debug(("Ran out of randomisation attempts, re-generating."));
1373             goto generate;
1374         }
1375         debug(("Re-randomising numbers under black squares."));
1376         goto randomise;
1377     }
1378
1379     ret = generate_desc(state, 0);
1380
1381     free_game(tosolve);
1382     free_game(state);
1383     solver_state_free(ss);
1384     sfree(scratch);
1385     sfree(rownums);
1386     sfree(colnums);
1387
1388     return ret;
1389 }
1390
1391 static char *validate_desc(game_params *params, char *desc)
1392 {
1393     char *ret = NULL;
1394
1395     unpick_desc(params, desc, NULL, &ret);
1396     return ret;
1397 }
1398
1399 static game_state *new_game(midend *me, game_params *params, char *desc)
1400 {
1401     game_state *state = NULL;
1402
1403     unpick_desc(params, desc, &state, NULL);
1404     if (!state) assert(!"new_game failed to unpick");
1405     return state;
1406 }
1407
1408 /* --- Game UI and move routines --- */
1409
1410 struct game_ui {
1411     int cx, cy, cshow;
1412     int show_black_nums;
1413 };
1414
1415 static game_ui *new_ui(game_state *state)
1416 {
1417     game_ui *ui = snew(game_ui);
1418
1419     ui->cx = ui->cy = ui->cshow = 0;
1420     ui->show_black_nums = 0;
1421
1422     return ui;
1423 }
1424
1425 static void free_ui(game_ui *ui)
1426 {
1427     sfree(ui);
1428 }
1429
1430 static char *encode_ui(game_ui *ui)
1431 {
1432     return NULL;
1433 }
1434
1435 static void decode_ui(game_ui *ui, char *encoding)
1436 {
1437 }
1438
1439 static void game_changed_state(game_ui *ui, game_state *oldstate,
1440                                game_state *newstate)
1441 {
1442     if (!oldstate->completed && newstate->completed)
1443         ui->cshow = 0;
1444 }
1445
1446 #define DS_BLACK        0x1
1447 #define DS_CIRCLE       0x2
1448 #define DS_CURSOR       0x4
1449 #define DS_BLACK_NUM    0x8
1450 #define DS_ERROR        0x10
1451 #define DS_FLASH        0x20
1452 #define DS_IMPOSSIBLE   0x40
1453
1454 struct game_drawstate {
1455     int tilesize, started, solved;
1456     int w, h, n;
1457
1458     unsigned int *flags;
1459 };
1460
1461 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1462                             int mx, int my, int button)
1463 {
1464     char buf[80], c;
1465     int i, x = FROMCOORD(mx), y = FROMCOORD(my);
1466     enum { NONE, TOGGLE_BLACK, TOGGLE_CIRCLE, UI } action = NONE;
1467
1468     if (IS_CURSOR_MOVE(button)) {
1469         move_cursor(button, &ui->cx, &ui->cy, state->w, state->h, 1);
1470         ui->cshow = 1;
1471         action = UI;
1472     } else if (IS_CURSOR_SELECT(button)) {
1473         x = ui->cx; y = ui->cy;
1474         if (!ui->cshow) {
1475             action = UI;
1476             ui->cshow = 1;
1477         }
1478         if (button == CURSOR_SELECT) {
1479             action = TOGGLE_BLACK;
1480         } else if (button == CURSOR_SELECT2) {
1481             action = TOGGLE_CIRCLE;
1482         }
1483     } else if (IS_MOUSE_DOWN(button)) {
1484         if (ui->cshow) {
1485             ui->cshow = 0;
1486             action = UI;
1487         }
1488         if (!INGRID(state, x, y)) {
1489             ui->show_black_nums = 1 - ui->show_black_nums;
1490             action = UI; /* this wants to be a per-game option. */
1491         } else if (button == LEFT_BUTTON) {
1492             action = TOGGLE_BLACK;
1493         } else if (button == RIGHT_BUTTON) {
1494             action = TOGGLE_CIRCLE;
1495         }
1496     }
1497     if (action == UI) return "";
1498
1499     if (action == TOGGLE_BLACK || action == TOGGLE_CIRCLE) {
1500         i = y * state->w + x;
1501         if (state->flags[i] & (F_BLACK | F_CIRCLE))
1502             c = 'E';
1503         else
1504             c = (action == TOGGLE_BLACK) ? 'B' : 'C';
1505         sprintf(buf, "%c%d,%d", (int)c, x, y);
1506         return dupstr(buf);
1507     }
1508
1509     return NULL;
1510 }
1511
1512 static game_state *execute_move(game_state *state, char *move)
1513 {
1514     game_state *ret = dup_game(state);
1515     int x, y, i, n;
1516
1517     debug(("move: %s", move));
1518
1519     while (*move) {
1520         char c = *move;
1521         if (c == 'B' || c == 'C' || c == 'E') {
1522             move++;
1523             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1524                 !INGRID(state, x, y))
1525                 goto badmove;
1526
1527             i = y*ret->w + x;
1528             ret->flags[i] &= ~(F_CIRCLE | F_BLACK); /* empty first, always. */
1529             if (c == 'B')
1530                 ret->flags[i] |= F_BLACK;
1531             else if (c == 'C')
1532                 ret->flags[i] |= F_CIRCLE;
1533             move += n;
1534         } else if (c == 'S') {
1535             move++;
1536             ret->used_solve = 1;
1537         } else
1538             goto badmove;
1539
1540         if (*move == ';')
1541             move++;
1542         else if (*move)
1543             goto badmove;
1544     }
1545     if (check_complete(ret, 1)) ret->completed = 1;
1546     return ret;
1547
1548 badmove:
1549     free_game(ret);
1550     return NULL;
1551 }
1552
1553 /* ----------------------------------------------------------------------
1554  * Drawing routines.
1555  */
1556
1557 static void game_compute_size(game_params *params, int tilesize,
1558                               int *x, int *y)
1559 {
1560     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1561     struct { int tilesize; } ads, *ds = &ads;
1562     ads.tilesize = tilesize;
1563
1564     *x = TILE_SIZE * params->w + 2 * BORDER;
1565     *y = TILE_SIZE * params->h + 2 * BORDER;
1566 }
1567
1568 static void game_set_size(drawing *dr, game_drawstate *ds,
1569                           game_params *params, int tilesize)
1570 {
1571     ds->tilesize = tilesize;
1572 }
1573
1574 static float *game_colours(frontend *fe, int *ncolours)
1575 {
1576     float *ret = snewn(3 * NCOLOURS, float);
1577     int i;
1578
1579     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1580     for (i = 0; i < 3; i++) {
1581         ret[COL_BLACK * 3 + i] = 0.0F;
1582         ret[COL_BLACKNUM * 3 + i] = 0.4F;
1583         ret[COL_WHITE * 3 + i] = 1.0F;
1584         ret[COL_GRID * 3 + i] = ret[COL_LOWLIGHT * 3 + i];
1585     }
1586     ret[COL_CURSOR * 3 + 0] = 0.2F;
1587     ret[COL_CURSOR * 3 + 1] = 0.8F;
1588     ret[COL_CURSOR * 3 + 2] = 0.0F;
1589
1590     ret[COL_ERROR * 3 + 0] = 1.0F;
1591     ret[COL_ERROR * 3 + 1] = 0.0F;
1592     ret[COL_ERROR * 3 + 2] = 0.0F;
1593
1594     *ncolours = NCOLOURS;
1595     return ret;
1596 }
1597
1598 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1599 {
1600     struct game_drawstate *ds = snew(struct game_drawstate);
1601
1602     ds->tilesize = ds->started = ds->solved = 0;
1603     ds->w = state->w;
1604     ds->h = state->h;
1605     ds->n = state->n;
1606
1607     ds->flags = snewn(state->n, unsigned int);
1608
1609     memset(ds->flags, 0, state->n*sizeof(unsigned int));
1610
1611     return ds;
1612 }
1613
1614 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1615 {
1616     sfree(ds->flags);
1617     sfree(ds);
1618 }
1619
1620 static void tile_redraw(drawing *dr, game_drawstate *ds, int x, int y,
1621                         int num, unsigned int f)
1622 {
1623     int tcol, bg, dnum, cx, cy, tsz;
1624     char buf[32];
1625
1626     if (f & DS_BLACK) {
1627         bg = (f & DS_ERROR) ? COL_ERROR : COL_BLACK;
1628         tcol = COL_BLACKNUM;
1629         dnum = (f & DS_BLACK_NUM) ? 1 : 0;
1630     } else {
1631         bg = (f & DS_FLASH) ? COL_LOWLIGHT : COL_BACKGROUND;
1632         tcol = (f & DS_ERROR) ? COL_ERROR : COL_BLACK;
1633         dnum = 1;
1634     }
1635
1636     cx = x + TILE_SIZE/2; cy = y + TILE_SIZE/2;
1637
1638     draw_rect(dr, x,    y, TILE_SIZE, TILE_SIZE, bg);
1639     draw_rect_outline(dr, x, y, TILE_SIZE, TILE_SIZE,
1640                       (f & DS_IMPOSSIBLE) ? COL_ERROR : COL_GRID);
1641
1642     if (f & DS_CIRCLE) {
1643         draw_circle(dr, cx, cy, CRAD, tcol, tcol);
1644         draw_circle(dr, cx, cy, CRAD-1, bg, tcol);
1645     }
1646
1647     if (dnum) {
1648         sprintf(buf, "%d", num);
1649         if (strlen(buf) == 1)
1650             tsz = TEXTSZ;
1651         else
1652             tsz = (CRAD*2 - 1) / strlen(buf);
1653         draw_text(dr, cx, cy, FONT_VARIABLE, tsz,
1654                   ALIGN_VCENTRE | ALIGN_HCENTRE, tcol, buf);
1655     }
1656
1657     if (f & DS_CURSOR)
1658         draw_rect_corners(dr, cx, cy, TEXTSZ/2, COL_CURSOR);
1659
1660     draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
1661 }
1662
1663 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1664                         game_state *state, int dir, game_ui *ui,
1665                         float animtime, float flashtime)
1666 {
1667     int x, y, i, flash;
1668     unsigned int f;
1669
1670     flash = (int)(flashtime * 5 / FLASH_TIME) % 2;
1671
1672     if (!ds->started) {
1673         int wsz = TILE_SIZE * state->w + 2 * BORDER;
1674         int hsz = TILE_SIZE * state->h + 2 * BORDER;
1675         draw_rect(dr, 0, 0, wsz, hsz, COL_BACKGROUND);
1676         draw_rect_outline(dr, COORD(0)-1, COORD(0)-1,
1677                           TILE_SIZE * state->w + 2, TILE_SIZE * state->h + 2,
1678                           COL_GRID);
1679         draw_update(dr, 0, 0, wsz, hsz);
1680     }
1681     for (x = 0; x < state->w; x++) {
1682         for (y = 0; y < state->h; y++) {
1683             i = y*state->w + x;
1684             f = 0;
1685
1686             if (flash) f |= DS_FLASH;
1687             if (state->impossible) f |= DS_IMPOSSIBLE;
1688
1689             if (ui->cshow && x == ui->cx && y == ui->cy)
1690                 f |= DS_CURSOR;
1691             if (state->flags[i] & F_BLACK) {
1692                 f |= DS_BLACK;
1693                 if (ui->show_black_nums) f |= DS_BLACK_NUM;
1694             }
1695             if (state->flags[i] & F_CIRCLE)
1696                 f |= DS_CIRCLE;
1697             if (state->flags[i] & F_ERROR)
1698                 f |= DS_ERROR;
1699
1700             if (!ds->started || ds->flags[i] != f) {
1701                 tile_redraw(dr, ds, COORD(x), COORD(y),
1702                             state->nums[i], f);
1703                 ds->flags[i] = f;
1704             }
1705         }
1706     }
1707     ds->started = 1;
1708 }
1709
1710 static float game_anim_length(game_state *oldstate, game_state *newstate,
1711                               int dir, game_ui *ui)
1712 {
1713     return 0.0F;
1714 }
1715
1716 static float game_flash_length(game_state *oldstate, game_state *newstate,
1717                                int dir, game_ui *ui)
1718 {
1719     if (!oldstate->completed &&
1720         newstate->completed && !newstate->used_solve)
1721         return FLASH_TIME;
1722     return 0.0F;
1723 }
1724
1725 static int game_timing_state(game_state *state, game_ui *ui)
1726 {
1727     return TRUE;
1728 }
1729
1730 static void game_print_size(game_params *params, float *x, float *y)
1731 {
1732     int pw, ph;
1733
1734     /* 8mm squares by default. */
1735     game_compute_size(params, 800, &pw, &ph);
1736     *x = pw / 100.0F;
1737     *y = ph / 100.0F;
1738 }
1739
1740 static void game_print(drawing *dr, game_state *state, int tilesize)
1741 {
1742     int ink = print_mono_colour(dr, 0);
1743     int paper = print_mono_colour(dr, 1);
1744     int x, y, ox, oy, i;
1745     char buf[32];
1746
1747     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1748     game_drawstate ads, *ds = &ads;
1749     game_set_size(dr, ds, NULL, tilesize);
1750
1751     print_line_width(dr, 2 * TILE_SIZE / 40);
1752
1753     for (x = 0; x < state->w; x++) {
1754         for (y = 0; y < state->h; y++) {
1755             ox = COORD(x); oy = COORD(y);
1756             i = y*state->w+x;
1757
1758             if (state->flags[i] & F_BLACK) {
1759                 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1760             } else {
1761                 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1762
1763                 if (state->flags[i] & DS_CIRCLE)
1764                     draw_circle(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, CRAD,
1765                                 paper, ink);
1766
1767                 sprintf(buf, "%d", state->nums[i]);
1768                 draw_text(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, FONT_VARIABLE,
1769                           TEXTSZ/strlen(buf), ALIGN_VCENTRE | ALIGN_HCENTRE,
1770                           ink, buf);
1771             }
1772         }
1773     }
1774 }
1775
1776 #ifdef COMBINED
1777 #define thegame singles
1778 #endif
1779
1780 const struct game thegame = {
1781     "Singles", "games.singles", "singles",
1782     default_params,
1783     game_fetch_preset,
1784     decode_params,
1785     encode_params,
1786     free_params,
1787     dup_params,
1788     TRUE, game_configure, custom_params,
1789     validate_params,
1790     new_game_desc,
1791     validate_desc,
1792     new_game,
1793     dup_game,
1794     free_game,
1795     TRUE, solve_game,
1796     TRUE, game_can_format_as_text_now, game_text_format,
1797     new_ui,
1798     free_ui,
1799     encode_ui,
1800     decode_ui,
1801     game_changed_state,
1802     interpret_move,
1803     execute_move,
1804     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1805     game_colours,
1806     game_new_drawstate,
1807     game_free_drawstate,
1808     game_redraw,
1809     game_anim_length,
1810     game_flash_length,
1811     TRUE, FALSE, game_print_size, game_print,
1812     FALSE,                             /* wants_statusbar */
1813     FALSE, game_timing_state,
1814     REQUIRE_RBUTTON,                   /* flags */
1815 };
1816
1817 #ifdef STANDALONE_SOLVER
1818
1819 #include <time.h>
1820 #include <stdarg.h>
1821
1822 static void start_soak(game_params *p, random_state *rs)
1823 {
1824     time_t tt_start, tt_now, tt_last;
1825     char *desc, *aux;
1826     game_state *s;
1827     int i, n = 0, ndiff[DIFF_MAX], diff, sret, nblack = 0, nsneaky = 0;
1828
1829     tt_start = tt_now = time(NULL);
1830
1831     printf("Soak-testing a %dx%d grid.\n", p->w, p->h);
1832     p->diff = DIFF_ANY;
1833
1834     memset(ndiff, 0, DIFF_MAX * sizeof(int));
1835
1836     while (1) {
1837         n++;
1838         desc = new_game_desc(p, rs, &aux, 0);
1839         s = new_game(NULL, p, desc);
1840         nsneaky += solve_sneaky(s, NULL);
1841
1842         for (diff = 0; diff < DIFF_MAX; diff++) {
1843             memset(s->flags, 0, s->n * sizeof(unsigned int));
1844             s->completed = s->impossible = 0;
1845             sret = solve_specific(s, diff, 0);
1846             if (sret > 0) {
1847                 ndiff[diff]++;
1848                 break;
1849             } else if (sret < 0)
1850                 fprintf(stderr, "Impossible! %s\n", desc);
1851         }
1852         for (i = 0; i < s->n; i++) {
1853             if (s->flags[i] & F_BLACK) nblack++;
1854         }
1855         free_game(s);
1856         sfree(desc);
1857
1858         tt_last = time(NULL);
1859         if (tt_last > tt_now) {
1860             tt_now = tt_last;
1861             printf("%d total, %3.1f/s, bl/sn %3.1f%%/%3.1f%%: ",
1862                    n, (double)n / ((double)tt_now - tt_start),
1863                    ((double)nblack * 100.0) / (double)(n * p->w * p->h),
1864                    ((double)nsneaky * 100.0) / (double)(n * p->w * p->h));
1865             for (diff = 0; diff < DIFF_MAX; diff++) {
1866                 if (diff > 0) printf(", ");
1867                 printf("%d (%3.1f%%) %s",
1868                        ndiff[diff], (double)ndiff[diff] * 100.0 / (double)n,
1869                        singles_diffnames[diff]);
1870             }
1871             printf("\n");
1872         }
1873     }
1874 }
1875
1876 int main(int argc, char **argv)
1877 {
1878     char *id = NULL, *desc, *desc_gen = NULL, *tgame, *err, *aux;
1879     game_state *s = NULL;
1880     game_params *p = NULL;
1881     int soln, soak = 0, ret = 1;
1882     time_t seed = time(NULL);
1883     random_state *rs = NULL;
1884
1885     setvbuf(stdout, NULL, _IONBF, 0);
1886
1887     while (--argc > 0) {
1888         char *p = *++argv;
1889         if (!strcmp(p, "-v")) {
1890             verbose = 1;
1891         } else if (!strcmp(p, "--soak")) {
1892             soak = 1;
1893         } else if (!strcmp(p, "--seed")) {
1894             if (argc == 0) {
1895                 fprintf(stderr, "%s: --seed needs an argument", argv[0]);
1896                 goto done;
1897             }
1898             seed = (time_t)atoi(*++argv);
1899             argc--;
1900         } else if (*p == '-') {
1901             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
1902             return 1;
1903         } else {
1904             id = p;
1905         }
1906     }
1907
1908     rs = random_new((void*)&seed, sizeof(time_t));
1909
1910     if (!id) {
1911         fprintf(stderr, "usage: %s [-v] [--soak] <params> | <game_id>\n", argv[0]);
1912         goto done;
1913     }
1914     desc = strchr(id, ':');
1915     if (desc) *desc++ = '\0';
1916
1917     p = default_params();
1918     decode_params(p, id);
1919     err = validate_params(p, 1);
1920     if (err) {
1921         fprintf(stderr, "%s: %s", argv[0], err);
1922         goto done;
1923     }
1924
1925     if (soak) {
1926         if (desc) {
1927             fprintf(stderr, "%s: --soak only needs params, not game desc.\n", argv[0]);
1928             goto done;
1929         }
1930         start_soak(p, rs);
1931     } else {
1932         if (!desc) desc = desc_gen = new_game_desc(p, rs, &aux, 0);
1933
1934         err = validate_desc(p, desc);
1935         if (err) {
1936             fprintf(stderr, "%s: %s\n", argv[0], err);
1937             free_params(p);
1938             goto done;
1939         }
1940         s = new_game(NULL, p, desc);
1941
1942         if (verbose) {
1943             tgame = game_text_format(s);
1944             printf(tgame);
1945             sfree(tgame);
1946         }
1947
1948         soln = solve_specific(s, DIFF_ANY, 0);
1949         tgame = game_text_format(s);
1950         printf(tgame);
1951         sfree(tgame);
1952         printf("Game was %s.\n\n",
1953                soln < 0 ? "impossible" : soln > 0 ? "solved" : "not solved");
1954     }
1955     ret = 0;
1956
1957 done:
1958     if (desc_gen) sfree(desc_gen);
1959     if (p) free_params(p);
1960     if (s) free_game(s);
1961     if (rs) random_free(rs);
1962
1963     return ret;
1964 }
1965
1966 #endif
1967
1968
1969 /* vim: set shiftwidth=4 tabstop=8: */