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