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