unequal.c

   1 /*
   2  * unequal.c
   3  *
   4  * Implementation of 'Futoshiki', a puzzle featured in the Guardian.
   5  *
   6  * TTD:
   7    * add multiple-links-on-same-col/row solver nous
   8    * Optimise set solver to use bit operations instead
   9  *
  10  * Guardian puzzles of note:
  11    * #1: 5:0,0L,0L,0,0,0R,0,0L,0D,0L,0R,0,2,0D,0,0,0,0,0,0,0U,0,0,0,0U,
  12    * #2: 5:0,0,0,4L,0L,0,2LU,0L,0U,0,0,0U,0,0,0,0,0D,0,3LRUD,0,0R,3,0L,0,0,
  13    * #3: (reprint of #2)
  14    * #4:
  15    * #5: 5:0,0,0,0,0,0,2,0U,3U,0U,0,0,3,0,0,0,3,0D,4,0,0,0L,0R,0,0,
  16    * #6: 5:0D,0L,0,0R,0,0,0D,0,3,0D,0,0R,0,0R,0D,0U,0L,0,1,2,0,0,0U,0,0L,
  17  */
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include <assert.h>
  23 #include <ctype.h>
  24 #include <math.h>
  25
  26 #include "puzzles.h"
  27 #include "latin.h" /* contains typedef for digit */
  28
  29 /* ----------------------------------------------------------
  30  * Constant and structure definitions
  31  */
  32
  33 #define FLASH_TIME 0.4F
  34
  35 #define PREFERRED_TILE_SIZE 32
  36
  37 #define TILE_SIZE (ds->tilesize)
  38 #define GAP_SIZE  (TILE_SIZE/2)
  39 #define SQUARE_SIZE (TILE_SIZE + GAP_SIZE)
  40
  41 #define BORDER    (TILE_SIZE / 2)
  42
  43 #define COORD(x)  ( (x) * SQUARE_SIZE + BORDER )
  44 #define FROMCOORD(x)  ( ((x) - BORDER + SQUARE_SIZE) / SQUARE_SIZE - 1 )
  45
  46 #define GRID(p,w,x,y) ((p)->w[((y)*(p)->order)+(x)])
  47 #define GRID3(p,w,x,y,z) ((p)->w[ (((x)*(p)->order+(y))*(p)->order+(z)) ])
  48 #define HINT(p,x,y,n) GRID3(p, hints, x, y, n)
  49
  50 enum {
  51     COL_BACKGROUND,
  52     COL_GRID,
  53     COL_TEXT, COL_GUESS, COL_ERROR, COL_PENCIL,
  54     COL_HIGHLIGHT, COL_LOWLIGHT, COL_SPENT = COL_LOWLIGHT,
  55     NCOLOURS
  56 };
  57
  58 struct game_params {
  59     int order;          /* Size of latin square */
  60     int diff;           /* Difficulty */
  61     int adjacent;       /* Puzzle indicators are 'adjacent number'
  62                             not 'greater-than'. */
  63 };
  64
  65 #define F_IMMUTABLE     1       /* passed in as game description */
  66 #define F_ADJ_UP        2
  67 #define F_ADJ_RIGHT     4
  68 #define F_ADJ_DOWN      8
  69 #define F_ADJ_LEFT      16
  70 #define F_ERROR         32
  71 #define F_ERROR_UP      64
  72 #define F_ERROR_RIGHT   128
  73 #define F_ERROR_DOWN    256
  74 #define F_ERROR_LEFT    512
  75 #define F_SPENT_UP      1024
  76 #define F_SPENT_RIGHT   2048
  77 #define F_SPENT_DOWN    4096
  78 #define F_SPENT_LEFT    8192
  79
  80 #define ADJ_TO_SPENT(x) ((x) << 9)
  81
  82 #define F_ERROR_MASK (F_ERROR|F_ERROR_UP|F_ERROR_RIGHT|F_ERROR_DOWN|F_ERROR_LEFT)
  83
  84 struct game_state {
  85     int order, completed, cheated, adjacent;
  86     digit *nums;                 /* actual numbers (size order^2) */
  87     unsigned char *hints;        /* remaining possiblities (size order^3) */
  88     unsigned int *flags;         /* flags (size order^2) */
  89 };
  90
  91 /* ----------------------------------------------------------
  92  * Game parameters and presets
  93  */
  94
  95 /* Steal the method from map.c for difficulty levels. */
  96 #define DIFFLIST(A)               \
  97     A(LATIN,Trivial,NULL,t)       \
  98     A(EASY,Easy,solver_easy, e)   \
  99     A(SET,Tricky,solver_set, k)   \
 100     A(EXTREME,Extreme,NULL,x)     \
 101     A(RECURSIVE,Recursive,NULL,r)
 102
 103 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
 104 #define TITLE(upper,title,func,lower) #title,
 105 #define ENCODE(upper,title,func,lower) #lower
 106 #define CONFIG(upper,title,func,lower) ":" #title
 107 enum { DIFFLIST(ENUM) DIFFCOUNT, DIFF_IMPOSSIBLE = diff_impossible, DIFF_AMBIGUOUS = diff_ambiguous, DIFF_UNFINISHED = diff_unfinished };
 108 static char const *const unequal_diffnames[] = { DIFFLIST(TITLE) };
 109 static char const unequal_diffchars[] = DIFFLIST(ENCODE);
 110 #define DIFFCONFIG DIFFLIST(CONFIG)
 111
 112 #define DEFAULT_PRESET 0
 113
 114 const static struct game_params unequal_presets[] = {
 115     {  4, DIFF_EASY,    0 },
 116     {  5, DIFF_EASY,    0 },
 117     {  5, DIFF_SET,     0 },
 118     {  5, DIFF_SET,     1 },
 119     {  5, DIFF_EXTREME, 0 },
 120     {  6, DIFF_EASY,    0 },
 121     {  6, DIFF_SET,     0 },
 122     {  6, DIFF_SET,     1 },
 123     {  6, DIFF_EXTREME, 0 },
 124     {  7, DIFF_SET,     0 },
 125     {  7, DIFF_SET,     1 },
 126     {  7, DIFF_EXTREME, 0 }
 127 };
 128
 129 static int game_fetch_preset(int i, char **name, game_params **params)
 130 {
 131     game_params *ret;
 132     char buf[80];
 133
 134     if (i < 0 || i >= lenof(unequal_presets))
 135         return FALSE;
 136
 137     ret = snew(game_params);
 138     *ret = unequal_presets[i]; /* structure copy */
 139
 140     sprintf(buf, "%s: %dx%d %s",
 141             ret->adjacent ? "Adjacent" : "Unequal",
 142             ret->order, ret->order,
 143             unequal_diffnames[ret->diff]);
 144
 145     *name = dupstr(buf);
 146     *params = ret;
 147     return TRUE;
 148 }
 149
 150 static game_params *default_params(void)
 151 {
 152     game_params *ret;
 153     char *name;
 154
 155     if (!game_fetch_preset(DEFAULT_PRESET, &name, &ret)) return NULL;
 156     sfree(name);
 157     return ret;
 158 }
 159
 160 static void free_params(game_params *params)
 161 {
 162     sfree(params);
 163 }
 164
 165 static game_params *dup_params(const game_params *params)
 166 {
 167     game_params *ret = snew(game_params);
 168     *ret = *params;       /* structure copy */
 169     return ret;
 170 }
 171
 172 static void decode_params(game_params *ret, char const *string)
 173 {
 174     char const *p = string;
 175
 176     ret->order = atoi(p);
 177     while (*p && isdigit((unsigned char)*p)) p++;
 178
 179     if (*p == 'a') {
 180         p++;
 181         ret->adjacent = 1;
 182     } else
 183         ret->adjacent = 0;
 184
 185     if (*p == 'd') {
 186         int i;
 187         p++;
 188         ret->diff = DIFFCOUNT+1; /* ...which is invalid */
 189         if (*p) {
 190             for (i = 0; i < DIFFCOUNT; i++) {
 191                 if (*p == unequal_diffchars[i])
 192                     ret->diff = i;
 193             }
 194             p++;
 195         }
 196     }
 197 }
 198
 199 static char *encode_params(const game_params *params, int full)
 200 {
 201     char ret[80];
 202
 203     sprintf(ret, "%d", params->order);
 204     if (params->adjacent)
 205         sprintf(ret + strlen(ret), "a");
 206     if (full)
 207         sprintf(ret + strlen(ret), "d%c", unequal_diffchars[params->diff]);
 208
 209     return dupstr(ret);
 210 }
 211
 212 static config_item *game_configure(const game_params *params)
 213 {
 214     config_item *ret;
 215     char buf[80];
 216
 217     ret = snewn(4, config_item);
 218
 219     ret[0].name = "Mode";
 220     ret[0].type = C_CHOICES;
 221     ret[0].u.choices.choicenames = ":Unequal:Adjacent";
 222     ret[0].u.choices.selected = params->adjacent;
 223
 224     ret[1].name = "Size (s*s)";
 225     ret[1].type = C_STRING;
 226     sprintf(buf, "%d", params->order);
 227     ret[1].u.string.sval = dupstr(buf);
 228
 229     ret[2].name = "Difficulty";
 230     ret[2].type = C_CHOICES;
 231     ret[2].u.choices.choicenames = DIFFCONFIG;
 232     ret[2].u.choices.selected = params->diff;
 233
 234     ret[3].name = NULL;
 235     ret[3].type = C_END;
 236
 237     return ret;
 238 }
 239
 240 static game_params *custom_params(const config_item *cfg)
 241 {
 242     game_params *ret = snew(game_params);
 243
 244     ret->adjacent = cfg[0].u.choices.selected;
 245     ret->order = atoi(cfg[1].u.string.sval);
 246     ret->diff = cfg[2].u.choices.selected;
 247
 248     return ret;
 249 }
 250
 251 static const char *validate_params(const game_params *params, int full)
 252 {
 253     if (params->order < 3 || params->order > 32)
 254         return "Order must be between 3 and 32";
 255     if (params->diff >= DIFFCOUNT)
 256         return "Unknown difficulty rating";
 257     if (params->order < 5 && params->adjacent &&
 258         params->diff >= DIFF_SET)
 259         return "Order must be at least 5 for Adjacent puzzles of this difficulty.";
 260     return NULL;
 261 }
 262
 263 /* ----------------------------------------------------------
 264  * Various utility functions
 265  */
 266
 267 static const struct { unsigned int f, fo, fe; int dx, dy; char c, ac; } adjthan[] = {
 268     { F_ADJ_UP,    F_ADJ_DOWN,  F_ERROR_UP,     0, -1, '^', '-' },
 269     { F_ADJ_RIGHT, F_ADJ_LEFT,  F_ERROR_RIGHT,  1,  0, '>', '|' },
 270     { F_ADJ_DOWN,  F_ADJ_UP,    F_ERROR_DOWN,   0,  1, 'v', '-' },
 271     { F_ADJ_LEFT,  F_ADJ_RIGHT, F_ERROR_LEFT,  -1,  0, '<', '|' }
 272 };
 273
 274 static game_state *blank_game(int order, int adjacent)
 275 {
 276     game_state *state = snew(game_state);
 277     int o2 = order*order, o3 = o2*order;
 278
 279     state->order = order;
 280     state->adjacent = adjacent;
 281     state->completed = state->cheated = 0;
 282
 283     state->nums = snewn(o2, digit);
 284     state->hints = snewn(o3, unsigned char);
 285     state->flags = snewn(o2, unsigned int);
 286
 287     memset(state->nums, 0, o2 * sizeof(digit));
 288     memset(state->hints, 0, o3);
 289     memset(state->flags, 0, o2 * sizeof(unsigned int));
 290
 291     return state;
 292 }
 293
 294 static game_state *dup_game(const game_state *state)
 295 {
 296     game_state *ret = blank_game(state->order, state->adjacent);
 297     int o2 = state->order*state->order, o3 = o2*state->order;
 298
 299     memcpy(ret->nums, state->nums, o2 * sizeof(digit));
 300     memcpy(ret->hints, state->hints, o3);
 301     memcpy(ret->flags, state->flags, o2 * sizeof(unsigned int));
 302
 303     return ret;
 304 }
 305
 306 static void free_game(game_state *state)
 307 {
 308     sfree(state->nums);
 309     sfree(state->hints);
 310     sfree(state->flags);
 311     sfree(state);
 312 }
 313
 314 #define CHECKG(x,y) grid[(y)*o+(x)]
 315
 316 /* Returns 0 if it finds an error, 1 otherwise. */
 317 static int check_num_adj(digit *grid, game_state *state,
 318                         int x, int y, int me)
 319 {
 320     unsigned int f = GRID(state, flags, x, y);
 321     int ret = 1, i, o = state->order;
 322
 323     for (i = 0; i < 4; i++) {
 324         int dx = adjthan[i].dx, dy = adjthan[i].dy, n, dn;
 325
 326         if (x+dx < 0 || x+dx >= o || y+dy < 0 || y+dy >= o)
 327             continue;
 328
 329         n = CHECKG(x, y);
 330         dn = CHECKG(x+dx, y+dy);
 331
 332         assert (n != 0);
 333         if (dn == 0) continue;
 334
 335         if (state->adjacent) {
 336             int gd = abs(n-dn);
 337
 338             if ((f & adjthan[i].f) && (gd != 1)) {
 339                 debug(("check_adj error (%d,%d):%d should be | (%d,%d):%d",
 340                        x, y, n, x+dx, y+dy, dn));
 341                 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
 342                 ret = 0;
 343             }
 344             if (!(f & adjthan[i].f) && (gd == 1)) {
 345                 debug(("check_adj error (%d,%d):%d should not be | (%d,%d):%d",
 346                        x, y, n, x+dx, y+dy, dn));
 347                 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
 348                 ret = 0;
 349             }
 350
 351         } else {
 352             if ((f & adjthan[i].f) && (n <= dn)) {
 353                 debug(("check_adj error (%d,%d):%d not > (%d,%d):%d",
 354                        x, y, n, x+dx, y+dy, dn));
 355                 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
 356                 ret = 0;
 357             }
 358         }
 359     }
 360     return ret;
 361 }
 362
 363 /* Returns 0 if it finds an error, 1 otherwise. */
 364 static int check_num_error(digit *grid, game_state *state,
 365                            int x, int y, int mark_errors)
 366 {
 367     int o = state->order;
 368     int xx, yy, val = CHECKG(x,y), ret = 1;
 369
 370     assert(val != 0);
 371
 372     /* check for dups in same column. */
 373     for (yy = 0; yy < state->order; yy++) {
 374         if (yy == y) continue;
 375         if (CHECKG(x,yy) == val) ret = 0;
 376     }
 377
 378     /* check for dups in same row. */
 379     for (xx = 0; xx < state->order; xx++) {
 380         if (xx == x) continue;
 381         if (CHECKG(xx,y) == val) ret = 0;
 382     }
 383
 384     if (!ret) {
 385         debug(("check_num_error (%d,%d) duplicate %d", x, y, val));
 386         if (mark_errors) GRID(state, flags, x, y) |= F_ERROR;
 387     }
 388     return ret;
 389 }
 390
 391 /* Returns:     -1 for 'wrong'
 392  *               0 for 'incomplete'
 393  *               1 for 'complete and correct'
 394  */
 395 static int check_complete(digit *grid, game_state *state, int mark_errors)
 396 {
 397     int x, y, ret = 1, o = state->order;
 398
 399     if (mark_errors)
 400         assert(grid == state->nums);
 401
 402     for (x = 0; x < state->order; x++) {
 403         for (y = 0; y < state->order; y++) {
 404             if (mark_errors)
 405                 GRID(state, flags, x, y) &= ~F_ERROR_MASK;
 406             if (grid[y*o+x] == 0) {
 407                 ret = 0;
 408             } else {
 409                 if (!check_num_error(grid, state, x, y, mark_errors)) ret = -1;
 410                 if (!check_num_adj(grid, state, x, y, mark_errors)) ret = -1;
 411             }
 412         }
 413     }
 414     if (ret == 1 && latin_check(grid, o))
 415         ret = -1;
 416     return ret;
 417 }
 418
 419 static char n2c(digit n, int order) {
 420     if (n == 0)         return ' ';
 421     if (order < 10) {
 422         if (n < 10)     return '0' + n;
 423     } else {
 424         if (n < 11)     return '0' + n-1;
 425         n -= 11;
 426         if (n <= 26)    return 'A' + n;
 427     }
 428     return '?';
 429 }
 430
 431 /* should be 'digit', but includes -1 for 'not a digit'.
 432  * Includes keypresses (0 especially) for interpret_move. */
 433 static int c2n(int c, int order) {
 434     if (c < 0 || c > 0xff)
 435         return -1;
 436     if (c == ' ' || c == '\b')
 437         return 0;
 438     if (order < 10) {
 439         if (c >= '0' && c <= '9')
 440             return (int)(c - '0');
 441     } else {
 442         if (c >= '0' && c <= '9')
 443             return (int)(c - '0' + 1);
 444         if (c >= 'A' && c <= 'Z')
 445             return (int)(c - 'A' + 11);
 446         if (c >= 'a' && c <= 'z')
 447             return (int)(c - 'a' + 11);
 448     }
 449     return -1;
 450 }
 451
 452 static int game_can_format_as_text_now(const game_params *params)
 453 {
 454     return TRUE;
 455 }
 456
 457 static char *game_text_format(const game_state *state)
 458 {
 459     int x, y, len, n;
 460     char *ret, *p;
 461
 462     len = (state->order*2) * (state->order*2-1) + 1;
 463     ret = snewn(len, char);
 464     p = ret;
 465
 466     for (y = 0; y < state->order; y++) {
 467         for (x = 0; x < state->order; x++) {
 468             n = GRID(state, nums, x, y);
 469             *p++ = n > 0 ? n2c(n, state->order) : '.';
 470
 471             if (x < (state->order-1)) {
 472                 if (state->adjacent) {
 473                     *p++ = (GRID(state, flags, x, y) & F_ADJ_RIGHT) ? '|' : ' ';
 474                 } else {
 475                     if (GRID(state, flags, x, y) & F_ADJ_RIGHT)
 476                         *p++ = '>';
 477                     else if (GRID(state, flags, x+1, y) & F_ADJ_LEFT)
 478                         *p++ = '<';
 479                     else
 480                         *p++ = ' ';
 481                 }
 482             }
 483         }
 484         *p++ = '\n';
 485
 486         if (y < (state->order-1)) {
 487             for (x = 0; x < state->order; x++) {
 488                 if (state->adjacent) {
 489                     *p++ = (GRID(state, flags, x, y) & F_ADJ_DOWN) ? '-' : ' ';
 490                 } else {
 491                     if (GRID(state, flags, x, y) & F_ADJ_DOWN)
 492                         *p++ = 'v';
 493                     else if (GRID(state, flags, x, y+1) & F_ADJ_UP)
 494                         *p++ = '^';
 495                     else
 496                         *p++ = ' ';
 497                 }
 498
 499                 if (x < state->order-1)
 500                   *p++ = ' ';
 501             }
 502             *p++ = '\n';
 503         }
 504     }
 505     *p++ = '\0';
 506
 507     assert(p - ret == len);
 508     return ret;
 509 }
 510
 511 #ifdef STANDALONE_SOLVER
 512 static void game_debug(game_state *state)
 513 {
 514     char *dbg = game_text_format(state);
 515     printf("%s", dbg);
 516     sfree(dbg);
 517 }
 518 #endif
 519
 520 /* ----------------------------------------------------------
 521  * Solver.
 522  */
 523
 524 struct solver_link {
 525     int len, gx, gy, lx, ly;
 526 };
 527
 528 struct solver_ctx {
 529     game_state *state;
 530
 531     int nlinks, alinks;
 532     struct solver_link *links;
 533 };
 534
 535 static void solver_add_link(struct solver_ctx *ctx,
 536                             int gx, int gy, int lx, int ly, int len)
 537 {
 538     if (ctx->alinks < ctx->nlinks+1) {
 539         ctx->alinks = ctx->alinks*2 + 1;
 540         /*debug(("resizing ctx->links, new size %d", ctx->alinks));*/
 541         ctx->links = sresize(ctx->links, ctx->alinks, struct solver_link);
 542     }
 543     ctx->links[ctx->nlinks].gx = gx;
 544     ctx->links[ctx->nlinks].gy = gy;
 545     ctx->links[ctx->nlinks].lx = lx;
 546     ctx->links[ctx->nlinks].ly = ly;
 547     ctx->links[ctx->nlinks].len = len;
 548     ctx->nlinks++;
 549     /*debug(("Adding new link: len %d (%d,%d) < (%d,%d), nlinks now %d",
 550            len, lx, ly, gx, gy, ctx->nlinks));*/
 551 }
 552
 553 static struct solver_ctx *new_ctx(game_state *state)
 554 {
 555     struct solver_ctx *ctx = snew(struct solver_ctx);
 556     int o = state->order;
 557     int i, x, y;
 558     unsigned int f;
 559
 560     ctx->nlinks = ctx->alinks = 0;
 561     ctx->links = NULL;
 562     ctx->state = state;
 563
 564     if (state->adjacent) return ctx; /* adjacent mode doesn't use links. */
 565
 566     for (x = 0; x < o; x++) {
 567         for (y = 0; y < o; y++) {
 568             f = GRID(state, flags, x, y);
 569             for (i = 0; i < 4; i++) {
 570                 if (f & adjthan[i].f)
 571                     solver_add_link(ctx, x, y, x+adjthan[i].dx, y+adjthan[i].dy, 1);
 572             }
 573         }
 574     }
 575
 576     return ctx;
 577 }
 578
 579 static void *clone_ctx(void *vctx)
 580 {
 581     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 582     return new_ctx(ctx->state);
 583 }
 584
 585 static void free_ctx(void *vctx)
 586 {
 587     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 588     if (ctx->links) sfree(ctx->links);
 589     sfree(ctx);
 590 }
 591
 592 static void solver_nminmax(struct latin_solver *solver,
 593                            int x, int y, int *min_r, int *max_r,
 594                            unsigned char **ns_r)
 595 {
 596     int o = solver->o, min = o, max = 0, n;
 597     unsigned char *ns;
 598
 599     assert(x >= 0 && y >= 0 && x < o && y < o);
 600
 601     ns = solver->cube + cubepos(x,y,1);
 602
 603     if (grid(x,y) > 0) {
 604         min = max = grid(x,y)-1;
 605     } else {
 606         for (n = 0; n < o; n++) {
 607             if (ns[n]) {
 608                 if (n > max) max = n;
 609                 if (n < min) min = n;
 610             }
 611         }
 612     }
 613     if (min_r) *min_r = min;
 614     if (max_r) *max_r = max;
 615     if (ns_r) *ns_r = ns;
 616 }
 617
 618 static int solver_links(struct latin_solver *solver, void *vctx)
 619 {
 620     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 621     int i, j, lmin, gmax, nchanged = 0;
 622     unsigned char *gns, *lns;
 623     struct solver_link *link;
 624
 625     for (i = 0; i < ctx->nlinks; i++) {
 626         link = &ctx->links[i];
 627         solver_nminmax(solver, link->gx, link->gy, NULL, &gmax, &gns);
 628         solver_nminmax(solver, link->lx, link->ly, &lmin, NULL, &lns);
 629
 630         for (j = 0; j < solver->o; j++) {
 631             /* For the 'greater' end of the link, discount all numbers
 632              * too small to satisfy the inequality. */
 633             if (gns[j]) {
 634                 if (j < (lmin+link->len)) {
 635 #ifdef STANDALONE_SOLVER
 636                     if (solver_show_working) {
 637                         printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
 638                                solver_recurse_depth*4, "",
 639                                link->gx+1, link->gy+1, link->lx+1, link->ly+1);
 640                         printf("%*s  ruling out %d at (%d,%d)\n",
 641                                solver_recurse_depth*4, "",
 642                                j+1, link->gx+1, link->gy+1);
 643                     }
 644 #endif
 645                     cube(link->gx, link->gy, j+1) = FALSE;
 646                     nchanged++;
 647                 }
 648             }
 649             /* For the 'lesser' end of the link, discount all numbers
 650              * too large to satisfy inequality. */
 651             if (lns[j]) {
 652                 if (j > (gmax-link->len)) {
 653 #ifdef STANDALONE_SOLVER
 654                     if (solver_show_working) {
 655                         printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
 656                                solver_recurse_depth*4, "",
 657                                link->gx+1, link->gy+1, link->lx+1, link->ly+1);
 658                         printf("%*s  ruling out %d at (%d,%d)\n",
 659                                solver_recurse_depth*4, "",
 660                                j+1, link->lx+1, link->ly+1);
 661                     }
 662 #endif
 663                     cube(link->lx, link->ly, j+1) = FALSE;
 664                     nchanged++;
 665                 }
 666             }
 667         }
 668     }
 669     return nchanged;
 670 }
 671
 672 static int solver_adjacent(struct latin_solver *solver, void *vctx)
 673 {
 674     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 675     int nchanged = 0, x, y, i, n, o = solver->o, nx, ny, gd;
 676
 677     /* Update possible values based on known values and adjacency clues. */
 678
 679     for (x = 0; x < o; x++) {
 680         for (y = 0; y < o; y++) {
 681             if (grid(x, y) == 0) continue;
 682
 683             /* We have a definite number here. Make sure that any
 684              * adjacent possibles reflect the adjacent/non-adjacent clue. */
 685
 686             for (i = 0; i < 4; i++) {
 687                 int isadjacent = (GRID(ctx->state, flags, x, y) & adjthan[i].f);
 688
 689                 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
 690                 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
 691                     continue;
 692
 693                 for (n = 0; n < o; n++) {
 694                     /* Continue past numbers the adjacent square _could_ be,
 695                      * given the clue we have. */
 696                     gd = abs((n+1) - grid(x, y));
 697                     if (isadjacent && (gd == 1)) continue;
 698                     if (!isadjacent && (gd != 1)) continue;
 699
 700                     if (cube(nx, ny, n+1) == FALSE)
 701                         continue; /* already discounted this possibility. */
 702
 703 #ifdef STANDALONE_SOLVER
 704                     if (solver_show_working) {
 705                         printf("%*sadjacent elimination, (%d,%d):%d %s (%d,%d):\n",
 706                                solver_recurse_depth*4, "",
 707                                x+1, y+1, grid(x, y), isadjacent ? "|" : "!|", nx+1, ny+1);
 708                         printf("%*s  ruling out %d at (%d,%d)\n",
 709                                solver_recurse_depth*4, "", n+1, nx+1, ny+1);
 710                     }
 711 #endif
 712                     cube(nx, ny, n+1) = FALSE;
 713                     nchanged++;
 714                 }
 715             }
 716         }
 717     }
 718
 719     return nchanged;
 720 }
 721
 722 static int solver_adjacent_set(struct latin_solver *solver, void *vctx)
 723 {
 724     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 725     int x, y, i, n, nn, o = solver->o, nx, ny, gd;
 726     int nchanged = 0, *scratch = snewn(o, int);
 727
 728     /* Update possible values based on other possible values
 729      * of adjacent squares, and adjacency clues. */
 730
 731     for (x = 0; x < o; x++) {
 732         for (y = 0; y < o; y++) {
 733             for (i = 0; i < 4; i++) {
 734                 int isadjacent = (GRID(ctx->state, flags, x, y) & adjthan[i].f);
 735
 736                 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
 737                 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
 738                     continue;
 739
 740                 /* We know the current possibles for the square (x,y)
 741                  * and also the adjacency clue from (x,y) to (nx,ny).
 742                  * Construct a maximum set of possibles for (nx,ny)
 743                  * in scratch, based on these constraints... */
 744
 745                 memset(scratch, 0, o*sizeof(int));
 746
 747                 for (n = 0; n < o; n++) {
 748                     if (cube(x, y, n+1) == FALSE) continue;
 749
 750                     for (nn = 0; nn < o; nn++) {
 751                         if (n == nn) continue;
 752
 753                         gd = abs(nn - n);
 754                         if (isadjacent && (gd != 1)) continue;
 755                         if (!isadjacent && (gd == 1)) continue;
 756
 757                         scratch[nn] = 1;
 758                     }
 759                 }
 760
 761                 /* ...and remove any possibilities for (nx,ny) that are
 762                  * currently set but are not indicated in scratch. */
 763                 for (n = 0; n < o; n++) {
 764                     if (scratch[n] == 1) continue;
 765                     if (cube(nx, ny, n+1) == FALSE) continue;
 766
 767 #ifdef STANDALONE_SOLVER
 768                     if (solver_show_working) {
 769                         printf("%*sadjacent possible elimination, (%d,%d) %s (%d,%d):\n",
 770                                solver_recurse_depth*4, "",
 771                                x+1, y+1, isadjacent ? "|" : "!|", nx+1, ny+1);
 772                         printf("%*s  ruling out %d at (%d,%d)\n",
 773                                solver_recurse_depth*4, "", n+1, nx+1, ny+1);
 774                     }
 775 #endif
 776                     cube(nx, ny, n+1) = FALSE;
 777                     nchanged++;
 778                 }
 779             }
 780         }
 781     }
 782
 783     return nchanged;
 784 }
 785
 786 static int solver_easy(struct latin_solver *solver, void *vctx)
 787 {
 788     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 789     if (ctx->state->adjacent)
 790         return solver_adjacent(solver, vctx);
 791     else
 792         return solver_links(solver, vctx);
 793 }
 794
 795 static int solver_set(struct latin_solver *solver, void *vctx)
 796 {
 797     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 798     if (ctx->state->adjacent)
 799         return solver_adjacent_set(solver, vctx);
 800     else
 801         return 0;
 802 }
 803
 804 #define SOLVER(upper,title,func,lower) func,
 805 static usersolver_t const unequal_solvers[] = { DIFFLIST(SOLVER) };
 806
 807 static int solver_state(game_state *state, int maxdiff)
 808 {
 809     struct solver_ctx *ctx = new_ctx(state);
 810     struct latin_solver solver;
 811     int diff;
 812
 813     latin_solver_alloc(&solver, state->nums, state->order);
 814
 815     diff = latin_solver_main(&solver, maxdiff,
 816                              DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
 817                              DIFF_EXTREME, DIFF_RECURSIVE,
 818                              unequal_solvers, ctx, clone_ctx, free_ctx);
 819
 820     memcpy(state->hints, solver.cube, state->order*state->order*state->order);
 821
 822     free_ctx(ctx);
 823
 824     latin_solver_free(&solver);
 825
 826     if (diff == DIFF_IMPOSSIBLE)
 827         return -1;
 828     if (diff == DIFF_UNFINISHED)
 829         return 0;
 830     if (diff == DIFF_AMBIGUOUS)
 831         return 2;
 832     return 1;
 833 }
 834
 835 static game_state *solver_hint(const game_state *state, int *diff_r,
 836                                int mindiff, int maxdiff)
 837 {
 838     game_state *ret = dup_game(state);
 839     int diff, r = 0;
 840
 841     for (diff = mindiff; diff <= maxdiff; diff++) {
 842         r = solver_state(ret, diff);
 843         debug(("solver_state after %s %d", unequal_diffnames[diff], r));
 844         if (r != 0) goto done;
 845     }
 846
 847 done:
 848     if (diff_r) *diff_r = (r > 0) ? diff : -1;
 849     return ret;
 850 }
 851
 852 /* ----------------------------------------------------------
 853  * Game generation.
 854  */
 855
 856 static char *latin_desc(digit *sq, size_t order)
 857 {
 858     int o2 = order*order, i;
 859     char *soln = snewn(o2+2, char);
 860
 861     soln[0] = 'S';
 862     for (i = 0; i < o2; i++)
 863         soln[i+1] = n2c(sq[i], order);
 864     soln[o2+1] = '\0';
 865
 866     return soln;
 867 }
 868
 869 /* returns non-zero if it placed (or could have placed) clue. */
 870 static int gg_place_clue(game_state *state, int ccode, digit *latin, int checkonly)
 871 {
 872     int loc = ccode / 5, which = ccode % 5;
 873     int x = loc % state->order, y = loc / state->order;
 874
 875     assert(loc < state->order*state->order);
 876
 877     if (which == 4) {           /* add number */
 878         if (state->nums[loc] != 0) {
 879 #ifdef STANDALONE_SOLVER
 880             if (state->nums[loc] != latin[loc]) {
 881                 printf("inconsistency for (%d,%d): state %d latin %d\n",
 882                        x+1, y+1, state->nums[loc], latin[loc]);
 883             }
 884 #endif
 885             assert(state->nums[loc] == latin[loc]);
 886             return 0;
 887         }
 888         if (!checkonly) {
 889             state->nums[loc] = latin[loc];
 890         }
 891     } else {                    /* add flag */
 892         int lx, ly, lloc;
 893
 894         if (state->adjacent)
 895             return 0; /* never add flag clues in adjacent mode (they're always
 896                          all present) */
 897
 898         if (state->flags[loc] & adjthan[which].f)
 899             return 0; /* already has flag. */
 900
 901         lx = x + adjthan[which].dx;
 902         ly = y + adjthan[which].dy;
 903         if (lx < 0 || ly < 0 || lx >= state->order || ly >= state->order)
 904             return 0; /* flag compares to off grid */
 905
 906         lloc = loc + adjthan[which].dx + adjthan[which].dy*state->order;
 907         if (latin[loc] <= latin[lloc])
 908             return 0; /* flag would be incorrect */
 909
 910         if (!checkonly) {
 911             state->flags[loc] |= adjthan[which].f;
 912         }
 913     }
 914     return 1;
 915 }
 916
 917 /* returns non-zero if it removed (or could have removed) the clue. */
 918 static int gg_remove_clue(game_state *state, int ccode, int checkonly)
 919 {
 920     int loc = ccode / 5, which = ccode % 5;
 921 #ifdef STANDALONE_SOLVER
 922     int x = loc % state->order, y = loc / state->order;
 923 #endif
 924
 925     assert(loc < state->order*state->order);
 926
 927     if (which == 4) {           /* remove number. */
 928         if (state->nums[loc] == 0) return 0;
 929         if (!checkonly) {
 930 #ifdef STANDALONE_SOLVER
 931             if (solver_show_working)
 932                 printf("gg_remove_clue: removing %d at (%d,%d)",
 933                        state->nums[loc], x+1, y+1);
 934 #endif
 935             state->nums[loc] = 0;
 936         }
 937     } else {                    /* remove flag */
 938         if (state->adjacent)
 939             return 0; /* never remove clues in adjacent mode. */
 940
 941         if (!(state->flags[loc] & adjthan[which].f)) return 0;
 942         if (!checkonly) {
 943 #ifdef STANDALONE_SOLVER
 944             if (solver_show_working)
 945                printf("gg_remove_clue: removing %c at (%d,%d)",
 946                        adjthan[which].c, x+1, y+1);
 947 #endif
 948             state->flags[loc] &= ~adjthan[which].f;
 949         }
 950     }
 951     return 1;
 952 }
 953
 954 static int gg_best_clue(game_state *state, int *scratch, digit *latin)
 955 {
 956     int ls = state->order * state->order * 5;
 957     int maxposs = 0, minclues = 5, best = -1, i, j;
 958     int nposs, nclues, loc;
 959
 960 #ifdef STANDALONE_SOLVER
 961     if (solver_show_working) {
 962         game_debug(state);
 963         latin_solver_debug(state->hints, state->order);
 964     }
 965 #endif
 966
 967     for (i = ls; i-- > 0 ;) {
 968         if (!gg_place_clue(state, scratch[i], latin, 1)) continue;
 969
 970         loc = scratch[i] / 5;
 971         for (j = nposs = 0; j < state->order; j++) {
 972             if (state->hints[loc*state->order + j]) nposs++;
 973         }
 974         for (j = nclues = 0; j < 4; j++) {
 975             if (state->flags[loc] & adjthan[j].f) nclues++;
 976         }
 977         if ((nposs > maxposs) ||
 978             (nposs == maxposs && nclues < minclues)) {
 979             best = i; maxposs = nposs; minclues = nclues;
 980 #ifdef STANDALONE_SOLVER
 981             if (solver_show_working) {
 982                 int x = loc % state->order, y = loc / state->order;
 983                 printf("gg_best_clue: b%d (%d,%d) new best [%d poss, %d clues].\n",
 984                        best, x+1, y+1, nposs, nclues);
 985             }
 986 #endif
 987         }
 988     }
 989     /* if we didn't solve, we must have 1 clue to place! */
 990     assert(best != -1);
 991     return best;
 992 }
 993
 994 #ifdef STANDALONE_SOLVER
 995 int maxtries;
 996 #define MAXTRIES maxtries
 997 #else
 998 #define MAXTRIES 50
 999 #endif
