ref: ceb12cb0804d437c4b4acd1540cfed0a621c5bcf
parent: 7c3413a2f2ab0d22f4e43c92a9c215bc24f88baf
author: Simon Tatham <anakin@pobox.com>
date: Thu Jan 7 13:42:00 EST 2010
New puzzle, again using the revised latin.c: 'Towers', a clone of a latin-square puzzle which I've seen described by several names but the most common is 'Skyscrapers'. [originally from svn r8816]
--- a/icons/Makefile
+++ b/icons/Makefile
@@ -2,7 +2,8 @@
PUZZLES = blackbox bridges cube dominosa fifteen filling flip galaxies guess \
inertia keen lightup loopy map mines net netslide pattern pegs \
- rect samegame sixteen slant solo tents twiddle unequal untangle
+ rect samegame sixteen slant solo tents towers twiddle unequal \
+ untangle
BASE = $(patsubst %,%-base.png,$(PUZZLES))
WEB = $(patsubst %,%-web.png,$(PUZZLES))
--- /dev/null
+++ b/icons/towers.sav
@@ -1,0 +1,26 @@
+SAVEFILE:41:Simon Tatham's Portable Puzzle Collection
+VERSION :1:1
+GAME :6:Towers
+PARAMS :3:4de
+CPARAMS :3:4de
+SEED :15:888431554483015
+DESC :31:2/2/1/3/2/2/3/1/3/1/2/2/2/3/2/1
+AUXINFO :34:297d7a2fcf9e14403a74c976fe0fefd306
+NSTATES :2:17
+STATEPOS:2:10
+MOVE :6:R2,0,4
+MOVE :6:R0,1,4
+MOVE :6:R3,3,4
+MOVE :6:R1,2,4
+MOVE :6:R0,3,3
+MOVE :6:R1,0,3
+MOVE :6:R3,2,3
+MOVE :6:R2,1,3
+MOVE :6:R3,0,2
+MOVE :6:R3,1,1
+MOVE :6:R1,1,2
+MOVE :6:R1,3,1
+MOVE :6:R2,3,2
+MOVE :6:R2,2,1
+MOVE :6:R0,2,2
+MOVE :6:R0,0,1
--- a/puzzles.but
+++ b/puzzles.but
@@ -2561,6 +2561,96 @@
still be unique. The remaining levels require increasingly complex
reasoning to avoid having to backtrack.
+
+\C{towers} \i{Towers}+
+\cfg{winhelp-topic}{games.towers}+
+You have a square grid. On each square of the grid you can build a
+tower, with its height ranging from 1 to the size of the grid.
+Around the edge of the grid are some numeric clues.
+
+Your task is to build a tower on every square, in such a way that:
+
+\b Each row contains every possible height of tower once
+
+\b Each column contains every possible height of tower once
+
+\b Each numeric clue describes the number of towers that can be seen
+if you look into the square from that direction, assuming that
+shorter towers are hidden behind taller ones. For example, in a
+5\by.5 grid, a clue marked \q{5} indicates that the five tower+heights must appear in increasing order (otherwise you would not be
+able to see all five towers), whereas a clue marked \q{1} indicates+that the tallest tower (the one marked 5) must come first.
+
+In harder or larger puzzles, some towers will be specified for you
+as well as the clues round the edge, and some edge clues may be
+missing.
+
+This puzzle appears on the web under various names, particularly
+\q{Skyscrapers}, but I don't know who first invented it.+
+
+\H{towers-controls} \i{Towers controls}+
+\IM{Towers controls} controls, for Towers+
+Towers shares much of its control system with Solo, Unequal and Keen.
+
+To play Towers, simply click the mouse in any empty square and then
+type a digit on the keyboard to fill that square with a tower of the
+given height. If you make a mistake, click the mouse in the
+incorrect square and press Space to clear it again (or use the Undo
+feature).
+
+If you \e{right}-click in a square and then type a number, that+number will be entered in the square as a \q{pencil mark}. You can+have pencil marks for multiple numbers in the same square. A square
+containing a tower cannot also contain pencil marks.
+
+The game pays no attention to pencil marks, so exactly what you use
+them for is up to you: you can use them as reminders that a
+particular square needs to be re-examined once you know more about a
+particular number, or you can use them as lists of the possible
+numbers in a given square, or anything else you feel like.
+
+To erase a single pencil mark, right-click in the square and type
+the same number again.
+
+All pencil marks in a square are erased when you left-click and type
+a number, or when you left-click and press space. Right-clicking and
+pressing space will also erase pencil marks.
+
+As for Solo, the cursor keys can be used in conjunction with the
+digit keys to set numbers or pencil marks. Use the cursor keys to
+move a highlight around the grid, and type a digit to enter it in
+the highlighted square. Pressing return toggles the highlight into a
+mode in which you can enter or remove pencil marks.
+
+Pressing M will fill in a full set of pencil marks in every square
+that does not have a main digit in it.
+
+(All the actions described in \k{common-actions} are also available.)+
+\H{towers-parameters} \I{parameters, for Towers}Towers parameters+
+These parameters are available from the \q{Custom...} option on the+\q{Type} menu.+
+\dt \e{Grid size}+
+\dd Specifies the size of the grid. Lower limit is 3; upper limit is
+9 (because the user interface would become more difficult with
+\q{digits} bigger than 9!).+
+\dt \e{Difficulty}+
+\dd Controls the difficulty of the generated puzzle. At Unreasonable
+level, some backtracking will be required, but the solution should
+still be unique. The remaining levels require increasingly complex
+reasoning to avoid having to backtrack.
+
\A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2009 Simon Tatham.--- /dev/null
+++ b/towers.R
@@ -1,0 +1,25 @@
+# -*- makefile -*-
+
+TOWERS_LATIN_EXTRA = tree234 maxflow
+TOWERS_EXTRA = latin TOWERS_LATIN_EXTRA
+
+towers : [X] GTK COMMON towers TOWERS_EXTRA towers-icon|no-icon
+
+towers : [G] WINDOWS COMMON towers TOWERS_EXTRA towers.res|noicon.res
+
+towerssolver : [U] towers[STANDALONE_SOLVER] latin[STANDALONE_SOLVER] TOWERS_LATIN_EXTRA STANDALONE
+towerssolver : [C] towers[STANDALONE_SOLVER] latin[STANDALONE_SOLVER] TOWERS_LATIN_EXTRA STANDALONE
+
+ALL += towers[COMBINED] TOWERS_EXTRA
+
+!begin gtk
+GAMES += towers
+!end
+
+!begin >list.c
+ A(towers) \
+!end
+
+!begin >wingames.lst
+towers.exe:Towers
+!end
--- /dev/null
+++ b/towers.c
@@ -1,0 +1,1929 @@
+/*
+ * towers.c: the puzzle also known as 'Skyscrapers'.
+ *
+ * Possible future work:
+ *
+ * - Relax the upper bound on grid size at 9?
+ * + I'd need TOCHAR and FROMCHAR macros a bit like group's, to
+ * be used wherever this code has +'0' or -'0'
+ * + the pencil marks in the drawstate would need a separate
+ * word to live in
+ * + the clues outside the grid would have to cope with being
+ * multi-digit, meaning in particular that the text formatting
+ * would become more unpleasant
+ * + most importantly, though, the solver just isn't fast
+ * enough. Even at size 9 it can't really do the solver_hard
+ * factorial-time enumeration at a sensible rate. Easy puzzles
+ * higher than that would be possible, but more latin-squarey
+ * than skyscrapery, as it were.
+ *
+ * - UI work?
+ * + Allow the user to mark a clue as 'spent' in some way once
+ * it's no longer interesting (typically because no
+ * arrangement of the remaining possibilities _can_ violate
+ * it)?
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+#include "latin.h"
+
+/*
+ * Difficulty levels. I do some macro ickery here to ensure that my
+ * enum and the various forms of my name list always match up.
+ */
+#define DIFFLIST(A) \
+ A(EASY,Easy,solver_easy,e) \
+ A(HARD,Hard,solver_hard,h) \
+ A(EXTREME,Extreme,NULL,x) \
+ A(UNREASONABLE,Unreasonable,NULL,u)
+#define ENUM(upper,title,func,lower) DIFF_ ## upper,
+#define TITLE(upper,title,func,lower) #title,
+#define ENCODE(upper,title,func,lower) #lower
+#define CONFIG(upper,title,func,lower) ":" #title
+enum { DIFFLIST(ENUM) DIFFCOUNT };+static char const *const towers_diffnames[] = { DIFFLIST(TITLE) };+static char const towers_diffchars[] = DIFFLIST(ENCODE);
+#define DIFFCONFIG DIFFLIST(CONFIG)
+
+enum {+ COL_BACKGROUND,
+ COL_GRID,
+ COL_USER,
+ COL_HIGHLIGHT,
+ COL_ERROR,
+ COL_PENCIL,
+ NCOLOURS
+};
+
+struct game_params {+ int w, diff;
+};
+
+struct clues {+ int refcount;
+ int w;
+ /*
+ * An array of 4w integers, of which:
+ * - the first w run across the top
+ * - the next w across the bottom
+ * - the third w down the left
+ * - the last w down the right.
+ */
+ int *clues;
+
+ /*
+ * An array of w*w digits.
+ */
+ digit *immutable;
+};
+
+/*
+ * Macros to compute clue indices and coordinates.
+ */
+#define STARTSTEP(start, step, index, w) do { \+ if (index < w) \
+ start = index, step = w; \
+ else if (index < 2*w) \
+ start = (w-1)*w+(index-w), step = -w; \
+ else if (index < 3*w) \
+ start = w*(index-2*w), step = 1; \
+ else \
+ start = w*(index-3*w)+(w-1), step = -1; \
+} while (0)
+#define CSTARTSTEP(start, step, index, w) \
+ STARTSTEP(start, step, (((index)+2*w)%(4*w)), w)
+#define CLUEPOS(x, y, index, w) do { \+ if (index < w) \
+ x = index, y = -1; \
+ else if (index < 2*w) \
+ x = index-w, y = w; \
+ else if (index < 3*w) \
+ x = -1, y = index-2*w; \
+ else \
+ x = w, y = index-3*w; \
+} while (0)
+
+#ifdef STANDALONE_SOLVER
+static const char *const cluepos[] = {+ "above column", "below column", "left of row", "right of row"
+};
+#endif
+
+struct game_state {+ game_params par;
+ struct clues *clues;
+ digit *grid;
+ int *pencil; /* bitmaps using bits 1<<1..1<<n */
+ int completed, cheated;
+};
+
+static game_params *default_params(void)
+{+ game_params *ret = snew(game_params);
+
+ ret->w = 5;
+ ret->diff = DIFF_EASY;
+
+ return ret;
+}
+
+const static struct game_params towers_presets[] = {+ { 4, DIFF_EASY },+ { 5, DIFF_EASY },+ { 5, DIFF_HARD },+ { 6, DIFF_EASY },+ { 6, DIFF_HARD },+ { 6, DIFF_EXTREME },+ { 6, DIFF_UNREASONABLE },+};
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{+ game_params *ret;
+ char buf[80];
+
+ if (i < 0 || i >= lenof(towers_presets))
+ return FALSE;
+
+ ret = snew(game_params);
+ *ret = towers_presets[i]; /* structure copy */
+
+ sprintf(buf, "%dx%d %s", ret->w, ret->w, towers_diffnames[ret->diff]);
+
+ *name = dupstr(buf);
+ *params = ret;
+ return TRUE;
+}
+
+static void free_params(game_params *params)
+{+ sfree(params);
+}
+
+static game_params *dup_params(game_params *params)
+{+ game_params *ret = snew(game_params);
+ *ret = *params; /* structure copy */
+ return ret;
+}
+
+static void decode_params(game_params *params, char const *string)
+{+ char const *p = string;
+
+ params->w = atoi(p);
+ while (*p && isdigit((unsigned char)*p)) p++;
+
+ if (*p == 'd') {+ int i;
+ p++;
+ params->diff = DIFFCOUNT+1; /* ...which is invalid */
+ if (*p) {+ for (i = 0; i < DIFFCOUNT; i++) {+ if (*p == towers_diffchars[i])
+ params->diff = i;
+ }
+ p++;
+ }
+ }
+}
+
+static char *encode_params(game_params *params, int full)
+{+ char ret[80];
+
+ sprintf(ret, "%d", params->w);
+ if (full)
+ sprintf(ret + strlen(ret), "d%c", towers_diffchars[params->diff]);
+
+ return dupstr(ret);
+}
+
+static config_item *game_configure(game_params *params)
+{+ config_item *ret;
+ char buf[80];
+
+ ret = snewn(3, config_item);
+
+ ret[0].name = "Grid size";
+ ret[0].type = C_STRING;
+ sprintf(buf, "%d", params->w);
+ ret[0].sval = dupstr(buf);
+ ret[0].ival = 0;
+
+ ret[1].name = "Difficulty";
+ ret[1].type = C_CHOICES;
+ ret[1].sval = DIFFCONFIG;
+ ret[1].ival = params->diff;
+
+ ret[2].name = NULL;
+ ret[2].type = C_END;
+ ret[2].sval = NULL;
+ ret[2].ival = 0;
+
+ return ret;
+}
+
+static game_params *custom_params(config_item *cfg)
+{+ game_params *ret = snew(game_params);
+
+ ret->w = atoi(cfg[0].sval);
+ ret->diff = cfg[1].ival;
+
+ return ret;
+}
+
+static char *validate_params(game_params *params, int full)
+{+ if (params->w < 3 || params->w > 9)
+ return "Grid size must be between 3 and 9";
+ if (params->diff >= DIFFCOUNT)
+ return "Unknown difficulty rating";
+ return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Solver.
+ */
+
+struct solver_ctx {+ int w, diff;
+ int started;
+ int *clues;
+ long *iscratch;
+ int *dscratch;
+};
+
+static int solver_easy(struct latin_solver *solver, void *vctx)
+{+ struct solver_ctx *ctx = (struct solver_ctx *)vctx;
+ int w = ctx->w;
+ int c, i, j, n, m, furthest;
+ int start, step, cstart, cstep, clue, pos, cpos;
+ int ret = 0;
+#ifdef STANDALONE_SOLVER
+ char prefix[256];
+#endif
+
+ if (!ctx->started) {+ ctx->started = TRUE;
+ /*
+ * One-off loop to help get started: when a pair of facing
+ * clues sum to w+1, it must mean that the row consists of
+ * two increasing sequences back to back, so we can
+ * immediately place the highest digit by knowing the
+ * lengths of those two sequences.
+ */
+ for (c = 0; c < 3*w; c = (c == w-1 ? 2*w : c+1)) {+ int c2 = c + w;
+
+ if (ctx->clues[c] && ctx->clues[c2] &&
+ ctx->clues[c] + ctx->clues[c2] == w+1) {+ STARTSTEP(start, step, c, w);
+ CSTARTSTEP(cstart, cstep, c, w);
+ pos = start + (ctx->clues[c]-1)*step;
+ cpos = cstart + (ctx->clues[c]-1)*cstep;
+ if (solver->cube[cpos*w+w-1]) {+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ printf("%*sfacing clues on %s %d are maximal:\n",+ solver_recurse_depth*4, "",
+ c>=2*w ? "row" : "column", c % w + 1);
+ printf("%*s placing %d at (%d,%d)\n",+ solver_recurse_depth*4, "",
+ w, pos%w+1, pos/w+1);
+ }
+#endif
+ latin_solver_place(solver, pos%w, pos/w, w);
+ ret = 1;
+ } else {+ ret = -1;
+ }
+ }
+ }
+
+ if (ret)
+ return ret;
+ }
+
+ /*
+ * Go over every clue doing reasonably simple heuristic
+ * deductions.
+ */
+ for (c = 0; c < 4*w; c++) {+ clue = ctx->clues[c];
+ if (!clue)
+ continue;
+ STARTSTEP(start, step, c, w);
+ CSTARTSTEP(cstart, cstep, c, w);
+
+ /* Find the location of each number in the row. */
+ for (i = 0; i < w; i++)
+ ctx->dscratch[i] = w;
+ for (i = 0; i < w; i++)
+ if (solver->grid[start+i*step])
+ ctx->dscratch[solver->grid[start+i*step]-1] = i;
+
+ n = m = 0;
+ furthest = w;
+ for (i = w; i >= 1; i--) {+ if (ctx->dscratch[i-1] == w) {+ break;
+ } else if (ctx->dscratch[i-1] < furthest) {+ furthest = ctx->dscratch[i-1];
+ m = i;
+ n++;
+ }
+ }
+ if (clue == n+1 && furthest > 1) {+#ifdef STANDALONE_SOLVER
+ if (solver_show_working)
+ sprintf(prefix, "%*sclue %s %d is nearly filled:\n",
+ solver_recurse_depth*4, "",
+ cluepos[c/w], c%w+1);
+ else
+ prefix[0] = '\0'; /* placate optimiser */
+#endif
+ /*
+ * We can already see an increasing sequence of the very
+ * highest numbers, of length one less than that
+ * specified in the clue. All of those numbers _must_ be
+ * part of the clue sequence, so the number right next
+ * to the clue must be the final one - i.e. it must be
+ * bigger than any of the numbers between it and m. This
+ * allows us to rule out small numbers in that square.
+ *
+ * (This is a generalisation of the obvious deduction
+ * that when you see a clue saying 1, it must be right
+ * next to the largest possible number; and similarly,
+ * when you see a clue saying 2 opposite that, it must
+ * be right next to the second-largest.)
+ */
+ j = furthest-1; /* number of small numbers we can rule out */
+ for (i = 1; i <= w && j > 0; i++) {+ if (ctx->dscratch[i-1] < w && ctx->dscratch[i-1] >= furthest)
+ continue; /* skip this number, it's elsewhere */
+ j--;
+ if (solver->cube[cstart*w+i-1]) {+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ printf("%s%*s ruling out %d at (%d,%d)\n",+ prefix, solver_recurse_depth*4, "",
+ i, start%w+1, start/w+1);
+ prefix[0] = '\0';
+ }
+#endif
+ solver->cube[cstart*w+i-1] = 0;
+ ret = 1;
+ }
+ }
+ }
+
+ if (ret)
+ return ret;
+
+#ifdef STANDALONE_SOLVER
+ if (solver_show_working)
+ sprintf(prefix, "%*slower bounds for clue %s %d:\n",
+ solver_recurse_depth*4, "",
+ cluepos[c/w], c%w+1);
+ else
+ prefix[0] = '\0'; /* placate optimiser */
+#endif
+
+ i = 0;
+ for (n = w; n > 0; n--) {+ /*
+ * The largest number cannot occur in the first (clue-1)
+ * squares of the row, or else there wouldn't be space
+ * for a sufficiently long increasing sequence which it
+ * terminated. The second-largest number (not counting
+ * any that are known to be on the far side of a larger
+ * number and hence excluded from this sequence) cannot
+ * occur in the first (clue-2) squares, similarly, and
+ * so on.
+ */
+
+ if (ctx->dscratch[n-1] < w) {+ for (m = n+1; m < w; m++)
+ if (ctx->dscratch[m] < ctx->dscratch[n-1])
+ break;
+ if (m < w)
+ continue; /* this number doesn't count */
+ }
+
+ for (j = 0; j < clue - i - 1; j++)
+ if (solver->cube[(cstart + j*cstep)*w+n-1]) {+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ int pos = start+j*step;
+ printf("%s%*s ruling out %d at (%d,%d)\n",+ prefix, solver_recurse_depth*4, "",
+ n, pos%w+1, pos/w+1);
+ prefix[0] = '\0';
+ }
+#endif
+ solver->cube[(cstart + j*cstep)*w+n-1] = 0;
+ ret = 1;
+ }
+ i++;
+ }
+ }
+
+ if (ret)
+ return ret;
+
+ return 0;
+}
+
+static int solver_hard(struct latin_solver *solver, void *vctx)
+{+ struct solver_ctx *ctx = (struct solver_ctx *)vctx;
+ int w = ctx->w;
+ int c, i, j, n, best, clue, start, step, ret;
+ long bitmap;
+#ifdef STANDALONE_SOLVER
+ char prefix[256];
+#endif
+
+ /*
+ * Go over every clue analysing all possibilities.
+ */
+ for (c = 0; c < 4*w; c++) {+ clue = ctx->clues[c];
+ if (!clue)
+ continue;
+ CSTARTSTEP(start, step, c, w);
+
+ for (i = 0; i < w; i++)
+ ctx->iscratch[i] = 0;
+
+ /*
+ * Instead of a tedious physical recursion, I iterate in the
+ * scratch array through all possibilities. At any given
+ * moment, i indexes the element of the box that will next
+ * be incremented.
+ */
+ i = 0;
+ ctx->dscratch[i] = 0;
+ best = n = 0;
+ bitmap = 0;
+
+ while (1) {+ if (i < w) {+ /*
+ * Find the next valid value for cell i.
+ */
+ int limit = (n == clue ? best : w);
+ int pos = start + step * i;
+ for (j = ctx->dscratch[i] + 1; j <= limit; j++) {+ if (bitmap & (1L << j))
+ continue; /* used this one already */
+ if (!solver->cube[pos*w+j-1])
+ continue; /* ruled out already */
+
+ /* Found one. */
+ break;
+ }
+
+ if (j > limit) {+ /* No valid values left; drop back. */
+ i--;
+ if (i < 0)
+ break; /* overall iteration is finished */
+ bitmap &= ~(1L << ctx->dscratch[i]);
+ if (ctx->dscratch[i] == best) {+ n--;
+ best = 0;
+ for (j = 0; j < i; j++)
+ if (best < ctx->dscratch[j])
+ best = ctx->dscratch[j];
+ }
+ } else {+ /* Got a valid value; store it and move on. */
+ bitmap |= 1L << j;
+ ctx->dscratch[i++] = j;
+ if (j > best) {+ best = j;
+ n++;
+ }
+ ctx->dscratch[i] = 0;
+ }
+ } else {+ if (n == clue) {+ for (j = 0; j < w; j++)
+ ctx->iscratch[j] |= 1L << ctx->dscratch[j];
+ }
+ i--;
+ bitmap &= ~(1L << ctx->dscratch[i]);
+ if (ctx->dscratch[i] == best) {+ n--;
+ best = 0;
+ for (j = 0; j < i; j++)
+ if (best < ctx->dscratch[j])
+ best = ctx->dscratch[j];
+ }
+ }
+ }
+
+#ifdef STANDALONE_SOLVER
+ if (solver_show_working)
+ sprintf(prefix, "%*sexhaustive analysis of clue %s %d:\n",
+ solver_recurse_depth*4, "",
+ cluepos[c/w], c%w+1);
+ else
+ prefix[0] = '\0'; /* placate optimiser */
+#endif
+
+ ret = 0;
+
+ for (i = 0; i < w; i++) {+ int pos = start + step * i;
+ for (j = 1; j <= w; j++) {+ if (solver->cube[pos*w+j-1] &&
+ !(ctx->iscratch[i] & (1L << j))) {+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ printf("%s%*s ruling out %d at (%d,%d)\n",+ prefix, solver_recurse_depth*4, "",
+ j, pos/w+1, pos%w+1);
+ prefix[0] = '\0';
+ }
+#endif
+ solver->cube[pos*w+j-1] = 0;
+ ret = 1;
+ }
+ }
+
+ /*
+ * Once we find one clue we can do something with in
+ * this way, revert to trying easier deductions, so as
+ * not to generate solver diagnostics that make the
+ * problem look harder than it is.
+ */
+ if (ret)
+ return ret;
+ }
+ }
+
+ return 0;
+}
+
+#define SOLVER(upper,title,func,lower) func,
+static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) };+
+static int solver(int w, int *clues, digit *soln, int maxdiff)
+{+ int ret;
+ struct solver_ctx ctx;
+
+ ctx.w = w;
+ ctx.diff = maxdiff;
+ ctx.clues = clues;
+ ctx.started = FALSE;
+ ctx.iscratch = snewn(w, long);
+ ctx.dscratch = snewn(w+1, int);
+
+ ret = latin_solver(soln, w, maxdiff,
+ DIFF_EASY, DIFF_HARD, DIFF_EXTREME,
+ DIFF_EXTREME, DIFF_UNREASONABLE,
+ towers_solvers, &ctx, NULL, NULL);
+
+ sfree(ctx.iscratch);
+ sfree(ctx.dscratch);
+
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Grid generation.
+ */
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{+ int w = params->w, a = w*w;
+ digit *grid, *soln, *soln2;
+ int *clues, *order;
+ int i, ret;
+ int diff = params->diff;
+ char *desc, *p;
+
+ /*
+ * Difficulty exceptions: some combinations of size and
+ * difficulty cannot be satisfied, because all puzzles of at
+ * most that difficulty are actually even easier.
+ *
+ * Remember to re-test this whenever a change is made to the
+ * solver logic!
+ *
+ * I tested it using the following shell command:
+
+for d in e h x u; do
+ for i in {3..9}; do+ echo -n "./towers --generate 1 ${i}d${d}: "+ perl -e 'alarm 30; exec @ARGV' ./towers --generate 1 ${i}d${d} >/dev/null \+ && echo ok
+ done
+done
+
+ * Of course, it's better to do that after taking the exceptions
+ * _out_, so as to detect exceptions that should be removed as
+ * well as those which should be added.
+ */
+ if (diff > DIFF_HARD && w <= 3)
+ diff = DIFF_HARD;
+
+ grid = NULL;
+ clues = snewn(4*w, int);
+ soln = snewn(a, digit);
+ soln2 = snewn(a, digit);
+ order = snewn(max(4*w,a), int);
+
+ while (1) {+ /*
+ * Construct a latin square to be the solution.
+ */
+ sfree(grid);
+ grid = latin_generate(w, rs);
+
+ /*
+ * Fill in the clues.
+ */
+ for (i = 0; i < 4*w; i++) {+ int start, step, j, k, best;
+ STARTSTEP(start, step, i, w);
+ k = best = 0;
+ for (j = 0; j < w; j++) {+ if (grid[start+j*step] > best) {+ best = grid[start+j*step];
+ k++;
+ }
+ }
+ clues[i] = k;
+ }
+
+ /*
+ * Remove the grid numbers and then the clues, one by one,
+ * for as long as the game remains soluble at the given
+ * difficulty.
+ */
+ memcpy(soln, grid, a);
+
+ if (diff == DIFF_EASY && w <= 5) {+ /*
+ * Special case: for Easy-mode grids that are small
+ * enough, it's nice to be able to find completely empty
+ * grids.
+ */
+ memset(soln2, 0, a);
+ ret = solver(w, clues, soln2, diff);
+ if (ret > diff)
+ continue;
+ }
+
+ for (i = 0; i < a; i++)
+ order[i] = i;
+ shuffle(order, a, sizeof(*order), rs);
+ for (i = 0; i < a; i++) {+ int j = order[i];
+
+ memcpy(soln2, grid, a);
+ soln2[j] = 0;
+ ret = solver(w, clues, soln2, diff);
+ if (ret <= diff)
+ grid[j] = 0;
+ }
+
+ if (diff > DIFF_EASY) { /* leave all clues on Easy mode */+ for (i = 0; i < 4*w; i++)
+ order[i] = i;
+ shuffle(order, 4*w, sizeof(*order), rs);
+ for (i = 0; i < 4*w; i++) {+ int j = order[i];
+ int clue = clues[j];
+
+ memcpy(soln2, grid, a);
+ clues[j] = 0;
+ ret = solver(w, clues, soln2, diff);
+ if (ret > diff)
+ clues[j] = clue;
+ }
+ }
+
+ /*
+ * See if the game can be solved at the specified difficulty
+ * level, but not at the one below.
+ */
+ memcpy(soln2, grid, a);
+ ret = solver(w, clues, soln2, diff);
+ if (ret != diff)
+ continue; /* go round again */
+
+ /*
+ * We've got a usable puzzle!
+ */
+ break;
+ }
+
+ /*
+ * Encode the puzzle description.
+ */
+ desc = snewn(40*a, char);
+ p = desc;
+ for (i = 0; i < 4*w; i++) {+ p += sprintf(p, "%s%.0d", i?"/":"", clues[i]);
+ }
+ for (i = 0; i < a; i++)
+ if (grid[i])
+ break;
+ if (i < a) {+ int run = 0;
+
+ *p++ = ',';
+
+ for (i = 0; i <= a; i++) {+ int n = (i < a ? grid[i] : -1);
+
+ if (!n)
+ run++;
+ else {+ if (run) {+ while (run > 0) {+ int thisrun = min(run, 26);
+ *p++ = thisrun - 1 + 'a';
+ run -= thisrun;
+ }
+ } else {+ /*
+ * If there's a number in the very top left or
+ * bottom right, there's no point putting an
+ * unnecessary _ before or after it.
+ */
+ if (i > 0 && n > 0)
+ *p++ = '_';
+ }
+ if (n > 0)
+ p += sprintf(p, "%d", n);
+ run = 0;
+ }
+ }
+ }
+ *p++ = '\0';
+ desc = sresize(desc, p - desc, char);
+
+ /*
+ * Encode the solution.
+ */
+ *aux = snewn(a+2, char);
+ (*aux)[0] = 'S';
+ for (i = 0; i < a; i++)
+ (*aux)[i+1] = '0' + soln[i];
+ (*aux)[a+1] = '\0';
+
+ sfree(grid);
+ sfree(clues);
+ sfree(soln);
+ sfree(soln2);
+ sfree(order);
+
+ return desc;
+}
+
+/* ----------------------------------------------------------------------
+ * Gameplay.
+ */
+
+static char *validate_desc(game_params *params, char *desc)
+{+ int w = params->w, a = w*w;
+ const char *p = desc;
+ int i, clue;
+
+ /*
+ * Verify that the right number of clues are given, and that
+ * they're in range.
+ */
+ for (i = 0; i < 4*w; i++) {+ if (!*p)
+ return "Too few clues for grid size";
+
+ if (i > 0) {+ if (*p != '/')
+ return "Expected commas between clues";
+ p++;
+ }
+
+ if (isdigit((unsigned char)*p)) {+ clue = atoi(p);
+ while (*p && isdigit((unsigned char)*p)) p++;
+
+ if (clue <= 0 || clue > w)
+ return "Clue number out of range";
+ }
+ }
+ if (*p == '/')
+ return "Too many clues for grid size";
+
+ if (*p == ',') {+ /*
+ * Verify that the right amount of grid data is given, and
+ * that any grid elements provided are in range.
+ */
+ int squares = 0;
+
+ p++;
+ while (*p) {+ int c = *p++;
+ if (c >= 'a' && c <= 'z') {+ squares += c - 'a' + 1;
+ } else if (c == '_') {+ /* do nothing */;
+ } else if (c > '0' && c <= '9') {+ int val = atoi(p-1);
+ if (val < 1 || val > w)
+ return "Out-of-range number in grid description";
+ squares++;
+ while (*p && isdigit((unsigned char)*p)) p++;
+ } else
+ return "Invalid character in game description";
+ }
+
+ if (squares < a)
+ return "Not enough data to fill grid";
+
+ if (squares > a)
+ return "Too much data to fit in grid";
+ }
+
+ return NULL;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc)
+{+ int w = params->w, a = w*w;
+ game_state *state = snew(game_state);
+ const char *p = desc;
+ int i;
+
+ state->par = *params; /* structure copy */
+ state->clues = snew(struct clues);
+ state->clues->refcount = 1;
+ state->clues->w = w;
+ state->clues->clues = snewn(4*w, int);
+ state->clues->immutable = snewn(a, digit);
+ state->grid = snewn(a, digit);
+ state->pencil = snewn(a, int);
+
+ for (i = 0; i < a; i++) {+ state->grid[i] = 0;
+ state->pencil[i] = 0;
+ }
+
+ memset(state->clues->immutable, 0, a);
+
+ for (i = 0; i < 4*w; i++) {+ if (i > 0) {+ assert(*p == '/');
+ p++;
+ }
+ if (*p && isdigit((unsigned char)*p)) {+ state->clues->clues[i] = atoi(p);
+ while (*p && isdigit((unsigned char)*p)) p++;
+ } else
+ state->clues->clues[i] = 0;
+ }
+
+ if (*p == ',') {+ int pos = 0;
+ p++;
+ while (*p) {+ int c = *p++;
+ if (c >= 'a' && c <= 'z') {+ pos += c - 'a' + 1;
+ } else if (c == '_') {+ /* do nothing */;
+ } else if (c > '0' && c <= '9') {+ int val = atoi(p-1);
+ assert(val >= 1 && val <= w);
+ assert(pos < a);
+ state->grid[pos] = state->clues->immutable[pos] = val;
+ pos++;
+ while (*p && isdigit((unsigned char)*p)) p++;
+ } else
+ assert(!"Corrupt game description");
+ }
+ assert(pos == a);
+ }
+ assert(!*p);
+
+ state->completed = state->cheated = FALSE;
+
+ return state;
+}
+
+static game_state *dup_game(game_state *state)
+{+ int w = state->par.w, a = w*w;
+ game_state *ret = snew(game_state);
+
+ ret->par = state->par; /* structure copy */
+
+ ret->clues = state->clues;
+ ret->clues->refcount++;
+
+ ret->grid = snewn(a, digit);
+ ret->pencil = snewn(a, int);
+ memcpy(ret->grid, state->grid, a*sizeof(digit));
+ memcpy(ret->pencil, state->pencil, a*sizeof(int));
+
+ ret->completed = state->completed;
+ ret->cheated = state->cheated;
+
+ return ret;
+}
+
+static void free_game(game_state *state)
+{+ sfree(state->grid);
+ sfree(state->pencil);
+ if (--state->clues->refcount <= 0) {+ sfree(state->clues->immutable);
+ sfree(state->clues->clues);
+ sfree(state->clues);
+ }
+ sfree(state);
+}
+
+static char *solve_game(game_state *state, game_state *currstate,
+ char *aux, char **error)
+{+ int w = state->par.w, a = w*w;
+ int i, ret;
+ digit *soln;
+ char *out;
+
+ if (aux)
+ return dupstr(aux);
+
+ soln = snewn(a, digit);
+ memcpy(soln, state->clues->immutable, a);
+
+ ret = solver(w, state->clues->clues, soln, DIFFCOUNT-1);
+
+ if (ret == diff_impossible) {+ *error = "No solution exists for this puzzle";
+ out = NULL;
+ } else if (ret == diff_ambiguous) {+ *error = "Multiple solutions exist for this puzzle";
+ out = NULL;
+ } else {+ out = snewn(a+2, char);
+ out[0] = 'S';
+ for (i = 0; i < a; i++)
+ out[i+1] = '0' + soln[i];
+ out[a+1] = '\0';
+ }
+
+ sfree(soln);
+ return out;
+}
+
+static int game_can_format_as_text_now(game_params *params)
+{+ return TRUE;
+}
+
+static char *game_text_format(game_state *state)
+{+ int w = state->par.w /* , a = w*w */;
+ char *ret;
+ char *p;
+ int x, y;
+ int total;
+
+ /*
+ * We have:
+ * - a top clue row, consisting of three spaces, then w clue
+ * digits with spaces between (total 2*w+3 chars including
+ * newline)
+ * - a blank line (one newline)
+ * - w main rows, consisting of a left clue digit, two spaces,
+ * w grid digits with spaces between, two spaces and a right
+ * clue digit (total 2*w+6 chars each including newline)
+ * - a blank line (one newline)
+ * - a bottom clue row (same as top clue row)
+ * - terminating NUL.
+ *
+ * Total size is therefore 2*(2*w+3) + 2 + w*(2*w+6) + 1
+ * = 2w^2+10w+9.
+ */
+ total = 2*w*w + 10*w + 9;
+ ret = snewn(total, char);
+ p = ret;
+
+ /* Top clue row. */
+ *p++ = ' '; *p++ = ' ';
+ for (x = 0; x < w; x++) {+ *p++ = ' ';
+ *p++ = (state->clues->clues[x] ? '0' + state->clues->clues[x] : ' ');
+ }
+ *p++ = '\n';
+
+ /* Blank line. */
+ *p++ = '\n';
+
+ /* Main grid. */
+ for (y = 0; y < w; y++) {+ *p++ = (state->clues->clues[y+2*w] ? '0' + state->clues->clues[y+2*w] :
+ ' ');
+ *p++ = ' ';
+ for (x = 0; x < w; x++) {+ *p++ = ' ';
+ *p++ = (state->grid[y*w+x] ? '0' + state->grid[y*w+x] : ' ');
+ }
+ *p++ = ' '; *p++ = ' ';
+ *p++ = (state->clues->clues[y+3*w] ? '0' + state->clues->clues[y+3*w] :
+ ' ');
+ *p++ = '\n';
+ }
+
+ /* Blank line. */
+ *p++ = '\n';
+
+ /* Bottom clue row. */
+ *p++ = ' '; *p++ = ' ';
+ for (x = 0; x < w; x++) {+ *p++ = ' ';
+ *p++ = (state->clues->clues[x+w] ? '0' + state->clues->clues[x+w] :
+ ' ');
+ }
+ *p++ = '\n';
+
+ *p++ = '\0';
+ assert(p == ret + total);
+
+ return ret;
+}
+
+struct game_ui {+ /*
+ * These are the coordinates of the currently highlighted
+ * square on the grid, if hshow = 1.
+ */
+ int hx, hy;
+ /*
+ * This indicates whether the current highlight is a
+ * pencil-mark one or a real one.
+ */
+ int hpencil;
+ /*
+ * This indicates whether or not we're showing the highlight
+ * (used to be hx = hy = -1); important so that when we're
+ * using the cursor keys it doesn't keep coming back at a
+ * fixed position. When hshow = 1, pressing a valid number
+ * or letter key or Space will enter that number or letter in the grid.
+ */
+ int hshow;
+ /*
+ * This indicates whether we're using the highlight as a cursor;
+ * it means that it doesn't vanish on a keypress, and that it is
+ * allowed on immutable squares.
+ */
+ int hcursor;
+};
+
+static game_ui *new_ui(game_state *state)
+{+ game_ui *ui = snew(game_ui);
+
+ ui->hx = ui->hy = 0;
+ ui->hpencil = ui->hshow = ui->hcursor = 0;
+
+ return ui;
+}
+
+static void free_ui(game_ui *ui)
+{+ sfree(ui);
+}
+
+static char *encode_ui(game_ui *ui)
+{+ return NULL;
+}
+
+static void decode_ui(game_ui *ui, char *encoding)
+{+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate,
+ game_state *newstate)
+{+ int w = newstate->par.w;
+ /*
+ * We prevent pencil-mode highlighting of a filled square, unless
+ * we're using the cursor keys. So if the user has just filled in
+ * a square which we had a pencil-mode highlight in (by Undo, or
+ * by Redo, or by Solve), then we cancel the highlight.
+ */
+ if (ui->hshow && ui->hpencil && !ui->hcursor &&
+ newstate->grid[ui->hy * w + ui->hx] != 0) {+ ui->hshow = 0;
+ }
+}
+
+#define PREFERRED_TILESIZE 48
+#define TILESIZE (ds->tilesize)
+#define BORDER (TILESIZE * 9 / 8)
+#define COORD(x) ((x)*TILESIZE + BORDER)
+#define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1)
+
+#define FLASH_TIME 0.4F
+
+#define DF_PENCIL_SHIFT 16
+#define DF_ERROR 0x8000
+#define DF_HIGHLIGHT 0x4000
+#define DF_HIGHLIGHT_PENCIL 0x2000
+#define DF_IMMUTABLE 0x1000
+#define DF_PLAYAREA 0x0800
+#define DF_DIGIT_MASK 0x00FF
+
+struct game_drawstate {+ int tilesize;
+ int started;
+ long *tiles;
+ int *errtmp;
+};
+
+static int check_errors(game_state *state, int *errors)
+{+ int w = state->par.w /*, a = w*w */;
+ int W = w+2, A = W*W; /* the errors array is (w+2) square */
+ int *clues = state->clues->clues;
+ digit *grid = state->grid;
+ int i, x, y, errs = FALSE;
+ int tmp[32];
+
+ assert(w < lenof(tmp));
+
+ if (errors)
+ for (i = 0; i < A; i++)
+ errors[i] = 0;
+
+ for (y = 0; y < w; y++) {+ unsigned long mask = 0, errmask = 0;
+ for (x = 0; x < w; x++) {+ unsigned long bit = 1UL << grid[y*w+x];
+ errmask |= (mask & bit);
+ mask |= bit;
+ }
+
+ if (mask != (1L << (w+1)) - (1L << 1)) {+ errs = TRUE;
+ errmask &= ~1UL;
+ if (errors) {+ for (x = 0; x < w; x++)
+ if (errmask & (1UL << grid[y*w+x]))
+ errors[(y+1)*W+(x+1)] = TRUE;
+ }
+ }
+ }
+
+ for (x = 0; x < w; x++) {+ unsigned long mask = 0, errmask = 0;
+ for (y = 0; y < w; y++) {+ unsigned long bit = 1UL << grid[y*w+x];
+ errmask |= (mask & bit);
+ mask |= bit;
+ }
+
+ if (mask != (1 << (w+1)) - (1 << 1)) {+ errs = TRUE;
+ errmask &= ~1UL;
+ if (errors) {+ for (y = 0; y < w; y++)
+ if (errmask & (1UL << grid[y*w+x]))
+ errors[(y+1)*W+(x+1)] = TRUE;
+ }
+ }
+ }
+
+ for (i = 0; i < 4*w; i++) {+ int start, step, j, k, n, best;
+ STARTSTEP(start, step, i, w);
+
+ if (!clues[i])
+ continue;
+
+ best = n = 0;
+ k = 0;
+ for (j = 0; j < w; j++) {+ int number = grid[start+j*step];
+ if (!number)
+ break; /* can't tell what happens next */
+ if (number > best) {+ best = number;
+ n++;
+ }
+ }
+
+ if (n > clues[i] || (j == w && n < clues[i])) {+ if (errors) {+ int x, y;
+ CLUEPOS(x, y, i, w);
+ errors[(y+1)*W+(x+1)] = TRUE;
+ }
+ errs = TRUE;
+ }
+ }
+
+ return errs;
+}
+
+static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button)
+{+ int w = state->par.w;
+ int tx, ty;
+ char buf[80];
+
+ button &= ~MOD_MASK;
+
+ tx = FROMCOORD(x);
+ ty = FROMCOORD(y);
+
+ if (tx >= 0 && tx < w && ty >= 0 && ty < w) {+ if (button == LEFT_BUTTON) {+ if (tx == ui->hx && ty == ui->hy &&
+ ui->hshow && ui->hpencil == 0) {+ ui->hshow = 0;
+ } else {+ ui->hx = tx;
+ ui->hy = ty;
+ ui->hshow = !state->clues->immutable[ty*w+tx];
+ ui->hpencil = 0;
+ }
+ ui->hcursor = 0;
+ return ""; /* UI activity occurred */
+ }
+ if (button == RIGHT_BUTTON) {+ /*
+ * Pencil-mode highlighting for non filled squares.
+ */
+ if (state->grid[ty*w+tx] == 0) {+ if (tx == ui->hx && ty == ui->hy &&
+ ui->hshow && ui->hpencil) {+ ui->hshow = 0;
+ } else {+ ui->hpencil = 1;
+ ui->hx = tx;
+ ui->hy = ty;
+ ui->hshow = 1;
+ }
+ } else {+ ui->hshow = 0;
+ }
+ ui->hcursor = 0;
+ return ""; /* UI activity occurred */
+ }
+ }
+ if (IS_CURSOR_MOVE(button)) {+ move_cursor(button, &ui->hx, &ui->hy, w, w, 0);
+ ui->hshow = ui->hcursor = 1;
+ return "";
+ }
+ if (ui->hshow &&
+ (button == CURSOR_SELECT)) {+ ui->hpencil = 1 - ui->hpencil;
+ ui->hcursor = 1;
+ return "";
+ }
+
+ if (ui->hshow &&
+ ((button >= '0' && button <= '9' && button - '0' <= w) ||
+ button == CURSOR_SELECT2 || button == '\b')) {+ int n = button - '0';
+ if (button == CURSOR_SELECT2 || button == '\b')
+ n = 0;
+
+ /*
+ * Can't make pencil marks in a filled square. This can only
+ * become highlighted if we're using cursor keys.
+ */
+ if (ui->hpencil && state->grid[ui->hy*w+ui->hx])
+ return NULL;
+
+ /*
+ * Can't do anything to an immutable square.
+ */
+ if (state->clues->immutable[ui->hy*w+ui->hx])
+ return NULL;
+
+ sprintf(buf, "%c%d,%d,%d",
+ (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
+
+ if (!ui->hcursor) ui->hshow = 0;
+
+ return dupstr(buf);
+ }
+
+ if (button == 'M' || button == 'm')
+ return dupstr("M");+
+ return NULL;
+}
+
+static game_state *execute_move(game_state *from, char *move)
+{+ int w = from->par.w, a = w*w;
+ game_state *ret;
+ int x, y, i, n;
+
+ if (move[0] == 'S') {+ ret = dup_game(from);
+ ret->completed = ret->cheated = TRUE;
+
+ for (i = 0; i < a; i++) {+ if (move[i+1] < '1' || move[i+1] > '0'+w) {+ free_game(ret);
+ return NULL;
+ }
+ ret->grid[i] = move[i+1] - '0';
+ ret->pencil[i] = 0;
+ }
+
+ if (move[a+1] != '\0') {+ free_game(ret);
+ return NULL;
+ }
+
+ return ret;
+ } else if ((move[0] == 'P' || move[0] == 'R') &&
+ sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
+ x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) {+ if (from->clues->immutable[y*w+x])
+ return NULL;
+
+ ret = dup_game(from);
+ if (move[0] == 'P' && n > 0) {+ ret->pencil[y*w+x] ^= 1L << n;
+ } else {+ ret->grid[y*w+x] = n;
+ ret->pencil[y*w+x] = 0;
+
+ if (!ret->completed && !check_errors(ret, NULL))
+ ret->completed = TRUE;
+ }
+ return ret;
+ } else if (move[0] == 'M') {+ /*
+ * Fill in absolutely all pencil marks everywhere. (I
+ * wouldn't use this for actual play, but it's a handy
+ * starting point when following through a set of
+ * diagnostics output by the standalone solver.)
+ */
+ ret = dup_game(from);
+ for (i = 0; i < a; i++) {+ if (!ret->grid[i])
+ ret->pencil[i] = (1L << (w+1)) - (1L << 1);
+ }
+ return ret;
+ } else
+ return NULL; /* couldn't parse move string */
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+#define SIZE(w) ((w) * TILESIZE + 2*BORDER)
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{+ /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+ struct { int tilesize; } ads, *ds = &ads;+ ads.tilesize = tilesize;
+
+ *x = *y = SIZE(params->w);
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize)
+{+ ds->tilesize = tilesize;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{+ float *ret = snewn(3 * NCOLOURS, float);
+
+ frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+
+ ret[COL_GRID * 3 + 0] = 0.0F;
+ ret[COL_GRID * 3 + 1] = 0.0F;
+ ret[COL_GRID * 3 + 2] = 0.0F;
+
+ ret[COL_USER * 3 + 0] = 0.0F;
+ ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_USER * 3 + 2] = 0.0F;
+
+ ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
+
+ ret[COL_ERROR * 3 + 0] = 1.0F;
+ ret[COL_ERROR * 3 + 1] = 0.0F;
+ ret[COL_ERROR * 3 + 2] = 0.0F;
+
+ ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static const char *const minus_signs[] = { "\xE2\x88\x92", "-" };+static const char *const times_signs[] = { "\xC3\x97", "*" };+static const char *const divide_signs[] = { "\xC3\xB7", "/" };+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+{+ int w = state->par.w /*, a = w*w */;
+ struct game_drawstate *ds = snew(struct game_drawstate);
+ int i;
+
+ ds->tilesize = 0;
+ ds->started = FALSE;
+ ds->tiles = snewn((w+2)*(w+2), long);
+ for (i = 0; i < (w+2)*(w+2); i++)
+ ds->tiles[i] = -1;
+ ds->errtmp = snewn((w+2)*(w+2), int);
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{+ sfree(ds->errtmp);
+ sfree(ds->tiles);
+ sfree(ds);
+}
+
+static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues,
+ int x, int y, long tile)
+{+ int w = clues->w /* , a = w*w */;
+ int tx, ty, tw, th;
+ int cx, cy, cw, ch;
+ char str[64];
+
+ tx = BORDER + x * TILESIZE + 1;
+ ty = BORDER + y * TILESIZE + 1;
+
+ cx = tx;
+ cy = ty;
+ cw = tw = TILESIZE-1;
+ ch = th = TILESIZE-1;
+
+ clip(dr, cx, cy, cw, ch);
+
+ /* background needs erasing */
+ draw_rect(dr, cx, cy, cw, ch,
+ (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND);
+
+ /* pencil-mode highlight */
+ if (tile & DF_HIGHLIGHT_PENCIL) {+ int coords[6];
+ coords[0] = cx;
+ coords[1] = cy;
+ coords[2] = cx+cw/2;
+ coords[3] = cy;
+ coords[4] = cx;
+ coords[5] = cy+ch/2;
+ draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
+ }
+
+ /* new number needs drawing? */
+ if (tile & DF_DIGIT_MASK) {+ str[1] = '\0';
+ str[0] = (tile & DF_DIGIT_MASK) + '0';
+ draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, FONT_VARIABLE,
+ (tile & DF_PLAYAREA ? TILESIZE/2 : TILESIZE*2/5),
+ ALIGN_VCENTRE | ALIGN_HCENTRE,
+ (tile & DF_ERROR) ? COL_ERROR :
+ (x < 0 || y < 0 || x >= w || y >= w) ? COL_GRID :
+ (tile & DF_IMMUTABLE) ? COL_GRID : COL_USER, str);
+ } else {+ int i, j, npencil;
+ int pl, pr, pt, pb;
+ float bestsize;
+ int pw, ph, minph, pbest, fontsize;
+
+ /* Count the pencil marks required. */
+ for (i = 1, npencil = 0; i <= w; i++)
+ if (tile & (1L << (i + DF_PENCIL_SHIFT)))
+ npencil++;
+ if (npencil) {+
+ minph = 2;
+
+ /*
+ * Determine the bounding rectangle within which we're going
+ * to put the pencil marks.
+ */
+ /* Start with the whole square */
+ pl = tx;
+ pr = pl + TILESIZE;
+ pt = ty;
+ pb = pt + TILESIZE;
+
+ /*
+ * We arrange our pencil marks in a grid layout, with
+ * the number of rows and columns adjusted to allow the
+ * maximum font size.
+ *
+ * So now we work out what the grid size ought to be.
+ */
+ bestsize = 0.0;
+ pbest = 0;
+ /* Minimum */
+ for (pw = 3; pw < max(npencil,4); pw++) {+ float fw, fh, fs;
+
+ ph = (npencil + pw - 1) / pw;
+ ph = max(ph, minph);
+ fw = (pr - pl) / (float)pw;
+ fh = (pb - pt) / (float)ph;
+ fs = min(fw, fh);
+ if (fs > bestsize) {+ bestsize = fs;
+ pbest = pw;
+ }
+ }
+ assert(pbest > 0);
+ pw = pbest;
+ ph = (npencil + pw - 1) / pw;
+ ph = max(ph, minph);
+
+ /*
+ * Now we've got our grid dimensions, work out the pixel
+ * size of a grid element, and round it to the nearest
+ * pixel. (We don't want rounding errors to make the
+ * grid look uneven at low pixel sizes.)
+ */
+ fontsize = min((pr - pl) / pw, (pb - pt) / ph);
+
+ /*
+ * Centre the resulting figure in the square.
+ */
+ pl = tx + (TILESIZE - fontsize * pw) / 2;
+ pt = ty + (TILESIZE - fontsize * ph) / 2;
+
+ /*
+ * Now actually draw the pencil marks.
+ */
+ for (i = 1, j = 0; i <= w; i++)
+ if (tile & (1L << (i + DF_PENCIL_SHIFT))) {+ int dx = j % pw, dy = j / pw;
+
+ str[1] = '\0';
+ str[0] = i + '0';
+ draw_text(dr, pl + fontsize * (2*dx+1) / 2,
+ pt + fontsize * (2*dy+1) / 2,
+ FONT_VARIABLE, fontsize,
+ ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
+ j++;
+ }
+ }
+ }
+
+ unclip(dr);
+
+ draw_update(dr, cx, cy, cw, ch);
+}
+
+static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
+ game_state *state, int dir, game_ui *ui,
+ float animtime, float flashtime)
+{+ int w = state->par.w /*, a = w*w */;
+ int i, x, y;
+
+ if (!ds->started) {+ /*
+ * The initial contents of the window are not guaranteed and
+ * can vary with front ends. To be on the safe side, all
+ * games should start by drawing a big background-colour
+ * rectangle covering the whole window.
+ */
+ draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND);
+
+ /*
+ * Big containing rectangle.
+ */
+ draw_rect(dr, COORD(0), COORD(0),
+ w*TILESIZE+1, w*TILESIZE+1,
+ COL_GRID);
+
+ draw_update(dr, 0, 0, SIZE(w), SIZE(w));
+
+ ds->started = TRUE;
+ }
+
+ check_errors(state, ds->errtmp);
+
+ /*
+ * Draw the clues.
+ */
+ for (i = 0; i < 4*w; i++) {+ long tile = state->clues->clues[i];
+
+ if (!tile)
+ continue;
+
+ CLUEPOS(x, y, i, w);
+
+ if (ds->errtmp[(y+1)*(w+2)+(x+1)])
+ tile |= DF_ERROR;
+
+ if (ds->tiles[(y+1)*(w+2)+(x+1)] != tile) {+ ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
+ draw_tile(dr, ds, state->clues, x, y, tile);
+ }
+ }
+
+ /*
+ * Draw the main grid.
+ */
+ for (y = 0; y < w; y++) {+ for (x = 0; x < w; x++) {+ long tile = DF_PLAYAREA;
+
+ if (state->grid[y*w+x])
+ tile |= state->grid[y*w+x];
+ else
+ tile |= (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT;
+
+ if (ui->hshow && ui->hx == x && ui->hy == y)
+ tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT);
+
+ if (state->clues->immutable[y*w+x])
+ tile |= DF_IMMUTABLE;
+
+ if (flashtime > 0 &&
+ (flashtime <= FLASH_TIME/3 ||
+ flashtime >= FLASH_TIME*2/3))
+ tile |= DF_HIGHLIGHT; /* completion flash */
+
+ if (ds->errtmp[(y+1)*(w+2)+(x+1)])
+ tile |= DF_ERROR;
+
+ if (ds->tiles[(y+1)*(w+2)+(x+1)] != tile) {+ ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
+ draw_tile(dr, ds, state->clues, x, y, tile);
+ }
+ }
+ }
+}
+
+static float game_anim_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{+ return 0.0F;
+}
+
+static float game_flash_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{+ if (!oldstate->completed && newstate->completed &&
+ !oldstate->cheated && !newstate->cheated)
+ return FLASH_TIME;
+ return 0.0F;
+}
+
+static int game_timing_state(game_state *state, game_ui *ui)
+{+ if (state->completed)
+ return FALSE;
+ return TRUE;
+}
+
+static void game_print_size(game_params *params, float *x, float *y)
+{+ int pw, ph;
+
+ /*
+ * We use 9mm squares by default, like Solo.
+ */
+ game_compute_size(params, 900, &pw, &ph);
+ *x = pw / 100.0F;
+ *y = ph / 100.0F;
+}
+
+static void game_print(drawing *dr, game_state *state, int tilesize)
+{+ int w = state->par.w;
+ int ink = print_mono_colour(dr, 0);
+ int i, x, y;
+
+ /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+ game_drawstate ads, *ds = &ads;
+ game_set_size(dr, ds, NULL, tilesize);
+
+ /*
+ * Border.
+ */
+ print_line_width(dr, 3 * TILESIZE / 40);
+ draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink);
+
+ /*
+ * Main grid.
+ */
+ for (x = 1; x < w; x++) {+ print_line_width(dr, TILESIZE / 40);
+ draw_line(dr, BORDER+x*TILESIZE, BORDER,
+ BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink);
+ }
+ for (y = 1; y < w; y++) {+ print_line_width(dr, TILESIZE / 40);
+ draw_line(dr, BORDER, BORDER+y*TILESIZE,
+ BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink);
+ }
+
+ /*
+ * Clues.
+ */
+ for (i = 0; i < 4*w; i++) {+ char str[128];
+
+ if (!state->clues->clues[i])
+ continue;
+
+ CLUEPOS(x, y, i, w);
+
+ sprintf (str, "%d", state->clues->clues[i]);
+
+ draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
+ BORDER + y*TILESIZE + TILESIZE/2,
+ FONT_VARIABLE, TILESIZE/2,
+ ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
+ }
+
+ /*
+ * Numbers for the solution, if any.
+ */
+ for (y = 0; y < w; y++)
+ for (x = 0; x < w; x++)
+ if (state->grid[y*w+x]) {+ char str[2];
+ str[1] = '\0';
+ str[0] = state->grid[y*w+x] + '0';
+ draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
+ BORDER + y*TILESIZE + TILESIZE/2,
+ FONT_VARIABLE, TILESIZE/2,
+ ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
+ }
+}
+
+#ifdef COMBINED
+#define thegame towers
+#endif
+
+const struct game thegame = {+ "Towers", "games.towers", "towers",
+ default_params,
+ game_fetch_preset,
+ decode_params,
+ encode_params,
+ free_params,
+ dup_params,
+ TRUE, game_configure, custom_params,
+ validate_params,
+ new_game_desc,
+ validate_desc,
+ new_game,
+ dup_game,
+ free_game,
+ TRUE, solve_game,
+ TRUE, game_can_format_as_text_now, game_text_format,
+ new_ui,
+ free_ui,
+ encode_ui,
+ decode_ui,
+ game_changed_state,
+ interpret_move,
+ execute_move,
+ PREFERRED_TILESIZE, game_compute_size, game_set_size,
+ game_colours,
+ game_new_drawstate,
+ game_free_drawstate,
+ game_redraw,
+ game_anim_length,
+ game_flash_length,
+ TRUE, FALSE, game_print_size, game_print,
+ FALSE, /* wants_statusbar */
+ FALSE, game_timing_state,
+ REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */
+};
+
+#ifdef STANDALONE_SOLVER
+
+#include <stdarg.h>
+
+int main(int argc, char **argv)
+{+ game_params *p;
+ game_state *s;
+ char *id = NULL, *desc, *err;
+ int grade = FALSE;
+ int ret, diff, really_show_working = FALSE;
+
+ while (--argc > 0) {+ char *p = *++argv;
+ if (!strcmp(p, "-v")) {+ really_show_working = TRUE;
+ } else if (!strcmp(p, "-g")) {+ grade = TRUE;
+ } else if (*p == '-') {+ fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
+ return 1;
+ } else {+ id = p;
+ }
+ }
+
+ if (!id) {+ fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
+ return 1;
+ }
+
+ desc = strchr(id, ':');
+ if (!desc) {+ fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
+ return 1;
+ }
+ *desc++ = '\0';
+
+ p = default_params();
+ decode_params(p, id);
+ err = validate_desc(p, desc);
+ if (err) {+ fprintf(stderr, "%s: %s\n", argv[0], err);
+ return 1;
+ }
+ s = new_game(NULL, p, desc);
+
+ /*
+ * When solving an Easy puzzle, we don't want to bother the
+ * user with Hard-level deductions. For this reason, we grade
+ * the puzzle internally before doing anything else.
+ */
+ ret = -1; /* placate optimiser */
+ solver_show_working = FALSE;
+ for (diff = 0; diff < DIFFCOUNT; diff++) {+ memcpy(s->grid, s->clues->immutable, p->w * p->w);
+ ret = solver(p->w, s->clues->clues, s->grid, diff);
+ if (ret <= diff)
+ break;
+ }
+
+ if (diff == DIFFCOUNT) {+ if (grade)
+ printf("Difficulty rating: ambiguous\n");+ else
+ printf("Unable to find a unique solution\n");+ } else {+ if (grade) {+ if (ret == diff_impossible)
+ printf("Difficulty rating: impossible (no solution exists)\n");+ else
+ printf("Difficulty rating: %s\n", towers_diffnames[ret]);+ } else {+ solver_show_working = really_show_working;
+ memcpy(s->grid, s->clues->immutable, p->w * p->w);
+ ret = solver(p->w, s->clues->clues, s->grid, diff);
+ if (ret != diff)
+ printf("Puzzle is inconsistent\n");+ else
+ fputs(game_text_format(s), stdout);
+ }
+ }
+
+ return 0;
+}
+
+#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */