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