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