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