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;
 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         for (j = nposs = 0; j < state->order; j++) {
 968             if (state->hints[loc*state->order + j]) nposs++;
 969         }
 970         for (j = nclues = 0; j < 4; j++) {
 971             if (state->flags[loc] & adjthan[j].f) nclues++;
 972         }
 973         if ((nposs > maxposs) ||
 974             (nposs == maxposs && nclues < minclues)) {
 975             best = i; maxposs = nposs; minclues = nclues;
 976 #ifdef STANDALONE_SOLVER
 977             if (solver_show_working) {
 978                 int x = loc % state->order, y = loc / state->order;
 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             }
 982 #endif
 983         }
 984     }
 985     /* if we didn't solve, we must have 1 clue to place! */
 986     assert(best != -1);
 987     return best;
 988 }
 989
 990 #ifdef STANDALONE_SOLVER
 991 int maxtries;
 992 #define MAXTRIES maxtries
 993 #else
 994 #define MAXTRIES 50
 995 #endif
 996 int gg_solved;
 997
 998 static int game_assemble(game_state *new, int *scratch, digit *latin,
 999                          int difficulty)
1000 {
1001     game_state *copy = dup_game(new);
1002     int best;
1003
1004     if (difficulty >= DIFF_RECURSIVE) {
1005         /* We mustn't use any solver that might guess answers;
1006          * if it guesses wrongly but solves, gg_place_clue will
1007          * get mighty confused. We will always trim clues down
1008          * (making it more difficult) in game_strip, which doesn't
1009          * have this problem. */
1010         difficulty = DIFF_RECURSIVE-1;
1011     }
1012
1013 #ifdef STANDALONE_SOLVER
1014     if (solver_show_working) {
1015         game_debug(new);
1016         latin_solver_debug(new->hints, new->order);
1017     }
1018 #endif
1019
1020     while(1) {
1021         gg_solved++;
1022         if (solver_state(copy, difficulty) == 1) break;
1023
1024         best = gg_best_clue(copy, scratch, latin);
1025         gg_place_clue(new, scratch[best], latin, 0);
1026         gg_place_clue(copy, scratch[best], latin, 0);
1027     }
1028     free_game(copy);
1029 #ifdef STANDALONE_SOLVER
1030     if (solver_show_working) {
1031         char *dbg = game_text_format(new);
1032         printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved, dbg);
1033         sfree(dbg);
1034     }
1035 #endif
1036     return 0;
1037 }
1038
1039 static void game_strip(game_state *new, int *scratch, digit *latin,
1040                        int difficulty)
1041 {
1042     int o = new->order, o2 = o*o, lscratch = o2*5, i;
1043     game_state *copy = blank_game(new->order, new->adjacent);
1044
1045     /* For each symbol (if it exists in new), try and remove it and
1046      * solve again; if we couldn't solve without it put it back. */
1047     for (i = 0; i < lscratch; i++) {
1048         if (!gg_remove_clue(new, scratch[i], 0)) continue;
1049
1050         memcpy(copy->nums,  new->nums,  o2 * sizeof(digit));
1051         memcpy(copy->flags, new->flags, o2 * sizeof(unsigned int));
1052         gg_solved++;
1053         if (solver_state(copy, difficulty) != 1) {
1054             /* put clue back, we can't solve without it. */
1055             int ret = gg_place_clue(new, scratch[i], latin, 0);
1056             assert(ret == 1);
1057         } else {
1058 #ifdef STANDALONE_SOLVER
1059             if (solver_show_working)
1060                 printf("game_strip: clue was redundant.");
1061 #endif
1062         }
1063     }
1064     free_game(copy);
1065 #ifdef STANDALONE_SOLVER
1066     if (solver_show_working) {
1067         char *dbg = game_text_format(new);
1068         debug(("game_strip: done, %d solver iterations.", gg_solved));
1069         debug(("%s", dbg));
1070         sfree(dbg);
1071     }
1072 #endif
1073 }
1074
1075 static void add_adjacent_flags(game_state *state, digit *latin)
1076 {
1077     int x, y, o = state->order;
1078
1079     /* All clues in adjacent mode are always present (the only variables are
1080      * the numbers). This adds all the flags to state based on the supplied
1081      * latin square. */
1082
1083     for (y = 0; y < o; y++) {
1084         for (x = 0; x < o; x++) {
1085             if (x < (o-1) && (abs(latin[y*o+x] - latin[y*o+x+1]) == 1)) {
1086                 GRID(state, flags, x, y) |= F_ADJ_RIGHT;
1087                 GRID(state, flags, x+1, y) |= F_ADJ_LEFT;
1088             }
1089             if (y < (o-1) && (abs(latin[y*o+x] - latin[(y+1)*o+x]) == 1)) {
1090                 GRID(state, flags, x, y) |= F_ADJ_DOWN;
1091                 GRID(state, flags, x, y+1) |= F_ADJ_UP;
1092             }
1093         }
1094     }
1095 }
1096
1097 static char *new_game_desc(const game_params *params_in, random_state *rs,
1098                            char **aux, int interactive)
1099 {
1100     game_params params_copy = *params_in; /* structure copy */
1101     game_params *params = &params_copy;
1102     digit *sq = NULL;
1103     int i, x, y, retlen, k, nsol;
1104     int o2 = params->order * params->order, ntries = 1;
1105     int *scratch, lscratch = o2*5;
1106     char *ret, buf[80];
1107     game_state *state = blank_game(params->order, params->adjacent);
1108
1109     /* Generate a list of 'things to strip' (randomised later) */
1110     scratch = snewn(lscratch, int);
1111     /* Put the numbers (4 mod 5) before the inequalities (0-3 mod 5) */
1112     for (i = 0; i < lscratch; i++) scratch[i] = (i%o2)*5 + 4 - (i/o2);
1113
1114 generate:
1115 #ifdef STANDALONE_SOLVER
1116     if (solver_show_working)
1117         printf("new_game_desc: generating %s puzzle, ntries so far %d\n",
1118                unequal_diffnames[params->diff], ntries);
1119 #endif
1120     if (sq) sfree(sq);
1121     sq = latin_generate(params->order, rs);
1122     latin_debug(sq, params->order);
1123     /* Separately shuffle the numeric and inequality clues */
1124     shuffle(scratch, lscratch/5, sizeof(int), rs);
1125     shuffle(scratch+lscratch/5, 4*lscratch/5, sizeof(int), rs);
1126
1127     memset(state->nums, 0, o2 * sizeof(digit));
1128     memset(state->flags, 0, o2 * sizeof(unsigned int));
1129
1130     if (state->adjacent) {
1131         /* All adjacency flags are always present. */
1132         add_adjacent_flags(state, sq);
1133     }
1134
1135     gg_solved = 0;
1136     if (game_assemble(state, scratch, sq, params->diff) < 0)
1137         goto generate;
1138     game_strip(state, scratch, sq, params->diff);
1139
1140     if (params->diff > 0) {
1141         game_state *copy = dup_game(state);
1142         nsol = solver_state(copy, params->diff-1);
1143         free_game(copy);
1144         if (nsol > 0) {
1145 #ifdef STANDALONE_SOLVER
1146             if (solver_show_working)
1147                 printf("game_assemble: puzzle as generated is too easy.\n");
1148 #endif
1149             if (ntries < MAXTRIES) {
1150                 ntries++;
1151                 goto generate;
1152             }
1153 #ifdef STANDALONE_SOLVER
1154             if (solver_show_working)
1155                 printf("Unable to generate %s %dx%d after %d attempts.\n",
1156                        unequal_diffnames[params->diff],
1157                        params->order, params->order, MAXTRIES);
1158 #endif
1159             params->diff--;
1160         }
1161     }
1162 #ifdef STANDALONE_SOLVER
1163     if (solver_show_working)
1164         printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).\n",
1165                unequal_diffnames[params->diff], ntries, gg_solved);
1166 #endif
1167
1168     ret = NULL; retlen = 0;
1169     for (y = 0; y < params->order; y++) {
1170         for (x = 0; x < params->order; x++) {
1171             unsigned int f = GRID(state, flags, x, y);
1172             k = sprintf(buf, "%d%s%s%s%s,",
1173                         GRID(state, nums, x, y),
1174                         (f & F_ADJ_UP)    ? "U" : "",
1175                         (f & F_ADJ_RIGHT) ? "R" : "",
1176                         (f & F_ADJ_DOWN)  ? "D" : "",
1177                         (f & F_ADJ_LEFT)  ? "L" : "");
1178
1179             ret = sresize(ret, retlen + k + 1, char);
1180             strcpy(ret + retlen, buf);
1181             retlen += k;
1182         }
1183     }
1184     *aux = latin_desc(sq, params->order);
1185
1186     free_game(state);
1187     sfree(sq);
1188     sfree(scratch);
1189
1190     return ret;
1191 }
1192
1193 static game_state *load_game(const game_params *params, char *desc,
1194                              char **why_r)
1195 {
1196     game_state *state = blank_game(params->order, params->adjacent);
1197     char *p = desc;
1198     int i = 0, n, o = params->order, x, y;
1199     char *why = NULL;
1200
1201     while (*p) {
1202         while (*p >= 'a' && *p <= 'z') {
1203             i += *p - 'a' + 1;
1204             p++;
1205         }
1206         if (i >= o*o) {
1207             why = "Too much data to fill grid"; goto fail;
1208         }
1209
1210         if (*p < '0' && *p > '9') {
1211             why = "Expecting number in game description"; goto fail;
1212         }
1213         n = atoi(p);
1214         if (n < 0 || n > o) {
1215             why = "Out-of-range number in game description"; goto fail;
1216         }
1217         state->nums[i] = (digit)n;
1218         while (*p >= '0' && *p <= '9') p++; /* skip number */
1219
1220         if (state->nums[i] != 0)
1221             state->flags[i] |= F_IMMUTABLE; /* === number set by game description */
1222
1223         while (*p == 'U' || *p == 'R' || *p == 'D' || *p == 'L') {
1224             switch (*p) {
1225             case 'U': state->flags[i] |= F_ADJ_UP;    break;
1226             case 'R': state->flags[i] |= F_ADJ_RIGHT; break;
1227             case 'D': state->flags[i] |= F_ADJ_DOWN;  break;
1228             case 'L': state->flags[i] |= F_ADJ_LEFT;  break;
1229             default: why = "Expecting flag URDL in game description"; goto fail;
1230             }
1231             p++;
1232         }
1233         i++;
1234         if (i < o*o && *p != ',') {
1235             why = "Missing separator"; goto fail;
1236         }
1237         if (*p == ',') p++;
1238     }
1239     if (i < o*o) {
1240         why = "Not enough data to fill grid"; goto fail;
1241     }
1242     i = 0;
1243     for (y = 0; y < o; y++) {
1244         for (x = 0; x < o; x++) {
1245             for (n = 0; n < 4; n++) {
1246                 if (GRID(state, flags, x, y) & adjthan[n].f) {
1247                     int nx = x + adjthan[n].dx;
1248                     int ny = y + adjthan[n].dy;
1249                     /* a flag must not point us off the grid. */
1250                     if (nx < 0 || ny < 0 || nx >= o || ny >= o) {
1251                         why = "Flags go off grid"; goto fail;
1252                     }
1253                     if (params->adjacent) {
1254                         /* if one cell is adjacent to another, the other must
1255                          * also be adjacent to the first. */
1256                         if (!(GRID(state, flags, nx, ny) & adjthan[n].fo)) {
1257                             why = "Flags contradicting each other"; goto fail;
1258                         }
1259                     } else {
1260                         /* if one cell is GT another, the other must _not_ also
1261                          * be GT the first. */
1262                         if (GRID(state, flags, nx, ny) & adjthan[n].fo) {
1263                             why = "Flags contradicting each other"; goto fail;
1264                         }
1265                     }
1266                 }
1267             }
1268         }
1269     }
1270
1271     return state;
1272
1273 fail:
1274     free_game(state);
1275     if (why_r) *why_r = why;
1276     return NULL;
1277 }
1278
1279 static game_state *new_game(midend *me, game_params *params, char *desc)
1280 {
1281     game_state *state = load_game(params, desc, NULL);
1282     if (!state) {
1283         assert("Unable to load ?validated game.");
1284         return NULL;
1285     }
1286     return state;
1287 }
1288
1289 static char *validate_desc(const game_params *params, char *desc)
1290 {
1291     char *why = NULL;
1292     game_state *dummy = load_game(params, desc, &why);
1293     if (dummy) {
1294         free_game(dummy);
1295         assert(!why);
1296     } else
1297         assert(why);
1298     return why;
1299 }
1300
1301 static char *solve_game(game_state *state, game_state *currstate,
1302                         char *aux, char **error)
1303 {
1304     game_state *solved;
1305     int r;
1306     char *ret = NULL;
1307
1308     if (aux) return dupstr(aux);
1309
1310     solved = dup_game(state);
1311     for (r = 0; r < state->order*state->order; r++) {
1312         if (!(solved->flags[r] & F_IMMUTABLE))
1313             solved->nums[r] = 0;
1314     }
1315     r = solver_state(solved, DIFFCOUNT-1);   /* always use full solver */
1316     if (r > 0) ret = latin_desc(solved->nums, solved->order);
1317     free_game(solved);
1318     return ret;
1319 }
1320
1321 /* ----------------------------------------------------------
1322  * Game UI input processing.
1323  */
1324
1325 struct game_ui {
1326     int hx, hy;                         /* as for solo.c, highlight pos */
1327     int hshow, hpencil, hcursor;        /* show state, type, and ?cursor. */
1328 };
1329
1330 static game_ui *new_ui(game_state *state)
1331 {
1332     game_ui *ui = snew(game_ui);
1333
1334     ui->hx = ui->hy = 0;
1335     ui->hpencil = ui->hshow = ui->hcursor = 0;
1336
1337     return ui;
1338 }
1339
1340 static void free_ui(game_ui *ui)
1341 {
1342     sfree(ui);
1343 }
1344
1345 static char *encode_ui(game_ui *ui)
1346 {
1347     return NULL;
1348 }
1349
1350 static void decode_ui(game_ui *ui, char *encoding)
1351 {
1352 }
1353
1354 static void game_changed_state(game_ui *ui, game_state *oldstate,
1355                                game_state *newstate)
1356 {
1357     /* See solo.c; if we were pencil-mode highlighting and
1358      * somehow a square has just been properly filled, cancel
1359      * pencil mode. */
1360     if (ui->hshow && ui->hpencil && !ui->hcursor &&
1361         GRID(newstate, nums, ui->hx, ui->hy) != 0) {
1362         ui->hshow = 0;
1363     }
1364 }
1365
1366 struct game_drawstate {
1367     int tilesize, order, started, adjacent;
1368     digit *nums;                /* copy of nums, o^2 */
1369     unsigned char *hints;       /* copy of hints, o^3 */
1370     unsigned int *flags;        /* o^2 */
1371
1372     int hx, hy, hshow, hpencil; /* as for game_ui. */
1373     int hflash;
1374 };
1375
1376 static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds,
1377                             int ox, int oy, int button)
1378 {
1379     int x = FROMCOORD(ox), y = FROMCOORD(oy), n;
1380     char buf[80];
1381
1382     button &= ~MOD_MASK;
1383
1384     if (x >= 0 && x < ds->order && ((ox - COORD(x)) <= TILE_SIZE) &&
1385         y >= 0 && y < ds->order && ((oy - COORD(y)) <= TILE_SIZE)) {
1386         if (button == LEFT_BUTTON) {
1387             /* normal highlighting for non-immutable squares */
1388             if (GRID(state, flags, x, y) & F_IMMUTABLE)
1389                 ui->hshow = 0;
1390             else if (x == ui->hx && y == ui->hy &&
1391                      ui->hshow && ui->hpencil == 0)
1392                 ui->hshow = 0;
1393             else {
1394                 ui->hx = x; ui->hy = y; ui->hpencil = 0;
1395                 ui->hshow = 1;
1396             }
1397             ui->hcursor = 0;
1398             return "";
1399         }
1400         if (button == RIGHT_BUTTON) {
1401             /* pencil highlighting for non-filled squares */
1402             if (GRID(state, nums, x, y) != 0)
1403                 ui->hshow = 0;
1404             else if (x == ui->hx && y == ui->hy &&
1405                      ui->hshow && ui->hpencil)
1406                 ui->hshow = 0;
1407             else {
1408                 ui->hx = x; ui->hy = y; ui->hpencil = 1;
1409                 ui->hshow = 1;
1410             }
1411             ui->hcursor = 0;
1412             return "";
1413         }
1414     }
1415
1416     if (IS_CURSOR_MOVE(button)) {
1417         move_cursor(button, &ui->hx, &ui->hy, ds->order, ds->order, 0);
1418         ui->hshow = ui->hcursor = 1;
1419         return "";
1420     }
1421     if (ui->hshow && IS_CURSOR_SELECT(button)) {
1422         ui->hpencil = 1 - ui->hpencil;
1423         ui->hcursor = 1;
1424         return "";
1425     }
1426
1427
1428     if (ui->hshow) {
1429         debug(("button %d, cbutton %d", button, (int)((char)button)));
1430         n = c2n(button, state->order);
1431
1432         debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1433                n, ui->hx, ui->hy, ui->hpencil,
1434                GRID(state, flags, ui->hx, ui->hy),
1435                GRID(state, nums, ui->hx, ui->hy)));
1436
1437         if (n < 0 || n > ds->order)
1438             return NULL;        /* out of range */
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(game_state *state, 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         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(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                           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, 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, game_state *state,
1695                            game_ui *ui, int x, int y, int hflash)
1696 {
1697     int ox = COORD(x), oy = COORD(y), bg, hon;
1698     unsigned int f = GRID(state, flags, x, y);
1699
1700     bg = hflash ? COL_HIGHLIGHT : COL_BACKGROUND;
1701
1702     hon = (ui->hshow && x == ui->hx && y == ui->hy);
1703
1704     /* Clear square. */
1705     draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
1706               (hon && !ui->hpencil) ? COL_HIGHLIGHT : bg);
1707
1708     /* Draw the highlight (pencil or full), if we're the highlight */
1709     if (hon && ui->hpencil) {
1710         int coords[6];
1711         coords[0] = ox;
1712         coords[1] = oy;
1713         coords[2] = ox + TILE_SIZE/2;
1714         coords[3] = oy;
1715         coords[4] = ox;
1716         coords[5] = oy + TILE_SIZE/2;
1717         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1718     }
1719
1720     /* Draw the square outline (which is the cursor, if we're the cursor). */
1721     draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
1722
1723     draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
1724
1725     /* Draw the adjacent clue signs. */
1726     if (ds->adjacent)
1727         draw_adjs(dr, ds, ox, oy, f, COL_BACKGROUND, COL_GRID);
1728     else
1729         draw_gts(dr, ds, ox, oy, f, COL_BACKGROUND, COL_TEXT);
1730 }
1731
1732 static void draw_num(drawing *dr, game_drawstate *ds, int x, int y)
1733 {
1734     int ox = COORD(x), oy = COORD(y);
1735     unsigned int f = GRID(ds,flags,x,y);
1736     char str[2];
1737
1738     /* (can assume square has just been cleared) */
1739
1740     /* Draw number, choosing appropriate colour */
1741     str[0] = n2c(GRID(ds, nums, x, y), ds->order);
1742     str[1] = '\0';
1743     draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1744               FONT_VARIABLE, 3*TILE_SIZE/4, ALIGN_VCENTRE | ALIGN_HCENTRE,
1745               (f & F_IMMUTABLE) ? COL_TEXT : (f & F_ERROR) ? COL_ERROR : COL_GUESS, str);
1746 }
1747
1748 static void draw_hints(drawing *dr, game_drawstate *ds, int x, int y)
1749 {
1750     int ox = COORD(x), oy = COORD(y);
1751     int nhints, i, j, hw, hh, hmax, fontsz;
1752     char str[2];
1753
1754     /* (can assume square has just been cleared) */
1755
1756     /* Draw hints; steal ingenious algorithm (basically)
1757      * from solo.c:draw_number() */
1758     for (i = nhints = 0; i < ds->order; i++) {
1759         if (HINT(ds, x, y, i)) nhints++;
1760     }
1761
1762     for (hw = 1; hw * hw < nhints; hw++);
1763     if (hw < 3) hw = 3;
1764     hh = (nhints + hw - 1) / hw;
1765     if (hh < 2) hh = 2;
1766     hmax = max(hw, hh);
1767     fontsz = TILE_SIZE/(hmax*(11-hmax)/8);
1768
1769     for (i = j = 0; i < ds->order; i++) {
1770         if (HINT(ds,x,y,i)) {
1771             int hx = j % hw, hy = j / hw;
1772
1773             str[0] = n2c(i+1, ds->order);
1774             str[1] = '\0';
1775             draw_text(dr,
1776                       ox + (4*hx+3) * TILE_SIZE / (4*hw+2),
1777                       oy + (4*hy+3) * TILE_SIZE / (4*hh+2),
1778                       FONT_VARIABLE, fontsz,
1779                       ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1780             j++;
1781         }
1782     }
1783 }
1784
1785 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1786                         game_state *state, int dir, game_ui *ui,
1787                         float animtime, float flashtime)
1788 {
1789     int x, y, i, hchanged = 0, stale, hflash = 0;
1790
1791     debug(("highlight old (%d,%d), new (%d,%d)", ds->hx, ds->hy, ui->hx, ui->hy));
1792
1793     if (flashtime > 0 &&
1794         (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3))
1795          hflash = 1;
1796
1797     if (!ds->started) {
1798         draw_rect(dr, 0, 0, DRAW_SIZE, DRAW_SIZE, COL_BACKGROUND);
1799         draw_update(dr, 0, 0, DRAW_SIZE, DRAW_SIZE);
1800     }
1801     if (ds->hx != ui->hx || ds->hy != ui->hy ||
1802         ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
1803         hchanged = 1;
1804
1805     for (x = 0; x < ds->order; x++) {
1806         for (y = 0; y < ds->order; y++) {
1807             if (!ds->started)
1808                 stale = 1;
1809             else if (hflash != ds->hflash)
1810                 stale = 1;
1811             else
1812                 stale = 0;
1813
1814             if (hchanged) {
1815                 if ((x == ui->hx && y == ui->hy) ||
1816                     (x == ds->hx && y == ds->hy))
1817                     stale = 1;
1818             }
1819
1820             if (GRID(state, nums, x, y) != GRID(ds, nums, x, y)) {
1821                 GRID(ds, nums, x, y) = GRID(state, nums, x, y);
1822                 stale = 1;
1823             }
1824             if (GRID(state, flags, x, y) != GRID(ds, flags, x, y)) {
1825                 GRID(ds, flags, x, y) = GRID(state, flags, x, y);
1826                 stale = 1;
1827             }
1828             if (GRID(ds, nums, x, y) == 0) {
1829                 /* We're not a number square (therefore we might
1830                  * display hints); do we need to update? */
1831                 for (i = 0; i < ds->order; i++) {
1832                     if (HINT(state, x, y, i) != HINT(ds, x, y, i)) {
1833                         HINT(ds, x, y, i) = HINT(state, x, y, i);
1834                         stale = 1;
1835                     }
1836                 }
1837             }
1838             if (stale) {
1839                 draw_furniture(dr, ds, state, ui, x, y, hflash);
1840                 if (GRID(ds, nums, x, y) > 0)
1841                     draw_num(dr, ds, x, y);
1842                 else
1843                     draw_hints(dr, ds, x, y);
1844             }
1845         }
1846     }
1847     ds->hx = ui->hx; ds->hy = ui->hy;
1848     ds->hshow = ui->hshow;
1849     ds->hpencil = ui->hpencil;
1850
1851     ds->started = 1;
1852     ds->hflash = hflash;
1853 }
1854
1855 static float game_anim_length(game_state *oldstate, game_state *newstate,
1856                               int dir, game_ui *ui)
1857 {
1858     return 0.0F;
1859 }
1860
1861 static float game_flash_length(game_state *oldstate, game_state *newstate,
1862                                int dir, game_ui *ui)
1863 {
1864     if (!oldstate->completed && newstate->completed &&
1865         !oldstate->cheated && !newstate->cheated)
1866         return FLASH_TIME;
1867     return 0.0F;
1868 }
1869
1870 static int game_status(game_state *state)
1871 {
1872     return state->completed ? +1 : 0;
1873 }
1874
1875 static int game_timing_state(game_state *state, game_ui *ui)
1876 {
1877     return TRUE;
1878 }
1879
1880 static void game_print_size(game_params *params, float *x, float *y)
1881 {
1882     int pw, ph;
1883
1884     /* 10mm squares by default, roughly the same as Grauniad. */
1885     game_compute_size(params, 1000, &pw, &ph);
1886     *x = pw / 100.0F;
1887     *y = ph / 100.0F;
1888 }
1889
1890 static void game_print(drawing *dr, game_state *state, int tilesize)
1891 {
1892     int ink = print_mono_colour(dr, 0);
1893     int x, y, o = state->order, ox, oy, n;
1894     char str[2];
1895
1896     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1897     game_drawstate ads, *ds = &ads;
1898     game_set_size(dr, ds, NULL, tilesize);
1899
1900     print_line_width(dr, 2 * TILE_SIZE / 40);
1901
1902     /* Squares, numbers, gt signs */
1903     for (y = 0; y < o; y++) {
1904         for (x = 0; x < o; x++) {
1905             ox = COORD(x); oy = COORD(y);
1906             n = GRID(state, nums, x, y);
1907
1908             draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1909
1910             str[0] = n ? n2c(n, state->order) : ' ';
1911             str[1] = '\0';
1912             draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1913                       FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1914                       ink, str);
1915
1916             if (state->adjacent)
1917                 draw_adjs(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
1918             else
1919                 draw_gts(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
1920         }
1921     }
1922 }
1923
1924 /* ----------------------------------------------------------------------
1925  * Housekeeping.
1926  */
1927
1928 #ifdef COMBINED
1929 #define thegame unequal
1930 #endif
1931
1932 const struct game thegame = {
1933     "Unequal", "games.unequal", "unequal",
1934     default_params,
1935     game_fetch_preset,
1936     decode_params,
1937     encode_params,
1938     free_params,
1939     dup_params,
1940     TRUE, game_configure, custom_params,
1941     validate_params,
1942     new_game_desc,
1943     validate_desc,
1944     new_game,
1945     dup_game,
1946     free_game,
1947     TRUE, solve_game,
1948     TRUE, game_can_format_as_text_now, game_text_format,
1949     new_ui,
1950     free_ui,
1951     encode_ui,
1952     decode_ui,
1953     game_changed_state,
1954     interpret_move,
1955     execute_move,
1956     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1957     game_colours,
1958     game_new_drawstate,
1959     game_free_drawstate,
1960     game_redraw,
1961     game_anim_length,
1962     game_flash_length,
1963     game_status,
1964     TRUE, FALSE, game_print_size, game_print,
1965     FALSE,                             /* wants_statusbar */
1966     FALSE, game_timing_state,
1967     REQUIRE_RBUTTON | REQUIRE_NUMPAD,  /* flags */
1968 };
1969
1970 /* ----------------------------------------------------------------------
1971  * Standalone solver.
1972  */
1973
1974 #ifdef STANDALONE_SOLVER
1975
1976 #include <time.h>
1977 #include <stdarg.h>
1978
1979 const char *quis = NULL;
1980
1981 #if 0 /* currently unused */
1982
1983 static void debug_printf(char *fmt, ...)
1984 {
1985     char buf[4096];
1986     va_list ap;
1987
1988     va_start(ap, fmt);
1989     vsprintf(buf, fmt, ap);
1990     puts(buf);
1991     va_end(ap);
1992 }
1993
1994 static void game_printf(game_state *state)
1995 {
1996     char *dbg = game_text_format(state);
1997     printf("%s", dbg);
1998     sfree(dbg);
1999 }
2000
2001 static void game_printf_wide(game_state *state)
2002 {
2003     int x, y, i, n;
2004
2005     for (y = 0; y < state->order; y++) {
2006         for (x = 0; x < state->order; x++) {
2007             n = GRID(state, nums, x, y);
2008             for (i = 0; i < state->order; i++) {
2009                 if (n > 0)
2010                     printf("%c", n2c(n, state->order));
2011                 else if (HINT(state, x, y, i))
2012                     printf("%c", n2c(i+1, state->order));
2013                 else
2014                     printf(".");
2015             }
2016             printf(" ");
2017         }
2018         printf("\n");
2019     }
2020     printf("\n");
2021 }
2022
2023 #endif
2024
2025 static void pdiff(int diff)
2026 {
2027     if (diff == DIFF_IMPOSSIBLE)
2028         printf("Game is impossible.\n");
2029     else if (diff == DIFF_UNFINISHED)
2030         printf("Game has incomplete.\n");
2031     else if (diff == DIFF_AMBIGUOUS)
2032         printf("Game has multiple solutions.\n");
2033     else
2034         printf("Game has difficulty %s.\n", unequal_diffnames[diff]);
2035 }
2036
2037 static int solve(game_params *p, char *desc, int debug)
2038 {
2039     game_state *state = new_game(NULL, p, desc);
2040     struct solver_ctx *ctx = new_ctx(state);
2041     struct latin_solver solver;
2042     int diff;
2043
2044     solver_show_working = debug;
2045     game_debug(state);
2046
2047     latin_solver_alloc(&solver, state->nums, state->order);
2048
2049     diff = latin_solver_main(&solver, DIFF_RECURSIVE,
2050                              DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
2051                              DIFF_EXTREME, DIFF_RECURSIVE,
2052                              unequal_solvers, ctx, clone_ctx, free_ctx);
2053
2054     free_ctx(ctx);
2055
2056     latin_solver_free(&solver);
2057
2058     if (debug) pdiff(diff);
2059
2060     game_debug(state);
2061     free_game(state);
2062     return diff;
2063 }
2064
2065 static void check(game_params *p)
2066 {
2067     char *msg = validate_params(p, 1);
2068     if (msg) {
2069         fprintf(stderr, "%s: %s", quis, msg);
2070         exit(1);
2071     }
2072 }
2073
2074 static int gen(game_params *p, random_state *rs, int debug)
2075 {
2076     char *desc, *aux;
2077     int diff;
2078
2079     check(p);
2080
2081     solver_show_working = debug;
2082     desc = new_game_desc(p, rs, &aux, 0);
2083     diff = solve(p, desc, debug);
2084     sfree(aux);
2085     sfree(desc);
2086
2087     return diff;
2088 }
2089
2090 static void soak(game_params *p, random_state *rs)
2091 {
2092     time_t tt_start, tt_now, tt_last;
2093     char *aux, *desc;
2094     game_state *st;
2095     int n = 0, neasy = 0, realdiff = p->diff;
2096
2097     check(p);
2098
2099     solver_show_working = 0;
2100     maxtries = 1;
2101
2102     tt_start = tt_now = time(NULL);
2103
2104     printf("Soak-generating an %s %dx%d grid, difficulty %s.\n",
2105            p->adjacent ? "adjacent" : "unequal",
2106            p->order, p->order, unequal_diffnames[p->diff]);
2107
2108     while (1) {
2109         p->diff = realdiff;
2110         desc = new_game_desc(p, rs, &aux, 0);
2111         st = new_game(NULL, p, desc);
2112         solver_state(st, DIFF_RECURSIVE);
2113         free_game(st);
2114         sfree(aux);
2115         sfree(desc);
2116
2117         n++;
2118         if (realdiff != p->diff) neasy++;
2119
2120         tt_last = time(NULL);
2121         if (tt_last > tt_now) {
2122             tt_now = tt_last;
2123             printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
2124                    n, (double)n / ((double)tt_now - tt_start),
2125                    neasy, (double)neasy*100.0/(double)n,
2126                    (double)(n - neasy) / ((double)tt_now - tt_start));
2127         }
2128     }
2129 }
2130
2131 static void usage_exit(const char *msg)
2132 {
2133     if (msg)
2134         fprintf(stderr, "%s: %s\n", quis, msg);
2135     fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
2136     exit(1);
2137 }
2138
2139 int main(int argc, const char *argv[])
2140 {
2141     random_state *rs;
2142     time_t seed = time(NULL);
2143     int do_soak = 0, diff;
2144
2145     game_params *p;
2146
2147     maxtries = 50;
2148
2149     quis = argv[0];
2150     while (--argc > 0) {
2151         const char *p = *++argv;
2152         if (!strcmp(p, "--soak"))
2153             do_soak = 1;
2154         else if (!strcmp(p, "--seed")) {
2155             if (argc == 0)
2156                 usage_exit("--seed needs an argument");
2157             seed = (time_t)atoi(*++argv);
2158             argc--;
2159         } else if (*p == '-')
2160             usage_exit("unrecognised option");
2161         else
2162             break;
2163     }
2164     rs = random_new((void*)&seed, sizeof(time_t));
2165
2166     if (do_soak == 1) {
2167         if (argc != 1) usage_exit("only one argument for --soak");
2168         p = default_params();
2169         decode_params(p, *argv);
2170         soak(p, rs);
2171     } else if (argc > 0) {
2172         int i;
2173         for (i = 0; i < argc; i++) {
2174             const char *id = *argv++;
2175             char *desc = strchr(id, ':'), *err;
2176             p = default_params();
2177             if (desc) {
2178                 *desc++ = '\0';
2179                 decode_params(p, id);
2180                 err = validate_desc(p, desc);
2181                 if (err) {
2182                     fprintf(stderr, "%s: %s\n", quis, err);
2183                     exit(1);
2184                 }
2185                 solve(p, desc, 1);
2186             } else {
2187                 decode_params(p, id);
2188                 diff = gen(p, rs, 1);
2189             }
2190         }
2191     } else {
2192         while(1) {
2193             p = default_params();
2194             p->order = random_upto(rs, 7) + 3;
2195             p->diff = random_upto(rs, 4);
2196             diff = gen(p, rs, 0);
2197             pdiff(diff);
2198         }
2199     }
2200
2201     return 0;
2202 }
2203
2204 #endif
2205
2206 /* vim: set shiftwidth=4 tabstop=8: */