2 * lightup.c: Implementation of the Nikoli game 'Light Up'.
14 /* --- Constants, structure definitions, etc. --- */
16 #define PREFERRED_TILE_SIZE 32
17 #define TILE_SIZE (ds->tilesize)
18 #define BORDER (TILE_SIZE / 2)
19 #define TILE_RADIUS (ds->crad)
21 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
22 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
24 #define FLASH_TIME 0.30F
29 COL_BLACK, /* black */
30 COL_LIGHT, /* white */
37 enum { SYMM_NONE, SYMM_REF2, SYMM_ROT2, SYMM_REF4, SYMM_ROT4, SYMM_MAX };
41 int blackpc; /* %age of black squares */
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 */
52 /* flags for non-black squares */
53 #define F_IMPOSSIBLE 8 /* can't put a light here */
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;
67 #define GRID(gs,grid,x,y) (gs->grid[(y)*((gs)->w) + (x)])
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. */
75 int minx, maxx, miny, maxy;
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 { \
85 for (lx = (lld)->minx; lx <= (lld)->maxx; lx++) { \
86 if (lx == (lld)->ox) continue; \
90 for (ly = (lld)->miny; ly <= (lld)->maxy; ly++) { \
91 if (!(lld)->include_origin && ly == (lld)->oy) continue; \
98 struct { int x, y; unsigned int f; } points[4];
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)
106 assert(ox >= 0 && ox < state->w && oy >= 0 && oy < state->h);
108 #define ADDPOINT(cond,nx,ny) do {\
110 s->points[s->npoints].x = (nx); \
111 s->points[s->npoints].y = (ny); \
112 s->points[s->npoints].f = 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);
121 /* --- Game parameter functions --- */
123 #define DEFAULT_PRESET 0
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 },
131 { 12, 12, 20, SYMM_ROT2, 0 },
132 { 12, 12, 20, SYMM_ROT2, 1 }
134 { 14, 14, 20, SYMM_ROT2, 0 },
135 { 14, 14, 20, SYMM_ROT2, 1 }
139 static game_params *default_params(void)
141 game_params *ret = snew(game_params);
142 *ret = lightup_presets[DEFAULT_PRESET];
147 static int game_fetch_preset(int i, char **name, game_params **params)
152 if (i < 0 || i >= lenof(lightup_presets))
155 ret = default_params();
156 *ret = lightup_presets[i];
159 sprintf(buf, "%dx%d %s",
160 ret->w, ret->h, ret->recurse ? "hard" : "easy");
166 static void free_params(game_params *params)
171 static game_params *dup_params(game_params *params)
173 game_params *ret = snew(game_params);
174 *ret = *params; /* structure copy */
178 #define EATNUM(x) do { \
179 (x) = atoi(string); \
180 while (*string && isdigit((unsigned char)*string)) string++; \
183 static void decode_params(game_params *params, char const *string)
186 if (*string == 'x') {
190 if (*string == 'b') {
192 EATNUM(params->blackpc);
194 if (*string == 's') {
196 EATNUM(params->symm);
199 if (*string == 'r') {
205 static char *encode_params(game_params *params, int full)
210 sprintf(buf, "%dx%db%ds%d%s",
211 params->w, params->h, params->blackpc,
213 params->recurse ? "r" : "");
215 sprintf(buf, "%dx%d", params->w, params->h);
220 static config_item *game_configure(game_params *params)
225 ret = snewn(6, config_item);
227 ret[0].name = "Width";
228 ret[0].type = C_STRING;
229 sprintf(buf, "%d", params->w);
230 ret[0].sval = dupstr(buf);
233 ret[1].name = "Height";
234 ret[1].type = C_STRING;
235 sprintf(buf, "%d", params->h);
236 ret[1].sval = dupstr(buf);
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);
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;
252 ret[4].name = "Difficulty";
253 ret[4].type = C_CHOICES;
254 ret[4].sval = ":Easy:Hard";
255 ret[4].ival = params->recurse;
265 static game_params *custom_params(config_item *cfg)
267 game_params *ret = snew(game_params);
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;
278 static char *validate_params(game_params *params, int full)
280 if (params->w < 2 || params->h < 2)
281 return "Width and height must be at least 2";
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";
289 if (params->symm < 0 || params->symm >= SYMM_MAX)
290 return "Unknown symmetry type";
295 /* --- Game state construction/freeing helper functions --- */
297 static game_state *new_state(game_params *params)
299 game_state *ret = snew(game_state);
303 ret->lights = snewn(ret->w * ret->h, int);
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;
312 static game_state *dup_game(game_state *state)
314 game_state *ret = snew(game_state);
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;
323 ret->flags = snewn(ret->w * ret->h, unsigned int);
324 memcpy(ret->flags, state->flags, ret->w * ret->h * sizeof(unsigned int));
326 ret->completed = state->completed;
327 ret->used_solve = state->used_solve;
332 static void free_game(game_state *state)
334 sfree(state->lights);
340 static void debug_state(game_state *state)
345 for (y = 0; y < state->h; y++) {
346 for (x = 0; x < state->w; x++) {
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';
354 if (GRID(state, flags, x, y) & F_LIGHT)
356 else if (GRID(state, flags, x, y) & F_IMPOSSIBLE)
359 printf("%c", (int)c);
362 for (x = 0; x < state->w; x++) {
363 if (GRID(state, flags, x, y) & F_BLACK)
366 c = (GRID(state, flags, x, y) & F_LIGHT) ? 'A' : 'a';
367 c += GRID(state, lights, x, y);
369 printf("%c", (int)c);
377 /* --- Game completion test routines. --- */
379 /* These are split up because occasionally functions are only
380 * interested in one particular aspect. */
382 /* Returns non-zero if all grid spaces are lit. */
383 static int grid_lit(game_state *state)
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)
397 /* Returns non-zero if any lights are lit by other lights. */
398 static int grid_overlap(game_state *state)
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)
412 static int number_wrong(game_state *state, int x, int y)
415 int i, n, empty, lights = GRID(state, lights, x, y);
418 * This function computes the display hint for a number: we
419 * turn the number red if it is definitely wrong. This means
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.
428 assert(GRID(state, flags, x, y) & F_NUMBERED);
429 get_surrounds(state, x, y, &s);
432 for (i = 0; i < s.npoints; i++) {
433 if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT) {
437 if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_BLACK)
439 if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_IMPOSSIBLE)
441 if (GRID(state,lights,s.points[i].x,s.points[i].y))
445 return (n > lights || (n + empty < lights));
448 static int number_correct(game_state *state, int x, int y)
451 int n = 0, i, lights = GRID(state, lights, x, y);
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)
459 return (n == lights) ? 1 : 0;
462 /* Returns non-zero if any numbers add up incorrectly. */
463 static int grid_addsup(game_state *state)
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;
476 static int grid_correct(game_state *state)
478 if (grid_lit(state) &&
479 !grid_overlap(state) &&
480 grid_addsup(state)) return 1;
484 /* --- Board initial setup (blacks, lights, numbers) --- */
486 static void clean_board(game_state *state, int leave_blacks)
489 for (x = 0; x < state->w; x++) {
490 for (y = 0; y < state->h; y++) {
492 GRID(state, flags, x, y) &= F_BLACK;
494 GRID(state, flags, x, y) = 0;
495 GRID(state, lights, x, y) = 0;
501 static void set_blacks(game_state *state, game_params *params, random_state *rs)
503 int x, y, degree = 0, rotate = 0, nblack;
505 int wodd = (state->w % 2) ? 1 : 0;
506 int hodd = (state->h % 2) ? 1 : 0;
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");
517 if (params->symm == SYMM_ROT4 && (state->h != state->w))
518 assert(!"4-fold symmetry unavailable without square grid");
523 if (!rotate) rw += wodd; /* ... but see below. */
525 } else if (degree == 2) {
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++) {
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;
545 /* Copy required region. */
546 if (params->symm == SYMM_NONE) return;
548 for (x = 0; x < rw; x++) {
549 for (y = 0; y < rh; 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);
562 xs[1] = rotate ? (state->w - 1 - x) : x;
563 ys[1] = state->h - 1 - y;
565 for (i = 1; i < degree; i++) {
566 GRID(state, flags, xs[i], ys[i]) =
567 GRID(state, flags, xs[0], ys[0]);
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))
575 state->w/2 + wodd - 1, state->h/2 + hodd - 1) |= F_BLACK;
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,
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;
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;
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;
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;
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;
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)
623 assert(!(GRID(state,flags,ox,oy) & F_BLACK));
625 if (!on && GRID(state,flags,ox,oy) & F_LIGHT) {
627 GRID(state,flags,ox,oy) &= ~F_LIGHT;
629 } else if (on && !(GRID(state,flags,ox,oy) & F_LIGHT)) {
631 GRID(state,flags,ox,oy) |= F_LIGHT;
636 list_lights(state,ox,oy,1,&lld);
637 FOREACHLIT(&lld, GRID(state,lights,lx,ly) += diff; );
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)
646 list_lights(state, x, y, 1, &lld);
647 FOREACHLIT(&lld, if (GRID(state,lights,lx,ly) == 1) { return 1; } );
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)
656 int i, x, y, n, *numindices, wh = state->w*state->h;
659 numindices = snewn(wh, int);
660 for (i = 0; i < wh; i++) numindices[i] = i;
661 shuffle(numindices, wh, sizeof(*numindices), rs);
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);
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);
679 /* If we're not lighting any lights ourself, don't remove anything. */
681 FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += 1; } );
682 if (n == 0) continue;
684 /* Check whether removing lights we're lighting would cause anything
687 FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += check_dark(state,lx,ly); } );
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;
694 if (!grid_overlap(state)) {
696 return; /* we're done. */
698 assert(grid_lit(state));
700 /* if we got here, we've somehow removed all our lights and still have overlaps. */
701 assert(!"Shouldn't get here!");
704 /* Fills in all black squares with numbers of adjacent lights. */
705 static void place_numbers(game_state *state)
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);
715 for (i = 0; i < s.npoints; i++) {
716 if (GRID(state,flags,s.points[i].x, s.points[i].y) & F_LIGHT)
719 GRID(state,flags,x,y) |= F_NUMBERED;
720 GRID(state,lights,x,y) = n;
725 /* --- Actual solver, with helper subroutines. --- */
727 static void tsl_callback(game_state *state,
728 int lx, int ly, int *x, int *y, int *n)
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)++;
735 static int try_solve_light(game_state *state, int ox, int oy,
736 unsigned int flags, int lights)
741 if (lights > 0) return 0;
742 if (flags & F_BLACK) return 0;
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); });
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",
762 static int could_place_light(unsigned int flags, int lights)
764 if (flags & (F_BLACK | F_IMPOSSIBLE)) return 0;
765 return (lights > 0) ? 0 : 1;
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)
774 int x, y, nl, ns, i, ret = 0, lights;
777 if (!(nflags & F_NUMBERED)) return 0;
779 get_surrounds(state,nx,ny,&s);
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. */
792 s.points[i].f |= F_MARK;
793 } else if (!could_place_light(flags, lights)) {
795 s.points[i].f |= F_MARK;
798 if (ns == 0) return 0; /* nowhere to put anything. */
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",
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;
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",
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);
830 static int solve_sub(game_state *state,
831 int forceunique, int maxrecurse, int depth,
835 int x, y, didstuff, ncanplace, lights;
836 int bestx, besty, n, bestn, copy_soluble, self_soluble, ret;
840 #ifdef SOLVE_DIAGNOSTICS
841 printf("solve_sub: depth = %d\n", depth);
843 if (maxdepth && *maxdepth < depth) *maxdepth = depth;
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. */
854 if (grid_correct(state)) return 1;
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);
866 if (try_solve_light(state, x, y, flags, lights)) didstuff = 1;
867 if (try_solve_number(state, x, y, flags, lights)) didstuff = 1;
870 if (didstuff) continue;
871 if (!ncanplace) return 0; /* nowhere to put a light, puzzle in unsoluble. */
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. */
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
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;
891 list_lights(state, x, y, 1, &lld);
892 FOREACHLIT(&lld, { if (GRID(state,lights,lx,ly) == 0) n++; });
894 bestn = n; bestx = x; besty = y;
899 assert(bestx >= 0 && besty >= 0);
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. */
904 scopy = dup_game(state);
905 GRID(state,flags,bestx,besty) |= F_IMPOSSIBLE;
906 self_soluble = solve_sub(state, forceunique, maxrecurse,
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. */
916 set_light(scopy, bestx, besty, 1);
917 copy_soluble = solve_sub(scopy, forceunique, maxrecurse,
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'. */
924 ((copy_soluble < 0) || (self_soluble < 0))) {
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. */
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));
940 ret = copy_soluble + self_soluble;
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)
957 for (x = 0; x < state->w; x++) {
958 for (y = 0; y < state->h; y++) {
959 GRID(state,flags,x,y) &= ~F_NUMBERUSED;
962 nsol = solve_sub(state, forceunique,
963 allowguess ? MAXRECURSE : 0, 0, maxdepth);
967 static int strip_unused_nums(game_state *state)
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;
983 static void unplace_lights(game_state *state)
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;
996 static int puzzle_is_good(game_state *state, game_params *params, int *mdepth)
1001 unplace_lights(state);
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) {
1011 printf("Ignoring recursive puzzle.\n");
1017 printf("%d solutions found.\n", nsol);
1019 if (nsol <= 0) return 0;
1020 if (nsol > 1) return 0;
1024 /* --- New game creation and user input code. --- */
1026 /* The basic algorithm here is to generate the most complex grid possible
1027 * while honouring two restrictions:
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).
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
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).
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.
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
1050 #define MAX_GRIDGEN_TRIES 20
1052 #define MAX_GRIDGEN_TRIES 50
1055 static char *new_game_desc(game_params *params, random_state *rs,
1056 char **aux, int interactive)
1058 game_state *news = new_state(params), *copys;
1059 int nsol, i, run, x, y, wh = params->w*params->h, num, mdepth;
1063 /* Construct a shuffled list of grid positions; we only
1064 * do this once, because if it gets used more than once it'll
1065 * be on a different grid layout. */
1066 numindices = snewn(wh, int);
1067 for (i = 0; i < wh; i++) numindices[i] = i;
1068 shuffle(numindices, wh, sizeof(*numindices), rs);
1071 for (i = 0; i < MAX_GRIDGEN_TRIES; i++) {
1072 set_blacks(news, params, rs); /* also cleans board. */
1074 /* set up lights and then the numbers, and remove the lights */
1075 place_lights(news, rs);
1076 debug(("Generating initial grid.\n"));
1077 place_numbers(news);
1078 if (!puzzle_is_good(news, params, &mdepth)) continue;
1080 /* Take a copy, remove numbers we didn't use and check there's
1081 * still a unique solution; if so, use the copy subsequently. */
1082 copys = dup_game(news);
1083 nsol = strip_unused_nums(copys);
1084 debug(("Stripped %d unused numbers.\n", nsol));
1085 if (!puzzle_is_good(copys, params, &mdepth)) {
1086 debug(("Stripped grid is not good, reverting.\n"));
1093 /* Go through grid removing numbers at random one-by-one and
1094 * trying to solve again; if it ceases to be good put the number back. */
1095 for (i = 0; i < wh; i++) {
1096 y = numindices[i] / params->w;
1097 x = numindices[i] % params->w;
1098 if (!(GRID(news, flags, x, y) & F_NUMBERED)) continue;
1099 num = GRID(news, lights, x, y);
1100 GRID(news, lights, x, y) = 0;
1101 GRID(news, flags, x, y) &= ~F_NUMBERED;
1102 if (!puzzle_is_good(news, params, &mdepth)) {
1103 GRID(news, lights, x, y) = num;
1104 GRID(news, flags, x, y) |= F_NUMBERED;
1106 debug(("Removed (%d,%d) still soluble.\n", x, y));
1108 /* Get a good value of mdepth for the following test */
1109 i = puzzle_is_good(news, params, &mdepth);
1111 if (params->recurse && mdepth == 0) {
1112 debug(("Maximum-difficulty puzzle still not recursive, skipping.\n"));
1118 /* Couldn't generate a good puzzle in however many goes. Ramp up the
1119 * %age of black squares (if we didn't already have lots; in which case
1120 * why couldn't we generate a puzzle?) and try again. */
1121 if (params->blackpc < 90) params->blackpc += 5;
1123 printf("New black layout %d%%.\n", params->blackpc);
1127 /* Game is encoded as a long string one character per square;
1129 * 'B' is a black square with no number
1130 * '0', '1', '2', '3', '4' is a black square with a number. */
1131 ret = snewn((params->w * params->h) + 1, char);
1134 for (y = 0; y < params->h; y++) {
1135 for (x = 0; x < params->w; x++) {
1136 if (GRID(news,flags,x,y) & F_BLACK) {
1138 *p++ = ('a'-1) + run;
1141 if (GRID(news,flags,x,y) & F_NUMBERED)
1142 *p++ = '0' + GRID(news,lights,x,y);
1147 *p++ = ('a'-1) + run;
1155 *p++ = ('a'-1) + run;
1159 assert(p - ret <= params->w * params->h);
1166 static char *validate_desc(game_params *params, char *desc)
1169 for (i = 0; i < params->w*params->h; i++) {
1170 if (*desc >= '0' && *desc <= '4')
1172 else if (*desc == 'B')
1174 else if (*desc >= 'a' && *desc <= 'z')
1175 i += *desc - 'a'; /* and the i++ will add another one */
1177 return "Game description shorter than expected";
1179 return "Game description contained unexpected character";
1182 if (*desc || i > params->w*params->h)
1183 return "Game description longer than expected";
1188 static game_state *new_game(midend_data *me, game_params *params, char *desc)
1190 game_state *ret = new_state(params);
1194 for (y = 0; y < params->h; y++) {
1195 for (x = 0; x < params->w; x++) {
1201 if (c >= 'a' && c <= 'z')
1211 case '0': case '1': case '2': case '3': case '4':
1212 GRID(ret,flags,x,y) |= F_NUMBERED;
1213 GRID(ret,lights,x,y) = (c - '0');
1217 GRID(ret,flags,x,y) |= F_BLACK;
1225 assert(!"Malformed desc.");
1230 if (*desc) assert(!"Over-long desc.");
1235 static char *solve_game(game_state *state, game_state *currstate,
1236 char *aux, char **error)
1239 char *move = NULL, buf[80];
1240 int movelen, movesize, x, y, len;
1241 unsigned int oldflags, solvedflags;
1243 /* We don't care here about non-unique puzzles; if the
1244 * user entered one themself then I doubt they care. */
1246 /* Try and solve from where we are now (for non-unique
1247 * puzzles this may produce a different answer). */
1248 solved = dup_game(currstate);
1249 if (dosolve(solved, 1, 0, NULL) > 0) goto solved;
1252 /* That didn't work; try solving from the clean puzzle. */
1253 solved = dup_game(state);
1254 if (dosolve(solved, 1, 0, NULL) > 0) goto solved;
1255 *error = "Puzzle is not self-consistent.";
1260 move = snewn(movesize, char);
1262 move[movelen++] = 'S';
1263 move[movelen] = '\0';
1264 for (x = 0; x < currstate->w; x++) {
1265 for (y = 0; y < currstate->h; y++) {
1267 oldflags = GRID(currstate, flags, x, y);
1268 solvedflags = GRID(solved, flags, x, y);
1269 if ((oldflags & F_LIGHT) != (solvedflags & F_LIGHT))
1270 len = sprintf(buf, ";L%d,%d", x, y);
1271 else if ((oldflags & F_IMPOSSIBLE) != (solvedflags & F_IMPOSSIBLE))
1272 len = sprintf(buf, ";I%d,%d", x, y);
1274 if (movelen + len >= movesize) {
1275 movesize = movelen + len + 256;
1276 move = sresize(move, movesize, char);
1278 strcpy(move + movelen, buf);
1289 /* 'borrowed' from slant.c, mainly. I could have printed it one
1290 * character per cell (like debug_state) but that comes out tiny.
1291 * 'L' is used for 'light here' because 'O' looks too much like '0'
1292 * (black square with no surrounding lights). */
1293 static char *game_text_format(game_state *state)
1295 int w = state->w, h = state->h, W = w+1, H = h+1;
1296 int x, y, len, lights;
1300 len = (h+H) * (w+W+1) + 1;
1301 ret = snewn(len, char);
1304 for (y = 0; y < H; y++) {
1305 for (x = 0; x < W; x++) {
1312 for (x = 0; x < W; x++) {
1315 /* actual interesting bit. */
1316 flags = GRID(state, flags, x, y);
1317 lights = GRID(state, lights, x, y);
1318 if (flags & F_BLACK) {
1319 if (flags & F_NUMBERED)
1320 *p++ = '0' + lights;
1324 if (flags & F_LIGHT)
1326 else if (flags & F_IMPOSSIBLE)
1328 else if (lights > 0)
1340 assert(p - ret == len);
1345 int cur_x, cur_y, cur_visible;
1348 static game_ui *new_ui(game_state *state)
1350 game_ui *ui = snew(game_ui);
1351 ui->cur_x = ui->cur_y = ui->cur_visible = 0;
1355 static void free_ui(game_ui *ui)
1360 static char *encode_ui(game_ui *ui)
1362 /* nothing to encode. */
1366 static void decode_ui(game_ui *ui, char *encoding)
1368 /* nothing to decode. */
1371 static void game_changed_state(game_ui *ui, game_state *oldstate,
1372 game_state *newstate)
1374 if (newstate->completed)
1375 ui->cur_visible = 0;
1378 #define DF_BLACK 1 /* black square */
1379 #define DF_NUMBERED 2 /* black square with number */
1380 #define DF_LIT 4 /* display (white) square lit up */
1381 #define DF_LIGHT 8 /* display light in square */
1382 #define DF_OVERLAP 16 /* display light as overlapped */
1383 #define DF_CURSOR 32 /* display cursor */
1384 #define DF_NUMBERWRONG 64 /* display black numbered square as error. */
1385 #define DF_FLASH 128 /* background flash is on. */
1386 #define DF_IMPOSSIBLE 256 /* display non-light little square */
1388 struct game_drawstate {
1391 unsigned int *flags; /* width * height */
1396 /* Believe it or not, this empty = "" hack is needed to get around a bug in
1397 * the prc-tools gcc when optimisation is turned on; before, it produced:
1398 lightup-sect.c: In function `interpret_move':
1399 lightup-sect.c:1416: internal error--unrecognizable insn:
1400 (insn 582 580 583 (set (reg:SI 134)
1404 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1405 int x, int y, int button)
1407 enum { NONE, FLIP_LIGHT, FLIP_IMPOSSIBLE } action = NONE;
1408 int cx = -1, cy = -1, cv = ui->cur_visible;
1410 char buf[80], *nullret, *empty = "", c;
1412 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1413 ui->cur_visible = 0;
1416 action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE;
1417 } else if (button == CURSOR_SELECT ||
1418 button == 'i' || button == 'I' ||
1419 button == ' ' || button == '\r' || button == '\n') {
1420 ui->cur_visible = 1;
1423 action = (button == 'i' || button == 'I') ?
1424 FLIP_IMPOSSIBLE : FLIP_LIGHT;
1425 } else if (button == CURSOR_UP || button == CURSOR_DOWN ||
1426 button == CURSOR_RIGHT || button == CURSOR_LEFT) {
1429 case CURSOR_UP: dy = -1; break;
1430 case CURSOR_DOWN: dy = 1; break;
1431 case CURSOR_RIGHT: dx = 1; break;
1432 case CURSOR_LEFT: dx = -1; break;
1433 default: assert(!"shouldn't get here");
1435 ui->cur_x += dx; ui->cur_y += dy;
1436 ui->cur_x = min(max(ui->cur_x, 0), state->w - 1);
1437 ui->cur_y = min(max(ui->cur_y, 0), state->h - 1);
1438 ui->cur_visible = 1;
1441 /* Always redraw if the cursor is on, or if it's just been
1443 if (ui->cur_visible) nullret = empty;
1444 else if (cv) nullret = empty;
1445 else nullret = NULL;
1449 case FLIP_IMPOSSIBLE:
1450 if (cx < 0 || cy < 0 || cx >= state->w || cy >= state->h)
1452 flags = GRID(state, flags, cx, cy);
1453 if (flags & F_BLACK)
1455 if (action == FLIP_LIGHT) {
1456 if (flags & F_IMPOSSIBLE) return nullret;
1459 if (flags & F_LIGHT) return nullret;
1462 sprintf(buf, "%c%d,%d", (int)c, cx, cy);
1469 assert(!"Shouldn't get here!");
1474 static game_state *execute_move(game_state *state, char *move)
1476 game_state *ret = dup_game(state);
1480 if (!*move) goto badmove;
1485 ret->used_solve = TRUE;
1487 } else if (c == 'L' || c == 'I') {
1489 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1490 x < 0 || y < 0 || x >= ret->w || y >= ret->h)
1493 flags = GRID(ret, flags, x, y);
1494 if (flags & F_BLACK) goto badmove;
1496 /* LIGHT and IMPOSSIBLE are mutually exclusive. */
1498 GRID(ret, flags, x, y) &= ~F_IMPOSSIBLE;
1499 set_light(ret, x, y, (flags & F_LIGHT) ? 0 : 1);
1501 set_light(ret, x, y, 0);
1502 GRID(ret, flags, x, y) ^= F_IMPOSSIBLE;
1505 } else goto badmove;
1509 else if (*move) goto badmove;
1511 if (grid_correct(ret)) ret->completed = 1;
1519 /* ----------------------------------------------------------------------
1523 /* XXX entirely cloned from fifteen.c; separate out? */
1524 static void game_compute_size(game_params *params, int tilesize,
1527 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1528 struct { int tilesize; } ads, *ds = &ads;
1529 ads.tilesize = tilesize;
1531 *x = TILE_SIZE * params->w + 2 * BORDER;
1532 *y = TILE_SIZE * params->h + 2 * BORDER;
1535 static void game_set_size(game_drawstate *ds, game_params *params,
1538 ds->tilesize = tilesize;
1539 ds->crad = 3*(tilesize-1)/8;
1542 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1544 float *ret = snewn(3 * NCOLOURS, float);
1547 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1549 for (i = 0; i < 3; i++) {
1550 ret[COL_BLACK * 3 + i] = 0.0F;
1551 ret[COL_LIGHT * 3 + i] = 1.0F;
1552 ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F;
1553 ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.5F;
1557 ret[COL_ERROR * 3 + 0] = 1.0F;
1558 ret[COL_ERROR * 3 + 1] = 0.25F;
1559 ret[COL_ERROR * 3 + 2] = 0.25F;
1561 ret[COL_LIT * 3 + 0] = 1.0F;
1562 ret[COL_LIT * 3 + 1] = 1.0F;
1563 ret[COL_LIT * 3 + 2] = 0.0F;
1565 *ncolours = NCOLOURS;
1569 static game_drawstate *game_new_drawstate(game_state *state)
1571 struct game_drawstate *ds = snew(struct game_drawstate);
1574 ds->tilesize = ds->crad = 0;
1575 ds->w = state->w; ds->h = state->h;
1577 ds->flags = snewn(ds->w*ds->h, unsigned int);
1578 for (i = 0; i < ds->w*ds->h; i++)
1586 static void game_free_drawstate(game_drawstate *ds)
1592 /* At some stage we should put these into a real options struct.
1593 * Note that tile_redraw has no #ifdeffery; it relies on tile_flags not
1594 * to put those flags in. */
1596 #define HINT_OVERLAPS
1597 #define HINT_NUMBERS
1599 static unsigned int tile_flags(game_drawstate *ds, game_state *state, game_ui *ui,
1600 int x, int y, int flashing)
1602 unsigned int flags = GRID(state, flags, x, y);
1603 int lights = GRID(state, lights, x, y);
1604 unsigned int ret = 0;
1606 if (flashing) ret |= DF_FLASH;
1607 if (ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
1610 if (flags & F_BLACK) {
1612 if (flags & F_NUMBERED) {
1614 if (number_wrong(state, x, y))
1615 ret |= DF_NUMBERWRONG;
1621 if (lights > 0) ret |= DF_LIT;
1623 if (flags & F_LIGHT) {
1625 #ifdef HINT_OVERLAPS
1626 if (lights > 1) ret |= DF_OVERLAP;
1629 if (flags & F_IMPOSSIBLE) ret |= DF_IMPOSSIBLE;
1634 static void tile_redraw(frontend *fe, game_drawstate *ds, game_state *state,
1637 unsigned int ds_flags = GRID(ds, flags, x, y);
1638 int dx = COORD(x), dy = COORD(y);
1639 int lit = (ds_flags & DF_FLASH) ? COL_GRID : COL_LIT;
1641 if (ds_flags & DF_BLACK) {
1642 draw_rect(fe, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK);
1643 if (ds_flags & DF_NUMBERED) {
1644 int ccol = (ds_flags & DF_NUMBERWRONG) ? COL_ERROR : COL_LIGHT;
1647 /* We know that this won't change over the course of the game
1648 * so it's OK to ignore this when calculating whether or not
1649 * to redraw the tile. */
1650 sprintf(str, "%d", GRID(state, lights, x, y));
1651 draw_text(fe, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
1652 FONT_VARIABLE, TILE_SIZE*3/5,
1653 ALIGN_VCENTRE | ALIGN_HCENTRE, ccol, str);
1656 draw_rect(fe, dx, dy, TILE_SIZE, TILE_SIZE,
1657 (ds_flags & DF_LIT) ? lit : COL_BACKGROUND);
1658 draw_rect_outline(fe, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID);
1659 if (ds_flags & DF_LIGHT) {
1660 int lcol = (ds_flags & DF_OVERLAP) ? COL_ERROR : COL_LIGHT;
1661 draw_circle(fe, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS,
1663 } else if (ds_flags & DF_IMPOSSIBLE) {
1664 int rlen = TILE_SIZE / 4;
1665 draw_rect(fe, dx + TILE_SIZE/2 - rlen/2, dy + TILE_SIZE/2 - rlen/2,
1666 rlen, rlen, COL_BLACK);
1670 if (ds_flags & DF_CURSOR) {
1671 int coff = TILE_SIZE/8;
1672 draw_rect_outline(fe, dx + coff, dy + coff,
1673 TILE_SIZE - coff*2, TILE_SIZE - coff*2, COL_CURSOR);
1676 draw_update(fe, dx, dy, TILE_SIZE, TILE_SIZE);
1679 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1680 game_state *state, int dir, game_ui *ui,
1681 float animtime, float flashtime)
1683 int flashing = FALSE;
1686 if (flashtime) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
1690 TILE_SIZE * ds->w + 2 * BORDER,
1691 TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
1693 draw_rect_outline(fe, COORD(0)-1, COORD(0)-1,
1694 TILE_SIZE * ds->w + 2,
1695 TILE_SIZE * ds->h + 2,
1698 draw_update(fe, 0, 0,
1699 TILE_SIZE * ds->w + 2 * BORDER,
1700 TILE_SIZE * ds->h + 2 * BORDER);
1704 for (x = 0; x < ds->w; x++) {
1705 for (y = 0; y < ds->h; y++) {
1706 unsigned int ds_flags = tile_flags(ds, state, ui, x, y, flashing);
1707 if (ds_flags != GRID(ds, flags, x, y)) {
1708 GRID(ds, flags, x, y) = ds_flags;
1709 tile_redraw(fe, ds, state, x, y);
1715 static float game_anim_length(game_state *oldstate, game_state *newstate,
1716 int dir, game_ui *ui)
1721 static float game_flash_length(game_state *oldstate, game_state *newstate,
1722 int dir, game_ui *ui)
1724 if (!oldstate->completed && newstate->completed &&
1725 !oldstate->used_solve && !newstate->used_solve)
1730 static int game_wants_statusbar(void)
1735 static int game_timing_state(game_state *state, game_ui *ui)
1741 #define thegame lightup
1744 const struct game thegame = {
1745 "Light Up", "games.lightup",
1752 TRUE, game_configure, custom_params,
1760 TRUE, game_text_format,
1768 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1771 game_free_drawstate,
1775 game_wants_statusbar,
1776 FALSE, game_timing_state,
1777 0, /* mouse_priorities */
1780 /* vim: set shiftwidth=4 tabstop=8: */