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