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