text: /*
   * 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(const 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(const 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(const 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(const 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(const 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(const 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(const game_params *params, const 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, const game_params *params,
                              const 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(const 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(const game_state *state, const game_state *currstate,
                          const 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(const game_params *params)
  {
      return TRUE;
  }
  
  static char *game_text_format(const 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(const 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(const game_ui *ui)
  {
      return NULL;
  }
  
  static void decode_ui(game_ui *ui, const char *encoding)
  {
  }
  
  static void game_changed_state(game_ui *ui, const game_state *oldstate,
                                 const 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)
  
  /* These always return positive values, though y offsets are actually -ve */
  #define X_3D_DISP(height, w) ((height) * TILESIZE / (8 * (w)))
  #define Y_3D_DISP(height, w) ((height) * TILESIZE / (4 * (w)))
  
  #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 three_d;		/* default 3D graphics are user-disableable */
      int started;
      long *tiles;		       /* (w+2)*(w+2) temp space */
      long *drawn;		       /* (w+2)*(w+2)*4: current drawn data */
      int *errtmp;
  };
  
  static int check_errors(const 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, n, best;
  	STARTSTEP(start, step, i, w);
  
  	if (!clues[i])
  	    continue;
  
  	best = n = 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(const game_state *state, game_ui *ui,
                              const 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 (ds->three_d) {
  	/*
  	 * In 3D mode, just locating the mouse click in the natural
  	 * square grid may not be sufficient to tell which tower the
  	 * user clicked on. Investigate the _tops_ of the nearby
  	 * towers to see if a click on one grid square was actually
  	 * a click on a tower protruding into that region from
  	 * another.
  	 */
  	int dx, dy;
  	for (dy = 0; dy <= 1; dy++)
  	    for (dx = 0; dx >= -1; dx--) {
  		int cx = tx + dx, cy = ty + dy;
  		if (cx >= 0 && cx < w && cy >= 0 && cy < w) {
  		    int height = state->grid[cy*w+cx];
  		    int bx = COORD(cx), by = COORD(cy);
  		    int ox = bx + X_3D_DISP(height, w);
  		    int oy = by - Y_3D_DISP(height, w);
  		    if (/* on top face? */
  			(x - ox >= 0 && x - ox < TILESIZE &&
  			 y - oy >= 0 && y - oy < TILESIZE) ||
  			/* in triangle between top-left corners? */
  			(ox > bx && x >= bx && x <= ox && y <= by &&
  			 (by-y) * (ox-bx) <= (by-oy) * (x-bx)) ||
  			/* in triangle between bottom-right corners? */
  			(ox > bx && x >= bx+TILESIZE && x <= ox+TILESIZE &&
  			 y >= oy+TILESIZE &&
  			 (by-y+TILESIZE)*(ox-bx) >= (by-oy)*(x-bx-TILESIZE))) {
  			tx = cx;
  			ty = cy;
  		    }
  		}
  	    }
      }
  
      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(const game_state *from, const 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(const 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,
                            const 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 game_drawstate *game_new_drawstate(drawing *dr, const 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->three_d = !getenv("TOWERS_2D");
      ds->started = FALSE;
      ds->tiles = snewn((w+2)*(w+2), long);
      ds->drawn = snewn((w+2)*(w+2)*4, long);
      for (i = 0; i < (w+2)*(w+2)*4; i++)
  	ds->drawn[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->drawn);
      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, bg;
      char str[64];
  
      tx = COORD(x);
      ty = COORD(y);
  
      bg = (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND;
  
      /* draw tower */
      if (ds->three_d && (tile & DF_PLAYAREA) && (tile & DF_DIGIT_MASK)) {
  	int coords[8];
  	int xoff = X_3D_DISP(tile & DF_DIGIT_MASK, w);
  	int yoff = Y_3D_DISP(tile & DF_DIGIT_MASK, w);
  
  	/* left face of tower */
  	coords[0] = tx;
  	coords[1] = ty - 1;
  	coords[2] = tx;
  	coords[3] = ty + TILESIZE - 1;
  	coords[4] = coords[2] + xoff;
  	coords[5] = coords[3] - yoff;
  	coords[6] = coords[0] + xoff;
  	coords[7] = coords[1] - yoff;
  	draw_polygon(dr, coords, 4, bg, COL_GRID);
  
  	/* bottom face of tower */
  	coords[0] = tx + TILESIZE;
  	coords[1] = ty + TILESIZE - 1;
  	coords[2] = tx;
  	coords[3] = ty + TILESIZE - 1;
  	coords[4] = coords[2] + xoff;
  	coords[5] = coords[3] - yoff;
  	coords[6] = coords[0] + xoff;
  	coords[7] = coords[1] - yoff;
  	draw_polygon(dr, coords, 4, bg, COL_GRID);
  
  	/* now offset all subsequent drawing to the top of the tower */
  	tx += xoff;
  	ty -= yoff;
      }
  
      /* erase background */
      draw_rect(dr, tx, ty, TILESIZE, TILESIZE, bg);
  
      /* pencil-mode highlight */
      if (tile & DF_HIGHLIGHT_PENCIL) {
          int coords[6];
          coords[0] = tx;
          coords[1] = ty;
          coords[2] = tx+TILESIZE/2;
          coords[3] = ty;
          coords[4] = tx;
          coords[5] = ty+TILESIZE/2;
          draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
      }
  
      /* draw box outline */
      if (tile & DF_PLAYAREA) {
          int coords[8];
          coords[0] = tx;
          coords[1] = ty - 1;
          coords[2] = tx + TILESIZE;
          coords[3] = ty - 1;
          coords[4] = tx + TILESIZE;
          coords[5] = ty + TILESIZE - 1;
          coords[6] = tx;
          coords[7] = ty + TILESIZE - 1;
          draw_polygon(dr, coords, 4, -1, COL_GRID);
      }
  
      /* 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, minus space for impinging towers */
  	    pl = tx + (ds->three_d ? X_3D_DISP(w,w) : 0);
  	    pr = tx + TILESIZE;
  	    pt = ty;
  	    pb = ty + TILESIZE - (ds->three_d ? Y_3D_DISP(w,w) : 0);
  
  	    /*
  	     * 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 = pl + (pr - pl - fontsize * pw) / 2;
  	    pt = pt + (pb - pt - 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++;
  		}
  	}
      }
  }
  
  static void game_redraw(drawing *dr, game_drawstate *ds,
                          const game_state *oldstate, const game_state *state,
                          int dir, const 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);
  
  	draw_update(dr, 0, 0, SIZE(w), SIZE(w));
  
  	ds->started = TRUE;
      }
  
      check_errors(state, ds->errtmp);
  
      /*
       * Work out what data each tile should contain.
       */
      for (i = 0; i < (w+2)*(w+2); i++)
  	ds->tiles[i] = 0;	       /* completely blank square */
      /* The clue squares... */
      for (i = 0; i < 4*w; i++) {
  	long tile = state->clues->clues[i];
  
  	CLUEPOS(x, y, i, w);
  
  	if (ds->errtmp[(y+1)*(w+2)+(x+1)])
  	    tile |= DF_ERROR;
  
  	ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
      }
      /* ... and 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;
  
  	    ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
  	}
      }
  
      /*
       * Now actually draw anything that needs to be changed.
       */
      for (y = 0; y < w+2; y++) {
  	for (x = 0; x < w+2; x++) {
  	    long tl, tr, bl, br;
  	    int i = y*(w+2)+x;
  
  	    tr = ds->tiles[y*(w+2)+x];
  	    tl = (x == 0 ? 0 : ds->tiles[y*(w+2)+(x-1)]);
  	    br = (y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+x]);
  	    bl = (x == 0 || y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+(x-1)]);
  
  	    if (ds->drawn[i*4] != tl || ds->drawn[i*4+1] != tr ||
  		ds->drawn[i*4+2] != bl || ds->drawn[i*4+3] != br) {
  		clip(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE);
  
  		draw_tile(dr, ds, state->clues, x-1, y-1, tr);
  		if (x > 0)
  		    draw_tile(dr, ds, state->clues, x-2, y-1, tl);
  		if (y <= w)
  		    draw_tile(dr, ds, state->clues, x-1, y, br);
  		if (x > 0 && y <= w)
  		    draw_tile(dr, ds, state->clues, x-2, y, bl);
  
  		unclip(dr);
  		draw_update(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE);
  
  		ds->drawn[i*4] = tl;
  		ds->drawn[i*4+1] = tr;
  		ds->drawn[i*4+2] = bl;
  		ds->drawn[i*4+3] = br;
  	    }
  	}
      }
  }
  
  static float game_anim_length(const game_state *oldstate,
                                const game_state *newstate, int dir, game_ui *ui)
  {
      return 0.0F;
  }
  
  static float game_flash_length(const game_state *oldstate,
                                 const 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_status(const game_state *state)
  {
      return state->completed ? +1 : 0;
  }
  
  static int game_timing_state(const game_state *state, game_ui *ui)
  {
      if (state->completed)
  	return FALSE;
      return TRUE;
  }
  
  static void game_print_size(const 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, const 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,
      game_status,
      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: */
  