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 }
 731
 732 /* Fills in all black squares with numbers of adjacent lights. */
 733 static void place_numbers(game_state *state)
 734 {
 735     int x, y, i, n;
 736     surrounds s;
 737
 738     for (x = 0; x < state->w; x++) {
 739         for (y = 0; y < state->h; y++) {
 740             if (!(GRID(state,flags,x,y) & F_BLACK)) continue;
 741             get_surrounds(state, x, y, &s);
 742             n = 0;
 743             for (i = 0; i < s.npoints; i++) {
 744                 if (GRID(state,flags,s.points[i].x, s.points[i].y) & F_LIGHT)
 745                     n++;
 746             }
 747             GRID(state,flags,x,y) |= F_NUMBERED;
 748             GRID(state,lights,x,y) = n;
 749         }
 750     }
 751 }
 752
 753 /* --- Actual solver, with helper subroutines. --- */
 754
 755 static void tsl_callback(game_state *state,
 756                          int lx, int ly, int *x, int *y, int *n)
 757 {
 758     if (GRID(state,flags,lx,ly) & F_IMPOSSIBLE) return;
 759     if (GRID(state,lights,lx,ly) > 0) return;
 760     *x = lx; *y = ly; (*n)++;
 761 }
 762
 763 static int try_solve_light(game_state *state, int ox, int oy,
 764                            unsigned int flags, int lights)
 765 {
 766     ll_data lld;
 767     int sx,sy,n = 0;
 768
 769     if (lights > 0) return 0;
 770     if (flags & F_BLACK) return 0;
 771
 772     /* We have an unlit square; count how many ways there are left to
 773      * place a light that lights us (including this square); if only
 774      * one, we must put a light there. Squares that could light us
 775      * are, of course, the same as the squares we would light... */
 776     list_lights(state, ox, oy, 1, &lld);
 777     FOREACHLIT(&lld, { tsl_callback(state, lx, ly, &sx, &sy, &n); });
 778     if (n == 1) {
 779         set_light(state, sx, sy, 1);
 780 #ifdef SOLVER_DIAGNOSTICS
 781         debug(("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n",
 782                 ox,oy,sx,sy));
 783         if (verbose) debug_state(state);
 784 #endif
 785         return 1;
 786     }
 787
 788     return 0;
 789 }
 790
 791 static int could_place_light(unsigned int flags, int lights)
 792 {
 793     if (flags & (F_BLACK | F_IMPOSSIBLE)) return 0;
 794     return (lights > 0) ? 0 : 1;
 795 }
 796
 797 static int could_place_light_xy(game_state *state, int x, int y)
 798 {
 799     int lights = GRID(state,lights,x,y);
 800     unsigned int flags = GRID(state,flags,x,y);
 801     return (could_place_light(flags, lights)) ? 1 : 0;
 802 }
 803
 804 /* For a given number square, determine whether we have enough info
 805  * to unambiguously place its lights. */
 806 static int try_solve_number(game_state *state, int nx, int ny,
 807                             unsigned int nflags, int nlights)
 808 {
 809     surrounds s;
 810     int x, y, nl, ns, i, ret = 0, lights;
 811     unsigned int flags;
 812
 813     if (!(nflags & F_NUMBERED)) return 0;
 814     nl = nlights;
 815     get_surrounds(state,nx,ny,&s);
 816     ns = s.npoints;
 817
 818     /* nl is no. of lights we need to place, ns is no. of spaces we
 819      * have to place them in. Try and narrow these down, and mark
 820      * points we can ignore later. */
 821     for (i = 0; i < s.npoints; i++) {
 822         x = s.points[i].x; y = s.points[i].y;
 823         flags = GRID(state,flags,x,y);
 824         lights = GRID(state,lights,x,y);
 825         if (flags & F_LIGHT) {
 826             /* light here already; one less light for one less place. */
 827             nl--; ns--;
 828             s.points[i].f |= F_MARK;
 829         } else if (!could_place_light(flags, lights)) {
 830             ns--;
 831             s.points[i].f |= F_MARK;
 832         }
 833     }
 834     if (ns == 0) return 0; /* nowhere to put anything. */
 835     if (nl == 0) {
 836         /* we have placed all lights we need to around here; all remaining
 837          * surrounds are therefore IMPOSSIBLE. */
 838         GRID(state,flags,nx,ny) |= F_NUMBERUSED;
 839         for (i = 0; i < s.npoints; i++) {
 840             if (!(s.points[i].f & F_MARK)) {
 841                 GRID(state,flags,s.points[i].x,s.points[i].y) |= F_IMPOSSIBLE;
 842                 ret = 1;
 843             }
 844         }
 845 #ifdef SOLVER_DIAGNOSTICS
 846         printf("Clue at (%d,%d) full; setting unlit to IMPOSSIBLE.\n",
 847                nx,ny);
 848         if (verbose) debug_state(state);
 849 #endif
 850     } else if (nl == ns) {
 851         /* we have as many lights to place as spaces; fill them all. */
 852         GRID(state,flags,nx,ny) |= F_NUMBERUSED;
 853         for (i = 0; i < s.npoints; i++) {
 854             if (!(s.points[i].f & F_MARK)) {
 855                 set_light(state, s.points[i].x,s.points[i].y, 1);
 856                 ret = 1;
 857             }
 858         }
 859 #ifdef SOLVER_DIAGNOSTICS
 860         printf("Clue at (%d,%d) trivial; setting unlit to LIGHT.\n",
 861                nx,ny);
 862         if (verbose) debug_state(state);
 863 #endif
 864     }
 865     return ret;
 866 }
 867
 868 struct setscratch {
 869     int x, y;
 870     int n;
 871 };
 872
 873 #define SCRATCHSZ (state->w+state->h)
 874
 875 /* New solver algorithm: overlapping sets can add IMPOSSIBLE flags.
 876  * Algorithm thanks to Simon:
 877  *
 878  * (a) Any square where you can place a light has a set of squares
 879  *     which would become non-lights as a result. (This includes
 880  *     squares lit by the first square, and can also include squares
 881  *     adjacent to the same clue square if the new light is the last
 882  *     one around that clue.) Call this MAKESDARK(x,y) with (x,y) being
 883  *     the square you place a light.
 884
 885  * (b) Any unlit square has a set of squares on which you could place
 886  *     a light to illuminate it. (Possibly including itself, of
 887  *     course.) This set of squares has the property that _at least
 888  *     one_ of them must contain a light. Sets of this type also arise
 889  *     from clue squares. Call this MAKESLIGHT(x,y), again with (x,y)
 890  *     the square you would place a light.
 891
 892  * (c) If there exists (dx,dy) and (lx,ly) such that MAKESDARK(dx,dy) is
 893  *     a superset of MAKESLIGHT(lx,ly), this implies that placing a light at
 894  *     (dx,dy) would either leave no remaining way to illuminate a certain
 895  *     square, or would leave no remaining way to fulfill a certain clue
 896  *     (at lx,ly). In either case, a light can be ruled out at that position.
 897  *
 898  * So, we construct all possible MAKESLIGHT sets, both from unlit squares
 899  * and clue squares, and then we look for plausible MAKESDARK sets that include
 900  * our (lx,ly) to see if we can find a (dx,dy) to rule out. By the time we have
 901  * constructed the MAKESLIGHT set we don't care about (lx,ly), just the set
 902  * members.
 903  *
 904  * Once we have such a set, Simon came up with a Cunning Plan to find
 905  * the most sensible MAKESDARK candidate:
 906  *
 907  * (a) for each square S in your set X, find all the squares which _would_
 908  *     rule it out. That means any square which would light S, plus
 909  *     any square adjacent to the same clue square as S (provided
 910  *     that clue square has only one remaining light to be placed).
 911  *     It's not hard to make this list. Don't do anything with this
 912  *     data at the moment except _count_ the squares.
 913
 914  * (b) Find the square S_min in the original set which has the
 915  *     _smallest_ number of other squares which would rule it out.
 916
 917  * (c) Find all the squares that rule out S_min (it's probably
 918  *     better to recompute this than to have stored it during step
 919  *     (a), since the CPU requirement is modest but the storage
 920  *     cost would get ugly.) For each of these squares, see if it
 921  *     rules out everything else in the set X. Any which does can
 922  *     be marked as not-a-light.
 923  *
 924  */
 925
 926 typedef void (*trl_cb)(game_state *state, int dx, int dy,
 927                        struct setscratch *scratch, int n, void *ctx);
 928
 929 static void try_rule_out(game_state *state, int x, int y,
 930                          struct setscratch *scratch, int n,
 931                          trl_cb cb, void *ctx);
 932
 933 static void trl_callback_search(game_state *state, int dx, int dy,
 934                        struct setscratch *scratch, int n, void *ignored)
 935 {
 936     int i;
 937
 938 #ifdef SOLVER_DIAGNOSTICS
 939     if (verbose) debug(("discount cb: light at (%d,%d)\n", dx, dy));
 940 #endif
 941
 942     for (i = 0; i < n; i++) {
 943         if (dx == scratch[i].x && dy == scratch[i].y) {
 944             scratch[i].n = 1;
 945             return;
 946         }
 947     }
 948 }
 949
 950 static void trl_callback_discount(game_state *state, int dx, int dy,
 951                        struct setscratch *scratch, int n, void *ctx)
 952 {
 953     int *didsth = (int *)ctx;
 954     int i;
 955
 956     if (GRID(state,flags,dx,dy) & F_IMPOSSIBLE) {
 957 #ifdef SOLVER_DIAGNOSTICS
 958         debug(("Square at (%d,%d) already impossible.\n", dx,dy));
 959 #endif
 960         return;
 961     }
 962
 963     /* Check whether a light at (dx,dy) rules out everything
 964      * in scratch, and mark (dx,dy) as IMPOSSIBLE if it does.
 965      * We can use try_rule_out for this as well, as the set of
 966      * squares which would rule out (x,y) is the same as the
 967      * set of squares which (x,y) would rule out. */
 968
 969 #ifdef SOLVER_DIAGNOSTICS
 970     if (verbose) debug(("Checking whether light at (%d,%d) rules out everything in scratch.\n", dx, dy));
 971 #endif
 972
 973     for (i = 0; i < n; i++)
 974         scratch[i].n = 0;
 975     try_rule_out(state, dx, dy, scratch, n, trl_callback_search, NULL);
 976     for (i = 0; i < n; i++) {
 977         if (scratch[i].n == 0) return;
 978     }
 979     /* The light ruled out everything in scratch. Yay. */
 980     GRID(state,flags,dx,dy) |= F_IMPOSSIBLE;
 981 #ifdef SOLVER_DIAGNOSTICS
 982     debug(("Set reduction discounted square at (%d,%d):\n", dx,dy));
 983     if (verbose) debug_state(state);
 984 #endif
 985
 986     *didsth = 1;
 987 }
 988
 989 static void trl_callback_incn(game_state *state, int dx, int dy,
 990                        struct setscratch *scratch, int n, void *ctx)
 991 {
 992     struct setscratch *s = (struct setscratch *)ctx;
 993     s->n++;
 994 }
 995
 996 static void try_rule_out(game_state *state, int x, int y,
 997                          struct setscratch *scratch, int n,
 998                          trl_cb cb, void *ctx)
 999 {
1000     /* XXX Find all the squares which would rule out (x,y); anything
1001      * that would light it as well as squares adjacent to same clues
1002      * as X assuming that clue only has one remaining light.
1003      * Call the callback with each square. */
1004     ll_data lld;
1005     surrounds s, ss;
1006     int i, j, curr_lights, tot_lights;
1007
1008     /* Find all squares that would rule out a light at (x,y) and call trl_cb
1009      * with them: anything that would light (x,y)... */
1010
1011     list_lights(state, x, y, 0, &lld);
1012     FOREACHLIT(&lld, { if (could_place_light_xy(state, lx, ly)) { cb(state, lx, ly, scratch, n, ctx); } });
1013
1014     /* ... as well as any empty space (that isn't x,y) next to any clue square
1015      * next to (x,y) that only has one light left to place. */
1016
1017     get_surrounds(state, x, y, &s);
1018     for (i = 0; i < s.npoints; i++) {
1019         if (!GRID(state,flags,s.points[i].x,s.points[i].y) & F_NUMBERED)
1020             continue;
1021         /* we have an adjacent clue square; find /it's/ surrounds
1022          * and count the remaining lights it needs. */
1023         get_surrounds(state,s.points[i].x,s.points[i].y,&ss);
1024         curr_lights = 0;
1025         for (j = 0; j < ss.npoints; j++) {
1026             if (GRID(state,flags,ss.points[j].x,ss.points[j].y) & F_LIGHT)
1027                 curr_lights++;
1028         }
1029         tot_lights = GRID(state, lights, s.points[i].x, s.points[i].y);
1030         /* We have a clue with tot_lights to fill, and curr_lights currently
1031          * around it. If adding a light at (x,y) fills up the clue (i.e.
1032          * curr_lights + 1 = tot_lights) then we need to discount all other
1033          * unlit squares around the clue. */
1034         if ((curr_lights + 1) == tot_lights) {
1035             for (j = 0; j < ss.npoints; j++) {
1036                 int lx = ss.points[j].x, ly = ss.points[j].y;
1037                 if (lx == x && ly == y) continue;
1038                 if (could_place_light_xy(state, lx, ly))
1039                     cb(state, lx, ly, scratch, n, ctx);
1040             }
1041         }
1042     }
1043 }
1044
1045 #ifdef SOLVER_DIAGNOSTICS
1046 static void debug_scratch(const char *msg, struct setscratch *scratch, int n)
1047 {
1048     int i;
1049     debug(("%s scratch (%d elements):\n", msg, n));
1050     for (i = 0; i < n; i++) {
1051         debug(("  (%d,%d) n%d\n", scratch[i].x, scratch[i].y, scratch[i].n));
1052     }
1053 }
1054 #endif
1055
1056 static int discount_set(game_state *state,
1057                         struct setscratch *scratch, int n)
1058 {
1059     int i, besti, bestn, didsth = 0;
1060
1061 #ifdef SOLVER_DIAGNOSTICS
1062     if (verbose > 1) debug_scratch("discount_set", scratch, n);
1063 #endif
1064     if (n == 0) return 0;
1065
1066     for (i = 0; i < n; i++) {
1067         try_rule_out(state, scratch[i].x, scratch[i].y, scratch, n,
1068                      trl_callback_incn, (void*)&(scratch[i]));
1069     }
1070 #ifdef SOLVER_DIAGNOSTICS
1071     if (verbose > 1) debug_scratch("discount_set after count", scratch, n);
1072 #endif
1073
1074     besti = -1; bestn = SCRATCHSZ;
1075     for (i = 0; i < n; i++) {
1076         if (scratch[i].n < bestn) {
1077             bestn = scratch[i].n;
1078             besti = i;
1079         }
1080     }
1081 #ifdef SOLVER_DIAGNOSTICS
1082     if (verbose > 1) debug(("best square (%d,%d) with n%d.\n",
1083            scratch[besti].x, scratch[besti].y, scratch[besti].n));
1084 #endif
1085     try_rule_out(state, scratch[besti].x, scratch[besti].y, scratch, n,
1086                  trl_callback_discount, (void*)&didsth);
1087 #ifdef SOLVER_DIAGNOSTICS
1088     if (didsth) debug((" [from square (%d,%d)]\n",
1089                        scratch[besti].x, scratch[besti].y));
1090 #endif
1091
1092     return didsth;
1093 }
1094
1095 static void discount_clear(game_state *state, struct setscratch *scratch, int *n)
1096 {
1097     *n = 0;
1098     memset(scratch, 0, SCRATCHSZ * sizeof(struct setscratch));
1099 }
1100
1101 static void unlit_cb(game_state *state, int lx, int ly,
1102                      struct setscratch *scratch, int *n)
1103 {
1104     if (could_place_light_xy(state, lx, ly)) {
1105         scratch[*n].x = lx; scratch[*n].y = ly; (*n)++;
1106     }
1107 }
1108
1109 /* Construct a MAKESLIGHT set from an unlit square. */
1110 static int discount_unlit(game_state *state, int x, int y,
1111                           struct setscratch *scratch)
1112 {
1113     ll_data lld;
1114     int n, didsth;
1115
1116 #ifdef SOLVER_DIAGNOSTICS
1117     if (verbose) debug(("Trying to discount for unlit square at (%d,%d).\n", x, y));
1118     if (verbose > 1) debug_state(state);
1119 #endif
1120
1121     discount_clear(state, scratch, &n);
1122
1123     list_lights(state, x, y, 1, &lld);
1124     FOREACHLIT(&lld, { unlit_cb(state, lx, ly, scratch, &n); });
1125     didsth = discount_set(state, scratch, n);
1126 #ifdef SOLVER_DIAGNOSTICS
1127     if (didsth) debug(("  [from unlit square at (%d,%d)].\n", x, y));
1128 #endif
1129     return didsth;
1130
1131 }
1132
1133 /* Construct a series of MAKESLIGHT sets from a clue square.
1134  *  for a clue square with N remaining spaces that must contain M lights, every
1135  *  subset of size N-M+1 of those N spaces forms such a set.
1136  */
1137
1138 static int discount_clue(game_state *state, int x, int y,
1139                           struct setscratch *scratch)
1140 {
1141     int slen, m = GRID(state, lights, x, y), n, i, didsth = 0, lights;
1142     unsigned int flags;
1143     surrounds s, sempty;
1144     combi_ctx *combi;
1145
1146     if (m == 0) return 0;
1147
1148 #ifdef SOLVER_DIAGNOSTICS
1149     if (verbose) debug(("Trying to discount for sets at clue (%d,%d).\n", x, y));
1150     if (verbose > 1) debug_state(state);
1151 #endif
1152
1153     /* m is no. of lights still to place; starts off at the clue value
1154      * and decreases when we find a light already down.
1155      * n is no. of spaces left; starts off at 0 and goes up when we find
1156      * a plausible space. */
1157
1158     get_surrounds(state, x, y, &s);
1159     memset(&sempty, 0, sizeof(surrounds));
1160     for (i = 0; i < s.npoints; i++) {
1161         int lx = s.points[i].x, ly = s.points[i].y;
1162         flags = GRID(state,flags,lx,ly);
1163         lights = GRID(state,lights,lx,ly);
1164
1165         if (flags & F_LIGHT) m--;
1166
1167         if (could_place_light(flags, lights)) {
1168             sempty.points[sempty.npoints].x = lx;
1169             sempty.points[sempty.npoints].y = ly;
1170             sempty.npoints++;
1171         }
1172     }
1173     n = sempty.npoints; /* sempty is now a surrounds of only blank squares. */
1174     if (n == 0) return 0; /* clue is full already. */
1175
1176     if (m < 0 || m > n) return 0; /* become impossible. */
1177
1178     combi = new_combi(n - m + 1, n);
1179     while (next_combi(combi)) {
1180         discount_clear(state, scratch, &slen);
1181         for (i = 0; i < combi->r; i++) {
1182             scratch[slen].x = sempty.points[combi->a[i]].x;
1183             scratch[slen].y = sempty.points[combi->a[i]].y;
1184             slen++;
1185         }
1186         if (discount_set(state, scratch, slen)) didsth = 1;
1187     }
1188     free_combi(combi);
1189 #ifdef SOLVER_DIAGNOSTICS
1190     if (didsth) debug(("  [from clue at (%d,%d)].\n", x, y));
1191 #endif
1192     return didsth;
1193 }
1194
1195 #define F_SOLVE_FORCEUNIQUE     1
1196 #define F_SOLVE_DISCOUNTSETS    2
1197 #define F_SOLVE_ALLOWRECURSE    4
1198
1199 static unsigned int flags_from_difficulty(int difficulty)
1200 {
1201     unsigned int sflags = F_SOLVE_FORCEUNIQUE;
1202     assert(difficulty <= DIFFCOUNT);
1203     if (difficulty >= 1) sflags |= F_SOLVE_DISCOUNTSETS;
1204     if (difficulty >= 2) sflags |= F_SOLVE_ALLOWRECURSE;
1205     return sflags;
1206 }
1207
1208 #define MAXRECURSE 5
1209
1210 static int solve_sub(game_state *state,
1211                      unsigned int solve_flags, int depth,
1212                      int *maxdepth)
1213 {
1214     unsigned int flags;
1215     int x, y, didstuff, ncanplace, lights;
1216     int bestx, besty, n, bestn, copy_soluble, self_soluble, ret, maxrecurse = 0;
1217     game_state *scopy;
1218     ll_data lld;
1219     struct setscratch *sscratch = NULL;
1220
1221 #ifdef SOLVER_DIAGNOSTICS
1222     printf("solve_sub: depth = %d\n", depth);
1223 #endif
1224     if (maxdepth && *maxdepth < depth) *maxdepth = depth;
1225     if (solve_flags & F_SOLVE_ALLOWRECURSE) maxrecurse = MAXRECURSE;
1226
1227     while (1) {
1228         if (grid_overlap(state)) {
1229             /* Our own solver, from scratch, should never cause this to happen
1230              * (assuming a soluble grid). However, if we're trying to solve
1231              * from a half-completed *incorrect* grid this might occur; we
1232              * just return the 'no solutions' code in this case. */
1233             ret = 0; goto done;
1234         }
1235
1236         if (grid_correct(state)) { ret = 1; goto done; }
1237
1238         ncanplace = 0;
1239         didstuff = 0;
1240         /* These 2 loops, and the functions they call, are the critical loops
1241          * for timing; any optimisations should look here first. */
1242         for (x = 0; x < state->w; x++) {
1243             for (y = 0; y < state->h; y++) {
1244                 flags = GRID(state,flags,x,y);
1245                 lights = GRID(state,lights,x,y);
1246                 ncanplace += could_place_light(flags, lights);
1247
1248                 if (try_solve_light(state, x, y, flags, lights)) didstuff = 1;
1249                 if (try_solve_number(state, x, y, flags, lights)) didstuff = 1;
1250             }
1251         }
1252         if (didstuff) continue;
1253         if (!ncanplace) {
1254             /* nowhere to put a light, puzzle is unsoluble. */
1255             ret = 0; goto done;
1256         }
1257
1258         if (solve_flags & F_SOLVE_DISCOUNTSETS) {
1259             if (!sscratch) sscratch = snewn(SCRATCHSZ, struct setscratch);
1260             /* Try a more cunning (and more involved) way... more details above. */
1261             for (x = 0; x < state->w; x++) {
1262                 for (y = 0; y < state->h; y++) {
1263                     flags = GRID(state,flags,x,y);
1264                     lights = GRID(state,lights,x,y);
1265
1266                     if (!(flags & F_BLACK) && lights == 0) {
1267                         if (discount_unlit(state, x, y, sscratch)) {
1268                             didstuff = 1;
1269                             goto reduction_success;
1270                         }
1271                     } else if (flags & F_NUMBERED) {
1272                         if (discount_clue(state, x, y, sscratch)) {
1273                             didstuff = 1;
1274                             goto reduction_success;
1275                         }
1276                     }
1277                 }
1278             }
1279         }
1280 reduction_success:
1281         if (didstuff) continue;
1282
1283         /* We now have to make a guess; we have places to put lights but
1284          * no definite idea about where they can go. */
1285         if (depth >= maxrecurse) {
1286             /* mustn't delve any deeper. */
1287             ret = -1; goto done;
1288         }
1289         /* Of all the squares that we could place a light, pick the one
1290          * that would light the most currently unlit squares. */
1291         /* This heuristic was just plucked from the air; there may well be
1292          * a more efficient way of choosing a square to flip to minimise
1293          * recursion. */
1294         bestn = 0;
1295         bestx = besty = -1; /* suyb */
1296         for (x = 0; x < state->w; x++) {
1297             for (y = 0; y < state->h; y++) {
1298                 flags = GRID(state,flags,x,y);
1299                 lights = GRID(state,lights,x,y);
1300                 if (!could_place_light(flags, lights)) continue;
1301
1302                 n = 0;
1303                 list_lights(state, x, y, 1, &lld);
1304                 FOREACHLIT(&lld, { if (GRID(state,lights,lx,ly) == 0) n++; });
1305                 if (n > bestn) {
1306                     bestn = n; bestx = x; besty = y;
1307                 }
1308             }
1309         }
1310         assert(bestn > 0);
1311         assert(bestx >= 0 && besty >= 0);
1312
1313         /* Now we've chosen a plausible (x,y), try to solve it once as 'lit'
1314          * and once as 'impossible'; we need to make one copy to do this. */
1315
1316         scopy = dup_game(state);
1317 #ifdef SOLVER_DIAGNOSTICS
1318         debug(("Recursing #1: trying (%d,%d) as IMPOSSIBLE\n", bestx, besty));
1319 #endif
1320         GRID(state,flags,bestx,besty) |= F_IMPOSSIBLE;
1321         self_soluble = solve_sub(state, solve_flags,  depth+1, maxdepth);
1322
1323         if (!(solve_flags & F_SOLVE_FORCEUNIQUE) && self_soluble > 0) {
1324             /* we didn't care about finding all solutions, and we just
1325              * found one; return with it immediately. */
1326             free_game(scopy);
1327             ret = self_soluble;
1328             goto done;
1329         }
1330
1331 #ifdef SOLVER_DIAGNOSTICS
1332         debug(("Recursing #2: trying (%d,%d) as LIGHT\n", bestx, besty));
1333 #endif
1334         set_light(scopy, bestx, besty, 1);
1335         copy_soluble = solve_sub(scopy, solve_flags, depth+1, maxdepth);
1336
1337         /* If we wanted a unique solution but we hit our recursion limit
1338          * (on either branch) then we have to assume we didn't find possible
1339          * extra solutions, and return 'not soluble'. */
1340         if ((solve_flags & F_SOLVE_FORCEUNIQUE) &&
1341             ((copy_soluble < 0) || (self_soluble < 0))) {
1342             ret = -1;
1343         /* Make sure that whether or not it was self or copy (or both) that
1344          * were soluble, that we return a solved state in self. */
1345         } else if (copy_soluble <= 0) {
1346             /* copy wasn't soluble; keep self state and return that result. */
1347             ret = self_soluble;
1348         } else if (self_soluble <= 0) {
1349             /* copy solved and we didn't, so copy in copy's (now solved)
1350              * flags and light state. */
1351             memcpy(state->lights, scopy->lights,
1352                    scopy->w * scopy->h * sizeof(int));
1353             memcpy(state->flags, scopy->flags,
1354                    scopy->w * scopy->h * sizeof(unsigned int));
1355             ret = copy_soluble;
1356         } else {
1357             ret = copy_soluble + self_soluble;
1358         }
1359         free_game(scopy);
1360         goto done;
1361     }
1362 done:
1363     if (sscratch) sfree(sscratch);
1364 #ifdef SOLVER_DIAGNOSTICS
1365     if (ret < 0)
1366         debug(("solve_sub: depth = %d returning, ran out of recursion.\n",
1367                depth));
1368     else
1369         debug(("solve_sub: depth = %d returning, %d solutions.\n",
1370                depth, ret));
1371 #endif
1372     return ret;
1373 }
1374
1375 /* Fills in the (possibly partially-complete) game_state as far as it can,
1376  * returning the number of possible solutions. If it returns >0 then the
1377  * game_state will be in a solved state, but you won't know which one. */
1378 static int dosolve(game_state *state, int solve_flags, int *maxdepth)
1379 {
1380     int x, y, nsol;
1381
1382     for (x = 0; x < state->w; x++) {
1383         for (y = 0; y < state->h; y++) {
1384             GRID(state,flags,x,y) &= ~F_NUMBERUSED;
1385         }
1386     }
1387     nsol = solve_sub(state, solve_flags, 0, maxdepth);
1388     return nsol;
1389 }
1390
1391 static int strip_unused_nums(game_state *state)
1392 {
1393     int x,y,n=0;
1394     for (x = 0; x < state->w; x++) {
1395         for (y = 0; y < state->h; y++) {
1396             if ((GRID(state,flags,x,y) & F_NUMBERED) &&
1397                 !(GRID(state,flags,x,y) & F_NUMBERUSED)) {
1398                 GRID(state,flags,x,y) &= ~F_NUMBERED;
1399                 GRID(state,lights,x,y) = 0;
1400                 n++;
1401             }
1402         }
1403     }
1404     return n;
1405 }
1406
1407 static void unplace_lights(game_state *state)
1408 {
1409     int x,y;
1410     for (x = 0; x < state->w; x++) {
1411         for (y = 0; y < state->h; y++) {
1412             if (GRID(state,flags,x,y) & F_LIGHT)
1413                 set_light(state,x,y,0);
1414             GRID(state,flags,x,y) &= ~F_IMPOSSIBLE;
1415             GRID(state,flags,x,y) &= ~F_NUMBERUSED;
1416         }
1417     }
1418 }
1419
1420 static int puzzle_is_good(game_state *state, int difficulty)
1421 {
1422     int nsol, mdepth = 0;
1423     unsigned int sflags = flags_from_difficulty(difficulty);
1424
1425     unplace_lights(state);
1426
1427 #ifdef SOLVER_DIAGNOSTICS
1428     debug(("Trying to solve with difficulty %d (0x%x):\n",
1429            difficulty, sflags));
1430     if (verbose) debug_state(state);
1431 #endif
1432
1433     nsol = dosolve(state, sflags, &mdepth);
1434     /* if we wanted an easy puzzle, make sure we didn't need recursion. */
1435     if (!(sflags & F_SOLVE_ALLOWRECURSE) && mdepth > 0) {
1436         debug(("Ignoring recursive puzzle.\n"));
1437         return 0;
1438     }
1439
1440     debug(("%d solutions found.\n", nsol));
1441     if (nsol <= 0) return 0;
1442     if (nsol > 1) return 0;
1443     return 1;
1444 }
1445
1446 /* --- New game creation and user input code. --- */
1447
1448 /* The basic algorithm here is to generate the most complex grid possible
1449  * while honouring two restrictions:
1450  *
1451  *  * we require a unique solution, and
1452  *  * either we require solubility with no recursion (!params->recurse)
1453  *  * or we require some recursion. (params->recurse).
1454  *
1455  * The solver helpfully keeps track of the numbers it needed to use to
1456  * get its solution, so we use that to remove an initial set of numbers
1457  * and check we still satsify our requirements (on uniqueness and
1458  * non-recursiveness, if applicable; we don't check explicit recursiveness
1459  * until the end).
1460  *
1461  * Then we try to remove all numbers in a random order, and see if we
1462  * still satisfy requirements (putting them back if we didn't).
1463  *
1464  * Removing numbers will always, in general terms, make a puzzle require
1465  * more recursion but it may also mean a puzzle becomes non-unique.
1466  *
1467  * Once we're done, if we wanted a recursive puzzle but the most difficult
1468  * puzzle we could come up with was non-recursive, we give up and try a new
1469  * grid. */
1470
1471 #define MAX_GRIDGEN_TRIES 20
1472
1473 static char *new_game_desc(game_params *params, random_state *rs,
1474                            char **aux, int interactive)
1475 {
1476     game_state *news = new_state(params), *copys;
1477     int nsol, i, j, run, x, y, wh = params->w*params->h, num;
1478     char *ret, *p;
1479     int *numindices;
1480
1481     /* Construct a shuffled list of grid positions; we only
1482      * do this once, because if it gets used more than once it'll
1483      * be on a different grid layout. */
1484     numindices = snewn(wh, int);
1485     for (j = 0; j < wh; j++) numindices[j] = j;
1486     shuffle(numindices, wh, sizeof(*numindices), rs);
1487
1488     while (1) {
1489         for (i = 0; i < MAX_GRIDGEN_TRIES; i++) {
1490             set_blacks(news, params, rs); /* also cleans board. */
1491
1492             /* set up lights and then the numbers, and remove the lights */
1493             place_lights(news, rs);
1494             debug(("Generating initial grid.\n"));
1495             place_numbers(news);
1496             if (!puzzle_is_good(news, params->difficulty)) continue;
1497
1498             /* Take a copy, remove numbers we didn't use and check there's
1499              * still a unique solution; if so, use the copy subsequently. */
1500             copys = dup_game(news);
1501             nsol = strip_unused_nums(copys);
1502             debug(("Stripped %d unused numbers.\n", nsol));
1503             if (!puzzle_is_good(copys, params->difficulty)) {
1504                 debug(("Stripped grid is not good, reverting.\n"));
1505                 free_game(copys);
1506             } else {
1507                 free_game(news);
1508                 news = copys;
1509             }
1510
1511             /* Go through grid removing numbers at random one-by-one and
1512              * trying to solve again; if it ceases to be good put the number back. */
1513             for (j = 0; j < wh; j++) {
1514                 y = numindices[j] / params->w;
1515                 x = numindices[j] % params->w;
1516                 if (!(GRID(news, flags, x, y) & F_NUMBERED)) continue;
1517                 num = GRID(news, lights, x, y);
1518                 GRID(news, lights, x, y) = 0;
1519                 GRID(news, flags, x, y) &= ~F_NUMBERED;
1520                 if (!puzzle_is_good(news, params->difficulty)) {
1521                     GRID(news, lights, x, y) = num;
1522                     GRID(news, flags, x, y) |= F_NUMBERED;
1523                 } else
1524                     debug(("Removed (%d,%d) still soluble.\n", x, y));
1525             }
1526             if (params->difficulty > 0) {
1527                 /* Was the maximally-difficult puzzle difficult enough?
1528                  * Check we can't solve it with a more simplistic solver. */
1529                 if (puzzle_is_good(news, params->difficulty-1)) {
1530                     debug(("Maximally-hard puzzle still not hard enough, skipping.\n"));
1531                     continue;
1532                 }
1533             }
1534
1535             goto goodpuzzle;
1536         }
1537         /* Couldn't generate a good puzzle in however many goes. Ramp up the
1538          * %age of black squares (if we didn't already have lots; in which case
1539          * why couldn't we generate a puzzle?) and try again. */
1540         if (params->blackpc < 90) params->blackpc += 5;
1541         debug(("New black layout %d%%.\n", params->blackpc));
1542     }
1543 goodpuzzle:
1544     /* Game is encoded as a long string one character per square;
1545      * 'S' is a space
1546      * 'B' is a black square with no number
1547      * '0', '1', '2', '3', '4' is a black square with a number. */
1548     ret = snewn((params->w * params->h) + 1, char);
1549     p = ret;
1550     run = 0;
1551     for (y = 0; y < params->h; y++) {
1552         for (x = 0; x < params->w; x++) {
1553             if (GRID(news,flags,x,y) & F_BLACK) {
1554                 if (run) {
1555                     *p++ = ('a'-1) + run;
1556                     run = 0;
1557                 }
1558                 if (GRID(news,flags,x,y) & F_NUMBERED)
1559                     *p++ = '0' + GRID(news,lights,x,y);
1560                 else
1561                     *p++ = 'B';
1562             } else {
1563                 if (run == 26) {
1564                     *p++ = ('a'-1) + run;
1565                     run = 0;
1566                 }
1567                 run++;
1568             }
1569         }
1570     }
1571     if (run) {
1572         *p++ = ('a'-1) + run;
1573         run = 0;
1574     }
1575     *p = '\0';
1576     assert(p - ret <= params->w * params->h);
1577     free_game(news);
1578     sfree(numindices);
1579
1580     return ret;
1581 }
1582
1583 static char *validate_desc(game_params *params, char *desc)
1584 {
1585     int i;
1586     for (i = 0; i < params->w*params->h; i++) {
1587         if (*desc >= '0' && *desc <= '4')
1588             /* OK */;
1589         else if (*desc == 'B')
1590             /* OK */;
1591         else if (*desc >= 'a' && *desc <= 'z')
1592             i += *desc - 'a';          /* and the i++ will add another one */
1593         else if (!*desc)
1594             return "Game description shorter than expected";
1595         else
1596             return "Game description contained unexpected character";
1597         desc++;
1598     }
1599     if (*desc || i > params->w*params->h)
1600         return "Game description longer than expected";
1601
1602     return NULL;
1603 }
1604
1605 static game_state *new_game(midend *me, game_params *params, char *desc)
1606 {
1607     game_state *ret = new_state(params);
1608     int x,y;
1609     int run = 0;
1610
1611     for (y = 0; y < params->h; y++) {
1612         for (x = 0; x < params->w; x++) {
1613             char c = '\0';
1614
1615             if (run == 0) {
1616                 c = *desc++;
1617                 assert(c != 'S');
1618                 if (c >= 'a' && c <= 'z')
1619                     run = c - 'a' + 1;
1620             }
1621
1622             if (run > 0) {
1623                 c = 'S';
1624                 run--;
1625             }
1626
1627             switch (c) {
1628               case '0': case '1': case '2': case '3': case '4':
1629                 GRID(ret,flags,x,y) |= F_NUMBERED;
1630                 GRID(ret,lights,x,y) = (c - '0');
1631                 /* run-on... */
1632
1633               case 'B':
1634                 GRID(ret,flags,x,y) |= F_BLACK;
1635                 break;
1636
1637               case 'S':
1638                 /* empty square */
1639                 break;
1640
1641               default:
1642                 assert(!"Malformed desc.");
1643                 break;
1644             }
1645         }
1646     }
1647     if (*desc) assert(!"Over-long desc.");
1648
1649     return ret;
1650 }
1651
1652 static char *solve_game(game_state *state, game_state *currstate,
1653                         char *aux, char **error)
1654 {
1655     game_state *solved;
1656     char *move = NULL, buf[80];
1657     int movelen, movesize, x, y, len;
1658     unsigned int oldflags, solvedflags, sflags;
1659
1660     /* We don't care here about non-unique puzzles; if the
1661      * user entered one themself then I doubt they care. */
1662
1663     sflags = F_SOLVE_ALLOWRECURSE | F_SOLVE_DISCOUNTSETS;
1664
1665     /* Try and solve from where we are now (for non-unique
1666      * puzzles this may produce a different answer). */
1667     solved = dup_game(currstate);
1668     if (dosolve(solved, sflags, NULL) > 0) goto solved;
1669     free_game(solved);
1670
1671     /* That didn't work; try solving from the clean puzzle. */
1672     solved = dup_game(state);
1673     if (dosolve(solved, sflags, NULL) > 0) goto solved;
1674     *error = "Puzzle is not self-consistent.";
1675     goto done;
1676
1677 solved:
1678     movesize = 256;
1679     move = snewn(movesize, char);
1680     movelen = 0;
1681     move[movelen++] = 'S';
1682     move[movelen] = '\0';
1683     for (x = 0; x < currstate->w; x++) {
1684         for (y = 0; y < currstate->h; y++) {
1685             len = 0;
1686             oldflags = GRID(currstate, flags, x, y);
1687             solvedflags = GRID(solved, flags, x, y);
1688             if ((oldflags & F_LIGHT) != (solvedflags & F_LIGHT))
1689                 len = sprintf(buf, ";L%d,%d", x, y);
1690             else if ((oldflags & F_IMPOSSIBLE) != (solvedflags & F_IMPOSSIBLE))
1691                 len = sprintf(buf, ";I%d,%d", x, y);
1692             if (len) {
1693                 if (movelen + len >= movesize) {
1694                     movesize = movelen + len + 256;
1695                     move = sresize(move, movesize, char);
1696                 }
1697                 strcpy(move + movelen, buf);
1698                 movelen += len;
1699             }
1700         }
1701     }
1702
1703 done:
1704     free_game(solved);
1705     return move;
1706 }
1707
1708 /* 'borrowed' from slant.c, mainly. I could have printed it one
1709  * character per cell (like debug_state) but that comes out tiny.
1710  * 'L' is used for 'light here' because 'O' looks too much like '0'
1711  * (black square with no surrounding lights). */
1712 static char *game_text_format(game_state *state)
1713 {
1714     int w = state->w, h = state->h, W = w+1, H = h+1;
1715     int x, y, len, lights;
1716     unsigned int flags;
1717     char *ret, *p;
1718
1719     len = (h+H) * (w+W+1) + 1;
1720     ret = snewn(len, char);
1721     p = ret;
1722
1723     for (y = 0; y < H; y++) {
1724         for (x = 0; x < W; x++) {
1725             *p++ = '+';
1726             if (x < w)
1727                 *p++ = '-';
1728         }
1729         *p++ = '\n';
1730         if (y < h) {
1731             for (x = 0; x < W; x++) {
1732                 *p++ = '|';
1733                 if (x < w) {
1734                     /* actual interesting bit. */
1735                     flags = GRID(state, flags, x, y);
1736                     lights = GRID(state, lights, x, y);
1737                     if (flags & F_BLACK) {
1738                         if (flags & F_NUMBERED)
1739                             *p++ = '0' + lights;
1740                         else
1741                             *p++ = '#';
1742                     } else {
1743                         if (flags & F_LIGHT)
1744                             *p++ = 'L';
1745                         else if (flags & F_IMPOSSIBLE)
1746                             *p++ = 'x';
1747                         else if (lights > 0)
1748                             *p++ = '.';
1749                         else
1750                             *p++ = ' ';
1751                     }
1752                 }
1753             }
1754             *p++ = '\n';
1755         }
1756     }
1757     *p++ = '\0';
1758
1759     assert(p - ret == len);
1760     return ret;
1761 }
1762
1763 struct game_ui {
1764     int cur_x, cur_y, cur_visible;
1765 };
1766
1767 static game_ui *new_ui(game_state *state)
1768 {
1769     game_ui *ui = snew(game_ui);
1770     ui->cur_x = ui->cur_y = ui->cur_visible = 0;
1771     return ui;
1772 }
1773
1774 static void free_ui(game_ui *ui)
1775 {
1776     sfree(ui);
1777 }
1778
1779 static char *encode_ui(game_ui *ui)
1780 {
1781     /* nothing to encode. */
1782     return NULL;
1783 }
1784
1785 static void decode_ui(game_ui *ui, char *encoding)
1786 {
1787     /* nothing to decode. */
1788 }
1789
1790 static void game_changed_state(game_ui *ui, game_state *oldstate,
1791                                game_state *newstate)
1792 {
1793     if (newstate->completed)
1794         ui->cur_visible = 0;
1795 }
1796
1797 #define DF_BLACK        1       /* black square */
1798 #define DF_NUMBERED     2       /* black square with number */
1799 #define DF_LIT          4       /* display (white) square lit up */
1800 #define DF_LIGHT        8       /* display light in square */
1801 #define DF_OVERLAP      16      /* display light as overlapped */
1802 #define DF_CURSOR       32      /* display cursor */
1803 #define DF_NUMBERWRONG  64      /* display black numbered square as error. */
1804 #define DF_FLASH        128     /* background flash is on. */
1805 #define DF_IMPOSSIBLE   256     /* display non-light little square */
1806
1807 struct game_drawstate {
1808     int tilesize, crad;
1809     int w, h;
1810     unsigned int *flags;         /* width * height */
1811     int started;
1812 };
1813
1814
1815 /* Believe it or not, this empty = "" hack is needed to get around a bug in
1816  * the prc-tools gcc when optimisation is turned on; before, it produced:
1817     lightup-sect.c: In function `interpret_move':
1818     lightup-sect.c:1416: internal error--unrecognizable insn:
1819     (insn 582 580 583 (set (reg:SI 134)
1820             (pc)) -1 (nil)
1821         (nil))
1822  */
1823 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1824                             int x, int y, int button)
1825 {
1826     enum { NONE, FLIP_LIGHT, FLIP_IMPOSSIBLE } action = NONE;
1827     int cx = -1, cy = -1;
1828     unsigned int flags;
1829     char buf[80], *nullret = NULL, *empty = "", c;
1830
1831     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1832         if (ui->cur_visible)
1833             nullret = empty;
1834         ui->cur_visible = 0;
1835         cx = FROMCOORD(x);
1836         cy = FROMCOORD(y);
1837         action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE;
1838     } else if (button == CURSOR_SELECT ||
1839                button == 'i' || button == 'I' ||
1840                button == ' ' || button == '\r' || button == '\n') {
1841         ui->cur_visible = 1;
1842         cx = ui->cur_x;
1843         cy = ui->cur_y;
1844         action = (button == 'i' || button == 'I') ?
1845             FLIP_IMPOSSIBLE : FLIP_LIGHT;
1846     } else if (button == CURSOR_UP || button == CURSOR_DOWN ||
1847                button == CURSOR_RIGHT || button == CURSOR_LEFT) {
1848         int dx = 0, dy = 0;
1849         switch (button) {
1850         case CURSOR_UP:         dy = -1; break;
1851         case CURSOR_DOWN:       dy = 1; break;
1852         case CURSOR_RIGHT:      dx = 1; break;
1853         case CURSOR_LEFT:       dx = -1; break;
1854         default: assert(!"shouldn't get here");
1855         }
1856         ui->cur_x += dx; ui->cur_y += dy;
1857         ui->cur_x = min(max(ui->cur_x, 0), state->w - 1);
1858         ui->cur_y = min(max(ui->cur_y, 0), state->h - 1);
1859         ui->cur_visible = 1;
1860         nullret = empty;
1861     } else
1862         return NULL;
1863
1864     switch (action) {
1865     case FLIP_LIGHT:
1866     case FLIP_IMPOSSIBLE:
1867         if (cx < 0 || cy < 0 || cx >= state->w || cy >= state->h)
1868             return nullret;
1869         flags = GRID(state, flags, cx, cy);
1870         if (flags & F_BLACK)
1871             return nullret;
1872         if (action == FLIP_LIGHT) {
1873             if (flags & F_IMPOSSIBLE) return nullret;
1874             c = 'L';
1875         } else {
1876             if (flags & F_LIGHT) return nullret;
1877             c = 'I';
1878         }
1879         sprintf(buf, "%c%d,%d", (int)c, cx, cy);
1880         break;
1881
1882     case NONE:
1883         return nullret;
1884
1885     default:
1886         assert(!"Shouldn't get here!");
1887     }
1888     return dupstr(buf);
1889 }
1890
1891 static game_state *execute_move(game_state *state, char *move)
1892 {
1893     game_state *ret = dup_game(state);
1894     int x, y, n, flags;
1895     char c;
1896
1897     if (!*move) goto badmove;
1898
1899     while (*move) {
1900         c = *move;
1901         if (c == 'S') {
1902             ret->used_solve = TRUE;
1903             move++;
1904         } else if (c == 'L' || c == 'I') {
1905             move++;
1906             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1907                 x < 0 || y < 0 || x >= ret->w || y >= ret->h)
1908                 goto badmove;
1909
1910             flags = GRID(ret, flags, x, y);
1911             if (flags & F_BLACK) goto badmove;
1912
1913             /* LIGHT and IMPOSSIBLE are mutually exclusive. */
1914             if (c == 'L') {
1915                 GRID(ret, flags, x, y) &= ~F_IMPOSSIBLE;
1916                 set_light(ret, x, y, (flags & F_LIGHT) ? 0 : 1);
1917             } else {
1918                 set_light(ret, x, y, 0);
1919                 GRID(ret, flags, x, y) ^= F_IMPOSSIBLE;
1920             }
1921             move += n;
1922         } else goto badmove;
1923
1924         if (*move == ';')
1925             move++;
1926         else if (*move) goto badmove;
1927     }
1928     if (grid_correct(ret)) ret->completed = 1;
1929     return ret;
1930
1931 badmove:
1932     free_game(ret);
1933     return NULL;
1934 }
1935
1936 /* ----------------------------------------------------------------------
1937  * Drawing routines.
1938  */
1939
1940 /* XXX entirely cloned from fifteen.c; separate out? */
1941 static void game_compute_size(game_params *params, int tilesize,
1942                               int *x, int *y)
1943 {
1944     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1945     struct { int tilesize; } ads, *ds = &ads;
1946     ads.tilesize = tilesize;
1947
1948     *x = TILE_SIZE * params->w + 2 * BORDER;
1949     *y = TILE_SIZE * params->h + 2 * BORDER;
1950 }
1951
1952 static void game_set_size(drawing *dr, game_drawstate *ds,
1953                           game_params *params, int tilesize)
1954 {
1955     ds->tilesize = tilesize;
1956     ds->crad = 3*(tilesize-1)/8;
1957 }
1958
1959 static float *game_colours(frontend *fe, int *ncolours)
1960 {
1961     float *ret = snewn(3 * NCOLOURS, float);
1962     int i;
1963
1964     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1965
1966     for (i = 0; i < 3; i++) {
1967         ret[COL_BLACK * 3 + i] = 0.0F;
1968         ret[COL_LIGHT * 3 + i] = 1.0F;
1969         ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F;
1970         ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.5F;
1971
1972     }
1973
1974     ret[COL_ERROR * 3 + 0] = 1.0F;
1975     ret[COL_ERROR * 3 + 1] = 0.25F;
1976     ret[COL_ERROR * 3 + 2] = 0.25F;
1977
1978     ret[COL_LIT * 3 + 0] = 1.0F;
1979     ret[COL_LIT * 3 + 1] = 1.0F;
1980     ret[COL_LIT * 3 + 2] = 0.0F;
1981
1982     *ncolours = NCOLOURS;
1983     return ret;
1984 }
1985
1986 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1987 {
1988     struct game_drawstate *ds = snew(struct game_drawstate);
1989     int i;
1990
1991     ds->tilesize = ds->crad = 0;
1992     ds->w = state->w; ds->h = state->h;
1993
1994     ds->flags = snewn(ds->w*ds->h, unsigned int);
1995     for (i = 0; i < ds->w*ds->h; i++)
1996         ds->flags[i] = -1;
1997
1998     ds->started = 0;
1999
2000     return ds;
2001 }
2002
2003 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2004 {
2005     sfree(ds->flags);
2006     sfree(ds);
2007 }
2008
2009 /* At some stage we should put these into a real options struct.
2010  * Note that tile_redraw has no #ifdeffery; it relies on tile_flags not
2011  * to put those flags in. */
2012 #define HINT_LIGHTS
2013 #define HINT_OVERLAPS
2014 #define HINT_NUMBERS
2015
2016 static unsigned int tile_flags(game_drawstate *ds, game_state *state, game_ui *ui,
2017                                int x, int y, int flashing)
2018 {
2019     unsigned int flags = GRID(state, flags, x, y);
2020     int lights = GRID(state, lights, x, y);
2021     unsigned int ret = 0;
2022
2023     if (flashing) ret |= DF_FLASH;
2024     if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
2025         ret |= DF_CURSOR;
2026
2027     if (flags & F_BLACK) {
2028         ret |= DF_BLACK;
2029         if (flags & F_NUMBERED) {
2030 #ifdef HINT_NUMBERS
2031             if (number_wrong(state, x, y))
2032                 ret |= DF_NUMBERWRONG;
2033 #endif
2034             ret |= DF_NUMBERED;
2035         }
2036     } else {
2037 #ifdef HINT_LIGHTS
2038         if (lights > 0) ret |= DF_LIT;
2039 #endif
2040         if (flags & F_LIGHT) {
2041             ret |= DF_LIGHT;
2042 #ifdef HINT_OVERLAPS
2043             if (lights > 1) ret |= DF_OVERLAP;
2044 #endif
2045         }
2046         if (flags & F_IMPOSSIBLE) ret |= DF_IMPOSSIBLE;
2047     }
2048     return ret;
2049 }
2050
2051 static void tile_redraw(drawing *dr, game_drawstate *ds, game_state *state,
2052                         int x, int y)
2053 {
2054     unsigned int ds_flags = GRID(ds, flags, x, y);
2055     int dx = COORD(x), dy = COORD(y);
2056     int lit = (ds_flags & DF_FLASH) ? COL_GRID : COL_LIT;
2057
2058     if (ds_flags & DF_BLACK) {
2059         draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK);
2060         if (ds_flags & DF_NUMBERED) {
2061             int ccol = (ds_flags & DF_NUMBERWRONG) ? COL_ERROR : COL_LIGHT;
2062             char str[10];
2063
2064             /* We know that this won't change over the course of the game
2065              * so it's OK to ignore this when calculating whether or not
2066              * to redraw the tile. */
2067             sprintf(str, "%d", GRID(state, lights, x, y));
2068             draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2069                       FONT_VARIABLE, TILE_SIZE*3/5,
2070                       ALIGN_VCENTRE | ALIGN_HCENTRE, ccol, str);
2071         }
2072     } else {
2073         draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE,
2074                   (ds_flags & DF_LIT) ? lit : COL_BACKGROUND);
2075         draw_rect_outline(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID);
2076         if (ds_flags & DF_LIGHT) {
2077             int lcol = (ds_flags & DF_OVERLAP) ? COL_ERROR : COL_LIGHT;
2078             draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS,
2079                         lcol, COL_BLACK);
2080         } else if (ds_flags & DF_IMPOSSIBLE) {
2081             int rlen = TILE_SIZE / 4;
2082             draw_rect(dr, dx + TILE_SIZE/2 - rlen/2, dy + TILE_SIZE/2 - rlen/2,
2083                       rlen, rlen, COL_BLACK);
2084         }
2085     }
2086
2087     if (ds_flags & DF_CURSOR) {
2088         int coff = TILE_SIZE/8;
2089         draw_rect_outline(dr, dx + coff, dy + coff,
2090                           TILE_SIZE - coff*2, TILE_SIZE - coff*2, COL_CURSOR);
2091     }
2092
2093     draw_update(dr, dx, dy, TILE_SIZE, TILE_SIZE);
2094 }
2095
2096 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2097                         game_state *state, int dir, game_ui *ui,
2098                         float animtime, float flashtime)
2099 {
2100     int flashing = FALSE;
2101     int x,y;
2102
2103     if (flashtime) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
2104
2105     if (!ds->started) {
2106         draw_rect(dr, 0, 0,
2107                   TILE_SIZE * ds->w + 2 * BORDER,
2108                   TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
2109
2110         draw_rect_outline(dr, COORD(0)-1, COORD(0)-1,
2111                           TILE_SIZE * ds->w + 2,
2112                           TILE_SIZE * ds->h + 2,
2113                           COL_GRID);
2114
2115         draw_update(dr, 0, 0,
2116                     TILE_SIZE * ds->w + 2 * BORDER,
2117                     TILE_SIZE * ds->h + 2 * BORDER);
2118         ds->started = 1;
2119     }
2120
2121     for (x = 0; x < ds->w; x++) {
2122         for (y = 0; y < ds->h; y++) {
2123             unsigned int ds_flags = tile_flags(ds, state, ui, x, y, flashing);
2124             if (ds_flags != GRID(ds, flags, x, y)) {
2125                 GRID(ds, flags, x, y) = ds_flags;
2126                 tile_redraw(dr, ds, state, x, y);
2127             }
2128         }
2129     }
2130 }
2131
2132 static float game_anim_length(game_state *oldstate, game_state *newstate,
2133                               int dir, game_ui *ui)
2134 {
2135     return 0.0F;
2136 }
2137
2138 static float game_flash_length(game_state *oldstate, game_state *newstate,
2139                                int dir, game_ui *ui)
2140 {
2141     if (!oldstate->completed && newstate->completed &&
2142         !oldstate->used_solve && !newstate->used_solve)
2143         return FLASH_TIME;
2144     return 0.0F;
2145 }
2146
2147 static int game_wants_statusbar(void)
2148 {
2149     return FALSE;
2150 }
2151
2152 static int game_timing_state(game_state *state, game_ui *ui)
2153 {
2154     return TRUE;
2155 }
2156
2157 static void game_print_size(game_params *params, float *x, float *y)
2158 {
2159     int pw, ph;
2160
2161     /*
2162      * I'll use 6mm squares by default.
2163      */
2164     game_compute_size(params, 600, &pw, &ph);
2165     *x = pw / 100.0;
2166     *y = ph / 100.0;
2167 }
2168
2169 static void game_print(drawing *dr, game_state *state, int tilesize)
2170 {
2171     int w = state->w, h = state->h;
2172     int ink = print_mono_colour(dr, 0);
2173     int paper = print_mono_colour(dr, 1);
2174     int x, y;
2175
2176     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2177     game_drawstate ads, *ds = &ads;
2178     game_set_size(dr, ds, NULL, tilesize);
2179
2180     /*
2181      * Border.
2182      */
2183     print_line_width(dr, TILE_SIZE / 16);
2184     draw_rect_outline(dr, COORD(0), COORD(0),
2185                       TILE_SIZE * w, TILE_SIZE * h, ink);
2186
2187     /*
2188      * Grid.
2189      */
2190     print_line_width(dr, TILE_SIZE / 24);
2191     for (x = 1; x < w; x++)
2192         draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink);
2193     for (y = 1; y < h; y++)
2194         draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink);
2195
2196     /*
2197      * Grid contents.
2198      */
2199     for (y = 0; y < h; y++)
2200         for (x = 0; x < w; x++) {
2201             unsigned int ds_flags = tile_flags(ds, state, NULL, x, y, FALSE);
2202             int dx = COORD(x), dy = COORD(y);
2203             if (ds_flags & DF_BLACK) {
2204                 draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, ink);
2205                 if (ds_flags & DF_NUMBERED) {
2206                     char str[10];
2207                     sprintf(str, "%d", GRID(state, lights, x, y));
2208                     draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2209                               FONT_VARIABLE, TILE_SIZE*3/5,
2210                               ALIGN_VCENTRE | ALIGN_HCENTRE, paper, str);
2211                 }
2212             } else if (ds_flags & DF_LIGHT) {
2213                 draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2214                             TILE_RADIUS, -1, ink);
2215             }
2216         }
2217 }
2218
2219 #ifdef COMBINED
2220 #define thegame lightup
2221 #endif
2222
2223 const struct game thegame = {
2224     "Light Up", "games.lightup",
2225     default_params,
2226     game_fetch_preset,
2227     decode_params,
2228     encode_params,
2229     free_params,
2230     dup_params,
2231     TRUE, game_configure, custom_params,
2232     validate_params,
2233     new_game_desc,
2234     validate_desc,
2235     new_game,
2236     dup_game,
2237     free_game,
2238     TRUE, solve_game,
2239     TRUE, game_text_format,
2240     new_ui,
2241     free_ui,
2242     encode_ui,
2243     decode_ui,
2244     game_changed_state,
2245     interpret_move,
2246     execute_move,
2247     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2248     game_colours,
2249     game_new_drawstate,
2250     game_free_drawstate,
2251     game_redraw,
2252     game_anim_length,
2253     game_flash_length,
2254     TRUE, FALSE, game_print_size, game_print,
2255     game_wants_statusbar,
2256     FALSE, game_timing_state,
2257     0,                                 /* flags */
2258 };
2259
2260 #ifdef STANDALONE_SOLVER
2261
2262 int main(int argc, char **argv)
2263 {
2264     game_params *p;
2265     game_state *s;
2266     char *id = NULL, *desc, *err, *result;
2267     int nsol, diff, really_verbose = 0;
2268     unsigned int sflags;
2269
2270     while (--argc > 0) {
2271         char *p = *++argv;
2272         if (!strcmp(p, "-v")) {
2273             really_verbose++;
2274         } else if (*p == '-') {
2275             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2276             return 1;
2277         } else {
2278             id = p;
2279         }
2280     }
2281
2282     if (!id) {
2283         fprintf(stderr, "usage: %s [-v] <game_id>\n", argv[0]);
2284         return 1;
2285     }
2286
2287     desc = strchr(id, ':');
2288     if (!desc) {
2289         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2290         return 1;
2291     }
2292     *desc++ = '\0';
2293
2294     p = default_params();
2295     decode_params(p, id);
2296     err = validate_desc(p, desc);
2297     if (err) {
2298         fprintf(stderr, "%s: %s\n", argv[0], err);
2299         return 1;
2300     }
2301     s = new_game(NULL, p, desc);
2302
2303     /* Run the solvers easiest to hardest until we find one that
2304      * can solve our puzzle. If it's soluble we know that the
2305      * hardest (recursive) solver will always find the solution. */
2306     nsol = sflags = 0;
2307     for (diff = 0; diff <= DIFFCOUNT; diff++) {
2308         printf("\nSolving with difficulty %d.\n", diff);
2309         sflags = flags_from_difficulty(diff);
2310         unplace_lights(s);
2311         nsol = dosolve(s, sflags, NULL);
2312         if (nsol == 1) break;
2313     }
2314
2315     printf("\n");
2316     if (nsol == 0) {
2317         printf("Puzzle has no solution.\n");
2318     } else if (nsol < 0) {
2319         printf("Unable to find a unique solution.\n");
2320     } else if (nsol > 1) {
2321         printf("Puzzle has multiple solutions.\n");
2322     } else {
2323         verbose = really_verbose;
2324         unplace_lights(s);
2325         printf("Puzzle has difficulty %d: solving...\n", diff);
2326         dosolve(s, sflags, NULL); /* sflags from last successful solve */
2327         result = game_text_format(s);
2328         printf("%s", result);
2329         sfree(result);
2330     }
2331
2332     return 0;
2333 }
2334
2335 #endif
2336
2337 /* vim: set shiftwidth=4 tabstop=8: */