1000 int gg_solved;
1001
1002 static int game_assemble(game_state *new, int *scratch, digit *latin,
1003                          int difficulty)
1004 {
1005     game_state *copy = dup_game(new);
1006     int best;
1007
1008     if (difficulty >= DIFF_RECURSIVE) {
1009         /* We mustn't use any solver that might guess answers;
1010          * if it guesses wrongly but solves, gg_place_clue will
1011          * get mighty confused. We will always trim clues down
1012          * (making it more difficult) in game_strip, which doesn't
1013          * have this problem. */
1014         difficulty = DIFF_RECURSIVE-1;
1015     }
1016
1017 #ifdef STANDALONE_SOLVER
1018     if (solver_show_working) {
1019         game_debug(new);
1020         latin_solver_debug(new->hints, new->order);
1021     }
1022 #endif
1023
1024     while(1) {
1025         gg_solved++;
1026         if (solver_state(copy, difficulty) == 1) break;
1027
1028         best = gg_best_clue(copy, scratch, latin);
1029         gg_place_clue(new, scratch[best], latin, 0);
1030         gg_place_clue(copy, scratch[best], latin, 0);
1031     }
1032     free_game(copy);
1033 #ifdef STANDALONE_SOLVER
1034     if (solver_show_working) {
1035         char *dbg = game_text_format(new);
1036         printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved, dbg);
1037         sfree(dbg);
1038     }
1039 #endif
1040     return 0;
1041 }
1042
1043 static void game_strip(game_state *new, int *scratch, digit *latin,
1044                        int difficulty)
1045 {
1046     int o = new->order, o2 = o*o, lscratch = o2*5, i;
1047     game_state *copy = blank_game(new->order, new->adjacent);
1048
1049     /* For each symbol (if it exists in new), try and remove it and
1050      * solve again; if we couldn't solve without it put it back. */
1051     for (i = 0; i < lscratch; i++) {
1052         if (!gg_remove_clue(new, scratch[i], 0)) continue;
1053
1054         memcpy(copy->nums,  new->nums,  o2 * sizeof(digit));
1055         memcpy(copy->flags, new->flags, o2 * sizeof(unsigned int));
1056         gg_solved++;
1057         if (solver_state(copy, difficulty) != 1) {
1058             /* put clue back, we can't solve without it. */
1059             int ret = gg_place_clue(new, scratch[i], latin, 0);
1060             assert(ret == 1);
1061         } else {
1062 #ifdef STANDALONE_SOLVER
1063             if (solver_show_working)
1064                 printf("game_strip: clue was redundant.");
1065 #endif
1066         }
1067     }
1068     free_game(copy);
1069 #ifdef STANDALONE_SOLVER
1070     if (solver_show_working) {
1071         char *dbg = game_text_format(new);
1072         debug(("game_strip: done, %d solver iterations.", gg_solved));
1073         debug(("%s", dbg));
1074         sfree(dbg);
1075     }
1076 #endif
1077 }
1078
1079 static void add_adjacent_flags(game_state *state, digit *latin)
1080 {
1081     int x, y, o = state->order;
1082
1083     /* All clues in adjacent mode are always present (the only variables are
1084      * the numbers). This adds all the flags to state based on the supplied
1085      * latin square. */
1086
1087     for (y = 0; y < o; y++) {
1088         for (x = 0; x < o; x++) {
1089             if (x < (o-1) && (abs(latin[y*o+x] - latin[y*o+x+1]) == 1)) {
1090                 GRID(state, flags, x, y) |= F_ADJ_RIGHT;
1091                 GRID(state, flags, x+1, y) |= F_ADJ_LEFT;
1092             }
1093             if (y < (o-1) && (abs(latin[y*o+x] - latin[(y+1)*o+x]) == 1)) {
1094                 GRID(state, flags, x, y) |= F_ADJ_DOWN;
1095                 GRID(state, flags, x, y+1) |= F_ADJ_UP;
1096             }
1097         }
1098     }
1099 }
1100
1101 static char *new_game_desc(const game_params *params_in, random_state *rs,
1102                            char **aux, int interactive)
1103 {
1104     game_params params_copy = *params_in; /* structure copy */
1105     game_params *params = &params_copy;
1106     digit *sq = NULL;
1107     int i, x, y, retlen, k, nsol;
1108     int o2 = params->order * params->order, ntries = 1;
1109     int *scratch, lscratch = o2*5;
1110     char *ret, buf[80];
1111     game_state *state = blank_game(params->order, params->adjacent);
1112
1113     /* Generate a list of 'things to strip' (randomised later) */
1114     scratch = snewn(lscratch, int);
1115     /* Put the numbers (4 mod 5) before the inequalities (0-3 mod 5) */
1116     for (i = 0; i < lscratch; i++) scratch[i] = (i%o2)*5 + 4 - (i/o2);
1117
1118 generate:
1119 #ifdef STANDALONE_SOLVER
1120     if (solver_show_working)
1121         printf("new_game_desc: generating %s puzzle, ntries so far %d\n",
1122                unequal_diffnames[params->diff], ntries);
1123 #endif
1124     if (sq) sfree(sq);
1125     sq = latin_generate(params->order, rs);
1126     latin_debug(sq, params->order);
1127     /* Separately shuffle the numeric and inequality clues */
1128     shuffle(scratch, lscratch/5, sizeof(int), rs);
1129     shuffle(scratch+lscratch/5, 4*lscratch/5, sizeof(int), rs);
1130
1131     memset(state->nums, 0, o2 * sizeof(digit));
1132     memset(state->flags, 0, o2 * sizeof(unsigned int));
1133
1134     if (state->adjacent) {
1135         /* All adjacency flags are always present. */
1136         add_adjacent_flags(state, sq);
1137     }
1138
1139     gg_solved = 0;
1140     if (game_assemble(state, scratch, sq, params->diff) < 0)
1141         goto generate;
1142     game_strip(state, scratch, sq, params->diff);
1143
1144     if (params->diff > 0) {
1145         game_state *copy = dup_game(state);
1146         nsol = solver_state(copy, params->diff-1);
1147         free_game(copy);
1148         if (nsol > 0) {
1149 #ifdef STANDALONE_SOLVER
1150             if (solver_show_working)
1151                 printf("game_assemble: puzzle as generated is too easy.\n");
1152 #endif
1153             if (ntries < MAXTRIES) {
1154                 ntries++;
1155                 goto generate;
1156             }
1157 #ifdef STANDALONE_SOLVER
1158             if (solver_show_working)
1159                 printf("Unable to generate %s %dx%d after %d attempts.\n",
1160                        unequal_diffnames[params->diff],
1161                        params->order, params->order, MAXTRIES);
1162 #endif
1163             params->diff--;
1164         }
1165     }
1166 #ifdef STANDALONE_SOLVER
1167     if (solver_show_working)
1168         printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).\n",
1169                unequal_diffnames[params->diff], ntries, gg_solved);
1170 #endif
1171
1172     ret = NULL; retlen = 0;
1173     for (y = 0; y < params->order; y++) {
1174         for (x = 0; x < params->order; x++) {
1175             unsigned int f = GRID(state, flags, x, y);
1176             k = sprintf(buf, "%d%s%s%s%s,",
1177                         GRID(state, nums, x, y),
1178                         (f & F_ADJ_UP)    ? "U" : "",
1179                         (f & F_ADJ_RIGHT) ? "R" : "",
1180                         (f & F_ADJ_DOWN)  ? "D" : "",
1181                         (f & F_ADJ_LEFT)  ? "L" : "");
1182
1183             ret = sresize(ret, retlen + k + 1, char);
1184             strcpy(ret + retlen, buf);
1185             retlen += k;
1186         }
1187     }
1188     *aux = latin_desc(sq, params->order);
1189
1190     free_game(state);
1191     sfree(sq);
1192     sfree(scratch);
1193
1194     return ret;
1195 }
1196
1197 static game_state *load_game(const game_params *params, const char *desc,
1198                              char **why_r)
1199 {
1200     game_state *state = blank_game(params->order, params->adjacent);
1201     const char *p = desc;
1202     int i = 0, n, o = params->order, x, y;
1203     char *why = NULL;
1204
1205     while (*p) {
1206         while (*p >= 'a' && *p <= 'z') {
1207             i += *p - 'a' + 1;
1208             p++;
1209         }
1210         if (i >= o*o) {
1211             why = "Too much data to fill grid"; goto fail;
1212         }
1213
1214         if (*p < '0' || *p > '9') {
1215             why = "Expecting number in game description"; goto fail;
1216         }
1217         n = atoi(p);
1218         if (n < 0 || n > o) {
1219             why = "Out-of-range number in game description"; goto fail;
1220         }
1221         state->nums[i] = (digit)n;
1222         while (*p >= '0' && *p <= '9') p++; /* skip number */
1223
1224         if (state->nums[i] != 0)
1225             state->flags[i] |= F_IMMUTABLE; /* === number set by game description */
1226
1227         while (*p == 'U' || *p == 'R' || *p == 'D' || *p == 'L') {
1228             switch (*p) {
1229             case 'U': state->flags[i] |= F_ADJ_UP;    break;
1230             case 'R': state->flags[i] |= F_ADJ_RIGHT; break;
1231             case 'D': state->flags[i] |= F_ADJ_DOWN;  break;
1232             case 'L': state->flags[i] |= F_ADJ_LEFT;  break;
1233             default: why = "Expecting flag URDL in game description"; goto fail;
1234             }
1235             p++;
1236         }
1237         i++;
1238         if (i < o*o && *p != ',') {
1239             why = "Missing separator"; goto fail;
1240         }
1241         if (*p == ',') p++;
1242     }
1243     if (i < o*o) {
1244         why = "Not enough data to fill grid"; goto fail;
1245     }
1246     i = 0;
1247     for (y = 0; y < o; y++) {
1248         for (x = 0; x < o; x++) {
1249             for (n = 0; n < 4; n++) {
1250                 if (GRID(state, flags, x, y) & adjthan[n].f) {
1251                     int nx = x + adjthan[n].dx;
1252                     int ny = y + adjthan[n].dy;
1253                     /* a flag must not point us off the grid. */
1254                     if (nx < 0 || ny < 0 || nx >= o || ny >= o) {
1255                         why = "Flags go off grid"; goto fail;
1256                     }
1257                     if (params->adjacent) {
1258                         /* if one cell is adjacent to another, the other must
1259                          * also be adjacent to the first. */
1260                         if (!(GRID(state, flags, nx, ny) & adjthan[n].fo)) {
1261                             why = "Flags contradicting each other"; goto fail;
1262                         }
1263                     } else {
1264                         /* if one cell is GT another, the other must _not_ also
1265                          * be GT the first. */
1266                         if (GRID(state, flags, nx, ny) & adjthan[n].fo) {
1267                             why = "Flags contradicting each other"; goto fail;
1268                         }
1269                     }
1270                 }
1271             }
1272         }
1273     }
1274
1275     return state;
1276
1277 fail:
1278     free_game(state);
1279     if (why_r) *why_r = why;
1280     return NULL;
1281 }
1282
1283 static game_state *new_game(midend *me, const game_params *params,
1284                             const char *desc)
1285 {
1286     game_state *state = load_game(params, desc, NULL);
1287     if (!state) {
1288         assert("Unable to load ?validated game.");
1289         return NULL;
1290     }
1291     return state;
1292 }
1293
1294 static const char *validate_desc(const game_params *params, const char *desc)
1295 {
1296     char *why = NULL;
1297     game_state *dummy = load_game(params, desc, &why);
1298     if (dummy) {
1299         free_game(dummy);
1300         assert(!why);
1301     } else
1302         assert(why);
1303     return why;
1304 }
1305
1306 static char *solve_game(const game_state *state, const game_state *currstate,
1307                         const char *aux, const char **error)
1308 {
1309     game_state *solved;
1310     int r;
1311     char *ret = NULL;
1312
1313     if (aux) return dupstr(aux);
1314
1315     solved = dup_game(state);
1316     for (r = 0; r < state->order*state->order; r++) {
1317         if (!(solved->flags[r] & F_IMMUTABLE))
1318             solved->nums[r] = 0;
1319     }
1320     r = solver_state(solved, DIFFCOUNT-1);   /* always use full solver */
1321     if (r > 0) ret = latin_desc(solved->nums, solved->order);
1322     free_game(solved);
1323     return ret;
1324 }
1325
1326 /* ----------------------------------------------------------
1327  * Game UI input processing.
1328  */
1329
1330 struct game_ui {
1331     int hx, hy;                         /* as for solo.c, highlight pos */
1332     int hshow, hpencil, hcursor;        /* show state, type, and ?cursor. */
1333 };
1334
1335 static game_ui *new_ui(const game_state *state)
1336 {
1337     game_ui *ui = snew(game_ui);
1338
1339     ui->hx = ui->hy = 0;
1340     ui->hpencil = ui->hshow = ui->hcursor = 0;
1341
1342     return ui;
1343 }
1344
1345 static void free_ui(game_ui *ui)
1346 {
1347     sfree(ui);
1348 }
1349
1350 static char *encode_ui(const game_ui *ui)
1351 {
1352     return NULL;
1353 }
1354
1355 static void decode_ui(game_ui *ui, const char *encoding)
1356 {
1357 }
1358
1359 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1360                                const game_state *newstate)
1361 {
1362     /* See solo.c; if we were pencil-mode highlighting and
1363      * somehow a square has just been properly filled, cancel
1364      * pencil mode. */
1365     if (ui->hshow && ui->hpencil && !ui->hcursor &&
1366         GRID(newstate, nums, ui->hx, ui->hy) != 0) {
1367         ui->hshow = 0;
1368     }
1369 }
1370
1371 struct game_drawstate {
1372     int tilesize, order, started, adjacent;
1373     digit *nums;                /* copy of nums, o^2 */
1374     unsigned char *hints;       /* copy of hints, o^3 */
1375     unsigned int *flags;        /* o^2 */
1376
1377     int hx, hy, hshow, hpencil; /* as for game_ui. */
1378     int hflash;
1379 };
1380
1381 static char *interpret_move(const game_state *state, game_ui *ui,
1382                             const game_drawstate *ds,
1383                             int ox, int oy, int button)
1384 {
1385     int x = FROMCOORD(ox), y = FROMCOORD(oy), n;
1386     char buf[80];
1387     int shift_or_control = button & (MOD_SHFT | MOD_CTRL);
1388
1389     button &= ~MOD_MASK;
1390
1391     if (x >= 0 && x < ds->order && y >= 0 && y < ds->order && IS_MOUSE_DOWN(button)) {
1392         if (oy - COORD(y) > TILE_SIZE && ox - COORD(x) > TILE_SIZE)
1393             return NULL;
1394
1395         if (oy - COORD(y) > TILE_SIZE) {
1396             if (GRID(state, flags, x, y) & F_ADJ_DOWN)
1397                 sprintf(buf, "F%d,%d,%d", x, y, F_SPENT_DOWN);
1398             else if (y + 1 < ds->order && GRID(state, flags, x, y + 1) & F_ADJ_UP)
1399                 sprintf(buf, "F%d,%d,%d", x, y + 1, F_SPENT_UP);
1400             else return NULL;
1401             return dupstr(buf);
1402         }
1403
1404         if (ox - COORD(x) > TILE_SIZE) {
1405             if (GRID(state, flags, x, y) & F_ADJ_RIGHT)
1406                 sprintf(buf, "F%d,%d,%d", x, y, F_SPENT_RIGHT);
1407             else if (x + 1 < ds->order && GRID(state, flags, x + 1, y) & F_ADJ_LEFT)
1408                 sprintf(buf, "F%d,%d,%d", x + 1, y, F_SPENT_LEFT);
1409             else return NULL;
1410             return dupstr(buf);
1411         }
1412
1413         if (button == LEFT_BUTTON) {
1414             /* normal highlighting for non-immutable squares */
1415             if (GRID(state, flags, x, y) & F_IMMUTABLE)
1416                 ui->hshow = 0;
1417             else if (x == ui->hx && y == ui->hy &&
1418                      ui->hshow && ui->hpencil == 0)
1419                 ui->hshow = 0;
1420             else {
1421                 ui->hx = x; ui->hy = y; ui->hpencil = 0;
1422                 ui->hshow = 1;
1423             }
1424             ui->hcursor = 0;
1425             return UI_UPDATE;
1426         }
1427         if (button == RIGHT_BUTTON) {
1428             /* pencil highlighting for non-filled squares */
1429             if (GRID(state, nums, x, y) != 0)
1430                 ui->hshow = 0;
1431             else if (x == ui->hx && y == ui->hy &&
1432                      ui->hshow && ui->hpencil)
1433                 ui->hshow = 0;
1434             else {
1435                 ui->hx = x; ui->hy = y; ui->hpencil = 1;
1436                 ui->hshow = 1;
1437             }
1438             ui->hcursor = 0;
1439             return UI_UPDATE;
1440         }
1441     }
1442
1443     if (IS_CURSOR_MOVE(button)) {
1444         if (shift_or_control) {
1445             int nx = ui->hx, ny = ui->hy, i, self;
1446             move_cursor(button, &nx, &ny, ds->order, ds->order, FALSE);
1447             ui->hshow = ui->hcursor = 1;
1448
1449             for (i = 0; i < 4 && (nx != ui->hx + adjthan[i].dx ||
1450                                   ny != ui->hy + adjthan[i].dy); ++i);
1451
1452             if (i == 4)
1453                 return UI_UPDATE; /* invalid direction, i.e. out of
1454                                    * the board */
1455
1456             if (!(GRID(state, flags, ui->hx, ui->hy) & adjthan[i].f ||
1457                   GRID(state, flags, nx,     ny    ) & adjthan[i].fo))
1458                 return UI_UPDATE; /* no clue to toggle */
1459
1460             if (state->adjacent)
1461                 self = (adjthan[i].dx >= 0 && adjthan[i].dy >= 0);
1462             else
1463                 self = (GRID(state, flags, ui->hx, ui->hy) & adjthan[i].f);
1464
1465             if (self)
1466                 sprintf(buf, "F%d,%d,%d", ui->hx, ui->hy,
1467                         ADJ_TO_SPENT(adjthan[i].f));
1468             else
1469                 sprintf(buf, "F%d,%d,%d", nx, ny,
1470                         ADJ_TO_SPENT(adjthan[i].fo));
1471
1472             return dupstr(buf);
1473         } else {
1474             move_cursor(button, &ui->hx, &ui->hy, ds->order, ds->order, FALSE);
1475             ui->hshow = ui->hcursor = 1;
1476             return UI_UPDATE;
1477         }
1478     }
1479     if (ui->hshow && IS_CURSOR_SELECT(button)) {
1480         ui->hpencil = 1 - ui->hpencil;
1481         ui->hcursor = 1;
1482         return UI_UPDATE;
1483     }
1484
1485     n = c2n(button, state->order);
1486     if (ui->hshow && n >= 0 && n <= ds->order) {
1487         debug(("button %d, cbutton %d", button, (int)((char)button)));
1488
1489         debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1490                n, ui->hx, ui->hy, ui->hpencil,
1491                GRID(state, flags, ui->hx, ui->hy),
1492                GRID(state, nums, ui->hx, ui->hy)));
1493
1494         if (GRID(state, flags, ui->hx, ui->hy) & F_IMMUTABLE)
1495             return NULL;        /* can't edit immutable square (!) */
1496         if (ui->hpencil && GRID(state, nums, ui->hx, ui->hy) > 0)
1497             return NULL;        /* can't change hints on filled square (!) */
1498
1499
1500         sprintf(buf, "%c%d,%d,%d",
1501                 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1502
1503         if (!ui->hcursor) ui->hshow = 0;
1504
1505         return dupstr(buf);
1506     }
1507
1508     if (button == 'H' || button == 'h')
1509         return dupstr("H");
1510     if (button == 'M' || button == 'm')
1511         return dupstr("M");
1512
1513     return NULL;
1514 }
1515
1516 static game_state *execute_move(const game_state *state, const char *move)
1517 {
1518     game_state *ret = NULL;
1519     int x, y, n, i, rc;
1520
1521     debug(("execute_move: %s", move));
1522
1523     if ((move[0] == 'P' || move[0] == 'R') &&
1524         sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1525         x >= 0 && x < state->order && y >= 0 && y < state->order &&
1526         n >= 0 && n <= state->order) {
1527         ret = dup_game(state);
1528         if (move[0] == 'P' && n > 0)
1529             HINT(ret, x, y, n-1) = !HINT(ret, x, y, n-1);
1530         else {
1531             GRID(ret, nums, x, y) = n;
1532             for (i = 0; i < state->order; i++)
1533                 HINT(ret, x, y, i) = 0;
1534
1535             /* real change to grid; check for completion */
1536             if (!ret->completed && check_complete(ret->nums, ret, 1) > 0)
1537                 ret->completed = TRUE;
1538         }
1539         return ret;
1540     } else if (move[0] == 'S') {
1541         const char *p;
1542
1543         ret = dup_game(state);
1544         ret->completed = ret->cheated = TRUE;
1545
1546         p = move+1;
1547         for (i = 0; i < state->order*state->order; i++) {
1548             n = c2n((int)*p, state->order);
1549             if (!*p || n <= 0 || n > state->order)
1550                 goto badmove;
1551             ret->nums[i] = n;
1552             p++;
1553         }
1554         if (*p) goto badmove;
1555         rc = check_complete(ret->nums, ret, 1);
1556         assert(rc > 0);
1557         return ret;
1558     } else if (move[0] == 'M') {
1559         ret = dup_game(state);
1560         for (x = 0; x < state->order; x++) {
1561             for (y = 0; y < state->order; y++) {
1562                 for (n = 0; n < state->order; n++) {
1563                     HINT(ret, x, y, n) = 1;
1564                 }
1565             }
1566         }
1567         return ret;
1568     } else if (move[0] == 'H') {
1569         return solver_hint(state, NULL, DIFF_EASY, DIFF_EASY);
1570     } else if (move[0] == 'F' && sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1571                x >= 0 && x < state->order && y >= 0 && y < state->order) {
1572         ret = dup_game(state);
1573         GRID(ret, flags, x, y) ^= n;
1574         return ret;
1575     }
1576
1577 badmove:
1578     if (ret) free_game(ret);
1579     return NULL;
1580 }
1581
1582 /* ----------------------------------------------------------------------
1583  * Drawing/printing routines.
1584  */
1585
1586 #define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2)
1587
1588 static void game_compute_size(const game_params *params, int tilesize,
1589                               int *x, int *y)
1590 {
1591     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1592     struct { int tilesize, order; } ads, *ds = &ads;
1593     ads.tilesize = tilesize;
1594     ads.order = params->order;
1595
1596     *x = *y = DRAW_SIZE;
1597 }
1598
1599 static void game_set_size(drawing *dr, game_drawstate *ds,
1600                           const game_params *params, int tilesize)
1601 {
1602     ds->tilesize = tilesize;
1603 }
1604
1605 static float *game_colours(frontend *fe, int *ncolours)
1606 {
1607     float *ret = snewn(3 * NCOLOURS, float);
1608     int i;
1609
1610     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1611
1612     for (i = 0; i < 3; i++) {
1613         ret[COL_TEXT * 3 + i] = 0.0F;
1614         ret[COL_GRID * 3 + i] = 0.5F;
1615     }
1616
1617     /* Lots of these were taken from solo.c. */
1618     ret[COL_GUESS * 3 + 0] = 0.0F;
1619     ret[COL_GUESS * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1620     ret[COL_GUESS * 3 + 2] = 0.0F;
1621
1622     ret[COL_ERROR * 3 + 0] = 1.0F;
1623     ret[COL_ERROR * 3 + 1] = 0.0F;
1624     ret[COL_ERROR * 3 + 2] = 0.0F;
1625
1626     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1627     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1628     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1629
1630     *ncolours = NCOLOURS;
1631     return ret;
1632 }
1633
1634 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1635 {
1636     struct game_drawstate *ds = snew(struct game_drawstate);
1637     int o2 = state->order*state->order, o3 = o2*state->order;
1638
1639     ds->tilesize = 0;
1640     ds->order = state->order;
1641     ds->adjacent = state->adjacent;
1642
1643     ds->nums = snewn(o2, digit);
1644     ds->hints = snewn(o3, unsigned char);
1645     ds->flags = snewn(o2, unsigned int);
1646     memset(ds->nums, 0, o2*sizeof(digit));
1647     memset(ds->hints, 0, o3);
1648     memset(ds->flags, 0, o2*sizeof(unsigned int));
1649
1650     ds->hx = ds->hy = 0;
1651     ds->started = ds->hshow = ds->hpencil = ds->hflash = 0;
1652
1653     return ds;
1654 }
1655
1656 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1657 {
1658     sfree(ds->nums);
1659     sfree(ds->hints);
1660     sfree(ds->flags);
1661     sfree(ds);
1662 }
1663
1664 static void draw_gt(drawing *dr, int ox, int oy,
1665                     int dx1, int dy1, int dx2, int dy2, int col)
1666 {
1667     int coords[12];
1668     int xdx = (dx1+dx2 ? 0 : 1), xdy = (dx1+dx2 ? 1 : 0);
1669     coords[0] = ox + xdx;
1670     coords[1] = oy + xdy;
1671     coords[2] = ox + xdx + dx1;
1672     coords[3] = oy + xdy + dy1;
1673     coords[4] = ox + xdx + dx1 + dx2;
1674     coords[5] = oy + xdy + dy1 + dy2;
1675     coords[6] = ox - xdx + dx1 + dx2;
1676     coords[7] = oy - xdy + dy1 + dy2;
1677     coords[8] = ox - xdx + dx1;
1678     coords[9] = oy - xdy + dy1;
1679     coords[10] = ox - xdx;
1680     coords[11] = oy - xdy;
1681     draw_polygon(dr, coords, 6, col, col);
1682 }
1683
1684 #define COLOUR(direction) (f & (F_ERROR_##direction) ? COL_ERROR : \
1685                            f & (F_SPENT_##direction) ? COL_SPENT : fg)
1686
1687 static void draw_gts(drawing *dr, game_drawstate *ds, int ox, int oy,
1688                      unsigned int f, int bg, int fg)
1689 {
1690     int g = GAP_SIZE, g2 = (g+1)/2, g4 = (g+1)/4;
1691
1692     /* Draw all the greater-than signs emanating from this tile. */
1693
1694     if (f & F_ADJ_UP) {
1695         if (bg >= 0) draw_rect(dr, ox, oy - g, TILE_SIZE, g, bg);
1696         draw_gt(dr, ox+g2, oy-g4, g2, -g2, g2, g2, COLOUR(UP));
1697         draw_update(dr, ox, oy-g, TILE_SIZE, g);
1698     }
1699     if (f & F_ADJ_RIGHT) {
1700         if (bg >= 0) draw_rect(dr, ox + TILE_SIZE, oy, g, TILE_SIZE, bg);
1701         draw_gt(dr, ox+TILE_SIZE+g4, oy+g2, g2, g2, -g2, g2, COLOUR(RIGHT));
1702         draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1703     }
1704     if (f & F_ADJ_DOWN) {
1705         if (bg >= 0) draw_rect(dr, ox, oy + TILE_SIZE, TILE_SIZE, g, bg);
1706         draw_gt(dr, ox+g2, oy+TILE_SIZE+g4, g2, g2, g2, -g2, COLOUR(DOWN));
1707         draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1708     }
1709     if (f & F_ADJ_LEFT) {
1710         if (bg >= 0) draw_rect(dr, ox - g, oy, g, TILE_SIZE, bg);
1711         draw_gt(dr, ox-g4, oy+g2, -g2, g2, g2, g2, COLOUR(LEFT));
1712         draw_update(dr, ox-g, oy, g, TILE_SIZE);
1713     }
1714 }
1715
1716 static void draw_adjs(drawing *dr, game_drawstate *ds, int ox, int oy,
1717                       unsigned int f, int bg, int fg)
1718 {
1719     int g = GAP_SIZE, g38 = 3*(g+1)/8, g4 = (g+1)/4;
1720
1721     /* Draw all the adjacency bars relevant to this tile; we only have
1722      * to worry about F_ADJ_RIGHT and F_ADJ_DOWN.
1723      *
1724      * If we _only_ have the error flag set (i.e. it's not supposed to be
1725      * adjacent, but adjacent numbers were entered) draw an outline red bar.
1726      */
1727
1728     if (f & (F_ADJ_RIGHT|F_ERROR_RIGHT)) {
1729         if (f & F_ADJ_RIGHT) {
1730             draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COLOUR(RIGHT));
1731         } else {
1732             draw_rect_outline(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COL_ERROR);
1733         }
1734     } else if (bg >= 0) {
1735         draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, bg);
1736     }
1737     draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1738
1739     if (f & (F_ADJ_DOWN|F_ERROR_DOWN)) {
1740         if (f & F_ADJ_DOWN) {
1741             draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COLOUR(DOWN));
1742         } else {
1743             draw_rect_outline(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COL_ERROR);
1744         }
1745     } else if (bg >= 0) {
1746         draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, bg);
1747     }
1748     draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1749 }
1750
1751 static void draw_furniture(drawing *dr, game_drawstate *ds,
1752                            const game_state *state, const game_ui *ui,
1753                            int x, int y, int hflash)
1754 {
1755     int ox = COORD(x), oy = COORD(y), bg, hon;
1756     unsigned int f = GRID(state, flags, x, y);
1757
1758     bg = hflash ? COL_HIGHLIGHT : COL_BACKGROUND;
1759
1760     hon = (ui->hshow && x == ui->hx && y == ui->hy);
1761
1762     /* Clear square. */
1763     draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
1764               (hon && !ui->hpencil) ? COL_HIGHLIGHT : bg);
1765
1766     /* Draw the highlight (pencil or full), if we're the highlight */
1767     if (hon && ui->hpencil) {
1768         int coords[6];
1769         coords[0] = ox;
1770         coords[1] = oy;
1771         coords[2] = ox + TILE_SIZE/2;
1772         coords[3] = oy;
1773         coords[4] = ox;
1774         coords[5] = oy + TILE_SIZE/2;
1775         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1776     }
1777
1778     /* Draw the square outline (which is the cursor, if we're the cursor). */
1779     draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
1780
1781     draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
1782
1783     /* Draw the adjacent clue signs. */
1784     if (ds->adjacent)
1785         draw_adjs(dr, ds, ox, oy, f, COL_BACKGROUND, COL_GRID);
1786     else
1787         draw_gts(dr, ds, ox, oy, f, COL_BACKGROUND, COL_TEXT);
1788 }
1789
1790 static void draw_num(drawing *dr, game_drawstate *ds, int x, int y)
1791 {
1792     int ox = COORD(x), oy = COORD(y);
1793     unsigned int f = GRID(ds,flags,x,y);
1794     char str[2];
1795
1796     /* (can assume square has just been cleared) */
1797
1798     /* Draw number, choosing appropriate colour */
1799     str[0] = n2c(GRID(ds, nums, x, y), ds->order);
1800     str[1] = '\0';
1801     draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1802               FONT_VARIABLE, 3*TILE_SIZE/4, ALIGN_VCENTRE | ALIGN_HCENTRE,
1803               (f & F_IMMUTABLE) ? COL_TEXT : (f & F_ERROR) ? COL_ERROR : COL_GUESS, str);
1804 }
1805
1806 static void draw_hints(drawing *dr, game_drawstate *ds, int x, int y)
1807 {
1808     int ox = COORD(x), oy = COORD(y);
1809     int nhints, i, j, hw, hh, hmax, fontsz;
1810     char str[2];
1811
1812     /* (can assume square has just been cleared) */
1813
1814     /* Draw hints; steal ingenious algorithm (basically)
1815      * from solo.c:draw_number() */
1816     for (i = nhints = 0; i < ds->order; i++) {
1817         if (HINT(ds, x, y, i)) nhints++;
1818     }
1819
1820     for (hw = 1; hw * hw < nhints; hw++);
1821     if (hw < 3) hw = 3;
1822     hh = (nhints + hw - 1) / hw;
1823     if (hh < 2) hh = 2;
1824     hmax = max(hw, hh);
1825     fontsz = TILE_SIZE/(hmax*(11-hmax)/8);
1826
1827     for (i = j = 0; i < ds->order; i++) {
1828         if (HINT(ds,x,y,i)) {
1829             int hx = j % hw, hy = j / hw;
1830
1831             str[0] = n2c(i+1, ds->order);
1832             str[1] = '\0';
1833             draw_text(dr,
1834                       ox + (4*hx+3) * TILE_SIZE / (4*hw+2),
1835                       oy + (4*hy+3) * TILE_SIZE / (4*hh+2),
1836                       FONT_VARIABLE, fontsz,
1837                       ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1838             j++;
1839         }
1840     }
1841 }
1842
1843 static void game_redraw(drawing *dr, game_drawstate *ds,
1844                         const game_state *oldstate, const game_state *state,
1845                         int dir, const game_ui *ui,
1846                         float animtime, float flashtime)
1847 {
1848     int x, y, i, hchanged = 0, stale, hflash = 0;
1849
1850     debug(("highlight old (%d,%d), new (%d,%d)", ds->hx, ds->hy, ui->hx, ui->hy));
1851
1852     if (flashtime > 0 &&
1853         (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3))
1854          hflash = 1;
1855
1856     if (!ds->started) {
1857         draw_rect(dr, 0, 0, DRAW_SIZE, DRAW_SIZE, COL_BACKGROUND);
1858         draw_update(dr, 0, 0, DRAW_SIZE, DRAW_SIZE);
1859     }
1860     if (ds->hx != ui->hx || ds->hy != ui->hy ||
1861         ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
1862         hchanged = 1;
1863
1864     for (x = 0; x < ds->order; x++) {
1865         for (y = 0; y < ds->order; y++) {
1866             if (!ds->started)
1867                 stale = 1;
1868             else if (hflash != ds->hflash)
1869                 stale = 1;
1870             else
1871                 stale = 0;
1872
1873             if (hchanged) {
1874                 if ((x == ui->hx && y == ui->hy) ||
1875                     (x == ds->hx && y == ds->hy))
1876                     stale = 1;
1877             }
1878
1879             if (GRID(state, nums, x, y) != GRID(ds, nums, x, y)) {
1880                 GRID(ds, nums, x, y) = GRID(state, nums, x, y);
1881                 stale = 1;
1882             }
1883             if (GRID(state, flags, x, y) != GRID(ds, flags, x, y)) {
1884                 GRID(ds, flags, x, y) = GRID(state, flags, x, y);
1885                 stale = 1;
1886             }
1887             if (GRID(ds, nums, x, y) == 0) {
1888                 /* We're not a number square (therefore we might
1889                  * display hints); do we need to update? */
1890                 for (i = 0; i < ds->order; i++) {
1891                     if (HINT(state, x, y, i) != HINT(ds, x, y, i)) {
1892                         HINT(ds, x, y, i) = HINT(state, x, y, i);
1893                         stale = 1;
1894                     }
1895                 }
1896             }
1897             if (stale) {
1898                 draw_furniture(dr, ds, state, ui, x, y, hflash);
1899                 if (GRID(ds, nums, x, y) > 0)
1900                     draw_num(dr, ds, x, y);
1901                 else
1902                     draw_hints(dr, ds, x, y);
1903             }
1904         }
1905     }
1906     ds->hx = ui->hx; ds->hy = ui->hy;
1907     ds->hshow = ui->hshow;
1908     ds->hpencil = ui->hpencil;
1909
1910     ds->started = 1;
1911     ds->hflash = hflash;
1912 }
1913
1914 static float game_anim_length(const game_state *oldstate,
1915                               const game_state *newstate, int dir, game_ui *ui)
1916 {
1917     return 0.0F;
1918 }
1919
1920 static float game_flash_length(const game_state *oldstate,
1921                                const game_state *newstate, int dir, game_ui *ui)
1922 {
1923     if (!oldstate->completed && newstate->completed &&
1924         !oldstate->cheated && !newstate->cheated)
1925         return FLASH_TIME;
1926     return 0.0F;
1927 }
1928
1929 static int game_status(const game_state *state)
1930 {
1931     return state->completed ? +1 : 0;
1932 }
1933
1934 static int game_timing_state(const game_state *state, game_ui *ui)
1935 {
1936     return TRUE;
1937 }
1938
1939 static void game_print_size(const game_params *params, float *x, float *y)
1940 {
1941     int pw, ph;
1942
1943     /* 10mm squares by default, roughly the same as Grauniad. */
1944     game_compute_size(params, 1000, &pw, &ph);
1945     *x = pw / 100.0F;
1946     *y = ph / 100.0F;
1947 }
1948
1949 static void game_print(drawing *dr, const game_state *state, int tilesize)
1950 {
1951     int ink = print_mono_colour(dr, 0);
1952     int x, y, o = state->order, ox, oy, n;
1953     char str[2];
1954
1955     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1956     game_drawstate ads, *ds = &ads;
1957     game_set_size(dr, ds, NULL, tilesize);
1958
1959     print_line_width(dr, 2 * TILE_SIZE / 40);
1960
1961     /* Squares, numbers, gt signs */
1962     for (y = 0; y < o; y++) {
1963         for (x = 0; x < o; x++) {
1964             ox = COORD(x); oy = COORD(y);
1965             n = GRID(state, nums, x, y);
1966
1967             draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1968
1969             str[0] = n ? n2c(n, state->order) : ' ';
1970             str[1] = '\0';
1971             draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1972                       FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1973                       ink, str);
1974
1975             if (state->adjacent)
1976                 draw_adjs(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
1977             else
1978                 draw_gts(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
1979         }
1980     }
1981 }
1982
1983 /* ----------------------------------------------------------------------
1984  * Housekeeping.
1985  */
1986
1987 #ifdef COMBINED
1988 #define thegame unequal
1989 #endif
1990
1991 const struct game thegame = {
1992     "Unequal", "games.unequal", "unequal",
1993     default_params,
1994     game_fetch_preset, NULL,
1995     decode_params,
1996     encode_params,
1997     free_params,
1998     dup_params,
1999     TRUE, game_configure, custom_params,
2000     validate_params,
2001     new_game_desc,
2002     validate_desc,
2003     new_game,
2004     dup_game,
2005     free_game,
2006     TRUE, solve_game,
2007     TRUE, game_can_format_as_text_now, game_text_format,
2008     new_ui,
2009     free_ui,
2010     encode_ui,
2011     decode_ui,
2012     game_changed_state,
2013     interpret_move,
2014     execute_move,
2015     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2016     game_colours,
2017     game_new_drawstate,
2018     game_free_drawstate,
2019     game_redraw,
2020     game_anim_length,
2021     game_flash_length,
2022     game_status,
2023     TRUE, FALSE, game_print_size, game_print,
2024     FALSE,                             /* wants_statusbar */
2025     FALSE, game_timing_state,
2026     REQUIRE_RBUTTON | REQUIRE_NUMPAD,  /* flags */
2027 };
2028
2029 /* ----------------------------------------------------------------------
2030  * Standalone solver.
2031  */
2032
2033 #ifdef STANDALONE_SOLVER
2034
2035 #include <time.h>
2036 #include <stdarg.h>
2037
2038 const char *quis = NULL;
2039
2040 #if 0 /* currently unused */
2041
2042 static void debug_printf(const char *fmt, ...)
2043 {
2044     char buf[4096];
2045     va_list ap;
2046
2047     va_start(ap, fmt);
2048     vsprintf(buf, fmt, ap);
2049     puts(buf);
2050     va_end(ap);
2051 }
2052
2053 static void game_printf(game_state *state)
2054 {
2055     char *dbg = game_text_format(state);
2056     printf("%s", dbg);
2057     sfree(dbg);
2058 }
2059
2060 static void game_printf_wide(game_state *state)
2061 {
2062     int x, y, i, n;
2063
2064     for (y = 0; y < state->order; y++) {
2065         for (x = 0; x < state->order; x++) {
2066             n = GRID(state, nums, x, y);
2067             for (i = 0; i < state->order; i++) {
2068                 if (n > 0)
2069                     printf("%c", n2c(n, state->order));
2070                 else if (HINT(state, x, y, i))
2071                     printf("%c", n2c(i+1, state->order));
2072                 else
2073                     printf(".");
2074             }
2075             printf(" ");
2076         }
2077         printf("\n");
2078     }
2079     printf("\n");
2080 }
2081
2082 #endif
2083
2084 static void pdiff(int diff)
2085 {
2086     if (diff == DIFF_IMPOSSIBLE)
2087         printf("Game is impossible.\n");
2088     else if (diff == DIFF_UNFINISHED)
2089         printf("Game has incomplete.\n");
2090     else if (diff == DIFF_AMBIGUOUS)
2091         printf("Game has multiple solutions.\n");
2092     else
2093         printf("Game has difficulty %s.\n", unequal_diffnames[diff]);
2094 }
2095
2096 static int solve(game_params *p, char *desc, int debug)
2097 {
2098     game_state *state = new_game(NULL, p, desc);
2099     struct solver_ctx *ctx = new_ctx(state);
2100     struct latin_solver solver;
2101     int diff;
2102
2103     solver_show_working = debug;
2104     game_debug(state);
2105
2106     latin_solver_alloc(&solver, state->nums, state->order);
2107
2108     diff = latin_solver_main(&solver, DIFF_RECURSIVE,
2109                              DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
2110                              DIFF_EXTREME, DIFF_RECURSIVE,
2111                              unequal_solvers, ctx, clone_ctx, free_ctx);
2112
2113     free_ctx(ctx);
2114
2115     latin_solver_free(&solver);
2116
2117     if (debug) pdiff(diff);
2118
2119     game_debug(state);
2120     free_game(state);
2121     return diff;
2122 }
2123
2124 static void check(game_params *p)
2125 {
2126     const char *msg = validate_params(p, 1);
2127     if (msg) {
2128         fprintf(stderr, "%s: %s", quis, msg);
2129         exit(1);
2130     }
2131 }
2132
2133 static int gen(game_params *p, random_state *rs, int debug)
2134 {
2135     char *desc, *aux;
2136     int diff;
2137
2138     check(p);
2139
2140     solver_show_working = debug;
2141     desc = new_game_desc(p, rs, &aux, 0);
2142     diff = solve(p, desc, debug);
2143     sfree(aux);
2144     sfree(desc);
2145
2146     return diff;
2147 }
2148
2149 static void soak(game_params *p, random_state *rs)
2150 {
2151     time_t tt_start, tt_now, tt_last;
2152     char *aux, *desc;
2153     game_state *st;
2154     int n = 0, neasy = 0, realdiff = p->diff;
2155
2156     check(p);
2157
2158     solver_show_working = 0;
2159     maxtries = 1;
2160
2161     tt_start = tt_now = time(NULL);
2162
2163     printf("Soak-generating an %s %dx%d grid, difficulty %s.\n",
2164            p->adjacent ? "adjacent" : "unequal",
2165            p->order, p->order, unequal_diffnames[p->diff]);
2166
2167     while (1) {
2168         p->diff = realdiff;
2169         desc = new_game_desc(p, rs, &aux, 0);
2170         st = new_game(NULL, p, desc);
2171         solver_state(st, DIFF_RECURSIVE);
2172         free_game(st);
2173         sfree(aux);
2174         sfree(desc);
2175
2176         n++;
2177         if (realdiff != p->diff) neasy++;
2178
2179         tt_last = time(NULL);
2180         if (tt_last > tt_now) {
2181             tt_now = tt_last;
2182             printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
2183                    n, (double)n / ((double)tt_now - tt_start),
2184                    neasy, (double)neasy*100.0/(double)n,
2185                    (double)(n - neasy) / ((double)tt_now - tt_start));
2186         }
2187     }
2188 }
2189
2190 static void usage_exit(const char *msg)
2191 {
2192     if (msg)
2193         fprintf(stderr, "%s: %s\n", quis, msg);
2194     fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
2195     exit(1);
2196 }
2197
2198 int main(int argc, const char *argv[])
2199 {
2200     random_state *rs;
2201     time_t seed = time(NULL);
2202     int do_soak = 0, diff;
2203
2204     game_params *p;
2205
2206     maxtries = 50;
2207
2208     quis = argv[0];
2209     while (--argc > 0) {
2210         const char *p = *++argv;
2211         if (!strcmp(p, "--soak"))
2212             do_soak = 1;
2213         else if (!strcmp(p, "--seed")) {
2214             if (argc == 0)
2215                 usage_exit("--seed needs an argument");
2216             seed = (time_t)atoi(*++argv);
2217             argc--;
2218         } else if (*p == '-')
2219             usage_exit("unrecognised option");
2220         else
2221             break;
2222     }
2223     rs = random_new((void*)&seed, sizeof(time_t));
2224
2225     if (do_soak == 1) {
2226         if (argc != 1) usage_exit("only one argument for --soak");
2227         p = default_params();
2228         decode_params(p, *argv);
2229         soak(p, rs);
2230     } else if (argc > 0) {
2231         int i;
2232         for (i = 0; i < argc; i++) {
2233             const char *id = *argv++;
2234             char *desc = strchr(id, ':');
2235             const char *err;
2236             p = default_params();
2237             if (desc) {
2238                 *desc++ = '\0';
2239                 decode_params(p, id);
2240                 err = validate_desc(p, desc);
2241                 if (err) {
2242                     fprintf(stderr, "%s: %s\n", quis, err);
2243                     exit(1);
2244                 }
2245                 solve(p, desc, 1);
2246             } else {
2247                 decode_params(p, id);
2248                 diff = gen(p, rs, 1);
2249             }
2250         }
2251     } else {
2252         while(1) {
2253             p = default_params();
2254             p->order = random_upto(rs, 7) + 3;
2255             p->diff = random_upto(rs, 4);
2256             diff = gen(p, rs, 0);
2257             pdiff(diff);
2258         }
2259     }
2260
2261     return 0;
2262 }
2263
2264 #endif
2265
2266 /* vim: set shiftwidth=4 tabstop=8: */