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";
286 /* ----------------------------------------------------------------------
290 int pearl_solve(int w
, int h
, char *clues
, char *result
,
291 int difficulty
, int partial
)
293 int W
= 2*w
+1, H
= 2*h
+1;
300 * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature
301 * of the square (x,y), as a logical OR of bitfields.
303 * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates
304 * whether the horizontal edge between (x,y) and (x+1,y) is
305 * connected (1), disconnected (2) or unknown (3).
307 * workspace[(2*y+1)*W+(2*x)], indicates the same about the
308 * vertical edge between (x,y) and (x,y+1).
310 * Initially, every square is considered capable of being in
311 * any of the seven possible states (two straights, four
312 * corners and empty), except those corresponding to clue
313 * squares which are more restricted.
315 * Initially, all edges are unknown, except the ones around the
316 * grid border which are known to be disconnected.
318 workspace
= snewn(W
*H
, short);
319 for (x
= 0; x
< W
*H
; x
++)
322 for (y
= 0; y
< h
; y
++)
323 for (x
= 0; x
< w
; x
++)
324 switch (clues
[y
*w
+x
]) {
326 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLU
|bLD
|bRU
|bRD
;
329 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLR
|bUD
;
332 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLR
|bUD
|bLU
|bLD
|bRU
|bRD
|bBLANK
;
335 /* Horizontal edges */
336 for (y
= 0; y
<= h
; y
++)
337 for (x
= 0; x
< w
; x
++)
338 workspace
[(2*y
)*W
+(2*x
+1)] = (y
==0 || y
==h
? 2 : 3);
340 for (y
= 0; y
< h
; y
++)
341 for (x
= 0; x
<= w
; x
++)
342 workspace
[(2*y
+1)*W
+(2*x
)] = (x
==0 || x
==w
? 2 : 3);
345 * We maintain a dsf of connected squares, together with a
346 * count of the size of each equivalence class.
348 dsf
= snewn(w
*h
, int);
349 dsfsize
= snewn(w
*h
, int);
352 * Now repeatedly try to find something we can do.
355 int done_something
= FALSE
;
357 #ifdef SOLVER_DIAGNOSTICS
358 for (y
= 0; y
< H
; y
++) {
359 for (x
= 0; x
< W
; x
++)
360 printf("%*x", (x
&1) ? 5 : 2, workspace
[y
*W
+x
]);
366 * Go through the square state words, and discard any
367 * square state which is inconsistent with known facts
368 * about the edges around the square.
370 for (y
= 0; y
< h
; y
++)
371 for (x
= 0; x
< w
; x
++) {
372 for (b
= 0; b
< 0xD; b
++)
373 if (workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<b
)) {
375 * If any edge of this square is known to
376 * be connected when state b would require
377 * it disconnected, or vice versa, discard
380 for (d
= 1; d
<= 8; d
+= d
) {
381 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
382 if (workspace
[ey
*W
+ex
] ==
384 workspace
[(2*y
+1)*W
+(2*x
+1)] &= ~(1<<b
);
385 #ifdef SOLVER_DIAGNOSTICS
386 printf("edge (%d,%d)-(%d,%d) rules out state"
387 " %d for square (%d,%d)\n",
388 ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2,
391 done_something
= TRUE
;
398 * Consistency check: each square must have at
399 * least one state left!
401 if (!workspace
[(2*y
+1)*W
+(2*x
+1)]) {
402 #ifdef SOLVER_DIAGNOSTICS
403 printf("edge check at (%d,%d): inconsistency\n", x
, y
);
411 * Now go through the states array again, and nail down any
412 * unknown edge if one of its neighbouring squares makes it
415 for (y
= 0; y
< h
; y
++)
416 for (x
= 0; x
< w
; x
++) {
417 int edgeor
= 0, edgeand
= 15;
419 for (b
= 0; b
< 0xD; b
++)
420 if (workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<b
)) {
426 * Now any bit clear in edgeor marks a disconnected
427 * edge, and any bit set in edgeand marks a
431 /* First check consistency: neither bit is both! */
432 if (edgeand
& ~edgeor
) {
433 #ifdef SOLVER_DIAGNOSTICS
434 printf("square check at (%d,%d): inconsistency\n", x
, y
);
440 for (d
= 1; d
<= 8; d
+= d
) {
441 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
443 if (!(edgeor
& d
) && workspace
[ey
*W
+ex
] == 3) {
444 workspace
[ey
*W
+ex
] = 2;
445 done_something
= TRUE
;
446 #ifdef SOLVER_DIAGNOSTICS
447 printf("possible states of square (%d,%d) force edge"
448 " (%d,%d)-(%d,%d) to be disconnected\n",
449 x
, y
, ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
451 } else if ((edgeand
& d
) && workspace
[ey
*W
+ex
] == 3) {
452 workspace
[ey
*W
+ex
] = 1;
453 done_something
= TRUE
;
454 #ifdef SOLVER_DIAGNOSTICS
455 printf("possible states of square (%d,%d) force edge"
456 " (%d,%d)-(%d,%d) to be connected\n",
457 x
, y
, ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
467 * Now for longer-range clue-based deductions (using the
468 * rules that a corner clue must connect to two straight
469 * squares, and a straight clue must connect to at least
470 * one corner square).
472 for (y
= 0; y
< h
; y
++)
473 for (x
= 0; x
< w
; x
++)
474 switch (clues
[y
*w
+x
]) {
476 for (d
= 1; d
<= 8; d
+= d
) {
477 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
478 int fx
= ex
+ DX(d
), fy
= ey
+ DY(d
);
481 if (workspace
[ey
*W
+ex
] == 1) {
483 * If a corner clue is connected on any
484 * edge, then we can immediately nail
485 * down the square beyond that edge as
486 * being a straight in the appropriate
489 if (workspace
[fy
*W
+fx
] != (1<<type
)) {
490 workspace
[fy
*W
+fx
] = (1<<type
);
491 done_something
= TRUE
;
492 #ifdef SOLVER_DIAGNOSTICS
493 printf("corner clue at (%d,%d) forces square "
494 "(%d,%d) into state %d\n", x
, y
,
499 } else if (workspace
[ey
*W
+ex
] == 3) {
501 * Conversely, if a corner clue is
502 * separated by an unknown edge from a
503 * square which _cannot_ be a straight
504 * in the appropriate direction, we can
505 * mark that edge as disconnected.
507 if (!(workspace
[fy
*W
+fx
] & (1<<type
))) {
508 workspace
[ey
*W
+ex
] = 2;
509 done_something
= TRUE
;
510 #ifdef SOLVER_DIAGNOSTICS
511 printf("corner clue at (%d,%d), plus square "
512 "(%d,%d) not being state %d, "
513 "disconnects edge (%d,%d)-(%d,%d)\n",
514 x
, y
, fx
/2, fy
/2, type
,
515 ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
525 * If a straight clue is between two squares
526 * neither of which is capable of being a
527 * corner connected to it, then the straight
528 * clue cannot point in that direction.
530 for (d
= 1; d
<= 2; d
+= d
) {
531 int fx
= 2*x
+1 + 2*DX(d
), fy
= 2*y
+1 + 2*DY(d
);
532 int gx
= 2*x
+1 - 2*DX(d
), gy
= 2*y
+1 - 2*DY(d
);
535 if (!(workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<type
)))
538 if (!(workspace
[fy
*W
+fx
] & ((1<<(F(d
)|A(d
))) |
539 (1<<(F(d
)|C(d
))))) &&
540 !(workspace
[gy
*W
+gx
] & ((1<<( d
|A(d
))) |
542 workspace
[(2*y
+1)*W
+(2*x
+1)] &= ~(1<<type
);
543 done_something
= TRUE
;
544 #ifdef SOLVER_DIAGNOSTICS
545 printf("straight clue at (%d,%d) cannot corner at "
546 "(%d,%d) or (%d,%d) so is not state %d\n",
547 x
, y
, fx
/2, fy
/2, gx
/2, gy
/2, type
);
554 * If a straight clue with known direction is
555 * connected on one side to a known straight,
556 * then on the other side it must be a corner.
558 for (d
= 1; d
<= 8; d
+= d
) {
559 int fx
= 2*x
+1 + 2*DX(d
), fy
= 2*y
+1 + 2*DY(d
);
560 int gx
= 2*x
+1 - 2*DX(d
), gy
= 2*y
+1 - 2*DY(d
);
563 if (workspace
[(2*y
+1)*W
+(2*x
+1)] != (1<<type
))
566 if (!(workspace
[fy
*W
+fx
] &~ (bLR
|bUD
)) &&
567 (workspace
[gy
*W
+gx
] &~ (bLU
|bLD
|bRU
|bRD
))) {
568 workspace
[gy
*W
+gx
] &= (bLU
|bLD
|bRU
|bRD
);
569 done_something
= TRUE
;
570 #ifdef SOLVER_DIAGNOSTICS
571 printf("straight clue at (%d,%d) connecting to "
572 "straight at (%d,%d) makes (%d,%d) a "
573 "corner\n", x
, y
, fx
/2, fy
/2, gx
/2, gy
/2);
585 * Now detect shortcut loops.
589 int nonblanks
, loopclass
;
592 for (x
= 0; x
< w
*h
; x
++)
596 * First go through the edge entries and update the dsf
597 * of which squares are connected to which others. We
598 * also track the number of squares in each equivalence
599 * class, and count the overall number of
600 * known-non-blank squares.
602 * In the process of doing this, we must notice if a
603 * loop has already been formed. If it has, we blank
604 * out any square which isn't part of that loop
605 * (failing a consistency check if any such square does
606 * not have BLANK as one of its remaining options) and
607 * exit the deduction loop with success.
611 for (y
= 1; y
< H
-1; y
++)
612 for (x
= 1; x
< W
-1; x
++)
615 * (x,y) are the workspace coordinates of
616 * an edge field. Compute the normal-space
617 * coordinates of the squares it connects.
619 int ax
= (x
-1)/2, ay
= (y
-1)/2, ac
= ay
*w
+ax
;
620 int bx
= x
/2, by
= y
/2, bc
= by
*w
+bx
;
623 * If the edge is connected, do the dsf
626 if (workspace
[y
*W
+x
] == 1) {
629 ae
= dsf_canonify(dsf
, ac
);
630 be
= dsf_canonify(dsf
, bc
);
636 if (loopclass
!= -1) {
638 * In fact, we have two
639 * separate loops, which is
642 #ifdef SOLVER_DIAGNOSTICS
643 printf("two loops found in grid!\n");
651 * Merge the two equivalence
654 int size
= dsfsize
[ae
] + dsfsize
[be
];
655 dsf_merge(dsf
, ac
, bc
);
656 ae
= dsf_canonify(dsf
, ac
);
660 } else if ((y
& x
) & 1) {
662 * (x,y) are the workspace coordinates of a
663 * square field. If the square is
664 * definitely not blank, count it.
666 if (!(workspace
[y
*W
+x
] & bBLANK
))
671 * If we discovered an existing loop above, we must now
672 * blank every square not part of it, and exit the main
675 if (loopclass
!= -1) {
676 #ifdef SOLVER_DIAGNOSTICS
677 printf("loop found in grid!\n");
679 for (y
= 0; y
< h
; y
++)
680 for (x
= 0; x
< w
; x
++)
681 if (dsf_canonify(dsf
, y
*w
+x
) != loopclass
) {
682 if (workspace
[(y
*2+1)*W
+(x
*2+1)] & bBLANK
) {
683 workspace
[(y
*2+1)*W
+(x
*2+1)] = bBLANK
;
686 * This square is not part of the
687 * loop, but is known non-blank. We
690 #ifdef SOLVER_DIAGNOSTICS
691 printf("non-blank square (%d,%d) found outside"
705 /* Further deductions are considered 'tricky'. */
706 if (difficulty
== DIFF_EASY
) goto done_deductions
;
709 * Now go through the workspace again and mark any edge
710 * which would cause a shortcut loop (i.e. would
711 * connect together two squares in the same equivalence
712 * class, and that equivalence class does not contain
713 * _all_ the known-non-blank squares currently in the
714 * grid) as disconnected. Also, mark any _square state_
715 * which would cause a shortcut loop as disconnected.
717 for (y
= 1; y
< H
-1; y
++)
718 for (x
= 1; x
< W
-1; x
++)
721 * (x,y) are the workspace coordinates of
722 * an edge field. Compute the normal-space
723 * coordinates of the squares it connects.
725 int ax
= (x
-1)/2, ay
= (y
-1)/2, ac
= ay
*w
+ax
;
726 int bx
= x
/2, by
= y
/2, bc
= by
*w
+bx
;
729 * If the edge is currently unknown, and
730 * sits between two squares in the same
731 * equivalence class, and the size of that
732 * class is less than nonblanks, then
733 * connecting this edge would be a shortcut
734 * loop and so we must not do so.
736 if (workspace
[y
*W
+x
] == 3) {
739 ae
= dsf_canonify(dsf
, ac
);
740 be
= dsf_canonify(dsf
, bc
);
744 * We have a loop. Is it a shortcut?
746 if (dsfsize
[ae
] < nonblanks
) {
748 * Yes! Mark this edge disconnected.
750 workspace
[y
*W
+x
] = 2;
751 done_something
= TRUE
;
752 #ifdef SOLVER_DIAGNOSTICS
753 printf("edge (%d,%d)-(%d,%d) would create"
754 " a shortcut loop, hence must be"
755 " disconnected\n", x
/2, y
/2,
761 } else if ((y
& x
) & 1) {
763 * (x,y) are the workspace coordinates of a
764 * square field. Go through its possible
765 * (non-blank) states and see if any gives
766 * rise to a shortcut loop.
768 * This is slightly fiddly, because we have
769 * to check whether this square is already
770 * part of the same equivalence class as
771 * the things it's joining.
773 int ae
= dsf_canonify(dsf
, (y
/2)*w
+(x
/2));
775 for (b
= 2; b
< 0xD; b
++)
776 if (workspace
[y
*W
+x
] & (1<<b
)) {
778 * Find the equivalence classes of
779 * the two squares this one would
780 * connect if it were in this
785 for (d
= 1; d
<= 8; d
+= d
) if (b
& d
) {
786 int xx
= x
/2 + DX(d
), yy
= y
/2 + DY(d
);
787 int ee
= dsf_canonify(dsf
, yy
*w
+xx
);
797 * This square state would form
798 * a loop on equivalence class
799 * e. Measure the size of that
800 * loop, and see if it's a
803 int loopsize
= dsfsize
[e
];
805 loopsize
++;/* add the square itself */
806 if (loopsize
< nonblanks
) {
808 * It is! Mark this square
811 workspace
[y
*W
+x
] &= ~(1<<b
);
812 done_something
= TRUE
;
813 #ifdef SOLVER_DIAGNOSTICS
814 printf("square (%d,%d) would create a "
815 "shortcut loop in state %d, "
831 * If we reach here, there is nothing left we can do.
832 * Return 2 for ambiguous puzzle.
841 * If ret = 1 then we've successfully achieved a solution. This
842 * means that we expect every square to be nailed down to
843 * exactly one possibility. If this is the case, or if the caller
844 * asked for a partial solution anyway, transcribe those
845 * possibilities into the result array.
847 if (ret
== 1 || partial
) {
848 for (y
= 0; y
< h
; y
++) {
849 for (x
= 0; x
< w
; x
++) {
850 for (b
= 0; b
< 0xD; b
++)
851 if (workspace
[(2*y
+1)*W
+(2*x
+1)] == (1<<b
)) {
855 if (ret
== 1) assert(b
< 0xD); /* we should have had a break by now */
867 /* ----------------------------------------------------------------------
872 * We use the loop generator code from loopy, hard-coding to a square
873 * grid of the appropriate size. Knowing the grid layout and the tile
874 * size we can shrink that to our small grid and then make our line
875 * layout from the face colour info.
877 * We provide a bias function to the loop generator which tries to
878 * bias in favour of loops with more scope for Pearl black clues. This
879 * seems to improve the success rate of the puzzle generator, in that
880 * such loops have a better chance of being soluble with all valid
884 struct pearl_loopgen_bias_ctx
{
886 * Our bias function counts the number of 'black clue' corners
887 * (i.e. corners adjacent to two straights) in both the
888 * BLACK/nonBLACK and WHITE/nonWHITE boundaries. In order to do
891 * - track the edges that are part of each of those loops
892 * - track the types of vertex in each loop (corner, straight,
894 * - track the current black-clue status of each vertex in each
897 * Each of these chunks of data is updated incrementally from the
898 * previous one, to avoid slowdown due to the bias function
899 * rescanning the whole grid every time it's called.
901 * So we need a lot of separate arrays, plus a tdq for each one,
902 * and we must repeat it all twice for the BLACK and WHITE
905 struct pearl_loopgen_bias_ctx_boundary
{
906 int colour
; /* FACE_WHITE or FACE_BLACK */
908 char *edges
; /* is each edge part of the loop? */
911 char *vertextypes
; /* bits 0-3 == outgoing edge bitmap;
912 * bit 4 set iff corner clue.
913 * Hence, 0 means non-vertex;
914 * nonzero but bit 4 zero = straight. */
915 int *neighbour
[2]; /* indices of neighbour vertices in loop */
916 tdq
*vertextypes_todo
;
918 char *blackclues
; /* is each vertex a black clue site? */
919 tdq
*blackclues_todo
;
920 } boundaries
[2]; /* boundaries[0]=WHITE, [1]=BLACK */
922 char *faces
; /* remember last-seen colour of each face */
929 int pearl_loopgen_bias(void *vctx
, char *board
, int face
)
931 struct pearl_loopgen_bias_ctx
*ctx
= (struct pearl_loopgen_bias_ctx
*)vctx
;
933 int oldface
, newface
;
936 tdq_add(ctx
->faces_todo
, face
);
937 while ((j
= tdq_remove(ctx
->faces_todo
)) >= 0) {
938 oldface
= ctx
->faces
[j
];
939 ctx
->faces
[j
] = newface
= board
[j
];
940 for (i
= 0; i
< 2; i
++) {
941 struct pearl_loopgen_bias_ctx_boundary
*b
= &ctx
->boundaries
[i
];
945 * If the face has changed either from or to colour c, we need
946 * to reprocess the edges for this boundary.
948 if (oldface
== c
|| newface
== c
) {
949 grid_face
*f
= &g
->faces
[face
];
950 for (k
= 0; k
< f
->order
; k
++)
951 tdq_add(b
->edges_todo
, f
->edges
[k
] - g
->edges
);
956 for (i
= 0; i
< 2; i
++) {
957 struct pearl_loopgen_bias_ctx_boundary
*b
= &ctx
->boundaries
[i
];
961 * Go through the to-do list of edges. For each edge, decide
962 * anew whether it's part of this boundary or not. Any edge
963 * that changes state has to have both its endpoints put on
964 * the vertextypes_todo list.
966 while ((j
= tdq_remove(b
->edges_todo
)) >= 0) {
967 grid_edge
*e
= &g
->edges
[j
];
968 int fc1
= e
->face1
? board
[e
->face1
- g
->faces
] : FACE_BLACK
;
969 int fc2
= e
->face2
? board
[e
->face2
- g
->faces
] : FACE_BLACK
;
970 int oldedge
= b
->edges
[j
];
971 int newedge
= (fc1
==c
) ^ (fc2
==c
);
972 if (oldedge
!= newedge
) {
973 b
->edges
[j
] = newedge
;
974 tdq_add(b
->vertextypes_todo
, e
->dot1
- g
->dots
);
975 tdq_add(b
->vertextypes_todo
, e
->dot2
- g
->dots
);
980 * Go through the to-do list of vertices whose types need
981 * refreshing. For each one, decide whether it's a corner, a
982 * straight, or a vertex not in the loop, and in the former
983 * two cases also work out the indices of its neighbour
984 * vertices along the loop. Any vertex that changes state must
985 * be put back on the to-do list for deciding if it's a black
986 * clue site, and so must its two new neighbours _and_ its two
989 while ((j
= tdq_remove(b
->vertextypes_todo
)) >= 0) {
990 grid_dot
*d
= &g
->dots
[j
];
991 int neighbours
[2], type
= 0, n
= 0;
993 for (k
= 0; k
< d
->order
; k
++) {
994 grid_edge
*e
= d
->edges
[k
];
995 grid_dot
*d2
= (e
->dot1
== d
? e
->dot2
: e
->dot1
);
996 /* dir == 0,1,2,3 for an edge going L,U,R,D */
997 int dir
= (d
->y
== d2
->y
) + 2*(d
->x
+d
->y
> d2
->x
+d2
->y
);
998 int ei
= e
- g
->edges
;
1001 neighbours
[n
] = d2
- g
->dots
;
1007 * Decide if it's a corner, and set the corner flag if so.
1009 if (type
!= 0 && type
!= 0x5 && type
!= 0xA)
1012 if (type
!= b
->vertextypes
[j
]) {
1014 * Recompute old neighbours, if any.
1016 if (b
->vertextypes
[j
]) {
1017 tdq_add(b
->blackclues_todo
, b
->neighbour
[0][j
]);
1018 tdq_add(b
->blackclues_todo
, b
->neighbour
[1][j
]);
1021 * Recompute this vertex.
1023 tdq_add(b
->blackclues_todo
, j
);
1024 b
->vertextypes
[j
] = type
;
1026 * Recompute new neighbours, if any.
1028 if (b
->vertextypes
[j
]) {
1029 b
->neighbour
[0][j
] = neighbours
[0];
1030 b
->neighbour
[1][j
] = neighbours
[1];
1031 tdq_add(b
->blackclues_todo
, b
->neighbour
[0][j
]);
1032 tdq_add(b
->blackclues_todo
, b
->neighbour
[1][j
]);
1038 * Go through the list of vertices which we must check to see
1039 * if they're black clue sites. Each one is a black clue site
1040 * iff it is a corner and its loop neighbours are non-corners.
1041 * Adjust the running total of black clues we've counted.
1043 while ((j
= tdq_remove(b
->blackclues_todo
)) >= 0) {
1044 ctx
->score
-= b
->blackclues
[j
];
1045 b
->blackclues
[j
] = ((b
->vertextypes
[j
] & 0x10) &&
1046 !((b
->vertextypes
[b
->neighbour
[0][j
]] |
1047 b
->vertextypes
[b
->neighbour
[1][j
]])
1049 ctx
->score
+= b
->blackclues
[j
];
1056 void pearl_loopgen(int w
, int h
, char *lines
, random_state
*rs
)
1058 grid
*g
= grid_new(GRID_SQUARE
, w
-1, h
-1, NULL
);
1059 char *board
= snewn(g
->num_faces
, char);
1060 int i
, s
= g
->tilesize
;
1061 struct pearl_loopgen_bias_ctx biasctx
;
1063 memset(lines
, 0, w
*h
);
1066 * Initialise the context for the bias function. Initially we fill
1067 * all the to-do lists, so that the first call will scan
1068 * everything; thereafter the lists stay empty so we make
1069 * incremental changes.
1072 biasctx
.faces
= snewn(g
->num_faces
, char);
1073 biasctx
.faces_todo
= tdq_new(g
->num_faces
);
1074 tdq_fill(biasctx
.faces_todo
);
1076 memset(biasctx
.faces
, FACE_GREY
, g
->num_faces
);
1077 for (i
= 0; i
< 2; i
++) {
1078 biasctx
.boundaries
[i
].edges
= snewn(g
->num_edges
, char);
1079 memset(biasctx
.boundaries
[i
].edges
, 0, g
->num_edges
);
1080 biasctx
.boundaries
[i
].edges_todo
= tdq_new(g
->num_edges
);
1081 tdq_fill(biasctx
.boundaries
[i
].edges_todo
);
1082 biasctx
.boundaries
[i
].vertextypes
= snewn(g
->num_dots
, char);
1083 memset(biasctx
.boundaries
[i
].vertextypes
, 0, g
->num_dots
);
1084 biasctx
.boundaries
[i
].neighbour
[0] = snewn(g
->num_dots
, int);
1085 biasctx
.boundaries
[i
].neighbour
[1] = snewn(g
->num_dots
, int);
1086 biasctx
.boundaries
[i
].vertextypes_todo
= tdq_new(g
->num_dots
);
1087 tdq_fill(biasctx
.boundaries
[i
].vertextypes_todo
);
1088 biasctx
.boundaries
[i
].blackclues
= snewn(g
->num_dots
, char);
1089 memset(biasctx
.boundaries
[i
].blackclues
, 0, g
->num_dots
);
1090 biasctx
.boundaries
[i
].blackclues_todo
= tdq_new(g
->num_dots
);
1091 tdq_fill(biasctx
.boundaries
[i
].blackclues_todo
);
1093 biasctx
.boundaries
[0].colour
= FACE_WHITE
;
1094 biasctx
.boundaries
[1].colour
= FACE_BLACK
;
1095 generate_loop(g
, board
, rs
, pearl_loopgen_bias
, &biasctx
);
1096 sfree(biasctx
.faces
);
1097 tdq_free(biasctx
.faces_todo
);
1098 for (i
= 0; i
< 2; i
++) {
1099 sfree(biasctx
.boundaries
[i
].edges
);
1100 tdq_free(biasctx
.boundaries
[i
].edges_todo
);
1101 sfree(biasctx
.boundaries
[i
].vertextypes
);
1102 sfree(biasctx
.boundaries
[i
].neighbour
[0]);
1103 sfree(biasctx
.boundaries
[i
].neighbour
[1]);
1104 tdq_free(biasctx
.boundaries
[i
].vertextypes_todo
);
1105 sfree(biasctx
.boundaries
[i
].blackclues
);
1106 tdq_free(biasctx
.boundaries
[i
].blackclues_todo
);
1109 for (i
= 0; i
< g
->num_edges
; i
++) {
1110 grid_edge
*e
= g
->edges
+ i
;
1111 enum face_colour c1
= FACE_COLOUR(e
->face1
);
1112 enum face_colour c2
= FACE_COLOUR(e
->face2
);
1113 assert(c1
!= FACE_GREY
);
1114 assert(c2
!= FACE_GREY
);
1116 /* This grid edge is on the loop: lay line along it */
1117 int x1
= e
->dot1
->x
/s
, y1
= e
->dot1
->y
/s
;
1118 int x2
= e
->dot2
->x
/s
, y2
= e
->dot2
->y
/s
;
1120 /* (x1,y1) and (x2,y2) are now in our grid coords (0-w,0-h). */
1122 if (y1
> y2
) SWAP(y1
,y2
);
1125 lines
[y1
*w
+x1
] |= D
;
1126 lines
[y2
*w
+x1
] |= U
;
1127 } else if (y1
== y2
) {
1128 if (x1
> x2
) SWAP(x1
,x2
);
1131 lines
[y1
*w
+x1
] |= R
;
1132 lines
[y1
*w
+x2
] |= L
;
1134 assert(!"grid with diagonal coords?!");
1141 #if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
1142 printf("as returned:\n");
1143 for (y
= 0; y
< h
; y
++) {
1144 for (x
= 0; x
< w
; x
++) {
1145 int type
= lines
[y
*w
+x
];
1147 if (type
& L
) *p
++ = 'L';
1148 if (type
& R
) *p
++ = 'R';
1149 if (type
& U
) *p
++ = 'U';
1150 if (type
& D
) *p
++ = 'D';
1160 static int new_clues(const game_params
*params
, random_state
*rs
,
1161 char *clues
, char *grid
)
1163 int w
= params
->w
, h
= params
->h
, diff
= params
->difficulty
;
1164 int ngen
= 0, x
, y
, d
, ret
, i
;
1168 * Difficulty exception: 5x5 Tricky is not generable (the
1169 * generator will spin forever trying) and so we fudge it to Easy.
1171 if (w
== 5 && h
== 5 && diff
> DIFF_EASY
)
1176 pearl_loopgen(w
, h
, grid
, rs
);
1178 #ifdef GENERATION_DIAGNOSTICS
1179 printf("grid array:\n");
1180 for (y
= 0; y
< h
; y
++) {
1181 for (x
= 0; x
< w
; x
++) {
1182 int type
= grid
[y
*w
+x
];
1184 if (type
& L
) *p
++ = 'L';
1185 if (type
& R
) *p
++ = 'R';
1186 if (type
& U
) *p
++ = 'U';
1187 if (type
& D
) *p
++ = 'D';
1197 * Set up the maximal clue array.
1199 for (y
= 0; y
< h
; y
++)
1200 for (x
= 0; x
< w
; x
++) {
1201 int type
= grid
[y
*w
+x
];
1203 clues
[y
*w
+x
] = NOCLUE
;
1205 if ((bLR
|bUD
) & (1 << type
)) {
1207 * This is a straight; see if it's a viable
1208 * candidate for a straight clue. It qualifies if
1209 * at least one of the squares it connects to is a
1212 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1213 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1214 assert(xx
>= 0 && xx
< w
&& yy
>= 0 && yy
< h
);
1215 if ((bLU
|bLD
|bRU
|bRD
) & (1 << grid
[yy
*w
+xx
]))
1218 if (d
<= 8) /* we found one */
1219 clues
[y
*w
+x
] = STRAIGHT
;
1220 } else if ((bLU
|bLD
|bRU
|bRD
) & (1 << type
)) {
1222 * This is a corner; see if it's a viable candidate
1223 * for a corner clue. It qualifies if all the
1224 * squares it connects to are straights.
1226 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1227 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1228 assert(xx
>= 0 && xx
< w
&& yy
>= 0 && yy
< h
);
1229 if (!((bLR
|bUD
) & (1 << grid
[yy
*w
+xx
])))
1232 if (d
> 8) /* we didn't find a counterexample */
1233 clues
[y
*w
+x
] = CORNER
;
1237 #ifdef GENERATION_DIAGNOSTICS
1238 printf("clue array:\n");
1239 for (y
= 0; y
< h
; y
++) {
1240 for (x
= 0; x
< w
; x
++) {
1241 printf("%c", " *O"[(unsigned char)clues
[y
*w
+x
]]);
1248 if (!params
->nosolve
) {
1249 int *cluespace
, *straights
, *corners
;
1250 int nstraights
, ncorners
, nstraightpos
, ncornerpos
;
1253 * See if we can solve the puzzle just like this.
1255 ret
= pearl_solve(w
, h
, clues
, grid
, diff
, FALSE
);
1256 assert(ret
> 0); /* shouldn't be inconsistent! */
1258 continue; /* go round and try again */
1261 * Check this puzzle isn't too easy.
1263 if (diff
> DIFF_EASY
) {
1264 ret
= pearl_solve(w
, h
, clues
, grid
, diff
-1, FALSE
);
1267 continue; /* too easy: try again */
1271 * Now shuffle the grid points and gradually remove the
1272 * clues to find a minimal set which still leaves the
1275 * We preferentially attempt to remove whichever type of
1276 * clue is currently most numerous, to combat a general
1277 * tendency of plain random generation to bias in favour
1278 * of many white clues and few black.
1280 * 'nstraights' and 'ncorners' count the number of clues
1281 * of each type currently remaining in the grid;
1282 * 'nstraightpos' and 'ncornerpos' count the clues of each
1283 * type we have left to try to remove. (Clues which we
1284 * have tried and failed to remove are counted by the
1285 * former but not the latter.)
1287 cluespace
= snewn(w
*h
, int);
1288 straights
= cluespace
;
1290 for (i
= 0; i
< w
*h
; i
++)
1291 if (clues
[i
] == STRAIGHT
)
1292 straights
[nstraightpos
++] = i
;
1293 corners
= straights
+ nstraightpos
;
1295 for (i
= 0; i
< w
*h
; i
++)
1296 if (clues
[i
] == STRAIGHT
)
1297 corners
[ncornerpos
++] = i
;
1298 nstraights
= nstraightpos
;
1299 ncorners
= ncornerpos
;
1301 shuffle(straights
, nstraightpos
, sizeof(*straights
), rs
);
1302 shuffle(corners
, ncornerpos
, sizeof(*corners
), rs
);
1303 while (nstraightpos
> 0 || ncornerpos
> 0) {
1308 * Decide which clue to try to remove next. If both
1309 * types are available, we choose whichever kind is
1310 * currently overrepresented; otherwise we take
1311 * whatever we can get.
1313 if (nstraightpos
> 0 && ncornerpos
> 0) {
1314 if (nstraights
>= ncorners
)
1315 cluepos
= straights
[--nstraightpos
];
1317 cluepos
= straights
[--ncornerpos
];
1319 if (nstraightpos
> 0)
1320 cluepos
= straights
[--nstraightpos
];
1322 cluepos
= straights
[--ncornerpos
];
1328 clue
= clues
[y
*w
+x
];
1329 clues
[y
*w
+x
] = 0; /* try removing this clue */
1331 ret
= pearl_solve(w
, h
, clues
, grid
, diff
, FALSE
);
1334 clues
[y
*w
+x
] = clue
; /* oops, put it back again */
1339 #ifdef FINISHED_PUZZLE
1340 printf("clue array:\n");
1341 for (y
= 0; y
< h
; y
++) {
1342 for (x
= 0; x
< w
; x
++) {
1343 printf("%c", " *O"[(unsigned char)clues
[y
*w
+x
]]);
1353 debug(("%d %dx%d loops before finished puzzle.\n", ngen
, w
, h
));
1358 static char *new_game_desc(const game_params
*params
, random_state
*rs
,
1359 char **aux
, int interactive
)
1363 int w
= params
->w
, h
= params
->h
, i
, j
;
1365 grid
= snewn(w
*h
, char);
1366 clues
= snewn(w
*h
, char);
1368 new_clues(params
, rs
, clues
, grid
);
1370 desc
= snewn(w
* h
+ 1, char);
1371 for (i
= j
= 0; i
< w
*h
; i
++) {
1372 if (clues
[i
] == NOCLUE
&& j
> 0 &&
1373 desc
[j
-1] >= 'a' && desc
[j
-1] < 'z')
1375 else if (clues
[i
] == NOCLUE
)
1377 else if (clues
[i
] == CORNER
)
1379 else if (clues
[i
] == STRAIGHT
)
1384 *aux
= snewn(w
*h
+1, char);
1385 for (i
= 0; i
< w
*h
; i
++)
1386 (*aux
)[i
] = (grid
[i
] < 10) ? (grid
[i
] + '0') : (grid
[i
] + 'A' - 10);
1395 static char *validate_desc(const game_params
*params
, const char *desc
)
1398 const int totalsize
= params
->w
* params
->h
;
1401 for (i
= 0; desc
[i
]; i
++) {
1402 if (desc
[i
] >= 'a' && desc
[i
] <= 'z')
1403 sizesofar
+= desc
[i
] - 'a' + 1;
1404 else if (desc
[i
] == 'B' || desc
[i
] == 'W')
1407 return "unrecognised character in string";
1410 if (sizesofar
> totalsize
)
1411 return "string too long";
1412 else if (sizesofar
< totalsize
)
1413 return "string too short";
1418 static game_state
*new_game(midend
*me
, const game_params
*params
,
1421 game_state
*state
= snew(game_state
);
1422 int i
, j
, sz
= params
->w
*params
->h
;
1424 state
->completed
= state
->used_solve
= FALSE
;
1425 state
->shared
= snew(struct shared_state
);
1427 state
->shared
->w
= params
->w
;
1428 state
->shared
->h
= params
->h
;
1429 state
->shared
->sz
= sz
;
1430 state
->shared
->refcnt
= 1;
1431 state
->shared
->clues
= snewn(sz
, char);
1432 for (i
= j
= 0; desc
[i
]; i
++) {
1434 if (desc
[i
] >= 'a' && desc
[i
] <= 'z') {
1435 int n
= desc
[i
] - 'a' + 1;
1436 assert(j
+ n
<= sz
);
1438 state
->shared
->clues
[j
++] = NOCLUE
;
1439 } else if (desc
[i
] == 'B') {
1440 state
->shared
->clues
[j
++] = CORNER
;
1441 } else if (desc
[i
] == 'W') {
1442 state
->shared
->clues
[j
++] = STRAIGHT
;
1446 state
->lines
= snewn(sz
, char);
1447 state
->errors
= snewn(sz
, char);
1448 state
->marks
= snewn(sz
, char);
1449 for (i
= 0; i
< sz
; i
++)
1450 state
->lines
[i
] = state
->errors
[i
] = state
->marks
[i
] = BLANK
;
1455 static game_state
*dup_game(const game_state
*state
)
1457 game_state
*ret
= snew(game_state
);
1458 int sz
= state
->shared
->sz
, i
;
1460 ret
->shared
= state
->shared
;
1461 ret
->completed
= state
->completed
;
1462 ret
->used_solve
= state
->used_solve
;
1463 ++ret
->shared
->refcnt
;
1465 ret
->lines
= snewn(sz
, char);
1466 ret
->errors
= snewn(sz
, char);
1467 ret
->marks
= snewn(sz
, char);
1468 for (i
= 0; i
< sz
; i
++) {
1469 ret
->lines
[i
] = state
->lines
[i
];
1470 ret
->errors
[i
] = state
->errors
[i
];
1471 ret
->marks
[i
] = state
->marks
[i
];
1477 static void free_game(game_state
*state
)
1480 if (--state
->shared
->refcnt
== 0) {
1481 sfree(state
->shared
->clues
);
1482 sfree(state
->shared
);
1484 sfree(state
->lines
);
1485 sfree(state
->errors
);
1486 sfree(state
->marks
);
1490 static char nbits
[16] = { 0, 1, 1, 2,
1494 #define NBITS(l) ( ((l) < 0 || (l) > 15) ? 4 : nbits[l] )
1496 #define ERROR_CLUE 16
1498 static void dsf_update_completion(game_state
*state
, int ax
, int ay
, char dir
,
1501 int w
= state
->shared
->w
/*, h = state->shared->h */;
1502 int ac
= ay
*w
+ax
, bx
, by
, bc
;
1504 if (!(state
->lines
[ac
] & dir
)) return; /* no link */
1505 bx
= ax
+ DX(dir
); by
= ay
+ DY(dir
);
1507 assert(INGRID(state
, bx
, by
)); /* should not have a link off grid */
1510 assert(state
->lines
[bc
] & F(dir
)); /* should have reciprocal link */
1511 if (!(state
->lines
[bc
] & F(dir
))) return;
1513 dsf_merge(dsf
, ac
, bc
);
1516 static void check_completion(game_state
*state
, int mark
)
1518 int w
= state
->shared
->w
, h
= state
->shared
->h
, x
, y
, i
, d
;
1519 int had_error
= FALSE
;
1520 int *dsf
, *component_state
;
1521 int nsilly
, nloop
, npath
, largest_comp
, largest_size
, total_pathsize
;
1522 enum { COMP_NONE
, COMP_LOOP
, COMP_PATH
, COMP_SILLY
, COMP_EMPTY
};
1525 for (i
= 0; i
< w
*h
; i
++) {
1526 state
->errors
[i
] = 0;
1530 #define ERROR(x,y,e) do { had_error = TRUE; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0)
1533 * Analyse the solution into loops, paths and stranger things.
1534 * Basic strategy here is all the same as in Loopy - see the big
1535 * comment in loopy.c's check_completion() - and for exactly the
1536 * same reasons, since Loopy and Pearl have basically the same
1537 * form of expected solution.
1539 dsf
= snew_dsf(w
*h
);
1541 /* Build the dsf. */
1542 for (x
= 0; x
< w
; x
++) {
1543 for (y
= 0; y
< h
; y
++) {
1544 dsf_update_completion(state
, x
, y
, R
, dsf
);
1545 dsf_update_completion(state
, x
, y
, D
, dsf
);
1549 /* Initialise a state variable for each connected component. */
1550 component_state
= snewn(w
*h
, int);
1551 for (i
= 0; i
< w
*h
; i
++) {
1552 if (dsf_canonify(dsf
, i
) == i
)
1553 component_state
[i
] = COMP_LOOP
;
1555 component_state
[i
] = COMP_NONE
;
1559 * Classify components, and mark errors where a square has more
1560 * than two line segments.
1562 for (x
= 0; x
< w
; x
++) {
1563 for (y
= 0; y
< h
; y
++) {
1564 int type
= state
->lines
[y
*w
+x
];
1565 int degree
= NBITS(type
);
1566 int comp
= dsf_canonify(dsf
, y
*w
+x
);
1569 component_state
[comp
] = COMP_SILLY
;
1570 } else if (degree
== 0) {
1571 component_state
[comp
] = COMP_EMPTY
;
1572 } else if (degree
== 1) {
1573 if (component_state
[comp
] != COMP_SILLY
)
1574 component_state
[comp
] = COMP_PATH
;
1579 /* Count the components, and find the largest sensible one. */
1580 nsilly
= nloop
= npath
= 0;
1582 largest_comp
= largest_size
= -1;
1583 for (i
= 0; i
< w
*h
; i
++) {
1584 if (component_state
[i
] == COMP_SILLY
) {
1586 } else if (component_state
[i
] == COMP_PATH
) {
1587 total_pathsize
+= dsf_size(dsf
, i
);
1589 } else if (component_state
[i
] == COMP_LOOP
) {
1594 if ((this_size
= dsf_size(dsf
, i
)) > largest_size
) {
1596 largest_size
= this_size
;
1600 if (largest_size
< total_pathsize
) {
1601 largest_comp
= -1; /* means the paths */
1602 largest_size
= total_pathsize
;
1605 if (nloop
> 0 && nloop
+ npath
> 1) {
1607 * If there are at least two sensible components including at
1608 * least one loop, highlight every sensible component that is
1609 * not the largest one.
1611 for (i
= 0; i
< w
*h
; i
++) {
1612 int comp
= dsf_canonify(dsf
, i
);
1613 if ((component_state
[comp
] == COMP_PATH
&&
1614 -1 != largest_comp
) ||
1615 (component_state
[comp
] == COMP_LOOP
&&
1616 comp
!= largest_comp
))
1617 ERROR(i
%w
, i
/w
, state
->lines
[i
]);
1621 /* Now we've finished with the dsf and component states. The only
1622 * thing we'll need to remember later on is whether all edges were
1623 * part of a single loop, for which our counter variables
1624 * nsilly,nloop,npath are enough. */
1625 sfree(component_state
);
1629 * Check that no clues are contradicted. This code is similar to
1630 * the code that sets up the maximal clue array for any given
1633 for (x
= 0; x
< w
; x
++) {
1634 for (y
= 0; y
< h
; y
++) {
1635 int type
= state
->lines
[y
*w
+x
];
1636 if (state
->shared
->clues
[y
*w
+x
] == CORNER
) {
1637 /* Supposed to be a corner: will find a contradiction if
1638 * it actually contains a straight line, or if it touches any
1640 if ((bLR
|bUD
) & (1 << type
)) {
1641 ERROR(x
,y
,ERROR_CLUE
); /* actually straight */
1643 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1644 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1645 if (!INGRID(state
, xx
, yy
)) {
1646 ERROR(x
,y
,d
); /* leads off grid */
1648 if ((bLU
|bLD
|bRU
|bRD
) & (1 << state
->lines
[yy
*w
+xx
])) {
1649 ERROR(x
,y
,ERROR_CLUE
); /* touches corner */
1653 } else if (state
->shared
->clues
[y
*w
+x
] == STRAIGHT
) {
1654 /* Supposed to be straight: will find a contradiction if
1655 * it actually contains a corner, or if it only touches
1656 * straight lines. */
1657 if ((bLU
|bLD
|bRU
|bRD
) & (1 << type
)) {
1658 ERROR(x
,y
,ERROR_CLUE
); /* actually a corner */
1661 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1662 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1663 if (!INGRID(state
, xx
, yy
)) {
1664 ERROR(x
,y
,d
); /* leads off grid */
1666 if ((bLR
|bUD
) & (1 << state
->lines
[yy
*w
+xx
]))
1667 i
++; /* a straight */
1670 if (i
>= 2 && NBITS(type
) >= 2) {
1671 ERROR(x
,y
,ERROR_CLUE
); /* everything touched is straight */
1677 if (nloop
== 1 && nsilly
== 0 && npath
== 0) {
1679 * If there's exactly one loop (so that the puzzle is at least
1680 * potentially complete), we need to ensure it hasn't left any
1681 * clue out completely.
1683 for (x
= 0; x
< w
; x
++) {
1684 for (y
= 0; y
< h
; y
++) {
1685 if (state
->lines
[y
*w
+x
] == BLANK
) {
1686 if (state
->shared
->clues
[y
*w
+x
] != NOCLUE
) {
1687 /* the loop doesn't include this clue square! */
1688 ERROR(x
, y
, ERROR_CLUE
);
1695 * But if not, then we're done!
1698 state
->completed
= TRUE
;
1702 /* completion check:
1704 * - no clues must be contradicted (highlight clue itself in error if so)
1705 * - if there is a closed loop it must include every line segment laid
1706 * - if there's a smaller closed loop then highlight whole loop as error
1707 * - no square must have more than 2 lines radiating from centre point
1708 * (highlight all lines in that square as error if so)
1711 static char *solve_for_diff(game_state
*state
, char *old_lines
, char *new_lines
)
1713 int w
= state
->shared
->w
, h
= state
->shared
->h
, i
;
1714 char *move
= snewn(w
*h
*40, char), *p
= move
;
1717 for (i
= 0; i
< w
*h
; i
++) {
1718 if (old_lines
[i
] != new_lines
[i
]) {
1719 p
+= sprintf(p
, ";R%d,%d,%d", new_lines
[i
], i
%w
, i
/w
);
1723 move
= sresize(move
, p
- move
, char);
1728 static char *solve_game(const game_state
*state
, const game_state
*currstate
,
1729 const char *aux
, char **error
)
1731 game_state
*solved
= dup_game(state
);
1732 int i
, ret
, sz
= state
->shared
->sz
;
1736 for (i
= 0; i
< sz
; i
++) {
1737 if (aux
[i
] >= '0' && aux
[i
] <= '9')
1738 solved
->lines
[i
] = aux
[i
] - '0';
1739 else if (aux
[i
] >= 'A' && aux
[i
] <= 'F')
1740 solved
->lines
[i
] = aux
[i
] - 'A' + 10;
1742 *error
= "invalid char in aux";
1749 /* Try to solve with present (half-solved) state first: if there's no
1750 * solution from there go back to original state. */
1751 ret
= pearl_solve(currstate
->shared
->w
, currstate
->shared
->h
,
1752 currstate
->shared
->clues
, solved
->lines
,
1755 ret
= pearl_solve(state
->shared
->w
, state
->shared
->h
,
1756 state
->shared
->clues
, solved
->lines
,
1762 *error
= "Unable to find solution";
1765 move
= solve_for_diff(solved
, currstate
->lines
, solved
->lines
);
1773 static int game_can_format_as_text_now(const game_params
*params
)
1778 static char *game_text_format(const game_state
*state
)
1780 int w
= state
->shared
->w
, h
= state
->shared
->h
, cw
= 4, ch
= 2;
1781 int gw
= cw
*(w
-1) + 2, gh
= ch
*(h
-1) + 1, len
= gw
* gh
, r
, c
, j
;
1782 char *board
= snewn(len
+ 1, char);
1785 memset(board
, ' ', len
);
1787 for (r
= 0; r
< h
; ++r
) {
1788 for (c
= 0; c
< w
; ++c
) {
1789 int i
= r
*w
+ c
, cell
= r
*ch
*gw
+ c
*cw
;
1790 board
[cell
] = "+BW"[(unsigned char)state
->shared
->clues
[i
]];
1791 if (c
< w
- 1 && (state
->lines
[i
] & R
|| state
->lines
[i
+1] & L
))
1792 memset(board
+ cell
+ 1, '-', cw
- 1);
1793 if (r
< h
- 1 && (state
->lines
[i
] & D
|| state
->lines
[i
+w
] & U
))
1794 for (j
= 1; j
< ch
; ++j
) board
[cell
+ j
*gw
] = '|';
1795 if (c
< w
- 1 && (state
->marks
[i
] & R
|| state
->marks
[i
+1] & L
))
1796 board
[cell
+ cw
/2] = 'x';
1797 if (r
< h
- 1 && (state
->marks
[i
] & D
|| state
->marks
[i
+w
] & U
))
1798 board
[cell
+ (ch
/2 * gw
)] = 'x';
1801 for (j
= 0; j
< (r
== h
- 1 ? 1 : ch
); ++j
)
1802 board
[r
*ch
*gw
+ (gw
- 1) + j
*gw
] = '\n';
1810 int *dragcoords
; /* list of (y*w+x) coords in drag so far */
1811 int ndragcoords
; /* number of entries in dragcoords.
1812 * 0 = click but no drag yet. -1 = no drag at all */
1813 int clickx
, clicky
; /* pixel position of initial click */
1815 int curx
, cury
; /* grid position of keyboard cursor */
1816 int cursor_active
; /* TRUE iff cursor is shown */
1819 static game_ui
*new_ui(const game_state
*state
)
1821 game_ui
*ui
= snew(game_ui
);
1822 int sz
= state
->shared
->sz
;
1824 ui
->ndragcoords
= -1;
1825 ui
->dragcoords
= snewn(sz
, int);
1826 ui
->cursor_active
= FALSE
;
1827 ui
->curx
= ui
->cury
= 0;
1832 static void free_ui(game_ui
*ui
)
1834 sfree(ui
->dragcoords
);
1838 static char *encode_ui(const game_ui
*ui
)
1843 static void decode_ui(game_ui
*ui
, const char *encoding
)
1847 static void game_changed_state(game_ui
*ui
, const game_state
*oldstate
,
1848 const game_state
*newstate
)
1852 #define PREFERRED_TILE_SIZE 31
1853 #define HALFSZ (ds->halfsz)
1854 #define TILE_SIZE (ds->halfsz*2 + 1)
1856 #define BORDER ((get_gui_style() == GUI_LOOPY) ? (TILE_SIZE/8) : (TILE_SIZE/2))
1858 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1860 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
1861 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1862 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) )
1864 #define DS_ESHIFT 4 /* R/U/L/D shift, for error flags */
1865 #define DS_DSHIFT 8 /* R/U/L/D shift, for drag-in-progress flags */
1866 #define DS_MSHIFT 12 /* shift for no-line mark */
1868 #define DS_ERROR_CLUE (1 << 20)
1869 #define DS_FLASH (1 << 21)
1870 #define DS_CURSOR (1 << 22)
1872 enum { GUI_MASYU
, GUI_LOOPY
};
1874 static int get_gui_style(void)
1876 static int gui_style
= -1;
1878 if (gui_style
== -1) {
1879 char *env
= getenv("PEARL_GUI_LOOPY");
1880 if (env
&& (env
[0] == 'y' || env
[0] == 'Y'))
1881 gui_style
= GUI_LOOPY
;
1883 gui_style
= GUI_MASYU
;
1888 struct game_drawstate
{
1893 unsigned int *lflags
; /* size w*h */
1895 char *draglines
; /* size w*h; lines flipped by current drag */
1898 static void update_ui_drag(const game_state
*state
, game_ui
*ui
,
1901 int /* sz = state->shared->sz, */ w
= state
->shared
->w
;
1905 if (!INGRID(state
, gx
, gy
))
1906 return; /* square is outside grid */
1908 if (ui
->ndragcoords
< 0)
1909 return; /* drag not in progress anyway */
1913 lastpos
= ui
->dragcoords
[ui
->ndragcoords
> 0 ? ui
->ndragcoords
-1 : 0];
1915 return; /* same square as last visited one */
1917 /* Drag confirmed, if it wasn't already. */
1918 if (ui
->ndragcoords
== 0)
1919 ui
->ndragcoords
= 1;
1922 * Dragging the mouse into a square that's already been visited by
1923 * the drag path so far has the effect of truncating the path back
1924 * to that square, so a player can back out part of an uncommitted
1925 * drag without having to let go of the mouse.
1927 for (i
= 0; i
< ui
->ndragcoords
; i
++)
1928 if (pos
== ui
->dragcoords
[i
]) {
1929 ui
->ndragcoords
= i
+1;
1934 * Otherwise, dragging the mouse into a square that's a rook-move
1935 * away from the last one on the path extends the path.
1937 oy
= ui
->dragcoords
[ui
->ndragcoords
-1] / w
;
1938 ox
= ui
->dragcoords
[ui
->ndragcoords
-1] % w
;
1939 if (ox
== gx
|| oy
== gy
) {
1940 int dx
= (gx
< ox
? -1 : gx
> ox
? +1 : 0);
1941 int dy
= (gy
< oy
? -1 : gy
> oy
? +1 : 0);
1942 int dir
= (dy
>0 ? D
: dy
<0 ? U
: dx
>0 ? R
: L
);
1943 while (ox
!= gx
|| oy
!= gy
) {
1945 * If the drag attempts to cross a 'no line here' mark,
1946 * stop there. We physically don't allow the user to drag
1949 if (state
->marks
[oy
*w
+ox
] & dir
)
1953 ui
->dragcoords
[ui
->ndragcoords
++] = oy
* w
+ ox
;
1958 * Failing that, we do nothing at all: if the user has dragged
1959 * diagonally across the board, they'll just have to return the
1960 * mouse to the last known position and do whatever they meant to
1961 * do again, more slowly and clearly.
1966 * Routine shared between interpret_move and game_redraw to work out
1967 * the intended effect of a drag path on the grid.
1969 * Call it in a loop, like this:
1971 * int clearing = TRUE;
1972 * for (i = 0; i < ui->ndragcoords - 1; i++) {
1973 * int sx, sy, dx, dy, dir, oldstate, newstate;
1974 * interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
1975 * &dir, &oldstate, &newstate);
1977 * [do whatever is needed to handle the fact that the drag
1978 * wants the edge from sx,sy to dx,dy (heading in direction
1979 * 'dir' at the sx,sy end) to be changed from state oldstate
1980 * to state newstate, each of which equals either 0 or dir]
1983 static void interpret_ui_drag(const game_state
*state
, const game_ui
*ui
,
1984 int *clearing
, int i
, int *sx
, int *sy
,
1985 int *dx
, int *dy
, int *dir
,
1986 int *oldstate
, int *newstate
)
1988 int w
= state
->shared
->w
;
1989 int sp
= ui
->dragcoords
[i
], dp
= ui
->dragcoords
[i
+1];
1994 *dir
= (*dy
>*sy
? D
: *dy
<*sy
? U
: *dx
>*sx
? R
: L
);
1995 *oldstate
= state
->lines
[sp
] & *dir
;
1998 * The edge we've dragged over was previously
1999 * present. Set it to absent, unless we've already
2000 * stopped doing that.
2002 *newstate
= *clearing
? 0 : *dir
;
2005 * The edge we've dragged over was previously
2006 * absent. Set it to present, and cancel the
2007 * 'clearing' flag so that all subsequent edges in
2008 * the drag are set rather than cleared.
2015 static char *mark_in_direction(const game_state
*state
, int x
, int y
, int dir
,
2016 int primary
, char *buf
)
2018 int w
= state
->shared
->w
/*, h = state->shared->h, sz = state->shared->sz */;
2019 int x2
= x
+ DX(dir
);
2020 int y2
= y
+ DY(dir
);
2023 char ch
= primary
? 'F' : 'M', *other
;
2025 if (!INGRID(state
, x
, y
) || !INGRID(state
, x2
, y2
)) return "";
2027 /* disallow laying a mark over a line, or vice versa. */
2028 other
= primary
? state
->marks
: state
->lines
;
2029 if (other
[y
*w
+x
] & dir
|| other
[y2
*w
+x2
] & dir2
) return "";
2031 sprintf(buf
, "%c%d,%d,%d;%c%d,%d,%d", ch
, dir
, x
, y
, ch
, dir2
, x2
, y2
);
2035 #define KEY_DIRECTION(btn) (\
2036 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
2037 (btn) == CURSOR_LEFT ? L : R)
2039 static char *interpret_move(const game_state
*state
, game_ui
*ui
,
2040 const game_drawstate
*ds
,
2041 int x
, int y
, int button
)
2043 int w
= state
->shared
->w
, h
= state
->shared
->h
/*, sz = state->shared->sz */;
2044 int gx
= FROMCOORD(x
), gy
= FROMCOORD(y
), i
;
2045 int release
= FALSE
;
2048 int shift
= button
& MOD_SHFT
, control
= button
& MOD_CTRL
;
2049 button
&= ~MOD_MASK
;
2051 if (IS_MOUSE_DOWN(button
)) {
2052 ui
->cursor_active
= FALSE
;
2054 if (!INGRID(state
, gx
, gy
)) {
2055 ui
->ndragcoords
= -1;
2059 ui
->clickx
= x
; ui
->clicky
= y
;
2060 ui
->dragcoords
[0] = gy
* w
+ gx
;
2061 ui
->ndragcoords
= 0; /* will be 1 once drag is confirmed */
2066 if (button
== LEFT_DRAG
&& ui
->ndragcoords
>= 0) {
2067 update_ui_drag(state
, ui
, gx
, gy
);
2071 if (IS_MOUSE_RELEASE(button
)) release
= TRUE
;
2073 if (IS_CURSOR_MOVE(button
)) {
2074 if (!ui
->cursor_active
) {
2075 ui
->cursor_active
= TRUE
;
2076 } else if (control
| shift
) {
2078 if (ui
->ndragcoords
> 0) return NULL
;
2079 ui
->ndragcoords
= -1;
2080 move
= mark_in_direction(state
, ui
->curx
, ui
->cury
,
2081 KEY_DIRECTION(button
), control
, tmpbuf
);
2082 if (control
&& !shift
&& *move
)
2083 move_cursor(button
, &ui
->curx
, &ui
->cury
, w
, h
, FALSE
);
2086 move_cursor(button
, &ui
->curx
, &ui
->cury
, w
, h
, FALSE
);
2087 if (ui
->ndragcoords
>= 0)
2088 update_ui_drag(state
, ui
, ui
->curx
, ui
->cury
);
2093 if (IS_CURSOR_SELECT(button
)) {
2094 if (!ui
->cursor_active
) {
2095 ui
->cursor_active
= TRUE
;
2097 } else if (button
== CURSOR_SELECT
) {
2098 if (ui
->ndragcoords
== -1) {
2099 ui
->ndragcoords
= 0;
2100 ui
->dragcoords
[0] = ui
->cury
* w
+ ui
->curx
;
2101 ui
->clickx
= CENTERED_COORD(ui
->curx
);
2102 ui
->clicky
= CENTERED_COORD(ui
->cury
);
2104 } else release
= TRUE
;
2105 } else if (button
== CURSOR_SELECT2
&& ui
->ndragcoords
>= 0) {
2106 ui
->ndragcoords
= -1;
2111 if (button
== 27 || button
== '\b') {
2112 ui
->ndragcoords
= -1;
2117 if (ui
->ndragcoords
> 0) {
2118 /* End of a drag: process the cached line data. */
2119 int buflen
= 0, bufsize
= 256, tmplen
;
2121 const char *sep
= "";
2122 int clearing
= TRUE
;
2124 for (i
= 0; i
< ui
->ndragcoords
- 1; i
++) {
2125 int sx
, sy
, dx
, dy
, dir
, oldstate
, newstate
;
2126 interpret_ui_drag(state
, ui
, &clearing
, i
, &sx
, &sy
, &dx
, &dy
,
2127 &dir
, &oldstate
, &newstate
);
2129 if (oldstate
!= newstate
) {
2130 if (!buf
) buf
= snewn(bufsize
, char);
2131 tmplen
= sprintf(tmpbuf
, "%sF%d,%d,%d;F%d,%d,%d", sep
,
2132 dir
, sx
, sy
, F(dir
), dx
, dy
);
2133 if (buflen
+ tmplen
>= bufsize
) {
2134 bufsize
= (buflen
+ tmplen
) * 5 / 4 + 256;
2135 buf
= sresize(buf
, bufsize
, char);
2137 strcpy(buf
+ buflen
, tmpbuf
);
2143 ui
->ndragcoords
= -1;
2145 return buf
? buf
: "";
2146 } else if (ui
->ndragcoords
== 0) {
2147 /* Click (or tiny drag). Work out which edge we were
2151 ui
->ndragcoords
= -1;
2154 * We process clicks based on the mouse-down location,
2155 * because that's more natural for a user to carefully
2156 * control than the mouse-up.
2163 cx
= CENTERED_COORD(gx
);
2164 cy
= CENTERED_COORD(gy
);
2166 if (!INGRID(state
, gx
, gy
)) return "";
2168 if (max(abs(x
-cx
),abs(y
-cy
)) < TILE_SIZE
/4) {
2169 /* TODO closer to centre of grid: process as a cell click not an edge click. */
2174 if (abs(x
-cx
) < abs(y
-cy
)) {
2175 /* Closest to top/bottom edge. */
2176 direction
= (y
< cy
) ? U
: D
;
2178 /* Closest to left/right edge. */
2179 direction
= (x
< cx
) ? L
: R
;
2181 return mark_in_direction(state
, gx
, gy
, direction
,
2182 (button
== LEFT_RELEASE
), tmpbuf
);
2187 if (button
== 'H' || button
== 'h')
2193 static game_state
*execute_move(const game_state
*state
, const char *move
)
2195 int w
= state
->shared
->w
, h
= state
->shared
->h
;
2198 game_state
*ret
= dup_game(state
);
2200 debug(("move: %s\n", move
));
2205 ret
->used_solve
= TRUE
;
2207 } else if (c
== 'L' || c
== 'N' || c
== 'R' || c
== 'F' || c
== 'M') {
2208 /* 'line' or 'noline' or 'replace' or 'flip' or 'mark' */
2210 if (sscanf(move
, "%d,%d,%d%n", &l
, &x
, &y
, &n
) != 3)
2212 if (!INGRID(state
, x
, y
)) goto badmove
;
2213 if (l
< 0 || l
> 15) goto badmove
;
2216 ret
->lines
[y
*w
+ x
] |= (char)l
;
2218 ret
->lines
[y
*w
+ x
] &= ~((char)l
);
2219 else if (c
== 'R') {
2220 ret
->lines
[y
*w
+ x
] = (char)l
;
2221 ret
->marks
[y
*w
+ x
] &= ~((char)l
); /* erase marks too */
2222 } else if (c
== 'F')
2223 ret
->lines
[y
*w
+ x
] ^= (char)l
;
2225 ret
->marks
[y
*w
+ x
] ^= (char)l
;
2228 * If we ended up trying to lay a line _over_ a mark,
2229 * that's a failed move: interpret_move() should have
2230 * ensured we never received a move string like that in
2233 if ((ret
->lines
[y
*w
+ x
] & (char)l
) &&
2234 (ret
->marks
[y
*w
+ x
] & (char)l
))
2238 } else if (strcmp(move
, "H") == 0) {
2239 pearl_solve(ret
->shared
->w
, ret
->shared
->h
,
2240 ret
->shared
->clues
, ret
->lines
, DIFFCOUNT
, TRUE
);
2241 for (n
= 0; n
< w
*h
; n
++)
2242 ret
->marks
[n
] &= ~ret
->lines
[n
]; /* erase marks too */
2253 check_completion(ret
, TRUE
);
2262 /* ----------------------------------------------------------------------
2266 #define FLASH_TIME 0.5F
2268 static void game_compute_size(const game_params
*params
, int tilesize
,
2271 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2272 struct { int halfsz
; } ads
, *ds
= &ads
;
2273 ads
.halfsz
= (tilesize
-1)/2;
2275 *x
= (params
->w
) * TILE_SIZE
+ 2 * BORDER
;
2276 *y
= (params
->h
) * TILE_SIZE
+ 2 * BORDER
;
2279 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2280 const game_params
*params
, int tilesize
)
2282 ds
->halfsz
= (tilesize
-1)/2;
2285 static float *game_colours(frontend
*fe
, int *ncolours
)
2287 float *ret
= snewn(3 * NCOLOURS
, float);
2290 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
2292 for (i
= 0; i
< 3; i
++) {
2293 ret
[COL_BLACK
* 3 + i
] = 0.0F
;
2294 ret
[COL_WHITE
* 3 + i
] = 1.0F
;
2295 ret
[COL_GRID
* 3 + i
] = 0.4F
;
2298 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
2299 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
2300 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
2302 ret
[COL_DRAGON
* 3 + 0] = 0.0F
;
2303 ret
[COL_DRAGON
* 3 + 1] = 0.0F
;
2304 ret
[COL_DRAGON
* 3 + 2] = 1.0F
;
2306 ret
[COL_DRAGOFF
* 3 + 0] = 0.8F
;
2307 ret
[COL_DRAGOFF
* 3 + 1] = 0.8F
;
2308 ret
[COL_DRAGOFF
* 3 + 2] = 1.0F
;
2310 ret
[COL_FLASH
* 3 + 0] = 1.0F
;
2311 ret
[COL_FLASH
* 3 + 1] = 1.0F
;
2312 ret
[COL_FLASH
* 3 + 2] = 1.0F
;
2314 *ncolours
= NCOLOURS
;
2319 static game_drawstate
*game_new_drawstate(drawing
*dr
, const game_state
*state
)
2321 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2325 ds
->started
= FALSE
;
2327 ds
->w
= state
->shared
->w
;
2328 ds
->h
= state
->shared
->h
;
2329 ds
->sz
= state
->shared
->sz
;
2330 ds
->lflags
= snewn(ds
->sz
, unsigned int);
2331 for (i
= 0; i
< ds
->sz
; i
++)
2334 ds
->draglines
= snewn(ds
->sz
, char);
2339 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2341 sfree(ds
->draglines
);
2346 static void draw_lines_specific(drawing
*dr
, game_drawstate
*ds
,
2347 int x
, int y
, unsigned int lflags
,
2348 unsigned int shift
, int c
)
2350 int ox
= COORD(x
), oy
= COORD(y
);
2351 int t2
= HALFSZ
, t16
= HALFSZ
/4;
2352 int cx
= ox
+ t2
, cy
= oy
+ t2
;
2355 /* Draw each of the four directions, where laid (or error, or drag, etc.) */
2356 for (d
= 1; d
< 16; d
*= 2) {
2357 int xoff
= t2
* DX(d
), yoff
= t2
* DY(d
);
2358 int xnudge
= abs(t16
* DX(C(d
))), ynudge
= abs(t16
* DY(C(d
)));
2360 if ((lflags
>> shift
) & d
) {
2361 int lx
= cx
+ ((xoff
< 0) ? xoff
: 0) - xnudge
;
2362 int ly
= cy
+ ((yoff
< 0) ? yoff
: 0) - ynudge
;
2364 if (c
== COL_DRAGOFF
&& !(lflags
& d
))
2366 if (c
== COL_DRAGON
&& (lflags
& d
))
2369 draw_rect(dr
, lx
, ly
,
2370 abs(xoff
)+2*xnudge
+1,
2371 abs(yoff
)+2*ynudge
+1, c
);
2373 draw_rect(dr
, cx
- t16
, cy
- t16
, 2*t16
+1, 2*t16
+1, c
);
2378 static void draw_square(drawing
*dr
, game_drawstate
*ds
, const game_ui
*ui
,
2379 int x
, int y
, unsigned int lflags
, char clue
)
2381 int ox
= COORD(x
), oy
= COORD(y
);
2382 int t2
= HALFSZ
, t16
= HALFSZ
/4;
2383 int cx
= ox
+ t2
, cy
= oy
+ t2
;
2388 /* Clip to the grid square. */
2389 clip(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2391 /* Clear the square. */
2392 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
,
2393 (lflags
& DS_CURSOR
) ?
2394 COL_CURSOR_BACKGROUND
: COL_BACKGROUND
);
2397 if (get_gui_style() == GUI_LOOPY
) {
2398 /* Draw small dot, underneath any lines. */
2399 draw_circle(dr
, cx
, cy
, t16
, COL_GRID
, COL_GRID
);
2401 /* Draw outline of grid square */
2402 draw_line(dr
, ox
, oy
, COORD(x
+1), oy
, COL_GRID
);
2403 draw_line(dr
, ox
, oy
, ox
, COORD(y
+1), COL_GRID
);
2406 /* Draw grid: either thin gridlines, or no-line marks.
2407 * We draw these first because the thick laid lines should be on top. */
2408 for (d
= 1; d
< 16; d
*= 2) {
2409 int xoff
= t2
* DX(d
), yoff
= t2
* DY(d
);
2411 if ((x
== 0 && d
== L
) ||
2412 (y
== 0 && d
== U
) ||
2413 (x
== ds
->w
-1 && d
== R
) ||
2414 (y
== ds
->h
-1 && d
== D
))
2415 continue; /* no gridlines out to the border. */
2417 if ((lflags
>> DS_MSHIFT
) & d
) {
2418 /* either a no-line mark ... */
2419 int mx
= cx
+ xoff
, my
= cy
+ yoff
, msz
= t16
;
2421 draw_line(dr
, mx
-msz
, my
-msz
, mx
+msz
, my
+msz
, COL_BLACK
);
2422 draw_line(dr
, mx
-msz
, my
+msz
, mx
+msz
, my
-msz
, COL_BLACK
);
2424 if (get_gui_style() == GUI_LOOPY
) {
2425 /* draw grid lines connecting centre of cells */
2426 draw_line(dr
, cx
, cy
, cx
+xoff
, cy
+yoff
, COL_GRID
);
2431 /* Draw each of the four directions, where laid (or error, or drag, etc.)
2432 * Order is important here, specifically for the eventual colours of the
2433 * exposed end caps. */
2434 draw_lines_specific(dr
, ds
, x
, y
, lflags
, 0,
2435 (lflags
& DS_FLASH
? COL_FLASH
: COL_BLACK
));
2436 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_ESHIFT
, COL_ERROR
);
2437 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_DSHIFT
, COL_DRAGOFF
);
2438 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_DSHIFT
, COL_DRAGON
);
2440 /* Draw a clue, if present */
2441 if (clue
!= NOCLUE
) {
2442 int c
= (lflags
& DS_FLASH
) ? COL_FLASH
:
2443 (clue
== STRAIGHT
) ? COL_WHITE
: COL_BLACK
;
2445 if (lflags
& DS_ERROR_CLUE
) /* draw a bigger 'error' clue circle. */
2446 draw_circle(dr
, cx
, cy
, TILE_SIZE
*3/8, COL_ERROR
, COL_ERROR
);
2448 draw_circle(dr
, cx
, cy
, TILE_SIZE
/4, c
, COL_BLACK
);
2452 draw_update(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2455 static void game_redraw(drawing
*dr
, game_drawstate
*ds
,
2456 const game_state
*oldstate
, const game_state
*state
,
2457 int dir
, const game_ui
*ui
,
2458 float animtime
, float flashtime
)
2460 int w
= state
->shared
->w
, h
= state
->shared
->h
, sz
= state
->shared
->sz
;
2461 int x
, y
, force
= 0, flashing
= 0;
2465 * The initial contents of the window are not guaranteed and
2466 * can vary with front ends. To be on the safe side, all games
2467 * should start by drawing a big background-colour rectangle
2468 * covering the whole window.
2470 draw_rect(dr
, 0, 0, w
*TILE_SIZE
+ 2*BORDER
, h
*TILE_SIZE
+ 2*BORDER
,
2473 if (get_gui_style() == GUI_MASYU
) {
2475 * Smaller black rectangle which is the main grid.
2477 draw_rect(dr
, BORDER
- BORDER_WIDTH
, BORDER
- BORDER_WIDTH
,
2478 w
*TILE_SIZE
+ 2*BORDER_WIDTH
+ 1,
2479 h
*TILE_SIZE
+ 2*BORDER_WIDTH
+ 1,
2483 draw_update(dr
, 0, 0, w
*TILE_SIZE
+ 2*BORDER
, h
*TILE_SIZE
+ 2*BORDER
);
2489 if (flashtime
> 0 &&
2490 (flashtime
<= FLASH_TIME
/3 ||
2491 flashtime
>= FLASH_TIME
*2/3))
2492 flashing
= DS_FLASH
;
2494 memset(ds
->draglines
, 0, sz
);
2495 if (ui
->ndragcoords
> 0) {
2496 int i
, clearing
= TRUE
;
2497 for (i
= 0; i
< ui
->ndragcoords
- 1; i
++) {
2498 int sx
, sy
, dx
, dy
, dir
, oldstate
, newstate
;
2499 interpret_ui_drag(state
, ui
, &clearing
, i
, &sx
, &sy
, &dx
, &dy
,
2500 &dir
, &oldstate
, &newstate
);
2501 ds
->draglines
[sy
*w
+sx
] ^= (oldstate
^ newstate
);
2502 ds
->draglines
[dy
*w
+dx
] ^= (F(oldstate
) ^ F(newstate
));
2506 for (x
= 0; x
< w
; x
++) {
2507 for (y
= 0; y
< h
; y
++) {
2508 unsigned int f
= (unsigned int)state
->lines
[y
*w
+x
];
2509 unsigned int eline
= (unsigned int)(state
->errors
[y
*w
+x
] & (R
|U
|L
|D
));
2511 f
|= eline
<< DS_ESHIFT
;
2512 f
|= ((unsigned int)ds
->draglines
[y
*w
+x
]) << DS_DSHIFT
;
2513 f
|= ((unsigned int)state
->marks
[y
*w
+x
]) << DS_MSHIFT
;
2515 if (state
->errors
[y
*w
+x
] & ERROR_CLUE
)
2520 if (ui
->cursor_active
&& x
== ui
->curx
&& y
== ui
->cury
)
2523 if (f
!= ds
->lflags
[y
*w
+x
] || force
) {
2524 ds
->lflags
[y
*w
+x
] = f
;
2525 draw_square(dr
, ds
, ui
, x
, y
, f
, state
->shared
->clues
[y
*w
+x
]);
2531 static float game_anim_length(const game_state
*oldstate
,
2532 const game_state
*newstate
, int dir
, game_ui
*ui
)
2537 static float game_flash_length(const game_state
*oldstate
,
2538 const game_state
*newstate
, int dir
, game_ui
*ui
)
2540 if (!oldstate
->completed
&& newstate
->completed
&&
2541 !oldstate
->used_solve
&& !newstate
->used_solve
)
2547 static int game_status(const game_state
*state
)
2549 return state
->completed
? +1 : 0;
2552 static int game_timing_state(const game_state
*state
, game_ui
*ui
)
2557 static void game_print_size(const game_params
*params
, float *x
, float *y
)
2562 * I'll use 6mm squares by default.
2564 game_compute_size(params
, 600, &pw
, &ph
);
2569 static void game_print(drawing
*dr
, const game_state
*state
, int tilesize
)
2571 int w
= state
->shared
->w
, h
= state
->shared
->h
, x
, y
;
2572 int black
= print_mono_colour(dr
, 0);
2573 int white
= print_mono_colour(dr
, 1);
2575 /* No GUI_LOOPY here: only use the familiar masyu style. */
2577 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2578 game_drawstate
*ds
= game_new_drawstate(dr
, state
);
2579 game_set_size(dr
, ds
, NULL
, tilesize
);
2581 /* Draw grid outlines (black). */
2582 for (x
= 0; x
<= w
; x
++)
2583 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(h
), black
);
2584 for (y
= 0; y
<= h
; y
++)
2585 draw_line(dr
, COORD(0), COORD(y
), COORD(w
), COORD(y
), black
);
2587 for (x
= 0; x
< w
; x
++) {
2588 for (y
= 0; y
< h
; y
++) {
2589 int cx
= COORD(x
) + HALFSZ
, cy
= COORD(y
) + HALFSZ
;
2590 int clue
= state
->shared
->clues
[y
*w
+x
];
2592 draw_lines_specific(dr
, ds
, x
, y
, state
->lines
[y
*w
+x
], 0, black
);
2594 if (clue
!= NOCLUE
) {
2595 int c
= (clue
== CORNER
) ? black
: white
;
2596 draw_circle(dr
, cx
, cy
, TILE_SIZE
/4, c
, black
);
2601 game_free_drawstate(dr
, ds
);
2605 #define thegame pearl
2608 const struct game thegame
= {
2609 "Pearl", "games.pearl", "pearl",
2611 game_fetch_preset
, NULL
,
2616 TRUE
, game_configure
, custom_params
,
2624 TRUE
, game_can_format_as_text_now
, game_text_format
,
2632 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
2635 game_free_drawstate
,
2640 TRUE
, FALSE
, game_print_size
, game_print
,
2641 FALSE
, /* wants_statusbar */
2642 FALSE
, game_timing_state
,
2646 #ifdef STANDALONE_SOLVER
2651 const char *quis
= NULL
;
2653 static void usage(FILE *out
) {
2654 fprintf(out
, "usage: %s <params>\n", quis
);
2657 static void pnum(int n
, int ntot
, const char *desc
)
2659 printf("%2.1f%% (%d) %s", (double)n
*100.0 / (double)ntot
, n
, desc
);
2662 static void start_soak(game_params
*p
, random_state
*rs
, int nsecs
)
2664 time_t tt_start
, tt_now
, tt_last
;
2665 int n
= 0, nsolved
= 0, nimpossible
= 0, ret
;
2668 tt_start
= tt_last
= time(NULL
);
2670 /* Currently this generates puzzles of any difficulty (trying to solve it
2671 * on the maximum difficulty level and not checking it's not too easy). */
2672 printf("Soak-testing a %dx%d grid (any difficulty)", p
->w
, p
->h
);
2673 if (nsecs
> 0) printf(" for %d seconds", nsecs
);
2678 grid
= snewn(p
->w
*p
->h
, char);
2679 clues
= snewn(p
->w
*p
->h
, char);
2682 n
+= new_clues(p
, rs
, clues
, grid
); /* should be 1, with nosolve */
2684 ret
= pearl_solve(p
->w
, p
->h
, clues
, grid
, DIFF_TRICKY
, FALSE
);
2685 if (ret
<= 0) nimpossible
++;
2686 if (ret
== 1) nsolved
++;
2688 tt_now
= time(NULL
);
2689 if (tt_now
> tt_last
) {
2692 printf("%d total, %3.1f/s, ",
2693 n
, (double)n
/ ((double)tt_now
- tt_start
));
2694 pnum(nsolved
, n
, "solved"); printf(", ");
2695 printf("%3.1f/s", (double)nsolved
/ ((double)tt_now
- tt_start
));
2696 if (nimpossible
> 0)
2697 pnum(nimpossible
, n
, "impossible");
2700 if (nsecs
> 0 && (tt_now
- tt_start
) > nsecs
) {
2710 int main(int argc
, const char *argv
[])
2712 game_params
*p
= NULL
;
2713 random_state
*rs
= NULL
;
2714 time_t seed
= time(NULL
);
2715 char *id
= NULL
, *err
;
2717 setvbuf(stdout
, NULL
, _IONBF
, 0);
2721 while (--argc
> 0) {
2722 char *p
= (char*)(*++argv
);
2723 if (!strcmp(p
, "-e") || !strcmp(p
, "--seed")) {
2724 seed
= atoi(*++argv
);
2726 } else if (*p
== '-') {
2727 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
2735 rs
= random_new((void*)&seed
, sizeof(time_t));
2736 p
= default_params();
2739 if (strchr(id
, ':')) {
2740 fprintf(stderr
, "soak takes params only.\n");
2744 decode_params(p
, id
);
2745 err
= validate_params(p
, 1);
2747 fprintf(stderr
, "%s: %s", argv
[0], err
);
2751 start_soak(p
, rs
, 0); /* run forever */
2755 for (i
= 5; i
<= 12; i
++) {
2757 start_soak(p
, rs
, 5);
2770 /* vim: set shiftwidth=4 tabstop=8: */