towers.c

   1 /*
   2  * towers.c: the puzzle also known as 'Skyscrapers'.
   3  *
   4  * Possible future work:
   5  *
   6  *  - Relax the upper bound on grid size at 9?
   7  *     + I'd need TOCHAR and FROMCHAR macros a bit like group's, to
   8  *       be used wherever this code has +'0' or -'0'
   9  *     + the pencil marks in the drawstate would need a separate
  10  *       word to live in
  11  *     + the clues outside the grid would have to cope with being
  12  *       multi-digit, meaning in particular that the text formatting
  13  *       would become more unpleasant
  14  *     + most importantly, though, the solver just isn't fast
  15  *       enough. Even at size 9 it can't really do the solver_hard
  16  *       factorial-time enumeration at a sensible rate. Easy puzzles
  17  *       higher than that would be possible, but more latin-squarey
  18  *       than skyscrapery, as it were.
  19  */
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <assert.h>
  25 #include <ctype.h>
  26 #include <math.h>
  27
  28 #include "puzzles.h"
  29 #include "latin.h"
  30
  31 /*
  32  * Difficulty levels. I do some macro ickery here to ensure that my
  33  * enum and the various forms of my name list always match up.
  34  */
  35 #define DIFFLIST(A) \
  36     A(EASY,Easy,solver_easy,e) \
  37     A(HARD,Hard,solver_hard,h) \
  38     A(EXTREME,Extreme,NULL,x) \
  39     A(UNREASONABLE,Unreasonable,NULL,u)
  40 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
  41 #define TITLE(upper,title,func,lower) #title,
  42 #define ENCODE(upper,title,func,lower) #lower
  43 #define CONFIG(upper,title,func,lower) ":" #title
  44 enum { DIFFLIST(ENUM) DIFFCOUNT };
  45 static char const *const towers_diffnames[] = { DIFFLIST(TITLE) };
  46 static char const towers_diffchars[] = DIFFLIST(ENCODE);
  47 #define DIFFCONFIG DIFFLIST(CONFIG)
  48
  49 enum {
  50     COL_BACKGROUND,
  51     COL_GRID,
  52     COL_USER,
  53     COL_HIGHLIGHT,
  54     COL_ERROR,
  55     COL_PENCIL,
  56     COL_DONE,
  57     NCOLOURS
  58 };
  59
  60 struct game_params {
  61     int w, diff;
  62 };
  63
  64 struct clues {
  65     int refcount;
  66     int w;
  67     /*
  68      * An array of 4w integers, of which:
  69      *  - the first w run across the top
  70      *  - the next w across the bottom
  71      *  - the third w down the left
  72      *  - the last w down the right.
  73      */
  74     int *clues;
  75
  76     /*
  77      * An array of w*w digits.
  78      */
  79     digit *immutable;
  80 };
  81
  82 /*
  83  * Macros to compute clue indices and coordinates.
  84  */
  85 #define STARTSTEP(start, step, index, w) do { \
  86     if (index < w) \
  87         start = index, step = w; \
  88     else if (index < 2*w) \
  89         start = (w-1)*w+(index-w), step = -w; \
  90     else if (index < 3*w) \
  91         start = w*(index-2*w), step = 1; \
  92     else \
  93         start = w*(index-3*w)+(w-1), step = -1; \
  94 } while (0)
  95 #define CSTARTSTEP(start, step, index, w) \
  96     STARTSTEP(start, step, (((index)+2*w)%(4*w)), w)
  97 #define CLUEPOS(x, y, index, w) do { \
  98     if (index < w) \
  99         x = index, y = -1; \
 100     else if (index < 2*w) \
 101         x = index-w, y = w; \
 102     else if (index < 3*w) \
 103         x = -1, y = index-2*w; \
 104     else \
 105         x = w, y = index-3*w; \
 106 } while (0)
 107
 108 #ifdef STANDALONE_SOLVER
 109 static const char *const cluepos[] = {
 110     "above column", "below column", "left of row", "right of row"
 111 };
 112 #endif
 113
 114 struct game_state {
 115     game_params par;
 116     struct clues *clues;
 117     bool *clues_done;
 118     digit *grid;
 119     int *pencil;                       /* bitmaps using bits 1<<1..1<<n */
 120     bool completed, cheated;
 121 };
 122
 123 static game_params *default_params(void)
 124 {
 125     game_params *ret = snew(game_params);
 126
 127     ret->w = 5;
 128     ret->diff = DIFF_EASY;
 129
 130     return ret;
 131 }
 132
 133 static const struct game_params towers_presets[] = {
 134     {  4, DIFF_EASY         },
 135     {  5, DIFF_EASY         },
 136     {  5, DIFF_HARD         },
 137     {  6, DIFF_EASY         },
 138     {  6, DIFF_HARD         },
 139     {  6, DIFF_EXTREME      },
 140     {  6, DIFF_UNREASONABLE },
 141 };
 142
 143 static bool game_fetch_preset(int i, char **name, game_params **params)
 144 {
 145     game_params *ret;
 146     char buf[80];
 147
 148     if (i < 0 || i >= lenof(towers_presets))
 149         return false;
 150
 151     ret = snew(game_params);
 152     *ret = towers_presets[i]; /* structure copy */
 153
 154     sprintf(buf, "%dx%d %s", ret->w, ret->w, towers_diffnames[ret->diff]);
 155
 156     *name = dupstr(buf);
 157     *params = ret;
 158     return true;
 159 }
 160
 161 static void free_params(game_params *params)
 162 {
 163     sfree(params);
 164 }
 165
 166 static game_params *dup_params(const game_params *params)
 167 {
 168     game_params *ret = snew(game_params);
 169     *ret = *params;                    /* structure copy */
 170     return ret;
 171 }
 172
 173 static void decode_params(game_params *params, char const *string)
 174 {
 175     char const *p = string;
 176
 177     params->w = atoi(p);
 178     while (*p && isdigit((unsigned char)*p)) p++;
 179
 180     if (*p == 'd') {
 181         int i;
 182         p++;
 183         params->diff = DIFFCOUNT+1; /* ...which is invalid */
 184         if (*p) {
 185             for (i = 0; i < DIFFCOUNT; i++) {
 186                 if (*p == towers_diffchars[i])
 187                     params->diff = i;
 188             }
 189             p++;
 190         }
 191     }
 192 }
 193
 194 static char *encode_params(const game_params *params, bool full)
 195 {
 196     char ret[80];
 197
 198     sprintf(ret, "%d", params->w);
 199     if (full)
 200         sprintf(ret + strlen(ret), "d%c", towers_diffchars[params->diff]);
 201
 202     return dupstr(ret);
 203 }
 204
 205 static config_item *game_configure(const game_params *params)
 206 {
 207     config_item *ret;
 208     char buf[80];
 209
 210     ret = snewn(3, config_item);
 211
 212     ret[0].name = "Grid size";
 213     ret[0].type = C_STRING;
 214     sprintf(buf, "%d", params->w);
 215     ret[0].u.string.sval = dupstr(buf);
 216
 217     ret[1].name = "Difficulty";
 218     ret[1].type = C_CHOICES;
 219     ret[1].u.choices.choicenames = DIFFCONFIG;
 220     ret[1].u.choices.selected = params->diff;
 221
 222     ret[2].name = NULL;
 223     ret[2].type = C_END;
 224
 225     return ret;
 226 }
 227
 228 static game_params *custom_params(const config_item *cfg)
 229 {
 230     game_params *ret = snew(game_params);
 231
 232     ret->w = atoi(cfg[0].u.string.sval);
 233     ret->diff = cfg[1].u.choices.selected;
 234
 235     return ret;
 236 }
 237
 238 static const char *validate_params(const game_params *params, bool full)
 239 {
 240     if (params->w < 3 || params->w > 9)
 241         return "Grid size must be between 3 and 9";
 242     if (params->diff >= DIFFCOUNT)
 243         return "Unknown difficulty rating";
 244     return NULL;
 245 }
 246
 247 /* ----------------------------------------------------------------------
 248  * Solver.
 249  */
 250
 251 struct solver_ctx {
 252     int w, diff;
 253     bool started;
 254     int *clues;
 255     long *iscratch;
 256     int *dscratch;
 257 };
 258
 259 static int solver_easy(struct latin_solver *solver, void *vctx)
 260 {
 261     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 262     int w = ctx->w;
 263     int c, i, j, n, m, furthest;
 264     int start, step, cstart, cstep, clue, pos, cpos;
 265     int ret = 0;
 266 #ifdef STANDALONE_SOLVER
 267     char prefix[256];
 268 #endif
 269
 270     if (!ctx->started) {
 271         ctx->started = true;
 272         /*
 273          * One-off loop to help get started: when a pair of facing
 274          * clues sum to w+1, it must mean that the row consists of
 275          * two increasing sequences back to back, so we can
 276          * immediately place the highest digit by knowing the
 277          * lengths of those two sequences.
 278          */
 279         for (c = 0; c < 3*w; c = (c == w-1 ? 2*w : c+1)) {
 280             int c2 = c + w;
 281
 282             if (ctx->clues[c] && ctx->clues[c2] &&
 283                 ctx->clues[c] + ctx->clues[c2] == w+1) {
 284                 STARTSTEP(start, step, c, w);
 285                 CSTARTSTEP(cstart, cstep, c, w);
 286                 pos = start + (ctx->clues[c]-1)*step;
 287                 cpos = cstart + (ctx->clues[c]-1)*cstep;
 288                 if (solver->cube[cpos*w+w-1]) {
 289 #ifdef STANDALONE_SOLVER
 290                     if (solver_show_working) {
 291                         printf("%*sfacing clues on %s %d are maximal:\n",
 292                                solver_recurse_depth*4, "",
 293                                c>=2*w ? "row" : "column", c % w + 1);
 294                         printf("%*s  placing %d at (%d,%d)\n",
 295                                solver_recurse_depth*4, "",
 296                                w, pos%w+1, pos/w+1);
 297                     }
 298 #endif
 299                     latin_solver_place(solver, pos%w, pos/w, w);
 300                     ret = 1;
 301                 } else {
 302                     ret = -1;
 303                 }
 304             }
 305         }
 306
 307         if (ret)
 308             return ret;
 309     }
 310
 311     /*
 312      * Go over every clue doing reasonably simple heuristic
 313      * deductions.
 314      */
 315     for (c = 0; c < 4*w; c++) {
 316         clue = ctx->clues[c];
 317         if (!clue)
 318             continue;
 319         STARTSTEP(start, step, c, w);
 320         CSTARTSTEP(cstart, cstep, c, w);
 321
 322         /* Find the location of each number in the row. */
 323         for (i = 0; i < w; i++)
 324             ctx->dscratch[i] = w;
 325         for (i = 0; i < w; i++)
 326             if (solver->grid[start+i*step])
 327                 ctx->dscratch[solver->grid[start+i*step]-1] = i;
 328
 329         n = m = 0;
 330         furthest = w;
 331         for (i = w; i >= 1; i--) {
 332             if (ctx->dscratch[i-1] == w) {
 333                 break;
 334             } else if (ctx->dscratch[i-1] < furthest) {
 335                 furthest = ctx->dscratch[i-1];
 336                 m = i;
 337                 n++;
 338             }
 339         }
 340         if (clue == n+1 && furthest > 1) {
 341 #ifdef STANDALONE_SOLVER
 342             if (solver_show_working)
 343                 sprintf(prefix, "%*sclue %s %d is nearly filled:\n",
 344                         solver_recurse_depth*4, "",
 345                         cluepos[c/w], c%w+1);
 346             else
 347                 prefix[0] = '\0';              /* placate optimiser */
 348 #endif
 349             /*
 350              * We can already see an increasing sequence of the very
 351              * highest numbers, of length one less than that
 352              * specified in the clue. All of those numbers _must_ be
 353              * part of the clue sequence, so the number right next
 354              * to the clue must be the final one - i.e. it must be
 355              * bigger than any of the numbers between it and m. This
 356              * allows us to rule out small numbers in that square.
 357              *
 358              * (This is a generalisation of the obvious deduction
 359              * that when you see a clue saying 1, it must be right
 360              * next to the largest possible number; and similarly,
 361              * when you see a clue saying 2 opposite that, it must
 362              * be right next to the second-largest.)
 363              */
 364             j = furthest-1;  /* number of small numbers we can rule out */
 365             for (i = 1; i <= w && j > 0; i++) {
 366                 if (ctx->dscratch[i-1] < w && ctx->dscratch[i-1] >= furthest)
 367                     continue;          /* skip this number, it's elsewhere */
 368                 j--;
 369                 if (solver->cube[cstart*w+i-1]) {
 370 #ifdef STANDALONE_SOLVER
 371                     if (solver_show_working) {
 372                         printf("%s%*s  ruling out %d at (%d,%d)\n",
 373                                prefix, solver_recurse_depth*4, "",
 374                                i, start%w+1, start/w+1);
 375                         prefix[0] = '\0';
 376                     }
 377 #endif
 378                     solver->cube[cstart*w+i-1] = 0;
 379                     ret = 1;
 380                 }
 381             }
 382         }
 383
 384         if (ret)
 385             return ret;
 386
 387 #ifdef STANDALONE_SOLVER
 388             if (solver_show_working)
 389                 sprintf(prefix, "%*slower bounds for clue %s %d:\n",
 390                         solver_recurse_depth*4, "",
 391                         cluepos[c/w], c%w+1);
 392             else
 393                 prefix[0] = '\0';              /* placate optimiser */
 394 #endif
 395
 396         i = 0;
 397         for (n = w; n > 0; n--) {
 398             /*
 399              * The largest number cannot occur in the first (clue-1)
 400              * squares of the row, or else there wouldn't be space
 401              * for a sufficiently long increasing sequence which it
 402              * terminated. The second-largest number (not counting
 403              * any that are known to be on the far side of a larger
 404              * number and hence excluded from this sequence) cannot
 405              * occur in the first (clue-2) squares, similarly, and
 406              * so on.
 407              */
 408
 409             if (ctx->dscratch[n-1] < w) {
 410                 for (m = n+1; m < w; m++)
 411                     if (ctx->dscratch[m] < ctx->dscratch[n-1])
 412                         break;
 413                 if (m < w)
 414                     continue;          /* this number doesn't count */
 415             }
 416
 417             for (j = 0; j < clue - i - 1; j++)
 418                 if (solver->cube[(cstart + j*cstep)*w+n-1]) {
 419 #ifdef STANDALONE_SOLVER
 420                     if (solver_show_working) {
 421                         int pos = start+j*step;
 422                         printf("%s%*s  ruling out %d at (%d,%d)\n",
 423                                prefix, solver_recurse_depth*4, "",
 424                                n, pos%w+1, pos/w+1);
 425                         prefix[0] = '\0';
 426                     }
 427 #endif
 428                     solver->cube[(cstart + j*cstep)*w+n-1] = 0;
 429                     ret = 1;
 430                 }
 431             i++;
 432         }
 433     }
 434
 435     if (ret)
 436         return ret;
 437
 438     return 0;
 439 }
 440
 441 static int solver_hard(struct latin_solver *solver, void *vctx)
 442 {
 443     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 444     int w = ctx->w;
 445     int c, i, j, n, best, clue, start, step, ret;
 446     long bitmap;
 447 #ifdef STANDALONE_SOLVER
 448     char prefix[256];
 449 #endif
 450
 451     /*
 452      * Go over every clue analysing all possibilities.
 453      */
 454     for (c = 0; c < 4*w; c++) {
 455         clue = ctx->clues[c];
 456         if (!clue)
 457             continue;
 458         CSTARTSTEP(start, step, c, w);
 459
 460         for (i = 0; i < w; i++)
 461             ctx->iscratch[i] = 0;
 462
 463         /*
 464          * Instead of a tedious physical recursion, I iterate in the
 465          * scratch array through all possibilities. At any given
 466          * moment, i indexes the element of the box that will next
 467          * be incremented.
 468          */
 469         i = 0;
 470         ctx->dscratch[i] = 0;
 471         best = n = 0;
 472         bitmap = 0;
 473
 474         while (1) {
 475             if (i < w) {
 476                 /*
 477                  * Find the next valid value for cell i.
 478                  */
 479                 int limit = (n == clue ? best : w);
 480                 int pos = start + step * i;
 481                 for (j = ctx->dscratch[i] + 1; j <= limit; j++) {
 482                     if (bitmap & (1L << j))
 483                         continue;      /* used this one already */
 484                     if (!solver->cube[pos*w+j-1])
 485                         continue;      /* ruled out already */
 486
 487                     /* Found one. */
 488                     break;
 489                 }
 490
 491                 if (j > limit) {
 492                     /* No valid values left; drop back. */
 493                     i--;
 494                     if (i < 0)
 495                         break;         /* overall iteration is finished */
 496                     bitmap &= ~(1L << ctx->dscratch[i]);
 497                     if (ctx->dscratch[i] == best) {
 498                         n--;
 499                         best = 0;
 500                         for (j = 0; j < i; j++)
 501                             if (best < ctx->dscratch[j])
 502                                 best = ctx->dscratch[j];
 503                     }
 504                 } else {
 505                     /* Got a valid value; store it and move on. */
 506                     bitmap |= 1L << j;
 507                     ctx->dscratch[i++] = j;
 508                     if (j > best) {
 509                         best = j;
 510                         n++;
 511                     }
 512                     ctx->dscratch[i] = 0;
 513                 }
 514             } else {
 515                 if (n == clue) {
 516                     for (j = 0; j < w; j++)
 517                         ctx->iscratch[j] |= 1L << ctx->dscratch[j];
 518                 }
 519                 i--;
 520                 bitmap &= ~(1L << ctx->dscratch[i]);
 521                 if (ctx->dscratch[i] == best) {
 522                     n--;
 523                     best = 0;
 524                     for (j = 0; j < i; j++)
 525                         if (best < ctx->dscratch[j])
 526                             best = ctx->dscratch[j];
 527                 }
 528             }
 529         }
 530
 531 #ifdef STANDALONE_SOLVER
 532         if (solver_show_working)
 533             sprintf(prefix, "%*sexhaustive analysis of clue %s %d:\n",
 534                     solver_recurse_depth*4, "",
 535                     cluepos[c/w], c%w+1);
 536         else
 537             prefix[0] = '\0';          /* placate optimiser */
 538 #endif
 539
 540         ret = 0;
 541
 542         for (i = 0; i < w; i++) {
 543             int pos = start + step * i;
 544             for (j = 1; j <= w; j++) {
 545                 if (solver->cube[pos*w+j-1] &&
 546                     !(ctx->iscratch[i] & (1L << j))) {
 547 #ifdef STANDALONE_SOLVER
 548                     if (solver_show_working) {
 549                         printf("%s%*s  ruling out %d at (%d,%d)\n",
 550                                prefix, solver_recurse_depth*4, "",
 551                                j, pos/w+1, pos%w+1);
 552                         prefix[0] = '\0';
 553                     }
 554 #endif
 555                     solver->cube[pos*w+j-1] = 0;
 556                     ret = 1;
 557                 }
 558             }
 559
 560             /*
 561              * Once we find one clue we can do something with in
 562              * this way, revert to trying easier deductions, so as
 563              * not to generate solver diagnostics that make the
 564              * problem look harder than it is.
 565              */
 566             if (ret)
 567                 return ret;
 568         }
 569     }
 570
 571     return 0;
 572 }
 573
 574 #define SOLVER(upper,title,func,lower) func,
 575 static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) };
 576
 577 static bool towers_valid(struct latin_solver *solver, void *vctx)
 578 {
 579     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
 580     int w = ctx->w;
 581     int c, i, n, best, clue, start, step;
 582     for (c = 0; c < 4*w; c++) {
 583         clue = ctx->clues[c];
 584         if (!clue)
 585             continue;
 586
 587         STARTSTEP(start, step, c, w);
 588         n = best = 0;
 589         for (i = 0; i < w; i++) {
 590             if (solver->grid[start+i*step] > best) {
 591                 best = solver->grid[start+i*step];
 592                 n++;
 593             }
 594         }
 595
 596         if (n != clue) {
 597 #ifdef STANDALONE_SOLVER
 598             if (solver_show_working)
 599                 printf("%*sclue %s %d is violated\n",
 600                         solver_recurse_depth*4, "",
 601                         cluepos[c/w], c%w+1);
 602 #endif
 603             return false;
 604         }
 605     }
 606     return true;
 607 }
 608
 609 static int solver(int w, int *clues, digit *soln, int maxdiff)
 610 {
 611     int ret;
 612     struct solver_ctx ctx;
 613
 614     ctx.w = w;
 615     ctx.diff = maxdiff;
 616     ctx.clues = clues;
 617     ctx.started = false;
 618     ctx.iscratch = snewn(w, long);
 619     ctx.dscratch = snewn(w+1, int);
 620
 621     ret = latin_solver(soln, w, maxdiff,
 622                        DIFF_EASY, DIFF_HARD, DIFF_EXTREME,
 623                        DIFF_EXTREME, DIFF_UNREASONABLE,
 624                        towers_solvers, towers_valid, &ctx, NULL, NULL);
 625
 626     sfree(ctx.iscratch);
 627     sfree(ctx.dscratch);
 628
 629     return ret;
 630 }
 631
 632 /* ----------------------------------------------------------------------
 633  * Grid generation.
 634  */
 635
 636 static char *new_game_desc(const game_params *params, random_state *rs,
 637                            char **aux, bool interactive)
 638 {
 639     int w = params->w, a = w*w;
 640     digit *grid, *soln, *soln2;
 641     int *clues, *order;
 642     int i, ret;
 643     int diff = params->diff;
 644     char *desc, *p;
 645
 646     /*
 647      * Difficulty exceptions: some combinations of size and
 648      * difficulty cannot be satisfied, because all puzzles of at
 649      * most that difficulty are actually even easier.
 650      *
 651      * Remember to re-test this whenever a change is made to the
 652      * solver logic!
 653      *
 654      * I tested it using the following shell command:
 655
 656 for d in e h x u; do
 657   for i in {3..9}; do
 658     echo -n "./towers --generate 1 ${i}d${d}: "
 659     perl -e 'alarm 30; exec @ARGV' ./towers --generate 1 ${i}d${d} >/dev/null \
 660       && echo ok
 661   done
 662 done
 663
 664      * Of course, it's better to do that after taking the exceptions
 665      * _out_, so as to detect exceptions that should be removed as
 666      * well as those which should be added.
 667      */
 668     if (diff > DIFF_HARD && w <= 3)
 669         diff = DIFF_HARD;
 670
 671     grid = NULL;
 672     clues = snewn(4*w, int);
 673     soln = snewn(a, digit);
 674     soln2 = snewn(a, digit);
 675     order = snewn(max(4*w,a), int);
 676
 677     while (1) {
 678         /*
 679          * Construct a latin square to be the solution.
 680          */
 681         sfree(grid);
 682         grid = latin_generate(w, rs);
 683
 684         /*
 685          * Fill in the clues.
 686          */
 687         for (i = 0; i < 4*w; i++) {
 688             int start, step, j, k, best;
 689             STARTSTEP(start, step, i, w);
 690             k = best = 0;
 691             for (j = 0; j < w; j++) {
 692                 if (grid[start+j*step] > best) {
 693                     best = grid[start+j*step];
 694                     k++;
 695                 }
 696             }
 697             clues[i] = k;
 698         }
 699
 700         /*
 701          * Remove the grid numbers and then the clues, one by one,
 702          * for as long as the game remains soluble at the given
 703          * difficulty.
 704          */
 705         memcpy(soln, grid, a);
 706
 707         if (diff == DIFF_EASY && w <= 5) {
 708             /*
 709              * Special case: for Easy-mode grids that are small
 710              * enough, it's nice to be able to find completely empty
 711              * grids.
 712              */
 713             memset(soln2, 0, a);
 714             ret = solver(w, clues, soln2, diff);
 715             if (ret > diff)
 716                 continue;
 717         }
 718
 719         for (i = 0; i < a; i++)
 720             order[i] = i;
 721         shuffle(order, a, sizeof(*order), rs);
 722         for (i = 0; i < a; i++) {
 723             int j = order[i];
 724
 725             memcpy(soln2, grid, a);
 726             soln2[j] = 0;
 727             ret = solver(w, clues, soln2, diff);
 728             if (ret <= diff)
 729                 grid[j] = 0;
 730         }
 731
 732         if (diff > DIFF_EASY) {        /* leave all clues on Easy mode */
 733             for (i = 0; i < 4*w; i++)
 734                 order[i] = i;
 735             shuffle(order, 4*w, sizeof(*order), rs);
 736             for (i = 0; i < 4*w; i++) {
 737                 int j = order[i];
 738                 int clue = clues[j];
 739
 740                 memcpy(soln2, grid, a);
 741                 clues[j] = 0;
 742                 ret = solver(w, clues, soln2, diff);
 743                 if (ret > diff)
 744                     clues[j] = clue;
 745             }
 746         }
 747
 748         /*
 749          * See if the game can be solved at the specified difficulty
 750          * level, but not at the one below.
 751          */
 752         memcpy(soln2, grid, a);
 753         ret = solver(w, clues, soln2, diff);
 754         if (ret != diff)
 755             continue;                  /* go round again */
 756
 757         /*
 758          * We've got a usable puzzle!
 759          */
 760         break;
 761     }
 762
 763     /*
 764      * Encode the puzzle description.
 765      */
 766     desc = snewn(40*a, char);
 767     p = desc;
 768     for (i = 0; i < 4*w; i++) {
 769         if (i)
 770             *p++ = '/';
 771         if (clues[i])
 772             p += sprintf(p, "%d", clues[i]);
 773     }
 774     for (i = 0; i < a; i++)
 775         if (grid[i])
 776             break;
 777     if (i < a) {
 778         int run = 0;
 779
 780         *p++ = ',';
 781
 782         for (i = 0; i <= a; i++) {
 783             int n = (i < a ? grid[i] : -1);
 784
 785             if (!n)
 786                 run++;
 787             else {
 788                 if (run) {
 789                     while (run > 0) {
 790                         int thisrun = min(run, 26);
 791                         *p++ = thisrun - 1 + 'a';
 792                         run -= thisrun;
 793                     }
 794                 } else {
 795                     /*
 796                      * If there's a number in the very top left or
 797                      * bottom right, there's no point putting an
 798                      * unnecessary _ before or after it.
 799                      */
 800                     if (i > 0 && n > 0)
 801                         *p++ = '_';
 802                 }
 803                 if (n > 0)
 804                     p += sprintf(p, "%d", n);
 805                 run = 0;
 806             }
 807         }
 808     }
 809     *p++ = '\0';
 810     desc = sresize(desc, p - desc, char);
 811
 812     /*
 813      * Encode the solution.
 814      */
 815     *aux = snewn(a+2, char);
 816     (*aux)[0] = 'S';
 817     for (i = 0; i < a; i++)
 818         (*aux)[i+1] = '0' + soln[i];
 819     (*aux)[a+1] = '\0';
 820
 821     sfree(grid);
 822     sfree(clues);
 823     sfree(soln);
 824     sfree(soln2);
 825     sfree(order);
 826
 827     return desc;
 828 }
 829
 830 /* ----------------------------------------------------------------------
 831  * Gameplay.
 832  */
 833
 834 static const char *validate_desc(const game_params *params, const char *desc)
 835 {
 836     int w = params->w, a = w*w;
 837     const char *p = desc;
 838     int i, clue;
 839
 840     /*
 841      * Verify that the right number of clues are given, and that
 842      * they're in range.
 843      */
 844     for (i = 0; i < 4*w; i++) {
 845         if (!*p)
 846             return "Too few clues for grid size";
 847
 848         if (i > 0) {
 849             if (*p != '/')
 850                 return "Expected commas between clues";
 851             p++;
 852         }
 853
 854         if (isdigit((unsigned char)*p)) {
 855             clue = atoi(p);
 856             while (*p && isdigit((unsigned char)*p)) p++;
 857
 858             if (clue <= 0 || clue > w)
 859                 return "Clue number out of range";
 860         }
 861     }
 862     if (*p == '/')
 863         return "Too many clues for grid size";
 864
 865     if (*p == ',') {
 866         /*
 867          * Verify that the right amount of grid data is given, and
 868          * that any grid elements provided are in range.
 869          */
 870         int squares = 0;
 871
 872         p++;
 873         while (*p) {
 874             int c = *p++;
 875             if (c >= 'a' && c <= 'z') {
 876                 squares += c - 'a' + 1;
 877             } else if (c == '_') {
 878                 /* do nothing */;
 879             } else if (c > '0' && c <= '9') {
 880                 int val = atoi(p-1);
 881                 if (val < 1 || val > w)
 882                     return "Out-of-range number in grid description";
 883                 squares++;
 884                 while (*p && isdigit((unsigned char)*p)) p++;
 885             } else
 886                 return "Invalid character in game description";
 887         }
 888
 889         if (squares < a)
 890             return "Not enough data to fill grid";
 891
 892         if (squares > a)
 893             return "Too much data to fit in grid";
 894     }
 895
 896     return NULL;
 897 }
 898
 899 static key_label *game_request_keys(const game_params *params, int *nkeys)
 900 {
 901     int i;
 902     int w = params->w;
 903     key_label *keys = snewn(w+1, key_label);
 904     *nkeys = w + 1;
 905
 906     for (i = 0; i < w; i++) {
 907         if (i<9) keys[i].button = '1' + i;
 908         else keys[i].button = 'a' + i - 9;
 909
 910         keys[i].label = NULL;
 911     }
 912     keys[w].button = '\b';
 913     keys[w].label = NULL;
 914
 915     return keys;
 916 }
 917
 918 static game_state *new_game(midend *me, const game_params *params,
 919                             const char *desc)
 920 {
 921     int w = params->w, a = w*w;
 922     game_state *state = snew(game_state);
 923     const char *p = desc;
 924     int i;
 925
 926     state->par = *params;              /* structure copy */
 927     state->clues = snew(struct clues);
 928     state->clues->refcount = 1;
 929     state->clues->w = w;
 930     state->clues->clues = snewn(4*w, int);
 931     state->clues->immutable = snewn(a, digit);
 932     state->grid = snewn(a, digit);
 933     state->clues_done = snewn(4*w, bool);
 934     state->pencil = snewn(a, int);
 935
 936     for (i = 0; i < a; i++) {
 937         state->grid[i] = 0;
 938         state->pencil[i] = 0;
 939     }
 940
 941     memset(state->clues->immutable, 0, a);
 942     memset(state->clues_done, 0, 4*w*sizeof(bool));
 943
 944     for (i = 0; i < 4*w; i++) {
 945         if (i > 0) {
 946             assert(*p == '/');
 947             p++;
 948         }
 949         if (*p && isdigit((unsigned char)*p)) {
 950             state->clues->clues[i] = atoi(p);
 951             while (*p && isdigit((unsigned char)*p)) p++;
 952         } else
 953             state->clues->clues[i] = 0;
 954     }
 955
 956     if (*p == ',') {
 957         int pos = 0;
 958         p++;
 959         while (*p) {
 960             int c = *p++;
 961             if (c >= 'a' && c <= 'z') {
 962                 pos += c - 'a' + 1;
 963             } else if (c == '_') {
 964                 /* do nothing */;
 965             } else if (c > '0' && c <= '9') {
 966                 int val = atoi(p-1);
 967                 assert(val >= 1 && val <= w);
 968                 assert(pos < a);
 969                 state->grid[pos] = state->clues->immutable[pos] = val;
 970                 pos++;
 971                 while (*p && isdigit((unsigned char)*p)) p++;
 972             } else
 973                 assert(!"Corrupt game description");
 974         }
 975         assert(pos == a);
 976     }
 977     assert(!*p);
 978
 979     state->completed = false;
 980     state->cheated = false;
 981
 982     return state;
 983 }
 984
 985 static game_state *dup_game(const game_state *state)
 986 {
 987     int w = state->par.w, a = w*w;
 988     game_state *ret = snew(game_state);
 989
 990     ret->par = state->par;             /* structure copy */
 991
 992     ret->clues = state->clues;
 993     ret->clues->refcount++;
 994
 995     ret->grid = snewn(a, digit);
 996     ret->pencil = snewn(a, int);
 997     ret->clues_done = snewn(4*w, bool);
 998     memcpy(ret->grid, state->grid, a*sizeof(digit));
 999     memcpy(ret->pencil, state->pencil, a*sizeof(int));
1000     memcpy(ret->clues_done, state->clues_done, 4*w*sizeof(bool));
1001
1002     ret->completed = state->completed;
1003     ret->cheated = state->cheated;
1004
1005     return ret;
1006 }
1007
1008 static void free_game(game_state *state)
1009 {
1010     sfree(state->grid);
1011     sfree(state->pencil);
1012     sfree(state->clues_done);
1013     if (--state->clues->refcount <= 0) {
1014         sfree(state->clues->immutable);
1015         sfree(state->clues->clues);
1016         sfree(state->clues);
1017     }
1018     sfree(state);
1019 }
1020
1021 static char *solve_game(const game_state *state, const game_state *currstate,
1022                         const char *aux, const char **error)
1023 {
1024     int w = state->par.w, a = w*w;
1025     int i, ret;
1026     digit *soln;
1027     char *out;
1028
1029     if (aux)
1030         return dupstr(aux);
1031
1032     soln = snewn(a, digit);
1033     memcpy(soln, state->clues->immutable, a);
1034
1035     ret = solver(w, state->clues->clues, soln, DIFFCOUNT-1);
1036
1037     if (ret == diff_impossible) {
1038         *error = "No solution exists for this puzzle";
1039         out = NULL;
1040     } else if (ret == diff_ambiguous) {
1041         *error = "Multiple solutions exist for this puzzle";
1042         out = NULL;
1043     } else {
1044         out = snewn(a+2, char);
1045         out[0] = 'S';
1046         for (i = 0; i < a; i++)
1047             out[i+1] = '0' + soln[i];
1048         out[a+1] = '\0';
1049     }
1050
1051     sfree(soln);
1052     return out;
1053 }
1054
1055 static bool game_can_format_as_text_now(const game_params *params)
1056 {
1057     return true;
1058 }
1059
1060 static char *game_text_format(const game_state *state)
1061 {
1062     int w = state->par.w /* , a = w*w */;
1063     char *ret;
1064     char *p;
1065     int x, y;
1066     int total;
1067
1068     /*
1069      * We have:
1070      *  - a top clue row, consisting of three spaces, then w clue
1071      *    digits with spaces between (total 2*w+3 chars including
1072      *    newline)
1073      *  - a blank line (one newline)
1074      *  - w main rows, consisting of a left clue digit, two spaces,
1075      *    w grid digits with spaces between, two spaces and a right
1076      *    clue digit (total 2*w+6 chars each including newline)
1077      *  - a blank line (one newline)
1078      *  - a bottom clue row (same as top clue row)
1079      *  - terminating NUL.
1080      *
1081      * Total size is therefore 2*(2*w+3) + 2 + w*(2*w+6) + 1
1082      * = 2w^2+10w+9.
1083      */
1084     total = 2*w*w + 10*w + 9;
1085     ret = snewn(total, char);
1086     p = ret;
1087
1088     /* Top clue row. */
1089     *p++ = ' '; *p++ = ' ';
1090     for (x = 0; x < w; x++) {
1091         *p++ = ' ';
1092         *p++ = (state->clues->clues[x] ? '0' + state->clues->clues[x] : ' ');
1093     }
1094     *p++ = '\n';
1095
1096     /* Blank line. */
1097     *p++ = '\n';
1098
1099     /* Main grid. */
1100     for (y = 0; y < w; y++) {
1101         *p++ = (state->clues->clues[y+2*w] ? '0' + state->clues->clues[y+2*w] :
1102                 ' ');
1103         *p++ = ' ';
1104         for (x = 0; x < w; x++) {
1105             *p++ = ' ';
1106             *p++ = (state->grid[y*w+x] ? '0' + state->grid[y*w+x] : ' ');
1107         }
1108         *p++ = ' '; *p++ = ' ';
1109         *p++ = (state->clues->clues[y+3*w] ? '0' + state->clues->clues[y+3*w] :
1110                 ' ');
1111         *p++ = '\n';
1112     }
1113
1114     /* Blank line. */
1115     *p++ = '\n';
1116
1117     /* Bottom clue row. */
1118     *p++ = ' '; *p++ = ' ';
1119     for (x = 0; x < w; x++) {
1120         *p++ = ' ';
1121         *p++ = (state->clues->clues[x+w] ? '0' + state->clues->clues[x+w] :
1122                 ' ');
1123     }
1124     *p++ = '\n';
1125
1126     *p++ = '\0';
1127     assert(p == ret + total);
1128
1129     return ret;
1130 }
1131
1132 struct game_ui {
1133     /*
1134      * These are the coordinates of the currently highlighted
1135      * square on the grid, if hshow = 1.
1136      */
1137     int hx, hy;
1138     /*
1139      * This indicates whether the current highlight is a
1140      * pencil-mark one or a real one.
1141      */
1142     bool hpencil;
1143     /*
1144      * This indicates whether or not we're showing the highlight
1145      * (used to be hx = hy = -1); important so that when we're
1146      * using the cursor keys it doesn't keep coming back at a
1147      * fixed position. When hshow = 1, pressing a valid number
1148      * or letter key or Space will enter that number or letter in the grid.
1149      */
1150     bool hshow;
1151     /*
1152      * This indicates whether we're using the highlight as a cursor;
1153      * it means that it doesn't vanish on a keypress, and that it is
1154      * allowed on immutable squares.
1155      */
1156     bool hcursor;
1157 };
1158
1159 static game_ui *new_ui(const game_state *state)
1160 {
1161     game_ui *ui = snew(game_ui);
1162
1163     ui->hx = ui->hy = 0;
1164     ui->hpencil = false;
1165     ui->hshow = false;
1166     ui->hcursor = false;
1167
1168     return ui;
1169 }
1170
1171 static void free_ui(game_ui *ui)
1172 {
1173     sfree(ui);
1174 }
1175
1176 static char *encode_ui(const game_ui *ui)
1177 {
1178     return NULL;
1179 }
1180
1181 static void decode_ui(game_ui *ui, const char *encoding)
1182 {
1183 }
1184
1185 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1186                                const game_state *newstate)
1187 {
1188     int w = newstate->par.w;
1189     /*
1190      * We prevent pencil-mode highlighting of a filled square, unless
1191      * we're using the cursor keys. So if the user has just filled in
1192      * a square which we had a pencil-mode highlight in (by Undo, or
1193      * by Redo, or by Solve), then we cancel the highlight.
1194      */
1195     if (ui->hshow && ui->hpencil && !ui->hcursor &&
1196         newstate->grid[ui->hy * w + ui->hx] != 0) {
1197         ui->hshow = false;
1198     }
1199 }
1200
1201 #define PREFERRED_TILESIZE 48
1202 #define TILESIZE (ds->tilesize)
1203 #define BORDER (TILESIZE * 9 / 8)
1204 #define COORD(x) ((x)*TILESIZE + BORDER)
1205 #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1)
1206
1207 /* These always return positive values, though y offsets are actually -ve */
1208 #define X_3D_DISP(height, w) ((height) * TILESIZE / (8 * (w)))
1209 #define Y_3D_DISP(height, w) ((height) * TILESIZE / (4 * (w)))
1210
1211 #define FLASH_TIME 0.4F
1212
1213 #define DF_PENCIL_SHIFT 16
1214 #define DF_CLUE_DONE 0x10000
1215 #define DF_ERROR 0x8000
1216 #define DF_HIGHLIGHT 0x4000
1217 #define DF_HIGHLIGHT_PENCIL 0x2000
1218 #define DF_IMMUTABLE 0x1000
1219 #define DF_PLAYAREA 0x0800
1220 #define DF_DIGIT_MASK 0x00FF
1221
1222 struct game_drawstate {
1223     int tilesize;
1224     bool three_d;       /* default 3D graphics are user-disableable */
1225     bool started;
1226     long *tiles;                       /* (w+2)*(w+2) temp space */
1227     long *drawn;                       /* (w+2)*(w+2)*4: current drawn data */
1228     bool *errtmp;
1229 };
1230
1231 static bool check_errors(const game_state *state, bool *errors)
1232 {
1233     int w = state->par.w /*, a = w*w */;
1234     int W = w+2, A = W*W;              /* the errors array is (w+2) square */
1235     int *clues = state->clues->clues;
1236     digit *grid = state->grid;
1237     int i, x, y;
1238     bool errs = false;
1239     int tmp[32];
1240
1241     assert(w < lenof(tmp));
1242
1243     if (errors)
1244         for (i = 0; i < A; i++)
1245             errors[i] = false;
1246
1247     for (y = 0; y < w; y++) {
1248         unsigned long mask = 0, errmask = 0;
1249         for (x = 0; x < w; x++) {
1250             unsigned long bit = 1UL << grid[y*w+x];
1251             errmask |= (mask & bit);
1252             mask |= bit;
1253         }
1254
1255         if (mask != (1L << (w+1)) - (1L << 1)) {
1256             errs = true;
1257             errmask &= ~1UL;
1258             if (errors) {
1259                 for (x = 0; x < w; x++)
1260                     if (errmask & (1UL << grid[y*w+x]))
1261                         errors[(y+1)*W+(x+1)] = true;
1262             }
1263         }
1264     }
1265
1266     for (x = 0; x < w; x++) {
1267         unsigned long mask = 0, errmask = 0;
1268         for (y = 0; y < w; y++) {
1269             unsigned long bit = 1UL << grid[y*w+x];
1270             errmask |= (mask & bit);
1271             mask |= bit;
1272         }
1273
1274         if (mask != (1 << (w+1)) - (1 << 1)) {
1275             errs = true;
1276             errmask &= ~1UL;
1277             if (errors) {
1278                 for (y = 0; y < w; y++)
1279                     if (errmask & (1UL << grid[y*w+x]))
1280                         errors[(y+1)*W+(x+1)] = true;
1281             }
1282         }
1283     }
1284
1285     for (i = 0; i < 4*w; i++) {
1286         int start, step, j, n, best;
1287         STARTSTEP(start, step, i, w);
1288
1289         if (!clues[i])
1290             continue;
1291
1292         best = n = 0;
1293         for (j = 0; j < w; j++) {
1294             int number = grid[start+j*step];
1295             if (!number)
1296                 break;                 /* can't tell what happens next */
1297             if (number > best) {
1298                 best = number;
1299                 n++;
1300             }
1301         }
1302
1303         if (n > clues[i] || (best == w && n < clues[i]) ||
1304             (best < w && n == clues[i])) {
1305             if (errors) {
1306                 int x, y;
1307                 CLUEPOS(x, y, i, w);
1308                 errors[(y+1)*W+(x+1)] = true;
1309             }
1310             errs = true;
1311         }
1312     }
1313
1314     return errs;
1315 }
1316
1317 static int clue_index(const game_state *state, int x, int y)
1318 {
1319     int w = state->par.w;
1320
1321     if (x == -1 || x == w)
1322         return w * (x == -1 ? 2 : 3) + y;
1323     else if (y == -1 || y == w)
1324         return (y == -1 ? 0 : w) + x;
1325
1326     return -1;
1327 }
1328
1329 static bool is_clue(const game_state *state, int x, int y)
1330 {
1331     int w = state->par.w;
1332
1333     if (((x == -1 || x == w) && y >= 0 && y < w) ||
1334         ((y == -1 || y == w) && x >= 0 && x < w))
1335     {
1336         if (state->clues->clues[clue_index(state, x, y)] & DF_DIGIT_MASK)
1337             return true;
1338     }
1339
1340     return false;
1341 }
1342
1343 static char *interpret_move(const game_state *state, game_ui *ui,
1344                             const game_drawstate *ds,
1345                             int x, int y, int button)
1346 {
1347     int w = state->par.w;
1348     bool shift_or_control = button & (MOD_SHFT | MOD_CTRL);
1349     int tx, ty;
1350     char buf[80];
1351
1352     button &= ~MOD_MASK;
1353
1354     tx = FROMCOORD(x);
1355     ty = FROMCOORD(y);
1356
1357     if (ds->three_d) {
1358         /*
1359          * In 3D mode, just locating the mouse click in the natural
1360          * square grid may not be sufficient to tell which tower the
1361          * user clicked on. Investigate the _tops_ of the nearby
1362          * towers to see if a click on one grid square was actually
1363          * a click on a tower protruding into that region from
1364          * another.
1365          */
1366         int dx, dy;
1367         for (dy = 0; dy <= 1; dy++)
1368             for (dx = 0; dx >= -1; dx--) {
1369                 int cx = tx + dx, cy = ty + dy;
1370                 if (cx >= 0 && cx < w && cy >= 0 && cy < w) {
1371                     int height = state->grid[cy*w+cx];
1372                     int bx = COORD(cx), by = COORD(cy);
1373                     int ox = bx + X_3D_DISP(height, w);
1374                     int oy = by - Y_3D_DISP(height, w);
1375                     if (/* on top face? */
1376                         (x - ox >= 0 && x - ox < TILESIZE &&
1377                          y - oy >= 0 && y - oy < TILESIZE) ||
1378                         /* in triangle between top-left corners? */
1379                         (ox > bx && x >= bx && x <= ox && y <= by &&
1380                          (by-y) * (ox-bx) <= (by-oy) * (x-bx)) ||
1381                         /* in triangle between bottom-right corners? */
1382                         (ox > bx && x >= bx+TILESIZE && x <= ox+TILESIZE &&
1383                          y >= oy+TILESIZE &&
1384                          (by-y+TILESIZE)*(ox-bx) >= (by-oy)*(x-bx-TILESIZE))) {
1385                         tx = cx;
1386                         ty = cy;
1387                     }
1388                 }
1389             }
1390     }
1391
1392     if (tx >= 0 && tx < w && ty >= 0 && ty < w) {
1393         if (button == LEFT_BUTTON) {
1394             if (tx == ui->hx && ty == ui->hy &&
1395                 ui->hshow && !ui->hpencil) {
1396                 ui->hshow = false;
1397             } else {
1398                 ui->hx = tx;
1399                 ui->hy = ty;
1400                 ui->hshow = !state->clues->immutable[ty*w+tx];
1401                 ui->hpencil = false;
1402             }
1403             ui->hcursor = false;
1404             return UI_UPDATE;
1405         }
1406         if (button == RIGHT_BUTTON) {
1407             /*
1408              * Pencil-mode highlighting for non filled squares.
1409              */
1410             if (state->grid[ty*w+tx] == 0) {
1411                 if (tx == ui->hx && ty == ui->hy &&
1412                     ui->hshow && ui->hpencil) {
1413                     ui->hshow = false;
1414                 } else {
1415                     ui->hpencil = true;
1416                     ui->hx = tx;
1417                     ui->hy = ty;
1418                     ui->hshow = true;
1419                 }
1420             } else {
1421                 ui->hshow = false;
1422             }
1423             ui->hcursor = false;
1424             return UI_UPDATE;
1425         }
1426     } else if (button == LEFT_BUTTON) {
1427         if (is_clue(state, tx, ty)) {
1428             sprintf(buf, "%c%d,%d", 'D', tx, ty);
1429             return dupstr(buf);
1430         }
1431     }
1432     if (IS_CURSOR_MOVE(button)) {
1433         if (shift_or_control) {
1434             int x = ui->hx, y = ui->hy;
1435             switch (button) {
1436             case CURSOR_LEFT:   x = -1; break;
1437             case CURSOR_RIGHT:  x =  w; break;
1438             case CURSOR_UP:     y = -1; break;
1439             case CURSOR_DOWN:   y =  w; break;
1440             }
1441             if (is_clue(state, x, y)) {
1442                 sprintf(buf, "%c%d,%d", 'D', x, y);
1443                 return dupstr(buf);
1444             }
1445             return NULL;
1446         }
1447         move_cursor(button, &ui->hx, &ui->hy, w, w, false);
1448         ui->hshow = true;
1449         ui->hcursor = true;
1450         return UI_UPDATE;
1451     }
1452     if (ui->hshow &&
1453         (button == CURSOR_SELECT)) {
1454         ui->hpencil = !ui->hpencil;
1455         ui->hcursor = true;
1456         return UI_UPDATE;
1457     }
1458
1459     if (ui->hshow &&
1460         ((button >= '0' && button <= '9' && button - '0' <= w) ||
1461          button == CURSOR_SELECT2 || button == '\b')) {
1462         int n = button - '0';
1463         if (button == CURSOR_SELECT2 || button == '\b')
1464             n = 0;
1465
1466         /*
1467          * Can't make pencil marks in a filled square. This can only
1468          * become highlighted if we're using cursor keys.
1469          */
1470         if (ui->hpencil && state->grid[ui->hy*w+ui->hx])
1471             return NULL;
1472
1473         /*
1474          * Can't do anything to an immutable square.
1475          */
1476         if (state->clues->immutable[ui->hy*w+ui->hx])
1477             return NULL;
1478
1479         sprintf(buf, "%c%d,%d,%d",
1480                 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1481
1482         if (!ui->hcursor) ui->hshow = false;
1483
1484         return dupstr(buf);
1485     }
1486
1487     if (button == 'M' || button == 'm')
1488         return dupstr("M");
1489
1490     return NULL;
1491 }
1492
1493 static game_state *execute_move(const game_state *from, const char *move)
1494 {
1495     int w = from->par.w, a = w*w;
1496     game_state *ret = dup_game(from);
1497     int x, y, i, n;
1498
1499     if (move[0] == 'S') {
1500         ret->completed = ret->cheated = true;
1501
1502         for (i = 0; i < a; i++) {
1503             if (move[i+1] < '1' || move[i+1] > '0'+w)
1504                 goto badmove;
1505             ret->grid[i] = move[i+1] - '0';
1506             ret->pencil[i] = 0;
1507         }
1508
1509         if (move[a+1] != '\0')
1510             goto badmove;
1511
1512         return ret;
1513     } else if ((move[0] == 'P' || move[0] == 'R') &&
1514         sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1515         x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) {
1516         if (from->clues->immutable[y*w+x])
1517             goto badmove;
1518
1519         if (move[0] == 'P' && n > 0) {
1520             ret->pencil[y*w+x] ^= 1L << n;
1521         } else {
1522             ret->grid[y*w+x] = n;
1523             ret->pencil[y*w+x] = 0;
1524
1525             if (!ret->completed && !check_errors(ret, NULL))
1526                 ret->completed = true;
1527         }
1528         return ret;
1529     } else if (move[0] == 'M') {
1530         /*
1531          * Fill in absolutely all pencil marks everywhere. (I
1532          * wouldn't use this for actual play, but it's a handy
1533          * starting point when following through a set of
1534          * diagnostics output by the standalone solver.)
1535          */
1536         for (i = 0; i < a; i++) {
1537             if (!ret->grid[i])
1538                 ret->pencil[i] = (1L << (w+1)) - (1L << 1);
1539         }
1540         return ret;
1541     } else if (move[0] == 'D' && sscanf(move+1, "%d,%d", &x, &y) == 2 &&
1542                is_clue(from, x, y)) {
1543         int index = clue_index(from, x, y);
1544         ret->clues_done[index] = !ret->clues_done[index];
1545         return ret;
1546     }
1547
1548   badmove:
1549     /* couldn't parse move string */
1550     free_game(ret);
1551     return NULL;
1552 }
1553
1554 /* ----------------------------------------------------------------------
1555  * Drawing routines.
1556  */
1557
1558 #define SIZE(w) ((w) * TILESIZE + 2*BORDER)
1559
1560 static void game_compute_size(const game_params *params, int tilesize,
1561                               int *x, int *y)
1562 {
1563     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1564     struct { int tilesize; } ads, *ds = &ads;
1565     ads.tilesize = tilesize;
1566
1567     *x = *y = SIZE(params->w);
1568 }
1569
1570 static void game_set_size(drawing *dr, game_drawstate *ds,
1571                           const game_params *params, int tilesize)
1572 {
1573     ds->tilesize = tilesize;
1574 }
1575
1576 static float *game_colours(frontend *fe, int *ncolours)
1577 {
1578     float *ret = snewn(3 * NCOLOURS, float);
1579
1580     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1581
1582     ret[COL_GRID * 3 + 0] = 0.0F;
1583     ret[COL_GRID * 3 + 1] = 0.0F;
1584     ret[COL_GRID * 3 + 2] = 0.0F;
1585
1586     ret[COL_USER * 3 + 0] = 0.0F;
1587     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1588     ret[COL_USER * 3 + 2] = 0.0F;
1589
1590     ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
1591     ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
1592     ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
1593
1594     ret[COL_ERROR * 3 + 0] = 1.0F;
1595     ret[COL_ERROR * 3 + 1] = 0.0F;
1596     ret[COL_ERROR * 3 + 2] = 0.0F;
1597
1598     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1599     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1600     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1601
1602     ret[COL_DONE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F;
1603     ret[COL_DONE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F;
1604     ret[COL_DONE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F;
1605
1606     *ncolours = NCOLOURS;
1607     return ret;
1608 }
1609
1610 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1611 {
1612     int w = state->par.w /*, a = w*w */;
1613     struct game_drawstate *ds = snew(struct game_drawstate);
1614     int i;
1615
1616     ds->tilesize = 0;
1617     ds->three_d = !getenv("TOWERS_2D");
1618     ds->started = false;
1619     ds->tiles = snewn((w+2)*(w+2), long);
1620     ds->drawn = snewn((w+2)*(w+2)*4, long);
1621     for (i = 0; i < (w+2)*(w+2)*4; i++)
1622         ds->drawn[i] = -1;
1623     ds->errtmp = snewn((w+2)*(w+2), bool);
1624
1625     return ds;
1626 }
1627
1628 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1629 {
1630     sfree(ds->errtmp);
1631     sfree(ds->tiles);
1632     sfree(ds->drawn);
1633     sfree(ds);
1634 }
1635
1636 static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues,
1637                       int x, int y, long tile)
1638 {
1639     int w = clues->w /* , a = w*w */;
1640     int tx, ty, bg;
1641     char str[64];
1642
1643     tx = COORD(x);
1644     ty = COORD(y);
1645
1646     bg = (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND;
1647
1648     /* draw tower */
1649     if (ds->three_d && (tile & DF_PLAYAREA) && (tile & DF_DIGIT_MASK)) {
1650         int coords[8];
1651         int xoff = X_3D_DISP(tile & DF_DIGIT_MASK, w);
1652         int yoff = Y_3D_DISP(tile & DF_DIGIT_MASK, w);
1653
1654         /* left face of tower */
1655         coords[0] = tx;
1656         coords[1] = ty - 1;
1657         coords[2] = tx;
1658         coords[3] = ty + TILESIZE - 1;
1659         coords[4] = coords[2] + xoff;
1660         coords[5] = coords[3] - yoff;
1661         coords[6] = coords[0] + xoff;
1662         coords[7] = coords[1] - yoff;
1663         draw_polygon(dr, coords, 4, bg, COL_GRID);
1664
1665         /* bottom face of tower */
1666         coords[0] = tx + TILESIZE;
1667         coords[1] = ty + TILESIZE - 1;
1668         coords[2] = tx;
1669         coords[3] = ty + TILESIZE - 1;
1670         coords[4] = coords[2] + xoff;
1671         coords[5] = coords[3] - yoff;
1672         coords[6] = coords[0] + xoff;
1673         coords[7] = coords[1] - yoff;
1674         draw_polygon(dr, coords, 4, bg, COL_GRID);
1675
1676         /* now offset all subsequent drawing to the top of the tower */
1677         tx += xoff;
1678         ty -= yoff;
1679     }
1680
1681     /* erase background */
1682     draw_rect(dr, tx, ty, TILESIZE, TILESIZE, bg);
1683
1684     /* pencil-mode highlight */
1685     if (tile & DF_HIGHLIGHT_PENCIL) {
1686         int coords[6];
1687         coords[0] = tx;
1688         coords[1] = ty;
1689         coords[2] = tx+TILESIZE/2;
1690         coords[3] = ty;
1691         coords[4] = tx;
1692         coords[5] = ty+TILESIZE/2;
1693         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1694     }
1695
1696     /* draw box outline */
1697     if (tile & DF_PLAYAREA) {
1698         int coords[8];
1699         coords[0] = tx;
1700         coords[1] = ty - 1;
1701         coords[2] = tx + TILESIZE;
1702         coords[3] = ty - 1;
1703         coords[4] = tx + TILESIZE;
1704         coords[5] = ty + TILESIZE - 1;
1705         coords[6] = tx;
1706         coords[7] = ty + TILESIZE - 1;
1707         draw_polygon(dr, coords, 4, -1, COL_GRID);
1708     }
1709
1710     /* new number needs drawing? */
1711     if (tile & DF_DIGIT_MASK) {
1712         int color;
1713
1714         str[1] = '\0';
1715         str[0] = (tile & DF_DIGIT_MASK) + '0';
1716
1717         if (tile & DF_ERROR)
1718             color = COL_ERROR;
1719         else if (tile & DF_CLUE_DONE)
1720             color = COL_DONE;
1721         else if (x < 0 || y < 0 || x >= w || y >= w)
1722             color = COL_GRID;
1723         else if (tile & DF_IMMUTABLE)
1724             color = COL_GRID;
1725         else
1726             color = COL_USER;
1727
1728         draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, FONT_VARIABLE,
1729                   (tile & DF_PLAYAREA ? TILESIZE/2 : TILESIZE*2/5),
1730                   ALIGN_VCENTRE | ALIGN_HCENTRE, color, str);
1731     } else {
1732         int i, j, npencil;
1733         int pl, pr, pt, pb;
1734         float bestsize;
1735         int pw, ph, minph, pbest, fontsize;
1736
1737         /* Count the pencil marks required. */
1738         for (i = 1, npencil = 0; i <= w; i++)
1739             if (tile & (1L << (i + DF_PENCIL_SHIFT)))
1740                 npencil++;
1741         if (npencil) {
1742
1743             minph = 2;
1744
1745             /*
1746              * Determine the bounding rectangle within which we're going
1747              * to put the pencil marks.
1748              */
1749             /* Start with the whole square, minus space for impinging towers */
1750             pl = tx + (ds->three_d ? X_3D_DISP(w,w) : 0);
1751             pr = tx + TILESIZE;
1752             pt = ty;
1753             pb = ty + TILESIZE - (ds->three_d ? Y_3D_DISP(w,w) : 0);
1754
1755             /*
1756              * We arrange our pencil marks in a grid layout, with
1757              * the number of rows and columns adjusted to allow the
1758              * maximum font size.
1759              *
1760              * So now we work out what the grid size ought to be.
1761              */
1762             bestsize = 0.0;
1763             pbest = 0;
1764             /* Minimum */
1765             for (pw = 3; pw < max(npencil,4); pw++) {
1766                 float fw, fh, fs;
1767
1768                 ph = (npencil + pw - 1) / pw;
1769                 ph = max(ph, minph);
1770                 fw = (pr - pl) / (float)pw;
1771                 fh = (pb - pt) / (float)ph;
1772                 fs = min(fw, fh);
1773                 if (fs > bestsize) {
1774                     bestsize = fs;
1775                     pbest = pw;
1776                 }
1777             }
1778             assert(pbest > 0);
1779             pw = pbest;
1780             ph = (npencil + pw - 1) / pw;
1781             ph = max(ph, minph);
1782
1783             /*
1784              * Now we've got our grid dimensions, work out the pixel
1785              * size of a grid element, and round it to the nearest
1786              * pixel. (We don't want rounding errors to make the
1787              * grid look uneven at low pixel sizes.)
1788              */
1789             fontsize = min((pr - pl) / pw, (pb - pt) / ph);
1790
1791             /*
1792              * Centre the resulting figure in the square.
1793              */
1794             pl = pl + (pr - pl - fontsize * pw) / 2;
1795             pt = pt + (pb - pt - fontsize * ph) / 2;
1796
1797             /*
1798              * Now actually draw the pencil marks.
1799              */
1800             for (i = 1, j = 0; i <= w; i++)
1801                 if (tile & (1L << (i + DF_PENCIL_SHIFT))) {
1802                     int dx = j % pw, dy = j / pw;
1803
1804                     str[1] = '\0';
1805                     str[0] = i + '0';
1806                     draw_text(dr, pl + fontsize * (2*dx+1) / 2,
1807                               pt + fontsize * (2*dy+1) / 2,
1808                               FONT_VARIABLE, fontsize,
1809                               ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1810                     j++;
1811                 }
1812         }
1813     }
1814 }
1815
1816 static void game_redraw(drawing *dr, game_drawstate *ds,
1817                         const game_state *oldstate, const game_state *state,
1818                         int dir, const game_ui *ui,
1819                         float animtime, float flashtime)
1820 {
1821     int w = state->par.w /*, a = w*w */;
1822     int i, x, y;
1823
1824     if (!ds->started) {
1825         /*
1826          * The initial contents of the window are not guaranteed and
1827          * can vary with front ends. To be on the safe side, all
1828          * games should start by drawing a big background-colour
1829          * rectangle covering the whole window.
1830          */
1831         draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND);
1832
1833         draw_update(dr, 0, 0, SIZE(w), SIZE(w));
1834
1835         ds->started = true;
1836     }
1837
1838     check_errors(state, ds->errtmp);
1839
1840     /*
1841      * Work out what data each tile should contain.
1842      */
1843     for (i = 0; i < (w+2)*(w+2); i++)
1844         ds->tiles[i] = 0;              /* completely blank square */
1845     /* The clue squares... */
1846     for (i = 0; i < 4*w; i++) {
1847         long tile = state->clues->clues[i];
1848
1849         CLUEPOS(x, y, i, w);
1850
1851         if (ds->errtmp[(y+1)*(w+2)+(x+1)])
1852             tile |= DF_ERROR;
1853         else if (state->clues_done[i])
1854             tile |= DF_CLUE_DONE;
1855
1856         ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
1857     }
1858     /* ... and the main grid. */
1859     for (y = 0; y < w; y++) {
1860         for (x = 0; x < w; x++) {
1861             long tile = DF_PLAYAREA;
1862
1863             if (state->grid[y*w+x])
1864                 tile |= state->grid[y*w+x];
1865             else
1866                 tile |= (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT;
1867
1868             if (ui->hshow && ui->hx == x && ui->hy == y)
1869                 tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT);
1870
1871             if (state->clues->immutable[y*w+x])
1872                 tile |= DF_IMMUTABLE;
1873
1874             if (flashtime > 0 &&
1875                 (flashtime <= FLASH_TIME/3 ||
1876                  flashtime >= FLASH_TIME*2/3))
1877                 tile |= DF_HIGHLIGHT;  /* completion flash */
1878
1879             if (ds->errtmp[(y+1)*(w+2)+(x+1)])
1880                 tile |= DF_ERROR;
1881
1882             ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
1883         }
1884     }
1885
1886     /*
1887      * Now actually draw anything that needs to be changed.
1888      */
1889     for (y = 0; y < w+2; y++) {
1890         for (x = 0; x < w+2; x++) {
1891             long tl, tr, bl, br;
1892             int i = y*(w+2)+x;
1893
1894             tr = ds->tiles[y*(w+2)+x];
1895             tl = (x == 0 ? 0 : ds->tiles[y*(w+2)+(x-1)]);
1896             br = (y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+x]);
1897             bl = (x == 0 || y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+(x-1)]);
1898
1899             if (ds->drawn[i*4] != tl || ds->drawn[i*4+1] != tr ||
1900                 ds->drawn[i*4+2] != bl || ds->drawn[i*4+3] != br) {
1901                 clip(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE);
1902
1903                 draw_tile(dr, ds, state->clues, x-1, y-1, tr);
1904                 if (x > 0)
1905                     draw_tile(dr, ds, state->clues, x-2, y-1, tl);
1906                 if (y <= w)
1907                     draw_tile(dr, ds, state->clues, x-1, y, br);
1908                 if (x > 0 && y <= w)
1909                     draw_tile(dr, ds, state->clues, x-2, y, bl);
1910
1911                 unclip(dr);
1912                 draw_update(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE);
1913
1914                 ds->drawn[i*4] = tl;
1915                 ds->drawn[i*4+1] = tr;
1916                 ds->drawn[i*4+2] = bl;
1917                 ds->drawn[i*4+3] = br;
1918             }
1919         }
1920     }
1921 }
1922
1923 static float game_anim_length(const game_state *oldstate,
1924                               const game_state *newstate, int dir, game_ui *ui)
1925 {
1926     return 0.0F;
1927 }
1928
1929 static float game_flash_length(const game_state *oldstate,
1930                                const game_state *newstate, int dir, game_ui *ui)
1931 {
1932     if (!oldstate->completed && newstate->completed &&
1933         !oldstate->cheated && !newstate->cheated)
1934         return FLASH_TIME;
1935     return 0.0F;
1936 }
1937
1938 static void game_get_cursor_location(const game_ui *ui,
1939                                      const game_drawstate *ds,
1940                                      const game_state *state,
1941                                      const game_params *params,
1942                                      int *x, int *y, int *w, int *h)
1943 {
1944     if(ui->hshow) {
1945         *x = COORD(ui->hx);
1946         *y = COORD(ui->hy);
1947         *w = *h = TILESIZE;
1948     }
1949 }
1950
1951 static int game_status(const game_state *state)
1952 {
1953     return state->completed ? +1 : 0;
1954 }
1955
1956 static bool game_timing_state(const game_state *state, game_ui *ui)
1957 {
1958     if (state->completed)
1959         return false;
1960     return true;
1961 }
1962
1963 static void game_print_size(const game_params *params, float *x, float *y)
1964 {
1965     int pw, ph;
1966
1967     /*
1968      * We use 9mm squares by default, like Solo.
1969      */
1970     game_compute_size(params, 900, &pw, &ph);
1971     *x = pw / 100.0F;
1972     *y = ph / 100.0F;
1973 }
1974
1975 static void game_print(drawing *dr, const game_state *state, int tilesize)
1976 {
1977     int w = state->par.w;
1978     int ink = print_mono_colour(dr, 0);
1979     int i, x, y;
1980
1981     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1982     game_drawstate ads, *ds = &ads;
1983     game_set_size(dr, ds, NULL, tilesize);
1984
1985     /*
1986      * Border.
1987      */
1988     print_line_width(dr, 3 * TILESIZE / 40);
1989     draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink);
1990
1991     /*
1992      * Main grid.
1993      */
1994     for (x = 1; x < w; x++) {
1995         print_line_width(dr, TILESIZE / 40);
1996         draw_line(dr, BORDER+x*TILESIZE, BORDER,
1997                   BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink);
1998     }
1999     for (y = 1; y < w; y++) {
2000         print_line_width(dr, TILESIZE / 40);
2001         draw_line(dr, BORDER, BORDER+y*TILESIZE,
2002                   BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink);
2003     }
2004
2005     /*
2006      * Clues.
2007      */
2008     for (i = 0; i < 4*w; i++) {
2009         char str[128];
2010
2011         if (!state->clues->clues[i])
2012             continue;
2013
2014         CLUEPOS(x, y, i, w);
2015
2016         sprintf (str, "%d", state->clues->clues[i]);
2017
2018         draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
2019                   BORDER + y*TILESIZE + TILESIZE/2,
2020                   FONT_VARIABLE, TILESIZE/2,
2021                   ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
2022     }
2023
2024     /*
2025      * Numbers for the solution, if any.
2026      */
2027     for (y = 0; y < w; y++)
2028         for (x = 0; x < w; x++)
2029             if (state->grid[y*w+x]) {
2030                 char str[2];
2031                 str[1] = '\0';
2032                 str[0] = state->grid[y*w+x] + '0';
2033                 draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
2034                           BORDER + y*TILESIZE + TILESIZE/2,
2035                           FONT_VARIABLE, TILESIZE/2,
2036                           ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
2037             }
2038 }
2039
2040 #ifdef COMBINED
2041 #define thegame towers
2042 #endif
2043
2044 const struct game thegame = {
2045     "Towers", "games.towers", "towers",
2046     default_params,
2047     game_fetch_preset, NULL,
2048     decode_params,
2049     encode_params,
2050     free_params,
2051     dup_params,
2052     true, game_configure, custom_params,
2053     validate_params,
2054     new_game_desc,
2055     validate_desc,
2056     new_game,
2057     dup_game,
2058     free_game,
2059     true, solve_game,
2060     true, game_can_format_as_text_now, game_text_format,
2061     new_ui,
2062     free_ui,
2063     encode_ui,
2064     decode_ui,
2065     game_request_keys,
2066     game_changed_state,
2067     interpret_move,
2068     execute_move,
2069     PREFERRED_TILESIZE, game_compute_size, game_set_size,
2070     game_colours,
2071     game_new_drawstate,
2072     game_free_drawstate,
2073     game_redraw,
2074     game_anim_length,
2075     game_flash_length,
2076     game_get_cursor_location,
2077     game_status,
2078     true, false, game_print_size, game_print,
2079     false,                             /* wants_statusbar */
2080     false, game_timing_state,
2081     REQUIRE_RBUTTON | REQUIRE_NUMPAD,  /* flags */
2082 };
2083
2084 #ifdef STANDALONE_SOLVER
2085
2086 #include <stdarg.h>
2087
2088 int main(int argc, char **argv)
2089 {
2090     game_params *p;
2091     game_state *s;
2092     char *id = NULL, *desc;
2093     const char *err;
2094     bool grade = false;
2095     int ret, diff;
2096     bool really_show_working = false;
2097
2098     while (--argc > 0) {
2099         char *p = *++argv;
2100         if (!strcmp(p, "-v")) {
2101             really_show_working = true;
2102         } else if (!strcmp(p, "-g")) {
2103             grade = true;
2104         } else if (*p == '-') {
2105             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2106             return 1;
2107         } else {
2108             id = p;
2109         }
2110     }
2111
2112     if (!id) {
2113         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2114         return 1;
2115     }
2116
2117     desc = strchr(id, ':');
2118     if (!desc) {
2119         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2120         return 1;
2121     }
2122     *desc++ = '\0';
2123
2124     p = default_params();
2125     decode_params(p, id);
2126     err = validate_desc(p, desc);
2127     if (err) {
2128         fprintf(stderr, "%s: %s\n", argv[0], err);
2129         return 1;
2130     }
2131     s = new_game(NULL, p, desc);
2132
2133     /*
2134      * When solving an Easy puzzle, we don't want to bother the
2135      * user with Hard-level deductions. For this reason, we grade
2136      * the puzzle internally before doing anything else.
2137      */
2138     ret = -1;                          /* placate optimiser */
2139     solver_show_working = 0;
2140     for (diff = 0; diff < DIFFCOUNT; diff++) {
2141         memcpy(s->grid, s->clues->immutable, p->w * p->w);
2142         ret = solver(p->w, s->clues->clues, s->grid, diff);
2143         if (ret <= diff)
2144             break;
2145     }
2146
2147     if (really_show_working) {
2148         /*
2149          * Now run the solver again at the last difficulty level we
2150          * tried, but this time with diagnostics enabled.
2151          */
2152         solver_show_working = really_show_working;
2153         memcpy(s->grid, s->clues->immutable, p->w * p->w);
2154         ret = solver(p->w, s->clues->clues, s->grid,
2155                      diff < DIFFCOUNT ? diff : DIFFCOUNT-1);
2156     }
2157
2158     if (diff == DIFFCOUNT) {
2159         if (grade)
2160             printf("Difficulty rating: ambiguous\n");
2161         else
2162             printf("Unable to find a unique solution\n");
2163     } else {
2164         if (grade) {
2165             if (ret == diff_impossible)
2166                 printf("Difficulty rating: impossible (no solution exists)\n");
2167             else
2168                 printf("Difficulty rating: %s\n", towers_diffnames[ret]);
2169         } else {
2170             if (ret != diff)
2171                 printf("Puzzle is inconsistent\n");
2172             else
2173                 fputs(game_text_format(s), stdout);
2174         }
2175     }
2176
2177     return 0;
2178 }
2179
2180 #endif
2181
2182 /* vim: set shiftwidth=4 tabstop=8: */