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 /* --- Constants, structure definitions, etc. --- */
  15
  16 #define PREFERRED_TILE_SIZE 32
  17 #define TILE_SIZE       (ds->tilesize)
  18 #define BORDER          (TILE_SIZE / 2)
  19 #define TILE_RADIUS     (ds->crad)
  20
  21 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  22 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  23
  24 #define FLASH_TIME 0.30F
  25
  26 enum {
  27     COL_BACKGROUND,
  28     COL_GRID,
  29     COL_BLACK,                         /* black */
  30     COL_LIGHT,                         /* white */
  31     COL_LIT,                           /* yellow */
  32     COL_ERROR,                         /* red */
  33     COL_CURSOR,
  34     NCOLOURS
  35 };
  36
  37 enum { SYMM_NONE, SYMM_REF2, SYMM_ROT2, SYMM_REF4, SYMM_ROT4, SYMM_MAX };
  38
  39 struct game_params {
  40     int w, h;
  41     int blackpc;        /* %age of black squares */
  42     int symm;
  43     int recurse;
  44 };
  45
  46 #define F_BLACK         1
  47
  48 /* flags for black squares */
  49 #define F_NUMBERED      2       /* it has a number attached */
  50 #define F_NUMBERUSED    4       /* this number was useful for solving */
  51
  52 /* flags for non-black squares */
  53 #define F_IMPOSSIBLE    8       /* can't put a light here */
  54 #define F_LIGHT         16
  55
  56 #define F_MARK          32
  57
  58 struct game_state {
  59     int w, h, nlights;
  60     int *lights;        /* For black squares, (optionally) the number
  61                            of surrounding lights. For non-black squares,
  62                            the number of times it's lit. size h*w*/
  63     unsigned int *flags;        /* size h*w */
  64     int completed, used_solve;
  65 };
  66
  67 #define GRID(gs,grid,x,y) (gs->grid[(y)*((gs)->w) + (x)])
  68
  69 /* A ll_data holds information about which lights would be lit by
  70  * a particular grid location's light (or conversely, which locations
  71  * could light a specific other location). */
  72 /* most things should consider this struct opaque. */
  73 typedef struct {
  74     int ox,oy;
  75     int minx, maxx, miny, maxy;
  76     int include_origin;
  77 } ll_data;
  78
  79 /* Macro that executes 'block' once per light in lld, including
  80  * the origin if include_origin is specified. 'block' can use
  81  * lx and ly as the coords. */
  82 #define FOREACHLIT(lld,block) do {                              \
  83   int lx,ly;                                                    \
  84   ly = (lld)->oy;                                               \
  85   for (lx = (lld)->minx; lx <= (lld)->maxx; lx++) {             \
  86     if (lx == (lld)->ox) continue;                              \
  87     block                                                       \
  88   }                                                             \
  89   lx = (lld)->ox;                                               \
  90   for (ly = (lld)->miny; ly <= (lld)->maxy; ly++) {             \
  91     if (!(lld)->include_origin && ly == (lld)->oy) continue;    \
  92     block                                                       \
  93   }                                                             \
  94 } while(0)
  95
  96
  97 typedef struct {
  98     struct { int x, y; unsigned int f; } points[4];
  99     int npoints;
 100 } surrounds;
 101
 102 /* Fills in (doesn't allocate) a surrounds structure with the grid locations
 103  * around a given square, taking account of the edges. */
 104 static void get_surrounds(game_state *state, int ox, int oy, surrounds *s)
 105 {
 106     assert(ox >= 0 && ox < state->w && oy >= 0 && oy < state->h);
 107     s->npoints = 0;
 108 #define ADDPOINT(cond,nx,ny) do {\
 109     if (cond) { \
 110         s->points[s->npoints].x = (nx); \
 111         s->points[s->npoints].y = (ny); \
 112         s->points[s->npoints].f = 0; \
 113         s->npoints++; \
 114     } } while(0)
 115     ADDPOINT(ox > 0,            ox-1, oy);
 116     ADDPOINT(ox < (state->w-1), ox+1, oy);
 117     ADDPOINT(oy > 0,            ox,   oy-1);
 118     ADDPOINT(oy < (state->h-1), ox,   oy+1);
 119 }
 120
 121 /* --- Game parameter functions --- */
 122
 123 #define DEFAULT_PRESET 0
 124
 125 const struct game_params lightup_presets[] = {
 126     { 7, 7, 20, SYMM_ROT4, 0 },
 127     { 7, 7, 20, SYMM_ROT4, 1 },
 128     { 10, 10, 20, SYMM_ROT2, 0 },
 129     { 10, 10, 20, SYMM_ROT2, 1 },
 130 #ifdef SLOW_SYSTEM
 131     { 12, 12, 20, SYMM_ROT2, 0 },
 132     { 12, 12, 20, SYMM_ROT2, 1 }
 133 #else
 134     { 14, 14, 20, SYMM_ROT2, 0 },
 135     { 14, 14, 20, SYMM_ROT2, 1 }
 136 #endif
 137 };
 138
 139 static game_params *default_params(void)
 140 {
 141     game_params *ret = snew(game_params);
 142     *ret = lightup_presets[DEFAULT_PRESET];
 143
 144     return ret;
 145 }
 146
 147 static int game_fetch_preset(int i, char **name, game_params **params)
 148 {
 149     game_params *ret;
 150     char buf[80];
 151
 152     if (i < 0 || i >= lenof(lightup_presets))
 153         return FALSE;
 154
 155     ret = default_params();
 156     *ret = lightup_presets[i];
 157     *params = ret;
 158
 159     sprintf(buf, "%dx%d %s",
 160             ret->w, ret->h, ret->recurse ? "hard" : "easy");
 161     *name = dupstr(buf);
 162
 163     return TRUE;
 164 }
 165
 166 static void free_params(game_params *params)
 167 {
 168     sfree(params);
 169 }
 170
 171 static game_params *dup_params(game_params *params)
 172 {
 173     game_params *ret = snew(game_params);
 174     *ret = *params;                    /* structure copy */
 175     return ret;
 176 }
 177
 178 #define EATNUM(x) do { \
 179     (x) = atoi(string); \
 180     while (*string && isdigit((unsigned char)*string)) string++; \
 181 } while(0)
 182
 183 static void decode_params(game_params *params, char const *string)
 184 {
 185     EATNUM(params->w);
 186     if (*string == 'x') {
 187         string++;
 188         EATNUM(params->h);
 189     }
 190     if (*string == 'b') {
 191         string++;
 192         EATNUM(params->blackpc);
 193     }
 194     if (*string == 's') {
 195         string++;
 196         EATNUM(params->symm);
 197     }
 198     params->recurse = 0;
 199     if (*string == 'r') {
 200         params->recurse = 1;
 201         string++;
 202     }
 203 }
 204
 205 static char *encode_params(game_params *params, int full)
 206 {
 207     char buf[80];
 208
 209     if (full) {
 210         sprintf(buf, "%dx%db%ds%d%s",
 211                 params->w, params->h, params->blackpc,
 212                 params->symm,
 213                 params->recurse ? "r" : "");
 214     } else {
 215         sprintf(buf, "%dx%d", params->w, params->h);
 216     }
 217     return dupstr(buf);
 218 }
 219
 220 static config_item *game_configure(game_params *params)
 221 {
 222     config_item *ret;
 223     char buf[80];
 224
 225     ret = snewn(6, config_item);
 226
 227     ret[0].name = "Width";
 228     ret[0].type = C_STRING;
 229     sprintf(buf, "%d", params->w);
 230     ret[0].sval = dupstr(buf);
 231     ret[0].ival = 0;
 232
 233     ret[1].name = "Height";
 234     ret[1].type = C_STRING;
 235     sprintf(buf, "%d", params->h);
 236     ret[1].sval = dupstr(buf);
 237     ret[1].ival = 0;
 238
 239     ret[2].name = "%age of black squares";
 240     ret[2].type = C_STRING;
 241     sprintf(buf, "%d", params->blackpc);
 242     ret[2].sval = dupstr(buf);
 243     ret[2].ival = 0;
 244
 245     ret[3].name = "Symmetry";
 246     ret[3].type = C_CHOICES;
 247     ret[3].sval = ":None"
 248                   ":2-way mirror:2-way rotational"
 249                   ":4-way mirror:4-way rotational";
 250     ret[3].ival = params->symm;
 251
 252     ret[4].name = "Difficulty";
 253     ret[4].type = C_CHOICES;
 254     ret[4].sval = ":Easy:Hard";
 255     ret[4].ival = params->recurse;
 256
 257     ret[5].name = NULL;
 258     ret[5].type = C_END;
 259     ret[5].sval = NULL;
 260     ret[5].ival = 0;
 261
 262     return ret;
 263 }
 264
 265 static game_params *custom_params(config_item *cfg)
 266 {
 267     game_params *ret = snew(game_params);
 268
 269     ret->w =       atoi(cfg[0].sval);
 270     ret->h =       atoi(cfg[1].sval);
 271     ret->blackpc = atoi(cfg[2].sval);
 272     ret->symm =    cfg[3].ival;
 273     ret->recurse = cfg[4].ival;
 274
 275     return ret;
 276 }
 277
 278 static char *validate_params(game_params *params, int full)
 279 {
 280     if (params->w < 2 || params->h < 2)
 281         return "Width and height must be at least 2";
 282     if (full) {
 283         if (params->blackpc < 5 || params->blackpc > 100)
 284             return "Percentage of black squares must be between 5% and 100%";
 285         if (params->w != params->h) {
 286             if (params->symm == SYMM_ROT4)
 287                 return "4-fold symmetry is only available with square grids";
 288         }
 289         if (params->symm < 0 || params->symm >= SYMM_MAX)
 290           return "Unknown symmetry type";
 291     }
 292     return NULL;
 293 }
 294
 295 /* --- Game state construction/freeing helper functions --- */
 296
 297 static game_state *new_state(game_params *params)
 298 {
 299     game_state *ret = snew(game_state);
 300
 301     ret->w = params->w;
 302     ret->h = params->h;
 303     ret->lights = snewn(ret->w * ret->h, int);
 304     ret->nlights = 0;
 305     memset(ret->lights, 0, ret->w * ret->h * sizeof(int));
 306     ret->flags = snewn(ret->w * ret->h, unsigned int);
 307     memset(ret->flags, 0, ret->w * ret->h * sizeof(unsigned int));
 308     ret->completed = ret->used_solve = 0;
 309     return ret;
 310 }
 311
 312 static game_state *dup_game(game_state *state)
 313 {
 314     game_state *ret = snew(game_state);
 315
 316     ret->w = state->w;
 317     ret->h = state->h;
 318
 319     ret->lights = snewn(ret->w * ret->h, int);
 320     memcpy(ret->lights, state->lights, ret->w * ret->h * sizeof(int));
 321     ret->nlights = state->nlights;
 322
 323     ret->flags = snewn(ret->w * ret->h, unsigned int);
 324     memcpy(ret->flags, state->flags, ret->w * ret->h * sizeof(unsigned int));
 325
 326     ret->completed = state->completed;
 327     ret->used_solve = state->used_solve;
 328
 329     return ret;
 330 }
 331
 332 static void free_game(game_state *state)
 333 {
 334     sfree(state->lights);
 335     sfree(state->flags);
 336     sfree(state);
 337 }
 338
 339 #ifdef DIAGNOSTICS
 340 static void debug_state(game_state *state)
 341 {
 342     int x, y;
 343     char c = '?';
 344
 345     for (y = 0; y < state->h; y++) {
 346         for (x = 0; x < state->w; x++) {
 347             c = '.';
 348             if (GRID(state, flags, x, y) & F_BLACK) {
 349                 if (GRID(state, flags, x, y) & F_NUMBERED)
 350                     c = GRID(state, lights, x, y) + '0';
 351                 else
 352                     c = '#';
 353             } else {
 354                 if (GRID(state, flags, x, y) & F_LIGHT)
 355                     c = 'O';
 356                 else if (GRID(state, flags, x, y) & F_IMPOSSIBLE)
 357                     c = 'X';
 358             }
 359             printf("%c", (int)c);
 360         }
 361         printf("     ");
 362         for (x = 0; x < state->w; x++) {
 363             if (GRID(state, flags, x, y) & F_BLACK)
 364                 c = '#';
 365             else {
 366                 c = (GRID(state, flags, x, y) & F_LIGHT) ? 'A' : 'a';
 367                 c += GRID(state, lights, x, y);
 368             }
 369             printf("%c", (int)c);
 370         }
 371         printf("\n");
 372     }
 373     printf("\n");
 374 }
 375 #endif
 376
 377 /* --- Game completion test routines. --- */
 378
 379 /* These are split up because occasionally functions are only
 380  * interested in one particular aspect. */
 381
 382 /* Returns non-zero if all grid spaces are lit. */
 383 static int grid_lit(game_state *state)
 384 {
 385     int x, y;
 386
 387     for (x = 0; x < state->w; x++) {
 388         for (y = 0; y < state->h; y++) {
 389             if (GRID(state,flags,x,y) & F_BLACK) continue;
 390             if (GRID(state,lights,x,y) == 0)
 391                 return 0;
 392         }
 393     }
 394     return 1;
 395 }
 396
 397 /* Returns non-zero if any lights are lit by other lights. */
 398 static int grid_overlap(game_state *state)
 399 {
 400     int x, y;
 401
 402     for (x = 0; x < state->w; x++) {
 403         for (y = 0; y < state->h; y++) {
 404             if (!(GRID(state, flags, x, y) & F_LIGHT)) continue;
 405             if (GRID(state, lights, x, y) > 1)
 406                 return 1;
 407         }
 408     }
 409     return 0;
 410 }
 411
 412 static int number_wrong(game_state *state, int x, int y)
 413 {
 414     surrounds s;
 415     int i, n, empty, lights = GRID(state, lights, x, y);
 416
 417     /*
 418      * This function computes the display hint for a number: we
 419      * turn the number red if it is definitely wrong. This means
 420      * that either
 421      *
 422      *  (a) it has too many lights around it, or
 423      *  (b) it would have too few lights around it even if all the
 424      *      plausible squares (not black, lit or F_IMPOSSIBLE) were
 425      *      filled with lights.
 426      */
 427
 428     assert(GRID(state, flags, x, y) & F_NUMBERED);
 429     get_surrounds(state, x, y, &s);
 430
 431     empty = n = 0;
 432     for (i = 0; i < s.npoints; i++) {
 433         if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT) {
 434             n++;
 435             continue;
 436         }
 437         if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_BLACK)
 438             continue;
 439         if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_IMPOSSIBLE)
 440             continue;
 441         if (GRID(state,lights,s.points[i].x,s.points[i].y))
 442             continue;
 443         empty++;
 444     }
 445     return (n > lights || (n + empty < lights));
 446 }
 447
 448 static int number_correct(game_state *state, int x, int y)
 449 {
 450     surrounds s;
 451     int n = 0, i, lights = GRID(state, lights, x, y);
 452
 453     assert(GRID(state, flags, x, y) & F_NUMBERED);
 454     get_surrounds(state, x, y, &s);
 455     for (i = 0; i < s.npoints; i++) {
 456         if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT)
 457             n++;
 458     }
 459     return (n == lights) ? 1 : 0;
 460 }
 461
 462 /* Returns non-zero if any numbers add up incorrectly. */
 463 static int grid_addsup(game_state *state)
 464 {
 465     int x, y;
 466
 467     for (x = 0; x < state->w; x++) {
 468         for (y = 0; y < state->h; y++) {
 469             if (!(GRID(state, flags, x, y) & F_NUMBERED)) continue;
 470             if (!number_correct(state, x, y)) return 0;
 471         }
 472     }
 473     return 1;
 474 }
 475
 476 static int grid_correct(game_state *state)
 477 {
 478     if (grid_lit(state) &&
 479         !grid_overlap(state) &&
 480         grid_addsup(state)) return 1;
 481     return 0;
 482 }
 483
 484 /* --- Board initial setup (blacks, lights, numbers) --- */
 485
 486 static void clean_board(game_state *state, int leave_blacks)
 487 {
 488     int x,y;
 489     for (x = 0; x < state->w; x++) {
 490         for (y = 0; y < state->h; y++) {
 491             if (leave_blacks)
 492                 GRID(state, flags, x, y) &= F_BLACK;
 493             else
 494                 GRID(state, flags, x, y) = 0;
 495             GRID(state, lights, x, y) = 0;
 496         }
 497     }
 498     state->nlights = 0;
 499 }
 500
 501 static void set_blacks(game_state *state, game_params *params, random_state *rs)
 502 {
 503     int x, y, degree = 0, rotate = 0, nblack;
 504     int rh, rw, i;
 505     int wodd = (state->w % 2) ? 1 : 0;
 506     int hodd = (state->h % 2) ? 1 : 0;
 507     int xs[4], ys[4];
 508
 509     switch (params->symm) {
 510     case SYMM_NONE: degree = 1; rotate = 0; break;
 511     case SYMM_ROT2: degree = 2; rotate = 1; break;
 512     case SYMM_REF2: degree = 2; rotate = 0; break;
 513     case SYMM_ROT4: degree = 4; rotate = 1; break;
 514     case SYMM_REF4: degree = 4; rotate = 0; break;
 515     default: assert(!"Unknown symmetry type");
 516     }
 517     if (params->symm == SYMM_ROT4 && (state->h != state->w))
 518         assert(!"4-fold symmetry unavailable without square grid");
 519
 520     if (degree == 4) {
 521         rw = state->w/2;
 522         rh = state->h/2;
 523         if (!rotate) rw += wodd; /* ... but see below. */
 524         rh += hodd;
 525     } else if (degree == 2) {
 526         rw = state->w;
 527         rh = state->h/2;
 528         rh += hodd;
 529     } else {
 530         rw = state->w;
 531         rh = state->h;
 532     }
 533
 534     /* clear, then randomise, required region. */
 535     clean_board(state, 0);
 536     nblack = (rw * rh * params->blackpc) / 100;
 537     for (i = 0; i < nblack; i++) {
 538         do {
 539             x = random_upto(rs,rw);
 540             y = random_upto(rs,rh);
 541         } while (GRID(state,flags,x,y) & F_BLACK);
 542         GRID(state, flags, x, y) |= F_BLACK;
 543     }
 544
 545     /* Copy required region. */
 546     if (params->symm == SYMM_NONE) return;
 547
 548     for (x = 0; x < rw; x++) {
 549         for (y = 0; y < rh; y++) {
 550             if (degree == 4) {
 551                 xs[0] = x;
 552                 ys[0] = y;
 553                 xs[1] = state->w - 1 - (rotate ? y : x);
 554                 ys[1] = rotate ? x : y;
 555                 xs[2] = rotate ? (state->w - 1 - x) : x;
 556                 ys[2] = state->h - 1 - y;
 557                 xs[3] = rotate ? y : (state->w - 1 - x);
 558                 ys[3] = state->h - 1 - (rotate ? x : y);
 559             } else {
 560                 xs[0] = x;
 561                 ys[0] = y;
 562                 xs[1] = rotate ? (state->w - 1 - x) : x;
 563                 ys[1] = state->h - 1 - y;
 564             }
 565             for (i = 1; i < degree; i++) {
 566                 GRID(state, flags, xs[i], ys[i]) =
 567                     GRID(state, flags, xs[0], ys[0]);
 568             }
 569         }
 570     }
 571     /* SYMM_ROT4 misses the middle square above; fix that here. */
 572     if (degree == 4 && rotate && wodd &&
 573         (random_upto(rs,100) <= (unsigned int)params->blackpc))
 574         GRID(state,flags,
 575              state->w/2 + wodd - 1, state->h/2 + hodd - 1) |= F_BLACK;
 576
 577 #ifdef DIAGNOSTICS
 578     debug_state(state);
 579 #endif
 580 }
 581
 582 /* Fills in (does not allocate) a ll_data with all the tiles that would
 583  * be illuminated by a light at point (ox,oy). If origin=1 then the
 584  * origin is included in this list. */
 585 static void list_lights(game_state *state, int ox, int oy, int origin,
 586                         ll_data *lld)
 587 {
 588     int x,y;
 589
 590     memset(lld, 0, sizeof(lld));
 591     lld->ox = lld->minx = lld->maxx = ox;
 592     lld->oy = lld->miny = lld->maxy = oy;
 593     lld->include_origin = origin;
 594
 595     y = oy;
 596     for (x = ox-1; x >= 0; x--) {
 597         if (GRID(state, flags, x, y) & F_BLACK) break;
 598         if (x < lld->minx) lld->minx = x;
 599     }
 600     for (x = ox+1; x < state->w; x++) {
 601         if (GRID(state, flags, x, y) & F_BLACK) break;
 602         if (x > lld->maxx) lld->maxx = x;
 603     }
 604
 605     x = ox;
 606     for (y = oy-1; y >= 0; y--) {
 607         if (GRID(state, flags, x, y) & F_BLACK) break;
 608         if (y < lld->miny) lld->miny = y;
 609     }
 610     for (y = oy+1; y < state->h; y++) {
 611         if (GRID(state, flags, x, y) & F_BLACK) break;
 612         if (y > lld->maxy) lld->maxy = y;
 613     }
 614 }
 615
 616 /* Makes sure a light is the given state, editing the lights table to suit the
 617  * new state if necessary. */
 618 static void set_light(game_state *state, int ox, int oy, int on)
 619 {
 620     ll_data lld;
 621     int diff = 0;
 622
 623     assert(!(GRID(state,flags,ox,oy) & F_BLACK));
 624
 625     if (!on && GRID(state,flags,ox,oy) & F_LIGHT) {
 626         diff = -1;
 627         GRID(state,flags,ox,oy) &= ~F_LIGHT;
 628         state->nlights--;
 629     } else if (on && !(GRID(state,flags,ox,oy) & F_LIGHT)) {
 630         diff = 1;
 631         GRID(state,flags,ox,oy) |= F_LIGHT;
 632         state->nlights++;
 633     }
 634
 635     if (diff != 0) {
 636         list_lights(state,ox,oy,1,&lld);
 637         FOREACHLIT(&lld, GRID(state,lights,lx,ly) += diff; );
 638     }
 639 }
 640
 641 /* Returns 1 if removing a light at (x,y) would cause a square to go dark. */
 642 static int check_dark(game_state *state, int x, int y)
 643 {
 644     ll_data lld;
 645
 646     list_lights(state, x, y, 1, &lld);
 647     FOREACHLIT(&lld, if (GRID(state,lights,lx,ly) == 1) { return 1; } );
 648     return 0;
 649 }
 650
 651 /* Sets up an initial random correct position (i.e. every
 652  * space lit, and no lights lit by other lights) by filling the
 653  * grid with lights and then removing lights one by one at random. */
 654 static void place_lights(game_state *state, random_state *rs)
 655 {
 656     int i, x, y, n, *numindices, wh = state->w*state->h;
 657     ll_data lld;
 658
 659     numindices = snewn(wh, int);
 660     for (i = 0; i < wh; i++) numindices[i] = i;
 661     shuffle(numindices, wh, sizeof(*numindices), rs);
 662
 663     /* Place a light on all grid squares without lights. */
 664     for (x = 0; x < state->w; x++) {
 665         for (y = 0; y < state->h; y++) {
 666             GRID(state, flags, x, y) &= ~F_MARK; /* we use this later. */
 667             if (GRID(state, flags, x, y) & F_BLACK) continue;
 668             set_light(state, x, y, 1);
 669         }
 670     }
 671
 672     for (i = 0; i < wh; i++) {
 673         y = numindices[i] / state->w;
 674         x = numindices[i] % state->w;
 675         if (!(GRID(state, flags, x, y) & F_LIGHT)) continue;
 676         if (GRID(state, flags, x, y) & F_MARK) continue;
 677         list_lights(state, x, y, 0, &lld);
 678
 679         /* If we're not lighting any lights ourself, don't remove anything. */
 680         n = 0;
 681         FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += 1; } );
 682         if (n == 0) continue;
 683
 684         /* Check whether removing lights we're lighting would cause anything
 685          * to go dark. */
 686         n = 0;
 687         FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += check_dark(state,lx,ly); } );
 688         if (n == 0) {
 689             /* No, it wouldn't, so we can remove them all. */
 690             FOREACHLIT(&lld, set_light(state,lx,ly, 0); );
 691             GRID(state,flags,x,y) |= F_MARK;
 692         }
 693
 694         if (!grid_overlap(state)) {
 695             sfree(numindices);
 696             return; /* we're done. */
 697         }
 698         assert(grid_lit(state));
 699     }
 700     /* if we got here, we've somehow removed all our lights and still have overlaps. */
 701     assert(!"Shouldn't get here!");
 702 }
 703
 704 /* Fills in all black squares with numbers of adjacent lights. */
 705 static void place_numbers(game_state *state)
 706 {
 707     int x, y, i, n;
 708     surrounds s;
 709
 710     for (x = 0; x < state->w; x++) {
 711         for (y = 0; y < state->h; y++) {
 712             if (!(GRID(state,flags,x,y) & F_BLACK)) continue;
 713             get_surrounds(state, x, y, &s);
 714             n = 0;
 715             for (i = 0; i < s.npoints; i++) {
 716                 if (GRID(state,flags,s.points[i].x, s.points[i].y) & F_LIGHT)
 717                     n++;
 718             }
 719             GRID(state,flags,x,y) |= F_NUMBERED;
 720             GRID(state,lights,x,y) = n;
 721         }
 722     }
 723 }
 724
 725 /* --- Actual solver, with helper subroutines. --- */
 726
 727 static void tsl_callback(game_state *state,
 728                          int lx, int ly, int *x, int *y, int *n)
 729 {
 730     if (GRID(state,flags,lx,ly) & F_IMPOSSIBLE) return;
 731     if (GRID(state,lights,lx,ly) > 0) return;
 732     *x = lx; *y = ly; (*n)++;
 733 }
 734
 735 static int try_solve_light(game_state *state, int ox, int oy,
 736                            unsigned int flags, int lights)
 737 {
 738     ll_data lld;
 739     int sx,sy,n = 0;
 740
 741     if (lights > 0) return 0;
 742     if (flags & F_BLACK) return 0;
 743
 744     /* We have an unlit square; count how many ways there are left to
 745      * place a light that lights us (including this square); if only
 746      * one, we must put a light there. Squares that could light us
 747      * are, of course, the same as the squares we would light... */
 748     list_lights(state, ox, oy, 1, &lld);
 749     FOREACHLIT(&lld, { tsl_callback(state, lx, ly, &sx, &sy, &n); });
 750     if (n == 1) {
 751         set_light(state, sx, sy, 1);
 752 #ifdef SOLVE_DIAGNOSTICS
 753         printf("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n",
 754                ox,oy,sx,sy);
 755 #endif
 756         return 1;
 757     }
 758
 759     return 0;
 760 }
 761
 762 static int could_place_light(unsigned int flags, int lights)
 763 {
 764     if (flags & (F_BLACK | F_IMPOSSIBLE)) return 0;
 765     return (lights > 0) ? 0 : 1;
 766 }
 767
 768 /* For a given number square, determine whether we have enough info
 769  * to unambiguously place its lights. */
 770 static int try_solve_number(game_state *state, int nx, int ny,
 771                             unsigned int nflags, int nlights)
 772 {
 773     surrounds s;
 774     int x, y, nl, ns, i, ret = 0, lights;
 775     unsigned int flags;
 776
 777     if (!(nflags & F_NUMBERED)) return 0;
 778     nl = nlights;
 779     get_surrounds(state,nx,ny,&s);
 780     ns = s.npoints;
 781
 782     /* nl is no. of lights we need to place, ns is no. of spaces we
 783      * have to place them in. Try and narrow these down, and mark
 784      * points we can ignore later. */
 785     for (i = 0; i < s.npoints; i++) {
 786         x = s.points[i].x; y = s.points[i].y;
 787         flags = GRID(state,flags,x,y);
 788         lights = GRID(state,lights,x,y);
 789         if (flags & F_LIGHT) {
 790             /* light here already; one less light for one less place. */
 791             nl--; ns--;
 792             s.points[i].f |= F_MARK;
 793         } else if (!could_place_light(flags, lights)) {
 794             ns--;
 795             s.points[i].f |= F_MARK;
 796         }
 797     }
 798     if (ns == 0) return 0; /* nowhere to put anything. */
 799     if (nl == 0) {
 800         /* we have placed all lights we need to around here; all remaining
 801          * surrounds are therefore IMPOSSIBLE. */
 802 #ifdef SOLVE_DIAGNOSTICS
 803         printf("Setting remaining surrounds to (%d,%d) IMPOSSIBLE.\n",
 804                nx,ny);
 805 #endif
 806         GRID(state,flags,nx,ny) |= F_NUMBERUSED;
 807         for (i = 0; i < s.npoints; i++) {
 808             if (!(s.points[i].f & F_MARK)) {
 809                 GRID(state,flags,s.points[i].x,s.points[i].y) |= F_IMPOSSIBLE;
 810                 ret = 1;
 811             }
 812         }
 813     } else if (nl == ns) {
 814         /* we have as many lights to place as spaces; fill them all. */
 815 #ifdef SOLVE_DIAGNOSTICS
 816         printf("Setting all remaining surrounds to (%d,%d) LIGHT.\n",
 817                nx,ny);
 818 #endif
 819         GRID(state,flags,nx,ny) |= F_NUMBERUSED;
 820         for (i = 0; i < s.npoints; i++) {
 821             if (!(s.points[i].f & F_MARK)) {
 822                 set_light(state, s.points[i].x,s.points[i].y, 1);
 823                 ret = 1;
 824             }
 825         }
 826     }
 827     return ret;
 828 }
 829
 830 static int solve_sub(game_state *state,
 831                      int forceunique, int maxrecurse, int depth,
 832                      int *maxdepth)
 833 {
 834     unsigned int flags;
 835     int x, y, didstuff, ncanplace, lights;
 836     int bestx, besty, n, bestn, copy_soluble, self_soluble, ret;
 837     game_state *scopy;
 838     ll_data lld;
 839
 840 #ifdef SOLVE_DIAGNOSTICS
 841     printf("solve_sub: depth = %d\n", depth);
 842 #endif
 843     if (maxdepth && *maxdepth < depth) *maxdepth = depth;
 844
 845     while (1) {
 846         if (grid_overlap(state)) {
 847             /* Our own solver, from scratch, should never cause this to happen
 848              * (assuming a soluble grid). However, if we're trying to solve
 849              * from a half-completed *incorrect* grid this might occur; we
 850              * just return the 'no solutions' code in this case. */
 851             return 0;
 852         }
 853
 854         if (grid_correct(state)) return 1;
 855
 856         ncanplace = 0;
 857         didstuff = 0;
 858         /* These 2 loops, and the functions they call, are the critical loops
 859          * for timing; any optimisations should look here first. */
 860         for (x = 0; x < state->w; x++) {
 861             for (y = 0; y < state->h; y++) {
 862                 flags = GRID(state,flags,x,y);
 863                 lights = GRID(state,lights,x,y);
 864                 ncanplace += could_place_light(flags, lights);
 865
 866                 if (try_solve_light(state, x, y, flags, lights)) didstuff = 1;
 867                 if (try_solve_number(state, x, y, flags, lights)) didstuff = 1;
 868             }
 869         }
 870         if (didstuff) continue;
 871         if (!ncanplace) return 0; /* nowhere to put a light, puzzle in unsoluble. */
 872
 873         /* We now have to make a guess; we have places to put lights but
 874          * no definite idea about where they can go. */
 875         if (depth >= maxrecurse) return -1; /* mustn't delve any deeper. */
 876
 877         /* Of all the squares that we could place a light, pick the one
 878          * that would light the most currently unlit squares. */
 879         /* This heuristic was just plucked from the air; there may well be
 880          * a more efficient way of choosing a square to flip to minimise
 881          * recursion. */
 882         bestn = 0;
 883         bestx = besty = -1; /* suyb */
 884         for (x = 0; x < state->w; x++) {
 885             for (y = 0; y < state->h; y++) {
 886                 flags = GRID(state,flags,x,y);
 887                 lights = GRID(state,lights,x,y);
 888                 if (!could_place_light(flags, lights)) continue;
 889
 890                 n = 0;
 891                 list_lights(state, x, y, 1, &lld);
 892                 FOREACHLIT(&lld, { if (GRID(state,lights,lx,ly) == 0) n++; });
 893                 if (n > bestn) {
 894                     bestn = n; bestx = x; besty = y;
 895                 }
 896             }
 897         }
 898         assert(bestn > 0);
 899         assert(bestx >= 0 && besty >= 0);
 900
 901         /* Now we've chosen a plausible (x,y), try to solve it once as 'lit'
 902          * and once as 'impossible'; we need to make one copy to do this. */
 903
 904         scopy = dup_game(state);
 905         GRID(state,flags,bestx,besty) |= F_IMPOSSIBLE;
 906         self_soluble = solve_sub(state, forceunique, maxrecurse,
 907                                  depth+1, maxdepth);
 908
 909         if (!forceunique && self_soluble > 0) {
 910             /* we didn't care about finding all solutions, and we just
 911              * found one; return with it immediately. */
 912             free_game(scopy);
 913             return self_soluble;
 914         }
 915
 916         set_light(scopy, bestx, besty, 1);
 917         copy_soluble = solve_sub(scopy, forceunique, maxrecurse,
 918                                  depth+1, maxdepth);
 919
 920         /* If we wanted a unique solution but we hit our recursion limit
 921          * (on either branch) then we have to assume we didn't find possible
 922          * extra solutions, and return 'not soluble'. */
 923         if (forceunique &&
 924             ((copy_soluble < 0) || (self_soluble < 0))) {
 925             ret = -1;
 926         /* Make sure that whether or not it was self or copy (or both) that
 927          * were soluble, that we return a solved state in self. */
 928         } else if (copy_soluble <= 0) {
 929             /* copy wasn't soluble; keep self state and return that result. */
 930             ret = self_soluble;
 931         } else if (self_soluble <= 0) {
 932             /* copy solved and we didn't, so copy in copy's (now solved)
 933              * flags and light state. */
 934             memcpy(state->lights, scopy->lights,
 935                    scopy->w * scopy->h * sizeof(int));
 936             memcpy(state->flags, scopy->flags,
 937                    scopy->w * scopy->h * sizeof(unsigned int));
 938             ret = copy_soluble;
 939         } else {
 940             ret = copy_soluble + self_soluble;
 941         }
 942         free_game(scopy);
 943         return ret;
 944     }
 945 }
 946
 947 #define MAXRECURSE 5
 948
 949 /* Fills in the (possibly partially-complete) game_state as far as it can,
 950  * returning the number of possible solutions. If it returns >0 then the
 951  * game_state will be in a solved state, but you won't know which one. */
 952 static int dosolve(game_state *state,
 953                    int allowguess, int forceunique, int *maxdepth)
 954 {
 955     int x, y, nsol;
 956
 957     for (x = 0; x < state->w; x++) {
 958         for (y = 0; y < state->h; y++) {
 959             GRID(state,flags,x,y) &= ~F_NUMBERUSED;
 960         }
 961     }
 962     nsol = solve_sub(state, forceunique,
 963                      allowguess ? MAXRECURSE : 0, 0, maxdepth);
 964     return nsol;
 965 }
 966
 967 static int strip_unused_nums(game_state *state)
 968 {
 969     int x,y,n=0;
 970     for (x = 0; x < state->w; x++) {
 971         for (y = 0; y < state->h; y++) {
 972             if ((GRID(state,flags,x,y) & F_NUMBERED) &&
 973                 !(GRID(state,flags,x,y) & F_NUMBERUSED)) {
 974                 GRID(state,flags,x,y) &= ~F_NUMBERED;
 975                 GRID(state,lights,x,y) = 0;
 976                 n++;
 977             }
 978         }
 979     }
 980     return n;
 981 }
 982
 983 static void unplace_lights(game_state *state)
 984 {
 985     int x,y;
 986     for (x = 0; x < state->w; x++) {
 987         for (y = 0; y < state->h; y++) {
 988             if (GRID(state,flags,x,y) & F_LIGHT)
 989                 set_light(state,x,y,0);
 990             GRID(state,flags,x,y) &= ~F_IMPOSSIBLE;
 991             GRID(state,flags,x,y) &= ~F_NUMBERUSED;
 992         }
 993     }
 994 }
 995
 996 static int puzzle_is_good(game_state *state, game_params *params, int *mdepth)
 997 {
 998     int nsol;
 999
1000     *mdepth = 0;
1001     unplace_lights(state);
1002
1003 #ifdef DIAGNOSTICS
1004     debug_state(state);
1005 #endif
1006
1007     nsol = dosolve(state, params->recurse, TRUE, mdepth);
1008     /* if we wanted an easy puzzle, make sure we didn't need recursion. */
1009     if (!params->recurse && *mdepth > 0) {
1010 #ifdef DIAGNOSTICS
1011         printf("Ignoring recursive puzzle.\n");
1012 #endif
1013         return 0;
1014     }
1015
1016 #ifdef DIAGNOSTICS
1017     printf("%d solutions found.\n", nsol);
1018 #endif
1019     if (nsol <= 0) return 0;
1020     if (nsol > 1) return 0;
1021     return 1;
1022 }
1023
1024 /* --- New game creation and user input code. --- */
1025
1026 /* The basic algorithm here is to generate the most complex grid possible
1027  * while honouring two restrictions:
1028  *
1029  *  * we require a unique solution, and
1030  *  * either we require solubility with no recursion (!params->recurse)
1031  *  * or we require some recursion. (params->recurse).
1032  *
1033  * The solver helpfully keeps track of the numbers it needed to use to
1034  * get its solution, so we use that to remove an initial set of numbers
1035  * and check we still satsify our requirements (on uniqueness and
1036  * non-recursiveness, if applicable; we don't check explicit recursiveness
1037  * until the end).
1038  *
1039  * Then we try to remove all numbers in a random order, and see if we
1040  * still satisfy requirements (putting them back if we didn't).
1041  *
1042  * Removing numbers will always, in general terms, make a puzzle require
1043  * more recursion but it may also mean a puzzle becomes non-unique.
1044  *
1045  * Once we're done, if we wanted a recursive puzzle but the most difficult
1046  * puzzle we could come up with was non-recursive, we give up and try a new
1047  * grid. */
1048
1049 #define MAX_GRIDGEN_TRIES 20
1050
1051 static char *new_game_desc(game_params *params, random_state *rs,
1052                            char **aux, int interactive)
1053 {
1054     game_state *news = new_state(params), *copys;
1055     int nsol, i, run, x, y, wh = params->w*params->h, num, mdepth;
1056     char *ret, *p;
1057     int *numindices;
1058
1059     /* Construct a shuffled list of grid positions; we only
1060      * do this once, because if it gets used more than once it'll
1061      * be on a different grid layout. */
1062     numindices = snewn(wh, int);
1063     for (i = 0; i < wh; i++) numindices[i] = i;
1064     shuffle(numindices, wh, sizeof(*numindices), rs);
1065
1066     while (1) {
1067         for (i = 0; i < MAX_GRIDGEN_TRIES; i++) {
1068             set_blacks(news, params, rs); /* also cleans board. */
1069
1070             /* set up lights and then the numbers, and remove the lights */
1071             place_lights(news, rs);
1072             debug(("Generating initial grid.\n"));
1073             place_numbers(news);
1074             if (!puzzle_is_good(news, params, &mdepth)) continue;
1075
1076             /* Take a copy, remove numbers we didn't use and check there's
1077              * still a unique solution; if so, use the copy subsequently. */
1078             copys = dup_game(news);
1079             nsol = strip_unused_nums(copys);
1080             debug(("Stripped %d unused numbers.\n", nsol));
1081             if (!puzzle_is_good(copys, params, &mdepth)) {
1082                 debug(("Stripped grid is not good, reverting.\n"));
1083                 free_game(copys);
1084             } else {
1085                 free_game(news);
1086                 news = copys;
1087             }
1088
1089             /* Go through grid removing numbers at random one-by-one and
1090              * trying to solve again; if it ceases to be good put the number back. */
1091             for (i = 0; i < wh; i++) {
1092                 y = numindices[i] / params->w;
1093                 x = numindices[i] % params->w;
1094                 if (!(GRID(news, flags, x, y) & F_NUMBERED)) continue;
1095                 num = GRID(news, lights, x, y);
1096                 GRID(news, lights, x, y) = 0;
1097                 GRID(news, flags, x, y) &= ~F_NUMBERED;
1098                 if (!puzzle_is_good(news, params, &mdepth)) {
1099                     GRID(news, lights, x, y) = num;
1100                     GRID(news, flags, x, y) |= F_NUMBERED;
1101                 } else
1102                     debug(("Removed (%d,%d) still soluble.\n", x, y));
1103             }
1104             /* Get a good value of mdepth for the following test */
1105             i = puzzle_is_good(news, params, &mdepth);
1106             assert(i);
1107             if (params->recurse && mdepth == 0) {
1108                 debug(("Maximum-difficulty puzzle still not recursive, skipping.\n"));
1109                 continue;
1110             }
1111
1112             goto goodpuzzle;
1113         }
1114         /* Couldn't generate a good puzzle in however many goes. Ramp up the
1115          * %age of black squares (if we didn't already have lots; in which case
1116          * why couldn't we generate a puzzle?) and try again. */
1117         if (params->blackpc < 90) params->blackpc += 5;
1118 #ifdef DIAGNOSTICS
1119         printf("New black layout %d%%.\n", params->blackpc);
1120 #endif
1121     }
1122 goodpuzzle:
1123     /* Game is encoded as a long string one character per square;
1124      * 'S' is a space
1125      * 'B' is a black square with no number
1126      * '0', '1', '2', '3', '4' is a black square with a number. */
1127     ret = snewn((params->w * params->h) + 1, char);
1128     p = ret;
1129     run = 0;
1130     for (y = 0; y < params->h; y++) {
1131         for (x = 0; x < params->w; x++) {
1132             if (GRID(news,flags,x,y) & F_BLACK) {
1133                 if (run) {
1134                     *p++ = ('a'-1) + run;
1135                     run = 0;
1136                 }
1137                 if (GRID(news,flags,x,y) & F_NUMBERED)
1138                     *p++ = '0' + GRID(news,lights,x,y);
1139                 else
1140                     *p++ = 'B';
1141             } else {
1142                 if (run == 26) {
1143                     *p++ = ('a'-1) + run;
1144                     run = 0;
1145                 }
1146                 run++;
1147             }
1148         }
1149     }
1150     if (run) {
1151         *p++ = ('a'-1) + run;
1152         run = 0;
1153     }
1154     *p = '\0';
1155     assert(p - ret <= params->w * params->h);
1156     free_game(news);
1157     sfree(numindices);
1158
1159     return ret;
1160 }
1161
1162 static char *validate_desc(game_params *params, char *desc)
1163 {
1164     int i;
1165     for (i = 0; i < params->w*params->h; i++) {
1166         if (*desc >= '0' && *desc <= '4')
1167             /* OK */;
1168         else if (*desc == 'B')
1169             /* OK */;
1170         else if (*desc >= 'a' && *desc <= 'z')
1171             i += *desc - 'a';          /* and the i++ will add another one */
1172         else if (!*desc)
1173             return "Game description shorter than expected";
1174         else
1175             return "Game description contained unexpected character";
1176         desc++;
1177     }
1178     if (*desc || i > params->w*params->h)
1179         return "Game description longer than expected";
1180
1181     return NULL;
1182 }
1183
1184 static game_state *new_game(midend_data *me, game_params *params, char *desc)
1185 {
1186     game_state *ret = new_state(params);
1187     int x,y;
1188     int run = 0;
1189
1190     for (y = 0; y < params->h; y++) {
1191         for (x = 0; x < params->w; x++) {
1192             char c = '\0';
1193
1194             if (run == 0) {
1195                 c = *desc++;
1196                 assert(c != 'S');
1197                 if (c >= 'a' && c <= 'z')
1198                     run = c - 'a' + 1;
1199             }
1200
1201             if (run > 0) {
1202                 c = 'S';
1203                 run--;
1204             }
1205
1206             switch (c) {
1207               case '0': case '1': case '2': case '3': case '4':
1208                 GRID(ret,flags,x,y) |= F_NUMBERED;
1209                 GRID(ret,lights,x,y) = (c - '0');
1210                 /* run-on... */
1211
1212               case 'B':
1213                 GRID(ret,flags,x,y) |= F_BLACK;
1214                 break;
1215
1216               case 'S':
1217                 /* empty square */
1218                 break;
1219
1220               default:
1221                 assert(!"Malformed desc.");
1222                 break;
1223             }
1224         }
1225     }
1226     if (*desc) assert(!"Over-long desc.");
1227
1228     return ret;
1229 }
1230
1231 static char *solve_game(game_state *state, game_state *currstate,
1232                         char *aux, char **error)
1233 {
1234     game_state *solved;
1235     char *move = NULL, buf[80];
1236     int movelen, movesize, x, y, len;
1237     unsigned int oldflags, solvedflags;
1238
1239     /* We don't care here about non-unique puzzles; if the
1240      * user entered one themself then I doubt they care. */
1241
1242     /* Try and solve from where we are now (for non-unique
1243      * puzzles this may produce a different answer). */
1244     solved = dup_game(currstate);
1245     if (dosolve(solved, 1, 0, NULL) > 0) goto solved;
1246     free_game(solved);
1247
1248     /* That didn't work; try solving from the clean puzzle. */
1249     solved = dup_game(state);
1250     if (dosolve(solved, 1, 0, NULL) > 0) goto solved;
1251     *error = "Puzzle is not self-consistent.";
1252     goto done;
1253
1254 solved:
1255     movesize = 256;
1256     move = snewn(movesize, char);
1257     movelen = 0;
1258     move[movelen++] = 'S';
1259     move[movelen] = '\0';
1260     for (x = 0; x < currstate->w; x++) {
1261         for (y = 0; y < currstate->h; y++) {
1262             len = 0;
1263             oldflags = GRID(currstate, flags, x, y);
1264             solvedflags = GRID(solved, flags, x, y);
1265             if ((oldflags & F_LIGHT) != (solvedflags & F_LIGHT))
1266                 len = sprintf(buf, ";L%d,%d", x, y);
1267             else if ((oldflags & F_IMPOSSIBLE) != (solvedflags & F_IMPOSSIBLE))
1268                 len = sprintf(buf, ";I%d,%d", x, y);
1269             if (len) {
1270                 if (movelen + len >= movesize) {
1271                     movesize = movelen + len + 256;
1272                     move = sresize(move, movesize, char);
1273                 }
1274                 strcpy(move + movelen, buf);
1275                 movelen += len;
1276             }
1277         }
1278     }
1279
1280 done:
1281     free_game(solved);
1282     return move;
1283 }
1284
1285 /* 'borrowed' from slant.c, mainly. I could have printed it one
1286  * character per cell (like debug_state) but that comes out tiny.
1287  * 'L' is used for 'light here' because 'O' looks too much like '0'
1288  * (black square with no surrounding lights). */
1289 static char *game_text_format(game_state *state)
1290 {
1291     int w = state->w, h = state->h, W = w+1, H = h+1;
1292     int x, y, len, lights;
1293     unsigned int flags;
1294     char *ret, *p;
1295
1296     len = (h+H) * (w+W+1) + 1;
1297     ret = snewn(len, char);
1298     p = ret;
1299
1300     for (y = 0; y < H; y++) {
1301         for (x = 0; x < W; x++) {
1302             *p++ = '+';
1303             if (x < w)
1304                 *p++ = '-';
1305         }
1306         *p++ = '\n';
1307         if (y < h) {
1308             for (x = 0; x < W; x++) {
1309                 *p++ = '|';
1310                 if (x < w) {
1311                     /* actual interesting bit. */
1312                     flags = GRID(state, flags, x, y);
1313                     lights = GRID(state, lights, x, y);
1314                     if (flags & F_BLACK) {
1315                         if (flags & F_NUMBERED)
1316                             *p++ = '0' + lights;
1317                         else
1318                             *p++ = '#';
1319                     } else {
1320                         if (flags & F_LIGHT)
1321                             *p++ = 'L';
1322                         else if (flags & F_IMPOSSIBLE)
1323                             *p++ = 'x';
1324                         else if (lights > 0)
1325                             *p++ = '.';
1326                         else
1327                             *p++ = ' ';
1328                     }
1329                 }
1330             }
1331             *p++ = '\n';
1332         }
1333     }
1334     *p++ = '\0';
1335
1336     assert(p - ret == len);
1337     return ret;
1338 }
1339
1340 struct game_ui {
1341     int cur_x, cur_y, cur_visible;
1342 };
1343
1344 static game_ui *new_ui(game_state *state)
1345 {
1346     game_ui *ui = snew(game_ui);
1347     ui->cur_x = ui->cur_y = ui->cur_visible = 0;
1348     return ui;
1349 }
1350
1351 static void free_ui(game_ui *ui)
1352 {
1353     sfree(ui);
1354 }
1355
1356 static char *encode_ui(game_ui *ui)
1357 {
1358     /* nothing to encode. */
1359     return NULL;
1360 }
1361
1362 static void decode_ui(game_ui *ui, char *encoding)
1363 {
1364     /* nothing to decode. */
1365 }
1366
1367 static void game_changed_state(game_ui *ui, game_state *oldstate,
1368                                game_state *newstate)
1369 {
1370     if (newstate->completed)
1371         ui->cur_visible = 0;
1372 }
1373
1374 #define DF_BLACK        1       /* black square */
1375 #define DF_NUMBERED     2       /* black square with number */
1376 #define DF_LIT          4       /* display (white) square lit up */
1377 #define DF_LIGHT        8       /* display light in square */
1378 #define DF_OVERLAP      16      /* display light as overlapped */
1379 #define DF_CURSOR       32      /* display cursor */
1380 #define DF_NUMBERWRONG  64      /* display black numbered square as error. */
1381 #define DF_FLASH        128     /* background flash is on. */
1382 #define DF_IMPOSSIBLE   256     /* display non-light little square */
1383
1384 struct game_drawstate {
1385     int tilesize, crad;
1386     int w, h;
1387     unsigned int *flags;         /* width * height */
1388     int started;
1389 };
1390
1391
1392 /* Believe it or not, this empty = "" hack is needed to get around a bug in
1393  * the prc-tools gcc when optimisation is turned on; before, it produced:
1394     lightup-sect.c: In function `interpret_move':
1395     lightup-sect.c:1416: internal error--unrecognizable insn:
1396     (insn 582 580 583 (set (reg:SI 134)
1397             (pc)) -1 (nil)
1398         (nil))
1399  */
1400 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1401                             int x, int y, int button)
1402 {
1403     enum { NONE, FLIP_LIGHT, FLIP_IMPOSSIBLE } action = NONE;
1404     int cx = -1, cy = -1, cv = ui->cur_visible;
1405     unsigned int flags;
1406     char buf[80], *nullret, *empty = "", c;
1407
1408     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1409         ui->cur_visible = 0;
1410         cx = FROMCOORD(x);
1411         cy = FROMCOORD(y);
1412         action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE;
1413     } else if (button == CURSOR_SELECT ||
1414                button == 'i' || button == 'I' ||
1415                button == ' ' || button == '\r' || button == '\n') {
1416         ui->cur_visible = 1;
1417         cx = ui->cur_x;
1418         cy = ui->cur_y;
1419         action = (button == 'i' || button == 'I') ?
1420             FLIP_IMPOSSIBLE : FLIP_LIGHT;
1421     } else if (button == CURSOR_UP || button == CURSOR_DOWN ||
1422                button == CURSOR_RIGHT || button == CURSOR_LEFT) {
1423         int dx = 0, dy = 0;
1424         switch (button) {
1425         case CURSOR_UP:         dy = -1; break;
1426         case CURSOR_DOWN:       dy = 1; break;
1427         case CURSOR_RIGHT:      dx = 1; break;
1428         case CURSOR_LEFT:       dx = -1; break;
1429         default: assert(!"shouldn't get here");
1430         }
1431         ui->cur_x += dx; ui->cur_y += dy;
1432         ui->cur_x = min(max(ui->cur_x, 0), state->w - 1);
1433         ui->cur_y = min(max(ui->cur_y, 0), state->h - 1);
1434         ui->cur_visible = 1;
1435     }
1436
1437     /* Always redraw if the cursor is on, or if it's just been
1438      * removed. */
1439     if (ui->cur_visible) nullret = empty;
1440     else if (cv) nullret = empty;
1441     else nullret = NULL;
1442
1443     switch (action) {
1444     case FLIP_LIGHT:
1445     case FLIP_IMPOSSIBLE:
1446         if (cx < 0 || cy < 0 || cx >= state->w || cy >= state->h)
1447             return nullret;
1448         flags = GRID(state, flags, cx, cy);
1449         if (flags & F_BLACK)
1450             return nullret;
1451         if (action == FLIP_LIGHT) {
1452             if (flags & F_IMPOSSIBLE) return nullret;
1453             c = 'L';
1454         } else {
1455             if (flags & F_LIGHT) return nullret;
1456             c = 'I';
1457         }
1458         sprintf(buf, "%c%d,%d", (int)c, cx, cy);
1459         break;
1460
1461     case NONE:
1462         return nullret;
1463
1464     default:
1465         assert(!"Shouldn't get here!");
1466     }
1467     return dupstr(buf);
1468 }
1469
1470 static game_state *execute_move(game_state *state, char *move)
1471 {
1472     game_state *ret = dup_game(state);
1473     int x, y, n, flags;
1474     char c;
1475
1476     if (!*move) goto badmove;
1477
1478     while (*move) {
1479         c = *move;
1480         if (c == 'S') {
1481             ret->used_solve = TRUE;
1482             move++;
1483         } else if (c == 'L' || c == 'I') {
1484             move++;
1485             if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1486                 x < 0 || y < 0 || x >= ret->w || y >= ret->h)
1487                 goto badmove;
1488
1489             flags = GRID(ret, flags, x, y);
1490             if (flags & F_BLACK) goto badmove;
1491
1492             /* LIGHT and IMPOSSIBLE are mutually exclusive. */
1493             if (c == 'L') {
1494                 GRID(ret, flags, x, y) &= ~F_IMPOSSIBLE;
1495                 set_light(ret, x, y, (flags & F_LIGHT) ? 0 : 1);
1496             } else {
1497                 set_light(ret, x, y, 0);
1498                 GRID(ret, flags, x, y) ^= F_IMPOSSIBLE;
1499             }
1500             move += n;
1501         } else goto badmove;
1502
1503         if (*move == ';')
1504             move++;
1505         else if (*move) goto badmove;
1506     }
1507     if (grid_correct(ret)) ret->completed = 1;
1508     return ret;
1509
1510 badmove:
1511     free_game(ret);
1512     return NULL;
1513 }
1514
1515 /* ----------------------------------------------------------------------
1516  * Drawing routines.
1517  */
1518
1519 /* XXX entirely cloned from fifteen.c; separate out? */
1520 static void game_compute_size(game_params *params, int tilesize,
1521                               int *x, int *y)
1522 {
1523     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1524     struct { int tilesize; } ads, *ds = &ads;
1525     ads.tilesize = tilesize;
1526
1527     *x = TILE_SIZE * params->w + 2 * BORDER;
1528     *y = TILE_SIZE * params->h + 2 * BORDER;
1529 }
1530
1531 static void game_set_size(game_drawstate *ds, game_params *params,
1532                           int tilesize)
1533 {
1534     ds->tilesize = tilesize;
1535     ds->crad = 3*(tilesize-1)/8;
1536 }
1537
1538 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1539 {
1540     float *ret = snewn(3 * NCOLOURS, float);
1541     int i;
1542
1543     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1544
1545     for (i = 0; i < 3; i++) {
1546         ret[COL_BLACK * 3 + i] = 0.0F;
1547         ret[COL_LIGHT * 3 + i] = 1.0F;
1548         ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F;
1549         ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.5F;
1550
1551     }
1552
1553     ret[COL_ERROR * 3 + 0] = 1.0F;
1554     ret[COL_ERROR * 3 + 1] = 0.25F;
1555     ret[COL_ERROR * 3 + 2] = 0.25F;
1556
1557     ret[COL_LIT * 3 + 0] = 1.0F;
1558     ret[COL_LIT * 3 + 1] = 1.0F;
1559     ret[COL_LIT * 3 + 2] = 0.0F;
1560
1561     *ncolours = NCOLOURS;
1562     return ret;
1563 }
1564
1565 static game_drawstate *game_new_drawstate(game_state *state)
1566 {
1567     struct game_drawstate *ds = snew(struct game_drawstate);
1568     int i;
1569
1570     ds->tilesize = ds->crad = 0;
1571     ds->w = state->w; ds->h = state->h;
1572
1573     ds->flags = snewn(ds->w*ds->h, unsigned int);
1574     for (i = 0; i < ds->w*ds->h; i++)
1575         ds->flags[i] = -1;
1576
1577     ds->started = 0;
1578
1579     return ds;
1580 }
1581
1582 static void game_free_drawstate(game_drawstate *ds)
1583 {
1584     sfree(ds->flags);
1585     sfree(ds);
1586 }
1587
1588 /* At some stage we should put these into a real options struct.
1589  * Note that tile_redraw has no #ifdeffery; it relies on tile_flags not
1590  * to put those flags in. */
1591 #define HINT_LIGHTS
1592 #define HINT_OVERLAPS
1593 #define HINT_NUMBERS
1594
1595 static unsigned int tile_flags(game_drawstate *ds, game_state *state, game_ui *ui,
1596                                int x, int y, int flashing)
1597 {
1598     unsigned int flags = GRID(state, flags, x, y);
1599     int lights = GRID(state, lights, x, y);
1600     unsigned int ret = 0;
1601
1602     if (flashing) ret |= DF_FLASH;
1603     if (ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
1604         ret |= DF_CURSOR;
1605
1606     if (flags & F_BLACK) {
1607         ret |= DF_BLACK;
1608         if (flags & F_NUMBERED) {
1609 #ifdef HINT_NUMBERS
1610             if (number_wrong(state, x, y))
1611                 ret |= DF_NUMBERWRONG;
1612 #endif
1613             ret |= DF_NUMBERED;
1614         }
1615     } else {
1616 #ifdef HINT_LIGHTS
1617         if (lights > 0) ret |= DF_LIT;
1618 #endif
1619         if (flags & F_LIGHT) {
1620             ret |= DF_LIGHT;
1621 #ifdef HINT_OVERLAPS
1622             if (lights > 1) ret |= DF_OVERLAP;
1623 #endif
1624         }
1625         if (flags & F_IMPOSSIBLE) ret |= DF_IMPOSSIBLE;
1626     }
1627     return ret;
1628 }
1629
1630 static void tile_redraw(frontend *fe, game_drawstate *ds, game_state *state,
1631                         int x, int y)
1632 {
1633     unsigned int ds_flags = GRID(ds, flags, x, y);
1634     int dx = COORD(x), dy = COORD(y);
1635     int lit = (ds_flags & DF_FLASH) ? COL_GRID : COL_LIT;
1636
1637     if (ds_flags & DF_BLACK) {
1638         draw_rect(fe, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK);
1639         if (ds_flags & DF_NUMBERED) {
1640             int ccol = (ds_flags & DF_NUMBERWRONG) ? COL_ERROR : COL_LIGHT;
1641             char str[10];
1642
1643             /* We know that this won't change over the course of the game
1644              * so it's OK to ignore this when calculating whether or not
1645              * to redraw the tile. */
1646             sprintf(str, "%d", GRID(state, lights, x, y));
1647             draw_text(fe, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
1648                       FONT_VARIABLE, TILE_SIZE*3/5,
1649                       ALIGN_VCENTRE | ALIGN_HCENTRE, ccol, str);
1650         }
1651     } else {
1652         draw_rect(fe, dx, dy, TILE_SIZE, TILE_SIZE,
1653                   (ds_flags & DF_LIT) ? lit : COL_BACKGROUND);
1654         draw_rect_outline(fe, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID);
1655         if (ds_flags & DF_LIGHT) {
1656             int lcol = (ds_flags & DF_OVERLAP) ? COL_ERROR : COL_LIGHT;
1657             draw_circle(fe, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS,
1658                         lcol, COL_BLACK);
1659         } else if (ds_flags & DF_IMPOSSIBLE) {
1660             int rlen = TILE_SIZE / 4;
1661             draw_rect(fe, dx + TILE_SIZE/2 - rlen/2, dy + TILE_SIZE/2 - rlen/2,
1662                       rlen, rlen, COL_BLACK);
1663         }
1664     }
1665
1666     if (ds_flags & DF_CURSOR) {
1667         int coff = TILE_SIZE/8;
1668         draw_rect_outline(fe, dx + coff, dy + coff,
1669                           TILE_SIZE - coff*2, TILE_SIZE - coff*2, COL_CURSOR);
1670     }
1671
1672     draw_update(fe, dx, dy, TILE_SIZE, TILE_SIZE);
1673 }
1674
1675 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1676                         game_state *state, int dir, game_ui *ui,
1677                         float animtime, float flashtime)
1678 {
1679     int flashing = FALSE;
1680     int x,y;
1681
1682     if (flashtime) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
1683
1684     if (!ds->started) {
1685         draw_rect(fe, 0, 0,
1686                   TILE_SIZE * ds->w + 2 * BORDER,
1687                   TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
1688
1689         draw_rect_outline(fe, COORD(0)-1, COORD(0)-1,
1690                           TILE_SIZE * ds->w + 2,
1691                           TILE_SIZE * ds->h + 2,
1692                           COL_GRID);
1693
1694         draw_update(fe, 0, 0,
1695                     TILE_SIZE * ds->w + 2 * BORDER,
1696                     TILE_SIZE * ds->h + 2 * BORDER);
1697         ds->started = 1;
1698     }
1699
1700     for (x = 0; x < ds->w; x++) {
1701         for (y = 0; y < ds->h; y++) {
1702             unsigned int ds_flags = tile_flags(ds, state, ui, x, y, flashing);
1703             if (ds_flags != GRID(ds, flags, x, y)) {
1704                 GRID(ds, flags, x, y) = ds_flags;
1705                 tile_redraw(fe, ds, state, x, y);
1706             }
1707         }
1708     }
1709 }
1710
1711 static float game_anim_length(game_state *oldstate, game_state *newstate,
1712                               int dir, game_ui *ui)
1713 {
1714     return 0.0F;
1715 }
1716
1717 static float game_flash_length(game_state *oldstate, game_state *newstate,
1718                                int dir, game_ui *ui)
1719 {
1720     if (!oldstate->completed && newstate->completed &&
1721         !oldstate->used_solve && !newstate->used_solve)
1722         return FLASH_TIME;
1723     return 0.0F;
1724 }
1725
1726 static int game_wants_statusbar(void)
1727 {
1728     return FALSE;
1729 }
1730
1731 static int game_timing_state(game_state *state, game_ui *ui)
1732 {
1733     return TRUE;
1734 }
1735
1736 #ifdef COMBINED
1737 #define thegame lightup
1738 #endif
1739
1740 const struct game thegame = {
1741     "Light Up", "games.lightup",
1742     default_params,
1743     game_fetch_preset,
1744     decode_params,
1745     encode_params,
1746     free_params,
1747     dup_params,
1748     TRUE, game_configure, custom_params,
1749     validate_params,
1750     new_game_desc,
1751     validate_desc,
1752     new_game,
1753     dup_game,
1754     free_game,
1755     TRUE, solve_game,
1756     TRUE, game_text_format,
1757     new_ui,
1758     free_ui,
1759     encode_ui,
1760     decode_ui,
1761     game_changed_state,
1762     interpret_move,
1763     execute_move,
1764     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1765     game_colours,
1766     game_new_drawstate,
1767     game_free_drawstate,
1768     game_redraw,
1769     game_anim_length,
1770     game_flash_length,
1771     game_wants_statusbar,
1772     FALSE, game_timing_state,
1773     0,                                 /* mouse_priorities */
1774 };
1775
1776 /* vim: set shiftwidth=4 tabstop=8: */