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 CONFIG(0, "Width", C_STRING
, 0, string(20, "%d", params
->w
));
123 CONFIG(1, "Height", C_STRING
, 0, string(20, "%d", params
->h
));
124 CONFIG(2, "Region size", C_STRING
, 0, string(20, "%d", params
->k
));
125 CONFIG(3, NULL
, C_END
, 0, NULL
);
130 static game_params
*custom_params(const config_item
*cfg
)
132 game_params
*params
= snew(game_params
);
134 params
->w
= atoi(cfg
[0].sval
);
135 params
->h
= atoi(cfg
[1].sval
);
136 params
->k
= atoi(cfg
[2].sval
);
141 /* +---+ << The one possible domino (up to symmetry). +---+---+
143 * | | If two dominos are adjacent as depicted here >> +---+---+
144 * | 3 | then it's ambiguous whether the edge between | 3 | 3 |
145 * +---+ the dominos is horizontal or vertical. +---+---+
148 static char *validate_params(const game_params
*params
, int full
)
150 int w
= params
->w
, h
= params
->h
, k
= params
->k
, wh
= w
* h
;
152 if (k
< 1) return "Region size must be at least one";
153 if (w
< 1) return "Width must be at least one";
154 if (h
< 1) return "Height must be at least one";
155 if (wh
% k
) return "Region size must divide grid area";
157 if (!full
) return NULL
; /* succeed partial validation */
159 /* MAYBE FIXME: we (just?) don't have the UI for winning these. */
160 if (k
== wh
) return "Region size must be less than the grid area";
161 assert (k
< wh
); /* or wh % k != 0 */
163 if (k
== 2 && w
!= 1 && h
!= 1)
164 return "Region size can't be two unless width or height is one";
166 return NULL
; /* succeed full validation */
169 /* --- Solver ------------------------------------------------------- */
171 /* the solver may write at will to these arrays, but shouldn't free them */
172 /* it's up to the client to dup/free as needed */
173 typedef struct solver_ctx
{
174 const game_params
*params
; /* also in shared_state */
175 clue
*clues
; /* also in shared_state */
176 borderflag
*borders
; /* also in game_state */
177 int *dsf
; /* particular to the solver */
182 * - If two adjacent clues do not have a border between them, this
183 * gives a lower limit on the size of their region (which is also an
184 * upper limit if both clues are 3). Rule out any non-border which
185 * would make its region either too large or too small.
187 * - If a clue, k, is adjacent to k borders or (4 - k) non-borders,
188 * the remaining edges incident to the clue are readily decided.
190 * - If a region has only one other region (e.g. square) to grow into
191 * and it's not of full size yet, grow it into that one region.
193 * - If two regions are adjacent and their combined size would be too
194 * large, put an edge between them.
196 * - If a border is adjacent to two non-borders, its last vertex-mate
197 * must also be a border. If a maybe-border is adjacent to three
198 * nonborders, the maybe-border is a non-border.
200 * - If a clue square is adjacent to several squares belonging to the
201 * same region, and enabling (disabling) those borders would violate
202 * the clue, those borders must be disabled (enabled).
204 * - If there's a path crossing only non-borders between two squares,
205 * the maybe-border between them is a non-border.
206 * (This is implicitly computed in the dsf representation)
211 * If a vertex is adjacent to a LINE_YES and (4-3)*LINE_NO, at least
212 * one of the last two edges are LINE_YES. If they're adjacent to a
213 * 1, then the other two edges incident to that 1 are LINE_NO.
215 * For each square: set all as unknown, then for each k-omino and each
216 * way of placing it on that square, if that way is consistent with
217 * the board, mark its edges and interior as possible LINE_YES and
218 * LINE_NO, respectively. When all k-ominos are through, see what
219 * isn't possible and remove those impossibilities from the board.
220 * (Sounds pretty nasty for k > 4 or so.)
222 * A black-bordered subregion must have a size divisible by k. So,
223 * draw a graph with one node per dsf component and edges between
224 * those dsf components which have adjacent squares. Identify cut
225 * vertices and edges. If a cut-vertex-delimited component contains a
226 * number of squares not divisible by k, cut vertex not included, then
227 * the cut vertex must belong to the component. If it has exactly one
228 * edge _out_ of the component, the line(s) corresponding to that edge
229 * are all LINE_YES (i.e. a BORDER()).
230 * (This sounds complicated, but visually it is rather easy.)
232 * [Look at loopy and see how the at-least/-most k out of m edges
233 * thing is done. See how it is propagated across multiple squares.]
238 #define BIT(i) (1 << (i))
239 #define BORDER(i) BIT(i)
240 #define BORDER_U BORDER(0)
241 #define BORDER_R BORDER(1)
242 #define BORDER_D BORDER(2)
243 #define BORDER_L BORDER(3)
244 #define FLIP(i) ((i) ^ 2)
245 #define BORDER_MASK (BORDER_U|BORDER_R|BORDER_D|BORDER_L)
246 #define DISABLED(border) ((border) << 4)
247 #define UNDISABLED(border) ((border) >> 4)
249 static const int dx
[4] = { 0, +1, 0, -1};
250 static const int dy
[4] = {-1, 0, +1, 0};
251 static const int bitcount
[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
252 /* bitcount[x & BORDER_MASK] == number of enabled borders */
254 #define COMPUTE_J (-1)
256 static void connect(solver_ctx
*ctx
, int i
, int j
)
258 dsf_merge(ctx
->dsf
, i
, j
);
261 static int connected(solver_ctx
*ctx
, int i
, int j
, int dir
)
263 if (j
== COMPUTE_J
) j
= i
+ dx
[dir
] + ctx
->params
->w
*dy
[dir
];
264 return dsf_canonify(ctx
->dsf
, i
) == dsf_canonify(ctx
->dsf
, j
);
267 static void disconnect(solver_ctx
*ctx
, int i
, int j
, int dir
)
269 if (j
== COMPUTE_J
) j
= i
+ dx
[dir
] + ctx
->params
->w
*dy
[dir
];
270 ctx
->borders
[i
] |= BORDER(dir
);
271 ctx
->borders
[j
] |= BORDER(FLIP(dir
));
274 static int disconnected(solver_ctx
*ctx
, int i
, int j
, int dir
)
276 assert (j
== COMPUTE_J
|| j
== i
+ dx
[dir
] + ctx
->params
->w
*dy
[dir
]);
277 return ctx
->borders
[i
] & BORDER(dir
);
280 static int maybe(solver_ctx
*ctx
, int i
, int j
, int dir
)
282 assert (j
== COMPUTE_J
|| j
== i
+ dx
[dir
] + ctx
->params
->w
*dy
[dir
]);
283 return !disconnected(ctx
, i
, j
, dir
) && !connected(ctx
, i
, j
, dir
);
284 /* the ordering is important: disconnected works for invalid
285 * squares (i.e. out of bounds), connected doesn't. */
288 static void solver_connected_clues_versus_region_size(solver_ctx
*ctx
)
290 int w
= ctx
->params
->w
, h
= ctx
->params
->h
, wh
= w
*h
, i
, dir
;
292 /* If i is connected to j and i has borders with p of the
293 * remaining three squares and j with q of the remaining three
294 * squares, then the region has size at least 1+(3-p) + 1+(3-q).
295 * If p = q = 3 then the region has size exactly 2. */
297 for (i
= 0; i
< wh
; ++i
) {
298 if (ctx
->clues
[i
] == EMPTY
) continue;
299 for (dir
= 0; dir
< 4; ++dir
) {
300 int j
= i
+ dx
[dir
] + w
*dy
[dir
];
301 if (disconnected(ctx
, i
, j
, dir
)) continue;
302 if (ctx
->clues
[j
] == EMPTY
) continue;
303 if ((8 - ctx
->clues
[i
] - ctx
->clues
[j
] > ctx
->params
->k
) ||
304 (ctx
->clues
[i
] == 3 && ctx
->clues
[j
] == 3 &&
305 ctx
->params
->k
!= 2))
307 disconnect(ctx
, i
, j
, dir
);
308 /* changed = TRUE, but this is a one-shot... */
314 static int solver_number_exhausted(solver_ctx
*ctx
)
316 int w
= ctx
->params
->w
, h
= ctx
->params
->h
, wh
= w
*h
, i
, dir
, off
;
319 for (i
= 0; i
< wh
; ++i
) {
320 if (ctx
->clues
[i
] == EMPTY
) continue;
322 if (bitcount
[(ctx
->borders
[i
] & BORDER_MASK
)] == ctx
->clues
[i
]) {
323 for (dir
= 0; dir
< 4; ++dir
) {
324 int j
= i
+ dx
[dir
] + w
*dy
[dir
];
325 if (!maybe(ctx
, i
, j
, dir
)) continue;
332 for (off
= dir
= 0; dir
< 4; ++dir
) {
333 int j
= i
+ dx
[dir
] + w
*dy
[dir
];
334 if (!disconnected(ctx
, i
, j
, dir
) && connected(ctx
, i
, j
, dir
))
335 ++off
; /* ^^^ bounds checking before ^^^^^ */
338 if (ctx
->clues
[i
] == 4 - off
)
339 for (dir
= 0; dir
< 4; ++dir
) {
340 int j
= i
+ dx
[dir
] + w
*dy
[dir
];
341 if (!maybe(ctx
, i
, j
, dir
)) continue;
342 disconnect(ctx
, i
, j
, dir
);
350 static int solver_not_too_big(solver_ctx
*ctx
)
352 int w
= ctx
->params
->w
, h
= ctx
->params
->h
, wh
= w
*h
, i
, dir
;
355 for (i
= 0; i
< wh
; ++i
) {
356 int size
= dsf_size(ctx
->dsf
, i
);
357 for (dir
= 0; dir
< 4; ++dir
) {
358 int j
= i
+ dx
[dir
] + w
*dy
[dir
];
359 if (!maybe(ctx
, i
, j
, dir
)) continue;
360 if (size
+ dsf_size(ctx
->dsf
, j
) <= ctx
->params
->k
) continue;
361 disconnect(ctx
, i
, j
, dir
);
369 static int solver_not_too_small(solver_ctx
*ctx
)
371 int w
= ctx
->params
->w
, h
= ctx
->params
->h
, wh
= w
*h
, i
, dir
;
372 int *outs
, k
= ctx
->params
->k
, ci
, changed
= FALSE
;
375 setmem(outs
, -1, wh
);
377 for (i
= 0; i
< wh
; ++i
) {
378 ci
= dsf_canonify(ctx
->dsf
, i
);
379 if (dsf_size(ctx
->dsf
, ci
) == k
) continue;
380 for (dir
= 0; dir
< 4; ++dir
) {
381 int j
= i
+ dx
[dir
] + w
*dy
[dir
];
382 if (!maybe(ctx
, i
, j
, dir
)) continue;
383 if (outs
[ci
] == -1) outs
[ci
] = dsf_canonify(ctx
->dsf
, j
);
384 else if (outs
[ci
] != dsf_canonify(ctx
->dsf
, j
)) outs
[ci
] = -2;
388 for (i
= 0; i
< wh
; ++i
) {
390 if (i
!= dsf_canonify(ctx
->dsf
, i
)) continue;
392 connect(ctx
, i
, j
); /* only one place for i to grow */
400 static int solver_no_dangling_edges(solver_ctx
*ctx
)
402 int w
= ctx
->params
->w
, h
= ctx
->params
->h
, r
, c
;
405 /* for each vertex */
406 for (r
= 1; r
< h
; ++r
)
407 for (c
= 1; c
< w
; ++c
) {
408 int i
= r
* w
+ c
, j
= i
- w
- 1, noline
= 0, dir
;
409 int squares
[4], e
= -1, f
= -1, de
= -1, df
= -1;
411 /* feels hacky: I align these with BORDER_[U0 R1 D2 L3] */
412 squares
[1] = squares
[2] = j
;
413 squares
[0] = squares
[3] = i
;
415 /* for each edge adjacent to the vertex */
416 for (dir
= 0; dir
< 4; ++dir
)
417 if (!connected(ctx
, squares
[dir
], COMPUTE_J
, dir
)) {
420 if (e
!= -1) continue;
425 if (4 - noline
== 1) {
427 disconnect(ctx
, e
, COMPUTE_J
, de
);
432 if (4 - noline
!= 2) continue;
437 if (ctx
->borders
[e
] & BORDER(de
)) {
438 if (!(ctx
->borders
[f
] & BORDER(df
))) {
439 disconnect(ctx
, f
, COMPUTE_J
, df
);
442 } else if (ctx
->borders
[f
] & BORDER(df
)) {
443 disconnect(ctx
, e
, COMPUTE_J
, de
);
451 static int solver_equivalent_edges(solver_ctx
*ctx
)
453 int w
= ctx
->params
->w
, h
= ctx
->params
->h
, wh
= w
*h
, i
, dirj
;
456 /* if a square is adjacent to two connected squares, the two
457 * borders (i,j) and (i,k) are either both on or both off. */
459 for (i
= 0; i
< wh
; ++i
) {
460 int n_on
= 0, n_off
= 0;
461 if (ctx
->clues
[i
] < 1 || ctx
->clues
[i
] > 3) continue;
463 if (ctx
->clues
[i
] == 2 /* don't need it otherwise */)
464 for (dirj
= 0; dirj
< 4; ++dirj
) {
465 int j
= i
+ dx
[dirj
] + w
*dy
[dirj
];
466 if (disconnected(ctx
, i
, j
, dirj
)) ++n_on
;
467 else if (connected(ctx
, i
, j
, dirj
)) ++n_off
;
470 for (dirj
= 0; dirj
< 4; ++dirj
) {
471 int j
= i
+ dx
[dirj
] + w
*dy
[dirj
], dirk
;
472 if (!maybe(ctx
, i
, j
, dirj
)) continue;
474 for (dirk
= dirj
+ 1; dirk
< 4; ++dirk
) {
475 int k
= i
+ dx
[dirk
] + w
*dy
[dirk
];
476 if (!maybe(ctx
, i
, k
, dirk
)) continue;
477 if (!connected(ctx
, j
, k
, -1)) continue;
479 if (n_on
+ 2 > ctx
->clues
[i
]) {
483 } else if (n_off
+ 2 > 4 - ctx
->clues
[i
]) {
484 disconnect(ctx
, i
, j
, dirj
);
485 disconnect(ctx
, i
, k
, dirk
);
497 /* build connected components in `dsf', along the lines of `borders'. */
498 static void dfs_dsf(int i
, int w
, borderflag
*border
, int *dsf
, int black
)
501 for (dir
= 0; dir
< 4; ++dir
) {
502 int ii
= i
+ dx
[dir
] + w
*dy
[dir
], bdir
= BORDER(dir
);
503 if (black
? (border
[i
] & bdir
) : !(border
[i
] & DISABLED(bdir
)))
505 if (dsf
[ii
] != UNVISITED
) continue;
506 dsf_merge(dsf
, i
, ii
);
507 dfs_dsf(ii
, w
, border
, dsf
, black
);
511 static int is_solved(const game_params
*params
, clue
*clues
,
514 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, k
= params
->k
;
516 int *dsf
= snew_dsf(wh
);
518 assert (dsf
[0] == UNVISITED
); /* check: UNVISITED and dsf.c match up */
521 * A game is solved if:
523 * - the borders drawn on the grid divide it into connected
524 * components such that every square is in a component of the
526 * - the borders also satisfy the clue set
528 for (i
= 0; i
< wh
; ++i
) {
529 if (dsf
[i
] == UNVISITED
) dfs_dsf(i
, params
->w
, border
, dsf
, TRUE
);
530 if (dsf_size(dsf
, i
) != k
) goto error
;
531 if (clues
[i
] == EMPTY
) continue;
532 if (clues
[i
] != bitcount
[border
[i
] & BORDER_MASK
]) goto error
;
538 * - there are no *stray* borders, in that every border is
539 * actually part of the division between two components.
540 * Otherwise you could cheat by finding a subdivision which did
541 * not *exceed* any clue square's counter, and then adding a
544 for (y
= 0; y
< h
; y
++) {
545 for (x
= 0; x
< w
; x
++) {
546 if (x
+1 < w
&& (border
[y
*w
+x
] & BORDER_R
) &&
547 dsf_canonify(dsf
, y
*w
+x
) == dsf_canonify(dsf
, y
*w
+(x
+1)))
549 if (y
+1 < h
&& (border
[y
*w
+x
] & BORDER_D
) &&
550 dsf_canonify(dsf
, y
*w
+x
) == dsf_canonify(dsf
, (y
+1)*w
+x
))
563 static int solver(const game_params
*params
, clue
*clues
, borderflag
*borders
)
565 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, changed
;
570 ctx
.borders
= borders
;
571 ctx
.dsf
= snew_dsf(wh
);
573 solver_connected_clues_versus_region_size(&ctx
); /* idempotent */
576 changed
|= solver_number_exhausted(&ctx
);
577 changed
|= solver_not_too_big(&ctx
);
578 changed
|= solver_not_too_small(&ctx
);
579 changed
|= solver_no_dangling_edges(&ctx
);
580 changed
|= solver_equivalent_edges(&ctx
);
585 return is_solved(params
, clues
, borders
);
588 /* --- Generator ---------------------------------------------------- */
590 static void init_borders(int w
, int h
, borderflag
*borders
)
593 setmem(borders
, 0, w
*h
);
594 for (c
= 0; c
< w
; ++c
) {
595 borders
[c
] |= BORDER_U
;
596 borders
[w
*h
-1 - c
] |= BORDER_D
;
598 for (r
= 0; r
< h
; ++r
) {
599 borders
[r
*w
] |= BORDER_L
;
600 borders
[w
*h
-1 - r
*w
] |= BORDER_R
;
604 #define OUT_OF_BOUNDS(x, y, w, h) \
605 ((x) < 0 || (x) >= (w) || (y) < 0 || (y) >= (h))
607 #define xshuffle(ptr, len, rs) shuffle((ptr), (len), sizeof (ptr)[0], (rs))
609 static char *new_game_desc(const game_params
*params
, random_state
*rs
,
610 char **aux
, int interactive
)
612 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, k
= params
->k
;
614 clue
*numbers
= snewn(wh
+ 1, clue
), *p
;
615 borderflag
*rim
= snewn(wh
, borderflag
);
616 borderflag
*scratch_borders
= snewn(wh
, borderflag
);
618 char *soln
= snewa(*aux
, wh
+ 2);
619 int *shuf
= snewn(wh
, int);
620 int *dsf
= NULL
, i
, r
, c
;
624 for (i
= 0; i
< wh
; ++i
) shuf
[i
] = i
;
625 xshuffle(shuf
, wh
, rs
);
627 init_borders(w
, h
, rim
);
629 assert (!('@' & BORDER_MASK
));
635 setmem(soln
, '@', wh
);
638 dsf
= divvy_rectangle(w
, h
, k
, rs
);
640 for (r
= 0; r
< h
; ++r
)
641 for (c
= 0; c
< w
; ++c
) {
642 int i
= r
* w
+ c
, dir
;
644 for (dir
= 0; dir
< 4; ++dir
) {
645 int rr
= r
+ dy
[dir
], cc
= c
+ dx
[dir
], ii
= rr
* w
+ cc
;
646 if (OUT_OF_BOUNDS(cc
, rr
, w
, h
) ||
647 dsf_canonify(dsf
, i
) != dsf_canonify(dsf
, ii
)) {
649 soln
[i
] |= BORDER(dir
);
654 scopy(scratch_borders
, rim
, wh
);
655 } while (!solver(params
, numbers
, scratch_borders
));
657 for (i
= 0; i
< wh
; ++i
) {
659 clue copy
= numbers
[j
];
661 scopy(scratch_borders
, rim
, wh
);
662 numbers
[j
] = EMPTY
; /* strip away unnecssary clues */
663 if (!solver(params
, numbers
, scratch_borders
))
669 sfree(scratch_borders
);
676 for (i
= 0; i
< wh
; ++i
) {
677 if (numbers
[i
] != EMPTY
) {
686 *p
++ = '0' + numbers
[i
];
691 return sresize(numbers
, p
- numbers
, clue
);
694 static char *validate_desc(const game_params
*params
, const char *desc
)
697 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, squares
= 0;
699 for (/* nop */; *desc
; ++desc
) {
700 if (islower((unsigned char)*desc
)) {
701 squares
+= *desc
- 'a' + 1;
702 } else if (isdigit((unsigned char)*desc
)) {
704 static char buf
[] = "Invalid (too large) number: '5'";
705 assert (isdigit((unsigned char)buf
[lenof(buf
) - 3]));
706 buf
[lenof(buf
) - 3] = *desc
; /* ... or 6, 7, 8, 9 :-) */
710 } else if (isprint((unsigned char)*desc
)) {
711 static char buf
[] = "Invalid character in data: '?'";
712 buf
[lenof(buf
) - 3] = *desc
;
714 } else return "Invalid (unprintable) character in data";
717 if (squares
> wh
) return "Data describes too many squares";
722 static game_state
*new_game(midend
*me
, const game_params
*params
,
725 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, i
;
726 game_state
*state
= snew(game_state
);
728 state
->shared
= snew(shared_state
);
729 state
->shared
->refcount
= 1;
730 state
->shared
->params
= *params
; /* struct copy */
731 snewa(state
->shared
->clues
, wh
);
733 setmem(state
->shared
->clues
, EMPTY
, wh
);
734 for (i
= 0; *desc
; ++desc
) {
735 if (isdigit((unsigned char)*desc
)) state
->shared
->clues
[i
++] = *desc
- '0';
736 else if (isalpha((unsigned char)*desc
)) i
+= *desc
- 'a' + 1;
739 snewa(state
->borders
, wh
);
740 init_borders(w
, h
, state
->borders
);
742 state
->completed
= (params
->k
== wh
);
743 state
->cheated
= FALSE
;
748 static game_state
*dup_game(const game_state
*state
)
750 int wh
= state
->shared
->params
.w
* state
->shared
->params
.h
;
751 game_state
*ret
= snew(game_state
);
753 ret
->borders
= dupmem(state
->borders
, wh
);
755 ret
->shared
= state
->shared
;
756 ++ret
->shared
->refcount
;
758 ret
->completed
= state
->completed
;
759 ret
->cheated
= state
->cheated
;
764 static void free_game(game_state
*state
)
766 if (--state
->shared
->refcount
== 0) {
767 sfree(state
->shared
->clues
);
768 sfree(state
->shared
);
770 sfree(state
->borders
);
774 static char *solve_game(const game_state
*state
, const game_state
*currstate
,
775 const char *aux
, char **error
)
777 int w
= state
->shared
->params
.w
, h
= state
->shared
->params
.h
, wh
= w
*h
;
780 if (aux
) return dupstr(aux
);
785 init_borders(w
, h
, move
+ 1);
788 if (solver(&state
->shared
->params
, state
->shared
->clues
, move
+ 1)) {
790 for (i
= 0; i
< wh
; i
++)
791 move
[i
+1] |= '@'; /* turn into sensible ASCII */
792 return (char *) move
;
795 *error
= "Sorry, I can't solve this puzzle";
800 /* compile-time-assert (borderflag is-a-kind-of char).
802 * depends on zero-size arrays being disallowed. GCC says
803 * ISO C forbids this, pointing to [-Werror=edantic]. Also,
804 * it depends on type-checking of (obviously) dead code. */
805 borderflag b
[sizeof (borderflag
) == sizeof (char)];
806 char c
= b
[0]; b
[0] = c
;
807 /* we could at least in principle put this anywhere, but it
808 * seems silly to not put it where the assumption is used. */
812 static int game_can_format_as_text_now(const game_params
*params
)
817 static char *game_text_format(const game_state
*state
)
819 int w
= state
->shared
->params
.w
, h
= state
->shared
->params
.h
, r
, c
;
820 int cw
= 4, ch
= 2, gw
= cw
*w
+ 2, gh
= ch
* h
+ 1, len
= gw
* gh
;
823 setmem(snewa(board
, len
+ 1), ' ', len
);
824 for (r
= 0; r
< h
; ++r
) {
825 for (c
= 0; c
< w
; ++c
) {
826 int cell
= r
*ch
*gw
+ cw
*c
, center
= cell
+ gw
*ch
/2 + cw
/2;
827 int i
= r
* w
+ c
, clue
= state
->shared
->clues
[i
];
829 if (clue
!= EMPTY
) board
[center
] = '0' + clue
;
833 if (state
->borders
[i
] & BORDER_U
)
834 setmem(board
+ cell
+ 1, '-', cw
- 1);
835 else if (state
->borders
[i
] & DISABLED(BORDER_U
))
836 board
[cell
+ cw
/ 2] = 'x';
838 if (state
->borders
[i
] & BORDER_L
)
839 board
[cell
+ gw
] = '|';
840 else if (state
->borders
[i
] & DISABLED(BORDER_L
))
841 board
[cell
+ gw
] = 'x';
844 for (c
= 0; c
< ch
; ++c
) {
845 board
[(r
*ch
+ c
)*gw
+ gw
- 2] = c
? '|' : '+';
846 board
[(r
*ch
+ c
)*gw
+ gw
- 1] = '\n';
850 scopy(board
+ len
- gw
, board
, gw
);
858 unsigned int show
: 1;
861 static game_ui
*new_ui(const game_state
*state
)
863 game_ui
*ui
= snew(game_ui
);
869 static void free_ui(game_ui
*ui
)
874 static char *encode_ui(const game_ui
*ui
)
879 static void decode_ui(game_ui
*ui
, const char *encoding
)
881 assert (encoding
== NULL
);
884 static void game_changed_state(game_ui
*ui
, const game_state
*oldstate
,
885 const game_state
*newstate
)
889 typedef unsigned short dsflags
;
891 struct game_drawstate
{
896 #define TILESIZE (ds->tilesize)
897 #define MARGIN (ds->tilesize / 2)
898 #define WIDTH (1 + (TILESIZE >= 16) + (TILESIZE >= 32) + (TILESIZE >= 64))
899 #define CENTER ((ds->tilesize / 2) + WIDTH/2)
901 #define FROMCOORD(x) (((x) - MARGIN) / TILESIZE)
903 enum {MAYBE_LEFT
, MAYBE_RIGHT
, ON_LEFT
, ON_RIGHT
, OFF_LEFT
, OFF_RIGHT
};
905 static char *interpret_move(const game_state
*state
, game_ui
*ui
,
906 const game_drawstate
*ds
, int x
, int y
, int button
)
908 int w
= state
->shared
->params
.w
, h
= state
->shared
->params
.h
;
909 int control
= button
& MOD_CTRL
, shift
= button
& MOD_SHFT
;
913 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
914 int gx
= FROMCOORD(x
), gy
= FROMCOORD(y
), possible
= BORDER_MASK
;
915 int px
= (x
- MARGIN
) % TILESIZE
, py
= (y
- MARGIN
) % TILESIZE
;
918 if (OUT_OF_BOUNDS(gx
, gy
, w
, h
)) return NULL
;
923 /* find edge closest to click point */
924 possible
&=~ (2*px
< TILESIZE
? BORDER_R
: BORDER_L
);
925 possible
&=~ (2*py
< TILESIZE
? BORDER_D
: BORDER_U
);
926 px
= min(px
, TILESIZE
- px
);
927 py
= min(py
, TILESIZE
- py
);
928 possible
&=~ (px
< py
? (BORDER_U
|BORDER_D
) : (BORDER_L
|BORDER_R
));
930 for (dir
= 0; dir
< 4 && BORDER(dir
) != possible
; ++dir
);
931 if (dir
== 4) return NULL
; /* there's not exactly one such edge */
936 if (OUT_OF_BOUNDS(hx
, hy
, w
, h
)) return NULL
;
941 switch ((button
== RIGHT_BUTTON
) |
942 ((state
->borders
[i
] & BORDER(dir
)) >> dir
<< 1) |
943 ((state
->borders
[i
] & DISABLED(BORDER(dir
))) >> dir
>> 2)) {
948 return string(80, "F%d,%d,%dF%d,%d,%d",
950 hx
, hy
, BORDER(FLIP(dir
)));
955 return string(80, "F%d,%d,%dF%d,%d,%d",
956 gx
, gy
, DISABLED(BORDER(dir
)),
957 hx
, hy
, DISABLED(BORDER(FLIP(dir
))));
961 if (IS_CURSOR_MOVE(button
)) {
963 if (control
|| shift
) {
964 borderflag flag
= 0, newflag
;
965 int dir
, i
= ui
->y
* w
+ ui
->x
;
968 move_cursor(button
, &x
, &y
, w
, h
, FALSE
);
969 if (OUT_OF_BOUNDS(x
, y
, w
, h
)) return NULL
;
971 for (dir
= 0; dir
< 4; ++dir
)
972 if (dx
[dir
] == x
- ui
->x
&& dy
[dir
] == y
- ui
->y
) break;
973 if (dir
== 4) return NULL
; /* how the ... ?! */
975 if (control
) flag
|= BORDER(dir
);
976 if (shift
) flag
|= DISABLED(BORDER(dir
));
978 newflag
= state
->borders
[i
] ^ flag
;
979 if (newflag
& BORDER(dir
) && newflag
& DISABLED(BORDER(dir
)))
983 if (control
) newflag
|= BORDER(FLIP(dir
));
984 if (shift
) newflag
|= DISABLED(BORDER(FLIP(dir
)));
985 return string(80, "F%d,%d,%dF%d,%d,%d",
986 ui
->x
, ui
->y
, flag
, x
, y
, newflag
);
988 move_cursor(button
, &ui
->x
, &ui
->y
, w
, h
, FALSE
);
996 static game_state
*execute_move(const game_state
*state
, const char *move
)
998 int w
= state
->shared
->params
.w
, h
= state
->shared
->params
.h
, wh
= w
* h
;
999 game_state
*ret
= dup_game(state
);
1000 int nchars
, x
, y
, flag
;
1005 for (i
= 0; i
< wh
&& move
[i
]; ++i
)
1007 (move
[i
] & BORDER_MASK
) | DISABLED(~move
[i
] & BORDER_MASK
);
1008 if (i
< wh
|| move
[i
]) return NULL
; /* leaks `ret', then we die */
1009 ret
->cheated
= ret
->completed
= TRUE
;
1013 while (sscanf(move
, "F%d,%d,%d%n", &x
, &y
, &flag
, &nchars
) == 3 &&
1014 !OUT_OF_BOUNDS(x
, y
, w
, h
)) {
1016 ret
->borders
[y
*w
+ x
] ^= flag
;
1019 if (*move
) return NULL
; /* leaks `ret', then we die */
1021 if (!ret
->completed
)
1022 ret
->completed
= is_solved(&ret
->shared
->params
, ret
->shared
->clues
,
1028 /* --- Drawing routines --------------------------------------------- */
1030 static void game_compute_size(const game_params
*params
, int tilesize
,
1033 *x
= (params
->w
+ 1) * tilesize
;
1034 *y
= (params
->h
+ 1) * tilesize
;
1037 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1038 const game_params
*params
, int tilesize
)
1040 ds
->tilesize
= tilesize
;
1047 COL_CLUE
= COL_GRID
,
1048 COL_LINE_YES
= COL_GRID
,
1056 #define COLOUR(i, r, g, b) \
1057 ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1060 static float *game_colours(frontend
*fe
, int *ncolours
)
1062 float *ret
= snewn(3 * NCOLOURS
, float);
1064 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, -1, COL_FLASH
);
1066 COLOUR(COL_GRID
, 0.0F
, 0.0F
, 0.0F
); /* black */
1067 COLOUR(COL_ERROR
, 1.0F
, 0.0F
, 0.0F
); /* red */
1069 COLOUR(COL_LINE_MAYBE
, /* yellow */
1070 ret
[COL_BACKGROUND
*3 + 0] * DARKER
,
1071 ret
[COL_BACKGROUND
*3 + 1] * DARKER
,
1075 ret
[COL_BACKGROUND
*3 + 0] * DARKER
,
1076 ret
[COL_BACKGROUND
*3 + 1] * DARKER
,
1077 ret
[COL_BACKGROUND
*3 + 2] * DARKER
);
1079 *ncolours
= NCOLOURS
;
1084 #define BORDER_ERROR(x) ((x) << 8)
1085 #define F_ERROR_U BORDER_ERROR(BORDER_U) /* BIT( 8) */
1086 #define F_ERROR_R BORDER_ERROR(BORDER_R) /* BIT( 9) */
1087 #define F_ERROR_D BORDER_ERROR(BORDER_D) /* BIT(10) */
1088 #define F_ERROR_L BORDER_ERROR(BORDER_L) /* BIT(11) */
1089 #define F_ERROR_CLUE BIT(12)
1090 #define F_FLASH BIT(13)
1091 #define F_CURSOR BIT(14)
1093 static game_drawstate
*game_new_drawstate(drawing
*dr
, const game_state
*state
)
1095 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1103 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1109 #define COLOUR(border) \
1110 (flags & BORDER_ERROR((border)) ? COL_ERROR : \
1111 flags & (border) ? COL_LINE_YES : \
1112 flags & DISABLED((border)) ? COL_LINE_NO : \
1115 static void draw_tile(drawing
*dr
, game_drawstate
*ds
, int r
, int c
,
1116 dsflags flags
, int clue
)
1118 int x
= MARGIN
+ TILESIZE
* c
, y
= MARGIN
+ TILESIZE
* r
;
1120 clip(dr
, x
, y
, TILESIZE
+ WIDTH
, TILESIZE
+ WIDTH
); /* { */
1122 draw_rect(dr
, x
+ WIDTH
, y
+ WIDTH
, TILESIZE
- WIDTH
, TILESIZE
- WIDTH
,
1123 (flags
& F_FLASH
? COL_FLASH
: COL_BACKGROUND
));
1125 if (flags
& F_CURSOR
)
1126 draw_rect_corners(dr
, x
+ CENTER
, y
+ CENTER
, TILESIZE
/ 3, COL_GRID
);
1128 if (clue
!= EMPTY
) {
1130 buf
[0] = '0' + clue
;
1132 draw_text(dr
, x
+ CENTER
, y
+ CENTER
, FONT_VARIABLE
,
1133 TILESIZE
/ 2, ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1134 (flags
& F_ERROR_CLUE
? COL_ERROR
: COL_CLUE
), buf
);
1140 draw_rect(dr
, x
+ w
, y
, ts
- w
, w
, COLOUR(BORDER_U
));
1141 draw_rect(dr
, x
+ ts
, y
+ w
, w
, ts
- w
, COLOUR(BORDER_R
));
1142 draw_rect(dr
, x
+ w
, y
+ ts
, ts
- w
, w
, COLOUR(BORDER_D
));
1143 draw_rect(dr
, x
, y
+ w
, w
, ts
- w
, COLOUR(BORDER_L
));
1148 draw_update(dr
, x
, y
, TILESIZE
+ WIDTH
, TILESIZE
+ WIDTH
);
1151 #define FLASH_TIME 0.7F
1153 static void game_redraw(drawing
*dr
, game_drawstate
*ds
,
1154 const game_state
*oldstate
, const game_state
*state
,
1155 int dir
, const game_ui
*ui
,
1156 float animtime
, float flashtime
)
1158 int w
= state
->shared
->params
.w
, h
= state
->shared
->params
.h
, wh
= w
*h
;
1159 int r
, c
, i
, flash
= ((int) (flashtime
* 5 / FLASH_TIME
)) % 2;
1160 int *black_border_dsf
= snew_dsf(wh
), *yellow_border_dsf
= snew_dsf(wh
);
1161 int k
= state
->shared
->params
.k
;
1165 int bgw
= (w
+1) * ds
->tilesize
, bgh
= (h
+1) * ds
->tilesize
;
1166 draw_rect(dr
, 0, 0, bgw
, bgh
, COL_BACKGROUND
);
1168 for (r
= 0; r
<= h
; ++r
)
1169 for (c
= 0; c
<= w
; ++c
)
1170 draw_rect(dr
, MARGIN
+ TILESIZE
* c
, MARGIN
+ TILESIZE
* r
,
1171 WIDTH
, WIDTH
, COL_GRID
);
1172 draw_update(dr
, 0, 0, bgw
, bgh
);
1174 snewa(ds
->grid
, wh
);
1175 setmem(ds
->grid
, ~0, wh
);
1177 sprintf(buf
, "Region size: %d", state
->shared
->params
.k
);
1178 status_bar(dr
, buf
);
1181 for (i
= 0; i
< wh
; ++i
) {
1182 if (black_border_dsf
[i
] == UNVISITED
)
1183 dfs_dsf(i
, w
, state
->borders
, black_border_dsf
, TRUE
);
1184 if (yellow_border_dsf
[i
] == UNVISITED
)
1185 dfs_dsf(i
, w
, state
->borders
, yellow_border_dsf
, FALSE
);
1188 for (r
= 0; r
< h
; ++r
)
1189 for (c
= 0; c
< w
; ++c
) {
1190 int i
= r
* w
+ c
, clue
= state
->shared
->clues
[i
], flags
, dir
;
1191 int on
= bitcount
[state
->borders
[i
] & BORDER_MASK
];
1192 int off
= bitcount
[(state
->borders
[i
] >> 4) & BORDER_MASK
];
1194 flags
= state
->borders
[i
];
1196 if (flash
) flags
|= F_FLASH
;
1198 if (clue
!= EMPTY
&& (on
> clue
|| clue
> 4 - off
))
1199 flags
|= F_ERROR_CLUE
;
1201 if (ui
->show
&& ui
->x
== c
&& ui
->y
== r
)
1205 for (dir
= 0; dir
< 4; ++dir
) {
1206 int rr
= r
+ dy
[dir
], cc
= c
+ dx
[dir
], ii
= rr
* w
+ cc
;
1208 if (OUT_OF_BOUNDS(cc
, rr
, w
, h
)) continue;
1210 /* we draw each border twice, except the outermost
1211 * big border, so we have to check for errors on
1212 * both sides of each border.*/
1213 if (/* region too large */
1214 ((dsf_size(yellow_border_dsf
, i
) > k
||
1215 dsf_size(yellow_border_dsf
, ii
) > k
) &&
1216 (dsf_canonify(yellow_border_dsf
, i
) !=
1217 dsf_canonify(yellow_border_dsf
, ii
)))
1220 /* region too small */
1221 ((dsf_size(black_border_dsf
, i
) < k
||
1222 dsf_size(black_border_dsf
, ii
) < k
) &&
1223 dsf_canonify(black_border_dsf
, i
) !=
1224 dsf_canonify(black_border_dsf
, ii
))
1227 /* dangling borders within a single region */
1228 ((state
->borders
[i
] & BORDER(dir
)) &&
1229 /* we know it's a single region because there's a
1230 * path crossing no border from i to ii... */
1231 (dsf_canonify(yellow_border_dsf
, i
) ==
1232 dsf_canonify(yellow_border_dsf
, ii
) ||
1233 /* or because any such border would be an error */
1234 (dsf_size(black_border_dsf
, i
) <= k
&&
1235 dsf_canonify(black_border_dsf
, i
) ==
1236 dsf_canonify(black_border_dsf
, ii
)))))
1238 flags
|= BORDER_ERROR(BORDER(dir
));
1241 if (flags
== ds
->grid
[i
]) continue;
1242 ds
->grid
[i
] = flags
;
1243 draw_tile(dr
, ds
, r
, c
, ds
->grid
[i
], clue
);
1246 sfree(black_border_dsf
);
1247 sfree(yellow_border_dsf
);
1250 static float game_anim_length(const game_state
*oldstate
,
1251 const game_state
*newstate
,
1252 int dir
, game_ui
*ui
)
1257 static float game_flash_length(const game_state
*oldstate
,
1258 const game_state
*newstate
,
1259 int dir
, game_ui
*ui
)
1261 if (newstate
->completed
&& !newstate
->cheated
&& !oldstate
->completed
)
1266 static int game_status(const game_state
*state
)
1268 return state
->completed
? +1 : 0;
1271 static int game_timing_state(const game_state
*state
, game_ui
*ui
)
1273 assert (!"this shouldn't get called");
1274 return 0; /* placate optimiser */
1277 static void game_print_size(const game_params
*params
, float *x
, float *y
)
1281 game_compute_size(params
, 700, &pw
, &ph
); /* 7mm, like loopy */
1287 static void print_line(drawing
*dr
, int x1
, int y1
, int x2
, int y2
,
1288 int colour
, int full
)
1291 int i
, subdivisions
= 8;
1292 for (i
= 1; i
< subdivisions
; ++i
) {
1293 int x
= (x1
* (subdivisions
- i
) + x2
* i
) / subdivisions
;
1294 int y
= (y1
* (subdivisions
- i
) + y2
* i
) / subdivisions
;
1295 draw_circle(dr
, x
, y
, 3, colour
, colour
);
1297 } else draw_line(dr
, x1
, y1
, x2
, y2
, colour
);
1300 static void game_print(drawing
*dr
, const game_state
*state
, int tilesize
)
1302 int w
= state
->shared
->params
.w
, h
= state
->shared
->params
.h
;
1303 int ink
= print_mono_colour(dr
, 0);
1304 game_drawstate for_tilesize_macros
, *ds
= &for_tilesize_macros
;
1307 ds
->tilesize
= tilesize
;
1309 for (r
= 0; r
< h
; ++r
)
1310 for (c
= 0; c
< w
; ++c
) {
1311 int x
= MARGIN
+ TILESIZE
* c
, y
= MARGIN
+ TILESIZE
* r
;
1312 int i
= r
* w
+ c
, clue
= state
->shared
->clues
[i
];
1314 if (clue
!= EMPTY
) {
1316 buf
[0] = '0' + clue
;
1318 draw_text(dr
, x
+ CENTER
, y
+ CENTER
, FONT_VARIABLE
,
1319 TILESIZE
/ 2, ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1324 #define FULL(DIR) (state->borders[i] & (BORDER_ ## DIR))
1325 print_line(dr
, x
, y
, x
+ ts
, y
, ink
, FULL(U
));
1326 print_line(dr
, x
+ ts
, y
, x
+ ts
, y
+ ts
, ink
, FULL(R
));
1327 print_line(dr
, x
, y
+ ts
, x
+ ts
, y
+ ts
, ink
, FULL(D
));
1328 print_line(dr
, x
, y
, x
, y
+ ts
, ink
, FULL(L
));
1333 for (r
= 1; r
< h
; ++r
)
1334 for (c
= 1; c
< w
; ++c
) {
1335 int j
= r
* w
+ c
, i
= j
- 1 - w
;
1336 int x
= MARGIN
+ TILESIZE
* c
, y
= MARGIN
+ TILESIZE
* r
;
1337 if (state
->borders
[i
] & (BORDER_D
|BORDER_R
)) continue;
1338 if (state
->borders
[j
] & (BORDER_U
|BORDER_L
)) continue;
1339 draw_circle(dr
, x
, y
, 3, ink
, ink
);
1344 #define thegame palisade
1347 const struct game thegame
= {
1348 "Palisade", "games.palisade", "palisade",
1350 game_fetch_preset
, NULL
,
1355 TRUE
, game_configure
, custom_params
,
1363 TRUE
, game_can_format_as_text_now
, game_text_format
,
1371 48, game_compute_size
, game_set_size
,
1374 game_free_drawstate
,
1379 TRUE
, FALSE
, game_print_size
, game_print
,
1380 TRUE
, /* wants_statusbar */
1381 FALSE
, game_timing_state
,