chiark / gitweb /
Make the images on the web page link to the JS puzzles.
[sgt-puzzles.git] / loopy.c
1 /*
2  * loopy.c:
3  *
4  * An implementation of the Nikoli game 'Loop the loop'.
5  * (c) Mike Pinna, 2005, 2006
6  * Substantially rewritten to allowing for more general types of grid.
7  * (c) Lambros Lambrou 2008
8  *
9  * vim: set shiftwidth=4 :set textwidth=80:
10  */
11
12 /*
13  * Possible future solver enhancements:
14  * 
15  *  - There's an interesting deductive technique which makes use
16  *    of topology rather than just graph theory. Each _face_ in
17  *    the grid is either inside or outside the loop; you can tell
18  *    that two faces are on the same side of the loop if they're
19  *    separated by a LINE_NO (or, more generally, by a path
20  *    crossing no LINE_UNKNOWNs and an even number of LINE_YESes),
21  *    and on the opposite side of the loop if they're separated by
22  *    a LINE_YES (or an odd number of LINE_YESes and no
23  *    LINE_UNKNOWNs). Oh, and any face separated from the outside
24  *    of the grid by a LINE_YES or a LINE_NO is on the inside or
25  *    outside respectively. So if you can track this for all
26  *    faces, you figure out the state of the line between a pair
27  *    once their relative insideness is known.
28  *     + The way I envisage this working is simply to keep an edsf
29  *       of all _faces_, which indicates whether they're on
30  *       opposite sides of the loop from one another. We also
31  *       include a special entry in the edsf for the infinite
32  *       exterior "face".
33  *     + So, the simple way to do this is to just go through the
34  *       edges: every time we see an edge in a state other than
35  *       LINE_UNKNOWN which separates two faces that aren't in the
36  *       same edsf class, we can rectify that by merging the
37  *       classes. Then, conversely, an edge in LINE_UNKNOWN state
38  *       which separates two faces that _are_ in the same edsf
39  *       class can immediately have its state determined.
40  *     + But you can go one better, if you're prepared to loop
41  *       over all _pairs_ of edges. Suppose we have edges A and B,
42  *       which respectively separate faces A1,A2 and B1,B2.
43  *       Suppose that A,B are in the same edge-edsf class and that
44  *       A1,B1 (wlog) are in the same face-edsf class; then we can
45  *       immediately place A2,B2 into the same face-edsf class (as
46  *       each other, not as A1 and A2) one way round or the other.
47  *       And conversely again, if A1,B1 are in the same face-edsf
48  *       class and so are A2,B2, then we can put A,B into the same
49  *       face-edsf class.
50  *        * Of course, this deduction requires a quadratic-time
51  *          loop over all pairs of edges in the grid, so it should
52  *          be reserved until there's nothing easier left to be
53  *          done.
54  * 
55  *  - The generalised grid support has made me (SGT) notice a
56  *    possible extension to the loop-avoidance code. When you have
57  *    a path of connected edges such that no other edges at all
58  *    are incident on any vertex in the middle of the path - or,
59  *    alternatively, such that any such edges are already known to
60  *    be LINE_NO - then you know those edges are either all
61  *    LINE_YES or all LINE_NO. Hence you can mentally merge the
62  *    entire path into a single long curly edge for the purposes
63  *    of loop avoidance, and look directly at whether or not the
64  *    extreme endpoints of the path are connected by some other
65  *    route. I find this coming up fairly often when I play on the
66  *    octagonal grid setting, so it might be worth implementing in
67  *    the solver.
68  *
69  *  - (Just a speed optimisation.)  Consider some todo list queue where every
70  *    time we modify something we mark it for consideration by other bits of
71  *    the solver, to save iteration over things that have already been done.
72  */
73
74 #include <stdio.h>
75 #include <stdlib.h>
76 #include <stddef.h>
77 #include <string.h>
78 #include <assert.h>
79 #include <ctype.h>
80 #include <math.h>
81
82 #include "puzzles.h"
83 #include "tree234.h"
84 #include "grid.h"
85 #include "loopgen.h"
86
87 /* Debugging options */
88
89 /*
90 #define DEBUG_CACHES
91 #define SHOW_WORKING
92 #define DEBUG_DLINES
93 */
94
95 /* ----------------------------------------------------------------------
96  * Struct, enum and function declarations
97  */
98
99 enum {
100     COL_BACKGROUND,
101     COL_FOREGROUND,
102     COL_LINEUNKNOWN,
103     COL_HIGHLIGHT,
104     COL_MISTAKE,
105     COL_SATISFIED,
106     COL_FAINT,
107     NCOLOURS
108 };
109
110 struct game_state {
111     grid *game_grid; /* ref-counted (internally) */
112
113     /* Put -1 in a face that doesn't get a clue */
114     signed char *clues;
115
116     /* Array of line states, to store whether each line is
117      * YES, NO or UNKNOWN */
118     char *lines;
119
120     unsigned char *line_errors;
121     int exactly_one_loop;
122
123     int solved;
124     int cheated;
125
126     /* Used in game_text_format(), so that it knows what type of
127      * grid it's trying to render as ASCII text. */
128     int grid_type;
129 };
130
131 enum solver_status {
132     SOLVER_SOLVED,    /* This is the only solution the solver could find */
133     SOLVER_MISTAKE,   /* This is definitely not a solution */
134     SOLVER_AMBIGUOUS, /* This _might_ be an ambiguous solution */
135     SOLVER_INCOMPLETE /* This may be a partial solution */
136 };
137
138 /* ------ Solver state ------ */
139 typedef struct solver_state {
140     game_state *state;
141     enum solver_status solver_status;
142     /* NB looplen is the number of dots that are joined together at a point, ie a
143      * looplen of 1 means there are no lines to a particular dot */
144     int *looplen;
145
146     /* Difficulty level of solver.  Used by solver functions that want to
147      * vary their behaviour depending on the requested difficulty level. */
148     int diff;
149
150     /* caches */
151     char *dot_yes_count;
152     char *dot_no_count;
153     char *face_yes_count;
154     char *face_no_count;
155     char *dot_solved, *face_solved;
156     int *dotdsf;
157
158     /* Information for Normal level deductions:
159      * For each dline, store a bitmask for whether we know:
160      * (bit 0) at least one is YES
161      * (bit 1) at most one is YES */
162     char *dlines;
163
164     /* Hard level information */
165     int *linedsf;
166 } solver_state;
167
168 /*
169  * Difficulty levels. I do some macro ickery here to ensure that my
170  * enum and the various forms of my name list always match up.
171  */
172
173 #define DIFFLIST(A) \
174     A(EASY,Easy,e) \
175     A(NORMAL,Normal,n) \
176     A(TRICKY,Tricky,t) \
177     A(HARD,Hard,h)
178 #define ENUM(upper,title,lower) DIFF_ ## upper,
179 #define TITLE(upper,title,lower) #title,
180 #define ENCODE(upper,title,lower) #lower
181 #define CONFIG(upper,title,lower) ":" #title
182 enum { DIFFLIST(ENUM) DIFF_MAX };
183 static char const *const diffnames[] = { DIFFLIST(TITLE) };
184 static char const diffchars[] = DIFFLIST(ENCODE);
185 #define DIFFCONFIG DIFFLIST(CONFIG)
186
187 /*
188  * Solver routines, sorted roughly in order of computational cost.
189  * The solver will run the faster deductions first, and slower deductions are
190  * only invoked when the faster deductions are unable to make progress.
191  * Each function is associated with a difficulty level, so that the generated
192  * puzzles are solvable by applying only the functions with the chosen
193  * difficulty level or lower.
194  */
195 #define SOLVERLIST(A) \
196     A(trivial_deductions, DIFF_EASY) \
197     A(dline_deductions, DIFF_NORMAL) \
198     A(linedsf_deductions, DIFF_HARD) \
199     A(loop_deductions, DIFF_EASY)
200 #define SOLVER_FN_DECL(fn,diff) static int fn(solver_state *);
201 #define SOLVER_FN(fn,diff) &fn,
202 #define SOLVER_DIFF(fn,diff) diff,
203 SOLVERLIST(SOLVER_FN_DECL)
204 static int (*(solver_fns[]))(solver_state *) = { SOLVERLIST(SOLVER_FN) };
205 static int const solver_diffs[] = { SOLVERLIST(SOLVER_DIFF) };
206 static const int NUM_SOLVERS = sizeof(solver_diffs)/sizeof(*solver_diffs);
207
208 struct game_params {
209     int w, h;
210     int diff;
211     int type;
212 };
213
214 /* line_drawstate is the same as line_state, but with the extra ERROR
215  * possibility.  The drawing code copies line_state to line_drawstate,
216  * except in the case that the line is an error. */
217 enum line_state { LINE_YES, LINE_UNKNOWN, LINE_NO };
218 enum line_drawstate { DS_LINE_YES, DS_LINE_UNKNOWN,
219                       DS_LINE_NO, DS_LINE_ERROR };
220
221 #define OPP(line_state) \
222     (2 - line_state)
223
224
225 struct game_drawstate {
226     int started;
227     int tilesize;
228     int flashing;
229     int *textx, *texty;
230     char *lines;
231     char *clue_error;
232     char *clue_satisfied;
233 };
234
235 static char *validate_desc(const game_params *params, const char *desc);
236 static int dot_order(const game_state* state, int i, char line_type);
237 static int face_order(const game_state* state, int i, char line_type);
238 static solver_state *solve_game_rec(const solver_state *sstate);
239
240 #ifdef DEBUG_CACHES
241 static void check_caches(const solver_state* sstate);
242 #else
243 #define check_caches(s)
244 #endif
245
246 /*
247  * Grid type config options available in Loopy.
248  *
249  * Annoyingly, we have to use an enum here which doesn't match up
250  * exactly to the grid-type enum in grid.h. Values in params->types
251  * are given by names such as LOOPY_GRID_SQUARE, which shouldn't be
252  * confused with GRID_SQUARE which is the value you pass to grid_new()
253  * and friends. So beware!
254  *
255  * (This is partly for historical reasons - Loopy's version of the
256  * enum is encoded in game parameter strings, so we keep it for
257  * backwards compatibility. But also, we need to store additional data
258  * here alongside each enum value, such as names for the presets menu,
259  * which isn't stored in grid.h; so we have to have our own list macro
260  * here anyway, and C doesn't make it easy to enforce that that lines
261  * up exactly with grid.h.)
262  *
263  * Do not add values to this list _except_ at the end, or old game ids
264  * will stop working!
265  */
266 #define GRIDLIST(A)                                             \
267     A("Squares",SQUARE,3,3)                                     \
268     A("Triangular",TRIANGULAR,3,3)                              \
269     A("Honeycomb",HONEYCOMB,3,3)                                \
270     A("Snub-Square",SNUBSQUARE,3,3)                             \
271     A("Cairo",CAIRO,3,4)                                        \
272     A("Great-Hexagonal",GREATHEXAGONAL,3,3)                     \
273     A("Octagonal",OCTAGONAL,3,3)                                \
274     A("Kites",KITE,3,3)                                         \
275     A("Floret",FLORET,1,2)                                      \
276     A("Dodecagonal",DODECAGONAL,2,2)                            \
277     A("Great-Dodecagonal",GREATDODECAGONAL,2,2)                 \
278     A("Penrose (kite/dart)",PENROSE_P2,3,3)                     \
279     A("Penrose (rhombs)",PENROSE_P3,3,3)                        \
280     A("Great-Great-Dodecagonal",GREATGREATDODECAGONAL,2,2)      \
281     /* end of list */
282
283 #define GRID_NAME(title,type,amin,omin) title,
284 #define GRID_CONFIG(title,type,amin,omin) ":" title
285 #define GRID_LOOPYTYPE(title,type,amin,omin) LOOPY_GRID_ ## type,
286 #define GRID_GRIDTYPE(title,type,amin,omin) GRID_ ## type,
287 #define GRID_SIZES(title,type,amin,omin) \
288     {amin, omin, \
289      "Width and height for this grid type must both be at least " #amin, \
290      "At least one of width and height for this grid type must be at least " #omin,},
291 enum { GRIDLIST(GRID_LOOPYTYPE) };
292 static char const *const gridnames[] = { GRIDLIST(GRID_NAME) };
293 #define GRID_CONFIGS GRIDLIST(GRID_CONFIG)
294 static grid_type grid_types[] = { GRIDLIST(GRID_GRIDTYPE) };
295 #define NUM_GRID_TYPES (sizeof(grid_types) / sizeof(grid_types[0]))
296 static const struct {
297     int amin, omin;
298     char *aerr, *oerr;
299 } grid_size_limits[] = { GRIDLIST(GRID_SIZES) };
300
301 /* Generates a (dynamically allocated) new grid, according to the
302  * type and size requested in params.  Does nothing if the grid is already
303  * generated. */
304 static grid *loopy_generate_grid(const game_params *params,
305                                  const char *grid_desc)
306 {
307     return grid_new(grid_types[params->type], params->w, params->h, grid_desc);
308 }
309
310 /* ----------------------------------------------------------------------
311  * Preprocessor magic
312  */
313
314 /* General constants */
315 #define PREFERRED_TILE_SIZE 32
316 #define BORDER(tilesize) ((tilesize) / 2)
317 #define FLASH_TIME 0.5F
318
319 #define BIT_SET(field, bit) ((field) & (1<<(bit)))
320
321 #define SET_BIT(field, bit)  (BIT_SET(field, bit) ? FALSE : \
322                               ((field) |= (1<<(bit)), TRUE))
323
324 #define CLEAR_BIT(field, bit) (BIT_SET(field, bit) ? \
325                                ((field) &= ~(1<<(bit)), TRUE) : FALSE)
326
327 #define CLUE2CHAR(c) \
328     ((c < 0) ? ' ' : c < 10 ? c + '0' : c - 10 + 'A')
329
330 /* ----------------------------------------------------------------------
331  * General struct manipulation and other straightforward code
332  */
333
334 static game_state *dup_game(const game_state *state)
335 {
336     game_state *ret = snew(game_state);
337
338     ret->game_grid = state->game_grid;
339     ret->game_grid->refcount++;
340
341     ret->solved = state->solved;
342     ret->cheated = state->cheated;
343
344     ret->clues = snewn(state->game_grid->num_faces, signed char);
345     memcpy(ret->clues, state->clues, state->game_grid->num_faces);
346
347     ret->lines = snewn(state->game_grid->num_edges, char);
348     memcpy(ret->lines, state->lines, state->game_grid->num_edges);
349
350     ret->line_errors = snewn(state->game_grid->num_edges, unsigned char);
351     memcpy(ret->line_errors, state->line_errors, state->game_grid->num_edges);
352     ret->exactly_one_loop = state->exactly_one_loop;
353
354     ret->grid_type = state->grid_type;
355     return ret;
356 }
357
358 static void free_game(game_state *state)
359 {
360     if (state) {
361         grid_free(state->game_grid);
362         sfree(state->clues);
363         sfree(state->lines);
364         sfree(state->line_errors);
365         sfree(state);
366     }
367 }
368
369 static solver_state *new_solver_state(const game_state *state, int diff) {
370     int i;
371     int num_dots = state->game_grid->num_dots;
372     int num_faces = state->game_grid->num_faces;
373     int num_edges = state->game_grid->num_edges;
374     solver_state *ret = snew(solver_state);
375
376     ret->state = dup_game(state);
377
378     ret->solver_status = SOLVER_INCOMPLETE;
379     ret->diff = diff;
380
381     ret->dotdsf = snew_dsf(num_dots);
382     ret->looplen = snewn(num_dots, int);
383
384     for (i = 0; i < num_dots; i++) {
385         ret->looplen[i] = 1;
386     }
387
388     ret->dot_solved = snewn(num_dots, char);
389     ret->face_solved = snewn(num_faces, char);
390     memset(ret->dot_solved, FALSE, num_dots);
391     memset(ret->face_solved, FALSE, num_faces);
392
393     ret->dot_yes_count = snewn(num_dots, char);
394     memset(ret->dot_yes_count, 0, num_dots);
395     ret->dot_no_count = snewn(num_dots, char);
396     memset(ret->dot_no_count, 0, num_dots);
397     ret->face_yes_count = snewn(num_faces, char);
398     memset(ret->face_yes_count, 0, num_faces);
399     ret->face_no_count = snewn(num_faces, char);
400     memset(ret->face_no_count, 0, num_faces);
401
402     if (diff < DIFF_NORMAL) {
403         ret->dlines = NULL;
404     } else {
405         ret->dlines = snewn(2*num_edges, char);
406         memset(ret->dlines, 0, 2*num_edges);
407     }
408
409     if (diff < DIFF_HARD) {
410         ret->linedsf = NULL;
411     } else {
412         ret->linedsf = snew_dsf(state->game_grid->num_edges);
413     }
414
415     return ret;
416 }
417
418 static void free_solver_state(solver_state *sstate) {
419     if (sstate) {
420         free_game(sstate->state);
421         sfree(sstate->dotdsf);
422         sfree(sstate->looplen);
423         sfree(sstate->dot_solved);
424         sfree(sstate->face_solved);
425         sfree(sstate->dot_yes_count);
426         sfree(sstate->dot_no_count);
427         sfree(sstate->face_yes_count);
428         sfree(sstate->face_no_count);
429
430         /* OK, because sfree(NULL) is a no-op */
431         sfree(sstate->dlines);
432         sfree(sstate->linedsf);
433
434         sfree(sstate);
435     }
436 }
437
438 static solver_state *dup_solver_state(const solver_state *sstate) {
439     game_state *state = sstate->state;
440     int num_dots = state->game_grid->num_dots;
441     int num_faces = state->game_grid->num_faces;
442     int num_edges = state->game_grid->num_edges;
443     solver_state *ret = snew(solver_state);
444
445     ret->state = state = dup_game(sstate->state);
446
447     ret->solver_status = sstate->solver_status;
448     ret->diff = sstate->diff;
449
450     ret->dotdsf = snewn(num_dots, int);
451     ret->looplen = snewn(num_dots, int);
452     memcpy(ret->dotdsf, sstate->dotdsf,
453            num_dots * sizeof(int));
454     memcpy(ret->looplen, sstate->looplen,
455            num_dots * sizeof(int));
456
457     ret->dot_solved = snewn(num_dots, char);
458     ret->face_solved = snewn(num_faces, char);
459     memcpy(ret->dot_solved, sstate->dot_solved, num_dots);
460     memcpy(ret->face_solved, sstate->face_solved, num_faces);
461
462     ret->dot_yes_count = snewn(num_dots, char);
463     memcpy(ret->dot_yes_count, sstate->dot_yes_count, num_dots);
464     ret->dot_no_count = snewn(num_dots, char);
465     memcpy(ret->dot_no_count, sstate->dot_no_count, num_dots);
466
467     ret->face_yes_count = snewn(num_faces, char);
468     memcpy(ret->face_yes_count, sstate->face_yes_count, num_faces);
469     ret->face_no_count = snewn(num_faces, char);
470     memcpy(ret->face_no_count, sstate->face_no_count, num_faces);
471
472     if (sstate->dlines) {
473         ret->dlines = snewn(2*num_edges, char);
474         memcpy(ret->dlines, sstate->dlines,
475                2*num_edges);
476     } else {
477         ret->dlines = NULL;
478     }
479
480     if (sstate->linedsf) {
481         ret->linedsf = snewn(num_edges, int);
482         memcpy(ret->linedsf, sstate->linedsf,
483                num_edges * sizeof(int));
484     } else {
485         ret->linedsf = NULL;
486     }
487
488     return ret;
489 }
490
491 static game_params *default_params(void)
492 {
493     game_params *ret = snew(game_params);
494
495 #ifdef SLOW_SYSTEM
496     ret->h = 7;
497     ret->w = 7;
498 #else
499     ret->h = 10;
500     ret->w = 10;
501 #endif
502     ret->diff = DIFF_EASY;
503     ret->type = 0;
504
505     return ret;
506 }
507
508 static game_params *dup_params(const game_params *params)
509 {
510     game_params *ret = snew(game_params);
511
512     *ret = *params;                       /* structure copy */
513     return ret;
514 }
515
516 static const game_params loopy_presets_top[] = {
517 #ifdef SMALL_SCREEN
518     {  7,  7, DIFF_EASY,   LOOPY_GRID_SQUARE },
519     {  7,  7, DIFF_NORMAL, LOOPY_GRID_SQUARE },
520     {  7,  7, DIFF_HARD,   LOOPY_GRID_SQUARE },
521     {  7,  7, DIFF_HARD,   LOOPY_GRID_TRIANGULAR },
522     {  5,  5, DIFF_HARD,   LOOPY_GRID_SNUBSQUARE },
523     {  7,  7, DIFF_HARD,   LOOPY_GRID_CAIRO },
524     {  5,  5, DIFF_HARD,   LOOPY_GRID_KITE },
525     {  6,  6, DIFF_HARD,   LOOPY_GRID_PENROSE_P2 },
526     {  6,  6, DIFF_HARD,   LOOPY_GRID_PENROSE_P3 },
527 #else
528     {  7,  7, DIFF_EASY,   LOOPY_GRID_SQUARE },
529     { 10, 10, DIFF_EASY,   LOOPY_GRID_SQUARE },
530     {  7,  7, DIFF_NORMAL, LOOPY_GRID_SQUARE },
531     { 10, 10, DIFF_NORMAL, LOOPY_GRID_SQUARE },
532     {  7,  7, DIFF_HARD,   LOOPY_GRID_SQUARE },
533     { 10, 10, DIFF_HARD,   LOOPY_GRID_SQUARE },
534     { 12, 10, DIFF_HARD,   LOOPY_GRID_TRIANGULAR },
535     {  7,  7, DIFF_HARD,   LOOPY_GRID_SNUBSQUARE },
536     {  9,  9, DIFF_HARD,   LOOPY_GRID_CAIRO },
537     {  5,  5, DIFF_HARD,   LOOPY_GRID_KITE },
538     { 10, 10, DIFF_HARD,   LOOPY_GRID_PENROSE_P2 },
539     { 10, 10, DIFF_HARD,   LOOPY_GRID_PENROSE_P3 },
540 #endif
541 };
542
543 static const game_params loopy_presets_more[] = {
544 #ifdef SMALL_SCREEN
545     {  7,  7, DIFF_HARD,   LOOPY_GRID_HONEYCOMB },
546     {  5,  4, DIFF_HARD,   LOOPY_GRID_GREATHEXAGONAL },
547     {  5,  5, DIFF_HARD,   LOOPY_GRID_OCTAGONAL },
548     {  3,  3, DIFF_HARD,   LOOPY_GRID_FLORET },
549     {  3,  3, DIFF_HARD,   LOOPY_GRID_DODECAGONAL },
550     {  3,  3, DIFF_HARD,   LOOPY_GRID_GREATDODECAGONAL },
551     {  3,  2, DIFF_HARD,   LOOPY_GRID_GREATGREATDODECAGONAL },
552 #else
553     { 10, 10, DIFF_HARD,   LOOPY_GRID_HONEYCOMB },
554     {  5,  4, DIFF_HARD,   LOOPY_GRID_GREATHEXAGONAL },
555     {  7,  7, DIFF_HARD,   LOOPY_GRID_OCTAGONAL },
556     {  5,  5, DIFF_HARD,   LOOPY_GRID_FLORET },
557     {  5,  4, DIFF_HARD,   LOOPY_GRID_DODECAGONAL },
558     {  5,  4, DIFF_HARD,   LOOPY_GRID_GREATDODECAGONAL },
559     {  5,  3, DIFF_HARD,   LOOPY_GRID_GREATGREATDODECAGONAL },
560 #endif
561 };
562
563 static void preset_menu_add_preset_with_title(struct preset_menu *menu,
564                                               const game_params *params)
565 {
566     char buf[80];
567     game_params *dup_params;
568
569     sprintf(buf, "%dx%d %s - %s", params->h, params->w,
570             gridnames[params->type], diffnames[params->diff]);
571
572     dup_params = snew(game_params);
573     *dup_params = *params;
574
575     preset_menu_add_preset(menu, dupstr(buf), dup_params);
576 }
577
578 static struct preset_menu *game_preset_menu(void)
579 {
580     struct preset_menu *top, *more;
581     int i;
582
583     top = preset_menu_new();
584     for (i = 0; i < lenof(loopy_presets_top); i++)
585         preset_menu_add_preset_with_title(top, &loopy_presets_top[i]);
586
587     more = preset_menu_add_submenu(top, dupstr("More..."));
588     for (i = 0; i < lenof(loopy_presets_more); i++)
589         preset_menu_add_preset_with_title(more, &loopy_presets_more[i]);
590
591     return top;
592 }
593
594 static void free_params(game_params *params)
595 {
596     sfree(params);
597 }
598
599 static void decode_params(game_params *params, char const *string)
600 {
601     params->h = params->w = atoi(string);
602     params->diff = DIFF_EASY;
603     while (*string && isdigit((unsigned char)*string)) string++;
604     if (*string == 'x') {
605         string++;
606         params->h = atoi(string);
607         while (*string && isdigit((unsigned char)*string)) string++;
608     }
609     if (*string == 't') {
610         string++;
611         params->type = atoi(string);
612         while (*string && isdigit((unsigned char)*string)) string++;
613     }
614     if (*string == 'd') {
615         int i;
616         string++;
617         for (i = 0; i < DIFF_MAX; i++)
618             if (*string == diffchars[i])
619                 params->diff = i;
620         if (*string) string++;
621     }
622 }
623
624 static char *encode_params(const game_params *params, int full)
625 {
626     char str[80];
627     sprintf(str, "%dx%dt%d", params->w, params->h, params->type);
628     if (full)
629         sprintf(str + strlen(str), "d%c", diffchars[params->diff]);
630     return dupstr(str);
631 }
632
633 static config_item *game_configure(const game_params *params)
634 {
635     config_item *ret;
636     char buf[80];
637
638     ret = snewn(5, config_item);
639
640     ret[0].name = "Width";
641     ret[0].type = C_STRING;
642     sprintf(buf, "%d", params->w);
643     ret[0].sval = dupstr(buf);
644     ret[0].ival = 0;
645
646     ret[1].name = "Height";
647     ret[1].type = C_STRING;
648     sprintf(buf, "%d", params->h);
649     ret[1].sval = dupstr(buf);
650     ret[1].ival = 0;
651
652     ret[2].name = "Grid type";
653     ret[2].type = C_CHOICES;
654     ret[2].sval = GRID_CONFIGS;
655     ret[2].ival = params->type;
656
657     ret[3].name = "Difficulty";
658     ret[3].type = C_CHOICES;
659     ret[3].sval = DIFFCONFIG;
660     ret[3].ival = params->diff;
661
662     ret[4].name = NULL;
663     ret[4].type = C_END;
664     ret[4].sval = NULL;
665     ret[4].ival = 0;
666
667     return ret;
668 }
669
670 static game_params *custom_params(const config_item *cfg)
671 {
672     game_params *ret = snew(game_params);
673
674     ret->w = atoi(cfg[0].sval);
675     ret->h = atoi(cfg[1].sval);
676     ret->type = cfg[2].ival;
677     ret->diff = cfg[3].ival;
678
679     return ret;
680 }
681
682 static char *validate_params(const game_params *params, int full)
683 {
684     if (params->type < 0 || params->type >= NUM_GRID_TYPES)
685         return "Illegal grid type";
686     if (params->w < grid_size_limits[params->type].amin ||
687         params->h < grid_size_limits[params->type].amin)
688         return grid_size_limits[params->type].aerr;
689     if (params->w < grid_size_limits[params->type].omin &&
690         params->h < grid_size_limits[params->type].omin)
691         return grid_size_limits[params->type].oerr;
692
693     /*
694      * This shouldn't be able to happen at all, since decode_params
695      * and custom_params will never generate anything that isn't
696      * within range.
697      */
698     assert(params->diff < DIFF_MAX);
699
700     return NULL;
701 }
702
703 /* Returns a newly allocated string describing the current puzzle */
704 static char *state_to_text(const game_state *state)
705 {
706     grid *g = state->game_grid;
707     char *retval;
708     int num_faces = g->num_faces;
709     char *description = snewn(num_faces + 1, char);
710     char *dp = description;
711     int empty_count = 0;
712     int i;
713
714     for (i = 0; i < num_faces; i++) {
715         if (state->clues[i] < 0) {
716             if (empty_count > 25) {
717                 dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
718                 empty_count = 0;
719             }
720             empty_count++;
721         } else {
722             if (empty_count) {
723                 dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
724                 empty_count = 0;
725             }
726             dp += sprintf(dp, "%c", (int)CLUE2CHAR(state->clues[i]));
727         }
728     }
729
730     if (empty_count)
731         dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
732
733     retval = dupstr(description);
734     sfree(description);
735
736     return retval;
737 }
738
739 #define GRID_DESC_SEP '_'
740
741 /* Splits up a (optional) grid_desc from the game desc. Returns the
742  * grid_desc (which needs freeing) and updates the desc pointer to
743  * start of real desc, or returns NULL if no desc. */
744 static char *extract_grid_desc(const char **desc)
745 {
746     char *sep = strchr(*desc, GRID_DESC_SEP), *gd;
747     int gd_len;
748
749     if (!sep) return NULL;
750
751     gd_len = sep - (*desc);
752     gd = snewn(gd_len+1, char);
753     memcpy(gd, *desc, gd_len);
754     gd[gd_len] = '\0';
755
756     *desc = sep+1;
757
758     return gd;
759 }
760
761 /* We require that the params pass the test in validate_params and that the
762  * description fills the entire game area */
763 static char *validate_desc(const game_params *params, const char *desc)
764 {
765     int count = 0;
766     grid *g;
767     char *grid_desc, *ret;
768
769     /* It's pretty inefficient to do this just for validation. All we need to
770      * know is the precise number of faces. */
771     grid_desc = extract_grid_desc(&desc);
772     ret = grid_validate_desc(grid_types[params->type], params->w, params->h, grid_desc);
773     if (ret) return ret;
774
775     g = loopy_generate_grid(params, grid_desc);
776     if (grid_desc) sfree(grid_desc);
777
778     for (; *desc; ++desc) {
779         if ((*desc >= '0' && *desc <= '9') || (*desc >= 'A' && *desc <= 'Z')) {
780             count++;
781             continue;
782         }
783         if (*desc >= 'a') {
784             count += *desc - 'a' + 1;
785             continue;
786         }
787         return "Unknown character in description";
788     }
789
790     if (count < g->num_faces)
791         return "Description too short for board size";
792     if (count > g->num_faces)
793         return "Description too long for board size";
794
795     grid_free(g);
796
797     return NULL;
798 }
799
800 /* Sums the lengths of the numbers in range [0,n) */
801 /* See equivalent function in solo.c for justification of this. */
802 static int len_0_to_n(int n)
803 {
804     int len = 1; /* Counting 0 as a bit of a special case */
805     int i;
806
807     for (i = 1; i < n; i *= 10) {
808         len += max(n - i, 0);
809     }
810
811     return len;
812 }
813
814 static char *encode_solve_move(const game_state *state)
815 {
816     int len;
817     char *ret, *p;
818     int i;
819     int num_edges = state->game_grid->num_edges;
820
821     /* This is going to return a string representing the moves needed to set
822      * every line in a grid to be the same as the ones in 'state'.  The exact
823      * length of this string is predictable. */
824
825     len = 1;  /* Count the 'S' prefix */
826     /* Numbers in all lines */
827     len += len_0_to_n(num_edges);
828     /* For each line we also have a letter */
829     len += num_edges;
830
831     ret = snewn(len + 1, char);
832     p = ret;
833
834     p += sprintf(p, "S");
835
836     for (i = 0; i < num_edges; i++) {
837         switch (state->lines[i]) {
838           case LINE_YES:
839             p += sprintf(p, "%dy", i);
840             break;
841           case LINE_NO:
842             p += sprintf(p, "%dn", i);
843             break;
844         }
845     }
846
847     /* No point in doing sums like that if they're going to be wrong */
848     assert(strlen(ret) <= (size_t)len);
849     return ret;
850 }
851
852 static game_ui *new_ui(const game_state *state)
853 {
854     return NULL;
855 }
856
857 static void free_ui(game_ui *ui)
858 {
859 }
860
861 static char *encode_ui(const game_ui *ui)
862 {
863     return NULL;
864 }
865
866 static void decode_ui(game_ui *ui, const char *encoding)
867 {
868 }
869
870 static void game_changed_state(game_ui *ui, const game_state *oldstate,
871                                const game_state *newstate)
872 {
873 }
874
875 static void game_compute_size(const game_params *params, int tilesize,
876                               int *x, int *y)
877 {
878     int grid_width, grid_height, rendered_width, rendered_height;
879     int g_tilesize;
880
881     grid_compute_size(grid_types[params->type], params->w, params->h,
882                       &g_tilesize, &grid_width, &grid_height);
883
884     /* multiply first to minimise rounding error on integer division */
885     rendered_width = grid_width * tilesize / g_tilesize;
886     rendered_height = grid_height * tilesize / g_tilesize;
887     *x = rendered_width + 2 * BORDER(tilesize) + 1;
888     *y = rendered_height + 2 * BORDER(tilesize) + 1;
889 }
890
891 static void game_set_size(drawing *dr, game_drawstate *ds,
892                           const game_params *params, int tilesize)
893 {
894     ds->tilesize = tilesize;
895 }
896
897 static float *game_colours(frontend *fe, int *ncolours)
898 {
899     float *ret = snewn(3 * NCOLOURS, float);
900
901     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
902
903     ret[COL_FOREGROUND * 3 + 0] = 0.0F;
904     ret[COL_FOREGROUND * 3 + 1] = 0.0F;
905     ret[COL_FOREGROUND * 3 + 2] = 0.0F;
906
907     /*
908      * We want COL_LINEUNKNOWN to be a yellow which is a bit darker
909      * than the background. (I previously set it to 0.8,0.8,0, but
910      * found that this went badly with the 0.8,0.8,0.8 favoured as a
911      * background by the Java frontend.)
912      */
913     ret[COL_LINEUNKNOWN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
914     ret[COL_LINEUNKNOWN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F;
915     ret[COL_LINEUNKNOWN * 3 + 2] = 0.0F;
916
917     ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
918     ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
919     ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
920
921     ret[COL_MISTAKE * 3 + 0] = 1.0F;
922     ret[COL_MISTAKE * 3 + 1] = 0.0F;
923     ret[COL_MISTAKE * 3 + 2] = 0.0F;
924
925     ret[COL_SATISFIED * 3 + 0] = 0.0F;
926     ret[COL_SATISFIED * 3 + 1] = 0.0F;
927     ret[COL_SATISFIED * 3 + 2] = 0.0F;
928
929     /* We want the faint lines to be a bit darker than the background.
930      * Except if the background is pretty dark already; then it ought to be a
931      * bit lighter.  Oy vey.
932      */
933     ret[COL_FAINT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
934     ret[COL_FAINT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F;
935     ret[COL_FAINT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.9F;
936
937     *ncolours = NCOLOURS;
938     return ret;
939 }
940
941 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
942 {
943     struct game_drawstate *ds = snew(struct game_drawstate);
944     int num_faces = state->game_grid->num_faces;
945     int num_edges = state->game_grid->num_edges;
946     int i;
947
948     ds->tilesize = 0;
949     ds->started = 0;
950     ds->lines = snewn(num_edges, char);
951     ds->clue_error = snewn(num_faces, char);
952     ds->clue_satisfied = snewn(num_faces, char);
953     ds->textx = snewn(num_faces, int);
954     ds->texty = snewn(num_faces, int);
955     ds->flashing = 0;
956
957     memset(ds->lines, LINE_UNKNOWN, num_edges);
958     memset(ds->clue_error, 0, num_faces);
959     memset(ds->clue_satisfied, 0, num_faces);
960     for (i = 0; i < num_faces; i++)
961         ds->textx[i] = ds->texty[i] = -1;
962
963     return ds;
964 }
965
966 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
967 {
968     sfree(ds->textx);
969     sfree(ds->texty);
970     sfree(ds->clue_error);
971     sfree(ds->clue_satisfied);
972     sfree(ds->lines);
973     sfree(ds);
974 }
975
976 static int game_timing_state(const game_state *state, game_ui *ui)
977 {
978     return TRUE;
979 }
980
981 static float game_anim_length(const game_state *oldstate,
982                               const game_state *newstate, int dir, game_ui *ui)
983 {
984     return 0.0F;
985 }
986
987 static int game_can_format_as_text_now(const game_params *params)
988 {
989     if (params->type != 0)
990         return FALSE;
991     return TRUE;
992 }
993
994 static char *game_text_format(const game_state *state)
995 {
996     int w, h, W, H;
997     int x, y, i;
998     int cell_size;
999     char *ret;
1000     grid *g = state->game_grid;
1001     grid_face *f;
1002
1003     assert(state->grid_type == 0);
1004
1005     /* Work out the basic size unit */
1006     f = g->faces; /* first face */
1007     assert(f->order == 4);
1008     /* The dots are ordered clockwise, so the two opposite
1009      * corners are guaranteed to span the square */
1010     cell_size = abs(f->dots[0]->x - f->dots[2]->x);
1011
1012     w = (g->highest_x - g->lowest_x) / cell_size;
1013     h = (g->highest_y - g->lowest_y) / cell_size;
1014
1015     /* Create a blank "canvas" to "draw" on */
1016     W = 2 * w + 2;
1017     H = 2 * h + 1;
1018     ret = snewn(W * H + 1, char);
1019     for (y = 0; y < H; y++) {
1020         for (x = 0; x < W-1; x++) {
1021             ret[y*W + x] = ' ';
1022         }
1023         ret[y*W + W-1] = '\n';
1024     }
1025     ret[H*W] = '\0';
1026
1027     /* Fill in edge info */
1028     for (i = 0; i < g->num_edges; i++) {
1029         grid_edge *e = g->edges + i;
1030         /* Cell coordinates, from (0,0) to (w-1,h-1) */
1031         int x1 = (e->dot1->x - g->lowest_x) / cell_size;
1032         int x2 = (e->dot2->x - g->lowest_x) / cell_size;
1033         int y1 = (e->dot1->y - g->lowest_y) / cell_size;
1034         int y2 = (e->dot2->y - g->lowest_y) / cell_size;
1035         /* Midpoint, in canvas coordinates (canvas coordinates are just twice
1036          * cell coordinates) */
1037         x = x1 + x2;
1038         y = y1 + y2;
1039         switch (state->lines[i]) {
1040           case LINE_YES:
1041             ret[y*W + x] = (y1 == y2) ? '-' : '|';
1042             break;
1043           case LINE_NO:
1044             ret[y*W + x] = 'x';
1045             break;
1046           case LINE_UNKNOWN:
1047             break; /* already a space */
1048           default:
1049             assert(!"Illegal line state");
1050         }
1051     }
1052
1053     /* Fill in clues */
1054     for (i = 0; i < g->num_faces; i++) {
1055         int x1, x2, y1, y2;
1056
1057         f = g->faces + i;
1058         assert(f->order == 4);
1059         /* Cell coordinates, from (0,0) to (w-1,h-1) */
1060         x1 = (f->dots[0]->x - g->lowest_x) / cell_size;
1061         x2 = (f->dots[2]->x - g->lowest_x) / cell_size;
1062         y1 = (f->dots[0]->y - g->lowest_y) / cell_size;
1063         y2 = (f->dots[2]->y - g->lowest_y) / cell_size;
1064         /* Midpoint, in canvas coordinates */
1065         x = x1 + x2;
1066         y = y1 + y2;
1067         ret[y*W + x] = CLUE2CHAR(state->clues[i]);
1068     }
1069     return ret;
1070 }
1071
1072 /* ----------------------------------------------------------------------
1073  * Debug code
1074  */
1075
1076 #ifdef DEBUG_CACHES
1077 static void check_caches(const solver_state* sstate)
1078 {
1079     int i;
1080     const game_state *state = sstate->state;
1081     const grid *g = state->game_grid;
1082
1083     for (i = 0; i < g->num_dots; i++) {
1084         assert(dot_order(state, i, LINE_YES) == sstate->dot_yes_count[i]);
1085         assert(dot_order(state, i, LINE_NO) == sstate->dot_no_count[i]);
1086     }
1087
1088     for (i = 0; i < g->num_faces; i++) {
1089         assert(face_order(state, i, LINE_YES) == sstate->face_yes_count[i]);
1090         assert(face_order(state, i, LINE_NO) == sstate->face_no_count[i]);
1091     }
1092 }
1093
1094 #if 0
1095 #define check_caches(s) \
1096     do { \
1097         fprintf(stderr, "check_caches at line %d\n", __LINE__); \
1098         check_caches(s); \
1099     } while (0)
1100 #endif
1101 #endif /* DEBUG_CACHES */
1102
1103 /* ----------------------------------------------------------------------
1104  * Solver utility functions
1105  */
1106
1107 /* Sets the line (with index i) to the new state 'line_new', and updates
1108  * the cached counts of any affected faces and dots.
1109  * Returns TRUE if this actually changed the line's state. */
1110 static int solver_set_line(solver_state *sstate, int i,
1111                            enum line_state line_new
1112 #ifdef SHOW_WORKING
1113                            , const char *reason
1114 #endif
1115                            )
1116 {
1117     game_state *state = sstate->state;
1118     grid *g;
1119     grid_edge *e;
1120
1121     assert(line_new != LINE_UNKNOWN);
1122
1123     check_caches(sstate);
1124
1125     if (state->lines[i] == line_new) {
1126         return FALSE; /* nothing changed */
1127     }
1128     state->lines[i] = line_new;
1129
1130 #ifdef SHOW_WORKING
1131     fprintf(stderr, "solver: set line [%d] to %s (%s)\n",
1132             i, line_new == LINE_YES ? "YES" : "NO",
1133             reason);
1134 #endif
1135
1136     g = state->game_grid;
1137     e = g->edges + i;
1138
1139     /* Update the cache for both dots and both faces affected by this. */
1140     if (line_new == LINE_YES) {
1141         sstate->dot_yes_count[e->dot1 - g->dots]++;
1142         sstate->dot_yes_count[e->dot2 - g->dots]++;
1143         if (e->face1) {
1144             sstate->face_yes_count[e->face1 - g->faces]++;
1145         }
1146         if (e->face2) {
1147             sstate->face_yes_count[e->face2 - g->faces]++;
1148         }
1149     } else {
1150         sstate->dot_no_count[e->dot1 - g->dots]++;
1151         sstate->dot_no_count[e->dot2 - g->dots]++;
1152         if (e->face1) {
1153             sstate->face_no_count[e->face1 - g->faces]++;
1154         }
1155         if (e->face2) {
1156             sstate->face_no_count[e->face2 - g->faces]++;
1157         }
1158     }
1159
1160     check_caches(sstate);
1161     return TRUE;
1162 }
1163
1164 #ifdef SHOW_WORKING
1165 #define solver_set_line(a, b, c) \
1166     solver_set_line(a, b, c, __FUNCTION__)
1167 #endif
1168
1169 /*
1170  * Merge two dots due to the existence of an edge between them.
1171  * Updates the dsf tracking equivalence classes, and keeps track of
1172  * the length of path each dot is currently a part of.
1173  * Returns TRUE if the dots were already linked, ie if they are part of a
1174  * closed loop, and false otherwise.
1175  */
1176 static int merge_dots(solver_state *sstate, int edge_index)
1177 {
1178     int i, j, len;
1179     grid *g = sstate->state->game_grid;
1180     grid_edge *e = g->edges + edge_index;
1181
1182     i = e->dot1 - g->dots;
1183     j = e->dot2 - g->dots;
1184
1185     i = dsf_canonify(sstate->dotdsf, i);
1186     j = dsf_canonify(sstate->dotdsf, j);
1187
1188     if (i == j) {
1189         return TRUE;
1190     } else {
1191         len = sstate->looplen[i] + sstate->looplen[j];
1192         dsf_merge(sstate->dotdsf, i, j);
1193         i = dsf_canonify(sstate->dotdsf, i);
1194         sstate->looplen[i] = len;
1195         return FALSE;
1196     }
1197 }
1198
1199 /* Merge two lines because the solver has deduced that they must be either
1200  * identical or opposite.   Returns TRUE if this is new information, otherwise
1201  * FALSE. */
1202 static int merge_lines(solver_state *sstate, int i, int j, int inverse
1203 #ifdef SHOW_WORKING
1204                        , const char *reason
1205 #endif
1206                        )
1207 {
1208     int inv_tmp;
1209
1210     assert(i < sstate->state->game_grid->num_edges);
1211     assert(j < sstate->state->game_grid->num_edges);
1212
1213     i = edsf_canonify(sstate->linedsf, i, &inv_tmp);
1214     inverse ^= inv_tmp;
1215     j = edsf_canonify(sstate->linedsf, j, &inv_tmp);
1216     inverse ^= inv_tmp;
1217
1218     edsf_merge(sstate->linedsf, i, j, inverse);
1219
1220 #ifdef SHOW_WORKING
1221     if (i != j) {
1222         fprintf(stderr, "%s [%d] [%d] %s(%s)\n",
1223                 __FUNCTION__, i, j,
1224                 inverse ? "inverse " : "", reason);
1225     }
1226 #endif
1227     return (i != j);
1228 }
1229
1230 #ifdef SHOW_WORKING
1231 #define merge_lines(a, b, c, d) \
1232     merge_lines(a, b, c, d, __FUNCTION__)
1233 #endif
1234
1235 /* Count the number of lines of a particular type currently going into the
1236  * given dot. */
1237 static int dot_order(const game_state* state, int dot, char line_type)
1238 {
1239     int n = 0;
1240     grid *g = state->game_grid;
1241     grid_dot *d = g->dots + dot;
1242     int i;
1243
1244     for (i = 0; i < d->order; i++) {
1245         grid_edge *e = d->edges[i];
1246         if (state->lines[e - g->edges] == line_type)
1247             ++n;
1248     }
1249     return n;
1250 }
1251
1252 /* Count the number of lines of a particular type currently surrounding the
1253  * given face */
1254 static int face_order(const game_state* state, int face, char line_type)
1255 {
1256     int n = 0;
1257     grid *g = state->game_grid;
1258     grid_face *f = g->faces + face;
1259     int i;
1260
1261     for (i = 0; i < f->order; i++) {
1262         grid_edge *e = f->edges[i];
1263         if (state->lines[e - g->edges] == line_type)
1264             ++n;
1265     }
1266     return n;
1267 }
1268
1269 /* Set all lines bordering a dot of type old_type to type new_type
1270  * Return value tells caller whether this function actually did anything */
1271 static int dot_setall(solver_state *sstate, int dot,
1272                       char old_type, char new_type)
1273 {
1274     int retval = FALSE, r;
1275     game_state *state = sstate->state;
1276     grid *g;
1277     grid_dot *d;
1278     int i;
1279
1280     if (old_type == new_type)
1281         return FALSE;
1282
1283     g = state->game_grid;
1284     d = g->dots + dot;
1285
1286     for (i = 0; i < d->order; i++) {
1287         int line_index = d->edges[i] - g->edges;
1288         if (state->lines[line_index] == old_type) {
1289             r = solver_set_line(sstate, line_index, new_type);
1290             assert(r == TRUE);
1291             retval = TRUE;
1292         }
1293     }
1294     return retval;
1295 }
1296
1297 /* Set all lines bordering a face of type old_type to type new_type */
1298 static int face_setall(solver_state *sstate, int face,
1299                        char old_type, char new_type)
1300 {
1301     int retval = FALSE, r;
1302     game_state *state = sstate->state;
1303     grid *g;
1304     grid_face *f;
1305     int i;
1306
1307     if (old_type == new_type)
1308         return FALSE;
1309
1310     g = state->game_grid;
1311     f = g->faces + face;
1312
1313     for (i = 0; i < f->order; i++) {
1314         int line_index = f->edges[i] - g->edges;
1315         if (state->lines[line_index] == old_type) {
1316             r = solver_set_line(sstate, line_index, new_type);
1317             assert(r == TRUE);
1318             retval = TRUE;
1319         }
1320     }
1321     return retval;
1322 }
1323
1324 /* ----------------------------------------------------------------------
1325  * Loop generation and clue removal
1326  */
1327
1328 static void add_full_clues(game_state *state, random_state *rs)
1329 {
1330     signed char *clues = state->clues;
1331     grid *g = state->game_grid;
1332     char *board = snewn(g->num_faces, char);
1333     int i;
1334
1335     generate_loop(g, board, rs, NULL, NULL);
1336
1337     /* Fill out all the clues by initialising to 0, then iterating over
1338      * all edges and incrementing each clue as we find edges that border
1339      * between BLACK/WHITE faces.  While we're at it, we verify that the
1340      * algorithm does work, and there aren't any GREY faces still there. */
1341     memset(clues, 0, g->num_faces);
1342     for (i = 0; i < g->num_edges; i++) {
1343         grid_edge *e = g->edges + i;
1344         grid_face *f1 = e->face1;
1345         grid_face *f2 = e->face2;
1346         enum face_colour c1 = FACE_COLOUR(f1);
1347         enum face_colour c2 = FACE_COLOUR(f2);
1348         assert(c1 != FACE_GREY);
1349         assert(c2 != FACE_GREY);
1350         if (c1 != c2) {
1351             if (f1) clues[f1 - g->faces]++;
1352             if (f2) clues[f2 - g->faces]++;
1353         }
1354     }
1355     sfree(board);
1356 }
1357
1358
1359 static int game_has_unique_soln(const game_state *state, int diff)
1360 {
1361     int ret;
1362     solver_state *sstate_new;
1363     solver_state *sstate = new_solver_state((game_state *)state, diff);
1364
1365     sstate_new = solve_game_rec(sstate);
1366
1367     assert(sstate_new->solver_status != SOLVER_MISTAKE);
1368     ret = (sstate_new->solver_status == SOLVER_SOLVED);
1369
1370     free_solver_state(sstate_new);
1371     free_solver_state(sstate);
1372
1373     return ret;
1374 }
1375
1376
1377 /* Remove clues one at a time at random. */
1378 static game_state *remove_clues(game_state *state, random_state *rs,
1379                                 int diff)
1380 {
1381     int *face_list;
1382     int num_faces = state->game_grid->num_faces;
1383     game_state *ret = dup_game(state), *saved_ret;
1384     int n;
1385
1386     /* We need to remove some clues.  We'll do this by forming a list of all
1387      * available clues, shuffling it, then going along one at a
1388      * time clearing each clue in turn for which doing so doesn't render the
1389      * board unsolvable. */
1390     face_list = snewn(num_faces, int);
1391     for (n = 0; n < num_faces; ++n) {
1392         face_list[n] = n;
1393     }
1394
1395     shuffle(face_list, num_faces, sizeof(int), rs);
1396
1397     for (n = 0; n < num_faces; ++n) {
1398         saved_ret = dup_game(ret);
1399         ret->clues[face_list[n]] = -1;
1400
1401         if (game_has_unique_soln(ret, diff)) {
1402             free_game(saved_ret);
1403         } else {
1404             free_game(ret);
1405             ret = saved_ret;
1406         }
1407     }
1408     sfree(face_list);
1409
1410     return ret;
1411 }
1412
1413
1414 static char *new_game_desc(const game_params *params, random_state *rs,
1415                            char **aux, int interactive)
1416 {
1417     /* solution and description both use run-length encoding in obvious ways */
1418     char *retval, *game_desc, *grid_desc;
1419     grid *g;
1420     game_state *state = snew(game_state);
1421     game_state *state_new;
1422
1423     grid_desc = grid_new_desc(grid_types[params->type], params->w, params->h, rs);
1424     state->game_grid = g = loopy_generate_grid(params, grid_desc);
1425
1426     state->clues = snewn(g->num_faces, signed char);
1427     state->lines = snewn(g->num_edges, char);
1428     state->line_errors = snewn(g->num_edges, unsigned char);
1429     state->exactly_one_loop = FALSE;
1430
1431     state->grid_type = params->type;
1432
1433     newboard_please:
1434
1435     memset(state->lines, LINE_UNKNOWN, g->num_edges);
1436     memset(state->line_errors, 0, g->num_edges);
1437
1438     state->solved = state->cheated = FALSE;
1439
1440     /* Get a new random solvable board with all its clues filled in.  Yes, this
1441      * can loop for ever if the params are suitably unfavourable, but
1442      * preventing games smaller than 4x4 seems to stop this happening */
1443     do {
1444         add_full_clues(state, rs);
1445     } while (!game_has_unique_soln(state, params->diff));
1446
1447     state_new = remove_clues(state, rs, params->diff);
1448     free_game(state);
1449     state = state_new;
1450
1451
1452     if (params->diff > 0 && game_has_unique_soln(state, params->diff-1)) {
1453 #ifdef SHOW_WORKING
1454         fprintf(stderr, "Rejecting board, it is too easy\n");
1455 #endif
1456         goto newboard_please;
1457     }
1458
1459     game_desc = state_to_text(state);
1460
1461     free_game(state);
1462
1463     if (grid_desc) {
1464         retval = snewn(strlen(grid_desc) + 1 + strlen(game_desc) + 1, char);
1465         sprintf(retval, "%s%c%s", grid_desc, (int)GRID_DESC_SEP, game_desc);
1466         sfree(grid_desc);
1467         sfree(game_desc);
1468     } else {
1469         retval = game_desc;
1470     }
1471
1472     assert(!validate_desc(params, retval));
1473
1474     return retval;
1475 }
1476
1477 static game_state *new_game(midend *me, const game_params *params,
1478                             const char *desc)
1479 {
1480     int i;
1481     game_state *state = snew(game_state);
1482     int empties_to_make = 0;
1483     int n,n2;
1484     const char *dp;
1485     char *grid_desc;
1486     grid *g;
1487     int num_faces, num_edges;
1488
1489     grid_desc = extract_grid_desc(&desc);
1490     state->game_grid = g = loopy_generate_grid(params, grid_desc);
1491     if (grid_desc) sfree(grid_desc);
1492
1493     dp = desc;
1494
1495     num_faces = g->num_faces;
1496     num_edges = g->num_edges;
1497
1498     state->clues = snewn(num_faces, signed char);
1499     state->lines = snewn(num_edges, char);
1500     state->line_errors = snewn(num_edges, unsigned char);
1501     state->exactly_one_loop = FALSE;
1502
1503     state->solved = state->cheated = FALSE;
1504
1505     state->grid_type = params->type;
1506
1507     for (i = 0; i < num_faces; i++) {
1508         if (empties_to_make) {
1509             empties_to_make--;
1510             state->clues[i] = -1;
1511             continue;
1512         }
1513
1514         assert(*dp);
1515         n = *dp - '0';
1516         n2 = *dp - 'A' + 10;
1517         if (n >= 0 && n < 10) {
1518             state->clues[i] = n;
1519         } else if (n2 >= 10 && n2 < 36) {
1520             state->clues[i] = n2;
1521         } else {
1522             n = *dp - 'a' + 1;
1523             assert(n > 0);
1524             state->clues[i] = -1;
1525             empties_to_make = n - 1;
1526         }
1527         ++dp;
1528     }
1529
1530     memset(state->lines, LINE_UNKNOWN, num_edges);
1531     memset(state->line_errors, 0, num_edges);
1532     return state;
1533 }
1534
1535 /* Calculates the line_errors data, and checks if the current state is a
1536  * solution */
1537 static int check_completion(game_state *state)
1538 {
1539     grid *g = state->game_grid;
1540     int i, ret;
1541     int *dsf, *component_state;
1542     int nsilly, nloop, npath, largest_comp, largest_size, total_pathsize;
1543     enum { COMP_NONE, COMP_LOOP, COMP_PATH, COMP_SILLY, COMP_EMPTY };
1544
1545     memset(state->line_errors, 0, g->num_edges);
1546
1547     /*
1548      * Find loops in the grid, and determine whether the puzzle is
1549      * solved.
1550      *
1551      * Loopy is a bit more complicated than most puzzles that care
1552      * about loop detection. In most of them, loops are simply
1553      * _forbidden_; so the obviously right way to do
1554      * error-highlighting during play is to light up a graph edge red
1555      * iff it is part of a loop, which is exactly what the centralised
1556      * findloop.c makes easy.
1557      *
1558      * But Loopy is unusual in that you're _supposed_ to be making a
1559      * loop - and yet _some_ loops are not the right loop. So we need
1560      * to be more discriminating, by identifying loops one by one and
1561      * then thinking about which ones to highlight, and so findloop.c
1562      * isn't quite the right tool for the job in this case.
1563      *
1564      * Worse still, consider situations in which the grid contains a
1565      * loop and also some non-loop edges: there are some cases like
1566      * this in which the user's intuitive expectation would be to
1567      * highlight the loop (if you're only about half way through the
1568      * puzzle and have accidentally made a little loop in some corner
1569      * of the grid), and others in which they'd be more likely to
1570      * expect you to highlight the non-loop edges (if you've just
1571      * closed off a whole loop that you thought was the entire
1572      * solution, but forgot some disconnected edges in a corner
1573      * somewhere). So while it's easy enough to check whether the
1574      * solution is _right_, highlighting the wrong parts is a tricky
1575      * problem for this puzzle!
1576      *
1577      * I'd quite like, in some situations, to identify the largest
1578      * loop among the player's YES edges, and then light up everything
1579      * other than that. But finding the longest cycle in a graph is an
1580      * NP-complete problem (because, in particular, it must return a
1581      * Hamilton cycle if one exists).
1582      *
1583      * However, I think we can make the problem tractable by
1584      * exercising the Puzzles principle that it isn't absolutely
1585      * necessary to highlight _all_ errors: the key point is that by
1586      * the time the user has filled in the whole grid, they should
1587      * either have seen a completion flash, or have _some_ error
1588      * highlight showing them why the solution isn't right. So in
1589      * principle it would be *just about* good enough to highlight
1590      * just one error in the whole grid, if there was really no better
1591      * way. But we'd like to highlight as many errors as possible.
1592      *
1593      * In this case, I think the simple approach is to make use of the
1594      * fact that no vertex may have degree > 2, and that's really
1595      * simple to detect. So the plan goes like this:
1596      *
1597      *  - Form the dsf of connected components of the graph vertices.
1598      *
1599      *  - Highlight an error at any vertex with degree > 2. (It so
1600      *    happens that we do this by lighting up all the edges
1601      *    incident to that vertex, but that's an output detail.)
1602      *
1603      *  - Any component that contains such a vertex is now excluded
1604      *    from further consideration, because it already has a
1605      *    highlight.
1606      *
1607      *  - The remaining components have no vertex with degree > 2, and
1608      *    hence they all consist of either a simple loop, or a simple
1609      *    path with two endpoints.
1610      *
1611      *  - For these purposes, group together all the paths and imagine
1612      *    them to be a single component (because in most normal
1613      *    situations the player will gradually build up the solution
1614      *    _not_ all in one connected segment, but as lots of separate
1615      *    little path pieces that gradually connect to each other).
1616      *
1617      *  - After doing that, if there is exactly one (sensible)
1618      *    component - be it a collection of paths or a loop - then
1619      *    highlight no further edge errors. (The former case is normal
1620      *    during play, and the latter is a potentially solved puzzle.)
1621      *
1622      *  - Otherwise, find the largest of the sensible components,
1623      *    leave that one unhighlighted, and light the rest up in red.
1624      */
1625
1626     dsf = snew_dsf(g->num_dots);
1627
1628     /* Build the dsf. */
1629     for (i = 0; i < g->num_edges; i++) {
1630         if (state->lines[i] == LINE_YES) {
1631             grid_edge *e = g->edges + i;
1632             int d1 = e->dot1 - g->dots, d2 = e->dot2 - g->dots;
1633             dsf_merge(dsf, d1, d2);
1634         }
1635     }
1636
1637     /* Initialise a state variable for each connected component. */
1638     component_state = snewn(g->num_dots, int);
1639     for (i = 0; i < g->num_dots; i++) {
1640         if (dsf_canonify(dsf, i) == i)
1641             component_state[i] = COMP_LOOP;
1642         else
1643             component_state[i] = COMP_NONE;
1644     }
1645
1646     /* Check for dots with degree > 3. Here we also spot dots of
1647      * degree 1 in which the user has marked all the non-edges as
1648      * LINE_NO, because those are also clear vertex-level errors, so
1649      * we give them the same treatment of excluding their connected
1650      * component from the subsequent loop analysis. */
1651     for (i = 0; i < g->num_dots; i++) {
1652         int comp = dsf_canonify(dsf, i);
1653         int yes = dot_order(state, i, LINE_YES);
1654         int unknown = dot_order(state, i, LINE_UNKNOWN);
1655         if ((yes == 1 && unknown == 0) || (yes >= 3)) {
1656             /* violation, so mark all YES edges as errors */
1657             grid_dot *d = g->dots + i;
1658             int j;
1659             for (j = 0; j < d->order; j++) {
1660                 int e = d->edges[j] - g->edges;
1661                 if (state->lines[e] == LINE_YES)
1662                     state->line_errors[e] = TRUE;
1663             }
1664             /* And mark this component as not worthy of further
1665              * consideration. */
1666             component_state[comp] = COMP_SILLY;
1667
1668         } else if (yes == 0) {
1669             /* A completely isolated dot must also be excluded it from
1670              * the subsequent loop highlighting pass, but we tag it
1671              * with a different enum value to avoid it counting
1672              * towards the components that inhibit returning a win
1673              * status. */
1674             component_state[comp] = COMP_EMPTY;
1675         } else if (yes == 1) {
1676             /* A dot with degree 1 that didn't fall into the 'clearly
1677              * erroneous' case above indicates that this connected
1678              * component will be a path rather than a loop - unless
1679              * something worse elsewhere in the component has
1680              * classified it as silly. */
1681             if (component_state[comp] != COMP_SILLY)
1682                 component_state[comp] = COMP_PATH;
1683         }
1684     }
1685
1686     /* Count up the components. Also, find the largest sensible
1687      * component. (Tie-breaking condition is derived from the order of
1688      * vertices in the grid data structure, which is fairly arbitrary
1689      * but at least stays stable throughout the game.) */
1690     nsilly = nloop = npath = 0;
1691     total_pathsize = 0;
1692     largest_comp = largest_size = -1;
1693     for (i = 0; i < g->num_dots; i++) {
1694         if (component_state[i] == COMP_SILLY) {
1695             nsilly++;
1696         } else if (component_state[i] == COMP_PATH) {
1697             total_pathsize += dsf_size(dsf, i);
1698             npath = 1;
1699         } else if (component_state[i] == COMP_LOOP) {
1700             int this_size;
1701
1702             nloop++;
1703
1704             if ((this_size = dsf_size(dsf, i)) > largest_size) {
1705                 largest_comp = i;
1706                 largest_size = this_size;
1707             }
1708         }
1709     }
1710     if (largest_size < total_pathsize) {
1711         largest_comp = -1;             /* means the paths */
1712         largest_size = total_pathsize;
1713     }
1714
1715     if (nloop > 0 && nloop + npath > 1) {
1716         /*
1717          * If there are at least two sensible components including at
1718          * least one loop, highlight all edges in every sensible
1719          * component that is not the largest one.
1720          */
1721         for (i = 0; i < g->num_edges; i++) {
1722             if (state->lines[i] == LINE_YES) {
1723                 grid_edge *e = g->edges + i;
1724                 int d1 = e->dot1 - g->dots; /* either endpoint is good enough */
1725                 int comp = dsf_canonify(dsf, d1);
1726                 if ((component_state[comp] == COMP_PATH &&
1727                      -1 != largest_comp) ||
1728                     (component_state[comp] == COMP_LOOP &&
1729                      comp != largest_comp))
1730                     state->line_errors[i] = TRUE;
1731             }
1732         }
1733     }
1734
1735     if (nloop == 1 && npath == 0 && nsilly == 0) {
1736         /*
1737          * If there is exactly one component and it is a loop, then
1738          * the puzzle is potentially complete, so check the clues.
1739          */
1740         ret = TRUE;
1741
1742         for (i = 0; i < g->num_faces; i++) {
1743             int c = state->clues[i];
1744             if (c >= 0 && face_order(state, i, LINE_YES) != c) {
1745                 ret = FALSE;
1746                 break;
1747             }
1748         }
1749
1750         /*
1751          * Also, whether or not the puzzle is actually complete, set
1752          * the flag that says this game_state has exactly one loop and
1753          * nothing else, which will be used to vary the semantics of
1754          * clue highlighting at display time.
1755          */
1756         state->exactly_one_loop = TRUE;
1757     } else {
1758         ret = FALSE;
1759         state->exactly_one_loop = FALSE;
1760     }
1761
1762     sfree(component_state);
1763     sfree(dsf);
1764
1765     return ret;
1766 }
1767
1768 /* ----------------------------------------------------------------------
1769  * Solver logic
1770  *
1771  * Our solver modes operate as follows.  Each mode also uses the modes above it.
1772  *
1773  *   Easy Mode
1774  *   Just implement the rules of the game.
1775  *
1776  *   Normal and Tricky Modes
1777  *   For each (adjacent) pair of lines through each dot we store a bit for
1778  *   whether at least one of them is on and whether at most one is on.  (If we
1779  *   know both or neither is on that's already stored more directly.)
1780  *
1781  *   Advanced Mode
1782  *   Use edsf data structure to make equivalence classes of lines that are
1783  *   known identical to or opposite to one another.
1784  */
1785
1786
1787 /* DLines:
1788  * For general grids, we consider "dlines" to be pairs of lines joined
1789  * at a dot.  The lines must be adjacent around the dot, so we can think of
1790  * a dline as being a dot+face combination.  Or, a dot+edge combination where
1791  * the second edge is taken to be the next clockwise edge from the dot.
1792  * Original loopy code didn't have this extra restriction of the lines being
1793  * adjacent.  From my tests with square grids, this extra restriction seems to
1794  * take little, if anything, away from the quality of the puzzles.
1795  * A dline can be uniquely identified by an edge/dot combination, given that
1796  * a dline-pair always goes clockwise around its common dot.  The edge/dot
1797  * combination can be represented by an edge/bool combination - if bool is
1798  * TRUE, use edge->dot1 else use edge->dot2.  So the total number of dlines is
1799  * exactly twice the number of edges in the grid - although the dlines
1800  * spanning the infinite face are not all that useful to the solver.
1801  * Note that, by convention, a dline goes clockwise around its common dot,
1802  * which means the dline goes anti-clockwise around its common face.
1803  */
1804
1805 /* Helper functions for obtaining an index into an array of dlines, given
1806  * various information.  We assume the grid layout conventions about how
1807  * the various lists are interleaved - see grid_make_consistent() for
1808  * details. */
1809
1810 /* i points to the first edge of the dline pair, reading clockwise around
1811  * the dot. */
1812 static int dline_index_from_dot(grid *g, grid_dot *d, int i)
1813 {
1814     grid_edge *e = d->edges[i];
1815     int ret;
1816 #ifdef DEBUG_DLINES
1817     grid_edge *e2;
1818     int i2 = i+1;
1819     if (i2 == d->order) i2 = 0;
1820     e2 = d->edges[i2];
1821 #endif
1822     ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0);
1823 #ifdef DEBUG_DLINES
1824     printf("dline_index_from_dot: d=%d,i=%d, edges [%d,%d] - %d\n",
1825            (int)(d - g->dots), i, (int)(e - g->edges),
1826            (int)(e2 - g->edges), ret);
1827 #endif
1828     return ret;
1829 }
1830 /* i points to the second edge of the dline pair, reading clockwise around
1831  * the face.  That is, the edges of the dline, starting at edge{i}, read
1832  * anti-clockwise around the face.  By layout conventions, the common dot
1833  * of the dline will be f->dots[i] */
1834 static int dline_index_from_face(grid *g, grid_face *f, int i)
1835 {
1836     grid_edge *e = f->edges[i];
1837     grid_dot *d = f->dots[i];
1838     int ret;
1839 #ifdef DEBUG_DLINES
1840     grid_edge *e2;
1841     int i2 = i - 1;
1842     if (i2 < 0) i2 += f->order;
1843     e2 = f->edges[i2];
1844 #endif
1845     ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0);
1846 #ifdef DEBUG_DLINES
1847     printf("dline_index_from_face: f=%d,i=%d, edges [%d,%d] - %d\n",
1848            (int)(f - g->faces), i, (int)(e - g->edges),
1849            (int)(e2 - g->edges), ret);
1850 #endif
1851     return ret;
1852 }
1853 static int is_atleastone(const char *dline_array, int index)
1854 {
1855     return BIT_SET(dline_array[index], 0);
1856 }
1857 static int set_atleastone(char *dline_array, int index)
1858 {
1859     return SET_BIT(dline_array[index], 0);
1860 }
1861 static int is_atmostone(const char *dline_array, int index)
1862 {
1863     return BIT_SET(dline_array[index], 1);
1864 }
1865 static int set_atmostone(char *dline_array, int index)
1866 {
1867     return SET_BIT(dline_array[index], 1);
1868 }
1869
1870 static void array_setall(char *array, char from, char to, int len)
1871 {
1872     char *p = array, *p_old = p;
1873     int len_remaining = len;
1874
1875     while ((p = memchr(p, from, len_remaining))) {
1876         *p = to;
1877         len_remaining -= p - p_old;
1878         p_old = p;
1879     }
1880 }
1881
1882 /* Helper, called when doing dline dot deductions, in the case where we
1883  * have 4 UNKNOWNs, and two of them (adjacent) have *exactly* one YES between
1884  * them (because of dline atmostone/atleastone).
1885  * On entry, edge points to the first of these two UNKNOWNs.  This function
1886  * will find the opposite UNKNOWNS (if they are adjacent to one another)
1887  * and set their corresponding dline to atleastone.  (Setting atmostone
1888  * already happens in earlier dline deductions) */
1889 static int dline_set_opp_atleastone(solver_state *sstate,
1890                                     grid_dot *d, int edge)
1891 {
1892     game_state *state = sstate->state;
1893     grid *g = state->game_grid;
1894     int N = d->order;
1895     int opp, opp2;
1896     for (opp = 0; opp < N; opp++) {
1897         int opp_dline_index;
1898         if (opp == edge || opp == edge+1 || opp == edge-1)
1899             continue;
1900         if (opp == 0 && edge == N-1)
1901             continue;
1902         if (opp == N-1 && edge == 0)
1903             continue;
1904         opp2 = opp + 1;
1905         if (opp2 == N) opp2 = 0;
1906         /* Check if opp, opp2 point to LINE_UNKNOWNs */
1907         if (state->lines[d->edges[opp] - g->edges] != LINE_UNKNOWN)
1908             continue;
1909         if (state->lines[d->edges[opp2] - g->edges] != LINE_UNKNOWN)
1910             continue;
1911         /* Found opposite UNKNOWNS and they're next to each other */
1912         opp_dline_index = dline_index_from_dot(g, d, opp);
1913         return set_atleastone(sstate->dlines, opp_dline_index);
1914     }
1915     return FALSE;
1916 }
1917
1918
1919 /* Set pairs of lines around this face which are known to be identical, to
1920  * the given line_state */
1921 static int face_setall_identical(solver_state *sstate, int face_index,
1922                                  enum line_state line_new)
1923 {
1924     /* can[dir] contains the canonical line associated with the line in
1925      * direction dir from the square in question.  Similarly inv[dir] is
1926      * whether or not the line in question is inverse to its canonical
1927      * element. */
1928     int retval = FALSE;
1929     game_state *state = sstate->state;
1930     grid *g = state->game_grid;
1931     grid_face *f = g->faces + face_index;
1932     int N = f->order;
1933     int i, j;
1934     int can1, can2, inv1, inv2;
1935
1936     for (i = 0; i < N; i++) {
1937         int line1_index = f->edges[i] - g->edges;
1938         if (state->lines[line1_index] != LINE_UNKNOWN)
1939             continue;
1940         for (j = i + 1; j < N; j++) {
1941             int line2_index = f->edges[j] - g->edges;
1942             if (state->lines[line2_index] != LINE_UNKNOWN)
1943                 continue;
1944
1945             /* Found two UNKNOWNS */
1946             can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1);
1947             can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2);
1948             if (can1 == can2 && inv1 == inv2) {
1949                 solver_set_line(sstate, line1_index, line_new);
1950                 solver_set_line(sstate, line2_index, line_new);
1951             }
1952         }
1953     }
1954     return retval;
1955 }
1956
1957 /* Given a dot or face, and a count of LINE_UNKNOWNs, find them and
1958  * return the edge indices into e. */
1959 static void find_unknowns(game_state *state,
1960     grid_edge **edge_list, /* Edge list to search (from a face or a dot) */
1961     int expected_count, /* Number of UNKNOWNs (comes from solver's cache) */
1962     int *e /* Returned edge indices */)
1963 {
1964     int c = 0;
1965     grid *g = state->game_grid;
1966     while (c < expected_count) {
1967         int line_index = *edge_list - g->edges;
1968         if (state->lines[line_index] == LINE_UNKNOWN) {
1969             e[c] = line_index;
1970             c++;
1971         }
1972         ++edge_list;
1973     }
1974 }
1975
1976 /* If we have a list of edges, and we know whether the number of YESs should
1977  * be odd or even, and there are only a few UNKNOWNs, we can do some simple
1978  * linedsf deductions.  This can be used for both face and dot deductions.
1979  * Returns the difficulty level of the next solver that should be used,
1980  * or DIFF_MAX if no progress was made. */
1981 static int parity_deductions(solver_state *sstate,
1982     grid_edge **edge_list, /* Edge list (from a face or a dot) */
1983     int total_parity, /* Expected number of YESs modulo 2 (either 0 or 1) */
1984     int unknown_count)
1985 {
1986     game_state *state = sstate->state;
1987     int diff = DIFF_MAX;
1988     int *linedsf = sstate->linedsf;
1989
1990     if (unknown_count == 2) {
1991         /* Lines are known alike/opposite, depending on inv. */
1992         int e[2];
1993         find_unknowns(state, edge_list, 2, e);
1994         if (merge_lines(sstate, e[0], e[1], total_parity))
1995             diff = min(diff, DIFF_HARD);
1996     } else if (unknown_count == 3) {
1997         int e[3];
1998         int can[3]; /* canonical edges */
1999         int inv[3]; /* whether can[x] is inverse to e[x] */
2000         find_unknowns(state, edge_list, 3, e);
2001         can[0] = edsf_canonify(linedsf, e[0], inv);
2002         can[1] = edsf_canonify(linedsf, e[1], inv+1);
2003         can[2] = edsf_canonify(linedsf, e[2], inv+2);
2004         if (can[0] == can[1]) {
2005             if (solver_set_line(sstate, e[2], (total_parity^inv[0]^inv[1]) ?
2006                                 LINE_YES : LINE_NO))
2007                 diff = min(diff, DIFF_EASY);
2008         }
2009         if (can[0] == can[2]) {
2010             if (solver_set_line(sstate, e[1], (total_parity^inv[0]^inv[2]) ?
2011                                 LINE_YES : LINE_NO))
2012                 diff = min(diff, DIFF_EASY);
2013         }
2014         if (can[1] == can[2]) {
2015             if (solver_set_line(sstate, e[0], (total_parity^inv[1]^inv[2]) ?
2016                                 LINE_YES : LINE_NO))
2017                 diff = min(diff, DIFF_EASY);
2018         }
2019     } else if (unknown_count == 4) {
2020         int e[4];
2021         int can[4]; /* canonical edges */
2022         int inv[4]; /* whether can[x] is inverse to e[x] */
2023         find_unknowns(state, edge_list, 4, e);
2024         can[0] = edsf_canonify(linedsf, e[0], inv);
2025         can[1] = edsf_canonify(linedsf, e[1], inv+1);
2026         can[2] = edsf_canonify(linedsf, e[2], inv+2);
2027         can[3] = edsf_canonify(linedsf, e[3], inv+3);
2028         if (can[0] == can[1]) {
2029             if (merge_lines(sstate, e[2], e[3], total_parity^inv[0]^inv[1]))
2030                 diff = min(diff, DIFF_HARD);
2031         } else if (can[0] == can[2]) {
2032             if (merge_lines(sstate, e[1], e[3], total_parity^inv[0]^inv[2]))
2033                 diff = min(diff, DIFF_HARD);
2034         } else if (can[0] == can[3]) {
2035             if (merge_lines(sstate, e[1], e[2], total_parity^inv[0]^inv[3]))
2036                 diff = min(diff, DIFF_HARD);
2037         } else if (can[1] == can[2]) {
2038             if (merge_lines(sstate, e[0], e[3], total_parity^inv[1]^inv[2]))
2039                 diff = min(diff, DIFF_HARD);
2040         } else if (can[1] == can[3]) {
2041             if (merge_lines(sstate, e[0], e[2], total_parity^inv[1]^inv[3]))
2042                 diff = min(diff, DIFF_HARD);
2043         } else if (can[2] == can[3]) {
2044             if (merge_lines(sstate, e[0], e[1], total_parity^inv[2]^inv[3]))
2045                 diff = min(diff, DIFF_HARD);
2046         }
2047     }
2048     return diff;
2049 }
2050
2051
2052 /*
2053  * These are the main solver functions.
2054  *
2055  * Their return values are diff values corresponding to the lowest mode solver
2056  * that would notice the work that they have done.  For example if the normal
2057  * mode solver adds actual lines or crosses, it will return DIFF_EASY as the
2058  * easy mode solver might be able to make progress using that.  It doesn't make
2059  * sense for one of them to return a diff value higher than that of the
2060  * function itself.
2061  *
2062  * Each function returns the lowest value it can, as early as possible, in
2063  * order to try and pass as much work as possible back to the lower level
2064  * solvers which progress more quickly.
2065  */
2066
2067 /* PROPOSED NEW DESIGN:
2068  * We have a work queue consisting of 'events' notifying us that something has
2069  * happened that a particular solver mode might be interested in.  For example
2070  * the hard mode solver might do something that helps the normal mode solver at
2071  * dot [x,y] in which case it will enqueue an event recording this fact.  Then
2072  * we pull events off the work queue, and hand each in turn to the solver that
2073  * is interested in them.  If a solver reports that it failed we pass the same
2074  * event on to progressively more advanced solvers and the loop detector.  Once
2075  * we've exhausted an event, or it has helped us progress, we drop it and
2076  * continue to the next one.  The events are sorted first in order of solver
2077  * complexity (easy first) then order of insertion (oldest first).
2078  * Once we run out of events we loop over each permitted solver in turn
2079  * (easiest first) until either a deduction is made (and an event therefore
2080  * emerges) or no further deductions can be made (in which case we've failed).
2081  *
2082  * QUESTIONS:
2083  *    * How do we 'loop over' a solver when both dots and squares are concerned.
2084  *      Answer: first all squares then all dots.
2085  */
2086
2087 static int trivial_deductions(solver_state *sstate)
2088 {
2089     int i, current_yes, current_no;
2090     game_state *state = sstate->state;
2091     grid *g = state->game_grid;
2092     int diff = DIFF_MAX;
2093
2094     /* Per-face deductions */
2095     for (i = 0; i < g->num_faces; i++) {
2096         grid_face *f = g->faces + i;
2097
2098         if (sstate->face_solved[i])
2099             continue;
2100
2101         current_yes = sstate->face_yes_count[i];
2102         current_no  = sstate->face_no_count[i];
2103
2104         if (current_yes + current_no == f->order)  {
2105             sstate->face_solved[i] = TRUE;
2106             continue;
2107         }
2108
2109         if (state->clues[i] < 0)
2110             continue;
2111
2112         /*
2113          * This code checks whether the numeric clue on a face is so
2114          * large as to permit all its remaining LINE_UNKNOWNs to be
2115          * filled in as LINE_YES, or alternatively so small as to
2116          * permit them all to be filled in as LINE_NO.
2117          */
2118
2119         if (state->clues[i] < current_yes) {
2120             sstate->solver_status = SOLVER_MISTAKE;
2121             return DIFF_EASY;
2122         }
2123         if (state->clues[i] == current_yes) {
2124             if (face_setall(sstate, i, LINE_UNKNOWN, LINE_NO))
2125                 diff = min(diff, DIFF_EASY);
2126             sstate->face_solved[i] = TRUE;
2127             continue;
2128         }
2129
2130         if (f->order - state->clues[i] < current_no) {
2131             sstate->solver_status = SOLVER_MISTAKE;
2132             return DIFF_EASY;
2133         }
2134         if (f->order - state->clues[i] == current_no) {
2135             if (face_setall(sstate, i, LINE_UNKNOWN, LINE_YES))
2136                 diff = min(diff, DIFF_EASY);
2137             sstate->face_solved[i] = TRUE;
2138             continue;
2139         }
2140
2141         if (f->order - state->clues[i] == current_no + 1 &&
2142             f->order - current_yes - current_no > 2) {
2143             /*
2144              * One small refinement to the above: we also look for any
2145              * adjacent pair of LINE_UNKNOWNs around the face with
2146              * some LINE_YES incident on it from elsewhere. If we find
2147              * one, then we know that pair of LINE_UNKNOWNs can't
2148              * _both_ be LINE_YES, and hence that pushes us one line
2149              * closer to being able to determine all the rest.
2150              */
2151             int j, k, e1, e2, e, d;
2152
2153             for (j = 0; j < f->order; j++) {
2154                 e1 = f->edges[j] - g->edges;
2155                 e2 = f->edges[j+1 < f->order ? j+1 : 0] - g->edges;
2156
2157                 if (g->edges[e1].dot1 == g->edges[e2].dot1 ||
2158                     g->edges[e1].dot1 == g->edges[e2].dot2) {
2159                     d = g->edges[e1].dot1 - g->dots;
2160                 } else {
2161                     assert(g->edges[e1].dot2 == g->edges[e2].dot1 ||
2162                            g->edges[e1].dot2 == g->edges[e2].dot2);
2163                     d = g->edges[e1].dot2 - g->dots;
2164                 }
2165
2166                 if (state->lines[e1] == LINE_UNKNOWN &&
2167                     state->lines[e2] == LINE_UNKNOWN) {
2168                     for (k = 0; k < g->dots[d].order; k++) {
2169                         int e = g->dots[d].edges[k] - g->edges;
2170                         if (state->lines[e] == LINE_YES)
2171                             goto found;    /* multi-level break */
2172                     }
2173                 }
2174             }
2175             continue;
2176
2177           found:
2178             /*
2179              * If we get here, we've found such a pair of edges, and
2180              * they're e1 and e2.
2181              */
2182             for (j = 0; j < f->order; j++) {
2183                 e = f->edges[j] - g->edges;
2184                 if (state->lines[e] == LINE_UNKNOWN && e != e1 && e != e2) {
2185                     int r = solver_set_line(sstate, e, LINE_YES);
2186                     assert(r);
2187                     diff = min(diff, DIFF_EASY);
2188                 }
2189             }
2190         }
2191     }
2192
2193     check_caches(sstate);
2194
2195     /* Per-dot deductions */
2196     for (i = 0; i < g->num_dots; i++) {
2197         grid_dot *d = g->dots + i;
2198         int yes, no, unknown;
2199
2200         if (sstate->dot_solved[i])
2201             continue;
2202
2203         yes = sstate->dot_yes_count[i];
2204         no = sstate->dot_no_count[i];
2205         unknown = d->order - yes - no;
2206
2207         if (yes == 0) {
2208             if (unknown == 0) {
2209                 sstate->dot_solved[i] = TRUE;
2210             } else if (unknown == 1) {
2211                 dot_setall(sstate, i, LINE_UNKNOWN, LINE_NO);
2212                 diff = min(diff, DIFF_EASY);
2213                 sstate->dot_solved[i] = TRUE;
2214             }
2215         } else if (yes == 1) {
2216             if (unknown == 0) {
2217                 sstate->solver_status = SOLVER_MISTAKE;
2218                 return DIFF_EASY;
2219             } else if (unknown == 1) {
2220                 dot_setall(sstate, i, LINE_UNKNOWN, LINE_YES);
2221                 diff = min(diff, DIFF_EASY);
2222             }
2223         } else if (yes == 2) {
2224             if (unknown > 0) {
2225                 dot_setall(sstate, i, LINE_UNKNOWN, LINE_NO);
2226                 diff = min(diff, DIFF_EASY);
2227             }
2228             sstate->dot_solved[i] = TRUE;
2229         } else {
2230             sstate->solver_status = SOLVER_MISTAKE;
2231             return DIFF_EASY;
2232         }
2233     }
2234
2235     check_caches(sstate);
2236
2237     return diff;
2238 }
2239
2240 static int dline_deductions(solver_state *sstate)
2241 {
2242     game_state *state = sstate->state;
2243     grid *g = state->game_grid;
2244     char *dlines = sstate->dlines;
2245     int i;
2246     int diff = DIFF_MAX;
2247
2248     /* ------ Face deductions ------ */
2249
2250     /* Given a set of dline atmostone/atleastone constraints, need to figure
2251      * out if we can deduce any further info.  For more general faces than
2252      * squares, this turns out to be a tricky problem.
2253      * The approach taken here is to define (per face) NxN matrices:
2254      * "maxs" and "mins".
2255      * The entries maxs(j,k) and mins(j,k) define the upper and lower limits
2256      * for the possible number of edges that are YES between positions j and k
2257      * going clockwise around the face.  Can think of j and k as marking dots
2258      * around the face (recall the labelling scheme: edge0 joins dot0 to dot1,
2259      * edge1 joins dot1 to dot2 etc).
2260      * Trivially, mins(j,j) = maxs(j,j) = 0, and we don't even bother storing
2261      * these.  mins(j,j+1) and maxs(j,j+1) are determined by whether edge{j}
2262      * is YES, NO or UNKNOWN.  mins(j,j+2) and maxs(j,j+2) are related to
2263      * the dline atmostone/atleastone status for edges j and j+1.
2264      *
2265      * Then we calculate the remaining entries recursively.  We definitely
2266      * know that
2267      * mins(j,k) >= { mins(j,u) + mins(u,k) } for any u between j and k.
2268      * This is because any valid placement of YESs between j and k must give
2269      * a valid placement between j and u, and also between u and k.
2270      * I believe it's sufficient to use just the two values of u:
2271      * j+1 and j+2.  Seems to work well in practice - the bounds we compute
2272      * are rigorous, even if they might not be best-possible.
2273      *
2274      * Once we have maxs and mins calculated, we can make inferences about
2275      * each dline{j,j+1} by looking at the possible complementary edge-counts
2276      * mins(j+2,j) and maxs(j+2,j) and comparing these with the face clue.
2277      * As well as dlines, we can make similar inferences about single edges.
2278      * For example, consider a pentagon with clue 3, and we know at most one
2279      * of (edge0, edge1) is YES, and at most one of (edge2, edge3) is YES.
2280      * We could then deduce edge4 is YES, because maxs(0,4) would be 2, so
2281      * that final edge would have to be YES to make the count up to 3.
2282      */
2283
2284     /* Much quicker to allocate arrays on the stack than the heap, so
2285      * define the largest possible face size, and base our array allocations
2286      * on that.  We check this with an assertion, in case someone decides to
2287      * make a grid which has larger faces than this.  Note, this algorithm
2288      * could get quite expensive if there are many large faces. */
2289 #define MAX_FACE_SIZE 12
2290
2291     for (i = 0; i < g->num_faces; i++) {
2292         int maxs[MAX_FACE_SIZE][MAX_FACE_SIZE];
2293         int mins[MAX_FACE_SIZE][MAX_FACE_SIZE];
2294         grid_face *f = g->faces + i;
2295         int N = f->order;
2296         int j,m;
2297         int clue = state->clues[i];
2298         assert(N <= MAX_FACE_SIZE);
2299         if (sstate->face_solved[i])
2300             continue;
2301         if (clue < 0) continue;
2302
2303         /* Calculate the (j,j+1) entries */
2304         for (j = 0; j < N; j++) {
2305             int edge_index = f->edges[j] - g->edges;
2306             int dline_index;
2307             enum line_state line1 = state->lines[edge_index];
2308             enum line_state line2;
2309             int tmp;
2310             int k = j + 1;
2311             if (k >= N) k = 0;
2312             maxs[j][k] = (line1 == LINE_NO) ? 0 : 1;
2313             mins[j][k] = (line1 == LINE_YES) ? 1 : 0;
2314             /* Calculate the (j,j+2) entries */
2315             dline_index = dline_index_from_face(g, f, k);
2316             edge_index = f->edges[k] - g->edges;
2317             line2 = state->lines[edge_index];
2318             k++;
2319             if (k >= N) k = 0;
2320
2321             /* max */
2322             tmp = 2;
2323             if (line1 == LINE_NO) tmp--;
2324             if (line2 == LINE_NO) tmp--;
2325             if (tmp == 2 && is_atmostone(dlines, dline_index))
2326                 tmp = 1;
2327             maxs[j][k] = tmp;
2328
2329             /* min */
2330             tmp = 0;
2331             if (line1 == LINE_YES) tmp++;
2332             if (line2 == LINE_YES) tmp++;
2333             if (tmp == 0 && is_atleastone(dlines, dline_index))
2334                 tmp = 1;
2335             mins[j][k] = tmp;
2336         }
2337
2338         /* Calculate the (j,j+m) entries for m between 3 and N-1 */
2339         for (m = 3; m < N; m++) {
2340             for (j = 0; j < N; j++) {
2341                 int k = j + m;
2342                 int u = j + 1;
2343                 int v = j + 2;
2344                 int tmp;
2345                 if (k >= N) k -= N;
2346                 if (u >= N) u -= N;
2347                 if (v >= N) v -= N;
2348                 maxs[j][k] = maxs[j][u] + maxs[u][k];
2349                 mins[j][k] = mins[j][u] + mins[u][k];
2350                 tmp = maxs[j][v] + maxs[v][k];
2351                 maxs[j][k] = min(maxs[j][k], tmp);
2352                 tmp = mins[j][v] + mins[v][k];
2353                 mins[j][k] = max(mins[j][k], tmp);
2354             }
2355         }
2356
2357         /* See if we can make any deductions */
2358         for (j = 0; j < N; j++) {
2359             int k;
2360             grid_edge *e = f->edges[j];
2361             int line_index = e - g->edges;
2362             int dline_index;
2363
2364             if (state->lines[line_index] != LINE_UNKNOWN)
2365                 continue;
2366             k = j + 1;
2367             if (k >= N) k = 0;
2368
2369             /* minimum YESs in the complement of this edge */
2370             if (mins[k][j] > clue) {
2371                 sstate->solver_status = SOLVER_MISTAKE;
2372                 return DIFF_EASY;
2373             }
2374             if (mins[k][j] == clue) {
2375                 /* setting this edge to YES would make at least
2376                  * (clue+1) edges - contradiction */
2377                 solver_set_line(sstate, line_index, LINE_NO);
2378                 diff = min(diff, DIFF_EASY);
2379             }
2380             if (maxs[k][j] < clue - 1) {
2381                 sstate->solver_status = SOLVER_MISTAKE;
2382                 return DIFF_EASY;
2383             }
2384             if (maxs[k][j] == clue - 1) {
2385                 /* Only way to satisfy the clue is to set edge{j} as YES */
2386                 solver_set_line(sstate, line_index, LINE_YES);
2387                 diff = min(diff, DIFF_EASY);
2388             }
2389
2390             /* More advanced deduction that allows propagation along diagonal
2391              * chains of faces connected by dots, for example, 3-2-...-2-3
2392              * in square grids. */
2393             if (sstate->diff >= DIFF_TRICKY) {
2394                 /* Now see if we can make dline deduction for edges{j,j+1} */
2395                 e = f->edges[k];
2396                 if (state->lines[e - g->edges] != LINE_UNKNOWN)
2397                     /* Only worth doing this for an UNKNOWN,UNKNOWN pair.
2398                      * Dlines where one of the edges is known, are handled in the
2399                      * dot-deductions */
2400                     continue;
2401     
2402                 dline_index = dline_index_from_face(g, f, k);
2403                 k++;
2404                 if (k >= N) k = 0;
2405     
2406                 /* minimum YESs in the complement of this dline */
2407                 if (mins[k][j] > clue - 2) {
2408                     /* Adding 2 YESs would break the clue */
2409                     if (set_atmostone(dlines, dline_index))
2410                         diff = min(diff, DIFF_NORMAL);
2411                 }
2412                 /* maximum YESs in the complement of this dline */
2413                 if (maxs[k][j] < clue) {
2414                     /* Adding 2 NOs would mean not enough YESs */
2415                     if (set_atleastone(dlines, dline_index))
2416                         diff = min(diff, DIFF_NORMAL);
2417                 }
2418             }
2419         }
2420     }
2421
2422     if (diff < DIFF_NORMAL)
2423         return diff;
2424
2425     /* ------ Dot deductions ------ */
2426
2427     for (i = 0; i < g->num_dots; i++) {
2428         grid_dot *d = g->dots + i;
2429         int N = d->order;
2430         int yes, no, unknown;
2431         int j;
2432         if (sstate->dot_solved[i])
2433             continue;
2434         yes = sstate->dot_yes_count[i];
2435         no = sstate->dot_no_count[i];
2436         unknown = N - yes - no;
2437
2438         for (j = 0; j < N; j++) {
2439             int k;
2440             int dline_index;
2441             int line1_index, line2_index;
2442             enum line_state line1, line2;
2443             k = j + 1;
2444             if (k >= N) k = 0;
2445             dline_index = dline_index_from_dot(g, d, j);
2446             line1_index = d->edges[j] - g->edges;
2447             line2_index = d->edges[k] - g->edges;
2448             line1 = state->lines[line1_index];
2449             line2 = state->lines[line2_index];
2450
2451             /* Infer dline state from line state */
2452             if (line1 == LINE_NO || line2 == LINE_NO) {
2453                 if (set_atmostone(dlines, dline_index))
2454                     diff = min(diff, DIFF_NORMAL);
2455             }
2456             if (line1 == LINE_YES || line2 == LINE_YES) {
2457                 if (set_atleastone(dlines, dline_index))
2458                     diff = min(diff, DIFF_NORMAL);
2459             }
2460             /* Infer line state from dline state */
2461             if (is_atmostone(dlines, dline_index)) {
2462                 if (line1 == LINE_YES && line2 == LINE_UNKNOWN) {
2463                     solver_set_line(sstate, line2_index, LINE_NO);
2464                     diff = min(diff, DIFF_EASY);
2465                 }
2466                 if (line2 == LINE_YES && line1 == LINE_UNKNOWN) {
2467                     solver_set_line(sstate, line1_index, LINE_NO);
2468                     diff = min(diff, DIFF_EASY);
2469                 }
2470             }
2471             if (is_atleastone(dlines, dline_index)) {
2472                 if (line1 == LINE_NO && line2 == LINE_UNKNOWN) {
2473                     solver_set_line(sstate, line2_index, LINE_YES);
2474                     diff = min(diff, DIFF_EASY);
2475                 }
2476                 if (line2 == LINE_NO && line1 == LINE_UNKNOWN) {
2477                     solver_set_line(sstate, line1_index, LINE_YES);
2478                     diff = min(diff, DIFF_EASY);
2479                 }
2480             }
2481             /* Deductions that depend on the numbers of lines.
2482              * Only bother if both lines are UNKNOWN, otherwise the
2483              * easy-mode solver (or deductions above) would have taken
2484              * care of it. */
2485             if (line1 != LINE_UNKNOWN || line2 != LINE_UNKNOWN)
2486                 continue;
2487
2488             if (yes == 0 && unknown == 2) {
2489                 /* Both these unknowns must be identical.  If we know
2490                  * atmostone or atleastone, we can make progress. */
2491                 if (is_atmostone(dlines, dline_index)) {
2492                     solver_set_line(sstate, line1_index, LINE_NO);
2493                     solver_set_line(sstate, line2_index, LINE_NO);
2494                     diff = min(diff, DIFF_EASY);
2495                 }
2496                 if (is_atleastone(dlines, dline_index)) {
2497                     solver_set_line(sstate, line1_index, LINE_YES);
2498                     solver_set_line(sstate, line2_index, LINE_YES);
2499                     diff = min(diff, DIFF_EASY);
2500                 }
2501             }
2502             if (yes == 1) {
2503                 if (set_atmostone(dlines, dline_index))
2504                     diff = min(diff, DIFF_NORMAL);
2505                 if (unknown == 2) {
2506                     if (set_atleastone(dlines, dline_index))
2507                         diff = min(diff, DIFF_NORMAL);
2508                 }
2509             }
2510
2511             /* More advanced deduction that allows propagation along diagonal
2512              * chains of faces connected by dots, for example: 3-2-...-2-3
2513              * in square grids. */
2514             if (sstate->diff >= DIFF_TRICKY) {
2515                 /* If we have atleastone set for this dline, infer
2516                  * atmostone for each "opposite" dline (that is, each
2517                  * dline without edges in common with this one).
2518                  * Again, this test is only worth doing if both these
2519                  * lines are UNKNOWN.  For if one of these lines were YES,
2520                  * the (yes == 1) test above would kick in instead. */
2521                 if (is_atleastone(dlines, dline_index)) {
2522                     int opp;
2523                     for (opp = 0; opp < N; opp++) {
2524                         int opp_dline_index;
2525                         if (opp == j || opp == j+1 || opp == j-1)
2526                             continue;
2527                         if (j == 0 && opp == N-1)
2528                             continue;
2529                         if (j == N-1 && opp == 0)
2530                             continue;
2531                         opp_dline_index = dline_index_from_dot(g, d, opp);
2532                         if (set_atmostone(dlines, opp_dline_index))
2533                             diff = min(diff, DIFF_NORMAL);
2534                     }
2535                     if (yes == 0 && is_atmostone(dlines, dline_index)) {
2536                         /* This dline has *exactly* one YES and there are no
2537                          * other YESs.  This allows more deductions. */
2538                         if (unknown == 3) {
2539                             /* Third unknown must be YES */
2540                             for (opp = 0; opp < N; opp++) {
2541                                 int opp_index;
2542                                 if (opp == j || opp == k)
2543                                     continue;
2544                                 opp_index = d->edges[opp] - g->edges;
2545                                 if (state->lines[opp_index] == LINE_UNKNOWN) {
2546                                     solver_set_line(sstate, opp_index,
2547                                                     LINE_YES);
2548                                     diff = min(diff, DIFF_EASY);
2549                                 }
2550                             }
2551                         } else if (unknown == 4) {
2552                             /* Exactly one of opposite UNKNOWNS is YES.  We've
2553                              * already set atmostone, so set atleastone as
2554                              * well.
2555                              */
2556                             if (dline_set_opp_atleastone(sstate, d, j))
2557                                 diff = min(diff, DIFF_NORMAL);
2558                         }
2559                     }
2560                 }
2561             }
2562         }
2563     }
2564     return diff;
2565 }
2566
2567 static int linedsf_deductions(solver_state *sstate)
2568 {
2569     game_state *state = sstate->state;
2570     grid *g = state->game_grid;
2571     char *dlines = sstate->dlines;
2572     int i;
2573     int diff = DIFF_MAX;
2574     int diff_tmp;
2575
2576     /* ------ Face deductions ------ */
2577
2578     /* A fully-general linedsf deduction seems overly complicated
2579      * (I suspect the problem is NP-complete, though in practice it might just
2580      * be doable because faces are limited in size).
2581      * For simplicity, we only consider *pairs* of LINE_UNKNOWNS that are
2582      * known to be identical.  If setting them both to YES (or NO) would break
2583      * the clue, set them to NO (or YES). */
2584
2585     for (i = 0; i < g->num_faces; i++) {
2586         int N, yes, no, unknown;
2587         int clue;
2588
2589         if (sstate->face_solved[i])
2590             continue;
2591         clue = state->clues[i];
2592         if (clue < 0)
2593             continue;
2594
2595         N = g->faces[i].order;
2596         yes = sstate->face_yes_count[i];
2597         if (yes + 1 == clue) {
2598             if (face_setall_identical(sstate, i, LINE_NO))
2599                 diff = min(diff, DIFF_EASY);
2600         }
2601         no = sstate->face_no_count[i];
2602         if (no + 1 == N - clue) {
2603             if (face_setall_identical(sstate, i, LINE_YES))
2604                 diff = min(diff, DIFF_EASY);
2605         }
2606
2607         /* Reload YES count, it might have changed */
2608         yes = sstate->face_yes_count[i];
2609         unknown = N - no - yes;
2610
2611         /* Deductions with small number of LINE_UNKNOWNs, based on overall
2612          * parity of lines. */
2613         diff_tmp = parity_deductions(sstate, g->faces[i].edges,
2614                                      (clue - yes) % 2, unknown);
2615         diff = min(diff, diff_tmp);
2616     }
2617
2618     /* ------ Dot deductions ------ */
2619     for (i = 0; i < g->num_dots; i++) {
2620         grid_dot *d = g->dots + i;
2621         int N = d->order;
2622         int j;
2623         int yes, no, unknown;
2624         /* Go through dlines, and do any dline<->linedsf deductions wherever
2625          * we find two UNKNOWNS. */
2626         for (j = 0; j < N; j++) {
2627             int dline_index = dline_index_from_dot(g, d, j);
2628             int line1_index;
2629             int line2_index;
2630             int can1, can2, inv1, inv2;
2631             int j2;
2632             line1_index = d->edges[j] - g->edges;
2633             if (state->lines[line1_index] != LINE_UNKNOWN)
2634                 continue;
2635             j2 = j + 1;
2636             if (j2 == N) j2 = 0;
2637             line2_index = d->edges[j2] - g->edges;
2638             if (state->lines[line2_index] != LINE_UNKNOWN)
2639                 continue;
2640             /* Infer dline flags from linedsf */
2641             can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1);
2642             can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2);
2643             if (can1 == can2 && inv1 != inv2) {
2644                 /* These are opposites, so set dline atmostone/atleastone */
2645                 if (set_atmostone(dlines, dline_index))
2646                     diff = min(diff, DIFF_NORMAL);
2647                 if (set_atleastone(dlines, dline_index))
2648                     diff = min(diff, DIFF_NORMAL);
2649                 continue;
2650             }
2651             /* Infer linedsf from dline flags */
2652             if (is_atmostone(dlines, dline_index)
2653                 && is_atleastone(dlines, dline_index)) {
2654                 if (merge_lines(sstate, line1_index, line2_index, 1))
2655                     diff = min(diff, DIFF_HARD);
2656             }
2657         }
2658
2659         /* Deductions with small number of LINE_UNKNOWNs, based on overall
2660          * parity of lines. */
2661         yes = sstate->dot_yes_count[i];
2662         no = sstate->dot_no_count[i];
2663         unknown = N - yes - no;
2664         diff_tmp = parity_deductions(sstate, d->edges,
2665                                      yes % 2, unknown);
2666         diff = min(diff, diff_tmp);
2667     }
2668
2669     /* ------ Edge dsf deductions ------ */
2670
2671     /* If the state of a line is known, deduce the state of its canonical line
2672      * too, and vice versa. */
2673     for (i = 0; i < g->num_edges; i++) {
2674         int can, inv;
2675         enum line_state s;
2676         can = edsf_canonify(sstate->linedsf, i, &inv);
2677         if (can == i)
2678             continue;
2679         s = sstate->state->lines[can];
2680         if (s != LINE_UNKNOWN) {
2681             if (solver_set_line(sstate, i, inv ? OPP(s) : s))
2682                 diff = min(diff, DIFF_EASY);
2683         } else {
2684             s = sstate->state->lines[i];
2685             if (s != LINE_UNKNOWN) {
2686                 if (solver_set_line(sstate, can, inv ? OPP(s) : s))
2687                     diff = min(diff, DIFF_EASY);
2688             }
2689         }
2690     }
2691
2692     return diff;
2693 }
2694
2695 static int loop_deductions(solver_state *sstate)
2696 {
2697     int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0;
2698     game_state *state = sstate->state;
2699     grid *g = state->game_grid;
2700     int shortest_chainlen = g->num_dots;
2701     int loop_found = FALSE;
2702     int dots_connected;
2703     int progress = FALSE;
2704     int i;
2705
2706     /*
2707      * Go through the grid and update for all the new edges.
2708      * Since merge_dots() is idempotent, the simplest way to
2709      * do this is just to update for _all_ the edges.
2710      * Also, while we're here, we count the edges.
2711      */
2712     for (i = 0; i < g->num_edges; i++) {
2713         if (state->lines[i] == LINE_YES) {
2714             loop_found |= merge_dots(sstate, i);
2715             edgecount++;
2716         }
2717     }
2718
2719     /*
2720      * Count the clues, count the satisfied clues, and count the
2721      * satisfied-minus-one clues.
2722      */
2723     for (i = 0; i < g->num_faces; i++) {
2724         int c = state->clues[i];
2725         if (c >= 0) {
2726             int o = sstate->face_yes_count[i];
2727             if (o == c)
2728                 satclues++;
2729             else if (o == c-1)
2730                 sm1clues++;
2731             clues++;
2732         }
2733     }
2734
2735     for (i = 0; i < g->num_dots; ++i) {
2736         dots_connected =
2737             sstate->looplen[dsf_canonify(sstate->dotdsf, i)];
2738         if (dots_connected > 1)
2739             shortest_chainlen = min(shortest_chainlen, dots_connected);
2740     }
2741
2742     assert(sstate->solver_status == SOLVER_INCOMPLETE);
2743
2744     if (satclues == clues && shortest_chainlen == edgecount) {
2745         sstate->solver_status = SOLVER_SOLVED;
2746         /* This discovery clearly counts as progress, even if we haven't
2747          * just added any lines or anything */
2748         progress = TRUE;
2749         goto finished_loop_deductionsing;
2750     }
2751
2752     /*
2753      * Now go through looking for LINE_UNKNOWN edges which
2754      * connect two dots that are already in the same
2755      * equivalence class. If we find one, test to see if the
2756      * loop it would create is a solution.
2757      */
2758     for (i = 0; i < g->num_edges; i++) {
2759         grid_edge *e = g->edges + i;
2760         int d1 = e->dot1 - g->dots;
2761         int d2 = e->dot2 - g->dots;
2762         int eqclass, val;
2763         if (state->lines[i] != LINE_UNKNOWN)
2764             continue;
2765
2766         eqclass = dsf_canonify(sstate->dotdsf, d1);
2767         if (eqclass != dsf_canonify(sstate->dotdsf, d2))
2768             continue;
2769
2770         val = LINE_NO;  /* loop is bad until proven otherwise */
2771
2772         /*
2773          * This edge would form a loop. Next
2774          * question: how long would the loop be?
2775          * Would it equal the total number of edges
2776          * (plus the one we'd be adding if we added
2777          * it)?
2778          */
2779         if (sstate->looplen[eqclass] == edgecount + 1) {
2780             int sm1_nearby;
2781
2782             /*
2783              * This edge would form a loop which
2784              * took in all the edges in the entire
2785              * grid. So now we need to work out
2786              * whether it would be a valid solution
2787              * to the puzzle, which means we have to
2788              * check if it satisfies all the clues.
2789              * This means that every clue must be
2790              * either satisfied or satisfied-minus-
2791              * 1, and also that the number of
2792              * satisfied-minus-1 clues must be at
2793              * most two and they must lie on either
2794              * side of this edge.
2795              */
2796             sm1_nearby = 0;
2797             if (e->face1) {
2798                 int f = e->face1 - g->faces;
2799                 int c = state->clues[f];
2800                 if (c >= 0 && sstate->face_yes_count[f] == c - 1)
2801                     sm1_nearby++;
2802             }
2803             if (e->face2) {
2804                 int f = e->face2 - g->faces;
2805                 int c = state->clues[f];
2806                 if (c >= 0 && sstate->face_yes_count[f] == c - 1)
2807                     sm1_nearby++;
2808             }
2809             if (sm1clues == sm1_nearby &&
2810                 sm1clues + satclues == clues) {
2811                 val = LINE_YES;  /* loop is good! */
2812             }
2813         }
2814
2815         /*
2816          * Right. Now we know that adding this edge
2817          * would form a loop, and we know whether
2818          * that loop would be a viable solution or
2819          * not.
2820          *
2821          * If adding this edge produces a solution,
2822          * then we know we've found _a_ solution but
2823          * we don't know that it's _the_ solution -
2824          * if it were provably the solution then
2825          * we'd have deduced this edge some time ago
2826          * without the need to do loop detection. So
2827          * in this state we return SOLVER_AMBIGUOUS,
2828          * which has the effect that hitting Solve
2829          * on a user-provided puzzle will fill in a
2830          * solution but using the solver to
2831          * construct new puzzles won't consider this
2832          * a reasonable deduction for the user to
2833          * make.
2834          */
2835         progress = solver_set_line(sstate, i, val);
2836         assert(progress == TRUE);
2837         if (val == LINE_YES) {
2838             sstate->solver_status = SOLVER_AMBIGUOUS;
2839             goto finished_loop_deductionsing;
2840         }
2841     }
2842
2843     finished_loop_deductionsing:
2844     return progress ? DIFF_EASY : DIFF_MAX;
2845 }
2846
2847 /* This will return a dynamically allocated solver_state containing the (more)
2848  * solved grid */
2849 static solver_state *solve_game_rec(const solver_state *sstate_start)
2850 {
2851     solver_state *sstate;
2852
2853     /* Index of the solver we should call next. */
2854     int i = 0;
2855     
2856     /* As a speed-optimisation, we avoid re-running solvers that we know
2857      * won't make any progress.  This happens when a high-difficulty
2858      * solver makes a deduction that can only help other high-difficulty
2859      * solvers.
2860      * For example: if a new 'dline' flag is set by dline_deductions, the
2861      * trivial_deductions solver cannot do anything with this information.
2862      * If we've already run the trivial_deductions solver (because it's
2863      * earlier in the list), there's no point running it again.
2864      *
2865      * Therefore: if a solver is earlier in the list than "threshold_index",
2866      * we don't bother running it if it's difficulty level is less than
2867      * "threshold_diff".
2868      */
2869     int threshold_diff = 0;
2870     int threshold_index = 0;
2871     
2872     sstate = dup_solver_state(sstate_start);
2873
2874     check_caches(sstate);
2875
2876     while (i < NUM_SOLVERS) {
2877         if (sstate->solver_status == SOLVER_MISTAKE)
2878             return sstate;
2879         if (sstate->solver_status == SOLVER_SOLVED ||
2880             sstate->solver_status == SOLVER_AMBIGUOUS) {
2881             /* solver finished */
2882             break;
2883         }
2884
2885         if ((solver_diffs[i] >= threshold_diff || i >= threshold_index)
2886             && solver_diffs[i] <= sstate->diff) {
2887             /* current_solver is eligible, so use it */
2888             int next_diff = solver_fns[i](sstate);
2889             if (next_diff != DIFF_MAX) {
2890                 /* solver made progress, so use new thresholds and
2891                 * start again at top of list. */
2892                 threshold_diff = next_diff;
2893                 threshold_index = i;
2894                 i = 0;
2895                 continue;
2896             }
2897         }
2898         /* current_solver is ineligible, or failed to make progress, so
2899          * go to the next solver in the list */
2900         i++;
2901     }
2902
2903     if (sstate->solver_status == SOLVER_SOLVED ||
2904         sstate->solver_status == SOLVER_AMBIGUOUS) {
2905         /* s/LINE_UNKNOWN/LINE_NO/g */
2906         array_setall(sstate->state->lines, LINE_UNKNOWN, LINE_NO,
2907                      sstate->state->game_grid->num_edges);
2908         return sstate;
2909     }
2910
2911     return sstate;
2912 }
2913
2914 static char *solve_game(const game_state *state, const game_state *currstate,
2915                         const char *aux, char **error)
2916 {
2917     char *soln = NULL;
2918     solver_state *sstate, *new_sstate;
2919
2920     sstate = new_solver_state(state, DIFF_MAX);
2921     new_sstate = solve_game_rec(sstate);
2922
2923     if (new_sstate->solver_status == SOLVER_SOLVED) {
2924         soln = encode_solve_move(new_sstate->state);
2925     } else if (new_sstate->solver_status == SOLVER_AMBIGUOUS) {
2926         soln = encode_solve_move(new_sstate->state);
2927         /**error = "Solver found ambiguous solutions"; */
2928     } else {
2929         soln = encode_solve_move(new_sstate->state);
2930         /**error = "Solver failed"; */
2931     }
2932
2933     free_solver_state(new_sstate);
2934     free_solver_state(sstate);
2935
2936     return soln;
2937 }
2938
2939 /* ----------------------------------------------------------------------
2940  * Drawing and mouse-handling
2941  */
2942
2943 static char *interpret_move(const game_state *state, game_ui *ui,
2944                             const game_drawstate *ds,
2945                             int x, int y, int button)
2946 {
2947     grid *g = state->game_grid;
2948     grid_edge *e;
2949     int i;
2950     char *movebuf;
2951     int movelen, movesize;
2952     char button_char = ' ';
2953     enum line_state old_state;
2954
2955     button &= ~MOD_MASK;
2956
2957     /* Convert mouse-click (x,y) to grid coordinates */
2958     x -= BORDER(ds->tilesize);
2959     y -= BORDER(ds->tilesize);
2960     x = x * g->tilesize / ds->tilesize;
2961     y = y * g->tilesize / ds->tilesize;
2962     x += g->lowest_x;
2963     y += g->lowest_y;
2964
2965     e = grid_nearest_edge(g, x, y);
2966     if (e == NULL)
2967         return NULL;
2968
2969     i = e - g->edges;
2970
2971     /* I think it's only possible to play this game with mouse clicks, sorry */
2972     /* Maybe will add mouse drag support some time */
2973     old_state = state->lines[i];
2974
2975     switch (button) {
2976       case LEFT_BUTTON:
2977         switch (old_state) {
2978           case LINE_UNKNOWN:
2979             button_char = 'y';
2980             break;
2981           case LINE_YES:
2982 #ifdef STYLUS_BASED
2983             button_char = 'n';
2984             break;
2985 #endif
2986           case LINE_NO:
2987             button_char = 'u';
2988             break;
2989         }
2990         break;
2991       case MIDDLE_BUTTON:
2992         button_char = 'u';
2993         break;
2994       case RIGHT_BUTTON:
2995         switch (old_state) {
2996           case LINE_UNKNOWN:
2997             button_char = 'n';
2998             break;
2999           case LINE_NO:
3000 #ifdef STYLUS_BASED
3001             button_char = 'y';
3002             break;
3003 #endif
3004           case LINE_YES:
3005             button_char = 'u';
3006             break;
3007         }
3008         break;
3009       default:
3010         return NULL;
3011     }
3012
3013     movelen = 0;
3014     movesize = 80;
3015     movebuf = snewn(movesize, char);
3016     movelen = sprintf(movebuf, "%d%c", i, (int)button_char);
3017     {
3018         static enum { OFF, FIXED, ADAPTIVE, DUNNO } autofollow = DUNNO;
3019         if (autofollow == DUNNO) {
3020             const char *env = getenv("LOOPY_AUTOFOLLOW");
3021             if (env && !strcmp(env, "off"))
3022                 autofollow = OFF;
3023             else if (env && !strcmp(env, "fixed"))
3024                 autofollow = FIXED;
3025             else if (env && !strcmp(env, "adaptive"))
3026                 autofollow = ADAPTIVE;
3027             else
3028                 autofollow = OFF;
3029         }
3030
3031         if (autofollow != OFF) {
3032             int dotid;
3033             for (dotid = 0; dotid < 2; dotid++) {
3034                 grid_dot *dot = (dotid == 0 ? e->dot1 : e->dot2);
3035                 grid_edge *e_this = e;
3036
3037                 while (1) {
3038                     int j, n_found;
3039                     grid_edge *e_next = NULL;
3040
3041                     for (j = n_found = 0; j < dot->order; j++) {
3042                         grid_edge *e_candidate = dot->edges[j];
3043                         int i_candidate = e_candidate - g->edges;
3044                         if (e_candidate != e_this &&
3045                             (autofollow == FIXED ||
3046                              state->lines[i] == LINE_NO ||
3047                              state->lines[i_candidate] != LINE_NO)) {
3048                             e_next = e_candidate;
3049                             n_found++;
3050                         }
3051                     }
3052
3053                     if (n_found != 1 ||
3054                         state->lines[e_next - g->edges] != state->lines[i])
3055                         break;
3056
3057                     if (e_next == e) {
3058                         /*
3059                          * Special case: we might have come all the
3060                          * way round a loop and found our way back to
3061                          * the same edge we started from. In that
3062                          * situation, we must terminate not only this
3063                          * while loop, but the 'for' outside it that
3064                          * was tracing in both directions from the
3065                          * starting edge, because if we let it trace
3066                          * in the second direction then we'll only
3067                          * find ourself traversing the same loop in
3068                          * the other order and generate an encoded
3069                          * move string that mentions the same set of
3070                          * edges twice.
3071                          */
3072                         goto autofollow_done;
3073                     }
3074
3075                     dot = (e_next->dot1 != dot ? e_next->dot1 : e_next->dot2);
3076                     if (movelen > movesize - 40) {
3077                         movesize = movesize * 5 / 4 + 128;
3078                         movebuf = sresize(movebuf, movesize, char);
3079                     }
3080                     e_this = e_next;
3081                     movelen += sprintf(movebuf+movelen, "%d%c",
3082                                        (int)(e_this - g->edges), button_char);
3083                 }
3084             }
3085           autofollow_done:;
3086         }
3087     }
3088
3089     return sresize(movebuf, movelen+1, char);
3090 }
3091
3092 static game_state *execute_move(const game_state *state, const char *move)
3093 {
3094     int i;
3095     game_state *newstate = dup_game(state);
3096
3097     if (move[0] == 'S') {
3098         move++;
3099         newstate->cheated = TRUE;
3100     }
3101
3102     while (*move) {
3103         i = atoi(move);
3104         if (i < 0 || i >= newstate->game_grid->num_edges)
3105             goto fail;
3106         move += strspn(move, "1234567890");
3107         switch (*(move++)) {
3108           case 'y':
3109             newstate->lines[i] = LINE_YES;
3110             break;
3111           case 'n':
3112             newstate->lines[i] = LINE_NO;
3113             break;
3114           case 'u':
3115             newstate->lines[i] = LINE_UNKNOWN;
3116             break;
3117           default:
3118             goto fail;
3119         }
3120     }
3121
3122     /*
3123      * Check for completion.
3124      */
3125     if (check_completion(newstate))
3126         newstate->solved = TRUE;
3127
3128     return newstate;
3129
3130     fail:
3131     free_game(newstate);
3132     return NULL;
3133 }
3134
3135 /* ----------------------------------------------------------------------
3136  * Drawing routines.
3137  */
3138
3139 /* Convert from grid coordinates to screen coordinates */
3140 static void grid_to_screen(const game_drawstate *ds, const grid *g,
3141                            int grid_x, int grid_y, int *x, int *y)
3142 {
3143     *x = grid_x - g->lowest_x;
3144     *y = grid_y - g->lowest_y;
3145     *x = *x * ds->tilesize / g->tilesize;
3146     *y = *y * ds->tilesize / g->tilesize;
3147     *x += BORDER(ds->tilesize);
3148     *y += BORDER(ds->tilesize);
3149 }
3150
3151 /* Returns (into x,y) position of centre of face for rendering the text clue.
3152  */
3153 static void face_text_pos(const game_drawstate *ds, const grid *g,
3154                           grid_face *f, int *xret, int *yret)
3155 {
3156     int faceindex = f - g->faces;
3157
3158     /*
3159      * Return the cached position for this face, if we've already
3160      * worked it out.
3161      */
3162     if (ds->textx[faceindex] >= 0) {
3163         *xret = ds->textx[faceindex];
3164         *yret = ds->texty[faceindex];
3165         return;
3166     }
3167
3168     /*
3169      * Otherwise, use the incentre computed by grid.c and convert it
3170      * to screen coordinates.
3171      */
3172     grid_find_incentre(f);
3173     grid_to_screen(ds, g, f->ix, f->iy,
3174                    &ds->textx[faceindex], &ds->texty[faceindex]);
3175
3176     *xret = ds->textx[faceindex];
3177     *yret = ds->texty[faceindex];
3178 }
3179
3180 static void face_text_bbox(game_drawstate *ds, grid *g, grid_face *f,
3181                            int *x, int *y, int *w, int *h)
3182 {
3183     int xx, yy;
3184     face_text_pos(ds, g, f, &xx, &yy);
3185
3186     /* There seems to be a certain amount of trial-and-error involved
3187      * in working out the correct bounding-box for the text. */
3188
3189     *x = xx - ds->tilesize/4 - 1;
3190     *y = yy - ds->tilesize/4 - 3;
3191     *w = ds->tilesize/2 + 2;
3192     *h = ds->tilesize/2 + 5;
3193 }
3194
3195 static void game_redraw_clue(drawing *dr, game_drawstate *ds,
3196                              const game_state *state, int i)
3197 {
3198     grid *g = state->game_grid;
3199     grid_face *f = g->faces + i;
3200     int x, y;
3201     char c[20];
3202
3203     sprintf(c, "%d", state->clues[i]);
3204
3205     face_text_pos(ds, g, f, &x, &y);
3206     draw_text(dr, x, y,
3207               FONT_VARIABLE, ds->tilesize/2,
3208               ALIGN_VCENTRE | ALIGN_HCENTRE,
3209               ds->clue_error[i] ? COL_MISTAKE :
3210               ds->clue_satisfied[i] ? COL_SATISFIED : COL_FOREGROUND, c);
3211 }
3212
3213 static void edge_bbox(game_drawstate *ds, grid *g, grid_edge *e,
3214                       int *x, int *y, int *w, int *h)
3215 {
3216     int x1 = e->dot1->x;
3217     int y1 = e->dot1->y;
3218     int x2 = e->dot2->x;
3219     int y2 = e->dot2->y;
3220     int xmin, xmax, ymin, ymax;
3221
3222     grid_to_screen(ds, g, x1, y1, &x1, &y1);
3223     grid_to_screen(ds, g, x2, y2, &x2, &y2);
3224     /* Allow extra margin for dots, and thickness of lines */
3225     xmin = min(x1, x2) - 2;
3226     xmax = max(x1, x2) + 2;
3227     ymin = min(y1, y2) - 2;
3228     ymax = max(y1, y2) + 2;
3229
3230     *x = xmin;
3231     *y = ymin;
3232     *w = xmax - xmin + 1;
3233     *h = ymax - ymin + 1;
3234 }
3235
3236 static void dot_bbox(game_drawstate *ds, grid *g, grid_dot *d,
3237                      int *x, int *y, int *w, int *h)
3238 {
3239     int x1, y1;
3240
3241     grid_to_screen(ds, g, d->x, d->y, &x1, &y1);
3242
3243     *x = x1 - 2;
3244     *y = y1 - 2;
3245     *w = 5;
3246     *h = 5;
3247 }
3248
3249 static const int loopy_line_redraw_phases[] = {
3250     COL_FAINT, COL_LINEUNKNOWN, COL_FOREGROUND, COL_HIGHLIGHT, COL_MISTAKE
3251 };
3252 #define NPHASES lenof(loopy_line_redraw_phases)
3253
3254 static void game_redraw_line(drawing *dr, game_drawstate *ds,
3255                              const game_state *state, int i, int phase)
3256 {
3257     grid *g = state->game_grid;
3258     grid_edge *e = g->edges + i;
3259     int x1, x2, y1, y2;
3260     int line_colour;
3261
3262     if (state->line_errors[i])
3263         line_colour = COL_MISTAKE;
3264     else if (state->lines[i] == LINE_UNKNOWN)
3265         line_colour = COL_LINEUNKNOWN;
3266     else if (state->lines[i] == LINE_NO)
3267         line_colour = COL_FAINT;
3268     else if (ds->flashing)
3269         line_colour = COL_HIGHLIGHT;
3270     else
3271         line_colour = COL_FOREGROUND;
3272     if (line_colour != loopy_line_redraw_phases[phase])
3273         return;
3274
3275     /* Convert from grid to screen coordinates */
3276     grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1);
3277     grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2);
3278
3279     if (line_colour == COL_FAINT) {
3280         static int draw_faint_lines = -1;
3281         if (draw_faint_lines < 0) {
3282             char *env = getenv("LOOPY_FAINT_LINES");
3283             draw_faint_lines = (!env || (env[0] == 'y' ||
3284                                          env[0] == 'Y'));
3285         }
3286         if (draw_faint_lines)
3287             draw_line(dr, x1, y1, x2, y2, line_colour);
3288     } else {
3289         draw_thick_line(dr, 3.0,
3290                         x1 + 0.5, y1 + 0.5,
3291                         x2 + 0.5, y2 + 0.5,
3292                         line_colour);
3293     }
3294 }
3295
3296 static void game_redraw_dot(drawing *dr, game_drawstate *ds,
3297                             const game_state *state, int i)
3298 {
3299     grid *g = state->game_grid;
3300     grid_dot *d = g->dots + i;
3301     int x, y;
3302
3303     grid_to_screen(ds, g, d->x, d->y, &x, &y);
3304     draw_circle(dr, x, y, 2, COL_FOREGROUND, COL_FOREGROUND);
3305 }
3306
3307 static int boxes_intersect(int x0, int y0, int w0, int h0,
3308                            int x1, int y1, int w1, int h1)
3309 {
3310     /*
3311      * Two intervals intersect iff neither is wholly on one side of
3312      * the other. Two boxes intersect iff their horizontal and
3313      * vertical intervals both intersect.
3314      */
3315     return (x0 < x1+w1 && x1 < x0+w0 && y0 < y1+h1 && y1 < y0+h0);
3316 }
3317
3318 static void game_redraw_in_rect(drawing *dr, game_drawstate *ds,
3319                                 const game_state *state,
3320                                 int x, int y, int w, int h)
3321 {
3322     grid *g = state->game_grid;
3323     int i, phase;
3324     int bx, by, bw, bh;
3325
3326     clip(dr, x, y, w, h);
3327     draw_rect(dr, x, y, w, h, COL_BACKGROUND);
3328
3329     for (i = 0; i < g->num_faces; i++) {
3330         if (state->clues[i] >= 0) {
3331             face_text_bbox(ds, g, &g->faces[i], &bx, &by, &bw, &bh);
3332             if (boxes_intersect(x, y, w, h, bx, by, bw, bh))
3333                 game_redraw_clue(dr, ds, state, i);
3334         }
3335     }
3336     for (phase = 0; phase < NPHASES; phase++) {
3337         for (i = 0; i < g->num_edges; i++) {
3338             edge_bbox(ds, g, &g->edges[i], &bx, &by, &bw, &bh);
3339             if (boxes_intersect(x, y, w, h, bx, by, bw, bh))
3340                 game_redraw_line(dr, ds, state, i, phase);
3341         }
3342     }
3343     for (i = 0; i < g->num_dots; i++) {
3344         dot_bbox(ds, g, &g->dots[i], &bx, &by, &bw, &bh);
3345         if (boxes_intersect(x, y, w, h, bx, by, bw, bh))
3346             game_redraw_dot(dr, ds, state, i);
3347     }
3348
3349     unclip(dr);
3350     draw_update(dr, x, y, w, h);
3351 }
3352
3353 static void game_redraw(drawing *dr, game_drawstate *ds,
3354                         const game_state *oldstate, const game_state *state,
3355                         int dir, const game_ui *ui,
3356                         float animtime, float flashtime)
3357 {
3358 #define REDRAW_OBJECTS_LIMIT 16         /* Somewhat arbitrary tradeoff */
3359
3360     grid *g = state->game_grid;
3361     int border = BORDER(ds->tilesize);
3362     int i;
3363     int flash_changed;
3364     int redraw_everything = FALSE;
3365
3366     int edges[REDRAW_OBJECTS_LIMIT], nedges = 0;
3367     int faces[REDRAW_OBJECTS_LIMIT], nfaces = 0;
3368
3369     /* Redrawing is somewhat involved.
3370      *
3371      * An update can theoretically affect an arbitrary number of edges
3372      * (consider, for example, completing or breaking a cycle which doesn't
3373      * satisfy all the clues -- we'll switch many edges between error and
3374      * normal states).  On the other hand, redrawing the whole grid takes a
3375      * while, making the game feel sluggish, and many updates are actually
3376      * quite well localized.
3377      *
3378      * This redraw algorithm attempts to cope with both situations gracefully
3379      * and correctly.  For localized changes, we set a clip rectangle, fill
3380      * it with background, and then redraw (a plausible but conservative
3381      * guess at) the objects which intersect the rectangle; if several
3382      * objects need redrawing, we'll do them individually.  However, if lots
3383      * of objects are affected, we'll just redraw everything.
3384      *
3385      * The reason for all of this is that it's just not safe to do the redraw
3386      * piecemeal.  If you try to draw an antialiased diagonal line over
3387      * itself, you get a slightly thicker antialiased diagonal line, which
3388      * looks rather ugly after a while.
3389      *
3390      * So, we take two passes over the grid.  The first attempts to work out
3391      * what needs doing, and the second actually does it.
3392      */
3393
3394     if (!ds->started) {
3395         redraw_everything = TRUE;
3396         /*
3397          * But we must still go through the upcoming loops, so that we
3398          * set up stuff in ds correctly for the initial redraw.
3399          */
3400     }
3401
3402     /* First, trundle through the faces. */
3403     for (i = 0; i < g->num_faces; i++) {
3404         grid_face *f = g->faces + i;
3405         int sides = f->order;
3406         int yes_order, no_order;
3407         int clue_mistake;
3408         int clue_satisfied;
3409         int n = state->clues[i];
3410         if (n < 0)
3411             continue;
3412
3413         yes_order = face_order(state, i, LINE_YES);
3414         if (state->exactly_one_loop) {
3415             /*
3416              * Special case: if the set of LINE_YES edges in the grid
3417              * consists of exactly one loop and nothing else, then we
3418              * switch to treating LINE_UNKNOWN the same as LINE_NO for
3419              * purposes of clue checking.
3420              *
3421              * This is because some people like to play Loopy without
3422              * using the right-click, i.e. never setting anything to
3423              * LINE_NO. Without this special case, if a person playing
3424              * in that style fills in what they think is a correct
3425              * solution loop but in fact it has an underfilled clue,
3426              * then we will display no victory flash and also no error
3427              * highlight explaining why not. With this special case,
3428              * we light up underfilled clues at the instant the loop
3429              * is closed. (Of course, *overfilled* clues are fine
3430              * either way.)
3431              *
3432              * (It might still be considered unfortunate that we can't
3433              * warn this style of player any earlier, if they make a
3434              * mistake very near the beginning which doesn't show up
3435              * until they close the last edge of the loop. One other
3436              * thing we _could_ do here is to treat any LINE_UNKNOWN
3437              * as LINE_NO if either of its endpoints has yes-degree 2,
3438              * reflecting the fact that setting that line to YES would
3439              * be an obvious error. But I don't think even that could
3440              * catch _all_ clue errors in a timely manner; I think
3441              * there are some that won't be displayed until the loop
3442              * is filled in, even so, and there's no way to avoid that
3443              * with complete reliability except to switch to being a
3444              * player who sets things to LINE_NO.)
3445              */
3446             no_order = sides - yes_order;
3447         } else {
3448             no_order = face_order(state, i, LINE_NO);
3449         }
3450
3451         clue_mistake = (yes_order > n || no_order > (sides-n));
3452         clue_satisfied = (yes_order == n && no_order == (sides-n));
3453
3454         if (clue_mistake != ds->clue_error[i] ||
3455             clue_satisfied != ds->clue_satisfied[i]) {
3456             ds->clue_error[i] = clue_mistake;
3457             ds->clue_satisfied[i] = clue_satisfied;
3458             if (nfaces == REDRAW_OBJECTS_LIMIT)
3459                 redraw_everything = TRUE;
3460             else
3461                 faces[nfaces++] = i;
3462         }
3463     }
3464
3465     /* Work out what the flash state needs to be. */
3466     if (flashtime > 0 &&
3467         (flashtime <= FLASH_TIME/3 ||
3468          flashtime >= FLASH_TIME*2/3)) {
3469         flash_changed = !ds->flashing;
3470         ds->flashing = TRUE;
3471     } else {
3472         flash_changed = ds->flashing;
3473         ds->flashing = FALSE;
3474     }
3475
3476     /* Now, trundle through the edges. */
3477     for (i = 0; i < g->num_edges; i++) {
3478         char new_ds =
3479             state->line_errors[i] ? DS_LINE_ERROR : state->lines[i];
3480         if (new_ds != ds->lines[i] ||
3481             (flash_changed && state->lines[i] == LINE_YES)) {
3482             ds->lines[i] = new_ds;
3483             if (nedges == REDRAW_OBJECTS_LIMIT)
3484                 redraw_everything = TRUE;
3485             else
3486                 edges[nedges++] = i;
3487         }
3488     }
3489
3490     /* Pass one is now done.  Now we do the actual drawing. */
3491     if (redraw_everything) {
3492         int grid_width = g->highest_x - g->lowest_x;
3493         int grid_height = g->highest_y - g->lowest_y;
3494         int w = grid_width * ds->tilesize / g->tilesize;
3495         int h = grid_height * ds->tilesize / g->tilesize;
3496
3497         game_redraw_in_rect(dr, ds, state,
3498                             0, 0, w + 2*border + 1, h + 2*border + 1);
3499     } else {
3500
3501         /* Right.  Now we roll up our sleeves. */
3502
3503         for (i = 0; i < nfaces; i++) {
3504             grid_face *f = g->faces + faces[i];
3505             int x, y, w, h;
3506
3507             face_text_bbox(ds, g, f, &x, &y, &w, &h);
3508             game_redraw_in_rect(dr, ds, state, x, y, w, h);
3509         }
3510
3511         for (i = 0; i < nedges; i++) {
3512             grid_edge *e = g->edges + edges[i];
3513             int x, y, w, h;
3514
3515             edge_bbox(ds, g, e, &x, &y, &w, &h);
3516             game_redraw_in_rect(dr, ds, state, x, y, w, h);
3517         }
3518     }
3519
3520     ds->started = TRUE;
3521 }
3522
3523 static float game_flash_length(const game_state *oldstate,
3524                                const game_state *newstate, int dir, game_ui *ui)
3525 {
3526     if (!oldstate->solved  &&  newstate->solved &&
3527         !oldstate->cheated && !newstate->cheated) {
3528         return FLASH_TIME;
3529     }
3530
3531     return 0.0F;
3532 }
3533
3534 static int game_status(const game_state *state)
3535 {
3536     return state->solved ? +1 : 0;
3537 }
3538
3539 static void game_print_size(const game_params *params, float *x, float *y)
3540 {
3541     int pw, ph;
3542
3543     /*
3544      * I'll use 7mm "squares" by default.
3545      */
3546     game_compute_size(params, 700, &pw, &ph);
3547     *x = pw / 100.0F;
3548     *y = ph / 100.0F;
3549 }
3550
3551 static void game_print(drawing *dr, const game_state *state, int tilesize)
3552 {
3553     int ink = print_mono_colour(dr, 0);
3554     int i;
3555     game_drawstate ads, *ds = &ads;
3556     grid *g = state->game_grid;
3557
3558     ds->tilesize = tilesize;
3559     ds->textx = snewn(g->num_faces, int);
3560     ds->texty = snewn(g->num_faces, int);
3561     for (i = 0; i < g->num_faces; i++)
3562         ds->textx[i] = ds->texty[i] = -1;
3563
3564     for (i = 0; i < g->num_dots; i++) {
3565         int x, y;
3566         grid_to_screen(ds, g, g->dots[i].x, g->dots[i].y, &x, &y);
3567         draw_circle(dr, x, y, ds->tilesize / 15, ink, ink);
3568     }
3569
3570     /*
3571      * Clues.
3572      */
3573     for (i = 0; i < g->num_faces; i++) {
3574         grid_face *f = g->faces + i;
3575         int clue = state->clues[i];
3576         if (clue >= 0) {
3577             char c[20];
3578             int x, y;
3579             sprintf(c, "%d", state->clues[i]);
3580             face_text_pos(ds, g, f, &x, &y);
3581             draw_text(dr, x, y,
3582                       FONT_VARIABLE, ds->tilesize / 2,
3583                       ALIGN_VCENTRE | ALIGN_HCENTRE, ink, c);
3584         }
3585     }
3586
3587     /*
3588      * Lines.
3589      */
3590     for (i = 0; i < g->num_edges; i++) {
3591         int thickness = (state->lines[i] == LINE_YES) ? 30 : 150;
3592         grid_edge *e = g->edges + i;
3593         int x1, y1, x2, y2;
3594         grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1);
3595         grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2);
3596         if (state->lines[i] == LINE_YES)
3597         {
3598             /* (dx, dy) points from (x1, y1) to (x2, y2).
3599              * The line is then "fattened" in a perpendicular
3600              * direction to create a thin rectangle. */
3601             double d = sqrt(SQ((double)x1 - x2) + SQ((double)y1 - y2));
3602             double dx = (x2 - x1) / d;
3603             double dy = (y2 - y1) / d;
3604             int points[8];
3605
3606             dx = (dx * ds->tilesize) / thickness;
3607             dy = (dy * ds->tilesize) / thickness;
3608             points[0] = x1 + (int)dy;
3609             points[1] = y1 - (int)dx;
3610             points[2] = x1 - (int)dy;
3611             points[3] = y1 + (int)dx;
3612             points[4] = x2 - (int)dy;
3613             points[5] = y2 + (int)dx;
3614             points[6] = x2 + (int)dy;
3615             points[7] = y2 - (int)dx;
3616             draw_polygon(dr, points, 4, ink, ink);
3617         }
3618         else
3619         {
3620             /* Draw a dotted line */
3621             int divisions = 6;
3622             int j;
3623             for (j = 1; j < divisions; j++) {
3624                 /* Weighted average */
3625                 int x = (x1 * (divisions -j) + x2 * j) / divisions;
3626                 int y = (y1 * (divisions -j) + y2 * j) / divisions;
3627                 draw_circle(dr, x, y, ds->tilesize / thickness, ink, ink);
3628             }
3629         }
3630     }
3631
3632     sfree(ds->textx);
3633     sfree(ds->texty);
3634 }
3635
3636 #ifdef COMBINED
3637 #define thegame loopy
3638 #endif
3639
3640 const struct game thegame = {
3641     "Loopy", "games.loopy", "loopy",
3642     default_params,
3643     NULL, game_preset_menu,
3644     decode_params,
3645     encode_params,
3646     free_params,
3647     dup_params,
3648     TRUE, game_configure, custom_params,
3649     validate_params,
3650     new_game_desc,
3651     validate_desc,
3652     new_game,
3653     dup_game,
3654     free_game,
3655     1, solve_game,
3656     TRUE, game_can_format_as_text_now, game_text_format,
3657     new_ui,
3658     free_ui,
3659     encode_ui,
3660     decode_ui,
3661     game_changed_state,
3662     interpret_move,
3663     execute_move,
3664     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3665     game_colours,
3666     game_new_drawstate,
3667     game_free_drawstate,
3668     game_redraw,
3669     game_anim_length,
3670     game_flash_length,
3671     game_status,
3672     TRUE, FALSE, game_print_size, game_print,
3673     FALSE /* wants_statusbar */,
3674     FALSE, game_timing_state,
3675     0,                                       /* mouse_priorities */
3676 };
3677
3678 #ifdef STANDALONE_SOLVER
3679
3680 /*
3681  * Half-hearted standalone solver. It can't output the solution to
3682  * anything but a square puzzle, and it can't log the deductions
3683  * it makes either. But it can solve square puzzles, and more
3684  * importantly it can use its solver to grade the difficulty of
3685  * any puzzle you give it.
3686  */
3687
3688 #include <stdarg.h>
3689
3690 int main(int argc, char **argv)
3691 {
3692     game_params *p;
3693     game_state *s;
3694     char *id = NULL, *desc, *err;
3695     int grade = FALSE;
3696     int ret, diff;
3697 #if 0 /* verbose solver not supported here (yet) */
3698     int really_verbose = FALSE;
3699 #endif
3700
3701     while (--argc > 0) {
3702         char *p = *++argv;
3703 #if 0 /* verbose solver not supported here (yet) */
3704         if (!strcmp(p, "-v")) {
3705             really_verbose = TRUE;
3706         } else
3707 #endif
3708         if (!strcmp(p, "-g")) {
3709             grade = TRUE;
3710         } else if (*p == '-') {
3711             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
3712             return 1;
3713         } else {
3714             id = p;
3715         }
3716     }
3717
3718     if (!id) {
3719         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
3720         return 1;
3721     }
3722
3723     desc = strchr(id, ':');
3724     if (!desc) {
3725         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3726         return 1;
3727     }
3728     *desc++ = '\0';
3729
3730     p = default_params();
3731     decode_params(p, id);
3732     err = validate_desc(p, desc);
3733     if (err) {
3734         fprintf(stderr, "%s: %s\n", argv[0], err);
3735         return 1;
3736     }
3737     s = new_game(NULL, p, desc);
3738
3739     /*
3740      * When solving an Easy puzzle, we don't want to bother the
3741      * user with Hard-level deductions. For this reason, we grade
3742      * the puzzle internally before doing anything else.
3743      */
3744     ret = -1;                          /* placate optimiser */
3745     for (diff = 0; diff < DIFF_MAX; diff++) {
3746         solver_state *sstate_new;
3747         solver_state *sstate = new_solver_state((game_state *)s, diff);
3748
3749         sstate_new = solve_game_rec(sstate);
3750
3751         if (sstate_new->solver_status == SOLVER_MISTAKE)
3752             ret = 0;
3753         else if (sstate_new->solver_status == SOLVER_SOLVED)
3754             ret = 1;
3755         else
3756             ret = 2;
3757
3758         free_solver_state(sstate_new);
3759         free_solver_state(sstate);
3760
3761         if (ret < 2)
3762             break;
3763     }
3764
3765     if (diff == DIFF_MAX) {
3766         if (grade)
3767             printf("Difficulty rating: harder than Hard, or ambiguous\n");
3768         else
3769             printf("Unable to find a unique solution\n");
3770     } else {
3771         if (grade) {
3772             if (ret == 0)
3773                 printf("Difficulty rating: impossible (no solution exists)\n");
3774             else if (ret == 1)
3775                 printf("Difficulty rating: %s\n", diffnames[diff]);
3776         } else {
3777             solver_state *sstate_new;
3778             solver_state *sstate = new_solver_state((game_state *)s, diff);
3779
3780             /* If we supported a verbose solver, we'd set verbosity here */
3781
3782             sstate_new = solve_game_rec(sstate);
3783
3784             if (sstate_new->solver_status == SOLVER_MISTAKE)
3785                 printf("Puzzle is inconsistent\n");
3786             else {
3787                 assert(sstate_new->solver_status == SOLVER_SOLVED);
3788                 if (s->grid_type == 0) {
3789                     fputs(game_text_format(sstate_new->state), stdout);
3790                 } else {
3791                     printf("Unable to output non-square grids\n");
3792                 }
3793             }
3794
3795             free_solver_state(sstate_new);
3796             free_solver_state(sstate);
3797         }
3798     }
3799
3800     return 0;
3801 }
3802
3803 #endif
3804
3805 /* vim: set shiftwidth=4 tabstop=8: */