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(const 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(const 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(const 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(const 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(const 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(const 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(const game_params *params)
 450 {
 451     return TRUE;
 452 }
 453
 454 static char *game_text_format(const 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(const game_state *state, int *diff_r,
 833                                int mindiff, int maxdiff)
 834 {
 835     game_state *ret = dup_game(state);
 836     int diff, r = 0;
 837
 838     for (diff = mindiff; diff <= maxdiff; diff++) {
 839         r = solver_state(ret, diff);
 840         debug(("solver_state after %s %d", unequal_diffnames[diff], r));
 841         if (r != 0) goto done;
 842     }
 843
 844 done:
 845     if (diff_r) *diff_r = (r > 0) ? diff : -1;
 846     return ret;
 847 }
 848
 849 /* ----------------------------------------------------------
 850  * Game generation.
 851  */
 852
 853 static char *latin_desc(digit *sq, size_t order)
 854 {
 855     int o2 = order*order, i;
 856     char *soln = snewn(o2+2, char);
 857
 858     soln[0] = 'S';
 859     for (i = 0; i < o2; i++)
 860         soln[i+1] = n2c(sq[i], order);
 861     soln[o2+1] = '\0';
 862
 863     return soln;
 864 }
 865
 866 /* returns non-zero if it placed (or could have placed) clue. */
 867 static int gg_place_clue(game_state *state, int ccode, digit *latin, int checkonly)
 868 {
 869     int loc = ccode / 5, which = ccode % 5;
 870     int x = loc % state->order, y = loc / state->order;
 871
 872     assert(loc < state->order*state->order);
 873
 874     if (which == 4) {           /* add number */
 875         if (state->nums[loc] != 0) {
 876 #ifdef STANDALONE_SOLVER
 877             if (state->nums[loc] != latin[loc]) {
 878                 printf("inconsistency for (%d,%d): state %d latin %d\n",
 879                        x+1, y+1, state->nums[loc], latin[loc]);
 880             }
 881 #endif
 882             assert(state->nums[loc] == latin[loc]);
 883             return 0;
 884         }
 885         if (!checkonly) {
 886             state->nums[loc] = latin[loc];
 887         }
 888     } else {                    /* add flag */
 889         int lx, ly, lloc;
 890
 891         if (state->adjacent)
 892             return 0; /* never add flag clues in adjacent mode (they're always
 893                          all present) */
 894
 895         if (state->flags[loc] & adjthan[which].f)
 896             return 0; /* already has flag. */
 897
 898         lx = x + adjthan[which].dx;
 899         ly = y + adjthan[which].dy;
 900         if (lx < 0 || ly < 0 || lx >= state->order || ly >= state->order)
 901             return 0; /* flag compares to off grid */
 902
 903         lloc = loc + adjthan[which].dx + adjthan[which].dy*state->order;
 904         if (latin[loc] <= latin[lloc])
 905             return 0; /* flag would be incorrect */
 906
 907         if (!checkonly) {
 908             state->flags[loc] |= adjthan[which].f;
 909         }
 910     }
 911     return 1;
 912 }
 913
 914 /* returns non-zero if it removed (or could have removed) the clue. */
 915 static int gg_remove_clue(game_state *state, int ccode, int checkonly)
 916 {
 917     int loc = ccode / 5, which = ccode % 5;
 918 #ifdef STANDALONE_SOLVER
 919     int x = loc % state->order, y = loc / state->order;
 920 #endif
 921
 922     assert(loc < state->order*state->order);
 923
 924     if (which == 4) {           /* remove number. */
 925         if (state->nums[loc] == 0) return 0;
 926         if (!checkonly) {
 927 #ifdef STANDALONE_SOLVER
 928             if (solver_show_working)
 929                 printf("gg_remove_clue: removing %d at (%d,%d)",
 930                        state->nums[loc], x+1, y+1);
 931 #endif
 932             state->nums[loc] = 0;
 933         }
 934     } else {                    /* remove flag */
 935         if (state->adjacent)
 936             return 0; /* never remove clues in adjacent mode. */
 937
 938         if (!(state->flags[loc] & adjthan[which].f)) return 0;
 939         if (!checkonly) {
 940 #ifdef STANDALONE_SOLVER
 941             if (solver_show_working)
 942                printf("gg_remove_clue: removing %c at (%d,%d)",
 943                        adjthan[which].c, x+1, y+1);
 944 #endif
 945             state->flags[loc] &= ~adjthan[which].f;
 946         }
 947     }
 948     return 1;
 949 }
 950
 951 static int gg_best_clue(game_state *state, int *scratch, digit *latin)
 952 {
 953     int ls = state->order * state->order * 5;
 954     int maxposs = 0, minclues = 5, best = -1, i, j;
 955     int nposs, nclues, loc;
 956
 957 #ifdef STANDALONE_SOLVER
 958     if (solver_show_working) {
 959         game_debug(state);
 960         latin_solver_debug(state->hints, state->order);
 961     }
 962 #endif
 963
 964     for (i = ls; i-- > 0 ;) {
 965         if (!gg_place_clue(state, scratch[i], latin, 1)) continue;
 966
 967         loc = scratch[i] / 5;
 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                 int x = loc % state->order, y = loc / state->order;
 980                 printf("gg_best_clue: b%d (%d,%d) new best [%d poss, %d clues].\n",
 981                        best, x+1, y+1, nposs, nclues);
 982             }
 983 #endif
 984         }
 985     }
 986     /* if we didn't solve, we must have 1 clue to place! */
 987     assert(best != -1);
 988     return best;
 989 }
 990
 991 #ifdef STANDALONE_SOLVER
 992 int maxtries;
 993 #define MAXTRIES maxtries
 994 #else
 995 #define MAXTRIES 50
 996 #endif
 997 int gg_solved;
 998
 999 static int game_assemble(game_state *new, int *scratch, digit *latin,
1000                          int difficulty)
1001 {
1002     game_state *copy = dup_game(new);
1003     int best;
1004
1005     if (difficulty >= DIFF_RECURSIVE) {
1006         /* We mustn't use any solver that might guess answers;
1007          * if it guesses wrongly but solves, gg_place_clue will
1008          * get mighty confused. We will always trim clues down
1009          * (making it more difficult) in game_strip, which doesn't
1010          * have this problem. */
1011         difficulty = DIFF_RECURSIVE-1;
1012     }
1013
1014 #ifdef STANDALONE_SOLVER
1015     if (solver_show_working) {
1016         game_debug(new);
1017         latin_solver_debug(new->hints, new->order);
1018     }
1019 #endif
1020
1021     while(1) {
1022         gg_solved++;
1023         if (solver_state(copy, difficulty) == 1) break;
1024
1025         best = gg_best_clue(copy, scratch, latin);
1026         gg_place_clue(new, scratch[best], latin, 0);
1027         gg_place_clue(copy, scratch[best], latin, 0);
1028     }
1029     free_game(copy);
1030 #ifdef STANDALONE_SOLVER
1031     if (solver_show_working) {
1032         char *dbg = game_text_format(new);
1033         printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved, dbg);
1034         sfree(dbg);
1035     }
1036 #endif
1037     return 0;
1038 }
1039
1040 static void game_strip(game_state *new, int *scratch, digit *latin,
1041                        int difficulty)
1042 {
1043     int o = new->order, o2 = o*o, lscratch = o2*5, i;
1044     game_state *copy = blank_game(new->order, new->adjacent);
1045
1046     /* For each symbol (if it exists in new), try and remove it and
1047      * solve again; if we couldn't solve without it put it back. */
1048     for (i = 0; i < lscratch; i++) {
1049         if (!gg_remove_clue(new, scratch[i], 0)) continue;
1050
1051         memcpy(copy->nums,  new->nums,  o2 * sizeof(digit));
1052         memcpy(copy->flags, new->flags, o2 * sizeof(unsigned int));
1053         gg_solved++;
1054         if (solver_state(copy, difficulty) != 1) {
1055             /* put clue back, we can't solve without it. */
1056             int ret = gg_place_clue(new, scratch[i], latin, 0);
1057             assert(ret == 1);
1058         } else {
1059 #ifdef STANDALONE_SOLVER
1060             if (solver_show_working)
1061                 printf("game_strip: clue was redundant.");
1062 #endif
1063         }
1064     }
1065     free_game(copy);
1066 #ifdef STANDALONE_SOLVER
1067     if (solver_show_working) {
1068         char *dbg = game_text_format(new);
1069         debug(("game_strip: done, %d solver iterations.", gg_solved));
1070         debug(("%s", dbg));
1071         sfree(dbg);
1072     }
1073 #endif
1074 }
1075
1076 static void add_adjacent_flags(game_state *state, digit *latin)
1077 {
1078     int x, y, o = state->order;
1079
1080     /* All clues in adjacent mode are always present (the only variables are
1081      * the numbers). This adds all the flags to state based on the supplied
1082      * latin square. */
1083
1084     for (y = 0; y < o; y++) {
1085         for (x = 0; x < o; x++) {
1086             if (x < (o-1) && (abs(latin[y*o+x] - latin[y*o+x+1]) == 1)) {
1087                 GRID(state, flags, x, y) |= F_ADJ_RIGHT;
1088                 GRID(state, flags, x+1, y) |= F_ADJ_LEFT;
1089             }
1090             if (y < (o-1) && (abs(latin[y*o+x] - latin[(y+1)*o+x]) == 1)) {
1091                 GRID(state, flags, x, y) |= F_ADJ_DOWN;
1092                 GRID(state, flags, x, y+1) |= F_ADJ_UP;
1093             }
1094         }
1095     }
1096 }
1097
1098 static char *new_game_desc(const game_params *params_in, random_state *rs,
1099                            char **aux, int interactive)
1100 {
1101     game_params params_copy = *params_in; /* structure copy */
1102     game_params *params = &params_copy;
1103     digit *sq = NULL;
1104     int i, x, y, retlen, k, nsol;
1105     int o2 = params->order * params->order, ntries = 1;
1106     int *scratch, lscratch = o2*5;
1107     char *ret, buf[80];
1108     game_state *state = blank_game(params->order, params->adjacent);
1109
1110     /* Generate a list of 'things to strip' (randomised later) */
1111     scratch = snewn(lscratch, int);
1112     /* Put the numbers (4 mod 5) before the inequalities (0-3 mod 5) */
1113     for (i = 0; i < lscratch; i++) scratch[i] = (i%o2)*5 + 4 - (i/o2);
1114
1115 generate:
1116 #ifdef STANDALONE_SOLVER
1117     if (solver_show_working)
1118         printf("new_game_desc: generating %s puzzle, ntries so far %d\n",
1119                unequal_diffnames[params->diff], ntries);
1120 #endif
1121     if (sq) sfree(sq);
1122     sq = latin_generate(params->order, rs);
1123     latin_debug(sq, params->order);
1124     /* Separately shuffle the numeric and inequality clues */
1125     shuffle(scratch, lscratch/5, sizeof(int), rs);
1126     shuffle(scratch+lscratch/5, 4*lscratch/5, sizeof(int), rs);
1127
1128     memset(state->nums, 0, o2 * sizeof(digit));
1129     memset(state->flags, 0, o2 * sizeof(unsigned int));
1130
1131     if (state->adjacent) {
1132         /* All adjacency flags are always present. */
1133         add_adjacent_flags(state, sq);
1134     }
1135
1136     gg_solved = 0;
1137     if (game_assemble(state, scratch, sq, params->diff) < 0)
1138         goto generate;
1139     game_strip(state, scratch, sq, params->diff);
1140
1141     if (params->diff > 0) {
1142         game_state *copy = dup_game(state);
1143         nsol = solver_state(copy, params->diff-1);
1144         free_game(copy);
1145         if (nsol > 0) {
1146 #ifdef STANDALONE_SOLVER
1147             if (solver_show_working)
1148                 printf("game_assemble: puzzle as generated is too easy.\n");
1149 #endif
1150             if (ntries < MAXTRIES) {
1151                 ntries++;
1152                 goto generate;
1153             }
1154 #ifdef STANDALONE_SOLVER
1155             if (solver_show_working)
1156                 printf("Unable to generate %s %dx%d after %d attempts.\n",
1157                        unequal_diffnames[params->diff],
1158                        params->order, params->order, MAXTRIES);
1159 #endif
1160             params->diff--;
1161         }
1162     }
1163 #ifdef STANDALONE_SOLVER
1164     if (solver_show_working)
1165         printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).\n",
1166                unequal_diffnames[params->diff], ntries, gg_solved);
1167 #endif
1168
1169     ret = NULL; retlen = 0;
1170     for (y = 0; y < params->order; y++) {
1171         for (x = 0; x < params->order; x++) {
1172             unsigned int f = GRID(state, flags, x, y);
1173             k = sprintf(buf, "%d%s%s%s%s,",
1174                         GRID(state, nums, x, y),
1175                         (f & F_ADJ_UP)    ? "U" : "",
1176                         (f & F_ADJ_RIGHT) ? "R" : "",
1177                         (f & F_ADJ_DOWN)  ? "D" : "",
1178                         (f & F_ADJ_LEFT)  ? "L" : "");
1179
1180             ret = sresize(ret, retlen + k + 1, char);
1181             strcpy(ret + retlen, buf);
1182             retlen += k;
1183         }
1184     }
1185     *aux = latin_desc(sq, params->order);
1186
1187     free_game(state);
1188     sfree(sq);
1189     sfree(scratch);
1190
1191     return ret;
1192 }
1193
1194 static game_state *load_game(const game_params *params, const char *desc,
1195                              char **why_r)
1196 {
1197     game_state *state = blank_game(params->order, params->adjacent);
1198     const char *p = desc;
1199     int i = 0, n, o = params->order, x, y;
1200     char *why = NULL;
1201
1202     while (*p) {
1203         while (*p >= 'a' && *p <= 'z') {
1204             i += *p - 'a' + 1;
1205             p++;
1206         }
1207         if (i >= o*o) {
1208             why = "Too much data to fill grid"; goto fail;
1209         }
1210
1211         if (*p < '0' && *p > '9') {
1212             why = "Expecting number in game description"; goto fail;
1213         }
1214         n = atoi(p);
1215         if (n < 0 || n > o) {
1216             why = "Out-of-range number in game description"; goto fail;
1217         }
1218         state->nums[i] = (digit)n;
1219         while (*p >= '0' && *p <= '9') p++; /* skip number */
1220
1221         if (state->nums[i] != 0)
1222             state->flags[i] |= F_IMMUTABLE; /* === number set by game description */
1223
1224         while (*p == 'U' || *p == 'R' || *p == 'D' || *p == 'L') {
1225             switch (*p) {
1226             case 'U': state->flags[i] |= F_ADJ_UP;    break;
1227             case 'R': state->flags[i] |= F_ADJ_RIGHT; break;
1228             case 'D': state->flags[i] |= F_ADJ_DOWN;  break;
1229             case 'L': state->flags[i] |= F_ADJ_LEFT;  break;
1230             default: why = "Expecting flag URDL in game description"; goto fail;
1231             }
1232             p++;
1233         }
1234         i++;
1235         if (i < o*o && *p != ',') {
1236             why = "Missing separator"; goto fail;
1237         }
1238         if (*p == ',') p++;
1239     }
1240     if (i < o*o) {
1241         why = "Not enough data to fill grid"; goto fail;
1242     }
1243     i = 0;
1244     for (y = 0; y < o; y++) {
1245         for (x = 0; x < o; x++) {
1246             for (n = 0; n < 4; n++) {
1247                 if (GRID(state, flags, x, y) & adjthan[n].f) {
1248                     int nx = x + adjthan[n].dx;
1249                     int ny = y + adjthan[n].dy;
1250                     /* a flag must not point us off the grid. */
1251                     if (nx < 0 || ny < 0 || nx >= o || ny >= o) {
1252                         why = "Flags go off grid"; goto fail;
1253                     }
1254                     if (params->adjacent) {
1255                         /* if one cell is adjacent to another, the other must
1256                          * also be adjacent to the first. */
1257                         if (!(GRID(state, flags, nx, ny) & adjthan[n].fo)) {
1258                             why = "Flags contradicting each other"; goto fail;
1259                         }
1260                     } else {
1261                         /* if one cell is GT another, the other must _not_ also
1262                          * be GT the first. */
1263                         if (GRID(state, flags, nx, ny) & adjthan[n].fo) {
1264                             why = "Flags contradicting each other"; goto fail;
1265                         }
1266                     }
1267                 }
1268             }
1269         }
1270     }
1271
1272     return state;
1273
1274 fail:
1275     free_game(state);
1276     if (why_r) *why_r = why;
1277     return NULL;
1278 }
1279
1280 static game_state *new_game(midend *me, const game_params *params,
1281                             const char *desc)
1282 {
1283     game_state *state = load_game(params, desc, NULL);
1284     if (!state) {
1285         assert("Unable to load ?validated game.");
1286         return NULL;
1287     }
1288     return state;
1289 }
1290
1291 static char *validate_desc(const game_params *params, const char *desc)
1292 {
1293     char *why = NULL;
1294     game_state *dummy = load_game(params, desc, &why);
1295     if (dummy) {
1296         free_game(dummy);
1297         assert(!why);
1298     } else
1299         assert(why);
1300     return why;
1301 }
1302
1303 static char *solve_game(const game_state *state, const game_state *currstate,
1304                         const char *aux, char **error)
1305 {
1306     game_state *solved;
1307     int r;
1308     char *ret = NULL;
1309
1310     if (aux) return dupstr(aux);
1311
1312     solved = dup_game(state);
1313     for (r = 0; r < state->order*state->order; r++) {
1314         if (!(solved->flags[r] & F_IMMUTABLE))
1315             solved->nums[r] = 0;
1316     }
1317     r = solver_state(solved, DIFFCOUNT-1);   /* always use full solver */
1318     if (r > 0) ret = latin_desc(solved->nums, solved->order);
1319     free_game(solved);
1320     return ret;
1321 }
1322
1323 /* ----------------------------------------------------------
1324  * Game UI input processing.
1325  */
1326
1327 struct game_ui {
1328     int hx, hy;                         /* as for solo.c, highlight pos */
1329     int hshow, hpencil, hcursor;        /* show state, type, and ?cursor. */
1330 };
1331
1332 static game_ui *new_ui(const game_state *state)
1333 {
1334     game_ui *ui = snew(game_ui);
1335
1336     ui->hx = ui->hy = 0;
1337     ui->hpencil = ui->hshow = ui->hcursor = 0;
1338
1339     return ui;
1340 }
1341
1342 static void free_ui(game_ui *ui)
1343 {
1344     sfree(ui);
1345 }
1346
1347 static char *encode_ui(const game_ui *ui)
1348 {
1349     return NULL;
1350 }
1351
1352 static void decode_ui(game_ui *ui, const char *encoding)
1353 {
1354 }
1355
1356 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1357                                const game_state *newstate)
1358 {
1359     /* See solo.c; if we were pencil-mode highlighting and
1360      * somehow a square has just been properly filled, cancel
1361      * pencil mode. */
1362     if (ui->hshow && ui->hpencil && !ui->hcursor &&
1363         GRID(newstate, nums, ui->hx, ui->hy) != 0) {
1364         ui->hshow = 0;
1365     }
1366 }
1367
1368 struct game_drawstate {
1369     int tilesize, order, started, adjacent;
1370     digit *nums;                /* copy of nums, o^2 */
1371     unsigned char *hints;       /* copy of hints, o^3 */
1372     unsigned int *flags;        /* o^2 */
1373
1374     int hx, hy, hshow, hpencil; /* as for game_ui. */
1375     int hflash;
1376 };
1377
1378 static char *interpret_move(const game_state *state, game_ui *ui,
1379                             const game_drawstate *ds,
1380                             int ox, int oy, int button)
1381 {
1382     int x = FROMCOORD(ox), y = FROMCOORD(oy), n;
1383     char buf[80];
1384
1385     button &= ~MOD_MASK;
1386
1387     if (x >= 0 && x < ds->order && ((ox - COORD(x)) <= TILE_SIZE) &&
1388         y >= 0 && y < ds->order && ((oy - COORD(y)) <= TILE_SIZE)) {
1389         if (button == LEFT_BUTTON) {
1390             /* normal highlighting for non-immutable squares */
1391             if (GRID(state, flags, x, y) & F_IMMUTABLE)
1392                 ui->hshow = 0;
1393             else if (x == ui->hx && y == ui->hy &&
1394                      ui->hshow && ui->hpencil == 0)
1395                 ui->hshow = 0;
1396             else {
1397                 ui->hx = x; ui->hy = y; ui->hpencil = 0;
1398                 ui->hshow = 1;
1399             }
1400             ui->hcursor = 0;
1401             return "";
1402         }
1403         if (button == RIGHT_BUTTON) {
1404             /* pencil highlighting for non-filled squares */
1405             if (GRID(state, nums, x, y) != 0)
1406                 ui->hshow = 0;
1407             else if (x == ui->hx && y == ui->hy &&
1408                      ui->hshow && ui->hpencil)
1409                 ui->hshow = 0;
1410             else {
1411                 ui->hx = x; ui->hy = y; ui->hpencil = 1;
1412                 ui->hshow = 1;
1413             }
1414             ui->hcursor = 0;
1415             return "";
1416         }
1417     }
1418
1419     if (IS_CURSOR_MOVE(button)) {
1420         move_cursor(button, &ui->hx, &ui->hy, ds->order, ds->order, 0);
1421         ui->hshow = ui->hcursor = 1;
1422         return "";
1423     }
1424     if (ui->hshow && IS_CURSOR_SELECT(button)) {
1425         ui->hpencil = 1 - ui->hpencil;
1426         ui->hcursor = 1;
1427         return "";
1428     }
1429
1430     n = c2n(button, state->order);
1431     if (ui->hshow && n >= 0 && n <= ds->order) {
1432         debug(("button %d, cbutton %d", button, (int)((char)button)));
1433
1434         debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1435                n, ui->hx, ui->hy, ui->hpencil,
1436                GRID(state, flags, ui->hx, ui->hy),
1437                GRID(state, nums, ui->hx, ui->hy)));
1438
1439         if (GRID(state, flags, ui->hx, ui->hy) & F_IMMUTABLE)
1440             return NULL;        /* can't edit immutable square (!) */
1441         if (ui->hpencil && GRID(state, nums, ui->hx, ui->hy) > 0)
1442             return NULL;        /* can't change hints on filled square (!) */
1443
1444
1445         sprintf(buf, "%c%d,%d,%d",
1446                 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1447
1448         if (!ui->hcursor) ui->hshow = 0;
1449
1450         return dupstr(buf);
1451     }
1452
1453     if (button == 'H' || button == 'h')
1454         return dupstr("H");
1455     if (button == 'M' || button == 'm')
1456         return dupstr("M");
1457
1458     return NULL;
1459 }
1460
1461 static game_state *execute_move(const game_state *state, const char *move)
1462 {
1463     game_state *ret = NULL;
1464     int x, y, n, i, rc;
1465
1466     debug(("execute_move: %s", move));
1467
1468     if ((move[0] == 'P' || move[0] == 'R') &&
1469         sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1470         x >= 0 && x < state->order && y >= 0 && y < state->order &&
1471         n >= 0 && n <= state->order) {
1472         ret = dup_game(state);
1473         if (move[0] == 'P' && n > 0)
1474             HINT(ret, x, y, n-1) = !HINT(ret, x, y, n-1);
1475         else {
1476             GRID(ret, nums, x, y) = n;
1477             for (i = 0; i < state->order; i++)
1478                 HINT(ret, x, y, i) = 0;
1479
1480             /* real change to grid; check for completion */
1481             if (!ret->completed && check_complete(ret->nums, ret, 1) > 0)
1482                 ret->completed = TRUE;
1483         }
1484         return ret;
1485     } else if (move[0] == 'S') {
1486         const char *p;
1487
1488         ret = dup_game(state);
1489         ret->completed = ret->cheated = TRUE;
1490
1491         p = move+1;
1492         for (i = 0; i < state->order*state->order; i++) {
1493             n = c2n((int)*p, state->order);
1494             if (!*p || n <= 0 || n > state->order)
1495                 goto badmove;
1496             ret->nums[i] = n;
1497             p++;
1498         }
1499         if (*p) goto badmove;
1500         rc = check_complete(ret->nums, ret, 1);
1501         assert(rc > 0);
1502         return ret;
1503     } else if (move[0] == 'M') {
1504         ret = dup_game(state);
1505         for (x = 0; x < state->order; x++) {
1506             for (y = 0; y < state->order; y++) {
1507                 for (n = 0; n < state->order; n++) {
1508                     HINT(ret, x, y, n) = 1;
1509                 }
1510             }
1511         }
1512         return ret;
1513     } else if (move[0] == 'H') {
1514         return solver_hint(state, NULL, DIFF_EASY, DIFF_EASY);
1515     }
1516
1517 badmove:
1518     if (ret) free_game(ret);
1519     return NULL;
1520 }
1521
1522 /* ----------------------------------------------------------------------
1523  * Drawing/printing routines.
1524  */
1525
1526 #define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2)
1527
1528 static void game_compute_size(const game_params *params, int tilesize,
1529                               int *x, int *y)
1530 {
1531     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1532     struct { int tilesize, order; } ads, *ds = &ads;
1533     ads.tilesize = tilesize;
1534     ads.order = params->order;
1535
1536     *x = *y = DRAW_SIZE;
1537 }
1538
1539 static void game_set_size(drawing *dr, game_drawstate *ds,
1540                           const game_params *params, int tilesize)
1541 {
1542     ds->tilesize = tilesize;
1543 }
1544
1545 static float *game_colours(frontend *fe, int *ncolours)
1546 {
1547     float *ret = snewn(3 * NCOLOURS, float);
1548     int i;
1549
1550     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1551
1552     for (i = 0; i < 3; i++) {
1553         ret[COL_TEXT * 3 + i] = 0.0F;
1554         ret[COL_GRID * 3 + i] = 0.5F;
1555     }
1556
1557     /* Lots of these were taken from solo.c. */
1558     ret[COL_GUESS * 3 + 0] = 0.0F;
1559     ret[COL_GUESS * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1560     ret[COL_GUESS * 3 + 2] = 0.0F;
1561
1562     ret[COL_ERROR * 3 + 0] = 1.0F;
1563     ret[COL_ERROR * 3 + 1] = 0.0F;
1564     ret[COL_ERROR * 3 + 2] = 0.0F;
1565
1566     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1567     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1568     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1569
1570     *ncolours = NCOLOURS;
1571     return ret;
1572 }
1573
1574 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1575 {
1576     struct game_drawstate *ds = snew(struct game_drawstate);
1577     int o2 = state->order*state->order, o3 = o2*state->order;
1578
1579     ds->tilesize = 0;
1580     ds->order = state->order;
1581     ds->adjacent = state->adjacent;
1582
1583     ds->nums = snewn(o2, digit);
1584     ds->hints = snewn(o3, unsigned char);
1585     ds->flags = snewn(o2, unsigned int);
1586     memset(ds->nums, 0, o2*sizeof(digit));
1587     memset(ds->hints, 0, o3);
1588     memset(ds->flags, 0, o2*sizeof(unsigned int));
1589
1590     ds->hx = ds->hy = 0;
1591     ds->started = ds->hshow = ds->hpencil = ds->hflash = 0;
1592
1593     return ds;
1594 }
1595
1596 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1597 {
1598     sfree(ds->nums);
1599     sfree(ds->hints);
1600     sfree(ds->flags);
1601     sfree(ds);
1602 }
1603
1604 static void draw_gt(drawing *dr, int ox, int oy,
1605                     int dx1, int dy1, int dx2, int dy2, int col)
1606 {
1607     int coords[12];
1608     int xdx = (dx1+dx2 ? 0 : 1), xdy = (dx1+dx2 ? 1 : 0);
1609     coords[0] = ox + xdx;
1610     coords[1] = oy + xdy;
1611     coords[2] = ox + xdx + dx1;
1612     coords[3] = oy + xdy + dy1;
1613     coords[4] = ox + xdx + dx1 + dx2;
1614     coords[5] = oy + xdy + dy1 + dy2;
1615     coords[6] = ox - xdx + dx1 + dx2;
1616     coords[7] = oy - xdy + dy1 + dy2;
1617     coords[8] = ox - xdx + dx1;
1618     coords[9] = oy - xdy + dy1;
1619     coords[10] = ox - xdx;
1620     coords[11] = oy - xdy;
1621     draw_polygon(dr, coords, 6, col, col);
1622 }
1623
1624 static void draw_gts(drawing *dr, game_drawstate *ds, int ox, int oy,
1625                      unsigned int f, int bg, int fg)
1626 {
1627     int g = GAP_SIZE, g2 = (g+1)/2, g4 = (g+1)/4;
1628
1629     /* Draw all the greater-than signs emanating from this tile. */
1630
1631     if (f & F_ADJ_UP) {
1632         if (bg >= 0) draw_rect(dr, ox, oy - g, TILE_SIZE, g, bg);
1633         draw_gt(dr, ox+g2, oy-g4, g2, -g2, g2, g2,
1634                (f & F_ERROR_UP) ? COL_ERROR : fg);
1635         draw_update(dr, ox, oy-g, TILE_SIZE, g);
1636     }
1637     if (f & F_ADJ_RIGHT) {
1638         if (bg >= 0) draw_rect(dr, ox + TILE_SIZE, oy, g, TILE_SIZE, bg);
1639         draw_gt(dr, ox+TILE_SIZE+g4, oy+g2, g2, g2, -g2, g2,
1640                 (f & F_ERROR_RIGHT) ? COL_ERROR : fg);
1641         draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1642     }
1643     if (f & F_ADJ_DOWN) {
1644         if (bg >= 0) draw_rect(dr, ox, oy + TILE_SIZE, TILE_SIZE, g, bg);
1645         draw_gt(dr, ox+g2, oy+TILE_SIZE+g4, g2, g2, g2, -g2,
1646                (f & F_ERROR_DOWN) ? COL_ERROR : fg);
1647         draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1648     }
1649     if (f & F_ADJ_LEFT) {
1650         if (bg >= 0) draw_rect(dr, ox - g, oy, g, TILE_SIZE, bg);
1651         draw_gt(dr, ox-g4, oy+g2, -g2, g2, g2, g2,
1652                 (f & F_ERROR_LEFT) ? COL_ERROR : fg);
1653         draw_update(dr, ox-g, oy, g, TILE_SIZE);
1654     }
1655 }
1656
1657 static void draw_adjs(drawing *dr, game_drawstate *ds, int ox, int oy,
1658                       unsigned int f, int bg, int fg)
1659 {
1660     int g = GAP_SIZE, g38 = 3*(g+1)/8, g4 = (g+1)/4;
1661
1662     /* Draw all the adjacency bars relevant to this tile; we only have
1663      * to worry about F_ADJ_RIGHT and F_ADJ_DOWN.
1664      *
1665      * If we _only_ have the error flag set (i.e. it's not supposed to be
1666      * adjacent, but adjacent numbers were entered) draw an outline red bar.
1667      */
1668
1669     if (f & (F_ADJ_RIGHT|F_ERROR_RIGHT)) {
1670         if (f & F_ADJ_RIGHT) {
1671             draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE,
1672                       (f & F_ERROR_RIGHT) ? COL_ERROR : fg);
1673         } else {
1674             draw_rect_outline(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COL_ERROR);
1675         }
1676     } else if (bg >= 0) {
1677         draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, bg);
1678     }
1679     draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1680
1681     if (f & (F_ADJ_DOWN|F_ERROR_DOWN)) {
1682         if (f & F_ADJ_DOWN) {
1683             draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4,
1684                       (f & F_ERROR_DOWN) ? COL_ERROR : fg);
1685         } else {
1686             draw_rect_outline(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COL_ERROR);
1687         }
1688     } else if (bg >= 0) {
1689         draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, bg);
1690     }
1691     draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1692 }
1693
1694 static void draw_furniture(drawing *dr, game_drawstate *ds,
1695                            const game_state *state, const game_ui *ui,
1696                            int x, int y, int hflash)
1697 {
1698     int ox = COORD(x), oy = COORD(y), bg, hon;
1699     unsigned int f = GRID(state, flags, x, y);
1700
1701     bg = hflash ? COL_HIGHLIGHT : COL_BACKGROUND;
1702
1703     hon = (ui->hshow && x == ui->hx && y == ui->hy);
1704
1705     /* Clear square. */
1706     draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
1707               (hon && !ui->hpencil) ? COL_HIGHLIGHT : bg);
1708
1709     /* Draw the highlight (pencil or full), if we're the highlight */
1710     if (hon && ui->hpencil) {
1711         int coords[6];
1712         coords[0] = ox;
1713         coords[1] = oy;
1714         coords[2] = ox + TILE_SIZE/2;
1715         coords[3] = oy;
1716         coords[4] = ox;
1717         coords[5] = oy + TILE_SIZE/2;
1718         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1719     }
1720
1721     /* Draw the square outline (which is the cursor, if we're the cursor). */
1722     draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
1723
1724     draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
1725
1726     /* Draw the adjacent clue signs. */
1727     if (ds->adjacent)
1728         draw_adjs(dr, ds, ox, oy, f, COL_BACKGROUND, COL_GRID);
1729     else
1730         draw_gts(dr, ds, ox, oy, f, COL_BACKGROUND, COL_TEXT);
1731 }
1732
1733 static void draw_num(drawing *dr, game_drawstate *ds, int x, int y)
1734 {
1735     int ox = COORD(x), oy = COORD(y);
1736     unsigned int f = GRID(ds,flags,x,y);
1737     char str[2];
1738
1739     /* (can assume square has just been cleared) */
1740
1741     /* Draw number, choosing appropriate colour */
1742     str[0] = n2c(GRID(ds, nums, x, y), ds->order);
1743     str[1] = '\0';
1744     draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1745               FONT_VARIABLE, 3*TILE_SIZE/4, ALIGN_VCENTRE | ALIGN_HCENTRE,
1746               (f & F_IMMUTABLE) ? COL_TEXT : (f & F_ERROR) ? COL_ERROR : COL_GUESS, str);
1747 }
1748
1749 static void draw_hints(drawing *dr, game_drawstate *ds, int x, int y)
1750 {
1751     int ox = COORD(x), oy = COORD(y);
1752     int nhints, i, j, hw, hh, hmax, fontsz;
1753     char str[2];
1754
1755     /* (can assume square has just been cleared) */
1756
1757     /* Draw hints; steal ingenious algorithm (basically)
1758      * from solo.c:draw_number() */
1759     for (i = nhints = 0; i < ds->order; i++) {
1760         if (HINT(ds, x, y, i)) nhints++;
1761     }
1762
1763     for (hw = 1; hw * hw < nhints; hw++);
1764     if (hw < 3) hw = 3;
1765     hh = (nhints + hw - 1) / hw;
1766     if (hh < 2) hh = 2;
1767     hmax = max(hw, hh);
1768     fontsz = TILE_SIZE/(hmax*(11-hmax)/8);
1769
1770     for (i = j = 0; i < ds->order; i++) {
1771         if (HINT(ds,x,y,i)) {
1772             int hx = j % hw, hy = j / hw;
1773
1774             str[0] = n2c(i+1, ds->order);
1775             str[1] = '\0';
1776             draw_text(dr,
1777                       ox + (4*hx+3) * TILE_SIZE / (4*hw+2),
1778                       oy + (4*hy+3) * TILE_SIZE / (4*hh+2),
1779                       FONT_VARIABLE, fontsz,
1780                       ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1781             j++;
1782         }
1783     }
1784 }
1785
1786 static void game_redraw(drawing *dr, game_drawstate *ds,
1787                         const game_state *oldstate, const game_state *state,
1788                         int dir, const game_ui *ui,
1789                         float animtime, float flashtime)
1790 {
1791     int x, y, i, hchanged = 0, stale, hflash = 0;
1792
1793     debug(("highlight old (%d,%d), new (%d,%d)", ds->hx, ds->hy, ui->hx, ui->hy));
1794
1795     if (flashtime > 0 &&
1796         (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3))
1797          hflash = 1;
1798
1799     if (!ds->started) {
1800         draw_rect(dr, 0, 0, DRAW_SIZE, DRAW_SIZE, COL_BACKGROUND);
1801         draw_update(dr, 0, 0, DRAW_SIZE, DRAW_SIZE);
1802     }
1803     if (ds->hx != ui->hx || ds->hy != ui->hy ||
1804         ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
1805         hchanged = 1;
1806
1807     for (x = 0; x < ds->order; x++) {
1808         for (y = 0; y < ds->order; y++) {
1809             if (!ds->started)
1810                 stale = 1;
1811             else if (hflash != ds->hflash)
1812                 stale = 1;
1813             else
1814                 stale = 0;
1815
1816             if (hchanged) {
1817                 if ((x == ui->hx && y == ui->hy) ||
1818                     (x == ds->hx && y == ds->hy))
1819                     stale = 1;
1820             }
1821
1822             if (GRID(state, nums, x, y) != GRID(ds, nums, x, y)) {
1823                 GRID(ds, nums, x, y) = GRID(state, nums, x, y);
1824                 stale = 1;
1825             }
1826             if (GRID(state, flags, x, y) != GRID(ds, flags, x, y)) {
1827                 GRID(ds, flags, x, y) = GRID(state, flags, x, y);
1828                 stale = 1;
1829             }
1830             if (GRID(ds, nums, x, y) == 0) {
1831                 /* We're not a number square (therefore we might
1832                  * display hints); do we need to update? */
1833                 for (i = 0; i < ds->order; i++) {
1834                     if (HINT(state, x, y, i) != HINT(ds, x, y, i)) {
1835                         HINT(ds, x, y, i) = HINT(state, x, y, i);
1836                         stale = 1;
1837                     }
1838                 }
1839             }
1840             if (stale) {
1841                 draw_furniture(dr, ds, state, ui, x, y, hflash);
1842                 if (GRID(ds, nums, x, y) > 0)
1843                     draw_num(dr, ds, x, y);
1844                 else
1845                     draw_hints(dr, ds, x, y);
1846             }
1847         }
1848     }
1849     ds->hx = ui->hx; ds->hy = ui->hy;
1850     ds->hshow = ui->hshow;
1851     ds->hpencil = ui->hpencil;
1852
1853     ds->started = 1;
1854     ds->hflash = hflash;
1855 }
1856
1857 static float game_anim_length(const game_state *oldstate,
1858                               const game_state *newstate, int dir, game_ui *ui)
1859 {
1860     return 0.0F;
1861 }
1862
1863 static float game_flash_length(const game_state *oldstate,
1864                                const game_state *newstate, int dir, game_ui *ui)
1865 {
1866     if (!oldstate->completed && newstate->completed &&
1867         !oldstate->cheated && !newstate->cheated)
1868         return FLASH_TIME;
1869     return 0.0F;
1870 }
1871
1872 static int game_status(const game_state *state)
1873 {
1874     return state->completed ? +1 : 0;
1875 }
1876
1877 static int game_timing_state(const game_state *state, game_ui *ui)
1878 {
1879     return TRUE;
1880 }
1881
1882 static void game_print_size(const game_params *params, float *x, float *y)
1883 {
1884     int pw, ph;
1885
1886     /* 10mm squares by default, roughly the same as Grauniad. */
1887     game_compute_size(params, 1000, &pw, &ph);
1888     *x = pw / 100.0F;
1889     *y = ph / 100.0F;
1890 }
1891
1892 static void game_print(drawing *dr, const game_state *state, int tilesize)
1893 {
1894     int ink = print_mono_colour(dr, 0);
1895     int x, y, o = state->order, ox, oy, n;
1896     char str[2];
1897
1898     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1899     game_drawstate ads, *ds = &ads;
1900     game_set_size(dr, ds, NULL, tilesize);
1901
1902     print_line_width(dr, 2 * TILE_SIZE / 40);
1903
1904     /* Squares, numbers, gt signs */
1905     for (y = 0; y < o; y++) {
1906         for (x = 0; x < o; x++) {
1907             ox = COORD(x); oy = COORD(y);
1908             n = GRID(state, nums, x, y);
1909
1910             draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1911
1912             str[0] = n ? n2c(n, state->order) : ' ';
1913             str[1] = '\0';
1914             draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1915                       FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1916                       ink, str);
1917
1918             if (state->adjacent)
1919                 draw_adjs(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
1920             else
1921                 draw_gts(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
1922         }
1923     }
1924 }
1925
1926 /* ----------------------------------------------------------------------
1927  * Housekeeping.
1928  */
1929
1930 #ifdef COMBINED
1931 #define thegame unequal
1932 #endif
1933
1934 const struct game thegame = {
1935     "Unequal", "games.unequal", "unequal",
1936     default_params,
1937     game_fetch_preset,
1938     decode_params,
1939     encode_params,
1940     free_params,
1941     dup_params,
1942     TRUE, game_configure, custom_params,
1943     validate_params,
1944     new_game_desc,
1945     validate_desc,
1946     new_game,
1947     dup_game,
1948     free_game,
1949     TRUE, solve_game,
1950     TRUE, game_can_format_as_text_now, game_text_format,
1951     new_ui,
1952     free_ui,
1953     encode_ui,
1954     decode_ui,
1955     game_changed_state,
1956     interpret_move,
1957     execute_move,
1958     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1959     game_colours,
1960     game_new_drawstate,
1961     game_free_drawstate,
1962     game_redraw,
1963     game_anim_length,
1964     game_flash_length,
1965     game_status,
1966     TRUE, FALSE, game_print_size, game_print,
1967     FALSE,                             /* wants_statusbar */
1968     FALSE, game_timing_state,
1969     REQUIRE_RBUTTON | REQUIRE_NUMPAD,  /* flags */
1970 };
1971
1972 /* ----------------------------------------------------------------------
1973  * Standalone solver.
1974  */
1975
1976 #ifdef STANDALONE_SOLVER
1977
1978 #include <time.h>
1979 #include <stdarg.h>
1980
1981 const char *quis = NULL;
1982
1983 #if 0 /* currently unused */
1984
1985 static void debug_printf(char *fmt, ...)
1986 {
1987     char buf[4096];
1988     va_list ap;
1989
1990     va_start(ap, fmt);
1991     vsprintf(buf, fmt, ap);
1992     puts(buf);
1993     va_end(ap);
1994 }
1995
1996 static void game_printf(game_state *state)
1997 {
1998     char *dbg = game_text_format(state);
1999     printf("%s", dbg);
2000     sfree(dbg);
2001 }
2002
2003 static void game_printf_wide(game_state *state)
2004 {
2005     int x, y, i, n;
2006
2007     for (y = 0; y < state->order; y++) {
2008         for (x = 0; x < state->order; x++) {
2009             n = GRID(state, nums, x, y);
2010             for (i = 0; i < state->order; i++) {
2011                 if (n > 0)
2012                     printf("%c", n2c(n, state->order));
2013                 else if (HINT(state, x, y, i))
2014                     printf("%c", n2c(i+1, state->order));
2015                 else
2016                     printf(".");
2017             }
2018             printf(" ");
2019         }
2020         printf("\n");
2021     }
2022     printf("\n");
2023 }
2024
2025 #endif
2026
2027 static void pdiff(int diff)
2028 {
2029     if (diff == DIFF_IMPOSSIBLE)
2030         printf("Game is impossible.\n");
2031     else if (diff == DIFF_UNFINISHED)
2032         printf("Game has incomplete.\n");
2033     else if (diff == DIFF_AMBIGUOUS)
2034         printf("Game has multiple solutions.\n");
2035     else
2036         printf("Game has difficulty %s.\n", unequal_diffnames[diff]);
2037 }
2038
2039 static int solve(game_params *p, char *desc, int debug)
2040 {
2041     game_state *state = new_game(NULL, p, desc);
2042     struct solver_ctx *ctx = new_ctx(state);
2043     struct latin_solver solver;
2044     int diff;
2045
2046     solver_show_working = debug;
2047     game_debug(state);
2048
2049     latin_solver_alloc(&solver, state->nums, state->order);
2050
2051     diff = latin_solver_main(&solver, DIFF_RECURSIVE,
2052                              DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
2053                              DIFF_EXTREME, DIFF_RECURSIVE,
2054                              unequal_solvers, ctx, clone_ctx, free_ctx);
2055
2056     free_ctx(ctx);
2057
2058     latin_solver_free(&solver);
2059
2060     if (debug) pdiff(diff);
2061
2062     game_debug(state);
2063     free_game(state);
2064     return diff;
2065 }
2066
2067 static void check(game_params *p)
2068 {
2069     char *msg = validate_params(p, 1);
2070     if (msg) {
2071         fprintf(stderr, "%s: %s", quis, msg);
2072         exit(1);
2073     }
2074 }
2075
2076 static int gen(game_params *p, random_state *rs, int debug)
2077 {
2078     char *desc, *aux;
2079     int diff;
2080
2081     check(p);
2082
2083     solver_show_working = debug;
2084     desc = new_game_desc(p, rs, &aux, 0);
2085     diff = solve(p, desc, debug);
2086     sfree(aux);
2087     sfree(desc);
2088
2089     return diff;
2090 }
2091
2092 static void soak(game_params *p, random_state *rs)
2093 {
2094     time_t tt_start, tt_now, tt_last;
2095     char *aux, *desc;
2096     game_state *st;
2097     int n = 0, neasy = 0, realdiff = p->diff;
2098
2099     check(p);
2100
2101     solver_show_working = 0;
2102     maxtries = 1;
2103
2104     tt_start = tt_now = time(NULL);
2105
2106     printf("Soak-generating an %s %dx%d grid, difficulty %s.\n",
2107            p->adjacent ? "adjacent" : "unequal",
2108            p->order, p->order, unequal_diffnames[p->diff]);
2109
2110     while (1) {
2111         p->diff = realdiff;
2112         desc = new_game_desc(p, rs, &aux, 0);
2113         st = new_game(NULL, p, desc);
2114         solver_state(st, DIFF_RECURSIVE);
2115         free_game(st);
2116         sfree(aux);
2117         sfree(desc);
2118
2119         n++;
2120         if (realdiff != p->diff) neasy++;
2121
2122         tt_last = time(NULL);
2123         if (tt_last > tt_now) {
2124             tt_now = tt_last;
2125             printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
2126                    n, (double)n / ((double)tt_now - tt_start),
2127                    neasy, (double)neasy*100.0/(double)n,
2128                    (double)(n - neasy) / ((double)tt_now - tt_start));
2129         }
2130     }
2131 }
2132
2133 static void usage_exit(const char *msg)
2134 {
2135     if (msg)
2136         fprintf(stderr, "%s: %s\n", quis, msg);
2137     fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
2138     exit(1);
2139 }
2140
2141 int main(int argc, const char *argv[])
2142 {
2143     random_state *rs;
2144     time_t seed = time(NULL);
2145     int do_soak = 0, diff;
2146
2147     game_params *p;
2148
2149     maxtries = 50;
2150
2151     quis = argv[0];
2152     while (--argc > 0) {
2153         const char *p = *++argv;
2154         if (!strcmp(p, "--soak"))
2155             do_soak = 1;
2156         else if (!strcmp(p, "--seed")) {
2157             if (argc == 0)
2158                 usage_exit("--seed needs an argument");
2159             seed = (time_t)atoi(*++argv);
2160             argc--;
2161         } else if (*p == '-')
2162             usage_exit("unrecognised option");
2163         else
2164             break;
2165     }
2166     rs = random_new((void*)&seed, sizeof(time_t));
2167
2168     if (do_soak == 1) {
2169         if (argc != 1) usage_exit("only one argument for --soak");
2170         p = default_params();
2171         decode_params(p, *argv);
2172         soak(p, rs);
2173     } else if (argc > 0) {
2174         int i;
2175         for (i = 0; i < argc; i++) {
2176             const char *id = *argv++;
2177             char *desc = strchr(id, ':'), *err;
2178             p = default_params();
2179             if (desc) {
2180                 *desc++ = '\0';
2181                 decode_params(p, id);
2182                 err = validate_desc(p, desc);
2183                 if (err) {
2184                     fprintf(stderr, "%s: %s\n", quis, err);
2185                     exit(1);
2186                 }
2187                 solve(p, desc, 1);
2188             } else {
2189                 decode_params(p, id);
2190                 diff = gen(p, rs, 1);
2191             }
2192         }
2193     } else {
2194         while(1) {
2195             p = default_params();
2196             p->order = random_upto(rs, 7) + 3;
2197             p->diff = random_upto(rs, 4);
2198             diff = gen(p, rs, 0);
2199             pdiff(diff);
2200         }
2201     }
2202
2203     return 0;
2204 }
2205
2206 #endif
2207
2208 /* vim: set shiftwidth=4 tabstop=8: */