tracks.c

   1 /*
   2  * Implementation of 'Train Tracks', a puzzle from the Times on Saturday.
   3  *
   4  * "Lay tracks to enable the train to travel from village A to village B.
   5  * The numbers indicate how many sections of rail go in each row and
   6  * column. There are only straight rails and curved rails. The track
   7  * cannot cross itself."
   8  *
   9  * Puzzles:
  10  * #9     8x8:d9s5c6zgAa,1,4,1,4,4,3,S3,5,2,2,4,S5,3,3,5,1
  11  * #112   8x8:w6x5mAa,1,3,1,4,6,4,S4,3,3,4,5,2,4,2,S5,1
  12  * #113   8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1
  13  * #114   8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1
  14  * #115   8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1
  15  */
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <assert.h>
  21 #include <ctype.h>
  22 #include <math.h>
  23
  24 #include "puzzles.h"
  25
  26 /* --- Game parameters --- */
  27
  28 /*
  29  * Difficulty levels. I do some macro ickery here to ensure that my
  30  * enum and the various forms of my name list always match up.
  31  */
  32 #define DIFFLIST(A) \
  33     A(EASY,Easy,e) \
  34     A(TRICKY,Tricky,t)
  35
  36 #define ENUM(upper,title,lower) DIFF_ ## upper,
  37 #define TITLE(upper,title,lower) #title,
  38 #define ENCODE(upper,title,lower) #lower
  39 #define CONFIG(upper,title,lower) ":" #title
  40 enum { DIFFLIST(ENUM) DIFFCOUNT };
  41 static char const *const tracks_diffnames[] = { DIFFLIST(TITLE) };
  42 static char const tracks_diffchars[] = DIFFLIST(ENCODE);
  43 #define DIFFCONFIG DIFFLIST(CONFIG)
  44
  45 struct game_params {
  46     int w, h, diff, single_ones;
  47 };
  48
  49 static game_params *default_params(void)
  50 {
  51     game_params *ret = snew(game_params);
  52
  53     ret->w = ret->h = 8;
  54     ret->diff = DIFF_TRICKY;
  55     ret->single_ones = TRUE;
  56
  57     return ret;
  58 }
  59
  60 static const struct game_params tracks_presets[] = {
  61     {8, 8, DIFF_EASY, 1},
  62     {8, 8, DIFF_TRICKY, 1},
  63     {10, 8, DIFF_EASY, 1},
  64     {10, 8, DIFF_TRICKY, 1 },
  65     {10, 10, DIFF_EASY, 1},
  66     {10, 10, DIFF_TRICKY, 1},
  67     {15, 10, DIFF_EASY, 1},
  68     {15, 10, DIFF_TRICKY, 1},
  69     {15, 15, DIFF_EASY, 1},
  70     {15, 15, DIFF_TRICKY, 1},
  71 };
  72
  73 static int game_fetch_preset(int i, char **name, game_params **params)
  74 {
  75     game_params *ret;
  76     char str[80];
  77
  78     if (i < 0 || i >= lenof(tracks_presets))
  79         return FALSE;
  80
  81     ret = snew(game_params);
  82     *ret = tracks_presets[i];
  83
  84     sprintf(str, "%dx%d %s", ret->w, ret->h, tracks_diffnames[ret->diff]);
  85
  86     *name = dupstr(str);
  87     *params = ret;
  88     return TRUE;
  89 }
  90
  91 static void free_params(game_params *params)
  92 {
  93     sfree(params);
  94 }
  95
  96 static game_params *dup_params(const game_params *params)
  97 {
  98     game_params *ret = snew(game_params);
  99     *ret = *params;                    /* structure copy */
 100     return ret;
 101 }
 102
 103 static void decode_params(game_params *params, char const *string)
 104 {
 105     params->w = params->h = atoi(string);
 106     while (*string && isdigit((unsigned char)*string)) string++;
 107     if (*string == 'x') {
 108         string++;
 109         params->h = atoi(string);
 110         while (*string && isdigit((unsigned char)*string)) string++;
 111     }
 112     if (*string == 'd') {
 113         int i;
 114         string++;
 115         params->diff = DIFF_TRICKY;
 116         for (i = 0; i < DIFFCOUNT; i++)
 117             if (*string == tracks_diffchars[i])
 118                 params->diff = i;
 119         if (*string) string++;
 120     }
 121     params->single_ones = TRUE;
 122     if (*string == 'o') {
 123         params->single_ones = FALSE;
 124         string++;
 125     }
 126
 127 }
 128
 129 static char *encode_params(const game_params *params, int full)
 130 {
 131     char buf[120];
 132
 133     sprintf(buf, "%dx%d", params->w, params->h);
 134     if (full)
 135         sprintf(buf + strlen(buf), "d%c%s",
 136                 tracks_diffchars[params->diff],
 137                 params->single_ones ? "" : "o");
 138     return dupstr(buf);
 139 }
 140
 141 static config_item *game_configure(const game_params *params)
 142 {
 143     config_item *ret;
 144     char buf[80];
 145
 146     ret = snewn(5, config_item);
 147
 148     ret[0].name = "Width";
 149     ret[0].type = C_STRING;
 150     sprintf(buf, "%d", params->w);
 151     ret[0].sval = dupstr(buf);
 152     ret[0].ival = 0;
 153
 154     ret[1].name = "Height";
 155     ret[1].type = C_STRING;
 156     sprintf(buf, "%d", params->h);
 157     ret[1].sval = dupstr(buf);
 158     ret[1].ival = 0;
 159
 160     ret[2].name = "Difficulty";
 161     ret[2].type = C_CHOICES;
 162     ret[2].sval = DIFFCONFIG;
 163     ret[2].ival = params->diff;
 164
 165     ret[3].name = "Disallow consecutive 1 clues";
 166     ret[3].type = C_BOOLEAN;
 167     ret[3].ival = params->single_ones;
 168
 169     ret[4].name = NULL;
 170     ret[4].type = C_END;
 171     ret[4].sval = NULL;
 172     ret[4].ival = 0;
 173
 174     return ret;
 175 }
 176
 177 static game_params *custom_params(const config_item *cfg)
 178 {
 179     game_params *ret = snew(game_params);
 180
 181     ret->w = atoi(cfg[0].sval);
 182     ret->h = atoi(cfg[1].sval);
 183     ret->diff = cfg[2].ival;
 184     ret->single_ones = cfg[3].ival;
 185
 186     return ret;
 187 }
 188
 189 static char *validate_params(const game_params *params, int full)
 190 {
 191     /*
 192      * Generating anything under 4x4 runs into trouble of one kind
 193      * or another.
 194      */
 195     if (params->w < 4 || params->h < 4)
 196         return "Width and height must both be at least four";
 197     return NULL;
 198 }
 199
 200 /* --- Game state --- */
 201
 202 /* flag usage copied from pearl */
 203
 204 #define R 1
 205 #define U 2
 206 #define L 4
 207 #define D 8
 208
 209 #define MOVECHAR(m) ((m==R)?'R':(m==U)?'U':(m==L)?'L':(m==D)?'D':'?')
 210
 211 #define DX(d) ( ((d)==R) - ((d)==L) )
 212 #define DY(d) ( ((d)==D) - ((d)==U) )
 213
 214 #define F(d) (((d << 2) | (d >> 2)) & 0xF)
 215 #define C(d) (((d << 3) | (d >> 1)) & 0xF)
 216 #define A(d) (((d << 1) | (d >> 3)) & 0xF)
 217
 218 #define LR (L | R)
 219 #define RL (R | L)
 220 #define UD (U | D)
 221 #define DU (D | U)
 222 #define LU (L | U)
 223 #define UL (U | L)
 224 #define LD (L | D)
 225 #define DL (D | L)
 226 #define RU (R | U)
 227 #define UR (U | R)
 228 #define RD (R | D)
 229 #define DR (D | R)
 230 #define ALLDIR 15
 231 #define BLANK 0
 232 #define UNKNOWN 15
 233
 234 int nbits[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
 235
 236 /* square grid flags */
 237 #define S_TRACK 1     /* a track passes through this square (--> 2 edges) */
 238 #define S_NOTRACK 2   /* no track passes through this square */
 239 #define S_ERROR 4
 240 #define S_CLUE 8
 241 #define S_MARK 16
 242
 243 #define S_TRACK_SHIFT   16 /* U/D/L/R flags for edge track indicators */
 244 #define S_NOTRACK_SHIFT 20 /* U/D/L/R flags for edge no-track indicators */
 245
 246 /* edge grid flags */
 247 #define E_TRACK 1     /* a track passes through this edge */
 248 #define E_NOTRACK 2   /* no track passes through this edge */
 249
 250 struct numbers {
 251     int refcount;
 252     int *numbers;     /* sz w+h */
 253     int row_s, col_s; /* stations: TODO think about multiple lines
 254                          (for bigger grids)? */
 255 };
 256
 257 #define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->p.w && \
 258                                (gy) >= 0 && (gy) < (state)->p.h)
 259
 260 struct game_state {
 261     game_params p;
 262     unsigned int *sflags;       /* size w*h */
 263     struct numbers *numbers;
 264     int *num_errors;            /* size w+h */
 265     int completed, used_solve, impossible;
 266 };
 267
 268 /* Return the four directions in which a particular edge flag is set, around a square. */
 269 int S_E_DIRS(const game_state *state, int sx, int sy, unsigned int eflag) {
 270     return (state->sflags[sy*state->p.w+sx] >>
 271             ((eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT)) & ALLDIR;
 272 }
 273
 274 /* Count the number of a particular edge flag around a grid square. */
 275 int S_E_COUNT(const game_state *state, int sx, int sy, unsigned int eflag) {
 276     return nbits[S_E_DIRS(state, sx, sy, eflag)];
 277 }
 278
 279 /* Return the two flags (E_TRACK and/or E_NOTRACK) set on a specific
 280  * edge of a square. */
 281 unsigned S_E_FLAGS(const game_state *state, int sx, int sy, int d) {
 282     unsigned f = state->sflags[sy*state->p.w+sx];
 283     int t = (f & (d << S_TRACK_SHIFT)), nt = (f & (d << S_NOTRACK_SHIFT));
 284     return (t ? E_TRACK : 0) | (nt ? E_NOTRACK : 0);
 285 }
 286
 287 int S_E_ADJ(const game_state *state, int sx, int sy, int d, int *ax, int *ay, unsigned int *ad) {
 288     if (d == L && sx > 0)            { *ax = sx-1; *ay = sy;   *ad = R; return 1; }
 289     if (d == R && sx < state->p.w-1) { *ax = sx+1; *ay = sy;   *ad = L; return 1; }
 290     if (d == U && sy > 0)            { *ax = sx;   *ay = sy-1; *ad = D; return 1; }
 291     if (d == D && sy < state->p.h-1) { *ax = sx;   *ay = sy+1; *ad = U; return 1; }
 292
 293     return 0;
 294 }
 295
 296 /* Sets flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
 297 void S_E_SET(game_state *state, int sx, int sy, int d, unsigned int eflag) {
 298     unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad;
 299     int ax, ay;
 300
 301     state->sflags[sy*state->p.w+sx] |= (d << shift);
 302
 303     if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
 304         state->sflags[ay*state->p.w+ax] |= (ad << shift);
 305     }
 306 }
 307
 308 /* Clears flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
 309 void S_E_CLEAR(game_state *state, int sx, int sy, int d, unsigned int eflag) {
 310     unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad;
 311     int ax, ay;
 312
 313     state->sflags[sy*state->p.w+sx] &= ~(d << shift);
 314
 315     if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
 316         state->sflags[ay*state->p.w+ax] &= ~(ad << shift);
 317     }
 318 }
 319
 320 static void clear_game(game_state *state)
 321 {
 322     int w = state->p.w, h = state->p.h;
 323
 324     memset(state->sflags, 0, w*h * sizeof(unsigned int));
 325
 326     memset(state->numbers->numbers, 0, (w+h) * sizeof(int));
 327     state->numbers->col_s = state->numbers->row_s = -1;
 328
 329     memset(state->num_errors, 0, (w+h) * sizeof(int));
 330
 331     state->completed = state->used_solve = state->impossible = FALSE;
 332 }
 333
 334 static game_state *blank_game(const game_params *params)
 335 {
 336     game_state *state = snew(game_state);
 337     int w = params->w, h = params->h;
 338
 339     state->p = *params;
 340
 341     state->sflags = snewn(w*h, unsigned int);
 342
 343     state->numbers = snew(struct numbers);
 344     state->numbers->refcount = 1;
 345     state->numbers->numbers = snewn(w+h, int);
 346
 347     state->num_errors = snewn(w+h, int);
 348
 349     clear_game(state);
 350
 351     return state;
 352 }
 353
 354 static void copy_game_flags(const game_state *src, game_state *dest)
 355 {
 356     int w = src->p.w, h = src->p.h;
 357
 358     memcpy(dest->sflags, src->sflags, w*h*sizeof(unsigned int));
 359 }
 360
 361 static game_state *dup_game(const game_state *state)
 362 {
 363     int w = state->p.w, h = state->p.h;
 364     game_state *ret = snew(game_state);
 365
 366     ret->p = state->p;                 /* structure copy */
 367
 368     ret->sflags = snewn(w*h, unsigned int);
 369     copy_game_flags(state, ret);
 370
 371     ret->numbers = state->numbers;
 372     state->numbers->refcount++;
 373     ret->num_errors = snewn(w+h, int);
 374     memcpy(ret->num_errors, state->num_errors, (w+h)*sizeof(int));
 375
 376     ret->completed = state->completed;
 377     ret->used_solve = state->used_solve;
 378     ret->impossible = state->impossible;
 379
 380     return ret;
 381 }
 382
 383 static void free_game(game_state *state)
 384 {
 385     if (--state->numbers->refcount <= 0) {
 386         sfree(state->numbers->numbers);
 387         sfree(state->numbers);
 388     }
 389     sfree(state->num_errors);
 390     sfree(state->sflags);
 391     sfree(state);
 392 }
 393
 394 #define NDIRS 4
 395 const unsigned int dirs_const[] = { U, D, L, R };
 396
 397 static unsigned int find_direction(game_state *state, random_state *rs,
 398                                    int x, int y)
 399 {
 400     int i, nx, ny, w=state->p.w, h=state->p.h;
 401     unsigned int dirs[NDIRS];
 402
 403     memcpy(dirs, dirs_const, sizeof(dirs));
 404     shuffle(dirs, NDIRS, sizeof(*dirs), rs);
 405     for (i = 0; i < NDIRS; i++) {
 406         nx = x + DX(dirs[i]);
 407         ny = y + DY(dirs[i]);
 408         if (nx >= 0 && nx < w && ny == h) {
 409             /* off the bottom of the board: we've finished the path. */
 410             return dirs[i];
 411         } else if (!INGRID(state, nx, ny)) {
 412             /* off the board: can't move here */
 413             continue;
 414         } else if (S_E_COUNT(state, nx, ny, E_TRACK) > 0) {
 415             /* already tracks here: can't move */
 416             continue;
 417         }
 418         return dirs[i];
 419     }
 420     return 0; /* no possible directions left. */
 421 }
 422
 423 static int check_completion(game_state *state, int mark);
 424
 425 static void lay_path(game_state *state, random_state *rs)
 426 {
 427     int px, py, w=state->p.w, h=state->p.h;
 428     unsigned int d;
 429
 430 start:
 431     clear_game(state);
 432
 433     /* pick a random entry point, lay its left edge */
 434     state->numbers->row_s = py = random_upto(rs, h);
 435     px = 0;
 436     S_E_SET(state, px, py, L, E_TRACK);
 437
 438     while (INGRID(state, px, py)) {
 439         d = find_direction(state, rs, px, py);
 440         if (d == 0)
 441             goto start; /* nowhere else to go, restart */
 442
 443         S_E_SET(state, px, py, d, E_TRACK);
 444         px += DX(d);
 445         py += DY(d);
 446     }
 447     /* double-check we got to the right place */
 448     assert(px >= 0 && px < w && py == h);
 449
 450     state->numbers->col_s = px;
 451 }
 452
 453 static int tracks_solve(game_state *state, int diff);
 454 static void debug_state(game_state *state, const char *what);
 455
 456 /* Clue-setting algorithm:
 457
 458  - first lay clues randomly until it's soluble
 459  - then remove clues randomly if removing them doesn't affect solubility
 460
 461  - We start with two clues, one at each path entrance.
 462
 463  More details:
 464  - start with an array of all square i positions
 465  - if the grid is already soluble by a level easier than we've requested,
 466     go back and make a new grid
 467  - if the grid is already soluble by our requested difficulty level, skip
 468     the clue-laying step
 469  - count the number of flags the solver managed to place, remember this.
 470
 471  - to lay clues:
 472    - shuffle the i positions
 473    - for each possible clue position:
 474      - copy the solved board, strip it
 475      - take the next position, add a clue there on the copy
 476      - try and solve the copy
 477      - if it's soluble by a level easier than we've requested, continue (on
 478         to next clue position: putting a clue here makes it too easy)
 479      - if it's soluble by our difficulty level, we're done:
 480        - put the clue flag into the solved board
 481        - go to strip-clues.
 482      - if the solver didn't manage to place any more flags, continue (on to next
 483         clue position: putting a clue here didn't help he solver)
 484      - otherwise put the clue flag in the original board, and go on to the next
 485         clue position
 486    - if we get here and we've not solved it yet, we never will (did we really
 487       fill _all_ the clues in?!). Go back and make a new grid.
 488
 489  - to strip clues:
 490    - shuffle the i positions
 491    - for each possible clue position:
 492      - if the solved grid doesn't have a clue here, skip
 493      - copy the solved board, remove this clue, strip it
 494      - try and solve the copy
 495      - assert that it is not soluble by a level easier than we've requested
 496        - (because this should never happen)
 497      - if this is (still) soluble by our difficulty level:
 498        - remove this clue from the solved board, it's redundant (with the other
 499           clues)
 500
 501   - that should be it.
 502 */
 503
 504 static game_state *copy_and_strip(const game_state *state, game_state *ret, int flipcluei)
 505 {
 506     int i, j, w = state->p.w, h = state->p.h;
 507
 508     copy_game_flags(state, ret);
 509
 510     /* Add/remove a clue before stripping, if required */
 511
 512     if (flipcluei != -1)
 513         ret->sflags[flipcluei] ^= S_CLUE;
 514
 515     /* All squares that are not clue squares have square track info erased, and some edge flags.. */
 516
 517     for (i = 0; i < w*h; i++) {
 518         if (!(ret->sflags[i] & S_CLUE)) {
 519             ret->sflags[i] &= ~(S_TRACK|S_NOTRACK|S_ERROR|S_MARK);
 520             for (j = 0; j < 4; j++) {
 521                 unsigned f = 1<<j;
 522                 int xx = i%w + DX(f), yy = i/w + DY(f);
 523                 if (!INGRID(state, xx, yy) || !(ret->sflags[yy*w+xx] & S_CLUE)) {
 524                     /* only erase an edge flag if neither side of the edge is S_CLUE. */
 525                     S_E_CLEAR(ret, i%w, i/w, f, E_TRACK);
 526                     S_E_CLEAR(ret, i%w, i/w, f, E_NOTRACK);
 527                 }
 528             }
 529         }
 530     }
 531     return ret;
 532 }
 533
 534 static int solve_progress(const game_state *state) {
 535     int i, w = state->p.w, h = state->p.h, progress = 0;
 536
 537     /* Work out how many flags the solver managed to set (either TRACK
 538        or NOTRACK) and return this as a progress measure, to check whether
 539        a partially-solved board gets any further than a previous partially-
 540        solved board. */
 541
 542     for (i = 0; i < w*h; i++) {
 543         if (state->sflags[i] & S_TRACK) progress++;
 544         if (state->sflags[i] & S_NOTRACK) progress++;
 545         progress += S_E_COUNT(state, i%w, i/w, E_TRACK);
 546         progress += S_E_COUNT(state, i%w, i/w, E_NOTRACK);
 547     }
 548     return progress;
 549 }
 550
 551 static int check_phantom_moves(const game_state *state) {
 552     int x, y, i;
 553
 554     /* Check that this state won't show 'phantom moves' at the start of the
 555      * game: squares which have multiple edge flags set but no clue flag
 556      * cause a piece of track to appear that isn't on a clue square. */
 557
 558     for (x = 0; x < state->p.w; x++) {
 559         for (y = 0; y < state->p.h; y++) {
 560             i = y*state->p.w+x;
 561             if (state->sflags[i] & S_CLUE)
 562                 continue;
 563             if (S_E_COUNT(state, x, y, E_TRACK) > 1)
 564                 return 1; /* found one! */
 565         }
 566     }
 567     return 0;
 568 }
 569
 570 static int add_clues(game_state *state, random_state *rs, int diff)
 571 {
 572     int i, j, pi, w = state->p.w, h = state->p.h, progress, ret = 0, sr;
 573     int *positions = snewn(w*h, int), npositions = 0;
 574     int *nedges_previous_solve = snewn(w*h, int);
 575     game_state *scratch = dup_game(state);
 576
 577     debug_state(state, "gen: Initial board");
 578
 579     debug(("gen: Adding clues..."));
 580
 581     /* set up the shuffly-position grid for later, used for adding clues:
 582      * we only bother adding clues where any edges are set. */
 583     for (i = 0; i < w*h; i++) {
 584         if (S_E_DIRS(state, i%w, i/w, E_TRACK) != 0) {
 585             positions[npositions++] = i;
 586         }
 587         nedges_previous_solve[i] = 0;
 588     }
 589
 590     /* First, check whether the puzzle is already either too easy, or just right */
 591     scratch = copy_and_strip(state, scratch, -1);
 592     if (diff > 0) {
 593         sr = tracks_solve(scratch, diff-1);
 594         if (sr < 0)
 595             assert(!"Generator should not have created impossible puzzle");
 596         if (sr > 0) {
 597             ret = -1; /* already too easy, even without adding clues. */
 598             debug(("gen:  ...already too easy, need new board."));
 599             goto done;
 600         }
 601     }
 602     sr = tracks_solve(scratch, diff);
 603     if (sr < 0)
 604         assert(!"Generator should not have created impossible puzzle");
 605     if (sr > 0) {
 606         ret = 1; /* already soluble without any extra clues. */
 607         debug(("gen:  ...soluble without clues, nothing to do."));
 608         goto done;
 609     }
 610     debug_state(scratch, "gen: Initial part-solved state: ");
 611     progress = solve_progress(scratch);
 612     debug(("gen: Initial solve progress is %d", progress));
 613
 614     /* First, lay clues until we're soluble. */
 615     shuffle(positions, npositions, sizeof(int), rs);
 616     for (pi = 0; pi < npositions; pi++) {
 617         i = positions[pi]; /* pick a random position */
 618         if (state->sflags[i] & S_CLUE)
 619             continue; /* already a clue here (entrance location?) */
 620         if (nedges_previous_solve[i] == 2)
 621             continue; /* no point putting a clue here, we could solve both edges
 622                          with the previous set of clues */
 623
 624         /* set a clue in that position (on a copy of the board) and test solubility */
 625         scratch = copy_and_strip(state, scratch, i);
 626
 627         if (check_phantom_moves(scratch))
 628             continue; /* adding a clue here would add phantom track */
 629
 630         if (diff > 0) {
 631             if (tracks_solve(scratch, diff-1) > 0) {
 632                 continue; /* adding a clue here makes it too easy */
 633             }
 634         }
 635         if (tracks_solve(scratch, diff) > 0) {
 636             /* we're now soluble (and we weren't before): add this clue, and then
 637                start stripping clues */
 638             debug(("gen:  ...adding clue at (%d,%d), now soluble", i%w, i/w));
 639             state->sflags[i] |= S_CLUE;
 640             goto strip_clues;
 641         }
 642         if (solve_progress(scratch) > progress) {
 643             /* We've made more progress solving: add this clue, then. */
 644             progress = solve_progress(scratch);
 645             debug(("gen:  ... adding clue at (%d,%d), new progress %d", i%w, i/w, progress));
 646             state->sflags[i] |= S_CLUE;
 647
 648             for (j = 0; j < w*h; j++)
 649                 nedges_previous_solve[j] = S_E_COUNT(scratch, j%w, j/w, E_TRACK);
 650         }
 651     }
 652     /* If we got here we didn't ever manage to make the puzzle soluble
 653        (without making it too easily soluble, that is): give up. */
 654
 655     debug(("gen: Unable to make soluble with clues, need new board."));
 656     ret = -1;
 657     goto done;
 658
 659 strip_clues:
 660     debug(("gen: Stripping clues."));
 661
 662     /* Now, strip redundant clues (i.e. those without which the puzzle is still
 663        soluble) */
 664     shuffle(positions, npositions, sizeof(int), rs);
 665     for (pi = 0; pi < npositions; pi++) {
 666         i = positions[pi]; /* pick a random position */
 667         if (!(state->sflags[i] & S_CLUE))
 668             continue; /* no clue here to strip */
 669         if ((i%w == 0 && i/w == state->numbers->row_s) ||
 670                 (i/w == (h-1) && i%w == state->numbers->col_s))
 671             continue; /* don't strip clues at entrance/exit */
 672
 673         scratch = copy_and_strip(state, scratch, i);
 674         if (check_phantom_moves(scratch))
 675             continue; /* removing a clue here would add phantom track */
 676
 677         if (tracks_solve(scratch, diff) > 0) {
 678             debug(("gen:  ... removing clue at (%d,%d), still soluble without it", i%w, i/w));
 679             state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */
 680         }
 681     }
 682     debug(("gen: Finished stripping clues."));
 683     ret = 1;
 684
 685 done:
 686     sfree(positions);
 687     free_game(scratch);
 688     return ret;
 689 }
 690
 691 static char *new_game_desc(const game_params *params, random_state *rs,
 692                            char **aux, int interactive)
 693 {
 694     int i, j, w = params->w, h = params->h, x, y, ret;
 695     game_state *state;
 696     char *desc, *p;
 697     game_params adjusted_params;
 698
 699     /*
 700      * 4x4 Tricky cannot be generated, so fall back to Easy.
 701      */
 702     if (w == 4 && h == 4 && params->diff > DIFF_EASY) {
 703         adjusted_params = *params;     /* structure copy */
 704         adjusted_params.diff = DIFF_EASY;
 705         params = &adjusted_params;
 706     }
 707
 708     state = blank_game(params);
 709
 710     /* --- lay the random path */
 711
 712 newpath:
 713     lay_path(state, rs);
 714     for (x = 0; x < w; x++) {
 715         for (y = 0; y < h; y++) {
 716             if (S_E_COUNT(state, x, y, E_TRACK) > 0) {
 717                 state->sflags[y*w + x] |= S_TRACK;
 718             }
 719             if ((x == 0 && y == state->numbers->row_s) ||
 720                     (y == (h-1) && x == state->numbers->col_s)) {
 721                 state->sflags[y*w + x] |= S_CLUE;
 722             }
 723         }
 724     }
 725
 726     /* --- Update the clue numbers based on the tracks we have generated. */
 727     for (x = 0; x < w; x++) {
 728         for (y = 0; y < h; y++) {
 729             if (state->sflags[y*w + x] & S_TRACK) {
 730                 state->numbers->numbers[x]++;
 731                 state->numbers->numbers[y+w]++;
 732             }
 733         }
 734     }
 735     for (i = 0; i < w+h; i++) {
 736         if (state->numbers->numbers[i] == 0)
 737             goto newpath; /* too boring */
 738     }
 739
 740     if (params->single_ones) {
 741         int last_was_one = 1, is_one; /* (disallow 1 clue at entry point) */
 742         for (i = 0; i < w+h; i++) {
 743             is_one = (state->numbers->numbers[i] == 1);
 744             if (is_one && last_was_one)
 745                 goto newpath; /* disallow consecutive 1 clues. */
 746             last_was_one = is_one;
 747         }
 748         if (state->numbers->numbers[w+h-1] == 1)
 749             goto newpath; /* (disallow 1 clue at exit point) */
 750     }
 751
 752     /* --- Add clues to make a soluble puzzle */
 753     ret = add_clues(state, rs, params->diff);
 754     if (ret != 1) goto newpath; /* couldn't make it soluble, or too easy */
 755
 756     /* --- Generate the game desc based on the generated grid. */
 757     desc = snewn(w*h*3 + (w+h)*5, char);
 758     for (i = j = 0; i < w*h; i++) {
 759         if (!(state->sflags[i] & S_CLUE) && j > 0 &&
 760                 desc[j-1] >= 'a' && desc[j-1] < 'z')
 761             desc[j-1]++;
 762         else if (!(state->sflags[i] & S_CLUE))
 763             desc[j++] = 'a';
 764         else {
 765             unsigned int f = S_E_DIRS(state, i%w, i/w, E_TRACK);
 766             desc[j++] = (f < 10) ? ('0' + f) : ('A' + (f-10));
 767         }
 768     }
 769
 770     p = desc + j;
 771     for (x = 0; x < w; x++) {
 772         p += sprintf(p, ",%s%d", x == state->numbers->col_s ? "S" : "",
 773                      state->numbers->numbers[x]);
 774     }
 775     for (y = 0; y < h; y++) {
 776         p += sprintf(p, ",%s%d", y == state->numbers->row_s ? "S" : "",
 777                      state->numbers->numbers[y+w]);
 778     }
 779     *p++ = '\0';
 780
 781     ret = tracks_solve(state, DIFFCOUNT);
 782     assert(ret >= 0);
 783     free_game(state);
 784
 785     debug(("new_game_desc: %s", desc));
 786     return desc;
 787 }
 788
 789 static char *validate_desc(const game_params *params, const char *desc)
 790 {
 791     int i = 0, w = params->w, h = params->h, in = 0, out = 0;
 792
 793     while (*desc) {
 794         unsigned int f = 0;
 795         if (*desc >= '0' && *desc <= '9')
 796             f = (*desc - '0');
 797         else if (*desc >= 'A' && *desc <= 'F')
 798             f = (*desc - 'A' + 10);
 799         else if (*desc >= 'a' && *desc <= 'z')
 800             i += *desc - 'a';
 801         else
 802             return "Game description contained unexpected characters";
 803
 804         if (f != 0) {
 805             if (nbits[f] != 2)
 806                 return "Clue did not provide 2 direction flags";
 807         }
 808         i++;
 809         desc++;
 810         if (i == w*h) break;
 811     }
 812     for (i = 0; i < w+h; i++) {
 813         if (!*desc)
 814             return "Not enough numbers given after grid specification";
 815         else if (*desc != ',')
 816             return "Invalid character in number list";
 817         desc++;
 818         if (*desc == 'S') {
 819             if (i < w)
 820                 out++;
 821             else
 822                 in++;
 823             desc++;
 824         }
 825         while (*desc && isdigit((unsigned char)*desc)) desc++;
 826     }
 827     if (in != 1 || out != 1)
 828         return "Puzzle must have one entrance and one exit";
 829     if (*desc)
 830         return "Unexpected additional character at end of game description";
 831     return NULL;
 832 }
 833
 834 static game_state *new_game(midend *me, const game_params *params, const char *desc)
 835 {
 836     game_state *state = blank_game(params);
 837     int w = params->w, h = params->h, i = 0;
 838
 839     while (*desc) {
 840         unsigned int f = 0;
 841         if (*desc >= '0' && *desc <= '9')
 842             f = (*desc - '0');
 843         else if (*desc >= 'A' && *desc <= 'F')
 844             f = (*desc - 'A' + 10);
 845         else if (*desc >= 'a' && *desc <= 'z')
 846             i += *desc - 'a';
 847
 848         if (f != 0) {
 849             int x = i % w, y = i / w;
 850             assert(f < 16);
 851             assert(nbits[f] == 2);
 852
 853             state->sflags[i] |= (S_TRACK | S_CLUE);
 854             if (f & U) S_E_SET(state, x, y, U, E_TRACK);
 855             if (f & D) S_E_SET(state, x, y, D, E_TRACK);
 856             if (f & L) S_E_SET(state, x, y, L, E_TRACK);
 857             if (f & R) S_E_SET(state, x, y, R, E_TRACK);
 858         }
 859         i++;
 860         desc++;
 861         if (i == w*h) break;
 862     }
 863     for (i = 0; i < w+h; i++) {
 864         assert(*desc == ',');
 865         desc++;
 866
 867         if (*desc == 'S') {
 868             if (i < w)
 869                 state->numbers->col_s = i;
 870             else
 871                 state->numbers->row_s = i-w;
 872             desc++;
 873         }
 874         state->numbers->numbers[i] = atoi(desc);
 875         while (*desc && isdigit((unsigned char)*desc)) desc++;
 876     }
 877
 878     assert(!*desc);
 879
 880     return state;
 881 }
 882
 883 static int solve_set_sflag(game_state *state, int x, int y,
 884                            unsigned int f, const char *why)
 885 {
 886     int w = state->p.w, i = y*w + x;
 887
 888     if (state->sflags[i] & f)
 889         return 0;
 890     debug(("solve: square (%d,%d) -> %s: %s",
 891            x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
 892     if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) {
 893         debug(("solve: opposite flag already set there, marking IMPOSSIBLE"));
 894         state->impossible = TRUE;
 895     }
 896     state->sflags[i] |= f;
 897     return 1;
 898 }
 899
 900 static int solve_set_eflag(game_state *state, int x, int y, int d,
 901                            unsigned int f, const char *why)
 902 {
 903     int sf = S_E_FLAGS(state, x, y, d);
 904
 905     if (sf & f)
 906         return 0;
 907     debug(("solve: edge (%d,%d)/%c -> %s: %s", x, y,
 908            (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R',
 909            (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
 910     if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) {
 911         debug(("solve: opposite flag already set there, marking IMPOSSIBLE"));
 912         state->impossible = TRUE;
 913     }
 914     S_E_SET(state, x, y, d, f);
 915     return 1;
 916 }
 917
 918 static int solve_update_flags(game_state *state)
 919 {
 920     int x, y, i, w = state->p.w, h = state->p.h, did = 0;
 921
 922     for (x = 0; x < w; x++) {
 923         for (y = 0; y < h; y++) {
 924             /* If a square is NOTRACK, all four edges must be. */
 925             if (state->sflags[y*w + x] & S_NOTRACK) {
 926                 for (i = 0; i < 4; i++) {
 927                     unsigned int d = 1<<i;
 928                     did += solve_set_eflag(state, x, y, d, E_NOTRACK, "edges around NOTRACK");
 929                 }
 930             }
 931
 932             /* If 3 or more edges around a square are NOTRACK, the square is. */
 933             if (S_E_COUNT(state, x, y, E_NOTRACK) >= 3) {
 934                 did += solve_set_sflag(state, x, y, S_NOTRACK, "square has >2 NOTRACK edges");
 935             }
 936
 937             /* If any edge around a square is TRACK, the square is. */
 938             if (S_E_COUNT(state, x, y, E_TRACK) > 0) {
 939                 did += solve_set_sflag(state, x, y, S_TRACK, "square has TRACK edge");
 940             }
 941
 942             /* If a square is TRACK and 2 edges are NOTRACK,
 943                the other two edges must be TRACK. */
 944             if ((state->sflags[y*w + x] & S_TRACK) &&
 945                     (S_E_COUNT(state, x, y, E_NOTRACK) == 2) &&
 946                     (S_E_COUNT(state, x, y, E_TRACK) < 2)) {
 947                 for (i = 0; i < 4; i++) {
 948                     unsigned int d = 1<<i;
 949                     if (!(S_E_FLAGS(state, x, y, d) & (E_TRACK|E_NOTRACK))) {
 950                         did += solve_set_eflag(state, x, y, d, E_TRACK,
 951                                                "TRACK square/2 NOTRACK edges");
 952                     }
 953                 }
 954             }
 955
 956             /* If a square is TRACK and 2 edges are TRACK, the other two
 957                must be NOTRACK. */
 958             if ((state->sflags[y*w + x] & S_TRACK) &&
 959                     (S_E_COUNT(state, x, y, E_TRACK) == 2) &&
 960                     (S_E_COUNT(state, x, y, E_NOTRACK) < 2)) {
 961                 for (i = 0; i < 4; i++) {
 962                     unsigned int d = 1<<i;
 963                     if (!(S_E_FLAGS(state, x, y, d) & (E_TRACK|E_NOTRACK))) {
 964                         did += solve_set_eflag(state, x, y, d, E_NOTRACK,
 965                                                "TRACK square/2 TRACK edges");
 966                     }
 967                 }
 968             }
 969         }
 970     }
 971     return did;
 972 }
 973
 974 static int solve_count_col(game_state *state, int col, unsigned int f)
 975 {
 976     int i, n, c = 0, h = state->p.h, w = state->p.w;
 977     for (n = 0, i = col; n < h; n++, i += w) {
 978         if (state->sflags[i] & f) c++;
 979     }
 980     return c;
 981 }
 982
 983 static int solve_count_row(game_state *state, int row, unsigned int f)
 984 {
 985     int i, n, c = 0, w = state->p.w;
 986     for (n = 0, i = w*row; n < state->p.w; n++, i++) {
 987         if (state->sflags[i] & f) c++;
 988     }
 989     return c;
 990 }
 991
 992 static int solve_count_clues_sub(game_state *state, int si, int id, int n,
 993                                  int target, const char *what)
 994 {
 995     int ctrack = 0, cnotrack = 0, did = 0, j, i, w = state->p.w;
 996
 997     for (j = 0, i = si; j < n; j++, i += id) {
 998         if (state->sflags[i] & S_TRACK)
 999             ctrack++;
1000         if (state->sflags[i] & S_NOTRACK)
1001             cnotrack++;
1002     }
1003     if (ctrack == target) {
1004         /* everything that's not S_TRACK must be S_NOTRACK. */
1005         for (j = 0, i = si; j < n; j++, i += id) {
1006             if (!(state->sflags[i] & S_TRACK))
1007                 did += solve_set_sflag(state, i%w, i/w, S_NOTRACK, what);
1008         }
1009     }
1010     if (cnotrack == (n-target)) {
1011         /* everything that's not S_NOTRACK must be S_TRACK. */
1012         for (j = 0, i = si; j < n; j++, i += id) {
1013             if (!(state->sflags[i] & S_NOTRACK))
1014                 did += solve_set_sflag(state, i%w, i/w, S_TRACK, what);
1015         }
1016     }
1017     return did;
1018 }
1019
1020 static int solve_count_clues(game_state *state)
1021 {
1022     int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1023
1024     for (x = 0; x < w; x++) {
1025         target = state->numbers->numbers[x];
1026         did += solve_count_clues_sub(state, x, w, h, target, "col count");
1027     }
1028     for (y = 0; y < h; y++) {
1029         target = state->numbers->numbers[w+y];
1030         did += solve_count_clues_sub(state, y*w, 1, w, target, "row count");
1031     }
1032     return did;
1033 }
1034
1035 static int solve_check_single_sub(game_state *state, int si, int id, int n,
1036                                   int target, unsigned int perpf,
1037                                   const char *what)
1038 {
1039     int ctrack = 0, nperp = 0, did = 0, j, i, w = state->p.w;
1040     int n1edge = 0, i1edge = 0, ox, oy, x, y;
1041     unsigned int impossible = 0;
1042
1043     /* For rows or columns which only have one more square to put a track in, we
1044        know the only way a new track section could be there would be to run
1045        perpendicular to the track (otherwise we'd need at least two free squares).
1046        So, if there is nowhere we can run perpendicular to the track (e.g. because
1047        we're on an edge) we know the extra track section much be on one end of an
1048        existing section. */
1049
1050     for (j = 0, i = si; j < n; j++, i += id) {
1051         if (state->sflags[i] & S_TRACK)
1052             ctrack++;
1053         impossible = S_E_DIRS(state, i%w, i/w, E_NOTRACK);
1054         if ((perpf & impossible) == 0)
1055             nperp++;
1056         if (S_E_COUNT(state, i%w, i/w, E_TRACK) <= 1) {
1057             n1edge++;
1058             i1edge = i;
1059         }
1060     }
1061     if (ctrack != (target-1)) return 0;
1062     if (nperp > 0 || n1edge != 1) return 0;
1063
1064     debug(("check_single from (%d,%d): 1 match from (%d,%d)",
1065            si%w, si/w, i1edge%w, i1edge/w));
1066
1067     /* We have a match: anything that's more than 1 away from this square
1068        cannot now contain a track. */
1069     ox = i1edge%w;
1070     oy = i1edge/w;
1071     for (j = 0, i = si; j < n; j++, i += id) {
1072         x = i%w;
1073         y = i/w;
1074         if (abs(ox-x) > 1 || abs(oy-y) > 1) {
1075             if (!state->sflags[i] & S_TRACK)
1076                 did += solve_set_sflag(state, x, y, S_NOTRACK, what);
1077         }
1078     }
1079
1080     return did;
1081 }
1082
1083 static int solve_check_single(game_state *state)
1084 {
1085     int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1086
1087     for (x = 0; x < w; x++) {
1088         target = state->numbers->numbers[x];
1089         did += solve_check_single_sub(state, x, w, h, target, R|L, "single on col");
1090     }
1091     for (y = 0; y < h; y++) {
1092         target = state->numbers->numbers[w+y];
1093         did += solve_check_single_sub(state, y*w, 1, w, target, U|D, "single on row");
1094     }
1095     return did;
1096 }
1097
1098 static int solve_check_loose_sub(game_state *state, int si, int id, int n,
1099                                  int target, unsigned int perpf,
1100                                  const char *what)
1101 {
1102     int nperp = 0, nloose = 0, e2count = 0, did = 0, i, j, k;
1103     int w = state->p.w;
1104     unsigned int parf = ALLDIR & (~perpf);
1105
1106     for (j = 0, i = si; j < n; j++, i += id) {
1107         int fcount = S_E_COUNT(state, i%w, i/w, E_TRACK);
1108         if (fcount == 2)
1109             e2count++; /* this cell has 2 definite edges */
1110         state->sflags[i] &= ~S_MARK;
1111         if (fcount == 1 && (parf & S_E_DIRS(state, i%w, i/w, E_TRACK))) {
1112             nloose++; /* this cell has a loose end (single flag set parallel
1113                     to the direction of this row/column) */
1114             state->sflags[i] |= S_MARK; /* mark loose ends */
1115         }
1116         if (fcount != 2 && !(perpf & S_E_DIRS(state, i%w, i/w, E_NOTRACK)))
1117             nperp++; /* we could lay perpendicular across this cell */
1118     }
1119
1120     if (nloose > (target - e2count)) {
1121         debug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE",
1122                what, si%w, si/w, nloose, target-e2count));
1123         state->impossible = TRUE;
1124     }
1125     if (nloose > 0 && nloose == (target - e2count)) {
1126         debug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.",
1127                what, si%w, si/w, nloose));
1128         for (j = 0, i = si; j < n; j++, i += id) {
1129             if (!(state->sflags[i] & S_MARK))
1130                 continue; /* skip non-loose ends */
1131             if (j > 0 && state->sflags[i-id] & S_MARK)
1132                 continue; /* next to other loose end, could join up */
1133             if (j < (n-1) && state->sflags[i+id] & S_MARK)
1134                 continue; /* ditto */
1135
1136             for (k = 0; k < 4; k++) {
1137                 if ((parf & (1<<k)) &&
1138                         !(S_E_DIRS(state, i%w, i/w, E_TRACK) & (1<<k))) {
1139                     /* set as NOTRACK the edge parallel to the row/column that's
1140                        not already set. */
1141                     did += solve_set_eflag(state, i%w, i/w, 1<<k, E_NOTRACK, what);
1142                 }
1143             }
1144         }
1145     }
1146     if (nloose == 1 && (target - e2count) == 2 && nperp == 0) {
1147         debug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel",
1148                what, si%w, si/w));
1149         for (j = 0, i = si; j < n; j++, i += id) {
1150             if (!(state->sflags[i] & S_MARK))
1151                 continue; /* skip non-loose ends */
1152             for (k = 0; k < 4; k++) {
1153                 if (parf & (1<<k))
1154                     did += solve_set_eflag(state, i%w, i/w, 1<<k, E_TRACK, what);
1155             }
1156         }
1157     }
1158
1159     return did;
1160 }
1161
1162 static int solve_check_loose_ends(game_state *state)
1163 {
1164     int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1165
1166     for (x = 0; x < w; x++) {
1167         target = state->numbers->numbers[x];
1168         did += solve_check_loose_sub(state, x, w, h, target, R|L, "loose on col");
1169     }
1170     for (y = 0; y < h; y++) {
1171         target = state->numbers->numbers[w+y];
1172         did += solve_check_loose_sub(state, y*w, 1, w, target, U|D, "loose on row");
1173     }
1174     return did;
1175 }
1176
1177 static int solve_check_loop_sub(game_state *state, int x, int y, int dir,
1178                                 int *dsf, int startc, int endc)
1179 {
1180     int w = state->p.w, h = state->p.h, i = y*w+x, j, k, satisfied = 1;
1181
1182     j = (y+DY(dir))*w + (x+DX(dir));
1183
1184     assert(i < w*h && j < w*h);
1185
1186     if ((state->sflags[i] & S_TRACK) &&
1187         (state->sflags[j] & S_TRACK) &&
1188         !(S_E_DIRS(state, x, y, E_TRACK) & dir) &&
1189         !(S_E_DIRS(state, x, y, E_NOTRACK) & dir)) {
1190         int ic = dsf_canonify(dsf, i), jc = dsf_canonify(dsf, j);
1191         if (ic == jc) {
1192             return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop");
1193         }
1194         if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) {
1195             debug(("Adding link at (%d,%d) would join start to end", x, y));
1196             /* We mustn't join the start to the end if:
1197                - there are other bits of track that aren't attached to either end
1198                - the clues are not fully satisfied yet
1199              */
1200             for (k = 0; k < w*h; k++) {
1201                 if (state->sflags[k] & S_TRACK &&
1202                         dsf_canonify(dsf, k) != startc && dsf_canonify(dsf, k) != endc) {
1203                     return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1204                                            "joins start to end but misses tracks");
1205                 }
1206             }
1207             for (k = 0; k < w; k++) {
1208                 int target = state->numbers->numbers[k];
1209                 int ntracks = solve_count_col(state, k, S_TRACK);
1210                 if (ntracks < target) satisfied = 0;
1211             }
1212             for (k = 0; k < h; k++) {
1213                 int target = state->numbers->numbers[w+k];
1214                 int ntracks = solve_count_row(state, k, S_TRACK);
1215                 if (ntracks < target) satisfied = 0;
1216             }
1217             if (!satisfied) {
1218                 return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1219                                        "joins start to end with incomplete clues");
1220             }
1221         }
1222     }
1223     return 0;
1224 }
1225
1226 static int solve_check_loop(game_state *state)
1227 {
1228     int w = state->p.w, h = state->p.h, x, y, i, j, did = 0;
1229     int *dsf, startc, endc;
1230
1231     /* TODO eventually we should pull this out into a solver struct and keep it
1232        updated as we connect squares. For now we recreate it every time we try
1233        this particular solver step. */
1234     dsf = snewn(w*h, int);
1235     dsf_init(dsf, w*h);
1236
1237     /* Work out the connectedness of the current loop set. */
1238     for (x = 0; x < w; x++) {
1239         for (y = 0; y < h; y++) {
1240             i = y*w + x;
1241             if (x < (w-1) && S_E_DIRS(state, x, y, E_TRACK) & R) {
1242                 /* connection to the right... */
1243                 j = y*w + (x+1);
1244                 assert(i < w*h && j < w*h);
1245                 dsf_merge(dsf, i, j);
1246             }
1247             if (y < (h-1) && S_E_DIRS(state, x, y, E_TRACK) & D) {
1248                 /* connection down... */
1249                 j = (y+1)*w + x;
1250                 assert(i < w*h && j < w*h);
1251                 dsf_merge(dsf, i, j);
1252             }
1253             /* NB no need to check up and left because they'll have been checked
1254                by the other side. */
1255         }
1256     }
1257
1258     startc = dsf_canonify(dsf, state->numbers->row_s*w);
1259     endc = dsf_canonify(dsf, (h-1)*w+state->numbers->col_s);
1260
1261     /* Now look at all adjacent squares that are both S_TRACK: if connecting
1262        any of them would complete a loop (i.e. they're both the same dsf class
1263        already) then that edge must be NOTRACK. */
1264     for (x = 0; x < w; x++) {
1265         for (y = 0; y < h; y++) {
1266             if (x < (w-1))
1267               did += solve_check_loop_sub(state, x, y, R, dsf, startc, endc);
1268             if (y < (h-1))
1269               did += solve_check_loop_sub(state, x, y, D, dsf, startc, endc);
1270         }
1271     }
1272
1273     sfree(dsf);
1274
1275     return did;
1276 }
1277
1278 static void solve_discount_edge(game_state *state, int x, int y, int d)
1279 {
1280     if (S_E_DIRS(state, x, y, E_TRACK) & d) {
1281         assert(state->sflags[y*state->p.w + x] & S_CLUE);
1282         return; /* (only) clue squares can have outer edges set. */
1283     }
1284     solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge");
1285 }
1286
1287 static int tracks_solve(game_state *state, int diff)
1288 {
1289     int didsth, x, y, w = state->p.w, h = state->p.h;
1290
1291     debug(("solve..."));
1292     state->impossible = FALSE;
1293
1294     /* Set all the outer border edges as no-track. */
1295     for (x = 0; x < w; x++) {
1296         solve_discount_edge(state, x, 0, U);
1297         solve_discount_edge(state, x, h-1, D);
1298     }
1299     for (y = 0; y < h; y++) {
1300         solve_discount_edge(state, 0, y, L);
1301         solve_discount_edge(state, w-1, y, R);
1302     }
1303
1304     while (1) {
1305         didsth = 0;
1306
1307         didsth += solve_update_flags(state);
1308         didsth += solve_count_clues(state);
1309         didsth += solve_check_loop(state);
1310
1311         if (diff >= DIFF_TRICKY) {
1312             didsth += solve_check_single(state);
1313             didsth += solve_check_loose_ends(state);
1314         }
1315
1316         if (!didsth || state->impossible) break;
1317     }
1318
1319     return state->impossible ? -1 : check_completion(state, FALSE) ? 1 : 0;
1320 }
1321
1322 static char *move_string_diff(const game_state *before, const game_state *after, int issolve)
1323 {
1324     int w = after->p.w, h = after->p.h, i, j;
1325     char *move = snewn(w*h*40, char), *p = move;
1326     const char *sep = "";
1327     unsigned int otf, ntf, onf, nnf;
1328
1329     if (issolve) {
1330         *p++ = 'S';
1331         sep = ";";
1332     }
1333     for (i = 0; i < w*h; i++) {
1334         otf = S_E_DIRS(before, i%w, i/w, E_TRACK);
1335         ntf = S_E_DIRS(after, i%w, i/w, E_TRACK);
1336         onf = S_E_DIRS(before, i%w, i/w, E_NOTRACK);
1337         nnf = S_E_DIRS(after, i%w, i/w, E_NOTRACK);
1338
1339         for (j = 0; j < 4; j++) {
1340             unsigned df = 1<<j;
1341             if ((otf & df) != (ntf & df)) {
1342                 p += sprintf(p, "%s%c%c%d,%d", sep,
1343                              (ntf & df) ? 'T' : 't', MOVECHAR(df), i%w, i/w);
1344                 sep = ";";
1345             }
1346             if ((onf & df) != (nnf & df)) {
1347                 p += sprintf(p, "%s%c%c%d,%d", sep,
1348                              (nnf & df) ? 'N' : 'n', MOVECHAR(df), i%w, i/w);
1349                 sep = ";";
1350             }
1351         }
1352
1353         if ((before->sflags[i] & S_NOTRACK) != (after->sflags[i] & S_NOTRACK)) {
1354             p += sprintf(p, "%s%cS%d,%d", sep,
1355                          (after->sflags[i] & S_NOTRACK) ? 'N' : 'n', i%w, i/w);
1356             sep = ";";
1357         }
1358         if ((before->sflags[i] & S_TRACK) != (after->sflags[i] & S_TRACK)) {
1359             p += sprintf(p, "%s%cS%d,%d", sep,
1360                          (after->sflags[i] & S_TRACK) ? 'T' : 't', i%w, i/w);
1361             sep = ";";
1362         }
1363     }
1364     *p++ = '\0';
1365     move = sresize(move, p - move, char);
1366
1367     return move;
1368 }
1369
1370 static char *solve_game(const game_state *state, const game_state *currstate,
1371                         const char *aux, char **error)
1372 {
1373     game_state *solved;
1374     int ret;
1375     char *move;
1376
1377     solved = dup_game(currstate);
1378     ret = tracks_solve(solved, DIFFCOUNT);
1379     if (ret < 1) {
1380         free_game(solved);
1381         solved = dup_game(state);
1382         ret = tracks_solve(solved, DIFFCOUNT);
1383     }
1384
1385     if (ret < 1) {
1386         *error = "Unable to find solution";
1387         move = NULL;
1388     } else {
1389         move = move_string_diff(currstate, solved, TRUE);
1390     }
1391
1392     free_game(solved);
1393     return move;
1394 }
1395
1396 static int game_can_format_as_text_now(const game_params *params)
1397 {
1398     return TRUE;
1399 }
1400
1401 static char *game_text_format(const game_state *state)
1402 {
1403     char *ret, *p;
1404     int x, y, len, w = state->p.w, h = state->p.h;
1405
1406     len = ((w*2) + 4) * ((h*2)+4) + 2;
1407     ret = snewn(len+1, char);
1408     p = ret;
1409
1410     /* top line: column clues */
1411     *p++ = ' ';
1412     *p++ = ' ';
1413     for (x = 0; x < w; x++) {
1414         *p++ = (state->numbers->numbers[x] < 10 ?
1415                 '0' + state->numbers->numbers[x] :
1416                 'A' + state->numbers->numbers[x] - 10);
1417         *p++ = ' ';
1418     }
1419     *p++ = '\n';
1420
1421     /* second line: top edge */
1422     *p++ = ' ';
1423     *p++ = '+';
1424     for (x = 0; x < w*2-1; x++)
1425         *p++ = '-';
1426     *p++ = '+';
1427     *p++ = '\n';
1428
1429     /* grid rows: one line of squares, one line of edges. */
1430     for (y = 0; y < h; y++) {
1431         /* grid square line */
1432         *p++ = (y == state->numbers->row_s) ? 'A' : ' ';
1433         *p++ = (y == state->numbers->row_s) ? '-' : '|';
1434
1435         for (x = 0; x < w; x++) {
1436             unsigned int f = S_E_DIRS(state, x, y, E_TRACK);
1437             if (state->sflags[y*w+x] & S_CLUE) *p++ = 'C';
1438             else if (f == LU || f == RD) *p++ = '/';
1439             else if (f == LD || f == RU) *p++ = '\\';
1440             else if (f == UD) *p++ = '|';
1441             else if (f == RL) *p++ = '-';
1442             else if (state->sflags[y*w+x] & S_NOTRACK) *p++ = 'x';
1443             else *p++ = ' ';
1444
1445             if (x < w-1) {
1446                 *p++ = (f & R) ? '-' : ' ';
1447             } else
1448                 *p++ = '|';
1449         }
1450         *p++ = (state->numbers->numbers[w+y] < 10 ?
1451                 '0' + state->numbers->numbers[w+y] :
1452                 'A' + state->numbers->numbers[w+y] - 10);
1453         *p++ = '\n';
1454
1455         if (y == h-1) continue;
1456
1457         /* edges line */
1458         *p++ = ' ';
1459         *p++ = '|';
1460         for (x = 0; x < w; x++) {
1461             unsigned int f = S_E_DIRS(state, x, y, E_TRACK);
1462             *p++ = (f & D) ? '|' : ' ';
1463             *p++ = (x < w-1) ? ' ' : '|';
1464         }
1465         *p++ = '\n';
1466     }
1467
1468     /* next line: bottom edge */
1469     *p++ = ' ';
1470     *p++ = '+';
1471     for (x = 0; x < w*2-1; x++)
1472         *p++ = (x == state->numbers->col_s*2) ? '|' : '-';
1473     *p++ = '+';
1474     *p++ = '\n';
1475
1476     /* final line: bottom clue */
1477     *p++ = ' ';
1478     *p++ = ' ';
1479     for (x = 0; x < w*2-1; x++)
1480         *p++ = (x == state->numbers->col_s*2) ? 'B' : ' ';
1481     *p++ = '\n';
1482
1483     *p = '\0';
1484     return ret;
1485 }
1486
1487 static void debug_state(game_state *state, const char *what) {
1488     char *sstring = game_text_format(state);
1489     debug(("%s: %s", what, sstring));
1490     sfree(sstring);
1491 }
1492
1493 static void dsf_update_completion(game_state *state, int *loopclass,
1494                                   int ax, int ay, char dir,
1495                                   int *dsf)
1496 {
1497     int w = state->p.w, ai = ay*w+ax, bx, by, bi, ac, bc;
1498
1499     if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return;
1500     bx = ax + DX(dir);
1501     by = ay + DY(dir);
1502
1503     if (!INGRID(state, bx, by)) return;
1504     bi = by*w+bx;
1505
1506     ac = dsf_canonify(dsf, ai);
1507     bc = dsf_canonify(dsf, bi);
1508
1509     if (ac == bc) {
1510         /* loop detected */
1511         *loopclass = ac;
1512     } else {
1513         dsf_merge(dsf, ai, bi);
1514     }
1515 }
1516
1517 static int check_completion(game_state *state, int mark)
1518 {
1519     int w = state->p.w, h = state->p.h, x, y, i, target, ret = TRUE;
1520     int ntrack, nnotrack, ntrackcomplete;
1521     int *dsf, loopclass, pathclass;
1522
1523     if (mark) {
1524         for (i = 0; i < w+h; i++) {
1525             state->num_errors[i] = 0;
1526         }
1527         for (i = 0; i < w*h; i++) {
1528             state->sflags[i] &= ~S_ERROR;
1529             if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0) {
1530                 if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 2)
1531                     state->sflags[i] |= S_ERROR;
1532             }
1533         }
1534     }
1535
1536     /* A cell is 'complete', for the purposes of marking the game as
1537      * finished, if it has two edges marked as TRACK. But it only has
1538      * to have one edge marked as TRACK, or be filled in as trackful
1539      * without any specific edges known, to count towards checking
1540      * row/column clue errors. */
1541     for (x = 0; x < w; x++) {
1542         target = state->numbers->numbers[x];
1543         ntrack = nnotrack = ntrackcomplete = 0;
1544         for (y = 0; y < h; y++) {
1545             if (S_E_COUNT(state, x, y, E_TRACK) > 0 ||
1546                 state->sflags[y*w+x] & S_TRACK)
1547                 ntrack++;
1548             if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1549                 ntrackcomplete++;
1550             if (state->sflags[y*w+x] & S_NOTRACK)
1551                 nnotrack++;
1552         }
1553         if (mark) {
1554             if (ntrack > target || nnotrack > (h-target)) {
1555                 debug(("col %d error: target %d, track %d, notrack %d",
1556                        x, target, ntrack, nnotrack));
1557                 state->num_errors[x] = 1;
1558             }
1559         }
1560         if (ntrackcomplete != target)
1561             ret = FALSE;
1562     }
1563     for (y = 0; y < h; y++) {
1564         target = state->numbers->numbers[w+y];
1565         ntrack = nnotrack = ntrackcomplete = 0;
1566         for (x = 0; x < w; x++) {
1567             if (S_E_COUNT(state, x, y, E_TRACK) > 0 ||
1568                 state->sflags[y*w+x] & S_TRACK)
1569                 ntrack++;
1570             if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1571                 ntrackcomplete++;
1572             if (state->sflags[y*w+x] & S_NOTRACK)
1573                 nnotrack++;
1574         }
1575         if (mark) {
1576             if (ntrack > target || nnotrack > (w-target)) {
1577                 debug(("row %d error: target %d, track %d, notrack %d",
1578                        y, target, ntrack, nnotrack));
1579                 state->num_errors[w+y] = 1;
1580             }
1581         }
1582         if (ntrackcomplete != target)
1583             ret = FALSE;
1584     }
1585
1586     dsf = snewn(w*h, int);
1587     dsf_init(dsf, w*h);
1588     loopclass = -1;
1589
1590     for (x = 0; x < w; x++) {
1591         for (y = 0; y < h; y++) {
1592             dsf_update_completion(state, &loopclass, x, y, R, dsf);
1593             dsf_update_completion(state, &loopclass, x, y, D, dsf);
1594         }
1595     }
1596     if (loopclass != -1) {
1597         debug(("loop detected, not complete"));
1598         ret = FALSE; /* no loop allowed */
1599         if (mark) {
1600             for (x = 0; x < w; x++) {
1601                 for (y = 0; y < h; y++) {
1602                     /* TODO this will only highlight the first loop found */
1603                     if (dsf_canonify(dsf, y*w + x) == loopclass) {
1604                         state->sflags[y*w+x] |= S_ERROR;
1605                     }
1606                 }
1607             }
1608         }
1609     }
1610     if (mark) {
1611         pathclass = dsf_canonify(dsf, state->numbers->row_s*w);
1612         if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) {
1613             /* We have a continuous path between the entrance and the exit: any
1614                other path must be in error. */
1615             for (i = 0; i < w*h; i++) {
1616                 if ((dsf_canonify(dsf, i) != pathclass) &&
1617                     ((state->sflags[i] & S_TRACK) ||
1618                      (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0)))
1619                     state->sflags[i] |= S_ERROR;
1620             }
1621         }
1622     }
1623
1624     if (mark)
1625         state->completed = ret;
1626     sfree(dsf);
1627     return ret;
1628 }
1629
1630 /* Code borrowed from Pearl. */
1631
1632 struct game_ui {
1633     int dragging, clearing, notrack;
1634     int drag_sx, drag_sy, drag_ex, drag_ey; /* drag start and end grid coords */
1635     int clickx, clicky;    /* pixel position of initial click */
1636
1637     int curx, cury;        /* grid position of keyboard cursor; uses half-size grid */
1638     int cursor_active;     /* TRUE iff cursor is shown */
1639 };
1640
1641 static game_ui *new_ui(const game_state *state)
1642 {
1643     game_ui *ui = snew(game_ui);
1644
1645     ui->clearing = ui->notrack = ui->dragging = 0;
1646     ui->drag_sx = ui->drag_sy = ui->drag_ex = ui->drag_ey = -1;
1647     ui->cursor_active = FALSE;
1648     ui->curx = ui->cury = 1;
1649
1650     return ui;
1651 }
1652
1653 static void free_ui(game_ui *ui)
1654 {
1655     sfree(ui);
1656 }
1657
1658 static char *encode_ui(const game_ui *ui)
1659 {
1660     return NULL;
1661 }
1662
1663 static void decode_ui(game_ui *ui, const char *encoding)
1664 {
1665 }
1666
1667 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1668                                const game_state *newstate)
1669 {
1670 }
1671
1672 #define PREFERRED_TILE_SIZE 30
1673 #define HALFSZ (ds->sz6*3)
1674 #define THIRDSZ (ds->sz6*2)
1675 #define TILE_SIZE (ds->sz6*6)
1676
1677 #define BORDER (TILE_SIZE/8)
1678 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1679
1680 #define COORD(x) ( (x+1) * TILE_SIZE + BORDER )
1681 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1682 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) - 1 )
1683
1684 #define DS_DSHIFT 4     /* R/U/L/D shift, for drag-in-progress flags */
1685
1686 #define DS_ERROR (1 << 8)
1687 #define DS_CLUE (1 << 9)
1688 #define DS_NOTRACK (1 << 10)
1689 #define DS_FLASH (1 << 11)
1690 #define DS_CURSOR (1 << 12) /* cursor in square (centre, or on edge) */
1691 #define DS_TRACK (1 << 13)
1692 #define DS_CLEARING (1 << 14)
1693
1694 #define DS_NSHIFT 16    /* R/U/L/D shift, for no-track edge flags */
1695 #define DS_CSHIFT 20    /* R/U/L/D shift, for cursor-on-edge */
1696
1697 struct game_drawstate {
1698     int sz6;
1699     int started;
1700
1701     int w, h, sz;
1702     unsigned int *flags, *flags_drag;
1703     int *num_errors;
1704 };
1705
1706 static void update_ui_drag(const game_state *state, game_ui *ui, int gx, int gy)
1707 {
1708     int w = state->p.w, h = state->p.h;
1709     int dx = abs(ui->drag_sx - gx), dy = abs(ui->drag_sy - gy);
1710
1711     if (dy == 0) {
1712         ui->drag_ex = gx < 0 ? 0 : gx >= w ? w-1 : gx;
1713         ui->drag_ey = ui->drag_sy;
1714         ui->dragging = TRUE;
1715     } else if (dx == 0) {
1716         ui->drag_ex = ui->drag_sx;
1717         ui->drag_ey = gy < 0 ? 0 : gy >= h ? h-1 : gy;
1718         ui->dragging = TRUE;
1719     } else {
1720         ui->drag_ex = ui->drag_sx;
1721         ui->drag_ey = ui->drag_sy;
1722         ui->dragging = FALSE;
1723     }
1724 }
1725
1726 static int ui_can_flip_edge(const game_state *state, int x, int y, int dir,
1727                             int notrack)
1728 {
1729     int w = state->p.w /*, h = state->shared->h, sz = state->shared->sz */;
1730     int x2 = x + DX(dir);
1731     int y2 = y + DY(dir);
1732     unsigned int sf1, sf2, ef;
1733
1734     if (!INGRID(state, x, y) || !INGRID(state, x2, y2))
1735         return FALSE;
1736
1737     sf1 = state->sflags[y*w + x];
1738     sf2 = state->sflags[y2*w + x2];
1739     if ( !notrack && ((sf1 & S_CLUE) || (sf2 & S_CLUE)) )
1740         return FALSE;
1741
1742     ef = S_E_FLAGS(state, x, y, dir);
1743     if (notrack) {
1744       /* if we're going to _set_ NOTRACK (i.e. the flag is currently unset),
1745          make sure the edge is not already set to TRACK. The adjacent squares
1746          could be set to TRACK, because we don't know which edges the general
1747          square setting refers to. */
1748       if (!(ef & E_NOTRACK) && (ef & E_TRACK))
1749           return FALSE;
1750     } else {
1751       if (!(ef & E_TRACK)) {
1752           /* if we're going to _set_ TRACK, make sure neither adjacent square nor
1753              the edge itself is already set to NOTRACK. */
1754           if ((sf1 & S_NOTRACK) || (sf2 & S_NOTRACK) || (ef & E_NOTRACK))
1755               return FALSE;
1756           /* if we're going to _set_ TRACK, make sure neither adjacent square has
1757              2 track flags already.  */
1758           if ((S_E_COUNT(state, x, y, E_TRACK) >= 2) ||
1759               (S_E_COUNT(state, x2, y2, E_TRACK) >= 2))
1760               return FALSE;
1761           }
1762     }
1763     return TRUE;
1764 }
1765
1766 static int ui_can_flip_square(const game_state *state, int x, int y, int notrack)
1767 {
1768     int w = state->p.w, trackc;
1769     unsigned sf;
1770
1771     if (!INGRID(state, x, y)) return FALSE;
1772     sf = state->sflags[y*w+x];
1773     trackc = S_E_COUNT(state, x, y, E_TRACK);
1774
1775     if (sf & S_CLUE) return FALSE;
1776
1777     if (notrack) {
1778         /* If we're setting S_NOTRACK, we cannot have either S_TRACK or any E_TRACK. */
1779         if (!(sf & S_NOTRACK) && ((sf & S_TRACK) || (trackc > 0)))
1780             return FALSE;
1781     } else {
1782         /* If we're setting S_TRACK, we cannot have any S_NOTRACK (we could have
1783           E_NOTRACK, though, because one or two wouldn't rule out a track) */
1784         if (!(sf & S_TRACK) && (sf & S_NOTRACK))
1785             return FALSE;
1786     }
1787     return TRUE;
1788 }
1789
1790 static char *edge_flip_str(const game_state *state, int x, int y, int dir, int notrack, char *buf) {
1791     unsigned ef = S_E_FLAGS(state, x, y, dir);
1792     char c;
1793
1794     if (notrack)
1795         c = (ef & E_NOTRACK) ? 'n' : 'N';
1796     else
1797         c = (ef & E_TRACK) ? 't' : 'T';
1798
1799     sprintf(buf, "%c%c%d,%d", c, MOVECHAR(dir), x, y);
1800     return dupstr(buf);
1801 }
1802
1803 static char *square_flip_str(const game_state *state, int x, int y, int notrack, char *buf) {
1804     unsigned f = state->sflags[y*state->p.w+x];
1805     char c;
1806
1807     if (notrack)
1808         c = (f & E_NOTRACK) ? 'n' : 'N';
1809     else
1810         c = (f & E_TRACK) ? 't' : 'T';
1811
1812     sprintf(buf, "%cS%d,%d", c, x, y);
1813     return dupstr(buf);
1814 }
1815
1816 #define SIGN(x) ((x<0) ? -1 : (x>0))
1817
1818 static game_state *copy_and_apply_drag(const game_state *state, const game_ui *ui)
1819 {
1820     game_state *after = dup_game(state);
1821     int x1, y1, x2, y2, x, y, w = state->p.w;
1822     unsigned f = ui->notrack ? S_NOTRACK : S_TRACK, ff;
1823
1824     x1 = min(ui->drag_sx, ui->drag_ex); x2 = max(ui->drag_sx, ui->drag_ex);
1825     y1 = min(ui->drag_sy, ui->drag_ey); y2 = max(ui->drag_sy, ui->drag_ey);
1826
1827     /* actually either x1 == x2, or y1 == y2, but it's easier just to code
1828        the nested loop. */
1829     for (x = x1; x <= x2; x++) {
1830         for (y = y1; y <= y2; y++) {
1831             ff = state->sflags[y*w+x];
1832             if (ui->clearing && !(ff & f))
1833                 continue; /* nothing to do, clearing and already clear */
1834             else if (!ui->clearing && (ff & f))
1835                 continue; /* nothing to do, setting and already set */
1836             else if (ui_can_flip_square(state, x, y, ui->notrack))
1837                 after->sflags[y*w+x] ^= f;
1838         }
1839     }
1840     return after;
1841 }
1842
1843 #define KEY_DIRECTION(btn) (\
1844     (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
1845     (btn) == CURSOR_LEFT ? L : R)
1846
1847 static char *interpret_move(const game_state *state, game_ui *ui,
1848                             const game_drawstate *ds,
1849                             int x, int y, int button)
1850 {
1851     int w = state->p.w, h = state->p.h, direction;
1852     int gx = FROMCOORD(x), gy = FROMCOORD(y);
1853     char tmpbuf[80];
1854
1855     /* --- mouse operations --- */
1856
1857     if (IS_MOUSE_DOWN(button)) {
1858         ui->cursor_active = FALSE;
1859         ui->dragging = FALSE;
1860
1861         if (!INGRID(state, gx, gy)) {
1862             /* can't drag from off grid */
1863             return NULL;
1864         }
1865
1866         if (button == RIGHT_BUTTON) {
1867             ui->notrack = TRUE;
1868             ui->clearing = state->sflags[gy*w+gx] & S_NOTRACK;
1869         } else {
1870             ui->notrack = FALSE;
1871             ui->clearing = state->sflags[gy*w+gx] & S_TRACK;
1872         }
1873
1874         ui->clickx = x;
1875         ui->clicky = y;
1876         ui->drag_sx = ui->drag_ex = gx;
1877         ui->drag_sy = ui->drag_ey = gy;
1878
1879         return "";
1880     }
1881
1882     if (IS_MOUSE_DRAG(button)) {
1883         ui->cursor_active = FALSE;
1884         update_ui_drag(state, ui, gx, gy);
1885         return "";
1886     }
1887
1888     if (IS_MOUSE_RELEASE(button)) {
1889         ui->cursor_active = FALSE;
1890         if (ui->dragging &&
1891             (ui->drag_sx != ui->drag_ex || ui->drag_sy != ui->drag_ey)) {
1892             game_state *dragged = copy_and_apply_drag(state, ui);
1893             char *ret = move_string_diff(state, dragged, FALSE);
1894
1895             ui->dragging = 0;
1896             free_game(dragged);
1897
1898             return ret;
1899         } else {
1900             int cx, cy;
1901
1902             /* We might still have been dragging (and just done a one-
1903              * square drag): cancel drag, so undo doesn't make it like
1904              * a drag-in-progress. */
1905             ui->dragging = 0;
1906
1907             /* Click (or tiny drag). Work out which edge we were
1908              * closest to. */
1909
1910             /*
1911              * We process clicks based on the mouse-down location,
1912              * because that's more natural for a user to carefully
1913              * control than the mouse-up.
1914              */
1915             x = ui->clickx;
1916             y = ui->clicky;
1917
1918             cx = CENTERED_COORD(gx);
1919             cy = CENTERED_COORD(gy);
1920
1921             if (!INGRID(state, gx, gy) || FROMCOORD(x) != gx || FROMCOORD(y) != gy)
1922                 return "";
1923
1924             if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
1925                 if (ui_can_flip_square(state, gx, gy, button == RIGHT_RELEASE))
1926                     return square_flip_str(state, gx, gy, button == RIGHT_RELEASE, tmpbuf);
1927                 return "";
1928             } else {
1929                 if (abs(x-cx) < abs(y-cy)) {
1930                     /* Closest to top/bottom edge. */
1931                     direction = (y < cy) ? U : D;
1932                 } else {
1933                     /* Closest to left/right edge. */
1934                     direction = (x < cx) ? L : R;
1935                 }
1936                 if (ui_can_flip_edge(state, gx, gy, direction,
1937                         button == RIGHT_RELEASE))
1938                     return edge_flip_str(state, gx, gy, direction,
1939                             button == RIGHT_RELEASE, tmpbuf);
1940                 else
1941                     return "";
1942             }
1943         }
1944     }
1945
1946     /* --- cursor/keyboard operations --- */
1947
1948     if (IS_CURSOR_MOVE(button)) {
1949         int dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1950         int dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP)    ? -1 : 0);
1951
1952         if (!ui->cursor_active) {
1953             ui->cursor_active = TRUE;
1954             return "";
1955         }
1956
1957         ui->curx = ui->curx + dx;
1958         ui->cury = ui->cury + dy;
1959         if ((ui->curx % 2 == 0) && (ui->cury % 2 == 0)) {
1960             /* disallow cursor on square corners: centres and edges only */
1961             ui->curx += dx; ui->cury += dy;
1962         }
1963         ui->curx = min(max(ui->curx, 1), 2*w-1);
1964         ui->cury = min(max(ui->cury, 1), 2*h-1);
1965         return "";
1966     }
1967
1968     if (IS_CURSOR_SELECT(button)) {
1969         if (!ui->cursor_active) {
1970             ui->cursor_active = TRUE;
1971             return "";
1972         }
1973         /* click on square corner does nothing (shouldn't get here) */
1974         if ((ui->curx % 2) == 0 && (ui->cury % 2 == 0))
1975             return "";
1976
1977         gx = ui->curx / 2;
1978         gy = ui->cury / 2;
1979         direction = ((ui->curx % 2) == 0) ? L : ((ui->cury % 2) == 0) ? U : 0;
1980
1981         if (direction &&
1982             ui_can_flip_edge(state, gx, gy, direction, button == CURSOR_SELECT2))
1983             return edge_flip_str(state, gx, gy, direction, button == CURSOR_SELECT2, tmpbuf);
1984         else if (!direction &&
1985                  ui_can_flip_square(state, gx, gy, button == CURSOR_SELECT2))
1986             return square_flip_str(state, gx, gy, button == CURSOR_SELECT2, tmpbuf);
1987         return "";
1988     }
1989
1990 #if 0
1991     /* helps to debug the solver */
1992     if (button == 'H' || button == 'h')
1993         return dupstr("H");
1994 #endif
1995
1996     return NULL;
1997 }
1998
1999 static game_state *execute_move(const game_state *state, const char *move)
2000 {
2001     int w = state->p.w, x, y, n, i;
2002     char c, d;
2003     unsigned f;
2004     game_state *ret = dup_game(state);
2005
2006     /* this is breaking the bank on GTK, which vsprintf's into a fixed-size buffer
2007      * which is 4096 bytes long. vsnprintf needs a feature-test macro to use, faff. */
2008     /*debug(("move: %s\n", move));*/
2009
2010     while (*move) {
2011         c = *move;
2012         if (c == 'S') {
2013             ret->used_solve = TRUE;
2014             move++;
2015         } else if (c == 'T' || c == 't' || c == 'N' || c == 'n') {
2016             /* set track, clear track; set notrack, clear notrack */
2017             move++;
2018             if (sscanf(move, "%c%d,%d%n", &d, &x, &y, &n) != 3)
2019                 goto badmove;
2020             if (!INGRID(state, x, y)) goto badmove;
2021
2022             f = (c == 'T' || c == 't') ? S_TRACK : S_NOTRACK;
2023
2024             if (d == 'S') {
2025                 if (c == 'T' || c == 'N')
2026                     ret->sflags[y*w+x] |= f;
2027                 else
2028                     ret->sflags[y*w+x] &= ~f;
2029             } else if (d == 'U' || d == 'D' || d == 'L' || d == 'R') {
2030                 for (i = 0; i < 4; i++) {
2031                     unsigned df = 1<<i;
2032
2033                     if (MOVECHAR(df) == d) {
2034                         if (c == 'T' || c == 'N')
2035                             S_E_SET(ret, x, y, df, f);
2036                         else
2037                             S_E_CLEAR(ret, x, y, df, f);
2038                     }
2039                 }
2040             } else
2041                 goto badmove;
2042             move += n;
2043         } else if (c == 'H') {
2044             tracks_solve(ret, DIFFCOUNT);
2045             move++;
2046         } else {
2047             goto badmove;
2048         }
2049         if (*move == ';')
2050             move++;
2051         else if (*move)
2052             goto badmove;
2053     }
2054
2055     check_completion(ret, TRUE);
2056
2057     return ret;
2058
2059     badmove:
2060     free_game(ret);
2061     return NULL;
2062 }
2063
2064 /* ----------------------------------------------------------------------
2065  * Drawing routines.
2066  */
2067
2068 #define FLASH_TIME 0.5F
2069
2070 static void game_compute_size(const game_params *params, int tilesize,
2071                               int *x, int *y)
2072 {
2073     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2074     struct {
2075         int sz6;
2076     } ads, *ds = &ads;
2077     ads.sz6 = tilesize/6;
2078
2079     *x = (params->w+2) * TILE_SIZE + 2 * BORDER;
2080     *y = (params->h+2) * TILE_SIZE + 2 * BORDER;
2081 }
2082
2083 static void game_set_size(drawing *dr, game_drawstate *ds,
2084                           const game_params *params, int tilesize)
2085 {
2086     ds->sz6 = tilesize/6;
2087 }
2088
2089 enum {
2090     COL_BACKGROUND, COL_LOWLIGHT, COL_HIGHLIGHT,
2091     COL_TRACK_BACKGROUND = COL_LOWLIGHT,
2092     COL_GRID, COL_CLUE, COL_CURSOR,
2093     COL_TRACK, COL_TRACK_CLUE, COL_SLEEPER,
2094     COL_DRAGON, COL_DRAGOFF,
2095     COL_ERROR, COL_FLASH,
2096     NCOLOURS
2097 };
2098
2099 static float *game_colours(frontend *fe, int *ncolours)
2100 {
2101     float *ret = snewn(3 * NCOLOURS, float);
2102     int i;
2103
2104     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2105
2106     for (i = 0; i < 3; i++) {
2107         ret[COL_TRACK_CLUE * 3 + i] = 0.0F;
2108         ret[COL_TRACK * 3 + i] = 0.5F;
2109         ret[COL_CLUE * 3 + i] = 0.0F;
2110         ret[COL_GRID * 3 + i] = 0.75F;
2111         ret[COL_CURSOR * 3 + i] = 0.6F;
2112     }
2113
2114     ret[COL_SLEEPER * 3 + 0] = 0.5F;
2115     ret[COL_SLEEPER * 3 + 1] = 0.4F;
2116     ret[COL_SLEEPER * 3 + 2] = 0.1F;
2117
2118     ret[COL_ERROR * 3 + 0] = 1.0F;
2119     ret[COL_ERROR * 3 + 1] = 0.0F;
2120     ret[COL_ERROR * 3 + 2] = 0.0F;
2121
2122     ret[COL_DRAGON * 3 + 0] = 0.0F;
2123     ret[COL_DRAGON * 3 + 1] = 0.0F;
2124     ret[COL_DRAGON * 3 + 2] = 1.0F;
2125
2126     ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2127     ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2128     ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2129
2130     ret[COL_FLASH * 3 + 0] = 1.0F;
2131     ret[COL_FLASH * 3 + 1] = 1.0F;
2132     ret[COL_FLASH * 3 + 2] = 1.0F;
2133
2134     *ncolours = NCOLOURS;
2135     return ret;
2136 }
2137
2138 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2139 {
2140     struct game_drawstate *ds = snew(struct game_drawstate);
2141     int i;
2142
2143     ds->sz6 = 0;
2144     ds->started = FALSE;
2145
2146     ds->w = state->p.w;
2147     ds->h = state->p.h;
2148     ds->sz = ds->w*ds->h;
2149     ds->flags = snewn(ds->sz, unsigned int);
2150     ds->flags_drag = snewn(ds->sz, unsigned int);
2151     for (i = 0; i < ds->sz; i++)
2152         ds->flags[i] = ds->flags_drag[i] = 0;
2153
2154     ds->num_errors = snewn(ds->w+ds->h, int);
2155     for (i = 0; i < ds->w+ds->h; i++)
2156         ds->num_errors[i] = 0;
2157
2158     return ds;
2159 }
2160
2161 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2162 {
2163     sfree(ds->flags);
2164     sfree(ds->flags_drag);
2165     sfree(ds->num_errors);
2166     sfree(ds);
2167 }
2168
2169 static void draw_circle_sleepers(drawing *dr, game_drawstate *ds,
2170                                  float cx, float cy, float r2, float thickness, int c)
2171 {
2172     float qr6 = (float)PI/12, qr3 = (float)PI/6, th, x1, y1, x2, y2;
2173     float t6 = THIRDSZ/2.0F, r1 = t6;
2174     int i;
2175
2176     for (i = 0; i < 12; i++) {
2177         th = qr6 + (i*qr3);
2178         x1 = r1*(float)cos(th);
2179         x2 = r2*(float)cos(th);
2180         y1 = r1*(float)sin(th);
2181         y2 = r2*(float)sin(th);
2182         draw_thick_line(dr, thickness, cx+x1, cy+y1, cx+x2, cy+y2, c);
2183     }
2184 }
2185
2186 static void draw_thick_circle_outline(drawing *dr, float thickness,
2187                                       float cx, float cy, float r,
2188                                       int colour)
2189 {
2190     float circ4 = 0.5F * (float)PI * r, ang, x1, y1, x2, y2;
2191     int i, nseg;
2192
2193     nseg = (int)(circ4 / 4.0F)*4; /* ensure a quarter-circle has a whole #segs */
2194     ang = 2.0F*(float)PI / nseg;
2195
2196     for (i = 0; i < nseg; i++) {
2197         float th = ang * i, th2 = ang * (i+1);
2198         x1 = cx + r*(float)cos(th);
2199         x2 = cx + r*(float)cos(th2);
2200         y1 = cy + r*(float)sin(th);
2201         y2 = cy + r*(float)sin(th2);
2202         debug(("circ outline: x=%.2f -> %.2f, thick=%.2f", x1, x2, thickness));
2203         draw_thick_line(dr, thickness, x1, y1, x2, y2, colour);
2204     }
2205 }
2206
2207 static void draw_tracks_specific(drawing *dr, game_drawstate *ds,
2208                                  int x, int y, unsigned int flags,
2209                                  int ctrack, int csleeper)
2210 {
2211     float ox = (float)COORD(x), oy = (float)COORD(y), cx, cy;
2212     float t1 = (float)TILE_SIZE, t3 = TILE_SIZE/3.0F, t6 = TILE_SIZE/6.0F;
2213     int d, i;
2214     float thick_track = TILE_SIZE/8.0F, thick_sleeper = TILE_SIZE/12.0F;
2215
2216     if (flags == LR) {
2217         for (i = 1; i <= 7; i+=2) {
2218             cx = ox + TILE_SIZE/8.0F*i;
2219             draw_thick_line(dr, thick_sleeper,
2220                             cx, oy+t6, cx, oy+t6+2*t3, csleeper);
2221         }
2222         draw_thick_line(dr, thick_track, ox, oy + t3, ox + TILE_SIZE, oy + t3, ctrack);
2223         draw_thick_line(dr, thick_track, ox, oy + 2*t3, ox + TILE_SIZE, oy + 2*t3, ctrack);
2224         return;
2225     }
2226     if (flags == UD) {
2227         for (i = 1; i <= 7; i+=2) {
2228             cy = oy + TILE_SIZE/8.0F*i;
2229             draw_thick_line(dr, thick_sleeper,
2230                             ox+t6, cy, ox+t6+2*t3, cy, csleeper);
2231         }
2232         debug(("vert line: x=%.2f, thick=%.2f", ox + t3, thick_track));
2233         draw_thick_line(dr, thick_track, ox + t3, oy, ox + t3, oy + TILE_SIZE, ctrack);
2234         draw_thick_line(dr, thick_track, ox + 2*t3, oy, ox + 2*t3, oy + TILE_SIZE, ctrack);
2235         return;
2236     }
2237     if (flags == UL || flags == DL || flags == UR || flags == DR) {
2238         cx = (flags & L) ? ox : ox + TILE_SIZE;
2239         cy = (flags & U) ? oy : oy + TILE_SIZE;
2240
2241         draw_circle_sleepers(dr, ds, cx, cy, (float)(5*t6), thick_sleeper, csleeper);
2242
2243         draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2244                                   2*t3, ctrack);
2245         draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2246                                   t3, ctrack);
2247
2248         return;
2249     }
2250
2251     for (d = 1; d < 16; d *= 2) {
2252         float ox1 = 0, ox2 = 0, oy1 = 0, oy2 = 0;
2253
2254         if (!(flags & d)) continue;
2255
2256         for (i = 1; i <= 2; i++) {
2257             if (d == L) {
2258                 ox1 = 0;
2259                 ox2 = thick_track;
2260                 oy1 = oy2 = i*t3;
2261             } else if (d == R) {
2262                 ox1 = t1;
2263                 ox2 = t1 - thick_track;
2264                 oy1 = oy2 = i*t3;
2265             } else if (d == U) {
2266                 ox1 = ox2 = i*t3;
2267                 oy1 = 0;
2268                 oy2 = thick_track;
2269             } else if (d == D) {
2270                 ox1 = ox2 = i*t3;
2271                 oy1 = t1;
2272                 oy2 = t1 - thick_track;
2273             }
2274             draw_thick_line(dr, thick_track, ox+ox1, oy+oy1, ox+ox2, oy+oy2, ctrack);
2275         }
2276     }
2277 }
2278
2279 static unsigned int best_bits(unsigned int flags, unsigned int flags_drag, int *col)
2280 {
2281     int nb_orig = nbits[flags & ALLDIR], nb_drag = nbits[flags_drag & ALLDIR];
2282
2283     if (nb_orig > nb_drag) {
2284         *col = COL_DRAGOFF;
2285         return flags & ALLDIR;
2286     } else if (nb_orig < nb_drag) {
2287         *col = COL_DRAGON;
2288         return flags_drag & ALLDIR;
2289     }
2290     return flags & ALLDIR; /* same number of bits: no special colour. */
2291 }
2292
2293 static void draw_square(drawing *dr, game_drawstate *ds,
2294                         int x, int y, unsigned int flags, unsigned int flags_drag)
2295 {
2296     int t2 = HALFSZ, t16 = HALFSZ/4, off;
2297     int ox = COORD(x), oy = COORD(y), cx = ox + t2, cy = oy + t2, d, c;
2298     int bg = (flags & DS_TRACK) ? COL_TRACK_BACKGROUND : COL_BACKGROUND;
2299     unsigned int flags_best;
2300
2301     assert(dr);
2302
2303     /* Clip to the grid square. */
2304     clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2305
2306     /* Clear the square. */
2307     best_bits((flags & DS_TRACK) == DS_TRACK,
2308               (flags_drag & DS_TRACK) == DS_TRACK, &bg);
2309     draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, bg);
2310
2311     /* Draw outline of grid square */
2312     draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID);
2313     draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID);
2314
2315     /* More outlines for clue squares. */
2316     if (flags & DS_CURSOR) {
2317         int curx, cury, curw, curh;
2318
2319         off = t16;
2320         curx = ox + off; cury = oy + off;
2321         curw = curh = TILE_SIZE - (2*off) + 1;
2322
2323         if (flags & (U << DS_CSHIFT)) {
2324             cury = oy - off; curh = 2*off + 1;
2325         } else if (flags & (D << DS_CSHIFT)) {
2326             cury = oy + TILE_SIZE - off; curh = 2*off + 1;
2327         } else if (flags & (L << DS_CSHIFT)) {
2328             curx = ox - off; curw = 2*off + 1;
2329         } else if (flags & (R << DS_CSHIFT)) {
2330             curx = ox + TILE_SIZE - off; curw = 2*off + 1;
2331         }
2332
2333         draw_rect_outline(dr, curx, cury, curw, curh, COL_GRID);
2334     }
2335
2336     /* Draw tracks themselves */
2337     c = (flags & DS_ERROR) ? COL_ERROR :
2338       (flags & DS_FLASH) ? COL_FLASH :
2339       (flags & DS_CLUE) ? COL_TRACK_CLUE : COL_TRACK;
2340     flags_best = best_bits(flags, flags_drag, &c);
2341     draw_tracks_specific(dr, ds, x, y, flags_best, c, COL_SLEEPER);
2342
2343     /* Draw no-track marks, if present, in square and on edges. */
2344     c = COL_TRACK;
2345     flags_best = best_bits((flags & DS_NOTRACK) == DS_NOTRACK,
2346                            (flags_drag & DS_NOTRACK) == DS_NOTRACK, &c);
2347     if (flags_best) {
2348         off = HALFSZ/2;
2349         draw_line(dr, cx - off, cy - off, cx + off, cy + off, c);
2350         draw_line(dr, cx - off, cy + off, cx + off, cy - off, c);
2351     }
2352
2353     c = COL_TRACK;
2354     flags_best = best_bits(flags >> DS_NSHIFT, flags_drag >> DS_NSHIFT, &c);
2355     for (d = 1; d < 16; d *= 2) {
2356         off = t16;
2357         cx = ox + t2;
2358         cy = oy + t2;
2359
2360         if (flags_best & d) {
2361             cx += (d == R) ? t2 : (d == L) ? -t2 : 0;
2362             cy += (d == D) ? t2 : (d == U) ? -t2 : 0;
2363
2364             draw_line(dr, cx - off, cy - off, cx + off, cy + off, c);
2365             draw_line(dr, cx - off, cy + off, cx + off, cy - off, c);
2366         }
2367     }
2368
2369     unclip(dr);
2370     draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2371 }
2372
2373 static void draw_clue(drawing *dr, game_drawstate *ds, int w, int clue, int i, int col)
2374 {
2375     int cx, cy, tsz = TILE_SIZE/2;
2376     char buf[20];
2377
2378     if (i < w) {
2379         cx = CENTERED_COORD(i);
2380         cy = CENTERED_COORD(-1);
2381     } else {
2382         cx = CENTERED_COORD(w);
2383         cy = CENTERED_COORD(i-w);
2384     }
2385
2386     draw_rect(dr, cx - tsz + BORDER, cy - tsz + BORDER,
2387               TILE_SIZE - BORDER, TILE_SIZE - BORDER, COL_BACKGROUND);
2388     sprintf(buf, "%d", clue);
2389     draw_text(dr, cx, cy, FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2390               col, buf);
2391     draw_update(dr, cx - tsz, cy - tsz, TILE_SIZE, TILE_SIZE);
2392 }
2393
2394 static void draw_loop_ends(drawing *dr, game_drawstate *ds,
2395                            const game_state *state, int c)
2396 {
2397     int tsz = TILE_SIZE/2;
2398
2399     draw_text(dr, CENTERED_COORD(-1), CENTERED_COORD(state->numbers->row_s),
2400               FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2401               c, "A");
2402
2403     draw_text(dr, CENTERED_COORD(state->numbers->col_s), CENTERED_COORD(state->p.h),
2404               FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2405               c, "B");
2406 }
2407
2408 static unsigned int s2d_flags(const game_state *state, int x, int y, const game_ui *ui)
2409 {
2410     unsigned int f;
2411     int w = state->p.w;
2412
2413     f = S_E_DIRS(state, x, y, E_TRACK);
2414     f |= (S_E_DIRS(state, x, y, E_NOTRACK) << DS_NSHIFT);
2415
2416     if (state->sflags[y*w+x] & S_ERROR)
2417         f |= DS_ERROR;
2418     if (state->sflags[y*w+x] & S_CLUE)
2419         f |= DS_CLUE;
2420     if (state->sflags[y*w+x] & S_NOTRACK)
2421         f |= DS_NOTRACK;
2422     if ((state->sflags[y*w+x] & S_TRACK) || (S_E_COUNT(state, x, y, E_TRACK) > 0))
2423         f |= DS_TRACK;
2424
2425     if (ui->cursor_active) {
2426         if (ui->curx >= x*2 && ui->curx <= (x+1)*2 &&
2427             ui->cury >= y*2 && ui->cury <= (y+1)*2) {
2428             f |= DS_CURSOR;
2429             if (ui->curx == x*2)        f |= (L << DS_CSHIFT);
2430             if (ui->curx == (x+1)*2)    f |= (R << DS_CSHIFT);
2431             if (ui->cury == y*2)        f |= (U << DS_CSHIFT);
2432             if (ui->cury == (y+1)*2)    f |= (D << DS_CSHIFT);
2433         }
2434     }
2435
2436     return f;
2437 }
2438
2439 static void game_redraw(drawing *dr, game_drawstate *ds, const game_state *oldstate,
2440                         const game_state *state, int dir, const game_ui *ui,
2441                         float animtime, float flashtime)
2442 {
2443     int i, x, y, force = 0, flashing = 0, w = ds->w, h = ds->h;
2444     game_state *drag_state = NULL;
2445
2446     if (!ds->started) {
2447         /*
2448          * The initial contents of the window are not guaranteed and
2449          * can vary with front ends. To be on the safe side, all games
2450          * should start by drawing a big background-colour rectangle
2451          * covering the whole window.
2452          */
2453         draw_rect(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER,
2454                   COL_BACKGROUND);
2455
2456         draw_loop_ends(dr, ds, state, COL_CLUE);
2457
2458         draw_line(dr, COORD(ds->w), COORD(0), COORD(ds->w), COORD(ds->h), COL_GRID);
2459         draw_line(dr, COORD(0), COORD(ds->h), COORD(ds->w), COORD(ds->h), COL_GRID);
2460
2461         draw_update(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER);
2462
2463         ds->started = TRUE;
2464         force = 1;
2465     }
2466
2467     for (i = 0; i < w+h; i++) {
2468         if (force || (state->num_errors[i] != ds->num_errors[i])) {
2469             ds->num_errors[i] = state->num_errors[i];
2470             draw_clue(dr, ds, w, state->numbers->numbers[i], i,
2471                       ds->num_errors[i] ? COL_ERROR : COL_CLUE);
2472         }
2473     }
2474
2475     if (flashtime > 0 &&
2476             (flashtime <= FLASH_TIME/3 ||
2477              flashtime >= FLASH_TIME*2/3))
2478         flashing = DS_FLASH;
2479
2480     if (ui->dragging)
2481         drag_state = copy_and_apply_drag(state, ui);
2482
2483     for (x = 0; x < w; x++) {
2484         for (y = 0; y < h; y++) {
2485             unsigned int f, f_d;
2486
2487             f = s2d_flags(state, x, y, ui) | flashing;
2488             f_d = drag_state ? s2d_flags(drag_state, x, y, ui) : f;
2489
2490             if (f != ds->flags[y*w+x] || f_d != ds->flags_drag[y*w+x] || force) {
2491                 ds->flags[y*w+x] = f;
2492                 ds->flags_drag[y*w+x] = f_d;
2493                 draw_square(dr, ds, x, y, f, f_d);
2494             }
2495         }
2496     }
2497
2498     if (drag_state) free_game(drag_state);
2499 }
2500
2501 static float game_anim_length(const game_state *oldstate, const game_state *newstate,
2502                               int dir, game_ui *ui)
2503 {
2504     return 0.0F;
2505 }
2506
2507 static float game_flash_length(const game_state *oldstate, const game_state *newstate,
2508                                int dir, game_ui *ui)
2509 {
2510     if (!oldstate->completed &&
2511             newstate->completed && !newstate->used_solve)
2512         return FLASH_TIME;
2513     else
2514         return 0.0F;
2515 }
2516
2517 static int game_status(const game_state *state)
2518 {
2519     return state->completed ? +1 : 0;
2520 }
2521
2522 static int game_timing_state(const game_state *state, game_ui *ui)
2523 {
2524     return TRUE;
2525 }
2526
2527 static void game_print_size(const game_params *params, float *x, float *y)
2528 {
2529     int pw, ph;
2530
2531     /* The Times uses 7mm squares */
2532     game_compute_size(params, 700, &pw, &ph);
2533     *x = pw / 100.0F;
2534     *y = ph / 100.0F;
2535 }
2536
2537 static void game_print(drawing *dr, const game_state *state, int tilesize)
2538 {
2539     int w = state->p.w, h = state->p.h;
2540     int black = print_mono_colour(dr, 0), grey = print_grey_colour(dr, 0.5F);
2541     int x, y, i;
2542
2543     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2544     game_drawstate ads, *ds = &ads;
2545     game_set_size(dr, ds, NULL, tilesize);
2546
2547     /* Grid, then border (second so it is on top) */
2548     print_line_width(dr, TILE_SIZE / 24);
2549     for (x = 1; x < w; x++)
2550         draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), grey);
2551     for (y = 1; y < h; y++)
2552         draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), grey);
2553
2554     print_line_width(dr, TILE_SIZE / 16);
2555     draw_rect_outline(dr, COORD(0), COORD(0), w*TILE_SIZE, h*TILE_SIZE, black);
2556
2557     print_line_width(dr, TILE_SIZE / 24);
2558
2559     /* clue numbers, and loop ends */
2560     for (i = 0; i < w+h; i++)
2561         draw_clue(dr, ds, w, state->numbers->numbers[i], i, black);
2562     draw_loop_ends(dr, ds, state, black);
2563
2564     /* clue tracks / solution */
2565     for (x = 0; x < w; x++) {
2566         for (y = 0; y < h; y++) {
2567             clip(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
2568             draw_tracks_specific(dr, ds, x, y, S_E_DIRS(state, x, y, E_TRACK),
2569                                  black, grey);
2570             unclip(dr);
2571         }
2572     }
2573 }
2574
2575 #ifdef COMBINED
2576 #define thegame tracks
2577 #endif
2578
2579 const struct game thegame = {
2580     "Train Tracks", "games.tracks", "tracks",
2581     default_params,
2582     game_fetch_preset,
2583     decode_params,
2584     encode_params,
2585     free_params,
2586     dup_params,
2587     TRUE, game_configure, custom_params,
2588     validate_params,
2589     new_game_desc,
2590     validate_desc,
2591     new_game,
2592     dup_game,
2593     free_game,
2594     TRUE, solve_game,
2595     TRUE, game_can_format_as_text_now, game_text_format,
2596     new_ui,
2597     free_ui,
2598     encode_ui,
2599     decode_ui,
2600     game_changed_state,
2601     interpret_move,
2602     execute_move,
2603     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2604     game_colours,
2605     game_new_drawstate,
2606     game_free_drawstate,
2607     game_redraw,
2608     game_anim_length,
2609     game_flash_length,
2610     game_status,
2611     TRUE, FALSE, game_print_size, game_print,
2612     FALSE,                             /* wants_statusbar */
2613     FALSE, game_timing_state,
2614     0,                                 /* flags */
2615 };
2616
2617 /* vim: set shiftwidth=4 tabstop=8: */