2 * galaxies.c: implementation of 'Tentai Show' from Nikoli,
3 * also sometimes called 'Spiral Galaxies'.
7 * Grid is stored as size (2n-1), holding edges as well as spaces
8 * (and thus vertices too, at edge intersections).
10 * Any dot will thus be positioned at one of our grid points,
11 * which saves any faffing with half-of-a-square stuff.
13 * Edges have on/off state; obviously the actual edges of the
14 * board are fixed to on, and everything else starts as off.
18 * Think about how to display remote groups of tiles?
24 * Nikoli's example [web site has wrong highlighting]
25 * (at http://www.nikoli.co.jp/en/puzzles/astronomical_show/):
28 * The 'spiral galaxies puzzles are NP-complete' paper
29 * (at http://www.stetson.edu/~efriedma/papers/spiral.pdf):
30 * 7x7:chpgdqqqoezdddki
32 * Puzzle competition pdf examples
33 * (at http://www.puzzleratings.org/Yurekli2006puz.pdf):
34 * 6x6:EDbaMucCohbrecEi
35 * 10x10:beFbufEEzowDlxldibMHezBQzCdcFzjlci
36 * 13x13:dCemIHFFkJajjgDfdbdBzdzEgjccoPOcztHjBczLDjczqktJjmpreivvNcggFi
52 int solver_show_working;
53 #define solvep(x) do { if (solver_show_working) { printf x; } } while(0)
70 A(UNREASONABLE,Unreasonable,u)
72 #define ENUM(upper,title,lower) DIFF_ ## upper,
73 #define TITLE(upper,title,lower) #title,
74 #define ENCODE(upper,title,lower) #lower
75 #define CONFIG(upper,title,lower) ":" #title
77 DIFF_IMPOSSIBLE, DIFF_AMBIGUOUS, DIFF_UNFINISHED, DIFF_MAX };
78 static char const *const galaxies_diffnames[] = {
79 DIFFLIST(TITLE) "Impossible", "Ambiguous", "Unfinished" };
80 static char const galaxies_diffchars[] = DIFFLIST(ENCODE);
81 #define DIFFCONFIG DIFFLIST(CONFIG)
84 /* X and Y is the area of the board as seen by
85 * the user, not the (2n+1) area the game uses. */
89 enum { s_tile, s_edge, s_vertex };
91 #define F_DOT 1 /* there's a dot here */
92 #define F_EDGE_SET 2 /* the edge is set */
93 #define F_TILE_ASSOC 4 /* this tile is associated with a dot. */
94 #define F_DOT_BLACK 8 /* (ui only) dot is black. */
95 #define F_MARK 16 /* scratch flag */
96 #define F_REACHABLE 32
98 #define F_MULTIPLE 128
99 #define F_DOT_HOLD 256
102 typedef struct space {
103 int x, y; /* its position */
106 int dotx, doty; /* if flags & F_TILE_ASSOC */
107 int nassoc; /* if flags & F_DOT */
110 #define INGRID(s,x,y) ((x) >= 0 && (y) >= 0 && \
111 (x) < (state)->sx && (y) < (state)->sy)
112 #define INUI(s,x,y) ((x) > 0 && (y) > 0 && \
113 (x) < ((state)->sx-1) && (y) < ((state)->sy-1))
115 #define GRID(s,g,x,y) ((s)->g[((y)*(s)->sx)+(x)])
116 #define SPACE(s,x,y) GRID(s,grid,x,y)
119 int w, h; /* size from params */
120 int sx, sy; /* allocated size, (2x-1)*(2y-1) */
122 int completed, used_solve;
126 midend *me; /* to call supersede_game_desc */
127 int cdiff; /* difficulty of current puzzle (for status bar),
131 /* ----------------------------------------------------------
132 * Game parameters and presets
135 /* make up some sensible default sizes */
137 #define DEFAULT_PRESET 0
139 static const game_params galaxies_presets[] = {
140 { 7, 7, DIFF_NORMAL },
141 { 7, 7, DIFF_UNREASONABLE },
142 { 10, 10, DIFF_NORMAL },
143 { 15, 15, DIFF_NORMAL },
146 static int game_fetch_preset(int i, char **name, game_params **params)
151 if (i < 0 || i >= lenof(galaxies_presets))
154 ret = snew(game_params);
155 *ret = galaxies_presets[i]; /* structure copy */
157 sprintf(buf, "%dx%d %s", ret->w, ret->h,
158 galaxies_diffnames[ret->diff]);
160 if (name) *name = dupstr(buf);
165 static game_params *default_params(void)
168 game_fetch_preset(DEFAULT_PRESET, NULL, &ret);
172 static void free_params(game_params *params)
177 static game_params *dup_params(game_params *params)
179 game_params *ret = snew(game_params);
180 *ret = *params; /* structure copy */
184 static void decode_params(game_params *params, char const *string)
186 params->h = params->w = atoi(string);
187 params->diff = DIFF_NORMAL;
188 while (*string && isdigit((unsigned char)*string)) string++;
189 if (*string == 'x') {
191 params->h = atoi(string);
192 while (*string && isdigit((unsigned char)*string)) string++;
194 if (*string == 'd') {
197 for (i = 0; i <= DIFF_UNREASONABLE; i++)
198 if (*string == galaxies_diffchars[i])
200 if (*string) string++;
204 static char *encode_params(game_params *params, int full)
207 sprintf(str, "%dx%d", params->w, params->h);
209 sprintf(str + strlen(str), "d%c", galaxies_diffchars[params->diff]);
213 static config_item *game_configure(game_params *params)
218 ret = snewn(4, config_item);
220 ret[0].name = "Width";
221 ret[0].type = C_STRING;
222 sprintf(buf, "%d", params->w);
223 ret[0].sval = dupstr(buf);
226 ret[1].name = "Height";
227 ret[1].type = C_STRING;
228 sprintf(buf, "%d", params->h);
229 ret[1].sval = dupstr(buf);
232 ret[2].name = "Difficulty";
233 ret[2].type = C_CHOICES;
234 ret[2].sval = DIFFCONFIG;
235 ret[2].ival = params->diff;
245 static game_params *custom_params(config_item *cfg)
247 game_params *ret = snew(game_params);
249 ret->w = atoi(cfg[0].sval);
250 ret->h = atoi(cfg[1].sval);
251 ret->diff = cfg[2].ival;
256 static char *validate_params(game_params *params, int full)
258 if (params->w < 3 || params->h < 3)
259 return "Width and height must both be at least 3";
261 * This shouldn't be able to happen at all, since decode_params
262 * and custom_params will never generate anything that isn't
265 assert(params->diff <= DIFF_UNREASONABLE);
270 /* ----------------------------------------------------------
271 * Game utility functions.
274 static void add_dot(space *space) {
275 assert(!(space->flags & F_DOT));
276 space->flags |= F_DOT;
280 static void remove_dot(space *space) {
281 assert(space->flags & F_DOT);
282 space->flags &= ~F_DOT;
285 static void remove_assoc(game_state *state, space *tile) {
286 if (tile->flags & F_TILE_ASSOC) {
287 SPACE(state, tile->dotx, tile->doty).nassoc--;
288 tile->flags &= ~F_TILE_ASSOC;
294 static void add_assoc(game_state *state, space *tile, space *dot) {
295 remove_assoc(state, tile);
297 tile->flags |= F_TILE_ASSOC;
301 debug(("add_assoc sp %d %d --> dot %d,%d, new nassoc %d.\n",
302 tile->x, tile->y, dot->x, dot->y, dot->nassoc));
305 static struct space *sp2dot(game_state *state, int x, int y)
307 struct space *sp = &SPACE(state, x, y);
308 if (!(sp->flags & F_TILE_ASSOC)) return NULL;
309 return &SPACE(state, sp->dotx, sp->doty);
312 #define IS_VERTICAL_EDGE(x) ((x % 2) == 0)
314 static char *game_text_format(game_state *state)
316 int maxlen = (state->sx+1)*state->sy, x, y;
320 ret = snewn(maxlen+1, char);
323 for (y = 0; y < state->sy; y++) {
324 for (x = 0; x < state->sx; x++) {
325 sp = &SPACE(state, x, y);
326 if (sp->flags & F_DOT)
328 else if (sp->flags & (F_REACHABLE|F_MULTIPLE|F_MARK))
329 *p++ = (sp->flags & F_MULTIPLE) ? 'M' :
330 (sp->flags & F_REACHABLE) ? 'R' : 'X';
334 if (sp->flags & F_TILE_ASSOC) {
335 space *dot = sp2dot(state, sp->x, sp->y);
336 if (dot->flags & F_DOT)
337 *p++ = (dot->flags & F_DOT_BLACK) ? 'B' : 'W';
339 *p++ = '?'; /* association with not-a-dot. */
349 if (sp->flags & F_EDGE_SET)
350 *p++ = (IS_VERTICAL_EDGE(x)) ? '|' : '-';
356 assert(!"shouldn't get here!");
363 assert(p - ret == maxlen);
369 static void dbg_state(game_state *state)
372 char *temp = game_text_format(state);
373 debug(("%s\n", temp));
378 /* Space-enumeration callbacks should all return 1 for 'progress made',
379 * -1 for 'impossible', and 0 otherwise. */
380 typedef int (*space_cb)(game_state *state, space *sp, void *ctx);
382 #define IMPOSSIBLE_QUITS 1
384 static int foreach_sub(game_state *state, space_cb cb, unsigned int f,
385 void *ctx, int startx, int starty)
387 int x, y, progress = 0, impossible = 0, ret;
390 for (y = starty; y < state->sy; y += 2) {
391 sp = &SPACE(state, startx, y);
392 for (x = startx; x < state->sx; x += 2) {
393 ret = cb(state, sp, ctx);
395 if (f & IMPOSSIBLE_QUITS) return -1;
397 } else if (ret == 1) {
403 return impossible ? -1 : progress;
406 static int foreach_tile(game_state *state, space_cb cb, unsigned int f,
409 return foreach_sub(state, cb, f, ctx, 1, 1);
412 static int foreach_edge(game_state *state, space_cb cb, unsigned int f,
417 ret1 = foreach_sub(state, cb, f, ctx, 0, 1);
418 ret2 = foreach_sub(state, cb, f, ctx, 1, 0);
420 if (ret1 == -1 || ret2 == -1) return -1;
421 return (ret1 || ret2) ? 1 : 0;
425 static int foreach_vertex(game_state *state, space_cb cb, unsigned int f,
428 return foreach_sub(state, cb, f, ctx, 0, 0);
433 static int is_same_assoc(game_state *state,
434 int x1, int y1, int x2, int y2)
436 struct space *s1, *s2;
438 if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2))
441 s1 = &SPACE(state, x1, y1);
442 s2 = &SPACE(state, x2, y2);
443 assert(s1->type == s_tile && s2->type == s_tile);
444 if ((s1->flags & F_TILE_ASSOC) && (s2->flags & F_TILE_ASSOC) &&
445 s1->dotx == s2->dotx && s1->doty == s2->doty)
447 return 0; /* 0 if not same or not both associated. */
452 static int edges_into_vertex(game_state *state,
455 int dx, dy, nx, ny, count = 0;
457 assert(SPACE(state, x, y).type == s_vertex);
458 for (dx = -1; dx <= 1; dx++) {
459 for (dy = -1; dy <= 1; dy++) {
460 if (dx != 0 && dy != 0) continue;
461 if (dx == 0 && dy == 0) continue;
463 nx = x+dx; ny = y+dy;
464 if (!INGRID(state, nx, ny)) continue;
465 assert(SPACE(state, nx, ny).type == s_edge);
466 if (SPACE(state, nx, ny).flags & F_EDGE_SET)
474 static struct space *space_opposite_dot(struct game_state *state,
475 struct space *sp, struct space *dot)
484 if (!INGRID(state, tx, ty)) return NULL;
486 sp2 = &SPACE(state, tx, ty);
487 assert(sp2->type == sp->type);
491 static struct space *tile_opposite(struct game_state *state, struct space *sp)
495 assert(sp->flags & F_TILE_ASSOC);
496 dot = &SPACE(state, sp->dotx, sp->doty);
497 return space_opposite_dot(state, sp, dot);
500 static int dotfortile(game_state *state, space *tile, space *dot)
502 space *tile_opp = space_opposite_dot(state, tile, dot);
504 if (!tile_opp) return 0; /* opposite would be off grid */
505 if (tile_opp->flags & F_TILE_ASSOC &&
506 (tile_opp->dotx != dot->x || tile_opp->doty != dot->y))
507 return 0; /* opposite already associated with diff. dot */
511 static void adjacencies(struct game_state *state, struct space *sp,
512 struct space **a1s, struct space **a2s)
514 int dxs[4] = {-1, 1, 0, 0}, dys[4] = {0, 0, -1, 1};
517 /* this function needs optimising. */
519 for (n = 0; n < 4; n++) {
523 if (INGRID(state, x, y)) {
524 a1s[n] = &SPACE(state, x, y);
526 x += dxs[n]; y += dys[n];
528 if (INGRID(state, x, y))
529 a2s[n] = &SPACE(state, x, y);
533 a1s[n] = a2s[n] = NULL;
538 static int outline_tile_fordot(game_state *state, space *tile, int mark)
540 struct space *tadj[4], *eadj[4];
541 int i, didsth = 0, edge, same;
543 assert(tile->type == s_tile);
544 adjacencies(state, tile, eadj, tadj);
545 for (i = 0; i < 4; i++) {
546 if (!eadj[i]) continue;
548 edge = (eadj[i]->flags & F_EDGE_SET) ? 1 : 0;
550 if (!(tile->flags & F_TILE_ASSOC))
551 same = (tadj[i]->flags & F_TILE_ASSOC) ? 0 : 1;
553 same = ((tadj[i]->flags & F_TILE_ASSOC) &&
554 tile->dotx == tadj[i]->dotx &&
555 tile->doty == tadj[i]->doty) ? 1 : 0;
559 if (!edge && !same) {
560 if (mark) eadj[i]->flags |= F_EDGE_SET;
562 } else if (edge && same) {
563 if (mark) eadj[i]->flags &= ~F_EDGE_SET;
570 static void tiles_from_edge(struct game_state *state,
571 struct space *sp, struct space **ts)
575 if (IS_VERTICAL_EDGE(sp->x)) {
576 xs[0] = sp->x-1; ys[0] = sp->y;
577 xs[1] = sp->x+1; ys[1] = sp->y;
579 xs[0] = sp->x; ys[0] = sp->y-1;
580 xs[1] = sp->x; ys[1] = sp->y+1;
582 ts[0] = INGRID(state, xs[0], ys[0]) ? &SPACE(state, xs[0], ys[0]) : NULL;
583 ts[1] = INGRID(state, xs[1], ys[1]) ? &SPACE(state, xs[1], ys[1]) : NULL;
586 /* Check all tiles are associated with something, and all shapes
587 * are the correct symmetry (i.e. all tiles have a matching tile
588 * the opposite direction from the dot) */
589 static int cccb_assoc(game_state *state, space *tile, void *unused)
591 assert(tile->type == s_tile);
593 if (!(tile->flags & F_TILE_ASSOC)) return -1;
602 static int dgs_cb_check(game_state *state, space *tile, void *vctx)
604 struct dgs_ctx *ctx = (struct dgs_ctx *)vctx;
607 if (!(tile->flags & F_TILE_ASSOC)) return 0;
608 if (tile->dotx != ctx->dot->x ||
609 tile->doty != ctx->dot->y) return 0;
613 /* Check this tile has an opposite associated with same dot. */
614 opp = tile_opposite(state, tile);
615 if (!opp || !(opp->flags & F_TILE_ASSOC)) return -1;
616 if (opp->dotx != tile->dotx || opp->doty != tile->doty) return -1;
618 /* Check its edges are correct */
619 if (outline_tile_fordot(state, tile, 0) == 1)
620 return -1; /* there was some fixing required, we're wrong. */
625 static int dot_good_shape(game_state *state, space *dot, int mark)
632 if (mark) dot->flags &= ~F_GOOD;
634 if (foreach_tile(state, dgs_cb_check, 0, &ctx) == -1)
636 if (ctx.ndots == 0) return 0; /* no dots assoc. with tile. */
639 debug(("marking dot %d,%d good tile.\n", dot->x, dot->y));
640 dot->flags |= F_GOOD;
645 static int check_complete(game_state *state, int mark_errors)
649 /* Are all tiles associated? */
650 if (foreach_tile(state, cccb_assoc, 0, NULL) == -1)
653 /* Check all dots are associated, and their tiles are well-formed. */
654 for (i = 0; i < state->ndots; i++) {
655 if (!dot_good_shape(state, state->dots[i], mark_errors))
659 /*if (complete == 1) printf("Complete!\n");*/
663 /* Returns a move string for use by 'solve'; if you don't want the
664 * initial 'S;' use ret[2]. */
665 static char *diff_game(game_state *src, game_state *dest, int issolve)
667 int movelen = 0, movesize = 256, x, y, len;
668 char *move = snewn(movesize, char), buf[80], *sep = "";
669 char achar = issolve ? 'a' : 'A';
672 assert(src->sx == dest->sx && src->sy == dest->sy);
675 move[movelen++] = 'S';
678 move[movelen] = '\0';
679 for (x = 0; x < src->sx; x++) {
680 for (y = 0; y < src->sy; y++) {
681 sps = &SPACE(src, x, y);
682 spd = &SPACE(dest, x, y);
684 assert(sps->type == spd->type);
687 if (sps->type == s_tile) {
688 if ((sps->flags & F_TILE_ASSOC) &&
689 (spd->flags & F_TILE_ASSOC)) {
690 if (sps->dotx != spd->dotx ||
691 sps->doty != spd->doty)
692 /* Both associated; change association, if different */
693 len = sprintf(buf, "%s%c%d,%d,%d,%d", sep,
694 (int)achar, x, y, spd->dotx, spd->doty);
695 } else if (sps->flags & F_TILE_ASSOC)
696 /* Only src associated; remove. */
697 len = sprintf(buf, "%sU%d,%d", sep, x, y);
698 else if (spd->flags & F_TILE_ASSOC)
699 /* Only dest associated; add. */
700 len = sprintf(buf, "%s%c%d,%d,%d,%d", sep,
701 (int)achar, x, y, spd->dotx, spd->doty);
702 } else if (sps->type == s_edge) {
703 if ((sps->flags & F_EDGE_SET) != (spd->flags & F_EDGE_SET))
704 /* edge flags are different; flip them. */
705 len = sprintf(buf, "%sE%d,%d", sep, x, y);
708 if (movelen + len >= movesize) {
709 movesize = movelen + len + 256;
710 move = sresize(move, movesize, char);
712 strcpy(move + movelen, buf);
718 debug(("diff_game src then dest:\n"));
721 debug(("diff string %s\n", move));
725 /* Returns 1 if a dot here would not be too close to any other dots
726 * (and would avoid other game furniture). */
727 static int dot_is_possible(game_state *state, space *sp, int allow_assoc)
729 int bx = 0, by = 0, dx, dy;
736 if (IS_VERTICAL_EDGE(sp->x)) {
746 for (dx = -bx; dx <= bx; dx++) {
747 for (dy = -by; dy <= by; dy++) {
748 if (!INGRID(state, sp->x+dx, sp->y+dy)) continue;
750 adj = &SPACE(state, sp->x+dx, sp->y+dy);
752 if (!allow_assoc && (adj->flags & F_TILE_ASSOC))
755 if (dx != 0 || dy != 0) {
756 /* Other than our own square, no dots nearby. */
757 if (adj->flags & (F_DOT))
761 /* We don't want edges within our rectangle
762 * (but don't care about edges on the edge) */
763 if (abs(dx) < bx && abs(dy) < by &&
764 adj->flags & F_EDGE_SET)
771 /* ----------------------------------------------------------
772 * Game generation, structure creation, and descriptions.
775 static game_state *blank_game(int w, int h)
777 game_state *state = snew(game_state);
785 state->grid = snewn(state->sx * state->sy, struct space);
786 state->completed = state->used_solve = 0;
788 for (x = 0; x < state->sx; x++) {
789 for (y = 0; y < state->sy; y++) {
790 struct space *sp = &SPACE(state, x, y);
791 memset(sp, 0, sizeof(struct space));
794 if ((x % 2) == 0 && (y % 2) == 0)
796 else if ((x % 2) == 0 || (y % 2) == 0) {
798 if (x == 0 || y == 0 || x == state->sx-1 || y == state->sy-1)
799 sp->flags |= F_EDGE_SET;
808 state->me = NULL; /* filled in by new_game. */
814 static void game_update_dots(game_state *state)
816 int i, n, sz = state->sx * state->sy;
818 if (state->dots) sfree(state->dots);
821 for (i = 0; i < sz; i++) {
822 if (state->grid[i].flags & F_DOT) state->ndots++;
824 state->dots = snewn(state->ndots, space *);
826 for (i = 0; i < sz; i++) {
827 if (state->grid[i].flags & F_DOT)
828 state->dots[n++] = &state->grid[i];
832 static void clear_game(game_state *state, int cleardots)
836 /* don't erase edge flags around outline! */
837 for (x = 1; x < state->sx-1; x++) {
838 for (y = 1; y < state->sy-1; y++) {
840 SPACE(state, x, y).flags = 0;
842 SPACE(state, x, y).flags &= (F_DOT|F_DOT_BLACK);
845 if (cleardots) game_update_dots(state);
848 static game_state *dup_game(game_state *state)
850 game_state *ret = blank_game(state->w, state->h);
852 ret->completed = state->completed;
853 ret->used_solve = state->used_solve;
855 memcpy(ret->grid, state->grid,
856 ret->sx*ret->sy*sizeof(struct space));
858 game_update_dots(ret);
861 ret->cdiff = state->cdiff;
866 static void free_game(game_state *state)
868 if (state->dots) sfree(state->dots);
873 /* Game description is a sequence of letters representing the number
874 * of spaces (a = 0, y = 24) before the next dot; a-y for a white dot,
875 * and A-Y for a black dot. 'z' is 25 spaces (and no dot).
877 * I know it's a bitch to generate by hand, so we provide
881 static char *encode_game(game_state *state)
887 area = (state->sx-2) * (state->sy-2);
889 desc = snewn(area, char);
892 for (y = 1; y < state->sy-1; y++) {
893 for (x = 1; x < state->sx-1; x++) {
894 f = SPACE(state, x, y).flags;
896 /* a/A is 0 spaces between, b/B is 1 space, ...
897 * y/Y is 24 spaces, za/zA is 25 spaces, ...
898 * It's easier to count from 0 because we then
899 * don't have to special-case the top left-hand corner
900 * (which could be a dot with 0 spaces before it). */
908 *p++ = ((f & F_DOT_BLACK) ? 'A' : 'a') + run;
913 assert(p - desc < area);
915 desc = sresize(desc, p - desc, char);
922 space *olddot, *newdot;
925 enum { MD_CHECK, MD_MOVE };
927 static int movedot_cb(game_state *state, space *tile, void *vctx)
929 struct movedot *md = (struct movedot *)vctx;
930 space *newopp = NULL;
932 assert(tile->type == s_tile);
933 assert(md->olddot && md->newdot);
935 if (!(tile->flags & F_TILE_ASSOC)) return 0;
936 if (tile->dotx != md->olddot->x || tile->doty != md->olddot->y)
939 newopp = space_opposite_dot(state, tile, md->newdot);
943 /* If the tile is associated with the old dot, check its
944 * opposite wrt the _new_ dot is empty or same assoc. */
945 if (!newopp) return -1; /* no new opposite */
946 if (newopp->flags & F_TILE_ASSOC) {
947 if (newopp->dotx != md->olddot->x ||
948 newopp->doty != md->olddot->y)
949 return -1; /* associated, but wrong dot. */
954 /* Move dot associations: anything that was associated
955 * with the old dot, and its opposite wrt the new dot,
956 * become associated with the new dot. */
958 debug(("Associating %d,%d and %d,%d with new dot %d,%d.\n",
959 tile->x, tile->y, newopp->x, newopp->y,
960 md->newdot->x, md->newdot->y));
961 add_assoc(state, tile, md->newdot);
962 add_assoc(state, newopp, md->newdot);
963 return 1; /* we did something! */
968 /* For the given dot, first see if we could expand it into all the given
969 * extra spaces (by checking for empty spaces on the far side), and then
970 * see if we can move the dot to shift the CoG to include the new spaces.
972 static int dot_expand_or_move(game_state *state, space *dot,
973 space **toadd, int nadd)
976 int i, ret, nnew, cx, cy;
979 debug(("dot_expand_or_move: %d tiles for dot %d,%d\n",
980 nadd, dot->x, dot->y));
981 for (i = 0; i < nadd; i++)
982 debug(("dot_expand_or_move: dot %d,%d\n",
983 toadd[i]->x, toadd[i]->y));
984 assert(dot->flags & F_DOT);
986 /* First off, could we just expand the current dot's tile to cover
987 * the space(s) passed in and their opposites? */
988 for (i = 0; i < nadd; i++) {
989 tileopp = space_opposite_dot(state, toadd[i], dot);
990 if (!tileopp) goto noexpand;
991 if (tileopp->flags & F_TILE_ASSOC) goto noexpand;
993 /* OK, all spaces have valid empty opposites: associate spaces and
994 * opposites with our dot. */
995 for (i = 0; i < nadd; i++) {
996 tileopp = space_opposite_dot(state, toadd[i], dot);
997 add_assoc(state, toadd[i], dot);
998 add_assoc(state, tileopp, dot);
999 debug(("Added associations %d,%d and %d,%d --> %d,%d\n",
1000 toadd[i]->x, toadd[i]->y,
1001 tileopp->x, tileopp->y,
1008 /* Otherwise, try to move dot so as to encompass given spaces: */
1009 /* first, alculate the 'centre of gravity' of the new dot. */
1010 nnew = dot->nassoc + nadd; /* number of tiles assoc. with new dot. */
1011 cx = dot->x * dot->nassoc;
1012 cy = dot->y * dot->nassoc;
1013 for (i = 0; i < nadd; i++) {
1017 /* If the CoG isn't a whole number, it's not possible. */
1018 if ((cx % nnew) != 0 || (cy % nnew) != 0) {
1019 debug(("Unable to move dot %d,%d, CoG not whole number.\n",
1023 cx /= nnew; cy /= nnew;
1025 /* Check whether all spaces in the old tile would have a good
1026 * opposite wrt the new dot. */
1028 md.newdot = &SPACE(state, cx, cy);
1030 ret = foreach_tile(state, movedot_cb, IMPOSSIBLE_QUITS, &md);
1032 debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
1036 /* Also check whether all spaces we're adding would have a good
1037 * opposite wrt the new dot. */
1038 for (i = 0; i < nadd; i++) {
1039 tileopp = space_opposite_dot(state, toadd[i], md.newdot);
1040 if (tileopp && (tileopp->flags & F_TILE_ASSOC) &&
1041 (tileopp->dotx != dot->x || tileopp->doty != dot->y)) {
1045 debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
1051 /* If we've got here, we're ok. First, associate all of 'toadd'
1052 * with the _old_ dot (so they'll get fixed up, with their opposites,
1053 * in the next step). */
1054 for (i = 0; i < nadd; i++) {
1055 debug(("Associating to-add %d,%d with old dot %d,%d.\n",
1056 toadd[i]->x, toadd[i]->y, dot->x, dot->y));
1057 add_assoc(state, toadd[i], dot);
1060 /* Finally, move the dot and fix up all the old associations. */
1061 debug(("Moving dot at %d,%d to %d,%d\n",
1062 dot->x, dot->y, md.newdot->x, md.newdot->y));
1067 ret = foreach_tile(state, movedot_cb, 0, &md);
1074 /* Hard-code to a max. of 2x2 squares, for speed (less malloc) */
1076 #define MAX_OUTSIDE 8
1078 #define MAX_TILE_PERC 20
1080 static int generate_try_block(game_state *state, random_state *rs,
1081 int x1, int y1, int x2, int y2)
1083 int x, y, nadd = 0, nout = 0, i, maxsz;
1084 space *sp, *toadd[MAX_TOADD], *outside[MAX_OUTSIDE], *dot;
1086 if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2)) return 0;
1088 /* We limit the maximum size of tiles to be ~2*sqrt(area); so,
1089 * a 5x5 grid shouldn't have anything >10 tiles, a 20x20 grid
1090 * nothing >40 tiles. */
1091 maxsz = (int)sqrt((double)(state->w * state->h)) * 2;
1092 debug(("generate_try_block, maxsz %d\n", maxsz));
1094 /* Make a static list of the spaces; if any space is already
1095 * associated then quit immediately. */
1096 for (x = x1; x <= x2; x += 2) {
1097 for (y = y1; y <= y2; y += 2) {
1098 assert(nadd < MAX_TOADD);
1099 sp = &SPACE(state, x, y);
1100 assert(sp->type == s_tile);
1101 if (sp->flags & F_TILE_ASSOC) return 0;
1106 /* Make a list of the spaces outside of our block, and shuffle it. */
1107 #define OUTSIDE(x, y) do { \
1108 if (INGRID(state, (x), (y))) { \
1109 assert(nout < MAX_OUTSIDE); \
1110 outside[nout++] = &SPACE(state, (x), (y)); \
1113 for (x = x1; x <= x2; x += 2) {
1117 for (y = y1; y <= y2; y += 2) {
1121 shuffle(outside, nout, sizeof(space *), rs);
1123 for (i = 0; i < nout; i++) {
1124 if (!(outside[i]->flags & F_TILE_ASSOC)) continue;
1125 dot = &SPACE(state, outside[i]->dotx, outside[i]->doty);
1126 if (dot->nassoc >= maxsz) {
1127 debug(("Not adding to dot %d,%d, large enough (%d) already.\n",
1128 dot->x, dot->y, dot->nassoc));
1131 if (dot_expand_or_move(state, dot, toadd, nadd)) return 1;
1136 #ifdef STANDALONE_SOLVER
1138 #define MAXTRIES maxtries
1143 static int solver_obvious_dot(game_state *state,space *dot);
1147 static void generate_pass(game_state *state, random_state *rs, int *scratch,
1148 int perc, unsigned int flags)
1150 int sz = state->sx*state->sy, nspc, i, ret;
1152 shuffle(scratch, sz, sizeof(int), rs);
1154 /* This bug took me a, er, little while to track down. On PalmOS,
1155 * which has 16-bit signed ints, puzzles over about 9x9 started
1156 * failing to generate because the nspc calculation would start
1157 * to overflow, causing the dots not to be filled in properly. */
1158 nspc = (int)(((long)perc * (long)sz) / 100L);
1159 debug(("generate_pass: %d%% (%d of %dx%d) squares, flags 0x%x\n",
1160 perc, nspc, state->sx, state->sy, flags));
1162 for (i = 0; i < nspc; i++) {
1163 space *sp = &state->grid[scratch[i]];
1164 int x1 = sp->x, y1 = sp->y, x2 = sp->x, y2 = sp->y;
1166 if (sp->type == s_edge) {
1167 if (IS_VERTICAL_EDGE(sp->x)) {
1173 if (sp->type != s_vertex) {
1174 /* heuristic; expanding from vertices tends to generate lots of
1175 * too-big regions of tiles. */
1176 if (generate_try_block(state, rs, x1, y1, x2, y2))
1177 continue; /* we expanded successfully. */
1180 if (!(flags & GP_DOTS)) continue;
1182 if ((sp->type == s_edge) && (i % 2)) {
1183 debug(("Omitting edge %d,%d as half-of.\n", sp->x, sp->y));
1187 /* If we've got here we might want to put a dot down. Check
1188 * if we can, and add one if so. */
1189 if (dot_is_possible(state, sp, 0)) {
1191 ret = solver_obvious_dot(state, sp);
1193 debug(("Added dot (and obvious associations) at %d,%d\n",
1201 static int solver_state(game_state *state, int maxdiff);
1203 static char *new_game_desc(game_params *params, random_state *rs,
1204 char **aux, int interactive)
1206 game_state *state = blank_game(params->w, params->h), *copy;
1208 int *scratch, sz = state->sx*state->sy, i;
1209 int diff, ntries = 0;
1211 /* Random list of squares to try and process, one-by-one. */
1212 scratch = snewn(sz, int);
1213 for (i = 0; i < sz; i++) scratch[i] = i;
1216 clear_game(state, 1);
1219 /* generate_pass(state, rs, scratch, 10, GP_DOTS); */
1220 /* generate_pass(state, rs, scratch, 100, 0); */
1221 generate_pass(state, rs, scratch, 100, GP_DOTS);
1223 game_update_dots(state);
1227 char *tmp = encode_game(state);
1228 debug(("new_game_desc state %dx%d:%s\n", params->w, params->h, tmp));
1233 copy = dup_game(state);
1234 clear_game(copy, 0);
1236 diff = solver_state(copy, params->diff);
1239 assert(diff != DIFF_IMPOSSIBLE);
1240 if (diff != params->diff) {
1242 * We'll grudgingly accept a too-easy puzzle, but we must
1243 * _not_ permit a too-hard one (one which the solver
1244 * couldn't handle at all).
1246 if (diff > params->diff ||
1247 ntries < MAXTRIES) goto generate;
1250 desc = encode_game(state);
1251 #ifndef STANDALONE_SOLVER
1252 debug(("new_game_desc generated: \n"));
1262 static int solver_obvious(game_state *state);
1264 static int dots_too_close(game_state *state)
1266 /* Quick-and-dirty check, using half the solver:
1267 * solver_obvious will only fail if the dots are
1268 * too close together, so dot-proximity associations
1270 game_state *tmp = dup_game(state);
1271 int ret = solver_obvious(tmp);
1273 return (ret == -1) ? 1 : 0;
1276 static game_state *load_game(game_params *params, char *desc,
1279 game_state *state = blank_game(params->w, params->h);
1291 if (n >= 'a' && n <= 'y') {
1294 } else if (n >= 'A' && n <= 'Y') {
1298 why = "Invalid characters in game description"; goto fail;
1300 /* if we got here we incremented i and have a dot to add. */
1301 y = (i / (state->sx-2)) + 1;
1302 x = (i % (state->sx-2)) + 1;
1303 if (!INUI(state, x, y)) {
1304 why = "Too much data to fit in grid"; goto fail;
1306 add_dot(&SPACE(state, x, y));
1307 SPACE(state, x, y).flags |= df;
1310 game_update_dots(state);
1312 if (dots_too_close(state)) {
1313 why = "Dots too close together"; goto fail;
1320 if (why_r) *why_r = why;
1324 static char *validate_desc(game_params *params, char *desc)
1327 game_state *dummy = load_game(params, desc, &why);
1336 static game_state *new_game(midend *me, game_params *params, char *desc)
1338 game_state *state = load_game(params, desc, NULL);
1340 assert("Unable to load ?validated game.");
1349 /* ----------------------------------------------------------
1350 * Solver and all its little wizards.
1353 int solver_recurse_depth;
1355 typedef struct solver_ctx {
1357 int sz; /* state->sx * state->sy */
1358 space **scratch; /* size sz */
1362 static solver_ctx *new_solver(game_state *state)
1364 solver_ctx *sctx = snew(solver_ctx);
1365 sctx->state = state;
1366 sctx->sz = state->sx*state->sy;
1367 sctx->scratch = snewn(sctx->sz, space *);
1371 static void free_solver(solver_ctx *sctx)
1373 sfree(sctx->scratch);
1377 /* Solver ideas so far:
1379 * For any empty space, work out how many dots it could associate
1381 * it needs line-of-sight
1382 * it needs an empty space on the far side
1383 * any adjacent lines need corresponding line possibilities.
1386 /* The solver_ctx should keep a list of dot positions, for quicker looping.
1388 * Solver techniques, in order of difficulty:
1389 * obvious adjacency to dots
1390 * transferring tiles to opposite side
1391 * transferring lines to opposite side
1392 * one possible dot for a given tile based on opposite availability
1393 * tile with 3 definite edges next to an associated tile must associate
1396 * one possible dot for a given tile based on line-of-sight
1399 static int solver_add_assoc(game_state *state, space *tile, int dx, int dy,
1402 space *dot, *tile_opp;
1404 dot = &SPACE(state, dx, dy);
1405 tile_opp = space_opposite_dot(state, tile, dot);
1407 assert(tile->type == s_tile);
1408 if (tile->flags & F_TILE_ASSOC) {
1409 if ((tile->dotx != dx) || (tile->doty != dy)) {
1410 solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
1411 "already --> %d,%d.\n",
1412 solver_recurse_depth*4, "",
1413 tile->x, tile->y, dx, dy, why,
1414 tile->dotx, tile->doty));
1417 return 0; /* no-op */
1420 solvep(("%*s%d,%d --> %d,%d impossible, no opposite tile.\n",
1421 solver_recurse_depth*4, "", tile->x, tile->y, dx, dy));
1424 if (tile_opp->flags & F_TILE_ASSOC &&
1425 (tile_opp->dotx != dx || tile_opp->doty != dy)) {
1426 solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
1427 "opposite already --> %d,%d.\n",
1428 solver_recurse_depth*4, "",
1429 tile->x, tile->y, dx, dy, why,
1430 tile_opp->dotx, tile_opp->doty));
1434 add_assoc(state, tile, dot);
1435 add_assoc(state, tile_opp, dot);
1436 solvep(("%*sSetting %d,%d --> %d,%d (%s).\n",
1437 solver_recurse_depth*4, "",
1438 tile->x, tile->y,dx, dy, why));
1439 solvep(("%*sSetting %d,%d --> %d,%d (%s, opposite).\n",
1440 solver_recurse_depth*4, "",
1441 tile_opp->x, tile_opp->y, dx, dy, why));
1445 static int solver_obvious_dot(game_state *state, space *dot)
1447 int dx, dy, ret, didsth = 0;
1450 debug(("%*ssolver_obvious_dot for %d,%d.\n",
1451 solver_recurse_depth*4, "", dot->x, dot->y));
1453 assert(dot->flags & F_DOT);
1454 for (dx = -1; dx <= 1; dx++) {
1455 for (dy = -1; dy <= 1; dy++) {
1456 if (!INGRID(state, dot->x+dx, dot->y+dy)) continue;
1458 tile = &SPACE(state, dot->x+dx, dot->y+dy);
1459 if (tile->type == s_tile) {
1460 ret = solver_add_assoc(state, tile, dot->x, dot->y,
1462 if (ret < 0) return -1;
1463 if (ret > 0) didsth = 1;
1470 static int solver_obvious(game_state *state)
1472 int i, didsth = 0, ret;
1474 debug(("%*ssolver_obvious.\n", solver_recurse_depth*4, ""));
1476 for (i = 0; i < state->ndots; i++) {
1477 ret = solver_obvious_dot(state, state->dots[i]);
1478 if (ret < 0) return -1;
1479 if (ret > 0) didsth = 1;
1484 static int solver_lines_opposite_cb(game_state *state, space *edge, void *ctx)
1486 int didsth = 0, n, dx, dy;
1487 space *tiles[2], *tile_opp, *edge_opp;
1489 assert(edge->type == s_edge);
1491 tiles_from_edge(state, edge, tiles);
1493 /* if tiles[0] && tiles[1] && they're both associated
1494 * and they're both associated with different dots,
1495 * ensure the line is set. */
1496 if (!(edge->flags & F_EDGE_SET) &&
1497 tiles[0] && tiles[1] &&
1498 (tiles[0]->flags & F_TILE_ASSOC) &&
1499 (tiles[1]->flags & F_TILE_ASSOC) &&
1500 (tiles[0]->dotx != tiles[1]->dotx ||
1501 tiles[0]->doty != tiles[1]->doty)) {
1502 /* No edge, but the two adjacent tiles are both
1503 * associated with different dots; add the edge. */
1504 solvep(("%*sSetting edge %d,%d - tiles different dots.\n",
1505 solver_recurse_depth*4, "", edge->x, edge->y));
1506 edge->flags |= F_EDGE_SET;
1510 if (!(edge->flags & F_EDGE_SET)) return didsth;
1511 for (n = 0; n < 2; n++) {
1512 if (!tiles[n]) continue;
1513 assert(tiles[n]->type == s_tile);
1514 if (!(tiles[n]->flags & F_TILE_ASSOC)) continue;
1516 tile_opp = tile_opposite(state, tiles[n]);
1518 solvep(("%*simpossible: edge %d,%d has assoc. tile %d,%d"
1519 " with no opposite.\n",
1520 solver_recurse_depth*4, "",
1521 edge->x, edge->y, tiles[n]->x, tiles[n]->y));
1522 /* edge of tile has no opposite edge (off grid?);
1523 * this is impossible. */
1527 dx = tiles[n]->x - edge->x;
1528 dy = tiles[n]->y - edge->y;
1529 assert(INGRID(state, tile_opp->x+dx, tile_opp->y+dy));
1530 edge_opp = &SPACE(state, tile_opp->x+dx, tile_opp->y+dy);
1531 if (!(edge_opp->flags & F_EDGE_SET)) {
1532 solvep(("%*sSetting edge %d,%d as opposite %d,%d\n",
1533 solver_recurse_depth*4, "",
1534 tile_opp->x-dx, tile_opp->y-dy, edge->x, edge->y));
1535 edge_opp->flags |= F_EDGE_SET;
1542 static int solver_spaces_oneposs_cb(game_state *state, space *tile, void *ctx)
1545 struct space *edgeadj[4], *tileadj[4];
1548 assert(tile->type == s_tile);
1549 if (tile->flags & F_TILE_ASSOC) return 0;
1551 adjacencies(state, tile, edgeadj, tileadj);
1553 /* Empty tile. If each edge is either set, or associated with
1554 * the same dot, we must also associate with dot. */
1555 eset = 0; dotx = -1; doty = -1;
1556 for (n = 0; n < 4; n++) {
1558 assert(edgeadj[n]->type == s_edge);
1559 if (edgeadj[n]->flags & F_EDGE_SET) {
1563 assert(tileadj[n]->type == s_tile);
1565 /* If an adjacent tile is empty we can't make any deductions.*/
1566 if (!(tileadj[n]->flags & F_TILE_ASSOC))
1569 /* If an adjacent tile is assoc. with a different dot
1570 * we can't make any deductions. */
1571 if (dotx != -1 && doty != -1 &&
1572 (tileadj[n]->dotx != dotx ||
1573 tileadj[n]->doty != doty))
1576 dotx = tileadj[n]->dotx;
1577 doty = tileadj[n]->doty;
1581 solvep(("%*simpossible: empty tile %d,%d has 4 edges\n",
1582 solver_recurse_depth*4, "",
1586 assert(dotx != -1 && doty != -1);
1588 ret = solver_add_assoc(state, tile, dotx, doty, "rest are edges");
1589 if (ret == -1) return -1;
1590 assert(ret != 0); /* really should have done something. */
1595 /* Improved algorithm for tracking line-of-sight from dots, and not spaces.
1597 * The solver_ctx already stores a list of dots: the algorithm proceeds by
1598 * expanding outwards from each dot in turn, expanding first to the boundary
1599 * of its currently-connected tile and then to all empty tiles that could see
1600 * it. Empty tiles will be flagged with a 'can see dot <x,y>' sticker.
1602 * Expansion will happen by (symmetrically opposite) pairs of squares; if
1603 * a square hasn't an opposite number there's no point trying to expand through
1604 * it. Empty tiles will therefore also be tagged in pairs.
1606 * If an empty tile already has a 'can see dot <x,y>' tag from a previous dot,
1607 * it (and its partner) gets untagged (or, rather, a 'can see two dots' tag)
1608 * because we're looking for single-dot possibilities.
1610 * Once we've gone through all the dots, any which still have a 'can see dot'
1611 * tag get associated with that dot (because it must have been the only one);
1612 * any without any tag (i.e. that could see _no_ dots) cause an impossibility
1615 * The expansion will happen each time with a stored list of (space *) pairs,
1616 * rather than a mark-and-sweep idea; that's horrifically inefficient.
1618 * expansion algorithm:
1620 * * allocate list of (space *) the size of s->sx*s->sy.
1621 * * allocate second grid for (flags, dotx, doty) size of sx*sy.
1623 * clear second grid (flags = 0, all dotx and doty = 0)
1624 * flags: F_REACHABLE, F_MULTIPLE
1627 * * for each dot, start with one pair of tiles that are associated with it --
1628 * * vertex --> (dx+1, dy+1), (dx-1, dy-1)
1629 * * edge --> (adj1, adj2)
1630 * * tile --> (tile, tile) ???
1631 * * mark that pair of tiles with F_MARK, clear all other F_MARKs.
1632 * * add two tiles to start of list.
1634 * set start = 0, end = next = 2
1636 * from (start to end-1, step 2) {
1637 * * we have two tiles (t1, t2), opposites wrt our dot.
1638 * * for each (at1) sensible adjacent tile to t1 (i.e. not past an edge):
1639 * * work out at2 as the opposite to at1
1640 * * assert at1 and at2 have the same F_MARK values.
1641 * * if at1 & F_MARK ignore it (we've been there on a previous sweep)
1642 * * if either are associated with a different dot
1643 * * mark both with F_MARK (so we ignore them later)
1644 * * otherwise (assoc. with our dot, or empty):
1645 * * mark both with F_MARK
1646 * * add their space * values to the end of the list, set next += 2.
1650 * * we didn't add any new squares; exit the loop.
1652 * * set start = next+1, end = next. go round again
1654 * We've finished expanding from the dot. Now, for each square we have
1655 * in our list (--> each square with F_MARK):
1656 * * if the tile is empty:
1657 * * if F_REACHABLE was already set
1660 * * set F_REACHABLE, set dotx and doty to our dot.
1662 * Then, continue the whole thing for each dot in turn.
1664 * Once we've done for each dot, go through the entire grid looking for
1665 * empty tiles: for each empty tile:
1666 * if F_REACHABLE and not F_MULTIPLE, set that dot (and its double)
1667 * if !F_REACHABLE, return as impossible.
1671 /* Returns 1 if this tile is either already associated with this dot,
1673 static int solver_expand_checkdot(space *tile, space *dot)
1675 if (!(tile->flags & F_TILE_ASSOC)) return 1;
1676 if (tile->dotx == dot->x && tile->doty == dot->y) return 1;
1680 static void solver_expand_fromdot(game_state *state, space *dot, solver_ctx *sctx)
1682 int i, j, x, y, start, end, next;
1685 /* Clear the grid of the (space) flags we'll use. */
1687 /* This is well optimised; analysis showed that:
1688 for (i = 0; i < sctx->sz; i++) state->grid[i].flags &= ~F_MARK;
1689 took up ~85% of the total function time! */
1690 for (y = 1; y < state->sy; y += 2) {
1691 sp = &SPACE(state, 1, y);
1692 for (x = 1; x < state->sx; x += 2, sp += 2)
1693 sp->flags &= ~F_MARK;
1696 /* Seed the list of marked squares with two that must be associated
1697 * with our dot (possibly the same space) */
1698 if (dot->type == s_tile) {
1699 sctx->scratch[0] = sctx->scratch[1] = dot;
1700 } else if (dot->type == s_edge) {
1701 tiles_from_edge(state, dot, sctx->scratch);
1702 } else if (dot->type == s_vertex) {
1703 /* pick two of the opposite ones arbitrarily. */
1704 sctx->scratch[0] = &SPACE(state, dot->x-1, dot->y-1);
1705 sctx->scratch[1] = &SPACE(state, dot->x+1, dot->y+1);
1707 assert(sctx->scratch[0]->flags & F_TILE_ASSOC);
1708 assert(sctx->scratch[1]->flags & F_TILE_ASSOC);
1710 sctx->scratch[0]->flags |= F_MARK;
1711 sctx->scratch[1]->flags |= F_MARK;
1713 debug(("%*sexpand from dot %d,%d seeded with %d,%d and %d,%d.\n",
1714 solver_recurse_depth*4, "", dot->x, dot->y,
1715 sctx->scratch[0]->x, sctx->scratch[0]->y,
1716 sctx->scratch[1]->x, sctx->scratch[1]->y));
1718 start = 0; end = 2; next = 2;
1721 debug(("%*sexpand: start %d, end %d, next %d\n",
1722 solver_recurse_depth*4, "", start, end, next));
1723 for (i = start; i < end; i += 2) {
1724 space *t1 = sctx->scratch[i]/*, *t2 = sctx->scratch[i+1]*/;
1725 space *edges[4], *tileadj[4], *tileadj2;
1727 adjacencies(state, t1, edges, tileadj);
1729 for (j = 0; j < 4; j++) {
1731 if (edges[j]->flags & F_EDGE_SET) continue;
1734 if (tileadj[j]->flags & F_MARK) continue; /* seen before. */
1736 /* We have a tile adjacent to t1; find its opposite. */
1737 tileadj2 = space_opposite_dot(state, tileadj[j], dot);
1739 debug(("%*sMarking %d,%d, no opposite.\n",
1740 solver_recurse_depth*4, "",
1741 tileadj[j]->x, tileadj[j]->y));
1742 tileadj[j]->flags |= F_MARK;
1743 continue; /* no opposite, so mark for next time. */
1745 /* If the tile had an opposite we should have either seen both of
1746 * these, or neither of these, before. */
1747 assert(!(tileadj2->flags & F_MARK));
1749 if (solver_expand_checkdot(tileadj[j], dot) &&
1750 solver_expand_checkdot(tileadj2, dot)) {
1751 /* Both tiles could associate with this dot; add them to
1753 debug(("%*sAdding %d,%d and %d,%d to possibles list.\n",
1754 solver_recurse_depth*4, "",
1755 tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y));
1756 sctx->scratch[next++] = tileadj[j];
1757 sctx->scratch[next++] = tileadj2;
1759 /* Either way, we've seen these tiles already so mark them. */
1760 debug(("%*sMarking %d,%d and %d,%d.\n",
1761 solver_recurse_depth*4, "",
1762 tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y));
1763 tileadj[j]->flags |= F_MARK;
1764 tileadj2->flags |= F_MARK;
1768 /* We added more squares; go back and try again. */
1769 start = end; end = next; goto expand;
1772 /* We've expanded as far as we can go. Now we update the main flags
1773 * on all tiles we've expanded into -- if they were empty, we have
1774 * found possible associations for this dot. */
1775 for (i = 0; i < end; i++) {
1776 if (sctx->scratch[i]->flags & F_TILE_ASSOC) continue;
1777 if (sctx->scratch[i]->flags & F_REACHABLE) {
1778 /* This is (at least) the second dot this tile could
1779 * associate with. */
1780 debug(("%*sempty tile %d,%d could assoc. other dot %d,%d\n",
1781 solver_recurse_depth*4, "",
1782 sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y));
1783 sctx->scratch[i]->flags |= F_MULTIPLE;
1785 /* This is the first (possibly only) dot. */
1786 debug(("%*sempty tile %d,%d could assoc. 1st dot %d,%d\n",
1787 solver_recurse_depth*4, "",
1788 sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y));
1789 sctx->scratch[i]->flags |= F_REACHABLE;
1790 sctx->scratch[i]->dotx = dot->x;
1791 sctx->scratch[i]->doty = dot->y;
1797 static int solver_expand_postcb(game_state *state, space *tile, void *ctx)
1799 assert(tile->type == s_tile);
1801 if (tile->flags & F_TILE_ASSOC) return 0;
1803 if (!(tile->flags & F_REACHABLE)) {
1804 solvep(("%*simpossible: space (%d,%d) can reach no dots.\n",
1805 solver_recurse_depth*4, "", tile->x, tile->y));
1808 if (tile->flags & F_MULTIPLE) return 0;
1810 return solver_add_assoc(state, tile, tile->dotx, tile->doty,
1811 "single possible dot after expansion");
1814 static int solver_expand_dots(game_state *state, solver_ctx *sctx)
1818 for (i = 0; i < sctx->sz; i++)
1819 state->grid[i].flags &= ~(F_REACHABLE|F_MULTIPLE);
1821 for (i = 0; i < state->ndots; i++)
1822 solver_expand_fromdot(state, state->dots[i], sctx);
1824 return foreach_tile(state, solver_expand_postcb, IMPOSSIBLE_QUITS, sctx);
1827 struct recurse_ctx {
1832 static int solver_recurse_cb(game_state *state, space *tile, void *ctx)
1834 struct recurse_ctx *rctx = (struct recurse_ctx *)ctx;
1837 assert(tile->type == s_tile);
1838 if (tile->flags & F_TILE_ASSOC) return 0;
1840 /* We're unassociated: count up all the dots we could associate with. */
1841 for (i = 0; i < state->ndots; i++) {
1842 if (dotfortile(state, tile, state->dots[i]))
1845 if (n > rctx->bestn) {
1852 static int solver_state(game_state *state, int maxdiff);
1854 #define MAXRECURSE 5
1856 static int solver_recurse(game_state *state, int maxdiff)
1858 int diff = DIFF_IMPOSSIBLE, ret, n, gsz = state->sx * state->sy;
1859 space *ingrid, *outgrid = NULL, *bestopp;
1860 struct recurse_ctx rctx;
1862 if (solver_recurse_depth >= MAXRECURSE) {
1863 solvep(("Limiting recursion to %d, returning.", MAXRECURSE));
1864 return DIFF_UNFINISHED;
1867 /* Work out the cell to recurse on; go through all unassociated tiles
1868 * and find which one has the most possible dots it could associate
1873 foreach_tile(state, solver_recurse_cb, 0, &rctx);
1874 if (rctx.bestn == 0) return DIFF_IMPOSSIBLE; /* or assert? */
1877 solvep(("%*sRecursing around %d,%d, with %d possible dots.\n",
1878 solver_recurse_depth*4, "",
1879 rctx.best->x, rctx.best->y, rctx.bestn));
1881 #ifdef STANDALONE_SOLVER
1882 solver_recurse_depth++;
1885 ingrid = snewn(gsz, struct space);
1886 memcpy(ingrid, state->grid, gsz * sizeof(struct space));
1888 for (n = 0; n < state->ndots; n++) {
1889 memcpy(state->grid, ingrid, gsz * sizeof(struct space));
1891 if (!dotfortile(state, rctx.best, state->dots[n])) continue;
1893 /* set cell (temporarily) pointing to that dot. */
1894 solver_add_assoc(state, rctx.best,
1895 state->dots[n]->x, state->dots[n]->y,
1896 "Attempting for recursion");
1898 ret = solver_state(state, maxdiff);
1900 if (diff == DIFF_IMPOSSIBLE && ret != DIFF_IMPOSSIBLE) {
1901 /* we found our first solved grid; copy it away. */
1903 outgrid = snewn(gsz, struct space);
1904 memcpy(outgrid, state->grid, gsz * sizeof(struct space));
1906 /* reset cell back to unassociated. */
1907 bestopp = tile_opposite(state, rctx.best);
1908 assert(bestopp && bestopp->flags & F_TILE_ASSOC);
1910 remove_assoc(state, rctx.best);
1911 remove_assoc(state, bestopp);
1913 if (ret == DIFF_AMBIGUOUS || ret == DIFF_UNFINISHED)
1915 else if (ret == DIFF_IMPOSSIBLE)
1918 /* precisely one solution */
1919 if (diff == DIFF_IMPOSSIBLE)
1920 diff = DIFF_UNREASONABLE;
1922 diff = DIFF_AMBIGUOUS;
1924 /* if we've found >1 solution, or ran out of recursion,
1925 * give up immediately. */
1926 if (diff == DIFF_AMBIGUOUS || diff == DIFF_UNFINISHED)
1930 #ifdef STANDALONE_SOLVER
1931 solver_recurse_depth--;
1935 /* we found (at least one) soln; copy it back to state */
1936 memcpy(state->grid, outgrid, gsz * sizeof(struct space));
1943 static int solver_state(game_state *state, int maxdiff)
1945 solver_ctx *sctx = new_solver(state);
1946 int ret, diff = DIFF_NORMAL;
1948 ret = solver_obvious(state);
1950 diff = DIFF_IMPOSSIBLE;
1954 #define CHECKRET(d) do { \
1955 if (ret < 0) { diff = DIFF_IMPOSSIBLE; goto got_result; } \
1956 if (ret > 0) { diff = max(diff, (d)); goto cont; } \
1961 ret = foreach_edge(state, solver_lines_opposite_cb,
1962 IMPOSSIBLE_QUITS, sctx);
1963 CHECKRET(DIFF_NORMAL);
1965 ret = foreach_tile(state, solver_spaces_oneposs_cb,
1966 IMPOSSIBLE_QUITS, sctx);
1967 CHECKRET(DIFF_NORMAL);
1969 ret = solver_expand_dots(state, sctx);
1970 CHECKRET(DIFF_NORMAL);
1972 if (maxdiff <= DIFF_NORMAL)
1977 /* if we reach here, we've made no deductions, so we terminate. */
1981 if (check_complete(state, 0)) goto got_result;
1983 diff = (maxdiff >= DIFF_UNREASONABLE) ?
1984 solver_recurse(state, maxdiff) : DIFF_UNFINISHED;
1988 #ifndef STANDALONE_SOLVER
1989 debug(("solver_state ends:\n"));
1997 static char *solve_game(game_state *state, game_state *currstate,
1998 char *aux, char **error)
2000 game_state *tosolve;
2005 tosolve = dup_game(currstate);
2006 diff = solver_state(tosolve, DIFF_UNREASONABLE);
2007 if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) {
2008 debug(("solve_game solved with current state.\n"));
2013 tosolve = dup_game(state);
2014 diff = solver_state(tosolve, DIFF_UNREASONABLE);
2015 if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) {
2016 debug(("solve_game solved with original state.\n"));
2025 * Clear tile associations: the solution will only include the
2028 for (i = 0; i < tosolve->sx*tosolve->sy; i++)
2029 tosolve->grid[i].flags &= ~F_TILE_ASSOC;
2030 ret = diff_game(currstate, tosolve, 1);
2036 /* ----------------------------------------------------------
2042 int dx, dy; /* pixel coords of drag pos. */
2043 int dotx, doty; /* grid coords of dot we're dragging from. */
2044 int srcx, srcy; /* grid coords of drag start */
2047 static game_ui *new_ui(game_state *state)
2049 game_ui *ui = snew(game_ui);
2050 ui->dragging = FALSE;
2054 static void free_ui(game_ui *ui)
2059 static char *encode_ui(game_ui *ui)
2064 static void decode_ui(game_ui *ui, char *encoding)
2068 static void game_changed_state(game_ui *ui, game_state *oldstate,
2069 game_state *newstate)
2073 #define FLASH_TIME 0.15F
2075 #define PREFERRED_TILE_SIZE 32
2076 #define TILE_SIZE (ds->tilesize)
2077 #define DOT_SIZE (TILE_SIZE / 4)
2078 #define EDGE_THICKNESS (TILE_SIZE / 16)
2079 #define BORDER TILE_SIZE
2081 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
2082 #define SCOORD(x) ( ((x) * TILE_SIZE)/2 + BORDER )
2083 #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
2085 #define DRAW_WIDTH (BORDER * 2 + ds->w * TILE_SIZE)
2086 #define DRAW_HEIGHT (BORDER * 2 + ds->h * TILE_SIZE)
2088 struct game_drawstate {
2092 unsigned long *grid;
2096 int dragging, dragx, dragy;
2098 int *colour_scratch;
2101 #define CORNER_TOLERANCE 0.15F
2102 #define CENTRE_TOLERANCE 0.15F
2105 * Round FP coordinates to the centre of the nearest edge.
2108 static void coord_round_to_edge(float x, float y, int *xr, int *yr)
2110 float xs, ys, xv, yv, dx, dy;
2113 * Find the nearest square-centre.
2115 xs = (float)floor(x) + 0.5F;
2116 ys = (float)floor(y) + 0.5F;
2119 * Find the nearest grid vertex.
2121 xv = (float)floor(x + 0.5F);
2122 yv = (float)floor(y + 0.5F);
2125 * Determine whether the horizontal or vertical edge from that
2126 * vertex alongside that square is closer to us, by comparing
2127 * distances from the square cente.
2129 dx = (float)fabs(x - xs);
2130 dy = (float)fabs(y - ys);
2132 /* Vertical edge: x-coord of corner,
2133 * y-coord of square centre. */
2135 *yr = 1 + 2 * (int)floor(ys);
2137 /* Horizontal edge: x-coord of square centre,
2138 * y-coord of corner. */
2139 *xr = 1 + 2 * (int)floor(xs);
2146 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
2147 int x, int y, int button)
2153 px = 2*FROMCOORD((float)x) + 0.5;
2154 py = 2*FROMCOORD((float)y) + 0.5;
2158 if (button == 'C' || button == 'c') return dupstr("C");
2160 if (button == 'S' || button == 's') {
2162 game_state *tmp = dup_game(state);
2163 state->cdiff = solver_state(tmp, DIFF_UNREASONABLE-1);
2164 ret = diff_game(state, tmp, 0);
2169 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2170 if (!INUI(state, px, py)) return NULL;
2171 sp = &SPACE(state, px, py);
2172 if (!dot_is_possible(state, sp, 1)) return NULL;
2173 sprintf(buf, "%c%d,%d",
2174 (char)((button == LEFT_BUTTON) ? 'D' : 'd'), px, py);
2181 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
2182 int x, int y, int button)
2184 /* UI operations (play mode):
2186 * Toggle edge (set/unset) (left-click on edge)
2187 * Associate space with dot (left-drag from dot)
2188 * Unassociate space (left-drag from space off grid)
2189 * Autofill lines around shape? (right-click?)
2191 * (edit mode; will clear all lines/associations)
2193 * Add or remove dot (left-click)
2198 struct space *sp, *dot;
2200 if (button == 'H' || button == 'h' ||
2201 button == 'S' || button == 's') {
2203 game_state *tmp = dup_game(state);
2204 if (button == 'H' || button == 'h')
2205 solver_obvious(tmp);
2207 solver_state(tmp, DIFF_UNREASONABLE-1);
2208 ret = diff_game(state, tmp, 0);
2213 if (button == LEFT_BUTTON) {
2214 coord_round_to_edge(FROMCOORD((float)x), FROMCOORD((float)y),
2217 if (!INUI(state, px, py)) return NULL;
2219 sp = &SPACE(state, px, py);
2220 assert(sp->type == s_edge);
2222 sprintf(buf, "E%d,%d", px, py);
2225 } else if (button == RIGHT_BUTTON) {
2228 px = (int)(2*FROMCOORD((float)x) + 0.5);
2229 py = (int)(2*FROMCOORD((float)y) + 0.5);
2234 * If there's a dot anywhere nearby, we pick up an arrow
2235 * pointing at that dot.
2237 for (py1 = py-1; py1 <= py+1; py1++)
2238 for (px1 = px-1; px1 <= px+1; px1++) {
2239 if (px1 >= 0 && px1 < state->sx &&
2240 py1 >= 0 && py1 < state->sx &&
2241 x >= SCOORD(px1-1) && x < SCOORD(px1+1) &&
2242 y >= SCOORD(py1-1) && y < SCOORD(py1+1) &&
2243 SPACE(state, px1, py1).flags & F_DOT) {
2245 * Found a dot. Begin a drag from it.
2247 dot = &SPACE(state, px1, py1);
2250 goto done; /* multi-level break */
2255 * Otherwise, find the nearest _square_, and pick up the
2256 * same arrow as it's got on it, if any.
2259 px = 2*FROMCOORD(x+TILE_SIZE) - 1;
2260 py = 2*FROMCOORD(y+TILE_SIZE) - 1;
2261 if (px >= 0 && px < state->sx && py >= 0 && py < state->sx) {
2262 sp = &SPACE(state, px, py);
2263 if (sp->flags & F_TILE_ASSOC) {
2264 dot = &SPACE(state, sp->dotx, sp->doty);
2273 * Now, if we've managed to find a dot, begin a drag.
2276 ui->dragging = TRUE;
2283 } else if (button == RIGHT_DRAG && ui->dragging) {
2284 /* just move the drag coords. */
2288 } else if (button == RIGHT_RELEASE && ui->dragging) {
2289 ui->dragging = FALSE;
2292 * Drags are always targeted at a single square.
2294 px = 2*FROMCOORD(x+TILE_SIZE) - 1;
2295 py = 2*FROMCOORD(y+TILE_SIZE) - 1;
2298 * Dragging an arrow on to the same square it started from
2299 * is a null move; just update the ui and finish.
2301 if (px == ui->srcx && py == ui->srcy)
2308 * Otherwise, we remove the arrow from its starting
2309 * square if we didn't start from a dot...
2311 if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) &&
2312 SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) {
2313 sprintf(buf + strlen(buf), "%sU%d,%d", sep, ui->srcx, ui->srcy);
2318 * ... and if the square we're moving it _to_ is valid, we
2319 * add one there instead.
2321 if (INUI(state, px, py)) {
2322 sp = &SPACE(state, px, py);
2324 if (!(sp->flags & F_DOT) && !(sp->flags & F_TILE_ASSOC))
2325 sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d",
2326 sep, px, py, ui->dotx, ui->doty);
2339 static int check_complete_in_play(game_state *state, int *dsf, int *colours)
2341 int w = state->w, h = state->h;
2346 int minx, miny, maxx, maxy;
2352 dsf = snew_dsf(w*h);
2360 * During actual game play, completion checking is done on the
2361 * basis of the edges rather than the square associations. So
2362 * first we must go through the grid figuring out the connected
2363 * components into which the edges divide it.
2365 for (y = 0; y < h; y++)
2366 for (x = 0; x < w; x++) {
2367 if (y+1 < h && !(SPACE(state, 2*x+1, 2*y+2).flags & F_EDGE_SET))
2368 dsf_merge(dsf, y*w+x, (y+1)*w+x);
2369 if (x+1 < w && !(SPACE(state, 2*x+2, 2*y+1).flags & F_EDGE_SET))
2370 dsf_merge(dsf, y*w+x, y*w+(x+1));
2374 * That gives us our connected components. Now, for each
2375 * component, decide whether it's _valid_. A valid component is
2378 * - is 180-degree rotationally symmetric
2379 * - has a dot at its centre of symmetry
2380 * - has no other dots anywhere within it (including on its
2382 * - contains no internal edges (i.e. edges separating two
2383 * squares which are both part of the component).
2387 * First, go through the grid finding the bounding box of each
2390 sqdata = snewn(w*h, struct sqdata);
2391 for (i = 0; i < w*h; i++) {
2392 sqdata[i].minx = w+1;
2393 sqdata[i].miny = h+1;
2394 sqdata[i].maxx = sqdata[i].maxy = -1;
2395 sqdata[i].valid = FALSE;
2397 for (y = 0; y < h; y++)
2398 for (x = 0; x < w; x++) {
2399 i = dsf_canonify(dsf, y*w+x);
2400 if (sqdata[i].minx > x)
2402 if (sqdata[i].maxx < x)
2404 if (sqdata[i].miny > y)
2406 if (sqdata[i].maxy < y)
2408 sqdata[i].valid = TRUE;
2412 * Now we're in a position to loop over each actual component
2413 * and figure out where its centre of symmetry has to be if
2416 for (i = 0; i < w*h; i++)
2417 if (sqdata[i].valid) {
2418 sqdata[i].cx = sqdata[i].minx + sqdata[i].maxx + 1;
2419 sqdata[i].cy = sqdata[i].miny + sqdata[i].maxy + 1;
2420 if (!(SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT))
2421 sqdata[i].valid = FALSE; /* no dot at centre of symmetry */
2422 if (SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT_BLACK)
2423 sqdata[i].colour = 2;
2425 sqdata[i].colour = 1;
2429 * Now we loop over the whole grid again, this time finding
2430 * extraneous dots (any dot which wholly or partially overlaps
2431 * a square and is not at the centre of symmetry of that
2432 * square's component disqualifies the component from validity)
2433 * and extraneous edges (any edge separating two squares
2434 * belonging to the same component also disqualifies that
2437 for (y = 1; y < state->sy-1; y++)
2438 for (x = 1; x < state->sx-1; x++) {
2439 space *sp = &SPACE(state, x, y);
2441 if (sp->flags & F_DOT) {
2443 * There's a dot here. Use it to disqualify any
2444 * component which deserves it.
2447 for (cy = (y-1) >> 1; cy <= y >> 1; cy++)
2448 for (cx = (x-1) >> 1; cx <= x >> 1; cx++) {
2449 i = dsf_canonify(dsf, cy*w+cx);
2450 if (x != sqdata[i].cx || y != sqdata[i].cy)
2451 sqdata[i].valid = FALSE;
2455 if (sp->flags & F_EDGE_SET) {
2457 * There's an edge here. Use it to disqualify a
2458 * component if necessary.
2460 int cx1 = (x-1) >> 1, cx2 = x >> 1;
2461 int cy1 = (y-1) >> 1, cy2 = y >> 1;
2462 assert((cx1==cx2) ^ (cy1==cy2));
2463 i = dsf_canonify(dsf, cy1*w+cx1);
2464 if (i == dsf_canonify(dsf, cy2*w+cx2))
2465 sqdata[i].valid = FALSE;
2470 * And finally we test rotational symmetry: for each square in
2471 * the grid, find which component it's in, test that that
2472 * component also has a square in the symmetric position, and
2473 * disqualify it if it doesn't.
2475 for (y = 0; y < h; y++)
2476 for (x = 0; x < w; x++) {
2479 i = dsf_canonify(dsf, y*w+x);
2481 x2 = sqdata[i].cx - 1 - x;
2482 y2 = sqdata[i].cy - 1 - y;
2483 if (i != dsf_canonify(dsf, y2*w+x2))
2484 sqdata[i].valid = FALSE;
2488 * That's it. We now have all the connected components marked
2489 * as valid or not valid. So now we return a `colours' array if
2490 * we were asked for one, and also we return an overall
2491 * true/false value depending on whether _every_ square in the
2492 * grid is part of a valid component.
2495 for (i = 0; i < w*h; i++) {
2496 int ci = dsf_canonify(dsf, i);
2497 int thisok = sqdata[ci].valid;
2499 colours[i] = thisok ? sqdata[ci].colour : 0;
2500 ret = ret && thisok;
2510 static game_state *execute_move(game_state *state, char *move)
2512 int x, y, ax, ay, n, dx, dy;
2513 game_state *ret = dup_game(state);
2514 struct space *sp, *dot;
2516 debug(("%s\n", move));
2520 if (c == 'E' || c == 'U' || c == 'M'
2522 || c == 'D' || c == 'd'
2526 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
2530 sp = &SPACE(ret, x, y);
2532 if (c == 'D' || c == 'd') {
2533 unsigned int currf, newf, maskf;
2535 if (!dot_is_possible(state, sp, 1)) goto badmove;
2537 newf = F_DOT | (c == 'd' ? F_DOT_BLACK : 0);
2538 currf = GRID(ret, grid, x, y).flags;
2539 maskf = F_DOT | F_DOT_BLACK;
2540 /* if we clicked 'white dot':
2541 * white --> empty, empty --> white, black --> white.
2542 * if we clicker 'black dot':
2543 * black --> empty, empty --> black, white --> black.
2545 if (currf & maskf) {
2546 sp->flags &= ~maskf;
2547 if ((currf & maskf) != newf)
2551 sp->nassoc = 0; /* edit-mode disallows associations. */
2552 game_update_dots(ret);
2556 if (sp->type != s_edge) goto badmove;
2557 sp->flags ^= F_EDGE_SET;
2558 } else if (c == 'U') {
2559 if (sp->type != s_tile || !(sp->flags & F_TILE_ASSOC))
2561 remove_assoc(ret, sp);
2562 } else if (c == 'M') {
2563 if (!(sp->flags & F_DOT)) goto badmove;
2564 sp->flags ^= F_DOT_HOLD;
2567 } else if (c == 'A' || c == 'a') {
2569 if (sscanf(move, "%d,%d,%d,%d%n", &x, &y, &ax, &ay, &n) != 4 ||
2570 x < 1 || y < 1 || x >= (state->sx-1) || y >= (state->sy-1) ||
2571 ax < 1 || ay < 1 || ax >= (state->sx-1) || ay >= (state->sy-1))
2574 dot = &GRID(ret, grid, ax, ay);
2575 if (!(dot->flags & F_DOT))goto badmove;
2576 if (dot->flags & F_DOT_HOLD) goto badmove;
2578 for (dx = -1; dx <= 1; dx++) {
2579 for (dy = -1; dy <= 1; dy++) {
2580 sp = &GRID(ret, grid, x+dx, y+dy);
2581 if (sp->type != s_tile) continue;
2582 if (sp->flags & F_TILE_ASSOC) {
2583 space *dot = &SPACE(state, sp->dotx, sp->doty);
2584 if (dot->flags & F_DOT_HOLD) continue;
2586 add_assoc(state, sp, dot);
2591 } else if (c == 'C') {
2595 } else if (c == 'S') {
2605 if (check_complete_in_play(ret, NULL, NULL))
2614 /* ----------------------------------------------------------------------
2618 /* Lines will be much smaller size than squares; say, 1/8 the size?
2620 * Need a 'top-left corner of location XxY' to take this into account;
2621 * alternaticaly, that could give the middle of that location, and the
2622 * drawing code would just know the expected dimensions.
2624 * We also need something to take a click and work out what it was
2625 * we were interested in. Clicking on vertices is required because
2626 * we may want to drag from them, for example.
2629 static void game_compute_size(game_params *params, int sz,
2632 struct { int tilesize, w, h; } ads, *ds = &ads;
2642 static void game_set_size(drawing *dr, game_drawstate *ds,
2643 game_params *params, int sz)
2647 assert(TILE_SIZE > 0);
2650 ds->bl = blitter_new(dr, TILE_SIZE, TILE_SIZE);
2653 static float *game_colours(frontend *fe, int *ncolours)
2655 float *ret = snewn(3 * NCOLOURS, float);
2659 * We call game_mkhighlight to ensure the background colour
2660 * isn't completely white. We don't actually use the high- and
2661 * lowlight colours it generates.
2663 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_WHITEBG, COL_BLACKBG);
2665 for (i = 0; i < 3; i++) {
2667 * Currently, white dots and white-background squares are
2670 ret[COL_WHITEDOT * 3 + i] = 1.0F;
2671 ret[COL_WHITEBG * 3 + i] = 1.0F;
2674 * But black-background squares are a dark grey, whereas
2675 * black dots are really black.
2677 ret[COL_BLACKDOT * 3 + i] = 0.0F;
2678 ret[COL_BLACKBG * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.3F;
2681 * In unfilled squares, we draw a faint gridwork.
2683 ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
2686 * Edges and arrows are filled in in pure black.
2688 ret[COL_EDGE * 3 + i] = 0.0F;
2689 ret[COL_ARROW * 3 + i] = 0.0F;
2693 /* tinge the edit background to bluey */
2694 ret[COL_BACKGROUND * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
2695 ret[COL_BACKGROUND * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
2696 ret[COL_BACKGROUND * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 1.4F;
2697 if (ret[COL_BACKGROUND * 3 + 2] > 1.0F) ret[COL_BACKGROUND * 3 + 2] = 1.0F;
2700 *ncolours = NCOLOURS;
2704 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
2706 struct game_drawstate *ds = snew(struct game_drawstate);
2713 ds->grid = snewn(ds->w*ds->h, unsigned long);
2714 for (i = 0; i < ds->w*ds->h; i++)
2715 ds->grid[i] = 0xFFFFFFFFUL;
2716 ds->dx = snewn(ds->w*ds->h, int);
2717 ds->dy = snewn(ds->w*ds->h, int);
2720 ds->dragging = FALSE;
2721 ds->dragx = ds->dragy = 0;
2723 ds->colour_scratch = snewn(ds->w * ds->h, int);
2728 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2730 sfree(ds->colour_scratch);
2731 if (ds->bl) blitter_free(dr, ds->bl);
2738 #define DRAW_EDGE_L 0x0001
2739 #define DRAW_EDGE_R 0x0002
2740 #define DRAW_EDGE_U 0x0004
2741 #define DRAW_EDGE_D 0x0008
2742 #define DRAW_CORNER_UL 0x0010
2743 #define DRAW_CORNER_UR 0x0020
2744 #define DRAW_CORNER_DL 0x0040
2745 #define DRAW_CORNER_DR 0x0080
2746 #define DRAW_WHITE 0x0100
2747 #define DRAW_BLACK 0x0200
2748 #define DRAW_ARROW 0x0400
2749 #define DOT_SHIFT_C 11
2750 #define DOT_SHIFT_M 2
2751 #define DOT_WHITE 1UL
2752 #define DOT_BLACK 2UL
2755 * Draw an arrow centred on (cx,cy), pointing in the direction
2756 * (ddx,ddy). (I.e. pointing at the point (cx+ddx, cy+ddy).
2758 static void draw_arrow(drawing *dr, game_drawstate *ds,
2759 int cx, int cy, int ddx, int ddy)
2761 float vlen = (float)sqrt(ddx*ddx+ddy*ddy);
2762 float xdx = ddx/vlen, xdy = ddy/vlen;
2763 float ydx = -xdy, ydy = xdx;
2764 int e1x = cx + (int)(xdx*TILE_SIZE/3), e1y = cy + (int)(xdy*TILE_SIZE/3);
2765 int e2x = cx - (int)(xdx*TILE_SIZE/3), e2y = cy - (int)(xdy*TILE_SIZE/3);
2766 int adx = (int)((ydx-xdx)*TILE_SIZE/8), ady = (int)((ydy-xdy)*TILE_SIZE/8);
2767 int adx2 = (int)((-ydx-xdx)*TILE_SIZE/8), ady2 = (int)((-ydy-xdy)*TILE_SIZE/8);
2769 draw_line(dr, e1x, e1y, e2x, e2y, COL_ARROW);
2770 draw_line(dr, e1x, e1y, e1x+adx, e1y+ady, COL_ARROW);
2771 draw_line(dr, e1x, e1y, e1x+adx2, e1y+ady2, COL_ARROW);
2774 static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
2775 unsigned long flags, int ddx, int ddy)
2777 int lx = COORD(x), ly = COORD(y);
2781 clip(dr, lx, ly, TILE_SIZE, TILE_SIZE);
2784 * Draw the tile background.
2786 draw_rect(dr, lx, ly, TILE_SIZE, TILE_SIZE,
2787 (flags & DRAW_WHITE ? COL_WHITEBG :
2788 flags & DRAW_BLACK ? COL_BLACKBG : COL_BACKGROUND));
2793 gridcol = (flags & DRAW_BLACK ? COL_BLACKDOT : COL_GRID);
2794 draw_rect(dr, lx, ly, 1, TILE_SIZE, gridcol);
2795 draw_rect(dr, lx, ly, TILE_SIZE, 1, gridcol);
2800 if (flags & DRAW_ARROW)
2801 draw_arrow(dr, ds, lx + TILE_SIZE/2, ly + TILE_SIZE/2, ddx, ddy);
2806 if (flags & DRAW_EDGE_L)
2807 draw_rect(dr, lx, ly, EDGE_THICKNESS, TILE_SIZE, COL_EDGE);
2808 if (flags & DRAW_EDGE_R)
2809 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly,
2810 EDGE_THICKNESS - 1, TILE_SIZE, COL_EDGE);
2811 if (flags & DRAW_EDGE_U)
2812 draw_rect(dr, lx, ly, TILE_SIZE, EDGE_THICKNESS, COL_EDGE);
2813 if (flags & DRAW_EDGE_D)
2814 draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1,
2815 TILE_SIZE, EDGE_THICKNESS - 1, COL_EDGE);
2816 if (flags & DRAW_CORNER_UL)
2817 draw_rect(dr, lx, ly, EDGE_THICKNESS, EDGE_THICKNESS, COL_EDGE);
2818 if (flags & DRAW_CORNER_UR)
2819 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly,
2820 EDGE_THICKNESS - 1, EDGE_THICKNESS, COL_EDGE);
2821 if (flags & DRAW_CORNER_DL)
2822 draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1,
2823 EDGE_THICKNESS, EDGE_THICKNESS - 1, COL_EDGE);
2824 if (flags & DRAW_CORNER_DR)
2825 draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1,
2826 ly + TILE_SIZE - EDGE_THICKNESS + 1,
2827 EDGE_THICKNESS - 1, EDGE_THICKNESS - 1, COL_EDGE);
2832 for (dy = 0; dy < 3; dy++)
2833 for (dx = 0; dx < 3; dx++) {
2834 int dotval = (flags >> (DOT_SHIFT_C + DOT_SHIFT_M*(dy*3+dx)));
2835 dotval &= (1 << DOT_SHIFT_M)-1;
2838 draw_circle(dr, lx+dx*TILE_SIZE/2, ly+dy*TILE_SIZE/2,
2840 (dotval == 1 ? COL_WHITEDOT : COL_BLACKDOT),
2845 draw_update(dr, lx, ly, TILE_SIZE, TILE_SIZE);
2848 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2849 game_state *state, int dir, game_ui *ui,
2850 float animtime, float flashtime)
2852 int w = ds->w, h = ds->h;
2853 int x, y, flashing = FALSE;
2855 if (flashtime > 0) {
2856 int frame = (int)(flashtime / FLASH_TIME);
2857 flashing = (frame % 2 == 0);
2862 blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
2863 draw_update(dr, ds->dragx, ds->dragy, TILE_SIZE, TILE_SIZE);
2864 ds->dragging = FALSE;
2868 draw_rect(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT, COL_BACKGROUND);
2869 draw_rect(dr, BORDER - EDGE_THICKNESS + 1, BORDER - EDGE_THICKNESS + 1,
2870 w*TILE_SIZE + EDGE_THICKNESS*2 - 1,
2871 h*TILE_SIZE + EDGE_THICKNESS*2 - 1, COL_EDGE);
2872 draw_update(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT);
2876 check_complete_in_play(state, NULL, ds->colour_scratch);
2878 for (y = 0; y < h; y++)
2879 for (x = 0; x < w; x++) {
2880 unsigned long flags = 0;
2881 int ddx = 0, ddy = 0;
2886 * Set up the flags for this square. Firstly, see if we
2889 if (SPACE(state, x*2, y*2+1).flags & F_EDGE_SET)
2890 flags |= DRAW_EDGE_L;
2891 if (SPACE(state, x*2+2, y*2+1).flags & F_EDGE_SET)
2892 flags |= DRAW_EDGE_R;
2893 if (SPACE(state, x*2+1, y*2).flags & F_EDGE_SET)
2894 flags |= DRAW_EDGE_U;
2895 if (SPACE(state, x*2+1, y*2+2).flags & F_EDGE_SET)
2896 flags |= DRAW_EDGE_D;
2899 * Also, mark corners of neighbouring edges.
2901 if ((x > 0 && SPACE(state, x*2-1, y*2).flags & F_EDGE_SET) ||
2902 (y > 0 && SPACE(state, x*2, y*2-1).flags & F_EDGE_SET))
2903 flags |= DRAW_CORNER_UL;
2904 if ((x+1 < w && SPACE(state, x*2+3, y*2).flags & F_EDGE_SET) ||
2905 (y > 0 && SPACE(state, x*2+2, y*2-1).flags & F_EDGE_SET))
2906 flags |= DRAW_CORNER_UR;
2907 if ((x > 0 && SPACE(state, x*2-1, y*2+2).flags & F_EDGE_SET) ||
2908 (y+1 < h && SPACE(state, x*2, y*2+3).flags & F_EDGE_SET))
2909 flags |= DRAW_CORNER_DL;
2910 if ((x+1 < w && SPACE(state, x*2+3, y*2+2).flags & F_EDGE_SET) ||
2911 (y+1 < h && SPACE(state, x*2+2, y*2+3).flags & F_EDGE_SET))
2912 flags |= DRAW_CORNER_DR;
2915 * If this square is part of a valid region, paint it
2916 * that region's colour. Exception: if we're flashing,
2917 * everything goes briefly back to background colour.
2919 sp = &SPACE(state, x*2+1, y*2+1);
2920 if (ds->colour_scratch[y*w+x] && !flashing) {
2921 flags |= (ds->colour_scratch[y*w+x] == 2 ?
2922 DRAW_BLACK : DRAW_WHITE);
2926 * If this square is associated with a dot but it isn't
2927 * part of a valid region, draw an arrow in it pointing
2928 * in the direction of that dot.
2930 * Exception: if this is the source point of an active
2931 * drag, we don't draw the arrow.
2933 if ((sp->flags & F_TILE_ASSOC) && !ds->colour_scratch[y*w+x]) {
2934 if (ui->dragging && ui->srcx == x*2+1 && ui->srcy == y*2+1) {
2936 } else if (sp->doty != y*2+1 || sp->dotx != x*2+1) {
2937 flags |= DRAW_ARROW;
2938 ddy = sp->doty - (y*2+1);
2939 ddx = sp->dotx - (x*2+1);
2944 * Now go through the nine possible places we could
2947 for (dy = 0; dy < 3; dy++)
2948 for (dx = 0; dx < 3; dx++) {
2949 sp = &SPACE(state, x*2+dx, y*2+dy);
2950 if (sp->flags & F_DOT) {
2951 unsigned long dotval = (sp->flags & F_DOT_BLACK ?
2952 DOT_BLACK : DOT_WHITE);
2953 flags |= dotval << (DOT_SHIFT_C +
2954 DOT_SHIFT_M*(dy*3+dx));
2959 * Now we have everything we're going to need. Draw the
2962 if (ds->grid[y*w+x] != flags ||
2963 ds->dx[y*w+x] != ddx ||
2964 ds->dy[y*w+x] != ddy) {
2965 draw_square(dr, ds, x, y, flags, ddx, ddy);
2966 ds->grid[y*w+x] = flags;
2967 ds->dx[y*w+x] = ddx;
2968 ds->dy[y*w+x] = ddy;
2973 ds->dragging = TRUE;
2974 ds->dragx = ui->dx - TILE_SIZE/2;
2975 ds->dragy = ui->dy - TILE_SIZE/2;
2976 blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
2977 draw_arrow(dr, ds, ui->dx, ui->dy,
2978 SCOORD(ui->dotx) - ui->dx,
2979 SCOORD(ui->doty) - ui->dy);
2984 if (state->cdiff != -1)
2985 sprintf(buf, "Puzzle is %s.", galaxies_diffnames[state->cdiff]);
2988 status_bar(dr, buf);
2993 static float game_anim_length(game_state *oldstate, game_state *newstate,
2994 int dir, game_ui *ui)
2999 static float game_flash_length(game_state *oldstate, game_state *newstate,
3000 int dir, game_ui *ui)
3002 if ((!oldstate->completed && newstate->completed) &&
3003 !(newstate->used_solve))
3004 return 3 * FLASH_TIME;
3009 static int game_timing_state(game_state *state, game_ui *ui)
3015 static void game_print_size(game_params *params, float *x, float *y)
3020 * 8mm squares by default. (There isn't all that much detail
3021 * that needs to go in each square.)
3023 game_compute_size(params, 800, &pw, &ph);
3028 static void game_print(drawing *dr, game_state *state, int sz)
3030 int w = state->w, h = state->h;
3031 int white, black, blackish;
3035 int ncoords = 0, coordsize = 0;
3037 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3038 game_drawstate ads, *ds = &ads;
3041 white = print_grey_colour(dr, HATCH_CLEAR, 1.0F);
3042 black = print_grey_colour(dr, HATCH_SOLID, 0.0F);
3043 blackish = print_grey_colour(dr, HATCH_X, 0.5F);
3046 * Get the completion information.
3048 dsf = snewn(w * h, int);
3049 colours = snewn(w * h, int);
3050 check_complete_in_play(state, dsf, colours);
3055 print_line_width(dr, TILE_SIZE / 64);
3056 for (x = 1; x < w; x++)
3057 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black);
3058 for (y = 1; y < h; y++)
3059 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black);
3062 * Shade the completed regions. Just in case any particular
3063 * printing platform deals badly with adjacent
3064 * similarly-hatched regions, we'll fill each one as a single
3067 for (i = 0; i < w*h; i++) {
3068 j = dsf_canonify(dsf, i);
3069 if (colours[j] != 0) {
3073 * This is the first square we've run into belonging to
3074 * this polyomino, which means an edge of the polyomino
3075 * is certain to be to our left. (After we finish
3076 * tracing round it, we'll set the colours[] entry to
3077 * zero to prevent accidentally doing it again.)
3087 * We are currently sitting on square (x,y), which
3088 * we know to be in our polyomino, and we also know
3089 * that (x+dx,y+dy) is not. The way I visualise
3090 * this is that we're standing to the right of a
3091 * boundary line, stretching our left arm out to
3092 * point to the exterior square on the far side.
3096 * First, check if we've gone round the entire
3100 (x == i%w && y == i/w && dx == -1 && dy == 0))
3104 * Add to our coordinate list the coordinate
3105 * backwards and to the left of where we are.
3107 if (ncoords + 2 > coordsize) {
3108 coordsize = (ncoords * 3 / 2) + 64;
3109 coords = sresize(coords, coordsize, int);
3111 coords[ncoords++] = COORD((2*x+1 + dx + dy) / 2);
3112 coords[ncoords++] = COORD((2*y+1 + dy - dx) / 2);
3115 * Follow the edge round. If the square directly in
3116 * front of us is not part of the polyomino, we
3117 * turn right; if it is and so is the square in
3118 * front of (x+dx,y+dy), we turn left; otherwise we
3121 if (x-dy < 0 || x-dy >= w || y+dx < 0 || y+dx >= h ||
3122 dsf_canonify(dsf, (y+dx)*w+(x-dy)) != j) {
3127 } else if (x+dx-dy >= 0 && x+dx-dy < w &&
3128 y+dy+dx >= 0 && y+dy+dx < h &&
3129 dsf_canonify(dsf, (y+dy+dx)*w+(x+dx-dy)) == j) {
3146 * Now we have our polygon complete, so fill it.
3148 draw_polygon(dr, coords, ncoords/2,
3149 colours[j] == 2 ? blackish : -1, black);
3152 * And mark this polyomino as done.
3161 for (y = 0; y <= h; y++)
3162 for (x = 0; x <= w; x++) {
3163 if (x < w && SPACE(state, x*2+1, y*2).flags & F_EDGE_SET)
3164 draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS,
3165 EDGE_THICKNESS * 2 + TILE_SIZE, EDGE_THICKNESS * 2,
3167 if (y < h && SPACE(state, x*2, y*2+1).flags & F_EDGE_SET)
3168 draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS,
3169 EDGE_THICKNESS * 2, EDGE_THICKNESS * 2 + TILE_SIZE,
3176 for (y = 0; y <= 2*h; y++)
3177 for (x = 0; x <= 2*w; x++)
3178 if (SPACE(state, x, y).flags & F_DOT) {
3179 draw_circle(dr, (int)COORD(x/2.0), (int)COORD(y/2.0), DOT_SIZE,
3180 (SPACE(state, x, y).flags & F_DOT_BLACK ?
3181 black : white), black);
3191 #define thegame galaxies
3194 const struct game thegame = {
3195 "Galaxies", "games.galaxies", "galaxies",
3202 TRUE, game_configure, custom_params,
3214 TRUE, game_text_format,
3222 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3225 game_free_drawstate,
3230 FALSE, FALSE, NULL, NULL,
3231 TRUE, /* wants_statusbar */
3233 TRUE, TRUE, game_print_size, game_print,
3234 FALSE, /* wants_statusbar */
3236 FALSE, game_timing_state,
3240 #ifdef STANDALONE_SOLVER
3246 static void usage_exit(const char *msg)
3249 fprintf(stderr, "%s: %s\n", quis, msg);
3250 fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
3254 static void dump_state(game_state *state)
3256 char *temp = game_text_format(state);
3257 printf("%s\n", temp);
3261 static int gen(game_params *p, random_state *rs, int debug)
3268 solver_show_working = debug;
3270 printf("Generating a %dx%d %s puzzle.\n",
3271 p->w, p->h, galaxies_diffnames[p->diff]);
3273 desc = new_game_desc(p, rs, NULL, 0);
3274 state = new_game(NULL, p, desc);
3277 diff = solver_state(state, DIFF_UNREASONABLE);
3278 printf("Generated %s game %dx%d:%s\n",
3279 galaxies_diffnames[diff], p->w, p->h, desc);
3288 static void soak(game_params *p, random_state *rs)
3290 time_t tt_start, tt_now, tt_last;
3293 int diff, n = 0, i, diffs[DIFF_MAX], ndots = 0, nspaces = 0;
3296 solver_show_working = 0;
3298 tt_start = tt_now = time(NULL);
3299 for (i = 0; i < DIFF_MAX; i++) diffs[i] = 0;
3302 printf("Soak-generating a %dx%d grid, max. diff %s.\n",
3303 p->w, p->h, galaxies_diffnames[p->diff]);
3305 for (i = 0; i < DIFF_MAX; i++)
3306 printf("%s%s", (i == 0) ? "" : ", ", galaxies_diffnames[i]);
3310 desc = new_game_desc(p, rs, NULL, 0);
3311 st = new_game(NULL, p, desc);
3312 diff = solver_state(st, p->diff);
3313 nspaces += st->w*st->h;
3314 for (i = 0; i < st->sx*st->sy; i++)
3315 if (st->grid[i].flags & F_DOT) ndots++;
3321 tt_last = time(NULL);
3322 if (tt_last > tt_now) {
3324 printf("%d total, %3.1f/s, [",
3325 n, (double)n / ((double)tt_now - tt_start));
3326 for (i = 0; i < DIFF_MAX; i++)
3327 printf("%s%.1f%%", (i == 0) ? "" : ", ",
3328 100.0 * ((double)diffs[i] / (double)n));
3329 printf("], %.1f%% dots\n",
3330 100.0 * ((double)ndots / (double)nspaces));
3335 int main(int argc, char **argv)
3338 char *id = NULL, *desc, *err;
3340 int diff, do_soak = 0, verbose = 0;
3342 time_t seed = time(NULL);
3345 while (--argc > 0) {
3347 if (!strcmp(p, "-v")) {
3349 } else if (!strcmp(p, "--seed")) {
3350 if (argc == 0) usage_exit("--seed needs an argument");
3351 seed = (time_t)atoi(*++argv);
3353 } else if (!strcmp(p, "--soak")) {
3355 } else if (*p == '-') {
3356 usage_exit("unrecognised option");
3364 p = default_params();
3365 rs = random_new((void*)&seed, sizeof(time_t));
3368 if (!id) usage_exit("need one argument for --soak");
3369 decode_params(p, *argv);
3376 p->w = random_upto(rs, 15) + 3;
3377 p->h = random_upto(rs, 15) + 3;
3378 p->diff = random_upto(rs, DIFF_UNREASONABLE);
3379 diff = gen(p, rs, 0);
3384 desc = strchr(id, ':');
3386 decode_params(p, id);
3387 gen(p, rs, verbose);
3390 solver_show_working = 1;
3393 decode_params(p, id);
3394 err = validate_desc(p, desc);
3396 fprintf(stderr, "%s: %s\n", argv[0], err);
3399 s = new_game(NULL, p, desc);
3400 diff = solver_state(s, DIFF_UNREASONABLE);
3402 printf("Puzzle is %s.\n", galaxies_diffnames[diff]);
3413 /* vim: set shiftwidth=4 tabstop=8: */