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
;
133 int loop_length
; /* filled in by check_completion when complete. */
136 #define DEFAULT_PRESET 3
138 static const struct game_params pearl_presets
[] = {
144 {10, 10, DIFF_TRICKY
},
146 {12, 8, DIFF_TRICKY
},
149 static game_params
*default_params(void)
151 game_params
*ret
= snew(game_params
);
153 *ret
= pearl_presets
[DEFAULT_PRESET
];
154 ret
->nosolve
= FALSE
;
159 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
164 if (i
< 0 || i
>= lenof(pearl_presets
)) return FALSE
;
166 ret
= default_params();
167 *ret
= pearl_presets
[i
]; /* struct copy */
170 sprintf(buf
, "%dx%d %s",
171 pearl_presets
[i
].w
, pearl_presets
[i
].h
,
172 pearl_diffnames
[pearl_presets
[i
].difficulty
]);
178 static void free_params(game_params
*params
)
183 static game_params
*dup_params(game_params
*params
)
185 game_params
*ret
= snew(game_params
);
186 *ret
= *params
; /* structure copy */
190 static void decode_params(game_params
*ret
, char const *string
)
192 ret
->w
= ret
->h
= atoi(string
);
193 while (*string
&& isdigit((unsigned char) *string
)) ++string
;
194 if (*string
== 'x') {
196 ret
->h
= atoi(string
);
197 while (*string
&& isdigit((unsigned char)*string
)) string
++;
200 ret
->difficulty
= DIFF_EASY
;
201 if (*string
== 'd') {
204 for (i
= 0; i
< DIFFCOUNT
; i
++)
205 if (*string
== pearl_diffchars
[i
])
207 if (*string
) string
++;
210 ret
->nosolve
= FALSE
;
211 if (*string
== 'n') {
217 static char *encode_params(game_params
*params
, int full
)
220 sprintf(buf
, "%dx%d", params
->w
, params
->h
);
222 sprintf(buf
+ strlen(buf
), "d%c%s",
223 pearl_diffchars
[params
->difficulty
],
224 params
->nosolve ?
"n" : "");
228 static config_item
*game_configure(game_params
*params
)
233 ret
= snewn(5, config_item
);
235 ret
[0].name
= "Width";
236 ret
[0].type
= C_STRING
;
237 sprintf(buf
, "%d", params
->w
);
238 ret
[0].sval
= dupstr(buf
);
241 ret
[1].name
= "Height";
242 ret
[1].type
= C_STRING
;
243 sprintf(buf
, "%d", params
->h
);
244 ret
[1].sval
= dupstr(buf
);
247 ret
[2].name
= "Difficulty";
248 ret
[2].type
= C_CHOICES
;
249 ret
[2].sval
= DIFFCONFIG
;
250 ret
[2].ival
= params
->difficulty
;
252 ret
[3].name
= "Allow unsoluble";
253 ret
[3].type
= C_BOOLEAN
;
255 ret
[3].ival
= params
->nosolve
;
265 static game_params
*custom_params(config_item
*cfg
)
267 game_params
*ret
= snew(game_params
);
269 ret
->w
= atoi(cfg
[0].sval
);
270 ret
->h
= atoi(cfg
[1].sval
);
271 ret
->difficulty
= cfg
[2].ival
;
272 ret
->nosolve
= cfg
[3].ival
;
277 static char *validate_params(game_params
*params
, int full
)
279 if (params
->w
< 5) return "Width must be at least five";
280 if (params
->h
< 5) return "Height must be at least five";
281 if (params
->difficulty
< 0 || params
->difficulty
>= DIFFCOUNT
)
282 return "Unknown difficulty level";
287 /* ----------------------------------------------------------------------
291 int pearl_solve(int w
, int h
, char *clues
, char *result
,
292 int difficulty
, int partial
)
294 int W
= 2*w
+1, H
= 2*h
+1;
301 * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature
302 * of the square (x,y), as a logical OR of bitfields.
304 * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates
305 * whether the horizontal edge between (x,y) and (x+1,y) is
306 * connected (1), disconnected (2) or unknown (3).
308 * workspace[(2*y+1)*W+(2*x)], indicates the same about the
309 * vertical edge between (x,y) and (x,y+1).
311 * Initially, every square is considered capable of being in
312 * any of the seven possible states (two straights, four
313 * corners and empty), except those corresponding to clue
314 * squares which are more restricted.
316 * Initially, all edges are unknown, except the ones around the
317 * grid border which are known to be disconnected.
319 workspace
= snewn(W
*H
, short);
320 for (x
= 0; x
< W
*H
; x
++)
323 for (y
= 0; y
< h
; y
++)
324 for (x
= 0; x
< w
; x
++)
325 switch (clues
[y
*w
+x
]) {
327 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLU
|bLD
|bRU
|bRD
;
330 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLR
|bUD
;
333 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLR
|bUD
|bLU
|bLD
|bRU
|bRD
|bBLANK
;
336 /* Horizontal edges */
337 for (y
= 0; y
<= h
; y
++)
338 for (x
= 0; x
< w
; x
++)
339 workspace
[(2*y
)*W
+(2*x
+1)] = (y
==0 || y
==h ?
2 : 3);
341 for (y
= 0; y
< h
; y
++)
342 for (x
= 0; x
<= w
; x
++)
343 workspace
[(2*y
+1)*W
+(2*x
)] = (x
==0 || x
==w ?
2 : 3);
346 * We maintain a dsf of connected squares, together with a
347 * count of the size of each equivalence class.
349 dsf
= snewn(w
*h
, int);
350 dsfsize
= snewn(w
*h
, int);
353 * Now repeatedly try to find something we can do.
356 int done_something
= FALSE
;
358 #ifdef SOLVER_DIAGNOSTICS
359 for (y
= 0; y
< H
; y
++) {
360 for (x
= 0; x
< W
; x
++)
361 printf("%*x", (x
&1) ?
5 : 2, workspace
[y
*W
+x
]);
367 * Go through the square state words, and discard any
368 * square state which is inconsistent with known facts
369 * about the edges around the square.
371 for (y
= 0; y
< h
; y
++)
372 for (x
= 0; x
< w
; x
++) {
373 for (b
= 0; b
< 0xD; b
++)
374 if (workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<b
)) {
376 * If any edge of this square is known to
377 * be connected when state b would require
378 * it disconnected, or vice versa, discard
381 for (d
= 1; d
<= 8; d
+= d
) {
382 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
383 if (workspace
[ey
*W
+ex
] ==
385 workspace
[(2*y
+1)*W
+(2*x
+1)] &= ~(1<<b
);
386 #ifdef SOLVER_DIAGNOSTICS
387 printf("edge (%d,%d)-(%d,%d) rules out state"
388 " %d for square (%d,%d)\n",
389 ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2,
392 done_something
= TRUE
;
399 * Consistency check: each square must have at
400 * least one state left!
402 if (!workspace
[(2*y
+1)*W
+(2*x
+1)]) {
403 #ifdef SOLVER_DIAGNOSTICS
404 printf("edge check at (%d,%d): inconsistency\n", x
, y
);
412 * Now go through the states array again, and nail down any
413 * unknown edge if one of its neighbouring squares makes it
416 for (y
= 0; y
< h
; y
++)
417 for (x
= 0; x
< w
; x
++) {
418 int edgeor
= 0, edgeand
= 15;
420 for (b
= 0; b
< 0xD; b
++)
421 if (workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<b
)) {
427 * Now any bit clear in edgeor marks a disconnected
428 * edge, and any bit set in edgeand marks a
432 /* First check consistency: neither bit is both! */
433 if (edgeand
& ~edgeor
) {
434 #ifdef SOLVER_DIAGNOSTICS
435 printf("square check at (%d,%d): inconsistency\n", x
, y
);
441 for (d
= 1; d
<= 8; d
+= d
) {
442 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
444 if (!(edgeor
& d
) && workspace
[ey
*W
+ex
] == 3) {
445 workspace
[ey
*W
+ex
] = 2;
446 done_something
= TRUE
;
447 #ifdef SOLVER_DIAGNOSTICS
448 printf("possible states of square (%d,%d) force edge"
449 " (%d,%d)-(%d,%d) to be disconnected\n",
450 x
, y
, ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
452 } else if ((edgeand
& d
) && workspace
[ey
*W
+ex
] == 3) {
453 workspace
[ey
*W
+ex
] = 1;
454 done_something
= TRUE
;
455 #ifdef SOLVER_DIAGNOSTICS
456 printf("possible states of square (%d,%d) force edge"
457 " (%d,%d)-(%d,%d) to be connected\n",
458 x
, y
, ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
468 * Now for longer-range clue-based deductions (using the
469 * rules that a corner clue must connect to two straight
470 * squares, and a straight clue must connect to at least
471 * one corner square).
473 for (y
= 0; y
< h
; y
++)
474 for (x
= 0; x
< w
; x
++)
475 switch (clues
[y
*w
+x
]) {
477 for (d
= 1; d
<= 8; d
+= d
) {
478 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
479 int fx
= ex
+ DX(d
), fy
= ey
+ DY(d
);
482 if (workspace
[ey
*W
+ex
] == 1) {
484 * If a corner clue is connected on any
485 * edge, then we can immediately nail
486 * down the square beyond that edge as
487 * being a straight in the appropriate
490 if (workspace
[fy
*W
+fx
] != (1<<type
)) {
491 workspace
[fy
*W
+fx
] = (1<<type
);
492 done_something
= TRUE
;
493 #ifdef SOLVER_DIAGNOSTICS
494 printf("corner clue at (%d,%d) forces square "
495 "(%d,%d) into state %d\n", x
, y
,
500 } else if (workspace
[ey
*W
+ex
] == 3) {
502 * Conversely, if a corner clue is
503 * separated by an unknown edge from a
504 * square which _cannot_ be a straight
505 * in the appropriate direction, we can
506 * mark that edge as disconnected.
508 if (!(workspace
[fy
*W
+fx
] & (1<<type
))) {
509 workspace
[ey
*W
+ex
] = 2;
510 done_something
= TRUE
;
511 #ifdef SOLVER_DIAGNOSTICS
512 printf("corner clue at (%d,%d), plus square "
513 "(%d,%d) not being state %d, "
514 "disconnects edge (%d,%d)-(%d,%d)\n",
515 x
, y
, fx
/2, fy
/2, type
,
516 ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
526 * If a straight clue is between two squares
527 * neither of which is capable of being a
528 * corner connected to it, then the straight
529 * clue cannot point in that direction.
531 for (d
= 1; d
<= 2; d
+= d
) {
532 int fx
= 2*x
+1 + 2*DX(d
), fy
= 2*y
+1 + 2*DY(d
);
533 int gx
= 2*x
+1 - 2*DX(d
), gy
= 2*y
+1 - 2*DY(d
);
536 if (!(workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<type
)))
539 if (!(workspace
[fy
*W
+fx
] & ((1<<(F(d
)|A(d
))) |
540 (1<<(F(d
)|C(d
))))) &&
541 !(workspace
[gy
*W
+gx
] & ((1<<( d
|A(d
))) |
543 workspace
[(2*y
+1)*W
+(2*x
+1)] &= ~(1<<type
);
544 done_something
= TRUE
;
545 #ifdef SOLVER_DIAGNOSTICS
546 printf("straight clue at (%d,%d) cannot corner at "
547 "(%d,%d) or (%d,%d) so is not state %d\n",
548 x
, y
, fx
/2, fy
/2, gx
/2, gy
/2, type
);
555 * If a straight clue with known direction is
556 * connected on one side to a known straight,
557 * then on the other side it must be a corner.
559 for (d
= 1; d
<= 8; d
+= d
) {
560 int fx
= 2*x
+1 + 2*DX(d
), fy
= 2*y
+1 + 2*DY(d
);
561 int gx
= 2*x
+1 - 2*DX(d
), gy
= 2*y
+1 - 2*DY(d
);
564 if (workspace
[(2*y
+1)*W
+(2*x
+1)] != (1<<type
))
567 if (!(workspace
[fy
*W
+fx
] &~ (bLR
|bUD
)) &&
568 (workspace
[gy
*W
+gx
] &~ (bLU
|bLD
|bRU
|bRD
))) {
569 workspace
[gy
*W
+gx
] &= (bLU
|bLD
|bRU
|bRD
);
570 done_something
= TRUE
;
571 #ifdef SOLVER_DIAGNOSTICS
572 printf("straight clue at (%d,%d) connecting to "
573 "straight at (%d,%d) makes (%d,%d) a "
574 "corner\n", x
, y
, fx
/2, fy
/2, gx
/2, gy
/2);
586 * Now detect shortcut loops.
590 int nonblanks
, loopclass
;
593 for (x
= 0; x
< w
*h
; x
++)
597 * First go through the edge entries and update the dsf
598 * of which squares are connected to which others. We
599 * also track the number of squares in each equivalence
600 * class, and count the overall number of
601 * known-non-blank squares.
603 * In the process of doing this, we must notice if a
604 * loop has already been formed. If it has, we blank
605 * out any square which isn't part of that loop
606 * (failing a consistency check if any such square does
607 * not have BLANK as one of its remaining options) and
608 * exit the deduction loop with success.
612 for (y
= 1; y
< H
-1; y
++)
613 for (x
= 1; x
< W
-1; x
++)
616 * (x,y) are the workspace coordinates of
617 * an edge field. Compute the normal-space
618 * coordinates of the squares it connects.
620 int ax
= (x
-1)/2, ay
= (y
-1)/2, ac
= ay
*w
+ax
;
621 int bx
= x
/2, by
= y
/2, bc
= by
*w
+bx
;
624 * If the edge is connected, do the dsf
627 if (workspace
[y
*W
+x
] == 1) {
630 ae
= dsf_canonify(dsf
, ac
);
631 be
= dsf_canonify(dsf
, bc
);
637 if (loopclass
!= -1) {
639 * In fact, we have two
640 * separate loops, which is
643 #ifdef SOLVER_DIAGNOSTICS
644 printf("two loops found in grid!\n");
652 * Merge the two equivalence
655 int size
= dsfsize
[ae
] + dsfsize
[be
];
656 dsf_merge(dsf
, ac
, bc
);
657 ae
= dsf_canonify(dsf
, ac
);
661 } else if ((y
& x
) & 1) {
663 * (x,y) are the workspace coordinates of a
664 * square field. If the square is
665 * definitely not blank, count it.
667 if (!(workspace
[y
*W
+x
] & bBLANK
))
672 * If we discovered an existing loop above, we must now
673 * blank every square not part of it, and exit the main
676 if (loopclass
!= -1) {
677 #ifdef SOLVER_DIAGNOSTICS
678 printf("loop found in grid!\n");
680 for (y
= 0; y
< h
; y
++)
681 for (x
= 0; x
< w
; x
++)
682 if (dsf_canonify(dsf
, y
*w
+x
) != loopclass
) {
683 if (workspace
[(y
*2+1)*W
+(x
*2+1)] & bBLANK
) {
684 workspace
[(y
*2+1)*W
+(x
*2+1)] = bBLANK
;
687 * This square is not part of the
688 * loop, but is known non-blank. We
691 #ifdef SOLVER_DIAGNOSTICS
692 printf("non-blank square (%d,%d) found outside"
706 /* Further deductions are considered 'tricky'. */
707 if (difficulty
== DIFF_EASY
) goto done_deductions
;
710 * Now go through the workspace again and mark any edge
711 * which would cause a shortcut loop (i.e. would
712 * connect together two squares in the same equivalence
713 * class, and that equivalence class does not contain
714 * _all_ the known-non-blank squares currently in the
715 * grid) as disconnected. Also, mark any _square state_
716 * which would cause a shortcut loop as disconnected.
718 for (y
= 1; y
< H
-1; y
++)
719 for (x
= 1; x
< W
-1; x
++)
722 * (x,y) are the workspace coordinates of
723 * an edge field. Compute the normal-space
724 * coordinates of the squares it connects.
726 int ax
= (x
-1)/2, ay
= (y
-1)/2, ac
= ay
*w
+ax
;
727 int bx
= x
/2, by
= y
/2, bc
= by
*w
+bx
;
730 * If the edge is currently unknown, and
731 * sits between two squares in the same
732 * equivalence class, and the size of that
733 * class is less than nonblanks, then
734 * connecting this edge would be a shortcut
735 * loop and so we must not do so.
737 if (workspace
[y
*W
+x
] == 3) {
740 ae
= dsf_canonify(dsf
, ac
);
741 be
= dsf_canonify(dsf
, bc
);
745 * We have a loop. Is it a shortcut?
747 if (dsfsize
[ae
] < nonblanks
) {
749 * Yes! Mark this edge disconnected.
751 workspace
[y
*W
+x
] = 2;
752 done_something
= TRUE
;
753 #ifdef SOLVER_DIAGNOSTICS
754 printf("edge (%d,%d)-(%d,%d) would create"
755 " a shortcut loop, hence must be"
756 " disconnected\n", x
/2, y
/2,
762 } else if ((y
& x
) & 1) {
764 * (x,y) are the workspace coordinates of a
765 * square field. Go through its possible
766 * (non-blank) states and see if any gives
767 * rise to a shortcut loop.
769 * This is slightly fiddly, because we have
770 * to check whether this square is already
771 * part of the same equivalence class as
772 * the things it's joining.
774 int ae
= dsf_canonify(dsf
, (y
/2)*w
+(x
/2));
776 for (b
= 2; b
< 0xD; b
++)
777 if (workspace
[y
*W
+x
] & (1<<b
)) {
779 * Find the equivalence classes of
780 * the two squares this one would
781 * connect if it were in this
786 for (d
= 1; d
<= 8; d
+= d
) if (b
& d
) {
787 int xx
= x
/2 + DX(d
), yy
= y
/2 + DY(d
);
788 int ee
= dsf_canonify(dsf
, yy
*w
+xx
);
798 * This square state would form
799 * a loop on equivalence class
800 * e. Measure the size of that
801 * loop, and see if it's a
804 int loopsize
= dsfsize
[e
];
806 loopsize
++;/* add the square itself */
807 if (loopsize
< nonblanks
) {
809 * It is! Mark this square
812 workspace
[y
*W
+x
] &= ~(1<<b
);
813 done_something
= TRUE
;
814 #ifdef SOLVER_DIAGNOSTICS
815 printf("square (%d,%d) would create a "
816 "shortcut loop in state %d, "
832 * If we reach here, there is nothing left we can do.
833 * Return 2 for ambiguous puzzle.
842 * If ret = 1 then we've successfully achieved a solution. This
843 * means that we expect every square to be nailed down to
844 * exactly one possibility. If this is the case, or if the caller
845 * asked for a partial solution anyway, transcribe those
846 * possibilities into the result array.
848 if (ret
== 1 || partial
) {
849 for (y
= 0; y
< h
; y
++) {
850 for (x
= 0; x
< w
; x
++) {
851 for (b
= 0; b
< 0xD; b
++)
852 if (workspace
[(2*y
+1)*W
+(2*x
+1)] == (1<<b
)) {
856 if (ret
== 1) assert(b
< 0xD); /* we should have had a break by now */
868 /* ----------------------------------------------------------------------
873 * We use the loop generator code from loopy, hard-coding to a square
874 * grid of the appropriate size. Knowing the grid layout and the tile
875 * size we can shrink that to our small grid and then make our line
876 * layout from the face colour info.
878 * We provide a bias function to the loop generator which tries to
879 * bias in favour of loops with more scope for Pearl black clues. This
880 * seems to improve the success rate of the puzzle generator, in that
881 * such loops have a better chance of being soluble with all valid
885 struct pearl_loopgen_bias_ctx
{
887 * Our bias function counts the number of 'black clue' corners
888 * (i.e. corners adjacent to two straights) in both the
889 * BLACK/nonBLACK and WHITE/nonWHITE boundaries. In order to do
892 * - track the edges that are part of each of those loops
893 * - track the types of vertex in each loop (corner, straight,
895 * - track the current black-clue status of each vertex in each
898 * Each of these chunks of data is updated incrementally from the
899 * previous one, to avoid slowdown due to the bias function
900 * rescanning the whole grid every time it's called.
902 * So we need a lot of separate arrays, plus a tdq for each one,
903 * and we must repeat it all twice for the BLACK and WHITE
906 struct pearl_loopgen_bias_ctx_boundary
{
907 int colour
; /* FACE_WHITE or FACE_BLACK */
909 char *edges
; /* is each edge part of the loop? */
912 char *vertextypes
; /* bits 0-3 == outgoing edge bitmap;
913 * bit 4 set iff corner clue.
914 * Hence, 0 means non-vertex;
915 * nonzero but bit 4 zero = straight. */
916 int *neighbour
[2]; /* indices of neighbour vertices in loop */
917 tdq
*vertextypes_todo
;
919 char *blackclues
; /* is each vertex a black clue site? */
920 tdq
*blackclues_todo
;
921 } boundaries
[2]; /* boundaries[0]=WHITE, [1]=BLACK */
923 char *faces
; /* remember last-seen colour of each face */
930 int pearl_loopgen_bias(void *vctx
, char *board
, int face
)
932 struct pearl_loopgen_bias_ctx
*ctx
= (struct pearl_loopgen_bias_ctx
*)vctx
;
934 int oldface
, newface
;
937 tdq_add(ctx
->faces_todo
, face
);
938 while ((j
= tdq_remove(ctx
->faces_todo
)) >= 0) {
939 oldface
= ctx
->faces
[j
];
940 ctx
->faces
[j
] = newface
= board
[j
];
941 for (i
= 0; i
< 2; i
++) {
942 struct pearl_loopgen_bias_ctx_boundary
*b
= &ctx
->boundaries
[i
];
946 * If the face has changed either from or to colour c, we need
947 * to reprocess the edges for this boundary.
949 if (oldface
== c
|| newface
== c
) {
950 grid_face
*f
= &g
->faces
[face
];
951 for (k
= 0; k
< f
->order
; k
++)
952 tdq_add(b
->edges_todo
, f
->edges
[k
] - g
->edges
);
957 for (i
= 0; i
< 2; i
++) {
958 struct pearl_loopgen_bias_ctx_boundary
*b
= &ctx
->boundaries
[i
];
962 * Go through the to-do list of edges. For each edge, decide
963 * anew whether it's part of this boundary or not. Any edge
964 * that changes state has to have both its endpoints put on
965 * the vertextypes_todo list.
967 while ((j
= tdq_remove(b
->edges_todo
)) >= 0) {
968 grid_edge
*e
= &g
->edges
[j
];
969 int fc1
= e
->face1 ? board
[e
->face1
- g
->faces
] : FACE_BLACK
;
970 int fc2
= e
->face2 ? board
[e
->face2
- g
->faces
] : FACE_BLACK
;
971 int oldedge
= b
->edges
[j
];
972 int newedge
= (fc1
==c
) ^ (fc2
==c
);
973 if (oldedge
!= newedge
) {
974 b
->edges
[j
] = newedge
;
975 tdq_add(b
->vertextypes_todo
, e
->dot1
- g
->dots
);
976 tdq_add(b
->vertextypes_todo
, e
->dot2
- g
->dots
);
981 * Go through the to-do list of vertices whose types need
982 * refreshing. For each one, decide whether it's a corner, a
983 * straight, or a vertex not in the loop, and in the former
984 * two cases also work out the indices of its neighbour
985 * vertices along the loop. Any vertex that changes state must
986 * be put back on the to-do list for deciding if it's a black
987 * clue site, and so must its two new neighbours _and_ its two
990 while ((j
= tdq_remove(b
->vertextypes_todo
)) >= 0) {
991 grid_dot
*d
= &g
->dots
[j
];
992 int neighbours
[2], type
= 0, n
= 0;
994 for (k
= 0; k
< d
->order
; k
++) {
995 grid_edge
*e
= d
->edges
[k
];
996 grid_dot
*d2
= (e
->dot1
== d ? e
->dot2
: e
->dot1
);
997 /* dir == 0,1,2,3 for an edge going L,U,R,D */
998 int dir
= (d
->y
== d2
->y
) + 2*(d
->x
+d
->y
> d2
->x
+d2
->y
);
999 int ei
= e
- g
->edges
;
1002 neighbours
[n
] = d2
- g
->dots
;
1008 * Decide if it's a corner, and set the corner flag if so.
1010 if (type
!= 0 && type
!= 0x5 && type
!= 0xA)
1013 if (type
!= b
->vertextypes
[j
]) {
1015 * Recompute old neighbours, if any.
1017 if (b
->vertextypes
[j
]) {
1018 tdq_add(b
->blackclues_todo
, b
->neighbour
[0][j
]);
1019 tdq_add(b
->blackclues_todo
, b
->neighbour
[1][j
]);
1022 * Recompute this vertex.
1024 tdq_add(b
->blackclues_todo
, j
);
1025 b
->vertextypes
[j
] = type
;
1027 * Recompute new neighbours, if any.
1029 if (b
->vertextypes
[j
]) {
1030 b
->neighbour
[0][j
] = neighbours
[0];
1031 b
->neighbour
[1][j
] = neighbours
[1];
1032 tdq_add(b
->blackclues_todo
, b
->neighbour
[0][j
]);
1033 tdq_add(b
->blackclues_todo
, b
->neighbour
[1][j
]);
1039 * Go through the list of vertices which we must check to see
1040 * if they're black clue sites. Each one is a black clue site
1041 * iff it is a corner and its loop neighbours are non-corners.
1042 * Adjust the running total of black clues we've counted.
1044 while ((j
= tdq_remove(b
->blackclues_todo
)) >= 0) {
1045 ctx
->score
-= b
->blackclues
[j
];
1046 b
->blackclues
[j
] = ((b
->vertextypes
[j
] & 0x10) &&
1047 !((b
->vertextypes
[b
->neighbour
[0][j
]] |
1048 b
->vertextypes
[b
->neighbour
[1][j
]])
1050 ctx
->score
+= b
->blackclues
[j
];
1057 void pearl_loopgen(int w
, int h
, char *lines
, random_state
*rs
)
1059 grid
*g
= grid_new(GRID_SQUARE
, w
-1, h
-1, NULL
);
1060 char *board
= snewn(g
->num_faces
, char);
1061 int i
, s
= g
->tilesize
;
1062 struct pearl_loopgen_bias_ctx biasctx
;
1064 memset(lines
, 0, w
*h
);
1067 * Initialise the context for the bias function. Initially we fill
1068 * all the to-do lists, so that the first call will scan
1069 * everything; thereafter the lists stay empty so we make
1070 * incremental changes.
1073 biasctx
.faces
= snewn(g
->num_faces
, char);
1074 biasctx
.faces_todo
= tdq_new(g
->num_faces
);
1075 tdq_fill(biasctx
.faces_todo
);
1077 memset(biasctx
.faces
, FACE_GREY
, g
->num_faces
);
1078 for (i
= 0; i
< 2; i
++) {
1079 biasctx
.boundaries
[i
].edges
= snewn(g
->num_edges
, char);
1080 memset(biasctx
.boundaries
[i
].edges
, 0, g
->num_edges
);
1081 biasctx
.boundaries
[i
].edges_todo
= tdq_new(g
->num_edges
);
1082 tdq_fill(biasctx
.boundaries
[i
].edges_todo
);
1083 biasctx
.boundaries
[i
].vertextypes
= snewn(g
->num_dots
, char);
1084 memset(biasctx
.boundaries
[i
].vertextypes
, 0, g
->num_dots
);
1085 biasctx
.boundaries
[i
].neighbour
[0] = snewn(g
->num_dots
, int);
1086 biasctx
.boundaries
[i
].neighbour
[1] = snewn(g
->num_dots
, int);
1087 biasctx
.boundaries
[i
].vertextypes_todo
= tdq_new(g
->num_dots
);
1088 tdq_fill(biasctx
.boundaries
[i
].vertextypes_todo
);
1089 biasctx
.boundaries
[i
].blackclues
= snewn(g
->num_dots
, char);
1090 memset(biasctx
.boundaries
[i
].blackclues
, 0, g
->num_dots
);
1091 biasctx
.boundaries
[i
].blackclues_todo
= tdq_new(g
->num_dots
);
1092 tdq_fill(biasctx
.boundaries
[i
].blackclues_todo
);
1094 biasctx
.boundaries
[0].colour
= FACE_WHITE
;
1095 biasctx
.boundaries
[1].colour
= FACE_BLACK
;
1096 generate_loop(g
, board
, rs
, pearl_loopgen_bias
, &biasctx
);
1097 sfree(biasctx
.faces
);
1098 tdq_free(biasctx
.faces_todo
);
1099 for (i
= 0; i
< 2; i
++) {
1100 sfree(biasctx
.boundaries
[i
].edges
);
1101 tdq_free(biasctx
.boundaries
[i
].edges_todo
);
1102 sfree(biasctx
.boundaries
[i
].vertextypes
);
1103 sfree(biasctx
.boundaries
[i
].neighbour
[0]);
1104 sfree(biasctx
.boundaries
[i
].neighbour
[1]);
1105 tdq_free(biasctx
.boundaries
[i
].vertextypes_todo
);
1106 sfree(biasctx
.boundaries
[i
].blackclues
);
1107 tdq_free(biasctx
.boundaries
[i
].blackclues_todo
);
1110 for (i
= 0; i
< g
->num_edges
; i
++) {
1111 grid_edge
*e
= g
->edges
+ i
;
1112 enum face_colour c1
= FACE_COLOUR(e
->face1
);
1113 enum face_colour c2
= FACE_COLOUR(e
->face2
);
1114 assert(c1
!= FACE_GREY
);
1115 assert(c2
!= FACE_GREY
);
1117 /* This grid edge is on the loop: lay line along it */
1118 int x1
= e
->dot1
->x
/s
, y1
= e
->dot1
->y
/s
;
1119 int x2
= e
->dot2
->x
/s
, y2
= e
->dot2
->y
/s
;
1121 /* (x1,y1) and (x2,y2) are now in our grid coords (0-w,0-h). */
1123 if (y1
> y2
) SWAP(y1
,y2
);
1126 lines
[y1
*w
+x1
] |= D
;
1127 lines
[y2
*w
+x1
] |= U
;
1128 } else if (y1
== y2
) {
1129 if (x1
> x2
) SWAP(x1
,x2
);
1132 lines
[y1
*w
+x1
] |= R
;
1133 lines
[y1
*w
+x2
] |= L
;
1135 assert(!"grid with diagonal coords?!");
1142 #if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
1143 printf("as returned:\n");
1144 for (y
= 0; y
< h
; y
++) {
1145 for (x
= 0; x
< w
; x
++) {
1146 int type
= lines
[y
*w
+x
];
1148 if (type
& L
) *p
++ = 'L';
1149 if (type
& R
) *p
++ = 'R';
1150 if (type
& U
) *p
++ = 'U';
1151 if (type
& D
) *p
++ = 'D';
1161 static int new_clues(game_params
*params
, random_state
*rs
,
1162 char *clues
, char *grid
)
1164 int w
= params
->w
, h
= params
->h
, diff
= params
->difficulty
;
1165 int ngen
= 0, x
, y
, d
, ret
, i
;
1169 * Difficulty exception: 5x5 Tricky is not generable (the
1170 * generator will spin forever trying) and so we fudge it to Easy.
1172 if (w
== 5 && h
== 5 && diff
> DIFF_EASY
)
1177 pearl_loopgen(w
, h
, grid
, rs
);
1179 #ifdef GENERATION_DIAGNOSTICS
1180 printf("grid array:\n");
1181 for (y
= 0; y
< h
; y
++) {
1182 for (x
= 0; x
< w
; x
++) {
1183 int type
= grid
[y
*w
+x
];
1185 if (type
& L
) *p
++ = 'L';
1186 if (type
& R
) *p
++ = 'R';
1187 if (type
& U
) *p
++ = 'U';
1188 if (type
& D
) *p
++ = 'D';
1198 * Set up the maximal clue array.
1200 for (y
= 0; y
< h
; y
++)
1201 for (x
= 0; x
< w
; x
++) {
1202 int type
= grid
[y
*w
+x
];
1204 clues
[y
*w
+x
] = NOCLUE
;
1206 if ((bLR
|bUD
) & (1 << type
)) {
1208 * This is a straight; see if it's a viable
1209 * candidate for a straight clue. It qualifies if
1210 * at least one of the squares it connects to is a
1213 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1214 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1215 assert(xx
>= 0 && xx
< w
&& yy
>= 0 && yy
< h
);
1216 if ((bLU
|bLD
|bRU
|bRD
) & (1 << grid
[yy
*w
+xx
]))
1219 if (d
<= 8) /* we found one */
1220 clues
[y
*w
+x
] = STRAIGHT
;
1221 } else if ((bLU
|bLD
|bRU
|bRD
) & (1 << type
)) {
1223 * This is a corner; see if it's a viable candidate
1224 * for a corner clue. It qualifies if all the
1225 * squares it connects to are straights.
1227 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1228 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1229 assert(xx
>= 0 && xx
< w
&& yy
>= 0 && yy
< h
);
1230 if (!((bLR
|bUD
) & (1 << grid
[yy
*w
+xx
])))
1233 if (d
> 8) /* we didn't find a counterexample */
1234 clues
[y
*w
+x
] = CORNER
;
1238 #ifdef GENERATION_DIAGNOSTICS
1239 printf("clue array:\n");
1240 for (y
= 0; y
< h
; y
++) {
1241 for (x
= 0; x
< w
; x
++) {
1242 printf("%c", " *O"[(unsigned char)clues
[y
*w
+x
]]);
1249 if (!params
->nosolve
) {
1250 int *cluespace
, *straights
, *corners
;
1251 int nstraights
, ncorners
, nstraightpos
, ncornerpos
;
1254 * See if we can solve the puzzle just like this.
1256 ret
= pearl_solve(w
, h
, clues
, grid
, diff
, FALSE
);
1257 assert(ret
> 0); /* shouldn't be inconsistent! */
1259 continue; /* go round and try again */
1262 * Check this puzzle isn't too easy.
1264 if (diff
> DIFF_EASY
) {
1265 ret
= pearl_solve(w
, h
, clues
, grid
, diff
-1, FALSE
);
1268 continue; /* too easy: try again */
1272 * Now shuffle the grid points and gradually remove the
1273 * clues to find a minimal set which still leaves the
1276 * We preferentially attempt to remove whichever type of
1277 * clue is currently most numerous, to combat a general
1278 * tendency of plain random generation to bias in favour
1279 * of many white clues and few black.
1281 * 'nstraights' and 'ncorners' count the number of clues
1282 * of each type currently remaining in the grid;
1283 * 'nstraightpos' and 'ncornerpos' count the clues of each
1284 * type we have left to try to remove. (Clues which we
1285 * have tried and failed to remove are counted by the
1286 * former but not the latter.)
1288 cluespace
= snewn(w
*h
, int);
1289 straights
= cluespace
;
1291 for (i
= 0; i
< w
*h
; i
++)
1292 if (clues
[i
] == STRAIGHT
)
1293 straights
[nstraightpos
++] = i
;
1294 corners
= straights
+ nstraightpos
;
1296 for (i
= 0; i
< w
*h
; i
++)
1297 if (clues
[i
] == STRAIGHT
)
1298 corners
[ncornerpos
++] = i
;
1299 nstraights
= nstraightpos
;
1300 ncorners
= ncornerpos
;
1302 shuffle(straights
, nstraightpos
, sizeof(*straights
), rs
);
1303 shuffle(corners
, ncornerpos
, sizeof(*corners
), rs
);
1304 while (nstraightpos
> 0 || ncornerpos
> 0) {
1309 * Decide which clue to try to remove next. If both
1310 * types are available, we choose whichever kind is
1311 * currently overrepresented; otherwise we take
1312 * whatever we can get.
1314 if (nstraightpos
> 0 && ncornerpos
> 0) {
1315 if (nstraights
>= ncorners
)
1316 cluepos
= straights
[--nstraightpos
];
1318 cluepos
= straights
[--ncornerpos
];
1320 if (nstraightpos
> 0)
1321 cluepos
= straights
[--nstraightpos
];
1323 cluepos
= straights
[--ncornerpos
];
1329 clue
= clues
[y
*w
+x
];
1330 clues
[y
*w
+x
] = 0; /* try removing this clue */
1332 ret
= pearl_solve(w
, h
, clues
, grid
, diff
, FALSE
);
1335 clues
[y
*w
+x
] = clue
; /* oops, put it back again */
1340 #ifdef FINISHED_PUZZLE
1341 printf("clue array:\n");
1342 for (y
= 0; y
< h
; y
++) {
1343 for (x
= 0; x
< w
; x
++) {
1344 printf("%c", " *O"[(unsigned char)clues
[y
*w
+x
]]);
1354 debug(("%d %dx%d loops before finished puzzle.\n", ngen
, w
, h
));
1359 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1360 char **aux
, int interactive
)
1364 int w
= params
->w
, h
= params
->h
, i
, j
;
1366 grid
= snewn(w
*h
, char);
1367 clues
= snewn(w
*h
, char);
1369 new_clues(params
, rs
, clues
, grid
);
1371 desc
= snewn(w
* h
+ 1, char);
1372 for (i
= j
= 0; i
< w
*h
; i
++) {
1373 if (clues
[i
] == NOCLUE
&& j
> 0 &&
1374 desc
[j
-1] >= 'a' && desc
[j
-1] < 'z')
1376 else if (clues
[i
] == NOCLUE
)
1378 else if (clues
[i
] == CORNER
)
1380 else if (clues
[i
] == STRAIGHT
)
1385 *aux
= snewn(w
*h
+1, char);
1386 for (i
= 0; i
< w
*h
; i
++)
1387 (*aux
)[i
] = (grid
[i
] < 10) ?
(grid
[i
] + '0') : (grid
[i
] + 'A' - 10);
1396 static char *validate_desc(game_params
*params
, char *desc
)
1399 const int totalsize
= params
->w
* params
->h
;
1402 for (i
= 0; desc
[i
]; i
++) {
1403 if (desc
[i
] >= 'a' && desc
[i
] <= 'z')
1404 sizesofar
+= desc
[i
] - 'a' + 1;
1405 else if (desc
[i
] == 'B' || desc
[i
] == 'W')
1408 return "unrecognised character in string";
1411 if (sizesofar
> totalsize
)
1412 return "string too long";
1413 else if (sizesofar
< totalsize
)
1414 return "string too short";
1419 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
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(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 *loopclass
,
1499 int ax
, int ay
, char dir
,
1500 int *dsf
, int *dsfsize
)
1502 int w
= state
->shared
->w
/*, h = state->shared->h */;
1503 int ac
= ay
*w
+ax
, ae
, bx
, by
, bc
, be
;
1505 if (!(state
->lines
[ac
] & dir
)) return; /* no link */
1506 bx
= ax
+ DX(dir
); by
= ay
+ DY(dir
);
1508 assert(INGRID(state
, bx
, by
)); /* should not have a link off grid */
1512 assert(state
->lines
[bc
] & F(dir
)); /* should have reciprocal link */
1514 /* TODO put above assertion back in once we stop generating partially
1515 * soluble puzzles. */
1516 if (!(state
->lines
[bc
] & F(dir
))) return;
1518 ae
= dsf_canonify(dsf
, ac
);
1519 be
= dsf_canonify(dsf
, bc
);
1521 if (ae
== be
) { /* detected a loop! */
1522 if (*loopclass
!= -1) /* this is the second loop, doom. */
1526 int size
= dsfsize
[ae
] + dsfsize
[be
];
1527 dsf_merge(dsf
, ac
, bc
);
1528 ae
= dsf_canonify(dsf
, ac
);
1534 static void check_completion(game_state
*state
, int mark
)
1536 int w
= state
->shared
->w
, h
= state
->shared
->h
, x
, y
, i
, d
;
1537 int had_error
= FALSE
/*, is_complete = FALSE */, loopclass
;
1541 for (i
= 0; i
< w
*h
; i
++) {
1542 state
->errors
[i
] = 0;
1546 #define ERROR(x,y,e) do { had_error = TRUE; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0)
1549 * First of all: we should have one single closed loop, passing through all clues.
1551 dsf
= snewn(w
*h
, int);
1552 dsfsize
= snewn(w
*h
, int);
1554 for (i
= 0; i
< w
*h
; i
++) dsfsize
[i
] = 1;
1557 for (x
= 0; x
< w
; x
++) {
1558 for (y
= 0; y
< h
; y
++) {
1559 dsf_update_completion(state
, &loopclass
, x
, y
, R
, dsf
, dsfsize
);
1560 dsf_update_completion(state
, &loopclass
, x
, y
, D
, dsf
, dsfsize
);
1563 if (loopclass
!= -1) {
1564 /* We have a loop. Check all squares with lines on. */
1565 for (x
= 0; x
< w
; x
++) {
1566 for (y
= 0; y
< h
; y
++) {
1567 if (state
->lines
[y
*w
+x
] == BLANK
) {
1568 if (state
->shared
->clues
[y
*w
+x
] != NOCLUE
) {
1569 /* the loop doesn't include this clue square! */
1570 ERROR(x
, y
, ERROR_CLUE
);
1573 if (dsf_canonify(dsf
, y
*w
+x
) != loopclass
) {
1574 /* these lines are not on the loop: mark them as error. */
1575 ERROR(x
, y
, state
->lines
[y
*w
+x
]);
1583 * Second: check no clues are contradicted.
1586 for (x
= 0; x
< w
; x
++) {
1587 for (y
= 0; y
< h
; y
++) {
1588 int type
= state
->lines
[y
*w
+x
];
1590 * Check that no square has more than two line segments.
1592 if (NBITS(type
) > 2) {
1596 * Check that no clues are contradicted. This code is similar to
1597 * the code that sets up the maximal clue array for any given
1600 if (state
->shared
->clues
[y
*w
+x
] == CORNER
) {
1601 /* Supposed to be a corner: will find a contradiction if
1602 * it actually contains a straight line, or if it touches any
1604 if ((bLR
|bUD
) & (1 << type
)) {
1605 ERROR(x
,y
,ERROR_CLUE
); /* actually straight */
1607 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1608 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1609 if (!INGRID(state
, xx
, yy
)) {
1610 ERROR(x
,y
,d
); /* leads off grid */
1612 if ((bLU
|bLD
|bRU
|bRD
) & (1 << state
->lines
[yy
*w
+xx
])) {
1613 ERROR(x
,y
,ERROR_CLUE
); /* touches corner */
1617 } else if (state
->shared
->clues
[y
*w
+x
] == STRAIGHT
) {
1618 /* Supposed to be straight: will find a contradiction if
1619 * it actually contains a corner, or if it only touches
1620 * straight lines. */
1621 if ((bLU
|bLD
|bRU
|bRD
) & (1 << type
)) {
1622 ERROR(x
,y
,ERROR_CLUE
); /* actually a corner */
1625 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1626 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1627 if (!INGRID(state
, xx
, yy
)) {
1628 ERROR(x
,y
,d
); /* leads off grid */
1630 if ((bLR
|bUD
) & (1 << state
->lines
[yy
*w
+xx
]))
1631 i
++; /* a straight */
1634 if (i
>= 2 && NBITS(type
) >= 2) {
1635 ERROR(x
,y
,ERROR_CLUE
); /* everything touched is straight */
1640 if (!had_error
&& loopclass
!= -1) {
1641 state
->completed
= TRUE
;
1642 state
->loop_length
= dsfsize
[loopclass
];
1644 state
->completed
= FALSE
;
1653 /* completion check:
1655 * - no clues must be contradicted (highlight clue itself in error if so)
1656 * - if there is a closed loop it must include every line segment laid
1657 * - if there's a smaller closed loop then highlight whole loop as error
1658 * - no square must have more than 3 lines radiating from centre point
1659 * (highlight all lines in that square as error if so)
1662 static char *solve_for_diff(game_state
*state
, char *old_lines
, char *new_lines
)
1664 int w
= state
->shared
->w
, h
= state
->shared
->h
, i
;
1665 char *move
= snewn(w
*h
*40, char), *p
= move
;
1668 for (i
= 0; i
< w
*h
; i
++) {
1669 if (old_lines
[i
] != new_lines
[i
]) {
1670 p
+= sprintf(p
, ";R%d,%d,%d", new_lines
[i
], i
%w
, i
/w
);
1674 move
= sresize(move
, p
- move
, char);
1679 static char *solve_game(game_state
*state
, game_state
*currstate
,
1680 char *aux
, char **error
)
1682 game_state
*solved
= dup_game(state
);
1683 int i
, ret
, sz
= state
->shared
->sz
;
1687 for (i
= 0; i
< sz
; i
++) {
1688 if (aux
[i
] >= '0' && aux
[i
] <= '9')
1689 solved
->lines
[i
] = aux
[i
] - '0';
1690 else if (aux
[i
] >= 'A' && aux
[i
] <= 'F')
1691 solved
->lines
[i
] = aux
[i
] - 'A' + 10;
1693 *error
= "invalid char in aux";
1700 /* Try to solve with present (half-solved) state first: if there's no
1701 * solution from there go back to original state. */
1702 ret
= pearl_solve(currstate
->shared
->w
, currstate
->shared
->h
,
1703 currstate
->shared
->clues
, solved
->lines
,
1706 ret
= pearl_solve(state
->shared
->w
, state
->shared
->h
,
1707 state
->shared
->clues
, solved
->lines
,
1713 *error
= "Unable to find solution";
1716 move
= solve_for_diff(solved
, currstate
->lines
, solved
->lines
);
1724 static int game_can_format_as_text_now(game_params
*params
)
1729 static char *game_text_format(game_state
*state
)
1735 int *dragcoords
; /* list of (y*w+x) coords in drag so far */
1736 int ndragcoords
; /* number of entries in dragcoords.
1737 * 0 = click but no drag yet. -1 = no drag at all */
1738 int clickx
, clicky
; /* pixel position of initial click */
1740 int curx
, cury
; /* grid position of keyboard cursor */
1741 int cursor_active
; /* TRUE iff cursor is shown */
1744 static game_ui
*new_ui(game_state
*state
)
1746 game_ui
*ui
= snew(game_ui
);
1747 int sz
= state
->shared
->sz
;
1749 ui
->ndragcoords
= -1;
1750 ui
->dragcoords
= snewn(sz
, int);
1751 ui
->cursor_active
= FALSE
;
1752 ui
->curx
= ui
->cury
= 0;
1757 static void free_ui(game_ui
*ui
)
1759 sfree(ui
->dragcoords
);
1763 static char *encode_ui(game_ui
*ui
)
1768 static void decode_ui(game_ui
*ui
, char *encoding
)
1772 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1773 game_state
*newstate
)
1777 #define PREFERRED_TILE_SIZE 31
1778 #define HALFSZ (ds->halfsz)
1779 #define TILE_SIZE (ds->halfsz*2 + 1)
1781 #define BORDER ((get_gui_style() == GUI_LOOPY) ? (TILE_SIZE/8) : (TILE_SIZE/2))
1783 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1785 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
1786 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1787 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) )
1789 #define DS_ESHIFT 4 /* R/U/L/D shift, for error flags */
1790 #define DS_DSHIFT 8 /* R/U/L/D shift, for drag-in-progress flags */
1791 #define DS_MSHIFT 12 /* shift for no-line mark */
1793 #define DS_ERROR_CLUE (1 << 20)
1794 #define DS_FLASH (1 << 21)
1795 #define DS_CURSOR (1 << 22)
1797 enum { GUI_MASYU
, GUI_LOOPY
};
1799 static int get_gui_style(void)
1801 static int gui_style
= -1;
1803 if (gui_style
== -1) {
1804 char *env
= getenv("PEARL_GUI_LOOPY");
1805 if (env
&& (env
[0] == 'y' || env
[0] == 'Y'))
1806 gui_style
= GUI_LOOPY
;
1808 gui_style
= GUI_MASYU
;
1813 struct game_drawstate
{
1818 unsigned int *lflags
; /* size w*h */
1820 char *draglines
; /* size w*h; lines flipped by current drag */
1823 static void update_ui_drag(game_state
*state
, game_ui
*ui
, int gx
, int gy
)
1825 int /* sz = state->shared->sz, */ w
= state
->shared
->w
;
1829 if (!INGRID(state
, gx
, gy
))
1830 return; /* square is outside grid */
1832 if (ui
->ndragcoords
< 0)
1833 return; /* drag not in progress anyway */
1837 lastpos
= ui
->dragcoords
[ui
->ndragcoords
> 0 ? ui
->ndragcoords
-1 : 0];
1839 return; /* same square as last visited one */
1841 /* Drag confirmed, if it wasn't already. */
1842 if (ui
->ndragcoords
== 0)
1843 ui
->ndragcoords
= 1;
1846 * Dragging the mouse into a square that's already been visited by
1847 * the drag path so far has the effect of truncating the path back
1848 * to that square, so a player can back out part of an uncommitted
1849 * drag without having to let go of the mouse.
1851 for (i
= 0; i
< ui
->ndragcoords
; i
++)
1852 if (pos
== ui
->dragcoords
[i
]) {
1853 ui
->ndragcoords
= i
+1;
1858 * Otherwise, dragging the mouse into a square that's a rook-move
1859 * away from the last one on the path extends the path.
1861 oy
= ui
->dragcoords
[ui
->ndragcoords
-1] / w
;
1862 ox
= ui
->dragcoords
[ui
->ndragcoords
-1] % w
;
1863 if (ox
== gx
|| oy
== gy
) {
1864 int dx
= (gx
< ox ?
-1 : gx
> ox ?
+1 : 0);
1865 int dy
= (gy
< oy ?
-1 : gy
> oy ?
+1 : 0);
1866 int dir
= (dy
>0 ? D
: dy
<0 ? U
: dx
>0 ? R
: L
);
1867 while (ox
!= gx
|| oy
!= gy
) {
1869 * If the drag attempts to cross a 'no line here' mark,
1870 * stop there. We physically don't allow the user to drag
1873 if (state
->marks
[oy
*w
+ox
] & dir
)
1877 ui
->dragcoords
[ui
->ndragcoords
++] = oy
* w
+ ox
;
1882 * Failing that, we do nothing at all: if the user has dragged
1883 * diagonally across the board, they'll just have to return the
1884 * mouse to the last known position and do whatever they meant to
1885 * do again, more slowly and clearly.
1890 * Routine shared between interpret_move and game_redraw to work out
1891 * the intended effect of a drag path on the grid.
1893 * Call it in a loop, like this:
1895 * int clearing = TRUE;
1896 * for (i = 0; i < ui->ndragcoords - 1; i++) {
1897 * int sx, sy, dx, dy, dir, oldstate, newstate;
1898 * interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
1899 * &dir, &oldstate, &newstate);
1901 * [do whatever is needed to handle the fact that the drag
1902 * wants the edge from sx,sy to dx,dy (heading in direction
1903 * 'dir' at the sx,sy end) to be changed from state oldstate
1904 * to state newstate, each of which equals either 0 or dir]
1907 static void interpret_ui_drag(game_state
*state
, game_ui
*ui
, int *clearing
,
1908 int i
, int *sx
, int *sy
, int *dx
, int *dy
,
1909 int *dir
, int *oldstate
, int *newstate
)
1911 int w
= state
->shared
->w
;
1912 int sp
= ui
->dragcoords
[i
], dp
= ui
->dragcoords
[i
+1];
1917 *dir
= (*dy
>*sy ? D
: *dy
<*sy ? U
: *dx
>*sx ? R
: L
);
1918 *oldstate
= state
->lines
[sp
] & *dir
;
1921 * The edge we've dragged over was previously
1922 * present. Set it to absent, unless we've already
1923 * stopped doing that.
1925 *newstate
= *clearing ?
0 : *dir
;
1928 * The edge we've dragged over was previously
1929 * absent. Set it to present, and cancel the
1930 * 'clearing' flag so that all subsequent edges in
1931 * the drag are set rather than cleared.
1938 static char *mark_in_direction(game_state
*state
, int x
, int y
, int dir
,
1939 int ismark
, char *buf
)
1941 int w
= state
->shared
->w
/*, h = state->shared->h, sz = state->shared->sz */;
1942 int x2
= x
+ DX(dir
);
1943 int y2
= y
+ DY(dir
);
1945 char ch
= ismark ?
'M' : 'F';
1947 if (!INGRID(state
, x
, y
) || !INGRID(state
, x2
, y2
)) return "";
1948 /* disallow laying a mark over a line, or vice versa. */
1950 if ((state
->lines
[y
*w
+x
] & dir
) || (state
->lines
[y2
*w
+x2
] & dir2
))
1953 if ((state
->marks
[y
*w
+x
] & dir
) || (state
->marks
[y2
*w
+x2
] & dir2
))
1957 sprintf(buf
, "%c%d,%d,%d;%c%d,%d,%d", ch
, dir
, x
, y
, ch
, dir2
, x2
, y2
);
1961 #define KEY_DIRECTION(btn) (\
1962 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
1963 (btn) == CURSOR_LEFT ? L : R)
1965 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1966 int x
, int y
, int button
)
1968 int w
= state
->shared
->w
, h
= state
->shared
->h
/*, sz = state->shared->sz */;
1969 int gx
= FROMCOORD(x
), gy
= FROMCOORD(y
), i
;
1970 int release
= FALSE
;
1973 if (IS_MOUSE_DOWN(button
)) {
1974 ui
->cursor_active
= FALSE
;
1976 if (!INGRID(state
, gx
, gy
)) {
1977 ui
->ndragcoords
= -1;
1981 ui
->clickx
= x
; ui
->clicky
= y
;
1982 ui
->dragcoords
[0] = gy
* w
+ gx
;
1983 ui
->ndragcoords
= 0; /* will be 1 once drag is confirmed */
1988 if (button
== LEFT_DRAG
&& ui
->ndragcoords
>= 0) {
1989 update_ui_drag(state
, ui
, gx
, gy
);
1993 if (IS_MOUSE_RELEASE(button
)) release
= TRUE
;
1995 if (IS_CURSOR_MOVE(button
& ~MOD_MASK
)) {
1996 if (!ui
->cursor_active
) {
1997 ui
->cursor_active
= TRUE
;
1998 } else if (button
& (MOD_SHFT
| MOD_CTRL
)) {
1999 if (ui
->ndragcoords
> 0) return NULL
;
2000 ui
->ndragcoords
= -1;
2001 return mark_in_direction(state
, ui
->curx
, ui
->cury
,
2002 KEY_DIRECTION(button
& ~MOD_MASK
),
2003 (button
& MOD_SHFT
), tmpbuf
);
2005 move_cursor(button
, &ui
->curx
, &ui
->cury
, w
, h
, FALSE
);
2006 if (ui
->ndragcoords
>= 0)
2007 update_ui_drag(state
, ui
, ui
->curx
, ui
->cury
);
2012 if (IS_CURSOR_SELECT(button
& ~MOD_MASK
)) {
2013 if (!ui
->cursor_active
) {
2014 ui
->cursor_active
= TRUE
;
2016 } else if (button
== CURSOR_SELECT
) {
2017 if (ui
->ndragcoords
== -1) {
2018 ui
->ndragcoords
= 0;
2019 ui
->dragcoords
[0] = ui
->cury
* w
+ ui
->curx
;
2020 ui
->clickx
= CENTERED_COORD(ui
->curx
);
2021 ui
->clicky
= CENTERED_COORD(ui
->cury
);
2023 } else release
= TRUE
;
2024 } else if (button
== CURSOR_SELECT2
&& ui
->ndragcoords
>= 0) {
2025 ui
->ndragcoords
= -1;
2031 if (ui
->ndragcoords
> 0) {
2032 /* End of a drag: process the cached line data. */
2033 int buflen
= 0, bufsize
= 256, tmplen
;
2035 const char *sep
= "";
2036 int clearing
= TRUE
;
2038 for (i
= 0; i
< ui
->ndragcoords
- 1; i
++) {
2039 int sx
, sy
, dx
, dy
, dir
, oldstate
, newstate
;
2040 interpret_ui_drag(state
, ui
, &clearing
, i
, &sx
, &sy
, &dx
, &dy
,
2041 &dir
, &oldstate
, &newstate
);
2043 if (oldstate
!= newstate
) {
2044 if (!buf
) buf
= snewn(bufsize
, char);
2045 tmplen
= sprintf(tmpbuf
, "%sF%d,%d,%d;F%d,%d,%d", sep
,
2046 dir
, sx
, sy
, F(dir
), dx
, dy
);
2047 if (buflen
+ tmplen
>= bufsize
) {
2048 bufsize
= (buflen
+ tmplen
) * 5 / 4 + 256;
2049 buf
= sresize(buf
, bufsize
, char);
2051 strcpy(buf
+ buflen
, tmpbuf
);
2057 ui
->ndragcoords
= -1;
2059 return buf ? buf
: "";
2060 } else if (ui
->ndragcoords
== 0) {
2061 /* Click (or tiny drag). Work out which edge we were
2065 ui
->ndragcoords
= -1;
2068 * We process clicks based on the mouse-down location,
2069 * because that's more natural for a user to carefully
2070 * control than the mouse-up.
2077 cx
= CENTERED_COORD(gx
);
2078 cy
= CENTERED_COORD(gy
);
2080 if (!INGRID(state
, gx
, gy
)) return "";
2082 if (max(abs(x
-cx
),abs(y
-cy
)) < TILE_SIZE
/4) {
2083 /* TODO closer to centre of grid: process as a cell click not an edge click. */
2088 if (abs(x
-cx
) < abs(y
-cy
)) {
2089 /* Closest to top/bottom edge. */
2090 direction
= (y
< cy
) ? U
: D
;
2092 /* Closest to left/right edge. */
2093 direction
= (x
< cx
) ? L
: R
;
2095 return mark_in_direction(state
, gx
, gy
, direction
,
2096 (button
== RIGHT_RELEASE
), tmpbuf
);
2101 if (button
== 'H' || button
== 'h')
2107 static game_state
*execute_move(game_state
*state
, char *move
)
2109 int w
= state
->shared
->w
, h
= state
->shared
->h
;
2112 game_state
*ret
= dup_game(state
);
2114 debug(("move: %s\n", move
));
2119 ret
->used_solve
= TRUE
;
2121 } else if (c
== 'L' || c
== 'N' || c
== 'R' || c
== 'F' || c
== 'M') {
2122 /* 'line' or 'noline' or 'replace' or 'flip' or 'mark' */
2124 if (sscanf(move
, "%d,%d,%d%n", &l
, &x
, &y
, &n
) != 3)
2126 if (!INGRID(state
, x
, y
)) goto badmove
;
2127 if (l
< 0 || l
> 15) goto badmove
;
2130 ret
->lines
[y
*w
+ x
] |= (char)l
;
2132 ret
->lines
[y
*w
+ x
] &= ~((char)l
);
2133 else if (c
== 'R') {
2134 ret
->lines
[y
*w
+ x
] = (char)l
;
2135 ret
->marks
[y
*w
+ x
] &= ~((char)l
); /* erase marks too */
2136 } else if (c
== 'F')
2137 ret
->lines
[y
*w
+ x
] ^= (char)l
;
2139 ret
->marks
[y
*w
+ x
] ^= (char)l
;
2142 * If we ended up trying to lay a line _over_ a mark,
2143 * that's a failed move: interpret_move() should have
2144 * ensured we never received a move string like that in
2147 if ((ret
->lines
[y
*w
+ x
] & (char)l
) &&
2148 (ret
->marks
[y
*w
+ x
] & (char)l
))
2152 } else if (strcmp(move
, "H") == 0) {
2153 pearl_solve(ret
->shared
->w
, ret
->shared
->h
,
2154 ret
->shared
->clues
, ret
->lines
, DIFFCOUNT
, TRUE
);
2155 for (n
= 0; n
< w
*h
; n
++)
2156 ret
->marks
[n
] &= ~ret
->lines
[n
]; /* erase marks too */
2167 check_completion(ret
, TRUE
);
2176 /* ----------------------------------------------------------------------
2180 #define FLASH_TIME 0.5F
2182 static void game_compute_size(game_params
*params
, int tilesize
,
2185 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2186 struct { int halfsz
; } ads
, *ds
= &ads
;
2187 ads
.halfsz
= (tilesize
-1)/2;
2189 *x
= (params
->w
) * TILE_SIZE
+ 2 * BORDER
;
2190 *y
= (params
->h
) * TILE_SIZE
+ 2 * BORDER
;
2193 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2194 game_params
*params
, int tilesize
)
2196 ds
->halfsz
= (tilesize
-1)/2;
2199 static float *game_colours(frontend
*fe
, int *ncolours
)
2201 float *ret
= snewn(3 * NCOLOURS
, float);
2204 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
2206 for (i
= 0; i
< 3; i
++) {
2207 ret
[COL_BLACK
* 3 + i
] = 0.0F
;
2208 ret
[COL_WHITE
* 3 + i
] = 1.0F
;
2209 ret
[COL_GRID
* 3 + i
] = 0.4F
;
2212 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
2213 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
2214 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
2216 ret
[COL_DRAGON
* 3 + 0] = 0.0F
;
2217 ret
[COL_DRAGON
* 3 + 1] = 0.0F
;
2218 ret
[COL_DRAGON
* 3 + 2] = 1.0F
;
2220 ret
[COL_DRAGOFF
* 3 + 0] = 0.8F
;
2221 ret
[COL_DRAGOFF
* 3 + 1] = 0.8F
;
2222 ret
[COL_DRAGOFF
* 3 + 2] = 1.0F
;
2224 ret
[COL_FLASH
* 3 + 0] = 1.0F
;
2225 ret
[COL_FLASH
* 3 + 1] = 1.0F
;
2226 ret
[COL_FLASH
* 3 + 2] = 1.0F
;
2228 *ncolours
= NCOLOURS
;
2233 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
2235 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2239 ds
->started
= FALSE
;
2241 ds
->w
= state
->shared
->w
;
2242 ds
->h
= state
->shared
->h
;
2243 ds
->sz
= state
->shared
->sz
;
2244 ds
->lflags
= snewn(ds
->sz
, unsigned int);
2245 for (i
= 0; i
< ds
->sz
; i
++)
2248 ds
->draglines
= snewn(ds
->sz
, char);
2253 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2255 sfree(ds
->draglines
);
2260 static void draw_lines_specific(drawing
*dr
, game_drawstate
*ds
,
2261 int x
, int y
, unsigned int lflags
,
2262 unsigned int shift
, int c
)
2264 int ox
= COORD(x
), oy
= COORD(y
);
2265 int t2
= HALFSZ
, t16
= HALFSZ
/4;
2266 int cx
= ox
+ t2
, cy
= oy
+ t2
;
2269 /* Draw each of the four directions, where laid (or error, or drag, etc.) */
2270 for (d
= 1; d
< 16; d
*= 2) {
2271 int xoff
= t2
* DX(d
), yoff
= t2
* DY(d
);
2272 int xnudge
= abs(t16
* DX(C(d
))), ynudge
= abs(t16
* DY(C(d
)));
2274 if ((lflags
>> shift
) & d
) {
2275 int lx
= cx
+ ((xoff
< 0) ? xoff
: 0) - xnudge
;
2276 int ly
= cy
+ ((yoff
< 0) ? yoff
: 0) - ynudge
;
2278 if (c
== COL_DRAGOFF
&& !(lflags
& d
))
2280 if (c
== COL_DRAGON
&& (lflags
& d
))
2283 draw_rect(dr
, lx
, ly
,
2284 abs(xoff
)+2*xnudge
+1,
2285 abs(yoff
)+2*ynudge
+1, c
);
2287 draw_rect(dr
, cx
- t16
, cy
- t16
, 2*t16
+1, 2*t16
+1, c
);
2292 static void draw_square(drawing
*dr
, game_drawstate
*ds
, game_ui
*ui
,
2293 int x
, int y
, unsigned int lflags
, char clue
)
2295 int ox
= COORD(x
), oy
= COORD(y
);
2296 int t2
= HALFSZ
, t16
= HALFSZ
/4;
2297 int cx
= ox
+ t2
, cy
= oy
+ t2
;
2302 /* Clip to the grid square. */
2303 clip(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2305 /* Clear the square. */
2306 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
,
2307 (lflags
& DS_CURSOR
) ?
2308 COL_CURSOR_BACKGROUND
: COL_BACKGROUND
);
2311 if (get_gui_style() == GUI_LOOPY
) {
2312 /* Draw small dot, underneath any lines. */
2313 draw_circle(dr
, cx
, cy
, t16
, COL_GRID
, COL_GRID
);
2315 /* Draw outline of grid square */
2316 draw_line(dr
, ox
, oy
, COORD(x
+1), oy
, COL_GRID
);
2317 draw_line(dr
, ox
, oy
, ox
, COORD(y
+1), COL_GRID
);
2320 /* Draw grid: either thin gridlines, or no-line marks.
2321 * We draw these first because the thick laid lines should be on top. */
2322 for (d
= 1; d
< 16; d
*= 2) {
2323 int xoff
= t2
* DX(d
), yoff
= t2
* DY(d
);
2325 if ((x
== 0 && d
== L
) ||
2326 (y
== 0 && d
== U
) ||
2327 (x
== ds
->w
-1 && d
== R
) ||
2328 (y
== ds
->h
-1 && d
== D
))
2329 continue; /* no gridlines out to the border. */
2331 if ((lflags
>> DS_MSHIFT
) & d
) {
2332 /* either a no-line mark ... */
2333 int mx
= cx
+ xoff
, my
= cy
+ yoff
, msz
= t16
;
2335 draw_line(dr
, mx
-msz
, my
-msz
, mx
+msz
, my
+msz
, COL_BLACK
);
2336 draw_line(dr
, mx
-msz
, my
+msz
, mx
+msz
, my
-msz
, COL_BLACK
);
2338 if (get_gui_style() == GUI_LOOPY
) {
2339 /* draw grid lines connecting centre of cells */
2340 draw_line(dr
, cx
, cy
, cx
+xoff
, cy
+yoff
, COL_GRID
);
2345 /* Draw each of the four directions, where laid (or error, or drag, etc.)
2346 * Order is important here, specifically for the eventual colours of the
2347 * exposed end caps. */
2348 draw_lines_specific(dr
, ds
, x
, y
, lflags
, 0,
2349 (lflags
& DS_FLASH ? COL_FLASH
: COL_BLACK
));
2350 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_ESHIFT
, COL_ERROR
);
2351 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_DSHIFT
, COL_DRAGOFF
);
2352 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_DSHIFT
, COL_DRAGON
);
2354 /* Draw a clue, if present */
2355 if (clue
!= NOCLUE
) {
2356 int c
= (lflags
& DS_FLASH
) ? COL_FLASH
:
2357 (clue
== STRAIGHT
) ? COL_WHITE
: COL_BLACK
;
2359 if (lflags
& DS_ERROR_CLUE
) /* draw a bigger 'error' clue circle. */
2360 draw_circle(dr
, cx
, cy
, TILE_SIZE
*3/8, COL_ERROR
, COL_ERROR
);
2362 draw_circle(dr
, cx
, cy
, TILE_SIZE
/4, c
, COL_BLACK
);
2366 draw_update(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2369 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2370 game_state
*state
, int dir
, game_ui
*ui
,
2371 float animtime
, float flashtime
)
2373 int w
= state
->shared
->w
, h
= state
->shared
->h
, sz
= state
->shared
->sz
;
2374 int x
, y
, force
= 0, flashing
= 0;
2378 * The initial contents of the window are not guaranteed and
2379 * can vary with front ends. To be on the safe side, all games
2380 * should start by drawing a big background-colour rectangle
2381 * covering the whole window.
2383 draw_rect(dr
, 0, 0, w
*TILE_SIZE
+ 2*BORDER
, h
*TILE_SIZE
+ 2*BORDER
,
2386 if (get_gui_style() == GUI_MASYU
) {
2388 * Smaller black rectangle which is the main grid.
2390 draw_rect(dr
, BORDER
- BORDER_WIDTH
, BORDER
- BORDER_WIDTH
,
2391 w
*TILE_SIZE
+ 2*BORDER_WIDTH
+ 1,
2392 h
*TILE_SIZE
+ 2*BORDER_WIDTH
+ 1,
2396 draw_update(dr
, 0, 0, w
*TILE_SIZE
+ 2*BORDER
, h
*TILE_SIZE
+ 2*BORDER
);
2402 if (flashtime
> 0 &&
2403 (flashtime
<= FLASH_TIME
/3 ||
2404 flashtime
>= FLASH_TIME
*2/3))
2405 flashing
= DS_FLASH
;
2407 memset(ds
->draglines
, 0, sz
);
2408 if (ui
->ndragcoords
> 0) {
2409 int i
, clearing
= TRUE
;
2410 for (i
= 0; i
< ui
->ndragcoords
- 1; i
++) {
2411 int sx
, sy
, dx
, dy
, dir
, oldstate
, newstate
;
2412 interpret_ui_drag(state
, ui
, &clearing
, i
, &sx
, &sy
, &dx
, &dy
,
2413 &dir
, &oldstate
, &newstate
);
2414 ds
->draglines
[sy
*w
+sx
] ^= (oldstate
^ newstate
);
2415 ds
->draglines
[dy
*w
+dx
] ^= (F(oldstate
) ^ F(newstate
));
2419 for (x
= 0; x
< w
; x
++) {
2420 for (y
= 0; y
< h
; y
++) {
2421 unsigned int f
= (unsigned int)state
->lines
[y
*w
+x
];
2422 unsigned int eline
= (unsigned int)(state
->errors
[y
*w
+x
] & (R
|U
|L
|D
));
2424 f
|= eline
<< DS_ESHIFT
;
2425 f
|= ((unsigned int)ds
->draglines
[y
*w
+x
]) << DS_DSHIFT
;
2426 f
|= ((unsigned int)state
->marks
[y
*w
+x
]) << DS_MSHIFT
;
2428 if (state
->errors
[y
*w
+x
] & ERROR_CLUE
)
2433 if (ui
->cursor_active
&& x
== ui
->curx
&& y
== ui
->cury
)
2436 if (f
!= ds
->lflags
[y
*w
+x
] || force
) {
2437 ds
->lflags
[y
*w
+x
] = f
;
2438 draw_square(dr
, ds
, ui
, x
, y
, f
, state
->shared
->clues
[y
*w
+x
]);
2444 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2445 int dir
, game_ui
*ui
)
2450 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2451 int dir
, game_ui
*ui
)
2453 if (!oldstate
->completed
&&
2454 newstate
->completed
&& !newstate
->used_solve
)
2460 static int game_status(game_state
*state
)
2462 return state
->completed ?
+1 : 0;
2465 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2470 static void game_print_size(game_params
*params
, float *x
, float *y
)
2475 * I'll use 6mm squares by default.
2477 game_compute_size(params
, 600, &pw
, &ph
);
2482 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2484 int w
= state
->shared
->w
, h
= state
->shared
->h
, x
, y
;
2485 int black
= print_mono_colour(dr
, 0);
2486 int white
= print_mono_colour(dr
, 1);
2488 /* No GUI_LOOPY here: only use the familiar masyu style. */
2490 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2491 game_drawstate
*ds
= game_new_drawstate(dr
, state
);
2492 game_set_size(dr
, ds
, NULL
, tilesize
);
2494 /* Draw grid outlines (black). */
2495 for (x
= 0; x
<= w
; x
++)
2496 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(h
), black
);
2497 for (y
= 0; y
<= h
; y
++)
2498 draw_line(dr
, COORD(0), COORD(y
), COORD(w
), COORD(y
), black
);
2500 for (x
= 0; x
< w
; x
++) {
2501 for (y
= 0; y
< h
; y
++) {
2502 int cx
= COORD(x
) + HALFSZ
, cy
= COORD(y
) + HALFSZ
;
2503 int clue
= state
->shared
->clues
[y
*w
+x
];
2505 draw_lines_specific(dr
, ds
, x
, y
, state
->lines
[y
*w
+x
], 0, black
);
2507 if (clue
!= NOCLUE
) {
2508 int c
= (clue
== CORNER
) ? black
: white
;
2509 draw_circle(dr
, cx
, cy
, TILE_SIZE
/4, c
, black
);
2514 game_free_drawstate(dr
, ds
);
2518 #define thegame pearl
2521 const struct game thegame
= {
2522 "Pearl", "games.pearl", "pearl",
2529 TRUE
, game_configure
, custom_params
,
2537 FALSE
, game_can_format_as_text_now
, game_text_format
,
2545 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
2548 game_free_drawstate
,
2553 TRUE
, FALSE
, game_print_size
, game_print
,
2554 FALSE
, /* wants_statusbar */
2555 FALSE
, game_timing_state
,
2559 #ifdef STANDALONE_SOLVER
2564 const char *quis
= NULL
;
2566 static void usage(FILE *out
) {
2567 fprintf(out
, "usage: %s <params>\n", quis
);
2570 static void pnum(int n
, int ntot
, const char *desc
)
2572 printf("%2.1f%% (%d) %s", (double)n
*100.0 / (double)ntot
, n
, desc
);
2575 static void start_soak(game_params
*p
, random_state
*rs
, int nsecs
)
2577 time_t tt_start
, tt_now
, tt_last
;
2578 int n
= 0, nsolved
= 0, nimpossible
= 0, ret
;
2581 tt_start
= tt_last
= time(NULL
);
2583 /* Currently this generates puzzles of any difficulty (trying to solve it
2584 * on the maximum difficulty level and not checking it's not too easy). */
2585 printf("Soak-testing a %dx%d grid (any difficulty)", p
->w
, p
->h
);
2586 if (nsecs
> 0) printf(" for %d seconds", nsecs
);
2591 grid
= snewn(p
->w
*p
->h
, char);
2592 clues
= snewn(p
->w
*p
->h
, char);
2595 n
+= new_clues(p
, rs
, clues
, grid
); /* should be 1, with nosolve */
2597 ret
= pearl_solve(p
->w
, p
->h
, clues
, grid
, DIFF_TRICKY
, FALSE
);
2598 if (ret
<= 0) nimpossible
++;
2599 if (ret
== 1) nsolved
++;
2601 tt_now
= time(NULL
);
2602 if (tt_now
> tt_last
) {
2605 printf("%d total, %3.1f/s, ",
2606 n
, (double)n
/ ((double)tt_now
- tt_start
));
2607 pnum(nsolved
, n
, "solved"); printf(", ");
2608 printf("%3.1f/s", (double)nsolved
/ ((double)tt_now
- tt_start
));
2609 if (nimpossible
> 0)
2610 pnum(nimpossible
, n
, "impossible");
2613 if (nsecs
> 0 && (tt_now
- tt_start
) > nsecs
) {
2623 int main(int argc
, const char *argv
[])
2625 game_params
*p
= NULL
;
2626 random_state
*rs
= NULL
;
2627 time_t seed
= time(NULL
);
2628 char *id
= NULL
, *err
;
2630 setvbuf(stdout
, NULL
, _IONBF
, 0);
2634 while (--argc
> 0) {
2635 char *p
= (char*)(*++argv
);
2636 if (!strcmp(p
, "-e") || !strcmp(p
, "--seed")) {
2637 seed
= atoi(*++argv
);
2639 } else if (*p
== '-') {
2640 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
2648 rs
= random_new((void*)&seed
, sizeof(time_t));
2649 p
= default_params();
2652 if (strchr(id
, ':')) {
2653 fprintf(stderr
, "soak takes params only.\n");
2657 decode_params(p
, id
);
2658 err
= validate_params(p
, 1);
2660 fprintf(stderr
, "%s: %s", argv
[0], err
);
2664 start_soak(p
, rs
, 0); /* run forever */
2668 for (i
= 5; i
<= 12; i
++) {
2670 start_soak(p
, rs
, 5);
2683 /* vim: set shiftwidth=4 tabstop=8: */