slant.c

   1 /*
   2  * slant.c: Puzzle from nikoli.co.jp involving drawing a diagonal
   3  * line through each square of a grid.
   4  */
   5
   6 /*
   7  * In this puzzle you have a grid of squares, each of which must
   8  * contain a diagonal line; you also have clue numbers placed at
   9  * _points_ of that grid, which means there's a (w+1) x (h+1) array
  10  * of possible clue positions.
  11  *
  12  * I'm therefore going to adopt a rigid convention throughout this
  13  * source file of using w and h for the dimensions of the grid of
  14  * squares, and W and H for the dimensions of the grid of points.
  15  * Thus, W == w+1 and H == h+1 always.
  16  *
  17  * Clue arrays will be W*H `signed char's, and the clue at each
  18  * point will be a number from 0 to 4, or -1 if there's no clue.
  19  *
  20  * Solution arrays will be W*H `signed char's, and the number at
  21  * each point will be +1 for a forward slash (/), -1 for a
  22  * backslash (\), and 0 for unknown.
  23  */
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <assert.h>
  29 #include <ctype.h>
  30 #include <math.h>
  31
  32 #include "puzzles.h"
  33
  34 enum {
  35     COL_BACKGROUND,
  36     COL_GRID,
  37     COL_INK,
  38     COL_SLANT1,
  39     COL_SLANT2,
  40     COL_ERROR,
  41     NCOLOURS
  42 };
  43
  44 /*
  45  * In standalone solver mode, `verbose' is a variable which can be
  46  * set by command-line option; in debugging mode it's simply always
  47  * true.
  48  */
  49 #if defined STANDALONE_SOLVER
  50 #define SOLVER_DIAGNOSTICS
  51 int verbose = FALSE;
  52 #elif defined SOLVER_DIAGNOSTICS
  53 #define verbose TRUE
  54 #endif
  55
  56 /*
  57  * Difficulty levels. I do some macro ickery here to ensure that my
  58  * enum and the various forms of my name list always match up.
  59  */
  60 #define DIFFLIST(A) \
  61     A(EASY,Easy,e) \
  62     A(HARD,Hard,h)
  63 #define ENUM(upper,title,lower) DIFF_ ## upper,
  64 #define TITLE(upper,title,lower) #title,
  65 #define ENCODE(upper,title,lower) #lower
  66 #define CONFIG(upper,title,lower) ":" #title
  67 enum { DIFFLIST(ENUM) DIFFCOUNT };
  68 static char const *const slant_diffnames[] = { DIFFLIST(TITLE) };
  69 static char const slant_diffchars[] = DIFFLIST(ENCODE);
  70 #define DIFFCONFIG DIFFLIST(CONFIG)
  71
  72 struct game_params {
  73     int w, h, diff;
  74 };
  75
  76 typedef struct game_clues {
  77     int w, h;
  78     signed char *clues;
  79     signed char *tmpsoln;
  80     int refcount;
  81 } game_clues;
  82
  83 #define ERR_VERTEX 1
  84 #define ERR_SQUARE 2
  85
  86 struct game_state {
  87     struct game_params p;
  88     game_clues *clues;
  89     signed char *soln;
  90     unsigned char *errors;
  91     int completed;
  92     int used_solve;                    /* used to suppress completion flash */
  93 };
  94
  95 static game_params *default_params(void)
  96 {
  97     game_params *ret = snew(game_params);
  98
  99     ret->w = ret->h = 8;
 100     ret->diff = DIFF_EASY;
 101
 102     return ret;
 103 }
 104
 105 static const struct game_params slant_presets[] = {
 106     {5, 5, DIFF_EASY},
 107     {5, 5, DIFF_HARD},
 108     {8, 8, DIFF_EASY},
 109     {8, 8, DIFF_HARD},
 110     {12, 10, DIFF_EASY},
 111     {12, 10, DIFF_HARD},
 112 };
 113
 114 static int game_fetch_preset(int i, char **name, game_params **params)
 115 {
 116     game_params *ret;
 117     char str[80];
 118
 119     if (i < 0 || i >= lenof(slant_presets))
 120         return FALSE;
 121
 122     ret = snew(game_params);
 123     *ret = slant_presets[i];
 124
 125     sprintf(str, "%dx%d %s", ret->w, ret->h, slant_diffnames[ret->diff]);
 126
 127     *name = dupstr(str);
 128     *params = ret;
 129     return TRUE;
 130 }
 131
 132 static void free_params(game_params *params)
 133 {
 134     sfree(params);
 135 }
 136
 137 static game_params *dup_params(game_params *params)
 138 {
 139     game_params *ret = snew(game_params);
 140     *ret = *params;                    /* structure copy */
 141     return ret;
 142 }
 143
 144 static void decode_params(game_params *ret, char const *string)
 145 {
 146     ret->w = ret->h = atoi(string);
 147     while (*string && isdigit((unsigned char)*string)) string++;
 148     if (*string == 'x') {
 149         string++;
 150         ret->h = atoi(string);
 151         while (*string && isdigit((unsigned char)*string)) string++;
 152     }
 153     if (*string == 'd') {
 154         int i;
 155         string++;
 156         for (i = 0; i < DIFFCOUNT; i++)
 157             if (*string == slant_diffchars[i])
 158                 ret->diff = i;
 159         if (*string) string++;
 160     }
 161 }
 162
 163 static char *encode_params(game_params *params, int full)
 164 {
 165     char data[256];
 166
 167     sprintf(data, "%dx%d", params->w, params->h);
 168     if (full)
 169         sprintf(data + strlen(data), "d%c", slant_diffchars[params->diff]);
 170
 171     return dupstr(data);
 172 }
 173
 174 static config_item *game_configure(game_params *params)
 175 {
 176     config_item *ret;
 177     char buf[80];
 178
 179     ret = snewn(4, config_item);
 180
 181     ret[0].name = "Width";
 182     ret[0].type = C_STRING;
 183     sprintf(buf, "%d", params->w);
 184     ret[0].sval = dupstr(buf);
 185     ret[0].ival = 0;
 186
 187     ret[1].name = "Height";
 188     ret[1].type = C_STRING;
 189     sprintf(buf, "%d", params->h);
 190     ret[1].sval = dupstr(buf);
 191     ret[1].ival = 0;
 192
 193     ret[2].name = "Difficulty";
 194     ret[2].type = C_CHOICES;
 195     ret[2].sval = DIFFCONFIG;
 196     ret[2].ival = params->diff;
 197
 198     ret[3].name = NULL;
 199     ret[3].type = C_END;
 200     ret[3].sval = NULL;
 201     ret[3].ival = 0;
 202
 203     return ret;
 204 }
 205
 206 static game_params *custom_params(config_item *cfg)
 207 {
 208     game_params *ret = snew(game_params);
 209
 210     ret->w = atoi(cfg[0].sval);
 211     ret->h = atoi(cfg[1].sval);
 212     ret->diff = cfg[2].ival;
 213
 214     return ret;
 215 }
 216
 217 static char *validate_params(game_params *params, int full)
 218 {
 219     /*
 220      * (At least at the time of writing this comment) The grid
 221      * generator is actually capable of handling even zero grid
 222      * dimensions without crashing. Puzzles with a zero-area grid
 223      * are a bit boring, though, because they're already solved :-)
 224      * And puzzles with a dimension of 1 can't be made Hard, which
 225      * means the simplest thing is to forbid them altogether.
 226      */
 227
 228     if (params->w < 2 || params->h < 2)
 229         return "Width and height must both be at least two";
 230
 231     return NULL;
 232 }
 233
 234 /*
 235  * Scratch space for solver.
 236  */
 237 struct solver_scratch {
 238     /*
 239      * Disjoint set forest which tracks the connected sets of
 240      * points.
 241      */
 242     int *connected;
 243
 244     /*
 245      * Counts the number of possible exits from each connected set
 246      * of points. (That is, the number of possible _simultaneous_
 247      * exits: an unconnected point labelled 2 has an exit count of
 248      * 2 even if all four possible edges are still under
 249      * consideration.)
 250      */
 251     int *exits;
 252
 253     /*
 254      * Tracks whether each connected set of points includes a
 255      * border point.
 256      */
 257     unsigned char *border;
 258
 259     /*
 260      * Another disjoint set forest. This one tracks _squares_ which
 261      * are known to slant in the same direction.
 262      */
 263     int *equiv;
 264
 265     /*
 266      * Stores slash values which we know for an equivalence class.
 267      * When we fill in a square, we set slashval[canonify(x)] to
 268      * the same value as soln[x], so that we can then spot other
 269      * squares equivalent to it and fill them in immediately via
 270      * their known equivalence.
 271      */
 272     signed char *slashval;
 273
 274     /*
 275      * Useful to have this information automatically passed to
 276      * solver subroutines. (This pointer is not dynamically
 277      * allocated by new_scratch and free_scratch.)
 278      */
 279     const signed char *clues;
 280 };
 281
 282 static struct solver_scratch *new_scratch(int w, int h)
 283 {
 284     int W = w+1, H = h+1;
 285     struct solver_scratch *ret = snew(struct solver_scratch);
 286     ret->connected = snewn(W*H, int);
 287     ret->exits = snewn(W*H, int);
 288     ret->border = snewn(W*H, unsigned char);
 289     ret->equiv = snewn(w*h, int);
 290     ret->slashval = snewn(w*h, signed char);
 291     return ret;
 292 }
 293
 294 static void free_scratch(struct solver_scratch *sc)
 295 {
 296     sfree(sc->slashval);
 297     sfree(sc->equiv);
 298     sfree(sc->border);
 299     sfree(sc->exits);
 300     sfree(sc->connected);
 301     sfree(sc);
 302 }
 303
 304 /*
 305  * Wrapper on dsf_merge() which updates the `exits' and `border'
 306  * arrays.
 307  */
 308 static void merge_vertices(int *connected,
 309                            struct solver_scratch *sc, int i, int j)
 310 {
 311     int exits = -1, border = FALSE;    /* initialise to placate optimiser */
 312
 313     if (sc) {
 314         i = dsf_canonify(connected, i);
 315         j = dsf_canonify(connected, j);
 316
 317         /*
 318          * We have used one possible exit from each of the two
 319          * classes. Thus, the viable exit count of the new class is
 320          * the sum of the old exit counts minus two.
 321          */
 322         exits = sc->exits[i] + sc->exits[j] - 2;
 323
 324         border = sc->border[i] || sc->border[j];
 325     }
 326
 327     dsf_merge(connected, i, j);
 328
 329     if (sc) {
 330         i = dsf_canonify(connected, i);
 331         sc->exits[i] = exits;
 332         sc->border[i] = border;
 333     }
 334 }
 335
 336 /*
 337  * Called when we have just blocked one way out of a particular
 338  * point. If that point is a non-clue point (thus has a variable
 339  * number of exits), we have therefore decreased its potential exit
 340  * count, so we must decrement the exit count for the group as a
 341  * whole.
 342  */
 343 static void decr_exits(struct solver_scratch *sc, int i)
 344 {
 345     if (sc->clues[i] < 0) {
 346         i = dsf_canonify(sc->connected, i);
 347         sc->exits[i]--;
 348     }
 349 }
 350
 351 static void fill_square(int w, int h, int x, int y, int v,
 352                         signed char *soln,
 353                         int *connected, struct solver_scratch *sc)
 354 {
 355     int W = w+1 /*, H = h+1 */;
 356
 357     assert(x >= 0 && x < w && y >= 0 && y < h);
 358
 359     if (soln[y*w+x] != 0) {
 360         return;                        /* do nothing */
 361     }
 362
 363 #ifdef SOLVER_DIAGNOSTICS
 364     if (verbose)
 365         printf("  placing %c in %d,%d\n", v == -1 ? '\\' : '/', x, y);
 366 #endif
 367
 368     soln[y*w+x] = v;
 369
 370     if (sc) {
 371         int c = dsf_canonify(sc->equiv, y*w+x);
 372         sc->slashval[c] = v;
 373     }
 374
 375     if (v < 0) {
 376         merge_vertices(connected, sc, y*W+x, (y+1)*W+(x+1));
 377         if (sc) {
 378             decr_exits(sc, y*W+(x+1));
 379             decr_exits(sc, (y+1)*W+x);
 380         }
 381     } else {
 382         merge_vertices(connected, sc, y*W+(x+1), (y+1)*W+x);
 383         if (sc) {
 384             decr_exits(sc, y*W+x);
 385             decr_exits(sc, (y+1)*W+(x+1));
 386         }
 387     }
 388 }
 389
 390 /*
 391  * Solver. Returns 0 for impossibility, 1 for success, 2 for
 392  * ambiguity or failure to converge.
 393  */
 394 static int slant_solve(int w, int h, const signed char *clues,
 395                        signed char *soln, struct solver_scratch *sc,
 396                        int difficulty)
 397 {
 398     int W = w+1, H = h+1;
 399     int x, y, i, j;
 400     int done_something;
 401
 402     /*
 403      * Clear the output.
 404      */
 405     memset(soln, 0, w*h);
 406
 407     sc->clues = clues;
 408
 409     /*
 410      * Establish a disjoint set forest for tracking connectedness
 411      * between grid points.
 412      */
 413     for (i = 0; i < W*H; i++)
 414         sc->connected[i] = i;          /* initially all distinct */
 415
 416     /*
 417      * Establish a disjoint set forest for tracking which squares
 418      * are known to slant in the same direction.
 419      */
 420     for (i = 0; i < w*h; i++)
 421         sc->equiv[i] = i;              /* initially all distinct */
 422
 423     /*
 424      * Clear the slashval array.
 425      */
 426     memset(sc->slashval, 0, w*h);
 427
 428     /*
 429      * Initialise the `exits' and `border' arrays. Theses is used
 430      * to do second-order loop avoidance: the dual of the no loops
 431      * constraint is that every point must be somehow connected to
 432      * the border of the grid (otherwise there would be a solid
 433      * loop around it which prevented this).
 434      *
 435      * I define a `dead end' to be a connected group of points
 436      * which contains no border point, and which can form at most
 437      * one new connection outside itself. Then I forbid placing an
 438      * edge so that it connects together two dead-end groups, since
 439      * this would yield a non-border-connected isolated subgraph
 440      * with no further scope to extend it.
 441      */
 442     for (y = 0; y < H; y++)
 443         for (x = 0; x < W; x++) {
 444             if (y == 0 || y == H-1 || x == 0 || x == W-1)
 445                 sc->border[y*W+x] = TRUE;
 446             else
 447                 sc->border[y*W+x] = FALSE;
 448
 449             if (clues[y*W+x] < 0)
 450                 sc->exits[y*W+x] = 4;
 451             else
 452                 sc->exits[y*W+x] = clues[y*W+x];
 453         }
 454
 455     /*
 456      * Make a one-off preliminary pass over the grid looking for
 457      * starting-point arrangements. The ones we need to spot are:
 458      *
 459      *  - two adjacent 1s in the centre of the grid imply that each
 460      *    one's single line points towards the other. (If either 1
 461      *    were connected on the far side, the two squares shared
 462      *    between the 1s would both link to the other 1 as a
 463      *    consequence of neither linking to the first.) Thus, we
 464      *    can fill in the four squares around them.
 465      *
 466      *  - dually, two adjacent 3s imply that each one's _non_-line
 467      *    points towards the other.
 468      *
 469      *  - if the pair of 1s and 3s is not _adjacent_ but is
 470      *    separated by one or more 2s, the reasoning still applies.
 471      *
 472      * This is more advanced than just spotting obvious starting
 473      * squares such as central 4s and edge 2s, so we disable it on
 474      * DIFF_EASY.
 475      *
 476      * (I don't like this loop; it feels grubby to me. My
 477      * mathematical intuition feels there ought to be some more
 478      * general deductive form which contains this loop as a special
 479      * case, but I can't bring it to mind right now.)
 480      */
 481     if (difficulty > DIFF_EASY) {
 482         for (y = 1; y+1 < H; y++)
 483             for (x = 1; x+1 < W; x++) {
 484                 int v = clues[y*W+x], s, x2, y2, dx, dy;
 485                 if (v != 1 && v != 3)
 486                     continue;
 487                 /* Slash value of the square up and left of (x,y). */
 488                 s = (v == 1 ? +1 : -1);
 489
 490                 /* Look in each direction once. */
 491                 for (dy = 0; dy < 2; dy++) {
 492                     dx = 1 - dy;
 493                     x2 = x+dx;
 494                     y2 = y+dy;
 495                     if (x2+1 >= W || y2+1 >= H)
 496                         continue;              /* too close to the border */
 497                     while (x2+dx+1 < W && y2+dy+1 < H && clues[y2*W+x2] == 2)
 498                         x2 += dx, y2 += dy;
 499                     if (clues[y2*W+x2] == v) {
 500 #ifdef SOLVER_DIAGNOSTICS
 501                         if (verbose)
 502                             printf("found adjacent %ds at %d,%d and %d,%d\n",
 503                                    v, x, y, x2, y2);
 504 #endif
 505                         fill_square(w, h, x-1, y-1, s, soln,
 506                                     sc->connected, sc);
 507                         fill_square(w, h, x-1+dy, y-1+dx, -s, soln,
 508                                     sc->connected, sc);
 509                         fill_square(w, h, x2, y2, s, soln,
 510                                     sc->connected, sc);
 511                         fill_square(w, h, x2-dy, y2-dx, -s, soln,
 512                                     sc->connected, sc);
 513                     }
 514                 }
 515             }
 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     } while (done_something);
 840
 841     /*
 842      * Solver can make no more progress. See if the grid is full.
 843      */
 844     for (i = 0; i < w*h; i++)
 845         if (!soln[i])
 846             return 2;                  /* failed to converge */
 847     return 1;                          /* success */
 848 }
 849
 850 /*
 851  * Filled-grid generator.
 852  */
 853 static void slant_generate(int w, int h, signed char *soln, random_state *rs)
 854 {
 855     int W = w+1, H = h+1;
 856     int x, y, i;
 857     int *connected, *indices;
 858
 859     /*
 860      * Clear the output.
 861      */
 862     memset(soln, 0, w*h);
 863
 864     /*
 865      * Establish a disjoint set forest for tracking connectedness
 866      * between grid points.
 867      */
 868     connected = snewn(W*H, int);
 869     for (i = 0; i < W*H; i++)
 870         connected[i] = i;                      /* initially all distinct */
 871
 872     /*
 873      * Prepare a list of the squares in the grid, and fill them in
 874      * in a random order.
 875      */
 876     indices = snewn(w*h, int);
 877     for (i = 0; i < w*h; i++)
 878         indices[i] = i;
 879     shuffle(indices, w*h, sizeof(*indices), rs);
 880
 881     /*
 882      * Fill in each one in turn.
 883      */
 884     for (i = 0; i < w*h; i++) {
 885         int fs, bs, v;
 886
 887         y = indices[i] / w;
 888         x = indices[i] % w;
 889
 890         fs = (dsf_canonify(connected, y*W+x) ==
 891               dsf_canonify(connected, (y+1)*W+(x+1)));
 892         bs = (dsf_canonify(connected, (y+1)*W+x) ==
 893               dsf_canonify(connected, y*W+(x+1)));
 894
 895         /*
 896          * It isn't possible to get into a situation where we
 897          * aren't allowed to place _either_ type of slash in a
 898          * square. Thus, filled-grid generation never has to
 899          * backtrack.
 900          *
 901          * Proof (thanks to Gareth Taylor):
 902          *
 903          * If it were possible, it would have to be because there
 904          * was an existing path (not using this square) between the
 905          * top-left and bottom-right corners of this square, and
 906          * another between the other two. These two paths would
 907          * have to cross at some point.
 908          *
 909          * Obviously they can't cross in the middle of a square, so
 910          * they must cross by sharing a point in common. But this
 911          * isn't possible either: if you chessboard-colour all the
 912          * points on the grid, you find that any continuous
 913          * diagonal path is entirely composed of points of the same
 914          * colour. And one of our two hypothetical paths is between
 915          * two black points, and the other is between two white
 916          * points - therefore they can have no point in common. []
 917          */
 918         assert(!(fs && bs));
 919
 920         v = fs ? +1 : bs ? -1 : 2 * random_upto(rs, 2) - 1;
 921         fill_square(w, h, x, y, v, soln, connected, NULL);
 922     }
 923
 924     sfree(indices);
 925     sfree(connected);
 926 }
 927
 928 static char *new_game_desc(game_params *params, random_state *rs,
 929                            char **aux, int interactive)
 930 {
 931     int w = params->w, h = params->h, W = w+1, H = h+1;
 932     signed char *soln, *tmpsoln, *clues;
 933     int *clueindices;
 934     struct solver_scratch *sc;
 935     int x, y, v, i, j;
 936     char *desc;
 937
 938     soln = snewn(w*h, signed char);
 939     tmpsoln = snewn(w*h, signed char);
 940     clues = snewn(W*H, signed char);
 941     clueindices = snewn(W*H, int);
 942     sc = new_scratch(w, h);
 943
 944     do {
 945         /*
 946          * Create the filled grid.
 947          */
 948         slant_generate(w, h, soln, rs);
 949
 950         /*
 951          * Fill in the complete set of clues.
 952          */
 953         for (y = 0; y < H; y++)
 954             for (x = 0; x < W; x++) {
 955                 v = 0;
 956
 957                 if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] == -1) v++;
 958                 if (x > 0 && y < h && soln[y*w+(x-1)] == +1) v++;
 959                 if (x < w && y > 0 && soln[(y-1)*w+x] == +1) v++;
 960                 if (x < w && y < h && soln[y*w+x] == -1) v++;
 961
 962                 clues[y*W+x] = v;
 963             }
 964
 965         /*
 966          * With all clue points filled in, all puzzles are easy: we can
 967          * simply process the clue points in lexicographic order, and
 968          * at each clue point we will always have at most one square
 969          * undecided, which we can then fill in uniquely.
 970          */
 971         assert(slant_solve(w, h, clues, tmpsoln, sc, DIFF_EASY) == 1);
 972
 973         /*
 974          * Remove as many clues as possible while retaining solubility.
 975          *
 976          * In DIFF_HARD mode, we prioritise the removal of obvious
 977          * starting points (4s, 0s, border 2s and corner 1s), on
 978          * the grounds that having as few of these as possible
 979          * seems like a good thing. In particular, we can often get
 980          * away without _any_ completely obvious starting points,
 981          * which is even better.
 982          */
 983         for (i = 0; i < W*H; i++)
 984             clueindices[i] = i;
 985         shuffle(clueindices, W*H, sizeof(*clueindices), rs);
 986         for (j = 0; j < 2; j++) {
 987             for (i = 0; i < W*H; i++) {
 988                 int pass, yb, xb;
 989
 990                 y = clueindices[i] / W;
 991                 x = clueindices[i] % W;
 992                 v = clues[y*W+x];
 993
 994                 /*
 995                  * Identify which pass we should process this point
 996                  * in. If it's an obvious start point, _or_ we're
 997                  * in DIFF_EASY, then it goes in pass 0; otherwise
 998                  * pass 1.
 999                  */
1000                 xb = (x == 0 || x == W-1);
1001                 yb = (y == 0 || y == H-1);
1002                 if (params->diff == DIFF_EASY || v == 4 || v == 0 ||
1003                     (v == 2 && (xb||yb)) || (v == 1 && xb && yb))
1004                     pass = 0;
1005                 else
1006                     pass = 1;
1007
1008                 if (pass == j) {
1009                     clues[y*W+x] = -1;
1010                     if (slant_solve(w, h, clues, tmpsoln, sc,
1011                                     params->diff) != 1)
1012                         clues[y*W+x] = v;              /* put it back */
1013                 }
1014             }
1015         }
1016
1017         /*
1018          * And finally, verify that the grid is of _at least_ the
1019          * requested difficulty, by running the solver one level
1020          * down and verifying that it can't manage it.
1021          */
1022     } while (params->diff > 0 &&
1023              slant_solve(w, h, clues, tmpsoln, sc, params->diff - 1) <= 1);
1024
1025     /*
1026      * Now we have the clue set as it will be presented to the
1027      * user. Encode it in a game desc.
1028      */
1029     {
1030         char *p;
1031         int run, i;
1032
1033         desc = snewn(W*H+1, char);
1034         p = desc;
1035         run = 0;
1036         for (i = 0; i <= W*H; i++) {
1037             int n = (i < W*H ? clues[i] : -2);
1038
1039             if (n == -1)
1040                 run++;
1041             else {
1042                 if (run) {
1043                     while (run > 0) {
1044                         int c = 'a' - 1 + run;
1045                         if (run > 26)
1046                             c = 'z';
1047                         *p++ = c;
1048                         run -= c - ('a' - 1);
1049                     }
1050                 }
1051                 if (n >= 0)
1052                     *p++ = '0' + n;
1053                 run = 0;
1054             }
1055         }
1056         assert(p - desc <= W*H);
1057         *p++ = '\0';
1058         desc = sresize(desc, p - desc, char);
1059     }
1060
1061     /*
1062      * Encode the solution as an aux_info.
1063      */
1064     {
1065         char *auxbuf;
1066         *aux = auxbuf = snewn(w*h+1, char);
1067         for (i = 0; i < w*h; i++)
1068             auxbuf[i] = soln[i] < 0 ? '\\' : '/';
1069         auxbuf[w*h] = '\0';
1070     }
1071
1072     free_scratch(sc);
1073     sfree(clueindices);
1074     sfree(clues);
1075     sfree(tmpsoln);
1076     sfree(soln);
1077
1078     return desc;
1079 }
1080
1081 static char *validate_desc(game_params *params, char *desc)
1082 {
1083     int w = params->w, h = params->h, W = w+1, H = h+1;
1084     int area = W*H;
1085     int squares = 0;
1086
1087     while (*desc) {
1088         int n = *desc++;
1089         if (n >= 'a' && n <= 'z') {
1090             squares += n - 'a' + 1;
1091         } else if (n >= '0' && n <= '4') {
1092             squares++;
1093         } else
1094             return "Invalid character in game description";
1095     }
1096
1097     if (squares < area)
1098         return "Not enough data to fill grid";
1099
1100     if (squares > area)
1101         return "Too much data to fit in grid";
1102
1103     return NULL;
1104 }
1105
1106 static game_state *new_game(midend *me, game_params *params, char *desc)
1107 {
1108     int w = params->w, h = params->h, W = w+1, H = h+1;
1109     game_state *state = snew(game_state);
1110     int area = W*H;
1111     int squares = 0;
1112
1113     state->p = *params;
1114     state->soln = snewn(w*h, signed char);
1115     memset(state->soln, 0, w*h);
1116     state->completed = state->used_solve = FALSE;
1117     state->errors = snewn(W*H, unsigned char);
1118     memset(state->errors, 0, W*H);
1119
1120     state->clues = snew(game_clues);
1121     state->clues->w = w;
1122     state->clues->h = h;
1123     state->clues->clues = snewn(W*H, signed char);
1124     state->clues->refcount = 1;
1125     state->clues->tmpsoln = snewn(w*h, signed char);
1126     memset(state->clues->clues, -1, W*H);
1127     while (*desc) {
1128         int n = *desc++;
1129         if (n >= 'a' && n <= 'z') {
1130             squares += n - 'a' + 1;
1131         } else if (n >= '0' && n <= '4') {
1132             state->clues->clues[squares++] = n - '0';
1133         } else
1134             assert(!"can't get here");
1135     }
1136     assert(squares == area);
1137
1138     return state;
1139 }
1140
1141 static game_state *dup_game(game_state *state)
1142 {
1143     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1144     game_state *ret = snew(game_state);
1145
1146     ret->p = state->p;
1147     ret->clues = state->clues;
1148     ret->clues->refcount++;
1149     ret->completed = state->completed;
1150     ret->used_solve = state->used_solve;
1151
1152     ret->soln = snewn(w*h, signed char);
1153     memcpy(ret->soln, state->soln, w*h);
1154
1155     ret->errors = snewn(W*H, unsigned char);
1156     memcpy(ret->errors, state->errors, W*H);
1157
1158     return ret;
1159 }
1160
1161 static void free_game(game_state *state)
1162 {
1163     sfree(state->errors);
1164     sfree(state->soln);
1165     assert(state->clues);
1166     if (--state->clues->refcount <= 0) {
1167         sfree(state->clues->clues);
1168         sfree(state->clues->tmpsoln);
1169         sfree(state->clues);
1170     }
1171     sfree(state);
1172 }
1173
1174 /*
1175  * Utility function to return the current degree of a vertex. If
1176  * `anti' is set, it returns the number of filled-in edges
1177  * surrounding the point which _don't_ connect to it; thus 4 minus
1178  * its anti-degree is the maximum degree it could have if all the
1179  * empty spaces around it were filled in.
1180  *
1181  * (Yes, _4_ minus its anti-degree even if it's a border vertex.)
1182  *
1183  * If ret > 0, *sx and *sy are set to the coordinates of one of the
1184  * squares that contributed to it.
1185  */
1186 static int vertex_degree(int w, int h, signed char *soln, int x, int y,
1187                          int anti, int *sx, int *sy)
1188 {
1189     int ret = 0;
1190
1191     assert(x >= 0 && x <= w && y >= 0 && y <= h);
1192     if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] - anti < 0) {
1193         if (sx) *sx = x-1;
1194         if (sy) *sy = y-1;
1195         ret++;
1196     }
1197     if (x > 0 && y < h && soln[y*w+(x-1)] + anti > 0) {
1198         if (sx) *sx = x-1;
1199         if (sy) *sy = y;
1200         ret++;
1201     }
1202     if (x < w && y > 0 && soln[(y-1)*w+x] + anti > 0) {
1203         if (sx) *sx = x;
1204         if (sy) *sy = y-1;
1205         ret++;
1206     }
1207     if (x < w && y < h && soln[y*w+x] - anti < 0) {
1208         if (sx) *sx = x;
1209         if (sy) *sy = y;
1210         ret++;
1211     }
1212
1213     return anti ? 4 - ret : ret;
1214 }
1215
1216 static int check_completion(game_state *state)
1217 {
1218     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1219     int x, y, err = FALSE;
1220     signed char *ts;
1221
1222     memset(state->errors, 0, W*H);
1223
1224     /*
1225      * An easy way to do loop checking would be by means of the
1226      * same dsf technique we've used elsewhere (loop over all edges
1227      * in the grid, joining vertices together into equivalence
1228      * classes when connected by an edge, and raise the alarm when
1229      * an edge joins two already-equivalent vertices). However, a
1230      * better approach is to repeatedly remove the single edge
1231      * connecting to any degree-1 vertex, and then see if there are
1232      * any edges left over; if so, precisely those edges are part
1233      * of loops, which means we can highlight them as errors for
1234      * the user.
1235      *
1236      * We use the `tmpsoln' scratch space in the shared clues
1237      * structure, to avoid mallocing too often.
1238      */
1239     ts = state->clues->tmpsoln;
1240     memcpy(ts, state->soln, w*h);
1241     for (y = 0; y < H; y++)
1242         for (x = 0; x < W; x++) {
1243             int vx = x, vy = y;
1244             int sx, sy;
1245             /*
1246              * Every time we disconnect a vertex like this, there
1247              * is precisely one other vertex which might have
1248              * become degree 1; so we follow the trail as far as it
1249              * leads. This ensures that we don't have to make more
1250              * than one loop over the grid, because whenever a
1251              * degree-1 vertex comes into existence somewhere we've
1252              * already looked, we immediately remove it again.
1253              * Hence one loop over the grid is adequate; and
1254              * moreover, this algorithm visits every vertex at most
1255              * twice (once in the loop and possibly once more as a
1256              * result of following a trail) so it has linear time
1257              * in the area of the grid.
1258              */
1259             while (vertex_degree(w, h, ts, vx, vy, FALSE, &sx, &sy) == 1) {
1260                 ts[sy*w+sx] = 0;
1261                 vx = vx + 1 + (sx - vx) * 2;
1262                 vy = vy + 1 + (sy - vy) * 2;
1263             }
1264         }
1265
1266     /*
1267      * Now mark any remaining edges with ERR_SQUARE.
1268      */
1269     for (y = 0; y < h; y++)
1270         for (x = 0; x < w; x++)
1271             if (ts[y*w+x]) {
1272                 state->errors[y*W+x] |= ERR_SQUARE;
1273                 err = TRUE;
1274             }
1275
1276     /*
1277      * Now go through and check the degree of each clue vertex, and
1278      * mark it with ERR_VERTEX if it cannot be fulfilled.
1279      */
1280     for (y = 0; y < H; y++)
1281         for (x = 0; x < W; x++) {
1282             int c;
1283
1284             if ((c = state->clues->clues[y*W+x]) < 0)
1285                 continue;
1286
1287             /*
1288              * Check to see if there are too many connections to
1289              * this vertex _or_ too many non-connections. Either is
1290              * grounds for marking the vertex as erroneous.
1291              */
1292             if (vertex_degree(w, h, state->soln, x, y,
1293                               FALSE, NULL, NULL) > c ||
1294                 vertex_degree(w, h, state->soln, x, y,
1295                               TRUE, NULL, NULL) > 4-c) {
1296                 state->errors[y*W+x] |= ERR_VERTEX;
1297                 err = TRUE;
1298             }
1299         }
1300
1301     /*
1302      * Now our actual victory condition is that (a) none of the
1303      * above code marked anything as erroneous, and (b) every
1304      * square has an edge in it.
1305      */
1306
1307     if (err)
1308         return FALSE;
1309
1310     for (y = 0; y < h; y++)
1311         for (x = 0; x < w; x++)
1312             if (state->soln[y*w+x] == 0)
1313                 return FALSE;
1314
1315     return TRUE;
1316 }
1317
1318 static char *solve_game(game_state *state, game_state *currstate,
1319                         char *aux, char **error)
1320 {
1321     int w = state->p.w, h = state->p.h;
1322     signed char *soln;
1323     int bs, ret;
1324     int free_soln = FALSE;
1325     char *move, buf[80];
1326     int movelen, movesize;
1327     int x, y;
1328
1329     if (aux) {
1330         /*
1331          * If we already have the solution, save ourselves some
1332          * time.
1333          */
1334         soln = (signed char *)aux;
1335         bs = (signed char)'\\';
1336         free_soln = FALSE;
1337     } else {
1338         struct solver_scratch *sc = new_scratch(w, h);
1339         soln = snewn(w*h, signed char);
1340         bs = -1;
1341         ret = slant_solve(w, h, state->clues->clues, soln, sc, DIFF_HARD);
1342         free_scratch(sc);
1343         if (ret != 1) {
1344             sfree(soln);
1345             if (ret == 0)
1346                 *error = "This puzzle is not self-consistent";
1347             else
1348                 *error = "Unable to find a unique solution for this puzzle";
1349             return NULL;
1350         }
1351         free_soln = TRUE;
1352     }
1353
1354     /*
1355      * Construct a move string which turns the current state into
1356      * the solved state.
1357      */
1358     movesize = 256;
1359     move = snewn(movesize, char);
1360     movelen = 0;
1361     move[movelen++] = 'S';
1362     move[movelen] = '\0';
1363     for (y = 0; y < h; y++)
1364         for (x = 0; x < w; x++) {
1365             int v = (soln[y*w+x] == bs ? -1 : +1);
1366             if (state->soln[y*w+x] != v) {
1367                 int len = sprintf(buf, ";%c%d,%d", (int)(v < 0 ? '\\' : '/'), x, y);
1368                 if (movelen + len >= movesize) {
1369                     movesize = movelen + len + 256;
1370                     move = sresize(move, movesize, char);
1371                 }
1372                 strcpy(move + movelen, buf);
1373                 movelen += len;
1374             }
1375         }
1376
1377     if (free_soln)
1378         sfree(soln);
1379
1380     return move;
1381 }
1382
1383 static char *game_text_format(game_state *state)
1384 {
1385     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1386     int x, y, len;
1387     char *ret, *p;
1388
1389     /*
1390      * There are h+H rows of w+W columns.
1391      */
1392     len = (h+H) * (w+W+1) + 1;
1393     ret = snewn(len, char);
1394     p = ret;
1395
1396     for (y = 0; y < H; y++) {
1397         for (x = 0; x < W; x++) {
1398             if (state->clues->clues[y*W+x] >= 0)
1399                 *p++ = state->clues->clues[y*W+x] + '0';
1400             else
1401                 *p++ = '+';
1402             if (x < w)
1403                 *p++ = '-';
1404         }
1405         *p++ = '\n';
1406         if (y < h) {
1407             for (x = 0; x < W; x++) {
1408                 *p++ = '|';
1409                 if (x < w) {
1410                     if (state->soln[y*w+x] != 0)
1411                         *p++ = (state->soln[y*w+x] < 0 ? '\\' : '/');
1412                     else
1413                         *p++ = ' ';
1414                 }
1415             }
1416             *p++ = '\n';
1417         }
1418     }
1419     *p++ = '\0';
1420
1421     assert(p - ret == len);
1422     return ret;
1423 }
1424
1425 static game_ui *new_ui(game_state *state)
1426 {
1427     return NULL;
1428 }
1429
1430 static void free_ui(game_ui *ui)
1431 {
1432 }
1433
1434 static char *encode_ui(game_ui *ui)
1435 {
1436     return NULL;
1437 }
1438
1439 static void decode_ui(game_ui *ui, char *encoding)
1440 {
1441 }
1442
1443 static void game_changed_state(game_ui *ui, game_state *oldstate,
1444                                game_state *newstate)
1445 {
1446 }
1447
1448 #define PREFERRED_TILESIZE 32
1449 #define TILESIZE (ds->tilesize)
1450 #define BORDER TILESIZE
1451 #define CLUE_RADIUS (TILESIZE / 3)
1452 #define CLUE_TEXTSIZE (TILESIZE / 2)
1453 #define COORD(x)  ( (x) * TILESIZE + BORDER )
1454 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1455
1456 #define FLASH_TIME 0.30F
1457
1458 /*
1459  * Bit fields in the `grid' and `todraw' elements of the drawstate.
1460  */
1461 #define BACKSLASH 0x00000001L
1462 #define FORWSLASH 0x00000002L
1463 #define L_T       0x00000004L
1464 #define ERR_L_T   0x00000008L
1465 #define L_B       0x00000010L
1466 #define ERR_L_B   0x00000020L
1467 #define T_L       0x00000040L
1468 #define ERR_T_L   0x00000080L
1469 #define T_R       0x00000100L
1470 #define ERR_T_R   0x00000200L
1471 #define C_TL      0x00000400L
1472 #define ERR_C_TL  0x00000800L
1473 #define FLASH     0x00001000L
1474 #define ERRSLASH  0x00002000L
1475 #define ERR_TL    0x00004000L
1476 #define ERR_TR    0x00008000L
1477 #define ERR_BL    0x00010000L
1478 #define ERR_BR    0x00020000L
1479
1480 struct game_drawstate {
1481     int tilesize;
1482     int started;
1483     long *grid;
1484     long *todraw;
1485 };
1486
1487 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1488                             int x, int y, int button)
1489 {
1490     int w = state->p.w, h = state->p.h;
1491
1492     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1493         int v;
1494         char buf[80];
1495
1496         /*
1497          * This is an utterly awful hack which I should really sort out
1498          * by means of a proper configuration mechanism. One Slant
1499          * player has observed that they prefer the mouse buttons to
1500          * function exactly the opposite way round, so here's a
1501          * mechanism for environment-based configuration. I cache the
1502          * result in a global variable - yuck! - to avoid repeated
1503          * lookups.
1504          */
1505         {
1506             static int swap_buttons = -1;
1507             if (swap_buttons < 0) {
1508                 char *env = getenv("SLANT_SWAP_BUTTONS");
1509                 swap_buttons = (env && (env[0] == 'y' || env[0] == 'Y'));
1510             }
1511             if (swap_buttons) {
1512                 if (button == LEFT_BUTTON)
1513                     button = RIGHT_BUTTON;
1514                 else
1515                     button = LEFT_BUTTON;
1516             }
1517         }
1518
1519         x = FROMCOORD(x);
1520         y = FROMCOORD(y);
1521         if (x < 0 || y < 0 || x >= w || y >= h)
1522             return NULL;
1523
1524         if (button == LEFT_BUTTON) {
1525             /*
1526              * Left-clicking cycles blank -> \ -> / -> blank.
1527              */
1528             v = state->soln[y*w+x] - 1;
1529             if (v == -2)
1530                 v = +1;
1531         } else {
1532             /*
1533              * Right-clicking cycles blank -> / -> \ -> blank.
1534              */
1535             v = state->soln[y*w+x] + 1;
1536             if (v == +2)
1537                 v = -1;
1538         }
1539
1540         sprintf(buf, "%c%d,%d", (int)(v==-1 ? '\\' : v==+1 ? '/' : 'C'), x, y);
1541         return dupstr(buf);
1542     }
1543
1544     return NULL;
1545 }
1546
1547 static game_state *execute_move(game_state *state, char *move)
1548 {
1549     int w = state->p.w, h = state->p.h;
1550     char c;
1551     int x, y, n;
1552     game_state *ret = dup_game(state);
1553
1554     while (*move) {
1555         c = *move;
1556         if (c == 'S') {
1557             ret->used_solve = TRUE;
1558             move++;
1559         } else if (c == '\\' || c == '/' || c == 'C') {
1560             move++;
1561             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1562                 x < 0 || y < 0 || x >= w || y >= h) {
1563                 free_game(ret);
1564                 return NULL;
1565             }
1566             ret->soln[y*w+x] = (c == '\\' ? -1 : c == '/' ? +1 : 0);
1567             move += n;
1568         } else {
1569             free_game(ret);
1570             return NULL;
1571         }
1572         if (*move == ';')
1573             move++;
1574         else if (*move) {
1575             free_game(ret);
1576             return NULL;
1577         }
1578     }
1579
1580     /*
1581      * We never clear the `completed' flag, but we must always
1582      * re-run the completion check because it also highlights
1583      * errors in the grid.
1584      */
1585     ret->completed = check_completion(ret) || ret->completed;
1586
1587     return ret;
1588 }
1589
1590 /* ----------------------------------------------------------------------
1591  * Drawing routines.
1592  */
1593
1594 static void game_compute_size(game_params *params, int tilesize,
1595                               int *x, int *y)
1596 {
1597     /* fool the macros */
1598     struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy;
1599
1600     *x = 2 * BORDER + params->w * TILESIZE + 1;
1601     *y = 2 * BORDER + params->h * TILESIZE + 1;
1602 }
1603
1604 static void game_set_size(drawing *dr, game_drawstate *ds,
1605                           game_params *params, int tilesize)
1606 {
1607     ds->tilesize = tilesize;
1608 }
1609
1610 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1611 {
1612     float *ret = snewn(3 * NCOLOURS, float);
1613
1614     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1615
1616     ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.7F;
1617     ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.7F;
1618     ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.7F;
1619
1620     ret[COL_INK * 3 + 0] = 0.0F;
1621     ret[COL_INK * 3 + 1] = 0.0F;
1622     ret[COL_INK * 3 + 2] = 0.0F;
1623
1624     ret[COL_SLANT1 * 3 + 0] = 0.0F;
1625     ret[COL_SLANT1 * 3 + 1] = 0.0F;
1626     ret[COL_SLANT1 * 3 + 2] = 0.0F;
1627
1628     ret[COL_SLANT2 * 3 + 0] = 0.0F;
1629     ret[COL_SLANT2 * 3 + 1] = 0.0F;
1630     ret[COL_SLANT2 * 3 + 2] = 0.0F;
1631
1632     ret[COL_ERROR * 3 + 0] = 1.0F;
1633     ret[COL_ERROR * 3 + 1] = 0.0F;
1634     ret[COL_ERROR * 3 + 2] = 0.0F;
1635
1636     *ncolours = NCOLOURS;
1637     return ret;
1638 }
1639
1640 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1641 {
1642     int w = state->p.w, h = state->p.h;
1643     int i;
1644     struct game_drawstate *ds = snew(struct game_drawstate);
1645
1646     ds->tilesize = 0;
1647     ds->started = FALSE;
1648     ds->grid = snewn((w+2)*(h+2), long);
1649     ds->todraw = snewn((w+2)*(h+2), long);
1650     for (i = 0; i < (w+2)*(h+2); i++)
1651         ds->grid[i] = ds->todraw[i] = -1;
1652
1653     return ds;
1654 }
1655
1656 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1657 {
1658     sfree(ds->todraw);
1659     sfree(ds->grid);
1660     sfree(ds);
1661 }
1662
1663 static void draw_clue(drawing *dr, game_drawstate *ds,
1664                       int x, int y, long v, long err, int bg, int colour)
1665 {
1666     char p[2];
1667     int ccol = colour >= 0 ? colour : ((x ^ y) & 1) ? COL_SLANT1 : COL_SLANT2;
1668     int tcol = colour >= 0 ? colour : err ? COL_ERROR : COL_INK;
1669
1670     if (v < 0)
1671         return;
1672
1673     p[0] = v + '0';
1674     p[1] = '\0';
1675     draw_circle(dr, COORD(x), COORD(y), CLUE_RADIUS,
1676                 bg >= 0 ? bg : COL_BACKGROUND, ccol);
1677     draw_text(dr, COORD(x), COORD(y), FONT_VARIABLE,
1678               CLUE_TEXTSIZE, ALIGN_VCENTRE|ALIGN_HCENTRE, tcol, p);
1679 }
1680
1681 static void draw_tile(drawing *dr, game_drawstate *ds, game_clues *clues,
1682                       int x, int y, long v)
1683 {
1684     int w = clues->w, h = clues->h, W = w+1 /*, H = h+1 */;
1685     int chesscolour = (x ^ y) & 1;
1686     int fscol = chesscolour ? COL_SLANT2 : COL_SLANT1;
1687     int bscol = chesscolour ? COL_SLANT1 : COL_SLANT2;
1688
1689     clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1690
1691     draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
1692               (v & FLASH) ? COL_GRID : COL_BACKGROUND);
1693
1694     /*
1695      * Draw the grid lines.
1696      */
1697     if (x >= 0 && x < w && y >= 0)
1698         draw_rect(dr, COORD(x), COORD(y), TILESIZE+1, 1, COL_GRID);
1699     if (x >= 0 && x < w && y < h)
1700         draw_rect(dr, COORD(x), COORD(y+1), TILESIZE+1, 1, COL_GRID);
1701     if (y >= 0 && y < h && x >= 0)
1702         draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE+1, COL_GRID);
1703     if (y >= 0 && y < h && x < w)
1704         draw_rect(dr, COORD(x+1), COORD(y), 1, TILESIZE+1, COL_GRID);
1705     if (x == -1 && y == -1)
1706         draw_rect(dr, COORD(x+1), COORD(y+1), 1, 1, COL_GRID);
1707     if (x == -1 && y == h)
1708         draw_rect(dr, COORD(x+1), COORD(y), 1, 1, COL_GRID);
1709     if (x == w && y == -1)
1710         draw_rect(dr, COORD(x), COORD(y+1), 1, 1, COL_GRID);
1711     if (x == w && y == h)
1712         draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
1713
1714     /*
1715      * Draw the slash.
1716      */
1717     if (v & BACKSLASH) {
1718         int scol = (v & ERRSLASH) ? COL_ERROR : bscol;
1719         draw_line(dr, COORD(x), COORD(y), COORD(x+1), COORD(y+1), scol);
1720         draw_line(dr, COORD(x)+1, COORD(y), COORD(x+1), COORD(y+1)-1,
1721                   scol);
1722         draw_line(dr, COORD(x), COORD(y)+1, COORD(x+1)-1, COORD(y+1),
1723                   scol);
1724     } else if (v & FORWSLASH) {
1725         int scol = (v & ERRSLASH) ? COL_ERROR : fscol;
1726         draw_line(dr, COORD(x+1), COORD(y), COORD(x), COORD(y+1), scol);
1727         draw_line(dr, COORD(x+1)-1, COORD(y), COORD(x), COORD(y+1)-1,
1728                   scol);
1729         draw_line(dr, COORD(x+1), COORD(y)+1, COORD(x)+1, COORD(y+1),
1730                   scol);
1731     }
1732
1733     /*
1734      * Draw dots on the grid corners that appear if a slash is in a
1735      * neighbouring cell.
1736      */
1737     if (v & (L_T | BACKSLASH))
1738         draw_rect(dr, COORD(x), COORD(y)+1, 1, 1,
1739                   (v & ERR_L_T ? COL_ERROR : bscol));
1740     if (v & (L_B | FORWSLASH))
1741         draw_rect(dr, COORD(x), COORD(y+1)-1, 1, 1,
1742                   (v & ERR_L_B ? COL_ERROR : fscol));
1743     if (v & (T_L | BACKSLASH))
1744         draw_rect(dr, COORD(x)+1, COORD(y), 1, 1,
1745                   (v & ERR_T_L ? COL_ERROR : bscol));
1746     if (v & (T_R | FORWSLASH))
1747         draw_rect(dr, COORD(x+1)-1, COORD(y), 1, 1,
1748                   (v & ERR_T_R ? COL_ERROR : fscol));
1749     if (v & (C_TL | BACKSLASH))
1750         draw_rect(dr, COORD(x), COORD(y), 1, 1,
1751                   (v & ERR_C_TL ? COL_ERROR : bscol));
1752
1753     /*
1754      * And finally the clues at the corners.
1755      */
1756     if (x >= 0 && y >= 0)
1757         draw_clue(dr, ds, x, y, clues->clues[y*W+x], v & ERR_TL, -1, -1);
1758     if (x < w && y >= 0)
1759         draw_clue(dr, ds, x+1, y, clues->clues[y*W+(x+1)], v & ERR_TR, -1, -1);
1760     if (x >= 0 && y < h)
1761         draw_clue(dr, ds, x, y+1, clues->clues[(y+1)*W+x], v & ERR_BL, -1, -1);
1762     if (x < w && y < h)
1763         draw_clue(dr, ds, x+1, y+1, clues->clues[(y+1)*W+(x+1)], v & ERR_BR,
1764                   -1, -1);
1765
1766     unclip(dr);
1767     draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1768 }
1769
1770 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1771                         game_state *state, int dir, game_ui *ui,
1772                         float animtime, float flashtime)
1773 {
1774     int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1775     int x, y;
1776     int flashing;
1777
1778     if (flashtime > 0)
1779         flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
1780     else
1781         flashing = FALSE;
1782
1783     if (!ds->started) {
1784         int ww, wh;
1785         game_compute_size(&state->p, TILESIZE, &ww, &wh);
1786         draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
1787         draw_update(dr, 0, 0, ww, wh);
1788         ds->started = TRUE;
1789     }
1790
1791     /*
1792      * Loop over the grid and work out where all the slashes are.
1793      * We need to do this because a slash in one square affects the
1794      * drawing of the next one along.
1795      */
1796     for (y = -1; y <= h; y++)
1797         for (x = -1; x <= w; x++) {
1798             if (x >= 0 && x < w && y >= 0 && y < h)
1799                 ds->todraw[(y+1)*(w+2)+(x+1)] = flashing ? FLASH : 0;
1800             else
1801                 ds->todraw[(y+1)*(w+2)+(x+1)] = 0;
1802         }
1803
1804     for (y = 0; y < h; y++) {
1805         for (x = 0; x < w; x++) {
1806             int err = state->errors[y*W+x] & ERR_SQUARE;
1807
1808             if (state->soln[y*w+x] < 0) {
1809                 ds->todraw[(y+1)*(w+2)+(x+1)] |= BACKSLASH;
1810                 ds->todraw[(y+2)*(w+2)+(x+1)] |= T_R;
1811                 ds->todraw[(y+1)*(w+2)+(x+2)] |= L_B;
1812                 ds->todraw[(y+2)*(w+2)+(x+2)] |= C_TL;
1813                 if (err) {
1814                     ds->todraw[(y+1)*(w+2)+(x+1)] |= ERRSLASH |
1815                         ERR_T_L | ERR_L_T | ERR_C_TL;
1816                     ds->todraw[(y+2)*(w+2)+(x+1)] |= ERR_T_R;
1817                     ds->todraw[(y+1)*(w+2)+(x+2)] |= ERR_L_B;
1818                     ds->todraw[(y+2)*(w+2)+(x+2)] |= ERR_C_TL;
1819                 }
1820             } else if (state->soln[y*w+x] > 0) {
1821                 ds->todraw[(y+1)*(w+2)+(x+1)] |= FORWSLASH;
1822                 ds->todraw[(y+1)*(w+2)+(x+2)] |= L_T | C_TL;
1823                 ds->todraw[(y+2)*(w+2)+(x+1)] |= T_L | C_TL;
1824                 if (err) {
1825                     ds->todraw[(y+1)*(w+2)+(x+1)] |= ERRSLASH |
1826                         ERR_L_B | ERR_T_R;
1827                     ds->todraw[(y+1)*(w+2)+(x+2)] |= ERR_L_T | ERR_C_TL;
1828                     ds->todraw[(y+2)*(w+2)+(x+1)] |= ERR_T_L | ERR_C_TL;
1829                 }
1830             }
1831         }
1832     }
1833
1834     for (y = 0; y < H; y++)
1835         for (x = 0; x < W; x++)
1836             if (state->errors[y*W+x] & ERR_VERTEX) {
1837                 ds->todraw[y*(w+2)+x] |= ERR_BR;
1838                 ds->todraw[y*(w+2)+(x+1)] |= ERR_BL;
1839                 ds->todraw[(y+1)*(w+2)+x] |= ERR_TR;
1840                 ds->todraw[(y+1)*(w+2)+(x+1)] |= ERR_TL;
1841             }
1842
1843     /*
1844      * Now go through and draw the grid squares.
1845      */
1846     for (y = -1; y <= h; y++) {
1847         for (x = -1; x <= w; x++) {
1848             if (ds->todraw[(y+1)*(w+2)+(x+1)] != ds->grid[(y+1)*(w+2)+(x+1)]) {
1849                 draw_tile(dr, ds, state->clues, x, y,
1850                           ds->todraw[(y+1)*(w+2)+(x+1)]);
1851                 ds->grid[(y+1)*(w+2)+(x+1)] = ds->todraw[(y+1)*(w+2)+(x+1)];
1852             }
1853         }
1854     }
1855 }
1856
1857 static float game_anim_length(game_state *oldstate, game_state *newstate,
1858                               int dir, game_ui *ui)
1859 {
1860     return 0.0F;
1861 }
1862
1863 static float game_flash_length(game_state *oldstate, game_state *newstate,
1864                                int dir, game_ui *ui)
1865 {
1866     if (!oldstate->completed && newstate->completed &&
1867         !oldstate->used_solve && !newstate->used_solve)
1868         return FLASH_TIME;
1869
1870     return 0.0F;
1871 }
1872
1873 static int game_wants_statusbar(void)
1874 {
1875     return FALSE;
1876 }
1877
1878 static int game_timing_state(game_state *state, game_ui *ui)
1879 {
1880     return TRUE;
1881 }
1882
1883 static void game_print_size(game_params *params, float *x, float *y)
1884 {
1885     int pw, ph;
1886
1887     /*
1888      * I'll use 6mm squares by default.
1889      */
1890     game_compute_size(params, 600, &pw, &ph);
1891     *x = pw / 100.0;
1892     *y = ph / 100.0;
1893 }
1894
1895 static void game_print(drawing *dr, game_state *state, int tilesize)
1896 {
1897     int w = state->p.w, h = state->p.h, W = w+1;
1898     int ink = print_mono_colour(dr, 0);
1899     int paper = print_mono_colour(dr, 1);
1900     int x, y;
1901
1902     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1903     game_drawstate ads, *ds = &ads;
1904     ads.tilesize = tilesize;
1905
1906     /*
1907      * Border.
1908      */
1909     print_line_width(dr, TILESIZE / 16);
1910     draw_rect_outline(dr, COORD(0), COORD(0), w*TILESIZE, h*TILESIZE, ink);
1911
1912     /*
1913      * Grid.
1914      */
1915     print_line_width(dr, TILESIZE / 24);
1916     for (x = 1; x < w; x++)
1917         draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink);
1918     for (y = 1; y < h; y++)
1919         draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink);
1920
1921     /*
1922      * Solution.
1923      */
1924     print_line_width(dr, TILESIZE / 12);
1925     for (y = 0; y < h; y++)
1926         for (x = 0; x < w; x++)
1927             if (state->soln[y*w+x]) {
1928                 int ly, ry;
1929                 /*
1930                  * To prevent nasty line-ending artefacts at
1931                  * corners, I'll do something slightly cunning
1932                  * here.
1933                  */
1934                 clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1935                 if (state->soln[y*w+x] < 0)
1936                     ly = y-1, ry = y+2;
1937                 else
1938                     ry = y-1, ly = y+2;
1939                 draw_line(dr, COORD(x-1), COORD(ly), COORD(x+2), COORD(ry),
1940                           ink);
1941                 unclip(dr);
1942             }
1943
1944     /*
1945      * Clues.
1946      */
1947     print_line_width(dr, TILESIZE / 24);
1948     for (y = 0; y <= h; y++)
1949         for (x = 0; x <= w; x++)
1950             draw_clue(dr, ds, x, y, state->clues->clues[y*W+x],
1951                       FALSE, paper, ink);
1952 }
1953
1954 #ifdef COMBINED
1955 #define thegame slant
1956 #endif
1957
1958 const struct game thegame = {
1959     "Slant", "games.slant",
1960     default_params,
1961     game_fetch_preset,
1962     decode_params,
1963     encode_params,
1964     free_params,
1965     dup_params,
1966     TRUE, game_configure, custom_params,
1967     validate_params,
1968     new_game_desc,
1969     validate_desc,
1970     new_game,
1971     dup_game,
1972     free_game,
1973     TRUE, solve_game,
1974     TRUE, game_text_format,
1975     new_ui,
1976     free_ui,
1977     encode_ui,
1978     decode_ui,
1979     game_changed_state,
1980     interpret_move,
1981     execute_move,
1982     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1983     game_colours,
1984     game_new_drawstate,
1985     game_free_drawstate,
1986     game_redraw,
1987     game_anim_length,
1988     game_flash_length,
1989     TRUE, FALSE, game_print_size, game_print,
1990     game_wants_statusbar,
1991     FALSE, game_timing_state,
1992     0,                                 /* mouse_priorities */
1993 };
1994
1995 #ifdef STANDALONE_SOLVER
1996
1997 #include <stdarg.h>
1998
1999 /*
2000  * gcc -DSTANDALONE_SOLVER -o slantsolver slant.c malloc.c
2001  */
2002
2003 void frontend_default_colour(frontend *fe, float *output) {}
2004 void draw_text(drawing *dr, int x, int y, int fonttype, int fontsize,
2005                int align, int colour, char *text) {}
2006 void draw_rect(drawing *dr, int x, int y, int w, int h, int colour) {}
2007 void draw_rect_outline(drawing *dr, int x, int y, int w, int h, int colour) {}
2008 void draw_line(drawing *dr, int x1, int y1, int x2, int y2, int colour) {}
2009 void draw_polygon(drawing *dr, int *coords, int npoints,
2010                   int fillcolour, int outlinecolour) {}
2011 void draw_circle(drawing *dr, int cx, int cy, int radius,
2012                  int fillcolour, int outlinecolour) {}
2013 void clip(drawing *dr, int x, int y, int w, int h) {}
2014 void unclip(drawing *dr) {}
2015 void start_draw(drawing *dr) {}
2016 void draw_update(drawing *dr, int x, int y, int w, int h) {}
2017 void end_draw(drawing *dr) {}
2018 int print_mono_colour(drawing *dr, int grey) { return 0; }
2019 void print_line_width(drawing *dr, int width) {}
2020 unsigned long random_bits(random_state *state, int bits)
2021 { assert(!"Shouldn't get randomness"); return 0; }
2022 unsigned long random_upto(random_state *state, unsigned long limit)
2023 { assert(!"Shouldn't get randomness"); return 0; }
2024 void shuffle(void *array, int nelts, int eltsize, random_state *rs)
2025 { assert(!"Shouldn't get randomness"); }
2026
2027 void fatal(char *fmt, ...)
2028 {
2029     va_list ap;
2030
2031     fprintf(stderr, "fatal error: ");
2032
2033     va_start(ap, fmt);
2034     vfprintf(stderr, fmt, ap);
2035     va_end(ap);
2036
2037     fprintf(stderr, "\n");
2038     exit(1);
2039 }
2040
2041 int main(int argc, char **argv)
2042 {
2043     game_params *p;
2044     game_state *s;
2045     char *id = NULL, *desc, *err;
2046     int grade = FALSE;
2047     int ret, diff, really_verbose = FALSE;
2048     struct solver_scratch *sc;
2049
2050     while (--argc > 0) {
2051         char *p = *++argv;
2052         if (!strcmp(p, "-v")) {
2053             really_verbose = TRUE;
2054         } else if (!strcmp(p, "-g")) {
2055             grade = TRUE;
2056         } else if (*p == '-') {
2057             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2058             return 1;
2059         } else {
2060             id = p;
2061         }
2062     }
2063
2064     if (!id) {
2065         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2066         return 1;
2067     }
2068
2069     desc = strchr(id, ':');
2070     if (!desc) {
2071         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2072         return 1;
2073     }
2074     *desc++ = '\0';
2075
2076     p = default_params();
2077     decode_params(p, id);
2078     err = validate_desc(p, desc);
2079     if (err) {
2080         fprintf(stderr, "%s: %s\n", argv[0], err);
2081         return 1;
2082     }
2083     s = new_game(NULL, p, desc);
2084
2085     sc = new_scratch(p->w, p->h);
2086
2087     /*
2088      * When solving an Easy puzzle, we don't want to bother the
2089      * user with Hard-level deductions. For this reason, we grade
2090      * the puzzle internally before doing anything else.
2091      */
2092     ret = -1;                          /* placate optimiser */
2093     for (diff = 0; diff < DIFFCOUNT; diff++) {
2094         ret = slant_solve(p->w, p->h, s->clues->clues,
2095                           s->soln, sc, diff);
2096         if (ret < 2)
2097             break;
2098     }
2099
2100     if (diff == DIFFCOUNT) {
2101         if (grade)
2102             printf("Difficulty rating: harder than Hard, or ambiguous\n");
2103         else
2104             printf("Unable to find a unique solution\n");
2105     } else {
2106         if (grade) {
2107             if (ret == 0)
2108                 printf("Difficulty rating: impossible (no solution exists)\n");
2109             else if (ret == 1)
2110                 printf("Difficulty rating: %s\n", slant_diffnames[diff]);
2111         } else {
2112             verbose = really_verbose;
2113             ret = slant_solve(p->w, p->h, s->clues->clues,
2114                               s->soln, sc, diff);
2115             if (ret == 0)
2116                 printf("Puzzle is inconsistent\n");
2117             else
2118                 fputs(game_text_format(s), stdout);
2119         }
2120     }
2121
2122     return 0;
2123 }
2124
2125 #endif