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 /*
  44  * In standalone solver mode, `verbose' is a variable which can be
  45  * set by command-line option; in debugging mode it's simply always
  46  * true.
  47  */
  48 #if defined STANDALONE_SOLVER
  49 #define SOLVER_DIAGNOSTICS
  50 int verbose = FALSE;
  51 #elif defined SOLVER_DIAGNOSTICS
  52 #define verbose TRUE
  53 #endif
  54
  55 /*
  56  * Difficulty levels. I do some macro ickery here to ensure that my
  57  * enum and the various forms of my name list always match up.
  58  */
  59 #define DIFFLIST(A) \
  60     A(EASY,Easy,e) \
  61     A(HARD,Hard,h)
  62 #define ENUM(upper,title,lower) DIFF_ ## upper,
  63 #define TITLE(upper,title,lower) #title,
  64 #define ENCODE(upper,title,lower) #lower
  65 #define CONFIG(upper,title,lower) ":" #title
  66 enum { DIFFLIST(ENUM) DIFFCOUNT };
  67 static char const *const slant_diffnames[] = { DIFFLIST(TITLE) };
  68 static char const slant_diffchars[] = DIFFLIST(ENCODE);
  69 #define DIFFCONFIG DIFFLIST(CONFIG)
  70
  71 struct game_params {
  72     int w, h, diff;
  73 };
  74
  75 typedef struct game_clues {
  76     int w, h;
  77     signed char *clues;
  78     int *dsf;                          /* scratch space for completion check */
  79     int refcount;
  80 } game_clues;
  81
  82 struct game_state {
  83     struct game_params p;
  84     game_clues *clues;
  85     signed char *soln;
  86     int completed;
  87     int used_solve;                    /* used to suppress completion flash */
  88 };
  89
  90 static game_params *default_params(void)
  91 {
  92     game_params *ret = snew(game_params);
  93
  94     ret->w = ret->h = 8;
  95     ret->diff = DIFF_EASY;
  96
  97     return ret;
  98 }
  99
 100 static const struct game_params slant_presets[] = {
 101     {5, 5, DIFF_EASY},
 102     {5, 5, DIFF_HARD},
 103     {8, 8, DIFF_EASY},
 104     {8, 8, DIFF_HARD},
 105     {12, 10, DIFF_EASY},
 106     {12, 10, DIFF_HARD},
 107 };
 108
 109 static int game_fetch_preset(int i, char **name, game_params **params)
 110 {
 111     game_params *ret;
 112     char str[80];
 113
 114     if (i < 0 || i >= lenof(slant_presets))
 115         return FALSE;
 116
 117     ret = snew(game_params);
 118     *ret = slant_presets[i];
 119
 120     sprintf(str, "%dx%d %s", ret->w, ret->h, slant_diffnames[ret->diff]);
 121
 122     *name = dupstr(str);
 123     *params = ret;
 124     return TRUE;
 125 }
 126
 127 static void free_params(game_params *params)
 128 {
 129     sfree(params);
 130 }
 131
 132 static game_params *dup_params(game_params *params)
 133 {
 134     game_params *ret = snew(game_params);
 135     *ret = *params;                    /* structure copy */
 136     return ret;
 137 }
 138
 139 static void decode_params(game_params *ret, char const *string)
 140 {
 141     ret->w = ret->h = atoi(string);
 142     while (*string && isdigit((unsigned char)*string)) string++;
 143     if (*string == 'x') {
 144         string++;
 145         ret->h = atoi(string);
 146         while (*string && isdigit((unsigned char)*string)) string++;
 147     }
 148     if (*string == 'd') {
 149         int i;
 150         string++;
 151         for (i = 0; i < DIFFCOUNT; i++)
 152             if (*string == slant_diffchars[i])
 153                 ret->diff = i;
 154         if (*string) string++;
 155     }
 156 }
 157
 158 static char *encode_params(game_params *params, int full)
 159 {
 160     char data[256];
 161
 162     sprintf(data, "%dx%d", params->w, params->h);
 163     if (full)
 164         sprintf(data + strlen(data), "d%c", slant_diffchars[params->diff]);
 165
 166     return dupstr(data);
 167 }
 168
 169 static config_item *game_configure(game_params *params)
 170 {
 171     config_item *ret;
 172     char buf[80];
 173
 174     ret = snewn(4, config_item);
 175
 176     ret[0].name = "Width";
 177     ret[0].type = C_STRING;
 178     sprintf(buf, "%d", params->w);
 179     ret[0].sval = dupstr(buf);
 180     ret[0].ival = 0;
 181
 182     ret[1].name = "Height";
 183     ret[1].type = C_STRING;
 184     sprintf(buf, "%d", params->h);
 185     ret[1].sval = dupstr(buf);
 186     ret[1].ival = 0;
 187
 188     ret[2].name = "Difficulty";
 189     ret[2].type = C_CHOICES;
 190     ret[2].sval = DIFFCONFIG;
 191     ret[2].ival = params->diff;
 192
 193     ret[3].name = NULL;
 194     ret[3].type = C_END;
 195     ret[3].sval = NULL;
 196     ret[3].ival = 0;
 197
 198     return ret;
 199 }
 200
 201 static game_params *custom_params(config_item *cfg)
 202 {
 203     game_params *ret = snew(game_params);
 204
 205     ret->w = atoi(cfg[0].sval);
 206     ret->h = atoi(cfg[1].sval);
 207     ret->diff = cfg[2].ival;
 208
 209     return ret;
 210 }
 211
 212 static char *validate_params(game_params *params, int full)
 213 {
 214     /*
 215      * (At least at the time of writing this comment) The grid
 216      * generator is actually capable of handling even zero grid
 217      * dimensions without crashing. Puzzles with a zero-area grid
 218      * are a bit boring, though, because they're already solved :-)
 219      * And puzzles with a dimension of 1 can't be made Hard, which
 220      * means the simplest thing is to forbid them altogether.
 221      */
 222
 223     if (params->w < 2 || params->h < 2)
 224         return "Width and height must both be at least two";
 225
 226     return NULL;
 227 }
 228
 229 /*
 230  * Scratch space for solver.
 231  */
 232 struct solver_scratch {
 233     /*
 234      * Disjoint set forest which tracks the connected sets of
 235      * points.
 236      */
 237     int *connected;
 238
 239     /*
 240      * Counts the number of possible exits from each connected set
 241      * of points. (That is, the number of possible _simultaneous_
 242      * exits: an unconnected point labelled 2 has an exit count of
 243      * 2 even if all four possible edges are still under
 244      * consideration.)
 245      */
 246     int *exits;
 247
 248     /*
 249      * Tracks whether each connected set of points includes a
 250      * border point.
 251      */
 252     unsigned char *border;
 253
 254     /*
 255      * Another disjoint set forest. This one tracks _squares_ which
 256      * are known to slant in the same direction.
 257      */
 258     int *equiv;
 259
 260     /*
 261      * Stores slash values which we know for an equivalence class.
 262      * When we fill in a square, we set slashval[canonify(x)] to
 263      * the same value as soln[x], so that we can then spot other
 264      * squares equivalent to it and fill them in immediately via
 265      * their known equivalence.
 266      */
 267     signed char *slashval;
 268
 269     /*
 270      * Useful to have this information automatically passed to
 271      * solver subroutines. (This pointer is not dynamically
 272      * allocated by new_scratch and free_scratch.)
 273      */
 274     const signed char *clues;
 275 };
 276
 277 static struct solver_scratch *new_scratch(int w, int h)
 278 {
 279     int W = w+1, H = h+1;
 280     struct solver_scratch *ret = snew(struct solver_scratch);
 281     ret->connected = snewn(W*H, int);
 282     ret->exits = snewn(W*H, int);
 283     ret->border = snewn(W*H, unsigned char);
 284     ret->equiv = snewn(w*h, int);
 285     ret->slashval = snewn(w*h, signed char);
 286     return ret;
 287 }
 288
 289 static void free_scratch(struct solver_scratch *sc)
 290 {
 291     sfree(sc->slashval);
 292     sfree(sc->equiv);
 293     sfree(sc->border);
 294     sfree(sc->exits);
 295     sfree(sc->connected);
 296     sfree(sc);
 297 }
 298
 299 /*
 300  * Wrapper on dsf_merge() which updates the `exits' and `border'
 301  * arrays.
 302  */
 303 static void merge_vertices(int *connected,
 304                            struct solver_scratch *sc, int i, int j)
 305 {
 306     int exits = -1, border = FALSE;    /* initialise to placate optimiser */
 307
 308     if (sc) {
 309         i = dsf_canonify(connected, i);
 310         j = dsf_canonify(connected, j);
 311
 312         /*
 313          * We have used one possible exit from each of the two
 314          * classes. Thus, the viable exit count of the new class is
 315          * the sum of the old exit counts minus two.
 316          */
 317         exits = sc->exits[i] + sc->exits[j] - 2;
 318
 319         border = sc->border[i] || sc->border[j];
 320     }
 321
 322     dsf_merge(connected, i, j);
 323
 324     if (sc) {
 325         i = dsf_canonify(connected, i);
 326         sc->exits[i] = exits;
 327         sc->border[i] = border;
 328     }
 329 }
 330
 331 /*
 332  * Called when we have just blocked one way out of a particular
 333  * point. If that point is a non-clue point (thus has a variable
 334  * number of exits), we have therefore decreased its potential exit
 335  * count, so we must decrement the exit count for the group as a
 336  * whole.
 337  */
 338 static void decr_exits(struct solver_scratch *sc, int i)
 339 {
 340     if (sc->clues[i] < 0) {
 341         i = dsf_canonify(sc->connected, i);
 342         sc->exits[i]--;
 343     }
 344 }
 345
 346 static void fill_square(int w, int h, int x, int y, int v,
 347                         signed char *soln,
 348                         int *connected, struct solver_scratch *sc)
 349 {
 350     int W = w+1 /*, H = h+1 */;
 351
 352     assert(x >= 0 && x < w && y >= 0 && y < h);
 353
 354     if (soln[y*w+x] != 0) {
 355         return;                        /* do nothing */
 356     }
 357
 358 #ifdef SOLVER_DIAGNOSTICS
 359     if (verbose)
 360         printf("  placing %c in %d,%d\n", v == -1 ? '\\' : '/', x, y);
 361 #endif
 362
 363     soln[y*w+x] = v;
 364
 365     if (sc) {
 366         int c = dsf_canonify(sc->equiv, y*w+x);
 367         sc->slashval[c] = v;
 368     }
 369
 370     if (v < 0) {
 371         merge_vertices(connected, sc, y*W+x, (y+1)*W+(x+1));
 372         if (sc) {
 373             decr_exits(sc, y*W+(x+1));
 374             decr_exits(sc, (y+1)*W+x);
 375         }
 376     } else {
 377         merge_vertices(connected, sc, y*W+(x+1), (y+1)*W+x);
 378         if (sc) {
 379             decr_exits(sc, y*W+x);
 380             decr_exits(sc, (y+1)*W+(x+1));
 381         }
 382     }
 383 }
 384
 385 /*
 386  * Solver. Returns 0 for impossibility, 1 for success, 2 for
 387  * ambiguity or failure to converge.
 388  */
 389 static int slant_solve(int w, int h, const signed char *clues,
 390                        signed char *soln, struct solver_scratch *sc,
 391                        int difficulty)
 392 {
 393     int W = w+1, H = h+1;
 394     int x, y, i, j;
 395     int done_something;
 396
 397     /*
 398      * Clear the output.
 399      */
 400     memset(soln, 0, w*h);
 401
 402     sc->clues = clues;
 403
 404     /*
 405      * Establish a disjoint set forest for tracking connectedness
 406      * between grid points.
 407      */
 408     for (i = 0; i < W*H; i++)
 409         sc->connected[i] = i;          /* initially all distinct */
 410
 411     /*
 412      * Establish a disjoint set forest for tracking which squares
 413      * are known to slant in the same direction.
 414      */
 415     for (i = 0; i < w*h; i++)
 416         sc->equiv[i] = i;              /* initially all distinct */
 417
 418     /*
 419      * Clear the slashval array.
 420      */
 421     memset(sc->slashval, 0, w*h);
 422
 423     /*
 424      * Initialise the `exits' and `border' arrays. Theses is used
 425      * to do second-order loop avoidance: the dual of the no loops
 426      * constraint is that every point must be somehow connected to
 427      * the border of the grid (otherwise there would be a solid
 428      * loop around it which prevented this).
 429      *
 430      * I define a `dead end' to be a connected group of points
 431      * which contains no border point, and which can form at most
 432      * one new connection outside itself. Then I forbid placing an
 433      * edge so that it connects together two dead-end groups, since
 434      * this would yield a non-border-connected isolated subgraph
 435      * with no further scope to extend it.
 436      */
 437     for (y = 0; y < H; y++)
 438         for (x = 0; x < W; x++) {
 439             if (y == 0 || y == H-1 || x == 0 || x == W-1)
 440                 sc->border[y*W+x] = TRUE;
 441             else
 442                 sc->border[y*W+x] = FALSE;
 443
 444             if (clues[y*W+x] < 0)
 445                 sc->exits[y*W+x] = 4;
 446             else
 447                 sc->exits[y*W+x] = clues[y*W+x];
 448         }
 449
 450     /*
 451      * Make a one-off preliminary pass over the grid looking for
 452      * starting-point arrangements. The ones we need to spot are:
 453      *
 454      *  - two adjacent 1s in the centre of the grid imply that each
 455      *    one's single line points towards the other. (If either 1
 456      *    were connected on the far side, the two squares shared
 457      *    between the 1s would both link to the other 1 as a
 458      *    consequence of neither linking to the first.) Thus, we
 459      *    can fill in the four squares around them.
 460      *
 461      *  - dually, two adjacent 3s imply that each one's _non_-line
 462      *    points towards the other.
 463      *
 464      *  - if the pair of 1s and 3s is not _adjacent_ but is
 465      *    separated by one or more 2s, the reasoning still applies.
 466      *
 467      * This is more advanced than just spotting obvious starting
 468      * squares such as central 4s and edge 2s, so we disable it on
 469      * DIFF_EASY.
 470      *
 471      * (I don't like this loop; it feels grubby to me. My
 472      * mathematical intuition feels there ought to be some more
 473      * general deductive form which contains this loop as a special
 474      * case, but I can't bring it to mind right now.)
 475      */
 476     if (difficulty > DIFF_EASY) {
 477         for (y = 1; y+1 < H; y++)
 478             for (x = 1; x+1 < W; x++) {
 479                 int v = clues[y*W+x], s, x2, y2, dx, dy;
 480                 if (v != 1 && v != 3)
 481                     continue;
 482                 /* Slash value of the square up and left of (x,y). */
 483                 s = (v == 1 ? +1 : -1);
 484
 485                 /* Look in each direction once. */
 486                 for (dy = 0; dy < 2; dy++) {
 487                     dx = 1 - dy;
 488                     x2 = x+dx;
 489                     y2 = y+dy;
 490                     if (x2+1 >= W || y2+1 >= H)
 491                         continue;              /* too close to the border */
 492                     while (x2+dx+1 < W && y2+dy+1 < H && clues[y2*W+x2] == 2)
 493                         x2 += dx, y2 += dy;
 494                     if (clues[y2*W+x2] == v) {
 495 #ifdef SOLVER_DIAGNOSTICS
 496                         if (verbose)
 497                             printf("found adjacent %ds at %d,%d and %d,%d\n",
 498                                    v, x, y, x2, y2);
 499 #endif
 500                         fill_square(w, h, x-1, y-1, s, soln,
 501                                     sc->connected, sc);
 502                         fill_square(w, h, x-1+dy, y-1+dx, -s, soln,
 503                                     sc->connected, sc);
 504                         fill_square(w, h, x2, y2, s, soln,
 505                                     sc->connected, sc);
 506                         fill_square(w, h, x2-dy, y2-dx, -s, soln,
 507                                     sc->connected, sc);
 508                     }
 509                 }
 510             }
 511     }
 512
 513     /*
 514      * Repeatedly try to deduce something until we can't.
 515      */
 516     do {
 517         done_something = FALSE;
 518
 519         /*
 520          * Any clue point with the number of remaining lines equal
 521          * to zero or to the number of remaining undecided
 522          * neighbouring squares can be filled in completely.
 523          */
 524         for (y = 0; y < H; y++)
 525             for (x = 0; x < W; x++) {
 526                 struct {
 527                     int pos, slash;
 528                 } neighbours[4];
 529                 int nneighbours;
 530                 int nu, nl, c, s, eq, eq2, last, meq, mj1, mj2;
 531
 532                 if ((c = clues[y*W+x]) < 0)
 533                     continue;
 534
 535                 /*
 536                  * We have a clue point. Start by listing its
 537                  * neighbouring squares, in order around the point,
 538                  * together with the type of slash that would be
 539                  * required in that square to connect to the point.
 540                  */
 541                 nneighbours = 0;
 542                 if (x > 0 && y > 0) {
 543                     neighbours[nneighbours].pos = (y-1)*w+(x-1);
 544                     neighbours[nneighbours].slash = -1;
 545                     nneighbours++;
 546                 }
 547                 if (x > 0 && y < h) {
 548                     neighbours[nneighbours].pos = y*w+(x-1);
 549                     neighbours[nneighbours].slash = +1;
 550                     nneighbours++;
 551                 }
 552                 if (x < w && y < h) {
 553                     neighbours[nneighbours].pos = y*w+x;
 554                     neighbours[nneighbours].slash = -1;
 555                     nneighbours++;
 556                 }
 557                 if (x < w && y > 0) {
 558                     neighbours[nneighbours].pos = (y-1)*w+x;
 559                     neighbours[nneighbours].slash = +1;
 560                     nneighbours++;
 561                 }
 562
 563                 /*
 564                  * Count up the number of undecided neighbours, and
 565                  * also the number of lines already present.
 566                  *
 567                  * If we're not on DIFF_EASY, then in this loop we
 568                  * also track whether we've seen two adjacent empty
 569                  * squares belonging to the same equivalence class
 570                  * (meaning they have the same type of slash). If
 571                  * so, we count them jointly as one line.
 572                  */
 573                 nu = 0;
 574                 nl = c;
 575                 last = neighbours[nneighbours-1].pos;
 576                 if (soln[last] == 0)
 577                     eq = dsf_canonify(sc->equiv, last);
 578                 else
 579                     eq = -1;
 580                 meq = mj1 = mj2 = -1;
 581                 for (i = 0; i < nneighbours; i++) {
 582                     j = neighbours[i].pos;
 583                     s = neighbours[i].slash;
 584                     if (soln[j] == 0) {
 585                         nu++;          /* undecided */
 586                         if (meq < 0 && difficulty > DIFF_EASY) {
 587                             eq2 = dsf_canonify(sc->equiv, j);
 588                             if (eq == eq2 && last != j) {
 589                                 /*
 590                                  * We've found an equivalent pair.
 591                                  * Mark it. This also inhibits any
 592                                  * further equivalence tracking
 593                                  * around this square, since we can
 594                                  * only handle one pair (and in
 595                                  * particular we want to avoid
 596                                  * being misled by two overlapping
 597                                  * equivalence pairs).
 598                                  */
 599                                 meq = eq;
 600                                 mj1 = last;
 601                                 mj2 = j;
 602                                 nl--;   /* count one line */
 603                                 nu -= 2;   /* and lose two undecideds */
 604                             } else
 605                                 eq = eq2;
 606                         }
 607                     } else {
 608                         eq = -1;
 609                         if (soln[j] == s)
 610                             nl--;      /* here's a line */
 611                     }
 612                     last = j;
 613                 }
 614
 615                 /*
 616                  * Check the counts.
 617                  */
 618                 if (nl < 0 || nl > nu) {
 619                     /*
 620                      * No consistent value for this at all!
 621                      */
 622 #ifdef SOLVER_DIAGNOSTICS
 623                     if (verbose)
 624                         printf("need %d / %d lines around clue point at %d,%d!\n",
 625                                nl, nu, x, y);
 626 #endif
 627                     return 0;          /* impossible */
 628                 }
 629
 630                 if (nu > 0 && (nl == 0 || nl == nu)) {
 631 #ifdef SOLVER_DIAGNOSTICS
 632                     if (verbose) {
 633                         if (meq >= 0)
 634                             printf("partially (since %d,%d == %d,%d) ",
 635                                    mj1%w, mj1/w, mj2%w, mj2/w);
 636                         printf("%s around clue point at %d,%d\n",
 637                                nl ? "filling" : "emptying", x, y);
 638                     }
 639 #endif
 640                     for (i = 0; i < nneighbours; i++) {
 641                         j = neighbours[i].pos;
 642                         s = neighbours[i].slash;
 643                         if (soln[j] == 0 && j != mj1 && j != mj2)
 644                             fill_square(w, h, j%w, j/w, (nl ? s : -s), soln,
 645                                         sc->connected, sc);
 646                     }
 647
 648                     done_something = TRUE;
 649                 } else if (nu == 2 && nl == 1 && difficulty > DIFF_EASY) {
 650                     /*
 651                      * If we have precisely two undecided squares
 652                      * and precisely one line to place between
 653                      * them, _and_ those squares are adjacent, then
 654                      * we can mark them as equivalent to one
 655                      * another.
 656                      *
 657                      * This even applies if meq >= 0: if we have a
 658                      * 2 clue point and two of its neighbours are
 659                      * already marked equivalent, we can indeed
 660                      * mark the other two as equivalent.
 661                      *
 662                      * We don't bother with this on DIFF_EASY,
 663                      * since we wouldn't have used the results
 664                      * anyway.
 665                      */
 666                     last = -1;
 667                     for (i = 0; i < nneighbours; i++) {
 668                         j = neighbours[i].pos;
 669                         if (soln[j] == 0 && j != mj1 && j != mj2) {
 670                             if (last < 0)
 671                                 last = i;
 672                             else if (last == i-1 || (last == 0 && i == 3))
 673                                 break; /* found a pair */
 674                         }
 675                     }
 676                     if (i < nneighbours) {
 677                         int sv1, sv2;
 678
 679                         assert(last >= 0);
 680                         /*
 681                          * neighbours[last] and neighbours[i] are
 682                          * the pair. Mark them equivalent.
 683                          */
 684 #ifdef SOLVER_DIAGNOSTICS
 685                         if (verbose) {
 686                             if (meq >= 0)
 687                                 printf("since %d,%d == %d,%d, ",
 688                                        mj1%w, mj1/w, mj2%w, mj2/w);
 689                         }
 690 #endif
 691                         mj1 = neighbours[last].pos;
 692                         mj2 = neighbours[i].pos;
 693 #ifdef SOLVER_DIAGNOSTICS
 694                         if (verbose)
 695                             printf("clue point at %d,%d implies %d,%d == %d,"
 696                                    "%d\n", x, y, mj1%w, mj1/w, mj2%w, mj2/w);
 697 #endif
 698                         mj1 = dsf_canonify(sc->equiv, mj1);
 699                         sv1 = sc->slashval[mj1];
 700                         mj2 = dsf_canonify(sc->equiv, mj2);
 701                         sv2 = sc->slashval[mj2];
 702                         if (sv1 != 0 && sv2 != 0 && sv1 != sv2) {
 703 #ifdef SOLVER_DIAGNOSTICS
 704                             if (verbose)
 705                                 printf("merged two equivalence classes with"
 706                                        " different slash values!\n");
 707 #endif
 708                             return 0;
 709                         }
 710                         sv1 = sv1 ? sv1 : sv2;
 711                         dsf_merge(sc->equiv, mj1, mj2);
 712                         mj1 = dsf_canonify(sc->equiv, mj1);
 713                         sc->slashval[mj1] = sv1;
 714                     }
 715                 }
 716             }
 717
 718         if (done_something)
 719             continue;
 720
 721         /*
 722          * Failing that, we now apply the second condition, which
 723          * is that no square may be filled in such a way as to form
 724          * a loop. Also in this loop (since it's over squares
 725          * rather than points), we check slashval to see if we've
 726          * already filled in another square in the same equivalence
 727          * class.
 728          *
 729          * The slashval check is disabled on DIFF_EASY, as is dead
 730          * end avoidance. Only _immediate_ loop avoidance remains.
 731          */
 732         for (y = 0; y < h; y++)
 733             for (x = 0; x < w; x++) {
 734                 int fs, bs, v;
 735                 int c1, c2;
 736 #ifdef SOLVER_DIAGNOSTICS
 737                 char *reason = "<internal error>";
 738 #endif
 739
 740                 if (soln[y*w+x])
 741                     continue;          /* got this one already */
 742
 743                 fs = FALSE;
 744                 bs = FALSE;
 745
 746                 if (difficulty > DIFF_EASY)
 747                     v = sc->slashval[dsf_canonify(sc->equiv, y*w+x)];
 748                 else
 749                     v = 0;
 750
 751                 /*
 752                  * Try to rule out connectivity between (x,y) and
 753                  * (x+1,y+1); if successful, we will deduce that we
 754                  * must have a forward slash.
 755                  */
 756                 c1 = dsf_canonify(sc->connected, y*W+x);
 757                 c2 = dsf_canonify(sc->connected, (y+1)*W+(x+1));
 758                 if (c1 == c2) {
 759                     fs = TRUE;
 760 #ifdef SOLVER_DIAGNOSTICS
 761                     reason = "simple loop avoidance";
 762 #endif
 763                 }
 764                 if (difficulty > DIFF_EASY &&
 765                     !sc->border[c1] && !sc->border[c2] &&
 766                     sc->exits[c1] <= 1 && sc->exits[c2] <= 1) {
 767                     fs = TRUE;
 768 #ifdef SOLVER_DIAGNOSTICS
 769                     reason = "dead end avoidance";
 770 #endif
 771                 }
 772                 if (v == +1) {
 773                     fs = TRUE;
 774 #ifdef SOLVER_DIAGNOSTICS
 775                     reason = "equivalence to an already filled square";
 776 #endif
 777                 }
 778
 779                 /*
 780                  * Now do the same between (x+1,y) and (x,y+1), to
 781                  * see if we are required to have a backslash.
 782                  */
 783                 c1 = dsf_canonify(sc->connected, y*W+(x+1));
 784                 c2 = dsf_canonify(sc->connected, (y+1)*W+x);
 785                 if (c1 == c2) {
 786                     bs = TRUE;
 787 #ifdef SOLVER_DIAGNOSTICS
 788                     reason = "simple loop avoidance";
 789 #endif
 790                 }
 791                 if (difficulty > DIFF_EASY &&
 792                     !sc->border[c1] && !sc->border[c2] &&
 793                     sc->exits[c1] <= 1 && sc->exits[c2] <= 1) {
 794                     bs = TRUE;
 795 #ifdef SOLVER_DIAGNOSTICS
 796                     reason = "dead end avoidance";
 797 #endif
 798                 }
 799                 if (v == -1) {
 800                     bs = TRUE;
 801 #ifdef SOLVER_DIAGNOSTICS
 802                     reason = "equivalence to an already filled square";
 803 #endif
 804                 }
 805
 806                 if (fs && bs) {
 807                     /*
 808                      * No consistent value for this at all!
 809                      */
 810 #ifdef SOLVER_DIAGNOSTICS
 811                     if (verbose)
 812                         printf("%d,%d has no consistent slash!\n", x, y);
 813 #endif
 814                     return 0;          /* impossible */
 815                 }
 816
 817                 if (fs) {
 818 #ifdef SOLVER_DIAGNOSTICS
 819                     if (verbose)
 820                         printf("employing %s\n", reason);
 821 #endif
 822                     fill_square(w, h, x, y, +1, soln, sc->connected, sc);
 823                     done_something = TRUE;
 824                 } else if (bs) {
 825 #ifdef SOLVER_DIAGNOSTICS
 826                     if (verbose)
 827                         printf("employing %s\n", reason);
 828 #endif
 829                     fill_square(w, h, x, y, -1, soln, sc->connected, sc);
 830                     done_something = TRUE;
 831                 }
 832             }
 833
 834     } while (done_something);
 835
 836     /*
 837      * Solver can make no more progress. See if the grid is full.
 838      */
 839     for (i = 0; i < w*h; i++)
 840         if (!soln[i])
 841             return 2;                  /* failed to converge */
 842     return 1;                          /* success */
 843 }
 844
 845 /*
 846  * Filled-grid generator.
 847  */
 848 static void slant_generate(int w, int h, signed char *soln, random_state *rs)
 849 {
 850     int W = w+1, H = h+1;
 851     int x, y, i;
 852     int *connected, *indices;
 853
 854     /*
 855      * Clear the output.
 856      */
 857     memset(soln, 0, w*h);
 858
 859     /*
 860      * Establish a disjoint set forest for tracking connectedness
 861      * between grid points.
 862      */
 863     connected = snewn(W*H, int);
 864     for (i = 0; i < W*H; i++)
 865         connected[i] = i;                      /* initially all distinct */
 866
 867     /*
 868      * Prepare a list of the squares in the grid, and fill them in
 869      * in a random order.
 870      */
 871     indices = snewn(w*h, int);
 872     for (i = 0; i < w*h; i++)
 873         indices[i] = i;
 874     shuffle(indices, w*h, sizeof(*indices), rs);
 875
 876     /*
 877      * Fill in each one in turn.
 878      */
 879     for (i = 0; i < w*h; i++) {
 880         int fs, bs, v;
 881
 882         y = indices[i] / w;
 883         x = indices[i] % w;
 884
 885         fs = (dsf_canonify(connected, y*W+x) ==
 886               dsf_canonify(connected, (y+1)*W+(x+1)));
 887         bs = (dsf_canonify(connected, (y+1)*W+x) ==
 888               dsf_canonify(connected, y*W+(x+1)));
 889
 890         /*
 891          * It isn't possible to get into a situation where we
 892          * aren't allowed to place _either_ type of slash in a
 893          * square. Thus, filled-grid generation never has to
 894          * backtrack.
 895          *
 896          * Proof (thanks to Gareth Taylor):
 897          *
 898          * If it were possible, it would have to be because there
 899          * was an existing path (not using this square) between the
 900          * top-left and bottom-right corners of this square, and
 901          * another between the other two. These two paths would
 902          * have to cross at some point.
 903          *
 904          * Obviously they can't cross in the middle of a square, so
 905          * they must cross by sharing a point in common. But this
 906          * isn't possible either: if you chessboard-colour all the
 907          * points on the grid, you find that any continuous
 908          * diagonal path is entirely composed of points of the same
 909          * colour. And one of our two hypothetical paths is between
 910          * two black points, and the other is between two white
 911          * points - therefore they can have no point in common. []
 912          */
 913         assert(!(fs && bs));
 914
 915         v = fs ? +1 : bs ? -1 : 2 * random_upto(rs, 2) - 1;
 916         fill_square(w, h, x, y, v, soln, connected, NULL);
 917     }
 918
 919     sfree(indices);
 920     sfree(connected);
 921 }
 922
 923 static char *new_game_desc(game_params *params, random_state *rs,
 924                            char **aux, int interactive)
 925 {
 926     int w = params->w, h = params->h, W = w+1, H = h+1;
 927     signed char *soln, *tmpsoln, *clues;
 928     int *clueindices;
 929     struct solver_scratch *sc;
 930     int x, y, v, i, j;
 931     char *desc;
 932
 933     soln = snewn(w*h, signed char);
 934     tmpsoln = snewn(w*h, signed char);
 935     clues = snewn(W*H, signed char);
 936     clueindices = snewn(W*H, int);
 937     sc = new_scratch(w, h);
 938
 939     do {
 940         /*
 941          * Create the filled grid.
 942          */
 943         slant_generate(w, h, soln, rs);
 944
 945         /*
 946          * Fill in the complete set of clues.
 947          */
 948         for (y = 0; y < H; y++)
 949             for (x = 0; x < W; x++) {
 950                 v = 0;
 951
 952                 if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] == -1) v++;
 953                 if (x > 0 && y < h && soln[y*w+(x-1)] == +1) v++;
 954                 if (x < w && y > 0 && soln[(y-1)*w+x] == +1) v++;
 955                 if (x < w && y < h && soln[y*w+x] == -1) v++;
 956
 957                 clues[y*W+x] = v;
 958             }
 959
 960         /*
 961          * With all clue points filled in, all puzzles are easy: we can
 962          * simply process the clue points in lexicographic order, and
 963          * at each clue point we will always have at most one square
 964          * undecided, which we can then fill in uniquely.
 965          */
 966         assert(slant_solve(w, h, clues, tmpsoln, sc, DIFF_EASY) == 1);
 967
 968         /*
 969          * Remove as many clues as possible while retaining solubility.
 970          *
 971          * In DIFF_HARD mode, we prioritise the removal of obvious
 972          * starting points (4s, 0s, border 2s and corner 1s), on
 973          * the grounds that having as few of these as possible
 974          * seems like a good thing. In particular, we can often get
 975          * away without _any_ completely obvious starting points,
 976          * which is even better.
 977          */
 978         for (i = 0; i < W*H; i++)
 979             clueindices[i] = i;
 980         shuffle(clueindices, W*H, sizeof(*clueindices), rs);
 981         for (j = 0; j < 2; j++) {
 982             for (i = 0; i < W*H; i++) {
 983                 int pass, yb, xb;
 984
 985                 y = clueindices[i] / W;
 986                 x = clueindices[i] % W;
 987                 v = clues[y*W+x];
 988
 989                 /*
 990                  * Identify which pass we should process this point
 991                  * in. If it's an obvious start point, _or_ we're
 992                  * in DIFF_EASY, then it goes in pass 0; otherwise
 993                  * pass 1.
 994                  */
 995                 xb = (x == 0 || x == W-1);
 996                 yb = (y == 0 || y == H-1);
 997                 if (params->diff == DIFF_EASY || v == 4 || v == 0 ||
 998                     (v == 2 && (xb||yb)) || (v == 1 && xb && yb))
 999                     pass = 0;
1000                 else
1001                     pass = 1;
1002
1003                 if (pass == j) {
1004                     clues[y*W+x] = -1;
1005                     if (slant_solve(w, h, clues, tmpsoln, sc,
1006                                     params->diff) != 1)
1007                         clues[y*W+x] = v;              /* put it back */
1008                 }
1009             }
1010         }
1011
1012         /*
1013          * And finally, verify that the grid is of _at least_ the
1014          * requested difficulty, by running the solver one level
1015          * down and verifying that it can't manage it.
1016          */
1017     } while (params->diff > 0 &&
1018              slant_solve(w, h, clues, tmpsoln, sc, params->diff - 1) <= 1);
1019
1020     /*
1021      * Now we have the clue set as it will be presented to the
1022      * user. Encode it in a game desc.
1023      */
1024     {
1025         char *p;
1026         int run, i;
1027
1028         desc = snewn(W*H+1, char);
1029         p = desc;
1030         run = 0;
1031         for (i = 0; i <= W*H; i++) {
1032             int n = (i < W*H ? clues[i] : -2);
1033
1034             if (n == -1)
1035                 run++;
1036             else {
1037                 if (run) {
1038                     while (run > 0) {
1039                         int c = 'a' - 1 + run;
1040                         if (run > 26)
1041                             c = 'z';
1042                         *p++ = c;
1043                         run -= c - ('a' - 1);
1044                     }
1045                 }
1046                 if (n >= 0)
1047                     *p++ = '0' + n;
1048                 run = 0;
1049             }
1050         }
1051         assert(p - desc <= W*H);
1052         *p++ = '\0';
1053         desc = sresize(desc, p - desc, char);
1054     }
1055
1056     /*
1057      * Encode the solution as an aux_info.
1058      */
1059     {
1060         char *auxbuf;
1061         *aux = auxbuf = snewn(w*h+1, char);
1062         for (i = 0; i < w*h; i++)
1063             auxbuf[i] = soln[i] < 0 ? '\\' : '/';
1064         auxbuf[w*h] = '\0';
1065     }
1066
1067     free_scratch(sc);
1068     sfree(clueindices);
1069     sfree(clues);
1070     sfree(tmpsoln);
1071     sfree(soln);
1072
1073     return desc;
1074 }
1075
1076 static char *validate_desc(game_params *params, char *desc)
1077 {
1078     int w = params->w, h = params->h, W = w+1, H = h+1;
1079     int area = W*H;
1080     int squares = 0;
1081
1082     while (*desc) {
1083         int n = *desc++;
1084         if (n >= 'a' && n <= 'z') {
1085             squares += n - 'a' + 1;
1086         } else if (n >= '0' && n <= '4') {
1087             squares++;
1088         } else
1089             return "Invalid character in game description";
1090     }
1091
1092     if (squares < area)
1093         return "Not enough data to fill grid";
1094
1095     if (squares > area)
1096         return "Too much data to fit in grid";
1097
1098     return NULL;
1099 }
1100
1101 static game_state *new_game(midend_data *me, game_params *params, char *desc)
1102 {
1103     int w = params->w, h = params->h, W = w+1, H = h+1;
1104     game_state *state = snew(game_state);
1105     int area = W*H;
1106     int squares = 0;
1107
1108     state->p = *params;
1109     state->soln = snewn(w*h, signed char);
1110     memset(state->soln, 0, w*h);
1111     state->completed = state->used_solve = FALSE;
1112
1113     state->clues = snew(game_clues);
1114     state->clues->w = w;
1115     state->clues->h = h;
1116     state->clues->clues = snewn(W*H, signed char);
1117     state->clues->refcount = 1;
1118     state->clues->dsf = snewn(W*H, int);
1119     memset(state->clues->clues, -1, W*H);
1120     while (*desc) {
1121         int n = *desc++;
1122         if (n >= 'a' && n <= 'z') {
1123             squares += n - 'a' + 1;
1124         } else if (n >= '0' && n <= '4') {
1125             state->clues->clues[squares++] = n - '0';
1126         } else
1127             assert(!"can't get here");
1128     }
1129     assert(squares == area);
1130
1131     return state;
1132 }
1133
1134 static game_state *dup_game(game_state *state)
1135 {
1136     int w = state->p.w, h = state->p.h;
1137     game_state *ret = snew(game_state);
1138
1139     ret->p = state->p;
1140     ret->clues = state->clues;
1141     ret->clues->refcount++;
1142     ret->completed = state->completed;
1143     ret->used_solve = state->used_solve;
1144
1145     ret->soln = snewn(w*h, signed char);
1146     memcpy(ret->soln, state->soln, w*h);
1147
1148     return ret;
1149 }
1150
1151 static void free_game(game_state *state)
1152 {
1153     sfree(state->soln);
1154     assert(state->clues);
1155     if (--state->clues->refcount <= 0) {
1156         sfree(state->clues->clues);
1157         sfree(state->clues->dsf);
1158         sfree(state->clues);
1159     }
1160     sfree(state);
1161 }
1162
1163 static int check_completion(game_state *state)
1164 {
1165     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1166     int i, x, y;
1167
1168     /*
1169      * Establish a disjoint set forest for tracking connectedness
1170      * between grid points. Use the dsf scratch space in the shared
1171      * clues structure, to avoid mallocing too often.
1172      */
1173     for (i = 0; i < W*H; i++)
1174         state->clues->dsf[i] = i;      /* initially all distinct */
1175
1176     /*
1177      * Now go through the grid checking connectedness. While we're
1178      * here, also check that everything is filled in.
1179      */
1180     for (y = 0; y < h; y++)
1181         for (x = 0; x < w; x++) {
1182             int i1, i2;
1183
1184             if (state->soln[y*w+x] == 0)
1185                 return FALSE;
1186             if (state->soln[y*w+x] < 0) {
1187                 i1 = y*W+x;
1188                 i2 = (y+1)*W+(x+1);
1189             } else {
1190                 i1 = (y+1)*W+x;
1191                 i2 = y*W+(x+1);
1192             }
1193
1194             /*
1195              * Our edge connects i1 with i2. If they're already
1196              * connected, return failure. Otherwise, link them.
1197              */
1198             if (dsf_canonify(state->clues->dsf, i1) ==
1199                 dsf_canonify(state->clues->dsf, i2))
1200                 return FALSE;
1201             else
1202                 dsf_merge(state->clues->dsf, i1, i2);
1203         }
1204
1205     /*
1206      * The grid is _a_ valid grid; let's see if it matches the
1207      * clues.
1208      */
1209     for (y = 0; y < H; y++)
1210         for (x = 0; x < W; x++) {
1211             int v, c;
1212
1213             if ((c = state->clues->clues[y*W+x]) < 0)
1214                 continue;
1215
1216             v = 0;
1217
1218             if (x > 0 && y > 0 && state->soln[(y-1)*w+(x-1)] == -1) v++;
1219             if (x > 0 && y < h && state->soln[y*w+(x-1)] == +1) v++;
1220             if (x < w && y > 0 && state->soln[(y-1)*w+x] == +1) v++;
1221             if (x < w && y < h && state->soln[y*w+x] == -1) v++;
1222
1223             if (c != v)
1224                 return FALSE;
1225         }
1226
1227     return TRUE;
1228 }
1229
1230 static char *solve_game(game_state *state, game_state *currstate,
1231                         char *aux, char **error)
1232 {
1233     int w = state->p.w, h = state->p.h;
1234     signed char *soln;
1235     int bs, ret;
1236     int free_soln = FALSE;
1237     char *move, buf[80];
1238     int movelen, movesize;
1239     int x, y;
1240
1241     if (aux) {
1242         /*
1243          * If we already have the solution, save ourselves some
1244          * time.
1245          */
1246         soln = (signed char *)aux;
1247         bs = (signed char)'\\';
1248         free_soln = FALSE;
1249     } else {
1250         struct solver_scratch *sc = new_scratch(w, h);
1251         soln = snewn(w*h, signed char);
1252         bs = -1;
1253         ret = slant_solve(w, h, state->clues->clues, soln, sc, DIFF_HARD);
1254         free_scratch(sc);
1255         if (ret != 1) {
1256             sfree(soln);
1257             if (ret == 0)
1258                 *error = "This puzzle is not self-consistent";
1259             else
1260                 *error = "Unable to find a unique solution for this puzzle";
1261             return NULL;
1262         }
1263         free_soln = TRUE;
1264     }
1265
1266     /*
1267      * Construct a move string which turns the current state into
1268      * the solved state.
1269      */
1270     movesize = 256;
1271     move = snewn(movesize, char);
1272     movelen = 0;
1273     move[movelen++] = 'S';
1274     move[movelen] = '\0';
1275     for (y = 0; y < h; y++)
1276         for (x = 0; x < w; x++) {
1277             int v = (soln[y*w+x] == bs ? -1 : +1);
1278             if (state->soln[y*w+x] != v) {
1279                 int len = sprintf(buf, ";%c%d,%d", (int)(v < 0 ? '\\' : '/'), x, y);
1280                 if (movelen + len >= movesize) {
1281                     movesize = movelen + len + 256;
1282                     move = sresize(move, movesize, char);
1283                 }
1284                 strcpy(move + movelen, buf);
1285                 movelen += len;
1286             }
1287         }
1288
1289     if (free_soln)
1290         sfree(soln);
1291
1292     return move;
1293 }
1294
1295 static char *game_text_format(game_state *state)
1296 {
1297     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1298     int x, y, len;
1299     char *ret, *p;
1300
1301     /*
1302      * There are h+H rows of w+W columns.
1303      */
1304     len = (h+H) * (w+W+1) + 1;
1305     ret = snewn(len, char);
1306     p = ret;
1307
1308     for (y = 0; y < H; y++) {
1309         for (x = 0; x < W; x++) {
1310             if (state->clues->clues[y*W+x] >= 0)
1311                 *p++ = state->clues->clues[y*W+x] + '0';
1312             else
1313                 *p++ = '+';
1314             if (x < w)
1315                 *p++ = '-';
1316         }
1317         *p++ = '\n';
1318         if (y < h) {
1319             for (x = 0; x < W; x++) {
1320                 *p++ = '|';
1321                 if (x < w) {
1322                     if (state->soln[y*w+x] != 0)
1323                         *p++ = (state->soln[y*w+x] < 0 ? '\\' : '/');
1324                     else
1325                         *p++ = ' ';
1326                 }
1327             }
1328             *p++ = '\n';
1329         }
1330     }
1331     *p++ = '\0';
1332
1333     assert(p - ret == len);
1334     return ret;
1335 }
1336
1337 static game_ui *new_ui(game_state *state)
1338 {
1339     return NULL;
1340 }
1341
1342 static void free_ui(game_ui *ui)
1343 {
1344 }
1345
1346 static char *encode_ui(game_ui *ui)
1347 {
1348     return NULL;
1349 }
1350
1351 static void decode_ui(game_ui *ui, char *encoding)
1352 {
1353 }
1354
1355 static void game_changed_state(game_ui *ui, game_state *oldstate,
1356                                game_state *newstate)
1357 {
1358 }
1359
1360 #define PREFERRED_TILESIZE 32
1361 #define TILESIZE (ds->tilesize)
1362 #define BORDER TILESIZE
1363 #define CLUE_RADIUS (TILESIZE / 3)
1364 #define CLUE_TEXTSIZE (TILESIZE / 2)
1365 #define COORD(x)  ( (x) * TILESIZE + BORDER )
1366 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1367
1368 #define FLASH_TIME 0.30F
1369
1370 /*
1371  * Bit fields in the `grid' and `todraw' elements of the drawstate.
1372  */
1373 #define BACKSLASH 0x0001
1374 #define FORWSLASH 0x0002
1375 #define L_T       0x0004
1376 #define L_B       0x0008
1377 #define T_L       0x0010
1378 #define T_R       0x0020
1379 #define R_T       0x0040
1380 #define R_B       0x0080
1381 #define B_L       0x0100
1382 #define B_R       0x0200
1383 #define C_TL      0x0400
1384 #define C_TR      0x0800
1385 #define C_BL      0x1000
1386 #define C_BR      0x2000
1387 #define FLASH     0x4000
1388
1389 struct game_drawstate {
1390     int tilesize;
1391     int started;
1392     int *grid;
1393     int *todraw;
1394 };
1395
1396 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1397                             int x, int y, int button)
1398 {
1399     int w = state->p.w, h = state->p.h;
1400
1401     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1402         int v;
1403         char buf[80];
1404
1405         /*
1406          * This is an utterly awful hack which I should really sort out
1407          * by means of a proper configuration mechanism. One Slant
1408          * player has observed that they prefer the mouse buttons to
1409          * function exactly the opposite way round, so here's a
1410          * mechanism for environment-based configuration. I cache the
1411          * result in a global variable - yuck! - to avoid repeated
1412          * lookups.
1413          */
1414         {
1415             static int swap_buttons = -1;
1416             if (swap_buttons < 0) {
1417                 char *env = getenv("SLANT_SWAP_BUTTONS");
1418                 swap_buttons = (env && (env[0] == 'y' || env[0] == 'Y'));
1419             }
1420             if (swap_buttons) {
1421                 if (button == LEFT_BUTTON)
1422                     button = RIGHT_BUTTON;
1423                 else
1424                     button = LEFT_BUTTON;
1425             }
1426         }
1427
1428         x = FROMCOORD(x);
1429         y = FROMCOORD(y);
1430         if (x < 0 || y < 0 || x >= w || y >= h)
1431             return NULL;
1432
1433         if (button == LEFT_BUTTON) {
1434             /*
1435              * Left-clicking cycles blank -> \ -> / -> blank.
1436              */
1437             v = state->soln[y*w+x] - 1;
1438             if (v == -2)
1439                 v = +1;
1440         } else {
1441             /*
1442              * Right-clicking cycles blank -> / -> \ -> blank.
1443              */
1444             v = state->soln[y*w+x] + 1;
1445             if (v == +2)
1446                 v = -1;
1447         }
1448
1449         sprintf(buf, "%c%d,%d", (int)(v==-1 ? '\\' : v==+1 ? '/' : 'C'), x, y);
1450         return dupstr(buf);
1451     }
1452
1453     return NULL;
1454 }
1455
1456 static game_state *execute_move(game_state *state, char *move)
1457 {
1458     int w = state->p.w, h = state->p.h;
1459     char c;
1460     int x, y, n;
1461     game_state *ret = dup_game(state);
1462
1463     while (*move) {
1464         c = *move;
1465         if (c == 'S') {
1466             ret->used_solve = TRUE;
1467             move++;
1468         } else if (c == '\\' || c == '/' || c == 'C') {
1469             move++;
1470             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1471                 x < 0 || y < 0 || x >= w || y >= h) {
1472                 free_game(ret);
1473                 return NULL;
1474             }
1475             ret->soln[y*w+x] = (c == '\\' ? -1 : c == '/' ? +1 : 0);
1476             move += n;
1477         } else {
1478             free_game(ret);
1479             return NULL;
1480         }
1481         if (*move == ';')
1482             move++;
1483         else if (*move) {
1484             free_game(ret);
1485             return NULL;
1486         }
1487     }
1488
1489     if (!ret->completed)
1490         ret->completed = check_completion(ret);
1491
1492     return ret;
1493 }
1494
1495 /* ----------------------------------------------------------------------
1496  * Drawing routines.
1497  */
1498
1499 static void game_compute_size(game_params *params, int tilesize,
1500                               int *x, int *y)
1501 {
1502     /* fool the macros */
1503     struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy;
1504
1505     *x = 2 * BORDER + params->w * TILESIZE + 1;
1506     *y = 2 * BORDER + params->h * TILESIZE + 1;
1507 }
1508
1509 static void game_set_size(game_drawstate *ds, game_params *params,
1510                           int tilesize)
1511 {
1512     ds->tilesize = tilesize;
1513 }
1514
1515 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1516 {
1517     float *ret = snewn(3 * NCOLOURS, float);
1518
1519     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1520
1521     ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.7F;
1522     ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.7F;
1523     ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.7F;
1524
1525     ret[COL_INK * 3 + 0] = 0.0F;
1526     ret[COL_INK * 3 + 1] = 0.0F;
1527     ret[COL_INK * 3 + 2] = 0.0F;
1528
1529     ret[COL_SLANT1 * 3 + 0] = 0.0F;
1530     ret[COL_SLANT1 * 3 + 1] = 0.0F;
1531     ret[COL_SLANT1 * 3 + 2] = 0.0F;
1532
1533     ret[COL_SLANT2 * 3 + 0] = 0.0F;
1534     ret[COL_SLANT2 * 3 + 1] = 0.0F;
1535     ret[COL_SLANT2 * 3 + 2] = 0.0F;
1536
1537     *ncolours = NCOLOURS;
1538     return ret;
1539 }
1540
1541 static game_drawstate *game_new_drawstate(game_state *state)
1542 {
1543     int w = state->p.w, h = state->p.h;
1544     int i;
1545     struct game_drawstate *ds = snew(struct game_drawstate);
1546
1547     ds->tilesize = 0;
1548     ds->started = FALSE;
1549     ds->grid = snewn(w*h, int);
1550     ds->todraw = snewn(w*h, int);
1551     for (i = 0; i < w*h; i++)
1552         ds->grid[i] = ds->todraw[i] = -1;
1553
1554     return ds;
1555 }
1556
1557 static void game_free_drawstate(game_drawstate *ds)
1558 {
1559     sfree(ds->todraw);
1560     sfree(ds->grid);
1561     sfree(ds);
1562 }
1563
1564 static void draw_clue(frontend *fe, game_drawstate *ds,
1565                       int x, int y, int v)
1566 {
1567     char p[2];
1568     int col = ((x ^ y) & 1) ? COL_SLANT1 : COL_SLANT2;
1569
1570     if (v < 0)
1571         return;
1572
1573     p[0] = v + '0';
1574     p[1] = '\0';
1575     draw_circle(fe, COORD(x), COORD(y), CLUE_RADIUS, COL_BACKGROUND, col);
1576     draw_text(fe, COORD(x), COORD(y), FONT_VARIABLE,
1577               CLUE_TEXTSIZE, ALIGN_VCENTRE|ALIGN_HCENTRE,
1578               COL_INK, p);
1579 }
1580
1581 static void draw_tile(frontend *fe, game_drawstate *ds, game_clues *clues,
1582                       int x, int y, int v)
1583 {
1584     int w = clues->w /*, h = clues->h*/, W = w+1 /*, H = h+1 */;
1585     int xx, yy;
1586     int chesscolour = (x ^ y) & 1;
1587     int fscol = chesscolour ? COL_SLANT2 : COL_SLANT1;
1588     int bscol = chesscolour ? COL_SLANT1 : COL_SLANT2;
1589
1590     clip(fe, COORD(x), COORD(y), TILESIZE+1, TILESIZE+1);
1591
1592     draw_rect(fe, COORD(x), COORD(y), TILESIZE, TILESIZE,
1593               (v & FLASH) ? COL_GRID : COL_BACKGROUND);
1594
1595     /*
1596      * Draw the grid lines.
1597      */
1598     draw_line(fe, COORD(x), COORD(y), COORD(x+1), COORD(y), COL_GRID);
1599     draw_line(fe, COORD(x), COORD(y+1), COORD(x+1), COORD(y+1), COL_GRID);
1600     draw_line(fe, COORD(x), COORD(y), COORD(x), COORD(y+1), COL_GRID);
1601     draw_line(fe, COORD(x+1), COORD(y), COORD(x+1), COORD(y+1), COL_GRID);
1602
1603     /*
1604      * Draw the slash.
1605      */
1606     if (v & BACKSLASH) {
1607         draw_line(fe, COORD(x), COORD(y), COORD(x+1), COORD(y+1), bscol);
1608         draw_line(fe, COORD(x)+1, COORD(y), COORD(x+1), COORD(y+1)-1,
1609                   bscol);
1610         draw_line(fe, COORD(x), COORD(y)+1, COORD(x+1)-1, COORD(y+1),
1611                   bscol);
1612     } else if (v & FORWSLASH) {
1613         draw_line(fe, COORD(x+1), COORD(y), COORD(x), COORD(y+1), fscol);
1614         draw_line(fe, COORD(x+1)-1, COORD(y), COORD(x), COORD(y+1)-1,
1615                   fscol);
1616         draw_line(fe, COORD(x+1), COORD(y)+1, COORD(x)+1, COORD(y+1),
1617                   fscol);
1618     }
1619
1620     /*
1621      * Draw dots on the grid corners that appear if a slash is in a
1622      * neighbouring cell.
1623      */
1624     if (v & L_T)
1625         draw_rect(fe, COORD(x), COORD(y)+1, 1, 1, bscol);
1626     if (v & L_B)
1627         draw_rect(fe, COORD(x), COORD(y+1)-1, 1, 1, fscol);
1628     if (v & R_T)
1629         draw_rect(fe, COORD(x+1), COORD(y)+1, 1, 1, fscol);
1630     if (v & R_B)
1631         draw_rect(fe, COORD(x+1), COORD(y+1)-1, 1, 1, bscol);
1632     if (v & T_L)
1633         draw_rect(fe, COORD(x)+1, COORD(y), 1, 1, bscol);
1634     if (v & T_R)
1635         draw_rect(fe, COORD(x+1)-1, COORD(y), 1, 1, fscol);
1636     if (v & B_L)
1637         draw_rect(fe, COORD(x)+1, COORD(y+1), 1, 1, fscol);
1638     if (v & B_R)
1639         draw_rect(fe, COORD(x+1)-1, COORD(y+1), 1, 1, bscol);
1640     if (v & C_TL)
1641         draw_rect(fe, COORD(x), COORD(y), 1, 1, bscol);
1642     if (v & C_TR)
1643         draw_rect(fe, COORD(x+1), COORD(y), 1, 1, fscol);
1644     if (v & C_BL)
1645         draw_rect(fe, COORD(x), COORD(y+1), 1, 1, fscol);
1646     if (v & C_BR)
1647         draw_rect(fe, COORD(x+1), COORD(y+1), 1, 1, bscol);
1648
1649     /*
1650      * And finally the clues at the corners.
1651      */
1652     for (xx = x; xx <= x+1; xx++)
1653         for (yy = y; yy <= y+1; yy++)
1654             draw_clue(fe, ds, xx, yy, clues->clues[yy*W+xx]);
1655
1656     unclip(fe);
1657     draw_update(fe, COORD(x), COORD(y), TILESIZE+1, TILESIZE+1);
1658 }
1659
1660 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1661                         game_state *state, int dir, game_ui *ui,
1662                         float animtime, float flashtime)
1663 {
1664     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1665     int x, y;
1666     int flashing;
1667
1668     if (flashtime > 0)
1669         flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
1670     else
1671         flashing = FALSE;
1672
1673     if (!ds->started) {
1674         int ww, wh;
1675         game_compute_size(&state->p, TILESIZE, &ww, &wh);
1676         draw_rect(fe, 0, 0, ww, wh, COL_BACKGROUND);
1677         draw_update(fe, 0, 0, ww, wh);
1678
1679         /*
1680          * Draw any clues on the very edges (since normal tile
1681          * redraw won't draw the bits outside the grid boundary).
1682          */
1683         for (y = 0; y < H; y++) {
1684             draw_clue(fe, ds, 0, y, state->clues->clues[y*W+0]);
1685             draw_clue(fe, ds, w, y, state->clues->clues[y*W+w]);
1686         }
1687         for (x = 0; x < W; x++) {
1688             draw_clue(fe, ds, x, 0, state->clues->clues[0*W+x]);
1689             draw_clue(fe, ds, x, h, state->clues->clues[h*W+x]);
1690         }
1691
1692         ds->started = TRUE;
1693     }
1694
1695     /*
1696      * Loop over the grid and work out where all the slashes are.
1697      * We need to do this because a slash in one square affects the
1698      * drawing of the next one along.
1699      */
1700     for (y = 0; y < h; y++)
1701         for (x = 0; x < w; x++)
1702             ds->todraw[y*w+x] = flashing ? FLASH : 0;
1703
1704     for (y = 0; y < h; y++) {
1705         for (x = 0; x < w; x++) {
1706             if (state->soln[y*w+x] < 0) {
1707                 ds->todraw[y*w+x] |= BACKSLASH;
1708                 if (x > 0)
1709                     ds->todraw[y*w+(x-1)] |= R_T | C_TR;
1710                 if (x+1 < w)
1711                     ds->todraw[y*w+(x+1)] |= L_B | C_BL;
1712                 if (y > 0)
1713                     ds->todraw[(y-1)*w+x] |= B_L | C_BL;
1714                 if (y+1 < h)
1715                     ds->todraw[(y+1)*w+x] |= T_R | C_TR;
1716                 if (x > 0 && y > 0)
1717                     ds->todraw[(y-1)*w+(x-1)] |= C_BR;
1718                 if (x+1 < w && y+1 < h)
1719                     ds->todraw[(y+1)*w+(x+1)] |= C_TL;
1720             } else if (state->soln[y*w+x] > 0) {
1721                 ds->todraw[y*w+x] |= FORWSLASH;
1722                 if (x > 0)
1723                     ds->todraw[y*w+(x-1)] |= R_B | C_BR;
1724                 if (x+1 < w)
1725                     ds->todraw[y*w+(x+1)] |= L_T | C_TL;
1726                 if (y > 0)
1727                     ds->todraw[(y-1)*w+x] |= B_R | C_BR;
1728                 if (y+1 < h)
1729                     ds->todraw[(y+1)*w+x] |= T_L | C_TL;
1730                 if (x > 0 && y+1 < h)
1731                     ds->todraw[(y+1)*w+(x-1)] |= C_TR;
1732                 if (x+1 < w && y > 0)
1733                     ds->todraw[(y-1)*w+(x+1)] |= C_BL;
1734             }
1735         }
1736     }
1737
1738     /*
1739      * Now go through and draw the grid squares.
1740      */
1741     for (y = 0; y < h; y++) {
1742         for (x = 0; x < w; x++) {
1743             if (ds->todraw[y*w+x] != ds->grid[y*w+x]) {
1744                 draw_tile(fe, ds, state->clues, x, y, ds->todraw[y*w+x]);
1745                 ds->grid[y*w+x] = ds->todraw[y*w+x];
1746             }
1747         }
1748     }
1749 }
1750
1751 static float game_anim_length(game_state *oldstate, game_state *newstate,
1752                               int dir, game_ui *ui)
1753 {
1754     return 0.0F;
1755 }
1756
1757 static float game_flash_length(game_state *oldstate, game_state *newstate,
1758                                int dir, game_ui *ui)
1759 {
1760     if (!oldstate->completed && newstate->completed &&
1761         !oldstate->used_solve && !newstate->used_solve)
1762         return FLASH_TIME;
1763
1764     return 0.0F;
1765 }
1766
1767 static int game_wants_statusbar(void)
1768 {
1769     return FALSE;
1770 }
1771
1772 static int game_timing_state(game_state *state, game_ui *ui)
1773 {
1774     return TRUE;
1775 }
1776
1777 #ifdef COMBINED
1778 #define thegame slant
1779 #endif
1780
1781 const struct game thegame = {
1782     "Slant", "games.slant",
1783     default_params,
1784     game_fetch_preset,
1785     decode_params,
1786     encode_params,
1787     free_params,
1788     dup_params,
1789     TRUE, game_configure, custom_params,
1790     validate_params,
1791     new_game_desc,
1792     validate_desc,
1793     new_game,
1794     dup_game,
1795     free_game,
1796     TRUE, solve_game,
1797     TRUE, game_text_format,
1798     new_ui,
1799     free_ui,
1800     encode_ui,
1801     decode_ui,
1802     game_changed_state,
1803     interpret_move,
1804     execute_move,
1805     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1806     game_colours,
1807     game_new_drawstate,
1808     game_free_drawstate,
1809     game_redraw,
1810     game_anim_length,
1811     game_flash_length,
1812     game_wants_statusbar,
1813     FALSE, game_timing_state,
1814     0,                                 /* mouse_priorities */
1815 };
1816
1817 #ifdef STANDALONE_SOLVER
1818
1819 #include <stdarg.h>
1820
1821 /*
1822  * gcc -DSTANDALONE_SOLVER -o slantsolver slant.c malloc.c
1823  */
1824
1825 void frontend_default_colour(frontend *fe, float *output) {}
1826 void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize,
1827                int align, int colour, char *text) {}
1828 void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {}
1829 void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {}
1830 void draw_polygon(frontend *fe, int *coords, int npoints,
1831                   int fillcolour, int outlinecolour) {}
1832 void draw_circle(frontend *fe, int cx, int cy, int radius,
1833                  int fillcolour, int outlinecolour) {}
1834 void clip(frontend *fe, int x, int y, int w, int h) {}
1835 void unclip(frontend *fe) {}
1836 void start_draw(frontend *fe) {}
1837 void draw_update(frontend *fe, int x, int y, int w, int h) {}
1838 void end_draw(frontend *fe) {}
1839 unsigned long random_bits(random_state *state, int bits)
1840 { assert(!"Shouldn't get randomness"); return 0; }
1841 unsigned long random_upto(random_state *state, unsigned long limit)
1842 { assert(!"Shouldn't get randomness"); return 0; }
1843 void shuffle(void *array, int nelts, int eltsize, random_state *rs)
1844 { assert(!"Shouldn't get randomness"); }
1845
1846 void fatal(char *fmt, ...)
1847 {
1848     va_list ap;
1849
1850     fprintf(stderr, "fatal error: ");
1851
1852     va_start(ap, fmt);
1853     vfprintf(stderr, fmt, ap);
1854     va_end(ap);
1855
1856     fprintf(stderr, "\n");
1857     exit(1);
1858 }
1859
1860 int main(int argc, char **argv)
1861 {
1862     game_params *p;
1863     game_state *s;
1864     char *id = NULL, *desc, *err;
1865     int grade = FALSE;
1866     int ret, diff, really_verbose = FALSE;
1867     struct solver_scratch *sc;
1868
1869     while (--argc > 0) {
1870         char *p = *++argv;
1871         if (!strcmp(p, "-v")) {
1872             really_verbose = TRUE;
1873         } else if (!strcmp(p, "-g")) {
1874             grade = TRUE;
1875         } else if (*p == '-') {
1876             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
1877             return 1;
1878         } else {
1879             id = p;
1880         }
1881     }
1882
1883     if (!id) {
1884         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
1885         return 1;
1886     }
1887
1888     desc = strchr(id, ':');
1889     if (!desc) {
1890         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
1891         return 1;
1892     }
1893     *desc++ = '\0';
1894
1895     p = default_params();
1896     decode_params(p, id);
1897     err = validate_desc(p, desc);
1898     if (err) {
1899         fprintf(stderr, "%s: %s\n", argv[0], err);
1900         return 1;
1901     }
1902     s = new_game(NULL, p, desc);
1903
1904     sc = new_scratch(p->w, p->h);
1905
1906     /*
1907      * When solving an Easy puzzle, we don't want to bother the
1908      * user with Hard-level deductions. For this reason, we grade
1909      * the puzzle internally before doing anything else.
1910      */
1911     for (diff = 0; diff < DIFFCOUNT; diff++) {
1912         ret = slant_solve(p->w, p->h, s->clues->clues,
1913                           s->soln, sc, diff);
1914         if (ret < 2)
1915             break;
1916     }
1917
1918     if (diff == DIFFCOUNT) {
1919         if (grade)
1920             printf("Difficulty rating: harder than Hard, or ambiguous\n");
1921         else
1922             printf("Unable to find a unique solution\n");
1923     } else {
1924         if (grade) {
1925             if (ret == 0)
1926                 printf("Difficulty rating: impossible (no solution exists)\n");
1927             else if (ret == 1)
1928                 printf("Difficulty rating: %s\n", slant_diffnames[diff]);
1929         } else {
1930             verbose = really_verbose;
1931             ret = slant_solve(p->w, p->h, s->clues->clues,
1932                               s->soln, sc, diff);
1933             if (ret == 0)
1934                 printf("Puzzle is inconsistent\n");
1935             else
1936                 fputs(game_text_format(s), stdout);
1937         }
1938     }
1939
1940     return 0;
1941 }
1942
1943 #endif