/*
 * Copyright info: this file is in the public domain.
 */

/*
 * Hexnet.  This is a Net-style game based on a hexagonal grid with six
 *  orientations instead of Net's square grid with four orientations.
 *
 * We store our grid in a square array, of which approximately 1/4 of
 *  the cells don't get used.  As an example, a size-3 grid has 19
 *  cells and looks, to the player, like
 *
 *	  A B C
 *       D E F G
 *	H I J K L
 *	 M N O P
 *	  Q R S
 *
 *  We store this in a square grid of size 5.  With dots representing
 *  unused cells, that grid for the size-3 example above looks like
 *
 *	. . A B C
 *	. D E F G
 *	H I J K L
 *	M N O P .
 *	Q R S . .
 *
 *  or, as I tend to think of it,
 *
 *	. . A B C
 *	 . D E F G
 *	  H I J K L
 *	   M N O P .
 *	    Q R S . .
 *
 *  I considered trying to store it with no wasted cells, but the
 *  computation involved in finding neighbour cells looked hairier than
 *  I wanted to get into.  I decided wasting a the memory for the
 *  unused cells was a lower price than the code complexity and bugs
 *  that would have resulted from trying to store the above as a single
 *  19-element array.
 *
 * Cell coordinates are represented in two ways, depending on which is
 *  more convenient for the task at hand.  One representation is a
 *  small integer (0..24 in the above example); the other is a pair of
 *  small integers (X,Y) (each 0..4 in the above example).  These
 *  coordinates are zero-origin and are fourth-quadrant, not
 *  first-quadrant; for example, in the above, cell G is at (4,1).
 *
 * Directions are small integers 0 through 5, indicating a direction in
 *  which a cell can potentially connect to another cell:
 *
 *	 2   1
 *	  \ /
 *	3--*--0
 *	  / \
 *	 4   5
 *
 * Rotations are represented by 1 for clockwise and -1 for
 *  counterclockwise.  (This is perhaps unfortunate, in that it's
 *  backwards from the change in direction values, but so far this
 *  hasn't proven to be a problem in practice.)
 */

#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "puzzles.h"

#define COL_BACKGROUND  1
#define COL_LOCKED      2
#define COL_BORDER      3
#define COL_WIRE        4
#define COL_ENDPOINT    5
#define COL_POWERED     6
#define COL_ERR         7
#define COL_LOOP        8
#define COL_BARRIER     9
#define COL_BGWRAP     10
#define COL_LOCKWRAP   11
#define COL_ERRBG      12
#define COL_ERRBGWRAP  13
#define NCOLOURS       14

#define ROTATE_TIME .2
#define FLASH_TIME .75
#define FLASH_FRAME .1
#define BORDER_PIXELS 10

// Typedefs for framework-specified types.
typedef config_item CONFIG_ITEM;
typedef random_state RANDOM_STATE;
typedef struct game_params PARAMS;
typedef struct game_state STATE;
typedef struct game_ui UI;
typedef struct game_drawstate DRAWSTATE;
typedef struct findloopstate FINDLOOPSTATE;
typedef drawing DRAWING;

// Typedefs for private types other than structs.
typedef unsigned int CELL;

// Typedefs for structs.
typedef struct cdq CDQ;
typedef struct cdqe CDQE;
typedef struct ixy IXY;
typedef struct loopctx LOOPCTX;
typedef struct updrect UPDRECT;
typedef struct dpar DPAR;
typedef struct solver SOLVER;

/*
 * A rectangle.  The name and associated API are designed around using
 *  this to find the rectangle to draw_update() after some changes.
 *
 * We could, instead, maintain some more elaborate data structure so as
 *  to do just the rectangles we need to.  Arguably we should,
 *  especially since the relatively common case of rotating a
 *  duplicated cell usually involves a bounding box including most of
 *  the board.  Someday.
 */
struct updrect {
  int minx;
  int maxx;
  int miny;
  int maxy;
  } ;

/*
 * The context structure we use when calling on findloop to, well, find
 *  loops.
 */
struct loopctx {
  STATE *s;
  int v;
  int d;
  } ;

/*
 * An integer (X,Y) coordinate pair.  The name is IXY rather than XY
 *  because at one point I as expecting to have FXY for floats, but
 *  that turned out to go unused.
 */
struct ixy {
  int x;
  int y;
  } ;

/*
 * Our game parameters.
 *
 * The board is hexagonal in the large.  Conceptually, it's a generally
 *  hexagonal subset of an infinite grid of hexagons.  If wrapping is
 *  off, there are conceptual barriers around the ouside edge of the
 *  grid.  If wrapping is on, each cell (small hexagon) on the border
 *  of the (large hexagon) grid is identified with one on the other
 *  side of the grid.  This reduces the effective number of cells in
 *  the grid, since there are (size-2)*3 duplicate pairs and two
 *  triplicate triads, but the wraparound aspects makes wrapping
 *  puzzles harder than nonwrapping puzzles of the same nominal size
 *  despite that.
 *
 * size is the number of hexagons on each side of the grid.
 *
 * wrap is 0 or 1 according as wrapping is off or on.
 *
 * hard is 0 or 1 according as we use easy or hard puzzle generation.
 *  (We have are two level generation algorithms; it turns out one of
 *  them generates easier puzzles than the other, though the difference
 *  is perceptible mostly for wrapping puzzles.)
 *
 * uniq is 0 or 1 according as we permit or forbid multiple-solution
 *  puzzles.
 *
 * Arguably I should collapse wrap and hard into a single flags word,
 *  but there are few enough of these the memory used is not a big
 *  deal, and there are code simplicity benefits to this way.
 */
struct game_params {
  int size;
  int wrap;
  int hard;
  int uniq;
  } ;

/*
 * The name comes from "derived parameters".  This collects data which
 *  depends on nothing but the values in a PARAMS; it exists to save us
 *  from having to do algorithmic computation of these values scattered
 *  all over the place.  Most places where you might expect to see a
 *  PARAMS pointer, you actually see a DPAR pointer instead; being able
 *  to do this is why there is a copy of the PARAMS in here.
 *
 * p is of course the PARAMS values we compute based on.
 *
 * asz is "allocated size", the side of the underlying square array.
 *
 * asz2 is asz*asz, the number of cells in the underlying array.
 *
 * hszd (<h>exagon <s>i<z>e for <d>isplay) is the number of hexagons in
 *  the display board, the number of hexagons we draw on the screen.
 *
 * hszg (<h>exagon <s>i<z>e for <g>ame) is the number of distinct
 *  hexagons in the effective board.  For non-wrapping games, this
 *  equals hszd, but, for wrapping games, it is reduced by all the
 *  duplications (and two triplications).  For example, a size-3
 *  wrapping game has hszd 19, but hszg only 12.  Using the same letter
 *  multiple times for replicated cells, a size-3 wrapping board is
 *
 *	  A B H
 *       D E F M
 *	H I J K A
 *	 M N O D
 *	  A B H
 *
 * fv[] is a vector of pointers we want to free when freeing a DPAR.
 *  These are kept here rather than just freeing the other pointer
 *  fields for two reasons.  One is const poisoning (we want to const
 *  the pointed-to type for these, since they never change after the
 *  DPAR is set up); the other is that one of them is the underlying
 *  vector of cells for a 2D array, and I'd rather not have the freeing
 *  code depend on exactly which subscript the setup code stores the
 *  original malloced pointer in.
 *
 * ix is a vector of asz2 ints.  It maps a single-number cell
 *  coordinate to its X coordinate in the allocated grid.  It operates
 *  on display cells, not game cells - or, equivalently, can be thought
 *  of as operating as if wrapping were always false.
 *
 * iy is just like ix, except it holds the Y coordinate instead.
 *
 * xyi maps an (X,Y) coordinate pair to its single-integer index.  Its
 *  intended use is as in i = dp->xyi[x][y].
 *
 * dupof is indexed by single-index coordinates.  For unused cells,
 *  this holds -1.  For ordinary cells, it is the identity map
 *  (dupof[i] holds i).  For non-wrapping games, there are no other
 *  caess.  For wrapping games, each replicated cell has its
 *  representative game-board cell's number in dupof[] for all its
 *  display-board replicas.  We choose the representatives to be the
 *  left and top edges.
 *  
 * For example, for a size=3 game, dupof[] subscripts look like
 *
 *	 0   1   2   3   4
 *	   5   6   7   8   9
 *	    10  11  12  13  14
 *	      15  16  17  18  19
 *	        20  21  22  23  24
 *
 *  and the values look like
 *
 *	wrapping off			wrapping on
 *
 *	-1  -1   2   3   4		-1  -1   2   3  10
 *	  -1   6   7   8   9		  -1   6   7   8  15
 *	    10  11  12  13  14		    10  11  12  13   2
 *	      15  16  17  18  -1	      15  16  17   6  -1
 *	        20  21  22  -1  -1	         2   3  10  -1  -1
 *
 * flags[] holds some flags for each cell.  UNUSED and DUP are used in
 *  a bunch of places.  The WRAP bits are used mostly - exclusively, at
 *  this writing - for drawing the duplicated-cell shadow.  If wrapping
 *  is off, the DUP and WRAP bits are always zero.
 *
 * refs is a reference count.  DPARs are garbage-collected based on
 *  refcounting.
 */
struct dpar {
  PARAMS p;
  int asz;
  int asz2;
  int hszd;
  int hszg;
  void *fv[6];
  const int *ix;
  const int *iy;
  const int * const *xyi;
  const int *dupof;
  const unsigned char *flags;
#define FCF_UNUSED 0x01
#define FCF_DUP    0x02
#define FCF_WRAP   0x3c
#define FCF_WRAP_NONE 0x00 // _NONE must be 0
#define FCF_WRAP_0    0x04
#define FCF_WRAP_01   0x08
#define FCF_WRAP_1    0x0c
#define FCF_WRAP_12   0x10
#define FCF_WRAP_2    0x14
#define FCF_WRAP_23   0x18
#define FCF_WRAP_3    0x1c
#define FCF_WRAP_34   0x20
#define FCF_WRAP_4    0x24
#define FCF_WRAP_45   0x28
#define FCF_WRAP_5    0x2c
#define FCF_WRAP_50   0x30
  int refs;
  } ;

/*
 * Game state.  This is what's mutated by moves (in the undo/redo
 *  sense).
 *
 * d is the DPAR for this game (including its PARAMS, as mentioned
 *  above).
 *
 * lastrot_loc and lastrot_dir store the location (_loc) and direction
 *  (_dir) of the last move's rotation.  If the last move wasn't a
 *  rotation, lastrot_loc is -1 and lastrot_dir is meaningless and
 *  indeterminate.
 *
 * flags is various state flags.  At this writing, there's only one,
 *  SOLVED, indicating whether the state represents a solved game (set)
 *  or not (clear).
 *
 * net is the major state.  This holds link bits and various state we
 *  attach to them.  There are four six-bit fields and some other bits.
 *  In the six-bit fields, _S is the shift count to reach the low bit
 *  of the field, _M is a mask for the field, _BASE is the low bit (ie,
 *  1 << the S value), and _ALL is all the bits of the field.  The bit
 *  corresponding to direction D is the _BASE value << D.
 *
 *	LINK_* represent the links themselves.
 *	ERR_* are set for error links.  When cell A links in direction
 *	  D (to cell B), both cells are locked, but cell B doesn't link
 *	  back to cell A in the reverse direction, then cell A's ERR
 *	  bit for direction D will be set.
 *	LOOP_* records loop state.  These are set for all links
 *	  involved in a loop.
 *	BIDIR_* are set whenever A links to B and B links back to A.
 *	  They exist to improve display; see redraw() for more.
 *	LOCKED is set when the cell is locked in position.
 *	UNUSED is set on unused cells, cells that exist in the allocate
 *	  square grid but not part of the hexagonal game grid.  (UNUSED
 *	  is the same regardless of wrapping; all replicas of
 *	  replicated cells are considered used.)
 *	DUP is set on cells that are duplicates of another cell, those
 *	  for which dupof[i]!=i (see the DPAR description).
 *	LIT is set on cells which are lit up.
 *	MARK is used as a mark bit when checking for solved status.
 *
 * Some of these are not actually set on net[] CELLs (for example, LIT
 *  is used by the DRAWSTATE's live[] array).  Arguably this block of
 *  #defines should be with the typedef for CELL rather than here.
 */
struct game_state {
  DPAR *d;
  int lastrot_loc;
  int lastrot_dir;
  unsigned int flags;
#define SF_SOLVED 0x00000001
  CELL *net;
#define LINK_S 0
#define LINK_M 0x3f
#define LINK_BASE (1U << LINK_S)
#define LINK_ALL (LINK_M << LINK_S)
#define ERR_S 6
#define ERR_M 0x3f
#define ERR_BASE (1U << ERR_S)
#define ERR_ALL (ERR_M << ERR_S)
#define LOOP_S 12
#define LOOP_M 0x3f
#define LOOP_BASE (1U << LOOP_S)
#define LOOP_ALL (LOOP_M << LOOP_S)
#define BIDIR_S 18
#define BIDIR_M 0x3f
#define BIDIR_BASE (1U << BIDIR_S)
#define BIDIR_ALL (BIDIR_M << BIDIR_S)
#define LOCKED 0x01000000
#define UNUSED 0x02000000
#define DUP    0x04000000
#define LIT    0x08000000
#define MARK   0x10000000
  } ;

/*
 * The game UI struct.  This is part of game state when it comes to
 *  drawing, but not when it comes to undo/redo.  For example, the
 *  location of the light source is here.
 *
 * light is the index of the cell that is the origin for lighting up
 *  the game grid.  In a wrapping game, it holds a representative game
 *  cell index (one for which dupof[i]==i).
 *
 * lighton indicates whether lighting up is enabled (true) or not
 *  (false).
 *
 * dispmap and dispimap support scrolling.  dispmap maps an on-screen
 *  game cell location (a number [0..dp->asz2) which is neither UNUSED
 *  nor DUP) into the location index of the game grid being displayed
 *  there (as another such number).  This is a always a permutation on
 *  the non-(UNUSED|DUP) subset of [0..d->asz2); dispimap is the
 *  inverse permutation.  Both dispmap and dispimap have -1 in
 *  inapplicable subscripts (those that are UNUSED or DUP).  If wrap is
 *  false, dispmap and dispimap are always the identity maps, except
 *  for the UNUSED cells, which map to -1 in each map.  (I could have
 *  ignored them when not wrapping but it turns out to simplify the
 *  code to just use the maps regardless.)
 *
 * mismatch is used to flag mismatches in a find_mismatches operation.
 *  It is otherwise full of 0 bytes.  Bytes [1] through [asz2] are 0
 *  for no mismatch or 1 for mismatch, for the cells subscripted one
 *  lower; byte [0] is 0 usually, 1 when displaying mismatches, or 2
 *  for the first replot after displaying mismatches (to clear the
 *  mismatch markings).
 */
struct game_ui {
  int light;
  int lighton;
  int *dispmap;
  int *dispimap;
  unsigned char *mismatch;
  } ;

/*
 * Drawing state.  This is other state needed by drawing, mostly either
 *  sizes in pixels or transient state such as on-screen shadow state.
 *
 * hexsize is half the side of a hexagon, in pixels (half so the
 *  hexagon side is always even, which we want because a bunch of
 *  things do arithmetic with the hexagon half-side).
 *
 * hexr3 is hexsize * sqrt(3), the distance from a hexagon centre to
 *  the midpoint of a side.
 *
 * linew2 is, loosely put, the half-width of the lines drawn to display
 *  links.  If linew2 is zero, lines are drawn as simple lines;
 *  otherwise, they are drawn as rectangles, with the short end being
 *  (linew2*2)+1 pixels wide (with adjustments for coordinate rounding
 *  to integers).
 *
 * epcr (<e>nd<p>oint <c>entre <r>adius) is the radius of the circle
 *  drawn at the centre of an endpoint cell.
 *
 * nepcr (n + epcr) is the radius of the circle drawn at the centre of
 *  an non-endpoint cell.
 *
 * litcr is the radius of the (hollow) circle drawn to mark the
 *  light-up origin cell.
 *
 * animloc is the cell index of the cell being animated, if there is
 *  one.  If no cell is being animated, its value is meaningless and
 *  indeterminate.
 *
 * live is a copy of the net array from the STATE.  We make a copy
 *  because we change this to, for example, compute lighting-up status,
 *  only after that using it to drive drawing.
 *
 * cur is a shadow copy of live, storing what the screen is currently
 *  displaying.  Loosely, redraw() amounts to making cur match live.
 *
 * want is a per-cell boolean used in redraw().  (We could get away
 *  with only ceil(asz2/8) bytes, here, but we don't bother compacting
 *  it that much.)
 *
 * curlight is the currently-displayed location of the lighting-up
 *  source cell - that is, of light in the UI.  It is a location in the
 *  _displayed_ board, not the _stored_ board.  However, if it refers
 *  to a duplicated cell, it is the underlying location; that is,
 *  dupof[curlight]==curlight (except curlight==-1 during startup).
 *
 * lastflash is used for completion flashing.  When not flashing, it is
 *  negative; otherwise, it is the time when we last changed flash
 *  status.
 *
 * flashing is boolean, true when we're flashing, false when not.  This
 *  is used to make sure we end the last flash even if the time ran out
 *  first.
 *
 * lineoff[] is used to compute line coordinates relative to cell
 *  centres only once, rather than redoing that each time we want to
 *  draw a line.  See set_size() and redraw().
 */
