From f10106138f70a92b276899d0822650cb2ec1adae Mon Sep 17 00:00:00 2001 From: simon Date: Tue, 2 Aug 2005 23:16:46 +0000 Subject: [PATCH] New puzzle: `Slant', picked from the Japanese-language section of nikoli.co.jp (which has quite a few puzzles that they don't seem to have bothered to translate into English). Minor structural change: the disjoint set forest code used in the Net solver has come in handy again, so I've moved it out into its own module dsf.c. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@6155 cda61777-01e9-0310-a592-d414129be87e --- Recipe | 9 +- dsf.c | 28 ++ list.c | 2 + net.c | 23 -- print.py | 56 ++- puzzles.but | 74 +++- puzzles.h | 6 + slant.c | 1251 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 1413 insertions(+), 36 deletions(-) create mode 100644 dsf.c create mode 100644 slant.c diff --git a/Recipe b/Recipe index 92c09a4..55b0213 100644 --- a/Recipe +++ b/Recipe @@ -15,15 +15,16 @@ WINDOWS = windows user32.lib gdi32.lib comctl32.lib comdlg32.lib COMMON = midend misc malloc random version -NET = net tree234 +NET = net tree234 dsf NETSLIDE = netslide tree234 MINES = mines tree234 FLIP = flip tree234 PEGS = pegs tree234 UNTANGLE = untangle tree234 +SLANT = slant dsf ALL = list NET NETSLIDE cube fifteen sixteen rect pattern solo twiddle - + MINES samegame FLIP guess PEGS dominosa UNTANGLE blackbox + + MINES samegame FLIP guess PEGS dominosa UNTANGLE blackbox SLANT net : [X] gtk COMMON NET netslide : [X] gtk COMMON NETSLIDE @@ -42,6 +43,7 @@ pegs : [X] gtk COMMON PEGS dominosa : [X] gtk COMMON dominosa untangle : [X] gtk COMMON UNTANGLE blackbox : [X] gtk COMMON blackbox +slant : [X] gtk COMMON SLANT # Auxiliary command-line programs. solosolver : [U] solo[STANDALONE_SOLVER] malloc @@ -71,6 +73,7 @@ pegs : [G] WINDOWS COMMON PEGS dominosa : [G] WINDOWS COMMON dominosa untangle : [G] WINDOWS COMMON UNTANGLE blackbox : [G] WINDOWS COMMON blackbox +slant : [G] WINDOWS COMMON SLANT # Mac OS X unified application containing all the puzzles. Puzzles : [MX] osx osx.icns osx-info.plist COMMON ALL @@ -162,7 +165,7 @@ FORCE: install: for i in cube net netslide fifteen sixteen twiddle \ pattern rect solo mines samegame flip guess \ - pegs dominosa untangle blackbox; do \ + pegs dominosa untangle blackbox slant; do \ $(INSTALL_PROGRAM) -m 755 $$i $(DESTDIR)$(gamesdir)/$$i; \ done !end diff --git a/dsf.c b/dsf.c new file mode 100644 index 0000000..353bf1a --- /dev/null +++ b/dsf.c @@ -0,0 +1,28 @@ +/* + * dsf.c: two small functions to handle a disjoint set forest, + * which is a data structure useful in any solver which has to + * worry about avoiding closed loops. + */ + +int dsf_canonify(int *dsf, int val) +{ + int v2 = val; + + while (dsf[val] != val) + val = dsf[val]; + + while (v2 != val) { + int tmp = dsf[v2]; + dsf[v2] = val; + v2 = tmp; + } + + return val; +} + +void dsf_merge(int *dsf, int v1, int v2) +{ + v1 = dsf_canonify(dsf, v1); + v2 = dsf_canonify(dsf, v2); + dsf[v2] = v1; +} diff --git a/list.c b/list.c index 93de9fc..3cb0495 100644 --- a/list.c +++ b/list.c @@ -31,6 +31,7 @@ extern const game pegs; extern const game rect; extern const game samegame; extern const game sixteen; +extern const game slant; extern const game solo; extern const game twiddle; extern const game untangle; @@ -50,6 +51,7 @@ const game *gamelist[] = { &rect, &samegame, &sixteen, + &slant, &solo, &twiddle, &untangle, diff --git a/net.c b/net.c index a788d46..71c2b9d 100644 --- a/net.c +++ b/net.c @@ -382,29 +382,6 @@ static char *validate_params(game_params *params, int full) * avoidance is required. */ -static int dsf_canonify(int *dsf, int val) -{ - int v2 = val; - - while (dsf[val] != val) - val = dsf[val]; - - while (v2 != val) { - int tmp = dsf[v2]; - dsf[v2] = val; - v2 = tmp; - } - - return val; -} - -static void dsf_merge(int *dsf, int v1, int v2) -{ - v1 = dsf_canonify(dsf, v1); - v2 = dsf_canonify(dsf, v2); - dsf[v2] = v1; -} - struct todo { unsigned char *marked; int *buffer; diff --git a/print.py b/print.py index d6b27f5..75a1f91 100755 --- a/print.py +++ b/print.py @@ -365,13 +365,67 @@ def dominosa_format(s): ((x+0.5)*gridpitch, (h-y-0.5)*gridpitch, grid[y*w+x])) return ret.coords, ret.s +def slant_format(s): + # Parse the game ID. + ret = Holder() + ret.s = "" + params, seed = string.split(s, ":") + w, h = map(string.atoi, string.split(params, "x")) + W = w+1 + H = h+1 + grid = [] + while len(seed) > 0: + if seed[0] in string.lowercase: + grid.extend([-1] * (ord(seed[0]) - ord('a') + 1)) + seed = seed[1:] + elif seed[0] in "01234": + grid.append(string.atoi(seed[0])) + seed = seed[1:] + assert W * H == len(grid) + # I'm going to arbitrarily choose to use 7pt text for the + # numbers, and a 14pt grid pitch. + textht = 7 + gridpitch = 14 + radius = textht * 2.0 / 3.0 + # Set up coordinate system. + pw = gridpitch * w + ph = gridpitch * h + ret.coords = (pw/2, pw/2, ph/2, ph/2) + psprint(ret, "%g %g translate" % (-ret.coords[0], -ret.coords[2])) + # Draw round the grid exterior, thickly. + psprint(ret, "newpath 1 setlinewidth") + psprint(ret, "0 0 moveto 0 %g rlineto %g 0 rlineto 0 %g rlineto" % \ + (h * gridpitch, w * gridpitch, -h * gridpitch)) + psprint(ret, "closepath stroke") + # Draw the internal grid lines, _very_ thin (the player will + # need to draw over them visibly). + psprint(ret, "newpath 0.01 setlinewidth") + for x in xrange(1,w): + psprint(ret, "%g 0 moveto 0 %g rlineto" % (x * gridpitch, h * gridpitch)) + for y in xrange(1,h): + psprint(ret, "0 %g moveto %g 0 rlineto" % (y * gridpitch, w * gridpitch)) + psprint(ret, "stroke") + # And draw the numbers. + psprint(ret, "/Helvetica findfont %g scalefont setfont" % textht) + for y in xrange(H): + for x in xrange(W): + n = grid[y*W+x] + if n >= 0: + psprint(ret, "newpath %g %g %g 0 360 arc" % \ + ((x)*gridpitch, (h-y)*gridpitch, radius), + "gsave 1 setgray fill grestore stroke") + psprint(ret, "%g %g (%d) ctshow" % \ + ((x)*gridpitch, (h-y)*gridpitch, n)) + return ret.coords, ret.s + formatters = { "net": net_format, "rect": rect_format, "rectangles": rect_format, "pattern": pattern_format, "solo": solo_format, -"dominosa": dominosa_format +"dominosa": dominosa_format, +"slant": slant_format } if len(sys.argv) < 3: diff --git a/puzzles.but b/puzzles.but index 13056d7..2c0fe87 100644 --- a/puzzles.but +++ b/puzzles.but @@ -20,6 +20,8 @@ \define{by} \u00D7{x} +\define{dash} \u2013{-} + This is a collection of small one-player puzzle games. \copyright This manual is copyright 2004-5 Simon Tatham. All rights @@ -43,9 +45,9 @@ both, and have more recently done a port to Mac OS X as well. When I find (or perhaps invent) further puzzle games that I like, they'll be added to this collection and will immediately be available on both platforms. And if anyone feels like writing any other front -ends - PocketPC, Mac OS pre-10, or whatever it might be - then all -the games in this framework will immediately become available on -another platform as well. +ends \dash PocketPC, Mac OS pre-10, or whatever it might be \dash +then all the games in this framework will immediately become +available on another platform as well. The actual games in this collection were mostly not my invention; they are re-implementations of existing game concepts within my portable @@ -1208,12 +1210,12 @@ time (but always one that is known to have a solution). \cfg{winhelp-topic}{games.dominosa} -A normal set of dominoes - that is, one instance of every (unordered) -pair of numbers from 0 to 6 - has been arranged irregularly into a -rectangle; then the number in each square has been written down and -the dominoes themselves removed. Your task is to reconstruct the -pattern by arranging the set of dominoes to match the provided array -of numbers. +A normal set of dominoes \dash that is, one instance of every +(unordered) pair of numbers from 0 to 6 \dash has been arranged +irregularly into a rectangle; then the number in each square has +been written down and the dominoes themselves removed. Your task is +to reconstruct the pattern by arranging the set of dominoes to match +the provided array of numbers. This puzzle is widely credited to O. S. Adler, and takes part of its name from those initials. @@ -1430,6 +1432,60 @@ using a different number to the original solution is still acceptable, if all the laser inputs and outputs match. +\C{slant} \i{Slant} + +\cfg{winhelp-topic}{games.slant} + +You have a grid of squares. Your aim is to draw a diagonal line +through each square, and choose which way each line slants so that +the following conditions are met: + +\b The diagonal lines never form a loop. + +\b Any point with a circled number has precisely that many lines +meeting at it. (Thus, a 4 is the centre of a cross shape, whereas a +zero is the centre of a diamond shape \dash or rather, a partial +diamond shape, because a zero can never appear in the middle of the +grid because that would immediately cause a loop.) + +Credit for this puzzle goes to \i{Nikoli} \k{nikoli-slant}. + +\B{nikoli-slant} +\W{http://www.nikoli.co.jp/puzzles/39/index.htm}\cw{http://www.nikoli.co.jp/puzzles/39/index.htm} +(in Japanese) + + +\H{slant-controls} \i{Slant controls} + +\IM{Slant controls} controls, for Slant +\IM{Slant controls} keys, for Slant +\IM{Slant controls} shortcuts (keyboard), for Slant + +Left-clicking in a blank square will place a \cw{\\} in it (a line +leaning to the left, i.e. running from the top left of the square to +the bottom right). Right-clicking in a blank square will place a +\cw{/} in it (leaning to the right, running from top right to bottom +left). + +Continuing to click either button will cycle between the three +possible square contents. Thus, if you left-click repeatedly in a +blank square it will change from blank to \cw{\\} to \cw{/} back to +blank, and if you right-click repeatedly the square will change from +blank to \cw{/} to \cw{\\} back to blank. (Therefore, you can play +the game entirely with one button if you need to.) + +(All the actions described in \k{common-actions} are also available.) + +\H{slant-parameters} \I{parameters, for slant}Slant parameters + +These parameters are available from the \q{Custom...} option on the +\q{Type} menu. + +\dt \e{Width}, \e{Height} + +\dd Size of grid in squares. + + \A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2005 Simon Tatham. diff --git a/puzzles.h b/puzzles.h index cf18255..4762c7c 100644 --- a/puzzles.h +++ b/puzzles.h @@ -235,6 +235,12 @@ void draw_rect_outline(frontend *fe, int x, int y, int w, int h, int colour); /* + * dsf.c + */ +int dsf_canonify(int *dsf, int val); +void dsf_merge(int *dsf, int v1, int v2); + +/* * version.c */ extern char ver[]; diff --git a/slant.c b/slant.c new file mode 100644 index 0000000..c562b48 --- /dev/null +++ b/slant.c @@ -0,0 +1,1251 @@ +/* + * slant.c: Puzzle from nikoli.co.jp involving drawing a diagonal + * line through each square of a grid. + */ + +/* + * In this puzzle you have a grid of squares, each of which must + * contain a diagonal line; you also have clue numbers placed at + * _points_ of that grid, which means there's a (w+1) x (h+1) array + * of possible clue positions. + * + * I'm therefore going to adopt a rigid convention throughout this + * source file of using w and h for the dimensions of the grid of + * squares, and W and H for the dimensions of the grid of points. + * Thus, W == w+1 and H == h+1 always. + * + * Clue arrays will be W*H `signed char's, and the clue at each + * point will be a number from 0 to 4, or -1 if there's no clue. + * + * Solution arrays will be W*H `signed char's, and the number at + * each point will be +1 for a forward slash (/), -1 for a + * backslash (\), and 0 for unknown. + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" + +enum { + COL_BACKGROUND, + COL_GRID, + COL_INK, + NCOLOURS +}; + +struct game_params { + int w, h; +}; + +typedef struct game_clues { + int w, h; + signed char *clues; + int *dsf; /* scratch space for completion check */ + int refcount; +} game_clues; + +struct game_state { + struct game_params p; + game_clues *clues; + signed char *soln; + int completed; + int used_solve; /* used to suppress completion flash */ +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = ret->h = 8; + + return ret; +} + +static const struct game_params slant_presets[] = { + {5, 5}, + {8, 8}, + {12, 10}, +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char str[80]; + + if (i < 0 || i >= lenof(slant_presets)) + return FALSE; + + ret = snew(game_params); + *ret = slant_presets[i]; + + sprintf(str, "%dx%d", ret->w, ret->h); + + *name = dupstr(str); + *params = ret; + return TRUE; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *ret, char const *string) +{ + ret->w = ret->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + ret->h = atoi(string); + } +} + +static char *encode_params(game_params *params, int full) +{ + char data[256]; + + sprintf(data, "%dx%d", params->w, params->h); + + return dupstr(data); +} + +static config_item *game_configure(game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(3, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].sval = dupstr(buf); + ret[1].ival = 0; + + ret[2].name = NULL; + ret[2].type = C_END; + ret[2].sval = NULL; + ret[2].ival = 0; + + return ret; +} + +static game_params *custom_params(config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].sval); + ret->h = atoi(cfg[1].sval); + + return ret; +} + +static char *validate_params(game_params *params, int full) +{ + /* + * (At least at the time of writing this comment) The grid + * generator is actually capable of handling even zero grid + * dimensions without crashing. Puzzles with a zero-area grid + * are a bit boring, though, because they're already solved :-) + */ + + if (params->w < 1 || params->h < 1) + return "Width and height must both be at least one"; + + return NULL; +} + +/* + * Utility function used by both the solver and the filled-grid + * generator. + */ + +static void fill_square(int w, int h, int y, int x, int v, + signed char *soln, int *dsf) +{ + int W = w+1 /*, H = h+1 */; + + soln[y*w+x] = v; + + if (v < 0) + dsf_merge(dsf, y*W+x, (y+1)*W+(x+1)); + else + dsf_merge(dsf, y*W+(x+1), (y+1)*W+x); +} + +/* + * Scratch space for solver. + */ +struct solver_scratch { + int *dsf; +}; + +struct solver_scratch *new_scratch(int w, int h) +{ + int W = w+1, H = h+1; + struct solver_scratch *ret = snew(struct solver_scratch); + ret->dsf = snewn(W*H, int); + return ret; +} + +void free_scratch(struct solver_scratch *sc) +{ + sfree(sc->dsf); + sfree(sc); +} + +/* + * Solver. Returns 0 for impossibility, 1 for success, 2 for + * ambiguity or failure to converge. + */ +static int slant_solve(int w, int h, const signed char *clues, + signed char *soln, struct solver_scratch *sc) +{ + int W = w+1, H = h+1; + int x, y, i; + int done_something; + + /* + * Clear the output. + */ + memset(soln, 0, w*h); + + /* + * Establish a disjoint set forest for tracking connectedness + * between grid points. + */ + for (i = 0; i < W*H; i++) + sc->dsf[i] = i; /* initially all distinct */ + + /* + * Repeatedly try to deduce something until we can't. + */ + do { + done_something = FALSE; + + /* + * Any clue point with the number of remaining lines equal + * to zero or to the number of remaining undecided + * neighbouring squares can be filled in completely. + */ + for (y = 0; y < H; y++) + for (x = 0; x < W; x++) { + int nu, nl, v, c; + + if ((c = clues[y*W+x]) < 0) + continue; + + /* + * We have a clue point. Count up the number of + * undecided neighbours, and also the number of + * lines already present. + */ + nu = 0; + nl = c; + if (x > 0 && y > 0 && (v = soln[(y-1)*w+(x-1)]) != +1) + v == 0 ? nu++ : nl--; + if (x > 0 && y < h && (v = soln[y*w+(x-1)]) != -1) + v == 0 ? nu++ : nl--; + if (x < w && y > 0 && (v = soln[(y-1)*w+x]) != -1) + v == 0 ? nu++ : nl--; + if (x < w && y < h && (v = soln[y*w+x]) != +1) + v == 0 ? nu++ : nl--; + + /* + * Check the counts. + */ + if (nl < 0 || nl > nu) { + /* + * No consistent value for this at all! + */ + return 0; /* impossible */ + } + + if (nu > 0 && (nl == 0 || nl == nu)) { +#ifdef SOLVER_DIAGNOSTICS + printf("%s around clue point at %d,%d\n", + nl ? "filling" : "emptying", x, y); +#endif + if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] == 0) + fill_square(w, h, y-1, x-1, (nl ? -1 : +1), soln, + sc->dsf); + if (x > 0 && y < h && soln[y*w+(x-1)] == 0) + fill_square(w, h, y, x-1, (nl ? +1 : -1), soln, + sc->dsf); + if (x < w && y > 0 && soln[(y-1)*w+x] == 0) + fill_square(w, h, y-1, x, (nl ? +1 : -1), soln, + sc->dsf); + if (x < w && y < h && soln[y*w+x] == 0) + fill_square(w, h, y, x, (nl ? -1 : +1), soln, + sc->dsf); + + done_something = TRUE; + } + } + + if (done_something) + continue; + + /* + * Failing that, we now apply the second condition, which + * is that no square may be filled in such a way as to form + * a loop. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int fs, bs; + + if (soln[y*w+x]) + continue; /* got this one already */ + + fs = (dsf_canonify(sc->dsf, y*W+x) == + dsf_canonify(sc->dsf, (y+1)*W+(x+1))); + bs = (dsf_canonify(sc->dsf, (y+1)*W+x) == + dsf_canonify(sc->dsf, y*W+(x+1))); + + if (fs && bs) { + /* + * Loop avoidance leaves no consistent value + * for this at all! + */ + return 0; /* impossible */ + } + + if (fs) { + /* + * Top left and bottom right corners of this + * square are already connected, which means we + * aren't allowed to put a backslash in here. + */ +#ifdef SOLVER_DIAGNOSTICS + printf("placing / in %d,%d by loop avoidance\n", x, y); +#endif + fill_square(w, h, y, x, +1, soln, sc->dsf); + done_something = TRUE; + } else if (bs) { + /* + * Top right and bottom left corners of this + * square are already connected, which means we + * aren't allowed to put a forward slash in + * here. + */ +#ifdef SOLVER_DIAGNOSTICS + printf("placing \\ in %d,%d by loop avoidance\n", x, y); +#endif + fill_square(w, h, y, x, -1, soln, sc->dsf); + done_something = TRUE; + } + } + + } while (done_something); + + /* + * Solver can make no more progress. See if the grid is full. + */ + for (i = 0; i < w*h; i++) + if (!soln[i]) + return 2; /* failed to converge */ + return 1; /* success */ +} + +/* + * Filled-grid generator. + */ +static void slant_generate(int w, int h, signed char *soln, random_state *rs) +{ + int W = w+1, H = h+1; + int x, y, i; + int *dsf, *indices; + + /* + * Clear the output. + */ + memset(soln, 0, w*h); + + /* + * Establish a disjoint set forest for tracking connectedness + * between grid points. + */ + dsf = snewn(W*H, int); + for (i = 0; i < W*H; i++) + dsf[i] = i; /* initially all distinct */ + + /* + * Prepare a list of the squares in the grid, and fill them in + * in a random order. + */ + indices = snewn(w*h, int); + for (i = 0; i < w*h; i++) + indices[i] = i; + shuffle(indices, w*h, sizeof(*indices), rs); + + /* + * Fill in each one in turn. + */ + for (i = 0; i < w*h; i++) { + int fs, bs, v; + + y = indices[i] / w; + x = indices[i] % w; + + fs = (dsf_canonify(dsf, y*W+x) == + dsf_canonify(dsf, (y+1)*W+(x+1))); + bs = (dsf_canonify(dsf, (y+1)*W+x) == + dsf_canonify(dsf, y*W+(x+1))); + + /* + * It isn't possible to get into a situation where we + * aren't allowed to place _either_ type of slash in a + * square. + * + * Proof (thanks to Gareth Taylor): + * + * If it were possible, it would have to be because there + * was an existing path (not using this square) between the + * top-left and bottom-right corners of this square, and + * another between the other two. These two paths would + * have to cross at some point. + * + * Obviously they can't cross in the middle of a square, so + * they must cross by sharing a point in common. But this + * isn't possible either: if you chessboard-colour all the + * points on the grid, you find that any continuous + * diagonal path is entirely composed of points of the same + * colour. And one of our two hypothetical paths is between + * two black points, and the other is between two white + * points - therefore they can have no point in common. [] + */ + assert(!(fs && bs)); + + v = fs ? +1 : bs ? -1 : 2 * random_upto(rs, 2) - 1; + fill_square(w, h, y, x, v, soln, dsf); + } + + sfree(indices); + sfree(dsf); +} + +static char *new_game_desc(game_params *params, random_state *rs, + char **aux, int interactive) +{ + int w = params->w, h = params->h, W = w+1, H = h+1; + signed char *soln, *tmpsoln, *clues; + int *clueindices; + struct solver_scratch *sc; + int x, y, v, i; + char *desc; + + soln = snewn(w*h, signed char); + tmpsoln = snewn(w*h, signed char); + clues = snewn(W*H, signed char); + clueindices = snewn(W*H, int); + sc = new_scratch(w, h); + + do { + /* + * Create the filled grid. + */ + slant_generate(w, h, soln, rs); + + /* + * Fill in the complete set of clues. + */ + for (y = 0; y < H; y++) + for (x = 0; x < W; x++) { + v = 0; + + if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] == -1) v++; + if (x > 0 && y < h && soln[y*w+(x-1)] == +1) v++; + if (x < w && y > 0 && soln[(y-1)*w+x] == +1) v++; + if (x < w && y < h && soln[y*w+x] == -1) v++; + + clues[y*W+x] = v; + } + } while (slant_solve(w, h, clues, tmpsoln, sc) != 1); + + /* + * Remove as many clues as possible while retaining solubility. + */ + for (i = 0; i < W*H; i++) + clueindices[i] = i; + shuffle(clueindices, W*H, sizeof(*clueindices), rs); + for (i = 0; i < W*H; i++) { + y = clueindices[i] / W; + x = clueindices[i] % W; + v = clues[y*W+x]; + clues[y*W+x] = -1; + if (slant_solve(w, h, clues, tmpsoln, sc) != 1) + clues[y*W+x] = v; /* put it back */ + } + + /* + * Now we have the clue set as it will be presented to the + * user. Encode it in a game desc. + */ + { + char *p; + int run, i; + + desc = snewn(W*H+1, char); + p = desc; + run = 0; + for (i = 0; i <= W*H; i++) { + int n = (i < W*H ? clues[i] : -2); + + if (n == -1) + run++; + else { + if (run) { + while (run > 0) { + int c = 'a' - 1 + run; + if (run > 26) + c = 'z'; + *p++ = c; + run -= c - ('a' - 1); + } + } + if (n >= 0) + *p++ = '0' + n; + run = 0; + } + } + assert(p - desc <= W*H); + *p++ = '\0'; + desc = sresize(desc, p - desc, char); + } + + /* + * Encode the solution as an aux_info. + */ + { + char *auxbuf; + *aux = auxbuf = snewn(w*h+1, char); + for (i = 0; i < w*h; i++) + auxbuf[i] = soln[i] < 0 ? '\\' : '/'; + auxbuf[w*h] = '\0'; + } + + free_scratch(sc); + sfree(clueindices); + sfree(clues); + sfree(tmpsoln); + sfree(soln); + + return desc; +} + +static char *validate_desc(game_params *params, char *desc) +{ + int w = params->w, h = params->h, W = w+1, H = h+1; + int area = W*H; + int squares = 0; + + while (*desc) { + int n = *desc++; + if (n >= 'a' && n <= 'z') { + squares += n - 'a' + 1; + } else if (n >= '0' && n <= '4') { + squares++; + } else + return "Invalid character in game description"; + } + + if (squares < area) + return "Not enough data to fill grid"; + + if (squares > area) + return "Too much data to fit in grid"; + + return NULL; +} + +static game_state *new_game(midend_data *me, game_params *params, char *desc) +{ + int w = params->w, h = params->h, W = w+1, H = h+1; + game_state *state = snew(game_state); + int area = W*H; + int squares = 0; + + state->p = *params; + state->soln = snewn(w*h, signed char); + memset(state->soln, 0, w*h); + state->completed = state->used_solve = FALSE; + + state->clues = snew(game_clues); + state->clues->w = w; + state->clues->h = h; + state->clues->clues = snewn(W*H, signed char); + state->clues->refcount = 1; + state->clues->dsf = snewn(W*H, int); + memset(state->clues->clues, -1, W*H); + while (*desc) { + int n = *desc++; + if (n >= 'a' && n <= 'z') { + squares += n - 'a' + 1; + } else if (n >= '0' && n <= '4') { + state->clues->clues[squares++] = n - '0'; + } else + assert(!"can't get here"); + } + assert(squares == area); + + return state; +} + +static game_state *dup_game(game_state *state) +{ + int w = state->p.w, h = state->p.h; + game_state *ret = snew(game_state); + + ret->p = state->p; + ret->clues = state->clues; + ret->clues->refcount++; + ret->completed = state->completed; + ret->used_solve = state->used_solve; + + ret->soln = snewn(w*h, signed char); + memcpy(ret->soln, state->soln, w*h); + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state); +} + +static int check_completion(game_state *state) +{ + int w = state->p.w, h = state->p.h, W = w+1, H = h+1; + int i, x, y; + + /* + * Establish a disjoint set forest for tracking connectedness + * between grid points. Use the dsf scratch space in the shared + * clues structure, to avoid mallocing too often. + */ + for (i = 0; i < W*H; i++) + state->clues->dsf[i] = i; /* initially all distinct */ + + /* + * Now go through the grid checking connectedness. While we're + * here, also check that everything is filled in. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int i1, i2; + + if (state->soln[y*w+x] == 0) + return FALSE; + if (state->soln[y*w+x] < 0) { + i1 = y*W+x; + i2 = (y+1)*W+(x+1); + } else { + i1 = (y+1)*W+x; + i2 = y*W+(x+1); + } + + /* + * Our edge connects i1 with i2. If they're already + * connected, return failure. Otherwise, link them. + */ + if (dsf_canonify(state->clues->dsf, i1) == + dsf_canonify(state->clues->dsf, i2)) + return FALSE; + else + dsf_merge(state->clues->dsf, i1, i2); + } + + /* + * The grid is _a_ valid grid; let's see if it matches the + * clues. + */ + for (y = 0; y < H; y++) + for (x = 0; x < W; x++) { + int v, c; + + if ((c = state->clues->clues[y*W+x]) < 0) + continue; + + v = 0; + + if (x > 0 && y > 0 && state->soln[(y-1)*w+(x-1)] == -1) v++; + if (x > 0 && y < h && state->soln[y*w+(x-1)] == +1) v++; + if (x < w && y > 0 && state->soln[(y-1)*w+x] == +1) v++; + if (x < w && y < h && state->soln[y*w+x] == -1) v++; + + if (c != v) + return FALSE; + } + + return TRUE; +} + +static char *solve_game(game_state *state, game_state *currstate, + char *aux, char **error) +{ + int w = state->p.w, h = state->p.h; + signed char *soln; + int bs, ret; + int free_soln = FALSE; + char *move, buf[80]; + int movelen, movesize; + int x, y; + + if (aux) { + /* + * If we already have the solution, save ourselves some + * time. + */ + soln = (signed char *)aux; + bs = (signed char)'\\'; + free_soln = FALSE; + } else { + struct solver_scratch *sc = new_scratch(w, h); + soln = snewn(w*h, signed char); + bs = -1; + ret = slant_solve(w, h, state->clues->clues, soln, sc); + free_scratch(sc); + if (ret != 1) { + sfree(soln); + if (ret == 0) + return "This puzzle is not self-consistent"; + else + return "Unable to find a unique solution for this puzzle"; + } + free_soln = TRUE; + } + + /* + * Construct a move string which turns the current state into + * the solved state. + */ + movesize = 256; + move = snewn(movesize, char); + movelen = 0; + move[movelen++] = 'S'; + move[movelen] = '\0'; + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int v = (soln[y*w+x] == bs ? -1 : +1); + if (state->soln[y*w+x] != v) { + int len = sprintf(buf, ";%c%d,%d", v < 0 ? '\\' : '/', x, y); + if (movelen + len >= movesize) { + movesize = movelen + len + 256; + move = sresize(move, movesize, char); + } + strcpy(move + movelen, buf); + movelen += len; + } + } + + if (free_soln) + sfree(soln); + + return move; +} + +static char *game_text_format(game_state *state) +{ + int w = state->p.w, h = state->p.h, W = w+1, H = h+1; + int x, y, len; + char *ret, *p; + + /* + * There are h+H rows of w+W columns. + */ + len = (h+H) * (w+W+1) + 1; + ret = snewn(len, char); + p = ret; + + for (y = 0; y < H; y++) { + for (x = 0; x < W; x++) { + if (state->clues->clues[y*W+x] >= 0) + *p++ = state->clues->clues[y*W+x] + '0'; + else + *p++ = '+'; + if (x < w) + *p++ = '-'; + } + *p++ = '\n'; + if (y < h) { + for (x = 0; x < W; x++) { + *p++ = '|'; + if (x < w) { + if (state->soln[y*w+x] != 0) + *p++ = (state->soln[y*w+x] < 0 ? '\\' : '/'); + else + *p++ = ' '; + } + } + *p++ = '\n'; + } + } + *p++ = '\0'; + + assert(p - ret == len); + return ret; +} + +static game_ui *new_ui(game_state *state) +{ + return NULL; +} + +static void free_ui(game_ui *ui) +{ +} + +static char *encode_ui(game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, char *encoding) +{ +} + +static void game_changed_state(game_ui *ui, game_state *oldstate, + game_state *newstate) +{ +} + +#define PREFERRED_TILESIZE 32 +#define TILESIZE (ds->tilesize) +#define BORDER TILESIZE +#define CLUE_RADIUS (TILESIZE / 3) +#define CLUE_TEXTSIZE (TILESIZE / 2) +#define COORD(x) ( (x) * TILESIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) + +#define FLASH_TIME 0.30F + +/* + * Bit fields in the `grid' and `todraw' elements of the drawstate. + */ +#define BACKSLASH 0x0001 +#define FORWSLASH 0x0002 +#define L_T 0x0004 +#define L_B 0x0008 +#define T_L 0x0010 +#define T_R 0x0020 +#define R_T 0x0040 +#define R_B 0x0080 +#define B_L 0x0100 +#define B_R 0x0200 +#define C_TL 0x0400 +#define C_TR 0x0800 +#define C_BL 0x1000 +#define C_BR 0x2000 +#define FLASH 0x4000 + +struct game_drawstate { + int tilesize; + int started; + int *grid; + int *todraw; +}; + +static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, + int x, int y, int button) +{ + int w = state->p.w, h = state->p.h; + + if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { + int v; + char buf[80]; + + x = FROMCOORD(x); + y = FROMCOORD(y); + if (x < 0 || y < 0 || x >= w || y >= h) + return NULL; + + if (button == LEFT_BUTTON) { + /* + * Left-clicking cycles blank -> \ -> / -> blank. + */ + v = state->soln[y*w+x] - 1; + if (v == -2) + v = +1; + } else { + /* + * Right-clicking cycles blank -> / -> \ -> blank. + */ + v = state->soln[y*w+x] + 1; + if (v == +2) + v = -1; + } + + sprintf(buf, "%c%d,%d", v==-1 ? '\\' : v==+1 ? '/' : 'C', x, y); + return dupstr(buf); + } + + return NULL; +} + +static game_state *execute_move(game_state *state, char *move) +{ + int w = state->p.w, h = state->p.h; + char c; + int x, y, n; + game_state *ret = dup_game(state); + + while (*move) { + c = *move; + if (c == 'S') { + ret->used_solve = TRUE; + move++; + } else if (c == '\\' || c == '/' || c == 'C') { + move++; + if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || + x < 0 || y < 0 || x >= w || y >= h) { + free_game(ret); + return NULL; + } + ret->soln[y*w+x] = (c == '\\' ? -1 : c == '/' ? +1 : 0); + move += n; + } else { + free_game(ret); + return NULL; + } + if (*move == ';') + move++; + else if (*move) { + free_game(ret); + return NULL; + } + } + + if (!ret->completed) + ret->completed = check_completion(ret); + + return ret; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_compute_size(game_params *params, int tilesize, + int *x, int *y) +{ + /* fool the macros */ + struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy; + + *x = 2 * BORDER + params->w * TILESIZE + 1; + *y = 2 * BORDER + params->h * TILESIZE + 1; +} + +static void game_set_size(game_drawstate *ds, game_params *params, + int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, game_state *state, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.7F; + ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.7F; + ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.7F; + + ret[COL_INK * 3 + 0] = 0.0F; + ret[COL_INK * 3 + 1] = 0.0F; + ret[COL_INK * 3 + 2] = 0.0F; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(game_state *state) +{ + int w = state->p.w, h = state->p.h; + int i; + struct game_drawstate *ds = snew(struct game_drawstate); + + ds->tilesize = 0; + ds->started = FALSE; + ds->grid = snewn(w*h, int); + ds->todraw = snewn(w*h, int); + for (i = 0; i < w*h; i++) + ds->grid[i] = ds->todraw[i] = -1; + + return ds; +} + +static void game_free_drawstate(game_drawstate *ds) +{ + sfree(ds->grid); + sfree(ds); +} + +static void draw_clue(frontend *fe, game_drawstate *ds, + int x, int y, int v) +{ + char p[2]; + + if (v < 0) + return; + + p[0] = v + '0'; + p[1] = '\0'; + draw_circle(fe, COORD(x), COORD(y), CLUE_RADIUS, + COL_BACKGROUND, COL_INK); + draw_text(fe, COORD(x), COORD(y), FONT_VARIABLE, + CLUE_TEXTSIZE, ALIGN_VCENTRE|ALIGN_HCENTRE, + COL_INK, p); +} + +static void draw_tile(frontend *fe, game_drawstate *ds, game_clues *clues, + int x, int y, int v) +{ + int w = clues->w /*, h = clues->h*/, W = w+1 /*, H = h+1 */; + int xx, yy; + + clip(fe, COORD(x), COORD(y), TILESIZE+1, TILESIZE+1); + + draw_rect(fe, COORD(x), COORD(y), TILESIZE, TILESIZE, + (v & FLASH) ? COL_GRID : COL_BACKGROUND); + + /* + * Draw the grid lines. + */ + draw_line(fe, COORD(x), COORD(y), COORD(x+1), COORD(y), COL_GRID); + draw_line(fe, COORD(x), COORD(y+1), COORD(x+1), COORD(y+1), COL_GRID); + draw_line(fe, COORD(x), COORD(y), COORD(x), COORD(y+1), COL_GRID); + draw_line(fe, COORD(x+1), COORD(y), COORD(x+1), COORD(y+1), COL_GRID); + + /* + * Draw the slash. + */ + if (v & BACKSLASH) { + draw_line(fe, COORD(x), COORD(y), COORD(x+1), COORD(y+1), COL_INK); + draw_line(fe, COORD(x)+1, COORD(y), COORD(x+1), COORD(y+1)-1, + COL_INK); + draw_line(fe, COORD(x), COORD(y)+1, COORD(x+1)-1, COORD(y+1), + COL_INK); + } else if (v & FORWSLASH) { + draw_line(fe, COORD(x+1), COORD(y), COORD(x), COORD(y+1), COL_INK); + draw_line(fe, COORD(x+1)-1, COORD(y), COORD(x), COORD(y+1)-1, + COL_INK); + draw_line(fe, COORD(x+1), COORD(y)+1, COORD(x)+1, COORD(y+1), + COL_INK); + } + + /* + * Draw dots on the grid corners that appear if a slash is in a + * neighbouring cell. + */ + if (v & L_T) + draw_rect(fe, COORD(x), COORD(y)+1, 1, 1, COL_INK); + if (v & L_B) + draw_rect(fe, COORD(x), COORD(y+1)-1, 1, 1, COL_INK); + if (v & R_T) + draw_rect(fe, COORD(x+1), COORD(y)+1, 1, 1, COL_INK); + if (v & R_B) + draw_rect(fe, COORD(x+1), COORD(y+1)-1, 1, 1, COL_INK); + if (v & T_L) + draw_rect(fe, COORD(x)+1, COORD(y), 1, 1, COL_INK); + if (v & T_R) + draw_rect(fe, COORD(x+1)-1, COORD(y), 1, 1, COL_INK); + if (v & B_L) + draw_rect(fe, COORD(x)+1, COORD(y+1), 1, 1, COL_INK); + if (v & B_R) + draw_rect(fe, COORD(x+1)-1, COORD(y+1), 1, 1, COL_INK); + if (v & C_TL) + draw_rect(fe, COORD(x), COORD(y), 1, 1, COL_INK); + if (v & C_TR) + draw_rect(fe, COORD(x+1), COORD(y), 1, 1, COL_INK); + if (v & C_BL) + draw_rect(fe, COORD(x), COORD(y+1), 1, 1, COL_INK); + if (v & C_BR) + draw_rect(fe, COORD(x+1), COORD(y+1), 1, 1, COL_INK); + + /* + * And finally the clues at the corners. + */ + for (xx = x; xx <= x+1; xx++) + for (yy = y; yy <= y+1; yy++) + draw_clue(fe, ds, xx, yy, clues->clues[yy*W+xx]); + + unclip(fe); + draw_update(fe, COORD(x), COORD(y), TILESIZE+1, TILESIZE+1); +} + +static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, + game_state *state, int dir, game_ui *ui, + float animtime, float flashtime) +{ + int w = state->p.w, h = state->p.h, W = w+1 /*, H = h+1 */; + int x, y; + int flashing; + + if (flashtime > 0) + flashing = (int)(flashtime * 3 / FLASH_TIME) != 1; + else + flashing = FALSE; + + if (!ds->started) { + int ww, wh; + game_compute_size(&state->p, TILESIZE, &ww, &wh); + draw_rect(fe, 0, 0, ww, wh, COL_BACKGROUND); + draw_update(fe, 0, 0, ww, wh); + + /* + * Draw any clues on the very edges (since normal tile + * redraw won't draw the bits outside the grid boundary). + */ + for (y = 0; y < h; y++) { + draw_clue(fe, ds, 0, y, state->clues->clues[y*W+0]); + draw_clue(fe, ds, w, y, state->clues->clues[y*W+w]); + } + for (x = 0; x < w; x++) { + draw_clue(fe, ds, x, 0, state->clues->clues[0*W+x]); + draw_clue(fe, ds, x, h, state->clues->clues[h*W+x]); + } + + ds->started = TRUE; + } + + /* + * Loop over the grid and work out where all the slashes are. + * We need to do this because a slash in one square affects the + * drawing of the next one along. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + ds->todraw[y*w+x] = flashing ? FLASH : 0; + + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (state->soln[y*w+x] < 0) { + ds->todraw[y*w+x] |= BACKSLASH; + if (x > 0) + ds->todraw[y*w+(x-1)] |= R_T | C_TR; + if (x+1 < w) + ds->todraw[y*w+(x+1)] |= L_B | C_BL; + if (y > 0) + ds->todraw[(y-1)*w+x] |= B_L | C_BL; + if (y+1 < h) + ds->todraw[(y+1)*w+x] |= T_R | C_TR; + if (x > 0 && y > 0) + ds->todraw[(y-1)*w+(x-1)] |= C_BR; + if (x+1 < w && y+1 < h) + ds->todraw[(y+1)*w+(x+1)] |= C_TL; + } else if (state->soln[y*w+x] > 0) { + ds->todraw[y*w+x] |= FORWSLASH; + if (x > 0) + ds->todraw[y*w+(x-1)] |= R_B | C_BR; + if (x+1 < w) + ds->todraw[y*w+(x+1)] |= L_T | C_TL; + if (y > 0) + ds->todraw[(y-1)*w+x] |= B_R | C_BR; + if (y+1 < h) + ds->todraw[(y+1)*w+x] |= T_L | C_TL; + if (x > 0 && y+1 < h) + ds->todraw[(y+1)*w+(x-1)] |= C_TR; + if (x+1 < w && y > 0) + ds->todraw[(y-1)*w+(x+1)] |= C_BL; + } + } + } + + /* + * Now go through and draw the grid squares. + */ + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (ds->todraw[y*w+x] != ds->grid[y*w+x]) { + draw_tile(fe, ds, state->clues, x, y, ds->todraw[y*w+x]); + ds->grid[y*w+x] = ds->todraw[y*w+x]; + } + } + } +} + +static float game_anim_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + if (!oldstate->completed && newstate->completed && + !oldstate->used_solve && !newstate->used_solve) + return FLASH_TIME; + + return 0.0F; +} + +static int game_wants_statusbar(void) +{ + return FALSE; +} + +static int game_timing_state(game_state *state, game_ui *ui) +{ + return TRUE; +} + +#ifdef COMBINED +#define thegame slant +#endif + +const struct game thegame = { + "Slant", "games.slant", + default_params, + game_fetch_preset, + decode_params, + encode_params, + free_params, + dup_params, + TRUE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + TRUE, solve_game, + TRUE, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + PREFERRED_TILESIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_wants_statusbar, + FALSE, game_timing_state, + 0, /* mouse_priorities */ +}; -- 2.11.0