loopy.c

   1 /*
   2  * loopy.c: An implementation of the Nikoli game 'Loop the loop'.
   3  * (c) Mike Pinna, 2005, 2006
   4  *
   5  * vim: set shiftwidth=4 :set textwidth=80:
   6  */
   7
   8 /*
   9  * TODO:
  10  *
  11  *  - Setting very high recursion depth seems to cause memory munching: are we
  12  *    recursing before checking completion, by any chance?
  13  *
  14  *  - There's an interesting deductive technique which makes use of topology
  15  *    rather than just graph theory. Each _square_ in the grid is either inside
  16  *    or outside the loop; you can tell that two squares are on the same side
  17  *    of the loop if they're separated by an x (or, more generally, by a path
  18  *    crossing no LINE_UNKNOWNs and an even number of LINE_YESes), and on the
  19  *    opposite side of the loop if they're separated by a line (or an odd
  20  *    number of LINE_YESes and no LINE_UNKNOWNs). Oh, and any square separated
  21  *    from the outside of the grid by a LINE_YES or a LINE_NO is on the inside
  22  *    or outside respectively. So if you can track this for all squares, you
  23  *    figure out the state of the line between a pair once their relative
  24  *    insideness is known.
  25  *
  26  *  - (Just a speed optimisation.)  Consider some todo list queue where every
  27  *    time we modify something we mark it for consideration by other bits of
  28  *    the solver, to save iteration over things that have already been done.
  29  */
  30
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <assert.h>
  35 #include <ctype.h>
  36 #include <math.h>
  37
  38 #include "puzzles.h"
  39 #include "tree234.h"
  40
  41 /* Debugging options */
  42 /*#define DEBUG_CACHES*/
  43 /*#define SHOW_WORKING*/
  44
  45 /* ----------------------------------------------------------------------
  46  * Struct, enum and function declarations
  47  */
  48
  49 enum {
  50     COL_BACKGROUND,
  51     COL_FOREGROUND,
  52     COL_HIGHLIGHT,
  53     COL_MISTAKE,
  54     NCOLOURS
  55 };
  56
  57 struct game_state {
  58     int w, h;
  59
  60     /* Put -1 in a square that doesn't get a clue */
  61     signed char *clues;
  62
  63     /* Arrays of line states, stored left-to-right, top-to-bottom */
  64     char *hl, *vl;
  65
  66     int solved;
  67     int cheated;
  68
  69     int recursion_depth;
  70 };
  71
  72 enum solver_status {
  73     SOLVER_SOLVED,    /* This is the only solution the solver could find */
  74     SOLVER_MISTAKE,   /* This is definitely not a solution */
  75     SOLVER_AMBIGUOUS, /* This _might_ be an ambiguous solution */
  76     SOLVER_INCOMPLETE /* This may be a partial solution */
  77 };
  78
  79 typedef struct normal {
  80     char *dot_atleastone;
  81     char *dot_atmostone;
  82 } normal_mode_state;
  83
  84 typedef struct hard {
  85     int *linedsf;
  86 } hard_mode_state;
  87
  88 typedef struct solver_state {
  89     game_state *state;
  90     int recursion_remaining;
  91     enum solver_status solver_status;
  92     /* NB looplen is the number of dots that are joined together at a point, ie a
  93      * looplen of 1 means there are no lines to a particular dot */
  94     int *looplen;
  95
  96     /* caches */
  97     char *dot_yescount;
  98     char *dot_nocount;
  99     char *square_yescount;
 100     char *square_nocount;
 101     char *dot_solved, *square_solved;
 102     int *dotdsf;
 103
 104     normal_mode_state *normal;
 105     hard_mode_state *hard;
 106 } solver_state;
 107
 108 /*
 109  * Difficulty levels. I do some macro ickery here to ensure that my
 110  * enum and the various forms of my name list always match up.
 111  */
 112
 113 #define DIFFLIST(A) \
 114     A(EASY,Easy,e,easy_mode_deductions) \
 115     A(NORMAL,Normal,n,normal_mode_deductions) \
 116     A(HARD,Hard,h,hard_mode_deductions)
 117 #define ENUM(upper,title,lower,fn) DIFF_ ## upper,
 118 #define TITLE(upper,title,lower,fn) #title,
 119 #define ENCODE(upper,title,lower,fn) #lower
 120 #define CONFIG(upper,title,lower,fn) ":" #title
 121 #define SOLVER_FN_DECL(upper,title,lower,fn) static int fn(solver_state *);
 122 #define SOLVER_FN(upper,title,lower,fn) &fn,
 123 enum { DIFFLIST(ENUM) DIFF_MAX };
 124 static char const *const diffnames[] = { DIFFLIST(TITLE) };
 125 static char const diffchars[] = DIFFLIST(ENCODE);
 126 #define DIFFCONFIG DIFFLIST(CONFIG)
 127 DIFFLIST(SOLVER_FN_DECL);
 128 static int (*(solver_fns[]))(solver_state *) = { DIFFLIST(SOLVER_FN) };
 129
 130 struct game_params {
 131     int w, h;
 132     int diff;
 133     int rec;
 134 };
 135
 136 enum line_state { LINE_YES, LINE_UNKNOWN, LINE_NO };
 137
 138 #define OPP(state) \
 139     (2 - state)
 140
 141 enum direction { UP, LEFT, RIGHT, DOWN };
 142
 143 #define OPP_DIR(dir) \
 144     (3 - dir)
 145
 146 struct game_drawstate {
 147     int started;
 148     int tilesize, linewidth;
 149     int flashing;
 150     char *hl, *vl;
 151     char *clue_error;
 152 };
 153
 154 static int game_can_format_as_text_now(game_params *params)
 155 {
 156     return TRUE;
 157 }
 158
 159 static char *game_text_format(game_state *state);
 160 static char *state_to_text(const game_state *state);
 161 static char *validate_desc(game_params *params, char *desc);
 162 static int get_line_status_from_point(const game_state *state,
 163                                       int x, int y, enum direction d);
 164 static int dot_order(const game_state* state, int i, int j, char line_type);
 165 static int square_order(const game_state* state, int i, int j, char line_type);
 166 static solver_state *solve_game_rec(const solver_state *sstate,
 167                                     int diff);
 168
 169 #ifdef DEBUG_CACHES
 170 static void check_caches(const solver_state* sstate);
 171 #else
 172 #define check_caches(s)
 173 #endif
 174
 175 /* ----------------------------------------------------------------------
 176  * Preprocessor magic
 177  */
 178
 179 /* General constants */
 180 #define PREFERRED_TILE_SIZE 32
 181 #define TILE_SIZE (ds->tilesize)
 182 #define LINEWIDTH (ds->linewidth)
 183 #define BORDER (TILE_SIZE / 2)
 184 #define FLASH_TIME 0.5F
 185
 186 /* Counts of various things that we're interested in */
 187 #define HL_COUNT(state) ((state)->w * ((state)->h + 1))
 188 #define VL_COUNT(state) (((state)->w + 1) * (state)->h)
 189 #define LINE_COUNT(state) (HL_COUNT(state) + VL_COUNT(state))
 190 #define DOT_COUNT(state) (((state)->w + 1) * ((state)->h + 1))
 191 #define SQUARE_COUNT(state) ((state)->w * (state)->h)
 192
 193 /* For indexing into arrays */
 194 #define DOT_INDEX(state, x, y) ((x) + ((state)->w + 1) * (y))
 195 #define SQUARE_INDEX(state, x, y) ((x) + ((state)->w) * (y))
 196 #define HL_INDEX(state, x, y) SQUARE_INDEX(state, x, y)
 197 #define VL_INDEX(state, x, y) DOT_INDEX(state, x, y)
 198
 199 /* Useful utility functions */
 200 #define LEGAL_DOT(state, i, j) ((i) >= 0 && (j) >= 0 && \
 201                                 (i) <= (state)->w && (j) <= (state)->h)
 202 #define LEGAL_SQUARE(state, i, j) ((i) >= 0 && (j) >= 0 && \
 203                                    (i) < (state)->w && (j) < (state)->h)
 204
 205 #define CLUE_AT(state, i, j) (LEGAL_SQUARE(state, i, j) ? \
 206                               LV_CLUE_AT(state, i, j) : -1)
 207
 208 #define LV_CLUE_AT(state, i, j) ((state)->clues[SQUARE_INDEX(state, i, j)])
 209
 210 #define BIT_SET(field, bit) ((field) & (1<<(bit)))
 211
 212 #define SET_BIT(field, bit)  (BIT_SET(field, bit) ? FALSE : \
 213                               ((field) |= (1<<(bit)), TRUE))
 214
 215 #define CLEAR_BIT(field, bit) (BIT_SET(field, bit) ? \
 216                                ((field) &= ~(1<<(bit)), TRUE) : FALSE)
 217
 218 #define DIR2STR(d) \
 219     ((d == UP) ? "up" : \
 220      (d == DOWN) ? "down" : \
 221      (d == LEFT) ? "left" : \
 222      (d == RIGHT) ? "right" : "oops")
 223
 224 #define CLUE2CHAR(c) \
 225     ((c < 0) ? ' ' : c + '0')
 226
 227 /* Lines that have particular relationships with given dots or squares */
 228 #define ABOVE_SQUARE(state, i, j) ((state)->hl[(i) + (state)->w * (j)])
 229 #define BELOW_SQUARE(state, i, j) ABOVE_SQUARE(state, i, (j)+1)
 230 #define LEFTOF_SQUARE(state, i, j)  ((state)->vl[(i) + ((state)->w + 1) * (j)])
 231 #define RIGHTOF_SQUARE(state, i, j) LEFTOF_SQUARE(state, (i)+1, j)
 232
 233 /*
 234  * These macros return rvalues only, but can cope with being passed
 235  * out-of-range coordinates.
 236  */
 237 /* XXX replace these with functions so we can create an array of function
 238  * pointers for nicer iteration over them.  This could probably be done with
 239  * loads of other things for eliminating many nasty hacks. */
 240 #define ABOVE_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || j <= 0) ? \
 241                                 LINE_NO : LV_ABOVE_DOT(state, i, j))
 242 #define BELOW_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || j >= (state)->h) ? \
 243                                 LINE_NO : LV_BELOW_DOT(state, i, j))
 244
 245 #define LEFTOF_DOT(state, i, j)  ((!LEGAL_DOT(state, i, j) || i <= 0) ? \
 246                                   LINE_NO : LV_LEFTOF_DOT(state, i, j))
 247 #define RIGHTOF_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || i >= (state)->w)? \
 248                                   LINE_NO : LV_RIGHTOF_DOT(state, i, j))
 249
 250 /*
 251  * These macros expect to be passed valid coordinates, and return
 252  * lvalues.
 253  */
 254 #define LV_BELOW_DOT(state, i, j) ((state)->vl[VL_INDEX(state, i, j)])
 255 #define LV_ABOVE_DOT(state, i, j) LV_BELOW_DOT(state, i, (j)-1)
 256
 257 #define LV_RIGHTOF_DOT(state, i, j) ((state)->hl[HL_INDEX(state, i, j)])
 258 #define LV_LEFTOF_DOT(state, i, j)  LV_RIGHTOF_DOT(state, (i)-1, j)
 259
 260 /* Counts of interesting things */
 261 #define DOT_YES_COUNT(sstate, i, j) \
 262     ((sstate)->dot_yescount[DOT_INDEX((sstate)->state, i, j)])
 263
 264 #define DOT_NO_COUNT(sstate, i, j) \
 265     ((sstate)->dot_nocount[DOT_INDEX((sstate)->state, i, j)])
 266
 267 #define SQUARE_YES_COUNT(sstate, i, j) \
 268     ((sstate)->square_yescount[SQUARE_INDEX((sstate)->state, i, j)])
 269
 270 #define SQUARE_NO_COUNT(sstate, i, j) \
 271     ((sstate)->square_nocount[SQUARE_INDEX((sstate)->state, i, j)])
 272
 273 /* Iterators.  NB these iterate over height more slowly than over width so that
 274  * the elements come out in 'reading' order */
 275 /* XXX considering adding a 'current' element to each of these which gets the
 276  * address of the current dot, say.  But expecting we'd need more than that
 277  * most of the time.  */
 278 #define FORALL(i, j, w, h) \
 279     for ((j) = 0; (j) < (h); ++(j)) \
 280         for ((i) = 0; (i) < (w); ++(i))
 281
 282 #define FORALL_DOTS(state, i, j) \
 283     FORALL(i, j, (state)->w + 1, (state)->h + 1)
 284
 285 #define FORALL_SQUARES(state, i, j) \
 286     FORALL(i, j, (state)->w, (state)->h)
 287
 288 #define FORALL_HL(state, i, j) \
 289     FORALL(i, j, (state)->w, (state)->h+1)
 290
 291 #define FORALL_VL(state, i, j) \
 292     FORALL(i, j, (state)->w+1, (state)->h)
 293
 294 /* ----------------------------------------------------------------------
 295  * General struct manipulation and other straightforward code
 296  */
 297
 298 static game_state *dup_game(game_state *state)
 299 {
 300     game_state *ret = snew(game_state);
 301
 302     ret->h = state->h;
 303     ret->w = state->w;
 304     ret->solved = state->solved;
 305     ret->cheated = state->cheated;
 306
 307     ret->clues = snewn(SQUARE_COUNT(state), signed char);
 308     memcpy(ret->clues, state->clues, SQUARE_COUNT(state));
 309
 310     ret->hl = snewn(HL_COUNT(state), char);
 311     memcpy(ret->hl, state->hl, HL_COUNT(state));
 312
 313     ret->vl = snewn(VL_COUNT(state), char);
 314     memcpy(ret->vl, state->vl, VL_COUNT(state));
 315
 316     ret->recursion_depth = state->recursion_depth;
 317
 318     return ret;
 319 }
 320
 321 static void free_game(game_state *state)
 322 {
 323     if (state) {
 324         sfree(state->clues);
 325         sfree(state->hl);
 326         sfree(state->vl);
 327         sfree(state);
 328     }
 329 }
 330
 331 static solver_state *new_solver_state(const game_state *state, int diff) {
 332     int i, j;
 333     solver_state *ret = snew(solver_state);
 334
 335     ret->state = dup_game((game_state *)state);
 336
 337     ret->recursion_remaining = state->recursion_depth;
 338     ret->solver_status = SOLVER_INCOMPLETE;
 339
 340     ret->dotdsf = snew_dsf(DOT_COUNT(state));
 341     ret->looplen = snewn(DOT_COUNT(state), int);
 342
 343     for (i = 0; i < DOT_COUNT(state); i++) {
 344         ret->looplen[i] = 1;
 345     }
 346
 347     ret->dot_solved = snewn(DOT_COUNT(state), char);
 348     ret->square_solved = snewn(SQUARE_COUNT(state), char);
 349     memset(ret->dot_solved, FALSE, DOT_COUNT(state));
 350     memset(ret->square_solved, FALSE, SQUARE_COUNT(state));
 351
 352     ret->dot_yescount = snewn(DOT_COUNT(state), char);
 353     memset(ret->dot_yescount, 0, DOT_COUNT(state));
 354     ret->dot_nocount = snewn(DOT_COUNT(state), char);
 355     memset(ret->dot_nocount, 0, DOT_COUNT(state));
 356     ret->square_yescount = snewn(SQUARE_COUNT(state), char);
 357     memset(ret->square_yescount, 0, SQUARE_COUNT(state));
 358     ret->square_nocount = snewn(SQUARE_COUNT(state), char);
 359     memset(ret->square_nocount, 0, SQUARE_COUNT(state));
 360
 361     /* dot_nocount needs special initialisation as we define lines coming off
 362      * dots on edges as fixed at NO */
 363
 364     FORALL_DOTS(state, i, j) {
 365         if (i == 0 || i == state->w)
 366             ++ret->dot_nocount[DOT_INDEX(state, i, j)];
 367         if (j == 0 || j == state->h)
 368             ++ret->dot_nocount[DOT_INDEX(state, i, j)];
 369     }
 370
 371     if (diff < DIFF_NORMAL) {
 372         ret->normal = NULL;
 373     } else {
 374         ret->normal = snew(normal_mode_state);
 375
 376         ret->normal->dot_atmostone = snewn(DOT_COUNT(state), char);
 377         memset(ret->normal->dot_atmostone, 0, DOT_COUNT(state));
 378         ret->normal->dot_atleastone = snewn(DOT_COUNT(state), char);
 379         memset(ret->normal->dot_atleastone, 0, DOT_COUNT(state));
 380     }
 381
 382     if (diff < DIFF_HARD) {
 383         ret->hard = NULL;
 384     } else {
 385         ret->hard = snew(hard_mode_state);
 386         ret->hard->linedsf = snew_dsf(LINE_COUNT(state));
 387     }
 388
 389     return ret;
 390 }
 391
 392 static void free_solver_state(solver_state *sstate) {
 393     if (sstate) {
 394         free_game(sstate->state);
 395         sfree(sstate->dotdsf);
 396         sfree(sstate->looplen);
 397         sfree(sstate->dot_solved);
 398         sfree(sstate->square_solved);
 399         sfree(sstate->dot_yescount);
 400         sfree(sstate->dot_nocount);
 401         sfree(sstate->square_yescount);
 402         sfree(sstate->square_nocount);
 403
 404         if (sstate->normal) {
 405             sfree(sstate->normal->dot_atleastone);
 406             sfree(sstate->normal->dot_atmostone);
 407             sfree(sstate->normal);
 408         }
 409
 410         if (sstate->hard) {
 411             sfree(sstate->hard->linedsf);
 412             sfree(sstate->hard);
 413         }
 414
 415         sfree(sstate);
 416     }
 417 }
 418
 419 static solver_state *dup_solver_state(const solver_state *sstate) {
 420     game_state *state;
 421
 422     solver_state *ret = snew(solver_state);
 423
 424     ret->state = state = dup_game(sstate->state);
 425
 426     ret->recursion_remaining = sstate->recursion_remaining;
 427     ret->solver_status = sstate->solver_status;
 428
 429     ret->dotdsf = snewn(DOT_COUNT(state), int);
 430     ret->looplen = snewn(DOT_COUNT(state), int);
 431     memcpy(ret->dotdsf, sstate->dotdsf,
 432            DOT_COUNT(state) * sizeof(int));
 433     memcpy(ret->looplen, sstate->looplen,
 434            DOT_COUNT(state) * sizeof(int));
 435
 436     ret->dot_solved = snewn(DOT_COUNT(state), char);
 437     ret->square_solved = snewn(SQUARE_COUNT(state), char);
 438     memcpy(ret->dot_solved, sstate->dot_solved,
 439            DOT_COUNT(state));
 440     memcpy(ret->square_solved, sstate->square_solved,
 441            SQUARE_COUNT(state));
 442
 443     ret->dot_yescount = snewn(DOT_COUNT(state), char);
 444     memcpy(ret->dot_yescount, sstate->dot_yescount,
 445            DOT_COUNT(state));
 446     ret->dot_nocount = snewn(DOT_COUNT(state), char);
 447     memcpy(ret->dot_nocount, sstate->dot_nocount,
 448            DOT_COUNT(state));
 449
 450     ret->square_yescount = snewn(SQUARE_COUNT(state), char);
 451     memcpy(ret->square_yescount, sstate->square_yescount,
 452            SQUARE_COUNT(state));
 453     ret->square_nocount = snewn(SQUARE_COUNT(state), char);
 454     memcpy(ret->square_nocount, sstate->square_nocount,
 455            SQUARE_COUNT(state));
 456
 457     if (sstate->normal) {
 458         ret->normal = snew(normal_mode_state);
 459         ret->normal->dot_atmostone = snewn(DOT_COUNT(state), char);
 460         memcpy(ret->normal->dot_atmostone, sstate->normal->dot_atmostone,
 461                DOT_COUNT(state));
 462
 463         ret->normal->dot_atleastone = snewn(DOT_COUNT(state), char);
 464         memcpy(ret->normal->dot_atleastone, sstate->normal->dot_atleastone,
 465                DOT_COUNT(state));
 466     } else {
 467         ret->normal = NULL;
 468     }
 469
 470     if (sstate->hard) {
 471         ret->hard = snew(hard_mode_state);
 472         ret->hard->linedsf = snewn(LINE_COUNT(state), int);
 473         memcpy(ret->hard->linedsf, sstate->hard->linedsf,
 474                LINE_COUNT(state) * sizeof(int));
 475     } else {
 476         ret->hard = NULL;
 477     }
 478
 479     return ret;
 480 }
 481
 482 static game_params *default_params(void)
 483 {
 484     game_params *ret = snew(game_params);
 485
 486 #ifdef SLOW_SYSTEM
 487     ret->h = 4;
 488     ret->w = 4;
 489 #else
 490     ret->h = 10;
 491     ret->w = 10;
 492 #endif
 493     ret->diff = DIFF_EASY;
 494     ret->rec = 0;
 495
 496     return ret;
 497 }
 498
 499 static game_params *dup_params(game_params *params)
 500 {
 501     game_params *ret = snew(game_params);
 502     *ret = *params;                       /* structure copy */
 503     return ret;
 504 }
 505
 506 static const game_params presets[] = {
 507     {  4,  4, DIFF_EASY, 0 },
 508     {  4,  4, DIFF_NORMAL, 0 },
 509     {  4,  4, DIFF_HARD, 0 },
 510     {  7,  7, DIFF_EASY, 0 },
 511     {  7,  7, DIFF_NORMAL, 0 },
 512     {  7,  7, DIFF_HARD, 0 },
 513     { 10, 10, DIFF_EASY, 0 },
 514     { 10, 10, DIFF_NORMAL, 0 },
 515     { 10, 10, DIFF_HARD, 0 },
 516 #ifndef SLOW_SYSTEM
 517     { 15, 15, DIFF_EASY, 0 },
 518     { 15, 15, DIFF_NORMAL, 0 },
 519     { 15, 15, DIFF_HARD, 0 },
 520 #ifndef SMALL_SCREEN
 521     { 30, 20, DIFF_EASY, 0 },
 522     { 30, 20, DIFF_NORMAL, 0 },
 523     { 30, 20, DIFF_HARD, 0 }
 524 #endif
 525 #endif
 526 };
 527
 528 static int game_fetch_preset(int i, char **name, game_params **params)
 529 {
 530     game_params *tmppar;
 531     char buf[80];
 532
 533     if (i < 0 || i >= lenof(presets))
 534         return FALSE;
 535
 536     tmppar = snew(game_params);
 537     *tmppar = presets[i];
 538     *params = tmppar;
 539     sprintf(buf, "%dx%d %s", tmppar->h, tmppar->w, diffnames[tmppar->diff]);
 540     *name = dupstr(buf);
 541
 542     return TRUE;
 543 }
 544
 545 static void free_params(game_params *params)
 546 {
 547     sfree(params);
 548 }
 549
 550 static void decode_params(game_params *params, char const *string)
 551 {
 552     params->h = params->w = atoi(string);
 553     params->rec = 0;
 554     params->diff = DIFF_EASY;
 555     while (*string && isdigit((unsigned char)*string)) string++;
 556     if (*string == 'x') {
 557         string++;
 558         params->h = atoi(string);
 559         while (*string && isdigit((unsigned char)*string)) string++;
 560     }
 561     if (*string == 'r') {
 562         string++;
 563         params->rec = atoi(string);
 564         while (*string && isdigit((unsigned char)*string)) string++;
 565     }
 566     if (*string == 'd') {
 567         int i;
 568         string++;
 569         for (i = 0; i < DIFF_MAX; i++)
 570             if (*string == diffchars[i])
 571                 params->diff = i;
 572         if (*string) string++;
 573     }
 574 }
 575
 576 static char *encode_params(game_params *params, int full)
 577 {
 578     char str[80];
 579     sprintf(str, "%dx%d", params->w, params->h);
 580     if (full)
 581     sprintf(str + strlen(str), "r%dd%c", params->rec, diffchars[params->diff]);
 582     return dupstr(str);
 583 }
 584
 585 static config_item *game_configure(game_params *params)
 586 {
 587     config_item *ret;
 588     char buf[80];
 589
 590     ret = snewn(4, config_item);
 591
 592     ret[0].name = "Width";
 593     ret[0].type = C_STRING;
 594     sprintf(buf, "%d", params->w);
 595     ret[0].sval = dupstr(buf);
 596     ret[0].ival = 0;
 597
 598     ret[1].name = "Height";
 599     ret[1].type = C_STRING;
 600     sprintf(buf, "%d", params->h);
 601     ret[1].sval = dupstr(buf);
 602     ret[1].ival = 0;
 603
 604     ret[2].name = "Difficulty";
 605     ret[2].type = C_CHOICES;
 606     ret[2].sval = DIFFCONFIG;
 607     ret[2].ival = params->diff;
 608
 609     ret[3].name = NULL;
 610     ret[3].type = C_END;
 611     ret[3].sval = NULL;
 612     ret[3].ival = 0;
 613
 614     return ret;
 615 }
 616
 617 static game_params *custom_params(config_item *cfg)
 618 {
 619     game_params *ret = snew(game_params);
 620
 621     ret->w = atoi(cfg[0].sval);
 622     ret->h = atoi(cfg[1].sval);
 623     ret->rec = 0;
 624     ret->diff = cfg[2].ival;
 625
 626     return ret;
 627 }
 628
 629 static char *validate_params(game_params *params, int full)
 630 {
 631     if (params->w < 4 || params->h < 4)
 632         return "Width and height must both be at least 4";
 633     if (params->rec < 0)
 634         return "Recursion depth can't be negative";
 635
 636     /*
 637      * This shouldn't be able to happen at all, since decode_params
 638      * and custom_params will never generate anything that isn't
 639      * within range.
 640      */
 641     assert(params->diff < DIFF_MAX);
 642
 643     return NULL;
 644 }
 645
 646 /* Returns a newly allocated string describing the current puzzle */
 647 static char *state_to_text(const game_state *state)
 648 {
 649     char *retval;
 650     char *description = snewn(SQUARE_COUNT(state) + 1, char);
 651     char *dp = description;
 652     int empty_count = 0;
 653     int i, j;
 654
 655     FORALL_SQUARES(state, i, j) {
 656         if (CLUE_AT(state, i, j) < 0) {
 657             if (empty_count > 25) {
 658                 dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
 659                 empty_count = 0;
 660             }
 661             empty_count++;
 662         } else {
 663             if (empty_count) {
 664                 dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
 665                 empty_count = 0;
 666             }
 667             dp += sprintf(dp, "%c", (int)CLUE2CHAR(CLUE_AT(state, i, j)));
 668         }
 669     }
 670
 671     if (empty_count)
 672         dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
 673
 674     retval = dupstr(description);
 675     sfree(description);
 676
 677     return retval;
 678 }
 679
 680 /* We require that the params pass the test in validate_params and that the
 681  * description fills the entire game area */
 682 static char *validate_desc(game_params *params, char *desc)
 683 {
 684     int count = 0;
 685
 686     for (; *desc; ++desc) {
 687         if (*desc >= '0' && *desc <= '9') {
 688             count++;
 689             continue;
 690         }
 691         if (*desc >= 'a') {
 692             count += *desc - 'a' + 1;
 693             continue;
 694         }
 695         return "Unknown character in description";
 696     }
 697
 698     if (count < SQUARE_COUNT(params))
 699         return "Description too short for board size";
 700     if (count > SQUARE_COUNT(params))
 701         return "Description too long for board size";
 702
 703     return NULL;
 704 }
 705
 706 /* Sums the lengths of the numbers in range [0,n) */
 707 /* See equivalent function in solo.c for justification of this. */
 708 static int len_0_to_n(int n)
 709 {
 710     int len = 1; /* Counting 0 as a bit of a special case */
 711     int i;
 712
 713     for (i = 1; i < n; i *= 10) {
 714         len += max(n - i, 0);
 715     }
 716
 717     return len;
 718 }
 719
 720 static char *encode_solve_move(const game_state *state)
 721 {
 722     int len, i, j;
 723     char *ret, *p;
 724     /* This is going to return a string representing the moves needed to set
 725      * every line in a grid to be the same as the ones in 'state'.  The exact
 726      * length of this string is predictable. */
 727
 728     len = 1;  /* Count the 'S' prefix */
 729     /* Numbers in horizontal lines */
 730     /* Horizontal lines, x position */
 731     len += len_0_to_n(state->w) * (state->h + 1);
 732     /* Horizontal lines, y position */
 733     len += len_0_to_n(state->h + 1) * (state->w);
 734     /* Vertical lines, y position */
 735     len += len_0_to_n(state->h) * (state->w + 1);
 736     /* Vertical lines, x position */
 737     len += len_0_to_n(state->w + 1) * (state->h);
 738     /* For each line we also have two letters and a comma */
 739     len += 3 * (LINE_COUNT(state));
 740
 741     ret = snewn(len + 1, char);
 742     p = ret;
 743
 744     p += sprintf(p, "S");
 745
 746     FORALL_HL(state, i, j) {
 747         switch (RIGHTOF_DOT(state, i, j)) {
 748             case LINE_YES:
 749                 p += sprintf(p, "%d,%dhy", i, j);
 750                 break;
 751             case LINE_NO:
 752                 p += sprintf(p, "%d,%dhn", i, j);
 753                 break;
 754         }
 755     }
 756
 757     FORALL_VL(state, i, j) {
 758         switch (BELOW_DOT(state, i, j)) {
 759             case LINE_YES:
 760                 p += sprintf(p, "%d,%dvy", i, j);
 761                 break;
 762             case LINE_NO:
 763                 p += sprintf(p, "%d,%dvn", i, j);
 764                 break;
 765         }
 766     }
 767
 768     /* No point in doing sums like that if they're going to be wrong */
 769     assert(strlen(ret) <= (size_t)len);
 770     return ret;
 771 }
 772
 773 static game_ui *new_ui(game_state *state)
 774 {
 775     return NULL;
 776 }
 777
 778 static void free_ui(game_ui *ui)
 779 {
 780 }
 781
 782 static char *encode_ui(game_ui *ui)
 783 {
 784     return NULL;
 785 }
 786
 787 static void decode_ui(game_ui *ui, char *encoding)
 788 {
 789 }
 790
 791 static void game_changed_state(game_ui *ui, game_state *oldstate,
 792                                game_state *newstate)
 793 {
 794 }
 795
 796 #define SIZE(d) ((d) * TILE_SIZE + 2 * BORDER + 1)
 797
 798 static void game_compute_size(game_params *params, int tilesize,
 799                               int *x, int *y)
 800 {
 801     struct { int tilesize; } ads, *ds = &ads;
 802     ads.tilesize = tilesize;
 803
 804     *x = SIZE(params->w);
 805     *y = SIZE(params->h);
 806 }
 807
 808 static void game_set_size(drawing *dr, game_drawstate *ds,
 809               game_params *params, int tilesize)
 810 {
 811     ds->tilesize = tilesize;
 812     ds->linewidth = max(1,tilesize/16);
 813 }
 814
 815 static float *game_colours(frontend *fe, int *ncolours)
 816 {
 817     float *ret = snewn(4 * NCOLOURS, float);
 818
 819     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 820
 821     ret[COL_FOREGROUND * 3 + 0] = 0.0F;
 822     ret[COL_FOREGROUND * 3 + 1] = 0.0F;
 823     ret[COL_FOREGROUND * 3 + 2] = 0.0F;
 824
 825     ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
 826     ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
 827     ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
 828
 829     ret[COL_MISTAKE * 3 + 0] = 1.0F;
 830     ret[COL_MISTAKE * 3 + 1] = 0.0F;
 831     ret[COL_MISTAKE * 3 + 2] = 0.0F;
 832
 833     *ncolours = NCOLOURS;
 834     return ret;
 835 }
 836
 837 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
 838 {
 839     struct game_drawstate *ds = snew(struct game_drawstate);
 840
 841     ds->tilesize = ds->linewidth = 0;
 842     ds->started = 0;
 843     ds->hl = snewn(HL_COUNT(state), char);
 844     ds->vl = snewn(VL_COUNT(state), char);
 845     ds->clue_error = snewn(SQUARE_COUNT(state), char);
 846     ds->flashing = 0;
 847
 848     memset(ds->hl, LINE_UNKNOWN, HL_COUNT(state));
 849     memset(ds->vl, LINE_UNKNOWN, VL_COUNT(state));
 850     memset(ds->clue_error, 0, SQUARE_COUNT(state));
 851
 852     return ds;
 853 }
 854
 855 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
 856 {
 857     sfree(ds->clue_error);
 858     sfree(ds->hl);
 859     sfree(ds->vl);
 860     sfree(ds);
 861 }
 862
 863 static int game_timing_state(game_state *state, game_ui *ui)
 864 {
 865     return TRUE;
 866 }
 867
 868 static float game_anim_length(game_state *oldstate, game_state *newstate,
 869                               int dir, game_ui *ui)
 870 {
 871     return 0.0F;
 872 }
 873
 874 static char *game_text_format(game_state *state)
 875 {
 876     int i, j;
 877     int len;
 878     char *ret, *rp;
 879
 880     len = (2 * state->w + 2) * (2 * state->h + 1);
 881     rp = ret = snewn(len + 1, char);
 882
 883 #define DRAW_HL \
 884     switch (ABOVE_SQUARE(state, i, j)) { \
 885         case LINE_YES: \
 886             rp += sprintf(rp, " -"); \
 887             break; \
 888         case LINE_NO: \
 889             rp += sprintf(rp, " x"); \
 890             break; \
 891         case LINE_UNKNOWN: \
 892             rp += sprintf(rp, "  "); \
 893             break; \
 894         default: \
 895             assert(!"Illegal line state for HL"); \
 896     }
 897
 898 #define DRAW_VL \
 899     switch (LEFTOF_SQUARE(state, i, j)) { \
 900         case LINE_YES: \
 901             rp += sprintf(rp, "|"); \
 902             break; \
 903         case LINE_NO: \
 904             rp += sprintf(rp, "x"); \
 905             break; \
 906         case LINE_UNKNOWN: \
 907             rp += sprintf(rp, " "); \
 908             break; \
 909         default: \
 910             assert(!"Illegal line state for VL"); \
 911     }
 912
 913     for (j = 0; j < state->h; ++j) {
 914         for (i = 0; i < state->w; ++i) {
 915             DRAW_HL;
 916         }
 917         rp += sprintf(rp, " \n");
 918         for (i = 0; i < state->w; ++i) {
 919             DRAW_VL;
 920             rp += sprintf(rp, "%c", (int)CLUE2CHAR(CLUE_AT(state, i, j)));
 921         }
 922         DRAW_VL;
 923         rp += sprintf(rp, "\n");
 924     }
 925     for (i = 0; i < state->w; ++i) {
 926         DRAW_HL;
 927     }
 928     rp += sprintf(rp, " \n");
 929
 930     assert(strlen(ret) == len);
 931     return ret;
 932 }
 933
 934 /* ----------------------------------------------------------------------
 935  * Debug code
 936  */
 937
 938 #ifdef DEBUG_CACHES
 939 static void check_caches(const solver_state* sstate)
 940 {
 941     int i, j;
 942     const game_state *state = sstate->state;
 943
 944     FORALL_DOTS(state, i, j) {
 945 #if 0
 946         fprintf(stderr, "dot [%d,%d] y: %d %d n: %d %d\n", i, j,
 947                dot_order(state, i, j, LINE_YES),
 948                sstate->dot_yescount[i + (state->w + 1) * j],
 949                dot_order(state, i, j, LINE_NO),
 950                sstate->dot_nocount[i + (state->w + 1) * j]);
 951 #endif
 952
 953         assert(dot_order(state, i, j, LINE_YES) ==
 954                DOT_YES_COUNT(sstate, i, j));
 955         assert(dot_order(state, i, j, LINE_NO) ==
 956                DOT_NO_COUNT(sstate, i, j));
 957     }
 958
 959     FORALL_SQUARES(state, i, j) {
 960 #if 0
 961         fprintf(stderr, "square [%d,%d] y: %d %d n: %d %d\n", i, j,
 962                square_order(state, i, j, LINE_YES),
 963                sstate->square_yescount[i + state->w * j],
 964                square_order(state, i, j, LINE_NO),
 965                sstate->square_nocount[i + state->w * j]);
 966 #endif
 967
 968         assert(square_order(state, i, j, LINE_YES) ==
 969                SQUARE_YES_COUNT(sstate, i, j));
 970         assert(square_order(state, i, j, LINE_NO) ==
 971                SQUARE_NO_COUNT(sstate, i, j));
 972     }
 973 }
 974
 975 #if 0
 976 #define check_caches(s) \
 977     do { \
 978         fprintf(stderr, "check_caches at line %d\n", __LINE__); \
 979         check_caches(s); \
 980     } while (0)
 981 #endif
 982 #endif /* DEBUG_CACHES */
 983
 984 /* ----------------------------------------------------------------------
 985  * Solver utility functions
 986  */
 987
 988 static int set_line_bydot(solver_state *sstate, int x, int y, enum direction d,
 989                           enum line_state line_new
 990 #ifdef SHOW_WORKING
 991                           , const char *reason
 992 #endif
 993                           )
 994 {
 995     game_state *state = sstate->state;
 996
 997     /* This line borders at most two squares in our board.  We figure out the
 998      * x and y positions of those squares so we can record that their yes or no
 999      * counts have been changed */
1000     int sq1_x=-1, sq1_y=-1, sq2_x=-1, sq2_y=-1;
1001     int otherdot_x=-1, otherdot_y=-1;
1002
1003     int progress = FALSE;
1004
1005 #if 0
1006     fprintf(stderr, "set_line_bydot [%d,%d], %s, %d\n",
1007             x, y, DIR2STR(d), line_new);
1008 #endif
1009
1010     assert(line_new != LINE_UNKNOWN);
1011
1012     check_caches(sstate);
1013
1014     switch (d) {
1015         case LEFT:
1016             assert(x > 0);
1017
1018             if (LEFTOF_DOT(state, x, y) != line_new) {
1019                 LV_LEFTOF_DOT(state, x, y) = line_new;
1020
1021                 otherdot_x = x-1;
1022                 otherdot_y = y;
1023
1024                 sq1_x = x-1;
1025                 sq1_y = y-1;
1026                 sq2_x = x-1;
1027                 sq2_y = y;
1028
1029                 progress = TRUE;
1030             }
1031             break;
1032         case RIGHT:
1033             assert(x < state->w);
1034             if (RIGHTOF_DOT(state, x, y) != line_new) {
1035                 LV_RIGHTOF_DOT(state, x, y) = line_new;
1036
1037                 otherdot_x = x+1;
1038                 otherdot_y = y;
1039
1040                 sq1_x = x;
1041                 sq1_y = y-1;
1042                 sq2_x = x;
1043                 sq2_y = y;
1044
1045                 progress = TRUE;
1046             }
1047             break;
1048         case UP:
1049             assert(y > 0);
1050             if (ABOVE_DOT(state, x, y) != line_new) {
1051                 LV_ABOVE_DOT(state, x, y) = line_new;
1052
1053                 otherdot_x = x;
1054                 otherdot_y = y-1;
1055
1056                 sq1_x = x-1;
1057                 sq1_y = y-1;
1058                 sq2_x = x;
1059                 sq2_y = y-1;
1060
1061                 progress = TRUE;
1062             }
1063             break;
1064         case DOWN:
1065             assert(y < state->h);
1066             if (BELOW_DOT(state, x, y) != line_new) {
1067                 LV_BELOW_DOT(state, x, y) = line_new;
1068
1069                 otherdot_x = x;
1070                 otherdot_y = y+1;
1071
1072                 sq1_x = x-1;
1073                 sq1_y = y;
1074                 sq2_x = x;
1075                 sq2_y = y;
1076
1077                 progress = TRUE;
1078             }
1079             break;
1080     }
1081
1082     if (!progress)
1083         return progress;
1084
1085 #ifdef SHOW_WORKING
1086     fprintf(stderr, "set line [%d,%d] -> [%d,%d] to %s (%s)\n",
1087             x, y, otherdot_x, otherdot_y, line_new == LINE_YES ? "YES" : "NO",
1088             reason);
1089 #endif
1090
1091     /* Above we updated the cache for the dot that the line in question reaches
1092      * from the dot we've been told about.  Here we update that for the dot
1093      * named in our arguments. */
1094     if (line_new == LINE_YES) {
1095         if (sq1_x >= 0 && sq1_y >= 0)
1096             ++SQUARE_YES_COUNT(sstate, sq1_x, sq1_y);
1097         if (sq2_x < state->w && sq2_y < state->h)
1098             ++SQUARE_YES_COUNT(sstate, sq2_x, sq2_y);
1099         ++DOT_YES_COUNT(sstate, x, y);
1100         ++DOT_YES_COUNT(sstate, otherdot_x, otherdot_y);
1101     } else {
1102         if (sq1_x >= 0 && sq1_y >= 0)
1103             ++SQUARE_NO_COUNT(sstate, sq1_x, sq1_y);
1104         if (sq2_x < state->w && sq2_y < state->h)
1105             ++SQUARE_NO_COUNT(sstate, sq2_x, sq2_y);
1106         ++DOT_NO_COUNT(sstate, x, y);
1107         ++DOT_NO_COUNT(sstate, otherdot_x, otherdot_y);
1108     }
1109
1110     check_caches(sstate);
1111     return progress;
1112 }
1113
1114 #ifdef SHOW_WORKING
1115 #define set_line_bydot(a, b, c, d, e) \
1116     set_line_bydot(a, b, c, d, e, __FUNCTION__)
1117 #endif
1118
1119 /*
1120  * Merge two dots due to the existence of an edge between them.
1121  * Updates the dsf tracking equivalence classes, and keeps track of
1122  * the length of path each dot is currently a part of.
1123  * Returns TRUE if the dots were already linked, ie if they are part of a
1124  * closed loop, and false otherwise.
1125  */
1126 static int merge_dots(solver_state *sstate, int x1, int y1, int x2, int y2)
1127 {
1128     int i, j, len;
1129
1130     i = y1 * (sstate->state->w + 1) + x1;
1131     j = y2 * (sstate->state->w + 1) + x2;
1132
1133     i = dsf_canonify(sstate->dotdsf, i);
1134     j = dsf_canonify(sstate->dotdsf, j);
1135
1136     if (i == j) {
1137         return TRUE;
1138     } else {
1139         len = sstate->looplen[i] + sstate->looplen[j];
1140         dsf_merge(sstate->dotdsf, i, j);
1141         i = dsf_canonify(sstate->dotdsf, i);
1142         sstate->looplen[i] = len;
1143         return FALSE;
1144     }
1145 }
1146
1147 /* Seriously, these should be functions */
1148
1149 #define LINEDSF_INDEX(state, x, y, d) \
1150    ((d == UP)    ? ((y-1) * (state->w + 1) + x) : \
1151     (d == DOWN)  ? ((y)   * (state->w + 1) + x) : \
1152     (d == LEFT)  ? ((y) * (state->w) + x-1 + VL_COUNT(state)) : \
1153     (d == RIGHT) ? ((y) * (state->w) + x   + VL_COUNT(state)) : \
1154     (assert(!"bad direction value"), 0))
1155
1156 static void linedsf_deindex(const game_state *state, int i,
1157                             int *px, int *py, enum direction *pd)
1158 {
1159     int i_mod;
1160     if (i < VL_COUNT(state)) {
1161         *(pd) = DOWN;
1162         *(px) = (i) % (state->w+1);
1163         *(py) = (i) / (state->w+1);
1164     } else {
1165         i_mod = i - VL_COUNT(state);
1166         *(pd) = RIGHT;
1167         *(px) = (i_mod) % (state->w);
1168         *(py) = (i_mod) / (state->w);
1169     }
1170 }
1171
1172 /* Merge two lines because the solver has deduced that they must be either
1173  * identical or opposite.   Returns TRUE if this is new information, otherwise
1174  * FALSE. */
1175 static int merge_lines(solver_state *sstate,
1176                        int x1, int y1, enum direction d1,
1177                        int x2, int y2, enum direction d2,
1178                        int inverse
1179 #ifdef SHOW_WORKING
1180                        , const char *reason
1181 #endif
1182                       )
1183 {
1184     int i, j, inv_tmp;
1185
1186     i = LINEDSF_INDEX(sstate->state, x1, y1, d1);
1187     j = LINEDSF_INDEX(sstate->state, x2, y2, d2);
1188
1189     assert(i < LINE_COUNT(sstate->state));
1190     assert(j < LINE_COUNT(sstate->state));
1191
1192     i = edsf_canonify(sstate->hard->linedsf, i, &inv_tmp);
1193     inverse ^= inv_tmp;
1194     j = edsf_canonify(sstate->hard->linedsf, j, &inv_tmp);
1195     inverse ^= inv_tmp;
1196
1197     edsf_merge(sstate->hard->linedsf, i, j, inverse);
1198
1199 #ifdef SHOW_WORKING
1200     if (i != j) {
1201         fprintf(stderr, "%s [%d,%d,%s] [%d,%d,%s] %s(%s)\n",
1202                 __FUNCTION__,
1203                 x1, y1, DIR2STR(d1),
1204                 x2, y2, DIR2STR(d2),
1205                 inverse ? "inverse " : "", reason);
1206     }
1207 #endif
1208     return (i != j);
1209 }
1210
1211 #ifdef SHOW_WORKING
1212 #define merge_lines(a, b, c, d, e, f, g, h) \
1213     merge_lines(a, b, c, d, e, f, g, h, __FUNCTION__)
1214 #endif
1215
1216 /* Return 0 if the given lines are not in the same equivalence class, 1 if they
1217  * are known identical, or 2 if they are known opposite */
1218 #if 0
1219 static int lines_related(solver_state *sstate,
1220                          int x1, int y1, enum direction d1,
1221                          int x2, int y2, enum direction d2)
1222 {
1223     int i, j, inv1, inv2;
1224
1225     i = LINEDSF_INDEX(sstate->state, x1, y1, d1);
1226     j = LINEDSF_INDEX(sstate->state, x2, y2, d2);
1227
1228     i = edsf_canonify(sstate->hard->linedsf, i, &inv1);
1229     j = edsf_canonify(sstate->hard->linedsf, j, &inv2);
1230
1231     if (i == j)
1232         return (inv1 == inv2) ? 1 : 2;
1233     else
1234         return 0;
1235 }
1236 #endif
1237
1238 /* Count the number of lines of a particular type currently going into the
1239  * given dot.  Lines going off the edge of the board are assumed fixed no. */
1240 static int dot_order(const game_state* state, int i, int j, char line_type)
1241 {
1242     int n = 0;
1243
1244     if (i > 0) {
1245         if (line_type == LV_LEFTOF_DOT(state, i, j))
1246             ++n;
1247     } else {
1248         if (line_type == LINE_NO)
1249             ++n;
1250     }
1251     if (i < state->w) {
1252         if (line_type == LV_RIGHTOF_DOT(state, i, j))
1253             ++n;
1254     } else {
1255         if (line_type == LINE_NO)
1256             ++n;
1257     }
1258     if (j > 0) {
1259         if (line_type == LV_ABOVE_DOT(state, i, j))
1260             ++n;
1261     } else {
1262         if (line_type == LINE_NO)
1263             ++n;
1264     }
1265     if (j < state->h) {
1266         if (line_type == LV_BELOW_DOT(state, i, j))
1267             ++n;
1268     } else {
1269         if (line_type == LINE_NO)
1270             ++n;
1271     }
1272
1273     return n;
1274 }
1275
1276 /* Count the number of lines of a particular type currently surrounding the
1277  * given square */
1278 static int square_order(const game_state* state, int i, int j, char line_type)
1279 {
1280     int n = 0;
1281
1282     if (ABOVE_SQUARE(state, i, j) == line_type)
1283         ++n;
1284     if (BELOW_SQUARE(state, i, j) == line_type)
1285         ++n;
1286     if (LEFTOF_SQUARE(state, i, j) == line_type)
1287         ++n;
1288     if (RIGHTOF_SQUARE(state, i, j) == line_type)
1289         ++n;
1290
1291     return n;
1292 }
1293
1294 /* Set all lines bordering a dot of type old_type to type new_type
1295  * Return value tells caller whether this function actually did anything */
1296 static int dot_setall(solver_state *sstate, int i, int j,
1297                        char old_type, char new_type)
1298 {
1299     int retval = FALSE, r;
1300     game_state *state = sstate->state;
1301
1302     if (old_type == new_type)
1303         return FALSE;
1304
1305     if (i > 0        && LEFTOF_DOT(state, i, j) == old_type) {
1306         r = set_line_bydot(sstate, i, j, LEFT, new_type);
1307         assert(r == TRUE);
1308         retval = TRUE;
1309     }
1310
1311     if (i < state->w && RIGHTOF_DOT(state, i, j) == old_type) {
1312         r = set_line_bydot(sstate, i, j, RIGHT, new_type);
1313         assert(r == TRUE);
1314         retval = TRUE;
1315     }
1316
1317     if (j > 0        && ABOVE_DOT(state, i, j) == old_type) {
1318         r = set_line_bydot(sstate, i, j, UP, new_type);
1319         assert(r == TRUE);
1320         retval = TRUE;
1321     }
1322
1323     if (j < state->h && BELOW_DOT(state, i, j) == old_type) {
1324         r = set_line_bydot(sstate, i, j, DOWN, new_type);
1325         assert(r == TRUE);
1326         retval = TRUE;
1327     }
1328
1329     return retval;
1330 }
1331
1332 /* Set all lines bordering a square of type old_type to type new_type */
1333 static int square_setall(solver_state *sstate, int i, int j,
1334                          char old_type, char new_type)
1335 {
1336     int r = FALSE;
1337     game_state *state = sstate->state;
1338
1339 #if 0
1340     fprintf(stderr, "square_setall [%d,%d] from %d to %d\n", i, j,
1341                     old_type, new_type);
1342 #endif
1343     if (ABOVE_SQUARE(state, i, j) == old_type) {
1344         r = set_line_bydot(sstate, i, j, RIGHT, new_type);
1345         assert(r == TRUE);
1346     }
1347     if (BELOW_SQUARE(state, i, j) == old_type) {
1348         r = set_line_bydot(sstate, i, j+1, RIGHT, new_type);
1349         assert(r == TRUE);
1350     }
1351     if (LEFTOF_SQUARE(state, i, j) == old_type) {
1352         r = set_line_bydot(sstate, i, j, DOWN, new_type);
1353         assert(r == TRUE);
1354     }
1355     if (RIGHTOF_SQUARE(state, i, j) == old_type) {
1356         r = set_line_bydot(sstate, i+1, j, DOWN, new_type);
1357         assert(r == TRUE);
1358     }
1359
1360     return r;
1361 }
1362
1363 /* ----------------------------------------------------------------------
1364  * Loop generation and clue removal
1365  */
1366
1367 /* We're going to store a list of current candidate squares for lighting.
1368  * Each square gets a 'score', which tells us how adding that square right
1369  * now would affect the length of the solution loop.  We're trying to
1370  * maximise that quantity so will bias our random selection of squares to
1371  * light towards those with high scores */
1372 struct square {
1373     int score;
1374     unsigned long random;
1375     int x, y;
1376 };
1377
1378 static int get_square_cmpfn(void *v1, void *v2)
1379 {
1380     struct square *s1 = v1;
1381     struct square *s2 = v2;
1382     int r;
1383
1384     r = s1->x - s2->x;
1385     if (r)
1386         return r;
1387
1388     r = s1->y - s2->y;
1389     if (r)
1390         return r;
1391
1392     return 0;
1393 }
1394
1395 static int square_sort_cmpfn(void *v1, void *v2)
1396 {
1397     struct square *s1 = v1;
1398     struct square *s2 = v2;
1399     int r;
1400
1401     r = s2->score - s1->score;
1402     if (r) {
1403         return r;
1404     }
1405
1406     if (s1->random < s2->random)
1407         return -1;
1408     else if (s1->random > s2->random)
1409         return 1;
1410
1411     /*
1412      * It's _just_ possible that two squares might have been given
1413      * the same random value. In that situation, fall back to
1414      * comparing based on the coordinates. This introduces a tiny
1415      * directional bias, but not a significant one.
1416      */
1417     return get_square_cmpfn(v1, v2);
1418 }
1419
1420 enum { SQUARE_LIT, SQUARE_UNLIT };
1421
1422 #define SQUARE_STATE(i, j) \
1423     ( LEGAL_SQUARE(state, i, j) ? \
1424         LV_SQUARE_STATE(i,j) : \
1425         SQUARE_UNLIT )
1426
1427 #define LV_SQUARE_STATE(i, j) board[SQUARE_INDEX(state, i, j)]
1428
1429 /* Generate a new complete set of clues for the given game_state (respecting
1430  * the dimensions provided by said game_state) */
1431 static void add_full_clues(game_state *state, random_state *rs)
1432 {
1433     signed char *clues;
1434     char *board;
1435     int i, j, a, b, c;
1436     int board_area = SQUARE_COUNT(state);
1437     int t;
1438
1439     struct square *square, *tmpsquare, *sq;
1440     struct square square_pos;
1441
1442     /* These will contain exactly the same information, sorted into different
1443      * orders */
1444     tree234 *lightable_squares_sorted, *lightable_squares_gettable;
1445
1446 #define SQUARE_REACHABLE(i,j) \
1447      (t = (SQUARE_STATE(i-1, j) == SQUARE_LIT || \
1448            SQUARE_STATE(i+1, j) == SQUARE_LIT || \
1449            SQUARE_STATE(i, j-1) == SQUARE_LIT || \
1450            SQUARE_STATE(i, j+1) == SQUARE_LIT), \
1451       t)
1452
1453     /* One situation in which we may not light a square is if that'll leave one
1454      * square above/below and one left/right of us unlit, separated by a lit
1455      * square diagnonal from us */
1456 #define SQUARE_DIAGONAL_VIOLATION(i, j, h, v) \
1457     (t = (SQUARE_STATE((i)+(h), (j))     == SQUARE_UNLIT && \
1458           SQUARE_STATE((i),     (j)+(v)) == SQUARE_UNLIT && \
1459           SQUARE_STATE((i)+(h), (j)+(v)) == SQUARE_LIT), \
1460      t)
1461
1462     /* We also may not light a square if it will form a loop of lit squares
1463      * around some unlit squares, as then the game soln won't have a single
1464      * loop */
1465 #define SQUARE_LOOP_VIOLATION(i, j, lit1, lit2) \
1466     (SQUARE_STATE((i)+1, (j)) == lit1    && \
1467      SQUARE_STATE((i)-1, (j)) == lit1    && \
1468      SQUARE_STATE((i), (j)+1) == lit2    && \
1469      SQUARE_STATE((i), (j)-1) == lit2)
1470
1471 #define CAN_LIGHT_SQUARE(i, j) \
1472     (SQUARE_REACHABLE(i, j)                                 && \
1473      !SQUARE_DIAGONAL_VIOLATION(i, j, -1, -1)               && \
1474      !SQUARE_DIAGONAL_VIOLATION(i, j, +1, -1)               && \
1475      !SQUARE_DIAGONAL_VIOLATION(i, j, -1, +1)               && \
1476      !SQUARE_DIAGONAL_VIOLATION(i, j, +1, +1)               && \
1477      !SQUARE_LOOP_VIOLATION(i, j, SQUARE_LIT, SQUARE_UNLIT) && \
1478      !SQUARE_LOOP_VIOLATION(i, j, SQUARE_UNLIT, SQUARE_LIT))
1479
1480 #define IS_LIGHTING_CANDIDATE(i, j) \
1481     (SQUARE_STATE(i, j) == SQUARE_UNLIT && \
1482      CAN_LIGHT_SQUARE(i,j))
1483
1484     /* The 'score' of a square reflects its current desirability for selection
1485      * as the next square to light.  We want to encourage moving into uncharted
1486      * areas so we give scores according to how many of the square's neighbours
1487      * are currently unlit. */
1488
1489    /* UNLIT    SCORE
1490     *   3        2
1491     *   2        0
1492     *   1       -2
1493     */
1494 #define SQUARE_SCORE(i,j) \
1495     (2*((SQUARE_STATE(i-1, j) == SQUARE_UNLIT)  + \
1496         (SQUARE_STATE(i+1, j) == SQUARE_UNLIT)  + \
1497         (SQUARE_STATE(i, j-1) == SQUARE_UNLIT)  + \
1498         (SQUARE_STATE(i, j+1) == SQUARE_UNLIT)) - 4)
1499
1500     /* When a square gets lit, this defines how far away from that square we
1501      * need to go recomputing scores */
1502 #define SCORE_DISTANCE 1
1503
1504     board = snewn(board_area, char);
1505     clues = state->clues;
1506
1507     /* Make a board */
1508     memset(board, SQUARE_UNLIT, board_area);
1509
1510     /* Seed the board with a single lit square near the middle */
1511     i = state->w / 2;
1512     j = state->h / 2;
1513     if (state->w & 1 && random_bits(rs, 1))
1514         ++i;
1515     if (state->h & 1 && random_bits(rs, 1))
1516         ++j;
1517
1518     LV_SQUARE_STATE(i, j) = SQUARE_LIT;
1519
1520     /* We need a way of favouring squares that will increase our loopiness.
1521      * We do this by maintaining a list of all candidate squares sorted by
1522      * their score and choose randomly from that with appropriate skew.
1523      * In order to avoid consistently biasing towards particular squares, we
1524      * need the sort order _within_ each group of scores to be completely
1525      * random.  But it would be abusing the hospitality of the tree234 data
1526      * structure if our comparison function were nondeterministic :-).  So with
1527      * each square we associate a random number that does not change during a
1528      * particular run of the generator, and use that as a secondary sort key.
1529      * Yes, this means we will be biased towards particular random squares in
1530      * any one run but that doesn't actually matter. */
1531
1532     lightable_squares_sorted   = newtree234(square_sort_cmpfn);
1533     lightable_squares_gettable = newtree234(get_square_cmpfn);
1534 #define ADD_SQUARE(s) \
1535     do { \
1536         sq = add234(lightable_squares_sorted, s); \
1537         assert(sq == s); \
1538         sq = add234(lightable_squares_gettable, s); \
1539         assert(sq == s); \
1540     } while (0)
1541
1542 #define REMOVE_SQUARE(s) \
1543     do { \
1544         sq = del234(lightable_squares_sorted, s); \
1545         assert(sq); \
1546         sq = del234(lightable_squares_gettable, s); \
1547         assert(sq); \
1548     } while (0)
1549
1550 #define HANDLE_DIR(a, b) \
1551     square = snew(struct square); \
1552     square->x = (i)+(a); \
1553     square->y = (j)+(b); \
1554     square->score = 2; \
1555     square->random = random_bits(rs, 31); \
1556     ADD_SQUARE(square);
1557     HANDLE_DIR(-1, 0);
1558     HANDLE_DIR( 1, 0);
1559     HANDLE_DIR( 0,-1);
1560     HANDLE_DIR( 0, 1);
1561 #undef HANDLE_DIR
1562
1563     /* Light squares one at a time until the board is interesting enough */
1564     while (TRUE)
1565     {
1566         /* We have count234(lightable_squares) possibilities, and in
1567          * lightable_squares_sorted they are sorted with the most desirable
1568          * first.  */
1569         c = count234(lightable_squares_sorted);
1570         if (c == 0)
1571             break;
1572         assert(c == count234(lightable_squares_gettable));
1573
1574         /* Check that the best square available is any good */
1575         square = (struct square *)index234(lightable_squares_sorted, 0);
1576         assert(square);
1577
1578         /*
1579          * We never want to _decrease_ the loop's perimeter. Making
1580          * moves that leave the perimeter the same is occasionally
1581          * useful: if it were _never_ done then the user would be
1582          * able to deduce illicitly that any degree-zero vertex was
1583          * on the outside of the loop. So we do it sometimes but
1584          * not always.
1585          */
1586         if (square->score < 0 || (square->score == 0 &&
1587                                   random_upto(rs, 2) == 0)) {
1588             break;
1589         }
1590
1591         assert(square->score == SQUARE_SCORE(square->x, square->y));
1592         assert(SQUARE_STATE(square->x, square->y) == SQUARE_UNLIT);
1593         assert(square->x >= 0 && square->x < state->w);
1594         assert(square->y >= 0 && square->y < state->h);
1595
1596         /* Update data structures */
1597         LV_SQUARE_STATE(square->x, square->y) = SQUARE_LIT;
1598         REMOVE_SQUARE(square);
1599
1600         /* We might have changed the score of any squares up to 2 units away in
1601          * any direction */
1602         for (b = -SCORE_DISTANCE; b <= SCORE_DISTANCE; b++) {
1603             for (a = -SCORE_DISTANCE; a <= SCORE_DISTANCE; a++) {
1604                 if (!a && !b)
1605                     continue;
1606                 square_pos.x = square->x + a;
1607                 square_pos.y = square->y + b;
1608                 if (square_pos.x < 0 || square_pos.x >= state->w ||
1609                     square_pos.y < 0 || square_pos.y >= state->h) {
1610                    continue;
1611                 }
1612                 tmpsquare = find234(lightable_squares_gettable, &square_pos,
1613                                     NULL);
1614                 if (tmpsquare) {
1615                     assert(tmpsquare->x == square_pos.x);
1616                     assert(tmpsquare->y == square_pos.y);
1617                     assert(SQUARE_STATE(tmpsquare->x, tmpsquare->y) ==
1618                            SQUARE_UNLIT);
1619                     REMOVE_SQUARE(tmpsquare);
1620                 } else {
1621                     tmpsquare = snew(struct square);
1622                     tmpsquare->x = square_pos.x;
1623                     tmpsquare->y = square_pos.y;
1624                     tmpsquare->random = random_bits(rs, 31);
1625                 }
1626                 tmpsquare->score = SQUARE_SCORE(tmpsquare->x, tmpsquare->y);
1627
1628                 if (IS_LIGHTING_CANDIDATE(tmpsquare->x, tmpsquare->y)) {
1629                     ADD_SQUARE(tmpsquare);
1630                 } else {
1631                     sfree(tmpsquare);
1632                 }
1633             }
1634         }
1635         sfree(square);
1636     }
1637
1638     /* Clean up */
1639     while ((square = delpos234(lightable_squares_gettable, 0)) != NULL)
1640         sfree(square);
1641     freetree234(lightable_squares_gettable);
1642     freetree234(lightable_squares_sorted);
1643
1644     /* Copy out all the clues */
1645     FORALL_SQUARES(state, i, j) {
1646         c = SQUARE_STATE(i, j);
1647         LV_CLUE_AT(state, i, j) = 0;
1648         if (SQUARE_STATE(i-1, j) != c) ++LV_CLUE_AT(state, i, j);
1649         if (SQUARE_STATE(i+1, j) != c) ++LV_CLUE_AT(state, i, j);
1650         if (SQUARE_STATE(i, j-1) != c) ++LV_CLUE_AT(state, i, j);
1651         if (SQUARE_STATE(i, j+1) != c) ++LV_CLUE_AT(state, i, j);
1652     }
1653
1654     sfree(board);
1655 }
1656
1657 static int game_has_unique_soln(const game_state *state, int diff)
1658 {
1659     int ret;
1660     solver_state *sstate_new;
1661     solver_state *sstate = new_solver_state((game_state *)state, diff);
1662
1663     sstate_new = solve_game_rec(sstate, diff);
1664
1665     assert(sstate_new->solver_status != SOLVER_MISTAKE);
1666     ret = (sstate_new->solver_status == SOLVER_SOLVED);
1667
1668     free_solver_state(sstate_new);
1669     free_solver_state(sstate);
1670
1671     return ret;
1672 }
1673
1674 /* Remove clues one at a time at random. */
1675 static game_state *remove_clues(game_state *state, random_state *rs,
1676                                 int diff)
1677 {
1678     int *square_list, squares;
1679     game_state *ret = dup_game(state), *saved_ret;
1680     int n;
1681 #ifdef SHOW_WORKING
1682     char *desc;
1683 #endif
1684
1685     /* We need to remove some clues.  We'll do this by forming a list of all
1686      * available clues, shuffling it, then going along one at a
1687      * time clearing each clue in turn for which doing so doesn't render the
1688      * board unsolvable. */
1689     squares = state->w * state->h;
1690     square_list = snewn(squares, int);
1691     for (n = 0; n < squares; ++n) {
1692         square_list[n] = n;
1693     }
1694
1695     shuffle(square_list, squares, sizeof(int), rs);
1696
1697     for (n = 0; n < squares; ++n) {
1698         saved_ret = dup_game(ret);
1699         LV_CLUE_AT(ret, square_list[n] % state->w,
1700                    square_list[n] / state->w) = -1;
1701
1702 #ifdef SHOW_WORKING
1703         desc = state_to_text(ret);
1704         fprintf(stderr, "%dx%d:%s\n", state->w, state->h, desc);
1705         sfree(desc);
1706 #endif
1707
1708         if (game_has_unique_soln(ret, diff)) {
1709             free_game(saved_ret);
1710         } else {
1711             free_game(ret);
1712             ret = saved_ret;
1713         }
1714     }
1715     sfree(square_list);
1716
1717     return ret;
1718 }
1719
1720 static char *new_game_desc(game_params *params, random_state *rs,
1721                            char **aux, int interactive)
1722 {
1723     /* solution and description both use run-length encoding in obvious ways */
1724     char *retval;
1725     game_state *state = snew(game_state), *state_new;
1726
1727     state->h = params->h;
1728     state->w = params->w;
1729
1730     state->clues = snewn(SQUARE_COUNT(params), signed char);
1731     state->hl = snewn(HL_COUNT(params), char);
1732     state->vl = snewn(VL_COUNT(params), char);
1733
1734 newboard_please:
1735     memset(state->hl, LINE_UNKNOWN, HL_COUNT(params));
1736     memset(state->vl, LINE_UNKNOWN, VL_COUNT(params));
1737
1738     state->solved = state->cheated = FALSE;
1739     state->recursion_depth = params->rec;
1740
1741     /* Get a new random solvable board with all its clues filled in.  Yes, this
1742      * can loop for ever if the params are suitably unfavourable, but
1743      * preventing games smaller than 4x4 seems to stop this happening */
1744
1745     do {
1746         add_full_clues(state, rs);
1747     } while (!game_has_unique_soln(state, params->diff));
1748
1749     state_new = remove_clues(state, rs, params->diff);
1750     free_game(state);
1751     state = state_new;
1752
1753     if (params->diff > 0 && game_has_unique_soln(state, params->diff-1)) {
1754 #ifdef SHOW_WORKING
1755         fprintf(stderr, "Rejecting board, it is too easy\n");
1756 #endif
1757         goto newboard_please;
1758     }
1759
1760     retval = state_to_text(state);
1761
1762     free_game(state);
1763
1764     assert(!validate_desc(params, retval));
1765
1766     return retval;
1767 }
1768
1769 static game_state *new_game(midend *me, game_params *params, char *desc)
1770 {
1771     int i,j;
1772     game_state *state = snew(game_state);
1773     int empties_to_make = 0;
1774     int n;
1775     const char *dp = desc;
1776
1777     state->recursion_depth = 0; /* XXX pending removal, probably */
1778
1779     state->h = params->h;
1780     state->w = params->w;
1781
1782     state->clues = snewn(SQUARE_COUNT(params), signed char);
1783     state->hl = snewn(HL_COUNT(params), char);
1784     state->vl = snewn(VL_COUNT(params), char);
1785
1786     state->solved = state->cheated = FALSE;
1787
1788     FORALL_SQUARES(params, i, j) {
1789         if (empties_to_make) {
1790             empties_to_make--;
1791             LV_CLUE_AT(state, i, j) = -1;
1792             continue;
1793         }
1794
1795         assert(*dp);
1796         n = *dp - '0';
1797         if (n >= 0 && n < 10) {
1798             LV_CLUE_AT(state, i, j) = n;
1799         } else {
1800             n = *dp - 'a' + 1;
1801             assert(n > 0);
1802             LV_CLUE_AT(state, i, j) = -1;
1803             empties_to_make = n - 1;
1804         }
1805         ++dp;
1806     }
1807
1808     memset(state->hl, LINE_UNKNOWN, HL_COUNT(params));
1809     memset(state->vl, LINE_UNKNOWN, VL_COUNT(params));
1810
1811     return state;
1812 }
1813
1814 enum { LOOP_NONE=0, LOOP_SOLN, LOOP_NOT_SOLN };
1815
1816 /* ----------------------------------------------------------------------
1817  * Solver logic
1818  *
1819  * Our solver modes operate as follows.  Each mode also uses the modes above it.
1820  *
1821  *   Easy Mode
1822  *   Just implement the rules of the game.
1823  *
1824  *   Normal Mode
1825  *   For each pair of lines through each dot we store a bit for whether
1826  *   at least one of them is on and whether at most one is on.  (If we know
1827  *   both or neither is on that's already stored more directly.)  That's six
1828  *   bits per dot.  Bit number n represents the lines shown in dline_desc.
1829  *
1830  *   Advanced Mode
1831  *   Use edsf data structure to make equivalence classes of lines that are
1832  *   known identical to or opposite to one another.
1833  */
1834
1835 /* The order the following are defined in is very important, see below.
1836  * The last two fields may seem non-obvious: they specify that when talking
1837  * about a square the dx and dy offsets should be added to the square coords to
1838  * get to the right dot.  Where dx and dy are -1 this means that the dline
1839  * doesn't make sense for a square. */
1840 /* XXX can this be done with a struct instead? */
1841 #define DLINES \
1842     DLINE(DLINE_UD, UP,   DOWN,  -1, -1) \
1843     DLINE(DLINE_LR, LEFT, RIGHT, -1, -1) \
1844     DLINE(DLINE_UR, UP,   RIGHT,  0,  1) \
1845     DLINE(DLINE_DL, DOWN, LEFT,   1,  0) \
1846     DLINE(DLINE_UL, UP,   LEFT,   1,  1) \
1847     DLINE(DLINE_DR, DOWN, RIGHT,  0,  0)
1848
1849 #define OPP_DLINE(dline_desc) ((dline_desc) ^ 1)
1850
1851 enum dline_desc {
1852 #define DLINE(desc, dir1, dir2, dx, dy) \
1853     desc,
1854     DLINES
1855 #undef DLINE
1856 };
1857
1858 struct dline {
1859     enum dline_desc desc;
1860     enum direction dir1, dir2;
1861     int dx, dy;
1862 };
1863
1864 const static struct dline dlines[] =  {
1865 #define DLINE(desc, dir1, dir2, dx, dy) \
1866     { desc, dir1, dir2, dx, dy },
1867     DLINES
1868 #undef DLINE
1869 };
1870
1871 #define FORALL_DOT_DLINES(dl_iter) \
1872     for (dl_iter = 0; dl_iter < lenof(dlines); ++dl_iter)
1873
1874 #define FORALL_SQUARE_DLINES(dl_iter) \
1875     for (dl_iter = 2; dl_iter < lenof(dlines); ++dl_iter)
1876
1877 #define DL2STR(d) \
1878     ((d==DLINE_UD) ? "DLINE_UD": \
1879      (d==DLINE_LR) ? "DLINE_LR": \
1880      (d==DLINE_UR) ? "DLINE_UR": \
1881      (d==DLINE_DL) ? "DLINE_DL": \
1882      (d==DLINE_UL) ? "DLINE_UL": \
1883      (d==DLINE_DR) ? "DLINE_DR": \
1884      "oops")
1885
1886 #define CHECK_DLINE_SENSIBLE(d) assert(dlines[(d)].dx != -1 && dlines[(d)].dy != -1)
1887
1888 /* This will fail an assertion if the directions handed to it are the same, as
1889  * no dline corresponds to that */
1890 static enum dline_desc dline_desc_from_dirs(enum direction dir1,
1891                                             enum direction dir2)
1892 {
1893     int i;
1894
1895     assert (dir1 != dir2);
1896
1897     for (i = 0; i < lenof(dlines); ++i) {
1898         if ((dir1 == dlines[i].dir1 && dir2 == dlines[i].dir2) ||
1899             (dir1 == dlines[i].dir2 && dir2 == dlines[i].dir1)) {
1900             return dlines[i].desc;
1901         }
1902     }
1903
1904     assert(!"dline not found");
1905     return DLINE_UD; /* placate compiler */
1906 }
1907
1908 /* The following functions allow you to get or set info about the selected
1909  * dline corresponding to the dot or square at [i,j].  You'll get an assertion
1910  * failure if you talk about a dline that doesn't exist, ie if you ask about
1911  * non-touching lines around a square. */
1912 static int get_dot_dline(const game_state *state, const char *dline_array,
1913                          int i, int j, enum dline_desc desc)
1914 {
1915 /*    fprintf(stderr, "get_dot_dline %p [%d,%d] %s\n", dline_array, i, j, DL2STR(desc)); */
1916     return BIT_SET(dline_array[i + (state->w + 1) * j], desc);
1917 }
1918
1919 static int set_dot_dline(game_state *state, char *dline_array,
1920                          int i, int j, enum dline_desc desc
1921 #ifdef SHOW_WORKING
1922                          , const char *reason
1923 #endif
1924                          )
1925 {
1926     int ret;
1927     ret = SET_BIT(dline_array[i + (state->w + 1) * j], desc);
1928
1929 #ifdef SHOW_WORKING
1930     if (ret)
1931         fprintf(stderr, "set_dot_dline %p [%d,%d] %s (%s)\n", dline_array, i, j, DL2STR(desc), reason);
1932 #endif
1933     return ret;
1934 }
1935
1936 static int get_square_dline(game_state *state, char *dline_array,
1937                             int i, int j, enum dline_desc desc)
1938 {
1939     CHECK_DLINE_SENSIBLE(desc);
1940 /*    fprintf(stderr, "get_square_dline %p [%d,%d] %s\n", dline_array, i, j, DL2STR(desc)); */
1941     return BIT_SET(dline_array[(i+dlines[desc].dx) + (state->w + 1) * (j+dlines[desc].dy)],
1942                    desc);
1943 }
1944
1945 static int set_square_dline(game_state *state, char *dline_array,
1946                             int i, int j, enum dline_desc desc
1947 #ifdef SHOW_WORKING
1948                             , const char *reason
1949 #endif
1950                             )
1951 {
1952     int ret;
1953     CHECK_DLINE_SENSIBLE(desc);
1954     ret = SET_BIT(dline_array[(i+dlines[desc].dx) + (state->w + 1) * (j+dlines[desc].dy)], desc);
1955 #ifdef SHOW_WORKING
1956     if (ret)
1957         fprintf(stderr, "set_square_dline %p [%d,%d] %s (%s)\n", dline_array, i, j, DL2STR(desc), reason);
1958 #endif
1959     return ret;
1960 }
1961
1962 #ifdef SHOW_WORKING
1963 #define set_dot_dline(a, b, c, d, e) \
1964         set_dot_dline(a, b, c, d, e, __FUNCTION__)
1965 #define set_square_dline(a, b, c, d, e) \
1966         set_square_dline(a, b, c, d, e, __FUNCTION__)
1967 #endif
1968
1969 static int set_dot_opp_dline(game_state *state, char *dline_array,
1970                              int i, int j, enum dline_desc desc)
1971 {
1972     return set_dot_dline(state, dline_array, i, j, OPP_DLINE(desc));
1973 }
1974
1975 static int set_square_opp_dline(game_state *state, char *dline_array,
1976                                 int i, int j, enum dline_desc desc)
1977 {
1978     return set_square_dline(state, dline_array, i, j, OPP_DLINE(desc));
1979 }
1980
1981 /* Find out if both the lines in the given dline are UNKNOWN */
1982 static int dline_both_unknown(const game_state *state, int i, int j,
1983                               enum dline_desc desc)
1984 {
1985     return
1986         (get_line_status_from_point(state, i, j, dlines[desc].dir1) == LINE_UNKNOWN) &&
1987         (get_line_status_from_point(state, i, j, dlines[desc].dir2) == LINE_UNKNOWN);
1988 }
1989
1990 #define SQUARE_DLINES \
1991                    HANDLE_DLINE(DLINE_UL, RIGHTOF_SQUARE, BELOW_SQUARE, 1, 1); \
1992                    HANDLE_DLINE(DLINE_UR, LEFTOF_SQUARE,  BELOW_SQUARE, 0, 1); \
1993                    HANDLE_DLINE(DLINE_DL, RIGHTOF_SQUARE, ABOVE_SQUARE, 1, 0); \
1994                    HANDLE_DLINE(DLINE_DR, LEFTOF_SQUARE,  ABOVE_SQUARE, 0, 0);
1995
1996 #define DOT_DLINES \
1997                    HANDLE_DLINE(DLINE_UD,    ABOVE_DOT,  BELOW_DOT); \
1998                    HANDLE_DLINE(DLINE_LR,    LEFTOF_DOT, RIGHTOF_DOT); \
1999                    HANDLE_DLINE(DLINE_UL,    ABOVE_DOT,  LEFTOF_DOT); \
2000                    HANDLE_DLINE(DLINE_UR,    ABOVE_DOT,  RIGHTOF_DOT); \
2001                    HANDLE_DLINE(DLINE_DL,    BELOW_DOT,  LEFTOF_DOT); \
2002                    HANDLE_DLINE(DLINE_DR,    BELOW_DOT,  RIGHTOF_DOT);
2003
2004 static void array_setall(char *array, char from, char to, int len)
2005 {
2006     char *p = array, *p_old = p;
2007     int len_remaining = len;
2008
2009     while ((p = memchr(p, from, len_remaining))) {
2010         *p = to;
2011         len_remaining -= p - p_old;
2012         p_old = p;
2013     }
2014 }
2015
2016
2017
2018 static int get_line_status_from_point(const game_state *state,
2019                                       int x, int y, enum direction d)
2020 {
2021     switch (d) {
2022         case LEFT:
2023             return LEFTOF_DOT(state, x, y);
2024         case RIGHT:
2025             return RIGHTOF_DOT(state, x, y);
2026         case UP:
2027             return ABOVE_DOT(state, x, y);
2028         case DOWN:
2029             return BELOW_DOT(state, x, y);
2030     }
2031
2032     return 0;
2033 }
2034
2035 /* First and second args are coord offset from top left of square to one end
2036  * of line in question, third and fourth args are the direction from the first
2037  * end of the line to the second.  Fifth arg is the direction of the line from
2038  * the coord offset position.
2039  * How confusing.
2040  */
2041 #define SQUARE_LINES \
2042     SQUARE_LINE( 0,  0, RIGHT, RIGHTOF_DOT, UP); \
2043     SQUARE_LINE( 0, +1, RIGHT, RIGHTOF_DOT, DOWN); \
2044     SQUARE_LINE( 0,  0, DOWN,  BELOW_DOT,   LEFT); \
2045     SQUARE_LINE(+1,  0, DOWN,  BELOW_DOT,   RIGHT);
2046
2047 /* Set pairs of lines around this square which are known to be identical to
2048  * the given line_state */
2049 static int square_setall_identical(solver_state *sstate, int x, int y,
2050                                    enum line_state line_new)
2051 {
2052     /* can[dir] contains the canonical line associated with the line in
2053      * direction dir from the square in question.  Similarly inv[dir] is
2054      * whether or not the line in question is inverse to its canonical
2055      * element. */
2056     int can[4], inv[4], i, j;
2057     int retval = FALSE;
2058
2059     i = 0;
2060
2061 #if 0
2062     fprintf(stderr, "Setting all identical unknown lines around square "
2063                     "[%d,%d] to %d:\n", x, y, line_new);
2064 #endif
2065
2066 #define SQUARE_LINE(dx, dy, linedir, dir_dot, sqdir) \
2067     can[sqdir] = \
2068         edsf_canonify(sstate->hard->linedsf, \
2069                       LINEDSF_INDEX(sstate->state, x+(dx), y+(dy), linedir), \
2070                       &inv[sqdir]);
2071
2072     SQUARE_LINES;
2073
2074 #undef SQUARE_LINE
2075
2076     for (j = 0; j < 4; ++j) {
2077         for (i = 0; i < 4; ++i) {
2078             if (i == j)
2079                 continue;
2080
2081             if (can[i] == can[j] && inv[i] == inv[j]) {
2082
2083                 /* Lines in directions i and j are identical.
2084                  * Only do j now, we'll do i when the loop causes us to
2085                  * consider {i,j} in the opposite order. */
2086 #define SQUARE_LINE(dx, dy, dir, c, sqdir) \
2087                 if (j == sqdir) { \
2088                     retval = set_line_bydot(sstate, x+(dx), y+(dy), dir, line_new); \
2089                     if (retval) { \
2090                         break; \
2091                     } \
2092                 }
2093
2094                 SQUARE_LINES;
2095
2096 #undef SQUARE_LINE
2097             }
2098         }
2099     }
2100
2101     return retval;
2102 }
2103
2104 #if 0
2105 /* Set all identical lines passing through the current dot to the chosen line
2106  * state.  (implicitly this only looks at UNKNOWN lines) */
2107 static int dot_setall_identical(solver_state *sstate, int x, int y,
2108                                 enum line_state line_new)
2109 {
2110     /* The implementation of this is a little naughty but I can't see how to do
2111      * it elegantly any other way */
2112     int can[4], inv[4], i, j;
2113     enum direction d;
2114     int retval = FALSE;
2115
2116     for (d = 0; d < 4; ++d) {
2117         can[d] = edsf_canonify(sstate->hard->linedsf,
2118                                LINEDSF_INDEX(sstate->state, x, y, d),
2119                                inv+d);
2120     }
2121
2122     for (j = 0; j < 4; ++j) {
2123 next_j:
2124         for (i = 0; i < j; ++i) {
2125             if (can[i] == can[j] && inv[i] == inv[j]) {
2126                 /* Lines in directions i and j are identical */
2127                 if (get_line_status_from_point(sstate->state, x, y, j) ==
2128                         LINE_UNKNOWN) {
2129                     set_line_bydot(sstate->state, x, y, j,
2130                                                line_new);
2131                     retval = TRUE;
2132                     goto next_j;
2133                 }
2134             }
2135
2136         }
2137     }
2138
2139     return retval;
2140 }
2141 #endif
2142
2143 static int square_setboth_in_dline(solver_state *sstate, enum dline_desc dd,
2144                                    int i, int j, enum line_state line_new)
2145 {
2146     int retval = FALSE;
2147     const struct dline dll = dlines[dd], *dl = &dll;
2148
2149 #if 0
2150     fprintf(stderr, "square_setboth_in_dline %s [%d,%d] to %d\n",
2151                     DL2STR(dd), i, j, line_new);
2152 #endif
2153
2154     CHECK_DLINE_SENSIBLE(dd);
2155
2156     retval |=
2157         set_line_bydot(sstate, i+dl->dx, j+dl->dy, dl->dir1, line_new);
2158     retval |=
2159         set_line_bydot(sstate, i+dl->dx, j+dl->dy, dl->dir2, line_new);
2160
2161     return retval;
2162 }
2163
2164 /* Call this function to register that the two unknown lines going into the dot
2165  * [x,y] are identical or opposite (depending on the value of 'inverse').  This
2166  * function will cause an assertion failure if anything other than exactly two
2167  * lines into the dot are unknown.
2168  * As usual returns TRUE if any progress was made, otherwise FALSE. */
2169 static int dot_relate_2_unknowns(solver_state *sstate, int x, int y, int inverse)
2170 {
2171     enum direction d1=DOWN, d2=DOWN; /* Just to keep compiler quiet */
2172     int dirs_set = 0;
2173
2174 #define TRY_DIR(d) \
2175               if (get_line_status_from_point(sstate->state, x, y, d) == \
2176                       LINE_UNKNOWN) { \
2177                   if (dirs_set == 0) \
2178                       d1 = d; \
2179                   else { \
2180                       assert(dirs_set == 1); \
2181                       d2 = d; \
2182                   } \
2183                   dirs_set++; \
2184               } while (0)
2185
2186     TRY_DIR(UP);
2187     TRY_DIR(DOWN);
2188     TRY_DIR(LEFT);
2189     TRY_DIR(RIGHT);
2190 #undef TRY_DIR
2191
2192     assert(dirs_set == 2);
2193     assert(d1 != d2);
2194
2195 #if 0
2196     fprintf(stderr, "Lines in direction %s and %s from dot [%d,%d] are %s\n",
2197             DIR2STR(d1), DIR2STR(d2), x, y, inverse?"opposite":"the same");
2198 #endif
2199
2200     return merge_lines(sstate, x, y, d1, x, y, d2, inverse);
2201 }
2202
2203 /* Very similar to dot_relate_2_unknowns. */
2204 static int square_relate_2_unknowns(solver_state *sstate, int x, int y, int inverse)
2205 {
2206     enum direction d1=DOWN, d2=DOWN;
2207     int x1=-1, y1=-1, x2=-1, y2=-1;
2208     int dirs_set = 0;
2209
2210 #if 0
2211     fprintf(stderr, "2 unknowns around square [%d,%d] are %s\n",
2212                      x, y, inverse?"opposite":"the same");
2213 #endif
2214
2215 #define TRY_DIR(i, j, d, dir_sq) \
2216           do { \
2217               if (dir_sq(sstate->state, x, y) == LINE_UNKNOWN) { \
2218                   if (dirs_set == 0) { \
2219                       d1 = d; x1 = i; y1 = j; \
2220                   } else { \
2221                       assert(dirs_set == 1); \
2222                       d2 = d; x2 = i; y2 = j; \
2223                   } \
2224                   dirs_set++; \
2225               } \
2226           } while (0)
2227
2228     TRY_DIR(x,   y,   RIGHT, ABOVE_SQUARE);
2229     TRY_DIR(x,   y,   DOWN, LEFTOF_SQUARE);
2230     TRY_DIR(x+1, y,   DOWN, RIGHTOF_SQUARE);
2231     TRY_DIR(x,   y+1, RIGHT, BELOW_SQUARE);
2232 #undef TRY_DIR
2233
2234     assert(dirs_set == 2);
2235
2236 #if 0
2237     fprintf(stderr, "Line in direction %s from dot [%d,%d] and line in direction %s from dot [%2d,%2d] are %s\n",
2238             DIR2STR(d1), x1, y1, DIR2STR(d2), x2, y2, inverse?"opposite":"the same");
2239 #endif
2240
2241     return merge_lines(sstate, x1, y1, d1, x2, y2, d2, inverse);
2242 }
2243
2244 /* Figure out if any dlines can be 'collapsed' (and do so if they can).  This
2245  * can happen if one of the lines is known and due to the dline status this
2246  * tells us state of the other, or if there's an interaction with the linedsf
2247  * (ie if atmostone is set for a dline and the lines are known identical they
2248  * must both be LINE_NO, etc).  XXX at the moment only the former is
2249  * implemented, and indeed the latter should be implemented in the hard mode
2250  * solver only.
2251  */
2252 static int dot_collapse_dlines(solver_state *sstate, int i, int j)
2253 {
2254     int progress = FALSE;
2255     enum direction dir1, dir2;
2256     int dir1st;
2257     int dlset;
2258     game_state *state = sstate->state;
2259     enum dline_desc dd;
2260
2261     for (dir1 = 0; dir1 < 4; dir1++) {
2262         dir1st = get_line_status_from_point(state, i, j, dir1);
2263         if (dir1st == LINE_UNKNOWN)
2264             continue;
2265         /* dir2 iterates over the whole range rather than starting at dir1+1
2266          * because test below is asymmetric */
2267         for (dir2 = 0; dir2 < 4; dir2++) {
2268             if (dir1 == dir2)
2269                 continue;
2270
2271             if ((i == 0        && (dir1 == LEFT  || dir2 == LEFT))  ||
2272                 (j == 0        && (dir1 == UP    || dir2 == UP))    ||
2273                 (i == state->w && (dir1 == RIGHT || dir2 == RIGHT)) ||
2274                 (j == state->h && (dir1 == DOWN  || dir2 == DOWN))) {
2275                 continue;
2276             }
2277
2278 #if 0
2279         fprintf(stderr, "dot_collapse_dlines [%d,%d], %s %s\n", i, j,
2280                     DIR2STR(dir1), DIR2STR(dir2));
2281 #endif
2282
2283             if (get_line_status_from_point(state, i, j, dir2) ==
2284                 LINE_UNKNOWN) {
2285                 dd = dline_desc_from_dirs(dir1, dir2);
2286
2287                 dlset = get_dot_dline(state, sstate->normal->dot_atmostone, i, j, dd);
2288                 if (dlset && dir1st == LINE_YES) {
2289 /*                    fprintf(stderr, "setting %s to NO\n", DIR2STR(dir2)); */
2290                     progress |=
2291                         set_line_bydot(sstate, i, j, dir2, LINE_NO);
2292                 }
2293
2294                 dlset = get_dot_dline(state, sstate->normal->dot_atleastone, i, j, dd);
2295                 if (dlset && dir1st == LINE_NO) {
2296 /*                    fprintf(stderr, "setting %s to YES\n", DIR2STR(dir2)); */
2297                     progress |=
2298                         set_line_bydot(sstate, i, j, dir2, LINE_YES);
2299                 }
2300             }
2301         }
2302     }
2303
2304     return progress;
2305 }
2306
2307 /*
2308  * These are the main solver functions.
2309  *
2310  * Their return values are diff values corresponding to the lowest mode solver
2311  * that would notice the work that they have done.  For example if the normal
2312  * mode solver adds actual lines or crosses, it will return DIFF_EASY as the
2313  * easy mode solver might be able to make progress using that.  It doesn't make
2314  * sense for one of them to return a diff value higher than that of the
2315  * function itself.
2316  *
2317  * Each function returns the lowest value it can, as early as possible, in
2318  * order to try and pass as much work as possible back to the lower level
2319  * solvers which progress more quickly.
2320  */
2321
2322 /* PROPOSED NEW DESIGN:
2323  * We have a work queue consisting of 'events' notifying us that something has
2324  * happened that a particular solver mode might be interested in.  For example
2325  * the hard mode solver might do something that helps the normal mode solver at
2326  * dot [x,y] in which case it will enqueue an event recording this fact.  Then
2327  * we pull events off the work queue, and hand each in turn to the solver that
2328  * is interested in them.  If a solver reports that it failed we pass the same
2329  * event on to progressively more advanced solvers and the loop detector.  Once
2330  * we've exhausted an event, or it has helped us progress, we drop it and
2331  * continue to the next one.  The events are sorted first in order of solver
2332  * complexity (easy first) then order of insertion (oldest first).
2333  * Once we run out of events we loop over each permitted solver in turn
2334  * (easiest first) until either a deduction is made (and an event therefore
2335  * emerges) or no further deductions can be made (in which case we've failed).
2336  *
2337  * QUESTIONS:
2338  *    * How do we 'loop over' a solver when both dots and squares are concerned.
2339  *      Answer: first all squares then all dots.
2340  */
2341
2342 static int easy_mode_deductions(solver_state *sstate)
2343 {
2344     int i, j, h, w, current_yes, current_no;
2345     game_state *state;
2346     int diff = DIFF_MAX;
2347
2348     state = sstate->state;
2349     h = state->h;
2350     w = state->w;
2351
2352     /* Per-square deductions */
2353     FORALL_SQUARES(state, i, j) {
2354         if (sstate->square_solved[SQUARE_INDEX(state, i, j)])
2355             continue;
2356
2357         current_yes = SQUARE_YES_COUNT(sstate, i, j);
2358         current_no  = SQUARE_NO_COUNT(sstate, i, j);
2359
2360         if (current_yes + current_no == 4)  {
2361             sstate->square_solved[SQUARE_INDEX(state, i, j)] = TRUE;
2362 /*            diff = min(diff, DIFF_EASY); */
2363             continue;
2364         }
2365
2366         if (CLUE_AT(state, i, j) < 0)
2367             continue;
2368
2369         if (CLUE_AT(state, i, j) < current_yes) {
2370 #if 0
2371             fprintf(stderr, "detected error [%d,%d] in %s at line %d\n", i, j, __FUNCTION__, __LINE__);
2372 #endif
2373             sstate->solver_status = SOLVER_MISTAKE;
2374             return DIFF_EASY;
2375         }
2376         if (CLUE_AT(state, i, j) == current_yes) {
2377             if (square_setall(sstate, i, j, LINE_UNKNOWN, LINE_NO))
2378                 diff = min(diff, DIFF_EASY);
2379             sstate->square_solved[SQUARE_INDEX(state, i, j)] = TRUE;
2380             continue;
2381         }
2382
2383         if (4 - CLUE_AT(state, i, j) < current_no) {
2384 #if 0
2385             fprintf(stderr, "detected error [%d,%d] in %s at line %d\n", i, j, __FUNCTION__, __LINE__);
2386 #endif
2387             sstate->solver_status = SOLVER_MISTAKE;
2388             return DIFF_EASY;
2389         }
2390         if (4 - CLUE_AT(state, i, j) == current_no) {
2391             if (square_setall(sstate, i, j, LINE_UNKNOWN, LINE_YES))
2392                 diff = min(diff, DIFF_EASY);
2393             sstate->square_solved[SQUARE_INDEX(state, i, j)] = TRUE;
2394             continue;
2395         }
2396     }
2397
2398     check_caches(sstate);
2399
2400     /* Per-dot deductions */
2401     FORALL_DOTS(state, i, j) {
2402         if (sstate->dot_solved[DOT_INDEX(state, i, j)])
2403             continue;
2404
2405         switch (DOT_YES_COUNT(sstate, i, j)) {
2406             case 0:
2407                 switch (DOT_NO_COUNT(sstate, i, j)) {
2408                     case 3:
2409 #if 0
2410                         fprintf(stderr, "dot [%d,%d]: 0 yes, 3 no\n", i, j);
2411 #endif
2412                         dot_setall(sstate, i, j, LINE_UNKNOWN, LINE_NO);
2413                         diff = min(diff, DIFF_EASY);
2414                         /* fall through */
2415                     case 4:
2416                         sstate->dot_solved[DOT_INDEX(state, i, j)] = TRUE;
2417                         break;
2418                 }
2419                 break;
2420             case 1:
2421                 switch (DOT_NO_COUNT(sstate, i, j)) {
2422                     case 2: /* 1 yes, 2 no */
2423 #if 0
2424                         fprintf(stderr, "dot [%d,%d]: 1 yes, 2 no\n", i, j);
2425 #endif
2426                         dot_setall(sstate, i, j, LINE_UNKNOWN, LINE_YES);
2427                         diff = min(diff, DIFF_EASY);
2428                         sstate->dot_solved[DOT_INDEX(state, i, j)] = TRUE;
2429                         break;
2430                     case 3: /* 1 yes, 3 no */
2431 #if 0
2432                         fprintf(stderr, "detected error [%d,%d] in %s at line %d\n", i, j, __FUNCTION__, __LINE__);
2433 #endif
2434                         sstate->solver_status = SOLVER_MISTAKE;
2435                         return DIFF_EASY;
2436                 }
2437                 break;
2438             case 2:
2439 #if 0
2440                 fprintf(stderr, "dot [%d,%d]: 2 yes\n", i, j);
2441 #endif
2442                 dot_setall(sstate, i, j, LINE_UNKNOWN, LINE_NO);
2443                 diff = min(diff, DIFF_EASY);
2444                 sstate->dot_solved[DOT_INDEX(state, i, j)] = TRUE;
2445                 break;
2446             case 3:
2447             case 4:
2448 #if 0
2449                 fprintf(stderr, "detected error [%d,%d] in %s at line %d\n", i, j, __FUNCTION__, __LINE__);
2450 #endif
2451                 sstate->solver_status = SOLVER_MISTAKE;
2452                 return DIFF_EASY;
2453         }
2454     }
2455
2456     check_caches(sstate);
2457
2458     return diff;
2459 }
2460
2461 static int normal_mode_deductions(solver_state *sstate)
2462 {
2463     int i, j;
2464     game_state *state = sstate->state;
2465     enum dline_desc dd;
2466     int diff = DIFF_MAX;
2467
2468     FORALL_SQUARES(state, i, j) {
2469         if (sstate->square_solved[SQUARE_INDEX(state, i, j)])
2470             continue;
2471
2472         if (CLUE_AT(state, i, j) < 0)
2473             continue;
2474
2475         switch (CLUE_AT(state, i, j)) {
2476             case 1:
2477 #if 0
2478                 fprintf(stderr, "clue [%d,%d] is 1, doing dline ops\n",
2479                         i, j);
2480 #endif
2481                 FORALL_SQUARE_DLINES(dd) {
2482                     /* At most one of any DLINE can be set */
2483                     if (set_square_dline(state,
2484                                          sstate->normal->dot_atmostone,
2485                                          i, j, dd)) {
2486                         diff = min(diff, DIFF_NORMAL);
2487                     }
2488
2489                     if (get_square_dline(state,
2490                                          sstate->normal->dot_atleastone,
2491                                          i, j, dd)) {
2492                         /* This DLINE provides enough YESes to solve the clue */
2493                         if (square_setboth_in_dline(sstate, OPP_DLINE(dd),
2494                                                      i, j, LINE_NO)) {
2495                             diff = min(diff, DIFF_EASY);
2496                         }
2497                     }
2498                 }
2499
2500                 break;
2501             case 2:
2502                 /* If at least one of one DLINE is set, at most one
2503                  * of the opposing one is and vice versa */
2504 #if 0
2505                 fprintf(stderr, "clue [%d,%d] is 2, doing dline ops\n",
2506                                i, j);
2507 #endif
2508                 FORALL_SQUARE_DLINES(dd) {
2509                     if (get_square_dline(state,
2510                                          sstate->normal->dot_atmostone,
2511                                          i, j, dd)) {
2512                         if (set_square_opp_dline(state,
2513                                                  sstate->normal->dot_atleastone,
2514                                                  i, j, dd)) {
2515                             diff = min(diff, DIFF_NORMAL);
2516                         }
2517                     }
2518                     if (get_square_dline(state,
2519                                          sstate->normal->dot_atleastone,
2520                                          i, j, dd)) {
2521                         if (set_square_opp_dline(state,
2522                                                  sstate->normal->dot_atmostone,
2523                                                  i, j, dd)) {
2524                             diff = min(diff, DIFF_NORMAL);
2525                         }
2526                     }
2527                 }
2528                 break;
2529             case 3:
2530 #if 0
2531                 fprintf(stderr, "clue [%d,%d] is 3, doing dline ops\n",
2532                                 i, j);
2533 #endif
2534                 FORALL_SQUARE_DLINES(dd) {
2535                     /* At least one of any DLINE must be set */
2536                     if (set_square_dline(state,
2537                                          sstate->normal->dot_atleastone,
2538                                          i, j, dd)) {
2539                         diff = min(diff, DIFF_NORMAL);
2540                     }
2541
2542                     if (get_square_dline(state,
2543                                          sstate->normal->dot_atmostone,
2544                                          i, j, dd)) {
2545                         /* This DLINE provides enough NOs to solve the clue */
2546                         if (square_setboth_in_dline(sstate, OPP_DLINE(dd),
2547                                                     i, j, LINE_YES)) {
2548                             diff = min(diff, DIFF_EASY);
2549                         }
2550                     }
2551                 }
2552                 break;
2553         }
2554     }
2555
2556     check_caches(sstate);
2557
2558     if (diff < DIFF_NORMAL)
2559         return diff;
2560
2561     FORALL_DOTS(state, i, j) {
2562         if (sstate->dot_solved[DOT_INDEX(state, i, j)])
2563             continue;
2564
2565 #if 0
2566         text = game_text_format(state);
2567         fprintf(stderr, "-----------------\n%s", text);
2568         sfree(text);
2569 #endif
2570
2571         switch (DOT_YES_COUNT(sstate, i, j)) {
2572         case 0:
2573             switch (DOT_NO_COUNT(sstate, i, j)) {
2574                 case 1:
2575                     /* Make note that at most one of each unknown DLINE
2576                      * is YES */
2577                     break;
2578             }
2579             break;
2580
2581         case 1:
2582             switch (DOT_NO_COUNT(sstate, i, j)) {
2583                 case 1:
2584                     /* 1 yes, 1 no, so exactly one of unknowns is
2585                      * yes */
2586 #if 0
2587                     fprintf(stderr, "dot [%d,%d]: 1 yes, 1 no\n", i, j);
2588 #endif
2589                     FORALL_DOT_DLINES(dd) {
2590                         if (dline_both_unknown(state,
2591                                                i, j, dd)) {
2592                             if (set_dot_dline(state,
2593                                               sstate->normal->dot_atleastone,
2594                                               i, j, dd)) {
2595                                 diff = min(diff, DIFF_NORMAL);
2596                             }
2597                         }
2598                     }
2599
2600                     /* fall through */
2601                 case 0:
2602 #if 0
2603                     fprintf(stderr, "dot [%d,%d]: 1 yes, 0 or 1 no\n", i, j);
2604 #endif
2605                     /* 1 yes, fewer than 2 no, so at most one of
2606                      * unknowns is yes */
2607                     FORALL_DOT_DLINES(dd) {
2608                         if (dline_both_unknown(state,
2609                                                i, j, dd)) {
2610                             if (set_dot_dline(state,
2611                                               sstate->normal->dot_atmostone,
2612                                               i, j, dd)) {
2613                                 diff = min(diff, DIFF_NORMAL);
2614                             }
2615                         }
2616                     }
2617                     break;
2618             }
2619             break;
2620         }
2621
2622         /* DLINE deductions that don't depend on the exact number of
2623          * LINE_YESs or LINE_NOs */
2624
2625         /* If at least one of a dline in a dot is YES, at most one
2626          * of the opposite dline to that dot must be YES. */
2627         FORALL_DOT_DLINES(dd) {
2628             if (get_dot_dline(state,
2629                               sstate->normal->dot_atleastone,
2630                               i, j, dd)) {
2631                 if (set_dot_opp_dline(state,
2632                                       sstate->normal->dot_atmostone,
2633                                       i, j, dd)) {
2634                     diff = min(diff, DIFF_NORMAL);
2635                 }
2636             }
2637         }
2638
2639         if (dot_collapse_dlines(sstate, i, j))
2640             diff = min(diff, DIFF_EASY);
2641     }
2642     check_caches(sstate);
2643
2644     return diff;
2645 }
2646
2647 static int hard_mode_deductions(solver_state *sstate)
2648 {
2649     int i, j, a, b, s;
2650     game_state *state = sstate->state;
2651     const int h=state->h, w=state->w;
2652     enum direction dir1, dir2;
2653     int can1, can2, inv1, inv2;
2654     int diff = DIFF_MAX;
2655     enum dline_desc dd;
2656
2657     FORALL_SQUARES(state, i, j) {
2658         if (sstate->square_solved[SQUARE_INDEX(state, i, j)])
2659             continue;
2660
2661         switch (CLUE_AT(state, i, j)) {
2662             case -1:
2663                 continue;
2664
2665             case 1:
2666                 if (square_setall_identical(sstate, i, j, LINE_NO))
2667                     diff = min(diff, DIFF_EASY);
2668                 break;
2669             case 3:
2670                 if (square_setall_identical(sstate, i, j, LINE_YES))
2671                     diff = min(diff, DIFF_EASY);
2672                 break;
2673         }
2674
2675         if (SQUARE_YES_COUNT(sstate, i, j) +
2676             SQUARE_NO_COUNT(sstate, i, j) == 2) {
2677             /* There are exactly two unknown lines bordering this
2678              * square. */
2679             if (SQUARE_YES_COUNT(sstate, i, j) + 1 ==
2680                 CLUE_AT(state, i, j)) {
2681                 /* They must be different */
2682                 if (square_relate_2_unknowns(sstate, i, j, TRUE))
2683                     diff = min(diff, DIFF_HARD);
2684             }
2685         }
2686     }
2687
2688     check_caches(sstate);
2689
2690     FORALL_DOTS(state, i, j) {
2691         if (DOT_YES_COUNT(sstate, i, j) == 1 &&
2692             DOT_NO_COUNT(sstate, i, j) == 1) {
2693             if (dot_relate_2_unknowns(sstate, i, j, TRUE))
2694                 diff = min(diff, DIFF_HARD);
2695             continue;
2696         }
2697
2698         if (DOT_YES_COUNT(sstate, i, j) == 0 &&
2699             DOT_NO_COUNT(sstate, i, j) == 2) {
2700             if (dot_relate_2_unknowns(sstate, i, j, FALSE))
2701                 diff = min(diff, DIFF_HARD);
2702             continue;
2703         }
2704     }
2705
2706     /* If two lines into a dot are related, the other two lines into that dot
2707      * are related in the same way. */
2708
2709     /* iter over points that aren't on edges */
2710     for (i = 1; i < w; ++i) {
2711         for (j = 1; j < h; ++j) {
2712             if (sstate->dot_solved[DOT_INDEX(state, i, j)])
2713                 continue;
2714
2715             /* iter over directions */
2716             for (dir1 = 0; dir1 < 4; ++dir1) {
2717                 for (dir2 = dir1+1; dir2 < 4; ++dir2) {
2718                     /* canonify both lines */
2719                     can1 = edsf_canonify
2720                         (sstate->hard->linedsf,
2721                          LINEDSF_INDEX(state, i, j, dir1),
2722                          &inv1);
2723                     can2 = edsf_canonify
2724                         (sstate->hard->linedsf,
2725                          LINEDSF_INDEX(state, i, j, dir2),
2726                          &inv2);
2727                     /* merge opposite lines */
2728                     if (can1 == can2) {
2729                         if (merge_lines(sstate,
2730                                         i, j, OPP_DIR(dir1),
2731                                         i, j, OPP_DIR(dir2),
2732                                         inv1 ^ inv2)) {
2733                             diff = min(diff, DIFF_HARD);
2734                         }
2735                     }
2736                 }
2737             }
2738         }
2739     }
2740
2741     /* If the state of a line is known, deduce the state of its canonical line
2742      * too. */
2743     FORALL_DOTS(state, i, j) {
2744         /* Do this even if the dot we're on is solved */
2745         if (i < w) {
2746             can1 = edsf_canonify(sstate->hard->linedsf,
2747                                  LINEDSF_INDEX(state, i, j, RIGHT),
2748                                  &inv1);
2749             linedsf_deindex(state, can1, &a, &b, &dir1);
2750             s = RIGHTOF_DOT(state, i, j);
2751             if (s != LINE_UNKNOWN)
2752             {
2753                 if (set_line_bydot(sstate, a, b, dir1, inv1 ? OPP(s) : s))
2754                     diff = min(diff, DIFF_EASY);
2755             }
2756         }
2757         if (j < h) {
2758             can1 = edsf_canonify(sstate->hard->linedsf,
2759                                  LINEDSF_INDEX(state, i, j, DOWN),
2760                                  &inv1);
2761             linedsf_deindex(state, can1, &a, &b, &dir1);
2762             s = BELOW_DOT(state, i, j);
2763             if (s != LINE_UNKNOWN)
2764             {
2765                 if (set_line_bydot(sstate, a, b, dir1, inv1 ? OPP(s) : s))
2766                     diff = min(diff, DIFF_EASY);
2767             }
2768         }
2769     }
2770
2771     /* Interactions between dline and linedsf */
2772     FORALL_DOTS(state, i, j) {
2773         if (sstate->dot_solved[DOT_INDEX(state, i, j)])
2774             continue;
2775
2776         FORALL_DOT_DLINES(dd) {
2777             const struct dline dll = dlines[dd], *dl = &dll;
2778             if (i == 0 && (dl->dir1 == LEFT || dl->dir2 == LEFT))
2779                 continue;
2780             if (i == w && (dl->dir1 == RIGHT || dl->dir2 == RIGHT))
2781                 continue;
2782             if (j == 0 && (dl->dir1 == UP || dl->dir2 == UP))
2783                 continue;
2784             if (j == h && (dl->dir1 == DOWN || dl->dir2 == DOWN))
2785                 continue;
2786
2787             if (get_dot_dline(state, sstate->normal->dot_atleastone,
2788                               i, j, dd) &&
2789                 get_dot_dline(state, sstate->normal->dot_atmostone,
2790                               i, j, dd)) {
2791                 /* atleastone && atmostone => inverse */
2792                 if (merge_lines(sstate, i, j, dl->dir1, i, j, dl->dir2, 1)) {
2793                     diff = min(diff, DIFF_HARD);
2794                 }
2795             } else {
2796                 /* don't have atleastone and atmostone for this dline */
2797                 can1 = edsf_canonify(sstate->hard->linedsf,
2798                                      LINEDSF_INDEX(state, i, j, dl->dir1),
2799                                      &inv1);
2800                 can2 = edsf_canonify(sstate->hard->linedsf,
2801                                      LINEDSF_INDEX(state, i, j, dl->dir2),
2802                                      &inv2);
2803                 if (can1 == can2) {
2804                     if (inv1 == inv2) {
2805                         /* identical => collapse dline */
2806                         if (get_dot_dline(state,
2807                                           sstate->normal->dot_atleastone,
2808                                           i, j, dd)) {
2809                             if (set_line_bydot(sstate, i, j,
2810                                                dl->dir1, LINE_YES)) {
2811                                 diff = min(diff, DIFF_EASY);
2812                             }
2813                             if (set_line_bydot(sstate, i, j,
2814                                                dl->dir2, LINE_YES)) {
2815                                 diff = min(diff, DIFF_EASY);
2816                             }
2817                         } else if (get_dot_dline(state,
2818                                                  sstate->normal->dot_atmostone,
2819                                                  i, j, dd)) {
2820                             if (set_line_bydot(sstate, i, j,
2821                                                dl->dir1, LINE_NO)) {
2822                                 diff = min(diff, DIFF_EASY);
2823                             }
2824                             if (set_line_bydot(sstate, i, j,
2825                                                dl->dir2, LINE_NO)) {
2826                                 diff = min(diff, DIFF_EASY);
2827                             }
2828                         }
2829                     } else {
2830                         /* inverse => atleastone && atmostone */
2831                         if (set_dot_dline(state,
2832                                           sstate->normal->dot_atleastone,
2833                                           i, j, dd)) {
2834                             diff = min(diff, DIFF_NORMAL);
2835                         }
2836                         if (set_dot_dline(state,
2837                                           sstate->normal->dot_atmostone,
2838                                           i, j, dd)) {
2839                             diff = min(diff, DIFF_NORMAL);
2840                         }
2841                     }
2842                 }
2843             }
2844         }
2845     }
2846
2847     /* If the state of the canonical line for line 'l' is known, deduce the
2848      * state of 'l' */
2849     FORALL_DOTS(state, i, j) {
2850         if (sstate->dot_solved[DOT_INDEX(state, i, j)])
2851             continue;
2852
2853         if (i < w) {
2854             can1 = edsf_canonify(sstate->hard->linedsf,
2855                                  LINEDSF_INDEX(state, i, j, RIGHT),
2856                                  &inv1);
2857             linedsf_deindex(state, can1, &a, &b, &dir1);
2858             s = get_line_status_from_point(state, a, b, dir1);
2859             if (s != LINE_UNKNOWN)
2860             {
2861                 if (set_line_bydot(sstate, i, j, RIGHT, inv1 ? OPP(s) : s))
2862                     diff = min(diff, DIFF_EASY);
2863             }
2864         }
2865         if (j < h) {
2866             can1 = edsf_canonify(sstate->hard->linedsf,
2867                                  LINEDSF_INDEX(state, i, j, DOWN),
2868                                  &inv1);
2869             linedsf_deindex(state, can1, &a, &b, &dir1);
2870             s = get_line_status_from_point(state, a, b, dir1);
2871             if (s != LINE_UNKNOWN)
2872             {
2873                 if (set_line_bydot(sstate, i, j, DOWN, inv1 ? OPP(s) : s))
2874                     diff = min(diff, DIFF_EASY);
2875             }
2876         }
2877     }
2878
2879     return diff;
2880 }
2881
2882 static int loop_deductions(solver_state *sstate)
2883 {
2884     int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0;
2885     game_state *state = sstate->state;
2886     int shortest_chainlen = DOT_COUNT(state);
2887     int loop_found = FALSE;
2888     int d;
2889     int dots_connected;
2890     int progress = FALSE;
2891     int i, j;
2892
2893     /*
2894      * Go through the grid and update for all the new edges.
2895      * Since merge_dots() is idempotent, the simplest way to
2896      * do this is just to update for _all_ the edges.
2897      *
2898      * Also, while we're here, we count the edges, count the
2899      * clues, count the satisfied clues, and count the
2900      * satisfied-minus-one clues.
2901      */
2902     FORALL_DOTS(state, i, j) {
2903         if (RIGHTOF_DOT(state, i, j) == LINE_YES) {
2904             loop_found |= merge_dots(sstate, i, j, i+1, j);
2905             edgecount++;
2906         }
2907         if (BELOW_DOT(state, i, j) == LINE_YES) {
2908             loop_found |= merge_dots(sstate, i, j, i, j+1);
2909             edgecount++;
2910         }
2911
2912         if (CLUE_AT(state, i, j) >= 0) {
2913             int c = CLUE_AT(state, i, j);
2914             int o = SQUARE_YES_COUNT(sstate, i, j);
2915             if (o == c)
2916                 satclues++;
2917             else if (o == c-1)
2918                 sm1clues++;
2919             clues++;
2920         }
2921     }
2922
2923     for (i = 0; i < DOT_COUNT(state); ++i) {
2924         dots_connected =
2925             sstate->looplen[dsf_canonify(sstate->dotdsf, i)];
2926         if (dots_connected > 1)
2927             shortest_chainlen = min(shortest_chainlen, dots_connected);
2928     }
2929
2930     assert(sstate->solver_status == SOLVER_INCOMPLETE);
2931
2932     if (satclues == clues && shortest_chainlen == edgecount) {
2933         sstate->solver_status = SOLVER_SOLVED;
2934         /* This discovery clearly counts as progress, even if we haven't
2935          * just added any lines or anything */
2936         progress = TRUE;
2937         goto finished_loop_deductionsing;
2938     }
2939
2940     /*
2941      * Now go through looking for LINE_UNKNOWN edges which
2942      * connect two dots that are already in the same
2943      * equivalence class. If we find one, test to see if the
2944      * loop it would create is a solution.
2945      */
2946     FORALL_DOTS(state, i, j) {
2947         for (d = 0; d < 2; d++) {
2948             int i2, j2, eqclass, val;
2949
2950             if (d == 0) {
2951                 if (RIGHTOF_DOT(state, i, j) !=
2952                         LINE_UNKNOWN)
2953                     continue;
2954                 i2 = i+1;
2955                 j2 = j;
2956             } else {
2957                 if (BELOW_DOT(state, i, j) !=
2958                     LINE_UNKNOWN) {
2959                     continue;
2960                 }
2961                 i2 = i;
2962                 j2 = j+1;
2963             }
2964
2965             eqclass = dsf_canonify(sstate->dotdsf, j * (state->w+1) + i);
2966             if (eqclass != dsf_canonify(sstate->dotdsf,
2967                                         j2 * (state->w+1) + i2)) {
2968                 continue;
2969             }
2970
2971             val = LINE_NO;  /* loop is bad until proven otherwise */
2972
2973             /*
2974              * This edge would form a loop. Next
2975              * question: how long would the loop be?
2976              * Would it equal the total number of edges
2977              * (plus the one we'd be adding if we added
2978              * it)?
2979              */
2980             if (sstate->looplen[eqclass] == edgecount + 1) {
2981                 int sm1_nearby;
2982                 int cx, cy;
2983
2984                 /*
2985                  * This edge would form a loop which
2986                  * took in all the edges in the entire
2987                  * grid. So now we need to work out
2988                  * whether it would be a valid solution
2989                  * to the puzzle, which means we have to
2990                  * check if it satisfies all the clues.
2991                  * This means that every clue must be
2992                  * either satisfied or satisfied-minus-
2993                  * 1, and also that the number of
2994                  * satisfied-minus-1 clues must be at
2995                  * most two and they must lie on either
2996                  * side of this edge.
2997                  */
2998                 sm1_nearby = 0;
2999                 cx = i - (j2-j);
3000                 cy = j - (i2-i);
3001                 if (CLUE_AT(state, cx,cy) >= 0 &&
3002                         square_order(state, cx,cy, LINE_YES) ==
3003                         CLUE_AT(state, cx,cy) - 1) {
3004                     sm1_nearby++;
3005                 }
3006                 if (CLUE_AT(state, i, j) >= 0 &&
3007                         SQUARE_YES_COUNT(sstate, i, j) ==
3008                         CLUE_AT(state, i, j) - 1) {
3009                     sm1_nearby++;
3010                 }
3011                 if (sm1clues == sm1_nearby &&
3012                     sm1clues + satclues == clues) {
3013                     val = LINE_YES;  /* loop is good! */
3014                 }
3015             }
3016
3017             /*
3018              * Right. Now we know that adding this edge
3019              * would form a loop, and we know whether
3020              * that loop would be a viable solution or
3021              * not.
3022              *
3023              * If adding this edge produces a solution,
3024              * then we know we've found _a_ solution but
3025              * we don't know that it's _the_ solution -
3026              * if it were provably the solution then
3027              * we'd have deduced this edge some time ago
3028              * without the need to do loop detection. So
3029              * in this state we return SOLVER_AMBIGUOUS,
3030              * which has the effect that hitting Solve
3031              * on a user-provided puzzle will fill in a
3032              * solution but using the solver to
3033              * construct new puzzles won't consider this
3034              * a reasonable deduction for the user to
3035              * make.
3036              */
3037             if (d == 0) {
3038                 progress = set_line_bydot(sstate, i, j, RIGHT, val);
3039                 assert(progress == TRUE);
3040             } else {
3041                 progress = set_line_bydot(sstate, i, j, DOWN, val);
3042                 assert(progress == TRUE);
3043             }
3044             if (val == LINE_YES) {
3045                 sstate->solver_status = SOLVER_AMBIGUOUS;
3046                 goto finished_loop_deductionsing;
3047             }
3048         }
3049     }
3050
3051 finished_loop_deductionsing:
3052     return progress ? DIFF_EASY : DIFF_MAX;
3053 }
3054
3055 /* This will return a dynamically allocated solver_state containing the (more)
3056  * solved grid */
3057 static solver_state *solve_game_rec(const solver_state *sstate_start,
3058                                     int diff)
3059 {
3060     int i, j;
3061     int w, h;
3062     solver_state *sstate, *sstate_saved, *sstate_tmp;
3063     solver_state *sstate_rec_solved;
3064     int recursive_soln_count;
3065     int solver_progress;
3066     game_state *state;
3067
3068     /* Indicates which solver we should call next.  This is a sensible starting
3069      * point */
3070     int current_solver = DIFF_EASY, next_solver;
3071 #ifdef SHOW_WORKING
3072     char *text;
3073 #endif
3074
3075 #if 0
3076     printf("solve_game_rec: recursion_remaining = %d\n",
3077            sstate_start->recursion_remaining);
3078 #endif
3079
3080     sstate = dup_solver_state(sstate_start);
3081
3082     /* Cache the values of some variables for readability */
3083     state = sstate->state;
3084     h = state->h;
3085     w = state->w;
3086
3087     sstate_saved = NULL;
3088
3089 nonrecursive_solver:
3090     solver_progress = FALSE;
3091
3092     check_caches(sstate);
3093
3094     do {
3095 #ifdef SHOW_WORKING
3096         text = game_text_format(state);
3097         fprintf(stderr, "-----------------\n%s", text);
3098         sfree(text);
3099 #endif
3100
3101         if (sstate->solver_status == SOLVER_MISTAKE)
3102             return sstate;
3103
3104 /*        fprintf(stderr, "Invoking solver %d\n", current_solver); */
3105         next_solver = solver_fns[current_solver](sstate);
3106
3107         if (next_solver == DIFF_MAX) {
3108 /*            fprintf(stderr, "Current solver failed\n"); */
3109             if (current_solver < diff && current_solver + 1 < DIFF_MAX) {
3110                 /* Try next beefier solver */
3111                 next_solver = current_solver + 1;
3112             } else {
3113 /*                fprintf(stderr, "Doing loop deductions\n"); */
3114                 next_solver = loop_deductions(sstate);
3115             }
3116         }
3117
3118         if (sstate->solver_status == SOLVER_SOLVED ||
3119             sstate->solver_status == SOLVER_AMBIGUOUS) {
3120 /*            fprintf(stderr, "Solver completed\n"); */
3121             break;
3122         }
3123
3124         /* Once we've looped over all permitted solvers then the loop
3125          * deductions without making any progress, we'll exit this while loop */
3126         current_solver = next_solver;
3127     } while (current_solver < DIFF_MAX);
3128
3129     if (sstate->solver_status == SOLVER_SOLVED ||
3130         sstate->solver_status == SOLVER_AMBIGUOUS) {
3131         /* s/LINE_UNKNOWN/LINE_NO/g */
3132         array_setall(sstate->state->hl, LINE_UNKNOWN, LINE_NO,
3133                      HL_COUNT(sstate->state));
3134         array_setall(sstate->state->vl, LINE_UNKNOWN, LINE_NO,
3135                      VL_COUNT(sstate->state));
3136         return sstate;
3137     }
3138
3139     /* Perform recursive calls */
3140     if (sstate->recursion_remaining) {
3141         sstate_saved = dup_solver_state(sstate);
3142
3143         sstate->recursion_remaining--;
3144
3145         recursive_soln_count = 0;
3146         sstate_rec_solved = NULL;
3147
3148         /* Memory management:
3149          * sstate_saved won't be modified but needs to be freed when we have
3150          * finished with it.
3151          * sstate is expected to contain our 'best' solution by the time we
3152          * finish this section of code.  It's the thing we'll try adding lines
3153          * to, seeing if they make it more solvable.
3154          * If sstate_rec_solved is non-NULL, it will supersede sstate
3155          * eventually.  sstate_tmp should not hold a value persistently.
3156          */
3157
3158         /* NB SOLVER_AMBIGUOUS is like SOLVER_SOLVED except the solver is aware
3159          * of the possibility of additional solutions.  So as soon as we have a
3160          * SOLVER_AMBIGUOUS we can safely propagate it back to our caller, but
3161          * if we get a SOLVER_SOLVED we want to keep trying in case we find
3162          * further solutions and have to mark it ambiguous.
3163          */
3164
3165 #define DO_RECURSIVE_CALL(dir_dot) \
3166     if (dir_dot(sstate->state, i, j) == LINE_UNKNOWN) { \
3167         debug(("Trying " #dir_dot " at [%d,%d]\n", i, j)); \
3168         LV_##dir_dot(sstate->state, i, j) = LINE_YES; \
3169         sstate_tmp = solve_game_rec(sstate, diff); \
3170         switch (sstate_tmp->solver_status) { \
3171             case SOLVER_AMBIGUOUS: \
3172                 debug(("Solver ambiguous, returning\n")); \
3173                 sstate_rec_solved = sstate_tmp; \
3174                 goto finished_recursion; \
3175             case SOLVER_SOLVED: \
3176                 switch (++recursive_soln_count) { \
3177                     case 1: \
3178                         debug(("One solution found\n")); \
3179                         sstate_rec_solved = sstate_tmp; \
3180                         break; \
3181                     case 2: \
3182                         debug(("Ambiguous solutions found\n")); \
3183                         free_solver_state(sstate_tmp); \
3184                         sstate_rec_solved->solver_status = SOLVER_AMBIGUOUS; \
3185                         goto finished_recursion; \
3186                     default: \
3187                         assert(!"recursive_soln_count out of range"); \
3188                         break; \
3189                 } \
3190                 break; \
3191             case SOLVER_MISTAKE: \
3192                 debug(("Non-solution found\n")); \
3193                 free_solver_state(sstate_tmp); \
3194                 free_solver_state(sstate_saved); \
3195                 LV_##dir_dot(sstate->state, i, j) = LINE_NO; \
3196                 goto nonrecursive_solver; \
3197             case SOLVER_INCOMPLETE: \
3198                 debug(("Recursive step inconclusive\n")); \
3199                 free_solver_state(sstate_tmp); \
3200                 break; \
3201         } \
3202         free_solver_state(sstate); \
3203         sstate = dup_solver_state(sstate_saved); \
3204     }
3205
3206        FORALL_DOTS(state, i, j) {
3207            /* Only perform recursive calls on 'loose ends' */
3208            if (DOT_YES_COUNT(sstate, i, j) == 1) {
3209                DO_RECURSIVE_CALL(LEFTOF_DOT);
3210                DO_RECURSIVE_CALL(RIGHTOF_DOT);
3211                DO_RECURSIVE_CALL(ABOVE_DOT);
3212                DO_RECURSIVE_CALL(BELOW_DOT);
3213            }
3214        }
3215
3216 finished_recursion:
3217
3218        if (sstate_rec_solved) {
3219            free_solver_state(sstate);
3220            sstate = sstate_rec_solved;
3221        }
3222     }
3223
3224     return sstate;
3225 }
3226
3227 #if 0
3228 #define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
3229                if (sstate->normal->dot_atmostone[i+a + (sstate->state->w + 1) * (j+b)] & \
3230                    1<<dline) { \
3231                    if (square_order(sstate->state, i, j,  LINE_UNKNOWN) - 1 == \
3232                        CLUE_AT(sstate->state, i, j) - '0') { \
3233                        square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES); \
3234                            /* XXX the following may overwrite known data! */ \
3235                        dir1_sq(sstate->state, i, j) = LINE_UNKNOWN; \
3236                        dir2_sq(sstate->state, i, j) = LINE_UNKNOWN; \
3237                    } \
3238                }
3239                SQUARE_DLINES;
3240 #undef HANDLE_DLINE
3241 #endif
3242
3243 static char *solve_game(game_state *state, game_state *currstate,
3244                         char *aux, char **error)
3245 {
3246     char *soln = NULL;
3247     solver_state *sstate, *new_sstate;
3248
3249     sstate = new_solver_state(state, DIFF_MAX);
3250     new_sstate = solve_game_rec(sstate, DIFF_MAX);
3251
3252     if (new_sstate->solver_status == SOLVER_SOLVED) {
3253         soln = encode_solve_move(new_sstate->state);
3254     } else if (new_sstate->solver_status == SOLVER_AMBIGUOUS) {
3255         soln = encode_solve_move(new_sstate->state);
3256         /**error = "Solver found ambiguous solutions"; */
3257     } else {
3258         soln = encode_solve_move(new_sstate->state);
3259         /**error = "Solver failed"; */
3260     }
3261
3262     free_solver_state(new_sstate);
3263     free_solver_state(sstate);
3264
3265     return soln;
3266 }
3267
3268 /* ----------------------------------------------------------------------
3269  * Drawing and mouse-handling
3270  */
3271
3272 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
3273                             int x, int y, int button)
3274 {
3275     int hl_selected;
3276     int i, j, p, q;
3277     char *ret, buf[80];
3278     char button_char = ' ';
3279     enum line_state old_state;
3280
3281     button &= ~MOD_MASK;
3282
3283     /* Around each line is a diamond-shaped region where points within that
3284      * region are closer to this line than any other.  We assume any click
3285      * within a line's diamond was meant for that line.  It would all be a lot
3286      * simpler if the / and % operators respected modulo arithmetic properly
3287      * for negative numbers. */
3288
3289     x -= BORDER;
3290     y -= BORDER;
3291
3292     /* Get the coordinates of the square the click was in */
3293     i = (x + TILE_SIZE) / TILE_SIZE - 1;
3294     j = (y + TILE_SIZE) / TILE_SIZE - 1;
3295
3296     /* Get the precise position inside square [i,j] */
3297     p = (x + TILE_SIZE) % TILE_SIZE;
3298     q = (y + TILE_SIZE) % TILE_SIZE;
3299
3300     /* After this bit of magic [i,j] will correspond to the point either above
3301      * or to the left of the line selected */
3302     if (p > q) {
3303         if (TILE_SIZE - p > q) {
3304             hl_selected = TRUE;
3305         } else {
3306             hl_selected = FALSE;
3307             ++i;
3308         }
3309     } else {
3310         if (TILE_SIZE - q > p) {
3311             hl_selected = FALSE;
3312         } else {
3313             hl_selected = TRUE;
3314             ++j;
3315         }
3316     }
3317
3318     if (i < 0 || j < 0)
3319         return NULL;
3320
3321     if (hl_selected) {
3322         if (i >= state->w || j >= state->h + 1)
3323             return NULL;
3324     } else {
3325         if (i >= state->w + 1 || j >= state->h)
3326             return NULL;
3327     }
3328
3329     /* I think it's only possible to play this game with mouse clicks, sorry */
3330     /* Maybe will add mouse drag support some time */
3331     if (hl_selected)
3332         old_state = RIGHTOF_DOT(state, i, j);
3333     else
3334         old_state = BELOW_DOT(state, i, j);
3335
3336     switch (button) {
3337         case LEFT_BUTTON:
3338             switch (old_state) {
3339                 case LINE_UNKNOWN:
3340                     button_char = 'y';
3341                     break;
3342                 case LINE_YES:
3343                 case LINE_NO:
3344                     button_char = 'u';
3345                     break;
3346             }
3347             break;
3348         case MIDDLE_BUTTON:
3349             button_char = 'u';
3350             break;
3351         case RIGHT_BUTTON:
3352             switch (old_state) {
3353                 case LINE_UNKNOWN:
3354                     button_char = 'n';
3355                     break;
3356                 case LINE_NO:
3357                 case LINE_YES:
3358                     button_char = 'u';
3359                     break;
3360             }
3361             break;
3362         default:
3363             return NULL;
3364     }
3365
3366
3367     sprintf(buf, "%d,%d%c%c", i, j, (int)(hl_selected ? 'h' : 'v'), (int)button_char);
3368     ret = dupstr(buf);
3369
3370     return ret;
3371 }
3372
3373 static game_state *execute_move(game_state *state, char *move)
3374 {
3375     int i, j;
3376     game_state *newstate = dup_game(state);
3377
3378     if (move[0] == 'S') {
3379         move++;
3380         newstate->cheated = TRUE;
3381     }
3382
3383     while (*move) {
3384         i = atoi(move);
3385         move = strchr(move, ',');
3386         if (!move)
3387             goto fail;
3388         j = atoi(++move);
3389         move += strspn(move, "1234567890");
3390         switch (*(move++)) {
3391             case 'h':
3392                 if (i >= newstate->w || j > newstate->h)
3393                     goto fail;
3394                 switch (*(move++)) {
3395                     case 'y':
3396                         LV_RIGHTOF_DOT(newstate, i, j) = LINE_YES;
3397                         break;
3398                     case 'n':
3399                         LV_RIGHTOF_DOT(newstate, i, j) = LINE_NO;
3400                         break;
3401                     case 'u':
3402                         LV_RIGHTOF_DOT(newstate, i, j) = LINE_UNKNOWN;
3403                         break;
3404                     default:
3405                         goto fail;
3406                 }
3407                 break;
3408             case 'v':
3409                 if (i > newstate->w || j >= newstate->h)
3410                     goto fail;
3411                 switch (*(move++)) {
3412                     case 'y':
3413                         LV_BELOW_DOT(newstate, i, j) = LINE_YES;
3414                         break;
3415                     case 'n':
3416                         LV_BELOW_DOT(newstate, i, j) = LINE_NO;
3417                         break;
3418                     case 'u':
3419                         LV_BELOW_DOT(newstate, i, j) = LINE_UNKNOWN;
3420                         break;
3421                     default:
3422                         goto fail;
3423                 }
3424                 break;
3425             default:
3426                 goto fail;
3427         }
3428     }
3429
3430     /*
3431      * Check for completion.
3432      */
3433     i = 0;                   /* placate optimiser */
3434     for (j = 0; j <= newstate->h; j++) {
3435         for (i = 0; i < newstate->w; i++)
3436             if (LV_RIGHTOF_DOT(newstate, i, j) == LINE_YES)
3437                 break;
3438         if (i < newstate->w)
3439             break;
3440     }
3441     if (j <= newstate->h) {
3442         int prevdir = 'R';
3443         int x = i, y = j;
3444         int looplen, count;
3445
3446         /*
3447          * We've found a horizontal edge at (i,j). Follow it round
3448          * to see if it's part of a loop.
3449          */
3450         looplen = 0;
3451         while (1) {
3452             int order = dot_order(newstate, x, y, LINE_YES);
3453             if (order != 2)
3454                 goto completion_check_done;
3455
3456             if (LEFTOF_DOT(newstate, x, y) == LINE_YES && prevdir != 'L') {
3457                 x--;
3458                 prevdir = 'R';
3459             } else if (RIGHTOF_DOT(newstate, x, y) == LINE_YES &&
3460                        prevdir != 'R') {
3461                 x++;
3462                 prevdir = 'L';
3463             } else if (ABOVE_DOT(newstate, x, y) == LINE_YES &&
3464                        prevdir != 'U') {
3465                 y--;
3466                 prevdir = 'D';
3467             } else if (BELOW_DOT(newstate, x, y) == LINE_YES &&
3468                        prevdir != 'D') {
3469                 y++;
3470                 prevdir = 'U';
3471             } else {
3472                 assert(!"Can't happen");   /* dot_order guarantees success */
3473             }
3474
3475             looplen++;
3476
3477             if (x == i && y == j)
3478                 break;
3479         }
3480
3481         if (x != i || y != j || looplen == 0)
3482             goto completion_check_done;
3483
3484         /*
3485          * We've traced our way round a loop, and we know how many
3486          * line segments were involved. Count _all_ the line
3487          * segments in the grid, to see if the loop includes them
3488          * all.
3489          */
3490         count = 0;
3491         FORALL_DOTS(newstate, i, j) {
3492             count += ((RIGHTOF_DOT(newstate, i, j) == LINE_YES) +
3493                       (BELOW_DOT(newstate, i, j) == LINE_YES));
3494         }
3495         assert(count >= looplen);
3496         if (count != looplen)
3497             goto completion_check_done;
3498
3499         /*
3500          * The grid contains one closed loop and nothing else.
3501          * Check that all the clues are satisfied.
3502          */
3503         FORALL_SQUARES(newstate, i, j) {
3504             if (CLUE_AT(newstate, i, j) >= 0) {
3505                 if (square_order(newstate, i, j, LINE_YES) !=
3506                     CLUE_AT(newstate, i, j)) {
3507                     goto completion_check_done;
3508                 }
3509             }
3510         }
3511
3512         /*
3513          * Completed!
3514          */
3515         newstate->solved = TRUE;
3516     }
3517
3518 completion_check_done:
3519     return newstate;
3520
3521 fail:
3522     free_game(newstate);
3523     return NULL;
3524 }
3525
3526 /* ----------------------------------------------------------------------
3527  * Drawing routines.
3528  */
3529 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
3530                         game_state *state, int dir, game_ui *ui,
3531                         float animtime, float flashtime)
3532 {
3533     int i, j, n;
3534     char c[2];
3535     int line_colour, flash_changed;
3536     int clue_mistake;
3537
3538     if (!ds->started) {
3539         /*
3540          * The initial contents of the window are not guaranteed and
3541          * can vary with front ends. To be on the safe side, all games
3542          * should start by drawing a big background-colour rectangle
3543          * covering the whole window.
3544          */
3545         draw_rect(dr, 0, 0, SIZE(state->w), SIZE(state->h), COL_BACKGROUND);
3546
3547         /* Draw dots */
3548         FORALL_DOTS(state, i, j) {
3549             draw_rect(dr,
3550                       BORDER + i * TILE_SIZE - LINEWIDTH/2,
3551                       BORDER + j * TILE_SIZE - LINEWIDTH/2,
3552                       LINEWIDTH, LINEWIDTH, COL_FOREGROUND);
3553         }
3554
3555         /* Draw clues */
3556         FORALL_SQUARES(state, i, j) {
3557             c[0] = CLUE2CHAR(CLUE_AT(state, i, j));
3558             c[1] = '\0';
3559             draw_text(dr,
3560                       BORDER + i * TILE_SIZE + TILE_SIZE/2,
3561                       BORDER + j * TILE_SIZE + TILE_SIZE/2,
3562                       FONT_VARIABLE, TILE_SIZE/2,
3563                       ALIGN_VCENTRE | ALIGN_HCENTRE, COL_FOREGROUND, c);
3564         }
3565         draw_update(dr, 0, 0,
3566                     state->w * TILE_SIZE + 2*BORDER + 1,
3567                     state->h * TILE_SIZE + 2*BORDER + 1);
3568         ds->started = TRUE;
3569     }
3570
3571     if (flashtime > 0 &&
3572         (flashtime <= FLASH_TIME/3 ||
3573          flashtime >= FLASH_TIME*2/3)) {
3574         flash_changed = !ds->flashing;
3575         ds->flashing = TRUE;
3576         line_colour = COL_HIGHLIGHT;
3577     } else {
3578         flash_changed = ds->flashing;
3579         ds->flashing = FALSE;
3580         line_colour = COL_FOREGROUND;
3581     }
3582
3583 #define CROSS_SIZE (3 * LINEWIDTH / 2)
3584
3585     /* Redraw clue colours if necessary */
3586     FORALL_SQUARES(state, i, j) {
3587         n = CLUE_AT(state, i, j);
3588         if (n < 0)
3589             continue;
3590
3591         assert(n >= 0 && n <= 4);
3592
3593         c[0] = CLUE2CHAR(CLUE_AT(state, i, j));
3594         c[1] = '\0';
3595
3596         clue_mistake = (square_order(state, i, j, LINE_YES) > n ||
3597                         square_order(state, i, j, LINE_NO ) > (4-n));
3598
3599         if (clue_mistake != ds->clue_error[SQUARE_INDEX(state, i, j)]) {
3600             draw_rect(dr,
3601                       BORDER + i * TILE_SIZE + CROSS_SIZE,
3602                       BORDER + j * TILE_SIZE + CROSS_SIZE,
3603                       TILE_SIZE - CROSS_SIZE * 2, TILE_SIZE - CROSS_SIZE * 2,
3604                       COL_BACKGROUND);
3605             draw_text(dr,
3606                       BORDER + i * TILE_SIZE + TILE_SIZE/2,
3607                       BORDER + j * TILE_SIZE + TILE_SIZE/2,
3608                       FONT_VARIABLE, TILE_SIZE/2,
3609                       ALIGN_VCENTRE | ALIGN_HCENTRE,
3610                       clue_mistake ? COL_MISTAKE : COL_FOREGROUND, c);
3611             draw_update(dr, i * TILE_SIZE + BORDER, j * TILE_SIZE + BORDER,
3612                         TILE_SIZE, TILE_SIZE);
3613
3614             ds->clue_error[SQUARE_INDEX(state, i, j)] = clue_mistake;
3615         }
3616     }
3617
3618     /* I've also had a request to colour lines red if they make a non-solution
3619      * loop, or if more than two lines go into any point.  I think that would
3620      * be good some time. */
3621
3622 #define CLEAR_VL(i, j) \
3623     do { \
3624        draw_rect(dr, \
3625                  BORDER + i * TILE_SIZE - CROSS_SIZE, \
3626                  BORDER + j * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, \
3627                  CROSS_SIZE * 2, \
3628                  TILE_SIZE - LINEWIDTH, \
3629                  COL_BACKGROUND); \
3630         draw_update(dr, \
3631                     BORDER + i * TILE_SIZE - CROSS_SIZE, \
3632                     BORDER + j * TILE_SIZE - CROSS_SIZE, \
3633                     CROSS_SIZE*2, \
3634                     TILE_SIZE + CROSS_SIZE*2); \
3635     } while (0)
3636
3637 #define CLEAR_HL(i, j) \
3638     do { \
3639        draw_rect(dr, \
3640                  BORDER + i * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, \
3641                  BORDER + j * TILE_SIZE - CROSS_SIZE, \
3642                  TILE_SIZE - LINEWIDTH, \
3643                  CROSS_SIZE * 2, \
3644                  COL_BACKGROUND); \
3645        draw_update(dr, \
3646                    BORDER + i * TILE_SIZE - CROSS_SIZE, \
3647                    BORDER + j * TILE_SIZE - CROSS_SIZE, \
3648                    TILE_SIZE + CROSS_SIZE*2, \
3649                    CROSS_SIZE*2); \
3650     } while (0)
3651
3652     /* Vertical lines */
3653     FORALL_VL(state, i, j) {
3654         switch (BELOW_DOT(state, i, j)) {
3655             case LINE_UNKNOWN:
3656                 if (ds->vl[VL_INDEX(state, i, j)] != BELOW_DOT(state, i, j)) {
3657                     CLEAR_VL(i, j);
3658                 }
3659                 break;
3660             case LINE_YES:
3661                 if (ds->vl[VL_INDEX(state, i, j)] != BELOW_DOT(state, i, j) ||
3662                     flash_changed) {
3663                     CLEAR_VL(i, j);
3664                     draw_rect(dr,
3665                               BORDER + i * TILE_SIZE - LINEWIDTH/2,
3666                               BORDER + j * TILE_SIZE + LINEWIDTH - LINEWIDTH/2,
3667                               LINEWIDTH, TILE_SIZE - LINEWIDTH,
3668                               line_colour);
3669                 }
3670                 break;
3671             case LINE_NO:
3672                 if (ds->vl[VL_INDEX(state, i, j)] != BELOW_DOT(state, i, j)) {
3673                     CLEAR_VL(i, j);
3674                     draw_line(dr,
3675                               BORDER + i * TILE_SIZE - CROSS_SIZE,
3676                               BORDER + j * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE,
3677                               BORDER + i * TILE_SIZE + CROSS_SIZE - 1,
3678                               BORDER + j * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1,
3679                               COL_FOREGROUND);
3680                     draw_line(dr,
3681                               BORDER + i * TILE_SIZE + CROSS_SIZE - 1,
3682                               BORDER + j * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE,
3683                               BORDER + i * TILE_SIZE - CROSS_SIZE,
3684                               BORDER + j * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1,
3685                               COL_FOREGROUND);
3686                 }
3687                 break;
3688         }
3689         ds->vl[VL_INDEX(state, i, j)] = BELOW_DOT(state, i, j);
3690     }
3691
3692     /* Horizontal lines */
3693     FORALL_HL(state, i, j) {
3694         switch (RIGHTOF_DOT(state, i, j)) {
3695             case LINE_UNKNOWN:
3696                 if (ds->hl[HL_INDEX(state, i, j)] != RIGHTOF_DOT(state, i, j)) {
3697                     CLEAR_HL(i, j);
3698                 }
3699                 break;
3700             case LINE_YES:
3701                 if (ds->hl[HL_INDEX(state, i, j)] != RIGHTOF_DOT(state, i, j) ||
3702                     flash_changed) {
3703                     CLEAR_HL(i, j);
3704                     draw_rect(dr,
3705                               BORDER + i * TILE_SIZE + LINEWIDTH - LINEWIDTH/2,
3706                               BORDER + j * TILE_SIZE - LINEWIDTH/2,
3707                               TILE_SIZE - LINEWIDTH, LINEWIDTH,
3708                               line_colour);
3709                 }
3710                 break;
3711             case LINE_NO:
3712                 if (ds->hl[HL_INDEX(state, i, j)] != RIGHTOF_DOT(state, i, j)) {
3713                     CLEAR_HL(i, j);
3714                     draw_line(dr,
3715                               BORDER + i * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE,
3716                               BORDER + j * TILE_SIZE + CROSS_SIZE - 1,
3717                               BORDER + i * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1,
3718                               BORDER + j * TILE_SIZE - CROSS_SIZE,
3719                               COL_FOREGROUND);
3720                     draw_line(dr,
3721                               BORDER + i * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE,
3722                               BORDER + j * TILE_SIZE - CROSS_SIZE,
3723                               BORDER + i * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1,
3724                               BORDER + j * TILE_SIZE + CROSS_SIZE - 1,
3725                               COL_FOREGROUND);
3726                     break;
3727                 }
3728         }
3729         ds->hl[HL_INDEX(state, i, j)] = RIGHTOF_DOT(state, i, j);
3730     }
3731 }
3732
3733 static float game_flash_length(game_state *oldstate, game_state *newstate,
3734                                int dir, game_ui *ui)
3735 {
3736     if (!oldstate->solved  &&  newstate->solved &&
3737         !oldstate->cheated && !newstate->cheated) {
3738         return FLASH_TIME;
3739     }
3740
3741     return 0.0F;
3742 }
3743
3744 static void game_print_size(game_params *params, float *x, float *y)
3745 {
3746     int pw, ph;
3747
3748     /*
3749      * I'll use 7mm squares by default.
3750      */
3751     game_compute_size(params, 700, &pw, &ph);
3752     *x = pw / 100.0F;
3753     *y = ph / 100.0F;
3754 }
3755
3756 static void game_print(drawing *dr, game_state *state, int tilesize)
3757 {
3758     int ink = print_mono_colour(dr, 0);
3759     int x, y;
3760     game_drawstate ads, *ds = &ads;
3761
3762     game_set_size(dr, ds, NULL, tilesize);
3763
3764     /*
3765      * Dots. I'll deliberately make the dots a bit wider than the
3766      * lines, so you can still see them. (And also because it's
3767      * annoyingly tricky to make them _exactly_ the same size...)
3768      */
3769     FORALL_DOTS(state, x, y) {
3770         draw_circle(dr, BORDER + x * TILE_SIZE, BORDER + y * TILE_SIZE,
3771                     LINEWIDTH, ink, ink);
3772     }
3773
3774     /*
3775      * Clues.
3776      */
3777     FORALL_SQUARES(state, x, y) {
3778         if (CLUE_AT(state, x, y) >= 0) {
3779             char c[2];
3780
3781             c[0] = CLUE2CHAR(CLUE_AT(state, x, y));
3782             c[1] = '\0';
3783             draw_text(dr,
3784                       BORDER + x * TILE_SIZE + TILE_SIZE/2,
3785                       BORDER + y * TILE_SIZE + TILE_SIZE/2,
3786                       FONT_VARIABLE, TILE_SIZE/2,
3787                       ALIGN_VCENTRE | ALIGN_HCENTRE, ink, c);
3788         }
3789     }
3790
3791     /*
3792      * Lines. (At the moment, I'm not bothering with crosses.)
3793      */
3794     FORALL_HL(state, x, y) {
3795         if (RIGHTOF_DOT(state, x, y) == LINE_YES)
3796         draw_rect(dr, BORDER + x * TILE_SIZE,
3797                   BORDER + y * TILE_SIZE - LINEWIDTH/2,
3798                   TILE_SIZE, (LINEWIDTH/2) * 2 + 1, ink);
3799     }
3800
3801     FORALL_VL(state, x, y) {
3802         if (BELOW_DOT(state, x, y) == LINE_YES)
3803         draw_rect(dr, BORDER + x * TILE_SIZE - LINEWIDTH/2,
3804                   BORDER + y * TILE_SIZE,
3805                   (LINEWIDTH/2) * 2 + 1, TILE_SIZE, ink);
3806     }
3807 }
3808
3809 #ifdef COMBINED
3810 #define thegame loopy
3811 #endif
3812
3813 const struct game thegame = {
3814     "Loopy", "games.loopy", "loopy",
3815     default_params,
3816     game_fetch_preset,
3817     decode_params,
3818     encode_params,
3819     free_params,
3820     dup_params,
3821     TRUE, game_configure, custom_params,
3822     validate_params,
3823     new_game_desc,
3824     validate_desc,
3825     new_game,
3826     dup_game,
3827     free_game,
3828     1, solve_game,
3829     TRUE, game_can_format_as_text_now, game_text_format,
3830     new_ui,
3831     free_ui,
3832     encode_ui,
3833     decode_ui,
3834     game_changed_state,
3835     interpret_move,
3836     execute_move,
3837     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3838     game_colours,
3839     game_new_drawstate,
3840     game_free_drawstate,
3841     game_redraw,
3842     game_anim_length,
3843     game_flash_length,
3844     TRUE, FALSE, game_print_size, game_print,
3845     FALSE /* wants_statusbar */,
3846     FALSE, game_timing_state,
3847     0,                                       /* mouse_priorities */
3848 };