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