keen.c

   1 /*
   2  * keen.c: an implementation of the Times's 'KenKen' puzzle.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10 #include <math.h>
  11
  12 #include "puzzles.h"
  13 #include "latin.h"
  14
  15 /*
  16  * Difficulty levels. I do some macro ickery here to ensure that my
  17  * enum and the various forms of my name list always match up.
  18  */
  19 #define DIFFLIST(A) \
  20     A(EASY,Easy,solver_easy,e) \
  21     A(NORMAL,Normal,solver_normal,n) \
  22     A(HARD,Hard,solver_hard,h) \
  23     A(EXTREME,Extreme,NULL,x) \
  24     A(UNREASONABLE,Unreasonable,NULL,u)
  25 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
  26 #define TITLE(upper,title,func,lower) #title,
  27 #define ENCODE(upper,title,func,lower) #lower
  28 #define CONFIG(upper,title,func,lower) ":" #title
  29 enum { DIFFLIST(ENUM) DIFFCOUNT };
  30 static char const *const keen_diffnames[] = { DIFFLIST(TITLE) };
  31 static char const keen_diffchars[] = DIFFLIST(ENCODE);
  32 #define DIFFCONFIG DIFFLIST(CONFIG)
  33
  34 /*
  35  * Clue notation. Important here that ADD and MUL come before SUB
  36  * and DIV, and that DIV comes last.
  37  */
  38 #define C_ADD 0x00000000L
  39 #define C_MUL 0x20000000L
  40 #define C_SUB 0x40000000L
  41 #define C_DIV 0x60000000L
  42 #define CMASK 0x60000000L
  43 #define CUNIT 0x20000000L
  44
  45 enum {
  46     COL_BACKGROUND,
  47     COL_GRID,
  48     COL_USER,
  49     COL_HIGHLIGHT,
  50     COL_ERROR,
  51     COL_PENCIL,
  52     NCOLOURS
  53 };
  54
  55 struct game_params {
  56     int w, diff;
  57 };
  58
  59 struct clues {
  60     int refcount;
  61     int w;
  62     int *dsf;
  63     long *clues;
  64 };
  65
  66 struct game_state {
  67     game_params par;
  68     struct clues *clues;
  69     digit *grid;
  70     int *pencil;                       /* bitmaps using bits 1<<1..1<<n */
  71     int completed, cheated;
  72 };
  73
  74 static game_params *default_params(void)
  75 {
  76     game_params *ret = snew(game_params);
  77
  78     ret->w = 6;
  79     ret->diff = DIFF_NORMAL;
  80
  81     return ret;
  82 }
  83
  84 const static struct game_params keen_presets[] = {
  85     {  4, DIFF_EASY         },
  86     {  5, DIFF_EASY         },
  87     {  6, DIFF_EASY         },
  88     {  6, DIFF_NORMAL       },
  89     {  6, DIFF_HARD         },
  90     {  6, DIFF_EXTREME      },
  91     {  6, DIFF_UNREASONABLE },
  92     {  9, DIFF_NORMAL       },
  93 };
  94
  95 static int game_fetch_preset(int i, char **name, game_params **params)
  96 {
  97     game_params *ret;
  98     char buf[80];
  99
 100     if (i < 0 || i >= lenof(keen_presets))
 101         return FALSE;
 102
 103     ret = snew(game_params);
 104     *ret = keen_presets[i]; /* structure copy */
 105
 106     sprintf(buf, "%dx%d %s", ret->w, ret->w, keen_diffnames[ret->diff]);
 107
 108     *name = dupstr(buf);
 109     *params = ret;
 110     return TRUE;
 111 }
 112
 113 static void free_params(game_params *params)
 114 {
 115     sfree(params);
 116 }
 117
 118 static game_params *dup_params(game_params *params)
 119 {
 120     game_params *ret = snew(game_params);
 121     *ret = *params;                    /* structure copy */
 122     return ret;
 123 }
 124
 125 static void decode_params(game_params *params, char const *string)
 126 {
 127     char const *p = string;
 128
 129     params->w = atoi(p);
 130     while (*p && isdigit((unsigned char)*p)) p++;
 131
 132     if (*p == 'd') {
 133         int i;
 134         p++;
 135         params->diff = DIFFCOUNT+1; /* ...which is invalid */
 136         if (*p) {
 137             for (i = 0; i < DIFFCOUNT; i++) {
 138                 if (*p == keen_diffchars[i])
 139                     params->diff = i;
 140             }
 141             p++;
 142         }
 143     }
 144 }
 145
 146 static char *encode_params(game_params *params, int full)
 147 {
 148     char ret[80];
 149
 150     sprintf(ret, "%d", params->w);
 151     if (full)
 152         sprintf(ret + strlen(ret), "d%c", keen_diffchars[params->diff]);
 153
 154     return dupstr(ret);
 155 }
 156
 157 static config_item *game_configure(game_params *params)
 158 {
 159     config_item *ret;
 160     char buf[80];
 161
 162     ret = snewn(3, config_item);
 163
 164     ret[0].name = "Grid size";
 165     ret[0].type = C_STRING;
 166     sprintf(buf, "%d", params->w);
 167     ret[0].sval = dupstr(buf);
 168     ret[0].ival = 0;
 169
 170     ret[1].name = "Difficulty";
 171     ret[1].type = C_CHOICES;
 172     ret[1].sval = DIFFCONFIG;
 173     ret[1].ival = params->diff;
 174
 175     ret[2].name = NULL;
 176     ret[2].type = C_END;
 177     ret[2].sval = NULL;
 178     ret[2].ival = 0;
 179
 180     return ret;
 181 }
 182
 183 static game_params *custom_params(config_item *cfg)
 184 {
 185     game_params *ret = snew(game_params);
 186
 187     ret->w = atoi(cfg[0].sval);
 188     ret->diff = cfg[1].ival;
 189
 190     return ret;
 191 }
 192
 193 static char *validate_params(game_params *params, int full)
 194 {
 195     if (params->w < 3 || params->w > 9)
 196         return "Grid size must be between 3 and 9";
 197     if (params->diff >= DIFFCOUNT)
 198         return "Unknown difficulty rating";
 199     return NULL;
 200 }
 201
 202 /* ----------------------------------------------------------------------
 203  * Solver.
 204  */
 205
 206 struct solver_ctx {
 207     int w, diff;
 208     int nboxes;
 209     int *boxes, *boxlist, *whichbox;
 210     long *clues;
 211     digit *soln;
 212     digit *dscratch;
 213     int *iscratch;
 214 };
 215
 216 static void solver_clue_candidate(struct solver_ctx *ctx, int diff, int box)
 217 {
 218     int w = ctx->w;
 219     int n = ctx->boxes[box+1] - ctx->boxes[box];
 220     int j;
 221
 222     /*
 223      * This function is called from the main clue-based solver
 224      * routine when we discover a candidate layout for a given clue
 225      * box consistent with everything we currently know about the
 226      * digit constraints in that box. We expect to find the digits
 227      * of the candidate layout in ctx->dscratch, and we update
 228      * ctx->iscratch as appropriate.
 229      */
 230     if (diff == DIFF_EASY) {
 231         unsigned mask = 0;
 232         /*
 233          * Easy-mode clue deductions: we do not record information
 234          * about which squares take which values, so we amalgamate
 235          * all the values in dscratch and OR them all into
 236          * everywhere.
 237          */
 238         for (j = 0; j < n; j++)
 239             mask |= 1 << ctx->dscratch[j];
 240         for (j = 0; j < n; j++)
 241             ctx->iscratch[j] |= mask;
 242     } else if (diff == DIFF_NORMAL) {
 243         /*
 244          * Normal-mode deductions: we process the information in
 245          * dscratch in the obvious way.
 246          */
 247         for (j = 0; j < n; j++)
 248             ctx->iscratch[j] |= 1 << ctx->dscratch[j];
 249     } else if (diff == DIFF_HARD) {
 250         /*
 251          * Hard-mode deductions: instead of ruling things out
 252          * _inside_ the clue box, we look for numbers which occur in
 253          * a given row or column in all candidate layouts, and rule
 254          * them out of all squares in that row or column that
 255          * _aren't_ part of this clue box.
 256          */
 257         int *sq = ctx->boxlist + ctx->boxes[box];
 258
 259         for (j = 0; j < 2*w; j++)
 260             ctx->iscratch[2*w+j] = 0;
 261         for (j = 0; j < n; j++) {
 262             int x = sq[j] / w, y = sq[j] % w;
 263             ctx->iscratch[2*w+x] |= 1 << ctx->dscratch[j];
 264             ctx->iscratch[3*w+y] |= 1 << ctx->dscratch[j];
 265         }
 266         for (j = 0; j < 2*w; j++)
 267             ctx->iscratch[j] &= ctx->iscratch[2*w+j];
 268     }
 269 }
 270
 271 static int solver_common(struct latin_solver *solver, void *vctx, int diff)
 272 {
 273     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 274     int w = ctx->w;
 275     int box, i, j, k;
 276     int ret = 0, total;
 277
 278     /*
 279      * Iterate over each clue box and deduce what we can.
 280      */
 281     for (box = 0; box < ctx->nboxes; box++) {
 282         int *sq = ctx->boxlist + ctx->boxes[box];
 283         int n = ctx->boxes[box+1] - ctx->boxes[box];
 284         long value = ctx->clues[box] & ~CMASK;
 285         long op = ctx->clues[box] & CMASK;
 286
 287         if (diff == DIFF_HARD) {
 288             for (i = 0; i < n; i++)
 289                 ctx->iscratch[i] = (1 << (w+1)) - (1 << 1);
 290         } else {
 291             for (i = 0; i < n; i++)
 292                 ctx->iscratch[i] = 0;
 293         }
 294
 295         switch (op) {
 296           case C_SUB:
 297           case C_DIV:
 298             /*
 299              * These two clue types must always apply to a box of
 300              * area 2. Also, the two digits in these boxes can never
 301              * be the same (because any domino must have its two
 302              * squares in either the same row or the same column).
 303              * So we simply iterate over all possibilities for the
 304              * two squares (both ways round), rule out any which are
 305              * inconsistent with the digit constraints we already
 306              * have, and update the digit constraints with any new
 307              * information thus garnered.
 308              */
 309             assert(n == 2);
 310
 311             for (i = 1; i <= w; i++) {
 312                 j = (op == C_SUB ? i + value : i * value);
 313                 if (j > w) break;
 314
 315                 /* (i,j) is a valid digit pair. Try it both ways round. */
 316
 317                 if (solver->cube[sq[0]*w+i-1] &&
 318                     solver->cube[sq[1]*w+j-1]) {
 319                     ctx->dscratch[0] = i;
 320                     ctx->dscratch[1] = j;
 321                     solver_clue_candidate(ctx, diff, box);
 322                 }
 323
 324                 if (solver->cube[sq[0]*w+j-1] &&
 325                     solver->cube[sq[1]*w+i-1]) {
 326                     ctx->dscratch[0] = j;
 327                     ctx->dscratch[1] = i;
 328                     solver_clue_candidate(ctx, diff, box);
 329                 }
 330             }
 331
 332             break;
 333
 334           case C_ADD:
 335           case C_MUL:
 336             /*
 337              * For these clue types, I have no alternative but to go
 338              * through all possible number combinations.
 339              *
 340              * Instead of a tedious physical recursion, I iterate in
 341              * the scratch array through all possibilities. At any
 342              * given moment, i indexes the element of the box that
 343              * will next be incremented.
 344              */
 345             i = 0;
 346             ctx->dscratch[i] = 0;
 347             total = value;             /* start with the identity */
 348             while (1) {
 349                 if (i < n) {
 350                     /*
 351                      * Find the next valid value for cell i.
 352                      */
 353                     for (j = ctx->dscratch[i] + 1; j <= w; j++) {
 354                         if (op == C_ADD ? (total < j) : (total % j != 0))
 355                             continue;  /* this one won't fit */
 356                         if (!solver->cube[sq[i]*w+j-1])
 357                             continue;  /* this one is ruled out already */
 358                         for (k = 0; k < i; k++)
 359                             if (ctx->dscratch[k] == j &&
 360                                 (sq[k] % w == sq[i] % w ||
 361                                  sq[k] / w == sq[i] / w))
 362                                 break; /* clashes with another row/col */
 363                         if (k < i)
 364                             continue;
 365
 366                         /* Found one. */
 367                         break;
 368                     }
 369
 370                     if (j > w) {
 371                         /* No valid values left; drop back. */
 372                         i--;
 373                         if (i < 0)
 374                             break;     /* overall iteration is finished */
 375                         if (op == C_ADD)
 376                             total += ctx->dscratch[i];
 377                         else
 378                             total *= ctx->dscratch[i];
 379                     } else {
 380                         /* Got a valid value; store it and move on. */
 381                         ctx->dscratch[i++] = j;
 382                         if (op == C_ADD)
 383                             total -= j;
 384                         else
 385                             total /= j;
 386                         ctx->dscratch[i] = 0;
 387                     }
 388                 } else {
 389                     if (total == (op == C_ADD ? 0 : 1))
 390                         solver_clue_candidate(ctx, diff, box);
 391                     i--;
 392                     if (op == C_ADD)
 393                         total += ctx->dscratch[i];
 394                     else
 395                         total *= ctx->dscratch[i];
 396                 }
 397             }
 398
 399             break;
 400         }
 401
 402         if (diff < DIFF_HARD) {
 403 #ifdef STANDALONE_SOLVER
 404             char prefix[256];
 405
 406             if (solver_show_working)
 407                 sprintf(prefix, "%*susing clue at (%d,%d):\n",
 408                         solver_recurse_depth*4, "",
 409                         sq[0]/w+1, sq[0]%w+1);
 410             else
 411                 prefix[0] = '\0';              /* placate optimiser */
 412 #endif
 413
 414             for (i = 0; i < n; i++)
 415                 for (j = 1; j <= w; j++) {
 416                     if (solver->cube[sq[i]*w+j-1] &&
 417                         !(ctx->iscratch[i] & (1 << j))) {
 418 #ifdef STANDALONE_SOLVER
 419                         if (solver_show_working) {
 420                             printf("%s%*s  ruling out %d at (%d,%d)\n",
 421                                    prefix, solver_recurse_depth*4, "",
 422                                    j, sq[i]/w+1, sq[i]%w+1);
 423                             prefix[0] = '\0';
 424                         }
 425 #endif
 426                         solver->cube[sq[i]*w+j-1] = 0;
 427                         ret = 1;
 428                     }
 429                 }
 430         } else {
 431 #ifdef STANDALONE_SOLVER
 432             char prefix[256];
 433
 434             if (solver_show_working)
 435                 sprintf(prefix, "%*susing clue at (%d,%d):\n",
 436                         solver_recurse_depth*4, "",
 437                         sq[0]/w+1, sq[0]%w+1);
 438             else
 439                 prefix[0] = '\0';              /* placate optimiser */
 440 #endif
 441
 442             for (i = 0; i < 2*w; i++) {
 443                 int start = (i < w ? i*w : i-w);
 444                 int step = (i < w ? 1 : w);
 445                 for (j = 1; j <= w; j++) if (ctx->iscratch[i] & (1 << j)) {
 446 #ifdef STANDALONE_SOLVER
 447                     char prefix2[256];
 448
 449                     if (solver_show_working)
 450                         sprintf(prefix2, "%*s  this clue requires %d in"
 451                                 " %s %d:\n", solver_recurse_depth*4, "",
 452                                 j, i < w ? "column" : "row", i%w+1);
 453                     else
 454                         prefix2[0] = '\0';   /* placate optimiser */
 455 #endif
 456
 457                     for (k = 0; k < w; k++) {
 458                         int pos = start + k*step;
 459                         if (ctx->whichbox[pos] != box &&
 460                             solver->cube[pos*w+j-1]) {
 461 #ifdef STANDALONE_SOLVER
 462                             if (solver_show_working) {
 463                                 printf("%s%s%*s   ruling out %d at (%d,%d)\n",
 464                                        prefix, prefix2,
 465                                        solver_recurse_depth*4, "",
 466                                        j, pos/w+1, pos%w+1);
 467                                 prefix[0] = prefix2[0] = '\0';
 468                             }
 469 #endif
 470                             solver->cube[pos*w+j-1] = 0;
 471                             ret = 1;
 472                         }
 473                     }
 474                 }
 475             }
 476
 477             /*
 478              * Once we find one block we can do something with in
 479              * this way, revert to trying easier deductions, so as
 480              * not to generate solver diagnostics that make the
 481              * problem look harder than it is. (We have to do this
 482              * for the Hard deductions but not the Easy/Normal ones,
 483              * because only the Hard deductions are cross-box.)
 484              */
 485             if (ret)
 486                 return ret;
 487         }
 488     }
 489
 490     return ret;
 491 }
 492
 493 static int solver_easy(struct latin_solver *solver, void *vctx)
 494 {
 495     /*
 496      * Omit the EASY deductions when solving at NORMAL level, since
 497      * the NORMAL deductions are a superset of them anyway and it
 498      * saves on time and confusing solver diagnostics.
 499      *
 500      * Note that this breaks the natural semantics of the return
 501      * value of latin_solver. Without this hack, you could determine
 502      * a puzzle's difficulty in one go by trying to solve it at
 503      * maximum difficulty and seeing what difficulty value was
 504      * returned; but with this hack, solving an Easy puzzle on
 505      * Normal difficulty will typically return Normal. Hence the
 506      * uses of the solver to determine difficulty are all arranged
 507      * so as to double-check by re-solving at the next difficulty
 508      * level down and making sure it failed.
 509      */
 510     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 511     if (ctx->diff > DIFF_EASY)
 512         return 0;
 513     return solver_common(solver, vctx, DIFF_EASY);
 514 }
 515
 516 static int solver_normal(struct latin_solver *solver, void *vctx)
 517 {
 518     return solver_common(solver, vctx, DIFF_NORMAL);
 519 }
 520
 521 static int solver_hard(struct latin_solver *solver, void *vctx)
 522 {
 523     return solver_common(solver, vctx, DIFF_HARD);
 524 }
 525
 526 #define SOLVER(upper,title,func,lower) func,
 527 static usersolver_t const keen_solvers[] = { DIFFLIST(SOLVER) };
 528
 529 static int solver(int w, int *dsf, long *clues, digit *soln, int maxdiff)
 530 {
 531     int a = w*w;
 532     struct solver_ctx ctx;
 533     int ret;
 534     int i, j, n, m;
 535
 536     ctx.w = w;
 537     ctx.soln = soln;
 538     ctx.diff = maxdiff;
 539
 540     /*
 541      * Transform the dsf-formatted clue list into one over which we
 542      * can iterate more easily.
 543      *
 544      * Also transpose the x- and y-coordinates at this point,
 545      * because the 'cube' array in the general Latin square solver
 546      * puts x first (oops).
 547      */
 548     for (ctx.nboxes = i = 0; i < a; i++)
 549         if (dsf_canonify(dsf, i) == i)
 550             ctx.nboxes++;
 551     ctx.boxlist = snewn(a, int);
 552     ctx.boxes = snewn(ctx.nboxes+1, int);
 553     ctx.clues = snewn(ctx.nboxes, long);
 554     ctx.whichbox = snewn(a, int);
 555     for (n = m = i = 0; i < a; i++)
 556         if (dsf_canonify(dsf, i) == i) {
 557             ctx.clues[n] = clues[i];
 558             ctx.boxes[n] = m;
 559             for (j = 0; j < a; j++)
 560                 if (dsf_canonify(dsf, j) == i) {
 561                     ctx.boxlist[m++] = (j % w) * w + (j / w);   /* transpose */
 562                     ctx.whichbox[ctx.boxlist[m-1]] = n;
 563                 }
 564             n++;
 565         }
 566     assert(n == ctx.nboxes);
 567     assert(m == a);
 568     ctx.boxes[n] = m;
 569
 570     ctx.dscratch = snewn(a+1, digit);
 571     ctx.iscratch = snewn(max(a+1, 4*w), int);
 572
 573     ret = latin_solver(soln, w, maxdiff,
 574                        DIFF_EASY, DIFF_HARD, DIFF_EXTREME,
 575                        DIFF_EXTREME, DIFF_UNREASONABLE,
 576                        keen_solvers, &ctx, NULL, NULL);
 577
 578     sfree(ctx.dscratch);
 579     sfree(ctx.iscratch);
 580     sfree(ctx.whichbox);
 581     sfree(ctx.boxlist);
 582     sfree(ctx.boxes);
 583     sfree(ctx.clues);
 584
 585     return ret;
 586 }
 587
 588 /* ----------------------------------------------------------------------
 589  * Grid generation.
 590  */
 591
 592 static char *encode_block_structure(char *p, int w, int *dsf)
 593 {
 594     int i, currrun = 0;
 595     char *orig, *q, *r, c;
 596
 597     orig = p;
 598
 599     /*
 600      * Encode the block structure. We do this by encoding the
 601      * pattern of dividing lines: first we iterate over the w*(w-1)
 602      * internal vertical grid lines in ordinary reading order, then
 603      * over the w*(w-1) internal horizontal ones in transposed
 604      * reading order.
 605      *
 606      * We encode the number of non-lines between the lines; _ means
 607      * zero (two adjacent divisions), a means 1, ..., y means 25,
 608      * and z means 25 non-lines _and no following line_ (so that za
 609      * means 26, zb 27 etc).
 610      */
 611     for (i = 0; i <= 2*w*(w-1); i++) {
 612         int x, y, p0, p1, edge;
 613
 614         if (i == 2*w*(w-1)) {
 615             edge = TRUE;       /* terminating virtual edge */
 616         } else {
 617             if (i < w*(w-1)) {
 618                 y = i/(w-1);
 619                 x = i%(w-1);
 620                 p0 = y*w+x;
 621                 p1 = y*w+x+1;
 622             } else {
 623                 x = i/(w-1) - w;
 624                 y = i%(w-1);
 625                 p0 = y*w+x;
 626                 p1 = (y+1)*w+x;
 627             }
 628             edge = (dsf_canonify(dsf, p0) != dsf_canonify(dsf, p1));
 629         }
 630
 631         if (edge) {
 632             while (currrun > 25)
 633                 *p++ = 'z', currrun -= 25;
 634             if (currrun)
 635                 *p++ = 'a'-1 + currrun;
 636             else
 637                 *p++ = '_';
 638             currrun = 0;
 639         } else
 640             currrun++;
 641     }
 642
 643     /*
 644      * Now go through and compress the string by replacing runs of
 645      * the same letter with a single copy of that letter followed by
 646      * a repeat count, where that makes it shorter. (This puzzle
 647      * seems to generate enough long strings of _ to make this a
 648      * worthwhile step.)
 649      */
 650     for (q = r = orig; r < p ;) {
 651         *q++ = c = *r;
 652
 653         for (i = 0; r+i < p && r[i] == c; i++);
 654         r += i;
 655
 656         if (i == 2) {
 657             *q++ = c;
 658         } else if (i > 2) {
 659             q += sprintf(q, "%d", i);
 660         }
 661     }
 662
 663     return q;
 664 }
 665
 666 static char *parse_block_structure(const char **p, int w, int *dsf)
 667 {
 668     int a = w*w;
 669     int pos = 0;
 670     int repc = 0, repn = 0;
 671
 672     dsf_init(dsf, a);
 673
 674     while (**p && (repn > 0 || **p != ',')) {
 675         int c, adv;
 676
 677         if (repn > 0) {
 678             repn--;
 679             c = repc;
 680         } else if (**p == '_' || (**p >= 'a' && **p <= 'z')) {
 681             c = (**p == '_' ? 0 : **p - 'a' + 1);
 682             (*p)++;
 683             if (**p && isdigit((unsigned char)**p)) {
 684                 repc = c;
 685                 repn = atoi(*p)-1;
 686                 while (**p && isdigit((unsigned char)**p)) (*p)++;
 687             }
 688         } else
 689             return "Invalid character in game description";
 690
 691         adv = (c != 25);               /* 'z' is a special case */
 692
 693         while (c-- > 0) {
 694             int p0, p1;
 695
 696             /*
 697              * Non-edge; merge the two dsf classes on either
 698              * side of it.
 699              */
 700             if (pos >= 2*w*(w-1))
 701                 return "Too much data in block structure specification";
 702             if (pos < w*(w-1)) {
 703                 int y = pos/(w-1);
 704                 int x = pos%(w-1);
 705                 p0 = y*w+x;
 706                 p1 = y*w+x+1;
 707             } else {
 708                 int x = pos/(w-1) - w;
 709                 int y = pos%(w-1);
 710                 p0 = y*w+x;
 711                 p1 = (y+1)*w+x;
 712             }
 713             dsf_merge(dsf, p0, p1);
 714
 715             pos++;
 716         }
 717         if (adv) {
 718             pos++;
 719             if (pos > 2*w*(w-1)+1)
 720                 return "Too much data in block structure specification";
 721         }
 722     }
 723
 724     /*
 725      * When desc is exhausted, we expect to have gone exactly
 726      * one space _past_ the end of the grid, due to the dummy
 727      * edge at the end.
 728      */
 729     if (pos != 2*w*(w-1)+1)
 730         return "Not enough data in block structure specification";
 731
 732     return NULL;
 733 }
 734
 735 static char *new_game_desc(game_params *params, random_state *rs,
 736                            char **aux, int interactive)
 737 {
 738     int w = params->w, a = w*w;
 739     digit *grid, *soln;
 740     int *order, *revorder, *singletons, *dsf;
 741     long *clues, *cluevals;
 742     int i, j, k, n, x, y, ret;
 743     int diff = params->diff;
 744     char *desc, *p;
 745
 746     /*
 747      * Difficulty exceptions: 3x3 puzzles at difficulty Hard or
 748      * higher are currently not generable - the generator will spin
 749      * forever looking for puzzles of the appropriate difficulty. We
 750      * dial each of these down to the next lower difficulty.
 751      *
 752      * Remember to re-test this whenever a change is made to the
 753      * solver logic!
 754      *
 755      * I tested it using the following shell command:
 756
 757 for d in e n h x u; do
 758   for i in {3..9}; do
 759     echo ./keen --generate 1 ${i}d${d}
 760     perl -e 'alarm 30; exec @ARGV' ./keen --generate 5 ${i}d${d} >/dev/null \
 761       || echo broken
 762   done
 763 done
 764
 765      * Of course, it's better to do that after taking the exceptions
 766      * _out_, so as to detect exceptions that should be removed as
 767      * well as those which should be added.
 768      */
 769     if (w == 3 && diff > DIFF_NORMAL)
 770         diff = DIFF_NORMAL;
 771
 772     grid = NULL;
 773
 774     order = snewn(a, int);
 775     revorder = snewn(a, int);
 776     singletons = snewn(a, int);
 777     dsf = snew_dsf(a);
 778     clues = snewn(a, long);
 779     cluevals = snewn(a, long);
 780     soln = snewn(a, digit);
 781
 782     while (1) {
 783         /*
 784          * First construct a latin square to be the solution.
 785          */
 786         sfree(grid);
 787         grid = latin_generate(w, rs);
 788
 789         /*
 790          * Divide the grid into arbitrarily sized blocks, but so as
 791          * to arrange plenty of dominoes which can be SUB/DIV clues.
 792          * We do this by first placing dominoes at random for a
 793          * while, then tying the remaining singletons one by one
 794          * into neighbouring blocks.
 795          */
 796         for (i = 0; i < a; i++)
 797             order[i] = i;
 798         shuffle(order, a, sizeof(*order), rs);
 799         for (i = 0; i < a; i++)
 800             revorder[order[i]] = i;
 801
 802         for (i = 0; i < a; i++)
 803             singletons[i] = TRUE;
 804
 805         dsf_init(dsf, a);
 806
 807         /* Place dominoes. */
 808         for (i = 0; i < a; i++) {
 809             if (singletons[i]) {
 810                 int best = -1;
 811
 812                 x = i % w;
 813                 y = i / w;
 814
 815                 if (x > 0 && singletons[i-1] &&
 816                     (best == -1 || revorder[i-1] < revorder[best]))
 817                     best = i-1;
 818                 if (x+1 < w && singletons[i+1] &&
 819                     (best == -1 || revorder[i+1] < revorder[best]))
 820                     best = i+1;
 821                 if (y > 0 && singletons[i-w] &&
 822                     (best == -1 || revorder[i-w] < revorder[best]))
 823                     best = i-w;
 824                 if (y+1 < w && singletons[i+w] &&
 825                     (best == -1 || revorder[i+w] < revorder[best]))
 826                     best = i+w;
 827
 828                 /*
 829                  * When we find a potential domino, we place it with
 830                  * probability 3/4, which seems to strike a decent
 831                  * balance between plenty of dominoes and leaving
 832                  * enough singletons to make interesting larger
 833                  * shapes.
 834                  */
 835                 if (best >= 0 && random_upto(rs, 4)) {
 836                     singletons[i] = singletons[best] = FALSE;
 837                     dsf_merge(dsf, i, best);
 838                 }
 839             }
 840         }
 841
 842         /* Fold in singletons. */
 843         for (i = 0; i < a; i++) {
 844             if (singletons[i]) {
 845                 int best = -1;
 846
 847                 x = i % w;
 848                 y = i / w;
 849
 850                 if (x > 0 &&
 851                     (best == -1 || revorder[i-1] < revorder[best]))
 852                     best = i-1;
 853                 if (x+1 < w &&
 854                     (best == -1 || revorder[i+1] < revorder[best]))
 855                     best = i+1;
 856                 if (y > 0 &&
 857                     (best == -1 || revorder[i-w] < revorder[best]))
 858                     best = i-w;
 859                 if (y+1 < w &&
 860                     (best == -1 || revorder[i+w] < revorder[best]))
 861                     best = i+w;
 862
 863                 if (best >= 0) {
 864                     singletons[i] = FALSE;
 865                     dsf_merge(dsf, i, best);
 866                 }
 867             }
 868         }
 869
 870         /*
 871          * Decide what would be acceptable clues for each block.
 872          *
 873          * Blocks larger than 2 have free choice of ADD or MUL;
 874          * blocks of size 2 can be anything in principle (except
 875          * that they can only be DIV if the two numbers have an
 876          * integer quotient, of course), but we rule out (or try to
 877          * avoid) some clues because they're of low quality.
 878          *
 879          * Hence, we iterate once over the grid, stopping at the
 880          * canonical element of every >2 block and the _non_-
 881          * canonical element of every 2-block; the latter means that
 882          * we can make our decision about a 2-block in the knowledge
 883          * of both numbers in it.
 884          *
 885          * We reuse the 'singletons' array (finished with in the
 886          * above loop) to hold information about which blocks are
 887          * suitable for what.
 888          */
 889 #define F_ADD     0x01
 890 #define F_SUB     0x02
 891 #define F_MUL     0x04
 892 #define F_DIV     0x08
 893 #define BAD_SHIFT 4
 894
 895         for (i = 0; i < a; i++) {
 896             singletons[i] = 0;
 897             j = dsf_canonify(dsf, i);
 898             k = dsf_size(dsf, j);
 899             if (j == i && k > 2) {
 900                 singletons[j] |= F_ADD | F_MUL;
 901             } else if (j != i && k == 2) {
 902                 /* Fetch the two numbers and sort them into order. */
 903                 int p = grid[j], q = grid[i], v;
 904                 if (p < q) {
 905                     int t = p; p = q; q = t;
 906                 }
 907
 908                 /*
 909                  * Addition clues are always allowed, but we try to
 910                  * avoid sums of 3, 4, (2w-1) and (2w-2) if we can,
 911                  * because they're too easy - they only leave one
 912                  * option for the pair of numbers involved.
 913                  */
 914                 v = p + q;
 915                 if (v > 4 && v < 2*w-2)
 916                     singletons[j] |= F_ADD;
 917                 else
 918                     singletons[j] |= F_ADD << BAD_SHIFT;
 919
 920                 /*
 921                  * Multiplication clues: above Normal difficulty, we
 922                  * prefer (but don't absolutely insist on) clues of
 923                  * this type which leave multiple options open.
 924                  */
 925                 v = p * q;
 926                 n = 0;
 927                 for (k = 1; k <= w; k++)
 928                     if (v % k == 0 && v / k <= w && v / k != k)
 929                         n++;
 930                 if (n <= 2 && diff > DIFF_NORMAL)
 931                     singletons[j] |= F_MUL << BAD_SHIFT;
 932                 else
 933                     singletons[j] |= F_MUL;
 934
 935                 /*
 936                  * Subtraction: we completely avoid a difference of
 937                  * w-1.
 938                  */
 939                 v = p - q;
 940                 if (v < w-1)
 941                     singletons[j] |= F_SUB;
 942
 943                 /*
 944                  * Division: for a start, the quotient must be an
 945                  * integer or the clue type is impossible. Also, we
 946                  * never use quotients strictly greater than w/2,
 947                  * because they're not only too easy but also
 948                  * inelegant.
 949                  */
 950                 if (p % q == 0 && 2 * (p / q) <= w)
 951                     singletons[j] |= F_DIV;
 952             }
 953         }
 954
 955         /*
 956          * Actually choose a clue for each block, trying to keep the
 957          * numbers of each type even, and starting with the
 958          * preferred candidates for each type where possible.
 959          *
 960          * I'm sure there should be a faster algorithm for doing
 961          * this, but I can't be bothered: O(N^2) is good enough when
 962          * N is at most the number of dominoes that fits into a 9x9
 963          * square.
 964          */
 965         shuffle(order, a, sizeof(*order), rs);
 966         for (i = 0; i < a; i++)
 967             clues[i] = 0;
 968         while (1) {
 969             int done_something = FALSE;
 970
 971             for (k = 0; k < 4; k++) {
 972                 long clue;
 973                 int good, bad;
 974                 switch (k) {
 975                   case 0:                clue = C_DIV; good = F_DIV; break;
 976                   case 1:                clue = C_SUB; good = F_SUB; break;
 977                   case 2:                clue = C_MUL; good = F_MUL; break;
 978                   default /* case 3 */ : clue = C_ADD; good = F_ADD; break;
 979                 }
 980
 981                 for (i = 0; i < a; i++) {
 982                     j = order[i];
 983                     if (singletons[j] & good) {
 984                         clues[j] = clue;
 985                         singletons[j] = 0;
 986                         break;
 987                     }
 988                 }
 989                 if (i == a) {
 990                     /* didn't find a nice one, use a nasty one */
 991                     bad = good << BAD_SHIFT;
 992                     for (i = 0; i < a; i++) {
 993                         j = order[i];
 994                         if (singletons[j] & bad) {
 995                             clues[j] = clue;
 996                             singletons[j] = 0;
 997                             break;
 998                         }
 999                     }
1000                 }
1001                 if (i < a)
1002                     done_something = TRUE;
1003             }
1004
1005             if (!done_something)
1006                 break;
1007         }
1008 #undef F_ADD
1009 #undef F_SUB
1010 #undef F_MUL
1011 #undef F_DIV
1012 #undef BAD_SHIFT
1013
1014         /*
1015          * Having chosen the clue types, calculate the clue values.
1016          */
1017         for (i = 0; i < a; i++) {
1018             j = dsf_canonify(dsf, i);
1019             if (j == i) {
1020                 cluevals[j] = grid[i];
1021             } else {
1022                 switch (clues[j]) {
1023                   case C_ADD:
1024                     cluevals[j] += grid[i];
1025                     break;
1026                   case C_MUL:
1027                     cluevals[j] *= grid[i];
1028                     break;
1029                   case C_SUB:
1030                     cluevals[j] = abs(cluevals[j] - grid[i]);
1031                     break;
1032                   case C_DIV:
1033                     {
1034                         int d1 = cluevals[j], d2 = grid[i];
1035                         if (d1 == 0 || d2 == 0)
1036                             cluevals[j] = 0;
1037                         else
1038                             cluevals[j] = d2/d1 + d1/d2;/* one is 0 :-) */
1039                     }
1040                     break;
1041                 }
1042             }
1043         }
1044
1045         for (i = 0; i < a; i++) {
1046             j = dsf_canonify(dsf, i);
1047             if (j == i) {
1048                 clues[j] |= cluevals[j];
1049             }
1050         }
1051
1052         /*
1053          * See if the game can be solved at the specified difficulty
1054          * level, but not at the one below.
1055          */
1056         if (diff > 0) {
1057             memset(soln, 0, a);
1058             ret = solver(w, dsf, clues, soln, diff-1);
1059             if (ret <= diff-1)
1060                 continue;
1061         }
1062         memset(soln, 0, a);
1063         ret = solver(w, dsf, clues, soln, diff);
1064         if (ret != diff)
1065             continue;                  /* go round again */
1066
1067         /*
1068          * I wondered if at this point it would be worth trying to
1069          * merge adjacent blocks together, to make the puzzle
1070          * gradually more difficult if it's currently easier than
1071          * specced, increasing the chance of a given generation run
1072          * being successful.
1073          *
1074          * It doesn't seem to be critical for the generation speed,
1075          * though, so for the moment I'm leaving it out.
1076          */
1077
1078         /*
1079          * We've got a usable puzzle!
1080          */
1081         break;
1082     }
1083
1084     /*
1085      * Encode the puzzle description.
1086      */
1087     desc = snewn(40*a, char);
1088     p = desc;
1089     p = encode_block_structure(p, w, dsf);
1090     *p++ = ',';
1091     for (i = 0; i < a; i++) {
1092         j = dsf_canonify(dsf, i);
1093         if (j == i) {
1094             switch (clues[j] & CMASK) {
1095               case C_ADD: *p++ = 'a'; break;
1096               case C_SUB: *p++ = 's'; break;
1097               case C_MUL: *p++ = 'm'; break;
1098               case C_DIV: *p++ = 'd'; break;
1099             }
1100             p += sprintf(p, "%ld", clues[j] & ~CMASK);
1101         }
1102     }
1103     *p++ = '\0';
1104     desc = sresize(desc, p - desc, char);
1105
1106     /*
1107      * Encode the solution.
1108      */
1109     assert(memcmp(soln, grid, a) == 0);
1110     *aux = snewn(a+2, char);
1111     (*aux)[0] = 'S';
1112     for (i = 0; i < a; i++)
1113         (*aux)[i+1] = '0' + soln[i];
1114     (*aux)[a+1] = '\0';
1115
1116     sfree(grid);
1117     sfree(order);
1118     sfree(revorder);
1119     sfree(singletons);
1120     sfree(dsf);
1121     sfree(clues);
1122     sfree(cluevals);
1123     sfree(soln);
1124
1125     return desc;
1126 }
1127
1128 /* ----------------------------------------------------------------------
1129  * Gameplay.
1130  */
1131
1132 static char *validate_desc(game_params *params, char *desc)
1133 {
1134     int w = params->w, a = w*w;
1135     int *dsf;
1136     char *ret;
1137     const char *p = desc;
1138     int i;
1139
1140     /*
1141      * Verify that the block structure makes sense.
1142      */
1143     dsf = snew_dsf(a);
1144     ret = parse_block_structure(&p, w, dsf);
1145     if (ret) {
1146         sfree(dsf);
1147         return ret;
1148     }
1149
1150     if (*p != ',')
1151         return "Expected ',' after block structure description";
1152     p++;
1153
1154     /*
1155      * Verify that the right number of clues are given, and that SUB
1156      * and DIV clues don't apply to blocks of the wrong size.
1157      */
1158     for (i = 0; i < a; i++) {
1159         if (dsf_canonify(dsf, i) == i) {
1160             if (*p == 'a' || *p == 'm') {
1161                 /* these clues need no validation */
1162             } else if (*p == 'd' || *p == 's') {
1163                 if (dsf_size(dsf, i) != 2)
1164                     return "Subtraction and division blocks must have area 2";
1165             } else if (!*p) {
1166                 return "Too few clues for block structure";
1167             } else {
1168                 return "Unrecognised clue type";
1169             }
1170             p++;
1171             while (*p && isdigit((unsigned char)*p)) p++;
1172         }
1173     }
1174     if (*p)
1175         return "Too many clues for block structure";
1176
1177     return NULL;
1178 }
1179
1180 static game_state *new_game(midend *me, game_params *params, char *desc)
1181 {
1182     int w = params->w, a = w*w;
1183     game_state *state = snew(game_state);
1184     const char *p = desc;
1185     int i;
1186
1187     state->par = *params;              /* structure copy */
1188     state->clues = snew(struct clues);
1189     state->clues->refcount = 1;
1190     state->clues->w = w;
1191     state->clues->dsf = snew_dsf(a);
1192     parse_block_structure(&p, w, state->clues->dsf);
1193
1194     assert(*p == ',');
1195     p++;
1196
1197     state->clues->clues = snewn(a, long);
1198     for (i = 0; i < a; i++) {
1199         if (dsf_canonify(state->clues->dsf, i) == i) {
1200             long clue = 0;
1201             switch (*p) {
1202               case 'a':
1203                 clue = C_ADD;
1204                 break;
1205               case 'm':
1206                 clue = C_MUL;
1207                 break;
1208               case 's':
1209                 clue = C_SUB;
1210                 assert(dsf_size(state->clues->dsf, i) == 2);
1211                 break;
1212               case 'd':
1213                 clue = C_DIV;
1214                 assert(dsf_size(state->clues->dsf, i) == 2);
1215                 break;
1216               default:
1217                 assert(!"Bad description in new_game");
1218             }
1219             p++;
1220             clue |= atol(p);
1221             while (*p && isdigit((unsigned char)*p)) p++;
1222             state->clues->clues[i] = clue;
1223         } else
1224             state->clues->clues[i] = 0;
1225     }
1226
1227     state->grid = snewn(a, digit);
1228     state->pencil = snewn(a, int);
1229     for (i = 0; i < a; i++) {
1230         state->grid[i] = 0;
1231         state->pencil[i] = 0;
1232     }
1233
1234     state->completed = state->cheated = FALSE;
1235
1236     return state;
1237 }
1238
1239 static game_state *dup_game(game_state *state)
1240 {
1241     int w = state->par.w, a = w*w;
1242     game_state *ret = snew(game_state);
1243
1244     ret->par = state->par;             /* structure copy */
1245
1246     ret->clues = state->clues;
1247     ret->clues->refcount++;
1248
1249     ret->grid = snewn(a, digit);
1250     ret->pencil = snewn(a, int);
1251     memcpy(ret->grid, state->grid, a*sizeof(digit));
1252     memcpy(ret->pencil, state->pencil, a*sizeof(int));
1253
1254     ret->completed = state->completed;
1255     ret->cheated = state->cheated;
1256
1257     return ret;
1258 }
1259
1260 static void free_game(game_state *state)
1261 {
1262     sfree(state->grid);
1263     sfree(state->pencil);
1264     if (--state->clues->refcount <= 0) {
1265         sfree(state->clues->dsf);
1266         sfree(state->clues->clues);
1267         sfree(state->clues);
1268     }
1269     sfree(state);
1270 }
1271
1272 static char *solve_game(game_state *state, game_state *currstate,
1273                         char *aux, char **error)
1274 {
1275     int w = state->par.w, a = w*w;
1276     int i, ret;
1277     digit *soln;
1278     char *out;
1279
1280     if (aux)
1281         return dupstr(aux);
1282
1283     soln = snewn(a, digit);
1284     memset(soln, 0, a);
1285
1286     ret = solver(w, state->clues->dsf, state->clues->clues,
1287                  soln, DIFFCOUNT-1);
1288
1289     if (ret == diff_impossible) {
1290         *error = "No solution exists for this puzzle";
1291         out = NULL;
1292     } else if (ret == diff_ambiguous) {
1293         *error = "Multiple solutions exist for this puzzle";
1294         out = NULL;
1295     } else {
1296         out = snewn(a+2, char);
1297         out[0] = 'S';
1298         for (i = 0; i < a; i++)
1299             out[i+1] = '0' + soln[i];
1300         out[a+1] = '\0';
1301     }
1302
1303     sfree(soln);
1304     return out;
1305 }
1306
1307 static int game_can_format_as_text_now(game_params *params)
1308 {
1309     return TRUE;
1310 }
1311
1312 static char *game_text_format(game_state *state)
1313 {
1314     return NULL;
1315 }
1316
1317 struct game_ui {
1318     /*
1319      * These are the coordinates of the currently highlighted
1320      * square on the grid, if hshow = 1.
1321      */
1322     int hx, hy;
1323     /*
1324      * This indicates whether the current highlight is a
1325      * pencil-mark one or a real one.
1326      */
1327     int hpencil;
1328     /*
1329      * This indicates whether or not we're showing the highlight
1330      * (used to be hx = hy = -1); important so that when we're
1331      * using the cursor keys it doesn't keep coming back at a
1332      * fixed position. When hshow = 1, pressing a valid number
1333      * or letter key or Space will enter that number or letter in the grid.
1334      */
1335     int hshow;
1336     /*
1337      * This indicates whether we're using the highlight as a cursor;
1338      * it means that it doesn't vanish on a keypress, and that it is
1339      * allowed on immutable squares.
1340      */
1341     int hcursor;
1342 };
1343
1344 static game_ui *new_ui(game_state *state)
1345 {
1346     game_ui *ui = snew(game_ui);
1347
1348     ui->hx = ui->hy = 0;
1349     ui->hpencil = ui->hshow = ui->hcursor = 0;
1350
1351     return ui;
1352 }
1353
1354 static void free_ui(game_ui *ui)
1355 {
1356     sfree(ui);
1357 }
1358
1359 static char *encode_ui(game_ui *ui)
1360 {
1361     return NULL;
1362 }
1363
1364 static void decode_ui(game_ui *ui, char *encoding)
1365 {
1366 }
1367
1368 static void game_changed_state(game_ui *ui, game_state *oldstate,
1369                                game_state *newstate)
1370 {
1371     int w = newstate->par.w;
1372     /*
1373      * We prevent pencil-mode highlighting of a filled square, unless
1374      * we're using the cursor keys. So if the user has just filled in
1375      * a square which we had a pencil-mode highlight in (by Undo, or
1376      * by Redo, or by Solve), then we cancel the highlight.
1377      */
1378     if (ui->hshow && ui->hpencil && !ui->hcursor &&
1379         newstate->grid[ui->hy * w + ui->hx] != 0) {
1380         ui->hshow = 0;
1381     }
1382 }
1383
1384 #define PREFERRED_TILESIZE 48
1385 #define TILESIZE (ds->tilesize)
1386 #define BORDER (TILESIZE / 2)
1387 #define GRIDEXTRA max((TILESIZE / 32),1)
1388 #define COORD(x) ((x)*TILESIZE + BORDER)
1389 #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1)
1390
1391 #define FLASH_TIME 0.4F
1392
1393 #define DF_PENCIL_SHIFT 16
1394 #define DF_ERR_LATIN 0x8000
1395 #define DF_ERR_CLUE 0x4000
1396 #define DF_HIGHLIGHT 0x2000
1397 #define DF_HIGHLIGHT_PENCIL 0x1000
1398 #define DF_DIGIT_MASK 0x000F
1399
1400 struct game_drawstate {
1401     int tilesize;
1402     int started;
1403     long *tiles;
1404     long *errors;
1405     char *minus_sign, *times_sign, *divide_sign;
1406 };
1407
1408 static int check_errors(game_state *state, long *errors)
1409 {
1410     int w = state->par.w, a = w*w;
1411     int i, j, x, y, errs = FALSE;
1412     long *cluevals;
1413     int *full;
1414
1415     cluevals = snewn(a, long);
1416     full = snewn(a, int);
1417
1418     if (errors)
1419         for (i = 0; i < a; i++) {
1420             errors[i] = 0;
1421             full[i] = TRUE;
1422         }
1423
1424     for (i = 0; i < a; i++) {
1425         long clue;
1426
1427         j = dsf_canonify(state->clues->dsf, i);
1428         if (j == i) {
1429             cluevals[i] = state->grid[i];
1430         } else {
1431             clue = state->clues->clues[j] & CMASK;
1432
1433             switch (clue) {
1434               case C_ADD:
1435                 cluevals[j] += state->grid[i];
1436                 break;
1437               case C_MUL:
1438                 cluevals[j] *= state->grid[i];
1439                 break;
1440               case C_SUB:
1441                 cluevals[j] = abs(cluevals[j] - state->grid[i]);
1442                 break;
1443               case C_DIV:
1444                 {
1445                     int d1 = min(cluevals[j], state->grid[i]);
1446                     int d2 = max(cluevals[j], state->grid[i]);
1447                     if (d1 == 0 || d2 % d1 != 0)
1448                         cluevals[j] = 0;
1449                     else
1450                         cluevals[j] = d2 / d1;
1451                 }
1452                 break;
1453             }
1454         }
1455
1456         if (!state->grid[i])
1457             full[j] = FALSE;
1458     }
1459
1460     for (i = 0; i < a; i++) {
1461         j = dsf_canonify(state->clues->dsf, i);
1462         if (j == i) {
1463             if ((state->clues->clues[j] & ~CMASK) != cluevals[i]) {
1464                 errs = TRUE;
1465                 if (errors && full[j])
1466                     errors[j] |= DF_ERR_CLUE;
1467             }
1468         }
1469     }
1470
1471     sfree(cluevals);
1472     sfree(full);
1473
1474     for (y = 0; y < w; y++) {
1475         int mask = 0, errmask = 0;
1476         for (x = 0; x < w; x++) {
1477             int bit = 1 << state->grid[y*w+x];
1478             errmask |= (mask & bit);
1479             mask |= bit;
1480         }
1481
1482         if (mask != (1 << (w+1)) - (1 << 1)) {
1483             errs = TRUE;
1484             errmask &= ~1;
1485             if (errors) {
1486                 for (x = 0; x < w; x++)
1487                     if (errmask & (1 << state->grid[y*w+x]))
1488                         errors[y*w+x] |= DF_ERR_LATIN;
1489             }
1490         }
1491     }
1492
1493     for (x = 0; x < w; x++) {
1494         int mask = 0, errmask = 0;
1495         for (y = 0; y < w; y++) {
1496             int bit = 1 << state->grid[y*w+x];
1497             errmask |= (mask & bit);
1498             mask |= bit;
1499         }
1500
1501         if (mask != (1 << (w+1)) - (1 << 1)) {
1502             errs = TRUE;
1503             errmask &= ~1;
1504             if (errors) {
1505                 for (y = 0; y < w; y++)
1506                     if (errmask & (1 << state->grid[y*w+x]))
1507                         errors[y*w+x] |= DF_ERR_LATIN;
1508             }
1509         }
1510     }
1511
1512     return errs;
1513 }
1514
1515 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1516                             int x, int y, int button)
1517 {
1518     int w = state->par.w;
1519     int tx, ty;
1520     char buf[80];
1521
1522     button &= ~MOD_MASK;
1523
1524     tx = FROMCOORD(x);
1525     ty = FROMCOORD(y);
1526
1527     if (tx >= 0 && tx < w && ty >= 0 && ty < w) {
1528         if (button == LEFT_BUTTON) {
1529             if (tx == ui->hx && ty == ui->hy &&
1530                 ui->hshow && ui->hpencil == 0) {
1531                 ui->hshow = 0;
1532             } else {
1533                 ui->hx = tx;
1534                 ui->hy = ty;
1535                 ui->hshow = 1;
1536                 ui->hpencil = 0;
1537             }
1538             ui->hcursor = 0;
1539             return "";                 /* UI activity occurred */
1540         }
1541         if (button == RIGHT_BUTTON) {
1542             /*
1543              * Pencil-mode highlighting for non filled squares.
1544              */
1545             if (state->grid[ty*w+tx] == 0) {
1546                 if (tx == ui->hx && ty == ui->hy &&
1547                     ui->hshow && ui->hpencil) {
1548                     ui->hshow = 0;
1549                 } else {
1550                     ui->hpencil = 1;
1551                     ui->hx = tx;
1552                     ui->hy = ty;
1553                     ui->hshow = 1;
1554                 }
1555             } else {
1556                 ui->hshow = 0;
1557             }
1558             ui->hcursor = 0;
1559             return "";                 /* UI activity occurred */
1560         }
1561     }
1562     if (IS_CURSOR_MOVE(button)) {
1563         move_cursor(button, &ui->hx, &ui->hy, w, w, 0);
1564         ui->hshow = ui->hcursor = 1;
1565         return "";
1566     }
1567     if (ui->hshow &&
1568         (button == CURSOR_SELECT)) {
1569         ui->hpencil = 1 - ui->hpencil;
1570         ui->hcursor = 1;
1571         return "";
1572     }
1573
1574     if (ui->hshow &&
1575         ((button >= '0' && button <= '9' && button - '0' <= w) ||
1576          button == CURSOR_SELECT2 || button == '\b')) {
1577         int n = button - '0';
1578         if (button == CURSOR_SELECT2 || button == '\b')
1579             n = 0;
1580
1581         /*
1582          * Can't make pencil marks in a filled square. This can only
1583          * become highlighted if we're using cursor keys.
1584          */
1585         if (ui->hpencil && state->grid[ui->hy*w+ui->hx])
1586             return NULL;
1587
1588         sprintf(buf, "%c%d,%d,%d",
1589                 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1590
1591         if (!ui->hcursor) ui->hshow = 0;
1592
1593         return dupstr(buf);
1594     }
1595
1596     if (button == 'M' || button == 'm')
1597         return dupstr("M");
1598
1599     return NULL;
1600 }
1601
1602 static game_state *execute_move(game_state *from, char *move)
1603 {
1604     int w = from->par.w, a = w*w;
1605     game_state *ret;
1606     int x, y, i, n;
1607
1608     if (move[0] == 'S') {
1609         ret = dup_game(from);
1610         ret->completed = ret->cheated = TRUE;
1611
1612         for (i = 0; i < a; i++) {
1613             if (move[i+1] < '1' || move[i+1] > '0'+w) {
1614                 free_game(ret);
1615                 return NULL;
1616             }
1617             ret->grid[i] = move[i+1] - '0';
1618             ret->pencil[i] = 0;
1619         }
1620
1621         if (move[a+1] != '\0') {
1622             free_game(ret);
1623             return NULL;
1624         }
1625
1626         return ret;
1627     } else if ((move[0] == 'P' || move[0] == 'R') &&
1628         sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1629         x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) {
1630
1631         ret = dup_game(from);
1632         if (move[0] == 'P' && n > 0) {
1633             ret->pencil[y*w+x] ^= 1 << n;
1634         } else {
1635             ret->grid[y*w+x] = n;
1636             ret->pencil[y*w+x] = 0;
1637
1638             if (!ret->completed && !check_errors(ret, NULL))
1639                 ret->completed = TRUE;
1640         }
1641         return ret;
1642     } else if (move[0] == 'M') {
1643         /*
1644          * Fill in absolutely all pencil marks everywhere. (I
1645          * wouldn't use this for actual play, but it's a handy
1646          * starting point when following through a set of
1647          * diagnostics output by the standalone solver.)
1648          */
1649         ret = dup_game(from);
1650         for (i = 0; i < a; i++) {
1651             if (!ret->grid[i])
1652                 ret->pencil[i] = (1 << (w+1)) - (1 << 1);
1653         }
1654         return ret;
1655     } else
1656         return NULL;                   /* couldn't parse move string */
1657 }
1658
1659 /* ----------------------------------------------------------------------
1660  * Drawing routines.
1661  */
1662
1663 #define SIZE(w) ((w) * TILESIZE + 2*BORDER)
1664
1665 static void game_compute_size(game_params *params, int tilesize,
1666                               int *x, int *y)
1667 {
1668     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1669     struct { int tilesize; } ads, *ds = &ads;
1670     ads.tilesize = tilesize;
1671
1672     *x = *y = SIZE(params->w);
1673 }
1674
1675 static void game_set_size(drawing *dr, game_drawstate *ds,
1676                           game_params *params, int tilesize)
1677 {
1678     ds->tilesize = tilesize;
1679 }
1680
1681 static float *game_colours(frontend *fe, int *ncolours)
1682 {
1683     float *ret = snewn(3 * NCOLOURS, float);
1684
1685     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1686
1687     ret[COL_GRID * 3 + 0] = 0.0F;
1688     ret[COL_GRID * 3 + 1] = 0.0F;
1689     ret[COL_GRID * 3 + 2] = 0.0F;
1690
1691     ret[COL_USER * 3 + 0] = 0.0F;
1692     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1693     ret[COL_USER * 3 + 2] = 0.0F;
1694
1695     ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
1696     ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
1697     ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
1698
1699     ret[COL_ERROR * 3 + 0] = 1.0F;
1700     ret[COL_ERROR * 3 + 1] = 0.0F;
1701     ret[COL_ERROR * 3 + 2] = 0.0F;
1702
1703     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1704     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1705     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1706
1707     *ncolours = NCOLOURS;
1708     return ret;
1709 }
1710
1711 static const char *const minus_signs[] = { "\xE2\x88\x92", "-" };
1712 static const char *const times_signs[] = { "\xC3\x97", "*" };
1713 static const char *const divide_signs[] = { "\xC3\xB7", "/" };
1714
1715 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1716 {
1717     int w = state->par.w, a = w*w;
1718     struct game_drawstate *ds = snew(struct game_drawstate);
1719     int i;
1720
1721     ds->tilesize = 0;
1722     ds->started = FALSE;
1723     ds->tiles = snewn(a, long);
1724     for (i = 0; i < a; i++)
1725         ds->tiles[i] = -1;
1726     ds->errors = snewn(a, long);
1727     ds->minus_sign = text_fallback(dr, minus_signs, lenof(minus_signs));
1728     ds->times_sign = text_fallback(dr, times_signs, lenof(times_signs));
1729     ds->divide_sign = text_fallback(dr, divide_signs, lenof(divide_signs));
1730
1731     return ds;
1732 }
1733
1734 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1735 {
1736     sfree(ds->tiles);
1737     sfree(ds->errors);
1738     sfree(ds->minus_sign);
1739     sfree(ds->times_sign);
1740     sfree(ds->divide_sign);
1741     sfree(ds);
1742 }
1743
1744 static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues,
1745                       int x, int y, long tile)
1746 {
1747     int w = clues->w /* , a = w*w */;
1748     int tx, ty, tw, th;
1749     int cx, cy, cw, ch;
1750     char str[64];
1751
1752     tx = BORDER + x * TILESIZE + 1 + GRIDEXTRA;
1753     ty = BORDER + y * TILESIZE + 1 + GRIDEXTRA;
1754
1755     cx = tx;
1756     cy = ty;
1757     cw = tw = TILESIZE-1-2*GRIDEXTRA;
1758     ch = th = TILESIZE-1-2*GRIDEXTRA;
1759
1760     if (x > 0 && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, y*w+x-1))
1761         cx -= GRIDEXTRA, cw += GRIDEXTRA;
1762     if (x+1 < w && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, y*w+x+1))
1763         cw += GRIDEXTRA;
1764     if (y > 0 && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, (y-1)*w+x))
1765         cy -= GRIDEXTRA, ch += GRIDEXTRA;
1766     if (y+1 < w && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, (y+1)*w+x))
1767         ch += GRIDEXTRA;
1768
1769     clip(dr, cx, cy, cw, ch);
1770
1771     /* background needs erasing */
1772     draw_rect(dr, cx, cy, cw, ch,
1773               (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND);
1774
1775     /*
1776      * Draw the corners of thick lines in corner-adjacent squares,
1777      * which jut into this square by one pixel.
1778      */
1779     if (x > 0 && y > 0 && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y-1)*w+x-1))
1780         draw_rect(dr, tx-GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
1781     if (x+1 < w && y > 0 && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y-1)*w+x+1))
1782         draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
1783     if (x > 0 && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x-1))
1784         draw_rect(dr, tx-GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
1785     if (x+1 < w && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x+1))
1786         draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
1787
1788     /* pencil-mode highlight */
1789     if (tile & DF_HIGHLIGHT_PENCIL) {
1790         int coords[6];
1791         coords[0] = cx;
1792         coords[1] = cy;
1793         coords[2] = cx+cw/2;
1794         coords[3] = cy;
1795         coords[4] = cx;
1796         coords[5] = cy+ch/2;
1797         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1798     }
1799
1800     /* Draw the box clue. */
1801     if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {
1802         long clue = clues->clues[y*w+x];
1803         long cluetype = clue & CMASK, clueval = clue & ~CMASK;
1804         int size = dsf_size(clues->dsf, y*w+x);
1805         /*
1806          * Special case of clue-drawing: a box with only one square
1807          * is written as just the number, with no operation, because
1808          * it doesn't matter whether the operation is ADD or MUL.
1809          * The generation code above should never produce puzzles
1810          * containing such a thing - I think they're inelegant - but
1811          * it's possible to type in game IDs from elsewhere, so I
1812          * want to display them right if so.
1813          */
1814         sprintf (str, "%ld%s", clueval,
1815                  (size == 1 ? "" :
1816                   cluetype == C_ADD ? "+" :
1817                   cluetype == C_SUB ? ds->minus_sign :
1818                   cluetype == C_MUL ? ds->times_sign :
1819                   /* cluetype == C_DIV ? */ ds->divide_sign));
1820         draw_text(dr, tx + GRIDEXTRA * 2, ty + GRIDEXTRA * 2 + TILESIZE/4,
1821                   FONT_VARIABLE, TILESIZE/4, ALIGN_VNORMAL | ALIGN_HLEFT,
1822                   (tile & DF_ERR_CLUE ? COL_ERROR : COL_GRID), str);
1823     }
1824
1825     /* new number needs drawing? */
1826     if (tile & DF_DIGIT_MASK) {
1827         str[1] = '\0';
1828         str[0] = (tile & DF_DIGIT_MASK) + '0';
1829         draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1830                   FONT_VARIABLE, TILESIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1831                   (tile & DF_ERR_LATIN) ? COL_ERROR : COL_USER, str);
1832     } else {
1833         int i, j, npencil;
1834         int pl, pr, pt, pb;
1835         float bestsize;
1836         int pw, ph, minph, pbest, fontsize;
1837
1838         /* Count the pencil marks required. */
1839         for (i = 1, npencil = 0; i <= w; i++)
1840             if (tile & (1L << (i + DF_PENCIL_SHIFT)))
1841                 npencil++;
1842         if (npencil) {
1843
1844             minph = 2;
1845
1846             /*
1847              * Determine the bounding rectangle within which we're going
1848              * to put the pencil marks.
1849              */
1850             /* Start with the whole square */
1851             pl = tx + GRIDEXTRA;
1852             pr = pl + TILESIZE - GRIDEXTRA;
1853             pt = ty + GRIDEXTRA;
1854             pb = pt + TILESIZE - GRIDEXTRA;
1855             if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {
1856                 /*
1857                  * Make space for the clue text.
1858                  */
1859                 pt += TILESIZE/4;
1860                 /* minph--; */
1861             }
1862
1863             /*
1864              * We arrange our pencil marks in a grid layout, with
1865              * the number of rows and columns adjusted to allow the
1866              * maximum font size.
1867              *
1868              * So now we work out what the grid size ought to be.
1869              */
1870             bestsize = 0.0;
1871             pbest = 0;
1872             /* Minimum */
1873             for (pw = 3; pw < max(npencil,4); pw++) {
1874                 float fw, fh, fs;
1875
1876                 ph = (npencil + pw - 1) / pw;
1877                 ph = max(ph, minph);
1878                 fw = (pr - pl) / (float)pw;
1879                 fh = (pb - pt) / (float)ph;
1880                 fs = min(fw, fh);
1881                 if (fs > bestsize) {
1882                     bestsize = fs;
1883                     pbest = pw;
1884                 }
1885             }
1886             assert(pbest > 0);
1887             pw = pbest;
1888             ph = (npencil + pw - 1) / pw;
1889             ph = max(ph, minph);
1890
1891             /*
1892              * Now we've got our grid dimensions, work out the pixel
1893              * size of a grid element, and round it to the nearest
1894              * pixel. (We don't want rounding errors to make the
1895              * grid look uneven at low pixel sizes.)
1896              */
1897             fontsize = min((pr - pl) / pw, (pb - pt) / ph);
1898
1899             /*
1900              * Centre the resulting figure in the square.
1901              */
1902             pl = tx + (TILESIZE - fontsize * pw) / 2;
1903             pt = ty + (TILESIZE - fontsize * ph) / 2;
1904
1905             /*
1906              * And move it down a bit if it's collided with some
1907              * clue text.
1908              */
1909             if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {
1910                 pt = max(pt, ty + GRIDEXTRA * 3 + TILESIZE/4);
1911             }
1912
1913             /*
1914              * Now actually draw the pencil marks.
1915              */
1916             for (i = 1, j = 0; i <= w; i++)
1917                 if (tile & (1L << (i + DF_PENCIL_SHIFT))) {
1918                     int dx = j % pw, dy = j / pw;
1919
1920                     str[1] = '\0';
1921                     str[0] = i + '0';
1922                     draw_text(dr, pl + fontsize * (2*dx+1) / 2,
1923                               pt + fontsize * (2*dy+1) / 2,
1924                               FONT_VARIABLE, fontsize,
1925                               ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1926                     j++;
1927                 }
1928         }
1929     }
1930
1931     unclip(dr);
1932
1933     draw_update(dr, cx, cy, cw, ch);
1934 }
1935
1936 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1937                         game_state *state, int dir, game_ui *ui,
1938                         float animtime, float flashtime)
1939 {
1940     int w = state->par.w /*, a = w*w */;
1941     int x, y;
1942
1943     if (!ds->started) {
1944         /*
1945          * The initial contents of the window are not guaranteed and
1946          * can vary with front ends. To be on the safe side, all
1947          * games should start by drawing a big background-colour
1948          * rectangle covering the whole window.
1949          */
1950         draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND);
1951
1952         /*
1953          * Big containing rectangle.
1954          */
1955         draw_rect(dr, COORD(0) - GRIDEXTRA, COORD(0) - GRIDEXTRA,
1956                   w*TILESIZE+1+GRIDEXTRA*2, w*TILESIZE+1+GRIDEXTRA*2,
1957                   COL_GRID);
1958
1959         draw_update(dr, 0, 0, SIZE(w), SIZE(w));
1960
1961         ds->started = TRUE;
1962     }
1963
1964     check_errors(state, ds->errors);
1965
1966     for (y = 0; y < w; y++) {
1967         for (x = 0; x < w; x++) {
1968             long tile = 0L;
1969
1970             if (state->grid[y*w+x])
1971                 tile = state->grid[y*w+x];
1972             else
1973                 tile = (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT;
1974
1975             if (ui->hshow && ui->hx == x && ui->hy == y)
1976                 tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT);
1977
1978             if (flashtime > 0 &&
1979                 (flashtime <= FLASH_TIME/3 ||
1980                  flashtime >= FLASH_TIME*2/3))
1981                 tile |= DF_HIGHLIGHT;  /* completion flash */
1982
1983             tile |= ds->errors[y*w+x];
1984
1985             if (ds->tiles[y*w+x] != tile) {
1986                 ds->tiles[y*w+x] = tile;
1987                 draw_tile(dr, ds, state->clues, x, y, tile);
1988             }
1989         }
1990     }
1991 }
1992
1993 static float game_anim_length(game_state *oldstate, game_state *newstate,
1994                               int dir, game_ui *ui)
1995 {
1996     return 0.0F;
1997 }
1998
1999 static float game_flash_length(game_state *oldstate, game_state *newstate,
2000                                int dir, game_ui *ui)
2001 {
2002     if (!oldstate->completed && newstate->completed &&
2003         !oldstate->cheated && !newstate->cheated)
2004         return FLASH_TIME;
2005     return 0.0F;
2006 }
2007
2008 static int game_is_solved(game_state *state)
2009 {
2010     return state->completed;
2011 }
2012
2013 static int game_timing_state(game_state *state, game_ui *ui)
2014 {
2015     if (state->completed)
2016         return FALSE;
2017     return TRUE;
2018 }
2019
2020 static void game_print_size(game_params *params, float *x, float *y)
2021 {
2022     int pw, ph;
2023
2024     /*
2025      * We use 9mm squares by default, like Solo.
2026      */
2027     game_compute_size(params, 900, &pw, &ph);
2028     *x = pw / 100.0F;
2029     *y = ph / 100.0F;
2030 }
2031
2032 /*
2033  * Subfunction to draw the thick lines between cells. In order to do
2034  * this using the line-drawing rather than rectangle-drawing API (so
2035  * as to get line thicknesses to scale correctly) and yet have
2036  * correctly mitred joins between lines, we must do this by tracing
2037  * the boundary of each sub-block and drawing it in one go as a
2038  * single polygon.
2039  */
2040 static void outline_block_structure(drawing *dr, game_drawstate *ds,
2041                                     int w, int *dsf, int ink)
2042 {
2043     int a = w*w;
2044     int *coords;
2045     int i, n;
2046     int x, y, dx, dy, sx, sy, sdx, sdy;
2047
2048     coords = snewn(4*a, int);
2049
2050     /*
2051      * Iterate over all the blocks.
2052      */
2053     for (i = 0; i < a; i++) {
2054         if (dsf_canonify(dsf, i) != i)
2055             continue;
2056
2057         /*
2058          * For each block, we need a starting square within it which
2059          * has a boundary at the left. Conveniently, we have one
2060          * right here, by construction.
2061          */
2062         x = i % w;
2063         y = i / w;
2064         dx = -1;
2065         dy = 0;
2066
2067         /*
2068          * Now begin tracing round the perimeter. At all
2069          * times, (x,y) describes some square within the
2070          * block, and (x+dx,y+dy) is some adjacent square
2071          * outside it; so the edge between those two squares
2072          * is always an edge of the block.
2073          */
2074         sx = x, sy = y, sdx = dx, sdy = dy;   /* save starting position */
2075         n = 0;
2076         do {
2077             int cx, cy, tx, ty, nin;
2078
2079             /*
2080              * Advance to the next edge, by looking at the two
2081              * squares beyond it. If they're both outside the block,
2082              * we turn right (by leaving x,y the same and rotating
2083              * dx,dy clockwise); if they're both inside, we turn
2084              * left (by rotating dx,dy anticlockwise and contriving
2085              * to leave x+dx,y+dy unchanged); if one of each, we go
2086              * straight on (and may enforce by assertion that
2087              * they're one of each the _right_ way round).
2088              */
2089             nin = 0;
2090             tx = x - dy + dx;
2091             ty = y + dx + dy;
2092             nin += (tx >= 0 && tx < w && ty >= 0 && ty < w &&
2093                     dsf_canonify(dsf, ty*w+tx) == i);
2094             tx = x - dy;
2095             ty = y + dx;
2096             nin += (tx >= 0 && tx < w && ty >= 0 && ty < w &&
2097                     dsf_canonify(dsf, ty*w+tx) == i);
2098             if (nin == 0) {
2099                 /*
2100                  * Turn right.
2101                  */
2102                 int tmp;
2103                 tmp = dx;
2104                 dx = -dy;
2105                 dy = tmp;
2106             } else if (nin == 2) {
2107                 /*
2108                  * Turn left.
2109                  */
2110                 int tmp;
2111
2112                 x += dx;
2113                 y += dy;
2114
2115                 tmp = dx;
2116                 dx = dy;
2117                 dy = -tmp;
2118
2119                 x -= dx;
2120                 y -= dy;
2121             } else {
2122                 /*
2123                  * Go straight on.
2124                  */
2125                 x -= dy;
2126                 y += dx;
2127             }
2128
2129             /*
2130              * Now enforce by assertion that we ended up
2131              * somewhere sensible.
2132              */
2133             assert(x >= 0 && x < w && y >= 0 && y < w &&
2134                    dsf_canonify(dsf, y*w+x) == i);
2135             assert(x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= w ||
2136                    dsf_canonify(dsf, (y+dy)*w+(x+dx)) != i);
2137
2138             /*
2139              * Record the point we just went past at one end of the
2140              * edge. To do this, we translate (x,y) down and right
2141              * by half a unit (so they're describing a point in the
2142              * _centre_ of the square) and then translate back again
2143              * in a manner rotated by dy and dx.
2144              */
2145             assert(n < 2*w+2);
2146             cx = ((2*x+1) + dy + dx) / 2;
2147             cy = ((2*y+1) - dx + dy) / 2;
2148             coords[2*n+0] = BORDER + cx * TILESIZE;
2149             coords[2*n+1] = BORDER + cy * TILESIZE;
2150             n++;
2151
2152         } while (x != sx || y != sy || dx != sdx || dy != sdy);
2153
2154         /*
2155          * That's our polygon; now draw it.
2156          */
2157         draw_polygon(dr, coords, n, -1, ink);
2158     }
2159
2160     sfree(coords);
2161 }
2162
2163 static void game_print(drawing *dr, game_state *state, int tilesize)
2164 {
2165     int w = state->par.w;
2166     int ink = print_mono_colour(dr, 0);
2167     int x, y;
2168     char *minus_sign, *times_sign, *divide_sign;
2169
2170     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2171     game_drawstate ads, *ds = &ads;
2172     game_set_size(dr, ds, NULL, tilesize);
2173
2174     minus_sign = text_fallback(dr, minus_signs, lenof(minus_signs));
2175     times_sign = text_fallback(dr, times_signs, lenof(times_signs));
2176     divide_sign = text_fallback(dr, divide_signs, lenof(divide_signs));
2177
2178     /*
2179      * Border.
2180      */
2181     print_line_width(dr, 3 * TILESIZE / 40);
2182     draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink);
2183
2184     /*
2185      * Main grid.
2186      */
2187     for (x = 1; x < w; x++) {
2188         print_line_width(dr, TILESIZE / 40);
2189         draw_line(dr, BORDER+x*TILESIZE, BORDER,
2190                   BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink);
2191     }
2192     for (y = 1; y < w; y++) {
2193         print_line_width(dr, TILESIZE / 40);
2194         draw_line(dr, BORDER, BORDER+y*TILESIZE,
2195                   BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink);
2196     }
2197
2198     /*
2199      * Thick lines between cells.
2200      */
2201     print_line_width(dr, 3 * TILESIZE / 40);
2202     outline_block_structure(dr, ds, w, state->clues->dsf, ink);
2203
2204     /*
2205      * Clues.
2206      */
2207     for (y = 0; y < w; y++)
2208         for (x = 0; x < w; x++)
2209             if (dsf_canonify(state->clues->dsf, y*w+x) == y*w+x) {
2210                 long clue = state->clues->clues[y*w+x];
2211                 long cluetype = clue & CMASK, clueval = clue & ~CMASK;
2212                 int size = dsf_size(state->clues->dsf, y*w+x);
2213                 char str[64];
2214
2215                 /*
2216                  * As in the drawing code, we omit the operator for
2217                  * blocks of area 1.
2218                  */
2219                 sprintf (str, "%ld%s", clueval,
2220                          (size == 1 ? "" :
2221                           cluetype == C_ADD ? "+" :
2222                           cluetype == C_SUB ? minus_sign :
2223                           cluetype == C_MUL ? times_sign :
2224                           /* cluetype == C_DIV ? */ divide_sign));
2225
2226                 draw_text(dr,
2227                           BORDER+x*TILESIZE + 5*TILESIZE/80,
2228                           BORDER+y*TILESIZE + 20*TILESIZE/80,
2229                           FONT_VARIABLE, TILESIZE/4,
2230                           ALIGN_VNORMAL | ALIGN_HLEFT,
2231                           ink, str);
2232             }
2233
2234     /*
2235      * Numbers for the solution, if any.
2236      */
2237     for (y = 0; y < w; y++)
2238         for (x = 0; x < w; x++)
2239             if (state->grid[y*w+x]) {
2240                 char str[2];
2241                 str[1] = '\0';
2242                 str[0] = state->grid[y*w+x] + '0';
2243                 draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
2244                           BORDER + y*TILESIZE + TILESIZE/2,
2245                           FONT_VARIABLE, TILESIZE/2,
2246                           ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
2247             }
2248
2249     sfree(minus_sign);
2250     sfree(times_sign);
2251     sfree(divide_sign);
2252 }
2253
2254 #ifdef COMBINED
2255 #define thegame keen
2256 #endif
2257
2258 const struct game thegame = {
2259     "Keen", "games.keen", "keen",
2260     default_params,
2261     game_fetch_preset,
2262     decode_params,
2263     encode_params,
2264     free_params,
2265     dup_params,
2266     TRUE, game_configure, custom_params,
2267     validate_params,
2268     new_game_desc,
2269     validate_desc,
2270     new_game,
2271     dup_game,
2272     free_game,
2273     TRUE, solve_game,
2274     FALSE, game_can_format_as_text_now, game_text_format,
2275     new_ui,
2276     free_ui,
2277     encode_ui,
2278     decode_ui,
2279     game_changed_state,
2280     interpret_move,
2281     execute_move,
2282     PREFERRED_TILESIZE, game_compute_size, game_set_size,
2283     game_colours,
2284     game_new_drawstate,
2285     game_free_drawstate,
2286     game_redraw,
2287     game_anim_length,
2288     game_flash_length,
2289     game_is_solved,
2290     TRUE, FALSE, game_print_size, game_print,
2291     FALSE,                             /* wants_statusbar */
2292     FALSE, game_timing_state,
2293     REQUIRE_RBUTTON | REQUIRE_NUMPAD,  /* flags */
2294 };
2295
2296 #ifdef STANDALONE_SOLVER
2297
2298 #include <stdarg.h>
2299
2300 int main(int argc, char **argv)
2301 {
2302     game_params *p;
2303     game_state *s;
2304     char *id = NULL, *desc, *err;
2305     int grade = FALSE;
2306     int ret, diff, really_show_working = FALSE;
2307
2308     while (--argc > 0) {
2309         char *p = *++argv;
2310         if (!strcmp(p, "-v")) {
2311             really_show_working = TRUE;
2312         } else if (!strcmp(p, "-g")) {
2313             grade = TRUE;
2314         } else if (*p == '-') {
2315             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2316             return 1;
2317         } else {
2318             id = p;
2319         }
2320     }
2321
2322     if (!id) {
2323         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2324         return 1;
2325     }
2326
2327     desc = strchr(id, ':');
2328     if (!desc) {
2329         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2330         return 1;
2331     }
2332     *desc++ = '\0';
2333
2334     p = default_params();
2335     decode_params(p, id);
2336     err = validate_desc(p, desc);
2337     if (err) {
2338         fprintf(stderr, "%s: %s\n", argv[0], err);
2339         return 1;
2340     }
2341     s = new_game(NULL, p, desc);
2342
2343     /*
2344      * When solving an Easy puzzle, we don't want to bother the
2345      * user with Hard-level deductions. For this reason, we grade
2346      * the puzzle internally before doing anything else.
2347      */
2348     ret = -1;                          /* placate optimiser */
2349     solver_show_working = FALSE;
2350     for (diff = 0; diff < DIFFCOUNT; diff++) {
2351         memset(s->grid, 0, p->w * p->w);
2352         ret = solver(p->w, s->clues->dsf, s->clues->clues,
2353                      s->grid, diff);
2354         if (ret <= diff)
2355             break;
2356     }
2357
2358     if (diff == DIFFCOUNT) {
2359         if (grade)
2360             printf("Difficulty rating: ambiguous\n");
2361         else
2362             printf("Unable to find a unique solution\n");
2363     } else {
2364         if (grade) {
2365             if (ret == diff_impossible)
2366                 printf("Difficulty rating: impossible (no solution exists)\n");
2367             else
2368                 printf("Difficulty rating: %s\n", keen_diffnames[ret]);
2369         } else {
2370             solver_show_working = really_show_working;
2371             memset(s->grid, 0, p->w * p->w);
2372             ret = solver(p->w, s->clues->dsf, s->clues->clues,
2373                          s->grid, diff);
2374             if (ret != diff)
2375                 printf("Puzzle is inconsistent\n");
2376             else {
2377                 /*
2378                  * We don't have a game_text_format for this game,
2379                  * so we have to output the solution manually.
2380                  */
2381                 int x, y;
2382                 for (y = 0; y < p->w; y++) {
2383                     for (x = 0; x < p->w; x++) {
2384                         printf("%s%c", x>0?" ":"", '0' + s->grid[y*p->w+x]);
2385                     }
2386                     putchar('\n');
2387                 }
2388             }
2389         }
2390     }
2391
2392     return 0;
2393 }
2394
2395 #endif
2396
2397 /* vim: set shiftwidth=4 tabstop=8: */