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