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