struct game_drawstate {
  DPAR *d;
  int first;
  int w;
  int h;
  int hexsize;
  int hexr3;
  int linew2;
  int epcr;
  int nepcr;
  int litcr;
  int animloc;
  CELL *live;
  CELL *cur;
  unsigned char *want;
  int curlight;
  double lastflash;
  int flashing;
  IXY lineoff[6][4];
  } ;

/*
 * CDQ and CDQE are used in places (such as game generation) where we
 *  want to store a list of cell-and-directions.  (CDQ = <c>ell and
 *  <d>irection <q>ueue, though it is not, strictly, a queue; the E in
 *  CDQE is <e>ntry.)  See cdq_init(), cdq_add(), cdq_n(), cdq_get(),
 *  and cdq_done().
 *
 * The original use of a CDQ was to keep a list and draw randomly from
 *  it, but it has also found use where randomness is not important.
 *  See cdq_get().
 */

// x = cell index; dir = direction.
struct cdqe {
  int x;
  unsigned char dir;
  } ;

// v = vector of CDQE; a = allocated size, n = current size.
struct cdq {
  CDQE *v;
  int a;
  int n;
  } ;
// Initializer appropriate for a CDQ with static storage duration.
#define CDQ_STATIC_INIT {0,0,0}

/*
 * Solver state.
 *
 * dp is the DPAR for the puzzle in question.
 *
 * net is the initial state of the puzzle we're trying to solve.
 *  (Rotation of cells here may affect the order in which solutions are
 *  found, but - modulo bugs in the solver, of course - does not affect
 *  the set of solutions found.)
 *
 * pos is the current position of each cell; POS_UNSET for cells we
 *  haven't yet fixed in position, or a number 0-5, representing the
 *  number of times we've rotated that cell left from s's state, if we
 *  have.
 *
 * nopt is the number of position options each cell has, in view of all
 *  the cells fixed in place so far.
 *
 * opts holds those options; if nopt is N, opts has N of its low six
 *  bits set.
 *
 * heap is a heap holding cell indices, where the heap criterion is
 *  such that the top-of-heap is the index of the (or a) cell with the
 *  lowest nopt value.
 *
 * heapn is of course the size of the heap.
 *
 * heapx is the inverse of heap: if heap[a]==b, heapx[b]==a; if i is
 *  not in heap[], heapx[i]==-1.
 *
 * ans records the output: for cells that have been in the same
 *  position in every solution, it's the position (as for pos); for
 *  cells that have been seen in multiple positions, it's
 *  ANS_AMBIGUOUS.  (For UNUSED or DUP cells, it's meaningless and
 *  indeterminate.  If nsoln < 1, all of ans[] is meaningless and
 *  indeterminate.)
 *
 * nsoln is the number of solutions found so far.
 */
struct solver {
  const DPAR *dp;
  const CELL *net;
  unsigned char *pos;
#define POS_UNSET 6
#define POS_UNUSED 7
  unsigned char *nopt;
  unsigned char *opts;
  unsigned int *heap;
  int heapn;
#define HEAP_L(x) (((x)*2)+1)
#define HEAP_R(x) (((x)+1)*2)
#define HEAP_U(x) (((x)-1)/2)
  int *heapx;
  unsigned char *ans;
#define ANS_AMBIGUOUS 6
  int nsoln;
  int *dsf;
  } ;

/*
 * We encode things in base 64.  b64chars is the list of characters we
 *  use for this.  (It is conceptually very much like MIME's base64
 *  encoding, but different in detail - for example, the two
 *  non-alphanumeric characters chosen are different.)
 *
 * We have a trailing NUL here so we can pass this string directly to,
 *  eg, strspn.  The trailing space is so typed game descriptions can
 *  make more sense; spaces are ignored by new_game().
 */
static const char b64chars[66] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz@$ ";

/*
 * The square root of 3, used to get hexagon coordinates right - or at
 *  least as right as we can with integer pixel coordinates.
 */
#define ROOT_3 1.73205080756887729352744634150587236694280525381038062805580698

/*
 * Used to speed up rotation, particularly multiple rotations.  Given a
 *  six-bit bitmask p and a number n in [0..5], rot[p][n] is the result
 *  of rotating p left n steps.
 */
static unsigned char rot[64][6]
 = { { 0, 0, 0, 0, 0, 0 },
     { 1, 2, 4, 8, 16, 32 },
     { 2, 4, 8, 16, 32, 1 },
     { 3, 6, 12, 24, 48, 33 },
     { 4, 8, 16, 32, 1, 2 },
     { 5, 10, 20, 40, 17, 34 },
     { 6, 12, 24, 48, 33, 3 },
     { 7, 14, 28, 56, 49, 35 },
     { 8, 16, 32, 1, 2, 4 },
     { 9, 18, 36, 9, 18, 36 },
     { 10, 20, 40, 17, 34, 5 },
     { 11, 22, 44, 25, 50, 37 },
     { 12, 24, 48, 33, 3, 6 },
     { 13, 26, 52, 41, 19, 38 },
     { 14, 28, 56, 49, 35, 7 },
     { 15, 30, 60, 57, 51, 39 },
     { 16, 32, 1, 2, 4, 8 },
     { 17, 34, 5, 10, 20, 40 },
     { 18, 36, 9, 18, 36, 9 },
     { 19, 38, 13, 26, 52, 41 },
     { 20, 40, 17, 34, 5, 10 },
     { 21, 42, 21, 42, 21, 42 },
     { 22, 44, 25, 50, 37, 11 },
     { 23, 46, 29, 58, 53, 43 },
     { 24, 48, 33, 3, 6, 12 },
     { 25, 50, 37, 11, 22, 44 },
     { 26, 52, 41, 19, 38, 13 },
     { 27, 54, 45, 27, 54, 45 },
     { 28, 56, 49, 35, 7, 14 },
     { 29, 58, 53, 43, 23, 46 },
     { 30, 60, 57, 51, 39, 15 },
     { 31, 62, 61, 59, 55, 47 },
     { 32, 1, 2, 4, 8, 16 },
     { 33, 3, 6, 12, 24, 48 },
     { 34, 5, 10, 20, 40, 17 },
     { 35, 7, 14, 28, 56, 49 },
     { 36, 9, 18, 36, 9, 18 },
     { 37, 11, 22, 44, 25, 50 },
     { 38, 13, 26, 52, 41, 19 },
     { 39, 15, 30, 60, 57, 51 },
     { 40, 17, 34, 5, 10, 20 },
     { 41, 19, 38, 13, 26, 52 },
     { 42, 21, 42, 21, 42, 21 },
     { 43, 23, 46, 29, 58, 53 },
     { 44, 25, 50, 37, 11, 22 },
     { 45, 27, 54, 45, 27, 54 },
     { 46, 29, 58, 53, 43, 23 },
     { 47, 31, 62, 61, 59, 55 },
     { 48, 33, 3, 6, 12, 24 },
     { 49, 35, 7, 14, 28, 56 },
     { 50, 37, 11, 22, 44, 25 },
     { 51, 39, 15, 30, 60, 57 },
     { 52, 41, 19, 38, 13, 26 },
     { 53, 43, 23, 46, 29, 58 },
     { 54, 45, 27, 54, 45, 27 },
     { 55, 47, 31, 62, 61, 59 },
     { 56, 49, 35, 7, 14, 28 },
     { 57, 51, 39, 15, 30, 60 },
     { 58, 53, 43, 23, 46, 29 },
     { 59, 55, 47, 31, 62, 61 },
     { 60, 57, 51, 39, 15, 30 },
     { 61, 59, 55, 47, 31, 62 },
     { 62, 61, 59, 55, 47, 31 },
     { 63, 63, 63, 63, 63, 63 } };
#define ROT_L(x) rot[(x)][1]
#define ROT_R(x) rot[(x)][5]

/*
 * Used by the solver.  This stores the number of effectively distinct
 *  rotational positions for a six-bit value.  (This is 6 for most
 *  values, 3 for a straight line or X, 2 for a Y, and 1 for the all-0
 *  and all-1 values.  Puzzles we generate never use the all-0 or all-1
 *  values, but we want to be able to support them.)
 *
 * We do not initialize this here.  It is initialized by the solver the
 *  first time it's needed (note that we initialize the [0] element to
 *  0, but none of the elements are 0 in actual operation).
 */
static unsigned char posrots[64] = { 0 };

/*
 * Given a direction D, return the direction value to go the other way.
 *  (That is, if direction D takes us from A to B, otherway(D) is the
 *  direction that would take us from B to A.)
 */
static int otherway(int) __attribute__((__const__));
static int otherway(int d)
{
 return((d<3)?d+3:d-3);
}

/*
 * Return true if cell coordinate pair (x,y) does not refer to a used
 *  cell.  This includes x and/or y being out of range.
 *
 * If disp is false and wrapping is on, the display duplicates of
 *  duplicated cells are counted as unused.  Otherwise (disp true or
 *  wrapping off), they are considered used.
 */
static int unused_xy(const DPAR *d, int x, int y, int disp)
{
 return ( (x < 0) || (y < 0) || (x >= d->asz) || (y >= d->asz) ||
	  (d->flags[d->xyi[x][y]] & ((disp||!d->p.wrap) ? FCF_UNUSED : (FCF_UNUSED|FCF_DUP))) );
}

/*
 * Given a cell index and a direction, return the cell index of the
 *  next cell in that direction, or -1 if that step would take us
 *  outside the board - the effective board, not the allocated board.
 *
 * If disp is true, this operates on the displayed board, with
 *  boundaries at the edges and p->size cells along each edge.  If disp
 *  is false, this operates on the game board.  When d->p.wrap is
 *  false, the game board is the same as the displayed board; when
 *  true, the right and bottom edges of the displayed board are an
 *  alternative view of the left and top edges, and the input and
 *  output values must/will be non-UNUSED non-DUP cell indices.  (This
 *  also means that if disp is false and wrap is true, no valid input
 *  can lead to a -1 return.)
 */
static int connect_to(const DPAR *d, int cell, int dir, int disp)
{
 int x;
 int y;

 if ((cell < 0) || (cell >= d->asz2)) abort();
 x = d->ix[cell];
 y = d->iy[cell];
 if (unused_xy(d,x,y,disp)) abort();
 switch (dir)
  { case 0:
       x ++;
       break;
    case 1:
       x ++;
       y --;
       break;
    case 2:
       y --;
       break;
    case 3:
       x --;
       break;
    case 4:
       x --;
       y ++;
       break;
    case 5:
       y ++;
       break;
    default:
       abort();
       break;
  }
 if (d->p.wrap && !disp)
  { if (y == -1)
     { x -= d->p.size - 1;
       y = d->asz - 2;
     }
    if (x == -1)
     { x = d->asz - 2;
       y -= d->p.size - 1;
     }
    if ((y < 0) || (x < 0) || (y >= d->asz) || (x >= d->asz)) abort();
    // XXX Is this next test still needed with dupof[]?
    if (x == d->p.size-2-y)
     { x += d->p.size - 1;
       y += d->p.size - 1;
     }
    return(d->dupof[d->xyi[x][y]]);
  }
 else
  { if ((y < 0) || (x < 0) || (y >= d->asz) || (x >= d->asz)) return(-1);
    if (unused_xy(d,x,y,1)) return(-1);
    return(d->xyi[x][y]);
  }
}

/*
 * Initialize a newly-allocated CDQ in preparation for use.
 */
static void cdq_init(CDQ *q)
{
 q->v = 0;
 q->a = 0;
 q->n = 0;
}

/*
 * Add a CDQE to a CDQ.  We just realloc if necessary, then store.
 */
static void cdq_add(CDQ *q, CDQE e)
{
 if (q->n >= q->a)
  { q->v = srealloc(q->v,(q->a=q->n+8)*sizeof(CDQE));
  }
 q->v[q->n++] = e;
}

/*
 * Return the number of CDQEs in a CDQ.
 */
static int cdq_n(CDQ *q)
{
 return(q->n);
}

/*
 * Get a CDQE from a CDQ.  If rs is non-nil, it is used to select a
 *  random one; if not, we're doing something for which the order
 *  doesn't matter, so we pick whichever one is most convenient.  It is
 *  an error to call this on an empty CDQ.
 */
static CDQE cdq_get(CDQ *q, RANDOM_STATE *rs)
{
 int i;
 CDQE e;

 if (q->n < 1) abort();
 i = rs ? random_upto(rs,q->n) : (q->n - 1);
 e = q->v[i];
 q->n --;
 if (i != q->n) q->v[i] = q->v[q->n];
 return(e);
}

/*
 * Clean up a CDQ after use.  After this, the CDQ itself can be freed
 *  without leaking memory.  It is an error to call this on a nonempty
 *  CDQ.
 */
static void cdq_done(CDQ *q)
{
 if (q->n) abort();
 sfree(q->v);
}

/*
 * Our default-parameters method: size 5, no wrap, easy, uniq.
 */
static PARAMS *default_params(void)
{
 PARAMS *p;

 p = snew(PARAMS);
 p->size = 5;
 p->wrap = 0;
 p->hard = 0;
 p->uniq = 1;
 return(p);
}

/*
 * Our presets.  We offer sizes 3, 5, 7, 9, and 11, each one
 *  non-wrapping easy, wrapping easy, and wrapping hard, all uniq.
 *  (The difference between non-wrapping easy and non-wrapping hard is
 *  comparatively minor.)
 */
static bool fetch_preset(int i, char **name, PARAMS **pp)
{
 PARAMS *p;

 if ((i < 0) || (i > 14)) return(false);
 p = snew(PARAMS);
 p->size = ((i % 5) * 2) + 3;
 p->wrap = i > 4;
 p->hard = i > 9;
 p->uniq = 1;
 asprintf(name,"Size %d%s",p->size,p->wrap?p->hard?", wrap, hard":", wrapping":"");
 *pp = p;
 return(true);
}

/*
 * Free a PARAMS.  We have no pointed-to state, so this is easy.
 */
static void free_params(PARAMS *p)
{
 sfree(p);
}

/*
 * Clone a PARAMS.  We still have no pointed-to state, so this is easy.
 */
static PARAMS *dup_params(const PARAMS *p)
{
 PARAMS *n;

 n = snew(PARAMS);
 *n = *p;
 return(n);
}

/*
 * Decode a parameter string as encoded by encode_params(), storing the
 *  result into a given PARAMS.
 *
 * XXX Do we want to error if the string contains anything unexpected?
 *  We don't have a good error-reporting channel here, though.
 */
static void decode_params(PARAMS *p, const char *s)
{
 char *e;
 long int szl;
 int sz;

 szl = strtol(s,&e,0);
 if (e == s) szl = 0;
 sz = szl;
 if (sz != szl) sz = 0;
 p->size = sz;
 p->wrap = 0;
 p->hard = 0;
 p->uniq = 0;
 for (;*e;e++)
  { switch (*e)
     { case 'h':
	  p->hard = 1;
	  break;
       case 'w':
	  p->wrap = 1;
	  break;
       case 'u':
	  p->uniq = 1;
	  break;
     }
  }
}

/*
 * Encode a PARAMS into a string.
 */
static char *encode_params(const PARAMS *p, bool full)
{
 char *s;

 (void)full;
 asprintf(&s,"%d%s%s%s",p->size,p->wrap?"w":"",p->hard?"h":"",p->uniq?"u":"");
 return(s);
}

/*
 * Return our configuration menu.
 */
