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
];
1651 /* completion check:
1653 * - no clues must be contradicted (highlight clue itself in error if so)
1654 * - if there is a closed loop it must include every line segment laid
1655 * - if there's a smaller closed loop then highlight whole loop as error
1656 * - no square must have more than 3 lines radiating from centre point
1657 * (highlight all lines in that square as error if so)
1660 static char *solve_for_diff(game_state
*state
, char *old_lines
, char *new_lines
)
1662 int w
= state
->shared
->w
, h
= state
->shared
->h
, i
;
1663 char *move
= snewn(w
*h
*40, char), *p
= move
;
1666 for (i
= 0; i
< w
*h
; i
++) {
1667 if (old_lines
[i
] != new_lines
[i
]) {
1668 p
+= sprintf(p
, ";R%d,%d,%d", new_lines
[i
], i
%w
, i
/w
);
1672 move
= sresize(move
, p
- move
, char);
1677 static char *solve_game(game_state
*state
, game_state
*currstate
,
1678 char *aux
, char **error
)
1680 game_state
*solved
= dup_game(state
);
1681 int i
, ret
, sz
= state
->shared
->sz
;
1685 for (i
= 0; i
< sz
; i
++) {
1686 if (aux
[i
] >= '0' && aux
[i
] <= '9')
1687 solved
->lines
[i
] = aux
[i
] - '0';
1688 else if (aux
[i
] >= 'A' && aux
[i
] <= 'F')
1689 solved
->lines
[i
] = aux
[i
] - 'A' + 10;
1691 *error
= "invalid char in aux";
1698 /* Try to solve with present (half-solved) state first: if there's no
1699 * solution from there go back to original state. */
1700 ret
= pearl_solve(currstate
->shared
->w
, currstate
->shared
->h
,
1701 currstate
->shared
->clues
, solved
->lines
,
1704 ret
= pearl_solve(state
->shared
->w
, state
->shared
->h
,
1705 state
->shared
->clues
, solved
->lines
,
1711 *error
= "Unable to find solution";
1714 move
= solve_for_diff(solved
, currstate
->lines
, solved
->lines
);
1722 static int game_can_format_as_text_now(game_params
*params
)
1727 static char *game_text_format(game_state
*state
)
1733 int *dragcoords
; /* list of (y*w+x) coords in drag so far */
1734 int ndragcoords
; /* number of entries in dragcoords.
1735 * 0 = click but no drag yet. -1 = no drag at all */
1736 int clickx
, clicky
; /* pixel position of initial click */
1738 int curx
, cury
; /* grid position of keyboard cursor */
1739 int cursor_active
; /* TRUE iff cursor is shown */
1742 static game_ui
*new_ui(game_state
*state
)
1744 game_ui
*ui
= snew(game_ui
);
1745 int sz
= state
->shared
->sz
;
1747 ui
->ndragcoords
= -1;
1748 ui
->dragcoords
= snewn(sz
, int);
1749 ui
->cursor_active
= FALSE
;
1750 ui
->curx
= ui
->cury
= 0;
1755 static void free_ui(game_ui
*ui
)
1757 sfree(ui
->dragcoords
);
1761 static char *encode_ui(game_ui
*ui
)
1766 static void decode_ui(game_ui
*ui
, char *encoding
)
1770 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1771 game_state
*newstate
)
1775 #define PREFERRED_TILE_SIZE 31
1776 #define HALFSZ (ds->halfsz)
1777 #define TILE_SIZE (ds->halfsz*2 + 1)
1779 #define BORDER ((get_gui_style() == GUI_LOOPY) ? (TILE_SIZE/8) : (TILE_SIZE/2))
1781 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1783 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
1784 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1785 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) )
1787 #define DS_ESHIFT 4 /* R/U/L/D shift, for error flags */
1788 #define DS_DSHIFT 8 /* R/U/L/D shift, for drag-in-progress flags */
1789 #define DS_MSHIFT 12 /* shift for no-line mark */
1791 #define DS_ERROR_CLUE (1 << 20)
1792 #define DS_FLASH (1 << 21)
1793 #define DS_CURSOR (1 << 22)
1795 enum { GUI_MASYU
, GUI_LOOPY
};
1797 static int get_gui_style(void)
1799 static int gui_style
= -1;
1801 if (gui_style
== -1) {
1802 char *env
= getenv("PEARL_GUI_LOOPY");
1803 if (env
&& (env
[0] == 'y' || env
[0] == 'Y'))
1804 gui_style
= GUI_LOOPY
;
1806 gui_style
= GUI_MASYU
;
1811 struct game_drawstate
{
1816 unsigned int *lflags
; /* size w*h */
1818 char *draglines
; /* size w*h; lines flipped by current drag */
1821 static void update_ui_drag(game_state
*state
, game_ui
*ui
, int gx
, int gy
)
1823 int /* sz = state->shared->sz, */ w
= state
->shared
->w
;
1827 if (!INGRID(state
, gx
, gy
))
1828 return; /* square is outside grid */
1830 if (ui
->ndragcoords
< 0)
1831 return; /* drag not in progress anyway */
1835 lastpos
= ui
->dragcoords
[ui
->ndragcoords
> 0 ? ui
->ndragcoords
-1 : 0];
1837 return; /* same square as last visited one */
1839 /* Drag confirmed, if it wasn't already. */
1840 if (ui
->ndragcoords
== 0)
1841 ui
->ndragcoords
= 1;
1844 * Dragging the mouse into a square that's already been visited by
1845 * the drag path so far has the effect of truncating the path back
1846 * to that square, so a player can back out part of an uncommitted
1847 * drag without having to let go of the mouse.
1849 for (i
= 0; i
< ui
->ndragcoords
; i
++)
1850 if (pos
== ui
->dragcoords
[i
]) {
1851 ui
->ndragcoords
= i
+1;
1856 * Otherwise, dragging the mouse into a square that's a rook-move
1857 * away from the last one on the path extends the path.
1859 oy
= ui
->dragcoords
[ui
->ndragcoords
-1] / w
;
1860 ox
= ui
->dragcoords
[ui
->ndragcoords
-1] % w
;
1861 if (ox
== gx
|| oy
== gy
) {
1862 int dx
= (gx
< ox ?
-1 : gx
> ox ?
+1 : 0);
1863 int dy
= (gy
< oy ?
-1 : gy
> oy ?
+1 : 0);
1864 int dir
= (dy
>0 ? D
: dy
<0 ? U
: dx
>0 ? R
: L
);
1865 while (ox
!= gx
|| oy
!= gy
) {
1867 * If the drag attempts to cross a 'no line here' mark,
1868 * stop there. We physically don't allow the user to drag
1871 if (state
->marks
[oy
*w
+ox
] & dir
)
1875 ui
->dragcoords
[ui
->ndragcoords
++] = oy
* w
+ ox
;
1880 * Failing that, we do nothing at all: if the user has dragged
1881 * diagonally across the board, they'll just have to return the
1882 * mouse to the last known position and do whatever they meant to
1883 * do again, more slowly and clearly.
1888 * Routine shared between interpret_move and game_redraw to work out
1889 * the intended effect of a drag path on the grid.
1891 * Call it in a loop, like this:
1893 * int clearing = TRUE;
1894 * for (i = 0; i < ui->ndragcoords - 1; i++) {
1895 * int sx, sy, dx, dy, dir, oldstate, newstate;
1896 * interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
1897 * &dir, &oldstate, &newstate);
1899 * [do whatever is needed to handle the fact that the drag
1900 * wants the edge from sx,sy to dx,dy (heading in direction
1901 * 'dir' at the sx,sy end) to be changed from state oldstate
1902 * to state newstate, each of which equals either 0 or dir]
1905 static void interpret_ui_drag(game_state
*state
, game_ui
*ui
, int *clearing
,
1906 int i
, int *sx
, int *sy
, int *dx
, int *dy
,
1907 int *dir
, int *oldstate
, int *newstate
)
1909 int w
= state
->shared
->w
;
1910 int sp
= ui
->dragcoords
[i
], dp
= ui
->dragcoords
[i
+1];
1915 *dir
= (*dy
>*sy ? D
: *dy
<*sy ? U
: *dx
>*sx ? R
: L
);
1916 *oldstate
= state
->lines
[sp
] & *dir
;
1919 * The edge we've dragged over was previously
1920 * present. Set it to absent, unless we've already
1921 * stopped doing that.
1923 *newstate
= *clearing ?
0 : *dir
;
1926 * The edge we've dragged over was previously
1927 * absent. Set it to present, and cancel the
1928 * 'clearing' flag so that all subsequent edges in
1929 * the drag are set rather than cleared.
1936 static char *mark_in_direction(game_state
*state
, int x
, int y
, int dir
,
1937 int ismark
, char *buf
)
1939 int w
= state
->shared
->w
/*, h = state->shared->h, sz = state->shared->sz */;
1940 int x2
= x
+ DX(dir
);
1941 int y2
= y
+ DY(dir
);
1943 char ch
= ismark ?
'M' : 'F';
1945 if (!INGRID(state
, x
, y
) || !INGRID(state
, x2
, y2
)) return "";
1946 /* disallow laying a mark over a line, or vice versa. */
1948 if ((state
->lines
[y
*w
+x
] & dir
) || (state
->lines
[y2
*w
+x2
] & dir2
))
1951 if ((state
->marks
[y
*w
+x
] & dir
) || (state
->marks
[y2
*w
+x2
] & dir2
))
1955 sprintf(buf
, "%c%d,%d,%d;%c%d,%d,%d", ch
, dir
, x
, y
, ch
, dir2
, x2
, y2
);
1959 #define KEY_DIRECTION(btn) (\
1960 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
1961 (btn) == CURSOR_LEFT ? L : R)
1963 static char *interpret_move(game_state
*state
, game_ui
*ui
, const game_drawstate
*ds
,
1964 int x
, int y
, int button
)
1966 int w
= state
->shared
->w
, h
= state
->shared
->h
/*, sz = state->shared->sz */;
1967 int gx
= FROMCOORD(x
), gy
= FROMCOORD(y
), i
;
1968 int release
= FALSE
;
1971 if (IS_MOUSE_DOWN(button
)) {
1972 ui
->cursor_active
= FALSE
;
1974 if (!INGRID(state
, gx
, gy
)) {
1975 ui
->ndragcoords
= -1;
1979 ui
->clickx
= x
; ui
->clicky
= y
;
1980 ui
->dragcoords
[0] = gy
* w
+ gx
;
1981 ui
->ndragcoords
= 0; /* will be 1 once drag is confirmed */
1986 if (button
== LEFT_DRAG
&& ui
->ndragcoords
>= 0) {
1987 update_ui_drag(state
, ui
, gx
, gy
);
1991 if (IS_MOUSE_RELEASE(button
)) release
= TRUE
;
1993 if (IS_CURSOR_MOVE(button
& ~MOD_MASK
)) {
1994 if (!ui
->cursor_active
) {
1995 ui
->cursor_active
= TRUE
;
1996 } else if (button
& (MOD_SHFT
| MOD_CTRL
)) {
1997 if (ui
->ndragcoords
> 0) return NULL
;
1998 ui
->ndragcoords
= -1;
1999 return mark_in_direction(state
, ui
->curx
, ui
->cury
,
2000 KEY_DIRECTION(button
& ~MOD_MASK
),
2001 (button
& MOD_SHFT
), tmpbuf
);
2003 move_cursor(button
, &ui
->curx
, &ui
->cury
, w
, h
, FALSE
);
2004 if (ui
->ndragcoords
>= 0)
2005 update_ui_drag(state
, ui
, ui
->curx
, ui
->cury
);
2010 if (IS_CURSOR_SELECT(button
& ~MOD_MASK
)) {
2011 if (!ui
->cursor_active
) {
2012 ui
->cursor_active
= TRUE
;
2014 } else if (button
== CURSOR_SELECT
) {
2015 if (ui
->ndragcoords
== -1) {
2016 ui
->ndragcoords
= 0;
2017 ui
->dragcoords
[0] = ui
->cury
* w
+ ui
->curx
;
2018 ui
->clickx
= CENTERED_COORD(ui
->curx
);
2019 ui
->clicky
= CENTERED_COORD(ui
->cury
);
2021 } else release
= TRUE
;
2022 } else if (button
== CURSOR_SELECT2
&& ui
->ndragcoords
>= 0) {
2023 ui
->ndragcoords
= -1;
2029 if (ui
->ndragcoords
> 0) {
2030 /* End of a drag: process the cached line data. */
2031 int buflen
= 0, bufsize
= 256, tmplen
;
2033 const char *sep
= "";
2034 int clearing
= TRUE
;
2036 for (i
= 0; i
< ui
->ndragcoords
- 1; i
++) {
2037 int sx
, sy
, dx
, dy
, dir
, oldstate
, newstate
;
2038 interpret_ui_drag(state
, ui
, &clearing
, i
, &sx
, &sy
, &dx
, &dy
,
2039 &dir
, &oldstate
, &newstate
);
2041 if (oldstate
!= newstate
) {
2042 if (!buf
) buf
= snewn(bufsize
, char);
2043 tmplen
= sprintf(tmpbuf
, "%sF%d,%d,%d;F%d,%d,%d", sep
,
2044 dir
, sx
, sy
, F(dir
), dx
, dy
);
2045 if (buflen
+ tmplen
>= bufsize
) {
2046 bufsize
= (buflen
+ tmplen
) * 5 / 4 + 256;
2047 buf
= sresize(buf
, bufsize
, char);
2049 strcpy(buf
+ buflen
, tmpbuf
);
2055 ui
->ndragcoords
= -1;
2057 return buf ? buf
: "";
2058 } else if (ui
->ndragcoords
== 0) {
2059 /* Click (or tiny drag). Work out which edge we were
2063 ui
->ndragcoords
= -1;
2066 * We process clicks based on the mouse-down location,
2067 * because that's more natural for a user to carefully
2068 * control than the mouse-up.
2075 cx
= CENTERED_COORD(gx
);
2076 cy
= CENTERED_COORD(gy
);
2078 if (!INGRID(state
, gx
, gy
)) return "";
2080 if (max(abs(x
-cx
),abs(y
-cy
)) < TILE_SIZE
/4) {
2081 /* TODO closer to centre of grid: process as a cell click not an edge click. */
2086 if (abs(x
-cx
) < abs(y
-cy
)) {
2087 /* Closest to top/bottom edge. */
2088 direction
= (y
< cy
) ? U
: D
;
2090 /* Closest to left/right edge. */
2091 direction
= (x
< cx
) ? L
: R
;
2093 return mark_in_direction(state
, gx
, gy
, direction
,
2094 (button
== RIGHT_RELEASE
), tmpbuf
);
2099 if (button
== 'H' || button
== 'h')
2105 static game_state
*execute_move(game_state
*state
, char *move
)
2107 int w
= state
->shared
->w
, h
= state
->shared
->h
;
2110 game_state
*ret
= dup_game(state
);
2112 debug(("move: %s\n", move
));
2117 ret
->used_solve
= TRUE
;
2119 } else if (c
== 'L' || c
== 'N' || c
== 'R' || c
== 'F' || c
== 'M') {
2120 /* 'line' or 'noline' or 'replace' or 'flip' or 'mark' */
2122 if (sscanf(move
, "%d,%d,%d%n", &l
, &x
, &y
, &n
) != 3)
2124 if (!INGRID(state
, x
, y
)) goto badmove
;
2125 if (l
< 0 || l
> 15) goto badmove
;
2128 ret
->lines
[y
*w
+ x
] |= (char)l
;
2130 ret
->lines
[y
*w
+ x
] &= ~((char)l
);
2131 else if (c
== 'R') {
2132 ret
->lines
[y
*w
+ x
] = (char)l
;
2133 ret
->marks
[y
*w
+ x
] &= ~((char)l
); /* erase marks too */
2134 } else if (c
== 'F')
2135 ret
->lines
[y
*w
+ x
] ^= (char)l
;
2137 ret
->marks
[y
*w
+ x
] ^= (char)l
;
2140 * If we ended up trying to lay a line _over_ a mark,
2141 * that's a failed move: interpret_move() should have
2142 * ensured we never received a move string like that in
2145 if ((ret
->lines
[y
*w
+ x
] & (char)l
) &&
2146 (ret
->marks
[y
*w
+ x
] & (char)l
))
2150 } else if (strcmp(move
, "H") == 0) {
2151 pearl_solve(ret
->shared
->w
, ret
->shared
->h
,
2152 ret
->shared
->clues
, ret
->lines
, DIFFCOUNT
, TRUE
);
2153 for (n
= 0; n
< w
*h
; n
++)
2154 ret
->marks
[n
] &= ~ret
->lines
[n
]; /* erase marks too */
2165 check_completion(ret
, TRUE
);
2174 /* ----------------------------------------------------------------------
2178 #define FLASH_TIME 0.5F
2180 static void game_compute_size(game_params
*params
, int tilesize
,
2183 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2184 struct { int halfsz
; } ads
, *ds
= &ads
;
2185 ads
.halfsz
= (tilesize
-1)/2;
2187 *x
= (params
->w
) * TILE_SIZE
+ 2 * BORDER
;
2188 *y
= (params
->h
) * TILE_SIZE
+ 2 * BORDER
;
2191 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2192 game_params
*params
, int tilesize
)
2194 ds
->halfsz
= (tilesize
-1)/2;
2197 static float *game_colours(frontend
*fe
, int *ncolours
)
2199 float *ret
= snewn(3 * NCOLOURS
, float);
2202 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
2204 for (i
= 0; i
< 3; i
++) {
2205 ret
[COL_BLACK
* 3 + i
] = 0.0F
;
2206 ret
[COL_WHITE
* 3 + i
] = 1.0F
;
2207 ret
[COL_GRID
* 3 + i
] = 0.4F
;
2210 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
2211 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
2212 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
2214 ret
[COL_DRAGON
* 3 + 0] = 0.0F
;
2215 ret
[COL_DRAGON
* 3 + 1] = 0.0F
;
2216 ret
[COL_DRAGON
* 3 + 2] = 1.0F
;
2218 ret
[COL_DRAGOFF
* 3 + 0] = 0.8F
;
2219 ret
[COL_DRAGOFF
* 3 + 1] = 0.8F
;
2220 ret
[COL_DRAGOFF
* 3 + 2] = 1.0F
;
2222 ret
[COL_FLASH
* 3 + 0] = 1.0F
;
2223 ret
[COL_FLASH
* 3 + 1] = 1.0F
;
2224 ret
[COL_FLASH
* 3 + 2] = 1.0F
;
2226 *ncolours
= NCOLOURS
;
2231 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
2233 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2237 ds
->started
= FALSE
;
2239 ds
->w
= state
->shared
->w
;
2240 ds
->h
= state
->shared
->h
;
2241 ds
->sz
= state
->shared
->sz
;
2242 ds
->lflags
= snewn(ds
->sz
, unsigned int);
2243 for (i
= 0; i
< ds
->sz
; i
++)
2246 ds
->draglines
= snewn(ds
->sz
, char);
2251 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2253 sfree(ds
->draglines
);
2258 static void draw_lines_specific(drawing
*dr
, game_drawstate
*ds
,
2259 int x
, int y
, unsigned int lflags
,
2260 unsigned int shift
, int c
)
2262 int ox
= COORD(x
), oy
= COORD(y
);
2263 int t2
= HALFSZ
, t16
= HALFSZ
/4;
2264 int cx
= ox
+ t2
, cy
= oy
+ t2
;
2267 /* Draw each of the four directions, where laid (or error, or drag, etc.) */
2268 for (d
= 1; d
< 16; d
*= 2) {
2269 int xoff
= t2
* DX(d
), yoff
= t2
* DY(d
);
2270 int xnudge
= abs(t16
* DX(C(d
))), ynudge
= abs(t16
* DY(C(d
)));
2272 if ((lflags
>> shift
) & d
) {
2273 int lx
= cx
+ ((xoff
< 0) ? xoff
: 0) - xnudge
;
2274 int ly
= cy
+ ((yoff
< 0) ? yoff
: 0) - ynudge
;
2276 if (c
== COL_DRAGOFF
&& !(lflags
& d
))
2278 if (c
== COL_DRAGON
&& (lflags
& d
))
2281 draw_rect(dr
, lx
, ly
,
2282 abs(xoff
)+2*xnudge
+1,
2283 abs(yoff
)+2*ynudge
+1, c
);
2285 draw_rect(dr
, cx
- t16
, cy
- t16
, 2*t16
+1, 2*t16
+1, c
);
2290 static void draw_square(drawing
*dr
, game_drawstate
*ds
, game_ui
*ui
,
2291 int x
, int y
, unsigned int lflags
, char clue
)
2293 int ox
= COORD(x
), oy
= COORD(y
);
2294 int t2
= HALFSZ
, t16
= HALFSZ
/4;
2295 int cx
= ox
+ t2
, cy
= oy
+ t2
;
2300 /* Clip to the grid square. */
2301 clip(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2303 /* Clear the square. */
2304 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
,
2305 (lflags
& DS_CURSOR
) ?
2306 COL_CURSOR_BACKGROUND
: COL_BACKGROUND
);
2309 if (get_gui_style() == GUI_LOOPY
) {
2310 /* Draw small dot, underneath any lines. */
2311 draw_circle(dr
, cx
, cy
, t16
, COL_GRID
, COL_GRID
);
2313 /* Draw outline of grid square */
2314 draw_line(dr
, ox
, oy
, COORD(x
+1), oy
, COL_GRID
);
2315 draw_line(dr
, ox
, oy
, ox
, COORD(y
+1), COL_GRID
);
2318 /* Draw grid: either thin gridlines, or no-line marks.
2319 * We draw these first because the thick laid lines should be on top. */
2320 for (d
= 1; d
< 16; d
*= 2) {
2321 int xoff
= t2
* DX(d
), yoff
= t2
* DY(d
);
2323 if ((x
== 0 && d
== L
) ||
2324 (y
== 0 && d
== U
) ||
2325 (x
== ds
->w
-1 && d
== R
) ||
2326 (y
== ds
->h
-1 && d
== D
))
2327 continue; /* no gridlines out to the border. */
2329 if ((lflags
>> DS_MSHIFT
) & d
) {
2330 /* either a no-line mark ... */
2331 int mx
= cx
+ xoff
, my
= cy
+ yoff
, msz
= t16
;
2333 draw_line(dr
, mx
-msz
, my
-msz
, mx
+msz
, my
+msz
, COL_BLACK
);
2334 draw_line(dr
, mx
-msz
, my
+msz
, mx
+msz
, my
-msz
, COL_BLACK
);
2336 if (get_gui_style() == GUI_LOOPY
) {
2337 /* draw grid lines connecting centre of cells */
2338 draw_line(dr
, cx
, cy
, cx
+xoff
, cy
+yoff
, COL_GRID
);
2343 /* Draw each of the four directions, where laid (or error, or drag, etc.)
2344 * Order is important here, specifically for the eventual colours of the
2345 * exposed end caps. */
2346 draw_lines_specific(dr
, ds
, x
, y
, lflags
, 0,
2347 (lflags
& DS_FLASH ? COL_FLASH
: COL_BLACK
));
2348 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_ESHIFT
, COL_ERROR
);
2349 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_DSHIFT
, COL_DRAGOFF
);
2350 draw_lines_specific(dr
, ds
, x
, y
, lflags
, DS_DSHIFT
, COL_DRAGON
);
2352 /* Draw a clue, if present */
2353 if (clue
!= NOCLUE
) {
2354 int c
= (lflags
& DS_FLASH
) ? COL_FLASH
:
2355 (clue
== STRAIGHT
) ? COL_WHITE
: COL_BLACK
;
2357 if (lflags
& DS_ERROR_CLUE
) /* draw a bigger 'error' clue circle. */
2358 draw_circle(dr
, cx
, cy
, TILE_SIZE
*3/8, COL_ERROR
, COL_ERROR
);
2360 draw_circle(dr
, cx
, cy
, TILE_SIZE
/4, c
, COL_BLACK
);
2364 draw_update(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
2367 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2368 game_state
*state
, int dir
, game_ui
*ui
,
2369 float animtime
, float flashtime
)
2371 int w
= state
->shared
->w
, h
= state
->shared
->h
, sz
= state
->shared
->sz
;
2372 int x
, y
, force
= 0, flashing
= 0;
2376 * The initial contents of the window are not guaranteed and
2377 * can vary with front ends. To be on the safe side, all games
2378 * should start by drawing a big background-colour rectangle
2379 * covering the whole window.
2381 draw_rect(dr
, 0, 0, w
*TILE_SIZE
+ 2*BORDER
, h
*TILE_SIZE
+ 2*BORDER
,
2384 if (get_gui_style() == GUI_MASYU
) {
2386 * Smaller black rectangle which is the main grid.
2388 draw_rect(dr
, BORDER
- BORDER_WIDTH
, BORDER
- BORDER_WIDTH
,
2389 w
*TILE_SIZE
+ 2*BORDER_WIDTH
+ 1,
2390 h
*TILE_SIZE
+ 2*BORDER_WIDTH
+ 1,
2394 draw_update(dr
, 0, 0, w
*TILE_SIZE
+ 2*BORDER
, h
*TILE_SIZE
+ 2*BORDER
);
2400 if (flashtime
> 0 &&
2401 (flashtime
<= FLASH_TIME
/3 ||
2402 flashtime
>= FLASH_TIME
*2/3))
2403 flashing
= DS_FLASH
;
2405 memset(ds
->draglines
, 0, sz
);
2406 if (ui
->ndragcoords
> 0) {
2407 int i
, clearing
= TRUE
;
2408 for (i
= 0; i
< ui
->ndragcoords
- 1; i
++) {
2409 int sx
, sy
, dx
, dy
, dir
, oldstate
, newstate
;
2410 interpret_ui_drag(state
, ui
, &clearing
, i
, &sx
, &sy
, &dx
, &dy
,
2411 &dir
, &oldstate
, &newstate
);
2412 ds
->draglines
[sy
*w
+sx
] ^= (oldstate
^ newstate
);
2413 ds
->draglines
[dy
*w
+dx
] ^= (F(oldstate
) ^ F(newstate
));
2417 for (x
= 0; x
< w
; x
++) {
2418 for (y
= 0; y
< h
; y
++) {
2419 unsigned int f
= (unsigned int)state
->lines
[y
*w
+x
];
2420 unsigned int eline
= (unsigned int)(state
->errors
[y
*w
+x
] & (R
|U
|L
|D
));
2422 f
|= eline
<< DS_ESHIFT
;
2423 f
|= ((unsigned int)ds
->draglines
[y
*w
+x
]) << DS_DSHIFT
;
2424 f
|= ((unsigned int)state
->marks
[y
*w
+x
]) << DS_MSHIFT
;
2426 if (state
->errors
[y
*w
+x
] & ERROR_CLUE
)
2431 if (ui
->cursor_active
&& x
== ui
->curx
&& y
== ui
->cury
)
2434 if (f
!= ds
->lflags
[y
*w
+x
] || force
) {
2435 ds
->lflags
[y
*w
+x
] = f
;
2436 draw_square(dr
, ds
, ui
, x
, y
, f
, state
->shared
->clues
[y
*w
+x
]);
2442 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2443 int dir
, game_ui
*ui
)
2448 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2449 int dir
, game_ui
*ui
)
2451 if (!oldstate
->completed
&& newstate
->completed
&&
2452 !oldstate
->used_solve
&& !newstate
->used_solve
)
2458 static int game_status(game_state
*state
)
2460 return state
->completed ?
+1 : 0;
2463 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2468 static void game_print_size(game_params
*params
, float *x
, float *y
)
2473 * I'll use 6mm squares by default.
2475 game_compute_size(params
, 600, &pw
, &ph
);
2480 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2482 int w
= state
->shared
->w
, h
= state
->shared
->h
, x
, y
;
2483 int black
= print_mono_colour(dr
, 0);
2484 int white
= print_mono_colour(dr
, 1);
2486 /* No GUI_LOOPY here: only use the familiar masyu style. */
2488 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2489 game_drawstate
*ds
= game_new_drawstate(dr
, state
);
2490 game_set_size(dr
, ds
, NULL
, tilesize
);
2492 /* Draw grid outlines (black). */
2493 for (x
= 0; x
<= w
; x
++)
2494 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(h
), black
);
2495 for (y
= 0; y
<= h
; y
++)
2496 draw_line(dr
, COORD(0), COORD(y
), COORD(w
), COORD(y
), black
);
2498 for (x
= 0; x
< w
; x
++) {
2499 for (y
= 0; y
< h
; y
++) {
2500 int cx
= COORD(x
) + HALFSZ
, cy
= COORD(y
) + HALFSZ
;
2501 int clue
= state
->shared
->clues
[y
*w
+x
];
2503 draw_lines_specific(dr
, ds
, x
, y
, state
->lines
[y
*w
+x
], 0, black
);
2505 if (clue
!= NOCLUE
) {
2506 int c
= (clue
== CORNER
) ? black
: white
;
2507 draw_circle(dr
, cx
, cy
, TILE_SIZE
/4, c
, black
);
2512 game_free_drawstate(dr
, ds
);
2516 #define thegame pearl
2519 const struct game thegame
= {
2520 "Pearl", "games.pearl", "pearl",
2527 TRUE
, game_configure
, custom_params
,
2535 FALSE
, game_can_format_as_text_now
, game_text_format
,
2543 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
2546 game_free_drawstate
,
2551 TRUE
, FALSE
, game_print_size
, game_print
,
2552 FALSE
, /* wants_statusbar */
2553 FALSE
, game_timing_state
,
2557 #ifdef STANDALONE_SOLVER
2562 const char *quis
= NULL
;
2564 static void usage(FILE *out
) {
2565 fprintf(out
, "usage: %s <params>\n", quis
);
2568 static void pnum(int n
, int ntot
, const char *desc
)
2570 printf("%2.1f%% (%d) %s", (double)n
*100.0 / (double)ntot
, n
, desc
);
2573 static void start_soak(game_params
*p
, random_state
*rs
, int nsecs
)
2575 time_t tt_start
, tt_now
, tt_last
;
2576 int n
= 0, nsolved
= 0, nimpossible
= 0, ret
;
2579 tt_start
= tt_last
= time(NULL
);
2581 /* Currently this generates puzzles of any difficulty (trying to solve it
2582 * on the maximum difficulty level and not checking it's not too easy). */
2583 printf("Soak-testing a %dx%d grid (any difficulty)", p
->w
, p
->h
);
2584 if (nsecs
> 0) printf(" for %d seconds", nsecs
);
2589 grid
= snewn(p
->w
*p
->h
, char);
2590 clues
= snewn(p
->w
*p
->h
, char);
2593 n
+= new_clues(p
, rs
, clues
, grid
); /* should be 1, with nosolve */
2595 ret
= pearl_solve(p
->w
, p
->h
, clues
, grid
, DIFF_TRICKY
, FALSE
);
2596 if (ret
<= 0) nimpossible
++;
2597 if (ret
== 1) nsolved
++;
2599 tt_now
= time(NULL
);
2600 if (tt_now
> tt_last
) {
2603 printf("%d total, %3.1f/s, ",
2604 n
, (double)n
/ ((double)tt_now
- tt_start
));
2605 pnum(nsolved
, n
, "solved"); printf(", ");
2606 printf("%3.1f/s", (double)nsolved
/ ((double)tt_now
- tt_start
));
2607 if (nimpossible
> 0)
2608 pnum(nimpossible
, n
, "impossible");
2611 if (nsecs
> 0 && (tt_now
- tt_start
) > nsecs
) {
2621 int main(int argc
, const char *argv
[])
2623 game_params
*p
= NULL
;
2624 random_state
*rs
= NULL
;
2625 time_t seed
= time(NULL
);
2626 char *id
= NULL
, *err
;
2628 setvbuf(stdout
, NULL
, _IONBF
, 0);
2632 while (--argc
> 0) {
2633 char *p
= (char*)(*++argv
);
2634 if (!strcmp(p
, "-e") || !strcmp(p
, "--seed")) {
2635 seed
= atoi(*++argv
);
2637 } else if (*p
== '-') {
2638 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
2646 rs
= random_new((void*)&seed
, sizeof(time_t));
2647 p
= default_params();
2650 if (strchr(id
, ':')) {
2651 fprintf(stderr
, "soak takes params only.\n");
2655 decode_params(p
, id
);
2656 err
= validate_params(p
, 1);
2658 fprintf(stderr
, "%s: %s", argv
[0], err
);
2662 start_soak(p
, rs
, 0); /* run forever */
2666 for (i
= 5; i
<= 12; i
++) {
2668 start_soak(p
, rs
, 5);
2681 /* vim: set shiftwidth=4 tabstop=8: */