lightup.c

   1 /*
   2  * lightup.c: Implementation of the Nikoli game 'Light Up'.
   3  *
   4  * Possible future solver enhancements:
   5  *
   6  *  - In a situation where two clues are diagonally adjacent, you can
   7  *    deduce bounds on the number of lights shared between them. For
   8  *    instance, suppose a 3 clue is diagonally adjacent to a 1 clue:
   9  *    of the two squares adjacent to both clues, at least one must be
  10  *    a light (or the 3 would be unsatisfiable) and yet at most one
  11  *    must be a light (or the 1 would be overcommitted), so in fact
  12  *    _exactly_ one must be a light, and hence the other two squares
  13  *    adjacent to the 3 must also be lights and the other two adjacent
  14  *    to the 1 must not. Likewise if the 3 is replaced with a 2 but
  15  *    one of its other two squares is known not to be a light, and so
  16  *    on.
  17  *
  18  *  - In a situation where two clues are orthogonally separated (not
  19  *    necessarily directly adjacent), you may be able to deduce
  20  *    something about the squares that align with each other. For
  21  *    instance, suppose two clues are vertically adjacent. Consider
  22  *    the pair of squares A,B horizontally adjacent to the top clue,
  23  *    and the pair C,D horizontally adjacent to the bottom clue.
  24  *    Assuming no intervening obstacles, A and C align with each other
  25  *    and hence at most one of them can be a light, and B and D
  26  *    likewise, so we must have at most two lights between the four
  27  *    squares. So if the clues indicate that there are at _least_ two
  28  *    lights in those four squares because the top clue requires at
  29  *    least one of AB to be a light and the bottom one requires at
  30  *    least one of CD, then we can in fact deduce that there are
  31  *    _exactly_ two lights between the four squares, and fill in the
  32  *    other squares adjacent to each clue accordingly. For instance,
  33  *    if both clues are 3s, then we instantly deduce that all four of
  34  *    the squares _vertically_ adjacent to the two clues must be
  35  *    lights. (For that to happen, of course, there'd also have to be
  36  *    a black square in between the clues, so the two inner lights
  37  *    don't light each other.)
  38  *
  39  *  - I haven't thought it through carefully, but there's always the
  40  *    possibility that both of the above deductions are special cases
  41  *    of some more general pattern which can be made computationally
  42  *    feasible...
  43  */
  44
  45 #include <stdio.h>
  46 #include <stdlib.h>
  47 #include <string.h>
  48 #include <assert.h>
  49 #include <ctype.h>
  50 #include <math.h>
  51
  52 #include "puzzles.h"
  53
  54 /*
  55  * In standalone solver mode, `verbose' is a variable which can be
  56  * set by command-line option; in debugging mode it's simply always
  57  * true.
  58  */
  59 #if defined STANDALONE_SOLVER
  60 #define SOLVER_DIAGNOSTICS
  61 int verbose = 0;
  62 #undef debug
  63 #define debug(x) printf x
  64 #elif defined SOLVER_DIAGNOSTICS
  65 #define verbose 2
  66 #endif
  67
  68 /* --- Constants, structure definitions, etc. --- */
  69
  70 #define PREFERRED_TILE_SIZE 32
  71 #define TILE_SIZE       (ds->tilesize)
  72 #define BORDER          (TILE_SIZE / 2)
  73 #define TILE_RADIUS     (ds->crad)
  74
  75 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  76 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  77
  78 #define FLASH_TIME 0.30F
  79
  80 enum {
  81     COL_BACKGROUND,
  82     COL_GRID,
  83     COL_BLACK,                         /* black */
  84     COL_LIGHT,                         /* white */
  85     COL_LIT,                           /* yellow */
  86     COL_ERROR,                         /* red */
  87     COL_CURSOR,
  88     NCOLOURS
  89 };
  90
  91 enum { SYMM_NONE, SYMM_REF2, SYMM_ROT2, SYMM_REF4, SYMM_ROT4, SYMM_MAX };
  92
  93 #define DIFFCOUNT 2
  94
  95 struct game_params {
  96     int w, h;
  97     int blackpc;        /* %age of black squares */
  98     int symm;
  99     int difficulty;     /* 0 to DIFFCOUNT */
 100 };
 101
 102 #define F_BLACK         1
 103
 104 /* flags for black squares */
 105 #define F_NUMBERED      2       /* it has a number attached */
 106 #define F_NUMBERUSED    4       /* this number was useful for solving */
 107
 108 /* flags for non-black squares */
 109 #define F_IMPOSSIBLE    8       /* can't put a light here */
 110 #define F_LIGHT         16
 111
 112 #define F_MARK          32
 113
 114 struct game_state {
 115     int w, h, nlights;
 116     int *lights;        /* For black squares, (optionally) the number
 117                            of surrounding lights. For non-black squares,
 118                            the number of times it's lit. size h*w*/
 119     unsigned int *flags;        /* size h*w */
 120     int completed, used_solve;
 121 };
 122
 123 #define GRID(gs,grid,x,y) (gs->grid[(y)*((gs)->w) + (x)])
 124
 125 /* A ll_data holds information about which lights would be lit by
 126  * a particular grid location's light (or conversely, which locations
 127  * could light a specific other location). */
 128 /* most things should consider this struct opaque. */
 129 typedef struct {
 130     int ox,oy;
 131     int minx, maxx, miny, maxy;
 132     int include_origin;
 133 } ll_data;
 134
 135 /* Macro that executes 'block' once per light in lld, including
 136  * the origin if include_origin is specified. 'block' can use
 137  * lx and ly as the coords. */
 138 #define FOREACHLIT(lld,block) do {                              \
 139   int lx,ly;                                                    \
 140   ly = (lld)->oy;                                               \
 141   for (lx = (lld)->minx; lx <= (lld)->maxx; lx++) {             \
 142     if (lx == (lld)->ox) continue;                              \
 143     block                                                       \
 144   }                                                             \
 145   lx = (lld)->ox;                                               \
 146   for (ly = (lld)->miny; ly <= (lld)->maxy; ly++) {             \
 147     if (!(lld)->include_origin && ly == (lld)->oy) continue;    \
 148     block                                                       \
 149   }                                                             \
 150 } while(0)
 151
 152
 153 typedef struct {
 154     struct { int x, y; unsigned int f; } points[4];
 155     int npoints;
 156 } surrounds;
 157
 158 /* Fills in (doesn't allocate) a surrounds structure with the grid locations
 159  * around a given square, taking account of the edges. */
 160 static void get_surrounds(const game_state *state, int ox, int oy,
 161                           surrounds *s)
 162 {
 163     assert(ox >= 0 && ox < state->w && oy >= 0 && oy < state->h);
 164     s->npoints = 0;
 165 #define ADDPOINT(cond,nx,ny) do {\
 166     if (cond) { \
 167         s->points[s->npoints].x = (nx); \
 168         s->points[s->npoints].y = (ny); \
 169         s->points[s->npoints].f = 0; \
 170         s->npoints++; \
 171     } } while(0)
 172     ADDPOINT(ox > 0,            ox-1, oy);
 173     ADDPOINT(ox < (state->w-1), ox+1, oy);
 174     ADDPOINT(oy > 0,            ox,   oy-1);
 175     ADDPOINT(oy < (state->h-1), ox,   oy+1);
 176 }
 177
 178 /* --- Game parameter functions --- */
 179
 180 #define DEFAULT_PRESET 0
 181
 182 const struct game_params lightup_presets[] = {
 183     { 7, 7, 20, SYMM_ROT4, 0 },
 184     { 7, 7, 20, SYMM_ROT4, 1 },
 185     { 7, 7, 20, SYMM_ROT4, 2 },
 186     { 10, 10, 20, SYMM_ROT2, 0 },
 187     { 10, 10, 20, SYMM_ROT2, 1 },
 188 #ifdef SLOW_SYSTEM
 189     { 12, 12, 20, SYMM_ROT2, 0 },
 190     { 12, 12, 20, SYMM_ROT2, 1 },
 191 #else
 192     { 10, 10, 20, SYMM_ROT2, 2 },
 193     { 14, 14, 20, SYMM_ROT2, 0 },
 194     { 14, 14, 20, SYMM_ROT2, 1 },
 195     { 14, 14, 20, SYMM_ROT2, 2 }
 196 #endif
 197 };
 198
 199 static game_params *default_params(void)
 200 {
 201     game_params *ret = snew(game_params);
 202     *ret = lightup_presets[DEFAULT_PRESET];
 203
 204     return ret;
 205 }
 206
 207 static int game_fetch_preset(int i, char **name, game_params **params)
 208 {
 209     game_params *ret;
 210     char buf[80];
 211
 212     if (i < 0 || i >= lenof(lightup_presets))
 213         return FALSE;
 214
 215     ret = default_params();
 216     *ret = lightup_presets[i];
 217     *params = ret;
 218
 219     sprintf(buf, "%dx%d %s",
 220             ret->w, ret->h,
 221             ret->difficulty == 2 ? "hard" :
 222             ret->difficulty == 1 ? "tricky" : "easy");
 223     *name = dupstr(buf);
 224
 225     return TRUE;
 226 }
 227
 228 static void free_params(game_params *params)
 229 {
 230     sfree(params);
 231 }
 232
 233 static game_params *dup_params(const game_params *params)
 234 {
 235     game_params *ret = snew(game_params);
 236     *ret = *params;                    /* structure copy */
 237     return ret;
 238 }
 239
 240 #define EATNUM(x) do { \
 241     (x) = atoi(string); \
 242     while (*string && isdigit((unsigned char)*string)) string++; \
 243 } while(0)
 244
 245 static void decode_params(game_params *params, char const *string)
 246 {
 247     EATNUM(params->w);
 248     if (*string == 'x') {
 249         string++;
 250         EATNUM(params->h);
 251     }
 252     if (*string == 'b') {
 253         string++;
 254         EATNUM(params->blackpc);
 255     }
 256     if (*string == 's') {
 257         string++;
 258         EATNUM(params->symm);
 259     } else {
 260         /* cope with user input such as '18x10' by ensuring symmetry
 261          * is not selected by default to be incompatible with dimensions */
 262         if (params->symm == SYMM_ROT4 && params->w != params->h)
 263             params->symm = SYMM_ROT2;
 264     }
 265     params->difficulty = 0;
 266     /* cope with old params */
 267     if (*string == 'r') {
 268         params->difficulty = 2;
 269         string++;
 270     }
 271     if (*string == 'd') {
 272         string++;
 273         EATNUM(params->difficulty);
 274     }
 275 }
 276
 277 static char *encode_params(const game_params *params, int full)
 278 {
 279     char buf[80];
 280
 281     if (full) {
 282         sprintf(buf, "%dx%db%ds%dd%d",
 283                 params->w, params->h, params->blackpc,
 284                 params->symm,
 285                 params->difficulty);
 286     } else {
 287         sprintf(buf, "%dx%d", params->w, params->h);
 288     }
 289     return dupstr(buf);
 290 }
 291
 292 static config_item *game_configure(const game_params *params)
 293 {
 294     config_item *ret;
 295     char buf[80];
 296
 297     ret = snewn(6, config_item);
 298
 299     ret[0].name = "Width";
 300     ret[0].type = C_STRING;
 301     sprintf(buf, "%d", params->w);
 302     ret[0].sval = dupstr(buf);
 303     ret[0].ival = 0;
 304
 305     ret[1].name = "Height";
 306     ret[1].type = C_STRING;
 307     sprintf(buf, "%d", params->h);
 308     ret[1].sval = dupstr(buf);
 309     ret[1].ival = 0;
 310
 311     ret[2].name = "%age of black squares";
 312     ret[2].type = C_STRING;
 313     sprintf(buf, "%d", params->blackpc);
 314     ret[2].sval = dupstr(buf);
 315     ret[2].ival = 0;
 316
 317     ret[3].name = "Symmetry";
 318     ret[3].type = C_CHOICES;
 319     ret[3].sval = ":None"
 320                   ":2-way mirror:2-way rotational"
 321                   ":4-way mirror:4-way rotational";
 322     ret[3].ival = params->symm;
 323
 324     ret[4].name = "Difficulty";
 325     ret[4].type = C_CHOICES;
 326     ret[4].sval = ":Easy:Tricky:Hard";
 327     ret[4].ival = params->difficulty;
 328
 329     ret[5].name = NULL;
 330     ret[5].type = C_END;
 331     ret[5].sval = NULL;
 332     ret[5].ival = 0;
 333
 334     return ret;
 335 }
 336
 337 static game_params *custom_params(const config_item *cfg)
 338 {
 339     game_params *ret = snew(game_params);
 340
 341     ret->w =       atoi(cfg[0].sval);
 342     ret->h =       atoi(cfg[1].sval);
 343     ret->blackpc = atoi(cfg[2].sval);
 344     ret->symm =    cfg[3].ival;
 345     ret->difficulty = cfg[4].ival;
 346
 347     return ret;
 348 }
 349
 350 static char *validate_params(const game_params *params, int full)
 351 {
 352     if (params->w < 2 || params->h < 2)
 353         return "Width and height must be at least 2";
 354     if (full) {
 355         if (params->blackpc < 5 || params->blackpc > 100)
 356             return "Percentage of black squares must be between 5% and 100%";
 357         if (params->w != params->h) {
 358             if (params->symm == SYMM_ROT4)
 359                 return "4-fold symmetry is only available with square grids";
 360         }
 361         if (params->symm < 0 || params->symm >= SYMM_MAX)
 362             return "Unknown symmetry type";
 363         if (params->difficulty < 0 || params->difficulty > DIFFCOUNT)
 364             return "Unknown difficulty level";
 365     }
 366     return NULL;
 367 }
 368
 369 /* --- Game state construction/freeing helper functions --- */
 370
 371 static game_state *new_state(const game_params *params)
 372 {
 373     game_state *ret = snew(game_state);
 374
 375     ret->w = params->w;
 376     ret->h = params->h;
 377     ret->lights = snewn(ret->w * ret->h, int);
 378     ret->nlights = 0;
 379     memset(ret->lights, 0, ret->w * ret->h * sizeof(int));
 380     ret->flags = snewn(ret->w * ret->h, unsigned int);
 381     memset(ret->flags, 0, ret->w * ret->h * sizeof(unsigned int));
 382     ret->completed = ret->used_solve = 0;
 383     return ret;
 384 }
 385
 386 static game_state *dup_game(const game_state *state)
 387 {
 388     game_state *ret = snew(game_state);
 389
 390     ret->w = state->w;
 391     ret->h = state->h;
 392
 393     ret->lights = snewn(ret->w * ret->h, int);
 394     memcpy(ret->lights, state->lights, ret->w * ret->h * sizeof(int));
 395     ret->nlights = state->nlights;
 396
 397     ret->flags = snewn(ret->w * ret->h, unsigned int);
 398     memcpy(ret->flags, state->flags, ret->w * ret->h * sizeof(unsigned int));
 399
 400     ret->completed = state->completed;
 401     ret->used_solve = state->used_solve;
 402
 403     return ret;
 404 }
 405
 406 static void free_game(game_state *state)
 407 {
 408     sfree(state->lights);
 409     sfree(state->flags);
 410     sfree(state);
 411 }
 412
 413 static void debug_state(game_state *state)
 414 {
 415     int x, y;
 416     char c = '?';
 417
 418     for (y = 0; y < state->h; y++) {
 419         for (x = 0; x < state->w; x++) {
 420             c = '.';
 421             if (GRID(state, flags, x, y) & F_BLACK) {
 422                 if (GRID(state, flags, x, y) & F_NUMBERED)
 423                     c = GRID(state, lights, x, y) + '0';
 424                 else
 425                     c = '#';
 426             } else {
 427                 if (GRID(state, flags, x, y) & F_LIGHT)
 428                     c = 'O';
 429                 else if (GRID(state, flags, x, y) & F_IMPOSSIBLE)
 430                     c = 'X';
 431             }
 432             debug(("%c", (int)c));
 433         }
 434         debug(("     "));
 435         for (x = 0; x < state->w; x++) {
 436             if (GRID(state, flags, x, y) & F_BLACK)
 437                 c = '#';
 438             else {
 439                 c = (GRID(state, flags, x, y) & F_LIGHT) ? 'A' : 'a';
 440                 c += GRID(state, lights, x, y);
 441             }
 442             debug(("%c", (int)c));
 443         }
 444         debug(("\n"));
 445     }
 446 }
 447
 448 /* --- Game completion test routines. --- */
 449
 450 /* These are split up because occasionally functions are only
 451  * interested in one particular aspect. */
 452
 453 /* Returns non-zero if all grid spaces are lit. */
 454 static int grid_lit(game_state *state)
 455 {
 456     int x, y;
 457
 458     for (x = 0; x < state->w; x++) {
 459         for (y = 0; y < state->h; y++) {
 460             if (GRID(state,flags,x,y) & F_BLACK) continue;
 461             if (GRID(state,lights,x,y) == 0)
 462                 return 0;
 463         }
 464     }
 465     return 1;
 466 }
 467
 468 /* Returns non-zero if any lights are lit by other lights. */
 469 static int grid_overlap(game_state *state)
 470 {
 471     int x, y;
 472
 473     for (x = 0; x < state->w; x++) {
 474         for (y = 0; y < state->h; y++) {
 475             if (!(GRID(state, flags, x, y) & F_LIGHT)) continue;
 476             if (GRID(state, lights, x, y) > 1)
 477                 return 1;
 478         }
 479     }
 480     return 0;
 481 }
 482
 483 static int number_wrong(const game_state *state, int x, int y)
 484 {
 485     surrounds s;
 486     int i, n, empty, lights = GRID(state, lights, x, y);
 487
 488     /*
 489      * This function computes the display hint for a number: we
 490      * turn the number red if it is definitely wrong. This means
 491      * that either
 492      *
 493      *  (a) it has too many lights around it, or
 494      *  (b) it would have too few lights around it even if all the
 495      *      plausible squares (not black, lit or F_IMPOSSIBLE) were
 496      *      filled with lights.
 497      */
 498
 499     assert(GRID(state, flags, x, y) & F_NUMBERED);
 500     get_surrounds(state, x, y, &s);
 501
 502     empty = n = 0;
 503     for (i = 0; i < s.npoints; i++) {
 504         if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT) {
 505             n++;
 506             continue;
 507         }
 508         if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_BLACK)
 509             continue;
 510         if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_IMPOSSIBLE)
 511             continue;
 512         if (GRID(state,lights,s.points[i].x,s.points[i].y))
 513             continue;
 514         empty++;
 515     }
 516     return (n > lights || (n + empty < lights));
 517 }
 518
 519 static int number_correct(game_state *state, int x, int y)
 520 {
 521     surrounds s;
 522     int n = 0, i, lights = GRID(state, lights, x, y);
 523
 524     assert(GRID(state, flags, x, y) & F_NUMBERED);
 525     get_surrounds(state, x, y, &s);
 526     for (i = 0; i < s.npoints; i++) {
 527         if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT)
 528             n++;
 529     }
 530     return (n == lights) ? 1 : 0;
 531 }
 532
 533 /* Returns non-zero if any numbers add up incorrectly. */
 534 static int grid_addsup(game_state *state)
 535 {
 536     int x, y;
 537
 538     for (x = 0; x < state->w; x++) {
 539         for (y = 0; y < state->h; y++) {
 540             if (!(GRID(state, flags, x, y) & F_NUMBERED)) continue;
 541             if (!number_correct(state, x, y)) return 0;
 542         }
 543     }
 544     return 1;
 545 }
 546
 547 static int grid_correct(game_state *state)
 548 {
 549     if (grid_lit(state) &&
 550         !grid_overlap(state) &&
 551         grid_addsup(state)) return 1;
 552     return 0;
 553 }
 554
 555 /* --- Board initial setup (blacks, lights, numbers) --- */
 556
 557 static void clean_board(game_state *state, int leave_blacks)
 558 {
 559     int x,y;
 560     for (x = 0; x < state->w; x++) {
 561         for (y = 0; y < state->h; y++) {
 562             if (leave_blacks)
 563                 GRID(state, flags, x, y) &= F_BLACK;
 564             else
 565                 GRID(state, flags, x, y) = 0;
 566             GRID(state, lights, x, y) = 0;
 567         }
 568     }
 569     state->nlights = 0;
 570 }
 571
 572 static void set_blacks(game_state *state, const game_params *params,
 573                        random_state *rs)
 574 {
 575     int x, y, degree = 0, rotate = 0, nblack;
 576     int rh, rw, i;
 577     int wodd = (state->w % 2) ? 1 : 0;
 578     int hodd = (state->h % 2) ? 1 : 0;
 579     int xs[4], ys[4];
 580
 581     switch (params->symm) {
 582     case SYMM_NONE: degree = 1; rotate = 0; break;
 583     case SYMM_ROT2: degree = 2; rotate = 1; break;
 584     case SYMM_REF2: degree = 2; rotate = 0; break;
 585     case SYMM_ROT4: degree = 4; rotate = 1; break;
 586     case SYMM_REF4: degree = 4; rotate = 0; break;
 587     default: assert(!"Unknown symmetry type");
 588     }
 589     if (params->symm == SYMM_ROT4 && (state->h != state->w))
 590         assert(!"4-fold symmetry unavailable without square grid");
 591
 592     if (degree == 4) {
 593         rw = state->w/2;
 594         rh = state->h/2;
 595         if (!rotate) rw += wodd; /* ... but see below. */
 596         rh += hodd;
 597     } else if (degree == 2) {
 598         rw = state->w;
 599         rh = state->h/2;
 600         rh += hodd;
 601     } else {
 602         rw = state->w;
 603         rh = state->h;
 604     }
 605
 606     /* clear, then randomise, required region. */
 607     clean_board(state, 0);
 608     nblack = (rw * rh * params->blackpc) / 100;
 609     for (i = 0; i < nblack; i++) {
 610         do {
 611             x = random_upto(rs,rw);
 612             y = random_upto(rs,rh);
 613         } while (GRID(state,flags,x,y) & F_BLACK);
 614         GRID(state, flags, x, y) |= F_BLACK;
 615     }
 616
 617     /* Copy required region. */
 618     if (params->symm == SYMM_NONE) return;
 619
 620     for (x = 0; x < rw; x++) {
 621         for (y = 0; y < rh; y++) {
 622             if (degree == 4) {
 623                 xs[0] = x;
 624                 ys[0] = y;
 625                 xs[1] = state->w - 1 - (rotate ? y : x);
 626                 ys[1] = rotate ? x : y;
 627                 xs[2] = rotate ? (state->w - 1 - x) : x;
 628                 ys[2] = state->h - 1 - y;
 629                 xs[3] = rotate ? y : (state->w - 1 - x);
 630                 ys[3] = state->h - 1 - (rotate ? x : y);
 631             } else {
 632                 xs[0] = x;
 633                 ys[0] = y;
 634                 xs[1] = rotate ? (state->w - 1 - x) : x;
 635                 ys[1] = state->h - 1 - y;
 636             }
 637             for (i = 1; i < degree; i++) {
 638                 GRID(state, flags, xs[i], ys[i]) =
 639                     GRID(state, flags, xs[0], ys[0]);
 640             }
 641         }
 642     }
 643     /* SYMM_ROT4 misses the middle square above; fix that here. */
 644     if (degree == 4 && rotate && wodd &&
 645         (random_upto(rs,100) <= (unsigned int)params->blackpc))
 646         GRID(state,flags,
 647              state->w/2 + wodd - 1, state->h/2 + hodd - 1) |= F_BLACK;
 648
 649 #ifdef SOLVER_DIAGNOSTICS
 650     if (verbose) debug_state(state);
 651 #endif
 652 }
 653
 654 /* Fills in (does not allocate) a ll_data with all the tiles that would
 655  * be illuminated by a light at point (ox,oy). If origin=1 then the
 656  * origin is included in this list. */
 657 static void list_lights(game_state *state, int ox, int oy, int origin,
 658                         ll_data *lld)
 659 {
 660     int x,y;
 661
 662     lld->ox = lld->minx = lld->maxx = ox;
 663     lld->oy = lld->miny = lld->maxy = oy;
 664     lld->include_origin = origin;
 665
 666     y = oy;
 667     for (x = ox-1; x >= 0; x--) {
 668         if (GRID(state, flags, x, y) & F_BLACK) break;
 669         if (x < lld->minx) lld->minx = x;
 670     }
 671     for (x = ox+1; x < state->w; x++) {
 672         if (GRID(state, flags, x, y) & F_BLACK) break;
 673         if (x > lld->maxx) lld->maxx = x;
 674     }
 675
 676     x = ox;
 677     for (y = oy-1; y >= 0; y--) {
 678         if (GRID(state, flags, x, y) & F_BLACK) break;
 679         if (y < lld->miny) lld->miny = y;
 680     }
 681     for (y = oy+1; y < state->h; y++) {
 682         if (GRID(state, flags, x, y) & F_BLACK) break;
 683         if (y > lld->maxy) lld->maxy = y;
 684     }
 685 }
 686
 687 /* Makes sure a light is the given state, editing the lights table to suit the
 688  * new state if necessary. */
 689 static void set_light(game_state *state, int ox, int oy, int on)
 690 {
 691     ll_data lld;
 692     int diff = 0;
 693
 694     assert(!(GRID(state,flags,ox,oy) & F_BLACK));
 695
 696     if (!on && GRID(state,flags,ox,oy) & F_LIGHT) {
 697         diff = -1;
 698         GRID(state,flags,ox,oy) &= ~F_LIGHT;
 699         state->nlights--;
 700     } else if (on && !(GRID(state,flags,ox,oy) & F_LIGHT)) {
 701         diff = 1;
 702         GRID(state,flags,ox,oy) |= F_LIGHT;
 703         state->nlights++;
 704     }
 705
 706     if (diff != 0) {
 707         list_lights(state,ox,oy,1,&lld);
 708         FOREACHLIT(&lld, GRID(state,lights,lx,ly) += diff; );
 709     }
 710 }
 711
 712 /* Returns 1 if removing a light at (x,y) would cause a square to go dark. */
 713 static int check_dark(game_state *state, int x, int y)
 714 {
 715     ll_data lld;
 716
 717     list_lights(state, x, y, 1, &lld);
 718     FOREACHLIT(&lld, if (GRID(state,lights,lx,ly) == 1) { return 1; } );
 719     return 0;
 720 }
 721
 722 /* Sets up an initial random correct position (i.e. every
 723  * space lit, and no lights lit by other lights) by filling the
 724  * grid with lights and then removing lights one by one at random. */
 725 static void place_lights(game_state *state, random_state *rs)
 726 {
 727     int i, x, y, n, *numindices, wh = state->w*state->h;
 728     ll_data lld;
 729
 730     numindices = snewn(wh, int);
 731     for (i = 0; i < wh; i++) numindices[i] = i;
 732     shuffle(numindices, wh, sizeof(*numindices), rs);
 733
 734     /* Place a light on all grid squares without lights. */
 735     for (x = 0; x < state->w; x++) {
 736         for (y = 0; y < state->h; y++) {
 737             GRID(state, flags, x, y) &= ~F_MARK; /* we use this later. */
 738             if (GRID(state, flags, x, y) & F_BLACK) continue;
 739             set_light(state, x, y, 1);
 740         }
 741     }
 742
 743     for (i = 0; i < wh; i++) {
 744         y = numindices[i] / state->w;
 745         x = numindices[i] % state->w;
 746         if (!(GRID(state, flags, x, y) & F_LIGHT)) continue;
 747         if (GRID(state, flags, x, y) & F_MARK) continue;
 748         list_lights(state, x, y, 0, &lld);
 749
 750         /* If we're not lighting any lights ourself, don't remove anything. */
 751         n = 0;
 752         FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += 1; } );
 753         if (n == 0) continue; /* [1] */
 754
 755         /* Check whether removing lights we're lighting would cause anything
 756          * to go dark. */
 757         n = 0;
 758         FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += check_dark(state,lx,ly); } );
 759         if (n == 0) {
 760             /* No, it wouldn't, so we can remove them all. */
 761             FOREACHLIT(&lld, set_light(state,lx,ly, 0); );
 762             GRID(state,flags,x,y) |= F_MARK;
 763         }
 764
 765         if (!grid_overlap(state)) {
 766             sfree(numindices);
 767             return; /* we're done. */
 768         }
 769         assert(grid_lit(state));
 770     }
 771     /* could get here if the line at [1] continue'd out of the loop. */
 772     if (grid_overlap(state)) {
 773         debug_state(state);
 774         assert(!"place_lights failed to resolve overlapping lights!");
 775     }
 776     sfree(numindices);
 777 }
 778
 779 /* Fills in all black squares with numbers of adjacent lights. */
 780 static void place_numbers(game_state *state)
 781 {
 782     int x, y, i, n;
 783     surrounds s;
 784
 785     for (x = 0; x < state->w; x++) {
 786         for (y = 0; y < state->h; y++) {
 787             if (!(GRID(state,flags,x,y) & F_BLACK)) continue;
 788             get_surrounds(state, x, y, &s);
 789             n = 0;
 790             for (i = 0; i < s.npoints; i++) {
 791                 if (GRID(state,flags,s.points[i].x, s.points[i].y) & F_LIGHT)
 792                     n++;
 793             }
 794             GRID(state,flags,x,y) |= F_NUMBERED;
 795             GRID(state,lights,x,y) = n;
 796         }
 797     }
 798 }
 799
 800 /* --- Actual solver, with helper subroutines. --- */
 801
 802 static void tsl_callback(game_state *state,
 803                          int lx, int ly, int *x, int *y, int *n)
 804 {
 805     if (GRID(state,flags,lx,ly) & F_IMPOSSIBLE) return;
 806     if (GRID(state,lights,lx,ly) > 0) return;
 807     *x = lx; *y = ly; (*n)++;
 808 }
 809
 810 static int try_solve_light(game_state *state, int ox, int oy,
 811                            unsigned int flags, int lights)
 812 {
 813     ll_data lld;
 814     int sx = 0, sy = 0, n = 0;
 815
 816     if (lights > 0) return 0;
 817     if (flags & F_BLACK) return 0;
 818
 819     /* We have an unlit square; count how many ways there are left to
 820      * place a light that lights us (including this square); if only
 821      * one, we must put a light there. Squares that could light us
 822      * are, of course, the same as the squares we would light... */
 823     list_lights(state, ox, oy, 1, &lld);
 824     FOREACHLIT(&lld, { tsl_callback(state, lx, ly, &sx, &sy, &n); });
 825     if (n == 1) {
 826         set_light(state, sx, sy, 1);
 827 #ifdef SOLVER_DIAGNOSTICS
 828         debug(("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n",
 829                 ox,oy,sx,sy));
 830         if (verbose) debug_state(state);
 831 #endif
 832         return 1;
 833     }
 834
 835     return 0;
 836 }
 837
 838 static int could_place_light(unsigned int flags, int lights)
 839 {
 840     if (flags & (F_BLACK | F_IMPOSSIBLE)) return 0;
 841     return (lights > 0) ? 0 : 1;
 842 }
 843
 844 static int could_place_light_xy(game_state *state, int x, int y)
 845 {
 846     int lights = GRID(state,lights,x,y);
 847     unsigned int flags = GRID(state,flags,x,y);
 848     return (could_place_light(flags, lights)) ? 1 : 0;
 849 }
 850
 851 /* For a given number square, determine whether we have enough info
 852  * to unambiguously place its lights. */
 853 static int try_solve_number(game_state *state, int nx, int ny,
 854                             unsigned int nflags, int nlights)
 855 {
 856     surrounds s;
 857     int x, y, nl, ns, i, ret = 0, lights;
 858     unsigned int flags;
 859
 860     if (!(nflags & F_NUMBERED)) return 0;
 861     nl = nlights;
 862     get_surrounds(state,nx,ny,&s);
 863     ns = s.npoints;
 864
 865     /* nl is no. of lights we need to place, ns is no. of spaces we
 866      * have to place them in. Try and narrow these down, and mark
 867      * points we can ignore later. */
 868     for (i = 0; i < s.npoints; i++) {
 869         x = s.points[i].x; y = s.points[i].y;
 870         flags = GRID(state,flags,x,y);
 871         lights = GRID(state,lights,x,y);
 872         if (flags & F_LIGHT) {
 873             /* light here already; one less light for one less place. */
 874             nl--; ns--;
 875             s.points[i].f |= F_MARK;
 876         } else if (!could_place_light(flags, lights)) {
 877             ns--;
 878             s.points[i].f |= F_MARK;
 879         }
 880     }
 881     if (ns == 0) return 0; /* nowhere to put anything. */
 882     if (nl == 0) {
 883         /* we have placed all lights we need to around here; all remaining
 884          * surrounds are therefore IMPOSSIBLE. */
 885         GRID(state,flags,nx,ny) |= F_NUMBERUSED;
 886         for (i = 0; i < s.npoints; i++) {
 887             if (!(s.points[i].f & F_MARK)) {
 888                 GRID(state,flags,s.points[i].x,s.points[i].y) |= F_IMPOSSIBLE;
 889                 ret = 1;
 890             }
 891         }
 892 #ifdef SOLVER_DIAGNOSTICS
 893         printf("Clue at (%d,%d) full; setting unlit to IMPOSSIBLE.\n",
 894                nx,ny);
 895         if (verbose) debug_state(state);
 896 #endif
 897     } else if (nl == ns) {
 898         /* we have as many lights to place as spaces; fill them all. */
 899         GRID(state,flags,nx,ny) |= F_NUMBERUSED;
 900         for (i = 0; i < s.npoints; i++) {
 901             if (!(s.points[i].f & F_MARK)) {
 902                 set_light(state, s.points[i].x,s.points[i].y, 1);
 903                 ret = 1;
 904             }
 905         }
 906 #ifdef SOLVER_DIAGNOSTICS
 907         printf("Clue at (%d,%d) trivial; setting unlit to LIGHT.\n",
 908                nx,ny);
 909         if (verbose) debug_state(state);
 910 #endif
 911     }
 912     return ret;
 913 }
 914
 915 struct setscratch {
 916     int x, y;
 917     int n;
 918 };
 919
 920 #define SCRATCHSZ (state->w+state->h)
 921
 922 /* New solver algorithm: overlapping sets can add IMPOSSIBLE flags.
 923  * Algorithm thanks to Simon:
 924  *
 925  * (a) Any square where you can place a light has a set of squares
 926  *     which would become non-lights as a result. (This includes
 927  *     squares lit by the first square, and can also include squares
 928  *     adjacent to the same clue square if the new light is the last
 929  *     one around that clue.) Call this MAKESDARK(x,y) with (x,y) being
 930  *     the square you place a light.
 931
 932  * (b) Any unlit square has a set of squares on which you could place
 933  *     a light to illuminate it. (Possibly including itself, of
 934  *     course.) This set of squares has the property that _at least
 935  *     one_ of them must contain a light. Sets of this type also arise
 936  *     from clue squares. Call this MAKESLIGHT(x,y), again with (x,y)
 937  *     the square you would place a light.
 938
 939  * (c) If there exists (dx,dy) and (lx,ly) such that MAKESDARK(dx,dy) is
 940  *     a superset of MAKESLIGHT(lx,ly), this implies that placing a light at
 941  *     (dx,dy) would either leave no remaining way to illuminate a certain
 942  *     square, or would leave no remaining way to fulfill a certain clue
 943  *     (at lx,ly). In either case, a light can be ruled out at that position.
 944  *
 945  * So, we construct all possible MAKESLIGHT sets, both from unlit squares
 946  * and clue squares, and then we look for plausible MAKESDARK sets that include
 947  * our (lx,ly) to see if we can find a (dx,dy) to rule out. By the time we have
 948  * constructed the MAKESLIGHT set we don't care about (lx,ly), just the set
 949  * members.
 950  *
 951  * Once we have such a set, Simon came up with a Cunning Plan to find
 952  * the most sensible MAKESDARK candidate:
 953  *
 954  * (a) for each square S in your set X, find all the squares which _would_
 955  *     rule it out. That means any square which would light S, plus
 956  *     any square adjacent to the same clue square as S (provided
 957  *     that clue square has only one remaining light to be placed).
 958  *     It's not hard to make this list. Don't do anything with this
 959  *     data at the moment except _count_ the squares.
 960
 961  * (b) Find the square S_min in the original set which has the
 962  *     _smallest_ number of other squares which would rule it out.
 963
 964  * (c) Find all the squares that rule out S_min (it's probably
 965  *     better to recompute this than to have stored it during step
 966  *     (a), since the CPU requirement is modest but the storage
 967  *     cost would get ugly.) For each of these squares, see if it
 968  *     rules out everything else in the set X. Any which does can
 969  *     be marked as not-a-light.
 970  *
 971  */
 972
 973 typedef void (*trl_cb)(game_state *state, int dx, int dy,
 974                        struct setscratch *scratch, int n, void *ctx);
 975
 976 static void try_rule_out(game_state *state, int x, int y,
 977                          struct setscratch *scratch, int n,
 978                          trl_cb cb, void *ctx);
 979
 980 static void trl_callback_search(game_state *state, int dx, int dy,
 981                        struct setscratch *scratch, int n, void *ignored)
 982 {
 983     int i;
 984
 985 #ifdef SOLVER_DIAGNOSTICS
 986     if (verbose) debug(("discount cb: light at (%d,%d)\n", dx, dy));
 987 #endif
 988
 989     for (i = 0; i < n; i++) {
 990         if (dx == scratch[i].x && dy == scratch[i].y) {
 991             scratch[i].n = 1;
 992             return;
 993         }
 994     }
 995 }
 996
 997 static void trl_callback_discount(game_state *state, int dx, int dy,
 998                        struct setscratch *scratch, int n, void *ctx)
 999 {
1000     int *didsth = (int *)ctx;
1001     int i;
1002
1003     if (GRID(state,flags,dx,dy) & F_IMPOSSIBLE) {
1004 #ifdef SOLVER_DIAGNOSTICS
1005         debug(("Square at (%d,%d) already impossible.\n", dx,dy));
1006 #endif
1007         return;
1008     }
1009
1010     /* Check whether a light at (dx,dy) rules out everything
1011      * in scratch, and mark (dx,dy) as IMPOSSIBLE if it does.
1012      * We can use try_rule_out for this as well, as the set of
1013      * squares which would rule out (x,y) is the same as the
1014      * set of squares which (x,y) would rule out. */
1015
1016 #ifdef SOLVER_DIAGNOSTICS
1017     if (verbose) debug(("Checking whether light at (%d,%d) rules out everything in scratch.\n", dx, dy));
1018 #endif
1019
1020     for (i = 0; i < n; i++)
1021         scratch[i].n = 0;
1022     try_rule_out(state, dx, dy, scratch, n, trl_callback_search, NULL);
1023     for (i = 0; i < n; i++) {
1024         if (scratch[i].n == 0) return;
1025     }
1026     /* The light ruled out everything in scratch. Yay. */
1027     GRID(state,flags,dx,dy) |= F_IMPOSSIBLE;
1028 #ifdef SOLVER_DIAGNOSTICS
1029     debug(("Set reduction discounted square at (%d,%d):\n", dx,dy));
1030     if (verbose) debug_state(state);
1031 #endif
1032
1033     *didsth = 1;
1034 }
1035
1036 static void trl_callback_incn(game_state *state, int dx, int dy,
1037                        struct setscratch *scratch, int n, void *ctx)
1038 {
1039     struct setscratch *s = (struct setscratch *)ctx;
1040     s->n++;
1041 }
1042
1043 static void try_rule_out(game_state *state, int x, int y,
1044                          struct setscratch *scratch, int n,
1045                          trl_cb cb, void *ctx)
1046 {
1047     /* XXX Find all the squares which would rule out (x,y); anything
1048      * that would light it as well as squares adjacent to same clues
1049      * as X assuming that clue only has one remaining light.
1050      * Call the callback with each square. */
1051     ll_data lld;
1052     surrounds s, ss;
1053     int i, j, curr_lights, tot_lights;
1054
1055     /* Find all squares that would rule out a light at (x,y) and call trl_cb
1056      * with them: anything that would light (x,y)... */
1057
1058     list_lights(state, x, y, 0, &lld);
1059     FOREACHLIT(&lld, { if (could_place_light_xy(state, lx, ly)) { cb(state, lx, ly, scratch, n, ctx); } });
1060
1061     /* ... as well as any empty space (that isn't x,y) next to any clue square
1062      * next to (x,y) that only has one light left to place. */
1063
1064     get_surrounds(state, x, y, &s);
1065     for (i = 0; i < s.npoints; i++) {
1066         if (!(GRID(state,flags,s.points[i].x,s.points[i].y) & F_NUMBERED))
1067             continue;
1068         /* we have an adjacent clue square; find /its/ surrounds
1069          * and count the remaining lights it needs. */
1070         get_surrounds(state,s.points[i].x,s.points[i].y,&ss);
1071         curr_lights = 0;
1072         for (j = 0; j < ss.npoints; j++) {
1073             if (GRID(state,flags,ss.points[j].x,ss.points[j].y) & F_LIGHT)
1074                 curr_lights++;
1075         }
1076         tot_lights = GRID(state, lights, s.points[i].x, s.points[i].y);
1077         /* We have a clue with tot_lights to fill, and curr_lights currently
1078          * around it. If adding a light at (x,y) fills up the clue (i.e.
1079          * curr_lights + 1 = tot_lights) then we need to discount all other
1080          * unlit squares around the clue. */
1081         if ((curr_lights + 1) == tot_lights) {
1082             for (j = 0; j < ss.npoints; j++) {
1083                 int lx = ss.points[j].x, ly = ss.points[j].y;
1084                 if (lx == x && ly == y) continue;
1085                 if (could_place_light_xy(state, lx, ly))
1086                     cb(state, lx, ly, scratch, n, ctx);
1087             }
1088         }
1089     }
1090 }
1091
1092 #ifdef SOLVER_DIAGNOSTICS
1093 static void debug_scratch(const char *msg, struct setscratch *scratch, int n)
1094 {
1095     int i;
1096     debug(("%s scratch (%d elements):\n", msg, n));
1097     for (i = 0; i < n; i++) {
1098         debug(("  (%d,%d) n%d\n", scratch[i].x, scratch[i].y, scratch[i].n));
1099     }
1100 }
1101 #endif
1102
1103 static int discount_set(game_state *state,
1104                         struct setscratch *scratch, int n)
1105 {
1106     int i, besti, bestn, didsth = 0;
1107
1108 #ifdef SOLVER_DIAGNOSTICS
1109     if (verbose > 1) debug_scratch("discount_set", scratch, n);
1110 #endif
1111     if (n == 0) return 0;
1112
1113     for (i = 0; i < n; i++) {
1114         try_rule_out(state, scratch[i].x, scratch[i].y, scratch, n,
1115                      trl_callback_incn, (void*)&(scratch[i]));
1116     }
1117 #ifdef SOLVER_DIAGNOSTICS
1118     if (verbose > 1) debug_scratch("discount_set after count", scratch, n);
1119 #endif
1120
1121     besti = -1; bestn = SCRATCHSZ;
1122     for (i = 0; i < n; i++) {
1123         if (scratch[i].n < bestn) {
1124             bestn = scratch[i].n;
1125             besti = i;
1126         }
1127     }
1128 #ifdef SOLVER_DIAGNOSTICS
1129     if (verbose > 1) debug(("best square (%d,%d) with n%d.\n",
1130            scratch[besti].x, scratch[besti].y, scratch[besti].n));
1131 #endif
1132     try_rule_out(state, scratch[besti].x, scratch[besti].y, scratch, n,
1133                  trl_callback_discount, (void*)&didsth);
1134 #ifdef SOLVER_DIAGNOSTICS
1135     if (didsth) debug((" [from square (%d,%d)]\n",
1136                        scratch[besti].x, scratch[besti].y));
1137 #endif
1138
1139     return didsth;
1140 }
1141
1142 static void discount_clear(game_state *state, struct setscratch *scratch, int *n)
1143 {
1144     *n = 0;
1145     memset(scratch, 0, SCRATCHSZ * sizeof(struct setscratch));
1146 }
1147
1148 static void unlit_cb(game_state *state, int lx, int ly,
1149                      struct setscratch *scratch, int *n)
1150 {
1151     if (could_place_light_xy(state, lx, ly)) {
1152         scratch[*n].x = lx; scratch[*n].y = ly; (*n)++;
1153     }
1154 }
1155
1156 /* Construct a MAKESLIGHT set from an unlit square. */
1157 static int discount_unlit(game_state *state, int x, int y,
1158                           struct setscratch *scratch)
1159 {
1160     ll_data lld;
1161     int n, didsth;
1162
1163 #ifdef SOLVER_DIAGNOSTICS
1164     if (verbose) debug(("Trying to discount for unlit square at (%d,%d).\n", x, y));
1165     if (verbose > 1) debug_state(state);
1166 #endif
1167
1168     discount_clear(state, scratch, &n);
1169
1170     list_lights(state, x, y, 1, &lld);
1171     FOREACHLIT(&lld, { unlit_cb(state, lx, ly, scratch, &n); });
1172     didsth = discount_set(state, scratch, n);
1173 #ifdef SOLVER_DIAGNOSTICS
1174     if (didsth) debug(("  [from unlit square at (%d,%d)].\n", x, y));
1175 #endif
1176     return didsth;
1177
1178 }
1179
1180 /* Construct a series of MAKESLIGHT sets from a clue square.
1181  *  for a clue square with N remaining spaces that must contain M lights, every
1182  *  subset of size N-M+1 of those N spaces forms such a set.
1183  */
1184
1185 static int discount_clue(game_state *state, int x, int y,
1186                           struct setscratch *scratch)
1187 {
1188     int slen, m = GRID(state, lights, x, y), n, i, didsth = 0, lights;
1189     unsigned int flags;
1190     surrounds s, sempty;
1191     combi_ctx *combi;
1192
1193     if (m == 0) return 0;
1194
1195 #ifdef SOLVER_DIAGNOSTICS
1196     if (verbose) debug(("Trying to discount for sets at clue (%d,%d).\n", x, y));
1197     if (verbose > 1) debug_state(state);
1198 #endif
1199
1200     /* m is no. of lights still to place; starts off at the clue value
1201      * and decreases when we find a light already down.
1202      * n is no. of spaces left; starts off at 0 and goes up when we find
1203      * a plausible space. */
1204
1205     get_surrounds(state, x, y, &s);
1206     memset(&sempty, 0, sizeof(surrounds));
1207     for (i = 0; i < s.npoints; i++) {
1208         int lx = s.points[i].x, ly = s.points[i].y;
1209         flags = GRID(state,flags,lx,ly);
1210         lights = GRID(state,lights,lx,ly);
1211
1212         if (flags & F_LIGHT) m--;
1213
1214         if (could_place_light(flags, lights)) {
1215             sempty.points[sempty.npoints].x = lx;
1216             sempty.points[sempty.npoints].y = ly;
1217             sempty.npoints++;
1218         }
1219     }
1220     n = sempty.npoints; /* sempty is now a surrounds of only blank squares. */
1221     if (n == 0) return 0; /* clue is full already. */
1222
1223     if (m < 0 || m > n) return 0; /* become impossible. */
1224
1225     combi = new_combi(n - m + 1, n);
1226     while (next_combi(combi)) {
1227         discount_clear(state, scratch, &slen);
1228         for (i = 0; i < combi->r; i++) {
1229             scratch[slen].x = sempty.points[combi->a[i]].x;
1230             scratch[slen].y = sempty.points[combi->a[i]].y;
1231             slen++;
1232         }
1233         if (discount_set(state, scratch, slen)) didsth = 1;
1234     }
1235     free_combi(combi);
1236 #ifdef SOLVER_DIAGNOSTICS
1237     if (didsth) debug(("  [from clue at (%d,%d)].\n", x, y));
1238 #endif
1239     return didsth;
1240 }
1241
1242 #define F_SOLVE_FORCEUNIQUE     1
1243 #define F_SOLVE_DISCOUNTSETS    2
1244 #define F_SOLVE_ALLOWRECURSE    4
1245
1246 static unsigned int flags_from_difficulty(int difficulty)
1247 {
1248     unsigned int sflags = F_SOLVE_FORCEUNIQUE;
1249     assert(difficulty <= DIFFCOUNT);
1250     if (difficulty >= 1) sflags |= F_SOLVE_DISCOUNTSETS;
1251     if (difficulty >= 2) sflags |= F_SOLVE_ALLOWRECURSE;
1252     return sflags;
1253 }
1254
1255 #define MAXRECURSE 5
1256
1257 static int solve_sub(game_state *state,
1258                      unsigned int solve_flags, int depth,
1259                      int *maxdepth)
1260 {
1261     unsigned int flags;
1262     int x, y, didstuff, ncanplace, lights;
1263     int bestx, besty, n, bestn, copy_soluble, self_soluble, ret, maxrecurse = 0;
1264     game_state *scopy;
1265     ll_data lld;
1266     struct setscratch *sscratch = NULL;
1267
1268 #ifdef SOLVER_DIAGNOSTICS
1269     printf("solve_sub: depth = %d\n", depth);
1270 #endif
1271     if (maxdepth && *maxdepth < depth) *maxdepth = depth;
1272     if (solve_flags & F_SOLVE_ALLOWRECURSE) maxrecurse = MAXRECURSE;
1273
1274     while (1) {
1275         if (grid_overlap(state)) {
1276             /* Our own solver, from scratch, should never cause this to happen
1277              * (assuming a soluble grid). However, if we're trying to solve
1278              * from a half-completed *incorrect* grid this might occur; we
1279              * just return the 'no solutions' code in this case. */
1280             ret = 0; goto done;
1281         }
1282
1283         if (grid_correct(state)) { ret = 1; goto done; }
1284
1285         ncanplace = 0;
1286         didstuff = 0;
1287         /* These 2 loops, and the functions they call, are the critical loops
1288          * for timing; any optimisations should look here first. */
1289         for (x = 0; x < state->w; x++) {
1290             for (y = 0; y < state->h; y++) {
1291                 flags = GRID(state,flags,x,y);
1292                 lights = GRID(state,lights,x,y);
1293                 ncanplace += could_place_light(flags, lights);
1294
1295                 if (try_solve_light(state, x, y, flags, lights)) didstuff = 1;
1296                 if (try_solve_number(state, x, y, flags, lights)) didstuff = 1;
1297             }
1298         }
1299         if (didstuff) continue;
1300         if (!ncanplace) {
1301             /* nowhere to put a light, puzzle is unsoluble. */
1302             ret = 0; goto done;
1303         }
1304
1305         if (solve_flags & F_SOLVE_DISCOUNTSETS) {
1306             if (!sscratch) sscratch = snewn(SCRATCHSZ, struct setscratch);
1307             /* Try a more cunning (and more involved) way... more details above. */
1308             for (x = 0; x < state->w; x++) {
1309                 for (y = 0; y < state->h; y++) {
1310                     flags = GRID(state,flags,x,y);
1311                     lights = GRID(state,lights,x,y);
1312
1313                     if (!(flags & F_BLACK) && lights == 0) {
1314                         if (discount_unlit(state, x, y, sscratch)) {
1315                             didstuff = 1;
1316                             goto reduction_success;
1317                         }
1318                     } else if (flags & F_NUMBERED) {
1319                         if (discount_clue(state, x, y, sscratch)) {
1320                             didstuff = 1;
1321                             goto reduction_success;
1322                         }
1323                     }
1324                 }
1325             }
1326         }
1327 reduction_success:
1328         if (didstuff) continue;
1329
1330         /* We now have to make a guess; we have places to put lights but
1331          * no definite idea about where they can go. */
1332         if (depth >= maxrecurse) {
1333             /* mustn't delve any deeper. */
1334             ret = -1; goto done;
1335         }
1336         /* Of all the squares that we could place a light, pick the one
1337          * that would light the most currently unlit squares. */
1338         /* This heuristic was just plucked from the air; there may well be
1339          * a more efficient way of choosing a square to flip to minimise
1340          * recursion. */
1341         bestn = 0;
1342         bestx = besty = -1; /* suyb */
1343         for (x = 0; x < state->w; x++) {
1344             for (y = 0; y < state->h; y++) {
1345                 flags = GRID(state,flags,x,y);
1346                 lights = GRID(state,lights,x,y);
1347                 if (!could_place_light(flags, lights)) continue;
1348
1349                 n = 0;
1350                 list_lights(state, x, y, 1, &lld);
1351                 FOREACHLIT(&lld, { if (GRID(state,lights,lx,ly) == 0) n++; });
1352                 if (n > bestn) {
1353                     bestn = n; bestx = x; besty = y;
1354                 }
1355             }
1356         }
1357         assert(bestn > 0);
1358         assert(bestx >= 0 && besty >= 0);
1359
1360         /* Now we've chosen a plausible (x,y), try to solve it once as 'lit'
1361          * and once as 'impossible'; we need to make one copy to do this. */
1362
1363         scopy = dup_game(state);
1364 #ifdef SOLVER_DIAGNOSTICS
1365         debug(("Recursing #1: trying (%d,%d) as IMPOSSIBLE\n", bestx, besty));
1366 #endif
1367         GRID(state,flags,bestx,besty) |= F_IMPOSSIBLE;
1368         self_soluble = solve_sub(state, solve_flags,  depth+1, maxdepth);
1369
1370         if (!(solve_flags & F_SOLVE_FORCEUNIQUE) && self_soluble > 0) {
1371             /* we didn't care about finding all solutions, and we just
1372              * found one; return with it immediately. */
1373             free_game(scopy);
1374             ret = self_soluble;
1375             goto done;
1376         }
1377
1378 #ifdef SOLVER_DIAGNOSTICS
1379         debug(("Recursing #2: trying (%d,%d) as LIGHT\n", bestx, besty));
1380 #endif
1381         set_light(scopy, bestx, besty, 1);
1382         copy_soluble = solve_sub(scopy, solve_flags, depth+1, maxdepth);
1383
1384         /* If we wanted a unique solution but we hit our recursion limit
1385          * (on either branch) then we have to assume we didn't find possible
1386          * extra solutions, and return 'not soluble'. */
1387         if ((solve_flags & F_SOLVE_FORCEUNIQUE) &&
1388             ((copy_soluble < 0) || (self_soluble < 0))) {
1389             ret = -1;
1390         /* Make sure that whether or not it was self or copy (or both) that
1391          * were soluble, that we return a solved state in self. */
1392         } else if (copy_soluble <= 0) {
1393             /* copy wasn't soluble; keep self state and return that result. */
1394             ret = self_soluble;
1395         } else if (self_soluble <= 0) {
1396             /* copy solved and we didn't, so copy in copy's (now solved)
1397              * flags and light state. */
1398             memcpy(state->lights, scopy->lights,
1399                    scopy->w * scopy->h * sizeof(int));
1400             memcpy(state->flags, scopy->flags,
1401                    scopy->w * scopy->h * sizeof(unsigned int));
1402             ret = copy_soluble;
1403         } else {
1404             ret = copy_soluble + self_soluble;
1405         }
1406         free_game(scopy);
1407         goto done;
1408     }
1409 done:
1410     if (sscratch) sfree(sscratch);
1411 #ifdef SOLVER_DIAGNOSTICS
1412     if (ret < 0)
1413         debug(("solve_sub: depth = %d returning, ran out of recursion.\n",
1414                depth));
1415     else
1416         debug(("solve_sub: depth = %d returning, %d solutions.\n",
1417                depth, ret));
1418 #endif
1419     return ret;
1420 }
1421
1422 /* Fills in the (possibly partially-complete) game_state as far as it can,
1423  * returning the number of possible solutions. If it returns >0 then the
1424  * game_state will be in a solved state, but you won't know which one. */
1425 static int dosolve(game_state *state, int solve_flags, int *maxdepth)
1426 {
1427     int x, y, nsol;
1428
1429     for (x = 0; x < state->w; x++) {
1430         for (y = 0; y < state->h; y++) {
1431             GRID(state,flags,x,y) &= ~F_NUMBERUSED;
1432         }
1433     }
1434     nsol = solve_sub(state, solve_flags, 0, maxdepth);
1435     return nsol;
1436 }
1437
1438 static int strip_unused_nums(game_state *state)
1439 {
1440     int x,y,n=0;
1441     for (x = 0; x < state->w; x++) {
1442         for (y = 0; y < state->h; y++) {
1443             if ((GRID(state,flags,x,y) & F_NUMBERED) &&
1444                 !(GRID(state,flags,x,y) & F_NUMBERUSED)) {
1445                 GRID(state,flags,x,y) &= ~F_NUMBERED;
1446                 GRID(state,lights,x,y) = 0;
1447                 n++;
1448             }
1449         }
1450     }
1451     debug(("Stripped %d unused numbers.\n", n));
1452     return n;
1453 }
1454
1455 static void unplace_lights(game_state *state)
1456 {
1457     int x,y;
1458     for (x = 0; x < state->w; x++) {
1459         for (y = 0; y < state->h; y++) {
1460             if (GRID(state,flags,x,y) & F_LIGHT)
1461                 set_light(state,x,y,0);
1462             GRID(state,flags,x,y) &= ~F_IMPOSSIBLE;
1463             GRID(state,flags,x,y) &= ~F_NUMBERUSED;
1464         }
1465     }
1466 }
1467
1468 static int puzzle_is_good(game_state *state, int difficulty)
1469 {
1470     int nsol, mdepth = 0;
1471     unsigned int sflags = flags_from_difficulty(difficulty);
1472
1473     unplace_lights(state);
1474
1475 #ifdef SOLVER_DIAGNOSTICS
1476     debug(("Trying to solve with difficulty %d (0x%x):\n",
1477            difficulty, sflags));
1478     if (verbose) debug_state(state);
1479 #endif
1480
1481     nsol = dosolve(state, sflags, &mdepth);
1482     /* if we wanted an easy puzzle, make sure we didn't need recursion. */
1483     if (!(sflags & F_SOLVE_ALLOWRECURSE) && mdepth > 0) {
1484         debug(("Ignoring recursive puzzle.\n"));
1485         return 0;
1486     }
1487
1488     debug(("%d solutions found.\n", nsol));
1489     if (nsol <= 0) return 0;
1490     if (nsol > 1) return 0;
1491     return 1;
1492 }
1493
1494 /* --- New game creation and user input code. --- */
1495
1496 /* The basic algorithm here is to generate the most complex grid possible
1497  * while honouring two restrictions:
1498  *
1499  *  * we require a unique solution, and
1500  *  * either we require solubility with no recursion (!params->recurse)
1501  *  * or we require some recursion. (params->recurse).
1502  *
1503  * The solver helpfully keeps track of the numbers it needed to use to
1504  * get its solution, so we use that to remove an initial set of numbers
1505  * and check we still satsify our requirements (on uniqueness and
1506  * non-recursiveness, if applicable; we don't check explicit recursiveness
1507  * until the end).
1508  *
1509  * Then we try to remove all numbers in a random order, and see if we
1510  * still satisfy requirements (putting them back if we didn't).
1511  *
1512  * Removing numbers will always, in general terms, make a puzzle require
1513  * more recursion but it may also mean a puzzle becomes non-unique.
1514  *
1515  * Once we're done, if we wanted a recursive puzzle but the most difficult
1516  * puzzle we could come up with was non-recursive, we give up and try a new
1517  * grid. */
1518
1519 #define MAX_GRIDGEN_TRIES 20
1520
1521 static char *new_game_desc(const game_params *params_in, random_state *rs,
1522                            char **aux, int interactive)
1523 {
1524     game_params params_copy = *params_in; /* structure copy */
1525     game_params *params = &params_copy;
1526     game_state *news = new_state(params), *copys;
1527     int i, j, run, x, y, wh = params->w*params->h, num;
1528     char *ret, *p;
1529     int *numindices;
1530
1531     /* Construct a shuffled list of grid positions; we only
1532      * do this once, because if it gets used more than once it'll
1533      * be on a different grid layout. */
1534     numindices = snewn(wh, int);
1535     for (j = 0; j < wh; j++) numindices[j] = j;
1536     shuffle(numindices, wh, sizeof(*numindices), rs);
1537
1538     while (1) {
1539         for (i = 0; i < MAX_GRIDGEN_TRIES; i++) {
1540             set_blacks(news, params, rs); /* also cleans board. */
1541
1542             /* set up lights and then the numbers, and remove the lights */
1543             place_lights(news, rs);
1544             debug(("Generating initial grid.\n"));
1545             place_numbers(news);
1546             if (!puzzle_is_good(news, params->difficulty)) continue;
1547
1548             /* Take a copy, remove numbers we didn't use and check there's
1549              * still a unique solution; if so, use the copy subsequently. */
1550             copys = dup_game(news);
1551             strip_unused_nums(copys);
1552             if (!puzzle_is_good(copys, params->difficulty)) {
1553                 debug(("Stripped grid is not good, reverting.\n"));
1554                 free_game(copys);
1555             } else {
1556                 free_game(news);
1557                 news = copys;
1558             }
1559
1560             /* Go through grid removing numbers at random one-by-one and
1561              * trying to solve again; if it ceases to be good put the number back. */
1562             for (j = 0; j < wh; j++) {
1563                 y = numindices[j] / params->w;
1564                 x = numindices[j] % params->w;
1565                 if (!(GRID(news, flags, x, y) & F_NUMBERED)) continue;
1566                 num = GRID(news, lights, x, y);
1567                 GRID(news, lights, x, y) = 0;
1568                 GRID(news, flags, x, y) &= ~F_NUMBERED;
1569                 if (!puzzle_is_good(news, params->difficulty)) {
1570                     GRID(news, lights, x, y) = num;
1571                     GRID(news, flags, x, y) |= F_NUMBERED;
1572                 } else
1573                     debug(("Removed (%d,%d) still soluble.\n", x, y));
1574             }
1575             if (params->difficulty > 0) {
1576                 /* Was the maximally-difficult puzzle difficult enough?
1577                  * Check we can't solve it with a more simplistic solver. */
1578                 if (puzzle_is_good(news, params->difficulty-1)) {
1579                     debug(("Maximally-hard puzzle still not hard enough, skipping.\n"));
1580                     continue;
1581                 }
1582             }
1583
1584             goto goodpuzzle;
1585         }
1586         /* Couldn't generate a good puzzle in however many goes. Ramp up the
1587          * %age of black squares (if we didn't already have lots; in which case
1588          * why couldn't we generate a puzzle?) and try again. */
1589         if (params->blackpc < 90) params->blackpc += 5;
1590         debug(("New black layout %d%%.\n", params->blackpc));
1591     }
1592 goodpuzzle:
1593     /* Game is encoded as a long string one character per square;
1594      * 'S' is a space
1595      * 'B' is a black square with no number
1596      * '0', '1', '2', '3', '4' is a black square with a number. */
1597     ret = snewn((params->w * params->h) + 1, char);
1598     p = ret;
1599     run = 0;
1600     for (y = 0; y < params->h; y++) {
1601         for (x = 0; x < params->w; x++) {
1602             if (GRID(news,flags,x,y) & F_BLACK) {
1603                 if (run) {
1604                     *p++ = ('a'-1) + run;
1605                     run = 0;
1606                 }
1607                 if (GRID(news,flags,x,y) & F_NUMBERED)
1608                     *p++ = '0' + GRID(news,lights,x,y);
1609                 else
1610                     *p++ = 'B';
1611             } else {
1612                 if (run == 26) {
1613                     *p++ = ('a'-1) + run;
1614                     run = 0;
1615                 }
1616                 run++;
1617             }
1618         }
1619     }
1620     if (run) {
1621         *p++ = ('a'-1) + run;
1622         run = 0;
1623     }
1624     *p = '\0';
1625     assert(p - ret <= params->w * params->h);
1626     free_game(news);
1627     sfree(numindices);
1628
1629     return ret;
1630 }
1631
1632 static char *validate_desc(const game_params *params, const char *desc)
1633 {
1634     int i;
1635     for (i = 0; i < params->w*params->h; i++) {
1636         if (*desc >= '0' && *desc <= '4')
1637             /* OK */;
1638         else if (*desc == 'B')
1639             /* OK */;
1640         else if (*desc >= 'a' && *desc <= 'z')
1641             i += *desc - 'a';          /* and the i++ will add another one */
1642         else if (!*desc)
1643             return "Game description shorter than expected";
1644         else
1645             return "Game description contained unexpected character";
1646         desc++;
1647     }
1648     if (*desc || i > params->w*params->h)
1649         return "Game description longer than expected";
1650
1651     return NULL;
1652 }
1653
1654 static game_state *new_game(midend *me, const game_params *params,
1655                             const char *desc)
1656 {
1657     game_state *ret = new_state(params);
1658     int x,y;
1659     int run = 0;
1660
1661     for (y = 0; y < params->h; y++) {
1662         for (x = 0; x < params->w; x++) {
1663             char c = '\0';
1664
1665             if (run == 0) {
1666                 c = *desc++;
1667                 assert(c != 'S');
1668                 if (c >= 'a' && c <= 'z')
1669                     run = c - 'a' + 1;
1670             }
1671
1672             if (run > 0) {
1673                 c = 'S';
1674                 run--;
1675             }
1676
1677             switch (c) {
1678               case '0': case '1': case '2': case '3': case '4':
1679                 GRID(ret,flags,x,y) |= F_NUMBERED;
1680                 GRID(ret,lights,x,y) = (c - '0');
1681                 /* run-on... */
1682
1683               case 'B':
1684                 GRID(ret,flags,x,y) |= F_BLACK;
1685                 break;
1686
1687               case 'S':
1688                 /* empty square */
1689                 break;
1690
1691               default:
1692                 assert(!"Malformed desc.");
1693                 break;
1694             }
1695         }
1696     }
1697     if (*desc) assert(!"Over-long desc.");
1698
1699     return ret;
1700 }
1701
1702 static char *solve_game(const game_state *state, const game_state *currstate,
1703                         const char *aux, char **error)
1704 {
1705     game_state *solved;
1706     char *move = NULL, buf[80];
1707     int movelen, movesize, x, y, len;
1708     unsigned int oldflags, solvedflags, sflags;
1709
1710     /* We don't care here about non-unique puzzles; if the
1711      * user entered one themself then I doubt they care. */
1712
1713     sflags = F_SOLVE_ALLOWRECURSE | F_SOLVE_DISCOUNTSETS;
1714
1715     /* Try and solve from where we are now (for non-unique
1716      * puzzles this may produce a different answer). */
1717     solved = dup_game(currstate);
1718     if (dosolve(solved, sflags, NULL) > 0) goto solved;
1719     free_game(solved);
1720
1721     /* That didn't work; try solving from the clean puzzle. */
1722     solved = dup_game(state);
1723     if (dosolve(solved, sflags, NULL) > 0) goto solved;
1724     *error = "Unable to find a solution to this puzzle.";
1725     goto done;
1726
1727 solved:
1728     movesize = 256;
1729     move = snewn(movesize, char);
1730     movelen = 0;
1731     move[movelen++] = 'S';
1732     move[movelen] = '\0';
1733     for (x = 0; x < currstate->w; x++) {
1734         for (y = 0; y < currstate->h; y++) {
1735             len = 0;
1736             oldflags = GRID(currstate, flags, x, y);
1737             solvedflags = GRID(solved, flags, x, y);
1738             if ((oldflags & F_LIGHT) != (solvedflags & F_LIGHT))
1739                 len = sprintf(buf, ";L%d,%d", x, y);
1740             else if ((oldflags & F_IMPOSSIBLE) != (solvedflags & F_IMPOSSIBLE))
1741                 len = sprintf(buf, ";I%d,%d", x, y);
1742             if (len) {
1743                 if (movelen + len >= movesize) {
1744                     movesize = movelen + len + 256;
1745                     move = sresize(move, movesize, char);
1746                 }
1747                 strcpy(move + movelen, buf);
1748                 movelen += len;
1749             }
1750         }
1751     }
1752
1753 done:
1754     free_game(solved);
1755     return move;
1756 }
1757
1758 static int game_can_format_as_text_now(const game_params *params)
1759 {
1760     return TRUE;
1761 }
1762
1763 /* 'borrowed' from slant.c, mainly. I could have printed it one
1764  * character per cell (like debug_state) but that comes out tiny.
1765  * 'L' is used for 'light here' because 'O' looks too much like '0'
1766  * (black square with no surrounding lights). */
1767 static char *game_text_format(const game_state *state)
1768 {
1769     int w = state->w, h = state->h, W = w+1, H = h+1;
1770     int x, y, len, lights;
1771     unsigned int flags;
1772     char *ret, *p;
1773
1774     len = (h+H) * (w+W+1) + 1;
1775     ret = snewn(len, char);
1776     p = ret;
1777
1778     for (y = 0; y < H; y++) {
1779         for (x = 0; x < W; x++) {
1780             *p++ = '+';
1781             if (x < w)
1782                 *p++ = '-';
1783         }
1784         *p++ = '\n';
1785         if (y < h) {
1786             for (x = 0; x < W; x++) {
1787                 *p++ = '|';
1788                 if (x < w) {
1789                     /* actual interesting bit. */
1790                     flags = GRID(state, flags, x, y);
1791                     lights = GRID(state, lights, x, y);
1792                     if (flags & F_BLACK) {
1793                         if (flags & F_NUMBERED)
1794                             *p++ = '0' + lights;
1795                         else
1796                             *p++ = '#';
1797                     } else {
1798                         if (flags & F_LIGHT)
1799                             *p++ = 'L';
1800                         else if (flags & F_IMPOSSIBLE)
1801                             *p++ = 'x';
1802                         else if (lights > 0)
1803                             *p++ = '.';
1804                         else
1805                             *p++ = ' ';
1806                     }
1807                 }
1808             }
1809             *p++ = '\n';
1810         }
1811     }
1812     *p++ = '\0';
1813
1814     assert(p - ret == len);
1815     return ret;
1816 }
1817
1818 struct game_ui {
1819     int cur_x, cur_y, cur_visible;
1820 };
1821
1822 static game_ui *new_ui(const game_state *state)
1823 {
1824     game_ui *ui = snew(game_ui);
1825     ui->cur_x = ui->cur_y = ui->cur_visible = 0;
1826     return ui;
1827 }
1828
1829 static void free_ui(game_ui *ui)
1830 {
1831     sfree(ui);
1832 }
1833
1834 static char *encode_ui(const game_ui *ui)
1835 {
1836     /* nothing to encode. */
1837     return NULL;
1838 }
1839
1840 static void decode_ui(game_ui *ui, const char *encoding)
1841 {
1842     /* nothing to decode. */
1843 }
1844
1845 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1846                                const game_state *newstate)
1847 {
1848     if (newstate->completed)
1849         ui->cur_visible = 0;
1850 }
1851
1852 #define DF_BLACK        1       /* black square */
1853 #define DF_NUMBERED     2       /* black square with number */
1854 #define DF_LIT          4       /* display (white) square lit up */
1855 #define DF_LIGHT        8       /* display light in square */
1856 #define DF_OVERLAP      16      /* display light as overlapped */
1857 #define DF_CURSOR       32      /* display cursor */
1858 #define DF_NUMBERWRONG  64      /* display black numbered square as error. */
1859 #define DF_FLASH        128     /* background flash is on. */
1860 #define DF_IMPOSSIBLE   256     /* display non-light little square */
1861
1862 struct game_drawstate {
1863     int tilesize, crad;
1864     int w, h;
1865     unsigned int *flags;         /* width * height */
1866     int started;
1867 };
1868
1869
1870 /* Believe it or not, this empty = "" hack is needed to get around a bug in
1871  * the prc-tools gcc when optimisation is turned on; before, it produced:
1872     lightup-sect.c: In function `interpret_move':
1873     lightup-sect.c:1416: internal error--unrecognizable insn:
1874     (insn 582 580 583 (set (reg:SI 134)
1875             (pc)) -1 (nil)
1876         (nil))
1877  */
1878 static char *interpret_move(const game_state *state, game_ui *ui,
1879                             const game_drawstate *ds,
1880                             int x, int y, int button)
1881 {
1882     enum { NONE, FLIP_LIGHT, FLIP_IMPOSSIBLE } action = NONE;
1883     int cx = -1, cy = -1;
1884     unsigned int flags;
1885     char buf[80], *nullret = NULL, *empty = "", c;
1886
1887     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1888         if (ui->cur_visible)
1889             nullret = empty;
1890         ui->cur_visible = 0;
1891         cx = FROMCOORD(x);
1892         cy = FROMCOORD(y);
1893         action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE;
1894     } else if (IS_CURSOR_SELECT(button) ||
1895                button == 'i' || button == 'I' ||
1896                button == ' ' || button == '\r' || button == '\n') {
1897         if (ui->cur_visible) {
1898             /* Only allow cursor-effect operations if the cursor is visible
1899              * (otherwise you have no idea which square it might be affecting) */
1900             cx = ui->cur_x;
1901             cy = ui->cur_y;
1902             action = (button == 'i' || button == 'I' || button == CURSOR_SELECT2) ?
1903                 FLIP_IMPOSSIBLE : FLIP_LIGHT;
1904         }
1905         ui->cur_visible = 1;
1906     } else if (IS_CURSOR_MOVE(button)) {
1907         move_cursor(button, &ui->cur_x, &ui->cur_y, state->w, state->h, 0);
1908         ui->cur_visible = 1;
1909         nullret = empty;
1910     } else
1911         return NULL;
1912
1913     switch (action) {
1914     case FLIP_LIGHT:
1915     case FLIP_IMPOSSIBLE:
1916         if (cx < 0 || cy < 0 || cx >= state->w || cy >= state->h)
1917             return nullret;
1918         flags = GRID(state, flags, cx, cy);
1919         if (flags & F_BLACK)
1920             return nullret;
1921         if (action == FLIP_LIGHT) {
1922 #ifdef STYLUS_BASED
1923             if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'I'; else c = 'L';
1924 #else
1925             if (flags & F_IMPOSSIBLE) return nullret;
1926             c = 'L';
1927 #endif
1928         } else {
1929 #ifdef STYLUS_BASED
1930             if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'L'; else c = 'I';
1931 #else
1932             if (flags & F_LIGHT) return nullret;
1933             c = 'I';
1934 #endif
1935         }
1936         sprintf(buf, "%c%d,%d", (int)c, cx, cy);
1937         break;
1938
1939     case NONE:
1940         return nullret;
1941
1942     default:
1943         assert(!"Shouldn't get here!");
1944     }
1945     return dupstr(buf);
1946 }
1947
1948 static game_state *execute_move(const game_state *state, const char *move)
1949 {
1950     game_state *ret = dup_game(state);
1951     int x, y, n, flags;
1952     char c;
1953
1954     if (!*move) goto badmove;
1955
1956     while (*move) {
1957         c = *move;
1958         if (c == 'S') {
1959             ret->used_solve = TRUE;
1960             move++;
1961         } else if (c == 'L' || c == 'I') {
1962             move++;
1963             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1964                 x < 0 || y < 0 || x >= ret->w || y >= ret->h)
1965                 goto badmove;
1966
1967             flags = GRID(ret, flags, x, y);
1968             if (flags & F_BLACK) goto badmove;
1969
1970             /* LIGHT and IMPOSSIBLE are mutually exclusive. */
1971             if (c == 'L') {
1972                 GRID(ret, flags, x, y) &= ~F_IMPOSSIBLE;
1973                 set_light(ret, x, y, (flags & F_LIGHT) ? 0 : 1);
1974             } else {
1975                 set_light(ret, x, y, 0);
1976                 GRID(ret, flags, x, y) ^= F_IMPOSSIBLE;
1977             }
1978             move += n;
1979         } else goto badmove;
1980
1981         if (*move == ';')
1982             move++;
1983         else if (*move) goto badmove;
1984     }
1985     if (grid_correct(ret)) ret->completed = 1;
1986     return ret;
1987
1988 badmove:
1989     free_game(ret);
1990     return NULL;
1991 }
1992
1993 /* ----------------------------------------------------------------------
1994  * Drawing routines.
1995  */
1996
1997 /* XXX entirely cloned from fifteen.c; separate out? */
1998 static void game_compute_size(const game_params *params, int tilesize,
1999                               int *x, int *y)
2000 {
2001     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2002     struct { int tilesize; } ads, *ds = &ads;
2003     ads.tilesize = tilesize;
2004
2005     *x = TILE_SIZE * params->w + 2 * BORDER;
2006     *y = TILE_SIZE * params->h + 2 * BORDER;
2007 }
2008
2009 static void game_set_size(drawing *dr, game_drawstate *ds,
2010                           const game_params *params, int tilesize)
2011 {
2012     ds->tilesize = tilesize;
2013     ds->crad = 3*(tilesize-1)/8;
2014 }
2015
2016 static float *game_colours(frontend *fe, int *ncolours)
2017 {
2018     float *ret = snewn(3 * NCOLOURS, float);
2019     int i;
2020
2021     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2022
2023     for (i = 0; i < 3; i++) {
2024         ret[COL_BLACK * 3 + i] = 0.0F;
2025         ret[COL_LIGHT * 3 + i] = 1.0F;
2026         ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F;
2027         ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.5F;
2028
2029     }
2030
2031     ret[COL_ERROR * 3 + 0] = 1.0F;
2032     ret[COL_ERROR * 3 + 1] = 0.25F;
2033     ret[COL_ERROR * 3 + 2] = 0.25F;
2034
2035     ret[COL_LIT * 3 + 0] = 1.0F;
2036     ret[COL_LIT * 3 + 1] = 1.0F;
2037     ret[COL_LIT * 3 + 2] = 0.0F;
2038
2039     *ncolours = NCOLOURS;
2040     return ret;
2041 }
2042
2043 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2044 {
2045     struct game_drawstate *ds = snew(struct game_drawstate);
2046     int i;
2047
2048     ds->tilesize = ds->crad = 0;
2049     ds->w = state->w; ds->h = state->h;
2050
2051     ds->flags = snewn(ds->w*ds->h, unsigned int);
2052     for (i = 0; i < ds->w*ds->h; i++)
2053         ds->flags[i] = -1;
2054
2055     ds->started = 0;
2056
2057     return ds;
2058 }
2059
2060 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2061 {
2062     sfree(ds->flags);
2063     sfree(ds);
2064 }
2065
2066 /* At some stage we should put these into a real options struct.
2067  * Note that tile_redraw has no #ifdeffery; it relies on tile_flags not
2068  * to put those flags in. */
2069 #define HINT_LIGHTS
2070 #define HINT_OVERLAPS
2071 #define HINT_NUMBERS
2072
2073 static unsigned int tile_flags(game_drawstate *ds, const game_state *state,
2074                                const game_ui *ui, int x, int y, int flashing)
2075 {
2076     unsigned int flags = GRID(state, flags, x, y);
2077     int lights = GRID(state, lights, x, y);
2078     unsigned int ret = 0;
2079
2080     if (flashing) ret |= DF_FLASH;
2081     if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
2082         ret |= DF_CURSOR;
2083
2084     if (flags & F_BLACK) {
2085         ret |= DF_BLACK;
2086         if (flags & F_NUMBERED) {
2087 #ifdef HINT_NUMBERS
2088             if (number_wrong(state, x, y))
2089                 ret |= DF_NUMBERWRONG;
2090 #endif
2091             ret |= DF_NUMBERED;
2092         }
2093     } else {
2094 #ifdef HINT_LIGHTS
2095         if (lights > 0) ret |= DF_LIT;
2096 #endif
2097         if (flags & F_LIGHT) {
2098             ret |= DF_LIGHT;
2099 #ifdef HINT_OVERLAPS
2100             if (lights > 1) ret |= DF_OVERLAP;
2101 #endif
2102         }
2103         if (flags & F_IMPOSSIBLE) ret |= DF_IMPOSSIBLE;
2104     }
2105     return ret;
2106 }
2107
2108 static void tile_redraw(drawing *dr, game_drawstate *ds,
2109                         const game_state *state, int x, int y)
2110 {
2111     unsigned int ds_flags = GRID(ds, flags, x, y);
2112     int dx = COORD(x), dy = COORD(y);
2113     int lit = (ds_flags & DF_FLASH) ? COL_GRID : COL_LIT;
2114
2115     if (ds_flags & DF_BLACK) {
2116         draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK);
2117         if (ds_flags & DF_NUMBERED) {
2118             int ccol = (ds_flags & DF_NUMBERWRONG) ? COL_ERROR : COL_LIGHT;
2119             char str[32];
2120
2121             /* We know that this won't change over the course of the game
2122              * so it's OK to ignore this when calculating whether or not
2123              * to redraw the tile. */
2124             sprintf(str, "%d", GRID(state, lights, x, y));
2125             draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2126                       FONT_VARIABLE, TILE_SIZE*3/5,
2127                       ALIGN_VCENTRE | ALIGN_HCENTRE, ccol, str);
2128         }
2129     } else {
2130         draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE,
2131                   (ds_flags & DF_LIT) ? lit : COL_BACKGROUND);
2132         draw_rect_outline(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID);
2133         if (ds_flags & DF_LIGHT) {
2134             int lcol = (ds_flags & DF_OVERLAP) ? COL_ERROR : COL_LIGHT;
2135             draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS,
2136                         lcol, COL_BLACK);
2137         } else if ((ds_flags & DF_IMPOSSIBLE)) {
2138             static int draw_blobs_when_lit = -1;
2139             if (draw_blobs_when_lit < 0) {
2140                 char *env = getenv("LIGHTUP_LIT_BLOBS");
2141                 draw_blobs_when_lit = (!env || (env[0] == 'y' ||
2142                                                 env[0] == 'Y'));
2143             }
2144             if (!(ds_flags & DF_LIT) || draw_blobs_when_lit) {
2145                 int rlen = TILE_SIZE / 4;
2146                 draw_rect(dr, dx + TILE_SIZE/2 - rlen/2,
2147                           dy + TILE_SIZE/2 - rlen/2,
2148                           rlen, rlen, COL_BLACK);
2149             }
2150         }
2151     }
2152
2153     if (ds_flags & DF_CURSOR) {
2154         int coff = TILE_SIZE/8;
2155         draw_rect_outline(dr, dx + coff, dy + coff,
2156                           TILE_SIZE - coff*2, TILE_SIZE - coff*2, COL_CURSOR);
2157     }
2158
2159     draw_update(dr, dx, dy, TILE_SIZE, TILE_SIZE);
2160 }
2161
2162 static void game_redraw(drawing *dr, game_drawstate *ds,
2163                         const game_state *oldstate, const game_state *state,
2164                         int dir, const game_ui *ui,
2165                         float animtime, float flashtime)
2166 {
2167     int flashing = FALSE;
2168     int x,y;
2169
2170     if (flashtime) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
2171
2172     if (!ds->started) {
2173         draw_rect(dr, 0, 0,
2174                   TILE_SIZE * ds->w + 2 * BORDER,
2175                   TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
2176
2177         draw_rect_outline(dr, COORD(0)-1, COORD(0)-1,
2178                           TILE_SIZE * ds->w + 2,
2179                           TILE_SIZE * ds->h + 2,
2180                           COL_GRID);
2181
2182         draw_update(dr, 0, 0,
2183                     TILE_SIZE * ds->w + 2 * BORDER,
2184                     TILE_SIZE * ds->h + 2 * BORDER);
2185         ds->started = 1;
2186     }
2187
2188     for (x = 0; x < ds->w; x++) {
2189         for (y = 0; y < ds->h; y++) {
2190             unsigned int ds_flags = tile_flags(ds, state, ui, x, y, flashing);
2191             if (ds_flags != GRID(ds, flags, x, y)) {
2192                 GRID(ds, flags, x, y) = ds_flags;
2193                 tile_redraw(dr, ds, state, x, y);
2194             }
2195         }
2196     }
2197 }
2198
2199 static float game_anim_length(const game_state *oldstate,
2200                               const game_state *newstate, int dir, game_ui *ui)
2201 {
2202     return 0.0F;
2203 }
2204
2205 static float game_flash_length(const game_state *oldstate,
2206                                const game_state *newstate, int dir, game_ui *ui)
2207 {
2208     if (!oldstate->completed && newstate->completed &&
2209         !oldstate->used_solve && !newstate->used_solve)
2210         return FLASH_TIME;
2211     return 0.0F;
2212 }
2213
2214 static int game_status(const game_state *state)
2215 {
2216     return state->completed ? +1 : 0;
2217 }
2218
2219 static int game_timing_state(const game_state *state, game_ui *ui)
2220 {
2221     return TRUE;
2222 }
2223
2224 static void game_print_size(const game_params *params, float *x, float *y)
2225 {
2226     int pw, ph;
2227
2228     /*
2229      * I'll use 6mm squares by default.
2230      */
2231     game_compute_size(params, 600, &pw, &ph);
2232     *x = pw / 100.0F;
2233     *y = ph / 100.0F;
2234 }
2235
2236 static void game_print(drawing *dr, const game_state *state, int tilesize)
2237 {
2238     int w = state->w, h = state->h;
2239     int ink = print_mono_colour(dr, 0);
2240     int paper = print_mono_colour(dr, 1);
2241     int x, y;
2242
2243     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2244     game_drawstate ads, *ds = &ads;
2245     game_set_size(dr, ds, NULL, tilesize);
2246
2247     /*
2248      * Border.
2249      */
2250     print_line_width(dr, TILE_SIZE / 16);
2251     draw_rect_outline(dr, COORD(0), COORD(0),
2252                       TILE_SIZE * w, TILE_SIZE * h, ink);
2253
2254     /*
2255      * Grid.
2256      */
2257     print_line_width(dr, TILE_SIZE / 24);
2258     for (x = 1; x < w; x++)
2259         draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink);
2260     for (y = 1; y < h; y++)
2261         draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink);
2262
2263     /*
2264      * Grid contents.
2265      */
2266     for (y = 0; y < h; y++)
2267         for (x = 0; x < w; x++) {
2268             unsigned int ds_flags = tile_flags(ds, state, NULL, x, y, FALSE);
2269             int dx = COORD(x), dy = COORD(y);
2270             if (ds_flags & DF_BLACK) {
2271                 draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, ink);
2272                 if (ds_flags & DF_NUMBERED) {
2273                     char str[32];
2274                     sprintf(str, "%d", GRID(state, lights, x, y));
2275                     draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2276                               FONT_VARIABLE, TILE_SIZE*3/5,
2277                               ALIGN_VCENTRE | ALIGN_HCENTRE, paper, str);
2278                 }
2279             } else if (ds_flags & DF_LIGHT) {
2280                 draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2281                             TILE_RADIUS, -1, ink);
2282             }
2283         }
2284 }
2285
2286 #ifdef COMBINED
2287 #define thegame lightup
2288 #endif
2289
2290 const struct game thegame = {
2291     "Light Up", "games.lightup", "lightup",
2292     default_params,
2293     game_fetch_preset,
2294     decode_params,
2295     encode_params,
2296     free_params,
2297     dup_params,
2298     TRUE, game_configure, custom_params,
2299     validate_params,
2300     new_game_desc,
2301     validate_desc,
2302     new_game,
2303     dup_game,
2304     free_game,
2305     TRUE, solve_game,
2306     TRUE, game_can_format_as_text_now, game_text_format,
2307     new_ui,
2308     free_ui,
2309     encode_ui,
2310     decode_ui,
2311     game_changed_state,
2312     interpret_move,
2313     execute_move,
2314     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2315     game_colours,
2316     game_new_drawstate,
2317     game_free_drawstate,
2318     game_redraw,
2319     game_anim_length,
2320     game_flash_length,
2321     game_status,
2322     TRUE, FALSE, game_print_size, game_print,
2323     FALSE,                             /* wants_statusbar */
2324     FALSE, game_timing_state,
2325     0,                                 /* flags */
2326 };
2327
2328 #ifdef STANDALONE_SOLVER
2329
2330 int main(int argc, char **argv)
2331 {
2332     game_params *p;
2333     game_state *s;
2334     char *id = NULL, *desc, *err, *result;
2335     int nsol, diff, really_verbose = 0;
2336     unsigned int sflags;
2337
2338     while (--argc > 0) {
2339         char *p = *++argv;
2340         if (!strcmp(p, "-v")) {
2341             really_verbose++;
2342         } else if (*p == '-') {
2343             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2344             return 1;
2345         } else {
2346             id = p;
2347         }
2348     }
2349
2350     if (!id) {
2351         fprintf(stderr, "usage: %s [-v] <game_id>\n", argv[0]);
2352         return 1;
2353     }
2354
2355     desc = strchr(id, ':');
2356     if (!desc) {
2357         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2358         return 1;
2359     }
2360     *desc++ = '\0';
2361
2362     p = default_params();
2363     decode_params(p, id);
2364     err = validate_desc(p, desc);
2365     if (err) {
2366         fprintf(stderr, "%s: %s\n", argv[0], err);
2367         return 1;
2368     }
2369     s = new_game(NULL, p, desc);
2370
2371     /* Run the solvers easiest to hardest until we find one that
2372      * can solve our puzzle. If it's soluble we know that the
2373      * hardest (recursive) solver will always find the solution. */
2374     nsol = sflags = 0;
2375     for (diff = 0; diff <= DIFFCOUNT; diff++) {
2376         printf("\nSolving with difficulty %d.\n", diff);
2377         sflags = flags_from_difficulty(diff);
2378         unplace_lights(s);
2379         nsol = dosolve(s, sflags, NULL);
2380         if (nsol == 1) break;
2381     }
2382
2383     printf("\n");
2384     if (nsol == 0) {
2385         printf("Puzzle has no solution.\n");
2386     } else if (nsol < 0) {
2387         printf("Unable to find a unique solution.\n");
2388     } else if (nsol > 1) {
2389         printf("Puzzle has multiple solutions.\n");
2390     } else {
2391         verbose = really_verbose;
2392         unplace_lights(s);
2393         printf("Puzzle has difficulty %d: solving...\n", diff);
2394         dosolve(s, sflags, NULL); /* sflags from last successful solve */
2395         result = game_text_format(s);
2396         printf("%s", result);
2397         sfree(result);
2398     }
2399
2400     return 0;
2401 }
2402
2403 #endif
2404
2405 /* vim: set shiftwidth=4 tabstop=8: */