static CONFIG_ITEM *configure(const PARAMS *p)
{
 CONFIG_ITEM *cv;
 char *s;

 cv = snewn(5,CONFIG_ITEM);
 cv[0].name = "Size";
 cv[0].type = C_STRING;
 asprintf(&s,"%d",p->size);
 cv[0].u.string.sval = s;
 cv[1].name = "Wraparound";
 cv[1].type = C_BOOLEAN;
 cv[1].u.boolean.bval = p->wrap;
 cv[2].name = "Difficulty";
 cv[2].type = C_CHOICES;
 cv[2].u.choices.choicenames = ".Easy.Hard";
 cv[2].u.choices.selected = p->hard ? 1 : 0;
 cv[3].name = "Ensure unique";
 cv[3].type = C_CHOICES;
 cv[3].u.choices.choicenames = ".No.Yes";
 cv[3].u.choices.selected = p->uniq ? 1 : 0;
 cv[4].name = 0;
 cv[4].type = C_END;
 return(cv);
}

/*
 * Given a (possibly modified) configuration menu, convert it back into
 *  a PARAMS.
 */
static PARAMS *custom_params(const CONFIG_ITEM *cfg)
{
 PARAMS *p;

 p = snew(PARAMS);
 p->size = atoi(cfg[0].u.string.sval);
 p->wrap = cfg[1].u.boolean.bval;
 switch (cfg[2].u.choices.selected)
  { case 0:
       p->hard = 0;
       break;
    case 1:
       p->hard = 1;
       break;
    default:
       abort();
       break;
  }
 switch (cfg[3].u.choices.selected)
  { case 0:
       p->uniq = 0;
       break;
    case 1:
       p->uniq = 1;
       break;
    default:
       abort();
       break;
  }
 return(p);
}

/*
 * Validate a PARAMS obtained from, eg, custom_params().
 */
static const char *validate_params(const PARAMS *p, bool full)
{
 (void)full;
 if (p->size < 3) return("Size must be at least 3");
 return(0);
}

/*
 * Return a new DPAR for a given PARAMS.  We could try to memoize this,
 *  always returning the same DPAR for functionally identical PARAMSes,
 *  but PARAMS changes happen seldom enough for that to seem like
 *  unnecessary bother to me.
 */
static DPAR *dpar_new(const PARAMS *p)
{
 DPAR *d;
 int *v;
 int i;
 int x;
 int y;
 int *ix;
 int *iy;
 int **xyi;
 int *dupof;
 unsigned char *cf;
 unsigned char f;

 d = snew(DPAR);
 d->p = *p;
 d->asz = (p->size * 2) - 1;
 d->asz2 = d->asz * d->asz;
 d->hszd = (3 * p->size * (p->size - 1)) + 1;
 d->hszg = p->wrap ? d->hszd - (3 * p->size) + 2 : d->hszd;
 ix = snewn(d->asz2,int);
 iy = snewn(d->asz2,int);
 xyi = snewn(d->asz,int *);
 dupof = snewn(d->asz2,int);
 v = snewn(d->asz2,int);
 cf = snewn(d->asz2,char);
 d->fv[0] = ix;
 d->fv[1] = iy;
 d->fv[2] = xyi;
 d->fv[3] = dupof;
 d->fv[4] = v;
 d->fv[5] = cf;
 for (i=d->asz-1;i>=0;i--)
  { xyi[i] = v;
    v += d->asz;
  }
 i = d->asz2;
 for (y=d->asz-1;y>=0;y--) for (x=d->asz-1;x>=0;x--)
  { i --;
    ix[i] = x;
    iy[i] = y;
    xyi[x][y] = i;
    f = 0;
    if (y < p->size)
     { if (x < p->size-1-y)
	{ f = FCF_UNUSED;
	}
       else if (x == p->size-1-y)
	{ if (y == 0)
	   { f = FCF_WRAP_2;
	   }
	  else if (y == p->size-1)
	   { f = FCF_WRAP_3;
	   }
	  else
	   { f = FCF_WRAP_23;
	   }
	}
       else
	{ if (x == d->asz-1)
	   { f = FCF_DUP;
	     if (y == 0)
	      { f |= FCF_WRAP_1;
	      }
	     else if (y == p->size-1)
	      { f |= FCF_WRAP_0;
	      }
	     else
	      { f |= FCF_WRAP_01;
	      }
	   }
	  else if (y == 0)
	   { f = FCF_WRAP_12;
	   }
	}
     }
    else
     { int m;
       m = d->asz - (2 + y - p->size);
       if (x > m)
	{ f = FCF_UNUSED;
	}
       else
	{ if (y == d->asz-1)
	   { if (x == 0)
	      { f = FCF_DUP | FCF_WRAP_4;
	      }
	     else if (x == p->size-1)
	      { f = FCF_DUP | FCF_WRAP_5;
	      }
	     else
	      { f = FCF_DUP | FCF_WRAP_45;
	      }
	   }
	  else if (x == 0)
	   { f = FCF_WRAP_34;
	   }
	  else if (x == m)
	   { f = FCF_DUP | FCF_WRAP_50;
	   }
	}
     }
    if (! p->wrap) f &= FCF_UNUSED;
    cf[i] = f;
  }
#if 0
 printf("cf\n");
 i = 0;
 for (y=0;y<d->asz;y++)
  { printf("%*s",y,"");
    for (x=0;x<d->asz;x++)
     { putchar(' ');
       switch (cf[i])
	{ case 0:
	     f = '.';
	     break;
	  case FCF_UNUSED:
	     f = 'u';
	     break;
	  case FCF_DUP | FCF_WRAP_0:
	     f = '0';
	     break;
	  case FCF_DUP | FCF_WRAP_01:
	     f = 'a';
	     break;
	  case FCF_DUP | FCF_WRAP_1:
	     f = '1';
	     break;
	  case FCF_WRAP_12:
	     f = 'b';
	     break;
	  case FCF_WRAP_2:
	     f = '2';
	     break;
	  case FCF_WRAP_23:
	     f = 'c';
	     break;
	  case FCF_WRAP_3:
	     f = '3';
	     break;
	  case FCF_WRAP_34:
	     f = 'd';
	     break;
	  case FCF_DUP | FCF_WRAP_4:
	     f = '4';
	     break;
	  case FCF_DUP | FCF_WRAP_45:
	     f = 'e';
	     break;
	  case FCF_DUP | FCF_WRAP_5:
	     f = '5';
	     break;
	  case FCF_DUP | FCF_WRAP_50:
	     f = 'f';
	     break;
	  default:
	     f = '\0';
	     printf("<%d>",cf[i]);
	     break;
	}
       if (f) putchar(f);
       i ++;
     }
    putchar('\n');
  }
 if (d->asz2) exit(0);
#endif
 i = d->asz2;
 for (y=d->asz-1;y>=0;y--) for (x=d->asz-1;x>=0;x--)
  { i --;
    if (cf[i] & FCF_UNUSED)
     { dupof[i] = -1;
     }
    else if (cf[i] & FCF_DUP)
     { if (x == d->asz-1)
	{ if (y == d->p.size - 1)
	   { dupof[i] = d->p.size - 1;
	   }
	  else
	   { dupof[i] = i + ((d->p.size - 2) * d->asz) + 1;
	   }
	}
       else if (y == d->asz-1)
	{ if (x == d->p.size - 1)
	   { dupof[i] = (d->p.size - 1) * d->asz;
	   }
	  else
	   { dupof[i] = i - ((d->asz-1) * d->asz) + d->p.size - 1;
	   }
	}
       else
	{ dupof[i] = i - ((d->p.size * d->asz) - 1) + d->p.size - 1;
	}
     }
    else
     { dupof[i] = i;
     }
  }
 d->ix = ix;
 d->iy = iy;
 d->xyi = (void *) xyi;
 d->dupof = dupof;
 d->flags = cf;
 d->refs = 1;
 return(d);
}

/*
 * Add a reference to a DPAR, returning it for convenience.
 */
static DPAR *dpar_ref(DPAR *d)
{
 if (d->refs < 1) abort();
 d->refs ++;
 return(d);
}

/*
 * Drop a reference to a DPAR, freeing it if that takes its refcount
 *  below 1.
 */
static void dpar_deref(DPAR *d)
{
 d->refs --;
 if (d->refs < 1)
  { sfree(d->fv[0]);
    sfree(d->fv[1]);
    sfree(d->fv[2]);
    sfree(d->fv[3]);
    sfree(d->fv[4]);
    sfree(d->fv[5]);
    sfree(d);
  }
}

/*
 * Given a six-bit mask, return true iff it has all but one of its bits
 *  set.  This is used by, eg, puzzle generation, where we want to
 *  treat such cells differently to avoid creating cells with all six
 *  links present (because such are orientation-independent).
 */
static int all_but_one(unsigned char v)
{
 switch (v)
  { case 0x3e:
    case 0x3d:
    case 0x3b:
    case 0x37:
    case 0x2f:
    case 0x1f:
       return(1);
       break;
  }
 return(0);
}

/*
 * Given a six-bit mask, return true iff it has exactly one of its bits
 *  set.  This is used to, eg, identify endpoints in redraw().
 */
static int only_one(unsigned char v)
{
 switch (v)
  { case 0x01:
    case 0x02:
    case 0x04:
    case 0x08:
    case 0x10:
    case 0x20:
       return(1);
       break;
  }
 return(0);
}

/*
 * Debugging assist.  Dumps a text representation of a CELL grid to
 *  stdout, where bit is the low bit of the six-bit field that should
 *  be drawn (with \, /, and -- characters) in the output.  bit should
 *  thus be LINK_BASE to display links, LOOP_BASE for loops, etc.  This
 *  is marked __used__ so it is present (and thus callable from a
 *  debugger) even if it's never called by code here.
 */
static void dump_cells(const DPAR *d, const CELL *v, CELL bit)
{
 int x;
 int y;
 int i;
 char c[8];

 i = 0;
 for (y=0;y<d->asz;y++)
  { printf("%*s",y*4,"");
    for (x=0;x<d->asz;x++)
     { printf("  %c  %c  ",
		((v[i+x] >> 2) & bit) ? '\\' : ' ',
		((v[i+x] >> 1) & bit) ? '/' : ' ' );
     }
    printf("\n");
    printf("%*s",y*4,"");
    for (x=0;x<d->asz;x++)
     { c[0] = ((v[i+x] >> 3) & bit) ? '-' : ' ';
       c[1] = c[0];
       c[2] = c[0];
       sprintf(&c[3],"%02d",(i+x)%100);
       c[7] = ((v[i+x] >> 0) & bit) ? '-' : ' ';
       c[6] = c[7];
       c[5] = c[7];
       if (v[i+x] & UNUSED)
	{ c[3] = '.';
	  c[4] = '.';
	}
       if (v[i+x] & DUP)
	{ c[2] = '(';
	  c[5] = ')';
	}
       if (v[i+x] & LIT)
	{ c[1] = '*';
	  c[6] = '*';
	}
       printf("%.8s",&c[0]);
     }
    printf("\n");
    printf("%*s",y*4,"");
    for (x=0;x<d->asz;x++)
     { printf("  %c  %c  ",
		((v[i+x] >> 4) & bit) ? '/' : ' ',
		((v[i+x] >> 5) & bit) ? '\\' : ' ' );
     }
    printf("\n");
    i += d->asz;;
  }
}

/*
 * Puzzle generation, easy version.
 *
 * This version starts from the centre cell of the grid and repeatedly
 *  enlarges the tree by one step, always being careful to neither fill
 *  in the last line from a cell (because the result would be
 *  orientation-independent, making the puzzle too easy) nor create a
 *  loop.  Because we are always linking isolated cells to the growing
 *  tree, this can never stall without finishing.  (In order for that
 *  to happen, we would have to have a cell surrounded by a ring of
 *  all-but-one cells, which can't happen because that would entail a
 *  loop.)
 *
 * This tends to generate puzzles with endpoints clustered away from
 *  the middle.  For non-wrapping puzzles, this is to be expected,
 *  because of the barriers at the edge of the board, but for wrapping
 *  puzzles, those clusters make the puzzle easier by providing lots of
 *  places to get deductions started.  See gen_solved_hard().
 */
static void gen_solved_easy(DPAR *dp, CELL *net, RANDOM_STATE *rs)
{
 int i;
 int j;
 CDQ q;
 CDQE e;

 i = (dp->p.size - 1) * (dp->asz + 1);
 cdq_init(&q);
 for (j=5;j>=0;j--) cdq_add(&q,(CDQE){.x=i,.dir=j});
 while (cdq_n(&q))
  { e = cdq_get(&q,rs);
    // If this would be the last line for this node, skip.
    if (all_but_one(net[e.x])) continue;
    i = connect_to(dp,e.x,e.dir,0);
    // If line points to unused space, skip.
    if (unused_xy(dp,dp->ix[i],dp->iy[i],0)) continue;
    // If the target has already been included, skip.
    // (We depend on "included" == "has >=1 line(s)".)
    if (net[i] != 0) continue;
    // Add the line.
    net[e.x] |= 1U << e.dir;
    net[i] = 1U << otherway(e.dir);
    // Queue all lines from the target.
    for (j=5;j>=0;j--) cdq_add(&q,(CDQE){.x=i,.dir=j});
  }
 cdq_done(&q);
}

/*
 * Puzzle generation, hard version.
 *
 * This operates by making a list of all possible <cell,dir> pairs.  It
 *  then goes through every element of that list in a random order.
 *  For each one, it ignores it if the cell already has all but one of
 *  its links, if the link would create a loop, or if the link links
 *  outside the board.  (For a wrapping game, that last condition
 *  cannot trip.)  Note that each line is present on the list twice,
 *  once for each of the involved cells; we could prune them from the
 *  list, but it seems unnecessary - the second copy of each line just
 *  ends up being skipped as a (trivial) loop.
 *
 * I'm not sure whether this algorithm can stall, ie, can run out of
 *  lines without connecting the whole board into a single tree.  In
 *  the square-grid analog, it can, but on the hex grid I think a chain
 *  of all-but-one cells can't happen because it will involve
 *  three-cell loops, and even if it did happen it would always a
 *  hexagon around an isolated cell.  However, since I haven't been
 *  able to prove it to the level of rigour I want, we check and, if we
 *  didn't generate a single tree, we just restart.  (We check this by
 *  counting how many lines we added; since we never create loops, we
 *  have a single tree exactly when we have one fewer lines than cells
 *  involved - every tree (connected loop-free undirected graph) has
 *  exactly one fewer lines than vertices.  For finite or countably
 *  infinite graphs this can be proved by induction; the finite case is
 *  obviously the one we care about.)
 *
 * XXX This should use the DSF routines instead of rolling its own.
 *  The use of a local variant is a historical artifact - I wrote this
 *  before I understood the DSF routines.
 *
 * XXX Should refactor the core of this code and the core of
 *  randomize_ambiguous().
 */
static void gen_solved_hard(DPAR *dp, CELL *net, RANDOM_STATE *rs)
{
 int *tn;
 CDQ q;
 CDQE e;
 int n;
 int i;
 int j;
 int k;
 int f;
 int t;
 int fails;

 tn = snewn(dp->asz2,int);
 fails = 0;
 while (1)
  { cdq_init(&q);
    n = 0;
    for (i=dp->asz2-1;i>=0;i--)
     { if (dp->flags[i] & (FCF_UNUSED|FCF_DUP)) continue;
       tn[i] = i;
       for (j=5;j>=0;j--) cdq_add(&q,(CDQE){.x=i,.dir=j});
       n ++;
     }
    if (n != dp->hszg) abort();
    n = 0;
    while (cdq_n(&q))
     { e = cdq_get(&q,rs);
       // If this node is down to one line left, skip.
       if (all_but_one(net[e.x])) continue;
       i = connect_to(dp,e.x,e.dir,0);
       // If line points to unused space, skip.
       if ((i < 0) || unused_xy(dp,dp->ix[i],dp->iy[i],0)) continue;
       // If this would create a loop, skip.
       if (tn[i] == tn[e.x]) continue;
       // If the linked-to node is down to one line left, skip.
       if (all_but_one(net[i])) continue;
       // Add the line.
       net[e.x] |= 1U << e.dir;
       net[i] |= 1U << otherway(e.dir);
       // Collapse the tree IDs.
       f = tn[i];
       t = tn[e.x];
       for (k=dp->asz2-1;k>=0;k--) if (tn[k] == f) tn[k] = t;
       // Count added lines.
       n ++;
     }
    cdq_done(&q);
    if (n == dp->hszg-1) break;
    fails ++;
  }
 sfree(tn);
// printf("hexgen gen: fails = %d\n",fails);
}

