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