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