/*
 * Validate a game description.
 *
 * Given how constrained the API here is, I see no way to get the DPAR
 *  for a game here.  This means we have to compute anything we need
 *  ourselves.
 *
 * So I'm punting on most of the verification here.  I would _like_ to
 *  verify that the string length is correct for the size and maybe
 *  that it has the right number of half-links.
 */
static const char *validate_desc(const PARAMS *p, const char *desc)
{
 (void)p;
 if (strspn(desc,&b64chars[0]) != strlen(desc)) return("Game description contains unexpected character");
 return(0);
}

/*
 * Neighbour function for loop detection (see findloop.c) when checking
 *  to see if a loop is present in the game state.
 *
 * See below for why the trailing underscore.
 */
static int loop_neighbour_(int v, void *vc)
{
 LOOPCTX *c;
 CELL *net;
 const DPAR *dp;
 int d;
 int v2;

 c = vc;
 net = c->s->net;
 dp = c->s->d;
 if (v >= 0)
  { if (net[v] & UNUSED) return(-1);
    c->v = v;
    d = 0;
  }
 else
  { v = c->v;
    d = c->d;
    if (d >= 6) return(-1);
  }
 while (1)
  { if ((net[v] >> d) & LINK_BASE)
     { v2 = connect_to(dp,v,d,0);
       if ( (v2 >= 0) &&
	    ((net[v2] >> otherway(d)) & LINK_BASE) )
	{ c->d = d + 1;
	  return(v2);
	}
     }
    d ++;
    if (d >= 6)
     { c->d = d;
       return(-1);
     }
  }
}

/*
 * Wrappar around loop_neighbour_(), above.  This exists as debugging
 *  assist.  At one point, I had a bug that led me to try to
 *  loop-detect in a graph that wasn't actually undirected (that is, A
 *  links to B, but B doesn't link back to A), a thing which tends to
 *  throw the algorithm used by findloop.c into an infinite loop.  This
 *  was debugging code - I was recording exactly what loop_neighbour
 *  was returning, so I could inspect it in a debugger when the thing
 *  went into an infinite loop.
 *
 * These variables, lrecord(), and loop_neighbour() are the wrapper.
 */

static int (*lb)[3];
static int la = 0;
static int ln;
static int lv;

static void lrecord(int v1, int v2, int v3)
{
 if (ln >= la) abort();
 lb[ln][0] = v1;
 lb[ln][1] = v2;
 lb[ln][2] = v3;
 ln ++;
}

static int loop_neighbour(int v, void *vc)
{
 int r;

 r = loop_neighbour_(v,vc);
 if (v < 0)
  { if (lv < 0) abort();
    lrecord(-1,lv,r);
  }
 else
  { lrecord(v,v,r);
    lv = v;
  }
 return(r);
}

/*
 * Check a STATE for loops.  Return the number of edges belonging to
 *  loops - at the moment, nothing uses this value, but it's there in
 *  case something wants it.
 *
 * This contains some infrastructure supporting the debugging wrapper
 *  mentioned above, but is mostly just a wrapper for the findloop_*()
 *  loop-finding API.  The point is to set the LOOP_* bits for any
 *  (half-)edges belonging to loops.
 */
static int find_loops(STATE *s)
{
 int i;
 int d;
 int j;
 int n;
 LOOPCTX ctx;
 FINDLOOPSTATE *fls;

 la = s->d->asz2*7;
 lb = smalloc(la*sizeof(*lb));
 ln = 0;
 lv = -1;
 n = 0;
 fls = findloop_new_state(s->d->asz2);
 ctx.s = s;
 findloop_run(fls,s->d->asz2,&loop_neighbour,&ctx);
 for (i=s->d->asz2-1;i>=0;i--) s->net[i] &= ~LOOP_ALL;
 for (i=s->d->asz2-1;i>=0;i--)
  { if (s->net[i] & UNUSED) continue;
    for (d=5;d>=0;d--)
     { if ((s->net[i] >> d) & LINK_BASE)
	{ j = connect_to(s->d,i,d,0);
	  if ( (j >= 0) &&
	       ((s->net[j] >> otherway(d)) & LINK_BASE) &&
	       findloop_is_loop_edge(fls,i,j) )
	   { s->net[i] |= LOOP_BASE << d;
	     s->net[j] |= LOOP_BASE << otherway(d);
	     n ++;
	   }
	}
     }
  }
 findloop_free_state(fls);
 return(n);
}

/*
 * Given a game description, such as returned by new-game_desc(),
 *  instantiate it as a STATE.
 *
 * We call find_loops() here because otherwise, any loops in the graph
 *  aren't noticed until after our first rotation.
 *
 * We could fix this by checking for loops on every redraw, but it
 *  seems better to me to do that check only when something happens
 *  that might create a loop.
 */
static STATE *new_game(midend *me, const PARAMS *p, const char *desc)
{
 STATE *s;
 DPAR *dp;
 int i;
 int j;
 const char *inx;

 (void)me;
 s = snew(STATE);
 dp = dpar_new(p);
 s->d = dp;
 s->lastrot_loc = -1;
 s->flags = 0;
 s->net = smalloc(dp->asz2*sizeof(*s->net));
 for (i=0;i<dp->asz2;i++)
  { if (dp->flags[i] & FCF_UNUSED)
     { s->net[i] = UNUSED;
     }
    else if (dp->p.wrap && (dp->flags[i] & FCF_DUP))
     { s->net[i] = DUP;
     }
    else
     { if (! *desc)
	{ s->net[i] = 0;
	}
       else
	{ inx = index(&b64chars[0],*desc++);
	  if (! inx) abort();
	  j = inx - &b64chars[0];
	  if (j > 63)
	   { i --;
	     continue;
	   }
	  s->net[i] = j << LINK_S;
	}
     }
  }
 find_loops(s);
 return(s);
}

/*
 * Duplicate a game state.
 */
static STATE *dup_game(const STATE *s)
{
 STATE *n;

 n = snew(STATE);
 *n = *s;
 n->d = dpar_ref(s->d);
 n->net = smalloc(n->d->asz2*sizeof(*n->net));
 bcopy(s->net,n->net,n->d->asz2*sizeof(*n->net));
 return(n);
}

/*
 * Free a game state.
 */
static void free_game(STATE *s)
{
 dpar_deref(s->d);
 sfree(s->net);
 sfree(s);
}

/*
 * Set up posrots[], if it's not already.
 */
static void solver_setup_posrots(void)
{
 int i;
 int r;
 int n;

 if (posrots[0] != 0) return;
 for (i=64-1;i>=0;i--)
  { n = 0;
    r = i;
    do
     { r = ROT_L(r);
       n ++;
     } while (r != i);
    posrots[i] = n;
  }
}

/*
 * Bubble a value down in the solver heap.
 */
static void solver_reheap_down(SOLVER *s, int x)
{
 int l;
 int r;
 unsigned int v;
 unsigned char cv;
 int i;

 v = s->heap[x];
 cv = s->nopt[v];
 while (1)
  { l = HEAP_L(x);
    if (l >= s->heapn) break;
    r = HEAP_R(x);
    if ((r >= s->heapn) || (cv < s->nopt[s->heap[r]]))
     { if (cv < s->nopt[s->heap[l]])
	{ break;
	}
       else
	{ i = l;
	}
     }
    else
     { if (cv < s->nopt[s->heap[l]])
	{ i = r;
	}
       else
	{ i = (s->nopt[s->heap[l]] < s->nopt[s->heap[r]]) ? l : r;
	}
     }
    s->heap[x] = s->heap[i];
    s->heapx[s->heap[x]] = x;
    x = i;
  }
 s->heap[x] = v;
 s->heapx[v] = x;
}

/*
 * Bubble a value up in the solver heap.
 */
static void solver_reheap_up(SOLVER *s, int x)
{
 int u;
 unsigned int v;
 unsigned char cv;

 v = s->heap[x];
 cv = s->nopt[v];
 while (1)
  { if (x == 0) break;
    u = HEAP_U(x);
    if (cv >= s->nopt[s->heap[u]]) break;
    s->heap[x] = s->heap[u];
    s->heapx[s->heap[x]] = x;
    x = u;
  }
 s->heap[x] = v;
 s->heapx[v] = x;
}

/*
 * The values in s->heap are in unknown or unsorted order.  Reorder
 *  them so that it's a heap.
 */
static void solver_heap_setup(SOLVER *s)
{
 int i;

 for (i=HEAP_U(s->heapn-1);i>=0;i--) solver_reheap_down(s,i);
}

/*
 * Remove cell c from the solver heap.
 *
 * XXX Arguably this code should reheap up too, and to be correct in
 *  full generality we'd need to.  We can get away with this mostly
 *  because this is never called except for the top-of-heap element.
 */
static void solver_heap_remove(SOLVER *s, int c)
{
 int x;

 x = s->heapx[c];
 if ((x < 0) || (x >= s->heapn) || (s->heap[x] != c)) abort();
 s->heapn --;
 s->heapx[c] = -1;
 if (x == s->heapn) return;
 s->heap[x] = s->heap[s->heapn];
 s->heapx[s->heap[x]] = x;
 solver_reheap_down(s,x);
}

/*
 * Add cell c to the solver heap.
 */
static void solver_heap_add(SOLVER *s, int c)
{
 int x;

 if (s->heapx[c] >= 0) abort();
 x = s->heapn++;
 s->heapx[c] = x;
 s->heap[x] = c;
 solver_reheap_up(s,x);
}

/*
 * The solver has found a solution.  Update accordingly.
 */
static void solver_found(SOLVER *s)
{
 int i;
 int d;
 unsigned char c;
 int j;

 dsf_init(s->dsf,s->dp->asz2);
 for (i=s->dp->asz2-1;i>=0;i--)
  { if (s->pos[i] > 6-1) continue;
    if (s->dp->flags[i] & (FCF_UNUSED|FCF_DUP)) continue;
    c = rot[(s->net[i]>>LINK_S)&LINK_M][s->pos[i]];
    for (d=6-1;d>=0;d--)
     { if ((c >> d) & 1)
	{ j = connect_to(s->dp,i,d,0);
	  if (j < 0) abort();
	  dsf_merge(s->dsf,i,j);
	}
     }
  }
#ifdef HEXNET_VERBOSE_SOLVE
 printf("solution found, dsf_size = %d, hszg = %d\n",dsf_size(s->dsf,s->dp->asz-2),s->dp->hszg);
#endif
 if (dsf_size(s->dsf,s->dp->asz-2) != s->dp->hszg) return;
 if (s->nsoln < 1)
  { bcopy(s->pos,s->ans,s->dp->asz2);
    s->nsoln = 1;
    return;
  }
 for (i=s->dp->asz2-1;i>=0;i--)
  { if (s->ans[i] == ANS_AMBIGUOUS) continue;
    if (s->pos[i] != s->ans[i]) s->ans[i] = ANS_AMBIGUOUS;
  }
 s->nsoln ++;
}

/*
 * Update the solver's opts and nopt array values for cell c.
 */
static void solver_update_opts(SOLVER *s, int c)
{
 int d;
 int a;
 int nd;
 int r;
 int p;
 unsigned char opts;
 unsigned char nopt;
 unsigned char adj[6];
 unsigned char set;
 unsigned char oldn;

 nd = posrots[(s->net[c]>>LINK_S)&LINK_M];
 set = 0x3f;
 for (d=6-1;d>=0;d--)
  { a = connect_to(s->dp,c,d,0);
    if (a < 0)
     { adj[d] = 0;
     }
    else
     { r = s->pos[a];
       if (r == POS_UNSET)
	{ adj[d] = 0x3f;
	  set &= ~(1U << d);
	}
       else
	{ adj[d] = rot[(s->net[a]>>LINK_S)&LINK_M][r];
	}
     }
  }
 opts = 0;
 nopt = 0;
 for <"rot"> (r=nd-1;r>=0;r--)
  { p = rot[(s->net[c]>>LINK_S)&LINK_M][r];
    for (d=6-1;d>=0;d--)
     { if ((p >> d) & 1)
	{ if (! ((adj[d] >> otherway(d)) & 1)) continue <"rot">;
	}
       else
	{ if ((set >> d) & (adj[d] >> otherway(d)) & 1) continue <"rot">;
	}
     }
    opts |= 1U << r;
    nopt ++;
  }
 oldn = s->nopt[c];
 s->opts[c] = opts;
 s->nopt[c] = nopt;
 p = s->heapx[c];
 if (p >= 0)
  { if (nopt < oldn)
     { solver_reheap_up(s,p);
     }
    else if (nopt > oldn)
     { solver_reheap_down(s,p);
     }
  }
}

/*
 * The solver has (tentatively) set position x.  Update its adjacent
 *  cells accordingly.
 */
static void solver_update_adjacent(SOLVER *s, int x)
{
 int d;
 int a;

 for (d=6-1;d>=0;d--)
  { a = connect_to(s->dp,x,d,0);
    if (a < 0) continue;
    solver_update_opts(s,a);
  }
}

/*
 * Run the solver proper.
 */
static void solver_run(SOLVER *s)
{
 int toh;
 unsigned char opts;
 int i;

#ifdef HEXNET_VERBOSE_SOLVE
 printf("solver_run entered, heapn %d\n",s->heapn);
 printf("heap");
 for (i=0;i<s->heapn;i++) printf(" %d",s->heap[i]);
 printf("\n");
 printf("    ");
 for (i=0;i<s->s->d->asz2;i++) printf("%3d",i);
 printf("\n");
 printf("pos ");
 for (i=0;i<s->s->d->asz2;i++)
  { switch (s->pos[i])
     { case POS_UNUSED: printf("  u"); break;
       case POS_UNSET:  printf("  -"); break;
       default:         printf("  %d",s->pos[i]); break;
     }
  }
 printf("\n");
 printf("nopt");
 for (i=0;i<s->s->d->asz2;i++)
  { switch (s->pos[i])
     { case POS_UNUSED: printf("  -"); break;
       default:         printf("  %d",s->nopt[i]); break;
     }
  }
 printf("\n");
 printf("opts");
 for (i=0;i<s->s->d->asz2;i++)
  { switch (s->pos[i])
     { case POS_UNUSED: printf("  -"); break;
       default:         printf(" %02x",s->opts[i]); break;
     }
  }
 printf("\n");
 printf("nsoln %d\n",s->nsoln);
 if (s->nsoln > 0)
  { printf("ans ");
    for (i=0;i<s->s->d->asz2;i++)
     { if (s->pos[i] == POS_UNUSED)
	{ printf("  -");
	}
       else if (s->ans[i] == ANS_AMBIGUOUS)
	{ printf(" ??");
	}
       else
	{ printf("  %d",s->ans[i]);
	}
     }
    printf("\n");
  }
#endif
 if (s->heapn < 1)
  { solver_found(s);
    return;
  }
 toh = s->heap[0];
 opts = s->opts[toh];
 if (opts == 0) return;
 if (s->heapx[toh] != 0) abort();
 solver_heap_remove(s,toh);
 for (i=6-1;i>=0;i--)
  { if ((opts >> i) & 1)
     { s->pos[toh] = i;
       solver_update_adjacent(s,toh);
       solver_run(s);
     }
    s->pos[toh] = POS_UNSET;
    solver_update_adjacent(s,toh);
  }
 solver_heap_add(s,toh);
}

static void solver_setup(SOLVER *s, const DPAR *dp, const CELL *net)
{
 int i;

 solver_setup_posrots();
 s->dp = dp;
 s->net = net;
 s->pos = snewn(dp->asz2,unsigned char);
 s->nopt = snewn(dp->asz2,unsigned char);
 s->opts = snewn(dp->asz2,unsigned char);
 s->heap = snewn(dp->asz2,unsigned int);
 s->heapn = 0;
 s->heapx = snewn(dp->asz2,unsigned int);
 s->ans = snewn(dp->asz2,unsigned char);
 s->nsoln = 0;
 s->dsf = snew_dsf(dp->asz2);
 for (i=dp->asz2-1;i>=0;i--)
  { if (dp->flags[i] & (FCF_UNUSED|FCF_DUP))
     { s->pos[i] = POS_UNUSED;
       s->heapx[i] = -1;
     }
    else
     { s->pos[i] = POS_UNSET;
       s->heap[s->heapn] = i;
       s->heapx[i] = s->heapn;
       s->heapn ++;
     }
    s->nopt[i] = 0;
    s->opts[i] = 0;
  }
 solver_heap_setup(s);
 for (i=dp->asz2-1;i>=0;i--)
  { if (! (dp->flags[i] & (FCF_UNUSED|FCF_DUP)))
     { solver_update_opts(s,i);
     }
  }
}

