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;
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' if it has any edges marked as TRACK. */
1537     for (x = 0; x < w; x++) {
1538         target = state->numbers->numbers[x];
1539         ntrack = nnotrack = 0;
1540         for (y = 0; y < h; y++) {
1541             if (S_E_COUNT(state, x, y, E_TRACK) > 0)
1542                 ntrack++;
1543             if (state->sflags[y*w+x] & S_NOTRACK)
1544                 nnotrack++;
1545         }
1546         if (mark) {
1547             if (ntrack > target || nnotrack > (h-target)) {
1548                 debug(("col %d error: target %d, track %d, notrack %d",
1549                        x, target, ntrack, nnotrack));
1550                 state->num_errors[x] = 1;
1551             }
1552         }
1553         if (ntrack != target)
1554             ret = FALSE;
1555     }
1556     for (y = 0; y < h; y++) {
1557         target = state->numbers->numbers[w+y];
1558         ntrack = nnotrack = 0;
1559         for (x = 0; x < w; x++) {
1560             if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1561                 ntrack++;
1562             if (state->sflags[y*w+x] & S_NOTRACK)
1563                 nnotrack++;
1564         }
1565         if (mark) {
1566             if (ntrack > target || nnotrack > (w-target)) {
1567                 debug(("row %d error: target %d, track %d, notrack %d",
1568                        y, target, ntrack, nnotrack));
1569                 state->num_errors[w+y] = 1;
1570             }
1571         }
1572         if (ntrack != target)
1573             ret = FALSE;
1574     }
1575
1576     dsf = snewn(w*h, int);
1577     dsf_init(dsf, w*h);
1578     loopclass = -1;
1579
1580     for (x = 0; x < w; x++) {
1581         for (y = 0; y < h; y++) {
1582             dsf_update_completion(state, &loopclass, x, y, R, dsf);
1583             dsf_update_completion(state, &loopclass, x, y, D, dsf);
1584         }
1585     }
1586     if (loopclass != -1) {
1587         debug(("loop detected, not complete"));
1588         ret = FALSE; /* no loop allowed */
1589         if (mark) {
1590             for (x = 0; x < w; x++) {
1591                 for (y = 0; y < h; y++) {
1592                     /* TODO this will only highlight the first loop found */
1593                     if (dsf_canonify(dsf, y*w + x) == loopclass) {
1594                         state->sflags[y*w+x] |= S_ERROR;
1595                     }
1596                 }
1597             }
1598         }
1599     }
1600     if (mark) {
1601         pathclass = dsf_canonify(dsf, state->numbers->row_s*w);
1602         if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) {
1603             /* We have a continuous path between the entrance and the exit: any
1604                other path must be in error. */
1605             for (i = 0; i < w*h; i++) {
1606                 if ((dsf_canonify(dsf, i) != pathclass) &&
1607                     ((state->sflags[i] & S_TRACK) ||
1608                      (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0)))
1609                     state->sflags[i] |= S_ERROR;
1610             }
1611         }
1612     }
1613
1614     if (mark)
1615         state->completed = ret;
1616     sfree(dsf);
1617     return ret;
1618 }
1619
1620 /* Code borrowed from Pearl. */
1621
1622 struct game_ui {
1623     int dragging, clearing, notrack;
1624     int drag_sx, drag_sy, drag_ex, drag_ey; /* drag start and end grid coords */
1625     int clickx, clicky;    /* pixel position of initial click */
1626
1627     int curx, cury;        /* grid position of keyboard cursor; uses half-size grid */
1628     int cursor_active;     /* TRUE iff cursor is shown */
1629 };
1630
1631 static game_ui *new_ui(const game_state *state)
1632 {
1633     game_ui *ui = snew(game_ui);
1634
1635     ui->clearing = ui->notrack = ui->dragging = 0;
1636     ui->drag_sx = ui->drag_sy = ui->drag_ex = ui->drag_ey = -1;
1637     ui->cursor_active = FALSE;
1638     ui->curx = ui->cury = 1;
1639
1640     return ui;
1641 }
1642
1643 static void free_ui(game_ui *ui)
1644 {
1645     sfree(ui);
1646 }
1647
1648 static char *encode_ui(const game_ui *ui)
1649 {
1650     return NULL;
1651 }
1652
1653 static void decode_ui(game_ui *ui, const char *encoding)
1654 {
1655 }
1656
1657 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1658                                const game_state *newstate)
1659 {
1660 }
1661
1662 #define PREFERRED_TILE_SIZE 30
1663 #define HALFSZ (ds->sz6*3)
1664 #define THIRDSZ (ds->sz6*2)
1665 #define TILE_SIZE (ds->sz6*6)
1666
1667 #define BORDER (TILE_SIZE/8)
1668 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1669
1670 #define COORD(x) ( (x+1) * TILE_SIZE + BORDER )
1671 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1672 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) - 1 )
1673
1674 #define DS_DSHIFT 4     /* R/U/L/D shift, for drag-in-progress flags */
1675
1676 #define DS_ERROR (1 << 8)
1677 #define DS_CLUE (1 << 9)
1678 #define DS_NOTRACK (1 << 10)
1679 #define DS_FLASH (1 << 11)
1680 #define DS_CURSOR (1 << 12) /* cursor in square (centre, or on edge) */
1681 #define DS_TRACK (1 << 13)
1682 #define DS_CLEARING (1 << 14)
1683
1684 #define DS_NSHIFT 16    /* R/U/L/D shift, for no-track edge flags */
1685 #define DS_CSHIFT 20    /* R/U/L/D shift, for cursor-on-edge */
1686
1687 struct game_drawstate {
1688     int sz6;
1689     int started;
1690
1691     int w, h, sz;
1692     unsigned int *flags, *flags_drag;
1693     int *num_errors;
1694 };
1695
1696 static void update_ui_drag(const game_state *state, game_ui *ui, int gx, int gy)
1697 {
1698     int w = state->p.w, h = state->p.h;
1699     int dx = abs(ui->drag_sx - gx), dy = abs(ui->drag_sy - gy);
1700
1701     if (dy == 0) {
1702         ui->drag_ex = gx < 0 ? 0 : gx >= w ? w-1 : gx;
1703         ui->drag_ey = ui->drag_sy;
1704         ui->dragging = TRUE;
1705     } else if (dx == 0) {
1706         ui->drag_ex = ui->drag_sx;
1707         ui->drag_ey = gy < 0 ? 0 : gy >= h ? h-1 : gy;
1708         ui->dragging = TRUE;
1709     } else {
1710         ui->drag_ex = ui->drag_sx;
1711         ui->drag_ey = ui->drag_sy;
1712         ui->dragging = FALSE;
1713     }
1714 }
1715
1716 static int ui_can_flip_edge(const game_state *state, int x, int y, int dir,
1717                             int notrack)
1718 {
1719     int w = state->p.w /*, h = state->shared->h, sz = state->shared->sz */;
1720     int x2 = x + DX(dir);
1721     int y2 = y + DY(dir);
1722     unsigned int sf1, sf2, ef;
1723
1724     if (!INGRID(state, x, y) || !INGRID(state, x2, y2))
1725         return FALSE;
1726
1727     sf1 = state->sflags[y*w + x];
1728     sf2 = state->sflags[y2*w + x2];
1729     if ( !notrack && ((sf1 & S_CLUE) || (sf2 & S_CLUE)) )
1730         return FALSE;
1731
1732     ef = S_E_FLAGS(state, x, y, dir);
1733     if (notrack) {
1734       /* if we're going to _set_ NOTRACK (i.e. the flag is currently unset),
1735          make sure the edge is not already set to TRACK. The adjacent squares
1736          could be set to TRACK, because we don't know which edges the general
1737          square setting refers to. */
1738       if (!(ef & E_NOTRACK) && (ef & E_TRACK))
1739           return FALSE;
1740     } else {
1741       if (!(ef & E_TRACK)) {
1742           /* if we're going to _set_ TRACK, make sure neither adjacent square nor
1743              the edge itself is already set to NOTRACK. */
1744           if ((sf1 & S_NOTRACK) || (sf2 & S_NOTRACK) || (ef & E_NOTRACK))
1745               return FALSE;
1746           /* if we're going to _set_ TRACK, make sure neither adjacent square has
1747              2 track flags already.  */
1748           if ((S_E_COUNT(state, x, y, E_TRACK) >= 2) ||
1749               (S_E_COUNT(state, x2, y2, E_TRACK) >= 2))
1750               return FALSE;
1751           }
1752     }
1753     return TRUE;
1754 }
1755
1756 static int ui_can_flip_square(const game_state *state, int x, int y, int notrack)
1757 {
1758     int w = state->p.w, trackc;
1759     unsigned sf;
1760
1761     if (!INGRID(state, x, y)) return FALSE;
1762     sf = state->sflags[y*w+x];
1763     trackc = S_E_COUNT(state, x, y, E_TRACK);
1764
1765     if (sf & S_CLUE) return FALSE;
1766
1767     if (notrack) {
1768         /* If we're setting S_NOTRACK, we cannot have either S_TRACK or any E_TRACK. */
1769         if (!(sf & S_NOTRACK) && ((sf & S_TRACK) || (trackc > 0)))
1770             return FALSE;
1771     } else {
1772         /* If we're setting S_TRACK, we cannot have any S_NOTRACK (we could have
1773           E_NOTRACK, though, because one or two wouldn't rule out a track) */
1774         if (!(sf & S_TRACK) && (sf & S_NOTRACK))
1775             return FALSE;
1776     }
1777     return TRUE;
1778 }
1779
1780 static char *edge_flip_str(const game_state *state, int x, int y, int dir, int notrack, char *buf) {
1781     unsigned ef = S_E_FLAGS(state, x, y, dir);
1782     char c;
1783
1784     if (notrack)
1785         c = (ef & E_NOTRACK) ? 'n' : 'N';
1786     else
1787         c = (ef & E_TRACK) ? 't' : 'T';
1788
1789     sprintf(buf, "%c%c%d,%d", c, MOVECHAR(dir), x, y);
1790     return dupstr(buf);
1791 }
1792
1793 static char *square_flip_str(const game_state *state, int x, int y, int notrack, char *buf) {
1794     unsigned f = state->sflags[y*state->p.w+x];
1795     char c;
1796
1797     if (notrack)
1798         c = (f & E_NOTRACK) ? 'n' : 'N';
1799     else
1800         c = (f & E_TRACK) ? 't' : 'T';
1801
1802     sprintf(buf, "%cS%d,%d", c, x, y);
1803     return dupstr(buf);
1804 }
1805
1806 #define SIGN(x) ((x<0) ? -1 : (x>0))
1807
1808 static game_state *copy_and_apply_drag(const game_state *state, const game_ui *ui)
1809 {
1810     game_state *after = dup_game(state);
1811     int x1, y1, x2, y2, x, y, w = state->p.w;
1812     unsigned f = ui->notrack ? S_NOTRACK : S_TRACK, ff;
1813
1814     x1 = min(ui->drag_sx, ui->drag_ex); x2 = max(ui->drag_sx, ui->drag_ex);
1815     y1 = min(ui->drag_sy, ui->drag_ey); y2 = max(ui->drag_sy, ui->drag_ey);
1816
1817     /* actually either x1 == x2, or y1 == y2, but it's easier just to code
1818        the nested loop. */
1819     for (x = x1; x <= x2; x++) {
1820         for (y = y1; y <= y2; y++) {
1821             ff = state->sflags[y*w+x];
1822             if (ui->clearing && !(ff & f))
1823                 continue; /* nothing to do, clearing and already clear */
1824             else if (!ui->clearing && (ff & f))
1825                 continue; /* nothing to do, setting and already set */
1826             else if (ui_can_flip_square(state, x, y, ui->notrack))
1827                 after->sflags[y*w+x] ^= f;
1828         }
1829     }
1830     return after;
1831 }
1832
1833 #define KEY_DIRECTION(btn) (\
1834     (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
1835     (btn) == CURSOR_LEFT ? L : R)
1836
1837 static char *interpret_move(const game_state *state, game_ui *ui,
1838                             const game_drawstate *ds,
1839                             int x, int y, int button)
1840 {
1841     int w = state->p.w, h = state->p.h, direction;
1842     int gx = FROMCOORD(x), gy = FROMCOORD(y);
1843     char tmpbuf[80];
1844
1845     /* --- mouse operations --- */
1846
1847     if (IS_MOUSE_DOWN(button)) {
1848         ui->cursor_active = FALSE;
1849         ui->dragging = FALSE;
1850
1851         if (!INGRID(state, gx, gy)) {
1852             /* can't drag from off grid */
1853             return NULL;
1854         }
1855
1856         if (button == RIGHT_BUTTON) {
1857             ui->notrack = TRUE;
1858             ui->clearing = state->sflags[gy*w+gx] & S_NOTRACK;
1859         } else {
1860             ui->notrack = FALSE;
1861             ui->clearing = state->sflags[gy*w+gx] & S_TRACK;
1862         }
1863
1864         ui->clickx = x;
1865         ui->clicky = y;
1866         ui->drag_sx = ui->drag_ex = gx;
1867         ui->drag_sy = ui->drag_ey = gy;
1868
1869         return "";
1870     }
1871
1872     if (IS_MOUSE_DRAG(button)) {
1873         ui->cursor_active = FALSE;
1874         update_ui_drag(state, ui, gx, gy);
1875         return "";
1876     }
1877
1878     if (IS_MOUSE_RELEASE(button)) {
1879         ui->cursor_active = FALSE;
1880         if (ui->dragging &&
1881             (ui->drag_sx != ui->drag_ex || ui->drag_sy != ui->drag_ey)) {
1882             game_state *dragged = copy_and_apply_drag(state, ui);
1883             char *ret = move_string_diff(state, dragged, FALSE);
1884
1885             ui->dragging = 0;
1886             free_game(dragged);
1887
1888             return ret;
1889         } else {
1890             int cx, cy;
1891
1892             /* We might still have been dragging (and just done a one-
1893              * square drag): cancel drag, so undo doesn't make it like
1894              * a drag-in-progress. */
1895             ui->dragging = 0;
1896
1897             /* Click (or tiny drag). Work out which edge we were
1898              * closest to. */
1899
1900             /*
1901              * We process clicks based on the mouse-down location,
1902              * because that's more natural for a user to carefully
1903              * control than the mouse-up.
1904              */
1905             x = ui->clickx;
1906             y = ui->clicky;
1907
1908             cx = CENTERED_COORD(gx);
1909             cy = CENTERED_COORD(gy);
1910
1911             if (!INGRID(state, gx, gy) || FROMCOORD(x) != gx || FROMCOORD(y) != gy)
1912                 return "";
1913
1914             if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
1915                 if (ui_can_flip_square(state, gx, gy, button == RIGHT_RELEASE))
1916                     return square_flip_str(state, gx, gy, button == RIGHT_RELEASE, tmpbuf);
1917                 return "";
1918             } else {
1919                 if (abs(x-cx) < abs(y-cy)) {
1920                     /* Closest to top/bottom edge. */
1921                     direction = (y < cy) ? U : D;
1922                 } else {
1923                     /* Closest to left/right edge. */
1924                     direction = (x < cx) ? L : R;
1925                 }
1926                 if (ui_can_flip_edge(state, gx, gy, direction,
1927                         button == RIGHT_RELEASE))
1928                     return edge_flip_str(state, gx, gy, direction,
1929                             button == RIGHT_RELEASE, tmpbuf);
1930                 else
1931                     return "";
1932             }
1933         }
1934     }
1935
1936     /* --- cursor/keyboard operations --- */
1937
1938     if (IS_CURSOR_MOVE(button)) {
1939         int dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1940         int dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP)    ? -1 : 0);
1941
1942         if (!ui->cursor_active) {
1943             ui->cursor_active = TRUE;
1944             return "";
1945         }
1946
1947         ui->curx = ui->curx + dx;
1948         ui->cury = ui->cury + dy;
1949         if ((ui->curx % 2 == 0) && (ui->cury % 2 == 0)) {
1950             /* disallow cursor on square corners: centres and edges only */
1951             ui->curx += dx; ui->cury += dy;
1952         }
1953         ui->curx = min(max(ui->curx, 1), 2*w-1);
1954         ui->cury = min(max(ui->cury, 1), 2*h-1);
1955         return "";
1956     }
1957
1958     if (IS_CURSOR_SELECT(button)) {
1959         if (!ui->cursor_active) {
1960             ui->cursor_active = TRUE;
1961             return "";
1962         }
1963         /* click on square corner does nothing (shouldn't get here) */
1964         if ((ui->curx % 2) == 0 && (ui->cury % 2 == 0))
1965             return "";
1966
1967         gx = ui->curx / 2;
1968         gy = ui->cury / 2;
1969         direction = ((ui->curx % 2) == 0) ? L : ((ui->cury % 2) == 0) ? U : 0;
1970
1971         if (direction &&
1972             ui_can_flip_edge(state, gx, gy, direction, button == CURSOR_SELECT2))
1973             return edge_flip_str(state, gx, gy, direction, button == CURSOR_SELECT2, tmpbuf);
1974         else if (!direction &&
1975                  ui_can_flip_square(state, gx, gy, button == CURSOR_SELECT2))
1976             return square_flip_str(state, gx, gy, button == CURSOR_SELECT2, tmpbuf);
1977         return "";
1978     }
1979
1980 #if 0
1981     /* helps to debug the solver */
1982     if (button == 'H' || button == 'h')
1983         return dupstr("H");
1984 #endif
1985
1986     return NULL;
1987 }
1988
1989 static game_state *execute_move(const game_state *state, const char *move)
1990 {
1991     int w = state->p.w, x, y, n, i;
1992     char c, d;
1993     unsigned f;
1994     game_state *ret = dup_game(state);
1995
1996     /* this is breaking the bank on GTK, which vsprintf's into a fixed-size buffer
1997      * which is 4096 bytes long. vsnprintf needs a feature-test macro to use, faff. */
1998     /*debug(("move: %s\n", move));*/
1999
2000     while (*move) {
2001         c = *move;
2002         if (c == 'S') {
2003             ret->used_solve = TRUE;
2004             move++;
2005         } else if (c == 'T' || c == 't' || c == 'N' || c == 'n') {
2006             /* set track, clear track; set notrack, clear notrack */
2007             move++;
2008             if (sscanf(move, "%c%d,%d%n", &d, &x, &y, &n) != 3)
2009                 goto badmove;
2010             if (!INGRID(state, x, y)) goto badmove;
2011
2012             f = (c == 'T' || c == 't') ? S_TRACK : S_NOTRACK;
2013
2014             if (d == 'S') {
2015                 if (c == 'T' || c == 'N')
2016                     ret->sflags[y*w+x] |= f;
2017                 else
2018                     ret->sflags[y*w+x] &= ~f;
2019             } else if (d == 'U' || d == 'D' || d == 'L' || d == 'R') {
2020                 for (i = 0; i < 4; i++) {
2021                     unsigned df = 1<<i;
2022
2023                     if (MOVECHAR(df) == d) {
2024                         if (c == 'T' || c == 'N')
2025                             S_E_SET(ret, x, y, df, f);
2026                         else
2027                             S_E_CLEAR(ret, x, y, df, f);
2028                     }
2029                 }
2030             } else
2031                 goto badmove;
2032             move += n;
2033         } else if (c == 'H') {
2034             tracks_solve(ret, DIFFCOUNT);
2035             move++;
2036         } else {
2037             goto badmove;
2038         }
2039         if (*move == ';')
2040             move++;
2041         else if (*move)
2042             goto badmove;
2043     }
2044
2045     check_completion(ret, TRUE);
2046
2047     return ret;
2048
2049     badmove:
2050     free_game(ret);
2051     return NULL;
2052 }
2053
2054 /* ----------------------------------------------------------------------
2055  * Drawing routines.
2056  */
2057
2058 #define FLASH_TIME 0.5F
2059
2060 static void game_compute_size(const game_params *params, int tilesize,
2061                               int *x, int *y)
2062 {
2063     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2064     struct {
2065         int sz6;
2066     } ads, *ds = &ads;
2067     ads.sz6 = tilesize/6;
2068
2069     *x = (params->w+2) * TILE_SIZE + 2 * BORDER;
2070     *y = (params->h+2) * TILE_SIZE + 2 * BORDER;
2071 }
2072
2073 static void game_set_size(drawing *dr, game_drawstate *ds,
2074                           const game_params *params, int tilesize)
2075 {
2076     ds->sz6 = tilesize/6;
2077 }
2078
2079 enum {
2080     COL_BACKGROUND, COL_LOWLIGHT, COL_HIGHLIGHT,
2081     COL_TRACK_BACKGROUND = COL_LOWLIGHT,
2082     COL_GRID, COL_CLUE, COL_CURSOR,
2083     COL_TRACK, COL_TRACK_CLUE, COL_SLEEPER,
2084     COL_DRAGON, COL_DRAGOFF,
2085     COL_ERROR, COL_FLASH,
2086     NCOLOURS
2087 };
2088
2089 static float *game_colours(frontend *fe, int *ncolours)
2090 {
2091     float *ret = snewn(3 * NCOLOURS, float);
2092     int i;
2093
2094     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2095
2096     for (i = 0; i < 3; i++) {
2097         ret[COL_TRACK_CLUE * 3 + i] = 0.0F;
2098         ret[COL_TRACK * 3 + i] = 0.5F;
2099         ret[COL_CLUE * 3 + i] = 0.0F;
2100         ret[COL_GRID * 3 + i] = 0.75F;
2101         ret[COL_CURSOR * 3 + i] = 0.6F;
2102     }
2103
2104     ret[COL_SLEEPER * 3 + 0] = 0.5F;
2105     ret[COL_SLEEPER * 3 + 1] = 0.4F;
2106     ret[COL_SLEEPER * 3 + 2] = 0.1F;
2107
2108     ret[COL_ERROR * 3 + 0] = 1.0F;
2109     ret[COL_ERROR * 3 + 1] = 0.0F;
2110     ret[COL_ERROR * 3 + 2] = 0.0F;
2111
2112     ret[COL_DRAGON * 3 + 0] = 0.0F;
2113     ret[COL_DRAGON * 3 + 1] = 0.0F;
2114     ret[COL_DRAGON * 3 + 2] = 1.0F;
2115
2116     ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2117     ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2118     ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2119
2120     ret[COL_FLASH * 3 + 0] = 1.0F;
2121     ret[COL_FLASH * 3 + 1] = 1.0F;
2122     ret[COL_FLASH * 3 + 2] = 1.0F;
2123
2124     *ncolours = NCOLOURS;
2125     return ret;
2126 }
2127
2128 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2129 {
2130     struct game_drawstate *ds = snew(struct game_drawstate);
2131     int i;
2132
2133     ds->sz6 = 0;
2134     ds->started = FALSE;
2135
2136     ds->w = state->p.w;
2137     ds->h = state->p.h;
2138     ds->sz = ds->w*ds->h;
2139     ds->flags = snewn(ds->sz, unsigned int);
2140     ds->flags_drag = snewn(ds->sz, unsigned int);
2141     for (i = 0; i < ds->sz; i++)
2142         ds->flags[i] = ds->flags_drag[i] = 0;
2143
2144     ds->num_errors = snewn(ds->w+ds->h, int);
2145     for (i = 0; i < ds->w+ds->h; i++)
2146         ds->num_errors[i] = 0;
2147
2148     return ds;
2149 }
2150
2151 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2152 {
2153     sfree(ds->flags);
2154     sfree(ds->flags_drag);
2155     sfree(ds->num_errors);
2156     sfree(ds);
2157 }
2158
2159 static void draw_circle_sleepers(drawing *dr, game_drawstate *ds,
2160                                  float cx, float cy, float r2, float thickness, int c)
2161 {
2162     float qr6 = (float)PI/12, qr3 = (float)PI/6, th, x1, y1, x2, y2;
2163     float t6 = THIRDSZ/2.0F, r1 = t6;
2164     int i;
2165
2166     for (i = 0; i < 12; i++) {
2167         th = qr6 + (i*qr3);
2168         x1 = r1*(float)cos(th);
2169         x2 = r2*(float)cos(th);
2170         y1 = r1*(float)sin(th);
2171         y2 = r2*(float)sin(th);
2172         draw_thick_line(dr, thickness, cx+x1, cy+y1, cx+x2, cy+y2, c);
2173     }
2174 }
2175
2176 static void draw_thick_circle_outline(drawing *dr, float thickness,
2177                                       float cx, float cy, float r,
2178                                       int colour)
2179 {
2180     float circ4 = 0.5F * (float)PI * r, ang, x1, y1, x2, y2;
2181     int i, nseg;
2182
2183     nseg = (int)(circ4 / 4.0F)*4; /* ensure a quarter-circle has a whole #segs */
2184     ang = 2.0F*(float)PI / nseg;
2185
2186     for (i = 0; i < nseg; i++) {
2187         float th = ang * i, th2 = ang * (i+1);
2188         x1 = cx + r*(float)cos(th);
2189         x2 = cx + r*(float)cos(th2);
2190         y1 = cy + r*(float)sin(th);
2191         y2 = cy + r*(float)sin(th2);
2192         debug(("circ outline: x=%.2f -> %.2f, thick=%.2f", x1, x2, thickness));
2193         draw_thick_line(dr, thickness, x1, y1, x2, y2, colour);
2194     }
2195 }
2196
2197 static void draw_tracks_specific(drawing *dr, game_drawstate *ds,
2198                                  int x, int y, unsigned int flags,
2199                                  int ctrack, int csleeper)
2200 {
2201     float ox = (float)COORD(x), oy = (float)COORD(y), cx, cy;
2202     float t1 = (float)TILE_SIZE, t3 = TILE_SIZE/3.0F, t6 = TILE_SIZE/6.0F;
2203     int d, i;
2204     float thick_track = TILE_SIZE/8.0F, thick_sleeper = TILE_SIZE/12.0F;
2205
2206     if (flags == LR) {
2207         for (i = 1; i <= 7; i+=2) {
2208             cx = ox + TILE_SIZE/8.0F*i;
2209             draw_thick_line(dr, thick_sleeper,
2210                             cx, oy+t6, cx, oy+t6+2*t3, csleeper);
2211         }
2212         draw_thick_line(dr, thick_track, ox, oy + t3, ox + TILE_SIZE, oy + t3, ctrack);
2213         draw_thick_line(dr, thick_track, ox, oy + 2*t3, ox + TILE_SIZE, oy + 2*t3, ctrack);
2214         return;
2215     }
2216     if (flags == UD) {
2217         for (i = 1; i <= 7; i+=2) {
2218             cy = oy + TILE_SIZE/8.0F*i;
2219             draw_thick_line(dr, thick_sleeper,
2220                             ox+t6, cy, ox+t6+2*t3, cy, csleeper);
2221         }
2222         debug(("vert line: x=%.2f, thick=%.2f", ox + t3, thick_track));
2223         draw_thick_line(dr, thick_track, ox + t3, oy, ox + t3, oy + TILE_SIZE, ctrack);
2224         draw_thick_line(dr, thick_track, ox + 2*t3, oy, ox + 2*t3, oy + TILE_SIZE, ctrack);
2225         return;
2226     }
2227     if (flags == UL || flags == DL || flags == UR || flags == DR) {
2228         cx = (flags & L) ? ox : ox + TILE_SIZE;
2229         cy = (flags & U) ? oy : oy + TILE_SIZE;
2230
2231         draw_circle_sleepers(dr, ds, cx, cy, (float)(5*t6), thick_sleeper, csleeper);
2232
2233         draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2234                                   2*t3, ctrack);
2235         draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2236                                   t3, ctrack);
2237
2238         return;
2239     }
2240
2241     for (d = 1; d < 16; d *= 2) {
2242         float ox1 = 0, ox2 = 0, oy1 = 0, oy2 = 0;
2243
2244         if (!(flags & d)) continue;
2245
2246         for (i = 1; i <= 2; i++) {
2247             if (d == L) {
2248                 ox1 = 0;
2249                 ox2 = thick_track;
2250                 oy1 = oy2 = i*t3;
2251             } else if (d == R) {
2252                 ox1 = t1;
2253                 ox2 = t1 - thick_track;
2254                 oy1 = oy2 = i*t3;
2255             } else if (d == U) {
2256                 ox1 = ox2 = i*t3;
2257                 oy1 = 0;
2258                 oy2 = thick_track;
2259             } else if (d == D) {
2260                 ox1 = ox2 = i*t3;
2261                 oy1 = t1;
2262                 oy2 = t1 - thick_track;
2263             }
2264             draw_thick_line(dr, thick_track, ox+ox1, oy+oy1, ox+ox2, oy+oy2, ctrack);
2265         }
2266     }
2267 }
2268
2269 static unsigned int best_bits(unsigned int flags, unsigned int flags_drag, int *col)
2270 {
2271     int nb_orig = nbits[flags & ALLDIR], nb_drag = nbits[flags_drag & ALLDIR];
2272
2273     if (nb_orig > nb_drag) {
2274         *col = COL_DRAGOFF;
2275         return flags & ALLDIR;
2276     } else if (nb_orig < nb_drag) {
2277         *col = COL_DRAGON;
2278         return flags_drag & ALLDIR;
2279     }
2280     return flags & ALLDIR; /* same number of bits: no special colour. */
2281 }
2282
2283 static void draw_square(drawing *dr, game_drawstate *ds,
2284                         int x, int y, unsigned int flags, unsigned int flags_drag)
2285 {
2286     int t2 = HALFSZ, t16 = HALFSZ/4, off;
2287     int ox = COORD(x), oy = COORD(y), cx = ox + t2, cy = oy + t2, d, c;
2288     int bg = (flags & DS_TRACK) ? COL_TRACK_BACKGROUND : COL_BACKGROUND;
2289     unsigned int flags_best;
2290
2291     assert(dr);
2292
2293     /* Clip to the grid square. */
2294     clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2295
2296     /* Clear the square. */
2297     best_bits((flags & DS_TRACK) == DS_TRACK,
2298               (flags_drag & DS_TRACK) == DS_TRACK, &bg);
2299     draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, bg);
2300
2301     /* Draw outline of grid square */
2302     draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID);
2303     draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID);
2304
2305     /* More outlines for clue squares. */
2306     if (flags & DS_CURSOR) {
2307         int curx, cury, curw, curh;
2308
2309         off = t16;
2310         curx = ox + off; cury = oy + off;
2311         curw = curh = TILE_SIZE - (2*off) + 1;
2312
2313         if (flags & (U << DS_CSHIFT)) {
2314             cury = oy - off; curh = 2*off + 1;
2315         } else if (flags & (D << DS_CSHIFT)) {
2316             cury = oy + TILE_SIZE - off; curh = 2*off + 1;
2317         } else if (flags & (L << DS_CSHIFT)) {
2318             curx = ox - off; curw = 2*off + 1;
2319         } else if (flags & (R << DS_CSHIFT)) {
2320             curx = ox + TILE_SIZE - off; curw = 2*off + 1;
2321         }
2322
2323         draw_rect_outline(dr, curx, cury, curw, curh, COL_GRID);
2324     }
2325
2326     /* Draw tracks themselves */
2327     c = (flags & DS_ERROR) ? COL_ERROR :
2328       (flags & DS_FLASH) ? COL_FLASH :
2329       (flags & DS_CLUE) ? COL_TRACK_CLUE : COL_TRACK;
2330     flags_best = best_bits(flags, flags_drag, &c);
2331     draw_tracks_specific(dr, ds, x, y, flags_best, c, COL_SLEEPER);
2332
2333     /* Draw no-track marks, if present, in square and on edges. */
2334     c = COL_TRACK;
2335     flags_best = best_bits((flags & DS_NOTRACK) == DS_NOTRACK,
2336                            (flags_drag & DS_NOTRACK) == DS_NOTRACK, &c);
2337     if (flags_best) {
2338         off = HALFSZ/2;
2339         draw_line(dr, cx - off, cy - off, cx + off, cy + off, c);
2340         draw_line(dr, cx - off, cy + off, cx + off, cy - off, c);
2341     }
2342
2343     c = COL_TRACK;
2344     flags_best = best_bits(flags >> DS_NSHIFT, flags_drag >> DS_NSHIFT, &c);
2345     for (d = 1; d < 16; d *= 2) {
2346         off = t16;
2347         cx = ox + t2;
2348         cy = oy + t2;
2349
2350         if (flags_best & d) {
2351             cx += (d == R) ? t2 : (d == L) ? -t2 : 0;
2352             cy += (d == D) ? t2 : (d == U) ? -t2 : 0;
2353
2354             draw_line(dr, cx - off, cy - off, cx + off, cy + off, c);
2355             draw_line(dr, cx - off, cy + off, cx + off, cy - off, c);
2356         }
2357     }
2358
2359     unclip(dr);
2360     draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2361 }
2362
2363 static void draw_clue(drawing *dr, game_drawstate *ds, int w, int clue, int i, int col)
2364 {
2365     int cx, cy, tsz = TILE_SIZE/2;
2366     char buf[20];
2367
2368     if (i < w) {
2369         cx = CENTERED_COORD(i);
2370         cy = CENTERED_COORD(-1);
2371     } else {
2372         cx = CENTERED_COORD(w);
2373         cy = CENTERED_COORD(i-w);
2374     }
2375
2376     draw_rect(dr, cx - tsz + BORDER, cy - tsz + BORDER,
2377               TILE_SIZE - BORDER, TILE_SIZE - BORDER, COL_BACKGROUND);
2378     sprintf(buf, "%d", clue);
2379     draw_text(dr, cx, cy, FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2380               col, buf);
2381     draw_update(dr, cx - tsz, cy - tsz, TILE_SIZE, TILE_SIZE);
2382 }
2383
2384 static void draw_loop_ends(drawing *dr, game_drawstate *ds,
2385                            const game_state *state, int c)
2386 {
2387     int tsz = TILE_SIZE/2;
2388
2389     draw_text(dr, CENTERED_COORD(-1), CENTERED_COORD(state->numbers->row_s),
2390               FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2391               c, "A");
2392
2393     draw_text(dr, CENTERED_COORD(state->numbers->col_s), CENTERED_COORD(state->p.h),
2394               FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2395               c, "B");
2396 }
2397
2398 static unsigned int s2d_flags(const game_state *state, int x, int y, const game_ui *ui)
2399 {
2400     unsigned int f;
2401     int w = state->p.w;
2402
2403     f = S_E_DIRS(state, x, y, E_TRACK);
2404     f |= (S_E_DIRS(state, x, y, E_NOTRACK) << DS_NSHIFT);
2405
2406     if (state->sflags[y*w+x] & S_ERROR)
2407         f |= DS_ERROR;
2408     if (state->sflags[y*w+x] & S_CLUE)
2409         f |= DS_CLUE;
2410     if (state->sflags[y*w+x] & S_NOTRACK)
2411         f |= DS_NOTRACK;
2412     if ((state->sflags[y*w+x] & S_TRACK) || (S_E_COUNT(state, x, y, E_TRACK) > 0))
2413         f |= DS_TRACK;
2414
2415     if (ui->cursor_active) {
2416         if (ui->curx >= x*2 && ui->curx <= (x+1)*2 &&
2417             ui->cury >= y*2 && ui->cury <= (y+1)*2) {
2418             f |= DS_CURSOR;
2419             if (ui->curx == x*2)        f |= (L << DS_CSHIFT);
2420             if (ui->curx == (x+1)*2)    f |= (R << DS_CSHIFT);
2421             if (ui->cury == y*2)        f |= (U << DS_CSHIFT);
2422             if (ui->cury == (y+1)*2)    f |= (D << DS_CSHIFT);
2423         }
2424     }
2425
2426     return f;
2427 }
2428
2429 static void game_redraw(drawing *dr, game_drawstate *ds, const game_state *oldstate,
2430                         const game_state *state, int dir, const game_ui *ui,
2431                         float animtime, float flashtime)
2432 {
2433     int i, x, y, force = 0, flashing = 0, w = ds->w, h = ds->h;
2434     game_state *drag_state = NULL;
2435
2436     if (!ds->started) {
2437         /*
2438          * The initial contents of the window are not guaranteed and
2439          * can vary with front ends. To be on the safe side, all games
2440          * should start by drawing a big background-colour rectangle
2441          * covering the whole window.
2442          */
2443         draw_rect(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER,
2444                   COL_BACKGROUND);
2445
2446         draw_loop_ends(dr, ds, state, COL_CLUE);
2447
2448         draw_line(dr, COORD(ds->w), COORD(0), COORD(ds->w), COORD(ds->h), COL_GRID);
2449         draw_line(dr, COORD(0), COORD(ds->h), COORD(ds->w), COORD(ds->h), COL_GRID);
2450
2451         draw_update(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER);
2452
2453         ds->started = TRUE;
2454         force = 1;
2455     }
2456
2457     for (i = 0; i < w+h; i++) {
2458         if (force || (state->num_errors[i] != ds->num_errors[i])) {
2459             ds->num_errors[i] = state->num_errors[i];
2460             draw_clue(dr, ds, w, state->numbers->numbers[i], i,
2461                       ds->num_errors[i] ? COL_ERROR : COL_CLUE);
2462         }
2463     }
2464
2465     if (flashtime > 0 &&
2466             (flashtime <= FLASH_TIME/3 ||
2467              flashtime >= FLASH_TIME*2/3))
2468         flashing = DS_FLASH;
2469
2470     if (ui->dragging)
2471         drag_state = copy_and_apply_drag(state, ui);
2472
2473     for (x = 0; x < w; x++) {
2474         for (y = 0; y < h; y++) {
2475             unsigned int f, f_d;
2476
2477             f = s2d_flags(state, x, y, ui) | flashing;
2478             f_d = drag_state ? s2d_flags(drag_state, x, y, ui) : f;
2479
2480             if (f != ds->flags[y*w+x] || f_d != ds->flags_drag[y*w+x] || force) {
2481                 ds->flags[y*w+x] = f;
2482                 ds->flags_drag[y*w+x] = f_d;
2483                 draw_square(dr, ds, x, y, f, f_d);
2484             }
2485         }
2486     }
2487
2488     if (drag_state) free_game(drag_state);
2489 }
2490
2491 static float game_anim_length(const game_state *oldstate, const game_state *newstate,
2492                               int dir, game_ui *ui)
2493 {
2494     return 0.0F;
2495 }
2496
2497 static float game_flash_length(const game_state *oldstate, const game_state *newstate,
2498                                int dir, game_ui *ui)
2499 {
2500     if (!oldstate->completed &&
2501             newstate->completed && !newstate->used_solve)
2502         return FLASH_TIME;
2503     else
2504         return 0.0F;
2505 }
2506
2507 static int game_status(const game_state *state)
2508 {
2509     return state->completed ? +1 : 0;
2510 }
2511
2512 static int game_timing_state(const game_state *state, game_ui *ui)
2513 {
2514     return TRUE;
2515 }
2516
2517 static void game_print_size(const game_params *params, float *x, float *y)
2518 {
2519     int pw, ph;
2520
2521     /* The Times uses 7mm squares */
2522     game_compute_size(params, 700, &pw, &ph);
2523     *x = pw / 100.0F;
2524     *y = ph / 100.0F;
2525 }
2526
2527 static void game_print(drawing *dr, const game_state *state, int tilesize)
2528 {
2529     int w = state->p.w, h = state->p.h;
2530     int black = print_mono_colour(dr, 0), grey = print_grey_colour(dr, 0.5F);
2531     int x, y, i;
2532
2533     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2534     game_drawstate ads, *ds = &ads;
2535     game_set_size(dr, ds, NULL, tilesize);
2536
2537     /* Grid, then border (second so it is on top) */
2538     print_line_width(dr, TILE_SIZE / 24);
2539     for (x = 1; x < w; x++)
2540         draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), grey);
2541     for (y = 1; y < h; y++)
2542         draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), grey);
2543
2544     print_line_width(dr, TILE_SIZE / 16);
2545     draw_rect_outline(dr, COORD(0), COORD(0), w*TILE_SIZE, h*TILE_SIZE, black);
2546
2547     print_line_width(dr, TILE_SIZE / 24);
2548
2549     /* clue numbers, and loop ends */
2550     for (i = 0; i < w+h; i++)
2551         draw_clue(dr, ds, w, state->numbers->numbers[i], i, black);
2552     draw_loop_ends(dr, ds, state, black);
2553
2554     /* clue tracks / solution */
2555     for (x = 0; x < w; x++) {
2556         for (y = 0; y < h; y++) {
2557             clip(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
2558             draw_tracks_specific(dr, ds, x, y, S_E_DIRS(state, x, y, E_TRACK),
2559                                  black, grey);
2560             unclip(dr);
2561         }
2562     }
2563 }
2564
2565 #ifdef COMBINED
2566 #define thegame tracks
2567 #endif
2568
2569 const struct game thegame = {
2570     "Train Tracks", "games.tracks", "tracks",
2571     default_params,
2572     game_fetch_preset,
2573     decode_params,
2574     encode_params,
2575     free_params,
2576     dup_params,
2577     TRUE, game_configure, custom_params,
2578     validate_params,
2579     new_game_desc,
2580     validate_desc,
2581     new_game,
2582     dup_game,
2583     free_game,
2584     TRUE, solve_game,
2585     TRUE, game_can_format_as_text_now, game_text_format,
2586     new_ui,
2587     free_ui,
2588     encode_ui,
2589     decode_ui,
2590     game_changed_state,
2591     interpret_move,
2592     execute_move,
2593     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2594     game_colours,
2595     game_new_drawstate,
2596     game_free_drawstate,
2597     game_redraw,
2598     game_anim_length,
2599     game_flash_length,
2600     game_status,
2601     TRUE, FALSE, game_print_size, game_print,
2602     FALSE,                             /* wants_statusbar */
2603     FALSE, game_timing_state,
2604     0,                                 /* flags */
2605 };
2606
2607 /* vim: set shiftwidth=4 tabstop=8: */