2 * pearl.c: Nikoli's `Masyu' puzzle.
8 * - The current keyboard cursor mechanism works well on ordinary PC
9 * keyboards, but for platforms with only arrow keys and a select
10 * button or two, we may at some point need a simpler one which can
11 * handle 'x' markings without needing shift keys. For instance, a
12 * cursor with twice the grid resolution, so that it can range
13 * across face centres, edge centres and vertices; 'clicks' on face
14 * centres begin a drag as currently, clicks on edges toggle
15 * markings, and clicks on vertices are ignored (but it would be
16 * too confusing not to let the cursor rest on them). But I'm
17 * pretty sure that would be less pleasant to play on a full
18 * keyboard, so probably a #ifdef would be the thing.
20 * - Generation is still pretty slow, due to difficulty coming up in
21 * the first place with a loop that makes a soluble puzzle even
22 * with all possible clues filled in.
23 * + A possible alternative strategy to further tuning of the
24 * existing loop generator would be to throw the entire
25 * mechanism out and instead write a different generator from
26 * scratch which evolves the solution along with the puzzle:
27 * place a few clues, nail down a bit of the loop, place another
28 * clue, nail down some more, etc. However, I don't have a
29 * detailed plan for any such mechanism, so it may be a pipe
44 #define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0)
55 #define DX(d) ( ((d)==R) - ((d)==L) )
56 #define DY(d) ( ((d)==D) - ((d)==U) )
58 #define F(d) (((d << 2) | (d >> 2)) & 0xF)
59 #define C(d) (((d << 3) | (d >> 1)) & 0xF)
60 #define A(d) (((d << 1) | (d >> 3)) & 0xF)
89 #define bBLANK (1 << BLANK)
92 COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT,
93 COL_CURSOR_BACKGROUND = COL_LOWLIGHT,
95 COL_ERROR, COL_GRID, COL_FLASH,
96 COL_DRAGON, COL_DRAGOFF,
100 /* Macro ickery copied from slant.c */
101 #define DIFFLIST(A) \
104 #define ENUM(upper,title,lower) DIFF_ ## upper,
105 #define TITLE(upper,title,lower) #title,
106 #define ENCODE(upper,title,lower) #lower
107 #define CONFIG(upper,title,lower) ":" #title
108 enum { DIFFLIST(ENUM) DIFFCOUNT };
109 static char const *const pearl_diffnames[] = { DIFFLIST(TITLE) "(count)" };
110 static char const pearl_diffchars[] = DIFFLIST(ENCODE);
111 #define DIFFCONFIG DIFFLIST(CONFIG)
116 int nosolve; /* XXX remove me! */
119 struct shared_state {
121 char *clues; /* size w*h */
125 #define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->shared->w && \
126 (gy) >= 0 && (gy) < (state)->shared->h)
128 struct shared_state *shared;
129 char *lines; /* size w*h: lines placed */
130 char *errors; /* size w*h: errors detected */
131 char *marks; /* size w*h: 'no line here' marks placed. */
132 int completed, used_solve;
135 #define DEFAULT_PRESET 3
137 static const struct game_params pearl_presets[] = {
143 {10, 10, DIFF_TRICKY},
145 {12, 8, DIFF_TRICKY},
148 static game_params *default_params(void)
150 game_params *ret = snew(game_params);
152 *ret = pearl_presets[DEFAULT_PRESET];
153 ret->nosolve = FALSE;
158 static int game_fetch_preset(int i, char **name, game_params **params)
163 if (i < 0 || i >= lenof(pearl_presets)) return FALSE;
165 ret = default_params();
166 *ret = pearl_presets[i]; /* struct copy */
169 sprintf(buf, "%dx%d %s",
170 pearl_presets[i].w, pearl_presets[i].h,
171 pearl_diffnames[pearl_presets[i].difficulty]);
177 static void free_params(game_params *params)
182 static game_params *dup_params(const game_params *params)
184 game_params *ret = snew(game_params);
185 *ret = *params; /* structure copy */
189 static void decode_params(game_params *ret, char const *string)
191 ret->w = ret->h = atoi(string);
192 while (*string && isdigit((unsigned char) *string)) ++string;
193 if (*string == 'x') {
195 ret->h = atoi(string);
196 while (*string && isdigit((unsigned char)*string)) string++;
199 ret->difficulty = DIFF_EASY;
200 if (*string == 'd') {
203 for (i = 0; i < DIFFCOUNT; i++)
204 if (*string == pearl_diffchars[i])
206 if (*string) string++;
209 ret->nosolve = FALSE;
210 if (*string == 'n') {
216 static char *encode_params(const game_params *params, int full)
219 sprintf(buf, "%dx%d", params->w, params->h);
221 sprintf(buf + strlen(buf), "d%c%s",
222 pearl_diffchars[params->difficulty],
223 params->nosolve ? "n" : "");
227 static config_item *game_configure(const game_params *params)
232 ret = snewn(5, config_item);
234 ret[0].name = "Width";
235 ret[0].type = C_STRING;
236 sprintf(buf, "%d", params->w);
237 ret[0].sval = dupstr(buf);
240 ret[1].name = "Height";
241 ret[1].type = C_STRING;
242 sprintf(buf, "%d", params->h);
243 ret[1].sval = dupstr(buf);
246 ret[2].name = "Difficulty";
247 ret[2].type = C_CHOICES;
248 ret[2].sval = DIFFCONFIG;
249 ret[2].ival = params->difficulty;
251 ret[3].name = "Allow unsoluble";
252 ret[3].type = C_BOOLEAN;
254 ret[3].ival = params->nosolve;
264 static game_params *custom_params(const config_item *cfg)
266 game_params *ret = snew(game_params);
268 ret->w = atoi(cfg[0].sval);
269 ret->h = atoi(cfg[1].sval);
270 ret->difficulty = cfg[2].ival;
271 ret->nosolve = cfg[3].ival;
276 static char *validate_params(const game_params *params, int full)
278 if (params->w < 5) return "Width must be at least five";
279 if (params->h < 5) return "Height must be at least five";
280 if (params->difficulty < 0 || params->difficulty >= DIFFCOUNT)
281 return "Unknown difficulty level";
282 if (params->difficulty >= DIFF_TRICKY && params->w + params->h < 11)
283 return "Width or height must be at least six for Tricky";
288 /* ----------------------------------------------------------------------
292 int pearl_solve(int w, int h, char *clues, char *result,
293 int difficulty, int partial)
295 int W = 2*w+1, H = 2*h+1;
302 * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature
303 * of the square (x,y), as a logical OR of bitfields.
305 * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates
306 * whether the horizontal edge between (x,y) and (x+1,y) is
307 * connected (1), disconnected (2) or unknown (3).
309 * workspace[(2*y+1)*W+(2*x)], indicates the same about the
310 * vertical edge between (x,y) and (x,y+1).
312 * Initially, every square is considered capable of being in
313 * any of the seven possible states (two straights, four
314 * corners and empty), except those corresponding to clue
315 * squares which are more restricted.
317 * Initially, all edges are unknown, except the ones around the
318 * grid border which are known to be disconnected.
320 workspace = snewn(W*H, short);
321 for (x = 0; x < W*H; x++)
324 for (y = 0; y < h; y++)
325 for (x = 0; x < w; x++)
326 switch (clues[y*w+x]) {
328 workspace[(2*y+1)*W+(2*x+1)] = bLU|bLD|bRU|bRD;
331 workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD;
334 workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD|bLU|bLD|bRU|bRD|bBLANK;
337 /* Horizontal edges */
338 for (y = 0; y <= h; y++)
339 for (x = 0; x < w; x++)
340 workspace[(2*y)*W+(2*x+1)] = (y==0 || y==h ? 2 : 3);
342 for (y = 0; y < h; y++)
343 for (x = 0; x <= w; x++)
344 workspace[(2*y+1)*W+(2*x)] = (x==0 || x==w ? 2 : 3);
347 * We maintain a dsf of connected squares, together with a
348 * count of the size of each equivalence class.
350 dsf = snewn(w*h, int);
351 dsfsize = snewn(w*h, int);
354 * Now repeatedly try to find something we can do.
357 int done_something = FALSE;
359 #ifdef SOLVER_DIAGNOSTICS
360 for (y = 0; y < H; y++) {
361 for (x = 0; x < W; x++)
362 printf("%*x", (x&1) ? 5 : 2, workspace[y*W+x]);
368 * Go through the square state words, and discard any
369 * square state which is inconsistent with known facts
370 * about the edges around the square.
372 for (y = 0; y < h; y++)
373 for (x = 0; x < w; x++) {
374 for (b = 0; b < 0xD; b++)
375 if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
377 * If any edge of this square is known to
378 * be connected when state b would require
379 * it disconnected, or vice versa, discard
382 for (d = 1; d <= 8; d += d) {
383 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
384 if (workspace[ey*W+ex] ==
386 workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<b);
387 #ifdef SOLVER_DIAGNOSTICS
388 printf("edge (%d,%d)-(%d,%d) rules out state"
389 " %d for square (%d,%d)\n",
390 ex/2, ey/2, (ex+1)/2, (ey+1)/2,
393 done_something = TRUE;
400 * Consistency check: each square must have at
401 * least one state left!
403 if (!workspace[(2*y+1)*W+(2*x+1)]) {
404 #ifdef SOLVER_DIAGNOSTICS
405 printf("edge check at (%d,%d): inconsistency\n", x, y);
413 * Now go through the states array again, and nail down any
414 * unknown edge if one of its neighbouring squares makes it
417 for (y = 0; y < h; y++)
418 for (x = 0; x < w; x++) {
419 int edgeor = 0, edgeand = 15;
421 for (b = 0; b < 0xD; b++)
422 if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
428 * Now any bit clear in edgeor marks a disconnected
429 * edge, and any bit set in edgeand marks a
433 /* First check consistency: neither bit is both! */
434 if (edgeand & ~edgeor) {
435 #ifdef SOLVER_DIAGNOSTICS
436 printf("square check at (%d,%d): inconsistency\n", x, y);
442 for (d = 1; d <= 8; d += d) {
443 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
445 if (!(edgeor & d) && workspace[ey*W+ex] == 3) {
446 workspace[ey*W+ex] = 2;
447 done_something = TRUE;
448 #ifdef SOLVER_DIAGNOSTICS
449 printf("possible states of square (%d,%d) force edge"
450 " (%d,%d)-(%d,%d) to be disconnected\n",
451 x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
453 } else if ((edgeand & d) && workspace[ey*W+ex] == 3) {
454 workspace[ey*W+ex] = 1;
455 done_something = TRUE;
456 #ifdef SOLVER_DIAGNOSTICS
457 printf("possible states of square (%d,%d) force edge"
458 " (%d,%d)-(%d,%d) to be connected\n",
459 x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
469 * Now for longer-range clue-based deductions (using the
470 * rules that a corner clue must connect to two straight
471 * squares, and a straight clue must connect to at least
472 * one corner square).
474 for (y = 0; y < h; y++)
475 for (x = 0; x < w; x++)
476 switch (clues[y*w+x]) {
478 for (d = 1; d <= 8; d += d) {
479 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
480 int fx = ex + DX(d), fy = ey + DY(d);
483 if (workspace[ey*W+ex] == 1) {
485 * If a corner clue is connected on any
486 * edge, then we can immediately nail
487 * down the square beyond that edge as
488 * being a straight in the appropriate
491 if (workspace[fy*W+fx] != (1<<type)) {
492 workspace[fy*W+fx] = (1<<type);
493 done_something = TRUE;
494 #ifdef SOLVER_DIAGNOSTICS
495 printf("corner clue at (%d,%d) forces square "
496 "(%d,%d) into state %d\n", x, y,
501 } else if (workspace[ey*W+ex] == 3) {
503 * Conversely, if a corner clue is
504 * separated by an unknown edge from a
505 * square which _cannot_ be a straight
506 * in the appropriate direction, we can
507 * mark that edge as disconnected.
509 if (!(workspace[fy*W+fx] & (1<<type))) {
510 workspace[ey*W+ex] = 2;
511 done_something = TRUE;
512 #ifdef SOLVER_DIAGNOSTICS
513 printf("corner clue at (%d,%d), plus square "
514 "(%d,%d) not being state %d, "
515 "disconnects edge (%d,%d)-(%d,%d)\n",
516 x, y, fx/2, fy/2, type,
517 ex/2, ey/2, (ex+1)/2, (ey+1)/2);
527 * If a straight clue is between two squares
528 * neither of which is capable of being a
529 * corner connected to it, then the straight
530 * clue cannot point in that direction.
532 for (d = 1; d <= 2; d += d) {
533 int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
534 int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
537 if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type)))
540 if (!(workspace[fy*W+fx] & ((1<<(F(d)|A(d))) |
541 (1<<(F(d)|C(d))))) &&
542 !(workspace[gy*W+gx] & ((1<<( d |A(d))) |
544 workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<type);
545 done_something = TRUE;
546 #ifdef SOLVER_DIAGNOSTICS
547 printf("straight clue at (%d,%d) cannot corner at "
548 "(%d,%d) or (%d,%d) so is not state %d\n",
549 x, y, fx/2, fy/2, gx/2, gy/2, type);
556 * If a straight clue with known direction is
557 * connected on one side to a known straight,
558 * then on the other side it must be a corner.
560 for (d = 1; d <= 8; d += d) {
561 int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
562 int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
565 if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type))
568 if (!(workspace[fy*W+fx] &~ (bLR|bUD)) &&
569 (workspace[gy*W+gx] &~ (bLU|bLD|bRU|bRD))) {
570 workspace[gy*W+gx] &= (bLU|bLD|bRU|bRD);
571 done_something = TRUE;
572 #ifdef SOLVER_DIAGNOSTICS
573 printf("straight clue at (%d,%d) connecting to "
574 "straight at (%d,%d) makes (%d,%d) a "
575 "corner\n", x, y, fx/2, fy/2, gx/2, gy/2);
587 * Now detect shortcut loops.
591 int nonblanks, loopclass;
594 for (x = 0; x < w*h; x++)
598 * First go through the edge entries and update the dsf
599 * of which squares are connected to which others. We
600 * also track the number of squares in each equivalence
601 * class, and count the overall number of
602 * known-non-blank squares.
604 * In the process of doing this, we must notice if a
605 * loop has already been formed. If it has, we blank
606 * out any square which isn't part of that loop
607 * (failing a consistency check if any such square does
608 * not have BLANK as one of its remaining options) and
609 * exit the deduction loop with success.
613 for (y = 1; y < H-1; y++)
614 for (x = 1; x < W-1; x++)
617 * (x,y) are the workspace coordinates of
618 * an edge field. Compute the normal-space
619 * coordinates of the squares it connects.
621 int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
622 int bx = x/2, by = y/2, bc = by*w+bx;
625 * If the edge is connected, do the dsf
628 if (workspace[y*W+x] == 1) {
631 ae = dsf_canonify(dsf, ac);
632 be = dsf_canonify(dsf, bc);
638 if (loopclass != -1) {
640 * In fact, we have two
641 * separate loops, which is
644 #ifdef SOLVER_DIAGNOSTICS
645 printf("two loops found in grid!\n");
653 * Merge the two equivalence
656 int size = dsfsize[ae] + dsfsize[be];
657 dsf_merge(dsf, ac, bc);
658 ae = dsf_canonify(dsf, ac);
662 } else if ((y & x) & 1) {
664 * (x,y) are the workspace coordinates of a
665 * square field. If the square is
666 * definitely not blank, count it.
668 if (!(workspace[y*W+x] & bBLANK))
673 * If we discovered an existing loop above, we must now
674 * blank every square not part of it, and exit the main
677 if (loopclass != -1) {
678 #ifdef SOLVER_DIAGNOSTICS
679 printf("loop found in grid!\n");
681 for (y = 0; y < h; y++)
682 for (x = 0; x < w; x++)
683 if (dsf_canonify(dsf, y*w+x) != loopclass) {
684 if (workspace[(y*2+1)*W+(x*2+1)] & bBLANK) {
685 workspace[(y*2+1)*W+(x*2+1)] = bBLANK;
688 * This square is not part of the
689 * loop, but is known non-blank. We
692 #ifdef SOLVER_DIAGNOSTICS
693 printf("non-blank square (%d,%d) found outside"
707 /* Further deductions are considered 'tricky'. */
708 if (difficulty == DIFF_EASY) goto done_deductions;
711 * Now go through the workspace again and mark any edge
712 * which would cause a shortcut loop (i.e. would
713 * connect together two squares in the same equivalence
714 * class, and that equivalence class does not contain
715 * _all_ the known-non-blank squares currently in the
716 * grid) as disconnected. Also, mark any _square state_
717 * which would cause a shortcut loop as disconnected.
719 for (y = 1; y < H-1; y++)
720 for (x = 1; x < W-1; x++)
723 * (x,y) are the workspace coordinates of
724 * an edge field. Compute the normal-space
725 * coordinates of the squares it connects.
727 int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
728 int bx = x/2, by = y/2, bc = by*w+bx;
731 * If the edge is currently unknown, and
732 * sits between two squares in the same
733 * equivalence class, and the size of that
734 * class is less than nonblanks, then
735 * connecting this edge would be a shortcut
736 * loop and so we must not do so.
738 if (workspace[y*W+x] == 3) {
741 ae = dsf_canonify(dsf, ac);
742 be = dsf_canonify(dsf, bc);
746 * We have a loop. Is it a shortcut?
748 if (dsfsize[ae] < nonblanks) {
750 * Yes! Mark this edge disconnected.
752 workspace[y*W+x] = 2;
753 done_something = TRUE;
754 #ifdef SOLVER_DIAGNOSTICS
755 printf("edge (%d,%d)-(%d,%d) would create"
756 " a shortcut loop, hence must be"
757 " disconnected\n", x/2, y/2,
763 } else if ((y & x) & 1) {
765 * (x,y) are the workspace coordinates of a
766 * square field. Go through its possible
767 * (non-blank) states and see if any gives
768 * rise to a shortcut loop.
770 * This is slightly fiddly, because we have
771 * to check whether this square is already
772 * part of the same equivalence class as
773 * the things it's joining.
775 int ae = dsf_canonify(dsf, (y/2)*w+(x/2));
777 for (b = 2; b < 0xD; b++)
778 if (workspace[y*W+x] & (1<<b)) {
780 * Find the equivalence classes of
781 * the two squares this one would
782 * connect if it were in this
787 for (d = 1; d <= 8; d += d) if (b & d) {
788 int xx = x/2 + DX(d), yy = y/2 + DY(d);
789 int ee = dsf_canonify(dsf, yy*w+xx);
799 * This square state would form
800 * a loop on equivalence class
801 * e. Measure the size of that
802 * loop, and see if it's a
805 int loopsize = dsfsize[e];
807 loopsize++;/* add the square itself */
808 if (loopsize < nonblanks) {
810 * It is! Mark this square
813 workspace[y*W+x] &= ~(1<<b);
814 done_something = TRUE;
815 #ifdef SOLVER_DIAGNOSTICS
816 printf("square (%d,%d) would create a "
817 "shortcut loop in state %d, "
833 * If we reach here, there is nothing left we can do.
834 * Return 2 for ambiguous puzzle.
843 * If ret = 1 then we've successfully achieved a solution. This
844 * means that we expect every square to be nailed down to
845 * exactly one possibility. If this is the case, or if the caller
846 * asked for a partial solution anyway, transcribe those
847 * possibilities into the result array.
849 if (ret == 1 || partial) {
850 for (y = 0; y < h; y++) {
851 for (x = 0; x < w; x++) {
852 for (b = 0; b < 0xD; b++)
853 if (workspace[(2*y+1)*W+(2*x+1)] == (1<<b)) {
857 if (ret == 1) assert(b < 0xD); /* we should have had a break by now */
869 /* ----------------------------------------------------------------------
874 * We use the loop generator code from loopy, hard-coding to a square
875 * grid of the appropriate size. Knowing the grid layout and the tile
876 * size we can shrink that to our small grid and then make our line
877 * layout from the face colour info.
879 * We provide a bias function to the loop generator which tries to
880 * bias in favour of loops with more scope for Pearl black clues. This
881 * seems to improve the success rate of the puzzle generator, in that
882 * such loops have a better chance of being soluble with all valid
886 struct pearl_loopgen_bias_ctx {
888 * Our bias function counts the number of 'black clue' corners
889 * (i.e. corners adjacent to two straights) in both the
890 * BLACK/nonBLACK and WHITE/nonWHITE boundaries. In order to do
893 * - track the edges that are part of each of those loops
894 * - track the types of vertex in each loop (corner, straight,
896 * - track the current black-clue status of each vertex in each
899 * Each of these chunks of data is updated incrementally from the
900 * previous one, to avoid slowdown due to the bias function
901 * rescanning the whole grid every time it's called.
903 * So we need a lot of separate arrays, plus a tdq for each one,
904 * and we must repeat it all twice for the BLACK and WHITE
907 struct pearl_loopgen_bias_ctx_boundary {
908 int colour; /* FACE_WHITE or FACE_BLACK */
910 char *edges; /* is each edge part of the loop? */
913 char *vertextypes; /* bits 0-3 == outgoing edge bitmap;
914 * bit 4 set iff corner clue.
915 * Hence, 0 means non-vertex;
916 * nonzero but bit 4 zero = straight. */
917 int *neighbour[2]; /* indices of neighbour vertices in loop */
918 tdq *vertextypes_todo;
920 char *blackclues; /* is each vertex a black clue site? */
921 tdq *blackclues_todo;
922 } boundaries[2]; /* boundaries[0]=WHITE, [1]=BLACK */
924 char *faces; /* remember last-seen colour of each face */
931 int pearl_loopgen_bias(void *vctx, char *board, int face)
933 struct pearl_loopgen_bias_ctx *ctx = (struct pearl_loopgen_bias_ctx *)vctx;
935 int oldface, newface;
938 tdq_add(ctx->faces_todo, face);
939 while ((j = tdq_remove(ctx->faces_todo)) >= 0) {
940 oldface = ctx->faces[j];
941 ctx->faces[j] = newface = board[j];
942 for (i = 0; i < 2; i++) {
943 struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i];
947 * If the face has changed either from or to colour c, we need
948 * to reprocess the edges for this boundary.
950 if (oldface == c || newface == c) {
951 grid_face *f = &g->faces[face];
952 for (k = 0; k < f->order; k++)
953 tdq_add(b->edges_todo, f->edges[k] - g->edges);
958 for (i = 0; i < 2; i++) {
959 struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i];
963 * Go through the to-do list of edges. For each edge, decide
964 * anew whether it's part of this boundary or not. Any edge
965 * that changes state has to have both its endpoints put on
966 * the vertextypes_todo list.
968 while ((j = tdq_remove(b->edges_todo)) >= 0) {
969 grid_edge *e = &g->edges[j];
970 int fc1 = e->face1 ? board[e->face1 - g->faces] : FACE_BLACK;
971 int fc2 = e->face2 ? board[e->face2 - g->faces] : FACE_BLACK;
972 int oldedge = b->edges[j];
973 int newedge = (fc1==c) ^ (fc2==c);
974 if (oldedge != newedge) {
975 b->edges[j] = newedge;
976 tdq_add(b->vertextypes_todo, e->dot1 - g->dots);
977 tdq_add(b->vertextypes_todo, e->dot2 - g->dots);
982 * Go through the to-do list of vertices whose types need
983 * refreshing. For each one, decide whether it's a corner, a
984 * straight, or a vertex not in the loop, and in the former
985 * two cases also work out the indices of its neighbour
986 * vertices along the loop. Any vertex that changes state must
987 * be put back on the to-do list for deciding if it's a black
988 * clue site, and so must its two new neighbours _and_ its two
991 while ((j = tdq_remove(b->vertextypes_todo)) >= 0) {
992 grid_dot *d = &g->dots[j];
993 int neighbours[2], type = 0, n = 0;
995 for (k = 0; k < d->order; k++) {
996 grid_edge *e = d->edges[k];
997 grid_dot *d2 = (e->dot1 == d ? e->dot2 : e->dot1);
998 /* dir == 0,1,2,3 for an edge going L,U,R,D */
999 int dir = (d->y == d2->y) + 2*(d->x+d->y > d2->x+d2->y);
1000 int ei = e - g->edges;
1003 neighbours[n] = d2 - g->dots;
1009 * Decide if it's a corner, and set the corner flag if so.
1011 if (type != 0 && type != 0x5 && type != 0xA)
1014 if (type != b->vertextypes[j]) {
1016 * Recompute old neighbours, if any.
1018 if (b->vertextypes[j]) {
1019 tdq_add(b->blackclues_todo, b->neighbour[0][j]);
1020 tdq_add(b->blackclues_todo, b->neighbour[1][j]);
1023 * Recompute this vertex.
1025 tdq_add(b->blackclues_todo, j);
1026 b->vertextypes[j] = type;
1028 * Recompute new neighbours, if any.
1030 if (b->vertextypes[j]) {
1031 b->neighbour[0][j] = neighbours[0];
1032 b->neighbour[1][j] = neighbours[1];
1033 tdq_add(b->blackclues_todo, b->neighbour[0][j]);
1034 tdq_add(b->blackclues_todo, b->neighbour[1][j]);
1040 * Go through the list of vertices which we must check to see
1041 * if they're black clue sites. Each one is a black clue site
1042 * iff it is a corner and its loop neighbours are non-corners.
1043 * Adjust the running total of black clues we've counted.
1045 while ((j = tdq_remove(b->blackclues_todo)) >= 0) {
1046 ctx->score -= b->blackclues[j];
1047 b->blackclues[j] = ((b->vertextypes[j] & 0x10) &&
1048 !((b->vertextypes[b->neighbour[0][j]] |
1049 b->vertextypes[b->neighbour[1][j]])
1051 ctx->score += b->blackclues[j];
1058 void pearl_loopgen(int w, int h, char *lines, random_state *rs)
1060 grid *g = grid_new(GRID_SQUARE, w-1, h-1, NULL);
1061 char *board = snewn(g->num_faces, char);
1062 int i, s = g->tilesize;
1063 struct pearl_loopgen_bias_ctx biasctx;
1065 memset(lines, 0, w*h);
1068 * Initialise the context for the bias function. Initially we fill
1069 * all the to-do lists, so that the first call will scan
1070 * everything; thereafter the lists stay empty so we make
1071 * incremental changes.
1074 biasctx.faces = snewn(g->num_faces, char);
1075 biasctx.faces_todo = tdq_new(g->num_faces);
1076 tdq_fill(biasctx.faces_todo);
1078 memset(biasctx.faces, FACE_GREY, g->num_faces);
1079 for (i = 0; i < 2; i++) {
1080 biasctx.boundaries[i].edges = snewn(g->num_edges, char);
1081 memset(biasctx.boundaries[i].edges, 0, g->num_edges);
1082 biasctx.boundaries[i].edges_todo = tdq_new(g->num_edges);
1083 tdq_fill(biasctx.boundaries[i].edges_todo);
1084 biasctx.boundaries[i].vertextypes = snewn(g->num_dots, char);
1085 memset(biasctx.boundaries[i].vertextypes, 0, g->num_dots);
1086 biasctx.boundaries[i].neighbour[0] = snewn(g->num_dots, int);
1087 biasctx.boundaries[i].neighbour[1] = snewn(g->num_dots, int);
1088 biasctx.boundaries[i].vertextypes_todo = tdq_new(g->num_dots);
1089 tdq_fill(biasctx.boundaries[i].vertextypes_todo);
1090 biasctx.boundaries[i].blackclues = snewn(g->num_dots, char);
1091 memset(biasctx.boundaries[i].blackclues, 0, g->num_dots);
1092 biasctx.boundaries[i].blackclues_todo = tdq_new(g->num_dots);
1093 tdq_fill(biasctx.boundaries[i].blackclues_todo);
1095 biasctx.boundaries[0].colour = FACE_WHITE;
1096 biasctx.boundaries[1].colour = FACE_BLACK;
1097 generate_loop(g, board, rs, pearl_loopgen_bias, &biasctx);
1098 sfree(biasctx.faces);
1099 tdq_free(biasctx.faces_todo);
1100 for (i = 0; i < 2; i++) {
1101 sfree(biasctx.boundaries[i].edges);
1102 tdq_free(biasctx.boundaries[i].edges_todo);
1103 sfree(biasctx.boundaries[i].vertextypes);
1104 sfree(biasctx.boundaries[i].neighbour[0]);
1105 sfree(biasctx.boundaries[i].neighbour[1]);
1106 tdq_free(biasctx.boundaries[i].vertextypes_todo);
1107 sfree(biasctx.boundaries[i].blackclues);
1108 tdq_free(biasctx.boundaries[i].blackclues_todo);
1111 for (i = 0; i < g->num_edges; i++) {
1112 grid_edge *e = g->edges + i;
1113 enum face_colour c1 = FACE_COLOUR(e->face1);
1114 enum face_colour c2 = FACE_COLOUR(e->face2);
1115 assert(c1 != FACE_GREY);
1116 assert(c2 != FACE_GREY);
1118 /* This grid edge is on the loop: lay line along it */
1119 int x1 = e->dot1->x/s, y1 = e->dot1->y/s;
1120 int x2 = e->dot2->x/s, y2 = e->dot2->y/s;
1122 /* (x1,y1) and (x2,y2) are now in our grid coords (0-w,0-h). */
1124 if (y1 > y2) SWAP(y1,y2);
1127 lines[y1*w+x1] |= D;
1128 lines[y2*w+x1] |= U;
1129 } else if (y1 == y2) {
1130 if (x1 > x2) SWAP(x1,x2);
1133 lines[y1*w+x1] |= R;
1134 lines[y1*w+x2] |= L;
1136 assert(!"grid with diagonal coords?!");
1143 #if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
1144 printf("as returned:\n");
1145 for (y = 0; y < h; y++) {
1146 for (x = 0; x < w; x++) {
1147 int type = lines[y*w+x];
1149 if (type & L) *p++ = 'L';
1150 if (type & R) *p++ = 'R';
1151 if (type & U) *p++ = 'U';
1152 if (type & D) *p++ = 'D';
1162 static int new_clues(const game_params *params, random_state *rs,
1163 char *clues, char *grid)
1165 int w = params->w, h = params->h, diff = params->difficulty;
1166 int ngen = 0, x, y, d, ret, i;
1170 * Difficulty exception: 5x5 Tricky is not generable (the
1171 * generator will spin forever trying) and so we fudge it to Easy.
1173 if (w == 5 && h == 5 && diff > DIFF_EASY)
1178 pearl_loopgen(w, h, grid, rs);
1180 #ifdef GENERATION_DIAGNOSTICS
1181 printf("grid array:\n");
1182 for (y = 0; y < h; y++) {
1183 for (x = 0; x < w; x++) {
1184 int type = grid[y*w+x];
1186 if (type & L) *p++ = 'L';
1187 if (type & R) *p++ = 'R';
1188 if (type & U) *p++ = 'U';
1189 if (type & D) *p++ = 'D';
1199 * Set up the maximal clue array.
1201 for (y = 0; y < h; y++)
1202 for (x = 0; x < w; x++) {
1203 int type = grid[y*w+x];
1205 clues[y*w+x] = NOCLUE;
1207 if ((bLR|bUD) & (1 << type)) {
1209 * This is a straight; see if it's a viable
1210 * candidate for a straight clue. It qualifies if
1211 * at least one of the squares it connects to is a
1214 for (d = 1; d <= 8; d += d) if (type & d) {
1215 int xx = x + DX(d), yy = y + DY(d);
1216 assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
1217 if ((bLU|bLD|bRU|bRD) & (1 << grid[yy*w+xx]))
1220 if (d <= 8) /* we found one */
1221 clues[y*w+x] = STRAIGHT;
1222 } else if ((bLU|bLD|bRU|bRD) & (1 << type)) {
1224 * This is a corner; see if it's a viable candidate
1225 * for a corner clue. It qualifies if all the
1226 * squares it connects to are straights.
1228 for (d = 1; d <= 8; d += d) if (type & d) {
1229 int xx = x + DX(d), yy = y + DY(d);
1230 assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
1231 if (!((bLR|bUD) & (1 << grid[yy*w+xx])))
1234 if (d > 8) /* we didn't find a counterexample */
1235 clues[y*w+x] = CORNER;
1239 #ifdef GENERATION_DIAGNOSTICS
1240 printf("clue array:\n");
1241 for (y = 0; y < h; y++) {
1242 for (x = 0; x < w; x++) {
1243 printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
1250 if (!params->nosolve) {
1251 int *cluespace, *straights, *corners;
1252 int nstraights, ncorners, nstraightpos, ncornerpos;
1255 * See if we can solve the puzzle just like this.
1257 ret = pearl_solve(w, h, clues, grid, diff, FALSE);
1258 assert(ret > 0); /* shouldn't be inconsistent! */
1260 continue; /* go round and try again */
1263 * Check this puzzle isn't too easy.
1265 if (diff > DIFF_EASY) {
1266 ret = pearl_solve(w, h, clues, grid, diff-1, FALSE);
1269 continue; /* too easy: try again */
1273 * Now shuffle the grid points and gradually remove the
1274 * clues to find a minimal set which still leaves the
1277 * We preferentially attempt to remove whichever type of
1278 * clue is currently most numerous, to combat a general
1279 * tendency of plain random generation to bias in favour
1280 * of many white clues and few black.
1282 * 'nstraights' and 'ncorners' count the number of clues
1283 * of each type currently remaining in the grid;
1284 * 'nstraightpos' and 'ncornerpos' count the clues of each
1285 * type we have left to try to remove. (Clues which we
1286 * have tried and failed to remove are counted by the
1287 * former but not the latter.)
1289 cluespace = snewn(w*h, int);
1290 straights = cluespace;
1292 for (i = 0; i < w*h; i++)
1293 if (clues[i] == STRAIGHT)
1294 straights[nstraightpos++] = i;
1295 corners = straights + nstraightpos;
1297 for (i = 0; i < w*h; i++)
1298 if (clues[i] == STRAIGHT)
1299 corners[ncornerpos++] = i;
1300 nstraights = nstraightpos;
1301 ncorners = ncornerpos;
1303 shuffle(straights, nstraightpos, sizeof(*straights), rs);
1304 shuffle(corners, ncornerpos, sizeof(*corners), rs);
1305 while (nstraightpos > 0 || ncornerpos > 0) {
1310 * Decide which clue to try to remove next. If both
1311 * types are available, we choose whichever kind is
1312 * currently overrepresented; otherwise we take
1313 * whatever we can get.
1315 if (nstraightpos > 0 && ncornerpos > 0) {
1316 if (nstraights >= ncorners)
1317 cluepos = straights[--nstraightpos];
1319 cluepos = straights[--ncornerpos];
1321 if (nstraightpos > 0)
1322 cluepos = straights[--nstraightpos];
1324 cluepos = straights[--ncornerpos];
1330 clue = clues[y*w+x];
1331 clues[y*w+x] = 0; /* try removing this clue */
1333 ret = pearl_solve(w, h, clues, grid, diff, FALSE);
1336 clues[y*w+x] = clue; /* oops, put it back again */
1341 #ifdef FINISHED_PUZZLE
1342 printf("clue array:\n");
1343 for (y = 0; y < h; y++) {
1344 for (x = 0; x < w; x++) {
1345 printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
1355 debug(("%d %dx%d loops before finished puzzle.\n", ngen, w, h));
1360 static char *new_game_desc(const game_params *params, random_state *rs,
1361 char **aux, int interactive)
1365 int w = params->w, h = params->h, i, j;
1367 grid = snewn(w*h, char);
1368 clues = snewn(w*h, char);
1370 new_clues(params, rs, clues, grid);
1372 desc = snewn(w * h + 1, char);
1373 for (i = j = 0; i < w*h; i++) {
1374 if (clues[i] == NOCLUE && j > 0 &&
1375 desc[j-1] >= 'a' && desc[j-1] < 'z')
1377 else if (clues[i] == NOCLUE)
1379 else if (clues[i] == CORNER)
1381 else if (clues[i] == STRAIGHT)
1386 *aux = snewn(w*h+1, char);
1387 for (i = 0; i < w*h; i++)
1388 (*aux)[i] = (grid[i] < 10) ? (grid[i] + '0') : (grid[i] + 'A' - 10);
1397 static char *validate_desc(const game_params *params, const char *desc)
1400 const int totalsize = params->w * params->h;
1403 for (i = 0; desc[i]; i++) {
1404 if (desc[i] >= 'a' && desc[i] <= 'z')
1405 sizesofar += desc[i] - 'a' + 1;
1406 else if (desc[i] == 'B' || desc[i] == 'W')
1409 return "unrecognised character in string";
1412 if (sizesofar > totalsize)
1413 return "string too long";
1414 else if (sizesofar < totalsize)
1415 return "string too short";
1420 static game_state *new_game(midend *me, const game_params *params,
1423 game_state *state = snew(game_state);
1424 int i, j, sz = params->w*params->h;
1426 state->completed = state->used_solve = FALSE;
1427 state->shared = snew(struct shared_state);
1429 state->shared->w = params->w;
1430 state->shared->h = params->h;
1431 state->shared->sz = sz;
1432 state->shared->refcnt = 1;
1433 state->shared->clues = snewn(sz, char);
1434 for (i = j = 0; desc[i]; i++) {
1436 if (desc[i] >= 'a' && desc[i] <= 'z') {
1437 int n = desc[i] - 'a' + 1;
1438 assert(j + n <= sz);
1440 state->shared->clues[j++] = NOCLUE;
1441 } else if (desc[i] == 'B') {
1442 state->shared->clues[j++] = CORNER;
1443 } else if (desc[i] == 'W') {
1444 state->shared->clues[j++] = STRAIGHT;
1448 state->lines = snewn(sz, char);
1449 state->errors = snewn(sz, char);
1450 state->marks = snewn(sz, char);
1451 for (i = 0; i < sz; i++)
1452 state->lines[i] = state->errors[i] = state->marks[i] = BLANK;
1457 static game_state *dup_game(const game_state *state)
1459 game_state *ret = snew(game_state);
1460 int sz = state->shared->sz, i;
1462 ret->shared = state->shared;
1463 ret->completed = state->completed;
1464 ret->used_solve = state->used_solve;
1465 ++ret->shared->refcnt;
1467 ret->lines = snewn(sz, char);
1468 ret->errors = snewn(sz, char);
1469 ret->marks = snewn(sz, char);
1470 for (i = 0; i < sz; i++) {
1471 ret->lines[i] = state->lines[i];
1472 ret->errors[i] = state->errors[i];
1473 ret->marks[i] = state->marks[i];
1479 static void free_game(game_state *state)
1482 if (--state->shared->refcnt == 0) {
1483 sfree(state->shared->clues);
1484 sfree(state->shared);
1486 sfree(state->lines);
1487 sfree(state->errors);
1488 sfree(state->marks);
1492 static char nbits[16] = { 0, 1, 1, 2,
1496 #define NBITS(l) ( ((l) < 0 || (l) > 15) ? 4 : nbits[l] )
1498 #define ERROR_CLUE 16
1500 static void dsf_update_completion(game_state *state, int ax, int ay, char dir,
1503 int w = state->shared->w /*, h = state->shared->h */;
1504 int ac = ay*w+ax, bx, by, bc;
1506 if (!(state->lines[ac] & dir)) return; /* no link */
1507 bx = ax + DX(dir); by = ay + DY(dir);
1509 assert(INGRID(state, bx, by)); /* should not have a link off grid */
1512 assert(state->lines[bc] & F(dir)); /* should have reciprocal link */
1513 if (!(state->lines[bc] & F(dir))) return;
1515 dsf_merge(dsf, ac, bc);
1518 static void check_completion(game_state *state, int mark)
1520 int w = state->shared->w, h = state->shared->h, x, y, i, d;
1521 int had_error = FALSE;
1522 int *dsf, *component_state;
1523 int nsilly, nloop, npath, largest_comp, largest_size, total_pathsize;
1524 enum { COMP_NONE, COMP_LOOP, COMP_PATH, COMP_SILLY, COMP_EMPTY };
1527 for (i = 0; i < w*h; i++) {
1528 state->errors[i] = 0;
1532 #define ERROR(x,y,e) do { had_error = TRUE; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0)
1535 * Analyse the solution into loops, paths and stranger things.
1536 * Basic strategy here is all the same as in Loopy - see the big
1537 * comment in loopy.c's check_completion() - and for exactly the
1538 * same reasons, since Loopy and Pearl have basically the same
1539 * form of expected solution.
1541 dsf = snew_dsf(w*h);
1543 /* Build the dsf. */
1544 for (x = 0; x < w; x++) {
1545 for (y = 0; y < h; y++) {
1546 dsf_update_completion(state, x, y, R, dsf);
1547 dsf_update_completion(state, x, y, D, dsf);
1551 /* Initialise a state variable for each connected component. */
1552 component_state = snewn(w*h, int);
1553 for (i = 0; i < w*h; i++) {
1554 if (dsf_canonify(dsf, i) == i)
1555 component_state[i] = COMP_LOOP;
1557 component_state[i] = COMP_NONE;
1561 * Classify components, and mark errors where a square has more
1562 * than two line segments.
1564 for (x = 0; x < w; x++) {
1565 for (y = 0; y < h; y++) {
1566 int type = state->lines[y*w+x];
1567 int degree = NBITS(type);
1568 int comp = dsf_canonify(dsf, y*w+x);
1571 component_state[comp] = COMP_SILLY;
1572 } else if (degree == 0) {
1573 component_state[comp] = COMP_EMPTY;
1574 } else if (degree == 1) {
1575 if (component_state[comp] != COMP_SILLY)
1576 component_state[comp] = COMP_PATH;
1581 /* Count the components, and find the largest sensible one. */
1582 nsilly = nloop = npath = 0;
1584 largest_comp = largest_size = -1;
1585 for (i = 0; i < w*h; i++) {
1586 if (component_state[i] == COMP_SILLY) {
1588 } else if (component_state[i] == COMP_PATH) {
1589 total_pathsize += dsf_size(dsf, i);
1591 } else if (component_state[i] == COMP_LOOP) {
1596 if ((this_size = dsf_size(dsf, i)) > largest_size) {
1598 largest_size = this_size;
1602 if (largest_size < total_pathsize) {
1603 largest_comp = -1; /* means the paths */
1604 largest_size = total_pathsize;
1607 if (nloop > 0 && nloop + npath > 1) {
1609 * If there are at least two sensible components including at
1610 * least one loop, highlight every sensible component that is
1611 * not the largest one.
1613 for (i = 0; i < w*h; i++) {
1614 int comp = dsf_canonify(dsf, i);
1615 if ((component_state[comp] == COMP_PATH &&
1616 -1 != largest_comp) ||
1617 (component_state[comp] == COMP_LOOP &&
1618 comp != largest_comp))
1619 ERROR(i%w, i/w, state->lines[i]);
1623 /* Now we've finished with the dsf and component states. The only
1624 * thing we'll need to remember later on is whether all edges were
1625 * part of a single loop, for which our counter variables
1626 * nsilly,nloop,npath are enough. */
1627 sfree(component_state);
1631 * Check that no clues are contradicted. This code is similar to
1632 * the code that sets up the maximal clue array for any given
1635 for (x = 0; x < w; x++) {
1636 for (y = 0; y < h; y++) {
1637 int type = state->lines[y*w+x];
1638 if (state->shared->clues[y*w+x] == CORNER) {
1639 /* Supposed to be a corner: will find a contradiction if
1640 * it actually contains a straight line, or if it touches any
1642 if ((bLR|bUD) & (1 << type)) {
1643 ERROR(x,y,ERROR_CLUE); /* actually straight */
1645 for (d = 1; d <= 8; d += d) if (type & d) {
1646 int xx = x + DX(d), yy = y + DY(d);
1647 if (!INGRID(state, xx, yy)) {
1648 ERROR(x,y,d); /* leads off grid */
1650 if ((bLU|bLD|bRU|bRD) & (1 << state->lines[yy*w+xx])) {
1651 ERROR(x,y,ERROR_CLUE); /* touches corner */
1655 } else if (state->shared->clues[y*w+x] == STRAIGHT) {
1656 /* Supposed to be straight: will find a contradiction if
1657 * it actually contains a corner, or if it only touches
1658 * straight lines. */
1659 if ((bLU|bLD|bRU|bRD) & (1 << type)) {
1660 ERROR(x,y,ERROR_CLUE); /* actually a corner */
1663 for (d = 1; d <= 8; d += d) if (type & d) {
1664 int xx = x + DX(d), yy = y + DY(d);
1665 if (!INGRID(state, xx, yy)) {
1666 ERROR(x,y,d); /* leads off grid */
1668 if ((bLR|bUD) & (1 << state->lines[yy*w+xx]))
1669 i++; /* a straight */
1672 if (i >= 2 && NBITS(type) >= 2) {
1673 ERROR(x,y,ERROR_CLUE); /* everything touched is straight */
1679 if (nloop == 1 && nsilly == 0 && npath == 0) {
1681 * If there's exactly one loop (so that the puzzle is at least
1682 * potentially complete), we need to ensure it hasn't left any
1683 * clue out completely.
1685 for (x = 0; x < w; x++) {
1686 for (y = 0; y < h; y++) {
1687 if (state->lines[y*w+x] == BLANK) {
1688 if (state->shared->clues[y*w+x] != NOCLUE) {
1689 /* the loop doesn't include this clue square! */
1690 ERROR(x, y, ERROR_CLUE);
1697 * But if not, then we're done!
1700 state->completed = TRUE;
1704 /* completion check:
1706 * - no clues must be contradicted (highlight clue itself in error if so)
1707 * - if there is a closed loop it must include every line segment laid
1708 * - if there's a smaller closed loop then highlight whole loop as error
1709 * - no square must have more than 2 lines radiating from centre point
1710 * (highlight all lines in that square as error if so)
1713 static char *solve_for_diff(game_state *state, char *old_lines, char *new_lines)
1715 int w = state->shared->w, h = state->shared->h, i;
1716 char *move = snewn(w*h*40, char), *p = move;
1719 for (i = 0; i < w*h; i++) {
1720 if (old_lines[i] != new_lines[i]) {
1721 p += sprintf(p, ";R%d,%d,%d", new_lines[i], i%w, i/w);
1725 move = sresize(move, p - move, char);
1730 static char *solve_game(const game_state *state, const game_state *currstate,
1731 const char *aux, char **error)
1733 game_state *solved = dup_game(state);
1734 int i, ret, sz = state->shared->sz;
1738 for (i = 0; i < sz; i++) {
1739 if (aux[i] >= '0' && aux[i] <= '9')
1740 solved->lines[i] = aux[i] - '0';
1741 else if (aux[i] >= 'A' && aux[i] <= 'F')
1742 solved->lines[i] = aux[i] - 'A' + 10;
1744 *error = "invalid char in aux";
1751 /* Try to solve with present (half-solved) state first: if there's no
1752 * solution from there go back to original state. */
1753 ret = pearl_solve(currstate->shared->w, currstate->shared->h,
1754 currstate->shared->clues, solved->lines,
1757 ret = pearl_solve(state->shared->w, state->shared->h,
1758 state->shared->clues, solved->lines,
1764 *error = "Unable to find solution";
1767 move = solve_for_diff(solved, currstate->lines, solved->lines);
1775 static int game_can_format_as_text_now(const game_params *params)
1780 static char *game_text_format(const game_state *state)
1782 int w = state->shared->w, h = state->shared->h, cw = 4, ch = 2;
1783 int gw = cw*(w-1) + 2, gh = ch*(h-1) + 1, len = gw * gh, r, c, j;
1784 char *board = snewn(len + 1, char);
1787 memset(board, ' ', len);
1789 for (r = 0; r < h; ++r) {
1790 for (c = 0; c < w; ++c) {
1791 int i = r*w + c, cell = r*ch*gw + c*cw;
1792 board[cell] = "+BW"[(unsigned char)state->shared->clues[i]];
1793 if (c < w - 1 && (state->lines[i] & R || state->lines[i+1] & L))
1794 memset(board + cell + 1, '-', cw - 1);
1795 if (r < h - 1 && (state->lines[i] & D || state->lines[i+w] & U))
1796 for (j = 1; j < ch; ++j) board[cell + j*gw] = '|';
1797 if (c < w - 1 && (state->marks[i] & R || state->marks[i+1] & L))
1798 board[cell + cw/2] = 'x';
1799 if (r < h - 1 && (state->marks[i] & D || state->marks[i+w] & U))
1800 board[cell + (ch/2 * gw)] = 'x';
1803 for (j = 0; j < (r == h - 1 ? 1 : ch); ++j)
1804 board[r*ch*gw + (gw - 1) + j*gw] = '\n';
1812 int *dragcoords; /* list of (y*w+x) coords in drag so far */
1813 int ndragcoords; /* number of entries in dragcoords.
1814 * 0 = click but no drag yet. -1 = no drag at all */
1815 int clickx, clicky; /* pixel position of initial click */
1817 int curx, cury; /* grid position of keyboard cursor */
1818 int cursor_active; /* TRUE iff cursor is shown */
1821 static game_ui *new_ui(const game_state *state)
1823 game_ui *ui = snew(game_ui);
1824 int sz = state->shared->sz;
1826 ui->ndragcoords = -1;
1827 ui->dragcoords = snewn(sz, int);
1828 ui->cursor_active = FALSE;
1829 ui->curx = ui->cury = 0;
1834 static void free_ui(game_ui *ui)
1836 sfree(ui->dragcoords);
1840 static char *encode_ui(const game_ui *ui)
1845 static void decode_ui(game_ui *ui, const char *encoding)
1849 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1850 const game_state *newstate)
1854 #define PREFERRED_TILE_SIZE 31
1855 #define HALFSZ (ds->halfsz)
1856 #define TILE_SIZE (ds->halfsz*2 + 1)
1858 #define BORDER ((get_gui_style() == GUI_LOOPY) ? (TILE_SIZE/8) : (TILE_SIZE/2))
1860 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1862 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
1863 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1864 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) )
1866 #define DS_ESHIFT 4 /* R/U/L/D shift, for error flags */
1867 #define DS_DSHIFT 8 /* R/U/L/D shift, for drag-in-progress flags */
1868 #define DS_MSHIFT 12 /* shift for no-line mark */
1870 #define DS_ERROR_CLUE (1 << 20)
1871 #define DS_FLASH (1 << 21)
1872 #define DS_CURSOR (1 << 22)
1874 enum { GUI_MASYU, GUI_LOOPY };
1876 static int get_gui_style(void)
1878 static int gui_style = -1;
1880 if (gui_style == -1) {
1881 char *env = getenv("PEARL_GUI_LOOPY");
1882 if (env && (env[0] == 'y' || env[0] == 'Y'))
1883 gui_style = GUI_LOOPY;
1885 gui_style = GUI_MASYU;
1890 struct game_drawstate {
1895 unsigned int *lflags; /* size w*h */
1897 char *draglines; /* size w*h; lines flipped by current drag */
1900 static void update_ui_drag(const game_state *state, game_ui *ui,
1903 int /* sz = state->shared->sz, */ w = state->shared->w;
1907 if (!INGRID(state, gx, gy))
1908 return; /* square is outside grid */
1910 if (ui->ndragcoords < 0)
1911 return; /* drag not in progress anyway */
1915 lastpos = ui->dragcoords[ui->ndragcoords > 0 ? ui->ndragcoords-1 : 0];
1917 return; /* same square as last visited one */
1919 /* Drag confirmed, if it wasn't already. */
1920 if (ui->ndragcoords == 0)
1921 ui->ndragcoords = 1;
1924 * Dragging the mouse into a square that's already been visited by
1925 * the drag path so far has the effect of truncating the path back
1926 * to that square, so a player can back out part of an uncommitted
1927 * drag without having to let go of the mouse.
1929 for (i = 0; i < ui->ndragcoords; i++)
1930 if (pos == ui->dragcoords[i]) {
1931 ui->ndragcoords = i+1;
1936 * Otherwise, dragging the mouse into a square that's a rook-move
1937 * away from the last one on the path extends the path.
1939 oy = ui->dragcoords[ui->ndragcoords-1] / w;
1940 ox = ui->dragcoords[ui->ndragcoords-1] % w;
1941 if (ox == gx || oy == gy) {
1942 int dx = (gx < ox ? -1 : gx > ox ? +1 : 0);
1943 int dy = (gy < oy ? -1 : gy > oy ? +1 : 0);
1944 int dir = (dy>0 ? D : dy<0 ? U : dx>0 ? R : L);
1945 while (ox != gx || oy != gy) {
1947 * If the drag attempts to cross a 'no line here' mark,
1948 * stop there. We physically don't allow the user to drag
1951 if (state->marks[oy*w+ox] & dir)
1955 ui->dragcoords[ui->ndragcoords++] = oy * w + ox;
1960 * Failing that, we do nothing at all: if the user has dragged
1961 * diagonally across the board, they'll just have to return the
1962 * mouse to the last known position and do whatever they meant to
1963 * do again, more slowly and clearly.
1968 * Routine shared between interpret_move and game_redraw to work out
1969 * the intended effect of a drag path on the grid.
1971 * Call it in a loop, like this:
1973 * int clearing = TRUE;
1974 * for (i = 0; i < ui->ndragcoords - 1; i++) {
1975 * int sx, sy, dx, dy, dir, oldstate, newstate;
1976 * interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
1977 * &dir, &oldstate, &newstate);
1979 * [do whatever is needed to handle the fact that the drag
1980 * wants the edge from sx,sy to dx,dy (heading in direction
1981 * 'dir' at the sx,sy end) to be changed from state oldstate
1982 * to state newstate, each of which equals either 0 or dir]
1985 static void interpret_ui_drag(const game_state *state, const game_ui *ui,
1986 int *clearing, int i, int *sx, int *sy,
1987 int *dx, int *dy, int *dir,
1988 int *oldstate, int *newstate)
1990 int w = state->shared->w;
1991 int sp = ui->dragcoords[i], dp = ui->dragcoords[i+1];
1996 *dir = (*dy>*sy ? D : *dy<*sy ? U : *dx>*sx ? R : L);
1997 *oldstate = state->lines[sp] & *dir;
2000 * The edge we've dragged over was previously
2001 * present. Set it to absent, unless we've already
2002 * stopped doing that.
2004 *newstate = *clearing ? 0 : *dir;
2007 * The edge we've dragged over was previously
2008 * absent. Set it to present, and cancel the
2009 * 'clearing' flag so that all subsequent edges in
2010 * the drag are set rather than cleared.
2017 static char *mark_in_direction(const game_state *state, int x, int y, int dir,
2018 int primary, char *buf)
2020 int w = state->shared->w /*, h = state->shared->h, sz = state->shared->sz */;
2021 int x2 = x + DX(dir);
2022 int y2 = y + DY(dir);
2025 char ch = primary ? 'F' : 'M', *other;
2027 if (!INGRID(state, x, y) || !INGRID(state, x2, y2)) return "";
2029 /* disallow laying a mark over a line, or vice versa. */
2030 other = primary ? state->marks : state->lines;
2031 if (other[y*w+x] & dir || other[y2*w+x2] & dir2) return "";
2033 sprintf(buf, "%c%d,%d,%d;%c%d,%d,%d", ch, dir, x, y, ch, dir2, x2, y2);
2037 #define KEY_DIRECTION(btn) (\
2038 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
2039 (btn) == CURSOR_LEFT ? L : R)
2041 static char *interpret_move(const game_state *state, game_ui *ui,
2042 const game_drawstate *ds,
2043 int x, int y, int button)
2045 int w = state->shared->w, h = state->shared->h /*, sz = state->shared->sz */;
2046 int gx = FROMCOORD(x), gy = FROMCOORD(y), i;
2047 int release = FALSE;
2050 int shift = button & MOD_SHFT, control = button & MOD_CTRL;
2051 button &= ~MOD_MASK;
2053 if (IS_MOUSE_DOWN(button)) {
2054 ui->cursor_active = FALSE;
2056 if (!INGRID(state, gx, gy)) {
2057 ui->ndragcoords = -1;
2061 ui->clickx = x; ui->clicky = y;
2062 ui->dragcoords[0] = gy * w + gx;
2063 ui->ndragcoords = 0; /* will be 1 once drag is confirmed */
2068 if (button == LEFT_DRAG && ui->ndragcoords >= 0) {
2069 update_ui_drag(state, ui, gx, gy);
2073 if (IS_MOUSE_RELEASE(button)) release = TRUE;
2075 if (IS_CURSOR_MOVE(button)) {
2076 if (!ui->cursor_active) {
2077 ui->cursor_active = TRUE;
2078 } else if (control | shift) {
2080 if (ui->ndragcoords > 0) return NULL;
2081 ui->ndragcoords = -1;
2082 move = mark_in_direction(state, ui->curx, ui->cury,
2083 KEY_DIRECTION(button), control, tmpbuf);
2084 if (control && !shift && *move)
2085 move_cursor(button, &ui->curx, &ui->cury, w, h, FALSE);
2088 move_cursor(button, &ui->curx, &ui->cury, w, h, FALSE);
2089 if (ui->ndragcoords >= 0)
2090 update_ui_drag(state, ui, ui->curx, ui->cury);
2095 if (IS_CURSOR_SELECT(button)) {
2096 if (!ui->cursor_active) {
2097 ui->cursor_active = TRUE;
2099 } else if (button == CURSOR_SELECT) {
2100 if (ui->ndragcoords == -1) {
2101 ui->ndragcoords = 0;
2102 ui->dragcoords[0] = ui->cury * w + ui->curx;
2103 ui->clickx = CENTERED_COORD(ui->curx);
2104 ui->clicky = CENTERED_COORD(ui->cury);
2106 } else release = TRUE;
2107 } else if (button == CURSOR_SELECT2 && ui->ndragcoords >= 0) {
2108 ui->ndragcoords = -1;
2113 if (button == 27 || button == '\b') {
2114 ui->ndragcoords = -1;
2119 if (ui->ndragcoords > 0) {
2120 /* End of a drag: process the cached line data. */
2121 int buflen = 0, bufsize = 256, tmplen;
2123 const char *sep = "";
2124 int clearing = TRUE;
2126 for (i = 0; i < ui->ndragcoords - 1; i++) {
2127 int sx, sy, dx, dy, dir, oldstate, newstate;
2128 interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
2129 &dir, &oldstate, &newstate);
2131 if (oldstate != newstate) {
2132 if (!buf) buf = snewn(bufsize, char);
2133 tmplen = sprintf(tmpbuf, "%sF%d,%d,%d;F%d,%d,%d", sep,
2134 dir, sx, sy, F(dir), dx, dy);
2135 if (buflen + tmplen >= bufsize) {
2136 bufsize = (buflen + tmplen) * 5 / 4 + 256;
2137 buf = sresize(buf, bufsize, char);
2139 strcpy(buf + buflen, tmpbuf);
2145 ui->ndragcoords = -1;
2147 return buf ? buf : "";
2148 } else if (ui->ndragcoords == 0) {
2149 /* Click (or tiny drag). Work out which edge we were
2153 ui->ndragcoords = -1;
2156 * We process clicks based on the mouse-down location,
2157 * because that's more natural for a user to carefully
2158 * control than the mouse-up.
2165 cx = CENTERED_COORD(gx);
2166 cy = CENTERED_COORD(gy);
2168 if (!INGRID(state, gx, gy)) return "";
2170 if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
2171 /* TODO closer to centre of grid: process as a cell click not an edge click. */
2176 if (abs(x-cx) < abs(y-cy)) {
2177 /* Closest to top/bottom edge. */
2178 direction = (y < cy) ? U : D;
2180 /* Closest to left/right edge. */
2181 direction = (x < cx) ? L : R;
2183 return mark_in_direction(state, gx, gy, direction,
2184 (button == LEFT_RELEASE), tmpbuf);
2189 if (button == 'H' || button == 'h')
2195 static game_state *execute_move(const game_state *state, const char *move)
2197 int w = state->shared->w, h = state->shared->h;
2200 game_state *ret = dup_game(state);
2202 debug(("move: %s\n", move));
2207 ret->used_solve = TRUE;
2209 } else if (c == 'L' || c == 'N' || c == 'R' || c == 'F' || c == 'M') {
2210 /* 'line' or 'noline' or 'replace' or 'flip' or 'mark' */
2212 if (sscanf(move, "%d,%d,%d%n", &l, &x, &y, &n) != 3)
2214 if (!INGRID(state, x, y)) goto badmove;
2215 if (l < 0 || l > 15) goto badmove;
2218 ret->lines[y*w + x] |= (char)l;
2220 ret->lines[y*w + x] &= ~((char)l);
2221 else if (c == 'R') {
2222 ret->lines[y*w + x] = (char)l;
2223 ret->marks[y*w + x] &= ~((char)l); /* erase marks too */
2224 } else if (c == 'F')
2225 ret->lines[y*w + x] ^= (char)l;
2227 ret->marks[y*w + x] ^= (char)l;
2230 * If we ended up trying to lay a line _over_ a mark,
2231 * that's a failed move: interpret_move() should have
2232 * ensured we never received a move string like that in
2235 if ((ret->lines[y*w + x] & (char)l) &&
2236 (ret->marks[y*w + x] & (char)l))
2240 } else if (strcmp(move, "H") == 0) {
2241 pearl_solve(ret->shared->w, ret->shared->h,
2242 ret->shared->clues, ret->lines, DIFFCOUNT, TRUE);
2243 for (n = 0; n < w*h; n++)
2244 ret->marks[n] &= ~ret->lines[n]; /* erase marks too */
2255 check_completion(ret, TRUE);
2264 /* ----------------------------------------------------------------------
2268 #define FLASH_TIME 0.5F
2270 static void game_compute_size(const game_params *params, int tilesize,
2273 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2274 struct { int halfsz; } ads, *ds = &ads;
2275 ads.halfsz = (tilesize-1)/2;
2277 *x = (params->w) * TILE_SIZE + 2 * BORDER;
2278 *y = (params->h) * TILE_SIZE + 2 * BORDER;
2281 static void game_set_size(drawing *dr, game_drawstate *ds,
2282 const game_params *params, int tilesize)
2284 ds->halfsz = (tilesize-1)/2;
2287 static float *game_colours(frontend *fe, int *ncolours)
2289 float *ret = snewn(3 * NCOLOURS, float);
2292 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2294 for (i = 0; i < 3; i++) {
2295 ret[COL_BLACK * 3 + i] = 0.0F;
2296 ret[COL_WHITE * 3 + i] = 1.0F;
2297 ret[COL_GRID * 3 + i] = 0.4F;
2300 ret[COL_ERROR * 3 + 0] = 1.0F;
2301 ret[COL_ERROR * 3 + 1] = 0.0F;
2302 ret[COL_ERROR * 3 + 2] = 0.0F;
2304 ret[COL_DRAGON * 3 + 0] = 0.0F;
2305 ret[COL_DRAGON * 3 + 1] = 0.0F;
2306 ret[COL_DRAGON * 3 + 2] = 1.0F;
2308 ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2309 ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2310 ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2312 ret[COL_FLASH * 3 + 0] = 1.0F;
2313 ret[COL_FLASH * 3 + 1] = 1.0F;
2314 ret[COL_FLASH * 3 + 2] = 1.0F;
2316 *ncolours = NCOLOURS;
2321 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2323 struct game_drawstate *ds = snew(struct game_drawstate);
2327 ds->started = FALSE;
2329 ds->w = state->shared->w;
2330 ds->h = state->shared->h;
2331 ds->sz = state->shared->sz;
2332 ds->lflags = snewn(ds->sz, unsigned int);
2333 for (i = 0; i < ds->sz; i++)
2336 ds->draglines = snewn(ds->sz, char);
2341 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2343 sfree(ds->draglines);
2348 static void draw_lines_specific(drawing *dr, game_drawstate *ds,
2349 int x, int y, unsigned int lflags,
2350 unsigned int shift, int c)
2352 int ox = COORD(x), oy = COORD(y);
2353 int t2 = HALFSZ, t16 = HALFSZ/4;
2354 int cx = ox + t2, cy = oy + t2;
2357 /* Draw each of the four directions, where laid (or error, or drag, etc.) */
2358 for (d = 1; d < 16; d *= 2) {
2359 int xoff = t2 * DX(d), yoff = t2 * DY(d);
2360 int xnudge = abs(t16 * DX(C(d))), ynudge = abs(t16 * DY(C(d)));
2362 if ((lflags >> shift) & d) {
2363 int lx = cx + ((xoff < 0) ? xoff : 0) - xnudge;
2364 int ly = cy + ((yoff < 0) ? yoff : 0) - ynudge;
2366 if (c == COL_DRAGOFF && !(lflags & d))
2368 if (c == COL_DRAGON && (lflags & d))
2371 draw_rect(dr, lx, ly,
2372 abs(xoff)+2*xnudge+1,
2373 abs(yoff)+2*ynudge+1, c);
2375 draw_rect(dr, cx - t16, cy - t16, 2*t16+1, 2*t16+1, c);
2380 static void draw_square(drawing *dr, game_drawstate *ds, const game_ui *ui,
2381 int x, int y, unsigned int lflags, char clue)
2383 int ox = COORD(x), oy = COORD(y);
2384 int t2 = HALFSZ, t16 = HALFSZ/4;
2385 int cx = ox + t2, cy = oy + t2;
2390 /* Clip to the grid square. */
2391 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2393 /* Clear the square. */
2394 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
2395 (lflags & DS_CURSOR) ?
2396 COL_CURSOR_BACKGROUND : COL_BACKGROUND);
2399 if (get_gui_style() == GUI_LOOPY) {
2400 /* Draw small dot, underneath any lines. */
2401 draw_circle(dr, cx, cy, t16, COL_GRID, COL_GRID);
2403 /* Draw outline of grid square */
2404 draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID);
2405 draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID);
2408 /* Draw grid: either thin gridlines, or no-line marks.
2409 * We draw these first because the thick laid lines should be on top. */
2410 for (d = 1; d < 16; d *= 2) {
2411 int xoff = t2 * DX(d), yoff = t2 * DY(d);
2413 if ((x == 0 && d == L) ||
2414 (y == 0 && d == U) ||
2415 (x == ds->w-1 && d == R) ||
2416 (y == ds->h-1 && d == D))
2417 continue; /* no gridlines out to the border. */
2419 if ((lflags >> DS_MSHIFT) & d) {
2420 /* either a no-line mark ... */
2421 int mx = cx + xoff, my = cy + yoff, msz = t16;
2423 draw_line(dr, mx-msz, my-msz, mx+msz, my+msz, COL_BLACK);
2424 draw_line(dr, mx-msz, my+msz, mx+msz, my-msz, COL_BLACK);
2426 if (get_gui_style() == GUI_LOOPY) {
2427 /* draw grid lines connecting centre of cells */
2428 draw_line(dr, cx, cy, cx+xoff, cy+yoff, COL_GRID);
2433 /* Draw each of the four directions, where laid (or error, or drag, etc.)
2434 * Order is important here, specifically for the eventual colours of the
2435 * exposed end caps. */
2436 draw_lines_specific(dr, ds, x, y, lflags, 0,
2437 (lflags & DS_FLASH ? COL_FLASH : COL_BLACK));
2438 draw_lines_specific(dr, ds, x, y, lflags, DS_ESHIFT, COL_ERROR);
2439 draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGOFF);
2440 draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGON);
2442 /* Draw a clue, if present */
2443 if (clue != NOCLUE) {
2444 int c = (lflags & DS_FLASH) ? COL_FLASH :
2445 (clue == STRAIGHT) ? COL_WHITE : COL_BLACK;
2447 if (lflags & DS_ERROR_CLUE) /* draw a bigger 'error' clue circle. */
2448 draw_circle(dr, cx, cy, TILE_SIZE*3/8, COL_ERROR, COL_ERROR);
2450 draw_circle(dr, cx, cy, TILE_SIZE/4, c, COL_BLACK);
2454 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2457 static void game_redraw(drawing *dr, game_drawstate *ds,
2458 const game_state *oldstate, const game_state *state,
2459 int dir, const game_ui *ui,
2460 float animtime, float flashtime)
2462 int w = state->shared->w, h = state->shared->h, sz = state->shared->sz;
2463 int x, y, force = 0, flashing = 0;
2467 * The initial contents of the window are not guaranteed and
2468 * can vary with front ends. To be on the safe side, all games
2469 * should start by drawing a big background-colour rectangle
2470 * covering the whole window.
2472 draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
2475 if (get_gui_style() == GUI_MASYU) {
2477 * Smaller black rectangle which is the main grid.
2479 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
2480 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
2481 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
2485 draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
2491 if (flashtime > 0 &&
2492 (flashtime <= FLASH_TIME/3 ||
2493 flashtime >= FLASH_TIME*2/3))
2494 flashing = DS_FLASH;
2496 memset(ds->draglines, 0, sz);
2497 if (ui->ndragcoords > 0) {
2498 int i, clearing = TRUE;
2499 for (i = 0; i < ui->ndragcoords - 1; i++) {
2500 int sx, sy, dx, dy, dir, oldstate, newstate;
2501 interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
2502 &dir, &oldstate, &newstate);
2503 ds->draglines[sy*w+sx] ^= (oldstate ^ newstate);
2504 ds->draglines[dy*w+dx] ^= (F(oldstate) ^ F(newstate));
2508 for (x = 0; x < w; x++) {
2509 for (y = 0; y < h; y++) {
2510 unsigned int f = (unsigned int)state->lines[y*w+x];
2511 unsigned int eline = (unsigned int)(state->errors[y*w+x] & (R|U|L|D));
2513 f |= eline << DS_ESHIFT;
2514 f |= ((unsigned int)ds->draglines[y*w+x]) << DS_DSHIFT;
2515 f |= ((unsigned int)state->marks[y*w+x]) << DS_MSHIFT;
2517 if (state->errors[y*w+x] & ERROR_CLUE)
2522 if (ui->cursor_active && x == ui->curx && y == ui->cury)
2525 if (f != ds->lflags[y*w+x] || force) {
2526 ds->lflags[y*w+x] = f;
2527 draw_square(dr, ds, ui, x, y, f, state->shared->clues[y*w+x]);
2533 static float game_anim_length(const game_state *oldstate,
2534 const game_state *newstate, int dir, game_ui *ui)
2539 static float game_flash_length(const game_state *oldstate,
2540 const game_state *newstate, int dir, game_ui *ui)
2542 if (!oldstate->completed && newstate->completed &&
2543 !oldstate->used_solve && !newstate->used_solve)
2549 static int game_status(const game_state *state)
2551 return state->completed ? +1 : 0;
2554 static int game_timing_state(const game_state *state, game_ui *ui)
2559 static void game_print_size(const game_params *params, float *x, float *y)
2564 * I'll use 6mm squares by default.
2566 game_compute_size(params, 600, &pw, &ph);
2571 static void game_print(drawing *dr, const game_state *state, int tilesize)
2573 int w = state->shared->w, h = state->shared->h, x, y;
2574 int black = print_mono_colour(dr, 0);
2575 int white = print_mono_colour(dr, 1);
2577 /* No GUI_LOOPY here: only use the familiar masyu style. */
2579 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2580 game_drawstate *ds = game_new_drawstate(dr, state);
2581 game_set_size(dr, ds, NULL, tilesize);
2583 /* Draw grid outlines (black). */
2584 for (x = 0; x <= w; x++)
2585 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black);
2586 for (y = 0; y <= h; y++)
2587 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black);
2589 for (x = 0; x < w; x++) {
2590 for (y = 0; y < h; y++) {
2591 int cx = COORD(x) + HALFSZ, cy = COORD(y) + HALFSZ;
2592 int clue = state->shared->clues[y*w+x];
2594 draw_lines_specific(dr, ds, x, y, state->lines[y*w+x], 0, black);
2596 if (clue != NOCLUE) {
2597 int c = (clue == CORNER) ? black : white;
2598 draw_circle(dr, cx, cy, TILE_SIZE/4, c, black);
2603 game_free_drawstate(dr, ds);
2607 #define thegame pearl
2610 const struct game thegame = {
2611 "Pearl", "games.pearl", "pearl",
2618 TRUE, game_configure, custom_params,
2626 TRUE, game_can_format_as_text_now, game_text_format,
2634 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2637 game_free_drawstate,
2642 TRUE, FALSE, game_print_size, game_print,
2643 FALSE, /* wants_statusbar */
2644 FALSE, game_timing_state,
2648 #ifdef STANDALONE_SOLVER
2653 const char *quis = NULL;
2655 static void usage(FILE *out) {
2656 fprintf(out, "usage: %s <params>\n", quis);
2659 static void pnum(int n, int ntot, const char *desc)
2661 printf("%2.1f%% (%d) %s", (double)n*100.0 / (double)ntot, n, desc);
2664 static void start_soak(game_params *p, random_state *rs, int nsecs)
2666 time_t tt_start, tt_now, tt_last;
2667 int n = 0, nsolved = 0, nimpossible = 0, ret;
2670 tt_start = tt_last = time(NULL);
2672 /* Currently this generates puzzles of any difficulty (trying to solve it
2673 * on the maximum difficulty level and not checking it's not too easy). */
2674 printf("Soak-testing a %dx%d grid (any difficulty)", p->w, p->h);
2675 if (nsecs > 0) printf(" for %d seconds", nsecs);
2680 grid = snewn(p->w*p->h, char);
2681 clues = snewn(p->w*p->h, char);
2684 n += new_clues(p, rs, clues, grid); /* should be 1, with nosolve */
2686 ret = pearl_solve(p->w, p->h, clues, grid, DIFF_TRICKY, FALSE);
2687 if (ret <= 0) nimpossible++;
2688 if (ret == 1) nsolved++;
2690 tt_now = time(NULL);
2691 if (tt_now > tt_last) {
2694 printf("%d total, %3.1f/s, ",
2695 n, (double)n / ((double)tt_now - tt_start));
2696 pnum(nsolved, n, "solved"); printf(", ");
2697 printf("%3.1f/s", (double)nsolved / ((double)tt_now - tt_start));
2698 if (nimpossible > 0)
2699 pnum(nimpossible, n, "impossible");
2702 if (nsecs > 0 && (tt_now - tt_start) > nsecs) {
2712 int main(int argc, const char *argv[])
2714 game_params *p = NULL;
2715 random_state *rs = NULL;
2716 time_t seed = time(NULL);
2717 char *id = NULL, *err;
2719 setvbuf(stdout, NULL, _IONBF, 0);
2723 while (--argc > 0) {
2724 char *p = (char*)(*++argv);
2725 if (!strcmp(p, "-e") || !strcmp(p, "--seed")) {
2726 seed = atoi(*++argv);
2728 } else if (*p == '-') {
2729 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2737 rs = random_new((void*)&seed, sizeof(time_t));
2738 p = default_params();
2741 if (strchr(id, ':')) {
2742 fprintf(stderr, "soak takes params only.\n");
2746 decode_params(p, id);
2747 err = validate_params(p, 1);
2749 fprintf(stderr, "%s: %s", argv[0], err);
2753 start_soak(p, rs, 0); /* run forever */
2757 for (i = 5; i <= 12; i++) {
2759 start_soak(p, rs, 5);
2772 /* vim: set shiftwidth=4 tabstop=8: */