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