static void solver_teardown(SOLVER *s)
{
 sfree(s->pos);
 sfree(s->nopt);
 sfree(s->opts);
 sfree(s->heap);
 sfree(s->heapx);
 sfree(s->ans);
 sfree(s->dsf);
}

/*
 * Randomize all links touching ANS_AMBIGUOUS cells.
 *
 * This is basically a version of gen_solved_hard that randomizes only
 *  some of the board's links.
 *
 * We set up a DSF and, for each link with an unambiguous cell on each
 *  end, merge those ends.  Other links go on a CDQ, once for each end;
 *  for links with ambiguous cells on each end, we do each end when
 *  handling that cell, while, for links with ambiguous on one end and
 *  unambiguous on the other, we do both ends when handling the
 *  ambiguous end.  Then we do the same sort of loop gen_solved_hard
 *  does, taking the CDQ's links in a random order and doing the same
 *  tests it does.
 *
 * For unambiguous links, we count only actually-present links.  For
 *  links with at least one ambiguous end, we count all potential
 *  links, present or not.
 *
 * XXX Should refactor the core of this code and the core of
 *  gen_solved_hard().
 */
static void randomize_ambiguous(SOLVER *s, CELL *net, RANDOM_STATE *rs)
{
 int i;
 int j;
 int k;
 int o;
 CDQ q;
 CDQE e;
 int n;

#ifdef HEXNET_VERBOSE_UNIQ
 printf("randomize_ambiguous called on\n");
 for (i=s->dp->asz2-1;i>=0;i--) if (s->ans[i] == ANS_AMBIGUOUS) net[i] |= LIT;
 dump_cells(s->dp,net,1);
#endif
 while (1)
  { dsf_init(s->dsf,s->dp->asz2);
    cdq_init(&q);
    n = 0;
    for (i=s->dp->asz2-1;i>=0;i--)
     { if (s->pos[i] == POS_UNUSED) continue;
       if (s->ans[i] != ANS_AMBIGUOUS)
	{ for (j=6-1;j>=0;j--)
	   { if (net[i] & (1U << j))
	      { k = connect_to(s->dp,i,j,0);
		if (k < 0) abort();
		if (s->ans[k] == ANS_AMBIGUOUS) continue;
		n ++;
		dsf_merge(s->dsf,i,k);
	      }
	   }
	  continue;
	}
       for (j=6-1;j>=0;j--)
	{ k = connect_to(s->dp,i,j,0);
	  if (k < 0) continue;
	  cdq_add(&q,(CDQE){.x=i,.dir=j});
	  net[i] &= ~(1U << j);
	  if (s->ans[k] == ANS_AMBIGUOUS) continue;
	  o = otherway(j);
	  cdq_add(&q,(CDQE){.x=k,.dir=o});
	  net[k] &= ~(1U << o);
	}
     }
    if (n & 1) abort();
    n >>= 1;
    while (cdq_n(&q))
     { e = cdq_get(&q,rs);
       if (all_but_one(net[e.x])) continue;
       k = connect_to(s->dp,e.x,e.dir,0);
       if ((k < 0) || unused_xy(s->dp,s->dp->ix[k],s->dp->iy[k],0)) continue;
       if (dsf_canonify(s->dsf,e.x) == dsf_canonify(s->dsf,k)) continue;
       if (all_but_one(net[k])) continue;
       net[e.x] |= 1U << e.dir;
       net[k] |= 1U << otherway(e.dir);
       dsf_merge(s->dsf,e.x,k);
       n ++;
     }
    cdq_done(&q);
    if (n == s->dp->hszg-1) break;
  }
#ifdef HEXNET_VERBOSE_UNIQ
 printf("randomize_ambiguous returning\n");
 for (i=s->dp->asz2-1;i>=0;i--) if (s->pos[i] != POS_UNUSED) net[i] &= 63;
 dump_cells(s->dp,net,1);
#endif
}

/*
 * Generate a new game and return a description string for it.
 *
 * We just call on gen_solved_*() to generate the solved form, mutate
 *  when necessary if we're doing unique-solution generation, and
 *  rotate each cell right a random number of times in [0..6).  Then we
 *  encode it for new_game().
 *
 * The only other thing of comment here is that we really want a DPAR
 *  for the argument PARAMS, but there is nowhere appropriate to hang
 *  it - no STATE or DRAWSTATE or any such.  So, ugly as it is, we have
 *  a static variable here which we use as a cache of size one,
 *  throwing it away and creating a new one for our PARAMS if it's
 *  different from the one in the cached DPAR (or, the first time, if
 *  there is nothing in the cache).
 */
static char *new_game_desc(const PARAMS *p, RANDOM_STATE *rs, char **aux, bool interactive)
{
 CELL *net;
 int i;
 int j;
 char *desc;
 static DPAR *dp = 0;

 (void)aux;
 (void)interactive;
 // dp is the ugly DPAR cache of size one described above.
 if (dp && ((dp->p.size != p->size) || (dp->p.wrap != p->wrap) || (dp->p.hard != p->hard) || (dp->p.uniq != p->uniq)))
  { dpar_deref(dp);
    dp = 0;
  }
 if (! dp) dp = dpar_new(p);
 net = snewn(dp->asz2,CELL);
 for (i=dp->asz2-1;i>=0;i--)
  { if (dp->flags[i] & FCF_UNUSED)
     { net[i] = UNUSED;
     }
    else if ((dp->flags[i] & FCF_DUP) && dp->p.wrap)
     { net[i] = DUP;
     }
    else
     { net[i] = 0;
     }
  }
 while (1)
  { if (p->hard) gen_solved_hard(dp,net,rs); else gen_solved_easy(dp,net,rs);
    if (p->uniq)
     { SOLVER s;
       /*
	* Loop only a relatively small number of times here.
	*
	* It is conceivable that the generated puzzle might contain an
	*  ambiguity that cannot be removed by re-randomizing without,
	*  for example, generating a cell with all its links set.  I
	*  can't think of a specific example, but I also have no proof
	*  it can't happen.  In practice I have yet to see a case where
	*  we need to do even two randomize_ambiguous runs, so 8 seems
	*  like a safe limit.  If we run out of iterations here, just
	*  go back and start over from gen_solved_*(), above.
	*/
       for (i=8;i>=0;i--)
	{ solver_setup(&s,dp,net);
	  solver_run(&s);
#ifdef HEXNET_VERBOSE_UNIQ
	  printf("checking uniq, nsoln = %d\n",s.nsoln);
#endif
	  if (s.nsoln == 1) break;
	  if (s.nsoln == 0) abort();
	  randomize_ambiguous(&s,net,rs);
	  solver_teardown(&s);
	}
       if (i < 0) continue;
     }
    break;
  }
 for (i=dp->asz2-1;i>=0;i--)
  { if (net[i] & (UNUSED|DUP)) continue;
    net[i] = rot[net[i]][random_upto(rs,6)];
  }
 desc = smalloc(dp->hszg+1);
 j = 0;
 for (i=0;i<dp->asz2;i++)
  { if (net[i] & (UNUSED|DUP)) continue;
    if (j >= dp->hszg) abort();
#if LINK_M != 63
#error "Game encoding doesn't work for this value of LINK_M"
#endif
    desc[j++] = b64chars[(net[i]>>LINK_S)&LINK_M];
  }
 if (j != dp->hszg) abort();
 desc[j++] = '\0';
 return(desc);
}

/*
 * Solve a game.
 */
static char *solve_game(const STATE *state, const STATE *curstate,
                        const char *aux, const char **error)
{
 SOLVER s;
 int i;
 int j;
 int n;
 char *sm;

 (void)curstate;
 (void)aux;
 /*
  * Trivial check: make sure total link count is right.  The total link
  *  count in a connected tree with N nodes is N-1.  But we're counting
  *  each end of each link separately, so the number we want is 2(N-1).
  */
 n = 0;
 for (i=state->d->asz2-1;i>=0;i--)
  { for (j=6-1;j>=0;j--)
     { if ((state->net[i] >> (LINK_S + j)) & 1) n ++;
     }
  }
 if (n != 2*(state->d->hszg-1))
  { printf("solver: no soln, n=%d hsgz=%d\n",n,state->d->hszg);
    *error = "Obviously no solution - link count wrong";
    return(0);
  }
#ifdef HEXNET_VERBOSE_SOLVE
 printf("solve called\n");
 printf("initial state:\n");
 dump_cells(state->d,state->net,LINK_BASE);
#endif
 solver_setup(&s,state->d,state->net);
 solver_run(&s);
#ifdef HEXNET_VERBOSE_SOLVE
 printf("soln count = %d\n",s.nsoln);
 printf("ans =");
 for (i=0;i<state->d->asz2;i++)
  { if (s.pos[i] == POS_UNUSED)
     { printf("  -");
     }
    else if (s.ans[i] == ANS_AMBIGUOUS)
     { printf(" ??");
     }
    else
     { printf("  %d",s.ans[i]);
     }
  }
 printf("\n");
#endif
 if (s.nsoln < 1)
  { *error = "No solutions found";
    sm = 0;
  }
 else
  { sm = snewn(1+state->d->hszg+1,char);
    j = 0;
    sm[j++] = 'S';
    for (i=0;i<state->d->asz2;i++)
     { if (s.pos[i] == POS_UNUSED) continue;
       if (s.ans[i] == ANS_AMBIGUOUS)
	{ sm[j++] = '.';
	}
       else
	{ sm[j++] = b64chars[rot[(state->net[i]>>LINK_S)&LINK_M][s.ans[i]]];
	}
     }
    if (j != state->d->hszg+1) abort();
    sm[j] = '\0';
  }
 solver_teardown(&s);
 return(sm);
}

/*
 * Formatting as text is not yet implemented.
 */
static bool can_format_as_text_now(const PARAMS *p)
{
 (void)p;
 return(false);
}

/*
 * Formatting as text is not yet implemented.
 */
static char *text_format(const STATE *s)
{
 (void)s;
 return(0);
}

/*
 * Create a new UI for a given STATE.
 */
static UI *new_ui(const STATE *s)
{
 UI *u;
 int i;

 u = snew(UI);
 u->light = 2 * s->d->p.size * (s->d->p.size - 1);
 u->lighton = 1;
 u->dispmap = snewn(s->d->asz2,int);
 u->dispimap = snewn(s->d->asz2,int);
 u->mismatch = snewn(s->d->asz2+1,unsigned char);
 bzero(u->mismatch,s->d->asz2+1);
 for (i=s->d->asz2-1;i>=0;i--)
  { if (s->d->flags[i] & (s->d->p.wrap ? FCF_UNUSED|FCF_DUP : FCF_UNUSED))
     { u->dispmap[i] = -1;
       u->dispimap[i] = -1;
     }
    else
     { u->dispmap[i] = i;
       u->dispimap[i] = i;
     }
  }
 return(u);
}

/*
 * Free a UI.
 */
static void free_ui(UI *u)
{
 sfree(u->dispmap);
 sfree(u->dispimap);
 sfree(u);
}

/*
 * Encode a UI as a string.  We don't have anything in the UI that's
 *  important enough to bother saving.
 *
 * XXX Is this actually true?  Maybe light and lighton?  Scrolling
 *  state?
 */
static char *encode_ui(const UI *u)
{
 (void)u;
 return(dupstr(""));
}

/*
 * Inverses of encode_ui(), qv.
 */
static void decode_ui(UI *u, const char *enc)
{
 (void)u;
 (void)enc;
}

/*
 * Our changed_state method.  We have nothing to do here.
 */
static void changed_state(UI *u, const STATE *old, const STATE *new)
{
 (void)u;
 (void)old;
 (void)new;
}

/*
 * Return the grid X (_cx_) and Y (_cy_) coordinates for a pixel (X,Y)
 *  location.
 *
 * Because if the way they're used by tile_for_loc, below, it's
 *  important that cell_c[xy]_xy work for out-of-range x and y,
 *  returning what the coordinates would be if the grid were extended
 *  far enough to cover the (x,y) passed in.
 *
 * This is also why we return X and Y coordinates rather than a
 *  single-index value; the single-index representation has no way to
 *  represent cells outside the grid in general.
 */

static int cell_cx_xy(const DRAWSTATE *ds, int x, int y)
{
 return((ds->w / 2) + ((((x - (ds->d->p.size - 1)) * 2) + y - (ds->d->p.size - 1)) * ds->hexr3));
}

static int cell_cy_xy(const DRAWSTATE *ds, int x, int y)
{
 (void)x;
 return((ds->h / 2) + ((y - (ds->d->p.size - 1)) * 3 * ds->hexsize));
}

/*
 * Convert a pixel X coordinate to a grid X coordinate, assuming it
 *  belongs to the row of hexagons with grid Y coordinate y.  It is
 *  important that this return an out-of-range grid coordinate (<0 or
 *  >=ds->asz) for out-of-range input coordinates, though it is not
 *  important to draw further distinctions between different
 *  out-of-range cells.
 */
static int cellx_for_pixx(const DRAWSTATE *ds, int x, int y)
{
 // Make x relative to the x=0 left edge for this row.
 x -= cell_cx_xy(ds,0,y) - ds->hexr3;
 // If x is negative, outside the allocated grid.
 if (x < 0) return(-1);
 // Convert x from pixels to grid index and return.
 return(x/(2*ds->hexr3));
}

/*
 * Return the square of the distance between (x1,y1) and (x2,y2).  We
 *  use this to tell which of two points is closer to a third point
 *  (eg, which of two cell centres is closer to a clicked-on pixel), so
 *  all that really matters is that this is strictly monotonic in the
 *  distance between the points.  This is why we can return the square
 *  of the distance, thereby saving ourselves a comparatively expensive
 *  square-root computation.
 */
static int id2(int x1, int y1, int x2, int y2)
{
 return(((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)));
}

/*
 * Return the index of the tile pixel (px,py) falls into.
 *
 * This is the tile (in the infinite grid of which the game board is a
 *  part) whose centre is closest to (px,py), except that if that tile
 *  isn't part of the actual game board, we return -1 instead.  This
 *  returns display cell numbers even when wrapping is enabled.
 *
 * If y is close enough to a hexagon row's centreline that every point
 *  with that y coordinate falls into that line of hexagons, it's easy.
 *  Otherwise, we compute the closest point in the band above and the
 *  band below, then check to see which one is closer to (px,py).
 */
static int tile_for_loc(const DRAWSTATE *ds, int px, int py)
{
 int x;
 int y;
 int xa;
 int xb;
 int cxa;
 int cya;
 int cxb;
 int cyb;

 // Make y relative to the top of the `easy' band for the (nonexistent)
 //  row just above the grid.
 y = py + (((ds->d->p.size * 3) + 1) * ds->hexsize) - (ds->h / 2);
 // If y is now negative, definitely off-grid.
 if (y < 0) return(-1);
 // Do we fall into an easy band?
 if ((y % (3 * ds->hexsize)) < (2 * ds->hexsize))
  { // Yes.
    y /= 3 * ds->hexsize;
    // Because of the offset, valid is 1..ds->asz.
    if ((y < 1) || (y > ds->d->asz)) return(-1);
    // Compensate for the offset.
    y --;
    // Convert x to cell index.
    x = cellx_for_pixx(ds,px,y);
    // unused_xy() range-checks as well as testing for unused cells.
    if (unused_xy(ds->d,x,y,1)) return(-1);
    // All good!
    return(ds->d->xyi[x][y]);
  }
 // No easy band.  Compute the y of the upper possible band.
 y /= 3 * ds->hexsize;
 // Compensate for the offset, same as above.
 y --;
 // If the _upper_ band is off the bottom edge, off-grid.
 if (y >= ds->d->asz) return(-1);
 // Get grid X coordinates for above and below.
 xa = cellx_for_pixx(ds,px,y);
 xb = cellx_for_pixx(ds,px,y+1);
 // Get pixel coordinates of cell centres.
 cxa = cell_cx_xy(ds,xa,y);
 cya = cell_cy_xy(ds,xa,y);
 cxb = cell_cx_xy(ds,xb,y+1);
 cyb = cell_cy_xy(ds,xb,y+1);
 // Which is closer?
 if (id2(cxa,cya,px,py) < id2(cxb,cyb,px,py))
  { x = xa;
  }
 else
  { x = xb;
    y ++;
  }
 // Return -1 if out of range, else the index.
 if (unused_xy(ds->d,x,y,1)) return(-1);
 return(ds->d->xyi[x][y]);
}

