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