From ee67eb171acde7124b49eddb6515834c6a0f60b9 Mon Sep 17 00:00:00 2001 From: simon Date: Thu, 7 Jan 2010 18:42:00 +0000 Subject: [PATCH] New puzzle, again using the revised latin.c: 'Towers', a clone of a latin-square puzzle which I've seen described by several names but the most common is 'Skyscrapers'. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@8816 cda61777-01e9-0310-a592-d414129be87e --- icons/Makefile | 3 +- icons/towers.sav | 26 + puzzles.but | 90 +++ towers.R | 25 + towers.c | 1929 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 2072 insertions(+), 1 deletion(-) create mode 100644 icons/towers.sav create mode 100644 towers.R create mode 100644 towers.c diff --git a/icons/Makefile b/icons/Makefile index edd8f87..350fd7c 100644 --- a/icons/Makefile +++ b/icons/Makefile @@ -2,7 +2,8 @@ PUZZLES = blackbox bridges cube dominosa fifteen filling flip galaxies guess \ inertia keen lightup loopy map mines net netslide pattern pegs \ - rect samegame sixteen slant solo tents twiddle unequal untangle + rect samegame sixteen slant solo tents towers twiddle unequal \ + untangle BASE = $(patsubst %,%-base.png,$(PUZZLES)) WEB = $(patsubst %,%-web.png,$(PUZZLES)) diff --git a/icons/towers.sav b/icons/towers.sav new file mode 100644 index 0000000..351d473 --- /dev/null +++ b/icons/towers.sav @@ -0,0 +1,26 @@ +SAVEFILE:41:Simon Tatham's Portable Puzzle Collection +VERSION :1:1 +GAME :6:Towers +PARAMS :3:4de +CPARAMS :3:4de +SEED :15:888431554483015 +DESC :31:2/2/1/3/2/2/3/1/3/1/2/2/2/3/2/1 +AUXINFO :34:297d7a2fcf9e14403a74c976fe0fefd306 +NSTATES :2:17 +STATEPOS:2:10 +MOVE :6:R2,0,4 +MOVE :6:R0,1,4 +MOVE :6:R3,3,4 +MOVE :6:R1,2,4 +MOVE :6:R0,3,3 +MOVE :6:R1,0,3 +MOVE :6:R3,2,3 +MOVE :6:R2,1,3 +MOVE :6:R3,0,2 +MOVE :6:R3,1,1 +MOVE :6:R1,1,2 +MOVE :6:R1,3,1 +MOVE :6:R2,3,2 +MOVE :6:R2,2,1 +MOVE :6:R0,2,2 +MOVE :6:R0,0,1 diff --git a/puzzles.but b/puzzles.but index 6343898..4485b81 100644 --- a/puzzles.but +++ b/puzzles.but @@ -2561,6 +2561,96 @@ level, some backtracking will be required, but the solution should still be unique. The remaining levels require increasingly complex reasoning to avoid having to backtrack. + +\C{towers} \i{Towers} + +\cfg{winhelp-topic}{games.towers} + +You have a square grid. On each square of the grid you can build a +tower, with its height ranging from 1 to the size of the grid. +Around the edge of the grid are some numeric clues. + +Your task is to build a tower on every square, in such a way that: + +\b Each row contains every possible height of tower once + +\b Each column contains every possible height of tower once + +\b Each numeric clue describes the number of towers that can be seen +if you look into the square from that direction, assuming that +shorter towers are hidden behind taller ones. For example, in a +5\by.5 grid, a clue marked \q{5} indicates that the five tower +heights must appear in increasing order (otherwise you would not be +able to see all five towers), whereas a clue marked \q{1} indicates +that the tallest tower (the one marked 5) must come first. + +In harder or larger puzzles, some towers will be specified for you +as well as the clues round the edge, and some edge clues may be +missing. + +This puzzle appears on the web under various names, particularly +\q{Skyscrapers}, but I don't know who first invented it. + + +\H{towers-controls} \i{Towers controls} + +\IM{Towers controls} controls, for Towers + +Towers shares much of its control system with Solo, Unequal and Keen. + +To play Towers, simply click the mouse in any empty square and then +type a digit on the keyboard to fill that square with a tower of the +given height. If you make a mistake, click the mouse in the +incorrect square and press Space to clear it again (or use the Undo +feature). + +If you \e{right}-click in a square and then type a number, that +number will be entered in the square as a \q{pencil mark}. You can +have pencil marks for multiple numbers in the same square. A square +containing a tower cannot also contain pencil marks. + +The game pays no attention to pencil marks, so exactly what you use +them for is up to you: you can use them as reminders that a +particular square needs to be re-examined once you know more about a +particular number, or you can use them as lists of the possible +numbers in a given square, or anything else you feel like. + +To erase a single pencil mark, right-click in the square and type +the same number again. + +All pencil marks in a square are erased when you left-click and type +a number, or when you left-click and press space. Right-clicking and +pressing space will also erase pencil marks. + +As for Solo, the cursor keys can be used in conjunction with the +digit keys to set numbers or pencil marks. Use the cursor keys to +move a highlight around the grid, and type a digit to enter it in +the highlighted square. Pressing return toggles the highlight into a +mode in which you can enter or remove pencil marks. + +Pressing M will fill in a full set of pencil marks in every square +that does not have a main digit in it. + +(All the actions described in \k{common-actions} are also available.) + +\H{towers-parameters} \I{parameters, for Towers}Towers parameters + +These parameters are available from the \q{Custom...} option on the +\q{Type} menu. + +\dt \e{Grid size} + +\dd Specifies the size of the grid. Lower limit is 3; upper limit is +9 (because the user interface would become more difficult with +\q{digits} bigger than 9!). + +\dt \e{Difficulty} + +\dd Controls the difficulty of the generated puzzle. At Unreasonable +level, some backtracking will be required, but the solution should +still be unique. The remaining levels require increasingly complex +reasoning to avoid having to backtrack. + \A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2009 Simon Tatham. diff --git a/towers.R b/towers.R new file mode 100644 index 0000000..49632d0 --- /dev/null +++ b/towers.R @@ -0,0 +1,25 @@ +# -*- makefile -*- + +TOWERS_LATIN_EXTRA = tree234 maxflow +TOWERS_EXTRA = latin TOWERS_LATIN_EXTRA + +towers : [X] GTK COMMON towers TOWERS_EXTRA towers-icon|no-icon + +towers : [G] WINDOWS COMMON towers TOWERS_EXTRA towers.res|noicon.res + +towerssolver : [U] towers[STANDALONE_SOLVER] latin[STANDALONE_SOLVER] TOWERS_LATIN_EXTRA STANDALONE +towerssolver : [C] towers[STANDALONE_SOLVER] latin[STANDALONE_SOLVER] TOWERS_LATIN_EXTRA STANDALONE + +ALL += towers[COMBINED] TOWERS_EXTRA + +!begin gtk +GAMES += towers +!end + +!begin >list.c + A(towers) \ +!end + +!begin >wingames.lst +towers.exe:Towers +!end diff --git a/towers.c b/towers.c new file mode 100644 index 0000000..56c69ba --- /dev/null +++ b/towers.c @@ -0,0 +1,1929 @@ +/* + * towers.c: the puzzle also known as 'Skyscrapers'. + * + * Possible future work: + * + * - Relax the upper bound on grid size at 9? + * + I'd need TOCHAR and FROMCHAR macros a bit like group's, to + * be used wherever this code has +'0' or -'0' + * + the pencil marks in the drawstate would need a separate + * word to live in + * + the clues outside the grid would have to cope with being + * multi-digit, meaning in particular that the text formatting + * would become more unpleasant + * + most importantly, though, the solver just isn't fast + * enough. Even at size 9 it can't really do the solver_hard + * factorial-time enumeration at a sensible rate. Easy puzzles + * higher than that would be possible, but more latin-squarey + * than skyscrapery, as it were. + * + * - UI work? + * + Allow the user to mark a clue as 'spent' in some way once + * it's no longer interesting (typically because no + * arrangement of the remaining possibilities _can_ violate + * it)? + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" +#include "latin.h" + +/* + * Difficulty levels. I do some macro ickery here to ensure that my + * enum and the various forms of my name list always match up. + */ +#define DIFFLIST(A) \ + A(EASY,Easy,solver_easy,e) \ + A(HARD,Hard,solver_hard,h) \ + A(EXTREME,Extreme,NULL,x) \ + A(UNREASONABLE,Unreasonable,NULL,u) +#define ENUM(upper,title,func,lower) DIFF_ ## upper, +#define TITLE(upper,title,func,lower) #title, +#define ENCODE(upper,title,func,lower) #lower +#define CONFIG(upper,title,func,lower) ":" #title +enum { DIFFLIST(ENUM) DIFFCOUNT }; +static char const *const towers_diffnames[] = { DIFFLIST(TITLE) }; +static char const towers_diffchars[] = DIFFLIST(ENCODE); +#define DIFFCONFIG DIFFLIST(CONFIG) + +enum { + COL_BACKGROUND, + COL_GRID, + COL_USER, + COL_HIGHLIGHT, + COL_ERROR, + COL_PENCIL, + NCOLOURS +}; + +struct game_params { + int w, diff; +}; + +struct clues { + int refcount; + int w; + /* + * An array of 4w integers, of which: + * - the first w run across the top + * - the next w across the bottom + * - the third w down the left + * - the last w down the right. + */ + int *clues; + + /* + * An array of w*w digits. + */ + digit *immutable; +}; + +/* + * Macros to compute clue indices and coordinates. + */ +#define STARTSTEP(start, step, index, w) do { \ + if (index < w) \ + start = index, step = w; \ + else if (index < 2*w) \ + start = (w-1)*w+(index-w), step = -w; \ + else if (index < 3*w) \ + start = w*(index-2*w), step = 1; \ + else \ + start = w*(index-3*w)+(w-1), step = -1; \ +} while (0) +#define CSTARTSTEP(start, step, index, w) \ + STARTSTEP(start, step, (((index)+2*w)%(4*w)), w) +#define CLUEPOS(x, y, index, w) do { \ + if (index < w) \ + x = index, y = -1; \ + else if (index < 2*w) \ + x = index-w, y = w; \ + else if (index < 3*w) \ + x = -1, y = index-2*w; \ + else \ + x = w, y = index-3*w; \ +} while (0) + +#ifdef STANDALONE_SOLVER +static const char *const cluepos[] = { + "above column", "below column", "left of row", "right of row" +}; +#endif + +struct game_state { + game_params par; + struct clues *clues; + digit *grid; + int *pencil; /* bitmaps using bits 1<<1..1<w = 5; + ret->diff = DIFF_EASY; + + return ret; +} + +const static struct game_params towers_presets[] = { + { 4, DIFF_EASY }, + { 5, DIFF_EASY }, + { 5, DIFF_HARD }, + { 6, DIFF_EASY }, + { 6, DIFF_HARD }, + { 6, DIFF_EXTREME }, + { 6, DIFF_UNREASONABLE }, +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char buf[80]; + + if (i < 0 || i >= lenof(towers_presets)) + return FALSE; + + ret = snew(game_params); + *ret = towers_presets[i]; /* structure copy */ + + sprintf(buf, "%dx%d %s", ret->w, ret->w, towers_diffnames[ret->diff]); + + *name = dupstr(buf); + *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 *params, char const *string) +{ + char const *p = string; + + params->w = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + + if (*p == 'd') { + int i; + p++; + params->diff = DIFFCOUNT+1; /* ...which is invalid */ + if (*p) { + for (i = 0; i < DIFFCOUNT; i++) { + if (*p == towers_diffchars[i]) + params->diff = i; + } + p++; + } + } +} + +static char *encode_params(game_params *params, int full) +{ + char ret[80]; + + sprintf(ret, "%d", params->w); + if (full) + sprintf(ret + strlen(ret), "d%c", towers_diffchars[params->diff]); + + return dupstr(ret); +} + +static config_item *game_configure(game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(3, config_item); + + ret[0].name = "Grid size"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Difficulty"; + ret[1].type = C_CHOICES; + ret[1].sval = DIFFCONFIG; + ret[1].ival = params->diff; + + 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->diff = cfg[1].ival; + + return ret; +} + +static char *validate_params(game_params *params, int full) +{ + if (params->w < 3 || params->w > 9) + return "Grid size must be between 3 and 9"; + if (params->diff >= DIFFCOUNT) + return "Unknown difficulty rating"; + return NULL; +} + +/* ---------------------------------------------------------------------- + * Solver. + */ + +struct solver_ctx { + int w, diff; + int started; + int *clues; + long *iscratch; + int *dscratch; +}; + +static int solver_easy(struct latin_solver *solver, void *vctx) +{ + struct solver_ctx *ctx = (struct solver_ctx *)vctx; + int w = ctx->w; + int c, i, j, n, m, furthest; + int start, step, cstart, cstep, clue, pos, cpos; + int ret = 0; +#ifdef STANDALONE_SOLVER + char prefix[256]; +#endif + + if (!ctx->started) { + ctx->started = TRUE; + /* + * One-off loop to help get started: when a pair of facing + * clues sum to w+1, it must mean that the row consists of + * two increasing sequences back to back, so we can + * immediately place the highest digit by knowing the + * lengths of those two sequences. + */ + for (c = 0; c < 3*w; c = (c == w-1 ? 2*w : c+1)) { + int c2 = c + w; + + if (ctx->clues[c] && ctx->clues[c2] && + ctx->clues[c] + ctx->clues[c2] == w+1) { + STARTSTEP(start, step, c, w); + CSTARTSTEP(cstart, cstep, c, w); + pos = start + (ctx->clues[c]-1)*step; + cpos = cstart + (ctx->clues[c]-1)*cstep; + if (solver->cube[cpos*w+w-1]) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*sfacing clues on %s %d are maximal:\n", + solver_recurse_depth*4, "", + c>=2*w ? "row" : "column", c % w + 1); + printf("%*s placing %d at (%d,%d)\n", + solver_recurse_depth*4, "", + w, pos%w+1, pos/w+1); + } +#endif + latin_solver_place(solver, pos%w, pos/w, w); + ret = 1; + } else { + ret = -1; + } + } + } + + if (ret) + return ret; + } + + /* + * Go over every clue doing reasonably simple heuristic + * deductions. + */ + for (c = 0; c < 4*w; c++) { + clue = ctx->clues[c]; + if (!clue) + continue; + STARTSTEP(start, step, c, w); + CSTARTSTEP(cstart, cstep, c, w); + + /* Find the location of each number in the row. */ + for (i = 0; i < w; i++) + ctx->dscratch[i] = w; + for (i = 0; i < w; i++) + if (solver->grid[start+i*step]) + ctx->dscratch[solver->grid[start+i*step]-1] = i; + + n = m = 0; + furthest = w; + for (i = w; i >= 1; i--) { + if (ctx->dscratch[i-1] == w) { + break; + } else if (ctx->dscratch[i-1] < furthest) { + furthest = ctx->dscratch[i-1]; + m = i; + n++; + } + } + if (clue == n+1 && furthest > 1) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + sprintf(prefix, "%*sclue %s %d is nearly filled:\n", + solver_recurse_depth*4, "", + cluepos[c/w], c%w+1); + else + prefix[0] = '\0'; /* placate optimiser */ +#endif + /* + * We can already see an increasing sequence of the very + * highest numbers, of length one less than that + * specified in the clue. All of those numbers _must_ be + * part of the clue sequence, so the number right next + * to the clue must be the final one - i.e. it must be + * bigger than any of the numbers between it and m. This + * allows us to rule out small numbers in that square. + * + * (This is a generalisation of the obvious deduction + * that when you see a clue saying 1, it must be right + * next to the largest possible number; and similarly, + * when you see a clue saying 2 opposite that, it must + * be right next to the second-largest.) + */ + j = furthest-1; /* number of small numbers we can rule out */ + for (i = 1; i <= w && j > 0; i++) { + if (ctx->dscratch[i-1] < w && ctx->dscratch[i-1] >= furthest) + continue; /* skip this number, it's elsewhere */ + j--; + if (solver->cube[cstart*w+i-1]) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%s%*s ruling out %d at (%d,%d)\n", + prefix, solver_recurse_depth*4, "", + i, start%w+1, start/w+1); + prefix[0] = '\0'; + } +#endif + solver->cube[cstart*w+i-1] = 0; + ret = 1; + } + } + } + + if (ret) + return ret; + +#ifdef STANDALONE_SOLVER + if (solver_show_working) + sprintf(prefix, "%*slower bounds for clue %s %d:\n", + solver_recurse_depth*4, "", + cluepos[c/w], c%w+1); + else + prefix[0] = '\0'; /* placate optimiser */ +#endif + + i = 0; + for (n = w; n > 0; n--) { + /* + * The largest number cannot occur in the first (clue-1) + * squares of the row, or else there wouldn't be space + * for a sufficiently long increasing sequence which it + * terminated. The second-largest number (not counting + * any that are known to be on the far side of a larger + * number and hence excluded from this sequence) cannot + * occur in the first (clue-2) squares, similarly, and + * so on. + */ + + if (ctx->dscratch[n-1] < w) { + for (m = n+1; m < w; m++) + if (ctx->dscratch[m] < ctx->dscratch[n-1]) + break; + if (m < w) + continue; /* this number doesn't count */ + } + + for (j = 0; j < clue - i - 1; j++) + if (solver->cube[(cstart + j*cstep)*w+n-1]) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + int pos = start+j*step; + printf("%s%*s ruling out %d at (%d,%d)\n", + prefix, solver_recurse_depth*4, "", + n, pos%w+1, pos/w+1); + prefix[0] = '\0'; + } +#endif + solver->cube[(cstart + j*cstep)*w+n-1] = 0; + ret = 1; + } + i++; + } + } + + if (ret) + return ret; + + return 0; +} + +static int solver_hard(struct latin_solver *solver, void *vctx) +{ + struct solver_ctx *ctx = (struct solver_ctx *)vctx; + int w = ctx->w; + int c, i, j, n, best, clue, start, step, ret; + long bitmap; +#ifdef STANDALONE_SOLVER + char prefix[256]; +#endif + + /* + * Go over every clue analysing all possibilities. + */ + for (c = 0; c < 4*w; c++) { + clue = ctx->clues[c]; + if (!clue) + continue; + CSTARTSTEP(start, step, c, w); + + for (i = 0; i < w; i++) + ctx->iscratch[i] = 0; + + /* + * Instead of a tedious physical recursion, I iterate in the + * scratch array through all possibilities. At any given + * moment, i indexes the element of the box that will next + * be incremented. + */ + i = 0; + ctx->dscratch[i] = 0; + best = n = 0; + bitmap = 0; + + while (1) { + if (i < w) { + /* + * Find the next valid value for cell i. + */ + int limit = (n == clue ? best : w); + int pos = start + step * i; + for (j = ctx->dscratch[i] + 1; j <= limit; j++) { + if (bitmap & (1L << j)) + continue; /* used this one already */ + if (!solver->cube[pos*w+j-1]) + continue; /* ruled out already */ + + /* Found one. */ + break; + } + + if (j > limit) { + /* No valid values left; drop back. */ + i--; + if (i < 0) + break; /* overall iteration is finished */ + bitmap &= ~(1L << ctx->dscratch[i]); + if (ctx->dscratch[i] == best) { + n--; + best = 0; + for (j = 0; j < i; j++) + if (best < ctx->dscratch[j]) + best = ctx->dscratch[j]; + } + } else { + /* Got a valid value; store it and move on. */ + bitmap |= 1L << j; + ctx->dscratch[i++] = j; + if (j > best) { + best = j; + n++; + } + ctx->dscratch[i] = 0; + } + } else { + if (n == clue) { + for (j = 0; j < w; j++) + ctx->iscratch[j] |= 1L << ctx->dscratch[j]; + } + i--; + bitmap &= ~(1L << ctx->dscratch[i]); + if (ctx->dscratch[i] == best) { + n--; + best = 0; + for (j = 0; j < i; j++) + if (best < ctx->dscratch[j]) + best = ctx->dscratch[j]; + } + } + } + +#ifdef STANDALONE_SOLVER + if (solver_show_working) + sprintf(prefix, "%*sexhaustive analysis of clue %s %d:\n", + solver_recurse_depth*4, "", + cluepos[c/w], c%w+1); + else + prefix[0] = '\0'; /* placate optimiser */ +#endif + + ret = 0; + + for (i = 0; i < w; i++) { + int pos = start + step * i; + for (j = 1; j <= w; j++) { + if (solver->cube[pos*w+j-1] && + !(ctx->iscratch[i] & (1L << j))) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%s%*s ruling out %d at (%d,%d)\n", + prefix, solver_recurse_depth*4, "", + j, pos/w+1, pos%w+1); + prefix[0] = '\0'; + } +#endif + solver->cube[pos*w+j-1] = 0; + ret = 1; + } + } + + /* + * Once we find one clue we can do something with in + * this way, revert to trying easier deductions, so as + * not to generate solver diagnostics that make the + * problem look harder than it is. + */ + if (ret) + return ret; + } + } + + return 0; +} + +#define SOLVER(upper,title,func,lower) func, +static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) }; + +static int solver(int w, int *clues, digit *soln, int maxdiff) +{ + int ret; + struct solver_ctx ctx; + + ctx.w = w; + ctx.diff = maxdiff; + ctx.clues = clues; + ctx.started = FALSE; + ctx.iscratch = snewn(w, long); + ctx.dscratch = snewn(w+1, int); + + ret = latin_solver(soln, w, maxdiff, + DIFF_EASY, DIFF_HARD, DIFF_EXTREME, + DIFF_EXTREME, DIFF_UNREASONABLE, + towers_solvers, &ctx, NULL, NULL); + + sfree(ctx.iscratch); + sfree(ctx.dscratch); + + return ret; +} + +/* ---------------------------------------------------------------------- + * Grid generation. + */ + +static char *new_game_desc(game_params *params, random_state *rs, + char **aux, int interactive) +{ + int w = params->w, a = w*w; + digit *grid, *soln, *soln2; + int *clues, *order; + int i, ret; + int diff = params->diff; + char *desc, *p; + + /* + * Difficulty exceptions: some combinations of size and + * difficulty cannot be satisfied, because all puzzles of at + * most that difficulty are actually even easier. + * + * Remember to re-test this whenever a change is made to the + * solver logic! + * + * I tested it using the following shell command: + +for d in e h x u; do + for i in {3..9}; do + echo -n "./towers --generate 1 ${i}d${d}: " + perl -e 'alarm 30; exec @ARGV' ./towers --generate 1 ${i}d${d} >/dev/null \ + && echo ok + done +done + + * Of course, it's better to do that after taking the exceptions + * _out_, so as to detect exceptions that should be removed as + * well as those which should be added. + */ + if (diff > DIFF_HARD && w <= 3) + diff = DIFF_HARD; + + grid = NULL; + clues = snewn(4*w, int); + soln = snewn(a, digit); + soln2 = snewn(a, digit); + order = snewn(max(4*w,a), int); + + while (1) { + /* + * Construct a latin square to be the solution. + */ + sfree(grid); + grid = latin_generate(w, rs); + + /* + * Fill in the clues. + */ + for (i = 0; i < 4*w; i++) { + int start, step, j, k, best; + STARTSTEP(start, step, i, w); + k = best = 0; + for (j = 0; j < w; j++) { + if (grid[start+j*step] > best) { + best = grid[start+j*step]; + k++; + } + } + clues[i] = k; + } + + /* + * Remove the grid numbers and then the clues, one by one, + * for as long as the game remains soluble at the given + * difficulty. + */ + memcpy(soln, grid, a); + + if (diff == DIFF_EASY && w <= 5) { + /* + * Special case: for Easy-mode grids that are small + * enough, it's nice to be able to find completely empty + * grids. + */ + memset(soln2, 0, a); + ret = solver(w, clues, soln2, diff); + if (ret > diff) + continue; + } + + for (i = 0; i < a; i++) + order[i] = i; + shuffle(order, a, sizeof(*order), rs); + for (i = 0; i < a; i++) { + int j = order[i]; + + memcpy(soln2, grid, a); + soln2[j] = 0; + ret = solver(w, clues, soln2, diff); + if (ret <= diff) + grid[j] = 0; + } + + if (diff > DIFF_EASY) { /* leave all clues on Easy mode */ + for (i = 0; i < 4*w; i++) + order[i] = i; + shuffle(order, 4*w, sizeof(*order), rs); + for (i = 0; i < 4*w; i++) { + int j = order[i]; + int clue = clues[j]; + + memcpy(soln2, grid, a); + clues[j] = 0; + ret = solver(w, clues, soln2, diff); + if (ret > diff) + clues[j] = clue; + } + } + + /* + * See if the game can be solved at the specified difficulty + * level, but not at the one below. + */ + memcpy(soln2, grid, a); + ret = solver(w, clues, soln2, diff); + if (ret != diff) + continue; /* go round again */ + + /* + * We've got a usable puzzle! + */ + break; + } + + /* + * Encode the puzzle description. + */ + desc = snewn(40*a, char); + p = desc; + for (i = 0; i < 4*w; i++) { + p += sprintf(p, "%s%.0d", i?"/":"", clues[i]); + } + for (i = 0; i < a; i++) + if (grid[i]) + break; + if (i < a) { + int run = 0; + + *p++ = ','; + + for (i = 0; i <= a; i++) { + int n = (i < a ? grid[i] : -1); + + if (!n) + run++; + else { + if (run) { + while (run > 0) { + int thisrun = min(run, 26); + *p++ = thisrun - 1 + 'a'; + run -= thisrun; + } + } else { + /* + * If there's a number in the very top left or + * bottom right, there's no point putting an + * unnecessary _ before or after it. + */ + if (i > 0 && n > 0) + *p++ = '_'; + } + if (n > 0) + p += sprintf(p, "%d", n); + run = 0; + } + } + } + *p++ = '\0'; + desc = sresize(desc, p - desc, char); + + /* + * Encode the solution. + */ + *aux = snewn(a+2, char); + (*aux)[0] = 'S'; + for (i = 0; i < a; i++) + (*aux)[i+1] = '0' + soln[i]; + (*aux)[a+1] = '\0'; + + sfree(grid); + sfree(clues); + sfree(soln); + sfree(soln2); + sfree(order); + + return desc; +} + +/* ---------------------------------------------------------------------- + * Gameplay. + */ + +static char *validate_desc(game_params *params, char *desc) +{ + int w = params->w, a = w*w; + const char *p = desc; + int i, clue; + + /* + * Verify that the right number of clues are given, and that + * they're in range. + */ + for (i = 0; i < 4*w; i++) { + if (!*p) + return "Too few clues for grid size"; + + if (i > 0) { + if (*p != '/') + return "Expected commas between clues"; + p++; + } + + if (isdigit((unsigned char)*p)) { + clue = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + + if (clue <= 0 || clue > w) + return "Clue number out of range"; + } + } + if (*p == '/') + return "Too many clues for grid size"; + + if (*p == ',') { + /* + * Verify that the right amount of grid data is given, and + * that any grid elements provided are in range. + */ + int squares = 0; + + p++; + while (*p) { + int c = *p++; + if (c >= 'a' && c <= 'z') { + squares += c - 'a' + 1; + } else if (c == '_') { + /* do nothing */; + } else if (c > '0' && c <= '9') { + int val = atoi(p-1); + if (val < 1 || val > w) + return "Out-of-range number in grid description"; + squares++; + while (*p && isdigit((unsigned char)*p)) p++; + } else + return "Invalid character in game description"; + } + + if (squares < a) + return "Not enough data to fill grid"; + + if (squares > a) + return "Too much data to fit in grid"; + } + + return NULL; +} + +static game_state *new_game(midend *me, game_params *params, char *desc) +{ + int w = params->w, a = w*w; + game_state *state = snew(game_state); + const char *p = desc; + int i; + + state->par = *params; /* structure copy */ + state->clues = snew(struct clues); + state->clues->refcount = 1; + state->clues->w = w; + state->clues->clues = snewn(4*w, int); + state->clues->immutable = snewn(a, digit); + state->grid = snewn(a, digit); + state->pencil = snewn(a, int); + + for (i = 0; i < a; i++) { + state->grid[i] = 0; + state->pencil[i] = 0; + } + + memset(state->clues->immutable, 0, a); + + for (i = 0; i < 4*w; i++) { + if (i > 0) { + assert(*p == '/'); + p++; + } + if (*p && isdigit((unsigned char)*p)) { + state->clues->clues[i] = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + } else + state->clues->clues[i] = 0; + } + + if (*p == ',') { + int pos = 0; + p++; + while (*p) { + int c = *p++; + if (c >= 'a' && c <= 'z') { + pos += c - 'a' + 1; + } else if (c == '_') { + /* do nothing */; + } else if (c > '0' && c <= '9') { + int val = atoi(p-1); + assert(val >= 1 && val <= w); + assert(pos < a); + state->grid[pos] = state->clues->immutable[pos] = val; + pos++; + while (*p && isdigit((unsigned char)*p)) p++; + } else + assert(!"Corrupt game description"); + } + assert(pos == a); + } + assert(!*p); + + state->completed = state->cheated = FALSE; + + return state; +} + +static game_state *dup_game(game_state *state) +{ + int w = state->par.w, a = w*w; + game_state *ret = snew(game_state); + + ret->par = state->par; /* structure copy */ + + ret->clues = state->clues; + ret->clues->refcount++; + + ret->grid = snewn(a, digit); + ret->pencil = snewn(a, int); + memcpy(ret->grid, state->grid, a*sizeof(digit)); + memcpy(ret->pencil, state->pencil, a*sizeof(int)); + + ret->completed = state->completed; + ret->cheated = state->cheated; + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->grid); + sfree(state->pencil); + if (--state->clues->refcount <= 0) { + sfree(state->clues->immutable); + sfree(state->clues->clues); + sfree(state->clues); + } + sfree(state); +} + +static char *solve_game(game_state *state, game_state *currstate, + char *aux, char **error) +{ + int w = state->par.w, a = w*w; + int i, ret; + digit *soln; + char *out; + + if (aux) + return dupstr(aux); + + soln = snewn(a, digit); + memcpy(soln, state->clues->immutable, a); + + ret = solver(w, state->clues->clues, soln, DIFFCOUNT-1); + + if (ret == diff_impossible) { + *error = "No solution exists for this puzzle"; + out = NULL; + } else if (ret == diff_ambiguous) { + *error = "Multiple solutions exist for this puzzle"; + out = NULL; + } else { + out = snewn(a+2, char); + out[0] = 'S'; + for (i = 0; i < a; i++) + out[i+1] = '0' + soln[i]; + out[a+1] = '\0'; + } + + sfree(soln); + return out; +} + +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + +static char *game_text_format(game_state *state) +{ + int w = state->par.w /* , a = w*w */; + char *ret; + char *p; + int x, y; + int total; + + /* + * We have: + * - a top clue row, consisting of three spaces, then w clue + * digits with spaces between (total 2*w+3 chars including + * newline) + * - a blank line (one newline) + * - w main rows, consisting of a left clue digit, two spaces, + * w grid digits with spaces between, two spaces and a right + * clue digit (total 2*w+6 chars each including newline) + * - a blank line (one newline) + * - a bottom clue row (same as top clue row) + * - terminating NUL. + * + * Total size is therefore 2*(2*w+3) + 2 + w*(2*w+6) + 1 + * = 2w^2+10w+9. + */ + total = 2*w*w + 10*w + 9; + ret = snewn(total, char); + p = ret; + + /* Top clue row. */ + *p++ = ' '; *p++ = ' '; + for (x = 0; x < w; x++) { + *p++ = ' '; + *p++ = (state->clues->clues[x] ? '0' + state->clues->clues[x] : ' '); + } + *p++ = '\n'; + + /* Blank line. */ + *p++ = '\n'; + + /* Main grid. */ + for (y = 0; y < w; y++) { + *p++ = (state->clues->clues[y+2*w] ? '0' + state->clues->clues[y+2*w] : + ' '); + *p++ = ' '; + for (x = 0; x < w; x++) { + *p++ = ' '; + *p++ = (state->grid[y*w+x] ? '0' + state->grid[y*w+x] : ' '); + } + *p++ = ' '; *p++ = ' '; + *p++ = (state->clues->clues[y+3*w] ? '0' + state->clues->clues[y+3*w] : + ' '); + *p++ = '\n'; + } + + /* Blank line. */ + *p++ = '\n'; + + /* Bottom clue row. */ + *p++ = ' '; *p++ = ' '; + for (x = 0; x < w; x++) { + *p++ = ' '; + *p++ = (state->clues->clues[x+w] ? '0' + state->clues->clues[x+w] : + ' '); + } + *p++ = '\n'; + + *p++ = '\0'; + assert(p == ret + total); + + return ret; +} + +struct game_ui { + /* + * These are the coordinates of the currently highlighted + * square on the grid, if hshow = 1. + */ + int hx, hy; + /* + * This indicates whether the current highlight is a + * pencil-mark one or a real one. + */ + int hpencil; + /* + * This indicates whether or not we're showing the highlight + * (used to be hx = hy = -1); important so that when we're + * using the cursor keys it doesn't keep coming back at a + * fixed position. When hshow = 1, pressing a valid number + * or letter key or Space will enter that number or letter in the grid. + */ + int hshow; + /* + * This indicates whether we're using the highlight as a cursor; + * it means that it doesn't vanish on a keypress, and that it is + * allowed on immutable squares. + */ + int hcursor; +}; + +static game_ui *new_ui(game_state *state) +{ + game_ui *ui = snew(game_ui); + + ui->hx = ui->hy = 0; + ui->hpencil = ui->hshow = ui->hcursor = 0; + + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(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) +{ + int w = newstate->par.w; + /* + * We prevent pencil-mode highlighting of a filled square, unless + * we're using the cursor keys. So if the user has just filled in + * a square which we had a pencil-mode highlight in (by Undo, or + * by Redo, or by Solve), then we cancel the highlight. + */ + if (ui->hshow && ui->hpencil && !ui->hcursor && + newstate->grid[ui->hy * w + ui->hx] != 0) { + ui->hshow = 0; + } +} + +#define PREFERRED_TILESIZE 48 +#define TILESIZE (ds->tilesize) +#define BORDER (TILESIZE * 9 / 8) +#define COORD(x) ((x)*TILESIZE + BORDER) +#define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1) + +#define FLASH_TIME 0.4F + +#define DF_PENCIL_SHIFT 16 +#define DF_ERROR 0x8000 +#define DF_HIGHLIGHT 0x4000 +#define DF_HIGHLIGHT_PENCIL 0x2000 +#define DF_IMMUTABLE 0x1000 +#define DF_PLAYAREA 0x0800 +#define DF_DIGIT_MASK 0x00FF + +struct game_drawstate { + int tilesize; + int started; + long *tiles; + int *errtmp; +}; + +static int check_errors(game_state *state, int *errors) +{ + int w = state->par.w /*, a = w*w */; + int W = w+2, A = W*W; /* the errors array is (w+2) square */ + int *clues = state->clues->clues; + digit *grid = state->grid; + int i, x, y, errs = FALSE; + int tmp[32]; + + assert(w < lenof(tmp)); + + if (errors) + for (i = 0; i < A; i++) + errors[i] = 0; + + for (y = 0; y < w; y++) { + unsigned long mask = 0, errmask = 0; + for (x = 0; x < w; x++) { + unsigned long bit = 1UL << grid[y*w+x]; + errmask |= (mask & bit); + mask |= bit; + } + + if (mask != (1L << (w+1)) - (1L << 1)) { + errs = TRUE; + errmask &= ~1UL; + if (errors) { + for (x = 0; x < w; x++) + if (errmask & (1UL << grid[y*w+x])) + errors[(y+1)*W+(x+1)] = TRUE; + } + } + } + + for (x = 0; x < w; x++) { + unsigned long mask = 0, errmask = 0; + for (y = 0; y < w; y++) { + unsigned long bit = 1UL << grid[y*w+x]; + errmask |= (mask & bit); + mask |= bit; + } + + if (mask != (1 << (w+1)) - (1 << 1)) { + errs = TRUE; + errmask &= ~1UL; + if (errors) { + for (y = 0; y < w; y++) + if (errmask & (1UL << grid[y*w+x])) + errors[(y+1)*W+(x+1)] = TRUE; + } + } + } + + for (i = 0; i < 4*w; i++) { + int start, step, j, k, n, best; + STARTSTEP(start, step, i, w); + + if (!clues[i]) + continue; + + best = n = 0; + k = 0; + for (j = 0; j < w; j++) { + int number = grid[start+j*step]; + if (!number) + break; /* can't tell what happens next */ + if (number > best) { + best = number; + n++; + } + } + + if (n > clues[i] || (j == w && n < clues[i])) { + if (errors) { + int x, y; + CLUEPOS(x, y, i, w); + errors[(y+1)*W+(x+1)] = TRUE; + } + errs = TRUE; + } + } + + return errs; +} + +static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, + int x, int y, int button) +{ + int w = state->par.w; + int tx, ty; + char buf[80]; + + button &= ~MOD_MASK; + + tx = FROMCOORD(x); + ty = FROMCOORD(y); + + if (tx >= 0 && tx < w && ty >= 0 && ty < w) { + if (button == LEFT_BUTTON) { + if (tx == ui->hx && ty == ui->hy && + ui->hshow && ui->hpencil == 0) { + ui->hshow = 0; + } else { + ui->hx = tx; + ui->hy = ty; + ui->hshow = !state->clues->immutable[ty*w+tx]; + ui->hpencil = 0; + } + ui->hcursor = 0; + return ""; /* UI activity occurred */ + } + if (button == RIGHT_BUTTON) { + /* + * Pencil-mode highlighting for non filled squares. + */ + if (state->grid[ty*w+tx] == 0) { + if (tx == ui->hx && ty == ui->hy && + ui->hshow && ui->hpencil) { + ui->hshow = 0; + } else { + ui->hpencil = 1; + ui->hx = tx; + ui->hy = ty; + ui->hshow = 1; + } + } else { + ui->hshow = 0; + } + ui->hcursor = 0; + return ""; /* UI activity occurred */ + } + } + if (IS_CURSOR_MOVE(button)) { + move_cursor(button, &ui->hx, &ui->hy, w, w, 0); + ui->hshow = ui->hcursor = 1; + return ""; + } + if (ui->hshow && + (button == CURSOR_SELECT)) { + ui->hpencil = 1 - ui->hpencil; + ui->hcursor = 1; + return ""; + } + + if (ui->hshow && + ((button >= '0' && button <= '9' && button - '0' <= w) || + button == CURSOR_SELECT2 || button == '\b')) { + int n = button - '0'; + if (button == CURSOR_SELECT2 || button == '\b') + n = 0; + + /* + * Can't make pencil marks in a filled square. This can only + * become highlighted if we're using cursor keys. + */ + if (ui->hpencil && state->grid[ui->hy*w+ui->hx]) + return NULL; + + /* + * Can't do anything to an immutable square. + */ + if (state->clues->immutable[ui->hy*w+ui->hx]) + return NULL; + + sprintf(buf, "%c%d,%d,%d", + (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n); + + if (!ui->hcursor) ui->hshow = 0; + + return dupstr(buf); + } + + if (button == 'M' || button == 'm') + return dupstr("M"); + + return NULL; +} + +static game_state *execute_move(game_state *from, char *move) +{ + int w = from->par.w, a = w*w; + game_state *ret; + int x, y, i, n; + + if (move[0] == 'S') { + ret = dup_game(from); + ret->completed = ret->cheated = TRUE; + + for (i = 0; i < a; i++) { + if (move[i+1] < '1' || move[i+1] > '0'+w) { + free_game(ret); + return NULL; + } + ret->grid[i] = move[i+1] - '0'; + ret->pencil[i] = 0; + } + + if (move[a+1] != '\0') { + free_game(ret); + return NULL; + } + + return ret; + } else if ((move[0] == 'P' || move[0] == 'R') && + sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 && + x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) { + if (from->clues->immutable[y*w+x]) + return NULL; + + ret = dup_game(from); + if (move[0] == 'P' && n > 0) { + ret->pencil[y*w+x] ^= 1L << n; + } else { + ret->grid[y*w+x] = n; + ret->pencil[y*w+x] = 0; + + if (!ret->completed && !check_errors(ret, NULL)) + ret->completed = TRUE; + } + return ret; + } else if (move[0] == 'M') { + /* + * Fill in absolutely all pencil marks everywhere. (I + * wouldn't use this for actual play, but it's a handy + * starting point when following through a set of + * diagnostics output by the standalone solver.) + */ + ret = dup_game(from); + for (i = 0; i < a; i++) { + if (!ret->grid[i]) + ret->pencil[i] = (1L << (w+1)) - (1L << 1); + } + return ret; + } else + return NULL; /* couldn't parse move string */ +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +#define SIZE(w) ((w) * TILESIZE + 2*BORDER) + +static void game_compute_size(game_params *params, int tilesize, + int *x, int *y) +{ + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + struct { int tilesize; } ads, *ds = &ads; + ads.tilesize = tilesize; + + *x = *y = SIZE(params->w); +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + ret[COL_GRID * 3 + 0] = 0.0F; + ret[COL_GRID * 3 + 1] = 0.0F; + ret[COL_GRID * 3 + 2] = 0.0F; + + ret[COL_USER * 3 + 0] = 0.0F; + ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_USER * 3 + 2] = 0.0F; + + ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0]; + ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2]; + + ret[COL_ERROR * 3 + 0] = 1.0F; + ret[COL_ERROR * 3 + 1] = 0.0F; + ret[COL_ERROR * 3 + 2] = 0.0F; + + ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; + ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; + + *ncolours = NCOLOURS; + return ret; +} + +static const char *const minus_signs[] = { "\xE2\x88\x92", "-" }; +static const char *const times_signs[] = { "\xC3\x97", "*" }; +static const char *const divide_signs[] = { "\xC3\xB7", "/" }; + +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +{ + int w = state->par.w /*, a = w*w */; + struct game_drawstate *ds = snew(struct game_drawstate); + int i; + + ds->tilesize = 0; + ds->started = FALSE; + ds->tiles = snewn((w+2)*(w+2), long); + for (i = 0; i < (w+2)*(w+2); i++) + ds->tiles[i] = -1; + ds->errtmp = snewn((w+2)*(w+2), int); + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->errtmp); + sfree(ds->tiles); + sfree(ds); +} + +static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, + int x, int y, long tile) +{ + int w = clues->w /* , a = w*w */; + int tx, ty, tw, th; + int cx, cy, cw, ch; + char str[64]; + + tx = BORDER + x * TILESIZE + 1; + ty = BORDER + y * TILESIZE + 1; + + cx = tx; + cy = ty; + cw = tw = TILESIZE-1; + ch = th = TILESIZE-1; + + clip(dr, cx, cy, cw, ch); + + /* background needs erasing */ + draw_rect(dr, cx, cy, cw, ch, + (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND); + + /* pencil-mode highlight */ + if (tile & DF_HIGHLIGHT_PENCIL) { + int coords[6]; + coords[0] = cx; + coords[1] = cy; + coords[2] = cx+cw/2; + coords[3] = cy; + coords[4] = cx; + coords[5] = cy+ch/2; + draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); + } + + /* new number needs drawing? */ + if (tile & DF_DIGIT_MASK) { + str[1] = '\0'; + str[0] = (tile & DF_DIGIT_MASK) + '0'; + draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, FONT_VARIABLE, + (tile & DF_PLAYAREA ? TILESIZE/2 : TILESIZE*2/5), + ALIGN_VCENTRE | ALIGN_HCENTRE, + (tile & DF_ERROR) ? COL_ERROR : + (x < 0 || y < 0 || x >= w || y >= w) ? COL_GRID : + (tile & DF_IMMUTABLE) ? COL_GRID : COL_USER, str); + } else { + int i, j, npencil; + int pl, pr, pt, pb; + float bestsize; + int pw, ph, minph, pbest, fontsize; + + /* Count the pencil marks required. */ + for (i = 1, npencil = 0; i <= w; i++) + if (tile & (1L << (i + DF_PENCIL_SHIFT))) + npencil++; + if (npencil) { + + minph = 2; + + /* + * Determine the bounding rectangle within which we're going + * to put the pencil marks. + */ + /* Start with the whole square */ + pl = tx; + pr = pl + TILESIZE; + pt = ty; + pb = pt + TILESIZE; + + /* + * We arrange our pencil marks in a grid layout, with + * the number of rows and columns adjusted to allow the + * maximum font size. + * + * So now we work out what the grid size ought to be. + */ + bestsize = 0.0; + pbest = 0; + /* Minimum */ + for (pw = 3; pw < max(npencil,4); pw++) { + float fw, fh, fs; + + ph = (npencil + pw - 1) / pw; + ph = max(ph, minph); + fw = (pr - pl) / (float)pw; + fh = (pb - pt) / (float)ph; + fs = min(fw, fh); + if (fs > bestsize) { + bestsize = fs; + pbest = pw; + } + } + assert(pbest > 0); + pw = pbest; + ph = (npencil + pw - 1) / pw; + ph = max(ph, minph); + + /* + * Now we've got our grid dimensions, work out the pixel + * size of a grid element, and round it to the nearest + * pixel. (We don't want rounding errors to make the + * grid look uneven at low pixel sizes.) + */ + fontsize = min((pr - pl) / pw, (pb - pt) / ph); + + /* + * Centre the resulting figure in the square. + */ + pl = tx + (TILESIZE - fontsize * pw) / 2; + pt = ty + (TILESIZE - fontsize * ph) / 2; + + /* + * Now actually draw the pencil marks. + */ + for (i = 1, j = 0; i <= w; i++) + if (tile & (1L << (i + DF_PENCIL_SHIFT))) { + int dx = j % pw, dy = j / pw; + + str[1] = '\0'; + str[0] = i + '0'; + draw_text(dr, pl + fontsize * (2*dx+1) / 2, + pt + fontsize * (2*dy+1) / 2, + FONT_VARIABLE, fontsize, + ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); + j++; + } + } + } + + unclip(dr); + + draw_update(dr, cx, cy, cw, ch); +} + +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, + game_state *state, int dir, game_ui *ui, + float animtime, float flashtime) +{ + int w = state->par.w /*, a = w*w */; + int i, x, y; + + if (!ds->started) { + /* + * The initial contents of the window are not guaranteed and + * can vary with front ends. To be on the safe side, all + * games should start by drawing a big background-colour + * rectangle covering the whole window. + */ + draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND); + + /* + * Big containing rectangle. + */ + draw_rect(dr, COORD(0), COORD(0), + w*TILESIZE+1, w*TILESIZE+1, + COL_GRID); + + draw_update(dr, 0, 0, SIZE(w), SIZE(w)); + + ds->started = TRUE; + } + + check_errors(state, ds->errtmp); + + /* + * Draw the clues. + */ + for (i = 0; i < 4*w; i++) { + long tile = state->clues->clues[i]; + + if (!tile) + continue; + + CLUEPOS(x, y, i, w); + + if (ds->errtmp[(y+1)*(w+2)+(x+1)]) + tile |= DF_ERROR; + + if (ds->tiles[(y+1)*(w+2)+(x+1)] != tile) { + ds->tiles[(y+1)*(w+2)+(x+1)] = tile; + draw_tile(dr, ds, state->clues, x, y, tile); + } + } + + /* + * Draw the main grid. + */ + for (y = 0; y < w; y++) { + for (x = 0; x < w; x++) { + long tile = DF_PLAYAREA; + + if (state->grid[y*w+x]) + tile |= state->grid[y*w+x]; + else + tile |= (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT; + + if (ui->hshow && ui->hx == x && ui->hy == y) + tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT); + + if (state->clues->immutable[y*w+x]) + tile |= DF_IMMUTABLE; + + if (flashtime > 0 && + (flashtime <= FLASH_TIME/3 || + flashtime >= FLASH_TIME*2/3)) + tile |= DF_HIGHLIGHT; /* completion flash */ + + if (ds->errtmp[(y+1)*(w+2)+(x+1)]) + tile |= DF_ERROR; + + if (ds->tiles[(y+1)*(w+2)+(x+1)] != tile) { + ds->tiles[(y+1)*(w+2)+(x+1)] = tile; + draw_tile(dr, ds, state->clues, x, y, tile); + } + } + } +} + +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->cheated && !newstate->cheated) + return FLASH_TIME; + return 0.0F; +} + +static int game_timing_state(game_state *state, game_ui *ui) +{ + if (state->completed) + return FALSE; + return TRUE; +} + +static void game_print_size(game_params *params, float *x, float *y) +{ + int pw, ph; + + /* + * We use 9mm squares by default, like Solo. + */ + game_compute_size(params, 900, &pw, &ph); + *x = pw / 100.0F; + *y = ph / 100.0F; +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ + int w = state->par.w; + int ink = print_mono_colour(dr, 0); + int i, x, y; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(dr, ds, NULL, tilesize); + + /* + * Border. + */ + print_line_width(dr, 3 * TILESIZE / 40); + draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink); + + /* + * Main grid. + */ + for (x = 1; x < w; x++) { + print_line_width(dr, TILESIZE / 40); + draw_line(dr, BORDER+x*TILESIZE, BORDER, + BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink); + } + for (y = 1; y < w; y++) { + print_line_width(dr, TILESIZE / 40); + draw_line(dr, BORDER, BORDER+y*TILESIZE, + BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink); + } + + /* + * Clues. + */ + for (i = 0; i < 4*w; i++) { + char str[128]; + + if (!state->clues->clues[i]) + continue; + + CLUEPOS(x, y, i, w); + + sprintf (str, "%d", state->clues->clues[i]); + + draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2, + BORDER + y*TILESIZE + TILESIZE/2, + FONT_VARIABLE, TILESIZE/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); + } + + /* + * Numbers for the solution, if any. + */ + for (y = 0; y < w; y++) + for (x = 0; x < w; x++) + if (state->grid[y*w+x]) { + char str[2]; + str[1] = '\0'; + str[0] = state->grid[y*w+x] + '0'; + draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2, + BORDER + y*TILESIZE + TILESIZE/2, + FONT_VARIABLE, TILESIZE/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); + } +} + +#ifdef COMBINED +#define thegame towers +#endif + +const struct game thegame = { + "Towers", "games.towers", "towers", + 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_can_format_as_text_now, 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, + TRUE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ + FALSE, game_timing_state, + REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */ +}; + +#ifdef STANDALONE_SOLVER + +#include + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc, *err; + int grade = FALSE; + int ret, diff, really_show_working = FALSE; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + really_show_working = TRUE; + } else if (!strcmp(p, "-g")) { + grade = TRUE; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-g | -v] \n", argv[0]); + return 1; + } + + desc = strchr(id, ':'); + if (!desc) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(NULL, p, desc); + + /* + * When solving an Easy puzzle, we don't want to bother the + * user with Hard-level deductions. For this reason, we grade + * the puzzle internally before doing anything else. + */ + ret = -1; /* placate optimiser */ + solver_show_working = FALSE; + for (diff = 0; diff < DIFFCOUNT; diff++) { + memcpy(s->grid, s->clues->immutable, p->w * p->w); + ret = solver(p->w, s->clues->clues, s->grid, diff); + if (ret <= diff) + break; + } + + if (diff == DIFFCOUNT) { + if (grade) + printf("Difficulty rating: ambiguous\n"); + else + printf("Unable to find a unique solution\n"); + } else { + if (grade) { + if (ret == diff_impossible) + printf("Difficulty rating: impossible (no solution exists)\n"); + else + printf("Difficulty rating: %s\n", towers_diffnames[ret]); + } else { + solver_show_working = really_show_working; + memcpy(s->grid, s->clues->immutable, p->w * p->w); + ret = solver(p->w, s->clues->clues, s->grid, diff); + if (ret != diff) + printf("Puzzle is inconsistent\n"); + else + fputs(game_text_format(s), stdout); + } + } + + return 0; +} + +#endif + +/* vim: set shiftwidth=4 tabstop=8: */ -- 2.11.0