/*
 * Scroll the display.  We do this by updating the permutations in
 *  dispmap and dispimap.
 *
 * We use dispimap's memory as a temporary, here, regenerating it by
 *  inverting dispmap once we're done.
 */
static void scroll_dispmap(const DRAWSTATE *ds, UI *u, int dir)
{
 int i;
 int *tmp;
 int j;

 if ((dir < 0) || (dir > 5) || !ds->d->p.wrap) abort();
 tmp = u->dispimap;
 for (i=ds->d->asz2-1;i>=0;i--)
  { tmp[i] = (u->dispmap[i] < 0) ? -1 : connect_to(ds->d,u->dispmap[i],dir,0);
  }
 bcopy(tmp,u->dispmap,ds->d->asz2*sizeof(int));
 for (i=ds->d->asz2-1;i>=0;i--) u->dispimap[i] = -1;
 for (i=ds->d->asz2-1;i>=0;i--)
  { j = u->dispmap[i];
    if (j < 0) continue;
    if (j >= ds->d->asz2) abort();
    if (u->dispimap[j] >= 0) abort();
    u->dispimap[j] = i;
  }
 for (i=ds->d->asz2-1;i>=0;i--)
  { if ( ((u->dispmap[i] < 0) && (u->dispimap[i] >= 0)) ||
	 ((u->dispmap[i] >= 0) && (u->dispimap[i] < 0)) ) abort();
  }
}

/*
 * Our interpret_move method.  This takes a UI gesture (in the form of
 *  button, x, and y) and returns a string representation of the move
 *  for use by execute_move().
 *
 * Our UI gestures:
 *
 *	Left click: rotate cell left
 *	Middle click: toggle cell lock
 *	Right click: rotate cell right
 *	Letter d, e, w, a, z, x: these form an approximate hex
 *	  direction pad around the s key.
 *	  With no modifiers, these do nothing.
 *	  With control: they move the light-origin cell.
 *	  With shift: they scroll the game board, if wrapping.
 *	s, with control: toggle lighting-up of cells connected to the
 *	  light-origin cell.
 *
 * The mouse-click actions are moves in the sense of returning
 *  something to be passed execute_move() and go on the undo/redo
 *  chain.  The letter gestures all are UI-only actions, returning
 *  UI_UPDATE.
 */
static char *interpret_move(
	const STATE *s,
	UI *u,
	const DRAWSTATE *ds,
	int x, int y,
	int button		)
{
 int tx;
 char *m;
 int mods;

 mods = button & MOD_MASK;
 button &= ~MOD_MASK;
 switch (button)
  { case LEFT_BUTTON:
    case MIDDLE_BUTTON:
    case RIGHT_BUTTON:
       tx = tile_for_loc(ds,x,y);
       if (tx < 0) return(0);
       if (tx >= ds->d->asz2) abort();
       tx = s->d->dupof[tx];
       if ((tx < 0) || (tx >= ds->d->asz2)) abort();
       tx = u->dispmap[tx];
       if ((tx < 0) || (tx >= ds->d->asz2)) abort();
       break;
  }
 m = 0;
 switch (button)
  { case MIDDLE_BUTTON:
       asprintf(&m,".%d",tx);
       m[0] = (s->net[tx] & LOCKED) ? 'U' : 'L';
       break;
    case LEFT_BUTTON:
	{ char rotch;
	  rotch = 'l';
	  if (0)
	   {
    case RIGHT_BUTTON:
	     rotch = 'r';
	   }
	  if (s->net[tx] & LOCKED) return(0);
	  asprintf(&m,"%c%d",rotch,tx);
	}
       break;
	{ int dir;
    case 'd': dir = 0;   if (0) {
    case 'e': dir = 1; } if (0) {
    case 'w': dir = 2; } if (0) {
    case 'a': dir = 3; } if (0) {
    case 'z': dir = 4; } if (0) {
    case 'x': dir = 5; }
	  if (mods & MOD_CTRL)
	   { int new;
	     new = connect_to(ds->d,u->light,dir,0);
	     if (new < 0) return(0);
	     u->light = new;
	     return(UI_UPDATE);
	   }
	  if ((mods & MOD_SHFT) && ds->d->p.wrap)
	   { scroll_dispmap(ds,u,dir);
	     return(UI_UPDATE);
	   }
	}
       break;
    case 's':
       if (mods & MOD_CTRL)
	{ u->lighton = ! u->lighton;
	  return(UI_UPDATE);
	}
       break;
    default:
       return(0);
       break;
  }
 return(m);
}

/*
 * Find any error half-links.  See the description of the ERR_ bits in
 *  the data structure comments above for more.
 */
static void find_err(STATE *s)
{
 int inx;
 int i;
 int to;

 for (inx=s->d->asz2-1;inx>=0;inx--) s->net[inx] &= ~ERR_ALL;
 for (inx=s->d->asz2-1;inx>=0;inx--)
  { if ((s->net[inx] & (UNUSED|DUP|LOCKED)) != LOCKED) continue;
    for (i=5;i>=0;i--)
     { if ((s->net[inx] >> i) & LINK_BASE)
	{ to = connect_to(s->d,inx,i,0);
	  if ((to < 0) || ((s->net[to] & LOCKED) && ! ((s->net[to] >> otherway(i)) & 1)))
	   { s->net[inx] |= ERR_BASE << i;
	   }
	}
     }
  }
}

/*
 * Check to see whether the game is solved.  We do this by doing a
 *  simple graph walk from an arbitrary cell (the leftmost on the top
 *  row, as it happens) and seeing whether we reach all the cells.
 */
static void check_solved(STATE *s)
{
 static CDQ q = CDQ_STATIC_INIT;
 int x;
 int i;
 int x2;
 int n;

 for (i=s->d->asz2-1;i>=0;i--) s->net[i] &= ~MARK;
 n = 0;
 if (cdq_n(&q) != 0) abort();
 cdq_add(&q,(CDQE){.x=s->d->p.size-1,.dir=0});
 while (cdq_n(&q) > 0)
  { x = cdq_get(&q,0).x;
    if (s->net[x] & MARK) continue;
    s->net[x] |= MARK;
    n ++;
    for (i=5;i>=0;i--)
     { if ((s->net[x] >> i) & LINK_BASE)
	{ x2 = connect_to(s->d,x,i,0);
	  if ( (x2 >= 0) &&
	       ((s->net[x2] >> otherway(i)) & LINK_BASE) )
	   { cdq_add(&q,(CDQE){.x=x2,.dir=0});
	   }
	}
     }
  }
 if (n == s->d->hszg) s->flags |= SF_SOLVED; else s->flags &= ~SF_SOLVED;
 for (i=s->d->asz2-1;i>=0;i--) s->net[i] &= ~MARK;
}

/*
 * Execute a move: given the string representation of a move, chop its
 *  head o^W^W^W^Wperform it, taking a STATE and returning a new STATE.
 *
 * Note that redraw() also knows how lastrot_loc and lastrot_dir work.
 */
static STATE *execute_move(const STATE *s, const char *move)
{
 STATE *n;
 int inx;
 int n1;
 int n2;
 char c;

 n = dup_game(s);
 n1 = -1;
 n2 = -1;
 switch (move[0])
  { case 'L':
       sscanf(move+1,"%d%n%c%n",&inx,&n1,&c,&n2);
       if ((n1 < 0) || (n2 >= 0) || (inx < 0) || (inx >= s->d->asz2) || (n->net[inx] & (UNUSED|DUP))) abort();
       n->net[inx] |= LOCKED;
       n->lastrot_loc = -1;
       find_err(n);
       break;
    case 'U':
       sscanf(move+1,"%d%n%c%n",&inx,&n1,&c,&n2);
       if ((n1 < 0) || (n2 >= 0) || (inx < 0) || (inx >= s->d->asz2) || (n->net[inx] & (UNUSED|DUP))) abort();
       n->net[inx] &= ~LOCKED;
       n->lastrot_loc = -1;
       find_err(n);
       break;
    case 'r':
       sscanf(move+1,"%d%n%c%n",&inx,&n1,&c,&n2);
       if ((n1 < 0) || (n2 >= 0) || (inx < 0) || (inx >= s->d->asz2) || (n->net[inx] & (UNUSED|DUP|LOCKED))) abort();
       n->net[inx] = ROT_R((n->net[inx]>>LINK_S)&LINK_M);
       n->lastrot_loc = inx;
       n->lastrot_dir = 1;
       find_loops(n);
       check_solved(n);
       break;
    case 'l':
       sscanf(move+1,"%d%n%c%n",&inx,&n1,&c,&n2);
       if ((n1 < 0) || (n2 >= 0) || (inx < 0) || (inx >= s->d->asz2) || (n->net[inx] & (UNUSED|DUP|LOCKED))) abort();
       n->net[inx] = ROT_L((n->net[inx]>>LINK_S)&LINK_M);
       n->lastrot_loc = inx;
       n->lastrot_dir = -1;
       find_loops(n);
       check_solved(n);
       break;
    case 'S':
	{ int i;
	  int j;
	  int x;
	  char *b64;
	  x = 1;
	  for (i=0;i<s->d->asz2;i++)
	   { if (s->d->flags[i] & (FCF_UNUSED|FCF_DUP)) continue;
	     c = move[x++];
	     if (! c) abort();
	     if (c == '.')
	      { n->net[i] &= ~LOCKED;
	      }
	     else
	      { b64 = index(&b64chars[0],c);
		if (! b64) abort();
		j = b64 - &b64chars[0];
		if (j > 63) // can this happen?
		 { i --;
		   continue;
		 }
		n->net[i] = j | LOCKED;
	      }
	   }
	  n->lastrot_loc = -1;
	  find_err(n);
	  find_loops(n);
	  check_solved(n);
	}
       break;
    default:
       abort();
       break;
  }
 return(n);
}

// ----------------------------------------------------------------------
// Drawing routines.

/*
 * Compute the pixel size we want for a given PARAMS and tilesize.
 *
 * In pixel terms, the board is not quite square.  Asymptotically, its
 *  aspect ratio tends to 4*sqrt(3) in X by 6 in Y.  This makes it
 *  bigger in X by the ratio by which sqrt(3) exceeds 1.5, which is a
 *  little under 15.5%.  But for any real game, this is not quite
 *  accurate, both because of BORDER_PIXELS and because the board
 *  hexagon is made up of smaller hexagons, not circles.
 *
 * Our computation of hexr3 must exactly match set_size()'s, or the
 *  size we get won't be quite what we want.
 *
 * We convert hexr3 to an integer before computing sizes based on it,
 *  so that all hexagons are exactly the same size; I consider it
 *  better to have each hexagon exactly the same size than to have the
 *  mean size closer to exact but individual hexagons not quite all the
 *  same size.
 *
 * The +1 on each coordinate is because otherwise the last pixel falls
 *  just outside, rather than just inside, the size.  This makes
 *  BORDER_PIXELS not quite equal to the number of blank pixels.
 */
static void compute_size(const PARAMS *p, int tilesize, int *x, int *y)
{
 int hexr3;

 hexr3 = (tilesize * ROOT_3) + .5;
 *x = (((2 * p->size) - 1) * 2 * hexr3) + (2 * BORDER_PIXELS) + 1;
 *y = (((3 * p->size) - 1) * 2 * tilesize) + (2 * BORDER_PIXELS) + 1;
}

/*
 * Utility used by set_size() to set up lineoff[][].
 */
static void rotate_points(const IXY *src, IXY *dst, int npts, double xx, double xy, double yx, double yy)
{
 for (;npts>0;npts--)
  { dst->x = rint((src->x * xx) + (src->y * yx));
    dst->y = rint((src->x * xy) + (src->y * yy));
    src ++;
    dst ++;
  }
}

/*
 * Set up to operate at a given tilesize.
 *
 * Note that our computation of hexr3 must exactly match
 *  compute_size()'s.
 *
 * lineoff is set up here to simplify redraw()'s drawing of lines.
 *  Without this, we'd have to do approximately what rotate_points()
 *  does all over the place when drawing links in redraw().  With this,
 *  we just need to subscript and add.
 *
 * For good appearance, it is important that nepcr >= (linew2*2)+1, so
 *  that the circle at a cell's centre covers any possible ugly angles
 *  from link endpoints.
 */
static void set_size(DRAWING *dr, DRAWSTATE *ds, const PARAMS *p, int tilesize)
{
 int rn;

 (void)dr;
 (void)p;
 ds->hexsize = tilesize;
 ds->hexr3 = (tilesize * ROOT_3) + .5;
 ds->linew2 = tilesize / 10;
 ds->epcr = (tilesize * 2) / 3;
 ds->nepcr = tilesize / 3;
 ds->litcr = tilesize;
 compute_size(p,tilesize,&ds->w,&ds->h);
 if (ds->linew2 < 1)
  { ds->lineoff[0][0].x = ds->hexr3 - 1;
    ds->lineoff[0][0].y = 0;
    rn = 1;
  }
 else
  { /*
     * Drawing bidirectional lines, in redraw(), that knows that the
     *	[2] and [3] points are the ones at the centre end.
     */
    ds->lineoff[0][0].x = ds->hexr3 - 1;
    ds->lineoff[0][0].y = ds->linew2;
    ds->lineoff[0][1].x = ds->lineoff[0][0].x;
    ds->lineoff[0][1].y = - ds->lineoff[0][0].y;
    ds->lineoff[0][2].x = 0;
    ds->lineoff[0][2].y = ds->lineoff[0][1].y;
    ds->lineoff[0][3].x = 0;
    ds->lineoff[0][3].y = ds->lineoff[0][0].y;
    rn = 4;
  }
 rotate_points(&ds->lineoff[0][0],&ds->lineoff[1][0],rn,.5,-ROOT_3/2,ROOT_3/2,.5);
 rotate_points(&ds->lineoff[0][0],&ds->lineoff[2][0],rn,-.5,-ROOT_3/2,ROOT_3/2,-.5);
 rotate_points(&ds->lineoff[0][0],&ds->lineoff[3][0],rn,-1,0,0,-1);
 rotate_points(&ds->lineoff[0][0],&ds->lineoff[4][0],rn,-.5,ROOT_3/2,-ROOT_3/2,-.5);
 rotate_points(&ds->lineoff[0][0],&ds->lineoff[5][0],rn,.5,ROOT_3/2,-ROOT_3/2,.5);
}

/*
 * Request colours.
 */
static float *colours(frontend *fe, int *ncolours)
{
 float *cv;

 cv = snewn(NCOLOURS*3,float);
 *ncolours = NCOLOURS;
#define SET(inx,r,g,b) \
	do {					\
		cv[((inx)*3)+0] = (r);		\
		cv[((inx)*3)+1] = (g);		\
		cv[((inx)*3)+2] = (b);		\
	} while (0)
 // Background is black.
 SET(COL_BACKGROUND,0,0,0);
 // (Unpowered) wires are blue.
 SET(COL_WIRE,0,.5,1);
 // Powered wires/endpoints are white.
 SET(COL_POWERED,1,1,1);
 // Errors are red.
 SET(COL_ERR,1,0,0);
 // Loops are same as unpowered, but with some red.
 SET(COL_LOOP,.75,.5,1);
 // Unpowered endpoints are grey.
 SET(COL_ENDPOINT,.6,.6,.6);
 // Tile borders are a darker grey.
 SET(COL_BORDER,.4,.4,.4);
 // Locked-tile backgrounds are brown (dim yellow).
 SET(COL_LOCKED,.2,.2,0);
 // The surrounding barrier is red.
 SET(COL_BARRIER,1,0,0);
 // Wrap-indicating background is a dim cyan
 SET(COL_BGWRAP,0,.2,.2);
 // A cross between COL_LOCKED and COL_BGWRAP.
 SET(COL_LOCKWRAP,.2,.3,.2);
 // Locked, but mismatching solution.
 SET(COL_ERRBG,.4,.2,0);
 // Locked, wrapped, but mismatching solution.
 SET(COL_ERRBGWRAP,.4,.3,.2);
#undef SET
 (void)fe;
 return(cv);
}

/*
 * Create a new DRAWSTATE for a given DRAWING and STATE.
 */
