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