slant.c

   1 /*
   2  * slant.c: Puzzle from nikoli.co.jp involving drawing a diagonal
   3  * line through each square of a grid.
   4  */
   5
   6 /*
   7  * In this puzzle you have a grid of squares, each of which must
   8  * contain a diagonal line; you also have clue numbers placed at
   9  * _points_ of that grid, which means there's a (w+1) x (h+1) array
  10  * of possible clue positions.
  11  *
  12  * I'm therefore going to adopt a rigid convention throughout this
  13  * source file of using w and h for the dimensions of the grid of
  14  * squares, and W and H for the dimensions of the grid of points.
  15  * Thus, W == w+1 and H == h+1 always.
  16  *
  17  * Clue arrays will be W*H `signed char's, and the clue at each
  18  * point will be a number from 0 to 4, or -1 if there's no clue.
  19  *
  20  * Solution arrays will be W*H `signed char's, and the number at
  21  * each point will be +1 for a forward slash (/), -1 for a
  22  * backslash (\), and 0 for unknown.
  23  */
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <assert.h>
  29 #include <ctype.h>
  30 #include <math.h>
  31
  32 #include "puzzles.h"
  33
  34 enum {
  35     COL_BACKGROUND,
  36     COL_GRID,
  37     COL_INK,
  38     NCOLOURS
  39 };
  40
  41 struct game_params {
  42     int w, h;
  43 };
  44
  45 typedef struct game_clues {
  46     int w, h;
  47     signed char *clues;
  48     int *dsf;                          /* scratch space for completion check */
  49     int refcount;
  50 } game_clues;
  51
  52 struct game_state {
  53     struct game_params p;
  54     game_clues *clues;
  55     signed char *soln;
  56     int completed;
  57     int used_solve;                    /* used to suppress completion flash */
  58 };
  59
  60 static game_params *default_params(void)
  61 {
  62     game_params *ret = snew(game_params);
  63
  64     ret->w = ret->h = 8;
  65
  66     return ret;
  67 }
  68
  69 static const struct game_params slant_presets[] = {
  70   {5, 5},
  71   {8, 8},
  72   {12, 10},
  73 };
  74
  75 static int game_fetch_preset(int i, char **name, game_params **params)
  76 {
  77     game_params *ret;
  78     char str[80];
  79
  80     if (i < 0 || i >= lenof(slant_presets))
  81         return FALSE;
  82
  83     ret = snew(game_params);
  84     *ret = slant_presets[i];
  85
  86     sprintf(str, "%dx%d", ret->w, ret->h);
  87
  88     *name = dupstr(str);
  89     *params = ret;
  90     return TRUE;
  91 }
  92
  93 static void free_params(game_params *params)
  94 {
  95     sfree(params);
  96 }
  97
  98 static game_params *dup_params(game_params *params)
  99 {
 100     game_params *ret = snew(game_params);
 101     *ret = *params;                    /* structure copy */
 102     return ret;
 103 }
 104
 105 static void decode_params(game_params *ret, char const *string)
 106 {
 107     ret->w = ret->h = atoi(string);
 108     while (*string && isdigit((unsigned char)*string)) string++;
 109     if (*string == 'x') {
 110         string++;
 111         ret->h = atoi(string);
 112     }
 113 }
 114
 115 static char *encode_params(game_params *params, int full)
 116 {
 117     char data[256];
 118
 119     sprintf(data, "%dx%d", params->w, params->h);
 120
 121     return dupstr(data);
 122 }
 123
 124 static config_item *game_configure(game_params *params)
 125 {
 126     config_item *ret;
 127     char buf[80];
 128
 129     ret = snewn(3, config_item);
 130
 131     ret[0].name = "Width";
 132     ret[0].type = C_STRING;
 133     sprintf(buf, "%d", params->w);
 134     ret[0].sval = dupstr(buf);
 135     ret[0].ival = 0;
 136
 137     ret[1].name = "Height";
 138     ret[1].type = C_STRING;
 139     sprintf(buf, "%d", params->h);
 140     ret[1].sval = dupstr(buf);
 141     ret[1].ival = 0;
 142
 143     ret[2].name = NULL;
 144     ret[2].type = C_END;
 145     ret[2].sval = NULL;
 146     ret[2].ival = 0;
 147
 148     return ret;
 149 }
 150
 151 static game_params *custom_params(config_item *cfg)
 152 {
 153     game_params *ret = snew(game_params);
 154
 155     ret->w = atoi(cfg[0].sval);
 156     ret->h = atoi(cfg[1].sval);
 157
 158     return ret;
 159 }
 160
 161 static char *validate_params(game_params *params, int full)
 162 {
 163     /*
 164      * (At least at the time of writing this comment) The grid
 165      * generator is actually capable of handling even zero grid
 166      * dimensions without crashing. Puzzles with a zero-area grid
 167      * are a bit boring, though, because they're already solved :-)
 168      */
 169
 170     if (params->w < 1 || params->h < 1)
 171         return "Width and height must both be at least one";
 172
 173     return NULL;
 174 }
 175
 176 /*
 177  * Utility function used by both the solver and the filled-grid
 178  * generator.
 179  */
 180
 181 static void fill_square(int w, int h, int y, int x, int v,
 182                         signed char *soln, int *dsf)
 183 {
 184     int W = w+1 /*, H = h+1 */;
 185
 186     soln[y*w+x] = v;
 187
 188     if (v < 0)
 189         dsf_merge(dsf, y*W+x, (y+1)*W+(x+1));
 190     else
 191         dsf_merge(dsf, y*W+(x+1), (y+1)*W+x);
 192 }
 193
 194 /*
 195  * Scratch space for solver.
 196  */
 197 struct solver_scratch {
 198     int *dsf;
 199 };
 200
 201 struct solver_scratch *new_scratch(int w, int h)
 202 {
 203     int W = w+1, H = h+1;
 204     struct solver_scratch *ret = snew(struct solver_scratch);
 205     ret->dsf = snewn(W*H, int);
 206     return ret;
 207 }
 208
 209 void free_scratch(struct solver_scratch *sc)
 210 {
 211     sfree(sc->dsf);
 212     sfree(sc);
 213 }
 214
 215 /*
 216  * Solver. Returns 0 for impossibility, 1 for success, 2 for
 217  * ambiguity or failure to converge.
 218  */
 219 static int slant_solve(int w, int h, const signed char *clues,
 220                        signed char *soln, struct solver_scratch *sc)
 221 {
 222     int W = w+1, H = h+1;
 223     int x, y, i;
 224     int done_something;
 225
 226     /*
 227      * Clear the output.
 228      */
 229     memset(soln, 0, w*h);
 230
 231     /*
 232      * Establish a disjoint set forest for tracking connectedness
 233      * between grid points.
 234      */
 235     for (i = 0; i < W*H; i++)
 236         sc->dsf[i] = i;                /* initially all distinct */
 237
 238     /*
 239      * Repeatedly try to deduce something until we can't.
 240      */
 241     do {
 242         done_something = FALSE;
 243
 244         /*
 245          * Any clue point with the number of remaining lines equal
 246          * to zero or to the number of remaining undecided
 247          * neighbouring squares can be filled in completely.
 248          */
 249         for (y = 0; y < H; y++)
 250             for (x = 0; x < W; x++) {
 251                 int nu, nl, v, c;
 252
 253                 if ((c = clues[y*W+x]) < 0)
 254                     continue;
 255
 256                 /*
 257                  * We have a clue point. Count up the number of
 258                  * undecided neighbours, and also the number of
 259                  * lines already present.
 260                  */
 261                 nu = 0;
 262                 nl = c;
 263                 if (x > 0 && y > 0 && (v = soln[(y-1)*w+(x-1)]) != +1)
 264                     v == 0 ? nu++ : nl--;
 265                 if (x > 0 && y < h && (v = soln[y*w+(x-1)]) != -1)
 266                     v == 0 ? nu++ : nl--;
 267                 if (x < w && y > 0 && (v = soln[(y-1)*w+x]) != -1)
 268                     v == 0 ? nu++ : nl--;
 269                 if (x < w && y < h && (v = soln[y*w+x]) != +1)
 270                     v == 0 ? nu++ : nl--;
 271
 272                 /*
 273                  * Check the counts.
 274                  */
 275                 if (nl < 0 || nl > nu) {
 276                     /*
 277                      * No consistent value for this at all!
 278                      */
 279                     return 0;          /* impossible */
 280                 }
 281
 282                 if (nu > 0 && (nl == 0 || nl == nu)) {
 283 #ifdef SOLVER_DIAGNOSTICS
 284                     printf("%s around clue point at %d,%d\n",
 285                            nl ? "filling" : "emptying", x, y);
 286 #endif
 287                     if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] == 0)
 288                         fill_square(w, h, y-1, x-1, (nl ? -1 : +1), soln,
 289                                     sc->dsf);
 290                     if (x > 0 && y < h && soln[y*w+(x-1)] == 0)
 291                         fill_square(w, h, y, x-1, (nl ? +1 : -1), soln,
 292                                     sc->dsf);
 293                     if (x < w && y > 0 && soln[(y-1)*w+x] == 0)
 294                         fill_square(w, h, y-1, x, (nl ? +1 : -1), soln,
 295                                     sc->dsf);
 296                     if (x < w && y < h && soln[y*w+x] == 0)
 297                         fill_square(w, h, y, x, (nl ? -1 : +1), soln,
 298                                     sc->dsf);
 299
 300                     done_something = TRUE;
 301                 }
 302             }
 303
 304         if (done_something)
 305             continue;
 306
 307         /*
 308          * Failing that, we now apply the second condition, which
 309          * is that no square may be filled in such a way as to form
 310          * a loop.
 311          */
 312         for (y = 0; y < h; y++)
 313             for (x = 0; x < w; x++) {
 314                 int fs, bs;
 315
 316                 if (soln[y*w+x])
 317                     continue;          /* got this one already */
 318
 319                 fs = (dsf_canonify(sc->dsf, y*W+x) ==
 320                       dsf_canonify(sc->dsf, (y+1)*W+(x+1)));
 321                 bs = (dsf_canonify(sc->dsf, (y+1)*W+x) ==
 322                       dsf_canonify(sc->dsf, y*W+(x+1)));
 323
 324                 if (fs && bs) {
 325                     /*
 326                      * Loop avoidance leaves no consistent value
 327                      * for this at all!
 328                      */
 329                     return 0;          /* impossible */
 330                 }
 331
 332                 if (fs) {
 333                     /*
 334                      * Top left and bottom right corners of this
 335                      * square are already connected, which means we
 336                      * aren't allowed to put a backslash in here.
 337                      */
 338 #ifdef SOLVER_DIAGNOSTICS
 339                     printf("placing / in %d,%d by loop avoidance\n", x, y);
 340 #endif
 341                     fill_square(w, h, y, x, +1, soln, sc->dsf);
 342                     done_something = TRUE;
 343                 } else if (bs) {
 344                     /*
 345                      * Top right and bottom left corners of this
 346                      * square are already connected, which means we
 347                      * aren't allowed to put a forward slash in
 348                      * here.
 349                      */
 350 #ifdef SOLVER_DIAGNOSTICS
 351                     printf("placing \\ in %d,%d by loop avoidance\n", x, y);
 352 #endif
 353                     fill_square(w, h, y, x, -1, soln, sc->dsf);
 354                     done_something = TRUE;
 355                 }
 356             }
 357
 358     } while (done_something);
 359
 360     /*
 361      * Solver can make no more progress. See if the grid is full.
 362      */
 363     for (i = 0; i < w*h; i++)
 364         if (!soln[i])
 365             return 2;                  /* failed to converge */
 366     return 1;                          /* success */
 367 }
 368
 369 /*
 370  * Filled-grid generator.
 371  */
 372 static void slant_generate(int w, int h, signed char *soln, random_state *rs)
 373 {
 374     int W = w+1, H = h+1;
 375     int x, y, i;
 376     int *dsf, *indices;
 377
 378     /*
 379      * Clear the output.
 380      */
 381     memset(soln, 0, w*h);
 382
 383     /*
 384      * Establish a disjoint set forest for tracking connectedness
 385      * between grid points.
 386      */
 387     dsf = snewn(W*H, int);
 388     for (i = 0; i < W*H; i++)
 389         dsf[i] = i;                    /* initially all distinct */
 390
 391     /*
 392      * Prepare a list of the squares in the grid, and fill them in
 393      * in a random order.
 394      */
 395     indices = snewn(w*h, int);
 396     for (i = 0; i < w*h; i++)
 397         indices[i] = i;
 398     shuffle(indices, w*h, sizeof(*indices), rs);
 399
 400     /*
 401      * Fill in each one in turn.
 402      */
 403     for (i = 0; i < w*h; i++) {
 404         int fs, bs, v;
 405
 406         y = indices[i] / w;
 407         x = indices[i] % w;
 408
 409         fs = (dsf_canonify(dsf, y*W+x) ==
 410               dsf_canonify(dsf, (y+1)*W+(x+1)));
 411         bs = (dsf_canonify(dsf, (y+1)*W+x) ==
 412               dsf_canonify(dsf, y*W+(x+1)));
 413
 414         /*
 415          * It isn't possible to get into a situation where we
 416          * aren't allowed to place _either_ type of slash in a
 417          * square.
 418          *
 419          * Proof (thanks to Gareth Taylor):
 420          *
 421          * If it were possible, it would have to be because there
 422          * was an existing path (not using this square) between the
 423          * top-left and bottom-right corners of this square, and
 424          * another between the other two. These two paths would
 425          * have to cross at some point.
 426          *
 427          * Obviously they can't cross in the middle of a square, so
 428          * they must cross by sharing a point in common. But this
 429          * isn't possible either: if you chessboard-colour all the
 430          * points on the grid, you find that any continuous
 431          * diagonal path is entirely composed of points of the same
 432          * colour. And one of our two hypothetical paths is between
 433          * two black points, and the other is between two white
 434          * points - therefore they can have no point in common. []
 435          */
 436         assert(!(fs && bs));
 437
 438         v = fs ? +1 : bs ? -1 : 2 * random_upto(rs, 2) - 1;
 439         fill_square(w, h, y, x, v, soln, dsf);
 440     }
 441
 442     sfree(indices);
 443     sfree(dsf);
 444 }
 445
 446 static char *new_game_desc(game_params *params, random_state *rs,
 447                            char **aux, int interactive)
 448 {
 449     int w = params->w, h = params->h, W = w+1, H = h+1;
 450     signed char *soln, *tmpsoln, *clues;
 451     int *clueindices;
 452     struct solver_scratch *sc;
 453     int x, y, v, i;
 454     char *desc;
 455
 456     soln = snewn(w*h, signed char);
 457     tmpsoln = snewn(w*h, signed char);
 458     clues = snewn(W*H, signed char);
 459     clueindices = snewn(W*H, int);
 460     sc = new_scratch(w, h);
 461
 462     do {
 463         /*
 464          * Create the filled grid.
 465          */
 466         slant_generate(w, h, soln, rs);
 467
 468         /*
 469          * Fill in the complete set of clues.
 470          */
 471         for (y = 0; y < H; y++)
 472             for (x = 0; x < W; x++) {
 473                 v = 0;
 474
 475                 if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] == -1) v++;
 476                 if (x > 0 && y < h && soln[y*w+(x-1)] == +1) v++;
 477                 if (x < w && y > 0 && soln[(y-1)*w+x] == +1) v++;
 478                 if (x < w && y < h && soln[y*w+x] == -1) v++;
 479
 480                 clues[y*W+x] = v;
 481             }
 482     } while (slant_solve(w, h, clues, tmpsoln, sc) != 1);
 483
 484     /*
 485      * Remove as many clues as possible while retaining solubility.
 486      */
 487     for (i = 0; i < W*H; i++)
 488         clueindices[i] = i;
 489     shuffle(clueindices, W*H, sizeof(*clueindices), rs);
 490     for (i = 0; i < W*H; i++) {
 491         y = clueindices[i] / W;
 492         x = clueindices[i] % W;
 493         v = clues[y*W+x];
 494         clues[y*W+x] = -1;
 495         if (slant_solve(w, h, clues, tmpsoln, sc) != 1)
 496             clues[y*W+x] = v;          /* put it back */
 497     }
 498
 499     /*
 500      * Now we have the clue set as it will be presented to the
 501      * user. Encode it in a game desc.
 502      */
 503     {
 504         char *p;
 505         int run, i;
 506
 507         desc = snewn(W*H+1, char);
 508         p = desc;
 509         run = 0;
 510         for (i = 0; i <= W*H; i++) {
 511             int n = (i < W*H ? clues[i] : -2);
 512
 513             if (n == -1)
 514                 run++;
 515             else {
 516                 if (run) {
 517                     while (run > 0) {
 518                         int c = 'a' - 1 + run;
 519                         if (run > 26)
 520                             c = 'z';
 521                         *p++ = c;
 522                         run -= c - ('a' - 1);
 523                     }
 524                 }
 525                 if (n >= 0)
 526                     *p++ = '0' + n;
 527                 run = 0;
 528             }
 529         }
 530         assert(p - desc <= W*H);
 531         *p++ = '\0';
 532         desc = sresize(desc, p - desc, char);
 533     }
 534
 535     /*
 536      * Encode the solution as an aux_info.
 537      */
 538     {
 539         char *auxbuf;
 540         *aux = auxbuf = snewn(w*h+1, char);
 541         for (i = 0; i < w*h; i++)
 542             auxbuf[i] = soln[i] < 0 ? '\\' : '/';
 543         auxbuf[w*h] = '\0';
 544     }
 545
 546     free_scratch(sc);
 547     sfree(clueindices);
 548     sfree(clues);
 549     sfree(tmpsoln);
 550     sfree(soln);
 551
 552     return desc;
 553 }
 554
 555 static char *validate_desc(game_params *params, char *desc)
 556 {
 557     int w = params->w, h = params->h, W = w+1, H = h+1;
 558     int area = W*H;
 559     int squares = 0;
 560
 561     while (*desc) {
 562         int n = *desc++;
 563         if (n >= 'a' && n <= 'z') {
 564             squares += n - 'a' + 1;
 565         } else if (n >= '0' && n <= '4') {
 566             squares++;
 567         } else
 568             return "Invalid character in game description";
 569     }
 570
 571     if (squares < area)
 572         return "Not enough data to fill grid";
 573
 574     if (squares > area)
 575         return "Too much data to fit in grid";
 576
 577     return NULL;
 578 }
 579
 580 static game_state *new_game(midend_data *me, game_params *params, char *desc)
 581 {
 582     int w = params->w, h = params->h, W = w+1, H = h+1;
 583     game_state *state = snew(game_state);
 584     int area = W*H;
 585     int squares = 0;
 586
 587     state->p = *params;
 588     state->soln = snewn(w*h, signed char);
 589     memset(state->soln, 0, w*h);
 590     state->completed = state->used_solve = FALSE;
 591
 592     state->clues = snew(game_clues);
 593     state->clues->w = w;
 594     state->clues->h = h;
 595     state->clues->clues = snewn(W*H, signed char);
 596     state->clues->refcount = 1;
 597     state->clues->dsf = snewn(W*H, int);
 598     memset(state->clues->clues, -1, W*H);
 599     while (*desc) {
 600         int n = *desc++;
 601         if (n >= 'a' && n <= 'z') {
 602             squares += n - 'a' + 1;
 603         } else if (n >= '0' && n <= '4') {
 604             state->clues->clues[squares++] = n - '0';
 605         } else
 606             assert(!"can't get here");
 607     }
 608     assert(squares == area);
 609
 610     return state;
 611 }
 612
 613 static game_state *dup_game(game_state *state)
 614 {
 615     int w = state->p.w, h = state->p.h;
 616     game_state *ret = snew(game_state);
 617
 618     ret->p = state->p;
 619     ret->clues = state->clues;
 620     ret->clues->refcount++;
 621     ret->completed = state->completed;
 622     ret->used_solve = state->used_solve;
 623
 624     ret->soln = snewn(w*h, signed char);
 625     memcpy(ret->soln, state->soln, w*h);
 626
 627     return ret;
 628 }
 629
 630 static void free_game(game_state *state)
 631 {
 632     sfree(state);
 633 }
 634
 635 static int check_completion(game_state *state)
 636 {
 637     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
 638     int i, x, y;
 639
 640     /*
 641      * Establish a disjoint set forest for tracking connectedness
 642      * between grid points. Use the dsf scratch space in the shared
 643      * clues structure, to avoid mallocing too often.
 644      */
 645     for (i = 0; i < W*H; i++)
 646         state->clues->dsf[i] = i;      /* initially all distinct */
 647
 648     /*
 649      * Now go through the grid checking connectedness. While we're
 650      * here, also check that everything is filled in.
 651      */
 652     for (y = 0; y < h; y++)
 653         for (x = 0; x < w; x++) {
 654             int i1, i2;
 655
 656             if (state->soln[y*w+x] == 0)
 657                 return FALSE;
 658             if (state->soln[y*w+x] < 0) {
 659                 i1 = y*W+x;
 660                 i2 = (y+1)*W+(x+1);
 661             } else {
 662                 i1 = (y+1)*W+x;
 663                 i2 = y*W+(x+1);
 664             }
 665
 666             /*
 667              * Our edge connects i1 with i2. If they're already
 668              * connected, return failure. Otherwise, link them.
 669              */
 670             if (dsf_canonify(state->clues->dsf, i1) ==
 671                 dsf_canonify(state->clues->dsf, i2))
 672                 return FALSE;
 673             else
 674                 dsf_merge(state->clues->dsf, i1, i2);
 675         }
 676
 677     /*
 678      * The grid is _a_ valid grid; let's see if it matches the
 679      * clues.
 680      */
 681     for (y = 0; y < H; y++)
 682         for (x = 0; x < W; x++) {
 683             int v, c;
 684
 685             if ((c = state->clues->clues[y*W+x]) < 0)
 686                 continue;
 687
 688             v = 0;
 689
 690             if (x > 0 && y > 0 && state->soln[(y-1)*w+(x-1)] == -1) v++;
 691             if (x > 0 && y < h && state->soln[y*w+(x-1)] == +1) v++;
 692             if (x < w && y > 0 && state->soln[(y-1)*w+x] == +1) v++;
 693             if (x < w && y < h && state->soln[y*w+x] == -1) v++;
 694
 695             if (c != v)
 696                 return FALSE;
 697         }
 698
 699     return TRUE;
 700 }
 701
 702 static char *solve_game(game_state *state, game_state *currstate,
 703                         char *aux, char **error)
 704 {
 705     int w = state->p.w, h = state->p.h;
 706     signed char *soln;
 707     int bs, ret;
 708     int free_soln = FALSE;
 709     char *move, buf[80];
 710     int movelen, movesize;
 711     int x, y;
 712
 713     if (aux) {
 714         /*
 715          * If we already have the solution, save ourselves some
 716          * time.
 717          */
 718         soln = (signed char *)aux;
 719         bs = (signed char)'\\';
 720         free_soln = FALSE;
 721     } else {
 722         struct solver_scratch *sc = new_scratch(w, h);
 723         soln = snewn(w*h, signed char);
 724         bs = -1;
 725         ret = slant_solve(w, h, state->clues->clues, soln, sc);
 726         free_scratch(sc);
 727         if (ret != 1) {
 728             sfree(soln);
 729             if (ret == 0)
 730                 return "This puzzle is not self-consistent";
 731             else
 732                 return "Unable to find a unique solution for this puzzle";
 733         }
 734         free_soln = TRUE;
 735     }
 736
 737     /*
 738      * Construct a move string which turns the current state into
 739      * the solved state.
 740      */
 741     movesize = 256;
 742     move = snewn(movesize, char);
 743     movelen = 0;
 744     move[movelen++] = 'S';
 745     move[movelen] = '\0';
 746     for (y = 0; y < h; y++)
 747         for (x = 0; x < w; x++) {
 748             int v = (soln[y*w+x] == bs ? -1 : +1);
 749             if (state->soln[y*w+x] != v) {
 750                 int len = sprintf(buf, ";%c%d,%d", v < 0 ? '\\' : '/', x, y);
 751                 if (movelen + len >= movesize) {
 752                     movesize = movelen + len + 256;
 753                     move = sresize(move, movesize, char);
 754                 }
 755                 strcpy(move + movelen, buf);
 756                 movelen += len;
 757             }
 758         }
 759
 760     if (free_soln)
 761         sfree(soln);
 762
 763     return move;
 764 }
 765
 766 static char *game_text_format(game_state *state)
 767 {
 768     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
 769     int x, y, len;
 770     char *ret, *p;
 771
 772     /*
 773      * There are h+H rows of w+W columns.
 774      */
 775     len = (h+H) * (w+W+1) + 1;
 776     ret = snewn(len, char);
 777     p = ret;
 778
 779     for (y = 0; y < H; y++) {
 780         for (x = 0; x < W; x++) {
 781             if (state->clues->clues[y*W+x] >= 0)
 782                 *p++ = state->clues->clues[y*W+x] + '0';
 783             else
 784                 *p++ = '+';
 785             if (x < w)
 786                 *p++ = '-';
 787         }
 788         *p++ = '\n';
 789         if (y < h) {
 790             for (x = 0; x < W; x++) {
 791                 *p++ = '|';
 792                 if (x < w) {
 793                     if (state->soln[y*w+x] != 0)
 794                         *p++ = (state->soln[y*w+x] < 0 ? '\\' : '/');
 795                     else
 796                         *p++ = ' ';
 797                 }
 798             }
 799             *p++ = '\n';
 800         }
 801     }
 802     *p++ = '\0';
 803
 804     assert(p - ret == len);
 805     return ret;
 806 }
 807
 808 static game_ui *new_ui(game_state *state)
 809 {
 810     return NULL;
 811 }
 812
 813 static void free_ui(game_ui *ui)
 814 {
 815 }
 816
 817 static char *encode_ui(game_ui *ui)
 818 {
 819     return NULL;
 820 }
 821
 822 static void decode_ui(game_ui *ui, char *encoding)
 823 {
 824 }
 825
 826 static void game_changed_state(game_ui *ui, game_state *oldstate,
 827                                game_state *newstate)
 828 {
 829 }
 830
 831 #define PREFERRED_TILESIZE 32
 832 #define TILESIZE (ds->tilesize)
 833 #define BORDER TILESIZE
 834 #define CLUE_RADIUS (TILESIZE / 3)
 835 #define CLUE_TEXTSIZE (TILESIZE / 2)
 836 #define COORD(x)  ( (x) * TILESIZE + BORDER )
 837 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
 838
 839 #define FLASH_TIME 0.30F
 840
 841 /*
 842  * Bit fields in the `grid' and `todraw' elements of the drawstate.
 843  */
 844 #define BACKSLASH 0x0001
 845 #define FORWSLASH 0x0002
 846 #define L_T       0x0004
 847 #define L_B       0x0008
 848 #define T_L       0x0010
 849 #define T_R       0x0020
 850 #define R_T       0x0040
 851 #define R_B       0x0080
 852 #define B_L       0x0100
 853 #define B_R       0x0200
 854 #define C_TL      0x0400
 855 #define C_TR      0x0800
 856 #define C_BL      0x1000
 857 #define C_BR      0x2000
 858 #define FLASH     0x4000
 859
 860 struct game_drawstate {
 861     int tilesize;
 862     int started;
 863     int *grid;
 864     int *todraw;
 865 };
 866
 867 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
 868                             int x, int y, int button)
 869 {
 870     int w = state->p.w, h = state->p.h;
 871
 872     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
 873         int v;
 874         char buf[80];
 875
 876         x = FROMCOORD(x);
 877         y = FROMCOORD(y);
 878         if (x < 0 || y < 0 || x >= w || y >= h)
 879             return NULL;
 880
 881         if (button == LEFT_BUTTON) {
 882             /*
 883              * Left-clicking cycles blank -> \ -> / -> blank.
 884              */
 885             v = state->soln[y*w+x] - 1;
 886             if (v == -2)
 887                 v = +1;
 888         } else {
 889             /*
 890              * Right-clicking cycles blank -> / -> \ -> blank.
 891              */
 892             v = state->soln[y*w+x] + 1;
 893             if (v == +2)
 894                 v = -1;
 895         }
 896
 897         sprintf(buf, "%c%d,%d", v==-1 ? '\\' : v==+1 ? '/' : 'C', x, y);
 898         return dupstr(buf);
 899     }
 900
 901     return NULL;
 902 }
 903
 904 static game_state *execute_move(game_state *state, char *move)
 905 {
 906     int w = state->p.w, h = state->p.h;
 907     char c;
 908     int x, y, n;
 909     game_state *ret = dup_game(state);
 910
 911     while (*move) {
 912         c = *move;
 913         if (c == 'S') {
 914             ret->used_solve = TRUE;
 915             move++;
 916         } else if (c == '\\' || c == '/' || c == 'C') {
 917             move++;
 918             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
 919                 x < 0 || y < 0 || x >= w || y >= h) {
 920                 free_game(ret);
 921                 return NULL;
 922             }
 923             ret->soln[y*w+x] = (c == '\\' ? -1 : c == '/' ? +1 : 0);
 924             move += n;
 925         } else {
 926             free_game(ret);
 927             return NULL;
 928         }
 929         if (*move == ';')
 930             move++;
 931         else if (*move) {
 932             free_game(ret);
 933             return NULL;
 934         }
 935     }
 936
 937     if (!ret->completed)
 938         ret->completed = check_completion(ret);
 939
 940     return ret;
 941 }
 942
 943 /* ----------------------------------------------------------------------
 944  * Drawing routines.
 945  */
 946
 947 static void game_compute_size(game_params *params, int tilesize,
 948                               int *x, int *y)
 949 {
 950     /* fool the macros */
 951     struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy;
 952
 953     *x = 2 * BORDER + params->w * TILESIZE + 1;
 954     *y = 2 * BORDER + params->h * TILESIZE + 1;
 955 }
 956
 957 static void game_set_size(game_drawstate *ds, game_params *params,
 958                           int tilesize)
 959 {
 960     ds->tilesize = tilesize;
 961 }
 962
 963 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
 964 {
 965     float *ret = snewn(3 * NCOLOURS, float);
 966
 967     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 968
 969     ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.7F;
 970     ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.7F;
 971     ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.7F;
 972
 973     ret[COL_INK * 3 + 0] = 0.0F;
 974     ret[COL_INK * 3 + 1] = 0.0F;
 975     ret[COL_INK * 3 + 2] = 0.0F;
 976
 977     *ncolours = NCOLOURS;
 978     return ret;
 979 }
 980
 981 static game_drawstate *game_new_drawstate(game_state *state)
 982 {
 983     int w = state->p.w, h = state->p.h;
 984     int i;
 985     struct game_drawstate *ds = snew(struct game_drawstate);
 986
 987     ds->tilesize = 0;
 988     ds->started = FALSE;
 989     ds->grid = snewn(w*h, int);
 990     ds->todraw = snewn(w*h, int);
 991     for (i = 0; i < w*h; i++)
 992         ds->grid[i] = ds->todraw[i] = -1;
 993
 994     return ds;
 995 }
 996
 997 static void game_free_drawstate(game_drawstate *ds)
 998 {
 999     sfree(ds->grid);
1000     sfree(ds);
1001 }
1002
1003 static void draw_clue(frontend *fe, game_drawstate *ds,
1004                       int x, int y, int v)
1005 {
1006     char p[2];
1007
1008     if (v < 0)
1009         return;
1010
1011     p[0] = v + '0';
1012     p[1] = '\0';
1013     draw_circle(fe, COORD(x), COORD(y), CLUE_RADIUS,
1014                 COL_BACKGROUND, COL_INK);
1015     draw_text(fe, COORD(x), COORD(y), FONT_VARIABLE,
1016               CLUE_TEXTSIZE, ALIGN_VCENTRE|ALIGN_HCENTRE,
1017               COL_INK, p);
1018 }
1019
1020 static void draw_tile(frontend *fe, game_drawstate *ds, game_clues *clues,
1021                       int x, int y, int v)
1022 {
1023     int w = clues->w /*, h = clues->h*/, W = w+1 /*, H = h+1 */;
1024     int xx, yy;
1025
1026     clip(fe, COORD(x), COORD(y), TILESIZE+1, TILESIZE+1);
1027
1028     draw_rect(fe, COORD(x), COORD(y), TILESIZE, TILESIZE,
1029               (v & FLASH) ? COL_GRID : COL_BACKGROUND);
1030
1031     /*
1032      * Draw the grid lines.
1033      */
1034     draw_line(fe, COORD(x), COORD(y), COORD(x+1), COORD(y), COL_GRID);
1035     draw_line(fe, COORD(x), COORD(y+1), COORD(x+1), COORD(y+1), COL_GRID);
1036     draw_line(fe, COORD(x), COORD(y), COORD(x), COORD(y+1), COL_GRID);
1037     draw_line(fe, COORD(x+1), COORD(y), COORD(x+1), COORD(y+1), COL_GRID);
1038
1039     /*
1040      * Draw the slash.
1041      */
1042     if (v & BACKSLASH) {
1043         draw_line(fe, COORD(x), COORD(y), COORD(x+1), COORD(y+1), COL_INK);
1044         draw_line(fe, COORD(x)+1, COORD(y), COORD(x+1), COORD(y+1)-1,
1045                   COL_INK);
1046         draw_line(fe, COORD(x), COORD(y)+1, COORD(x+1)-1, COORD(y+1),
1047                   COL_INK);
1048     } else if (v & FORWSLASH) {
1049         draw_line(fe, COORD(x+1), COORD(y), COORD(x), COORD(y+1), COL_INK);
1050         draw_line(fe, COORD(x+1)-1, COORD(y), COORD(x), COORD(y+1)-1,
1051                   COL_INK);
1052         draw_line(fe, COORD(x+1), COORD(y)+1, COORD(x)+1, COORD(y+1),
1053                   COL_INK);
1054     }
1055
1056     /*
1057      * Draw dots on the grid corners that appear if a slash is in a
1058      * neighbouring cell.
1059      */
1060     if (v & L_T)
1061         draw_rect(fe, COORD(x), COORD(y)+1, 1, 1, COL_INK);
1062     if (v & L_B)
1063         draw_rect(fe, COORD(x), COORD(y+1)-1, 1, 1, COL_INK);
1064     if (v & R_T)
1065         draw_rect(fe, COORD(x+1), COORD(y)+1, 1, 1, COL_INK);
1066     if (v & R_B)
1067         draw_rect(fe, COORD(x+1), COORD(y+1)-1, 1, 1, COL_INK);
1068     if (v & T_L)
1069         draw_rect(fe, COORD(x)+1, COORD(y), 1, 1, COL_INK);
1070     if (v & T_R)
1071         draw_rect(fe, COORD(x+1)-1, COORD(y), 1, 1, COL_INK);
1072     if (v & B_L)
1073         draw_rect(fe, COORD(x)+1, COORD(y+1), 1, 1, COL_INK);
1074     if (v & B_R)
1075         draw_rect(fe, COORD(x+1)-1, COORD(y+1), 1, 1, COL_INK);
1076     if (v & C_TL)
1077         draw_rect(fe, COORD(x), COORD(y), 1, 1, COL_INK);
1078     if (v & C_TR)
1079         draw_rect(fe, COORD(x+1), COORD(y), 1, 1, COL_INK);
1080     if (v & C_BL)
1081         draw_rect(fe, COORD(x), COORD(y+1), 1, 1, COL_INK);
1082     if (v & C_BR)
1083         draw_rect(fe, COORD(x+1), COORD(y+1), 1, 1, COL_INK);
1084
1085     /*
1086      * And finally the clues at the corners.
1087      */
1088     for (xx = x; xx <= x+1; xx++)
1089         for (yy = y; yy <= y+1; yy++)
1090             draw_clue(fe, ds, xx, yy, clues->clues[yy*W+xx]);
1091
1092     unclip(fe);
1093     draw_update(fe, COORD(x), COORD(y), TILESIZE+1, TILESIZE+1);
1094 }
1095
1096 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1097                         game_state *state, int dir, game_ui *ui,
1098                         float animtime, float flashtime)
1099 {
1100     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1101     int x, y;
1102     int flashing;
1103
1104     if (flashtime > 0)
1105         flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
1106     else
1107         flashing = FALSE;
1108
1109     if (!ds->started) {
1110         int ww, wh;
1111         game_compute_size(&state->p, TILESIZE, &ww, &wh);
1112         draw_rect(fe, 0, 0, ww, wh, COL_BACKGROUND);
1113         draw_update(fe, 0, 0, ww, wh);
1114
1115         /*
1116          * Draw any clues on the very edges (since normal tile
1117          * redraw won't draw the bits outside the grid boundary).
1118          */
1119         for (y = 0; y < H; y++) {
1120             draw_clue(fe, ds, 0, y, state->clues->clues[y*W+0]);
1121             draw_clue(fe, ds, w, y, state->clues->clues[y*W+w]);
1122         }
1123         for (x = 0; x < W; x++) {
1124             draw_clue(fe, ds, x, 0, state->clues->clues[0*W+x]);
1125             draw_clue(fe, ds, x, h, state->clues->clues[h*W+x]);
1126         }
1127
1128         ds->started = TRUE;
1129     }
1130
1131     /*
1132      * Loop over the grid and work out where all the slashes are.
1133      * We need to do this because a slash in one square affects the
1134      * drawing of the next one along.
1135      */
1136     for (y = 0; y < h; y++)
1137         for (x = 0; x < w; x++)
1138             ds->todraw[y*w+x] = flashing ? FLASH : 0;
1139
1140     for (y = 0; y < h; y++) {
1141         for (x = 0; x < w; x++) {
1142             if (state->soln[y*w+x] < 0) {
1143                 ds->todraw[y*w+x] |= BACKSLASH;
1144                 if (x > 0)
1145                     ds->todraw[y*w+(x-1)] |= R_T | C_TR;
1146                 if (x+1 < w)
1147                     ds->todraw[y*w+(x+1)] |= L_B | C_BL;
1148                 if (y > 0)
1149                     ds->todraw[(y-1)*w+x] |= B_L | C_BL;
1150                 if (y+1 < h)
1151                     ds->todraw[(y+1)*w+x] |= T_R | C_TR;
1152                 if (x > 0 && y > 0)
1153                     ds->todraw[(y-1)*w+(x-1)] |= C_BR;
1154                 if (x+1 < w && y+1 < h)
1155                     ds->todraw[(y+1)*w+(x+1)] |= C_TL;
1156             } else if (state->soln[y*w+x] > 0) {
1157                 ds->todraw[y*w+x] |= FORWSLASH;
1158                 if (x > 0)
1159                     ds->todraw[y*w+(x-1)] |= R_B | C_BR;
1160                 if (x+1 < w)
1161                     ds->todraw[y*w+(x+1)] |= L_T | C_TL;
1162                 if (y > 0)
1163                     ds->todraw[(y-1)*w+x] |= B_R | C_BR;
1164                 if (y+1 < h)
1165                     ds->todraw[(y+1)*w+x] |= T_L | C_TL;
1166                 if (x > 0 && y+1 < h)
1167                     ds->todraw[(y+1)*w+(x-1)] |= C_TR;
1168                 if (x+1 < w && y > 0)
1169                     ds->todraw[(y-1)*w+(x+1)] |= C_BL;
1170             }
1171         }
1172     }
1173
1174     /*
1175      * Now go through and draw the grid squares.
1176      */
1177     for (y = 0; y < h; y++) {
1178         for (x = 0; x < w; x++) {
1179             if (ds->todraw[y*w+x] != ds->grid[y*w+x]) {
1180                 draw_tile(fe, ds, state->clues, x, y, ds->todraw[y*w+x]);
1181                 ds->grid[y*w+x] = ds->todraw[y*w+x];
1182             }
1183         }
1184     }
1185 }
1186
1187 static float game_anim_length(game_state *oldstate, game_state *newstate,
1188                               int dir, game_ui *ui)
1189 {
1190     return 0.0F;
1191 }
1192
1193 static float game_flash_length(game_state *oldstate, game_state *newstate,
1194                                int dir, game_ui *ui)
1195 {
1196     if (!oldstate->completed && newstate->completed &&
1197         !oldstate->used_solve && !newstate->used_solve)
1198         return FLASH_TIME;
1199
1200     return 0.0F;
1201 }
1202
1203 static int game_wants_statusbar(void)
1204 {
1205     return FALSE;
1206 }
1207
1208 static int game_timing_state(game_state *state, game_ui *ui)
1209 {
1210     return TRUE;
1211 }
1212
1213 #ifdef COMBINED
1214 #define thegame slant
1215 #endif
1216
1217 const struct game thegame = {
1218     "Slant", "games.slant",
1219     default_params,
1220     game_fetch_preset,
1221     decode_params,
1222     encode_params,
1223     free_params,
1224     dup_params,
1225     TRUE, game_configure, custom_params,
1226     validate_params,
1227     new_game_desc,
1228     validate_desc,
1229     new_game,
1230     dup_game,
1231     free_game,
1232     TRUE, solve_game,
1233     TRUE, game_text_format,
1234     new_ui,
1235     free_ui,
1236     encode_ui,
1237     decode_ui,
1238     game_changed_state,
1239     interpret_move,
1240     execute_move,
1241     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1242     game_colours,
1243     game_new_drawstate,
1244     game_free_drawstate,
1245     game_redraw,
1246     game_anim_length,
1247     game_flash_length,
1248     game_wants_statusbar,
1249     FALSE, game_timing_state,
1250     0,                                 /* mouse_priorities */
1251 };