static DRAWSTATE *new_drawstate(DRAWING *dr, const STATE *s)
{
 DRAWSTATE *ds;

 ds = snew(DRAWSTATE);
 (void)dr;
 (void)s;
 ds->d = dpar_ref(s->d);
 ds->first = 1;
 ds->hexsize = 0;
 ds->hexr3 = 0;
 ds->animloc = -1;
 ds->live = smalloc(ds->d->asz2*sizeof(*ds->live));
 ds->cur = smalloc(ds->d->asz2*sizeof(*ds->cur));
 ds->want = smalloc(ds->d->asz2*sizeof(*ds->want));
 ds->curlight = -1;
 ds->lastflash = -1;
 ds->flashing = 0;
 return(ds);
}

/*
 * Free up a DRAWSTATE.
 */
static void free_drawstate(DRAWING *dr, DRAWSTATE *ds)
{
 (void)dr;
 sfree(ds->live);
 sfree(ds->cur);
 sfree(ds->want);
 dpar_deref(ds->d);
 sfree(ds);
}

/*
 * Find the lit cells in a DRAWSTATE's live-cells array.  light is the
 *  source-of-light cell index.  This sets LIT on the appropriate cells
 *  in the DRAWSTATE's live[] array.
 */
static void find_lit(DRAWSTATE *ds, int light)
{
 static CDQ q = CDQ_STATIC_INIT;
 int x;
 int i;
 int x2;
 int n;

 n = 0;
 if (cdq_n(&q) != 0) abort();
 cdq_add(&q,(CDQE){.x=light,.dir=0});
 while (cdq_n(&q) > 0)
  { x = cdq_get(&q,0).x;
    if (ds->live[x] & LIT) continue;
    ds->live[x] |= LIT;
    n ++;
    for (i=5;i>=0;i--)
     { if ((ds->live[x] >> i) & LINK_BASE)
	{ x2 = connect_to(ds->d,x,i,0);
	  if ( (x2 >= 0) &&
	       ((ds->live[x2] >> otherway(i)) & LINK_BASE) )
	   { cdq_add(&q,(CDQE){.x=x2,.dir=0});
	   }
	}
     }
  }
}

/*
 * Set up for a draw_polygon() call for a cell's hexagon.  This is
 *  factored out because it's used multiple times in redraw().
 */
static void load_hexagon(int *phex, const DRAWSTATE *ds, int cx, int cy)
{
 phex[0] = cx;
 phex[1] = cy - (2 * ds->hexsize);
 phex[2] = cx + ds->hexr3;
 phex[3] = cy - ds->hexsize;
 phex[4] = cx + ds->hexr3;
 phex[5] = cy + ds->hexsize;
 phex[6] = cx;
 phex[7] = cy + (2 * ds->hexsize);
 phex[8] = cx - ds->hexr3;
 phex[9] = cy + ds->hexsize;
 phex[10] = cx - ds->hexr3;
 phex[11] = cy - ds->hexsize;
}

/*
 * Set up for a draw_polygon() call for one cell's portion of the
 *  wrap-mark highlight.  cx and cy are the centre of the cell; cf is
 *  one of the FCF_WRAP values, indicating which portions of the cell
 *  to draw.  Return value is the number of points to draw, always
 *  either 5 or 7.
 */
static int load_wrap_region(int *pvec, const DRAWSTATE *ds, int cx, int cy, unsigned char cf)
{
 int x;

#define STORE(dx,dy) do { pvec[x++] = cx + (dx); pvec[x++] = cy + (dy); } while (0)
 x = 0;
 switch (cf)
  { case FCF_WRAP_0:
       STORE(0,0);
       STORE(-ds->hexr3/2,-(3*ds->hexsize)/2);
       STORE(0,-2*ds->hexsize);
       STORE(ds->hexr3,-ds->hexsize);
       STORE(ds->hexr3,ds->hexsize);
       STORE(0,2*ds->hexsize);
       STORE(-ds->hexr3/2,(3*ds->hexsize)/2);
       return(7);
       break;
    case FCF_WRAP_01:
       STORE(-ds->hexr3/2,-(3*ds->hexsize)/2);
       STORE(0,-2*ds->hexsize);
       STORE(ds->hexr3,-ds->hexsize);
       STORE(ds->hexr3,ds->hexsize);
       STORE(ds->hexr3/2,(3*ds->hexsize)/2);
       return(5);
       break;
    case FCF_WRAP_1:
       STORE(0,0);
       STORE(-ds->hexr3,0);
       STORE(-ds->hexr3,-ds->hexsize);
       STORE(0,-2*ds->hexsize);
       STORE(ds->hexr3,-ds->hexsize);
       STORE(ds->hexr3,ds->hexsize);
       STORE(ds->hexr3/2,(3*ds->hexsize)/2);
       return(7);
       break;
    case FCF_WRAP_12:
       STORE(-ds->hexr3,0);
       STORE(-ds->hexr3,-ds->hexsize);
       STORE(0,-2*ds->hexsize);
       STORE(ds->hexr3,-ds->hexsize);
       STORE(ds->hexr3,0);
       return(5);
       break;
    case FCF_WRAP_2:
       STORE(0,0);
       STORE(-ds->hexr3/2,(3*ds->hexsize)/2);
       STORE(-ds->hexr3,ds->hexsize);
       STORE(-ds->hexr3,-ds->hexsize);
       STORE(0,-2*ds->hexsize);
       STORE(ds->hexr3,-ds->hexsize);
       STORE(ds->hexr3,0);
       return(7);
       break;
    case FCF_WRAP_23:
       STORE(-ds->hexr3/2,(3*ds->hexsize)/2);
       STORE(-ds->hexr3,ds->hexsize);
       STORE(-ds->hexr3,-ds->hexsize);
       STORE(0,-2*ds->hexsize);
       STORE(ds->hexr3/2,-(3*ds->hexsize)/2);
       return(5);
       break;
    case FCF_WRAP_3:
       STORE(0,0);
       STORE(ds->hexr3/2,(3*ds->hexsize)/2);
       STORE(0,2*ds->hexsize);
       STORE(-ds->hexr3,ds->hexsize);
       STORE(-ds->hexr3,-ds->hexsize);
       STORE(0,-2*ds->hexsize);
       STORE(ds->hexr3/2,-(3*ds->hexsize)/2);
       return(7);
       break;
    case FCF_WRAP_34:
       STORE(ds->hexr3/2,(3*ds->hexsize)/2);
       STORE(0,2*ds->hexsize);
       STORE(-ds->hexr3,ds->hexsize);
       STORE(-ds->hexr3,-ds->hexsize);
       STORE(-ds->hexr3/2,-(3*ds->hexsize)/2);
       return(5);
       break;
    case FCF_WRAP_4:
       STORE(0,0);
       STORE(ds->hexr3,0);
       STORE(ds->hexr3,ds->hexsize);
       STORE(0,2*ds->hexsize);
       STORE(-ds->hexr3,ds->hexsize);
       STORE(-ds->hexr3,-ds->hexsize);
       STORE(-ds->hexr3/2,-(3*ds->hexsize)/2);
       return(7);
       break;
    case FCF_WRAP_45:
       STORE(ds->hexr3,0);
       STORE(ds->hexr3,ds->hexsize);
       STORE(0,2*ds->hexsize);
       STORE(-ds->hexr3,ds->hexsize);
       STORE(-ds->hexr3,0);
       return(5);
       break;
    case FCF_WRAP_5:
       STORE(0,0);
       STORE(ds->hexr3/2,-(3*ds->hexsize)/2);
       STORE(ds->hexr3,-ds->hexsize);
       STORE(ds->hexr3,ds->hexsize);
       STORE(0,2*ds->hexsize);
       STORE(-ds->hexr3,ds->hexsize);
       STORE(-ds->hexr3,0);
       return(7);
       break;
    case FCF_WRAP_50:
       STORE(ds->hexr3/2,-(3*ds->hexsize)/2);
       STORE(ds->hexr3,-ds->hexsize);
       STORE(ds->hexr3,ds->hexsize);
       STORE(0,2*ds->hexsize);
       STORE(-ds->hexr3/2,(3*ds->hexsize)/2);
       return(5);
       break;
  }
 abort();
}

/*
 * Initialize an UPDRECT.  We get suitable values from the size in the
 *  DRAWSTATE.
 */
static void updr_init(UPDRECT *ur, const DRAWSTATE *ds)
{
 ur->minx = ds->w;
 ur->maxx = 0;
 ur->miny = ds->h;
 ur->maxy = 0;
}

/*
 * Add a bounding-box rectangle to an UPDRECT.  (The bounding box
 *  doesn't have to be tight, but it helps speed if it is, or at least
 *  close to.)
 */
static void updr_add(UPDRECT *ur, int x, int y, int w, int h)
{
 if (x < ur->minx) ur->minx = x;
 if (y < ur->miny) ur->miny = y;
 x += w;
 if (x > ur->maxx) ur->maxx = x;
 y += h;
 if (y > ur->maxy) ur->maxy = y;
}

/*
 * Make the draw_update() call for the rectangle accumulated in an
 *  UPDRECT.
 */
static void updr_draw_update(UPDRECT *ur, DRAWING *dr)
{
 draw_update(dr,ur->minx,ur->miny,ur->maxx-ur->minx,ur->maxy-ur->miny);
}

/*
 * Redraw the game board.
 *
 * In order to get all the occlusion correct, we order our drawing very
 *  carefully.
 *
 * First we determine which cells we want to draw.  This includes:
 *  1) Cells which have changed.
 *  2) The cell being animated, if any.
 *  3) The cell we just stopped animating, if any.
 *  4) The current and former light source cells, if they differ.
 *  5) Certain cells which share a bidirectional link with a cell in
 *     classes 1, 3, or 4.
 *
 * The reason for (5) is that we want to draw such a link as a single
 *  polygon (or, if thin, line) so as to avoid a glitch at the cell
 *  boundary due to coordinate rounding.  But we don't want to do this
 *  always, or we have the same problem if the adjacent cell has a
 *  second bidirectional link - we end up redrawing the whole connected
 *  subgraph, which is way more than we need to, or we end up not
 *  redrawing some links correctly.  We redraw the adjacent cell only
 *  when not doing so would produce a visible glitch.  This means, when
 *  (a) the adjacent cell is an endpoint (because otherwise the link
 *  would intrude into the large circle) or when (b) it's the light
 *  source cell (because otherwise we'd overdraw part of the light
 *  circle with the link).
 *
 * We draw things in this order, where a cell being animated is never
 *  considered to participate in bidirectional links:
 *  1) Cell backgrounds.
 *  2) Bidirectional links.
 *  3) Unidirectional links.
 *  4) Cell-centre circles.
 *  5) Grid hexagons.
 *
 * For each of the items in the list above, we draw that thing for all
 *  cells being redrawn before going on to the next thing.  This is
 *  semi-necessary to make occlusion work right.  To avoid flicker,
 *  though, we want to do _one_ draw_update call, at the end, covering
 *  all cells which got redrawn, rather than doing them as we go.
 */
