keen.c

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