lightup.c

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