static void redraw(
	DRAWING *dr,
	DRAWSTATE *ds,
	const STATE *old,
	const STATE *new,
	int dir,
	const UI *u,
	float animtime,
	float flashtime		)
{
 DPAR *d;
 int i;
 int ii;
 int j;
 int k;
 int cx;
 int cy;
 int x;
 int y;
 int kx;
 int ky;
 int oj;
 int phex[14];
 int pwire[8];
 int px;
 int l;
 int col;
 int rotloc;
 double rotang;
 double racos;
 double rasin;
 UPDRECT upd;
 int lighton;
 int drl;
 int dal;
 int dl;

 d = ds->d;
 // If we're animating a rotation, set up variables for it.
 if (!old || !dir)
  { // Not animating.
    rotloc = -1;
  }
 else
  { /*
     * Animating.  animtime runs from 0 to ROTATE_TIME here.  old is
     *	the former state, new is the state we're moving to.  That would
     *	be all we'd need, except that we want to do the move specified.
     *	For example, if we have a 0x15 piece being changed into a 0x2a
     *	piece, we have to rotate it the way the user expects, and we
     *	can't tell that just from 0x15 and 0x2a.  So execute_move sets
     *	lastrot_loc and lastrot_dir when it does rotations.  Undo and
     *	redo are done by saving states and moving between them, not by
     *	re-executing moves.  This means that, when animating an undo,
     *	we have to animate by reversing the move in the old state
     *	rather than performing the move in the new state, whereas for a
     *	move or redo, we have to do the obvious thing and perform the
     *	move in the new state.
     *
     * Also, we have to be careful that animtime=0 corresponds to old
     *	and animtime=ROTATE_TIME to new, visually, even though our base
     *	position is always the new one.  This is why rotang is
     *	sometimes negative below.
     *
     * Our execute_move() uses lastrot_dir=1 for rotates right,
     *	lastrot_dir=-1 for rotates left.  And we're in fourth quadrant,
     *	not first quadrant.  So we have to be very careful about
     *	angular directions here.
     *
     * We do not always get a final animation call with
     *	animtime==ROTATE_TIME.  We get a final call, but it's a
     *	non-animating call.  Making sure we finish the rotation is what
     *	ds->animloc is for.
     */
    if (dir > 0)
     { // Move or redo.
       rotloc = new->lastrot_loc;
       rotang = - new->lastrot_dir * M_PI / 3;
     }
    else
     { // Undo.
       rotloc = old->lastrot_loc;
       rotang = old->lastrot_dir * M_PI / 3;
     }
    rotang *= (ROTATE_TIME - animtime) / ROTATE_TIME;
    racos = cos(rotang);
    rasin = sin(rotang);
  }
 /*
  * We implement flashing by, effectively, blinking between
  *  lighton=true and lighton=false.  Ideally, we toggle every
  *  FLASH_FRAME, with ds->lastflash used to ensure we end the flash
  *  correctly.
  */
 lighton = u->lighton;
 if (flashtime > 0)
  { if (ds->lastflash < 0)
     { ds->flashing = 1;
       ds->lastflash = 0;
     }
    else if (flashtime > ds->lastflash + FLASH_FRAME)
     { ds->flashing = ! ds->flashing;
       ds->lastflash += FLASH_FRAME;
     }
    if (ds->flashing) lighton = ! lighton;
  }
 else if (ds->lastflash >= 0)
  { ds->lastflash = -1;
    ds->flashing = 0;
  }
 /*
  * On first redraw, we want to draw the surrounding barrier for
  *  non-wrapping games.  We force a redraw of all cells by
  *  initializing ds->cur such that every cell is different from the
  *  corresponding cell of new->net, so every cell will get redrawn.
  */
 if (ds->first)
  { ds->first = 0;
    for (i=d->asz2-1;i>=0;i--) ds->cur[i] = new->net[i] ^ 1;
    if (! d->p.wrap)
     { /*
	* Generate the barrier surround by drawing offset borders for
	*  all hexagons.  Doing it this way does O(n^2) work instead of
	*  the O(n) work we could do by drawing only the border
	*  hexagons, but n is small and this is done just once.  In my
	*  opinion, the code complexity of arranging to do just the
	*  border hexagons outweighs the run-time cost of this way.
	*
	* All the extra COL_BARRIER drawing we do gets overwritten by
	*  ordinary cell hexagons below.
	*/
       for (y=d->asz-1;y>=0;y--) for (x=d->asz-1;x>=0;x--)
	{ if (unused_xy(d,x,y,0)) continue;
	  cx = cell_cx_xy(ds,x,y);
	  cy = cell_cy_xy(ds,x,y);
	  load_hexagon(&phex[0],ds,cx+1,cy);
	  draw_polygon(dr,&phex[0],6,-1,COL_BARRIER);
	  load_hexagon(&phex[0],ds,cx-1,cy);
	  draw_polygon(dr,&phex[0],6,-1,COL_BARRIER);
	  load_hexagon(&phex[0],ds,cx,cy+1);
	  draw_polygon(dr,&phex[0],6,-1,COL_BARRIER);
	  load_hexagon(&phex[0],ds,cx,cy-1);
	  draw_polygon(dr,&phex[0],6,-1,COL_BARRIER);
	}
     }
  }
 /*
  * Copy from new->net to ds->live.  While we do this, we also make
  *  sure ds->live has UNUSED and DUP set exactly where appropriate.
  */
 for (i=d->asz2-1;i>=0;i--)
  { if (d->flags[i] & FCF_UNUSED)
     { ds->live[i] = UNUSED;
     }
    else if (d->flags[i] & FCF_DUP)
     { ds->live[i] = DUP | (new->net[u->dispmap[d->dupof[i]]] & ~DUP);
     }
    else
     { ds->live[i] = new->net[u->dispmap[i]] & ~DUP;
     }
  }
 /*
  * drl is the effective game-board cell being rotated.  This exists
  *  because rotloc is a cell in the stored game board, but for redraw
  *  purposes we want the cell in the displayed game board.  Similarly,
  *  dal and dl are the display-board locations of ds->animloc and
  *  u->light.
  *
  * Rotation of all replicas of a replicated rotating cell is handled
  *  below, when we draw the cells, by checking whether dupof[]==drl.
  */
 drl = (rotloc < 0) ? -1 : u->dispimap[rotloc];
 if (lighton)
  { if (rotloc >= 0) ds->live[drl] = old->net[rotloc];
    find_lit(ds,u->dispimap[u->light]);
    if (rotloc >= 0) ds->live[drl] = (ds->live[drl] & LIT) | (new->net[rotloc] & ~LIT);
  }
 dal = (ds->animloc < 0) ? -1 : u->dispimap[ds->animloc];
 dl = u->dispimap[u->light];
 /*
  * Find bidirectional links and set BIDIR on the affected links (which
  *  may or may not be getting redrawn anyway; that doesn't matter).
  *  But if a cell is being animated, it never participates in
  *  bidirectional links (for graphical purposes, which are the only
  *  purposes for which bidirectional links exist anyway).
  *
  * BIDIR depends on the way we clear BIDIR when saving ds->live[] into
  *  ds->cur[].  Set BIDIR on both half-links so we can use it to
  *  identify which cells need such attention.
  *
  * Note that all per-line markings (ERR, LOOP, etc) are such that they
  *  will always be present on both or neither of the two half-lines.
  *  We could check this, but the code would be a bit messy and, if
  *  things are broken badly enough for that check to trip, a display
  *  glitch is the least of our worries.
  */
 // Determine which (display) cells get redrawn, first cut.
 bzero(ds->want,d->asz2*sizeof(*ds->want));
 for (i=d->asz2-1;i>=0;i--)
  { if (ds->live[i] & UNUSED) continue;
    ii = d->dupof[i];
    if ( (ds->cur[ii] != ds->live[ii]) ||
	 (ii == drl) ||
	 (ii == dal) ||
	 (u->mismatch[0] && (ds->live[ii] & LOCKED)) ||
	 ( (ds->curlight != dl) &&
	   ( (ii == ds->curlight) ||
	     (ii == dl) ) ) ) ds->want[i] = 1;
  }
 // Find (relevant) bidirectional links.
 // This sets bits on game cells; we fix that below.
 for (i=d->asz2-1;i>=0;i--) ds->live[i] &= ~BIDIR_ALL;
 for (i=d->asz2-1;i>=0;i--)
  { if (ds->live[i] & (UNUSED|DUP)) continue;
    if (ds->want[i])
     { for (j=5;j>=0;j--)
	{ if ((ds->live[i] >> j) & LINK_BASE)
	   { k = connect_to(d,i,j,0);
	     if ( (k >= 0) && (d->dupof[i] != drl) && (d->dupof[k] != drl) &&
		  ((ds->live[k] >> otherway(j)) & LINK_BASE) )
	      { ds->live[k] |= BIDIR_BASE << otherway(j);
		ds->live[i] |= BIDIR_BASE << j;
	      }
	   }
	}
     }
  }
 // Now copy BIDIR bits to display cells.
 for (i=d->asz2-1;i>=0;i--)
  { if (ds->live[i] & UNUSED) continue;
    ii = ds->d->dupof[i];
    if (ii == i) continue;
    ds->live[i] |= ds->live[ii] & BIDIR_ALL;
  }
 /*
  * Clear BIDIR bits on (display) links that wrap.  Do this after
  *  copying from game cells to display, because it's possible to have
  *  two copies of a link, one of which wraps and one of which doesn't,
  *  and we want to draw only the non-wrapped one BIDIR-style.
  */
 for (i=d->asz2-1;i>=0;i--)
  { if (ds->live[i] & UNUSED) continue;
    if (! (ds->live[i] & BIDIR_ALL)) continue;
    for (j=5;j>=0;j--)
     { if ((ds->live[i] >> j) & BIDIR_BASE)
	{ k = connect_to(d,i,j,1);
	  if (k < 0) ds->live[i] &= ~ (BIDIR_BASE << j);
	  // other end handled by a different i value
	}
     }
  }
 /*
  * Above, we set BIDIR on both halves of bidirectional links.  We want
  *  to redraw other cells which would not normally get redrawn exactly
  *  when, as sketched above, they are endpoints or the light source
  *  cell.
  */
 for (i=d->asz2-1;i>=0;i--)
  { if (ds->live[i] & UNUSED) continue;
    if ( (ds->live[i] & BIDIR_ALL) &&
	 ( only_one((ds->live[i]>>LINK_S)&LINK_M) ||
	   (d->dupof[i] == dl) ) ) ds->want[i] = 1;
  }
 // Prepare to compute the update box.
 updr_init(&upd,ds);
 // Draw (1) cell backgrounds.
 for (i=d->asz2-1;i>=0;i--)
  { if (ds->live[i] & UNUSED) continue;
    if (! ds->want[i]) continue;
    cx = cell_cx_xy(ds,d->ix[i],d->iy[i]);
    cy = cell_cy_xy(ds,d->ix[i],d->iy[i]);
    load_hexagon(&phex[0],ds,cx,cy);
    draw_polygon(dr,&phex[0],6,(ds->live[d->dupof[i]]&LOCKED)?u->mismatch[u->dispmap[d->dupof[i]]+1]?COL_ERRBG:COL_LOCKED:COL_BACKGROUND,COL_BACKGROUND);
    if (ds->d->flags[i] & FCF_WRAP)
     { j = load_wrap_region(&phex[0],ds,cx,cy,ds->d->flags[i]&FCF_WRAP);
       col = (ds->live[d->dupof[i]] & LOCKED) ? u->mismatch[u->dispmap[d->dupof[i]]+1] ? COL_ERRBGWRAP : COL_LOCKWRAP : COL_BGWRAP;
       draw_polygon(dr,&phex[0],j,col,col);
     }
  }
 switch (u->mismatch[0])
  { case 0:
       break;
    case 1:
       bzero(u->mismatch+1,d->asz2);
       u->mismatch[0] = 2;
       break;
    case 2:
       u->mismatch[0] = 0;
       break;
  }
 // Draw (2) bidirectional links.
 i = d->asz2;
 for (y=d->asz-1;y>=0;y--) for (x=d->asz-1;x>=0;x--)
  { i --;
    if (! ds->want[i]) continue;
    if (ds->live[i] & UNUSED) continue;
    if (! (ds->live[i] & BIDIR_ALL)) continue;
    ii = d->dupof[i];
    cx = cell_cx_xy(ds,x,y);
    cy = cell_cy_xy(ds,x,y);
    for (j=5;j>=0;j--)
     { if ((ds->live[i] >> j) & BIDIR_BASE)
	{ oj = otherway(j);
	  k = connect_to(ds->d,i,j,1);
	  if (k < 0) abort();
	  if ((i < k) || !ds->want[k])
	   { col = ((ds->live[i] >> j) & ERR_BASE) ? COL_ERR :
		   ((ds->live[i] >> j) & LOOP_BASE) ? COL_LOOP :
		   (ds->live[ii] & LIT) ? COL_POWERED : COL_WIRE;
	     l = k / ds->d->asz;
	     k %= ds->d->asz;
	     kx = cell_cx_xy(ds,k,l);
	     ky = cell_cy_xy(ds,k,l);
	     if (ds->linew2 < 1)
	      { draw_line(dr,cx,cy,kx,ky,col);
	      }
	     else
	      { px = 0;
		// This code depends on how set_size() sets up lineoff.
		pwire[px++] = kx + ds->lineoff[oj][2].x;
		pwire[px++] = ky + ds->lineoff[oj][2].y;
		pwire[px++] = kx + ds->lineoff[oj][3].x;
		pwire[px++] = ky + ds->lineoff[oj][3].y;
		pwire[px++] = cx + ds->lineoff[j][2].x;
		pwire[px++] = cy + ds->lineoff[j][2].y;
		pwire[px++] = cx + ds->lineoff[j][3].x;
		pwire[px++] = cy + ds->lineoff[j][3].y;
		draw_polygon(dr,&pwire[0],4,col,col);
		updr_add(&upd,cx-ds->hexr3-1,cy-(2*ds->hexsize)-1,(ds->hexr3+1)*2,((2*ds->hexsize)+1)*2);
		updr_add(&upd,kx-ds->hexr3-1,ky-(2*ds->hexsize)-1,(ds->hexr3+1)*2,((2*ds->hexsize)+1)*2);
	      }
	   }
	}
     }
  }
 // Draw (3) unidirectional links (including animated ones).
 i = d->asz2;
 for (y=d->asz-1;y>=0;y--) for (x=d->asz-1;x>=0;x--)
  { i --;
    if (! ds->want[i]) continue;
    ii = d->dupof[i];
    cx = cell_cx_xy(ds,x,y);
    cy = cell_cy_xy(ds,x,y);
    for (j=5;j>=0;j--)
     { if ( ((ds->live[ii] >> j) & LINK_BASE) &&
	    !((ds->live[i] >> j) & BIDIR_BASE) )
	{ col = ((ds->live[ii] >> j) & ERR_BASE) ? COL_ERR :
		((ds->live[ii] >> j) & LOOP_BASE) ? COL_LOOP :
		(ds->live[ii] & LIT) ? COL_POWERED : COL_WIRE;
	  if (ds->linew2 < 1)
	   { if (ii == drl)
	      { draw_line(dr,cx,cy,
			cx + rint((ds->lineoff[j][0].x * racos) - (ds->lineoff[j][0].y * rasin)),
			cy + rint((ds->lineoff[j][0].x * rasin) + (ds->lineoff[j][0].y * racos)),
			col);
	      }
	     else
	      { draw_line(dr,cx,cy,cx+ds->lineoff[j][0].x,cy+ds->lineoff[j][0].y,col);
	      }
	   }
	  else
	   { px = 0;
	     for (l=4-1;l>=0;l--)
	      { if (ii == drl)
		 { pwire[px++] = cx + rint((ds->lineoff[j][l].x * racos) - (ds->lineoff[j][l].y * rasin));
		   pwire[px++] = cy + rint((ds->lineoff[j][l].x * rasin) + (ds->lineoff[j][l].y * racos));
		 }
		else
		 { pwire[px++] = cx + ds->lineoff[j][l].x;
		   pwire[px++] = cy + ds->lineoff[j][l].y;
		 }
	      }
	     draw_polygon(dr,&pwire[0],4,col,col);
	   }
	}
     }
  }
 // Draw (4) cell-centre circles.
 i = d->asz2;
 for (y=d->asz-1;y>=0;y--) for (x=d->asz-1;x>=0;x--)
  { i --;
    if (! ds->want[i]) continue;
    ii = d->dupof[i];
    cx = cell_cx_xy(ds,x,y);
    cy = cell_cy_xy(ds,x,y);
    if (only_one((ds->live[ii]>>LINK_S)&LINK_M))
     { col = (ds->live[ii] & LIT) ? COL_POWERED : COL_ENDPOINT;
       draw_circle(dr,cx,cy,ds->epcr,COL_WIRE,COL_WIRE);
       draw_circle(dr,cx,cy,ds->epcr-ds->linew2,col,col);
     }
    else
     { col = ((ds->live[ii] >> ERR_S) & ERR_M) ? COL_ERR :
	     ((ds->live[ii] >> LOOP_S) & LOOP_M) ? COL_LOOP :
	     (ds->live[ii] & LIT) ? COL_POWERED : COL_WIRE;
       draw_circle(dr,cx,cy,ds->nepcr,col,col);
     }
    if (ii == dl) draw_circle(dr,cx,cy,ds->litcr,-1,COL_POWERED);
  }
 // Draw (5) grid hexagons.
 i = d->asz2;
 for (y=d->asz-1;y>=0;y--) for (x=d->asz-1;x>=0;x--)
  { i --;
    if (! ds->want[i]) continue;
    cx = cell_cx_xy(ds,x,y);
    cy = cell_cy_xy(ds,x,y);
    load_hexagon(&phex[0],ds,cx,cy);
    draw_polygon(dr,&phex[0],6,-1,COL_BORDER);
    updr_add(&upd,cx-ds->hexr3-1,cy-(2*ds->hexsize)-1,(ds->hexr3+1)*2,((2*ds->hexsize)+1)*2);
  }
 // Push the updates.
 updr_draw_update(&upd,dr);
 // Update ds->cur.  As mentioned above, we must clear BIDIR_ALL.
 for (i=d->asz2-1;i>=0;i--) ds->cur[i] = ds->live[i] & ~BIDIR_ALL;
 ds->animloc = rotloc;
 ds->curlight = u->dispimap[u->light];
}

/*
 * Determine whether a move should be animated, and if so return for
 *  how long.  We animate rotations (and only rotations).
 */
static float anim_length(const STATE *old, const STATE *new, int dir, UI *u)
{
 int rdir;

 (void)u;
 if (dir < 0)
  { rdir = (old->lastrot_loc < 0) ? 0 : old->lastrot_dir;
  }
 else
  { rdir = (new->lastrot_loc < 0) ? 0 : new->lastrot_dir;
  }
 if (! rdir) return(0);
 return(ROTATE_TIME);
}

/*
 * Determine whether a change calls for a flash, and if so return how
 *  long it is.  We flash on any change that changes from not-solved to
 *  solved.
 *
 * XXX we arguably should do this on only the first such transition;
 *  maybe figure out where to save the state to do that?
 */
static float flash_length(const STATE *old, const STATE *new, int dir, UI *u)
{
 (void)dir;
 (void)u;
 if ((new->flags & ~old->flags) & SF_SOLVED) return(FLASH_TIME);
 return(0);
}

static int flag_mismatches(const STATE *cur, const STATE *solved, UI *u)
{
 int i;

 for (i=cur->d->asz2-1;i>=0;i--)
  { u->mismatch[i+1] = 
	( (solved->net[i] & cur->net[i] & LOCKED) &&
	  ((solved->net[i] ^ cur->net[i]) & LINK_ALL) );
  }
 u->mismatch[0] = 1;
 return(MISMATCH_REDRAW);
}

/*
 * Status.  For hexnet, we always return 0.
 *
 * XXX Should we maybe return 1 sometimes?
 */
static int status(const STATE *s)
{
 (void)s;
 return(0);
}

// Should never get called, since our is_timed is false.
static bool timing_state(const STATE *s, UI *u)
{
 (void)s;
 (void)u;
 return(false);
}

// Should never get called, since our can_print is false.
static void print_size(const PARAMS *p, float *x, float *y)
{
 (void)p;
 (void)x;
 (void)y;
 abort();
}

// Should never get called, since our can_print is false.
// We arbitrarily "use" dump_cells here.
static void print(DRAWING *dr, const STATE *s, int tilesize)
{
 (void)&dump_cells;
 (void)dr;
 (void)s;
 (void)tilesize;
 abort();
}

#ifdef COMBINED
#define thegame hexnetgame
#endif

const struct game thegame
 = { "Hex Net Game",
     0, // winhelp_topic
     0, // htmlhelp_topic
     &default_params,
     &fetch_preset,
     0, // preset_menu
     &decode_params,
     &encode_params,
     &free_params,
     &dup_params,
     true, // can_configure
     &configure,
     &custom_params,
     &validate_params,
     &new_game_desc,
     &validate_desc,
     &new_game,
     &dup_game,
     &free_game,
     true, // can_solve
     &solve_game,
     false, // can_format_as_text_ever
     &can_format_as_text_now,
     &text_format,
     &new_ui,
     &free_ui,
     &encode_ui,
     &decode_ui,
     0, // request_keys
     &changed_state,
     &interpret_move,
     &execute_move,
     10, // preferred_tilesize
     &compute_size,
     &set_size,
     &colours,
     &new_drawstate,
     &free_drawstate,
     &redraw,
     &anim_length,
     &flash_length,
     0, // get_cursor_location
     &status,
     false, // can_print
     false, // can_print_in_colour
     &print_size,
     &print,
     false, // wants_statusbar
     false, // is_timed
     &timing_state,
     0, // flags
     &flag_mismatches,
     };