fifteen.c

   1 /*
   2  * fifteen.c: standard 15-puzzle.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10 #include <math.h>
  11
  12 #include "puzzles.h"
  13
  14 #define PREFERRED_TILE_SIZE 48
  15 #define TILE_SIZE (ds->tilesize)
  16 #define BORDER    (TILE_SIZE / 2)
  17 #define HIGHLIGHT_WIDTH (TILE_SIZE / 20)
  18 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  19 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  20
  21 #define ANIM_TIME 0.13F
  22 #define FLASH_FRAME 0.13F
  23
  24 #define X(state, i) ( (i) % (state)->w )
  25 #define Y(state, i) ( (i) / (state)->w )
  26 #define C(state, x, y) ( (y) * (state)->w + (x) )
  27
  28 #define PARITY_P(params, gap) (((X((params), (gap)) - ((params)->w - 1)) ^ \
  29                                 (Y((params), (gap)) - ((params)->h - 1)) ^ \
  30                                 (((params)->w * (params)->h) + 1)) & 1)
  31 #define PARITY_S(state) PARITY_P((state), ((state)->gap_pos))
  32
  33 enum {
  34     COL_BACKGROUND,
  35     COL_TEXT,
  36     COL_HIGHLIGHT,
  37     COL_LOWLIGHT,
  38     NCOLOURS
  39 };
  40
  41 struct game_params {
  42     int w, h;
  43 };
  44
  45 struct game_state {
  46     int w, h, n;
  47     int *tiles;
  48     int gap_pos;
  49     int completed;
  50     int used_solve;                    /* used to suppress completion flash */
  51     int movecount;
  52 };
  53
  54 static game_params *default_params(void)
  55 {
  56     game_params *ret = snew(game_params);
  57
  58     ret->w = ret->h = 4;
  59
  60     return ret;
  61 }
  62
  63 static int game_fetch_preset(int i, char **name, game_params **params)
  64 {
  65     if (i == 0) {
  66         *params = default_params();
  67         *name = dupstr("4x4");
  68         return TRUE;
  69     }
  70     return FALSE;
  71 }
  72
  73 static void free_params(game_params *params)
  74 {
  75     sfree(params);
  76 }
  77
  78 static game_params *dup_params(const game_params *params)
  79 {
  80     game_params *ret = snew(game_params);
  81     *ret = *params;                    /* structure copy */
  82     return ret;
  83 }
  84
  85 static void decode_params(game_params *ret, char const *string)
  86 {
  87     ret->w = ret->h = atoi(string);
  88     while (*string && isdigit((unsigned char)*string)) string++;
  89     if (*string == 'x') {
  90         string++;
  91         ret->h = atoi(string);
  92     }
  93 }
  94
  95 static char *encode_params(const game_params *params, int full)
  96 {
  97     char data[256];
  98
  99     sprintf(data, "%dx%d", params->w, params->h);
 100
 101     return dupstr(data);
 102 }
 103
 104 static config_item *game_configure(const game_params *params)
 105 {
 106     config_item *ret;
 107     char buf[80];
 108
 109     ret = snewn(3, config_item);
 110
 111     ret[0].name = "Width";
 112     ret[0].type = C_STRING;
 113     sprintf(buf, "%d", params->w);
 114     ret[0].u.string.sval = dupstr(buf);
 115
 116     ret[1].name = "Height";
 117     ret[1].type = C_STRING;
 118     sprintf(buf, "%d", params->h);
 119     ret[1].u.string.sval = dupstr(buf);
 120
 121     ret[2].name = NULL;
 122     ret[2].type = C_END;
 123
 124     return ret;
 125 }
 126
 127 static game_params *custom_params(const config_item *cfg)
 128 {
 129     game_params *ret = snew(game_params);
 130
 131     ret->w = atoi(cfg[0].u.string.sval);
 132     ret->h = atoi(cfg[1].u.string.sval);
 133
 134     return ret;
 135 }
 136
 137 static const char *validate_params(const game_params *params, int full)
 138 {
 139     if (params->w < 2 || params->h < 2)
 140         return "Width and height must both be at least two";
 141
 142     return NULL;
 143 }
 144
 145 static int perm_parity(int *perm, int n)
 146 {
 147     int i, j, ret;
 148
 149     ret = 0;
 150
 151     for (i = 0; i < n-1; i++)
 152         for (j = i+1; j < n; j++)
 153             if (perm[i] > perm[j])
 154                 ret = !ret;
 155
 156     return ret;
 157 }
 158
 159 static char *new_game_desc(const game_params *params, random_state *rs,
 160                            char **aux, int interactive)
 161 {
 162     int gap, n, i, x;
 163     int x1, x2, p1, p2, parity;
 164     int *tiles, *used;
 165     char *ret;
 166     int retlen;
 167
 168     n = params->w * params->h;
 169
 170     tiles = snewn(n, int);
 171     used = snewn(n, int);
 172
 173     for (i = 0; i < n; i++) {
 174         tiles[i] = -1;
 175         used[i] = FALSE;
 176     }
 177
 178     gap = random_upto(rs, n);
 179     tiles[gap] = 0;
 180     used[0] = TRUE;
 181
 182     /*
 183      * Place everything else except the last two tiles.
 184      */
 185     for (x = 0, i = n-1; i > 2; i--) {
 186         int k = random_upto(rs, i);
 187         int j;
 188
 189         for (j = 0; j < n; j++)
 190             if (!used[j] && (k-- == 0))
 191                 break;
 192
 193         assert(j < n && !used[j]);
 194         used[j] = TRUE;
 195
 196         while (tiles[x] >= 0)
 197             x++;
 198         assert(x < n);
 199         tiles[x] = j;
 200     }
 201
 202     /*
 203      * Find the last two locations, and the last two pieces.
 204      */
 205     while (tiles[x] >= 0)
 206         x++;
 207     assert(x < n);
 208     x1 = x;
 209     x++;
 210     while (tiles[x] >= 0)
 211         x++;
 212     assert(x < n);
 213     x2 = x;
 214
 215     for (i = 0; i < n; i++)
 216         if (!used[i])
 217             break;
 218     p1 = i;
 219     for (i = p1+1; i < n; i++)
 220         if (!used[i])
 221             break;
 222     p2 = i;
 223
 224     /*
 225      * Determine the required parity of the overall permutation.
 226      * This is the XOR of:
 227      *
 228      *  - The chessboard parity ((x^y)&1) of the gap square. The
 229      *    bottom right counts as even.
 230      *
 231      *  - The parity of n. (The target permutation is 1,...,n-1,0
 232      *    rather than 0,...,n-1; this is a cyclic permutation of
 233      *    the starting point and hence is odd iff n is even.)
 234      */
 235     parity = PARITY_P(params, gap);
 236
 237     /*
 238      * Try the last two tiles one way round. If that fails, swap
 239      * them.
 240      */
 241     tiles[x1] = p1;
 242     tiles[x2] = p2;
 243     if (perm_parity(tiles, n) != parity) {
 244         tiles[x1] = p2;
 245         tiles[x2] = p1;
 246         assert(perm_parity(tiles, n) == parity);
 247     }
 248
 249     /*
 250      * Now construct the game description, by describing the tile
 251      * array as a simple sequence of comma-separated integers.
 252      */
 253     ret = NULL;
 254     retlen = 0;
 255     for (i = 0; i < n; i++) {
 256         char buf[80];
 257         int k;
 258
 259         k = sprintf(buf, "%d,", tiles[i]);
 260
 261         ret = sresize(ret, retlen + k + 1, char);
 262         strcpy(ret + retlen, buf);
 263         retlen += k;
 264     }
 265     ret[retlen-1] = '\0';              /* delete last comma */
 266
 267     sfree(tiles);
 268     sfree(used);
 269
 270     return ret;
 271 }
 272
 273 static const char *validate_desc(const game_params *params, const char *desc)
 274 {
 275     const char *p;
 276     const char *err;
 277     int i, area;
 278     int *used;
 279
 280     area = params->w * params->h;
 281     p = desc;
 282     err = NULL;
 283
 284     used = snewn(area, int);
 285     for (i = 0; i < area; i++)
 286         used[i] = FALSE;
 287
 288     for (i = 0; i < area; i++) {
 289         const char *q = p;
 290         int n;
 291
 292         if (*p < '0' || *p > '9') {
 293             err = "Not enough numbers in string";
 294             goto leave;
 295         }
 296         while (*p >= '0' && *p <= '9')
 297             p++;
 298         if (i < area-1 && *p != ',') {
 299             err = "Expected comma after number";
 300             goto leave;
 301         }
 302         else if (i == area-1 && *p) {
 303             err = "Excess junk at end of string";
 304             goto leave;
 305         }
 306         n = atoi(q);
 307         if (n < 0 || n >= area) {
 308             err = "Number out of range";
 309             goto leave;
 310         }
 311         if (used[n]) {
 312             err = "Number used twice";
 313             goto leave;
 314         }
 315         used[n] = TRUE;
 316
 317         if (*p) p++;                   /* eat comma */
 318     }
 319
 320     leave:
 321     sfree(used);
 322     return err;
 323 }
 324
 325 static game_state *new_game(midend *me, const game_params *params,
 326                             const char *desc)
 327 {
 328     game_state *state = snew(game_state);
 329     int i;
 330     const char *p;
 331
 332     state->w = params->w;
 333     state->h = params->h;
 334     state->n = params->w * params->h;
 335     state->tiles = snewn(state->n, int);
 336
 337     state->gap_pos = 0;
 338     p = desc;
 339     i = 0;
 340     for (i = 0; i < state->n; i++) {
 341         assert(*p);
 342         state->tiles[i] = atoi(p);
 343         if (state->tiles[i] == 0)
 344             state->gap_pos = i;
 345         while (*p && *p != ',')
 346             p++;
 347         if (*p) p++;                   /* eat comma */
 348     }
 349     assert(!*p);
 350     assert(state->tiles[state->gap_pos] == 0);
 351
 352     state->completed = state->movecount = 0;
 353     state->used_solve = FALSE;
 354
 355     return state;
 356 }
 357
 358 static game_state *dup_game(const game_state *state)
 359 {
 360     game_state *ret = snew(game_state);
 361
 362     ret->w = state->w;
 363     ret->h = state->h;
 364     ret->n = state->n;
 365     ret->tiles = snewn(state->w * state->h, int);
 366     memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int));
 367     ret->gap_pos = state->gap_pos;
 368     ret->completed = state->completed;
 369     ret->movecount = state->movecount;
 370     ret->used_solve = state->used_solve;
 371
 372     return ret;
 373 }
 374
 375 static void free_game(game_state *state)
 376 {
 377     sfree(state->tiles);
 378     sfree(state);
 379 }
 380
 381 static char *solve_game(const game_state *state, const game_state *currstate,
 382                         const char *aux, const char **error)
 383 {
 384     return dupstr("S");
 385 }
 386
 387 static int game_can_format_as_text_now(const game_params *params)
 388 {
 389     return TRUE;
 390 }
 391
 392 static char *game_text_format(const game_state *state)
 393 {
 394     char *ret, *p, buf[80];
 395     int x, y, col, maxlen;
 396
 397     /*
 398      * First work out how many characters we need to display each
 399      * number.
 400      */
 401     col = sprintf(buf, "%d", state->n-1);
 402
 403     /*
 404      * Now we know the exact total size of the grid we're going to
 405      * produce: it's got h rows, each containing w lots of col, w-1
 406      * spaces and a trailing newline.
 407      */
 408     maxlen = state->h * state->w * (col+1);
 409
 410     ret = snewn(maxlen+1, char);
 411     p = ret;
 412
 413     for (y = 0; y < state->h; y++) {
 414         for (x = 0; x < state->w; x++) {
 415             int v = state->tiles[state->w*y+x];
 416             if (v == 0)
 417                 sprintf(buf, "%*s", col, "");
 418             else
 419                 sprintf(buf, "%*d", col, v);
 420             memcpy(p, buf, col);
 421             p += col;
 422             if (x+1 == state->w)
 423                 *p++ = '\n';
 424             else
 425                 *p++ = ' ';
 426         }
 427     }
 428
 429     assert(p - ret == maxlen);
 430     *p = '\0';
 431     return ret;
 432 }
 433
 434 static game_ui *new_ui(const game_state *state)
 435 {
 436     return NULL;
 437 }
 438
 439 static void free_ui(game_ui *ui)
 440 {
 441 }
 442
 443 static char *encode_ui(const game_ui *ui)
 444 {
 445     return NULL;
 446 }
 447
 448 static void decode_ui(game_ui *ui, const char *encoding)
 449 {
 450 }
 451
 452 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 453                                const game_state *newstate)
 454 {
 455 }
 456
 457 struct game_drawstate {
 458     int started;
 459     int w, h, bgcolour;
 460     int *tiles;
 461     int tilesize;
 462 };
 463
 464 static int flip_cursor(int button)
 465 {
 466     switch (button) {
 467     case CURSOR_UP: return CURSOR_DOWN;
 468     case CURSOR_DOWN: return CURSOR_UP;
 469     case CURSOR_LEFT: return CURSOR_RIGHT;
 470     case CURSOR_RIGHT: return CURSOR_LEFT;
 471     }
 472     return 0;
 473 }
 474
 475 static void next_move_3x2(int ax, int ay, int bx, int by,
 476                           int gx, int gy, int *dx, int *dy)
 477 {
 478     /* When w = 3 and h = 2 and the tile going in the top left corner
 479      * is at (ax, ay) and the tile going in the bottom left corner is
 480      * at (bx, by) and the blank tile is at (gx, gy), how do you move? */
 481
 482     /* Hard-coded shortest solutions.  Sorry. */
 483     static const unsigned char move[120] = {
 484         1,2,0,1,2,2,
 485         2,0,0,2,0,0,
 486         0,0,2,0,2,0,
 487         0,0,0,2,0,2,
 488         2,0,0,0,2,0,
 489
 490         0,3,0,1,1,1,
 491         3,0,3,2,1,2,
 492         2,1,1,0,1,0,
 493         2,1,2,1,0,1,
 494         1,2,0,2,1,2,
 495
 496         0,1,3,1,3,0,
 497         1,3,1,3,0,3,
 498         0,0,3,3,0,0,
 499         0,0,0,1,2,1,
 500         3,0,0,1,1,1,
 501
 502         3,1,1,1,3,0,
 503         1,1,1,1,1,1,
 504         1,3,1,1,3,0,
 505         1,1,3,3,1,3,
 506         1,3,0,0,0,0
 507     };
 508     static const struct { int dx, dy; } d[4] = {{+1,0},{-1,0},{0,+1},{0,-1}};
 509
 510     int ea = 3*ay + ax, eb = 3*by + bx, eg = 3*gy + gx, v;
 511     if (eb > ea) --eb;
 512     if (eg > ea) --eg;
 513     if (eg > eb) --eg;
 514     v = move[ea + eb*6 + eg*5*6];
 515     *dx = d[v].dx;
 516     *dy = d[v].dy;
 517 }
 518
 519 static void next_move(int nx, int ny, int ox, int oy, int gx, int gy,
 520                       int tx, int ty, int w, int *dx, int *dy)
 521 {
 522     const int to_tile_x = (gx < nx ? +1 : -1);
 523     const int to_goal_x = (gx < tx ? +1 : -1);
 524     const int gap_x_on_goal_side = ((nx-tx) * (nx-gx) > 0);
 525
 526     assert (nx != tx || ny != ty); /* not already in place */
 527     assert (nx != gx || ny != gy); /* not placing the gap */
 528     assert (ty <= ny); /* because we're greedy (and flipping) */
 529     assert (ty <= gy); /* because we're greedy (and flipping) */
 530
 531     /* TODO: define a termination function.  Idea: 0 if solved, or
 532      * the number of moves to solve the next piece plus the number of
 533      * further unsolved pieces times an upper bound on the number of
 534      * moves required to solve any piece.  If such a function can be
 535      * found, we have (termination && (termination => correctness)).
 536      * The catch is our temporary disturbance of 2x3 corners. */
 537
 538     /* handles end-of-row, when 3 and 4 are in the top right 2x3 box */
 539     if (tx == w - 2 &&
 540         ny <= ty + 2 && (nx == tx || nx == tx + 1) &&
 541         oy <= ty + 2 && (ox == tx || ox == tx + 1) &&
 542         gy <= ty + 2 && (gx == tx || gx == tx + 1))
 543     {
 544         next_move_3x2(oy - ty, tx + 1 - ox,
 545                       ny - ty, tx + 1 - nx,
 546                       gy - ty, tx + 1 - gx, dy, dx);
 547         *dx *= -1;
 548         return;
 549     }
 550
 551     if (tx == w - 1) {
 552         if (ny <= ty + 2 && (nx == tx || nx == tx - 1) &&
 553             gy <= ty + 2 && (gx == tx || gx == tx - 1)) {
 554             next_move_3x2(ny - ty, tx - nx, 0, 1, gy - ty, tx - gx, dy, dx);
 555             *dx *= -1;
 556         } else if (gy == ty)
 557             *dy = +1;
 558         else if (nx != tx || ny != ty + 1) {
 559             next_move((w - 1) - nx, ny, -1, -1, (w - 1) - gx, gy,
 560                       0, ty + 1, -1, dx, dy);
 561             *dx *= -1;
 562         } else if (gx == nx)
 563             *dy = -1;
 564         else
 565             *dx = +1;
 566         return;
 567     }
 568
 569     /* note that *dy = -1 is unsafe when gy = ty + 1 and gx < tx */
 570     if (gy < ny)
 571         if (nx == gx || (gy == ty && gx == tx))
 572             *dy = +1;
 573         else if (!gap_x_on_goal_side)
 574             *dx = to_tile_x;
 575         else if (ny - ty > abs(nx - tx))
 576             *dx = to_tile_x;
 577         else *dy = +1;
 578
 579     else if (gy == ny)
 580         if (nx == tx) /* then we know ny > ty */
 581             if (gx > nx || ny > ty + 1)
 582                 *dy = -1; /* ... so this is safe */
 583             else
 584                 *dy = +1;
 585         else if (gap_x_on_goal_side)
 586             *dx = to_tile_x;
 587         else if (gy == ty || (gy == ty + 1 && gx < tx))
 588             *dy = +1;
 589         else
 590             *dy = -1;
 591
 592     else if (nx == tx) /* gy > ny */
 593         if (gx > nx)
 594             *dy = -1;
 595         else
 596             *dx = +1;
 597     else if (gx == nx)
 598         *dx = to_goal_x;
 599     else if (gap_x_on_goal_side)
 600         if (gy == ty + 1 && gx < tx)
 601             *dx = to_tile_x;
 602         else
 603             *dy = -1;
 604
 605     else if (ny - ty > abs(nx - tx))
 606         *dy = -1;
 607     else
 608         *dx = to_tile_x;
 609 }
 610
 611 static int compute_hint(const game_state *state, int *out_x, int *out_y)
 612 {
 613     /* The overall solving process is this:
 614      * 1. Find the next piece to be put in its place
 615      * 2. Move it diagonally towards its place
 616      * 3. Move it horizontally or vertically towards its place
 617      * (Modulo the last two tiles at the end of each row/column)
 618      */
 619
 620     int gx = X(state, state->gap_pos);
 621     int gy = Y(state, state->gap_pos);
 622
 623     int tx, ty, nx, ny, ox, oy, /* {target,next,next2}_{x,y} */ i;
 624     int dx = 0, dy = 0;
 625
 626     /* 1. Find the next piece
 627      * if (there are no more unfinished columns than rows) {
 628      *     fill the top-most row, left to right
 629      * } else { fill the left-most column, top to bottom }
 630      */
 631     const int w = state->w, h = state->h, n = w*h;
 632     int next_piece = 0, next_piece_2 = 0, solr = 0, solc = 0;
 633     int unsolved_rows = h, unsolved_cols = w;
 634
 635     assert(out_x);
 636     assert(out_y);
 637
 638     while (solr < h && solc < w) {
 639         int start, step, stop;
 640         if (unsolved_cols <= unsolved_rows)
 641             start = solr*w + solc, step = 1, stop = unsolved_cols;
 642         else
 643             start = solr*w + solc, step = w, stop = unsolved_rows;
 644         for (i = 0; i < stop; ++i) {
 645             const int j = start + i*step;
 646             if (state->tiles[j] != j + 1) {
 647                 next_piece = j + 1;
 648                 next_piece_2 = next_piece + step;
 649                 break;
 650             }
 651         }
 652         if (i < stop) break;
 653
 654         (unsolved_cols <= unsolved_rows)
 655             ? (++solr, --unsolved_rows)
 656             : (++solc, --unsolved_cols);
 657     }
 658
 659     if (next_piece == n)
 660         return FALSE;
 661
 662     /* 2, 3. Move the next piece towards its place */
 663
 664     /* gx, gy already set */
 665     tx = X(state, next_piece - 1); /* where we're going */
 666     ty = Y(state, next_piece - 1);
 667     for (i = 0; i < n && state->tiles[i] != next_piece; ++i);
 668     nx = X(state, i); /* where we're at */
 669     ny = Y(state, i);
 670     for (i = 0; i < n && state->tiles[i] != next_piece_2; ++i);
 671     ox = X(state, i);
 672     oy = Y(state, i);
 673
 674     if (unsolved_cols <= unsolved_rows)
 675         next_move(nx, ny, ox, oy, gx, gy, tx, ty, w, &dx, &dy);
 676     else
 677         next_move(ny, nx, oy, ox, gy, gx, ty, tx, h, &dy, &dx);
 678
 679     assert (dx || dy);
 680
 681     *out_x = gx + dx;
 682     *out_y = gy + dy;
 683     return TRUE;
 684 }
 685
 686 static char *interpret_move(const game_state *state, game_ui *ui,
 687                             const game_drawstate *ds,
 688                             int x, int y, int button)
 689 {
 690     int cx = X(state, state->gap_pos), nx = cx;
 691     int cy = Y(state, state->gap_pos), ny = cy;
 692     char buf[80];
 693
 694     button &= ~MOD_MASK;
 695
 696     if (button == LEFT_BUTTON) {
 697         nx = FROMCOORD(x);
 698         ny = FROMCOORD(y);
 699         if (nx < 0 || nx >= state->w || ny < 0 || ny >= state->h)
 700             return NULL;               /* out of bounds */
 701     } else if (IS_CURSOR_MOVE(button)) {
 702         static int invert_cursor = -1;
 703         if (invert_cursor == -1) {
 704             char *env = getenv("FIFTEEN_INVERT_CURSOR");
 705             invert_cursor = (env && (env[0] == 'y' || env[0] == 'Y'));
 706         }
 707         button = flip_cursor(button); /* the default */
 708         if (invert_cursor)
 709             button = flip_cursor(button); /* undoes the first flip */
 710         move_cursor(button, &nx, &ny, state->w, state->h, FALSE);
 711     } else if ((button == 'h' || button == 'H') && !state->completed) {
 712         if (!compute_hint(state, &nx, &ny))
 713             return NULL; /* shouldn't happen, since ^^we^^checked^^ */
 714     } else
 715         return NULL;                   /* no move */
 716
 717     /*
 718      * Any click location should be equal to the gap location
 719      * in _precisely_ one coordinate.
 720      */
 721     if ((cx == nx) ^ (cy == ny)) {
 722         sprintf(buf, "M%d,%d", nx, ny);
 723         return dupstr(buf);
 724     }
 725
 726     return NULL;
 727 }
 728
 729 static game_state *execute_move(const game_state *from, const char *move)
 730 {
 731     int gx, gy, dx, dy, ux, uy, up, p;
 732     game_state *ret;
 733
 734     if (!strcmp(move, "S")) {
 735         int i;
 736
 737         ret = dup_game(from);
 738
 739         /*
 740          * Simply replace the grid with a solved one. For this game,
 741          * this isn't a useful operation for actually telling the user
 742          * what they should have done, but it is useful for
 743          * conveniently being able to get hold of a clean state from
 744          * which to practise manoeuvres.
 745          */
 746         for (i = 0; i < ret->n; i++)
 747             ret->tiles[i] = (i+1) % ret->n;
 748         ret->gap_pos = ret->n-1;
 749         ret->used_solve = TRUE;
 750         ret->completed = ret->movecount = 1;
 751
 752         return ret;
 753     }
 754
 755     gx = X(from, from->gap_pos);
 756     gy = Y(from, from->gap_pos);
 757
 758     if (move[0] != 'M' ||
 759         sscanf(move+1, "%d,%d", &dx, &dy) != 2 ||
 760         (dx == gx && dy == gy) || (dx != gx && dy != gy) ||
 761         dx < 0 || dx >= from->w || dy < 0 || dy >= from->h)
 762         return NULL;
 763
 764     /*
 765      * Find the unit displacement from the original gap
 766      * position towards this one.
 767      */
 768     ux = (dx < gx ? -1 : dx > gx ? +1 : 0);
 769     uy = (dy < gy ? -1 : dy > gy ? +1 : 0);
 770     up = C(from, ux, uy);
 771
 772     ret = dup_game(from);
 773
 774     ret->gap_pos = C(from, dx, dy);
 775     assert(ret->gap_pos >= 0 && ret->gap_pos < ret->n);
 776
 777     ret->tiles[ret->gap_pos] = 0;
 778
 779     for (p = from->gap_pos; p != ret->gap_pos; p += up) {
 780         assert(p >= 0 && p < from->n);
 781         ret->tiles[p] = from->tiles[p + up];
 782         ret->movecount++;
 783     }
 784
 785     /*
 786      * See if the game has been completed.
 787      */
 788     if (!ret->completed) {
 789         ret->completed = ret->movecount;
 790         for (p = 0; p < ret->n; p++)
 791             if (ret->tiles[p] != (p < ret->n-1 ? p+1 : 0))
 792                 ret->completed = 0;
 793     }
 794
 795     return ret;
 796 }
 797
 798 /* ----------------------------------------------------------------------
 799  * Drawing routines.
 800  */
 801
 802 static void game_compute_size(const game_params *params, int tilesize,
 803                               int *x, int *y)
 804 {
 805     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
 806     struct { int tilesize; } ads, *ds = &ads;
 807     ads.tilesize = tilesize;
 808
 809     *x = TILE_SIZE * params->w + 2 * BORDER;
 810     *y = TILE_SIZE * params->h + 2 * BORDER;
 811 }
 812
 813 static void game_set_size(drawing *dr, game_drawstate *ds,
 814                           const game_params *params, int tilesize)
 815 {
 816     ds->tilesize = tilesize;
 817 }
 818
 819 static float *game_colours(frontend *fe, int *ncolours)
 820 {
 821     float *ret = snewn(3 * NCOLOURS, float);
 822     int i;
 823
 824     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
 825
 826     for (i = 0; i < 3; i++)
 827         ret[COL_TEXT * 3 + i] = 0.0;
 828
 829     *ncolours = NCOLOURS;
 830     return ret;
 831 }
 832
 833 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
 834 {
 835     struct game_drawstate *ds = snew(struct game_drawstate);
 836     int i;
 837
 838     ds->started = FALSE;
 839     ds->w = state->w;
 840     ds->h = state->h;
 841     ds->bgcolour = COL_BACKGROUND;
 842     ds->tiles = snewn(ds->w*ds->h, int);
 843     ds->tilesize = 0;                  /* haven't decided yet */
 844     for (i = 0; i < ds->w*ds->h; i++)
 845         ds->tiles[i] = -1;
 846
 847     return ds;
 848 }
 849
 850 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
 851 {
 852     sfree(ds->tiles);
 853     sfree(ds);
 854 }
 855
 856 static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state,
 857                       int x, int y, int tile, int flash_colour)
 858 {
 859     if (tile == 0) {
 860         draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE,
 861                   flash_colour);
 862     } else {
 863         int coords[6];
 864         char str[40];
 865
 866         coords[0] = x + TILE_SIZE - 1;
 867         coords[1] = y + TILE_SIZE - 1;
 868         coords[2] = x + TILE_SIZE - 1;
 869         coords[3] = y;
 870         coords[4] = x;
 871         coords[5] = y + TILE_SIZE - 1;
 872         draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
 873
 874         coords[0] = x;
 875         coords[1] = y;
 876         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
 877
 878         draw_rect(dr, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
 879                   TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
 880                   flash_colour);
 881
 882         sprintf(str, "%d", tile);
 883         draw_text(dr, x + TILE_SIZE/2, y + TILE_SIZE/2,
 884                   FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE,
 885                   COL_TEXT, str);
 886     }
 887     draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
 888 }
 889
 890 static void game_redraw(drawing *dr, game_drawstate *ds,
 891                         const game_state *oldstate, const game_state *state,
 892                         int dir, const game_ui *ui,
 893                         float animtime, float flashtime)
 894 {
 895     int i, pass, bgcolour;
 896
 897     if (flashtime > 0) {
 898         int frame = (int)(flashtime / FLASH_FRAME);
 899         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
 900     } else
 901         bgcolour = COL_BACKGROUND;
 902
 903     if (!ds->started) {
 904         int coords[10];
 905
 906         draw_rect(dr, 0, 0,
 907                   TILE_SIZE * state->w + 2 * BORDER,
 908                   TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
 909         draw_update(dr, 0, 0,
 910                     TILE_SIZE * state->w + 2 * BORDER,
 911                     TILE_SIZE * state->h + 2 * BORDER);
 912
 913         /*
 914          * Recessed area containing the whole puzzle.
 915          */
 916         coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 917         coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 918         coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1;
 919         coords[3] = COORD(0) - HIGHLIGHT_WIDTH;
 920         coords[4] = coords[2] - TILE_SIZE;
 921         coords[5] = coords[3] + TILE_SIZE;
 922         coords[8] = COORD(0) - HIGHLIGHT_WIDTH;
 923         coords[9] = COORD(state->h) + HIGHLIGHT_WIDTH - 1;
 924         coords[6] = coords[8] + TILE_SIZE;
 925         coords[7] = coords[9] - TILE_SIZE;
 926         draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
 927
 928         coords[1] = COORD(0) - HIGHLIGHT_WIDTH;
 929         coords[0] = COORD(0) - HIGHLIGHT_WIDTH;
 930         draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
 931
 932         ds->started = TRUE;
 933     }
 934
 935     /*
 936      * Now draw each tile. We do this in two passes to make
 937      * animation easy.
 938      */
 939     for (pass = 0; pass < 2; pass++) {
 940         for (i = 0; i < state->n; i++) {
 941             int t, t0;
 942             /*
 943              * Figure out what should be displayed at this
 944              * location. It's either a simple tile, or it's a
 945              * transition between two tiles (in which case we say
 946              * -1 because it must always be drawn).
 947              */
 948
 949             if (oldstate && oldstate->tiles[i] != state->tiles[i])
 950                 t = -1;
 951             else
 952                 t = state->tiles[i];
 953
 954             t0 = t;
 955
 956             if (ds->bgcolour != bgcolour ||   /* always redraw when flashing */
 957                 ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) {
 958                 int x, y;
 959
 960                 /*
 961                  * Figure out what to _actually_ draw, and where to
 962                  * draw it.
 963                  */
 964                 if (t == -1) {
 965                     int x0, y0, x1, y1;
 966                     int j;
 967
 968                     /*
 969                      * On the first pass, just blank the tile.
 970                      */
 971                     if (pass == 0) {
 972                         x = COORD(X(state, i));
 973                         y = COORD(Y(state, i));
 974                         t = 0;
 975                     } else {
 976                         float c;
 977
 978                         t = state->tiles[i];
 979
 980                         /*
 981                          * Don't bother moving the gap; just don't
 982                          * draw it.
 983                          */
 984                         if (t == 0)
 985                             continue;
 986
 987                         /*
 988                          * Find the coordinates of this tile in the old and
 989                          * new states.
 990                          */
 991                         x1 = COORD(X(state, i));
 992                         y1 = COORD(Y(state, i));
 993                         for (j = 0; j < oldstate->n; j++)
 994                             if (oldstate->tiles[j] == state->tiles[i])
 995                                 break;
 996                         assert(j < oldstate->n);
 997                         x0 = COORD(X(state, j));
 998                         y0 = COORD(Y(state, j));
 999
1000                         c = (animtime / ANIM_TIME);
1001                         if (c < 0.0F) c = 0.0F;
1002                         if (c > 1.0F) c = 1.0F;
1003
1004                         x = x0 + (int)(c * (x1 - x0));
1005                         y = y0 + (int)(c * (y1 - y0));
1006                     }
1007
1008                 } else {
1009                     if (pass == 0)
1010                         continue;
1011                     x = COORD(X(state, i));
1012                     y = COORD(Y(state, i));
1013                 }
1014
1015                 draw_tile(dr, ds, state, x, y, t, bgcolour);
1016             }
1017             ds->tiles[i] = t0;
1018         }
1019     }
1020     ds->bgcolour = bgcolour;
1021
1022     /*
1023      * Update the status bar.
1024      */
1025     {
1026         char statusbuf[256];
1027
1028         /*
1029          * Don't show the new status until we're also showing the
1030          * new _state_ - after the game animation is complete.
1031          */
1032         if (oldstate)
1033             state = oldstate;
1034
1035         if (state->used_solve)
1036             sprintf(statusbuf, "Moves since auto-solve: %d",
1037                     state->movecount - state->completed);
1038         else
1039             sprintf(statusbuf, "%sMoves: %d",
1040                     (state->completed ? "COMPLETED! " : ""),
1041                     (state->completed ? state->completed : state->movecount));
1042
1043         status_bar(dr, statusbuf);
1044     }
1045 }
1046
1047 static float game_anim_length(const game_state *oldstate,
1048                               const game_state *newstate, int dir, game_ui *ui)
1049 {
1050     return ANIM_TIME;
1051 }
1052
1053 static float game_flash_length(const game_state *oldstate,
1054                                const game_state *newstate, int dir, game_ui *ui)
1055 {
1056     if (!oldstate->completed && newstate->completed &&
1057         !oldstate->used_solve && !newstate->used_solve)
1058         return 2 * FLASH_FRAME;
1059     else
1060         return 0.0F;
1061 }
1062
1063 static int game_status(const game_state *state)
1064 {
1065     return state->completed ? +1 : 0;
1066 }
1067
1068 static int game_timing_state(const game_state *state, game_ui *ui)
1069 {
1070     return TRUE;
1071 }
1072
1073 static void game_print_size(const game_params *params, float *x, float *y)
1074 {
1075 }
1076
1077 static void game_print(drawing *dr, const game_state *state, int tilesize)
1078 {
1079 }
1080
1081 #ifdef COMBINED
1082 #define thegame fifteen
1083 #endif
1084
1085 const struct game thegame = {
1086     "Fifteen", "games.fifteen", "fifteen",
1087     default_params,
1088     game_fetch_preset, NULL,
1089     decode_params,
1090     encode_params,
1091     free_params,
1092     dup_params,
1093     TRUE, game_configure, custom_params,
1094     validate_params,
1095     new_game_desc,
1096     validate_desc,
1097     new_game,
1098     dup_game,
1099     free_game,
1100     TRUE, solve_game,
1101     TRUE, game_can_format_as_text_now, game_text_format,
1102     new_ui,
1103     free_ui,
1104     encode_ui,
1105     decode_ui,
1106     game_changed_state,
1107     interpret_move,
1108     execute_move,
1109     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1110     game_colours,
1111     game_new_drawstate,
1112     game_free_drawstate,
1113     game_redraw,
1114     game_anim_length,
1115     game_flash_length,
1116     game_status,
1117     FALSE, FALSE, game_print_size, game_print,
1118     TRUE,                              /* wants_statusbar */
1119     FALSE, game_timing_state,
1120     0,                                 /* flags */
1121 };
1122
1123 #ifdef STANDALONE_SOLVER
1124
1125 int main(int argc, char **argv)
1126 {
1127     game_params *params;
1128     game_state *state;
1129     char *id = NULL, *desc;
1130     const char *err;
1131     int grade = FALSE;
1132     char *progname = argv[0];
1133
1134     char buf[80];
1135     int limit, x, y, solvable;
1136
1137     while (--argc > 0) {
1138         char *p = *++argv;
1139         if (!strcmp(p, "-v")) {
1140             /* solver_show_working = TRUE; */
1141         } else if (!strcmp(p, "-g")) {
1142             grade = TRUE;
1143         } else if (*p == '-') {
1144             fprintf(stderr, "%s: unrecognised option `%s'\n", progname, p);
1145             return 1;
1146         } else {
1147             id = p;
1148         }
1149     }
1150
1151     if (!id) {
1152         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
1153         return 1;
1154     }
1155
1156     desc = strchr(id, ':');
1157     if (!desc) {
1158         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
1159         return 1;
1160     }
1161     *desc++ = '\0';
1162
1163     params = default_params();
1164     decode_params(params, id);
1165     err = validate_desc(params, desc);
1166     if (err) {
1167         free_params(params);
1168         fprintf(stderr, "%s: %s\n", argv[0], err);
1169         return 1;
1170     }
1171
1172     state = new_game(NULL, params, desc);
1173     free_params(params);
1174
1175     solvable = (PARITY_S(state) == perm_parity(state->tiles, state->n));
1176     if (grade || !solvable) {
1177         free_game(state);
1178         fputs(solvable ? "Game is solvable" : "Game is unsolvable",
1179               grade ? stdout : stderr);
1180         return !grade;
1181     }
1182
1183     for (limit = 5 * state->n * state->n * state->n; limit; --limit) {
1184         game_state *next_state;
1185         if (!compute_hint(state, &x, &y)) {
1186             fprintf(stderr, "couldn't compute next move while solving %s:%s",
1187                     id, desc);
1188             return 1;
1189         }
1190         printf("Move the space to (%d, %d), moving %d into the space\n",
1191                x + 1, y + 1, state->tiles[C(state, x, y)]);
1192         sprintf(buf, "M%d,%d", x, y);
1193         next_state = execute_move(state, buf);
1194
1195         free_game(state);
1196         if (!next_state) {
1197             fprintf(stderr, "invalid move when solving %s:%s\n", id, desc);
1198             return 1;
1199         }
1200         state = next_state;
1201         if (next_state->completed) {
1202             free_game(state);
1203             return 0;
1204         }
1205     }
1206
1207     free_game(state);
1208     fprintf(stderr, "ran out of moves for %s:%s\n", id, desc);
1209     return 1;
1210 }
1211
1212 #endif