X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/444203b4c3de7b9a8c51fc940927c6f8352cd898..HEAD:/loopy.c diff --git a/loopy.c b/loopy.c index f4d3e6a..0ee1098 100644 --- a/loopy.c +++ b/loopy.c @@ -1,51 +1,79 @@ /* - * loopy.c: An implementation of the Nikoli game 'Loop the loop'. - * (c) Mike Pinna, 2005 + * loopy.c: + * + * An implementation of the Nikoli game 'Loop the loop'. + * (c) Mike Pinna, 2005, 2006 + * Substantially rewritten to allowing for more general types of grid. + * (c) Lambros Lambrou 2008 * * vim: set shiftwidth=4 :set textwidth=80: - */ + */ /* - * TODO: + * Possible future solver enhancements: + * + * - There's an interesting deductive technique which makes use + * of topology rather than just graph theory. Each _face_ in + * the grid is either inside or outside the loop; you can tell + * that two faces are on the same side of the loop if they're + * separated by a LINE_NO (or, more generally, by a path + * crossing no LINE_UNKNOWNs and an even number of LINE_YESes), + * and on the opposite side of the loop if they're separated by + * a LINE_YES (or an odd number of LINE_YESes and no + * LINE_UNKNOWNs). Oh, and any face separated from the outside + * of the grid by a LINE_YES or a LINE_NO is on the inside or + * outside respectively. So if you can track this for all + * faces, you figure out the state of the line between a pair + * once their relative insideness is known. + * + The way I envisage this working is simply to keep an edsf + * of all _faces_, which indicates whether they're on + * opposite sides of the loop from one another. We also + * include a special entry in the edsf for the infinite + * exterior "face". + * + So, the simple way to do this is to just go through the + * edges: every time we see an edge in a state other than + * LINE_UNKNOWN which separates two faces that aren't in the + * same edsf class, we can rectify that by merging the + * classes. Then, conversely, an edge in LINE_UNKNOWN state + * which separates two faces that _are_ in the same edsf + * class can immediately have its state determined. + * + But you can go one better, if you're prepared to loop + * over all _pairs_ of edges. Suppose we have edges A and B, + * which respectively separate faces A1,A2 and B1,B2. + * Suppose that A,B are in the same edge-edsf class and that + * A1,B1 (wlog) are in the same face-edsf class; then we can + * immediately place A2,B2 into the same face-edsf class (as + * each other, not as A1 and A2) one way round or the other. + * And conversely again, if A1,B1 are in the same face-edsf + * class and so are A2,B2, then we can put A,B into the same + * face-edsf class. + * * Of course, this deduction requires a quadratic-time + * loop over all pairs of edges in the grid, so it should + * be reserved until there's nothing easier left to be + * done. + * + * - The generalised grid support has made me (SGT) notice a + * possible extension to the loop-avoidance code. When you have + * a path of connected edges such that no other edges at all + * are incident on any vertex in the middle of the path - or, + * alternatively, such that any such edges are already known to + * be LINE_NO - then you know those edges are either all + * LINE_YES or all LINE_NO. Hence you can mentally merge the + * entire path into a single long curly edge for the purposes + * of loop avoidance, and look directly at whether or not the + * extreme endpoints of the path are connected by some other + * route. I find this coming up fairly often when I play on the + * octagonal grid setting, so it might be worth implementing in + * the solver. * - * - setting very high recursion depth seems to cause memory - * munching: are we recursing before checking completion, by any - * chance? - * - * - there's an interesting deductive technique which makes use of - * topology rather than just graph theory. Each _square_ in the - * grid is either inside or outside the loop; you can tell that - * two squares are on the same side of the loop if they're - * separated by an x (or, more generally, by a path crossing no - * LINE_UNKNOWNs and an even number of LINE_YESes), and on the - * opposite side of the loop if they're separated by a line (or - * an odd number of LINE_YESes and no LINE_UNKNOWNs). Oh, and - * any square separated from the outside of the grid by a - * LINE_YES or a LINE_NO is on the inside or outside - * respectively. So if you can track this for all squares, you - * can occasionally spot that two squares are separated by a - * LINE_UNKNOWN but their relative insideness is known, and - * therefore deduce the state of the edge between them. - * + An efficient way to track this would be by augmenting the - * disjoint set forest data structure. Each element, along - * with a pointer to a parent member of its equivalence - * class, would also carry a one-bit field indicating whether - * it was equal or opposite to its parent. Then you could - * keep flipping a bit as you ascended the tree during - * dsf_canonify(), and hence you'd be able to return the - * relationship of the input value to its ultimate parent - * (and also you could then get all those bits right when you - * went back up the tree rewriting). So you'd be able to - * query whether any two elements were known-equal, - * known-opposite, or not-known, and you could add new - * equalities or oppositenesses to increase your knowledge. - * (Of course the algorithm would have to fail an assertion - * if you tried to tell it two things it already knew to be - * opposite were equal, or vice versa!) + * - (Just a speed optimisation.) Consider some todo list queue where every + * time we modify something we mark it for consideration by other bits of + * the solver, to save iteration over things that have already been done. */ #include #include +#include #include #include #include @@ -53,169 +81,309 @@ #include "puzzles.h" #include "tree234.h" +#include "grid.h" +#include "loopgen.h" -#define PREFERRED_TILE_SIZE 32 -#define TILE_SIZE (ds->tilesize) -#define LINEWIDTH TILE_SIZE / 16 -#define BORDER (TILE_SIZE / 2) +/* Debugging options */ + +/* +#define DEBUG_CACHES +#define SHOW_WORKING +#define DEBUG_DLINES +*/ + +/* ---------------------------------------------------------------------- + * Struct, enum and function declarations + */ + +enum { + COL_BACKGROUND, + COL_FOREGROUND, + COL_LINEUNKNOWN, + COL_HIGHLIGHT, + COL_MISTAKE, + COL_SATISFIED, + COL_FAINT, + NCOLOURS +}; -#define FLASH_TIME 0.4F +struct game_state { + grid *game_grid; /* ref-counted (internally) */ + + /* Put -1 in a face that doesn't get a clue */ + signed char *clues; + + /* Array of line states, to store whether each line is + * YES, NO or UNKNOWN */ + char *lines; + + unsigned char *line_errors; -#define HL_COUNT(state) ((state)->w * ((state)->h + 1)) -#define VL_COUNT(state) (((state)->w + 1) * (state)->h) -#define DOT_COUNT(state) (((state)->w + 1) * ((state)->h + 1)) -#define SQUARE_COUNT(state) ((state)->w * (state)->h) + int solved; + int cheated; -#define ABOVE_SQUARE(state, i, j) ((state)->hl[(i) + (state)->w * (j)]) -#define BELOW_SQUARE(state, i, j) ABOVE_SQUARE(state, i, (j)+1) + /* Used in game_text_format(), so that it knows what type of + * grid it's trying to render as ASCII text. */ + int grid_type; +}; -#define LEFTOF_SQUARE(state, i, j) ((state)->vl[(i) + ((state)->w + 1) * (j)]) -#define RIGHTOF_SQUARE(state, i, j) LEFTOF_SQUARE(state, (i)+1, j) +enum solver_status { + SOLVER_SOLVED, /* This is the only solution the solver could find */ + SOLVER_MISTAKE, /* This is definitely not a solution */ + SOLVER_AMBIGUOUS, /* This _might_ be an ambiguous solution */ + SOLVER_INCOMPLETE /* This may be a partial solution */ +}; -#define LEGAL_DOT(state, i, j) ((i) >= 0 && (j) >= 0 && \ - (i) <= (state)->w && (j) <= (state)->h) +/* ------ Solver state ------ */ +typedef struct solver_state { + game_state *state; + enum solver_status solver_status; + /* NB looplen is the number of dots that are joined together at a point, ie a + * looplen of 1 means there are no lines to a particular dot */ + int *looplen; + + /* Difficulty level of solver. Used by solver functions that want to + * vary their behaviour depending on the requested difficulty level. */ + int diff; + + /* caches */ + char *dot_yes_count; + char *dot_no_count; + char *face_yes_count; + char *face_no_count; + char *dot_solved, *face_solved; + int *dotdsf; + + /* Information for Normal level deductions: + * For each dline, store a bitmask for whether we know: + * (bit 0) at least one is YES + * (bit 1) at most one is YES */ + char *dlines; + + /* Hard level information */ + int *linedsf; +} solver_state; /* - * These macros return rvalues only, but can cope with being passed - * out-of-range coordinates. + * 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 ABOVE_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || j <= 0) ? \ - LINE_NO : LV_ABOVE_DOT(state, i, j)) -#define BELOW_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || j >= (state)->h) ? \ - LINE_NO : LV_BELOW_DOT(state, i, j)) -#define LEFTOF_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || i <= 0) ? \ - LINE_NO : LV_LEFTOF_DOT(state, i, j)) -#define RIGHTOF_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || i >= (state)->w)?\ - LINE_NO : LV_RIGHTOF_DOT(state, i, j)) +#define DIFFLIST(A) \ + A(EASY,Easy,e) \ + A(NORMAL,Normal,n) \ + A(TRICKY,Tricky,t) \ + A(HARD,Hard,h) +#define ENUM(upper,title,lower) DIFF_ ## upper, +#define TITLE(upper,title,lower) #title, +#define ENCODE(upper,title,lower) #lower +#define CONFIG(upper,title,lower) ":" #title +enum { DIFFLIST(ENUM) DIFF_MAX }; +static char const *const diffnames[] = { DIFFLIST(TITLE) }; +static char const diffchars[] = DIFFLIST(ENCODE); +#define DIFFCONFIG DIFFLIST(CONFIG) /* - * These macros expect to be passed valid coordinates, and return - * lvalues. + * Solver routines, sorted roughly in order of computational cost. + * The solver will run the faster deductions first, and slower deductions are + * only invoked when the faster deductions are unable to make progress. + * Each function is associated with a difficulty level, so that the generated + * puzzles are solvable by applying only the functions with the chosen + * difficulty level or lower. */ -#define LV_BELOW_DOT(state, i, j) ((state)->vl[(i) + ((state)->w + 1) * (j)]) -#define LV_ABOVE_DOT(state, i, j) LV_BELOW_DOT(state, i, (j)-1) +#define SOLVERLIST(A) \ + A(trivial_deductions, DIFF_EASY) \ + A(dline_deductions, DIFF_NORMAL) \ + A(linedsf_deductions, DIFF_HARD) \ + A(loop_deductions, DIFF_EASY) +#define SOLVER_FN_DECL(fn,diff) static int fn(solver_state *); +#define SOLVER_FN(fn,diff) &fn, +#define SOLVER_DIFF(fn,diff) diff, +SOLVERLIST(SOLVER_FN_DECL) +static int (*(solver_fns[]))(solver_state *) = { SOLVERLIST(SOLVER_FN) }; +static int const solver_diffs[] = { SOLVERLIST(SOLVER_DIFF) }; +static const int NUM_SOLVERS = sizeof(solver_diffs)/sizeof(*solver_diffs); -#define LV_RIGHTOF_DOT(state, i, j) ((state)->hl[(i) + (state)->w * (j)]) -#define LV_LEFTOF_DOT(state, i, j) LV_RIGHTOF_DOT(state, (i)-1, j) +struct game_params { + int w, h; + int diff; + int type; +}; -#define CLUE_AT(state, i, j) ((i < 0 || i >= (state)->w || \ - j < 0 || j >= (state)->h) ? \ - ' ' : LV_CLUE_AT(state, i, j)) - -#define LV_CLUE_AT(state, i, j) ((state)->clues[(i) + (state)->w * (j)]) +/* line_drawstate is the same as line_state, but with the extra ERROR + * possibility. The drawing code copies line_state to line_drawstate, + * except in the case that the line is an error. */ +enum line_state { LINE_YES, LINE_UNKNOWN, LINE_NO }; +enum line_drawstate { DS_LINE_YES, DS_LINE_UNKNOWN, + DS_LINE_NO, DS_LINE_ERROR }; -#define OPP(dir) (dir == LINE_UNKNOWN ? LINE_UNKNOWN : \ - dir == LINE_YES ? LINE_NO : LINE_YES) +#define OPP(line_state) \ + (2 - line_state) -static char *game_text_format(game_state *state); -enum { - COL_BACKGROUND, - COL_FOREGROUND, - COL_HIGHLIGHT, - NCOLOURS +struct game_drawstate { + int started; + int tilesize; + int flashing; + int *textx, *texty; + char *lines; + char *clue_error; + char *clue_satisfied; }; -enum line_state { LINE_UNKNOWN, LINE_YES, LINE_NO }; +static char *validate_desc(game_params *params, char *desc); +static int dot_order(const game_state* state, int i, char line_type); +static int face_order(const game_state* state, int i, char line_type); +static solver_state *solve_game_rec(const solver_state *sstate); + +#ifdef DEBUG_CACHES +static void check_caches(const solver_state* sstate); +#else +#define check_caches(s) +#endif -enum direction { UP, DOWN, LEFT, RIGHT }; +/* ------- List of grid generators ------- */ +#define GRIDLIST(A) \ + A(Squares,GRID_SQUARE,3,3) \ + A(Triangular,GRID_TRIANGULAR,3,3) \ + A(Honeycomb,GRID_HONEYCOMB,3,3) \ + A(Snub-Square,GRID_SNUBSQUARE,3,3) \ + A(Cairo,GRID_CAIRO,3,4) \ + A(Great-Hexagonal,GRID_GREATHEXAGONAL,3,3) \ + A(Octagonal,GRID_OCTAGONAL,3,3) \ + A(Kites,GRID_KITE,3,3) \ + A(Floret,GRID_FLORET,1,2) \ + A(Dodecagonal,GRID_DODECAGONAL,2,2) \ + A(Great-Dodecagonal,GRID_GREATDODECAGONAL,2,2) \ + A(Penrose (kite/dart),GRID_PENROSE_P2,3,3) \ + A(Penrose (rhombs),GRID_PENROSE_P3,3,3) + +#define GRID_NAME(title,type,amin,omin) #title, +#define GRID_CONFIG(title,type,amin,omin) ":" #title +#define GRID_TYPE(title,type,amin,omin) type, +#define GRID_SIZES(title,type,amin,omin) \ + {amin, omin, \ + "Width and height for this grid type must both be at least " #amin, \ + "At least one of width and height for this grid type must be at least " #omin,}, +static char const *const gridnames[] = { GRIDLIST(GRID_NAME) }; +#define GRID_CONFIGS GRIDLIST(GRID_CONFIG) +static grid_type grid_types[] = { GRIDLIST(GRID_TYPE) }; +#define NUM_GRID_TYPES (sizeof(grid_types) / sizeof(grid_types[0])) +static const struct { + int amin, omin; + char *aerr, *oerr; +} grid_size_limits[] = { GRIDLIST(GRID_SIZES) }; + +/* Generates a (dynamically allocated) new grid, according to the + * type and size requested in params. Does nothing if the grid is already + * generated. */ +static grid *loopy_generate_grid(game_params *params, char *grid_desc) +{ + return grid_new(grid_types[params->type], params->w, params->h, grid_desc); +} -struct game_params { - int w, h, rec; -}; +/* ---------------------------------------------------------------------- + * Preprocessor magic + */ -struct game_state { - int w, h; - - /* Put ' ' in a square that doesn't get a clue */ - char *clues; - - /* Arrays of line states, stored left-to-right, top-to-bottom */ - char *hl, *vl; +/* General constants */ +#define PREFERRED_TILE_SIZE 32 +#define BORDER(tilesize) ((tilesize) / 2) +#define FLASH_TIME 0.5F - int solved; - int cheated; +#define BIT_SET(field, bit) ((field) & (1<<(bit))) - int recursion_depth; -}; +#define SET_BIT(field, bit) (BIT_SET(field, bit) ? FALSE : \ + ((field) |= (1<<(bit)), TRUE)) + +#define CLEAR_BIT(field, bit) (BIT_SET(field, bit) ? \ + ((field) &= ~(1<<(bit)), TRUE) : FALSE) + +#define CLUE2CHAR(c) \ + ((c < 0) ? ' ' : c < 10 ? c + '0' : c - 10 + 'A') + +/* ---------------------------------------------------------------------- + * General struct manipulation and other straightforward code + */ static game_state *dup_game(game_state *state) { game_state *ret = snew(game_state); - ret->h = state->h; - ret->w = state->w; + ret->game_grid = state->game_grid; + ret->game_grid->refcount++; + ret->solved = state->solved; ret->cheated = state->cheated; - ret->clues = snewn(SQUARE_COUNT(state), char); - memcpy(ret->clues, state->clues, SQUARE_COUNT(state)); + ret->clues = snewn(state->game_grid->num_faces, signed char); + memcpy(ret->clues, state->clues, state->game_grid->num_faces); - ret->hl = snewn(HL_COUNT(state), char); - memcpy(ret->hl, state->hl, HL_COUNT(state)); + ret->lines = snewn(state->game_grid->num_edges, char); + memcpy(ret->lines, state->lines, state->game_grid->num_edges); - ret->vl = snewn(VL_COUNT(state), char); - memcpy(ret->vl, state->vl, VL_COUNT(state)); - - ret->recursion_depth = state->recursion_depth; + ret->line_errors = snewn(state->game_grid->num_edges, unsigned char); + memcpy(ret->line_errors, state->line_errors, state->game_grid->num_edges); + ret->grid_type = state->grid_type; return ret; } static void free_game(game_state *state) { if (state) { + grid_free(state->game_grid); sfree(state->clues); - sfree(state->hl); - sfree(state->vl); + sfree(state->lines); + sfree(state->line_errors); sfree(state); } } -enum solver_status { - SOLVER_SOLVED, /* This is the only solution the solver could find */ - SOLVER_MISTAKE, /* This is definitely not a solution */ - SOLVER_AMBIGUOUS, /* This _might_ be an ambiguous solution */ - SOLVER_INCOMPLETE /* This may be a partial solution */ -}; - -typedef struct solver_state { - game_state *state; - /* XXX dot_atleastone[i,j, dline] is equivalent to */ - /* dot_atmostone[i,j,OPP_DLINE(dline)] */ - char *dot_atleastone; - char *dot_atmostone; -/* char *dline_identical; */ - int recursion_remaining; - enum solver_status solver_status; - int *dotdsf, *looplen; -} solver_state; - -static solver_state *new_solver_state(game_state *state) { - solver_state *ret = snew(solver_state); +static solver_state *new_solver_state(game_state *state, int diff) { int i; + int num_dots = state->game_grid->num_dots; + int num_faces = state->game_grid->num_faces; + int num_edges = state->game_grid->num_edges; + solver_state *ret = snew(solver_state); ret->state = dup_game(state); - - ret->dot_atmostone = snewn(DOT_COUNT(state), char); - memset(ret->dot_atmostone, 0, DOT_COUNT(state)); - ret->dot_atleastone = snewn(DOT_COUNT(state), char); - memset(ret->dot_atleastone, 0, DOT_COUNT(state)); -#if 0 - dline_identical = snewn(DOT_COUNT(state), char); - memset(dline_identical, 0, DOT_COUNT(state)); -#endif + ret->solver_status = SOLVER_INCOMPLETE; + ret->diff = diff; + + ret->dotdsf = snew_dsf(num_dots); + ret->looplen = snewn(num_dots, int); + + for (i = 0; i < num_dots; i++) { + ret->looplen[i] = 1; + } - ret->recursion_remaining = state->recursion_depth; - ret->solver_status = SOLVER_INCOMPLETE; /* XXX This may be a lie */ + ret->dot_solved = snewn(num_dots, char); + ret->face_solved = snewn(num_faces, char); + memset(ret->dot_solved, FALSE, num_dots); + memset(ret->face_solved, FALSE, num_faces); + + ret->dot_yes_count = snewn(num_dots, char); + memset(ret->dot_yes_count, 0, num_dots); + ret->dot_no_count = snewn(num_dots, char); + memset(ret->dot_no_count, 0, num_dots); + ret->face_yes_count = snewn(num_faces, char); + memset(ret->face_yes_count, 0, num_faces); + ret->face_no_count = snewn(num_faces, char); + memset(ret->face_no_count, 0, num_faces); + + if (diff < DIFF_NORMAL) { + ret->dlines = NULL; + } else { + ret->dlines = snewn(2*num_edges, char); + memset(ret->dlines, 0, 2*num_edges); + } - ret->dotdsf = snewn(DOT_COUNT(state), int); - ret->looplen = snewn(DOT_COUNT(state), int); - for (i = 0; i < DOT_COUNT(state); i++) { - ret->dotdsf[i] = i; - ret->looplen[i] = 1; + if (diff < DIFF_HARD) { + ret->linedsf = NULL; + } else { + ret->linedsf = snew_dsf(state->game_grid->num_edges); } return ret; @@ -224,149 +392,74 @@ static solver_state *new_solver_state(game_state *state) { static void free_solver_state(solver_state *sstate) { if (sstate) { free_game(sstate->state); - sfree(sstate->dot_atleastone); - sfree(sstate->dot_atmostone); - /* sfree(sstate->dline_identical); */ sfree(sstate->dotdsf); sfree(sstate->looplen); + sfree(sstate->dot_solved); + sfree(sstate->face_solved); + sfree(sstate->dot_yes_count); + sfree(sstate->dot_no_count); + sfree(sstate->face_yes_count); + sfree(sstate->face_no_count); + + /* OK, because sfree(NULL) is a no-op */ + sfree(sstate->dlines); + sfree(sstate->linedsf); + sfree(sstate); } } -static solver_state *dup_solver_state(solver_state *sstate) { - game_state *state; - +static solver_state *dup_solver_state(const solver_state *sstate) { + game_state *state = sstate->state; + int num_dots = state->game_grid->num_dots; + int num_faces = state->game_grid->num_faces; + int num_edges = state->game_grid->num_edges; solver_state *ret = snew(solver_state); ret->state = state = dup_game(sstate->state); - ret->dot_atmostone = snewn(DOT_COUNT(state), char); - memcpy(ret->dot_atmostone, sstate->dot_atmostone, DOT_COUNT(state)); - - ret->dot_atleastone = snewn(DOT_COUNT(state), char); - memcpy(ret->dot_atleastone, sstate->dot_atleastone, DOT_COUNT(state)); - -#if 0 - ret->dline_identical = snewn((state->w + 1) * (state->h + 1), char); - memcpy(ret->dline_identical, state->dot_atmostone, - (state->w + 1) * (state->h + 1)); -#endif - - ret->recursion_remaining = sstate->recursion_remaining; ret->solver_status = sstate->solver_status; - - ret->dotdsf = snewn(DOT_COUNT(state), int); - ret->looplen = snewn(DOT_COUNT(state), int); - memcpy(ret->dotdsf, sstate->dotdsf, DOT_COUNT(state) * sizeof(int)); - memcpy(ret->looplen, sstate->looplen, DOT_COUNT(state) * sizeof(int)); - - return ret; -} - -/* - * Merge two dots due to the existence of an edge between them. - * Updates the dsf tracking equivalence classes, and keeps track of - * the length of path each dot is currently a part of. - */ -static void merge_dots(solver_state *sstate, int x1, int y1, int x2, int y2) -{ - int i, j, len; - - i = y1 * (sstate->state->w + 1) + x1; - j = y2 * (sstate->state->w + 1) + x2; - - i = dsf_canonify(sstate->dotdsf, i); - j = dsf_canonify(sstate->dotdsf, j); - - if (i != j) { - len = sstate->looplen[i] + sstate->looplen[j]; - dsf_merge(sstate->dotdsf, i, j); - i = dsf_canonify(sstate->dotdsf, i); - sstate->looplen[i] = len; - } -} - -/* Count the number of lines of a particular type currently going into the - * given dot. Lines going off the edge of the board are assumed fixed no. */ -static int dot_order(const game_state* state, int i, int j, char line_type) -{ - int n = 0; - - if (i > 0) { - if (LEFTOF_DOT(state, i, j) == line_type) - ++n; + ret->diff = sstate->diff; + + ret->dotdsf = snewn(num_dots, int); + ret->looplen = snewn(num_dots, int); + memcpy(ret->dotdsf, sstate->dotdsf, + num_dots * sizeof(int)); + memcpy(ret->looplen, sstate->looplen, + num_dots * sizeof(int)); + + ret->dot_solved = snewn(num_dots, char); + ret->face_solved = snewn(num_faces, char); + memcpy(ret->dot_solved, sstate->dot_solved, num_dots); + memcpy(ret->face_solved, sstate->face_solved, num_faces); + + ret->dot_yes_count = snewn(num_dots, char); + memcpy(ret->dot_yes_count, sstate->dot_yes_count, num_dots); + ret->dot_no_count = snewn(num_dots, char); + memcpy(ret->dot_no_count, sstate->dot_no_count, num_dots); + + ret->face_yes_count = snewn(num_faces, char); + memcpy(ret->face_yes_count, sstate->face_yes_count, num_faces); + ret->face_no_count = snewn(num_faces, char); + memcpy(ret->face_no_count, sstate->face_no_count, num_faces); + + if (sstate->dlines) { + ret->dlines = snewn(2*num_edges, char); + memcpy(ret->dlines, sstate->dlines, + 2*num_edges); } else { - if (line_type == LINE_NO) - ++n; - } - if (i < state->w) { - if (RIGHTOF_DOT(state, i, j) == line_type) - ++n; - } else { - if (line_type == LINE_NO) - ++n; - } - if (j > 0) { - if (ABOVE_DOT(state, i, j) == line_type) - ++n; - } else { - if (line_type == LINE_NO) - ++n; + ret->dlines = NULL; } - if (j < state->h) { - if (BELOW_DOT(state, i, j) == line_type) - ++n; + + if (sstate->linedsf) { + ret->linedsf = snewn(num_edges, int); + memcpy(ret->linedsf, sstate->linedsf, + num_edges * sizeof(int)); } else { - if (line_type == LINE_NO) - ++n; + ret->linedsf = NULL; } - return n; -} -/* Count the number of lines of a particular type currently surrounding the - * given square */ -static int square_order(const game_state* state, int i, int j, char line_type) -{ - int n = 0; - - if (ABOVE_SQUARE(state, i, j) == line_type) - ++n; - if (BELOW_SQUARE(state, i, j) == line_type) - ++n; - if (LEFTOF_SQUARE(state, i, j) == line_type) - ++n; - if (RIGHTOF_SQUARE(state, i, j) == line_type) - ++n; - - return n; -} - -/* Set all lines bordering a dot of type old_type to type new_type */ -static void dot_setall(game_state *state, int i, int j, - char old_type, char new_type) -{ -/* printf("dot_setall([%d,%d], %d, %d)\n", i, j, old_type, new_type); */ - if (i > 0 && LEFTOF_DOT(state, i, j) == old_type) - LV_LEFTOF_DOT(state, i, j) = new_type; - if (i < state->w && RIGHTOF_DOT(state, i, j) == old_type) - LV_RIGHTOF_DOT(state, i, j) = new_type; - if (j > 0 && ABOVE_DOT(state, i, j) == old_type) - LV_ABOVE_DOT(state, i, j) = new_type; - if (j < state->h && BELOW_DOT(state, i, j) == old_type) - LV_BELOW_DOT(state, i, j) = new_type; -} -/* Set all lines bordering a square of type old_type to type new_type */ -static void square_setall(game_state *state, int i, int j, - char old_type, char new_type) -{ - if (ABOVE_SQUARE(state, i, j) == old_type) - ABOVE_SQUARE(state, i, j) = new_type; - if (BELOW_SQUARE(state, i, j) == old_type) - BELOW_SQUARE(state, i, j) = new_type; - if (LEFTOF_SQUARE(state, i, j) == old_type) - LEFTOF_SQUARE(state, i, j) = new_type; - if (RIGHTOF_SQUARE(state, i, j) == old_type) - RIGHTOF_SQUARE(state, i, j) = new_type; + return ret; } static game_params *default_params(void) @@ -374,13 +467,14 @@ static game_params *default_params(void) game_params *ret = snew(game_params); #ifdef SLOW_SYSTEM - ret->h = 4; - ret->w = 4; + ret->h = 7; + ret->w = 7; #else ret->h = 10; ret->w = 10; #endif - ret->rec = 0; + ret->diff = DIFF_EASY; + ret->type = 0; return ret; } @@ -388,36 +482,64 @@ static game_params *default_params(void) static game_params *dup_params(game_params *params) { game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ return ret; } -static const struct { - char *desc; - game_params params; -} loopy_presets[] = { - { "4x4 Easy", { 4, 4, 0 } }, - { "4x4 Hard", { 4, 4, 2 } }, - { "7x7 Easy", { 7, 7, 0 } }, - { "7x7 Hard", { 7, 7, 2 } }, - { "10x10 Easy", { 10, 10, 0 } }, -#ifndef SLOW_SYSTEM - { "10x10 Hard", { 10, 10, 2 } }, - { "15x15 Easy", { 15, 15, 0 } }, - { "30x20 Easy", { 30, 20, 0 } } +static const game_params presets[] = { +#ifdef SMALL_SCREEN + { 7, 7, DIFF_EASY, 0 }, + { 7, 7, DIFF_NORMAL, 0 }, + { 7, 7, DIFF_HARD, 0 }, + { 7, 7, DIFF_HARD, 1 }, + { 7, 7, DIFF_HARD, 2 }, + { 5, 5, DIFF_HARD, 3 }, + { 7, 7, DIFF_HARD, 4 }, + { 5, 4, DIFF_HARD, 5 }, + { 5, 5, DIFF_HARD, 6 }, + { 5, 5, DIFF_HARD, 7 }, + { 3, 3, DIFF_HARD, 8 }, + { 3, 3, DIFF_HARD, 9 }, + { 3, 3, DIFF_HARD, 10 }, + { 6, 6, DIFF_HARD, 11 }, + { 6, 6, DIFF_HARD, 12 }, +#else + { 7, 7, DIFF_EASY, 0 }, + { 10, 10, DIFF_EASY, 0 }, + { 7, 7, DIFF_NORMAL, 0 }, + { 10, 10, DIFF_NORMAL, 0 }, + { 7, 7, DIFF_HARD, 0 }, + { 10, 10, DIFF_HARD, 0 }, + { 10, 10, DIFF_HARD, 1 }, + { 12, 10, DIFF_HARD, 2 }, + { 7, 7, DIFF_HARD, 3 }, + { 9, 9, DIFF_HARD, 4 }, + { 5, 4, DIFF_HARD, 5 }, + { 7, 7, DIFF_HARD, 6 }, + { 5, 5, DIFF_HARD, 7 }, + { 5, 5, DIFF_HARD, 8 }, + { 5, 4, DIFF_HARD, 9 }, + { 5, 4, DIFF_HARD, 10 }, + { 10, 10, DIFF_HARD, 11 }, + { 10, 10, DIFF_HARD, 12 } #endif }; static int game_fetch_preset(int i, char **name, game_params **params) { - game_params tmppar; + game_params *tmppar; + char buf[80]; - if (i < 0 || i >= lenof(loopy_presets)) + if (i < 0 || i >= lenof(presets)) return FALSE; - tmppar = loopy_presets[i].params; - *params = dup_params(&tmppar); - *name = dupstr(loopy_presets[i].desc); + tmppar = snew(game_params); + *tmppar = presets[i]; + *params = tmppar; + sprintf(buf, "%dx%d %s - %s", tmppar->h, tmppar->w, + gridnames[tmppar->type], diffnames[tmppar->diff]); + *name = dupstr(buf); return TRUE; } @@ -430,26 +552,34 @@ static void free_params(game_params *params) static void decode_params(game_params *params, char const *string) { params->h = params->w = atoi(string); - params->rec = 0; + params->diff = DIFF_EASY; while (*string && isdigit((unsigned char)*string)) string++; if (*string == 'x') { string++; params->h = atoi(string); - while (*string && isdigit((unsigned char)*string)) string++; + while (*string && isdigit((unsigned char)*string)) string++; + } + if (*string == 't') { + string++; + params->type = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; } - if (*string == 'r') { + if (*string == 'd') { + int i; string++; - params->rec = atoi(string); - while (*string && isdigit((unsigned char)*string)) string++; + for (i = 0; i < DIFF_MAX; i++) + if (*string == diffchars[i]) + params->diff = i; + if (*string) string++; } } static char *encode_params(game_params *params, int full) { char str[80]; - sprintf(str, "%dx%d", params->w, params->h); + sprintf(str, "%dx%dt%d", params->w, params->h, params->type); if (full) - sprintf(str + strlen(str), "r%d", params->rec); + sprintf(str + strlen(str), "d%c", diffchars[params->diff]); return dupstr(str); } @@ -458,7 +588,7 @@ static config_item *game_configure(game_params *params) config_item *ret; char buf[80]; - ret = snewn(4, config_item); + ret = snewn(5, config_item); ret[0].name = "Width"; ret[0].type = C_STRING; @@ -472,16 +602,20 @@ static config_item *game_configure(game_params *params) ret[1].sval = dupstr(buf); ret[1].ival = 0; - ret[2].name = "Recursion depth"; - ret[2].type = C_STRING; - sprintf(buf, "%d", params->rec); - ret[2].sval = dupstr(buf); - ret[2].ival = 0; + ret[2].name = "Grid type"; + ret[2].type = C_CHOICES; + ret[2].sval = GRID_CONFIGS; + ret[2].ival = params->type; + + ret[3].name = "Difficulty"; + ret[3].type = C_CHOICES; + ret[3].sval = DIFFCONFIG; + ret[3].ival = params->diff; - ret[3].name = NULL; - ret[3].type = C_END; - ret[3].sval = NULL; - ret[3].ival = 0; + ret[4].name = NULL; + ret[4].type = C_END; + ret[4].sval = NULL; + ret[4].ival = 0; return ret; } @@ -492,1687 +626,2263 @@ static game_params *custom_params(config_item *cfg) ret->w = atoi(cfg[0].sval); ret->h = atoi(cfg[1].sval); - ret->rec = atoi(cfg[2].sval); + ret->type = cfg[2].ival; + ret->diff = cfg[3].ival; return ret; } static char *validate_params(game_params *params, int full) { - if (params->w < 4 || params->h < 4) - return "Width and height must both be at least 4"; - if (params->rec < 0) - return "Recursion depth can't be negative"; - return NULL; -} - -/* We're going to store a list of current candidate squares for lighting. - * Each square gets a 'score', which tells us how adding that square right - * now would affect the length of the solution loop. We're trying to - * maximise that quantity so will bias our random selection of squares to - * light towards those with high scores */ -struct square { - int score; - unsigned long random; - int x, y; -}; - -static int get_square_cmpfn(void *v1, void *v2) -{ - struct square *s1 = (struct square *)v1; - struct square *s2 = (struct square *)v2; - int r; - - r = s1->x - s2->x; - if (r) - return r; + if (params->type < 0 || params->type >= NUM_GRID_TYPES) + return "Illegal grid type"; + if (params->w < grid_size_limits[params->type].amin || + params->h < grid_size_limits[params->type].amin) + return grid_size_limits[params->type].aerr; + if (params->w < grid_size_limits[params->type].omin && + params->h < grid_size_limits[params->type].omin) + return grid_size_limits[params->type].oerr; - r = s1->y - s2->y; - if (r) - return r; + /* + * This shouldn't be able to happen at all, since decode_params + * and custom_params will never generate anything that isn't + * within range. + */ + assert(params->diff < DIFF_MAX); - return 0; + return NULL; } -static int square_sort_cmpfn(void *v1, void *v2) +/* Returns a newly allocated string describing the current puzzle */ +static char *state_to_text(const game_state *state) { - struct square *s1 = (struct square *)v1; - struct square *s2 = (struct square *)v2; - int r; + grid *g = state->game_grid; + char *retval; + int num_faces = g->num_faces; + char *description = snewn(num_faces + 1, char); + char *dp = description; + int empty_count = 0; + int i; - r = s2->score - s1->score; - if (r) { - return r; + for (i = 0; i < num_faces; i++) { + if (state->clues[i] < 0) { + if (empty_count > 25) { + dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); + empty_count = 0; + } + empty_count++; + } else { + if (empty_count) { + dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); + empty_count = 0; + } + dp += sprintf(dp, "%c", (int)CLUE2CHAR(state->clues[i])); + } } - if (s1->random < s2->random) - return -1; - else if (s1->random > s2->random) - return 1; + if (empty_count) + dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); - /* - * It's _just_ possible that two squares might have been given - * the same random value. In that situation, fall back to - * comparing based on the coordinates. This introduces a tiny - * directional bias, but not a significant one. - */ - return get_square_cmpfn(v1, v2); -} + retval = dupstr(description); + sfree(description); -static void print_tree(tree234 *tree) -{ -#if 0 - int i = 0; - struct square *s; - printf("Print tree:\n"); - while (i < count234(tree)) { - s = (struct square *)index234(tree, i); - assert(s); - printf(" [%d,%d], %d, %d\n", s->x, s->y, s->score, s->random); - ++i; - } -#endif + return retval; } -enum { SQUARE_LIT, SQUARE_UNLIT }; - -#define SQUARE_STATE(i, j) \ - (((i) < 0 || (i) >= params->w || \ - (j) < 0 || (j) >= params->h) ? \ - SQUARE_UNLIT : LV_SQUARE_STATE(i,j)) +#define GRID_DESC_SEP '_' -#define LV_SQUARE_STATE(i, j) board[(i) + params->w * (j)] - -static void print_board(const game_params *params, const char *board) +/* Splits up a (optional) grid_desc from the game desc. Returns the + * grid_desc (which needs freeing) and updates the desc pointer to + * start of real desc, or returns NULL if no desc. */ +static char *extract_grid_desc(char **desc) { -#if 0 - int i,j; - - printf(" "); - for (i = 0; i < params->w; i++) { - printf("%d", i%10); - } - printf("\n"); - for (j = 0; j < params->h; j++) { - printf("%d", j%10); - for (i = 0; i < params->w; i++) { - printf("%c", SQUARE_STATE(i, j) ? ' ' : 'O'); - } - printf("\n"); - } -#endif -} - -static char *new_fullyclued_board(game_params *params, random_state *rs) -{ - char *clues; - char *board; - int i, j, a, b, c; - game_state s; - game_state *state = &s; - int board_area = SQUARE_COUNT(params); - int t; - - struct square *square, *tmpsquare, *sq; - struct square square_pos; - - /* These will contain exactly the same information, sorted into different - * orders */ - tree234 *lightable_squares_sorted, *lightable_squares_gettable; - -#define SQUARE_REACHABLE(i,j) \ - (t = (SQUARE_STATE(i-1, j) == SQUARE_LIT || \ - SQUARE_STATE(i+1, j) == SQUARE_LIT || \ - SQUARE_STATE(i, j-1) == SQUARE_LIT || \ - SQUARE_STATE(i, j+1) == SQUARE_LIT), \ -/* printf("SQUARE_REACHABLE(%d,%d) = %d\n", i, j, t), */ \ - t) - - - /* One situation in which we may not light a square is if that'll leave one - * square above/below and one left/right of us unlit, separated by a lit - * square diagnonal from us */ -#define SQUARE_DIAGONAL_VIOLATION(i, j, h, v) \ - (t = (SQUARE_STATE((i)+(h), (j)) == SQUARE_UNLIT && \ - SQUARE_STATE((i), (j)+(v)) == SQUARE_UNLIT && \ - SQUARE_STATE((i)+(h), (j)+(v)) == SQUARE_LIT), \ -/* t ? printf("SQUARE_DIAGONAL_VIOLATION(%d, %d, %d, %d)\n", - i, j, h, v) : 0,*/ \ - t) - - /* We also may not light a square if it will form a loop of lit squares - * around some unlit squares, as then the game soln won't have a single - * loop */ -#define SQUARE_LOOP_VIOLATION(i, j, lit1, lit2) \ - (SQUARE_STATE((i)+1, (j)) == lit1 && \ - SQUARE_STATE((i)-1, (j)) == lit1 && \ - SQUARE_STATE((i), (j)+1) == lit2 && \ - SQUARE_STATE((i), (j)-1) == lit2) - -#define CAN_LIGHT_SQUARE(i, j) \ - (SQUARE_REACHABLE(i, j) && \ - !SQUARE_DIAGONAL_VIOLATION(i, j, -1, -1) && \ - !SQUARE_DIAGONAL_VIOLATION(i, j, +1, -1) && \ - !SQUARE_DIAGONAL_VIOLATION(i, j, -1, +1) && \ - !SQUARE_DIAGONAL_VIOLATION(i, j, +1, +1) && \ - !SQUARE_LOOP_VIOLATION(i, j, SQUARE_LIT, SQUARE_UNLIT) && \ - !SQUARE_LOOP_VIOLATION(i, j, SQUARE_UNLIT, SQUARE_LIT)) - -#define IS_LIGHTING_CANDIDATE(i, j) \ - (SQUARE_STATE(i, j) == SQUARE_UNLIT && \ - CAN_LIGHT_SQUARE(i,j)) - - /* The 'score' of a square reflects its current desirability for selection - * as the next square to light. We want to encourage moving into uncharted - * areas so we give scores according to how many of the square's neighbours - * are currently unlit. */ - - /* UNLIT SCORE - * 3 2 - * 2 0 - * 1 -2 - */ -#define SQUARE_SCORE(i,j) \ - (2*((SQUARE_STATE(i-1, j) == SQUARE_UNLIT) + \ - (SQUARE_STATE(i+1, j) == SQUARE_UNLIT) + \ - (SQUARE_STATE(i, j-1) == SQUARE_UNLIT) + \ - (SQUARE_STATE(i, j+1) == SQUARE_UNLIT)) - 4) - - /* When a square gets lit, this defines how far away from that square we - * need to go recomputing scores */ -#define SCORE_DISTANCE 1 - - board = snewn(board_area, char); - clues = snewn(board_area, char); - - state->h = params->h; - state->w = params->w; - state->clues = clues; - - /* Make a board */ - memset(board, SQUARE_UNLIT, board_area); - - /* Seed the board with a single lit square near the middle */ - i = params->w / 2; - j = params->h / 2; - if (params->w & 1 && random_bits(rs, 1)) - ++i; - if (params->h & 1 && random_bits(rs, 1)) - ++j; - - LV_SQUARE_STATE(i, j) = SQUARE_LIT; - - /* We need a way of favouring squares that will increase our loopiness. - * We do this by maintaining a list of all candidate squares sorted by - * their score and choose randomly from that with appropriate skew. - * In order to avoid consistently biasing towards particular squares, we - * need the sort order _within_ each group of scores to be completely - * random. But it would be abusing the hospitality of the tree234 data - * structure if our comparison function were nondeterministic :-). So with - * each square we associate a random number that does not change during a - * particular run of the generator, and use that as a secondary sort key. - * Yes, this means we will be biased towards particular random squares in - * any one run but that doesn't actually matter. */ - - lightable_squares_sorted = newtree234(square_sort_cmpfn); - lightable_squares_gettable = newtree234(get_square_cmpfn); -#define ADD_SQUARE(s) \ - do { \ -/* printf("ADD SQUARE: [%d,%d], %d, %d\n", - s->x, s->y, s->score, s->random);*/ \ - sq = add234(lightable_squares_sorted, s); \ - assert(sq == s); \ - sq = add234(lightable_squares_gettable, s); \ - assert(sq == s); \ - } while (0) + char *sep = strchr(*desc, GRID_DESC_SEP), *gd; + int gd_len; -#define REMOVE_SQUARE(s) \ - do { \ -/* printf("DELETE SQUARE: [%d,%d], %d, %d\n", - s->x, s->y, s->score, s->random);*/ \ - sq = del234(lightable_squares_sorted, s); \ - assert(sq); \ - sq = del234(lightable_squares_gettable, s); \ - assert(sq); \ - } while (0) - -#define HANDLE_DIR(a, b) \ - square = snew(struct square); \ - square->x = (i)+(a); \ - square->y = (j)+(b); \ - square->score = 2; \ - square->random = random_bits(rs, 31); \ - ADD_SQUARE(square); - HANDLE_DIR(-1, 0); - HANDLE_DIR( 1, 0); - HANDLE_DIR( 0,-1); - HANDLE_DIR( 0, 1); -#undef HANDLE_DIR - - /* Light squares one at a time until the board is interesting enough */ - while (TRUE) - { - /* We have count234(lightable_squares) possibilities, and in - * lightable_squares_sorted they are sorted with the most desirable - * first. */ - c = count234(lightable_squares_sorted); - if (c == 0) - break; - assert(c == count234(lightable_squares_gettable)); + if (!sep) return NULL; - /* Check that the best square available is any good */ - square = (struct square *)index234(lightable_squares_sorted, 0); - assert(square); + gd_len = sep - (*desc); + gd = snewn(gd_len+1, char); + memcpy(gd, *desc, gd_len); + gd[gd_len] = '\0'; - if (square->score <= 0) - break; + *desc = sep+1; - print_tree(lightable_squares_sorted); - assert(square->score == SQUARE_SCORE(square->x, square->y)); - assert(SQUARE_STATE(square->x, square->y) == SQUARE_UNLIT); - assert(square->x >= 0 && square->x < params->w); - assert(square->y >= 0 && square->y < params->h); -/* printf("LIGHT SQUARE: [%d,%d], score = %d\n", square->x, square->y, square->score); */ + return gd; +} - /* Update data structures */ - LV_SQUARE_STATE(square->x, square->y) = SQUARE_LIT; - REMOVE_SQUARE(square); +/* We require that the params pass the test in validate_params and that the + * description fills the entire game area */ +static char *validate_desc(game_params *params, char *desc) +{ + int count = 0; + grid *g; + char *grid_desc, *ret; - print_board(params, board); + /* It's pretty inefficient to do this just for validation. All we need to + * know is the precise number of faces. */ + grid_desc = extract_grid_desc(&desc); + ret = grid_validate_desc(grid_types[params->type], params->w, params->h, grid_desc); + if (ret) return ret; - /* We might have changed the score of any squares up to 2 units away in - * any direction */ - for (b = -SCORE_DISTANCE; b <= SCORE_DISTANCE; b++) { - for (a = -SCORE_DISTANCE; a <= SCORE_DISTANCE; a++) { - if (!a && !b) - continue; - square_pos.x = square->x + a; - square_pos.y = square->y + b; -/* printf("Refreshing score for [%d,%d]:\n", square_pos.x, square_pos.y); */ - if (square_pos.x < 0 || square_pos.x >= params->w || - square_pos.y < 0 || square_pos.y >= params->h) { -/* printf(" Out of bounds\n"); */ - continue; - } - tmpsquare = find234(lightable_squares_gettable, &square_pos, - NULL); - if (tmpsquare) { -/* printf(" Removing\n"); */ - assert(tmpsquare->x == square_pos.x); - assert(tmpsquare->y == square_pos.y); - assert(SQUARE_STATE(tmpsquare->x, tmpsquare->y) == - SQUARE_UNLIT); - REMOVE_SQUARE(tmpsquare); - } else { -/* printf(" Creating\n"); */ - tmpsquare = snew(struct square); - tmpsquare->x = square_pos.x; - tmpsquare->y = square_pos.y; - tmpsquare->random = random_bits(rs, 31); - } - tmpsquare->score = SQUARE_SCORE(tmpsquare->x, tmpsquare->y); + g = loopy_generate_grid(params, grid_desc); + if (grid_desc) sfree(grid_desc); - if (IS_LIGHTING_CANDIDATE(tmpsquare->x, tmpsquare->y)) { -/* printf(" Adding\n"); */ - ADD_SQUARE(tmpsquare); - } else { -/* printf(" Destroying\n"); */ - sfree(tmpsquare); - } - } + for (; *desc; ++desc) { + if ((*desc >= '0' && *desc <= '9') || (*desc >= 'A' && *desc <= 'Z')) { + count++; + continue; } - sfree(square); -/* printf("\n\n"); */ - } - - while ((square = delpos234(lightable_squares_gettable, 0)) != NULL) - sfree(square); - freetree234(lightable_squares_gettable); - freetree234(lightable_squares_sorted); - - /* Copy out all the clues */ - for (j = 0; j < params->h; ++j) { - for (i = 0; i < params->w; ++i) { - c = SQUARE_STATE(i, j); - LV_CLUE_AT(state, i, j) = '0'; - if (SQUARE_STATE(i-1, j) != c) ++LV_CLUE_AT(state, i, j); - if (SQUARE_STATE(i+1, j) != c) ++LV_CLUE_AT(state, i, j); - if (SQUARE_STATE(i, j-1) != c) ++LV_CLUE_AT(state, i, j); - if (SQUARE_STATE(i, j+1) != c) ++LV_CLUE_AT(state, i, j); + if (*desc >= 'a') { + count += *desc - 'a' + 1; + continue; } + return "Unknown character in description"; } - sfree(board); - return clues; -} + if (count < g->num_faces) + return "Description too short for board size"; + if (count > g->num_faces) + return "Description too long for board size"; -static solver_state *solve_game_rec(const solver_state *sstate); + grid_free(g); -static int game_has_unique_soln(const game_state *state) + return NULL; +} + +/* Sums the lengths of the numbers in range [0,n) */ +/* See equivalent function in solo.c for justification of this. */ +static int len_0_to_n(int n) { - int ret; - solver_state *sstate_new; - solver_state *sstate = new_solver_state((game_state *)state); - - sstate_new = solve_game_rec(sstate); + int len = 1; /* Counting 0 as a bit of a special case */ + int i; - ret = (sstate_new->solver_status == SOLVER_SOLVED); + for (i = 1; i < n; i *= 10) { + len += max(n - i, 0); + } - free_solver_state(sstate_new); - free_solver_state(sstate); + return len; +} +static char *encode_solve_move(const game_state *state) +{ + int len; + char *ret, *p; + int i; + int num_edges = state->game_grid->num_edges; + + /* This is going to return a string representing the moves needed to set + * every line in a grid to be the same as the ones in 'state'. The exact + * length of this string is predictable. */ + + len = 1; /* Count the 'S' prefix */ + /* Numbers in all lines */ + len += len_0_to_n(num_edges); + /* For each line we also have a letter */ + len += num_edges; + + ret = snewn(len + 1, char); + p = ret; + + p += sprintf(p, "S"); + + for (i = 0; i < num_edges; i++) { + switch (state->lines[i]) { + case LINE_YES: + p += sprintf(p, "%dy", i); + break; + case LINE_NO: + p += sprintf(p, "%dn", i); + break; + } + } + + /* No point in doing sums like that if they're going to be wrong */ + assert(strlen(ret) <= (size_t)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) +{ +} + +static void game_compute_size(game_params *params, int tilesize, + int *x, int *y) +{ + int grid_width, grid_height, rendered_width, rendered_height; + int g_tilesize; + + grid_compute_size(grid_types[params->type], params->w, params->h, + &g_tilesize, &grid_width, &grid_height); + + /* multiply first to minimise rounding error on integer division */ + rendered_width = grid_width * tilesize / g_tilesize; + rendered_height = grid_height * tilesize / g_tilesize; + *x = rendered_width + 2 * BORDER(tilesize) + 1; + *y = rendered_height + 2 * BORDER(tilesize) + 1; +} + +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(4 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + ret[COL_FOREGROUND * 3 + 0] = 0.0F; + ret[COL_FOREGROUND * 3 + 1] = 0.0F; + ret[COL_FOREGROUND * 3 + 2] = 0.0F; + + /* + * We want COL_LINEUNKNOWN to be a yellow which is a bit darker + * than the background. (I previously set it to 0.8,0.8,0, but + * found that this went badly with the 0.8,0.8,0.8 favoured as a + * background by the Java frontend.) + */ + ret[COL_LINEUNKNOWN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F; + ret[COL_LINEUNKNOWN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F; + ret[COL_LINEUNKNOWN * 3 + 2] = 0.0F; + + ret[COL_HIGHLIGHT * 3 + 0] = 1.0F; + ret[COL_HIGHLIGHT * 3 + 1] = 1.0F; + ret[COL_HIGHLIGHT * 3 + 2] = 1.0F; + + ret[COL_MISTAKE * 3 + 0] = 1.0F; + ret[COL_MISTAKE * 3 + 1] = 0.0F; + ret[COL_MISTAKE * 3 + 2] = 0.0F; + + ret[COL_SATISFIED * 3 + 0] = 0.0F; + ret[COL_SATISFIED * 3 + 1] = 0.0F; + ret[COL_SATISFIED * 3 + 2] = 0.0F; + + /* We want the faint lines to be a bit darker than the background. + * Except if the background is pretty dark already; then it ought to be a + * bit lighter. Oy vey. + */ + ret[COL_FAINT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F; + ret[COL_FAINT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F; + ret[COL_FAINT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.9F; + + *ncolours = NCOLOURS; return ret; } +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + int num_faces = state->game_grid->num_faces; + int num_edges = state->game_grid->num_edges; + int i; + + ds->tilesize = 0; + ds->started = 0; + ds->lines = snewn(num_edges, char); + ds->clue_error = snewn(num_faces, char); + ds->clue_satisfied = snewn(num_faces, char); + ds->textx = snewn(num_faces, int); + ds->texty = snewn(num_faces, int); + ds->flashing = 0; + + memset(ds->lines, LINE_UNKNOWN, num_edges); + memset(ds->clue_error, 0, num_faces); + memset(ds->clue_satisfied, 0, num_faces); + for (i = 0; i < num_faces; i++) + ds->textx[i] = ds->texty[i] = -1; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->textx); + sfree(ds->texty); + sfree(ds->clue_error); + sfree(ds->clue_satisfied); + sfree(ds->lines); + sfree(ds); +} + +static int game_timing_state(game_state *state, game_ui *ui) +{ + return TRUE; +} + +static float game_anim_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + return 0.0F; +} + +static int game_can_format_as_text_now(game_params *params) +{ + if (params->type != 0) + return FALSE; + return TRUE; +} + +static char *game_text_format(game_state *state) +{ + int w, h, W, H; + int x, y, i; + int cell_size; + char *ret; + grid *g = state->game_grid; + grid_face *f; + + assert(state->grid_type == 0); + + /* Work out the basic size unit */ + f = g->faces; /* first face */ + assert(f->order == 4); + /* The dots are ordered clockwise, so the two opposite + * corners are guaranteed to span the square */ + cell_size = abs(f->dots[0]->x - f->dots[2]->x); + + w = (g->highest_x - g->lowest_x) / cell_size; + h = (g->highest_y - g->lowest_y) / cell_size; + + /* Create a blank "canvas" to "draw" on */ + W = 2 * w + 2; + H = 2 * h + 1; + ret = snewn(W * H + 1, char); + for (y = 0; y < H; y++) { + for (x = 0; x < W-1; x++) { + ret[y*W + x] = ' '; + } + ret[y*W + W-1] = '\n'; + } + ret[H*W] = '\0'; + + /* Fill in edge info */ + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + /* Cell coordinates, from (0,0) to (w-1,h-1) */ + int x1 = (e->dot1->x - g->lowest_x) / cell_size; + int x2 = (e->dot2->x - g->lowest_x) / cell_size; + int y1 = (e->dot1->y - g->lowest_y) / cell_size; + int y2 = (e->dot2->y - g->lowest_y) / cell_size; + /* Midpoint, in canvas coordinates (canvas coordinates are just twice + * cell coordinates) */ + x = x1 + x2; + y = y1 + y2; + switch (state->lines[i]) { + case LINE_YES: + ret[y*W + x] = (y1 == y2) ? '-' : '|'; + break; + case LINE_NO: + ret[y*W + x] = 'x'; + break; + case LINE_UNKNOWN: + break; /* already a space */ + default: + assert(!"Illegal line state"); + } + } + + /* Fill in clues */ + for (i = 0; i < g->num_faces; i++) { + int x1, x2, y1, y2; + + f = g->faces + i; + assert(f->order == 4); + /* Cell coordinates, from (0,0) to (w-1,h-1) */ + x1 = (f->dots[0]->x - g->lowest_x) / cell_size; + x2 = (f->dots[2]->x - g->lowest_x) / cell_size; + y1 = (f->dots[0]->y - g->lowest_y) / cell_size; + y2 = (f->dots[2]->y - g->lowest_y) / cell_size; + /* Midpoint, in canvas coordinates */ + x = x1 + x2; + y = y1 + y2; + ret[y*W + x] = CLUE2CHAR(state->clues[i]); + } + return ret; +} + +/* ---------------------------------------------------------------------- + * Debug code + */ + +#ifdef DEBUG_CACHES +static void check_caches(const solver_state* sstate) +{ + int i; + const game_state *state = sstate->state; + const grid *g = state->game_grid; + + for (i = 0; i < g->num_dots; i++) { + assert(dot_order(state, i, LINE_YES) == sstate->dot_yes_count[i]); + assert(dot_order(state, i, LINE_NO) == sstate->dot_no_count[i]); + } + + for (i = 0; i < g->num_faces; i++) { + assert(face_order(state, i, LINE_YES) == sstate->face_yes_count[i]); + assert(face_order(state, i, LINE_NO) == sstate->face_no_count[i]); + } +} + +#if 0 +#define check_caches(s) \ + do { \ + fprintf(stderr, "check_caches at line %d\n", __LINE__); \ + check_caches(s); \ + } while (0) +#endif +#endif /* DEBUG_CACHES */ + +/* ---------------------------------------------------------------------- + * Solver utility functions + */ + +/* Sets the line (with index i) to the new state 'line_new', and updates + * the cached counts of any affected faces and dots. + * Returns TRUE if this actually changed the line's state. */ +static int solver_set_line(solver_state *sstate, int i, + enum line_state line_new +#ifdef SHOW_WORKING + , const char *reason +#endif + ) +{ + game_state *state = sstate->state; + grid *g; + grid_edge *e; + + assert(line_new != LINE_UNKNOWN); + + check_caches(sstate); + + if (state->lines[i] == line_new) { + return FALSE; /* nothing changed */ + } + state->lines[i] = line_new; + +#ifdef SHOW_WORKING + fprintf(stderr, "solver: set line [%d] to %s (%s)\n", + i, line_new == LINE_YES ? "YES" : "NO", + reason); +#endif + + g = state->game_grid; + e = g->edges + i; + + /* Update the cache for both dots and both faces affected by this. */ + if (line_new == LINE_YES) { + sstate->dot_yes_count[e->dot1 - g->dots]++; + sstate->dot_yes_count[e->dot2 - g->dots]++; + if (e->face1) { + sstate->face_yes_count[e->face1 - g->faces]++; + } + if (e->face2) { + sstate->face_yes_count[e->face2 - g->faces]++; + } + } else { + sstate->dot_no_count[e->dot1 - g->dots]++; + sstate->dot_no_count[e->dot2 - g->dots]++; + if (e->face1) { + sstate->face_no_count[e->face1 - g->faces]++; + } + if (e->face2) { + sstate->face_no_count[e->face2 - g->faces]++; + } + } + + check_caches(sstate); + return TRUE; +} + +#ifdef SHOW_WORKING +#define solver_set_line(a, b, c) \ + solver_set_line(a, b, c, __FUNCTION__) +#endif + +/* + * Merge two dots due to the existence of an edge between them. + * Updates the dsf tracking equivalence classes, and keeps track of + * the length of path each dot is currently a part of. + * Returns TRUE if the dots were already linked, ie if they are part of a + * closed loop, and false otherwise. + */ +static int merge_dots(solver_state *sstate, int edge_index) +{ + int i, j, len; + grid *g = sstate->state->game_grid; + grid_edge *e = g->edges + edge_index; + + i = e->dot1 - g->dots; + j = e->dot2 - g->dots; + + i = dsf_canonify(sstate->dotdsf, i); + j = dsf_canonify(sstate->dotdsf, j); + + if (i == j) { + return TRUE; + } else { + len = sstate->looplen[i] + sstate->looplen[j]; + dsf_merge(sstate->dotdsf, i, j); + i = dsf_canonify(sstate->dotdsf, i); + sstate->looplen[i] = len; + return FALSE; + } +} + +/* Merge two lines because the solver has deduced that they must be either + * identical or opposite. Returns TRUE if this is new information, otherwise + * FALSE. */ +static int merge_lines(solver_state *sstate, int i, int j, int inverse +#ifdef SHOW_WORKING + , const char *reason +#endif + ) +{ + int inv_tmp; + + assert(i < sstate->state->game_grid->num_edges); + assert(j < sstate->state->game_grid->num_edges); + + i = edsf_canonify(sstate->linedsf, i, &inv_tmp); + inverse ^= inv_tmp; + j = edsf_canonify(sstate->linedsf, j, &inv_tmp); + inverse ^= inv_tmp; + + edsf_merge(sstate->linedsf, i, j, inverse); + +#ifdef SHOW_WORKING + if (i != j) { + fprintf(stderr, "%s [%d] [%d] %s(%s)\n", + __FUNCTION__, i, j, + inverse ? "inverse " : "", reason); + } +#endif + return (i != j); +} + +#ifdef SHOW_WORKING +#define merge_lines(a, b, c, d) \ + merge_lines(a, b, c, d, __FUNCTION__) +#endif + +/* Count the number of lines of a particular type currently going into the + * given dot. */ +static int dot_order(const game_state* state, int dot, char line_type) +{ + int n = 0; + grid *g = state->game_grid; + grid_dot *d = g->dots + dot; + int i; + + for (i = 0; i < d->order; i++) { + grid_edge *e = d->edges[i]; + if (state->lines[e - g->edges] == line_type) + ++n; + } + return n; +} + +/* Count the number of lines of a particular type currently surrounding the + * given face */ +static int face_order(const game_state* state, int face, char line_type) +{ + int n = 0; + grid *g = state->game_grid; + grid_face *f = g->faces + face; + int i; + + for (i = 0; i < f->order; i++) { + grid_edge *e = f->edges[i]; + if (state->lines[e - g->edges] == line_type) + ++n; + } + return n; +} + +/* Set all lines bordering a dot of type old_type to type new_type + * Return value tells caller whether this function actually did anything */ +static int dot_setall(solver_state *sstate, int dot, + char old_type, char new_type) +{ + int retval = FALSE, r; + game_state *state = sstate->state; + grid *g; + grid_dot *d; + int i; + + if (old_type == new_type) + return FALSE; + + g = state->game_grid; + d = g->dots + dot; + + for (i = 0; i < d->order; i++) { + int line_index = d->edges[i] - g->edges; + if (state->lines[line_index] == old_type) { + r = solver_set_line(sstate, line_index, new_type); + assert(r == TRUE); + retval = TRUE; + } + } + return retval; +} + +/* Set all lines bordering a face of type old_type to type new_type */ +static int face_setall(solver_state *sstate, int face, + char old_type, char new_type) +{ + int retval = FALSE, r; + game_state *state = sstate->state; + grid *g; + grid_face *f; + int i; + + if (old_type == new_type) + return FALSE; + + g = state->game_grid; + f = g->faces + face; + + for (i = 0; i < f->order; i++) { + int line_index = f->edges[i] - g->edges; + if (state->lines[line_index] == old_type) { + r = solver_set_line(sstate, line_index, new_type); + assert(r == TRUE); + retval = TRUE; + } + } + return retval; +} + +/* ---------------------------------------------------------------------- + * Loop generation and clue removal + */ + +static void add_full_clues(game_state *state, random_state *rs) +{ + signed char *clues = state->clues; + grid *g = state->game_grid; + char *board = snewn(g->num_faces, char); + int i; + + generate_loop(g, board, rs, NULL, NULL); + + /* Fill out all the clues by initialising to 0, then iterating over + * all edges and incrementing each clue as we find edges that border + * between BLACK/WHITE faces. While we're at it, we verify that the + * algorithm does work, and there aren't any GREY faces still there. */ + memset(clues, 0, g->num_faces); + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + grid_face *f1 = e->face1; + grid_face *f2 = e->face2; + enum face_colour c1 = FACE_COLOUR(f1); + enum face_colour c2 = FACE_COLOUR(f2); + assert(c1 != FACE_GREY); + assert(c2 != FACE_GREY); + if (c1 != c2) { + if (f1) clues[f1 - g->faces]++; + if (f2) clues[f2 - g->faces]++; + } + } + sfree(board); +} + + +static int game_has_unique_soln(const game_state *state, int diff) +{ + int ret; + solver_state *sstate_new; + solver_state *sstate = new_solver_state((game_state *)state, diff); + + sstate_new = solve_game_rec(sstate); + + assert(sstate_new->solver_status != SOLVER_MISTAKE); + ret = (sstate_new->solver_status == SOLVER_SOLVED); + + free_solver_state(sstate_new); + free_solver_state(sstate); + + return ret; +} + + /* Remove clues one at a time at random. */ -static game_state *remove_clues(game_state *state, random_state *rs) +static game_state *remove_clues(game_state *state, random_state *rs, + int diff) { - int *square_list, squares; + int *face_list; + int num_faces = state->game_grid->num_faces; game_state *ret = dup_game(state), *saved_ret; int n; /* We need to remove some clues. We'll do this by forming a list of all - * available equivalence classes, shuffling it, then going along one at a - * time clearing every member of each equivalence class, where removing a - * class doesn't render the board unsolvable. */ - squares = state->w * state->h; - square_list = snewn(squares, int); - for (n = 0; n < squares; ++n) { - square_list[n] = n; + * available clues, shuffling it, then going along one at a + * time clearing each clue in turn for which doing so doesn't render the + * board unsolvable. */ + face_list = snewn(num_faces, int); + for (n = 0; n < num_faces; ++n) { + face_list[n] = n; } - shuffle(square_list, squares, sizeof(int), rs); - - for (n = 0; n < squares; ++n) { + shuffle(face_list, num_faces, sizeof(int), rs); + + for (n = 0; n < num_faces; ++n) { saved_ret = dup_game(ret); - LV_CLUE_AT(ret, square_list[n] % state->w, - square_list[n] / state->w) = ' '; - if (game_has_unique_soln(ret)) { - free_game(saved_ret); + ret->clues[face_list[n]] = -1; + + if (game_has_unique_soln(ret, diff)) { + free_game(saved_ret); } else { free_game(ret); ret = saved_ret; } } - sfree(square_list); + sfree(face_list); return ret; } -static char *validate_desc(game_params *params, char *desc); static char *new_game_desc(game_params *params, random_state *rs, char **aux, int interactive) { /* solution and description both use run-length encoding in obvious ways */ - char *retval; - char *description = snewn(SQUARE_COUNT(params) + 1, char); - char *dp = description; - int i, j; - int empty_count; - game_state *state = snew(game_state), *state_new; + char *retval, *game_desc, *grid_desc; + grid *g; + game_state *state = snew(game_state); + game_state *state_new; + + grid_desc = grid_new_desc(grid_types[params->type], params->w, params->h, rs); + state->game_grid = g = loopy_generate_grid(params, grid_desc); + + state->clues = snewn(g->num_faces, signed char); + state->lines = snewn(g->num_edges, char); + state->line_errors = snewn(g->num_edges, unsigned char); - state->h = params->h; - state->w = params->w; + state->grid_type = params->type; - state->hl = snewn(HL_COUNT(params), char); - state->vl = snewn(VL_COUNT(params), char); - memset(state->hl, LINE_UNKNOWN, HL_COUNT(params)); - memset(state->vl, LINE_UNKNOWN, VL_COUNT(params)); + newboard_please: + + memset(state->lines, LINE_UNKNOWN, g->num_edges); + memset(state->line_errors, 0, g->num_edges); state->solved = state->cheated = FALSE; - state->recursion_depth = params->rec; /* Get a new random solvable board with all its clues filled in. Yes, this * can loop for ever if the params are suitably unfavourable, but * preventing games smaller than 4x4 seems to stop this happening */ do { - state->clues = new_fullyclued_board(params, rs); - } while (!game_has_unique_soln(state)); + add_full_clues(state, rs); + } while (!game_has_unique_soln(state, params->diff)); - state_new = remove_clues(state, rs); + state_new = remove_clues(state, rs, params->diff); free_game(state); state = state_new; - empty_count = 0; - for (j = 0; j < params->h; ++j) { - for (i = 0; i < params->w; ++i) { - if (CLUE_AT(state, i, j) == ' ') { - if (empty_count > 25) { - dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); - empty_count = 0; - } - empty_count++; - } else { - if (empty_count) { - dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); - empty_count = 0; - } - dp += sprintf(dp, "%c", (int)(CLUE_AT(state, i, j))); - } - } + + if (params->diff > 0 && game_has_unique_soln(state, params->diff-1)) { +#ifdef SHOW_WORKING + fprintf(stderr, "Rejecting board, it is too easy\n"); +#endif + goto newboard_please; } - if (empty_count) - dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); + + game_desc = state_to_text(state); free_game(state); - retval = dupstr(description); - sfree(description); - + + if (grid_desc) { + retval = snewn(strlen(grid_desc) + 1 + strlen(game_desc) + 1, char); + sprintf(retval, "%s%c%s", grid_desc, (int)GRID_DESC_SEP, game_desc); + sfree(grid_desc); + sfree(game_desc); + } else { + retval = game_desc; + } + assert(!validate_desc(params, retval)); return retval; } -/* We require that the params pass the test in validate_params and that the - * description fills the entire game area */ -static char *validate_desc(game_params *params, char *desc) +static game_state *new_game(midend *me, game_params *params, char *desc) { - int count = 0; + int i; + game_state *state = snew(game_state); + int empties_to_make = 0; + int n,n2; + const char *dp; + char *grid_desc; + grid *g; + int num_faces, num_edges; - for (; *desc; ++desc) { - if (*desc >= '0' && *desc <= '9') { - count++; + grid_desc = extract_grid_desc(&desc); + state->game_grid = g = loopy_generate_grid(params, grid_desc); + if (grid_desc) sfree(grid_desc); + + dp = desc; + + num_faces = g->num_faces; + num_edges = g->num_edges; + + state->clues = snewn(num_faces, signed char); + state->lines = snewn(num_edges, char); + state->line_errors = snewn(num_edges, unsigned char); + + state->solved = state->cheated = FALSE; + + state->grid_type = params->type; + + for (i = 0; i < num_faces; i++) { + if (empties_to_make) { + empties_to_make--; + state->clues[i] = -1; continue; } - if (*desc >= 'a') { - count += *desc - 'a' + 1; + + assert(*dp); + n = *dp - '0'; + n2 = *dp - 'A' + 10; + if (n >= 0 && n < 10) { + state->clues[i] = n; + } else if (n2 >= 10 && n2 < 36) { + state->clues[i] = n2; + } else { + n = *dp - 'a' + 1; + assert(n > 0); + state->clues[i] = -1; + empties_to_make = n - 1; + } + ++dp; + } + + memset(state->lines, LINE_UNKNOWN, num_edges); + memset(state->line_errors, 0, num_edges); + return state; +} + +/* Calculates the line_errors data, and checks if the current state is a + * solution */ +static int check_completion(game_state *state) +{ + grid *g = state->game_grid; + int *dsf; + int num_faces = g->num_faces; + int i; + int infinite_area, finite_area; + int loops_found = 0; + int found_edge_not_in_loop = FALSE; + + memset(state->line_errors, 0, g->num_edges); + + /* LL implementation of SGT's idea: + * A loop will partition the grid into an inside and an outside. + * If there is more than one loop, the grid will be partitioned into + * even more distinct regions. We can therefore track equivalence of + * faces, by saying that two faces are equivalent when there is a non-YES + * edge between them. + * We could keep track of the number of connected components, by counting + * the number of dsf-merges that aren't no-ops. + * But we're only interested in 3 separate cases: + * no loops, one loop, more than one loop. + * + * No loops: all faces are equivalent to the infinite face. + * One loop: only two equivalence classes - finite and infinite. + * >= 2 loops: there are 2 distinct finite regions. + * + * So we simply make two passes through all the edges. + * In the first pass, we dsf-merge the two faces bordering each non-YES + * edge. + * In the second pass, we look for YES-edges bordering: + * a) two non-equivalent faces. + * b) two non-equivalent faces, and one of them is part of a different + * finite area from the first finite area we've seen. + * + * An occurrence of a) means there is at least one loop. + * An occurrence of b) means there is more than one loop. + * Edges satisfying a) are marked as errors. + * + * While we're at it, we set a flag if we find a YES edge that is not + * part of a loop. + * This information will help decide, if there's a single loop, whether it + * is a candidate for being a solution (that is, all YES edges are part of + * this loop). + * + * If there is a candidate loop, we then go through all clues and check + * they are all satisfied. If so, we have found a solution and we can + * unmark all line_errors. + */ + + /* Infinite face is at the end - its index is num_faces. + * This macro is just to make this obvious! */ + #define INF_FACE num_faces + dsf = snewn(num_faces + 1, int); + dsf_init(dsf, num_faces + 1); + + /* First pass */ + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + int f1 = e->face1 ? e->face1 - g->faces : INF_FACE; + int f2 = e->face2 ? e->face2 - g->faces : INF_FACE; + if (state->lines[i] != LINE_YES) + dsf_merge(dsf, f1, f2); + } + + /* Second pass */ + infinite_area = dsf_canonify(dsf, INF_FACE); + finite_area = -1; + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + int f1 = e->face1 ? e->face1 - g->faces : INF_FACE; + int can1 = dsf_canonify(dsf, f1); + int f2 = e->face2 ? e->face2 - g->faces : INF_FACE; + int can2 = dsf_canonify(dsf, f2); + if (state->lines[i] != LINE_YES) continue; + + if (can1 == can2) { + /* Faces are equivalent, so this edge not part of a loop */ + found_edge_not_in_loop = TRUE; continue; } - return "Unknown character in description"; + state->line_errors[i] = TRUE; + if (loops_found == 0) loops_found = 1; + + /* Don't bother with further checks if we've already found 2 loops */ + if (loops_found == 2) continue; + + if (finite_area == -1) { + /* Found our first finite area */ + if (can1 != infinite_area) + finite_area = can1; + else + finite_area = can2; + } + + /* Have we found a second area? */ + if (finite_area != -1) { + if (can1 != infinite_area && can1 != finite_area) { + loops_found = 2; + continue; + } + if (can2 != infinite_area && can2 != finite_area) { + loops_found = 2; + } + } } - if (count < SQUARE_COUNT(params)) - return "Description too short for board size"; - if (count > SQUARE_COUNT(params)) - return "Description too long for board size"; +/* + printf("loops_found = %d\n", loops_found); + printf("found_edge_not_in_loop = %s\n", + found_edge_not_in_loop ? "TRUE" : "FALSE"); +*/ - return NULL; + sfree(dsf); /* No longer need the dsf */ + + /* Have we found a candidate loop? */ + if (loops_found == 1 && !found_edge_not_in_loop) { + /* Yes, so check all clues are satisfied */ + int found_clue_violation = FALSE; + for (i = 0; i < num_faces; i++) { + int c = state->clues[i]; + if (c >= 0) { + if (face_order(state, i, LINE_YES) != c) { + found_clue_violation = TRUE; + break; + } + } + } + + if (!found_clue_violation) { + /* The loop is good */ + memset(state->line_errors, 0, g->num_edges); + return TRUE; /* No need to bother checking for dot violations */ + } + } + + /* Check for dot violations */ + for (i = 0; i < g->num_dots; i++) { + int yes = dot_order(state, i, LINE_YES); + int unknown = dot_order(state, i, LINE_UNKNOWN); + if ((yes == 1 && unknown == 0) || (yes >= 3)) { + /* violation, so mark all YES edges as errors */ + grid_dot *d = g->dots + i; + int j; + for (j = 0; j < d->order; j++) { + int e = d->edges[j] - g->edges; + if (state->lines[e] == LINE_YES) + state->line_errors[e] = TRUE; + } + } + } + return FALSE; } -static game_state *new_game(midend *me, game_params *params, char *desc) +/* ---------------------------------------------------------------------- + * Solver logic + * + * Our solver modes operate as follows. Each mode also uses the modes above it. + * + * Easy Mode + * Just implement the rules of the game. + * + * Normal and Tricky Modes + * For each (adjacent) pair of lines through each dot we store a bit for + * whether at least one of them is on and whether at most one is on. (If we + * know both or neither is on that's already stored more directly.) + * + * Advanced Mode + * Use edsf data structure to make equivalence classes of lines that are + * known identical to or opposite to one another. + */ + + +/* DLines: + * For general grids, we consider "dlines" to be pairs of lines joined + * at a dot. The lines must be adjacent around the dot, so we can think of + * a dline as being a dot+face combination. Or, a dot+edge combination where + * the second edge is taken to be the next clockwise edge from the dot. + * Original loopy code didn't have this extra restriction of the lines being + * adjacent. From my tests with square grids, this extra restriction seems to + * take little, if anything, away from the quality of the puzzles. + * A dline can be uniquely identified by an edge/dot combination, given that + * a dline-pair always goes clockwise around its common dot. The edge/dot + * combination can be represented by an edge/bool combination - if bool is + * TRUE, use edge->dot1 else use edge->dot2. So the total number of dlines is + * exactly twice the number of edges in the grid - although the dlines + * spanning the infinite face are not all that useful to the solver. + * Note that, by convention, a dline goes clockwise around its common dot, + * which means the dline goes anti-clockwise around its common face. + */ + +/* Helper functions for obtaining an index into an array of dlines, given + * various information. We assume the grid layout conventions about how + * the various lists are interleaved - see grid_make_consistent() for + * details. */ + +/* i points to the first edge of the dline pair, reading clockwise around + * the dot. */ +static int dline_index_from_dot(grid *g, grid_dot *d, int i) { - int i,j; - game_state *state = snew(game_state); - int empties_to_make = 0; - int n; - const char *dp = desc; + grid_edge *e = d->edges[i]; + int ret; +#ifdef DEBUG_DLINES + grid_edge *e2; + int i2 = i+1; + if (i2 == d->order) i2 = 0; + e2 = d->edges[i2]; +#endif + ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0); +#ifdef DEBUG_DLINES + printf("dline_index_from_dot: d=%d,i=%d, edges [%d,%d] - %d\n", + (int)(d - g->dots), i, (int)(e - g->edges), + (int)(e2 - g->edges), ret); +#endif + return ret; +} +/* i points to the second edge of the dline pair, reading clockwise around + * the face. That is, the edges of the dline, starting at edge{i}, read + * anti-clockwise around the face. By layout conventions, the common dot + * of the dline will be f->dots[i] */ +static int dline_index_from_face(grid *g, grid_face *f, int i) +{ + grid_edge *e = f->edges[i]; + grid_dot *d = f->dots[i]; + int ret; +#ifdef DEBUG_DLINES + grid_edge *e2; + int i2 = i - 1; + if (i2 < 0) i2 += f->order; + e2 = f->edges[i2]; +#endif + ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0); +#ifdef DEBUG_DLINES + printf("dline_index_from_face: f=%d,i=%d, edges [%d,%d] - %d\n", + (int)(f - g->faces), i, (int)(e - g->edges), + (int)(e2 - g->edges), ret); +#endif + return ret; +} +static int is_atleastone(const char *dline_array, int index) +{ + return BIT_SET(dline_array[index], 0); +} +static int set_atleastone(char *dline_array, int index) +{ + return SET_BIT(dline_array[index], 0); +} +static int is_atmostone(const char *dline_array, int index) +{ + return BIT_SET(dline_array[index], 1); +} +static int set_atmostone(char *dline_array, int index) +{ + return SET_BIT(dline_array[index], 1); +} - state->recursion_depth = params->rec; - - state->h = params->h; - state->w = params->w; +static void array_setall(char *array, char from, char to, int len) +{ + char *p = array, *p_old = p; + int len_remaining = len; - state->clues = snewn(SQUARE_COUNT(params), char); - state->hl = snewn(HL_COUNT(params), char); - state->vl = snewn(VL_COUNT(params), char); + while ((p = memchr(p, from, len_remaining))) { + *p = to; + len_remaining -= p - p_old; + p_old = p; + } +} - state->solved = state->cheated = FALSE; +/* Helper, called when doing dline dot deductions, in the case where we + * have 4 UNKNOWNs, and two of them (adjacent) have *exactly* one YES between + * them (because of dline atmostone/atleastone). + * On entry, edge points to the first of these two UNKNOWNs. This function + * will find the opposite UNKNOWNS (if they are adjacent to one another) + * and set their corresponding dline to atleastone. (Setting atmostone + * already happens in earlier dline deductions) */ +static int dline_set_opp_atleastone(solver_state *sstate, + grid_dot *d, int edge) +{ + game_state *state = sstate->state; + grid *g = state->game_grid; + int N = d->order; + int opp, opp2; + for (opp = 0; opp < N; opp++) { + int opp_dline_index; + if (opp == edge || opp == edge+1 || opp == edge-1) + continue; + if (opp == 0 && edge == N-1) + continue; + if (opp == N-1 && edge == 0) + continue; + opp2 = opp + 1; + if (opp2 == N) opp2 = 0; + /* Check if opp, opp2 point to LINE_UNKNOWNs */ + if (state->lines[d->edges[opp] - g->edges] != LINE_UNKNOWN) + continue; + if (state->lines[d->edges[opp2] - g->edges] != LINE_UNKNOWN) + continue; + /* Found opposite UNKNOWNS and they're next to each other */ + opp_dline_index = dline_index_from_dot(g, d, opp); + return set_atleastone(sstate->dlines, opp_dline_index); + } + return FALSE; +} - for (j = 0 ; j < params->h; ++j) { - for (i = 0 ; i < params->w; ++i) { - if (empties_to_make) { - empties_to_make--; - LV_CLUE_AT(state, i, j) = ' '; + +/* Set pairs of lines around this face which are known to be identical, to + * the given line_state */ +static int face_setall_identical(solver_state *sstate, int face_index, + enum line_state line_new) +{ + /* can[dir] contains the canonical line associated with the line in + * direction dir from the square in question. Similarly inv[dir] is + * whether or not the line in question is inverse to its canonical + * element. */ + int retval = FALSE; + game_state *state = sstate->state; + grid *g = state->game_grid; + grid_face *f = g->faces + face_index; + int N = f->order; + int i, j; + int can1, can2, inv1, inv2; + + for (i = 0; i < N; i++) { + int line1_index = f->edges[i] - g->edges; + if (state->lines[line1_index] != LINE_UNKNOWN) + continue; + for (j = i + 1; j < N; j++) { + int line2_index = f->edges[j] - g->edges; + if (state->lines[line2_index] != LINE_UNKNOWN) continue; - } - assert(*dp); - n = *dp - '0'; - if (n >=0 && n < 10) { - LV_CLUE_AT(state, i, j) = *dp; - } else { - n = *dp - 'a' + 1; - assert(n > 0); - LV_CLUE_AT(state, i, j) = ' '; - empties_to_make = n - 1; + /* Found two UNKNOWNS */ + can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1); + can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2); + if (can1 == can2 && inv1 == inv2) { + solver_set_line(sstate, line1_index, line_new); + solver_set_line(sstate, line2_index, line_new); } - ++dp; } } - - memset(state->hl, LINE_UNKNOWN, HL_COUNT(params)); - memset(state->vl, LINE_UNKNOWN, VL_COUNT(params)); - - return state; + return retval; } -enum { LOOP_NONE=0, LOOP_SOLN, LOOP_NOT_SOLN }; - -/* Starting at dot [i,j] moves around 'state' removing lines until it's clear - * whether or not the starting dot was on a loop. Returns boolean specifying - * whether a loop was found. loop_status calls this and assumes that if state - * has any lines set, this function will always remove at least one. */ -static int destructively_find_loop(game_state *state) +/* Given a dot or face, and a count of LINE_UNKNOWNs, find them and + * return the edge indices into e. */ +static void find_unknowns(game_state *state, + grid_edge **edge_list, /* Edge list to search (from a face or a dot) */ + int expected_count, /* Number of UNKNOWNs (comes from solver's cache) */ + int *e /* Returned edge indices */) { - int a, b, i, j, new_i, new_j, n; - char *lp; + int c = 0; + grid *g = state->game_grid; + while (c < expected_count) { + int line_index = *edge_list - g->edges; + if (state->lines[line_index] == LINE_UNKNOWN) { + e[c] = line_index; + c++; + } + ++edge_list; + } +} - lp = (char *)memchr(state->hl, LINE_YES, HL_COUNT(state)); - if (!lp) { - /* We know we're going to return false but we have to fulfil our - * contract */ - lp = (char *)memchr(state->vl, LINE_YES, VL_COUNT(state)); - if (lp) - *lp = LINE_NO; - - return FALSE; +/* If we have a list of edges, and we know whether the number of YESs should + * be odd or even, and there are only a few UNKNOWNs, we can do some simple + * linedsf deductions. This can be used for both face and dot deductions. + * Returns the difficulty level of the next solver that should be used, + * or DIFF_MAX if no progress was made. */ +static int parity_deductions(solver_state *sstate, + grid_edge **edge_list, /* Edge list (from a face or a dot) */ + int total_parity, /* Expected number of YESs modulo 2 (either 0 or 1) */ + int unknown_count) +{ + game_state *state = sstate->state; + int diff = DIFF_MAX; + int *linedsf = sstate->linedsf; + + if (unknown_count == 2) { + /* Lines are known alike/opposite, depending on inv. */ + int e[2]; + find_unknowns(state, edge_list, 2, e); + if (merge_lines(sstate, e[0], e[1], total_parity)) + diff = min(diff, DIFF_HARD); + } else if (unknown_count == 3) { + int e[3]; + int can[3]; /* canonical edges */ + int inv[3]; /* whether can[x] is inverse to e[x] */ + find_unknowns(state, edge_list, 3, e); + can[0] = edsf_canonify(linedsf, e[0], inv); + can[1] = edsf_canonify(linedsf, e[1], inv+1); + can[2] = edsf_canonify(linedsf, e[2], inv+2); + if (can[0] == can[1]) { + if (solver_set_line(sstate, e[2], (total_parity^inv[0]^inv[1]) ? + LINE_YES : LINE_NO)) + diff = min(diff, DIFF_EASY); + } + if (can[0] == can[2]) { + if (solver_set_line(sstate, e[1], (total_parity^inv[0]^inv[2]) ? + LINE_YES : LINE_NO)) + diff = min(diff, DIFF_EASY); + } + if (can[1] == can[2]) { + if (solver_set_line(sstate, e[0], (total_parity^inv[1]^inv[2]) ? + LINE_YES : LINE_NO)) + diff = min(diff, DIFF_EASY); + } + } else if (unknown_count == 4) { + int e[4]; + int can[4]; /* canonical edges */ + int inv[4]; /* whether can[x] is inverse to e[x] */ + find_unknowns(state, edge_list, 4, e); + can[0] = edsf_canonify(linedsf, e[0], inv); + can[1] = edsf_canonify(linedsf, e[1], inv+1); + can[2] = edsf_canonify(linedsf, e[2], inv+2); + can[3] = edsf_canonify(linedsf, e[3], inv+3); + if (can[0] == can[1]) { + if (merge_lines(sstate, e[2], e[3], total_parity^inv[0]^inv[1])) + diff = min(diff, DIFF_HARD); + } else if (can[0] == can[2]) { + if (merge_lines(sstate, e[1], e[3], total_parity^inv[0]^inv[2])) + diff = min(diff, DIFF_HARD); + } else if (can[0] == can[3]) { + if (merge_lines(sstate, e[1], e[2], total_parity^inv[0]^inv[3])) + diff = min(diff, DIFF_HARD); + } else if (can[1] == can[2]) { + if (merge_lines(sstate, e[0], e[3], total_parity^inv[1]^inv[2])) + diff = min(diff, DIFF_HARD); + } else if (can[1] == can[3]) { + if (merge_lines(sstate, e[0], e[2], total_parity^inv[1]^inv[3])) + diff = min(diff, DIFF_HARD); + } else if (can[2] == can[3]) { + if (merge_lines(sstate, e[0], e[1], total_parity^inv[2]^inv[3])) + diff = min(diff, DIFF_HARD); + } } + return diff; +} - n = lp - state->hl; - i = n % state->w; - j = n / state->w; +/* + * These are the main solver functions. + * + * Their return values are diff values corresponding to the lowest mode solver + * that would notice the work that they have done. For example if the normal + * mode solver adds actual lines or crosses, it will return DIFF_EASY as the + * easy mode solver might be able to make progress using that. It doesn't make + * sense for one of them to return a diff value higher than that of the + * function itself. + * + * Each function returns the lowest value it can, as early as possible, in + * order to try and pass as much work as possible back to the lower level + * solvers which progress more quickly. + */ - assert(i + j * state->w == n); /* because I'm feeling stupid */ - /* Save start position */ - a = i; - b = j; +/* PROPOSED NEW DESIGN: + * We have a work queue consisting of 'events' notifying us that something has + * happened that a particular solver mode might be interested in. For example + * the hard mode solver might do something that helps the normal mode solver at + * dot [x,y] in which case it will enqueue an event recording this fact. Then + * we pull events off the work queue, and hand each in turn to the solver that + * is interested in them. If a solver reports that it failed we pass the same + * event on to progressively more advanced solvers and the loop detector. Once + * we've exhausted an event, or it has helped us progress, we drop it and + * continue to the next one. The events are sorted first in order of solver + * complexity (easy first) then order of insertion (oldest first). + * Once we run out of events we loop over each permitted solver in turn + * (easiest first) until either a deduction is made (and an event therefore + * emerges) or no further deductions can be made (in which case we've failed). + * + * QUESTIONS: + * * How do we 'loop over' a solver when both dots and squares are concerned. + * Answer: first all squares then all dots. + */ - /* Delete one line from the potential loop */ - if (LEFTOF_DOT(state, i, j) == LINE_YES) { - LV_LEFTOF_DOT(state, i, j) = LINE_NO; - i--; - } else if (ABOVE_DOT(state, i, j) == LINE_YES) { - LV_ABOVE_DOT(state, i, j) = LINE_NO; - j--; - } else if (RIGHTOF_DOT(state, i, j) == LINE_YES) { - LV_RIGHTOF_DOT(state, i, j) = LINE_NO; - i++; - } else if (BELOW_DOT(state, i, j) == LINE_YES) { - LV_BELOW_DOT(state, i, j) = LINE_NO; - j++; - } else { - return FALSE; - } +static int trivial_deductions(solver_state *sstate) +{ + int i, current_yes, current_no; + game_state *state = sstate->state; + grid *g = state->game_grid; + int diff = DIFF_MAX; - do { - /* From the current position of [i,j] there needs to be exactly one - * line */ - new_i = new_j = -1; - -#define HANDLE_DIR(dir_dot, x, y) \ - if (dir_dot(state, i, j) == LINE_YES) { \ - if (new_i != -1 || new_j != -1) \ - return FALSE; \ - new_i = (i)+(x); \ - new_j = (j)+(y); \ - LV_##dir_dot(state, i, j) = LINE_NO; \ - } - HANDLE_DIR(ABOVE_DOT, 0, -1); - HANDLE_DIR(BELOW_DOT, 0, +1); - HANDLE_DIR(LEFTOF_DOT, -1, 0); - HANDLE_DIR(RIGHTOF_DOT, +1, 0); -#undef HANDLE_DIR - if (new_i == -1 || new_j == -1) { - return FALSE; - } + /* Per-face deductions */ + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; - i = new_i; - j = new_j; - } while (i != a || j != b); + if (sstate->face_solved[i]) + continue; - return TRUE; -} + current_yes = sstate->face_yes_count[i]; + current_no = sstate->face_no_count[i]; -static int loop_status(game_state *state) -{ - int i, j, n; - game_state *tmpstate; - int loop_found = FALSE, non_loop_found = FALSE, any_lines_found = FALSE; + if (current_yes + current_no == f->order) { + sstate->face_solved[i] = TRUE; + continue; + } -#define BAD_LOOP_FOUND \ - do { free_game(tmpstate); return LOOP_NOT_SOLN; } while(0) + if (state->clues[i] < 0) + continue; - /* Repeatedly look for loops until we either run out of lines to consider - * or discover for sure that the board fails on the grounds of having no - * loop */ - tmpstate = dup_game(state); + /* + * This code checks whether the numeric clue on a face is so + * large as to permit all its remaining LINE_UNKNOWNs to be + * filled in as LINE_YES, or alternatively so small as to + * permit them all to be filled in as LINE_NO. + */ - while (TRUE) { - if (!memchr(tmpstate->hl, LINE_YES, HL_COUNT(tmpstate)) && - !memchr(tmpstate->vl, LINE_YES, VL_COUNT(tmpstate))) { - break; + if (state->clues[i] < current_yes) { + sstate->solver_status = SOLVER_MISTAKE; + return DIFF_EASY; } - any_lines_found = TRUE; - - if (loop_found) - BAD_LOOP_FOUND; - if (destructively_find_loop(tmpstate)) { - loop_found = TRUE; - if (non_loop_found) - BAD_LOOP_FOUND; - } else { - non_loop_found = TRUE; + if (state->clues[i] == current_yes) { + if (face_setall(sstate, i, LINE_UNKNOWN, LINE_NO)) + diff = min(diff, DIFF_EASY); + sstate->face_solved[i] = TRUE; + continue; + } + + if (f->order - state->clues[i] < current_no) { + sstate->solver_status = SOLVER_MISTAKE; + return DIFF_EASY; + } + if (f->order - state->clues[i] == current_no) { + if (face_setall(sstate, i, LINE_UNKNOWN, LINE_YES)) + diff = min(diff, DIFF_EASY); + sstate->face_solved[i] = TRUE; + continue; } - } - free_game(tmpstate); + if (f->order - state->clues[i] == current_no + 1 && + f->order - current_yes - current_no > 2) { + /* + * One small refinement to the above: we also look for any + * adjacent pair of LINE_UNKNOWNs around the face with + * some LINE_YES incident on it from elsewhere. If we find + * one, then we know that pair of LINE_UNKNOWNs can't + * _both_ be LINE_YES, and hence that pushes us one line + * closer to being able to determine all the rest. + */ + int j, k, e1, e2, e, d; + + for (j = 0; j < f->order; j++) { + e1 = f->edges[j] - g->edges; + e2 = f->edges[j+1 < f->order ? j+1 : 0] - g->edges; + + if (g->edges[e1].dot1 == g->edges[e2].dot1 || + g->edges[e1].dot1 == g->edges[e2].dot2) { + d = g->edges[e1].dot1 - g->dots; + } else { + assert(g->edges[e1].dot2 == g->edges[e2].dot1 || + g->edges[e1].dot2 == g->edges[e2].dot2); + d = g->edges[e1].dot2 - g->dots; + } - if (!any_lines_found) - return LOOP_NONE; - - if (non_loop_found) { - assert(!loop_found); /* should have dealt with this already */ - return LOOP_NONE; - } - - /* Check that every clue is satisfied */ - for (j = 0; j < state->h; ++j) { - for (i = 0; i < state->w; ++i) { - n = CLUE_AT(state, i, j); - if (n != ' ') { - if (square_order(state, i, j, LINE_YES) != n - '0') { - return LOOP_NOT_SOLN; + if (state->lines[e1] == LINE_UNKNOWN && + state->lines[e2] == LINE_UNKNOWN) { + for (k = 0; k < g->dots[d].order; k++) { + int e = g->dots[d].edges[k] - g->edges; + if (state->lines[e] == LINE_YES) + goto found; /* multi-level break */ + } + } + } + continue; + + found: + /* + * If we get here, we've found such a pair of edges, and + * they're e1 and e2. + */ + for (j = 0; j < f->order; j++) { + e = f->edges[j] - g->edges; + if (state->lines[e] == LINE_UNKNOWN && e != e1 && e != e2) { + int r = solver_set_line(sstate, e, LINE_YES); + assert(r); + diff = min(diff, DIFF_EASY); } } } } - return LOOP_SOLN; -} + check_caches(sstate); -/* Sums the lengths of the numbers in range [0,n) */ -/* See equivalent function in solo.c for justification of this. */ -static int len_0_to_n(int n) -{ - int len = 1; /* Counting 0 as a bit of a special case */ - int i; + /* Per-dot deductions */ + for (i = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots + i; + int yes, no, unknown; - for (i = 1; i < n; i *= 10) { - len += max(n - i, 0); + if (sstate->dot_solved[i]) + continue; + + yes = sstate->dot_yes_count[i]; + no = sstate->dot_no_count[i]; + unknown = d->order - yes - no; + + if (yes == 0) { + if (unknown == 0) { + sstate->dot_solved[i] = TRUE; + } else if (unknown == 1) { + dot_setall(sstate, i, LINE_UNKNOWN, LINE_NO); + diff = min(diff, DIFF_EASY); + sstate->dot_solved[i] = TRUE; + } + } else if (yes == 1) { + if (unknown == 0) { + sstate->solver_status = SOLVER_MISTAKE; + return DIFF_EASY; + } else if (unknown == 1) { + dot_setall(sstate, i, LINE_UNKNOWN, LINE_YES); + diff = min(diff, DIFF_EASY); + } + } else if (yes == 2) { + if (unknown > 0) { + dot_setall(sstate, i, LINE_UNKNOWN, LINE_NO); + diff = min(diff, DIFF_EASY); + } + sstate->dot_solved[i] = TRUE; + } else { + sstate->solver_status = SOLVER_MISTAKE; + return DIFF_EASY; + } } - return len; + check_caches(sstate); + + return diff; } -static char *encode_solve_move(const game_state *state) +static int dline_deductions(solver_state *sstate) { - int len, i, j; - char *ret, *p; - /* This is going to return a string representing the moves needed to set - * every line in a grid to be the same as the ones in 'state'. The exact - * length of this string is predictable. */ - - len = 1; /* Count the 'S' prefix */ - /* Numbers in horizontal lines */ - /* Horizontal lines, x position */ - len += len_0_to_n(state->w) * (state->h + 1); - /* Horizontal lines, y position */ - len += len_0_to_n(state->h + 1) * (state->w); - /* Vertical lines, y position */ - len += len_0_to_n(state->h) * (state->w + 1); - /* Vertical lines, x position */ - len += len_0_to_n(state->w + 1) * (state->h); - /* For each line we also have two letters and a comma */ - len += 3 * (HL_COUNT(state) + VL_COUNT(state)); - - ret = snewn(len + 1, char); - p = ret; - - p += sprintf(p, "S"); + game_state *state = sstate->state; + grid *g = state->game_grid; + char *dlines = sstate->dlines; + int i; + int diff = DIFF_MAX; + + /* ------ Face deductions ------ */ + + /* Given a set of dline atmostone/atleastone constraints, need to figure + * out if we can deduce any further info. For more general faces than + * squares, this turns out to be a tricky problem. + * The approach taken here is to define (per face) NxN matrices: + * "maxs" and "mins". + * The entries maxs(j,k) and mins(j,k) define the upper and lower limits + * for the possible number of edges that are YES between positions j and k + * going clockwise around the face. Can think of j and k as marking dots + * around the face (recall the labelling scheme: edge0 joins dot0 to dot1, + * edge1 joins dot1 to dot2 etc). + * Trivially, mins(j,j) = maxs(j,j) = 0, and we don't even bother storing + * these. mins(j,j+1) and maxs(j,j+1) are determined by whether edge{j} + * is YES, NO or UNKNOWN. mins(j,j+2) and maxs(j,j+2) are related to + * the dline atmostone/atleastone status for edges j and j+1. + * + * Then we calculate the remaining entries recursively. We definitely + * know that + * mins(j,k) >= { mins(j,u) + mins(u,k) } for any u between j and k. + * This is because any valid placement of YESs between j and k must give + * a valid placement between j and u, and also between u and k. + * I believe it's sufficient to use just the two values of u: + * j+1 and j+2. Seems to work well in practice - the bounds we compute + * are rigorous, even if they might not be best-possible. + * + * Once we have maxs and mins calculated, we can make inferences about + * each dline{j,j+1} by looking at the possible complementary edge-counts + * mins(j+2,j) and maxs(j+2,j) and comparing these with the face clue. + * As well as dlines, we can make similar inferences about single edges. + * For example, consider a pentagon with clue 3, and we know at most one + * of (edge0, edge1) is YES, and at most one of (edge2, edge3) is YES. + * We could then deduce edge4 is YES, because maxs(0,4) would be 2, so + * that final edge would have to be YES to make the count up to 3. + */ - for (j = 0; j < state->h + 1; ++j) { - for (i = 0; i < state->w; ++i) { - switch (RIGHTOF_DOT(state, i, j)) { - case LINE_YES: - p += sprintf(p, "%d,%dhy", i, j); - break; - case LINE_NO: - p += sprintf(p, "%d,%dhn", i, j); - break; -/* default: */ - /* I'm going to forgive this because I think the results - * are cute. */ -/* assert(!"Solver produced incomplete solution!"); */ - } + /* Much quicker to allocate arrays on the stack than the heap, so + * define the largest possible face size, and base our array allocations + * on that. We check this with an assertion, in case someone decides to + * make a grid which has larger faces than this. Note, this algorithm + * could get quite expensive if there are many large faces. */ +#define MAX_FACE_SIZE 12 + + for (i = 0; i < g->num_faces; i++) { + int maxs[MAX_FACE_SIZE][MAX_FACE_SIZE]; + int mins[MAX_FACE_SIZE][MAX_FACE_SIZE]; + grid_face *f = g->faces + i; + int N = f->order; + int j,m; + int clue = state->clues[i]; + assert(N <= MAX_FACE_SIZE); + if (sstate->face_solved[i]) + continue; + if (clue < 0) continue; + + /* Calculate the (j,j+1) entries */ + for (j = 0; j < N; j++) { + int edge_index = f->edges[j] - g->edges; + int dline_index; + enum line_state line1 = state->lines[edge_index]; + enum line_state line2; + int tmp; + int k = j + 1; + if (k >= N) k = 0; + maxs[j][k] = (line1 == LINE_NO) ? 0 : 1; + mins[j][k] = (line1 == LINE_YES) ? 1 : 0; + /* Calculate the (j,j+2) entries */ + dline_index = dline_index_from_face(g, f, k); + edge_index = f->edges[k] - g->edges; + line2 = state->lines[edge_index]; + k++; + if (k >= N) k = 0; + + /* max */ + tmp = 2; + if (line1 == LINE_NO) tmp--; + if (line2 == LINE_NO) tmp--; + if (tmp == 2 && is_atmostone(dlines, dline_index)) + tmp = 1; + maxs[j][k] = tmp; + + /* min */ + tmp = 0; + if (line1 == LINE_YES) tmp++; + if (line2 == LINE_YES) tmp++; + if (tmp == 0 && is_atleastone(dlines, dline_index)) + tmp = 1; + mins[j][k] = tmp; } - } - for (j = 0; j < state->h; ++j) { - for (i = 0; i < state->w + 1; ++i) { - switch (BELOW_DOT(state, i, j)) { - case LINE_YES: - p += sprintf(p, "%d,%dvy", i, j); - break; - case LINE_NO: - p += sprintf(p, "%d,%dvn", i, j); - break; -/* default: */ - /* I'm going to forgive this because I think the results - * are cute. */ -/* assert(!"Solver produced incomplete solution!"); */ + /* Calculate the (j,j+m) entries for m between 3 and N-1 */ + for (m = 3; m < N; m++) { + for (j = 0; j < N; j++) { + int k = j + m; + int u = j + 1; + int v = j + 2; + int tmp; + if (k >= N) k -= N; + if (u >= N) u -= N; + if (v >= N) v -= N; + maxs[j][k] = maxs[j][u] + maxs[u][k]; + mins[j][k] = mins[j][u] + mins[u][k]; + tmp = maxs[j][v] + maxs[v][k]; + maxs[j][k] = min(maxs[j][k], tmp); + tmp = mins[j][v] + mins[v][k]; + mins[j][k] = max(mins[j][k], tmp); } } - } - /* No point in doing sums like that if they're going to be wrong */ - assert(strlen(ret) <= (size_t)len); - return ret; -} + /* See if we can make any deductions */ + for (j = 0; j < N; j++) { + int k; + grid_edge *e = f->edges[j]; + int line_index = e - g->edges; + int dline_index; -/* BEGIN SOLVER IMPLEMENTATION */ + if (state->lines[line_index] != LINE_UNKNOWN) + continue; + k = j + 1; + if (k >= N) k = 0; - /* For each pair of lines through each dot we store a bit for whether - * exactly one of those lines is ON, and in separate arrays we store whether - * at least one is on and whether at most 1 is on. (If we know both or - * neither is on that's already stored more directly.) That's six bits per - * dot. Bit number n represents the lines shown in dot_type_dirs[n]. */ + /* minimum YESs in the complement of this edge */ + if (mins[k][j] > clue) { + sstate->solver_status = SOLVER_MISTAKE; + return DIFF_EASY; + } + if (mins[k][j] == clue) { + /* setting this edge to YES would make at least + * (clue+1) edges - contradiction */ + solver_set_line(sstate, line_index, LINE_NO); + diff = min(diff, DIFF_EASY); + } + if (maxs[k][j] < clue - 1) { + sstate->solver_status = SOLVER_MISTAKE; + return DIFF_EASY; + } + if (maxs[k][j] == clue - 1) { + /* Only way to satisfy the clue is to set edge{j} as YES */ + solver_set_line(sstate, line_index, LINE_YES); + diff = min(diff, DIFF_EASY); + } -enum dline { - DLINE_VERT = 0, - DLINE_HORIZ = 1, - DLINE_UL = 2, - DLINE_DR = 3, - DLINE_UR = 4, - DLINE_DL = 5 -}; + /* More advanced deduction that allows propagation along diagonal + * chains of faces connected by dots, for example, 3-2-...-2-3 + * in square grids. */ + if (sstate->diff >= DIFF_TRICKY) { + /* Now see if we can make dline deduction for edges{j,j+1} */ + e = f->edges[k]; + if (state->lines[e - g->edges] != LINE_UNKNOWN) + /* Only worth doing this for an UNKNOWN,UNKNOWN pair. + * Dlines where one of the edges is known, are handled in the + * dot-deductions */ + continue; + + dline_index = dline_index_from_face(g, f, k); + k++; + if (k >= N) k = 0; + + /* minimum YESs in the complement of this dline */ + if (mins[k][j] > clue - 2) { + /* Adding 2 YESs would break the clue */ + if (set_atmostone(dlines, dline_index)) + diff = min(diff, DIFF_NORMAL); + } + /* maximum YESs in the complement of this dline */ + if (maxs[k][j] < clue) { + /* Adding 2 NOs would mean not enough YESs */ + if (set_atleastone(dlines, dline_index)) + diff = min(diff, DIFF_NORMAL); + } + } + } + } -#define OPP_DLINE(dline) (dline ^ 1) - + if (diff < DIFF_NORMAL) + return diff; -#define SQUARE_DLINES \ - HANDLE_DLINE(DLINE_UL, RIGHTOF_SQUARE, BELOW_SQUARE, 1, 1); \ - HANDLE_DLINE(DLINE_UR, LEFTOF_SQUARE, BELOW_SQUARE, 0, 1); \ - HANDLE_DLINE(DLINE_DL, RIGHTOF_SQUARE, ABOVE_SQUARE, 1, 0); \ - HANDLE_DLINE(DLINE_DR, LEFTOF_SQUARE, ABOVE_SQUARE, 0, 0); + /* ------ Dot deductions ------ */ -#define DOT_DLINES \ - HANDLE_DLINE(DLINE_VERT, ABOVE_DOT, BELOW_DOT); \ - HANDLE_DLINE(DLINE_HORIZ, LEFTOF_DOT, RIGHTOF_DOT); \ - HANDLE_DLINE(DLINE_UL, ABOVE_DOT, LEFTOF_DOT); \ - HANDLE_DLINE(DLINE_UR, ABOVE_DOT, RIGHTOF_DOT); \ - HANDLE_DLINE(DLINE_DL, BELOW_DOT, LEFTOF_DOT); \ - HANDLE_DLINE(DLINE_DR, BELOW_DOT, RIGHTOF_DOT); + for (i = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots + i; + int N = d->order; + int yes, no, unknown; + int j; + if (sstate->dot_solved[i]) + continue; + yes = sstate->dot_yes_count[i]; + no = sstate->dot_no_count[i]; + unknown = N - yes - no; + + for (j = 0; j < N; j++) { + int k; + int dline_index; + int line1_index, line2_index; + enum line_state line1, line2; + k = j + 1; + if (k >= N) k = 0; + dline_index = dline_index_from_dot(g, d, j); + line1_index = d->edges[j] - g->edges; + line2_index = d->edges[k] - g->edges; + line1 = state->lines[line1_index]; + line2 = state->lines[line2_index]; + + /* Infer dline state from line state */ + if (line1 == LINE_NO || line2 == LINE_NO) { + if (set_atmostone(dlines, dline_index)) + diff = min(diff, DIFF_NORMAL); + } + if (line1 == LINE_YES || line2 == LINE_YES) { + if (set_atleastone(dlines, dline_index)) + diff = min(diff, DIFF_NORMAL); + } + /* Infer line state from dline state */ + if (is_atmostone(dlines, dline_index)) { + if (line1 == LINE_YES && line2 == LINE_UNKNOWN) { + solver_set_line(sstate, line2_index, LINE_NO); + diff = min(diff, DIFF_EASY); + } + if (line2 == LINE_YES && line1 == LINE_UNKNOWN) { + solver_set_line(sstate, line1_index, LINE_NO); + diff = min(diff, DIFF_EASY); + } + } + if (is_atleastone(dlines, dline_index)) { + if (line1 == LINE_NO && line2 == LINE_UNKNOWN) { + solver_set_line(sstate, line2_index, LINE_YES); + diff = min(diff, DIFF_EASY); + } + if (line2 == LINE_NO && line1 == LINE_UNKNOWN) { + solver_set_line(sstate, line1_index, LINE_YES); + diff = min(diff, DIFF_EASY); + } + } + /* Deductions that depend on the numbers of lines. + * Only bother if both lines are UNKNOWN, otherwise the + * easy-mode solver (or deductions above) would have taken + * care of it. */ + if (line1 != LINE_UNKNOWN || line2 != LINE_UNKNOWN) + continue; -static void array_setall(char *array, char from, char to, int len) -{ - char *p = array, *p_old = p; - int len_remaining = len; + if (yes == 0 && unknown == 2) { + /* Both these unknowns must be identical. If we know + * atmostone or atleastone, we can make progress. */ + if (is_atmostone(dlines, dline_index)) { + solver_set_line(sstate, line1_index, LINE_NO); + solver_set_line(sstate, line2_index, LINE_NO); + diff = min(diff, DIFF_EASY); + } + if (is_atleastone(dlines, dline_index)) { + solver_set_line(sstate, line1_index, LINE_YES); + solver_set_line(sstate, line2_index, LINE_YES); + diff = min(diff, DIFF_EASY); + } + } + if (yes == 1) { + if (set_atmostone(dlines, dline_index)) + diff = min(diff, DIFF_NORMAL); + if (unknown == 2) { + if (set_atleastone(dlines, dline_index)) + diff = min(diff, DIFF_NORMAL); + } + } - while ((p = memchr(p, from, len_remaining))) { - *p = to; - len_remaining -= p - p_old; - p_old = p; + /* More advanced deduction that allows propagation along diagonal + * chains of faces connected by dots, for example: 3-2-...-2-3 + * in square grids. */ + if (sstate->diff >= DIFF_TRICKY) { + /* If we have atleastone set for this dline, infer + * atmostone for each "opposite" dline (that is, each + * dline without edges in common with this one). + * Again, this test is only worth doing if both these + * lines are UNKNOWN. For if one of these lines were YES, + * the (yes == 1) test above would kick in instead. */ + if (is_atleastone(dlines, dline_index)) { + int opp; + for (opp = 0; opp < N; opp++) { + int opp_dline_index; + if (opp == j || opp == j+1 || opp == j-1) + continue; + if (j == 0 && opp == N-1) + continue; + if (j == N-1 && opp == 0) + continue; + opp_dline_index = dline_index_from_dot(g, d, opp); + if (set_atmostone(dlines, opp_dline_index)) + diff = min(diff, DIFF_NORMAL); + } + if (yes == 0 && is_atmostone(dlines, dline_index)) { + /* This dline has *exactly* one YES and there are no + * other YESs. This allows more deductions. */ + if (unknown == 3) { + /* Third unknown must be YES */ + for (opp = 0; opp < N; opp++) { + int opp_index; + if (opp == j || opp == k) + continue; + opp_index = d->edges[opp] - g->edges; + if (state->lines[opp_index] == LINE_UNKNOWN) { + solver_set_line(sstate, opp_index, + LINE_YES); + diff = min(diff, DIFF_EASY); + } + } + } else if (unknown == 4) { + /* Exactly one of opposite UNKNOWNS is YES. We've + * already set atmostone, so set atleastone as + * well. + */ + if (dline_set_opp_atleastone(sstate, d, j)) + diff = min(diff, DIFF_NORMAL); + } + } + } + } + } } + return diff; } - -static int game_states_equal(const game_state *state1, - const game_state *state2) +static int linedsf_deductions(solver_state *sstate) { - /* This deliberately doesn't check _all_ fields, just the ones that make a - * game state 'interesting' from the POV of the solver */ - /* XXX review this */ - if (state1 == state2) - return 1; + game_state *state = sstate->state; + grid *g = state->game_grid; + char *dlines = sstate->dlines; + int i; + int diff = DIFF_MAX; + int diff_tmp; - if (!state1 || !state2) - return 0; + /* ------ Face deductions ------ */ - if (state1->w != state2->w || state1->h != state2->h) - return 0; + /* A fully-general linedsf deduction seems overly complicated + * (I suspect the problem is NP-complete, though in practice it might just + * be doable because faces are limited in size). + * For simplicity, we only consider *pairs* of LINE_UNKNOWNS that are + * known to be identical. If setting them both to YES (or NO) would break + * the clue, set them to NO (or YES). */ - if (memcmp(state1->hl, state2->hl, HL_COUNT(state1))) - return 0; + for (i = 0; i < g->num_faces; i++) { + int N, yes, no, unknown; + int clue; - if (memcmp(state1->vl, state2->vl, VL_COUNT(state1))) - return 0; + if (sstate->face_solved[i]) + continue; + clue = state->clues[i]; + if (clue < 0) + continue; - return 1; -} + N = g->faces[i].order; + yes = sstate->face_yes_count[i]; + if (yes + 1 == clue) { + if (face_setall_identical(sstate, i, LINE_NO)) + diff = min(diff, DIFF_EASY); + } + no = sstate->face_no_count[i]; + if (no + 1 == N - clue) { + if (face_setall_identical(sstate, i, LINE_YES)) + diff = min(diff, DIFF_EASY); + } -static int solver_states_equal(const solver_state *sstate1, - const solver_state *sstate2) -{ - if (!sstate1) { - if (!sstate2) - return TRUE; - else - return FALSE; - } - - if (!game_states_equal(sstate1->state, sstate2->state)) { - return 0; + /* Reload YES count, it might have changed */ + yes = sstate->face_yes_count[i]; + unknown = N - no - yes; + + /* Deductions with small number of LINE_UNKNOWNs, based on overall + * parity of lines. */ + diff_tmp = parity_deductions(sstate, g->faces[i].edges, + (clue - yes) % 2, unknown); + diff = min(diff, diff_tmp); } - /* XXX fields missing, needs review */ - /* XXX we're deliberately not looking at solver_state as it's only a cache */ + /* ------ Dot deductions ------ */ + for (i = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots + i; + int N = d->order; + int j; + int yes, no, unknown; + /* Go through dlines, and do any dline<->linedsf deductions wherever + * we find two UNKNOWNS. */ + for (j = 0; j < N; j++) { + int dline_index = dline_index_from_dot(g, d, j); + int line1_index; + int line2_index; + int can1, can2, inv1, inv2; + int j2; + line1_index = d->edges[j] - g->edges; + if (state->lines[line1_index] != LINE_UNKNOWN) + continue; + j2 = j + 1; + if (j2 == N) j2 = 0; + line2_index = d->edges[j2] - g->edges; + if (state->lines[line2_index] != LINE_UNKNOWN) + continue; + /* Infer dline flags from linedsf */ + can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1); + can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2); + if (can1 == can2 && inv1 != inv2) { + /* These are opposites, so set dline atmostone/atleastone */ + if (set_atmostone(dlines, dline_index)) + diff = min(diff, DIFF_NORMAL); + if (set_atleastone(dlines, dline_index)) + diff = min(diff, DIFF_NORMAL); + continue; + } + /* Infer linedsf from dline flags */ + if (is_atmostone(dlines, dline_index) + && is_atleastone(dlines, dline_index)) { + if (merge_lines(sstate, line1_index, line2_index, 1)) + diff = min(diff, DIFF_HARD); + } + } - if (memcmp(sstate1->dot_atleastone, sstate2->dot_atleastone, - DOT_COUNT(sstate1->state))) { - return 0; + /* Deductions with small number of LINE_UNKNOWNs, based on overall + * parity of lines. */ + yes = sstate->dot_yes_count[i]; + no = sstate->dot_no_count[i]; + unknown = N - yes - no; + diff_tmp = parity_deductions(sstate, d->edges, + yes % 2, unknown); + diff = min(diff, diff_tmp); } - if (memcmp(sstate1->dot_atmostone, sstate2->dot_atmostone, - DOT_COUNT(sstate1->state))) { - return 0; - } + /* ------ Edge dsf deductions ------ */ - /* handle dline_identical here */ + /* If the state of a line is known, deduce the state of its canonical line + * too, and vice versa. */ + for (i = 0; i < g->num_edges; i++) { + int can, inv; + enum line_state s; + can = edsf_canonify(sstate->linedsf, i, &inv); + if (can == i) + continue; + s = sstate->state->lines[can]; + if (s != LINE_UNKNOWN) { + if (solver_set_line(sstate, i, inv ? OPP(s) : s)) + diff = min(diff, DIFF_EASY); + } else { + s = sstate->state->lines[i]; + if (s != LINE_UNKNOWN) { + if (solver_set_line(sstate, can, inv ? OPP(s) : s)) + diff = min(diff, DIFF_EASY); + } + } + } - return 1; + return diff; } -static void dot_setall_dlines(solver_state *sstate, enum dline dl, int i, int j, - enum line_state line_old, enum line_state line_new) +static int loop_deductions(solver_state *sstate) { + int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0; game_state *state = sstate->state; + grid *g = state->game_grid; + int shortest_chainlen = g->num_dots; + int loop_found = FALSE; + int dots_connected; + int progress = FALSE; + int i; - /* First line in dline */ - switch (dl) { - case DLINE_UL: - case DLINE_UR: - case DLINE_VERT: - if (j > 0 && ABOVE_DOT(state, i, j) == line_old) - LV_ABOVE_DOT(state, i, j) = line_new; - break; - case DLINE_DL: - case DLINE_DR: - if (j <= (state)->h && BELOW_DOT(state, i, j) == line_old) - LV_BELOW_DOT(state, i, j) = line_new; - break; - case DLINE_HORIZ: - if (i > 0 && LEFTOF_DOT(state, i, j) == line_old) - LV_LEFTOF_DOT(state, i, j) = line_new; - break; - } - - /* Second line in dline */ - switch (dl) { - case DLINE_UL: - case DLINE_DL: - if (i > 0 && LEFTOF_DOT(state, i, j) == line_old) - LV_LEFTOF_DOT(state, i, j) = line_new; - break; - case DLINE_UR: - case DLINE_DR: - case DLINE_HORIZ: - if (i <= (state)->w && RIGHTOF_DOT(state, i, j) == line_old) - LV_RIGHTOF_DOT(state, i, j) = line_new; - break; - case DLINE_VERT: - if (j <= (state)->h && BELOW_DOT(state, i, j) == line_old) - LV_BELOW_DOT(state, i, j) = line_new; - break; - } -} - -static void update_solver_status(solver_state *sstate) -{ - if (sstate->solver_status == SOLVER_INCOMPLETE) { - switch (loop_status(sstate->state)) { - case LOOP_NONE: - sstate->solver_status = SOLVER_INCOMPLETE; - break; - case LOOP_SOLN: - if (sstate->solver_status != SOLVER_AMBIGUOUS) - sstate->solver_status = SOLVER_SOLVED; - break; - case LOOP_NOT_SOLN: - sstate->solver_status = SOLVER_MISTAKE; - break; + /* + * Go through the grid and update for all the new edges. + * Since merge_dots() is idempotent, the simplest way to + * do this is just to update for _all_ the edges. + * Also, while we're here, we count the edges. + */ + for (i = 0; i < g->num_edges; i++) { + if (state->lines[i] == LINE_YES) { + loop_found |= merge_dots(sstate, i); + edgecount++; } } -} - - -/* This will return a dynamically allocated solver_state containing the (more) - * solved grid */ -static solver_state *solve_game_rec(const solver_state *sstate_start) -{ - int i, j; - int current_yes, current_no, desired; - solver_state *sstate, *sstate_saved, *sstate_tmp; - int t; -/* char *text; */ - solver_state *sstate_rec_solved; - int recursive_soln_count; - -#if 0 - printf("solve_game_rec: recursion_remaining = %d\n", - sstate_start->recursion_remaining); -#endif - sstate = dup_solver_state((solver_state *)sstate_start); + /* + * Count the clues, count the satisfied clues, and count the + * satisfied-minus-one clues. + */ + for (i = 0; i < g->num_faces; i++) { + int c = state->clues[i]; + if (c >= 0) { + int o = sstate->face_yes_count[i]; + if (o == c) + satclues++; + else if (o == c-1) + sm1clues++; + clues++; + } + } -#if 0 - text = game_text_format(sstate->state); - printf("%s\n", text); - sfree(text); -#endif - -#define RETURN_IF_SOLVED \ - do { \ - update_solver_status(sstate); \ - if (sstate->solver_status != SOLVER_INCOMPLETE) { \ - free_solver_state(sstate_saved); \ - return sstate; \ - } \ - } while (0) - - sstate_saved = NULL; - RETURN_IF_SOLVED; - -nonrecursive_solver: - - while (1) { - sstate_saved = dup_solver_state(sstate); - - /* First we do the 'easy' work, that might cause concrete results */ - - /* Per-square deductions */ - for (j = 0; j < sstate->state->h; ++j) { - for (i = 0; i < sstate->state->w; ++i) { - /* Begin rules that look at the clue (if there is one) */ - desired = CLUE_AT(sstate->state, i, j); - if (desired == ' ') - continue; - desired = desired - '0'; - current_yes = square_order(sstate->state, i, j, LINE_YES); - current_no = square_order(sstate->state, i, j, LINE_NO); - - if (desired <= current_yes) { - square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO); - continue; - } - - if (4 - desired <= current_no) { - square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES); - } - } - } - - RETURN_IF_SOLVED; - - /* Per-dot deductions */ - for (j = 0; j < sstate->state->h + 1; ++j) { - for (i = 0; i < sstate->state->w + 1; ++i) { - switch (dot_order(sstate->state, i, j, LINE_YES)) { - case 0: - if (dot_order(sstate->state, i, j, LINE_NO) == 3) { - dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO); - } - break; - case 1: - switch (dot_order(sstate->state, i, j, LINE_NO)) { -#define H1(dline, dir1_dot, dir2_dot, dot_howmany) \ - if (dir1_dot(sstate->state, i, j) == LINE_UNKNOWN) { \ - if (dir2_dot(sstate->state, i, j) == LINE_UNKNOWN){ \ - sstate->dot_howmany \ - [i + (sstate->state->w + 1) * j] |= 1<state, i, j, - LINE_UNKNOWN, LINE_YES); - break; - } - break; - case 2: - case 3: - dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO); - } -#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \ - if (sstate->dot_atleastone \ - [i + (sstate->state->w + 1) * j] & 1<dot_atmostone \ - [i + (sstate->state->w + 1) * j] |= 1<state->h; ++j) { - for (i = 0; i < sstate->state->w; ++i) { -#define H1(dline, dir1_sq, dir2_sq, a, b, dot_howmany, line_query, line_set) \ - if (sstate->dot_howmany[i+a + (sstate->state->w + 1) * (j+b)] &\ - 1<state, i, j); \ - if (t == line_query) \ - dir2_sq(sstate->state, i, j) = line_set; \ - else { \ - t = dir2_sq(sstate->state, i, j); \ - if (t == line_query) \ - dir1_sq(sstate->state, i, j) = line_set; \ - } \ - } -#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \ - H1(dline, dir1_sq, dir2_sq, a, b, dot_atmostone, \ - LINE_YES, LINE_NO) - /* If at most one of the DLINE is on, and one is definitely on, - * set the other to definitely off */ - SQUARE_DLINES; -#undef HANDLE_DLINE - -#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \ - H1(dline, dir1_sq, dir2_sq, a, b, dot_atleastone, \ - LINE_NO, LINE_YES) - /* If at least one of the DLINE is on, and one is definitely - * off, set the other to definitely on */ - SQUARE_DLINES; -#undef HANDLE_DLINE -#undef H1 - - switch (CLUE_AT(sstate->state, i, j)) { - case '0': - case '1': -#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \ - /* At most one of any DLINE can be set */ \ - sstate->dot_atmostone \ - [i+a + (sstate->state->w + 1) * (j+b)] |= 1<dot_atleastone \ - [i+a + (sstate->state->w + 1) * (j+b)] & \ - 1<dot_at1one \ - [i+a + (sstate->state->w + 1) * (j+b)] & \ - 1<dot_at2one \ - [i+(1-a) + (sstate->state->w + 1) * (j+(1-b))] |= \ - 1<dot_atleastone \ - [i+a + (sstate->state->w + 1) * (j+b)] |= 1<dot_atmostone \ - [i+a + (sstate->state->w + 1) * (j+b)] & \ - 1<state->h; ++j) { - for (i = 0; i <= sstate->state->w; ++i) { - if (RIGHTOF_DOT(sstate->state, i, j) == LINE_YES) { - merge_dots(sstate, i, j, i+1, j); - edgecount++; - } - if (BELOW_DOT(sstate->state, i, j) == LINE_YES) { - merge_dots(sstate, i, j, i, j+1); - edgecount++; - } - - if (CLUE_AT(sstate->state, i, j) != ' ') { - int c = CLUE_AT(sstate->state, i, j) - '0'; - int o = square_order(sstate->state, i, j, LINE_YES); - if (o == c) - satclues++; - else if (o == c-1) - sm1clues++; - clues++; - } - } - } - - /* - * Now go through looking for LINE_UNKNOWN edges which - * connect two dots that are already in the same - * equivalence class. If we find one, test to see if the - * loop it would create is a solution. - */ - for (j = 0; j <= sstate->state->h; ++j) { - for (i = 0; i <= sstate->state->w; ++i) { - for (d = 0; d < 2; d++) { - int i2, j2, eqclass, val; - - if (d == 0) { - if (RIGHTOF_DOT(sstate->state, i, j) != - LINE_UNKNOWN) - continue; - i2 = i+1; - j2 = j; - } else { - if (BELOW_DOT(sstate->state, i, j) != - LINE_UNKNOWN) - continue; - i2 = i; - j2 = j+1; - } - - eqclass = dsf_canonify(sstate->dotdsf, - j * (sstate->state->w+1) + i); - if (eqclass != dsf_canonify(sstate->dotdsf, - j2 * (sstate->state->w+1) + - i2)) - continue; - - val = LINE_NO; /* loop is bad until proven otherwise */ - - /* - * This edge would form a loop. Next - * question: how long would the loop be? - * Would it equal the total number of edges - * (plus the one we'd be adding if we added - * it)? - */ - if (sstate->looplen[eqclass] == edgecount + 1) { - int sm1_nearby; - int cx, cy; - - /* - * This edge would form a loop which - * took in all the edges in the entire - * grid. So now we need to work out - * whether it would be a valid solution - * to the puzzle, which means we have to - * check if it satisfies all the clues. - * This means that every clue must be - * either satisfied or satisfied-minus- - * 1, and also that the number of - * satisfied-minus-1 clues must be at - * most two and they must lie on either - * side of this edge. - */ - sm1_nearby = 0; - cx = i - (j2-j); - cy = j - (i2-i); - if (CLUE_AT(sstate->state, cx,cy) != ' ' && - square_order(sstate->state, cx,cy, LINE_YES) == - CLUE_AT(sstate->state, cx,cy) - '0' - 1) - sm1_nearby++; - if (CLUE_AT(sstate->state, i, j) != ' ' && - square_order(sstate->state, i, j, LINE_YES) == - CLUE_AT(sstate->state, i, j) - '0' - 1) - sm1_nearby++; - if (sm1clues == sm1_nearby && - sm1clues + satclues == clues) - val = LINE_YES; /* loop is good! */ - } - - /* - * Right. Now we know that adding this edge - * would form a loop, and we know whether - * that loop would be a viable solution or - * not. - * - * If adding this edge produces a solution, - * then we know we've found _a_ solution but - * we don't know that it's _the_ solution - - * if it were provably the solution then - * we'd have deduced this edge some time ago - * without the need to do loop detection. So - * in this state we return SOLVER_AMBIGUOUS, - * which has the effect that hitting Solve - * on a user-provided puzzle will fill in a - * solution but using the solver to - * construct new puzzles won't consider this - * a reasonable deduction for the user to - * make. - */ - if (d == 0) - LV_RIGHTOF_DOT(sstate->state, i, j) = val; - else - LV_BELOW_DOT(sstate->state, i, j) = val; - if (val == LINE_YES) { - sstate->solver_status = SOLVER_AMBIGUOUS; - goto finished_loop_checking; - } - } - } - } - - finished_loop_checking: - - RETURN_IF_SOLVED; - } - - if (solver_states_equal(sstate, sstate_saved)) { - /* Solver has stopped making progress so we terminate */ - free_solver_state(sstate_saved); - break; - } - - free_solver_state(sstate_saved); - } - - if (sstate->solver_status == SOLVER_SOLVED || - sstate->solver_status == SOLVER_AMBIGUOUS) { - /* s/LINE_UNKNOWN/LINE_NO/g */ - array_setall(sstate->state->hl, LINE_UNKNOWN, LINE_NO, - HL_COUNT(sstate->state)); - array_setall(sstate->state->vl, LINE_UNKNOWN, LINE_NO, - VL_COUNT(sstate->state)); - return sstate; - } - - /* Perform recursive calls */ - if (sstate->recursion_remaining) { - sstate->recursion_remaining--; - - sstate_saved = dup_solver_state(sstate); - - recursive_soln_count = 0; - sstate_rec_solved = NULL; - - /* Memory management: - * sstate_saved won't be modified but needs to be freed when we have - * finished with it. - * sstate is expected to contain our 'best' solution by the time we - * finish this section of code. It's the thing we'll try adding lines - * to, seeing if they make it more solvable. - * If sstate_rec_solved is non-NULL, it will supersede sstate - * eventually. sstate_tmp should not hold a value persistently. - */ - - /* NB SOLVER_AMBIGUOUS is like SOLVER_SOLVED except the solver is aware - * of the possibility of additional solutions. So as soon as we have a - * SOLVER_AMBIGUOUS we can safely propagate it back to our caller, but - * if we get a SOLVER_SOLVED we want to keep trying in case we find - * further solutions and have to mark it ambiguous. - */ - -#define DO_RECURSIVE_CALL(dir_dot) \ - if (dir_dot(sstate->state, i, j) == LINE_UNKNOWN) { \ - debug(("Trying " #dir_dot " at [%d,%d]\n", i, j)); \ - LV_##dir_dot(sstate->state, i, j) = LINE_YES; \ - sstate_tmp = solve_game_rec(sstate); \ - switch (sstate_tmp->solver_status) { \ - case SOLVER_AMBIGUOUS: \ - debug(("Solver ambiguous, returning\n")); \ - sstate_rec_solved = sstate_tmp; \ - goto finished_recursion; \ - case SOLVER_SOLVED: \ - switch (++recursive_soln_count) { \ - case 1: \ - debug(("One solution found\n")); \ - sstate_rec_solved = sstate_tmp; \ - break; \ - case 2: \ - debug(("Ambiguous solutions found\n")); \ - free_solver_state(sstate_tmp); \ - sstate_rec_solved->solver_status = SOLVER_AMBIGUOUS;\ - goto finished_recursion; \ - default: \ - assert(!"recursive_soln_count out of range"); \ - break; \ - } \ - break; \ - case SOLVER_MISTAKE: \ - debug(("Non-solution found\n")); \ - free_solver_state(sstate_tmp); \ - free_solver_state(sstate_saved); \ - LV_##dir_dot(sstate->state, i, j) = LINE_NO; \ - goto nonrecursive_solver; \ - case SOLVER_INCOMPLETE: \ - debug(("Recursive step inconclusive\n")); \ - free_solver_state(sstate_tmp); \ - break; \ - } \ - free_solver_state(sstate); \ - sstate = dup_solver_state(sstate_saved); \ - } - - for (j = 0; j < sstate->state->h + 1; ++j) { - for (i = 0; i < sstate->state->w + 1; ++i) { - /* Only perform recursive calls on 'loose ends' */ - if (dot_order(sstate->state, i, j, LINE_YES) == 1) { - if (LEFTOF_DOT(sstate->state, i, j) == LINE_UNKNOWN) - DO_RECURSIVE_CALL(LEFTOF_DOT); - if (RIGHTOF_DOT(sstate->state, i, j) == LINE_UNKNOWN) - DO_RECURSIVE_CALL(RIGHTOF_DOT); - if (ABOVE_DOT(sstate->state, i, j) == LINE_UNKNOWN) - DO_RECURSIVE_CALL(ABOVE_DOT); - if (BELOW_DOT(sstate->state, i, j) == LINE_UNKNOWN) - DO_RECURSIVE_CALL(BELOW_DOT); - } - } - } - -finished_recursion: - - if (sstate_rec_solved) { - free_solver_state(sstate); - sstate = sstate_rec_solved; - } - } - - return sstate; -} - -/* XXX bits of solver that may come in handy one day */ -#if 0 -#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \ - /* dline from this dot that's entirely unknown must have - * both lines identical */ \ - if (dir1_dot(sstate->state, i, j) == LINE_UNKNOWN && \ - dir2_dot(sstate->state, i, j) == LINE_UNKNOWN) { \ - sstate->dline_identical[i + (sstate->state->w + 1) * j] |= \ - 1<dline_identical[i + - (sstate->state->w + 1) * j] &\ - 1<state, i, j); \ - if (t != LINE_UNKNOWN) \ - dir2_dot(sstate->state, i, j) = t; \ - else { \ - t = dir2_dot(sstate->state, i, j); \ - if (t != LINE_UNKNOWN) \ - dir1_dot(sstate->state, i, j) = t; \ - } \ - } \ - DOT_DLINES; -#undef HANDLE_DLINE -#endif + for (i = 0; i < g->num_dots; ++i) { + dots_connected = + sstate->looplen[dsf_canonify(sstate->dotdsf, i)]; + if (dots_connected > 1) + shortest_chainlen = min(shortest_chainlen, dots_connected); + } -#if 0 -#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \ - if (sstate->dline_identical[i+a + \ - (sstate->state->w + 1) * (j+b)] &\ - 1<state, i, j) = LINE_YES; \ - dir2_sq(sstate->state, i, j) = LINE_YES; \ - } - /* If two lines are the same they must be on */ - SQUARE_DLINES; -#undef HANDLE_DLINE -#endif + assert(sstate->solver_status == SOLVER_INCOMPLETE); + if (satclues == clues && shortest_chainlen == edgecount) { + sstate->solver_status = SOLVER_SOLVED; + /* This discovery clearly counts as progress, even if we haven't + * just added any lines or anything */ + progress = TRUE; + goto finished_loop_deductionsing; + } -#if 0 -#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \ - if (sstate->dot_atmostone[i+a + (sstate->state->w + 1) * (j+b)] & \ - 1<state, i, j, LINE_UNKNOWN) - 1 == \ - CLUE_AT(sstate->state, i, j) - '0') { \ - square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES); \ - /* XXX the following may overwrite known data! */ \ - dir1_sq(sstate->state, i, j) = LINE_UNKNOWN; \ - dir2_sq(sstate->state, i, j) = LINE_UNKNOWN; \ - } \ - } - SQUARE_DLINES; -#undef HANDLE_DLINE -#endif + /* + * Now go through looking for LINE_UNKNOWN edges which + * connect two dots that are already in the same + * equivalence class. If we find one, test to see if the + * loop it would create is a solution. + */ + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + int d1 = e->dot1 - g->dots; + int d2 = e->dot2 - g->dots; + int eqclass, val; + if (state->lines[i] != LINE_UNKNOWN) + continue; -#if 0 -#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \ - if (sstate->dline_identical[i+a + - (sstate->state->w + 1) * (j+b)] &\ - 1<state, i, j) = LINE_NO; \ - dir2_sq(sstate->state, i, j) = LINE_NO; \ - } - /* If two lines are the same they must be off */ - SQUARE_DLINES; -#undef HANDLE_DLINE -#endif + eqclass = dsf_canonify(sstate->dotdsf, d1); + if (eqclass != dsf_canonify(sstate->dotdsf, d2)) + continue; -static char *solve_game(game_state *state, game_state *currstate, - char *aux, char **error) -{ - char *soln = NULL; - solver_state *sstate, *new_sstate; + val = LINE_NO; /* loop is bad until proven otherwise */ - sstate = new_solver_state(state); - new_sstate = solve_game_rec(sstate); + /* + * This edge would form a loop. Next + * question: how long would the loop be? + * Would it equal the total number of edges + * (plus the one we'd be adding if we added + * it)? + */ + if (sstate->looplen[eqclass] == edgecount + 1) { + int sm1_nearby; + + /* + * This edge would form a loop which + * took in all the edges in the entire + * grid. So now we need to work out + * whether it would be a valid solution + * to the puzzle, which means we have to + * check if it satisfies all the clues. + * This means that every clue must be + * either satisfied or satisfied-minus- + * 1, and also that the number of + * satisfied-minus-1 clues must be at + * most two and they must lie on either + * side of this edge. + */ + sm1_nearby = 0; + if (e->face1) { + int f = e->face1 - g->faces; + int c = state->clues[f]; + if (c >= 0 && sstate->face_yes_count[f] == c - 1) + sm1_nearby++; + } + if (e->face2) { + int f = e->face2 - g->faces; + int c = state->clues[f]; + if (c >= 0 && sstate->face_yes_count[f] == c - 1) + sm1_nearby++; + } + if (sm1clues == sm1_nearby && + sm1clues + satclues == clues) { + val = LINE_YES; /* loop is good! */ + } + } - if (new_sstate->solver_status == SOLVER_SOLVED) { - soln = encode_solve_move(new_sstate->state); - } else if (new_sstate->solver_status == SOLVER_AMBIGUOUS) { - soln = encode_solve_move(new_sstate->state); - /**error = "Solver found ambiguous solutions"; */ - } else { - soln = encode_solve_move(new_sstate->state); - /**error = "Solver failed"; */ + /* + * Right. Now we know that adding this edge + * would form a loop, and we know whether + * that loop would be a viable solution or + * not. + * + * If adding this edge produces a solution, + * then we know we've found _a_ solution but + * we don't know that it's _the_ solution - + * if it were provably the solution then + * we'd have deduced this edge some time ago + * without the need to do loop detection. So + * in this state we return SOLVER_AMBIGUOUS, + * which has the effect that hitting Solve + * on a user-provided puzzle will fill in a + * solution but using the solver to + * construct new puzzles won't consider this + * a reasonable deduction for the user to + * make. + */ + progress = solver_set_line(sstate, i, val); + assert(progress == TRUE); + if (val == LINE_YES) { + sstate->solver_status = SOLVER_AMBIGUOUS; + goto finished_loop_deductionsing; + } } - free_solver_state(new_sstate); - free_solver_state(sstate); - - return soln; + finished_loop_deductionsing: + return progress ? DIFF_EASY : DIFF_MAX; } -static char *game_text_format(game_state *state) +/* This will return a dynamically allocated solver_state containing the (more) + * solved grid */ +static solver_state *solve_game_rec(const solver_state *sstate_start) { - int i, j; - int len; - char *ret, *rp; + solver_state *sstate; - len = (2 * state->w + 2) * (2 * state->h + 1); - rp = ret = snewn(len + 1, char); + /* Index of the solver we should call next. */ + int i = 0; -#define DRAW_HL \ - switch (ABOVE_SQUARE(state, i, j)) { \ - case LINE_YES: \ - rp += sprintf(rp, " -"); \ - break; \ - case LINE_NO: \ - rp += sprintf(rp, " x"); \ - break; \ - case LINE_UNKNOWN: \ - rp += sprintf(rp, " "); \ - break; \ - default: \ - assert(!"Illegal line state for HL");\ - } - -#define DRAW_VL \ - switch (LEFTOF_SQUARE(state, i, j)) {\ - case LINE_YES: \ - rp += sprintf(rp, "|"); \ - break; \ - case LINE_NO: \ - rp += sprintf(rp, "x"); \ - break; \ - case LINE_UNKNOWN: \ - rp += sprintf(rp, " "); \ - break; \ - default: \ - assert(!"Illegal line state for VL");\ - } + /* As a speed-optimisation, we avoid re-running solvers that we know + * won't make any progress. This happens when a high-difficulty + * solver makes a deduction that can only help other high-difficulty + * solvers. + * For example: if a new 'dline' flag is set by dline_deductions, the + * trivial_deductions solver cannot do anything with this information. + * If we've already run the trivial_deductions solver (because it's + * earlier in the list), there's no point running it again. + * + * Therefore: if a solver is earlier in the list than "threshold_index", + * we don't bother running it if it's difficulty level is less than + * "threshold_diff". + */ + int threshold_diff = 0; + int threshold_index = 0; - for (j = 0; j < state->h; ++j) { - for (i = 0; i < state->w; ++i) { - DRAW_HL; + sstate = dup_solver_state(sstate_start); + + check_caches(sstate); + + while (i < NUM_SOLVERS) { + if (sstate->solver_status == SOLVER_MISTAKE) + return sstate; + if (sstate->solver_status == SOLVER_SOLVED || + sstate->solver_status == SOLVER_AMBIGUOUS) { + /* solver finished */ + break; } - rp += sprintf(rp, " \n"); - for (i = 0; i < state->w; ++i) { - DRAW_VL; - rp += sprintf(rp, "%c", (int)(CLUE_AT(state, i, j))); + + if ((solver_diffs[i] >= threshold_diff || i >= threshold_index) + && solver_diffs[i] <= sstate->diff) { + /* current_solver is eligible, so use it */ + int next_diff = solver_fns[i](sstate); + if (next_diff != DIFF_MAX) { + /* solver made progress, so use new thresholds and + * start again at top of list. */ + threshold_diff = next_diff; + threshold_index = i; + i = 0; + continue; + } } - DRAW_VL; - rp += sprintf(rp, "\n"); - } - for (i = 0; i < state->w; ++i) { - DRAW_HL; + /* current_solver is ineligible, or failed to make progress, so + * go to the next solver in the list */ + i++; } - rp += sprintf(rp, " \n"); - - assert(strlen(ret) == len); - return ret; -} -static game_ui *new_ui(game_state *state) -{ - return NULL; -} + if (sstate->solver_status == SOLVER_SOLVED || + sstate->solver_status == SOLVER_AMBIGUOUS) { + /* s/LINE_UNKNOWN/LINE_NO/g */ + array_setall(sstate->state->lines, LINE_UNKNOWN, LINE_NO, + sstate->state->game_grid->num_edges); + return sstate; + } -static void free_ui(game_ui *ui) -{ + return sstate; } -static char *encode_ui(game_ui *ui) +static char *solve_game(game_state *state, game_state *currstate, + char *aux, char **error) { - return NULL; -} + char *soln = NULL; + solver_state *sstate, *new_sstate; -static void decode_ui(game_ui *ui, char *encoding) -{ -} + sstate = new_solver_state(state, DIFF_MAX); + new_sstate = solve_game_rec(sstate); -static void game_changed_state(game_ui *ui, game_state *oldstate, - game_state *newstate) -{ + if (new_sstate->solver_status == SOLVER_SOLVED) { + soln = encode_solve_move(new_sstate->state); + } else if (new_sstate->solver_status == SOLVER_AMBIGUOUS) { + soln = encode_solve_move(new_sstate->state); + /**error = "Solver found ambiguous solutions"; */ + } else { + soln = encode_solve_move(new_sstate->state); + /**error = "Solver failed"; */ + } + + free_solver_state(new_sstate); + free_solver_state(sstate); + + return soln; } -struct game_drawstate { - int started; - int tilesize; - int flashing; - char *hl, *vl; -}; +/* ---------------------------------------------------------------------- + * Drawing and mouse-handling + */ -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, +static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds, int x, int y, int button) { - int hl_selected; - int i, j, p, q; + grid *g = state->game_grid; + grid_edge *e; + int i; char *ret, buf[80]; char button_char = ' '; enum line_state old_state; button &= ~MOD_MASK; - /* Around each line is a diamond-shaped region where points within that - * region are closer to this line than any other. We assume any click - * within a line's diamond was meant for that line. It would all be a lot - * simpler if the / and % operators respected modulo arithmetic properly - * for negative numbers. */ - - x -= BORDER; - y -= BORDER; - - /* Get the coordinates of the square the click was in */ - i = (x + TILE_SIZE) / TILE_SIZE - 1; - j = (y + TILE_SIZE) / TILE_SIZE - 1; - - /* Get the precise position inside square [i,j] */ - p = (x + TILE_SIZE) % TILE_SIZE; - q = (y + TILE_SIZE) % TILE_SIZE; - - /* After this bit of magic [i,j] will correspond to the point either above - * or to the left of the line selected */ - if (p > q) { - if (TILE_SIZE - p > q) { - hl_selected = TRUE; - } else { - hl_selected = FALSE; - ++i; - } - } else { - if (TILE_SIZE - q > p) { - hl_selected = FALSE; - } else { - hl_selected = TRUE; - ++j; - } - } + /* Convert mouse-click (x,y) to grid coordinates */ + x -= BORDER(ds->tilesize); + y -= BORDER(ds->tilesize); + x = x * g->tilesize / ds->tilesize; + y = y * g->tilesize / ds->tilesize; + x += g->lowest_x; + y += g->lowest_y; - if (i < 0 || j < 0) + e = grid_nearest_edge(g, x, y); + if (e == NULL) return NULL; - if (hl_selected) { - if (i >= state->w || j >= state->h + 1) - return NULL; - } else { - if (i >= state->w + 1 || j >= state->h) - return NULL; - } + i = e - g->edges; /* I think it's only possible to play this game with mouse clicks, sorry */ /* Maybe will add mouse drag support some time */ - if (hl_selected) - old_state = RIGHTOF_DOT(state, i, j); - else - old_state = BELOW_DOT(state, i, j); + old_state = state->lines[i]; switch (button) { - case LEFT_BUTTON: - switch (old_state) { - case LINE_UNKNOWN: - button_char = 'y'; - break; - case LINE_YES: - case LINE_NO: - button_char = 'u'; - break; - } - break; - case MIDDLE_BUTTON: - button_char = 'u'; - break; - case RIGHT_BUTTON: - switch (old_state) { - case LINE_UNKNOWN: - button_char = 'n'; - break; - case LINE_NO: - case LINE_YES: - button_char = 'u'; - break; - } - break; - default: - return NULL; + case LEFT_BUTTON: + switch (old_state) { + case LINE_UNKNOWN: + button_char = 'y'; + break; + case LINE_YES: +#ifdef STYLUS_BASED + button_char = 'n'; + break; +#endif + case LINE_NO: + button_char = 'u'; + break; + } + break; + case MIDDLE_BUTTON: + button_char = 'u'; + break; + case RIGHT_BUTTON: + switch (old_state) { + case LINE_UNKNOWN: + button_char = 'n'; + break; + case LINE_NO: +#ifdef STYLUS_BASED + button_char = 'y'; + break; +#endif + case LINE_YES: + button_char = 'u'; + break; + } + break; + default: + return NULL; } - sprintf(buf, "%d,%d%c%c", i, j, (int)(hl_selected ? 'h' : 'v'), (int)button_char); + sprintf(buf, "%d%c", i, (int)button_char); ret = dupstr(buf); return ret; @@ -2180,7 +2890,7 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, static game_state *execute_move(game_state *state, char *move) { - int i, j; + int i; game_state *newstate = dup_game(state); if (move[0] == 'S') { @@ -2190,145 +2900,33 @@ static game_state *execute_move(game_state *state, char *move) while (*move) { i = atoi(move); - move = strchr(move, ','); - if (!move) + if (i < 0 || i >= newstate->game_grid->num_edges) goto fail; - j = atoi(++move); move += strspn(move, "1234567890"); switch (*(move++)) { - case 'h': - if (i >= newstate->w || j > newstate->h) - goto fail; - switch (*(move++)) { - case 'y': - LV_RIGHTOF_DOT(newstate, i, j) = LINE_YES; - break; - case 'n': - LV_RIGHTOF_DOT(newstate, i, j) = LINE_NO; - break; - case 'u': - LV_RIGHTOF_DOT(newstate, i, j) = LINE_UNKNOWN; - break; - default: - goto fail; - } - break; - case 'v': - if (i > newstate->w || j >= newstate->h) - goto fail; - switch (*(move++)) { - case 'y': - LV_BELOW_DOT(newstate, i, j) = LINE_YES; - break; - case 'n': - LV_BELOW_DOT(newstate, i, j) = LINE_NO; - break; - case 'u': - LV_BELOW_DOT(newstate, i, j) = LINE_UNKNOWN; - break; - default: - goto fail; - } - break; - default: - goto fail; + case 'y': + newstate->lines[i] = LINE_YES; + break; + case 'n': + newstate->lines[i] = LINE_NO; + break; + case 'u': + newstate->lines[i] = LINE_UNKNOWN; + break; + default: + goto fail; } } /* * Check for completion. */ - i = 0; /* placate optimiser */ - for (j = 0; j <= newstate->h; j++) { - for (i = 0; i < newstate->w; i++) - if (LV_RIGHTOF_DOT(newstate, i, j) == LINE_YES) - break; - if (i < newstate->w) - break; - } - if (j <= newstate->h) { - int prevdir = 'R'; - int x = i, y = j; - int looplen, count; - - /* - * We've found a horizontal edge at (i,j). Follow it round - * to see if it's part of a loop. - */ - looplen = 0; - while (1) { - int order = dot_order(newstate, x, y, LINE_YES); - if (order != 2) - goto completion_check_done; - - if (LEFTOF_DOT(newstate, x, y) == LINE_YES && prevdir != 'L') { - x--; - prevdir = 'R'; - } else if (RIGHTOF_DOT(newstate, x, y) == LINE_YES && - prevdir != 'R') { - x++; - prevdir = 'L'; - } else if (ABOVE_DOT(newstate, x, y) == LINE_YES && - prevdir != 'U') { - y--; - prevdir = 'D'; - } else if (BELOW_DOT(newstate, x, y) == LINE_YES && - prevdir != 'D') { - y++; - prevdir = 'U'; - } else { - assert(!"Can't happen"); /* dot_order guarantees success */ - } - - looplen++; - - if (x == i && y == j) - break; - } - - if (x != i || y != j || looplen == 0) - goto completion_check_done; - - /* - * We've traced our way round a loop, and we know how many - * line segments were involved. Count _all_ the line - * segments in the grid, to see if the loop includes them - * all. - */ - count = 0; - for (j = 0; j <= newstate->h; j++) - for (i = 0; i <= newstate->w; i++) - count += ((RIGHTOF_DOT(newstate, i, j) == LINE_YES) + - (BELOW_DOT(newstate, i, j) == LINE_YES)); - assert(count >= looplen); - if (count != looplen) - goto completion_check_done; - - /* - * The grid contains one closed loop and nothing else. - * Check that all the clues are satisfied. - */ - for (j = 0; j < newstate->h; ++j) { - for (i = 0; i < newstate->w; ++i) { - int n = CLUE_AT(newstate, i, j); - if (n != ' ') { - if (square_order(newstate, i, j, LINE_YES) != n - '0') { - goto completion_check_done; - } - } - } - } + if (check_completion(newstate)) + newstate->solved = TRUE; - /* - * Completed! - */ - newstate->solved = TRUE; - } - -completion_check_done: return newstate; -fail: + fail: free_game(newstate); return NULL; } @@ -2337,242 +2935,354 @@ fail: * Drawing routines. */ -#define SIZE(d) ((d) * TILE_SIZE + 2 * BORDER + 1) +/* Convert from grid coordinates to screen coordinates */ +static void grid_to_screen(const game_drawstate *ds, const grid *g, + int grid_x, int grid_y, int *x, int *y) +{ + *x = grid_x - g->lowest_x; + *y = grid_y - g->lowest_y; + *x = *x * ds->tilesize / g->tilesize; + *y = *y * ds->tilesize / g->tilesize; + *x += BORDER(ds->tilesize); + *y += BORDER(ds->tilesize); +} -static void game_compute_size(game_params *params, int tilesize, - int *x, int *y) +/* Returns (into x,y) position of centre of face for rendering the text clue. + */ +static void face_text_pos(const game_drawstate *ds, const grid *g, + grid_face *f, int *xret, int *yret) { - struct { int tilesize; } ads, *ds = &ads; - ads.tilesize = tilesize; + int faceindex = f - g->faces; + + /* + * Return the cached position for this face, if we've already + * worked it out. + */ + if (ds->textx[faceindex] >= 0) { + *xret = ds->textx[faceindex]; + *yret = ds->texty[faceindex]; + return; + } + + /* + * Otherwise, use the incentre computed by grid.c and convert it + * to screen coordinates. + */ + grid_find_incentre(f); + grid_to_screen(ds, g, f->ix, f->iy, + &ds->textx[faceindex], &ds->texty[faceindex]); - *x = SIZE(params->w); - *y = SIZE(params->h); + *xret = ds->textx[faceindex]; + *yret = ds->texty[faceindex]; } -static void game_set_size(drawing *dr, game_drawstate *ds, - game_params *params, int tilesize) +static void face_text_bbox(game_drawstate *ds, grid *g, grid_face *f, + int *x, int *y, int *w, int *h) { - ds->tilesize = tilesize; + int xx, yy; + face_text_pos(ds, g, f, &xx, &yy); + + /* There seems to be a certain amount of trial-and-error involved + * in working out the correct bounding-box for the text. */ + + *x = xx - ds->tilesize/4 - 1; + *y = yy - ds->tilesize/4 - 3; + *w = ds->tilesize/2 + 2; + *h = ds->tilesize/2 + 5; } -static float *game_colours(frontend *fe, game_state *state, int *ncolours) +static void game_redraw_clue(drawing *dr, game_drawstate *ds, + game_state *state, int i) { - float *ret = snewn(4 * NCOLOURS, float); + grid *g = state->game_grid; + grid_face *f = g->faces + i; + int x, y; + char c[3]; - frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + if (state->clues[i] < 10) { + c[0] = CLUE2CHAR(state->clues[i]); + c[1] = '\0'; + } else { + sprintf(c, "%d", state->clues[i]); + } - ret[COL_FOREGROUND * 3 + 0] = 0.0F; - ret[COL_FOREGROUND * 3 + 1] = 0.0F; - ret[COL_FOREGROUND * 3 + 2] = 0.0F; + face_text_pos(ds, g, f, &x, &y); + draw_text(dr, x, y, + FONT_VARIABLE, ds->tilesize/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, + ds->clue_error[i] ? COL_MISTAKE : + ds->clue_satisfied[i] ? COL_SATISFIED : COL_FOREGROUND, c); +} - ret[COL_HIGHLIGHT * 3 + 0] = 1.0F; - ret[COL_HIGHLIGHT * 3 + 1] = 1.0F; - ret[COL_HIGHLIGHT * 3 + 2] = 1.0F; +static void edge_bbox(game_drawstate *ds, grid *g, grid_edge *e, + int *x, int *y, int *w, int *h) +{ + int x1 = e->dot1->x; + int y1 = e->dot1->y; + int x2 = e->dot2->x; + int y2 = e->dot2->y; + int xmin, xmax, ymin, ymax; + + grid_to_screen(ds, g, x1, y1, &x1, &y1); + grid_to_screen(ds, g, x2, y2, &x2, &y2); + /* Allow extra margin for dots, and thickness of lines */ + xmin = min(x1, x2) - 2; + xmax = max(x1, x2) + 2; + ymin = min(y1, y2) - 2; + ymax = max(y1, y2) + 2; + + *x = xmin; + *y = ymin; + *w = xmax - xmin + 1; + *h = ymax - ymin + 1; +} - *ncolours = NCOLOURS; - return ret; +static void dot_bbox(game_drawstate *ds, grid *g, grid_dot *d, + int *x, int *y, int *w, int *h) +{ + int x1, y1; + + grid_to_screen(ds, g, d->x, d->y, &x1, &y1); + + *x = x1 - 2; + *y = y1 - 2; + *w = 5; + *h = 5; } -static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +static const int loopy_line_redraw_phases[] = { + COL_FAINT, COL_LINEUNKNOWN, COL_FOREGROUND, COL_HIGHLIGHT, COL_MISTAKE +}; +#define NPHASES lenof(loopy_line_redraw_phases) + +static void game_redraw_line(drawing *dr, game_drawstate *ds, + game_state *state, int i, int phase) { - struct game_drawstate *ds = snew(struct game_drawstate); + grid *g = state->game_grid; + grid_edge *e = g->edges + i; + int x1, x2, y1, y2; + int line_colour; + + if (state->line_errors[i]) + line_colour = COL_MISTAKE; + else if (state->lines[i] == LINE_UNKNOWN) + line_colour = COL_LINEUNKNOWN; + else if (state->lines[i] == LINE_NO) + line_colour = COL_FAINT; + else if (ds->flashing) + line_colour = COL_HIGHLIGHT; + else + line_colour = COL_FOREGROUND; + if (line_colour != loopy_line_redraw_phases[phase]) + return; + + /* Convert from grid to screen coordinates */ + grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1); + grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2); + + if (line_colour == COL_FAINT) { + static int draw_faint_lines = -1; + if (draw_faint_lines < 0) { + char *env = getenv("LOOPY_FAINT_LINES"); + draw_faint_lines = (!env || (env[0] == 'y' || + env[0] == 'Y')); + } + if (draw_faint_lines) + draw_line(dr, x1, y1, x2, y2, line_colour); + } else { + draw_thick_line(dr, 3.0, + x1 + 0.5, y1 + 0.5, + x2 + 0.5, y2 + 0.5, + line_colour); + } +} - ds->tilesize = 0; - ds->started = 0; - ds->hl = snewn(HL_COUNT(state), char); - ds->vl = snewn(VL_COUNT(state), char); - ds->flashing = 0; +static void game_redraw_dot(drawing *dr, game_drawstate *ds, + game_state *state, int i) +{ + grid *g = state->game_grid; + grid_dot *d = g->dots + i; + int x, y; - memset(ds->hl, LINE_UNKNOWN, HL_COUNT(state)); - memset(ds->vl, LINE_UNKNOWN, VL_COUNT(state)); + grid_to_screen(ds, g, d->x, d->y, &x, &y); + draw_circle(dr, x, y, 2, COL_FOREGROUND, COL_FOREGROUND); +} - return ds; +static int boxes_intersect(int x0, int y0, int w0, int h0, + int x1, int y1, int w1, int h1) +{ + /* + * Two intervals intersect iff neither is wholly on one side of + * the other. Two boxes intersect iff their horizontal and + * vertical intervals both intersect. + */ + return (x0 < x1+w1 && x1 < x0+w0 && y0 < y1+h1 && y1 < y0+h0); } -static void game_free_drawstate(drawing *dr, game_drawstate *ds) +static void game_redraw_in_rect(drawing *dr, game_drawstate *ds, + game_state *state, int x, int y, int w, int h) { - sfree(ds->hl); - sfree(ds->vl); - sfree(ds); + grid *g = state->game_grid; + int i, phase; + int bx, by, bw, bh; + + clip(dr, x, y, w, h); + draw_rect(dr, x, y, w, h, COL_BACKGROUND); + + for (i = 0; i < g->num_faces; i++) { + if (state->clues[i] >= 0) { + face_text_bbox(ds, g, &g->faces[i], &bx, &by, &bw, &bh); + if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) + game_redraw_clue(dr, ds, state, i); + } + } + for (phase = 0; phase < NPHASES; phase++) { + for (i = 0; i < g->num_edges; i++) { + edge_bbox(ds, g, &g->edges[i], &bx, &by, &bw, &bh); + if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) + game_redraw_line(dr, ds, state, i, phase); + } + } + for (i = 0; i < g->num_dots; i++) { + dot_bbox(ds, g, &g->dots[i], &bx, &by, &bw, &bh); + if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) + game_redraw_dot(dr, ds, state, i); + } + + unclip(dr); + draw_update(dr, x, y, w, h); } 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 i, j; - int w = state->w, h = state->h; - char c[2]; - int line_colour, flash_changed; +#define REDRAW_OBJECTS_LIMIT 16 /* Somewhat arbitrary tradeoff */ + + grid *g = state->game_grid; + int border = BORDER(ds->tilesize); + int i; + int flash_changed; + int redraw_everything = FALSE; + + int edges[REDRAW_OBJECTS_LIMIT], nedges = 0; + int faces[REDRAW_OBJECTS_LIMIT], nfaces = 0; + + /* Redrawing is somewhat involved. + * + * An update can theoretically affect an arbitrary number of edges + * (consider, for example, completing or breaking a cycle which doesn't + * satisfy all the clues -- we'll switch many edges between error and + * normal states). On the other hand, redrawing the whole grid takes a + * while, making the game feel sluggish, and many updates are actually + * quite well localized. + * + * This redraw algorithm attempts to cope with both situations gracefully + * and correctly. For localized changes, we set a clip rectangle, fill + * it with background, and then redraw (a plausible but conservative + * guess at) the objects which intersect the rectangle; if several + * objects need redrawing, we'll do them individually. However, if lots + * of objects are affected, we'll just redraw everything. + * + * The reason for all of this is that it's just not safe to do the redraw + * piecemeal. If you try to draw an antialiased diagonal line over + * itself, you get a slightly thicker antialiased diagonal line, which + * looks rather ugly after a while. + * + * So, we take two passes over the grid. The first attempts to work out + * what needs doing, and the second actually does it. + */ if (!ds->started) { + redraw_everything = TRUE; /* - * 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. + * But we must still go through the upcoming loops, so that we + * set up stuff in ds correctly for the initial redraw. */ - draw_rect(dr, 0, 0, SIZE(state->w), SIZE(state->h), COL_BACKGROUND); - - /* Draw dots */ - for (j = 0; j < h + 1; ++j) { - for (i = 0; i < w + 1; ++i) { - draw_rect(dr, - BORDER + i * TILE_SIZE - LINEWIDTH/2, - BORDER + j * TILE_SIZE - LINEWIDTH/2, - LINEWIDTH, LINEWIDTH, COL_FOREGROUND); - } - } + } - /* Draw clues */ - for (j = 0; j < h; ++j) { - for (i = 0; i < w; ++i) { - c[0] = CLUE_AT(state, i, j); - c[1] = '\0'; - draw_text(dr, - BORDER + i * TILE_SIZE + TILE_SIZE/2, - BORDER + j * TILE_SIZE + TILE_SIZE/2, - FONT_VARIABLE, TILE_SIZE/2, - ALIGN_VCENTRE | ALIGN_HCENTRE, COL_FOREGROUND, c); - } + /* First, trundle through the faces. */ + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int sides = f->order; + int clue_mistake; + int clue_satisfied; + int n = state->clues[i]; + if (n < 0) + continue; + + clue_mistake = (face_order(state, i, LINE_YES) > n || + face_order(state, i, LINE_NO ) > (sides-n)); + clue_satisfied = (face_order(state, i, LINE_YES) == n && + face_order(state, i, LINE_NO ) == (sides-n)); + + if (clue_mistake != ds->clue_error[i] || + clue_satisfied != ds->clue_satisfied[i]) { + ds->clue_error[i] = clue_mistake; + ds->clue_satisfied[i] = clue_satisfied; + if (nfaces == REDRAW_OBJECTS_LIMIT) + redraw_everything = TRUE; + else + faces[nfaces++] = i; } - draw_update(dr, 0, 0, - state->w * TILE_SIZE + 2*BORDER + 1, - state->h * TILE_SIZE + 2*BORDER + 1); - ds->started = TRUE; } - if (flashtime > 0 && + /* Work out what the flash state needs to be. */ + if (flashtime > 0 && (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3)) { flash_changed = !ds->flashing; ds->flashing = TRUE; - line_colour = COL_HIGHLIGHT; } else { flash_changed = ds->flashing; ds->flashing = FALSE; - line_colour = COL_FOREGROUND; } -#define CROSS_SIZE (3 * LINEWIDTH / 2) - -#define CLEAR_VL(i, j) do { \ - draw_rect(dr, \ - BORDER + i * TILE_SIZE - CROSS_SIZE, \ - BORDER + j * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, \ - CROSS_SIZE * 2, \ - TILE_SIZE - LINEWIDTH, \ - COL_BACKGROUND); \ - draw_update(dr, \ - BORDER + i * TILE_SIZE - CROSS_SIZE, \ - BORDER + j * TILE_SIZE - CROSS_SIZE, \ - CROSS_SIZE*2, \ - TILE_SIZE + CROSS_SIZE*2); \ - } while (0) - -#define CLEAR_HL(i, j) do { \ - draw_rect(dr, \ - BORDER + i * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, \ - BORDER + j * TILE_SIZE - CROSS_SIZE, \ - TILE_SIZE - LINEWIDTH, \ - CROSS_SIZE * 2, \ - COL_BACKGROUND); \ - draw_update(dr, \ - BORDER + i * TILE_SIZE - CROSS_SIZE, \ - BORDER + j * TILE_SIZE - CROSS_SIZE, \ - TILE_SIZE + CROSS_SIZE*2, \ - CROSS_SIZE*2); \ - } while (0) - - /* Vertical lines */ - for (j = 0; j < h; ++j) { - for (i = 0; i < w + 1; ++i) { - switch (BELOW_DOT(state, i, j)) { - case LINE_UNKNOWN: - if (ds->vl[i + (w + 1) * j] != BELOW_DOT(state, i, j)) { - CLEAR_VL(i, j); - } - break; - case LINE_YES: - if (ds->vl[i + (w + 1) * j] != BELOW_DOT(state, i, j) || - flash_changed) { - CLEAR_VL(i, j); - draw_rect(dr, - BORDER + i * TILE_SIZE - LINEWIDTH/2, - BORDER + j * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, - LINEWIDTH, TILE_SIZE - LINEWIDTH, - line_colour); - } - break; - case LINE_NO: - if (ds->vl[i + (w + 1) * j] != BELOW_DOT(state, i, j)) { - CLEAR_VL(i, j); - draw_line(dr, - BORDER + i * TILE_SIZE - CROSS_SIZE, - BORDER + j * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE, - BORDER + i * TILE_SIZE + CROSS_SIZE - 1, - BORDER + j * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1, - COL_FOREGROUND); - draw_line(dr, - BORDER + i * TILE_SIZE + CROSS_SIZE - 1, - BORDER + j * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE, - BORDER + i * TILE_SIZE - CROSS_SIZE, - BORDER + j * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1, - COL_FOREGROUND); - } - break; - } - ds->vl[i + (w + 1) * j] = BELOW_DOT(state, i, j); + /* Now, trundle through the edges. */ + for (i = 0; i < g->num_edges; i++) { + char new_ds = + state->line_errors[i] ? DS_LINE_ERROR : state->lines[i]; + if (new_ds != ds->lines[i] || + (flash_changed && state->lines[i] == LINE_YES)) { + ds->lines[i] = new_ds; + if (nedges == REDRAW_OBJECTS_LIMIT) + redraw_everything = TRUE; + else + edges[nedges++] = i; } } - /* Horizontal lines */ - for (j = 0; j < h + 1; ++j) { - for (i = 0; i < w; ++i) { - switch (RIGHTOF_DOT(state, i, j)) { - case LINE_UNKNOWN: - if (ds->hl[i + w * j] != RIGHTOF_DOT(state, i, j)) { - CLEAR_HL(i, j); - } - break; - case LINE_YES: - if (ds->hl[i + w * j] != RIGHTOF_DOT(state, i, j) || - flash_changed) { - CLEAR_HL(i, j); - draw_rect(dr, - BORDER + i * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, - BORDER + j * TILE_SIZE - LINEWIDTH/2, - TILE_SIZE - LINEWIDTH, LINEWIDTH, - line_colour); - break; - } - case LINE_NO: - if (ds->hl[i + w * j] != RIGHTOF_DOT(state, i, j)) { - CLEAR_HL(i, j); - draw_line(dr, - BORDER + i * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE, - BORDER + j * TILE_SIZE + CROSS_SIZE - 1, - BORDER + i * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1, - BORDER + j * TILE_SIZE - CROSS_SIZE, - COL_FOREGROUND); - draw_line(dr, - BORDER + i * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE, - BORDER + j * TILE_SIZE - CROSS_SIZE, - BORDER + i * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1, - BORDER + j * TILE_SIZE + CROSS_SIZE - 1, - COL_FOREGROUND); - break; - } - } - ds->hl[i + w * j] = RIGHTOF_DOT(state, i, j); - } + /* Pass one is now done. Now we do the actual drawing. */ + if (redraw_everything) { + int grid_width = g->highest_x - g->lowest_x; + int grid_height = g->highest_y - g->lowest_y; + int w = grid_width * ds->tilesize / g->tilesize; + int h = grid_height * ds->tilesize / g->tilesize; + + game_redraw_in_rect(dr, ds, state, + 0, 0, w + 2*border + 1, h + 2*border + 1); + } else { + + /* Right. Now we roll up our sleeves. */ + + for (i = 0; i < nfaces; i++) { + grid_face *f = g->faces + faces[i]; + int x, y, w, h; + + face_text_bbox(ds, g, f, &x, &y, &w, &h); + game_redraw_in_rect(dr, ds, state, x, y, w, h); + } + + for (i = 0; i < nedges; i++) { + grid_edge *e = g->edges + edges[i]; + int x, y, w, h; + + edge_bbox(ds, g, e, &x, &y, &w, &h); + game_redraw_in_rect(dr, ds, state, x, y, w, h); + } } -} -static float game_anim_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) -{ - return 0.0F; + ds->started = TRUE; } static float game_flash_length(game_state *oldstate, game_state *newstate, @@ -2586,14 +3296,9 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_wants_statusbar(void) -{ - return FALSE; -} - -static int game_timing_state(game_state *state, game_ui *ui) +static int game_status(game_state *state) { - return TRUE; + return state->solved ? +1 : 0; } static void game_print_size(game_params *params, float *x, float *y) @@ -2601,7 +3306,7 @@ static void game_print_size(game_params *params, float *x, float *y) int pw, ph; /* - * I'll use 7mm squares by default. + * I'll use 7mm "squares" by default. */ game_compute_size(params, 700, &pw, &ph); *x = pw / 100.0F; @@ -2610,54 +3315,88 @@ static void game_print_size(game_params *params, float *x, float *y) static void game_print(drawing *dr, game_state *state, int tilesize) { - int w = state->w, h = state->h; int ink = print_mono_colour(dr, 0); - int x, y; + int i; game_drawstate ads, *ds = &ads; - ds->tilesize = tilesize; + grid *g = state->game_grid; - /* - * Dots. I'll deliberately make the dots a bit wider than the - * lines, so you can still see them. (And also because it's - * annoyingly tricky to make them _exactly_ the same size...) - */ - for (y = 0; y <= h; y++) - for (x = 0; x <= w; x++) - draw_circle(dr, BORDER + x * TILE_SIZE, BORDER + y * TILE_SIZE, - LINEWIDTH, ink, ink); + ds->tilesize = tilesize; + ds->textx = snewn(g->num_faces, int); + ds->texty = snewn(g->num_faces, int); + for (i = 0; i < g->num_faces; i++) + ds->textx[i] = ds->texty[i] = -1; + + for (i = 0; i < g->num_dots; i++) { + int x, y; + grid_to_screen(ds, g, g->dots[i].x, g->dots[i].y, &x, &y); + draw_circle(dr, x, y, ds->tilesize / 15, ink, ink); + } /* * Clues. */ - for (y = 0; y < h; y++) - for (x = 0; x < w; x++) - if (CLUE_AT(state, x, y) != ' ') { - char c[2]; - - c[0] = CLUE_AT(state, x, y); - c[1] = '\0'; - draw_text(dr, - BORDER + x * TILE_SIZE + TILE_SIZE/2, - BORDER + y * TILE_SIZE + TILE_SIZE/2, - FONT_VARIABLE, TILE_SIZE/2, - ALIGN_VCENTRE | ALIGN_HCENTRE, ink, c); - } + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int clue = state->clues[i]; + if (clue >= 0) { + char c[2]; + int x, y; + c[0] = CLUE2CHAR(clue); + c[1] = '\0'; + face_text_pos(ds, g, f, &x, &y); + draw_text(dr, x, y, + FONT_VARIABLE, ds->tilesize / 2, + ALIGN_VCENTRE | ALIGN_HCENTRE, ink, c); + } + } /* - * Lines. (At the moment, I'm not bothering with crosses.) + * Lines. */ - for (y = 0; y <= h; y++) - for (x = 0; x < w; x++) - if (RIGHTOF_DOT(state, x, y) == LINE_YES) - draw_rect(dr, BORDER + x * TILE_SIZE, - BORDER + y * TILE_SIZE - LINEWIDTH/2, - TILE_SIZE, (LINEWIDTH/2) * 2 + 1, ink); - for (y = 0; y < h; y++) - for (x = 0; x <= w; x++) - if (BELOW_DOT(state, x, y) == LINE_YES) - draw_rect(dr, BORDER + x * TILE_SIZE - LINEWIDTH/2, - BORDER + y * TILE_SIZE, - (LINEWIDTH/2) * 2 + 1, TILE_SIZE, ink); + for (i = 0; i < g->num_edges; i++) { + int thickness = (state->lines[i] == LINE_YES) ? 30 : 150; + grid_edge *e = g->edges + i; + int x1, y1, x2, y2; + grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1); + grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2); + if (state->lines[i] == LINE_YES) + { + /* (dx, dy) points from (x1, y1) to (x2, y2). + * The line is then "fattened" in a perpendicular + * direction to create a thin rectangle. */ + double d = sqrt(SQ((double)x1 - x2) + SQ((double)y1 - y2)); + double dx = (x2 - x1) / d; + double dy = (y2 - y1) / d; + int points[8]; + + dx = (dx * ds->tilesize) / thickness; + dy = (dy * ds->tilesize) / thickness; + points[0] = x1 + (int)dy; + points[1] = y1 - (int)dx; + points[2] = x1 - (int)dy; + points[3] = y1 + (int)dx; + points[4] = x2 - (int)dy; + points[5] = y2 + (int)dx; + points[6] = x2 + (int)dy; + points[7] = y2 - (int)dx; + draw_polygon(dr, points, 4, ink, ink); + } + else + { + /* Draw a dotted line */ + int divisions = 6; + int j; + for (j = 1; j < divisions; j++) { + /* Weighted average */ + int x = (x1 * (divisions -j) + x2 * j) / divisions; + int y = (y1 * (divisions -j) + y2 * j) / divisions; + draw_circle(dr, x, y, ds->tilesize / thickness, ink, ink); + } + } + } + + sfree(ds->textx); + sfree(ds->texty); } #ifdef COMBINED @@ -2665,7 +3404,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) #endif const struct game thegame = { - "Loopy", "games.loopy", + "Loopy", "games.loopy", "loopy", default_params, game_fetch_preset, decode_params, @@ -2680,7 +3419,7 @@ const struct game thegame = { dup_game, free_game, 1, solve_game, - TRUE, game_text_format, + TRUE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -2695,8 +3434,138 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, FALSE, game_print_size, game_print, - game_wants_statusbar, + FALSE /* wants_statusbar */, FALSE, game_timing_state, 0, /* mouse_priorities */ }; + +#ifdef STANDALONE_SOLVER + +/* + * Half-hearted standalone solver. It can't output the solution to + * anything but a square puzzle, and it can't log the deductions + * it makes either. But it can solve square puzzles, and more + * importantly it can use its solver to grade the difficulty of + * any puzzle you give it. + */ + +#include + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc, *err; + int grade = FALSE; + int ret, diff; +#if 0 /* verbose solver not supported here (yet) */ + int really_verbose = FALSE; +#endif + + while (--argc > 0) { + char *p = *++argv; +#if 0 /* verbose solver not supported here (yet) */ + if (!strcmp(p, "-v")) { + really_verbose = TRUE; + } else +#endif + 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 */ + for (diff = 0; diff < DIFF_MAX; diff++) { + solver_state *sstate_new; + solver_state *sstate = new_solver_state((game_state *)s, diff); + + sstate_new = solve_game_rec(sstate); + + if (sstate_new->solver_status == SOLVER_MISTAKE) + ret = 0; + else if (sstate_new->solver_status == SOLVER_SOLVED) + ret = 1; + else + ret = 2; + + free_solver_state(sstate_new); + free_solver_state(sstate); + + if (ret < 2) + break; + } + + if (diff == DIFF_MAX) { + if (grade) + printf("Difficulty rating: harder than Hard, or ambiguous\n"); + else + printf("Unable to find a unique solution\n"); + } else { + if (grade) { + if (ret == 0) + printf("Difficulty rating: impossible (no solution exists)\n"); + else if (ret == 1) + printf("Difficulty rating: %s\n", diffnames[diff]); + } else { + solver_state *sstate_new; + solver_state *sstate = new_solver_state((game_state *)s, diff); + + /* If we supported a verbose solver, we'd set verbosity here */ + + sstate_new = solve_game_rec(sstate); + + if (sstate_new->solver_status == SOLVER_MISTAKE) + printf("Puzzle is inconsistent\n"); + else { + assert(sstate_new->solver_status == SOLVER_SOLVED); + if (s->grid_type == 0) { + fputs(game_text_format(sstate_new->state), stdout); + } else { + printf("Unable to output non-square grids\n"); + } + } + + free_solver_state(sstate_new); + free_solver_state(sstate); + } + } + + return 0; +} + +#endif + +/* vim: set shiftwidth=4 tabstop=8: */