1 /* -*- indent-tabs-mode: nil; tab-width: 1000 -*- */
4 * palisade.c: Nikoli's `Five Cells' puzzle.
6 * See http://nikoli.co.jp/en/puzzles/five_cells.html
11 * - better solver: implement the sketched-out deductions
13 * - improve the victory flash?
14 * - the LINE_NOs look ugly against COL_FLASH.
15 * - white-blink the edges (instead), a la loopy?
27 #define setmem(ptr, byte, len) memset((ptr), (byte), (len) * sizeof (ptr)[0])
28 #define scopy(dst, src, len) memcpy((dst), (src), (len) * sizeof (dst)[0])
29 #define dupmem(p, n) memcpy(smalloc(n * sizeof (*p)), p, n * sizeof (*p))
30 #define snewa(ptr, len) (ptr) = smalloc((len) * sizeof (*ptr))
31 #define clone(ptr) (dupmem((ptr), 1))
33 static char *string(int n, const char *fmt, ...)
39 m = vsprintf(snewa(ret, n + 1), fmt, va);
41 if (m > n) fatal("memory corruption");
50 typedef unsigned char borderflag;
52 typedef struct shared_state {
60 borderflag *borders; /* length w*h */
62 unsigned int completed: 1;
63 unsigned int cheated: 1;
66 #define DEFAULT_PRESET 0
67 static struct game_params presets[] = {
68 {5, 5, 5}, {8, 6, 6}, {10, 8, 8}, {15, 12, 10}
69 /* I definitely want 5x5n5 since that gives "Five Cells" its name.
70 * But how about the others? By which criteria do I choose? */
73 static game_params *default_params(void)
75 return clone(&presets[DEFAULT_PRESET]);
78 static int game_fetch_preset(int i, char **name, game_params **params)
80 if (i < 0 || i >= lenof(presets)) return FALSE;
82 *params = clone(&presets[i]);
83 *name = string(60, "%d x %d, regions of size %d",
84 presets[i].w, presets[i].h, presets[i].k);
89 static void free_params(game_params *params)
94 static game_params *dup_params(const game_params *params)
99 static void decode_params(game_params *params, char const *string)
101 params->w = params->h = params->k = atoi(string);
102 while (*string && isdigit((unsigned char)*string)) ++string;
103 if (*string == 'x') {
104 params->h = atoi(++string);
105 while (*string && isdigit((unsigned char)*string)) ++string;
107 if (*string == 'n') params->k = atoi(++string);
110 static char *encode_params(const game_params *params, int full)
112 return string(40, "%dx%dn%d", params->w, params->h, params->k);
115 #define CONFIG(i, nm, ty, iv, sv) \
116 (ret[i].name = nm, ret[i].type = ty, ret[i].ival = iv, ret[i].sval = sv)
118 static config_item *game_configure(const game_params *params)
120 config_item *ret = snewn(4, config_item);
122 ret[0].name = "Width";
123 ret[0].type = C_STRING;
124 ret[0].u.string.sval = string(20, "%d", params->w);
126 ret[1].name = "Height";
127 ret[1].type = C_STRING;
128 ret[1].u.string.sval = string(20, "%d", params->h);
130 ret[2].name = "Region size";
131 ret[2].type = C_STRING;
132 ret[2].u.string.sval = string(20, "%d", params->k);
140 static game_params *custom_params(const config_item *cfg)
142 game_params *params = snew(game_params);
144 params->w = atoi(cfg[0].u.string.sval);
145 params->h = atoi(cfg[1].u.string.sval);
146 params->k = atoi(cfg[2].u.string.sval);
151 /* +---+ << The one possible domino (up to symmetry). +---+---+
153 * | | If two dominos are adjacent as depicted here >> +---+---+
154 * | 3 | then it's ambiguous whether the edge between | 3 | 3 |
155 * +---+ the dominos is horizontal or vertical. +---+---+
158 static char *validate_params(const game_params *params, int full)
160 int w = params->w, h = params->h, k = params->k, wh = w * h;
162 if (k < 1) return "Region size must be at least one";
163 if (w < 1) return "Width must be at least one";
164 if (h < 1) return "Height must be at least one";
165 if (wh % k) return "Region size must divide grid area";
167 if (!full) return NULL; /* succeed partial validation */
169 /* MAYBE FIXME: we (just?) don't have the UI for winning these. */
170 if (k == wh) return "Region size must be less than the grid area";
171 assert (k < wh); /* or wh % k != 0 */
173 if (k == 2 && w != 1 && h != 1)
174 return "Region size can't be two unless width or height is one";
176 return NULL; /* succeed full validation */
179 /* --- Solver ------------------------------------------------------- */
181 /* the solver may write at will to these arrays, but shouldn't free them */
182 /* it's up to the client to dup/free as needed */
183 typedef struct solver_ctx {
184 const game_params *params; /* also in shared_state */
185 clue *clues; /* also in shared_state */
186 borderflag *borders; /* also in game_state */
187 int *dsf; /* particular to the solver */
192 * - If two adjacent clues do not have a border between them, this
193 * gives a lower limit on the size of their region (which is also an
194 * upper limit if both clues are 3). Rule out any non-border which
195 * would make its region either too large or too small.
197 * - If a clue, k, is adjacent to k borders or (4 - k) non-borders,
198 * the remaining edges incident to the clue are readily decided.
200 * - If a region has only one other region (e.g. square) to grow into
201 * and it's not of full size yet, grow it into that one region.
203 * - If two regions are adjacent and their combined size would be too
204 * large, put an edge between them.
206 * - If a border is adjacent to two non-borders, its last vertex-mate
207 * must also be a border. If a maybe-border is adjacent to three
208 * nonborders, the maybe-border is a non-border.
210 * - If a clue square is adjacent to several squares belonging to the
211 * same region, and enabling (disabling) those borders would violate
212 * the clue, those borders must be disabled (enabled).
214 * - If there's a path crossing only non-borders between two squares,
215 * the maybe-border between them is a non-border.
216 * (This is implicitly computed in the dsf representation)
221 * If a vertex is adjacent to a LINE_YES and (4-3)*LINE_NO, at least
222 * one of the last two edges are LINE_YES. If they're adjacent to a
223 * 1, then the other two edges incident to that 1 are LINE_NO.
225 * For each square: set all as unknown, then for each k-omino and each
226 * way of placing it on that square, if that way is consistent with
227 * the board, mark its edges and interior as possible LINE_YES and
228 * LINE_NO, respectively. When all k-ominos are through, see what
229 * isn't possible and remove those impossibilities from the board.
230 * (Sounds pretty nasty for k > 4 or so.)
232 * A black-bordered subregion must have a size divisible by k. So,
233 * draw a graph with one node per dsf component and edges between
234 * those dsf components which have adjacent squares. Identify cut
235 * vertices and edges. If a cut-vertex-delimited component contains a
236 * number of squares not divisible by k, cut vertex not included, then
237 * the cut vertex must belong to the component. If it has exactly one
238 * edge _out_ of the component, the line(s) corresponding to that edge
239 * are all LINE_YES (i.e. a BORDER()).
240 * (This sounds complicated, but visually it is rather easy.)
242 * [Look at loopy and see how the at-least/-most k out of m edges
243 * thing is done. See how it is propagated across multiple squares.]
248 #define BIT(i) (1 << (i))
249 #define BORDER(i) BIT(i)
250 #define BORDER_U BORDER(0)
251 #define BORDER_R BORDER(1)
252 #define BORDER_D BORDER(2)
253 #define BORDER_L BORDER(3)
254 #define FLIP(i) ((i) ^ 2)
255 #define BORDER_MASK (BORDER_U|BORDER_R|BORDER_D|BORDER_L)
256 #define DISABLED(border) ((border) << 4)
257 #define UNDISABLED(border) ((border) >> 4)
259 static const int dx[4] = { 0, +1, 0, -1};
260 static const int dy[4] = {-1, 0, +1, 0};
261 static const int bitcount[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
262 /* bitcount[x & BORDER_MASK] == number of enabled borders */
264 #define COMPUTE_J (-1)
266 static void connect(solver_ctx *ctx, int i, int j)
268 dsf_merge(ctx->dsf, i, j);
271 static int connected(solver_ctx *ctx, int i, int j, int dir)
273 if (j == COMPUTE_J) j = i + dx[dir] + ctx->params->w*dy[dir];
274 return dsf_canonify(ctx->dsf, i) == dsf_canonify(ctx->dsf, j);
277 static void disconnect(solver_ctx *ctx, int i, int j, int dir)
279 if (j == COMPUTE_J) j = i + dx[dir] + ctx->params->w*dy[dir];
280 ctx->borders[i] |= BORDER(dir);
281 ctx->borders[j] |= BORDER(FLIP(dir));
284 static int disconnected(solver_ctx *ctx, int i, int j, int dir)
286 assert (j == COMPUTE_J || j == i + dx[dir] + ctx->params->w*dy[dir]);
287 return ctx->borders[i] & BORDER(dir);
290 static int maybe(solver_ctx *ctx, int i, int j, int dir)
292 assert (j == COMPUTE_J || j == i + dx[dir] + ctx->params->w*dy[dir]);
293 return !disconnected(ctx, i, j, dir) && !connected(ctx, i, j, dir);
294 /* the ordering is important: disconnected works for invalid
295 * squares (i.e. out of bounds), connected doesn't. */
298 static void solver_connected_clues_versus_region_size(solver_ctx *ctx)
300 int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir;
302 /* If i is connected to j and i has borders with p of the
303 * remaining three squares and j with q of the remaining three
304 * squares, then the region has size at least 1+(3-p) + 1+(3-q).
305 * If p = q = 3 then the region has size exactly 2. */
307 for (i = 0; i < wh; ++i) {
308 if (ctx->clues[i] == EMPTY) continue;
309 for (dir = 0; dir < 4; ++dir) {
310 int j = i + dx[dir] + w*dy[dir];
311 if (disconnected(ctx, i, j, dir)) continue;
312 if (ctx->clues[j] == EMPTY) continue;
313 if ((8 - ctx->clues[i] - ctx->clues[j] > ctx->params->k) ||
314 (ctx->clues[i] == 3 && ctx->clues[j] == 3 &&
315 ctx->params->k != 2))
317 disconnect(ctx, i, j, dir);
318 /* changed = TRUE, but this is a one-shot... */
324 static int solver_number_exhausted(solver_ctx *ctx)
326 int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir, off;
329 for (i = 0; i < wh; ++i) {
330 if (ctx->clues[i] == EMPTY) continue;
332 if (bitcount[(ctx->borders[i] & BORDER_MASK)] == ctx->clues[i]) {
333 for (dir = 0; dir < 4; ++dir) {
334 int j = i + dx[dir] + w*dy[dir];
335 if (!maybe(ctx, i, j, dir)) continue;
342 for (off = dir = 0; dir < 4; ++dir) {
343 int j = i + dx[dir] + w*dy[dir];
344 if (!disconnected(ctx, i, j, dir) && connected(ctx, i, j, dir))
345 ++off; /* ^^^ bounds checking before ^^^^^ */
348 if (ctx->clues[i] == 4 - off)
349 for (dir = 0; dir < 4; ++dir) {
350 int j = i + dx[dir] + w*dy[dir];
351 if (!maybe(ctx, i, j, dir)) continue;
352 disconnect(ctx, i, j, dir);
360 static int solver_not_too_big(solver_ctx *ctx)
362 int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir;
365 for (i = 0; i < wh; ++i) {
366 int size = dsf_size(ctx->dsf, i);
367 for (dir = 0; dir < 4; ++dir) {
368 int j = i + dx[dir] + w*dy[dir];
369 if (!maybe(ctx, i, j, dir)) continue;
370 if (size + dsf_size(ctx->dsf, j) <= ctx->params->k) continue;
371 disconnect(ctx, i, j, dir);
379 static int solver_not_too_small(solver_ctx *ctx)
381 int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir;
382 int *outs, k = ctx->params->k, ci, changed = FALSE;
385 setmem(outs, -1, wh);
387 for (i = 0; i < wh; ++i) {
388 ci = dsf_canonify(ctx->dsf, i);
389 if (dsf_size(ctx->dsf, ci) == k) continue;
390 for (dir = 0; dir < 4; ++dir) {
391 int j = i + dx[dir] + w*dy[dir];
392 if (!maybe(ctx, i, j, dir)) continue;
393 if (outs[ci] == -1) outs[ci] = dsf_canonify(ctx->dsf, j);
394 else if (outs[ci] != dsf_canonify(ctx->dsf, j)) outs[ci] = -2;
398 for (i = 0; i < wh; ++i) {
400 if (i != dsf_canonify(ctx->dsf, i)) continue;
402 connect(ctx, i, j); /* only one place for i to grow */
410 static int solver_no_dangling_edges(solver_ctx *ctx)
412 int w = ctx->params->w, h = ctx->params->h, r, c;
415 /* for each vertex */
416 for (r = 1; r < h; ++r)
417 for (c = 1; c < w; ++c) {
418 int i = r * w + c, j = i - w - 1, noline = 0, dir;
419 int squares[4], e = -1, f = -1, de = -1, df = -1;
421 /* feels hacky: I align these with BORDER_[U0 R1 D2 L3] */
422 squares[1] = squares[2] = j;
423 squares[0] = squares[3] = i;
425 /* for each edge adjacent to the vertex */
426 for (dir = 0; dir < 4; ++dir)
427 if (!connected(ctx, squares[dir], COMPUTE_J, dir)) {
430 if (e != -1) continue;
435 if (4 - noline == 1) {
437 disconnect(ctx, e, COMPUTE_J, de);
442 if (4 - noline != 2) continue;
447 if (ctx->borders[e] & BORDER(de)) {
448 if (!(ctx->borders[f] & BORDER(df))) {
449 disconnect(ctx, f, COMPUTE_J, df);
452 } else if (ctx->borders[f] & BORDER(df)) {
453 disconnect(ctx, e, COMPUTE_J, de);
461 static int solver_equivalent_edges(solver_ctx *ctx)
463 int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dirj;
466 /* if a square is adjacent to two connected squares, the two
467 * borders (i,j) and (i,k) are either both on or both off. */
469 for (i = 0; i < wh; ++i) {
470 int n_on = 0, n_off = 0;
471 if (ctx->clues[i] < 1 || ctx->clues[i] > 3) continue;
473 if (ctx->clues[i] == 2 /* don't need it otherwise */)
474 for (dirj = 0; dirj < 4; ++dirj) {
475 int j = i + dx[dirj] + w*dy[dirj];
476 if (disconnected(ctx, i, j, dirj)) ++n_on;
477 else if (connected(ctx, i, j, dirj)) ++n_off;
480 for (dirj = 0; dirj < 4; ++dirj) {
481 int j = i + dx[dirj] + w*dy[dirj], dirk;
482 if (!maybe(ctx, i, j, dirj)) continue;
484 for (dirk = dirj + 1; dirk < 4; ++dirk) {
485 int k = i + dx[dirk] + w*dy[dirk];
486 if (!maybe(ctx, i, k, dirk)) continue;
487 if (!connected(ctx, j, k, -1)) continue;
489 if (n_on + 2 > ctx->clues[i]) {
493 } else if (n_off + 2 > 4 - ctx->clues[i]) {
494 disconnect(ctx, i, j, dirj);
495 disconnect(ctx, i, k, dirk);
507 /* build connected components in `dsf', along the lines of `borders'. */
508 static void dfs_dsf(int i, int w, borderflag *border, int *dsf, int black)
511 for (dir = 0; dir < 4; ++dir) {
512 int ii = i + dx[dir] + w*dy[dir], bdir = BORDER(dir);
513 if (black ? (border[i] & bdir) : !(border[i] & DISABLED(bdir)))
515 if (dsf[ii] != UNVISITED) continue;
516 dsf_merge(dsf, i, ii);
517 dfs_dsf(ii, w, border, dsf, black);
521 static int is_solved(const game_params *params, clue *clues,
524 int w = params->w, h = params->h, wh = w*h, k = params->k;
526 int *dsf = snew_dsf(wh);
528 assert (dsf[0] == UNVISITED); /* check: UNVISITED and dsf.c match up */
531 * A game is solved if:
533 * - the borders drawn on the grid divide it into connected
534 * components such that every square is in a component of the
536 * - the borders also satisfy the clue set
538 for (i = 0; i < wh; ++i) {
539 if (dsf[i] == UNVISITED) dfs_dsf(i, params->w, border, dsf, TRUE);
540 if (dsf_size(dsf, i) != k) goto error;
541 if (clues[i] == EMPTY) continue;
542 if (clues[i] != bitcount[border[i] & BORDER_MASK]) goto error;
548 * - there are no *stray* borders, in that every border is
549 * actually part of the division between two components.
550 * Otherwise you could cheat by finding a subdivision which did
551 * not *exceed* any clue square's counter, and then adding a
554 for (y = 0; y < h; y++) {
555 for (x = 0; x < w; x++) {
556 if (x+1 < w && (border[y*w+x] & BORDER_R) &&
557 dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, y*w+(x+1)))
559 if (y+1 < h && (border[y*w+x] & BORDER_D) &&
560 dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, (y+1)*w+x))
573 static int solver(const game_params *params, clue *clues, borderflag *borders)
575 int w = params->w, h = params->h, wh = w*h, changed;
580 ctx.borders = borders;
581 ctx.dsf = snew_dsf(wh);
583 solver_connected_clues_versus_region_size(&ctx); /* idempotent */
586 changed |= solver_number_exhausted(&ctx);
587 changed |= solver_not_too_big(&ctx);
588 changed |= solver_not_too_small(&ctx);
589 changed |= solver_no_dangling_edges(&ctx);
590 changed |= solver_equivalent_edges(&ctx);
595 return is_solved(params, clues, borders);
598 /* --- Generator ---------------------------------------------------- */
600 static void init_borders(int w, int h, borderflag *borders)
603 setmem(borders, 0, w*h);
604 for (c = 0; c < w; ++c) {
605 borders[c] |= BORDER_U;
606 borders[w*h-1 - c] |= BORDER_D;
608 for (r = 0; r < h; ++r) {
609 borders[r*w] |= BORDER_L;
610 borders[w*h-1 - r*w] |= BORDER_R;
614 #define OUT_OF_BOUNDS(x, y, w, h) \
615 ((x) < 0 || (x) >= (w) || (y) < 0 || (y) >= (h))
617 #define xshuffle(ptr, len, rs) shuffle((ptr), (len), sizeof (ptr)[0], (rs))
619 static char *new_game_desc(const game_params *params, random_state *rs,
620 char **aux, int interactive)
622 int w = params->w, h = params->h, wh = w*h, k = params->k;
624 clue *numbers = snewn(wh + 1, clue), *p;
625 borderflag *rim = snewn(wh, borderflag);
626 borderflag *scratch_borders = snewn(wh, borderflag);
628 char *soln = snewa(*aux, wh + 2);
629 int *shuf = snewn(wh, int);
630 int *dsf = NULL, i, r, c;
634 for (i = 0; i < wh; ++i) shuf[i] = i;
635 xshuffle(shuf, wh, rs);
637 init_borders(w, h, rim);
639 assert (!('@' & BORDER_MASK));
645 setmem(soln, '@', wh);
648 dsf = divvy_rectangle(w, h, k, rs);
650 for (r = 0; r < h; ++r)
651 for (c = 0; c < w; ++c) {
652 int i = r * w + c, dir;
654 for (dir = 0; dir < 4; ++dir) {
655 int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc;
656 if (OUT_OF_BOUNDS(cc, rr, w, h) ||
657 dsf_canonify(dsf, i) != dsf_canonify(dsf, ii)) {
659 soln[i] |= BORDER(dir);
664 scopy(scratch_borders, rim, wh);
665 } while (!solver(params, numbers, scratch_borders));
667 for (i = 0; i < wh; ++i) {
669 clue copy = numbers[j];
671 scopy(scratch_borders, rim, wh);
672 numbers[j] = EMPTY; /* strip away unnecssary clues */
673 if (!solver(params, numbers, scratch_borders))
679 sfree(scratch_borders);
686 for (i = 0; i < wh; ++i) {
687 if (numbers[i] != EMPTY) {
696 *p++ = '0' + numbers[i];
701 return sresize(numbers, p - numbers, clue);
704 static char *validate_desc(const game_params *params, const char *desc)
707 int w = params->w, h = params->h, wh = w*h, squares = 0;
709 for (/* nop */; *desc; ++desc) {
710 if (islower((unsigned char)*desc)) {
711 squares += *desc - 'a' + 1;
712 } else if (isdigit((unsigned char)*desc)) {
714 static char buf[] = "Invalid (too large) number: '5'";
715 assert (isdigit((unsigned char)buf[lenof(buf) - 3]));
716 buf[lenof(buf) - 3] = *desc; /* ... or 6, 7, 8, 9 :-) */
720 } else if (isprint((unsigned char)*desc)) {
721 static char buf[] = "Invalid character in data: '?'";
722 buf[lenof(buf) - 3] = *desc;
724 } else return "Invalid (unprintable) character in data";
727 if (squares > wh) return "Data describes too many squares";
732 static game_state *new_game(midend *me, const game_params *params,
735 int w = params->w, h = params->h, wh = w*h, i;
736 game_state *state = snew(game_state);
738 state->shared = snew(shared_state);
739 state->shared->refcount = 1;
740 state->shared->params = *params; /* struct copy */
741 snewa(state->shared->clues, wh);
743 setmem(state->shared->clues, EMPTY, wh);
744 for (i = 0; *desc; ++desc) {
745 if (isdigit((unsigned char)*desc)) state->shared->clues[i++] = *desc - '0';
746 else if (isalpha((unsigned char)*desc)) i += *desc - 'a' + 1;
749 snewa(state->borders, wh);
750 init_borders(w, h, state->borders);
752 state->completed = (params->k == wh);
753 state->cheated = FALSE;
758 static game_state *dup_game(const game_state *state)
760 int wh = state->shared->params.w * state->shared->params.h;
761 game_state *ret = snew(game_state);
763 ret->borders = dupmem(state->borders, wh);
765 ret->shared = state->shared;
766 ++ret->shared->refcount;
768 ret->completed = state->completed;
769 ret->cheated = state->cheated;
774 static void free_game(game_state *state)
776 if (--state->shared->refcount == 0) {
777 sfree(state->shared->clues);
778 sfree(state->shared);
780 sfree(state->borders);
784 static char *solve_game(const game_state *state, const game_state *currstate,
785 const char *aux, char **error)
787 int w = state->shared->params.w, h = state->shared->params.h, wh = w*h;
790 if (aux) return dupstr(aux);
795 init_borders(w, h, move + 1);
798 if (solver(&state->shared->params, state->shared->clues, move + 1)) {
800 for (i = 0; i < wh; i++)
801 move[i+1] |= '@'; /* turn into sensible ASCII */
802 return (char *) move;
805 *error = "Sorry, I can't solve this puzzle";
810 /* compile-time-assert (borderflag is-a-kind-of char).
812 * depends on zero-size arrays being disallowed. GCC says
813 * ISO C forbids this, pointing to [-Werror=edantic]. Also,
814 * it depends on type-checking of (obviously) dead code. */
815 borderflag b[sizeof (borderflag) == sizeof (char)];
816 char c = b[0]; b[0] = c;
817 /* we could at least in principle put this anywhere, but it
818 * seems silly to not put it where the assumption is used. */
822 static int game_can_format_as_text_now(const game_params *params)
827 static char *game_text_format(const game_state *state)
829 int w = state->shared->params.w, h = state->shared->params.h, r, c;
830 int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh;
833 setmem(snewa(board, len + 1), ' ', len);
834 for (r = 0; r < h; ++r) {
835 for (c = 0; c < w; ++c) {
836 int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
837 int i = r * w + c, clue = state->shared->clues[i];
839 if (clue != EMPTY) board[center] = '0' + clue;
843 if (state->borders[i] & BORDER_U)
844 setmem(board + cell + 1, '-', cw - 1);
845 else if (state->borders[i] & DISABLED(BORDER_U))
846 board[cell + cw / 2] = 'x';
848 if (state->borders[i] & BORDER_L)
849 board[cell + gw] = '|';
850 else if (state->borders[i] & DISABLED(BORDER_L))
851 board[cell + gw] = 'x';
854 for (c = 0; c < ch; ++c) {
855 board[(r*ch + c)*gw + gw - 2] = c ? '|' : '+';
856 board[(r*ch + c)*gw + gw - 1] = '\n';
860 scopy(board + len - gw, board, gw);
868 unsigned int show: 1;
871 static game_ui *new_ui(const game_state *state)
873 game_ui *ui = snew(game_ui);
879 static void free_ui(game_ui *ui)
884 static char *encode_ui(const game_ui *ui)
889 static void decode_ui(game_ui *ui, const char *encoding)
891 assert (encoding == NULL);
894 static void game_changed_state(game_ui *ui, const game_state *oldstate,
895 const game_state *newstate)
899 typedef unsigned short dsflags;
901 struct game_drawstate {
906 #define TILESIZE (ds->tilesize)
907 #define MARGIN (ds->tilesize / 2)
908 #define WIDTH (1 + (TILESIZE >= 16) + (TILESIZE >= 32) + (TILESIZE >= 64))
909 #define CENTER ((ds->tilesize / 2) + WIDTH/2)
911 #define FROMCOORD(x) (((x) - MARGIN) / TILESIZE)
913 enum {MAYBE_LEFT, MAYBE_RIGHT, ON_LEFT, ON_RIGHT, OFF_LEFT, OFF_RIGHT};
915 static char *interpret_move(const game_state *state, game_ui *ui,
916 const game_drawstate *ds, int x, int y, int button)
918 int w = state->shared->params.w, h = state->shared->params.h;
919 int control = button & MOD_CTRL, shift = button & MOD_SHFT;
923 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
924 int gx = FROMCOORD(x), gy = FROMCOORD(y), possible = BORDER_MASK;
925 int px = (x - MARGIN) % TILESIZE, py = (y - MARGIN) % TILESIZE;
928 if (OUT_OF_BOUNDS(gx, gy, w, h)) return NULL;
933 /* find edge closest to click point */
934 possible &=~ (2*px < TILESIZE ? BORDER_R : BORDER_L);
935 possible &=~ (2*py < TILESIZE ? BORDER_D : BORDER_U);
936 px = min(px, TILESIZE - px);
937 py = min(py, TILESIZE - py);
938 possible &=~ (px < py ? (BORDER_U|BORDER_D) : (BORDER_L|BORDER_R));
940 for (dir = 0; dir < 4 && BORDER(dir) != possible; ++dir);
941 if (dir == 4) return NULL; /* there's not exactly one such edge */
946 if (OUT_OF_BOUNDS(hx, hy, w, h)) return NULL;
951 switch ((button == RIGHT_BUTTON) |
952 ((state->borders[i] & BORDER(dir)) >> dir << 1) |
953 ((state->borders[i] & DISABLED(BORDER(dir))) >> dir >> 2)) {
958 return string(80, "F%d,%d,%dF%d,%d,%d",
960 hx, hy, BORDER(FLIP(dir)));
965 return string(80, "F%d,%d,%dF%d,%d,%d",
966 gx, gy, DISABLED(BORDER(dir)),
967 hx, hy, DISABLED(BORDER(FLIP(dir))));
971 if (IS_CURSOR_MOVE(button)) {
973 if (control || shift) {
974 borderflag flag = 0, newflag;
975 int dir, i = ui->y * w + ui->x;
978 move_cursor(button, &x, &y, w, h, FALSE);
979 if (OUT_OF_BOUNDS(x, y, w, h)) return NULL;
981 for (dir = 0; dir < 4; ++dir)
982 if (dx[dir] == x - ui->x && dy[dir] == y - ui->y) break;
983 if (dir == 4) return NULL; /* how the ... ?! */
985 if (control) flag |= BORDER(dir);
986 if (shift) flag |= DISABLED(BORDER(dir));
988 newflag = state->borders[i] ^ flag;
989 if (newflag & BORDER(dir) && newflag & DISABLED(BORDER(dir)))
993 if (control) newflag |= BORDER(FLIP(dir));
994 if (shift) newflag |= DISABLED(BORDER(FLIP(dir)));
995 return string(80, "F%d,%d,%dF%d,%d,%d",
996 ui->x, ui->y, flag, x, y, newflag);
998 move_cursor(button, &ui->x, &ui->y, w, h, FALSE);
1006 static game_state *execute_move(const game_state *state, const char *move)
1008 int w = state->shared->params.w, h = state->shared->params.h, wh = w * h;
1009 game_state *ret = dup_game(state);
1010 int nchars, x, y, flag;
1015 for (i = 0; i < wh && move[i]; ++i)
1017 (move[i] & BORDER_MASK) | DISABLED(~move[i] & BORDER_MASK);
1018 if (i < wh || move[i]) return NULL; /* leaks `ret', then we die */
1019 ret->cheated = ret->completed = TRUE;
1023 while (sscanf(move, "F%d,%d,%d%n", &x, &y, &flag, &nchars) == 3 &&
1024 !OUT_OF_BOUNDS(x, y, w, h)) {
1026 ret->borders[y*w + x] ^= flag;
1029 if (*move) return NULL; /* leaks `ret', then we die */
1031 if (!ret->completed)
1032 ret->completed = is_solved(&ret->shared->params, ret->shared->clues,
1038 /* --- Drawing routines --------------------------------------------- */
1040 static void game_compute_size(const game_params *params, int tilesize,
1043 *x = (params->w + 1) * tilesize;
1044 *y = (params->h + 1) * tilesize;
1047 static void game_set_size(drawing *dr, game_drawstate *ds,
1048 const game_params *params, int tilesize)
1050 ds->tilesize = tilesize;
1057 COL_CLUE = COL_GRID,
1058 COL_LINE_YES = COL_GRID,
1066 #define COLOUR(i, r, g, b) \
1067 ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1070 static float *game_colours(frontend *fe, int *ncolours)
1072 float *ret = snewn(3 * NCOLOURS, float);
1074 game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_FLASH);
1076 COLOUR(COL_GRID, 0.0F, 0.0F, 0.0F); /* black */
1077 COLOUR(COL_ERROR, 1.0F, 0.0F, 0.0F); /* red */
1079 COLOUR(COL_LINE_MAYBE, /* yellow */
1080 ret[COL_BACKGROUND*3 + 0] * DARKER,
1081 ret[COL_BACKGROUND*3 + 1] * DARKER,
1085 ret[COL_BACKGROUND*3 + 0] * DARKER,
1086 ret[COL_BACKGROUND*3 + 1] * DARKER,
1087 ret[COL_BACKGROUND*3 + 2] * DARKER);
1089 *ncolours = NCOLOURS;
1094 #define BORDER_ERROR(x) ((x) << 8)
1095 #define F_ERROR_U BORDER_ERROR(BORDER_U) /* BIT( 8) */
1096 #define F_ERROR_R BORDER_ERROR(BORDER_R) /* BIT( 9) */
1097 #define F_ERROR_D BORDER_ERROR(BORDER_D) /* BIT(10) */
1098 #define F_ERROR_L BORDER_ERROR(BORDER_L) /* BIT(11) */
1099 #define F_ERROR_CLUE BIT(12)
1100 #define F_FLASH BIT(13)
1101 #define F_CURSOR BIT(14)
1103 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1105 struct game_drawstate *ds = snew(struct game_drawstate);
1113 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1119 #define COLOUR(border) \
1120 (flags & BORDER_ERROR((border)) ? COL_ERROR : \
1121 flags & (border) ? COL_LINE_YES : \
1122 flags & DISABLED((border)) ? COL_LINE_NO : \
1125 static void draw_tile(drawing *dr, game_drawstate *ds, int r, int c,
1126 dsflags flags, int clue)
1128 int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1130 clip(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH); /* { */
1132 draw_rect(dr, x + WIDTH, y + WIDTH, TILESIZE - WIDTH, TILESIZE - WIDTH,
1133 (flags & F_FLASH ? COL_FLASH : COL_BACKGROUND));
1135 if (flags & F_CURSOR)
1136 draw_rect_corners(dr, x + CENTER, y + CENTER, TILESIZE / 3, COL_GRID);
1138 if (clue != EMPTY) {
1140 buf[0] = '0' + clue;
1142 draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE,
1143 TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1144 (flags & F_ERROR_CLUE ? COL_ERROR : COL_CLUE), buf);
1150 draw_rect(dr, x + w, y, ts - w, w, COLOUR(BORDER_U));
1151 draw_rect(dr, x + ts, y + w, w, ts - w, COLOUR(BORDER_R));
1152 draw_rect(dr, x + w, y + ts, ts - w, w, COLOUR(BORDER_D));
1153 draw_rect(dr, x, y + w, w, ts - w, COLOUR(BORDER_L));
1158 draw_update(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH);
1161 #define FLASH_TIME 0.7F
1163 static void game_redraw(drawing *dr, game_drawstate *ds,
1164 const game_state *oldstate, const game_state *state,
1165 int dir, const game_ui *ui,
1166 float animtime, float flashtime)
1168 int w = state->shared->params.w, h = state->shared->params.h, wh = w*h;
1169 int r, c, i, flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2;
1170 int *black_border_dsf = snew_dsf(wh), *yellow_border_dsf = snew_dsf(wh);
1171 int k = state->shared->params.k;
1175 int bgw = (w+1) * ds->tilesize, bgh = (h+1) * ds->tilesize;
1176 draw_rect(dr, 0, 0, bgw, bgh, COL_BACKGROUND);
1178 for (r = 0; r <= h; ++r)
1179 for (c = 0; c <= w; ++c)
1180 draw_rect(dr, MARGIN + TILESIZE * c, MARGIN + TILESIZE * r,
1181 WIDTH, WIDTH, COL_GRID);
1182 draw_update(dr, 0, 0, bgw, bgh);
1184 snewa(ds->grid, wh);
1185 setmem(ds->grid, ~0, wh);
1187 sprintf(buf, "Region size: %d", state->shared->params.k);
1188 status_bar(dr, buf);
1191 for (i = 0; i < wh; ++i) {
1192 if (black_border_dsf[i] == UNVISITED)
1193 dfs_dsf(i, w, state->borders, black_border_dsf, TRUE);
1194 if (yellow_border_dsf[i] == UNVISITED)
1195 dfs_dsf(i, w, state->borders, yellow_border_dsf, FALSE);
1198 for (r = 0; r < h; ++r)
1199 for (c = 0; c < w; ++c) {
1200 int i = r * w + c, clue = state->shared->clues[i], flags, dir;
1201 int on = bitcount[state->borders[i] & BORDER_MASK];
1202 int off = bitcount[(state->borders[i] >> 4) & BORDER_MASK];
1204 flags = state->borders[i];
1206 if (flash) flags |= F_FLASH;
1208 if (clue != EMPTY && (on > clue || clue > 4 - off))
1209 flags |= F_ERROR_CLUE;
1211 if (ui->show && ui->x == c && ui->y == r)
1215 for (dir = 0; dir < 4; ++dir) {
1216 int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc;
1218 if (OUT_OF_BOUNDS(cc, rr, w, h)) continue;
1220 /* we draw each border twice, except the outermost
1221 * big border, so we have to check for errors on
1222 * both sides of each border.*/
1223 if (/* region too large */
1224 ((dsf_size(yellow_border_dsf, i) > k ||
1225 dsf_size(yellow_border_dsf, ii) > k) &&
1226 (dsf_canonify(yellow_border_dsf, i) !=
1227 dsf_canonify(yellow_border_dsf, ii)))
1230 /* region too small */
1231 ((dsf_size(black_border_dsf, i) < k ||
1232 dsf_size(black_border_dsf, ii) < k) &&
1233 dsf_canonify(black_border_dsf, i) !=
1234 dsf_canonify(black_border_dsf, ii))
1237 /* dangling borders within a single region */
1238 ((state->borders[i] & BORDER(dir)) &&
1239 /* we know it's a single region because there's a
1240 * path crossing no border from i to ii... */
1241 (dsf_canonify(yellow_border_dsf, i) ==
1242 dsf_canonify(yellow_border_dsf, ii) ||
1243 /* or because any such border would be an error */
1244 (dsf_size(black_border_dsf, i) <= k &&
1245 dsf_canonify(black_border_dsf, i) ==
1246 dsf_canonify(black_border_dsf, ii)))))
1248 flags |= BORDER_ERROR(BORDER(dir));
1251 if (flags == ds->grid[i]) continue;
1252 ds->grid[i] = flags;
1253 draw_tile(dr, ds, r, c, ds->grid[i], clue);
1256 sfree(black_border_dsf);
1257 sfree(yellow_border_dsf);
1260 static float game_anim_length(const game_state *oldstate,
1261 const game_state *newstate,
1262 int dir, game_ui *ui)
1267 static float game_flash_length(const game_state *oldstate,
1268 const game_state *newstate,
1269 int dir, game_ui *ui)
1271 if (newstate->completed && !newstate->cheated && !oldstate->completed)
1276 static int game_status(const game_state *state)
1278 return state->completed ? +1 : 0;
1281 static int game_timing_state(const game_state *state, game_ui *ui)
1283 assert (!"this shouldn't get called");
1284 return 0; /* placate optimiser */
1287 static void game_print_size(const game_params *params, float *x, float *y)
1291 game_compute_size(params, 700, &pw, &ph); /* 7mm, like loopy */
1297 static void print_line(drawing *dr, int x1, int y1, int x2, int y2,
1298 int colour, int full)
1301 int i, subdivisions = 8;
1302 for (i = 1; i < subdivisions; ++i) {
1303 int x = (x1 * (subdivisions - i) + x2 * i) / subdivisions;
1304 int y = (y1 * (subdivisions - i) + y2 * i) / subdivisions;
1305 draw_circle(dr, x, y, 3, colour, colour);
1307 } else draw_line(dr, x1, y1, x2, y2, colour);
1310 static void game_print(drawing *dr, const game_state *state, int tilesize)
1312 int w = state->shared->params.w, h = state->shared->params.h;
1313 int ink = print_mono_colour(dr, 0);
1314 game_drawstate for_tilesize_macros, *ds = &for_tilesize_macros;
1317 ds->tilesize = tilesize;
1319 for (r = 0; r < h; ++r)
1320 for (c = 0; c < w; ++c) {
1321 int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1322 int i = r * w + c, clue = state->shared->clues[i];
1324 if (clue != EMPTY) {
1326 buf[0] = '0' + clue;
1328 draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE,
1329 TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1334 #define FULL(DIR) (state->borders[i] & (BORDER_ ## DIR))
1335 print_line(dr, x, y, x + ts, y, ink, FULL(U));
1336 print_line(dr, x + ts, y, x + ts, y + ts, ink, FULL(R));
1337 print_line(dr, x, y + ts, x + ts, y + ts, ink, FULL(D));
1338 print_line(dr, x, y, x, y + ts, ink, FULL(L));
1343 for (r = 1; r < h; ++r)
1344 for (c = 1; c < w; ++c) {
1345 int j = r * w + c, i = j - 1 - w;
1346 int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1347 if (state->borders[i] & (BORDER_D|BORDER_R)) continue;
1348 if (state->borders[j] & (BORDER_U|BORDER_L)) continue;
1349 draw_circle(dr, x, y, 3, ink, ink);
1354 #define thegame palisade
1357 const struct game thegame = {
1358 "Palisade", "games.palisade", "palisade",
1360 game_fetch_preset, NULL,
1365 TRUE, game_configure, custom_params,
1373 TRUE, game_can_format_as_text_now, game_text_format,
1381 48, game_compute_size, game_set_size,
1384 game_free_drawstate,
1389 TRUE, FALSE, game_print_size, game_print,
1390 TRUE, /* wants_statusbar */
1391 FALSE, game_timing_state,