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(const 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(const 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(const 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(const 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(const 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, const 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, const game_params *params,
1197                             const char *desc)
1198 {
1199     int w = params->w, a = w*w;
1200     game_state *state = snew(game_state);
1201     const char *p = desc;
1202     int i;
1203
1204     state->par = *params;              /* structure copy */
1205     state->clues = snew(struct clues);
1206     state->clues->refcount = 1;
1207     state->clues->w = w;
1208     state->clues->dsf = snew_dsf(a);
1209     parse_block_structure(&p, w, state->clues->dsf);
1210
1211     assert(*p == ',');
1212     p++;
1213
1214     state->clues->clues = snewn(a, long);
1215     for (i = 0; i < a; i++) {
1216         if (dsf_canonify(state->clues->dsf, i) == i) {
1217             long clue = 0;
1218             switch (*p) {
1219               case 'a':
1220                 clue = C_ADD;
1221                 break;
1222               case 'm':
1223                 clue = C_MUL;
1224                 break;
1225               case 's':
1226                 clue = C_SUB;
1227                 assert(dsf_size(state->clues->dsf, i) == 2);
1228                 break;
1229               case 'd':
1230                 clue = C_DIV;
1231                 assert(dsf_size(state->clues->dsf, i) == 2);
1232                 break;
1233               default:
1234                 assert(!"Bad description in new_game");
1235             }
1236             p++;
1237             clue |= atol(p);
1238             while (*p && isdigit((unsigned char)*p)) p++;
1239             state->clues->clues[i] = clue;
1240         } else
1241             state->clues->clues[i] = 0;
1242     }
1243
1244     state->grid = snewn(a, digit);
1245     state->pencil = snewn(a, int);
1246     for (i = 0; i < a; i++) {
1247         state->grid[i] = 0;
1248         state->pencil[i] = 0;
1249     }
1250
1251     state->completed = state->cheated = FALSE;
1252
1253     return state;
1254 }
1255
1256 static game_state *dup_game(const game_state *state)
1257 {
1258     int w = state->par.w, a = w*w;
1259     game_state *ret = snew(game_state);
1260
1261     ret->par = state->par;             /* structure copy */
1262
1263     ret->clues = state->clues;
1264     ret->clues->refcount++;
1265
1266     ret->grid = snewn(a, digit);
1267     ret->pencil = snewn(a, int);
1268     memcpy(ret->grid, state->grid, a*sizeof(digit));
1269     memcpy(ret->pencil, state->pencil, a*sizeof(int));
1270
1271     ret->completed = state->completed;
1272     ret->cheated = state->cheated;
1273
1274     return ret;
1275 }
1276
1277 static void free_game(game_state *state)
1278 {
1279     sfree(state->grid);
1280     sfree(state->pencil);
1281     if (--state->clues->refcount <= 0) {
1282         sfree(state->clues->dsf);
1283         sfree(state->clues->clues);
1284         sfree(state->clues);
1285     }
1286     sfree(state);
1287 }
1288
1289 static char *solve_game(const game_state *state, const game_state *currstate,
1290                         const char *aux, char **error)
1291 {
1292     int w = state->par.w, a = w*w;
1293     int i, ret;
1294     digit *soln;
1295     char *out;
1296
1297     if (aux)
1298         return dupstr(aux);
1299
1300     soln = snewn(a, digit);
1301     memset(soln, 0, a);
1302
1303     ret = solver(w, state->clues->dsf, state->clues->clues,
1304                  soln, DIFFCOUNT-1);
1305
1306     if (ret == diff_impossible) {
1307         *error = "No solution exists for this puzzle";
1308         out = NULL;
1309     } else if (ret == diff_ambiguous) {
1310         *error = "Multiple solutions exist for this puzzle";
1311         out = NULL;
1312     } else {
1313         out = snewn(a+2, char);
1314         out[0] = 'S';
1315         for (i = 0; i < a; i++)
1316             out[i+1] = '0' + soln[i];
1317         out[a+1] = '\0';
1318     }
1319
1320     sfree(soln);
1321     return out;
1322 }
1323
1324 static int game_can_format_as_text_now(const game_params *params)
1325 {
1326     return TRUE;
1327 }
1328
1329 static char *game_text_format(const game_state *state)
1330 {
1331     return NULL;
1332 }
1333
1334 struct game_ui {
1335     /*
1336      * These are the coordinates of the currently highlighted
1337      * square on the grid, if hshow = 1.
1338      */
1339     int hx, hy;
1340     /*
1341      * This indicates whether the current highlight is a
1342      * pencil-mark one or a real one.
1343      */
1344     int hpencil;
1345     /*
1346      * This indicates whether or not we're showing the highlight
1347      * (used to be hx = hy = -1); important so that when we're
1348      * using the cursor keys it doesn't keep coming back at a
1349      * fixed position. When hshow = 1, pressing a valid number
1350      * or letter key or Space will enter that number or letter in the grid.
1351      */
1352     int hshow;
1353     /*
1354      * This indicates whether we're using the highlight as a cursor;
1355      * it means that it doesn't vanish on a keypress, and that it is
1356      * allowed on immutable squares.
1357      */
1358     int hcursor;
1359 };
1360
1361 static game_ui *new_ui(const game_state *state)
1362 {
1363     game_ui *ui = snew(game_ui);
1364
1365     ui->hx = ui->hy = 0;
1366     ui->hpencil = ui->hshow = ui->hcursor = 0;
1367
1368     return ui;
1369 }
1370
1371 static void free_ui(game_ui *ui)
1372 {
1373     sfree(ui);
1374 }
1375
1376 static char *encode_ui(const game_ui *ui)
1377 {
1378     return NULL;
1379 }
1380
1381 static void decode_ui(game_ui *ui, const char *encoding)
1382 {
1383 }
1384
1385 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1386                                const game_state *newstate)
1387 {
1388     int w = newstate->par.w;
1389     /*
1390      * We prevent pencil-mode highlighting of a filled square, unless
1391      * we're using the cursor keys. So if the user has just filled in
1392      * a square which we had a pencil-mode highlight in (by Undo, or
1393      * by Redo, or by Solve), then we cancel the highlight.
1394      */
1395     if (ui->hshow && ui->hpencil && !ui->hcursor &&
1396         newstate->grid[ui->hy * w + ui->hx] != 0) {
1397         ui->hshow = 0;
1398     }
1399 }
1400
1401 #define PREFERRED_TILESIZE 48
1402 #define TILESIZE (ds->tilesize)
1403 #define BORDER (TILESIZE / 2)
1404 #define GRIDEXTRA max((TILESIZE / 32),1)
1405 #define COORD(x) ((x)*TILESIZE + BORDER)
1406 #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1)
1407
1408 #define FLASH_TIME 0.4F
1409
1410 #define DF_PENCIL_SHIFT 16
1411 #define DF_ERR_LATIN 0x8000
1412 #define DF_ERR_CLUE 0x4000
1413 #define DF_HIGHLIGHT 0x2000
1414 #define DF_HIGHLIGHT_PENCIL 0x1000
1415 #define DF_DIGIT_MASK 0x000F
1416
1417 struct game_drawstate {
1418     int tilesize;
1419     int started;
1420     long *tiles;
1421     long *errors;
1422     char *minus_sign, *times_sign, *divide_sign;
1423 };
1424
1425 static int check_errors(const game_state *state, long *errors)
1426 {
1427     int w = state->par.w, a = w*w;
1428     int i, j, x, y, errs = FALSE;
1429     long *cluevals;
1430     int *full;
1431
1432     cluevals = snewn(a, long);
1433     full = snewn(a, int);
1434
1435     if (errors)
1436         for (i = 0; i < a; i++) {
1437             errors[i] = 0;
1438             full[i] = TRUE;
1439         }
1440
1441     for (i = 0; i < a; i++) {
1442         long clue;
1443
1444         j = dsf_canonify(state->clues->dsf, i);
1445         if (j == i) {
1446             cluevals[i] = state->grid[i];
1447         } else {
1448             clue = state->clues->clues[j] & CMASK;
1449
1450             switch (clue) {
1451               case C_ADD:
1452                 cluevals[j] += state->grid[i];
1453                 break;
1454               case C_MUL:
1455                 cluevals[j] *= state->grid[i];
1456                 break;
1457               case C_SUB:
1458                 cluevals[j] = abs(cluevals[j] - state->grid[i]);
1459                 break;
1460               case C_DIV:
1461                 {
1462                     int d1 = min(cluevals[j], state->grid[i]);
1463                     int d2 = max(cluevals[j], state->grid[i]);
1464                     if (d1 == 0 || d2 % d1 != 0)
1465                         cluevals[j] = 0;
1466                     else
1467                         cluevals[j] = d2 / d1;
1468                 }
1469                 break;
1470             }
1471         }
1472
1473         if (!state->grid[i])
1474             full[j] = FALSE;
1475     }
1476
1477     for (i = 0; i < a; i++) {
1478         j = dsf_canonify(state->clues->dsf, i);
1479         if (j == i) {
1480             if ((state->clues->clues[j] & ~CMASK) != cluevals[i]) {
1481                 errs = TRUE;
1482                 if (errors && full[j])
1483                     errors[j] |= DF_ERR_CLUE;
1484             }
1485         }
1486     }
1487
1488     sfree(cluevals);
1489     sfree(full);
1490
1491     for (y = 0; y < w; y++) {
1492         int mask = 0, errmask = 0;
1493         for (x = 0; x < w; x++) {
1494             int bit = 1 << state->grid[y*w+x];
1495             errmask |= (mask & bit);
1496             mask |= bit;
1497         }
1498
1499         if (mask != (1 << (w+1)) - (1 << 1)) {
1500             errs = TRUE;
1501             errmask &= ~1;
1502             if (errors) {
1503                 for (x = 0; x < w; x++)
1504                     if (errmask & (1 << state->grid[y*w+x]))
1505                         errors[y*w+x] |= DF_ERR_LATIN;
1506             }
1507         }
1508     }
1509
1510     for (x = 0; x < w; x++) {
1511         int mask = 0, errmask = 0;
1512         for (y = 0; y < w; y++) {
1513             int bit = 1 << state->grid[y*w+x];
1514             errmask |= (mask & bit);
1515             mask |= bit;
1516         }
1517
1518         if (mask != (1 << (w+1)) - (1 << 1)) {
1519             errs = TRUE;
1520             errmask &= ~1;
1521             if (errors) {
1522                 for (y = 0; y < w; y++)
1523                     if (errmask & (1 << state->grid[y*w+x]))
1524                         errors[y*w+x] |= DF_ERR_LATIN;
1525             }
1526         }
1527     }
1528
1529     return errs;
1530 }
1531
1532 static char *interpret_move(const game_state *state, game_ui *ui,
1533                             const game_drawstate *ds,
1534                             int x, int y, int button)
1535 {
1536     int w = state->par.w;
1537     int tx, ty;
1538     char buf[80];
1539
1540     button &= ~MOD_MASK;
1541
1542     tx = FROMCOORD(x);
1543     ty = FROMCOORD(y);
1544
1545     if (tx >= 0 && tx < w && ty >= 0 && ty < w) {
1546         if (button == LEFT_BUTTON) {
1547             if (tx == ui->hx && ty == ui->hy &&
1548                 ui->hshow && ui->hpencil == 0) {
1549                 ui->hshow = 0;
1550             } else {
1551                 ui->hx = tx;
1552                 ui->hy = ty;
1553                 ui->hshow = 1;
1554                 ui->hpencil = 0;
1555             }
1556             ui->hcursor = 0;
1557             return "";                 /* UI activity occurred */
1558         }
1559         if (button == RIGHT_BUTTON) {
1560             /*
1561              * Pencil-mode highlighting for non filled squares.
1562              */
1563             if (state->grid[ty*w+tx] == 0) {
1564                 if (tx == ui->hx && ty == ui->hy &&
1565                     ui->hshow && ui->hpencil) {
1566                     ui->hshow = 0;
1567                 } else {
1568                     ui->hpencil = 1;
1569                     ui->hx = tx;
1570                     ui->hy = ty;
1571                     ui->hshow = 1;
1572                 }
1573             } else {
1574                 ui->hshow = 0;
1575             }
1576             ui->hcursor = 0;
1577             return "";                 /* UI activity occurred */
1578         }
1579     }
1580     if (IS_CURSOR_MOVE(button)) {
1581         move_cursor(button, &ui->hx, &ui->hy, w, w, 0);
1582         ui->hshow = ui->hcursor = 1;
1583         return "";
1584     }
1585     if (ui->hshow &&
1586         (button == CURSOR_SELECT)) {
1587         ui->hpencil = 1 - ui->hpencil;
1588         ui->hcursor = 1;
1589         return "";
1590     }
1591
1592     if (ui->hshow &&
1593         ((button >= '0' && button <= '9' && button - '0' <= w) ||
1594          button == CURSOR_SELECT2 || button == '\b')) {
1595         int n = button - '0';
1596         if (button == CURSOR_SELECT2 || button == '\b')
1597             n = 0;
1598
1599         /*
1600          * Can't make pencil marks in a filled square. This can only
1601          * become highlighted if we're using cursor keys.
1602          */
1603         if (ui->hpencil && state->grid[ui->hy*w+ui->hx])
1604             return NULL;
1605
1606         sprintf(buf, "%c%d,%d,%d",
1607                 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1608
1609         if (!ui->hcursor) ui->hshow = 0;
1610
1611         return dupstr(buf);
1612     }
1613
1614     if (button == 'M' || button == 'm')
1615         return dupstr("M");
1616
1617     return NULL;
1618 }
1619
1620 static game_state *execute_move(const game_state *from, const char *move)
1621 {
1622     int w = from->par.w, a = w*w;
1623     game_state *ret;
1624     int x, y, i, n;
1625
1626     if (move[0] == 'S') {
1627         ret = dup_game(from);
1628         ret->completed = ret->cheated = TRUE;
1629
1630         for (i = 0; i < a; i++) {
1631             if (move[i+1] < '1' || move[i+1] > '0'+w) {
1632                 free_game(ret);
1633                 return NULL;
1634             }
1635             ret->grid[i] = move[i+1] - '0';
1636             ret->pencil[i] = 0;
1637         }
1638
1639         if (move[a+1] != '\0') {
1640             free_game(ret);
1641             return NULL;
1642         }
1643
1644         return ret;
1645     } else if ((move[0] == 'P' || move[0] == 'R') &&
1646         sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1647         x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) {
1648
1649         ret = dup_game(from);
1650         if (move[0] == 'P' && n > 0) {
1651             ret->pencil[y*w+x] ^= 1 << n;
1652         } else {
1653             ret->grid[y*w+x] = n;
1654             ret->pencil[y*w+x] = 0;
1655
1656             if (!ret->completed && !check_errors(ret, NULL))
1657                 ret->completed = TRUE;
1658         }
1659         return ret;
1660     } else if (move[0] == 'M') {
1661         /*
1662          * Fill in absolutely all pencil marks everywhere. (I
1663          * wouldn't use this for actual play, but it's a handy
1664          * starting point when following through a set of
1665          * diagnostics output by the standalone solver.)
1666          */
1667         ret = dup_game(from);
1668         for (i = 0; i < a; i++) {
1669             if (!ret->grid[i])
1670                 ret->pencil[i] = (1 << (w+1)) - (1 << 1);
1671         }
1672         return ret;
1673     } else
1674         return NULL;                   /* couldn't parse move string */
1675 }
1676
1677 /* ----------------------------------------------------------------------
1678  * Drawing routines.
1679  */
1680
1681 #define SIZE(w) ((w) * TILESIZE + 2*BORDER)
1682
1683 static void game_compute_size(const game_params *params, int tilesize,
1684                               int *x, int *y)
1685 {
1686     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1687     struct { int tilesize; } ads, *ds = &ads;
1688     ads.tilesize = tilesize;
1689
1690     *x = *y = SIZE(params->w);
1691 }
1692
1693 static void game_set_size(drawing *dr, game_drawstate *ds,
1694                           const game_params *params, int tilesize)
1695 {
1696     ds->tilesize = tilesize;
1697 }
1698
1699 static float *game_colours(frontend *fe, int *ncolours)
1700 {
1701     float *ret = snewn(3 * NCOLOURS, float);
1702
1703     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1704
1705     ret[COL_GRID * 3 + 0] = 0.0F;
1706     ret[COL_GRID * 3 + 1] = 0.0F;
1707     ret[COL_GRID * 3 + 2] = 0.0F;
1708
1709     ret[COL_USER * 3 + 0] = 0.0F;
1710     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1711     ret[COL_USER * 3 + 2] = 0.0F;
1712
1713     ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
1714     ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
1715     ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
1716
1717     ret[COL_ERROR * 3 + 0] = 1.0F;
1718     ret[COL_ERROR * 3 + 1] = 0.0F;
1719     ret[COL_ERROR * 3 + 2] = 0.0F;
1720
1721     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1722     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1723     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1724
1725     *ncolours = NCOLOURS;
1726     return ret;
1727 }
1728
1729 static const char *const minus_signs[] = { "\xE2\x88\x92", "-" };
1730 static const char *const times_signs[] = { "\xC3\x97", "*" };
1731 static const char *const divide_signs[] = { "\xC3\xB7", "/" };
1732
1733 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1734 {
1735     int w = state->par.w, a = w*w;
1736     struct game_drawstate *ds = snew(struct game_drawstate);
1737     int i;
1738
1739     ds->tilesize = 0;
1740     ds->started = FALSE;
1741     ds->tiles = snewn(a, long);
1742     for (i = 0; i < a; i++)
1743         ds->tiles[i] = -1;
1744     ds->errors = snewn(a, long);
1745     ds->minus_sign = text_fallback(dr, minus_signs, lenof(minus_signs));
1746     ds->times_sign = text_fallback(dr, times_signs, lenof(times_signs));
1747     ds->divide_sign = text_fallback(dr, divide_signs, lenof(divide_signs));
1748
1749     return ds;
1750 }
1751
1752 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1753 {
1754     sfree(ds->tiles);
1755     sfree(ds->errors);
1756     sfree(ds->minus_sign);
1757     sfree(ds->times_sign);
1758     sfree(ds->divide_sign);
1759     sfree(ds);
1760 }
1761
1762 static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues,
1763                       int x, int y, long tile)
1764 {
1765     int w = clues->w /* , a = w*w */;
1766     int tx, ty, tw, th;
1767     int cx, cy, cw, ch;
1768     char str[64];
1769
1770     tx = BORDER + x * TILESIZE + 1 + GRIDEXTRA;
1771     ty = BORDER + y * TILESIZE + 1 + GRIDEXTRA;
1772
1773     cx = tx;
1774     cy = ty;
1775     cw = tw = TILESIZE-1-2*GRIDEXTRA;
1776     ch = th = TILESIZE-1-2*GRIDEXTRA;
1777
1778     if (x > 0 && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, y*w+x-1))
1779         cx -= GRIDEXTRA, cw += GRIDEXTRA;
1780     if (x+1 < w && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, y*w+x+1))
1781         cw += GRIDEXTRA;
1782     if (y > 0 && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, (y-1)*w+x))
1783         cy -= GRIDEXTRA, ch += GRIDEXTRA;
1784     if (y+1 < w && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, (y+1)*w+x))
1785         ch += GRIDEXTRA;
1786
1787     clip(dr, cx, cy, cw, ch);
1788
1789     /* background needs erasing */
1790     draw_rect(dr, cx, cy, cw, ch,
1791               (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND);
1792
1793     /*
1794      * Draw the corners of thick lines in corner-adjacent squares,
1795      * which jut into this square by one pixel.
1796      */
1797     if (x > 0 && y > 0 && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y-1)*w+x-1))
1798         draw_rect(dr, tx-GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
1799     if (x+1 < w && y > 0 && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y-1)*w+x+1))
1800         draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
1801     if (x > 0 && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x-1))
1802         draw_rect(dr, tx-GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
1803     if (x+1 < w && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x+1))
1804         draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
1805
1806     /* pencil-mode highlight */
1807     if (tile & DF_HIGHLIGHT_PENCIL) {
1808         int coords[6];
1809         coords[0] = cx;
1810         coords[1] = cy;
1811         coords[2] = cx+cw/2;
1812         coords[3] = cy;
1813         coords[4] = cx;
1814         coords[5] = cy+ch/2;
1815         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1816     }
1817
1818     /* Draw the box clue. */
1819     if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {
1820         long clue = clues->clues[y*w+x];
1821         long cluetype = clue & CMASK, clueval = clue & ~CMASK;
1822         int size = dsf_size(clues->dsf, y*w+x);
1823         /*
1824          * Special case of clue-drawing: a box with only one square
1825          * is written as just the number, with no operation, because
1826          * it doesn't matter whether the operation is ADD or MUL.
1827          * The generation code above should never produce puzzles
1828          * containing such a thing - I think they're inelegant - but
1829          * it's possible to type in game IDs from elsewhere, so I
1830          * want to display them right if so.
1831          */
1832         sprintf (str, "%ld%s", clueval,
1833                  (size == 1 ? "" :
1834                   cluetype == C_ADD ? "+" :
1835                   cluetype == C_SUB ? ds->minus_sign :
1836                   cluetype == C_MUL ? ds->times_sign :
1837                   /* cluetype == C_DIV ? */ ds->divide_sign));
1838         draw_text(dr, tx + GRIDEXTRA * 2, ty + GRIDEXTRA * 2 + TILESIZE/4,
1839                   FONT_VARIABLE, TILESIZE/4, ALIGN_VNORMAL | ALIGN_HLEFT,
1840                   (tile & DF_ERR_CLUE ? COL_ERROR : COL_GRID), str);
1841     }
1842
1843     /* new number needs drawing? */
1844     if (tile & DF_DIGIT_MASK) {
1845         str[1] = '\0';
1846         str[0] = (tile & DF_DIGIT_MASK) + '0';
1847         draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1848                   FONT_VARIABLE, TILESIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1849                   (tile & DF_ERR_LATIN) ? COL_ERROR : COL_USER, str);
1850     } else {
1851         int i, j, npencil;
1852         int pl, pr, pt, pb;
1853         float bestsize;
1854         int pw, ph, minph, pbest, fontsize;
1855
1856         /* Count the pencil marks required. */
1857         for (i = 1, npencil = 0; i <= w; i++)
1858             if (tile & (1L << (i + DF_PENCIL_SHIFT)))
1859                 npencil++;
1860         if (npencil) {
1861
1862             minph = 2;
1863
1864             /*
1865              * Determine the bounding rectangle within which we're going
1866              * to put the pencil marks.
1867              */
1868             /* Start with the whole square */
1869             pl = tx + GRIDEXTRA;
1870             pr = pl + TILESIZE - GRIDEXTRA;
1871             pt = ty + GRIDEXTRA;
1872             pb = pt + TILESIZE - GRIDEXTRA;
1873             if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {
1874                 /*
1875                  * Make space for the clue text.
1876                  */
1877                 pt += TILESIZE/4;
1878                 /* minph--; */
1879             }
1880
1881             /*
1882              * We arrange our pencil marks in a grid layout, with
1883              * the number of rows and columns adjusted to allow the
1884              * maximum font size.
1885              *
1886              * So now we work out what the grid size ought to be.
1887              */
1888             bestsize = 0.0;
1889             pbest = 0;
1890             /* Minimum */
1891             for (pw = 3; pw < max(npencil,4); pw++) {
1892                 float fw, fh, fs;
1893
1894                 ph = (npencil + pw - 1) / pw;
1895                 ph = max(ph, minph);
1896                 fw = (pr - pl) / (float)pw;
1897                 fh = (pb - pt) / (float)ph;
1898                 fs = min(fw, fh);
1899                 if (fs > bestsize) {
1900                     bestsize = fs;
1901                     pbest = pw;
1902                 }
1903             }
1904             assert(pbest > 0);
1905             pw = pbest;
1906             ph = (npencil + pw - 1) / pw;
1907             ph = max(ph, minph);
1908
1909             /*
1910              * Now we've got our grid dimensions, work out the pixel
1911              * size of a grid element, and round it to the nearest
1912              * pixel. (We don't want rounding errors to make the
1913              * grid look uneven at low pixel sizes.)
1914              */
1915             fontsize = min((pr - pl) / pw, (pb - pt) / ph);
1916
1917             /*
1918              * Centre the resulting figure in the square.
1919              */
1920             pl = tx + (TILESIZE - fontsize * pw) / 2;
1921             pt = ty + (TILESIZE - fontsize * ph) / 2;
1922
1923             /*
1924              * And move it down a bit if it's collided with some
1925              * clue text.
1926              */
1927             if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {
1928                 pt = max(pt, ty + GRIDEXTRA * 3 + TILESIZE/4);
1929             }
1930
1931             /*
1932              * Now actually draw the pencil marks.
1933              */
1934             for (i = 1, j = 0; i <= w; i++)
1935                 if (tile & (1L << (i + DF_PENCIL_SHIFT))) {
1936                     int dx = j % pw, dy = j / pw;
1937
1938                     str[1] = '\0';
1939                     str[0] = i + '0';
1940                     draw_text(dr, pl + fontsize * (2*dx+1) / 2,
1941                               pt + fontsize * (2*dy+1) / 2,
1942                               FONT_VARIABLE, fontsize,
1943                               ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1944                     j++;
1945                 }
1946         }
1947     }
1948
1949     unclip(dr);
1950
1951     draw_update(dr, cx, cy, cw, ch);
1952 }
1953
1954 static void game_redraw(drawing *dr, game_drawstate *ds,
1955                         const game_state *oldstate, const game_state *state,
1956                         int dir, const game_ui *ui,
1957                         float animtime, float flashtime)
1958 {
1959     int w = state->par.w /*, a = w*w */;
1960     int x, y;
1961
1962     if (!ds->started) {
1963         /*
1964          * The initial contents of the window are not guaranteed and
1965          * can vary with front ends. To be on the safe side, all
1966          * games should start by drawing a big background-colour
1967          * rectangle covering the whole window.
1968          */
1969         draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND);
1970
1971         /*
1972          * Big containing rectangle.
1973          */
1974         draw_rect(dr, COORD(0) - GRIDEXTRA, COORD(0) - GRIDEXTRA,
1975                   w*TILESIZE+1+GRIDEXTRA*2, w*TILESIZE+1+GRIDEXTRA*2,
1976                   COL_GRID);
1977
1978         draw_update(dr, 0, 0, SIZE(w), SIZE(w));
1979
1980         ds->started = TRUE;
1981     }
1982
1983     check_errors(state, ds->errors);
1984
1985     for (y = 0; y < w; y++) {
1986         for (x = 0; x < w; x++) {
1987             long tile = 0L;
1988
1989             if (state->grid[y*w+x])
1990                 tile = state->grid[y*w+x];
1991             else
1992                 tile = (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT;
1993
1994             if (ui->hshow && ui->hx == x && ui->hy == y)
1995                 tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT);
1996
1997             if (flashtime > 0 &&
1998                 (flashtime <= FLASH_TIME/3 ||
1999                  flashtime >= FLASH_TIME*2/3))
2000                 tile |= DF_HIGHLIGHT;  /* completion flash */
2001
2002             tile |= ds->errors[y*w+x];
2003
2004             if (ds->tiles[y*w+x] != tile) {
2005                 ds->tiles[y*w+x] = tile;
2006                 draw_tile(dr, ds, state->clues, x, y, tile);
2007             }
2008         }
2009     }
2010 }
2011
2012 static float game_anim_length(const game_state *oldstate,
2013                               const game_state *newstate, int dir, game_ui *ui)
2014 {
2015     return 0.0F;
2016 }
2017
2018 static float game_flash_length(const game_state *oldstate,
2019                                const game_state *newstate, int dir, game_ui *ui)
2020 {
2021     if (!oldstate->completed && newstate->completed &&
2022         !oldstate->cheated && !newstate->cheated)
2023         return FLASH_TIME;
2024     return 0.0F;
2025 }
2026
2027 static int game_status(const game_state *state)
2028 {
2029     return state->completed ? +1 : 0;
2030 }
2031
2032 static int game_timing_state(const game_state *state, game_ui *ui)
2033 {
2034     if (state->completed)
2035         return FALSE;
2036     return TRUE;
2037 }
2038
2039 static void game_print_size(const game_params *params, float *x, float *y)
2040 {
2041     int pw, ph;
2042
2043     /*
2044      * We use 9mm squares by default, like Solo.
2045      */
2046     game_compute_size(params, 900, &pw, &ph);
2047     *x = pw / 100.0F;
2048     *y = ph / 100.0F;
2049 }
2050
2051 /*
2052  * Subfunction to draw the thick lines between cells. In order to do
2053  * this using the line-drawing rather than rectangle-drawing API (so
2054  * as to get line thicknesses to scale correctly) and yet have
2055  * correctly mitred joins between lines, we must do this by tracing
2056  * the boundary of each sub-block and drawing it in one go as a
2057  * single polygon.
2058  */
2059 static void outline_block_structure(drawing *dr, game_drawstate *ds,
2060                                     int w, int *dsf, int ink)
2061 {
2062     int a = w*w;
2063     int *coords;
2064     int i, n;
2065     int x, y, dx, dy, sx, sy, sdx, sdy;
2066
2067     coords = snewn(4*a, int);
2068
2069     /*
2070      * Iterate over all the blocks.
2071      */
2072     for (i = 0; i < a; i++) {
2073         if (dsf_canonify(dsf, i) != i)
2074             continue;
2075
2076         /*
2077          * For each block, we need a starting square within it which
2078          * has a boundary at the left. Conveniently, we have one
2079          * right here, by construction.
2080          */
2081         x = i % w;
2082         y = i / w;
2083         dx = -1;
2084         dy = 0;
2085
2086         /*
2087          * Now begin tracing round the perimeter. At all
2088          * times, (x,y) describes some square within the
2089          * block, and (x+dx,y+dy) is some adjacent square
2090          * outside it; so the edge between those two squares
2091          * is always an edge of the block.
2092          */
2093         sx = x, sy = y, sdx = dx, sdy = dy;   /* save starting position */
2094         n = 0;
2095         do {
2096             int cx, cy, tx, ty, nin;
2097
2098             /*
2099              * Advance to the next edge, by looking at the two
2100              * squares beyond it. If they're both outside the block,
2101              * we turn right (by leaving x,y the same and rotating
2102              * dx,dy clockwise); if they're both inside, we turn
2103              * left (by rotating dx,dy anticlockwise and contriving
2104              * to leave x+dx,y+dy unchanged); if one of each, we go
2105              * straight on (and may enforce by assertion that
2106              * they're one of each the _right_ way round).
2107              */
2108             nin = 0;
2109             tx = x - dy + dx;
2110             ty = y + dx + dy;
2111             nin += (tx >= 0 && tx < w && ty >= 0 && ty < w &&
2112                     dsf_canonify(dsf, ty*w+tx) == i);
2113             tx = x - dy;
2114             ty = y + dx;
2115             nin += (tx >= 0 && tx < w && ty >= 0 && ty < w &&
2116                     dsf_canonify(dsf, ty*w+tx) == i);
2117             if (nin == 0) {
2118                 /*
2119                  * Turn right.
2120                  */
2121                 int tmp;
2122                 tmp = dx;
2123                 dx = -dy;
2124                 dy = tmp;
2125             } else if (nin == 2) {
2126                 /*
2127                  * Turn left.
2128                  */
2129                 int tmp;
2130
2131                 x += dx;
2132                 y += dy;
2133
2134                 tmp = dx;
2135                 dx = dy;
2136                 dy = -tmp;
2137
2138                 x -= dx;
2139                 y -= dy;
2140             } else {
2141                 /*
2142                  * Go straight on.
2143                  */
2144                 x -= dy;
2145                 y += dx;
2146             }
2147
2148             /*
2149              * Now enforce by assertion that we ended up
2150              * somewhere sensible.
2151              */
2152             assert(x >= 0 && x < w && y >= 0 && y < w &&
2153                    dsf_canonify(dsf, y*w+x) == i);
2154             assert(x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= w ||
2155                    dsf_canonify(dsf, (y+dy)*w+(x+dx)) != i);
2156
2157             /*
2158              * Record the point we just went past at one end of the
2159              * edge. To do this, we translate (x,y) down and right
2160              * by half a unit (so they're describing a point in the
2161              * _centre_ of the square) and then translate back again
2162              * in a manner rotated by dy and dx.
2163              */
2164             assert(n < 2*w+2);
2165             cx = ((2*x+1) + dy + dx) / 2;
2166             cy = ((2*y+1) - dx + dy) / 2;
2167             coords[2*n+0] = BORDER + cx * TILESIZE;
2168             coords[2*n+1] = BORDER + cy * TILESIZE;
2169             n++;
2170
2171         } while (x != sx || y != sy || dx != sdx || dy != sdy);
2172
2173         /*
2174          * That's our polygon; now draw it.
2175          */
2176         draw_polygon(dr, coords, n, -1, ink);
2177     }
2178
2179     sfree(coords);
2180 }
2181
2182 static void game_print(drawing *dr, const game_state *state, int tilesize)
2183 {
2184     int w = state->par.w;
2185     int ink = print_mono_colour(dr, 0);
2186     int x, y;
2187     char *minus_sign, *times_sign, *divide_sign;
2188
2189     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2190     game_drawstate ads, *ds = &ads;
2191     game_set_size(dr, ds, NULL, tilesize);
2192
2193     minus_sign = text_fallback(dr, minus_signs, lenof(minus_signs));
2194     times_sign = text_fallback(dr, times_signs, lenof(times_signs));
2195     divide_sign = text_fallback(dr, divide_signs, lenof(divide_signs));
2196
2197     /*
2198      * Border.
2199      */
2200     print_line_width(dr, 3 * TILESIZE / 40);
2201     draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink);
2202
2203     /*
2204      * Main grid.
2205      */
2206     for (x = 1; x < w; x++) {
2207         print_line_width(dr, TILESIZE / 40);
2208         draw_line(dr, BORDER+x*TILESIZE, BORDER,
2209                   BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink);
2210     }
2211     for (y = 1; y < w; y++) {
2212         print_line_width(dr, TILESIZE / 40);
2213         draw_line(dr, BORDER, BORDER+y*TILESIZE,
2214                   BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink);
2215     }
2216
2217     /*
2218      * Thick lines between cells.
2219      */
2220     print_line_width(dr, 3 * TILESIZE / 40);
2221     outline_block_structure(dr, ds, w, state->clues->dsf, ink);
2222
2223     /*
2224      * Clues.
2225      */
2226     for (y = 0; y < w; y++)
2227         for (x = 0; x < w; x++)
2228             if (dsf_canonify(state->clues->dsf, y*w+x) == y*w+x) {
2229                 long clue = state->clues->clues[y*w+x];
2230                 long cluetype = clue & CMASK, clueval = clue & ~CMASK;
2231                 int size = dsf_size(state->clues->dsf, y*w+x);
2232                 char str[64];
2233
2234                 /*
2235                  * As in the drawing code, we omit the operator for
2236                  * blocks of area 1.
2237                  */
2238                 sprintf (str, "%ld%s", clueval,
2239                          (size == 1 ? "" :
2240                           cluetype == C_ADD ? "+" :
2241                           cluetype == C_SUB ? minus_sign :
2242                           cluetype == C_MUL ? times_sign :
2243                           /* cluetype == C_DIV ? */ divide_sign));
2244
2245                 draw_text(dr,
2246                           BORDER+x*TILESIZE + 5*TILESIZE/80,
2247                           BORDER+y*TILESIZE + 20*TILESIZE/80,
2248                           FONT_VARIABLE, TILESIZE/4,
2249                           ALIGN_VNORMAL | ALIGN_HLEFT,
2250                           ink, str);
2251             }
2252
2253     /*
2254      * Numbers for the solution, if any.
2255      */
2256     for (y = 0; y < w; y++)
2257         for (x = 0; x < w; x++)
2258             if (state->grid[y*w+x]) {
2259                 char str[2];
2260                 str[1] = '\0';
2261                 str[0] = state->grid[y*w+x] + '0';
2262                 draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
2263                           BORDER + y*TILESIZE + TILESIZE/2,
2264                           FONT_VARIABLE, TILESIZE/2,
2265                           ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
2266             }
2267
2268     sfree(minus_sign);
2269     sfree(times_sign);
2270     sfree(divide_sign);
2271 }
2272
2273 #ifdef COMBINED
2274 #define thegame keen
2275 #endif
2276
2277 const struct game thegame = {
2278     "Keen", "games.keen", "keen",
2279     default_params,
2280     game_fetch_preset,
2281     decode_params,
2282     encode_params,
2283     free_params,
2284     dup_params,
2285     TRUE, game_configure, custom_params,
2286     validate_params,
2287     new_game_desc,
2288     validate_desc,
2289     new_game,
2290     dup_game,
2291     free_game,
2292     TRUE, solve_game,
2293     FALSE, game_can_format_as_text_now, game_text_format,
2294     new_ui,
2295     free_ui,
2296     encode_ui,
2297     decode_ui,
2298     game_changed_state,
2299     interpret_move,
2300     execute_move,
2301     PREFERRED_TILESIZE, game_compute_size, game_set_size,
2302     game_colours,
2303     game_new_drawstate,
2304     game_free_drawstate,
2305     game_redraw,
2306     game_anim_length,
2307     game_flash_length,
2308     game_status,
2309     TRUE, FALSE, game_print_size, game_print,
2310     FALSE,                             /* wants_statusbar */
2311     FALSE, game_timing_state,
2312     REQUIRE_RBUTTON | REQUIRE_NUMPAD,  /* flags */
2313 };
2314
2315 #ifdef STANDALONE_SOLVER
2316
2317 #include <stdarg.h>
2318
2319 int main(int argc, char **argv)
2320 {
2321     game_params *p;
2322     game_state *s;
2323     char *id = NULL, *desc, *err;
2324     int grade = FALSE;
2325     int ret, diff, really_show_working = FALSE;
2326
2327     while (--argc > 0) {
2328         char *p = *++argv;
2329         if (!strcmp(p, "-v")) {
2330             really_show_working = TRUE;
2331         } else if (!strcmp(p, "-g")) {
2332             grade = TRUE;
2333         } else if (*p == '-') {
2334             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2335             return 1;
2336         } else {
2337             id = p;
2338         }
2339     }
2340
2341     if (!id) {
2342         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2343         return 1;
2344     }
2345
2346     desc = strchr(id, ':');
2347     if (!desc) {
2348         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2349         return 1;
2350     }
2351     *desc++ = '\0';
2352
2353     p = default_params();
2354     decode_params(p, id);
2355     err = validate_desc(p, desc);
2356     if (err) {
2357         fprintf(stderr, "%s: %s\n", argv[0], err);
2358         return 1;
2359     }
2360     s = new_game(NULL, p, desc);
2361
2362     /*
2363      * When solving an Easy puzzle, we don't want to bother the
2364      * user with Hard-level deductions. For this reason, we grade
2365      * the puzzle internally before doing anything else.
2366      */
2367     ret = -1;                          /* placate optimiser */
2368     solver_show_working = FALSE;
2369     for (diff = 0; diff < DIFFCOUNT; diff++) {
2370         memset(s->grid, 0, p->w * p->w);
2371         ret = solver(p->w, s->clues->dsf, s->clues->clues,
2372                      s->grid, diff);
2373         if (ret <= diff)
2374             break;
2375     }
2376
2377     if (diff == DIFFCOUNT) {
2378         if (grade)
2379             printf("Difficulty rating: ambiguous\n");
2380         else
2381             printf("Unable to find a unique solution\n");
2382     } else {
2383         if (grade) {
2384             if (ret == diff_impossible)
2385                 printf("Difficulty rating: impossible (no solution exists)\n");
2386             else
2387                 printf("Difficulty rating: %s\n", keen_diffnames[ret]);
2388         } else {
2389             solver_show_working = really_show_working;
2390             memset(s->grid, 0, p->w * p->w);
2391             ret = solver(p->w, s->clues->dsf, s->clues->clues,
2392                          s->grid, diff);
2393             if (ret != diff)
2394                 printf("Puzzle is inconsistent\n");
2395             else {
2396                 /*
2397                  * We don't have a game_text_format for this game,
2398                  * so we have to output the solution manually.
2399                  */
2400                 int x, y;
2401                 for (y = 0; y < p->w; y++) {
2402                     for (x = 0; x < p->w; x++) {
2403                         printf("%s%c", x>0?" ":"", '0' + s->grid[y*p->w+x]);
2404                     }
2405                     putchar('\n');
2406                 }
2407             }
2408         }
2409     }
2410
2411     return 0;
2412 }
2413
2414 #endif
2415
2416 /* vim: set shiftwidth=4 tabstop=8: */