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