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