1 /*
2 * pearl.c: Nikoli's `Masyu' puzzle.
3 */
4
5 /*
6 * TODO:
7 *
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.
19 *
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
30 * dream.
31 */
32
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include <assert.h>
37 #include <ctype.h>
38 #include <math.h>
39
40 #include "puzzles.h"
41 #include "grid.h"
42 #include "loopgen.h"
43
44 #define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0)
45
46 #define NOCLUE 0
47 #define CORNER 1
48 #define STRAIGHT 2
49
50 #define R 1
51 #define U 2
52 #define L 4
53 #define D 8
54
55 #define DX(d) ( ((d)==R) - ((d)==L) )
56 #define DY(d) ( ((d)==D) - ((d)==U) )
57
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)
61
62 #define LR (L | R)
63 #define RL (R | L)
64 #define UD (U | D)
65 #define DU (D | U)
66 #define LU (L | U)
67 #define UL (U | L)
68 #define LD (L | D)
69 #define DL (D | L)
70 #define RU (R | U)
71 #define UR (U | R)
72 #define RD (R | D)
73 #define DR (D | R)
74 #define BLANK 0
75 #define UNKNOWN 15
76
77 #define bLR (1 << LR)
78 #define bRL (1 << RL)
79 #define bUD (1 << UD)
80 #define bDU (1 << DU)
81 #define bLU (1 << LU)
82 #define bUL (1 << UL)
83 #define bLD (1 << LD)
84 #define bDL (1 << DL)
85 #define bRU (1 << RU)
86 #define bUR (1 << UR)
87 #define bRD (1 << RD)
88 #define bDR (1 << DR)
89 #define bBLANK (1 << BLANK)
90
91 enum {
92 COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT,
93 COL_CURSOR_BACKGROUND = COL_LOWLIGHT,
94 COL_BLACK, COL_WHITE,
95 COL_ERROR, COL_GRID, COL_FLASH,
96 COL_DRAGON, COL_DRAGOFF,
97 NCOLOURS
98 };
99
100 /* Macro ickery copied from slant.c */
101 #define DIFFLIST(A) \
102 A(EASY,Easy,e) \
103 A(TRICKY,Tricky,t)
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)
112
113 struct game_params {
114 int w, h;
115 int difficulty;
116 bool nosolve; /* XXX remove me! */
117 };
118
119 struct shared_state {
120 int w, h, sz;
121 char *clues; /* size w*h */
122 int refcnt;
123 };
124
125 #define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->shared->w && \
126 (gy) >= 0 && (gy) < (state)->shared->h)
127 struct game_state {
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 bool completed, used_solve;
133 };
134
135 #define DEFAULT_PRESET 3
136
137 static const struct game_params pearl_presets[] = {
138 {6, 6, DIFF_EASY},
139 {6, 6, DIFF_TRICKY},
140 {8, 8, DIFF_EASY},
141 {8, 8, DIFF_TRICKY},
142 {10, 10, DIFF_EASY},
143 {10, 10, DIFF_TRICKY},
144 {12, 8, DIFF_EASY},
145 {12, 8, DIFF_TRICKY},
146 };
147
default_params(void)148 static game_params *default_params(void)
149 {
150 game_params *ret = snew(game_params);
151
152 *ret = pearl_presets[DEFAULT_PRESET];
153 ret->nosolve = false;
154
155 return ret;
156 }
157
game_fetch_preset(int i,char ** name,game_params ** params)158 static bool game_fetch_preset(int i, char **name, game_params **params)
159 {
160 game_params *ret;
161 char buf[64];
162
163 if (i < 0 || i >= lenof(pearl_presets)) return false;
164
165 ret = default_params();
166 *ret = pearl_presets[i]; /* struct copy */
167 *params = ret;
168
169 sprintf(buf, "%dx%d %s",
170 pearl_presets[i].w, pearl_presets[i].h,
171 pearl_diffnames[pearl_presets[i].difficulty]);
172 *name = dupstr(buf);
173
174 return true;
175 }
176
free_params(game_params * params)177 static void free_params(game_params *params)
178 {
179 sfree(params);
180 }
181
dup_params(const game_params * params)182 static game_params *dup_params(const game_params *params)
183 {
184 game_params *ret = snew(game_params);
185 *ret = *params; /* structure copy */
186 return ret;
187 }
188
decode_params(game_params * ret,char const * string)189 static void decode_params(game_params *ret, char const *string)
190 {
191 ret->w = ret->h = atoi(string);
192 while (*string && isdigit((unsigned char) *string)) ++string;
193 if (*string == 'x') {
194 string++;
195 ret->h = atoi(string);
196 while (*string && isdigit((unsigned char)*string)) string++;
197 }
198
199 ret->difficulty = DIFF_EASY;
200 if (*string == 'd') {
201 int i;
202 string++;
203 for (i = 0; i < DIFFCOUNT; i++)
204 if (*string == pearl_diffchars[i])
205 ret->difficulty = i;
206 if (*string) string++;
207 }
208
209 ret->nosolve = false;
210 if (*string == 'n') {
211 ret->nosolve = true;
212 string++;
213 }
214 }
215
encode_params(const game_params * params,bool full)216 static char *encode_params(const game_params *params, bool full)
217 {
218 char buf[256];
219 sprintf(buf, "%dx%d", params->w, params->h);
220 if (full)
221 sprintf(buf + strlen(buf), "d%c%s",
222 pearl_diffchars[params->difficulty],
223 params->nosolve ? "n" : "");
224 return dupstr(buf);
225 }
226
game_configure(const game_params * params)227 static config_item *game_configure(const game_params *params)
228 {
229 config_item *ret;
230 char buf[64];
231
232 ret = snewn(5, config_item);
233
234 ret[0].name = "Width";
235 ret[0].type = C_STRING;
236 sprintf(buf, "%d", params->w);
237 ret[0].u.string.sval = dupstr(buf);
238
239 ret[1].name = "Height";
240 ret[1].type = C_STRING;
241 sprintf(buf, "%d", params->h);
242 ret[1].u.string.sval = dupstr(buf);
243
244 ret[2].name = "Difficulty";
245 ret[2].type = C_CHOICES;
246 ret[2].u.choices.choicenames = DIFFCONFIG;
247 ret[2].u.choices.selected = params->difficulty;
248
249 ret[3].name = "Allow unsoluble";
250 ret[3].type = C_BOOLEAN;
251 ret[3].u.boolean.bval = params->nosolve;
252
253 ret[4].name = NULL;
254 ret[4].type = C_END;
255
256 return ret;
257 }
258
custom_params(const config_item * cfg)259 static game_params *custom_params(const config_item *cfg)
260 {
261 game_params *ret = snew(game_params);
262
263 ret->w = atoi(cfg[0].u.string.sval);
264 ret->h = atoi(cfg[1].u.string.sval);
265 ret->difficulty = cfg[2].u.choices.selected;
266 ret->nosolve = cfg[3].u.boolean.bval;
267
268 return ret;
269 }
270
validate_params(const game_params * params,bool full)271 static const char *validate_params(const game_params *params, bool full)
272 {
273 if (params->w < 5) return "Width must be at least five";
274 if (params->h < 5) return "Height must be at least five";
275 if (params->difficulty < 0 || params->difficulty >= DIFFCOUNT)
276 return "Unknown difficulty level";
277
278 return NULL;
279 }
280
281 /* ----------------------------------------------------------------------
282 * Solver.
283 */
284
pearl_solve(int w,int h,char * clues,char * result,int difficulty,bool partial)285 static int pearl_solve(int w, int h, char *clues, char *result,
286 int difficulty, bool partial)
287 {
288 int W = 2*w+1, H = 2*h+1;
289 short *workspace;
290 int *dsf, *dsfsize;
291 int x, y, b, d;
292 int ret = -1;
293
294 /*
295 * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature
296 * of the square (x,y), as a logical OR of bitfields.
297 *
298 * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates
299 * whether the horizontal edge between (x,y) and (x+1,y) is
300 * connected (1), disconnected (2) or unknown (3).
301 *
302 * workspace[(2*y+1)*W+(2*x)], indicates the same about the
303 * vertical edge between (x,y) and (x,y+1).
304 *
305 * Initially, every square is considered capable of being in
306 * any of the seven possible states (two straights, four
307 * corners and empty), except those corresponding to clue
308 * squares which are more restricted.
309 *
310 * Initially, all edges are unknown, except the ones around the
311 * grid border which are known to be disconnected.
312 */
313 workspace = snewn(W*H, short);
314 for (x = 0; x < W*H; x++)
315 workspace[x] = 0;
316 /* Square states */
317 for (y = 0; y < h; y++)
318 for (x = 0; x < w; x++)
319 switch (clues[y*w+x]) {
320 case CORNER:
321 workspace[(2*y+1)*W+(2*x+1)] = bLU|bLD|bRU|bRD;
322 break;
323 case STRAIGHT:
324 workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD;
325 break;
326 default:
327 workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD|bLU|bLD|bRU|bRD|bBLANK;
328 break;
329 }
330 /* Horizontal edges */
331 for (y = 0; y <= h; y++)
332 for (x = 0; x < w; x++)
333 workspace[(2*y)*W+(2*x+1)] = (y==0 || y==h ? 2 : 3);
334 /* Vertical edges */
335 for (y = 0; y < h; y++)
336 for (x = 0; x <= w; x++)
337 workspace[(2*y+1)*W+(2*x)] = (x==0 || x==w ? 2 : 3);
338
339 /*
340 * We maintain a dsf of connected squares, together with a
341 * count of the size of each equivalence class.
342 */
343 dsf = snewn(w*h, int);
344 dsfsize = snewn(w*h, int);
345
346 /*
347 * Now repeatedly try to find something we can do.
348 */
349 while (1) {
350 bool done_something = false;
351
352 #ifdef SOLVER_DIAGNOSTICS
353 for (y = 0; y < H; y++) {
354 for (x = 0; x < W; x++)
355 printf("%*x", (x&1) ? 5 : 2, workspace[y*W+x]);
356 printf("\n");
357 }
358 #endif
359
360 /*
361 * Go through the square state words, and discard any
362 * square state which is inconsistent with known facts
363 * about the edges around the square.
364 */
365 for (y = 0; y < h; y++)
366 for (x = 0; x < w; x++) {
367 for (b = 0; b < 0xD; b++)
368 if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
369 /*
370 * If any edge of this square is known to
371 * be connected when state b would require
372 * it disconnected, or vice versa, discard
373 * the state.
374 */
375 for (d = 1; d <= 8; d += d) {
376 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
377 if (workspace[ey*W+ex] ==
378 ((b & d) ? 2 : 1)) {
379 workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<b);
380 #ifdef SOLVER_DIAGNOSTICS
381 printf("edge (%d,%d)-(%d,%d) rules out state"
382 " %d for square (%d,%d)\n",
383 ex/2, ey/2, (ex+1)/2, (ey+1)/2,
384 b, x, y);
385 #endif
386 done_something = true;
387 break;
388 }
389 }
390 }
391
392 /*
393 * Consistency check: each square must have at
394 * least one state left!
395 */
396 if (!workspace[(2*y+1)*W+(2*x+1)]) {
397 #ifdef SOLVER_DIAGNOSTICS
398 printf("edge check at (%d,%d): inconsistency\n", x, y);
399 #endif
400 ret = 0;
401 goto cleanup;
402 }
403 }
404
405 /*
406 * Now go through the states array again, and nail down any
407 * unknown edge if one of its neighbouring squares makes it
408 * known.
409 */
410 for (y = 0; y < h; y++)
411 for (x = 0; x < w; x++) {
412 int edgeor = 0, edgeand = 15;
413
414 for (b = 0; b < 0xD; b++)
415 if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
416 edgeor |= b;
417 edgeand &= b;
418 }
419
420 /*
421 * Now any bit clear in edgeor marks a disconnected
422 * edge, and any bit set in edgeand marks a
423 * connected edge.
424 */
425
426 /* First check consistency: neither bit is both! */
427 if (edgeand & ~edgeor) {
428 #ifdef SOLVER_DIAGNOSTICS
429 printf("square check at (%d,%d): inconsistency\n", x, y);
430 #endif
431 ret = 0;
432 goto cleanup;
433 }
434
435 for (d = 1; d <= 8; d += d) {
436 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
437
438 if (!(edgeor & d) && workspace[ey*W+ex] == 3) {
439 workspace[ey*W+ex] = 2;
440 done_something = true;
441 #ifdef SOLVER_DIAGNOSTICS
442 printf("possible states of square (%d,%d) force edge"
443 " (%d,%d)-(%d,%d) to be disconnected\n",
444 x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
445 #endif
446 } else if ((edgeand & d) && workspace[ey*W+ex] == 3) {
447 workspace[ey*W+ex] = 1;
448 done_something = true;
449 #ifdef SOLVER_DIAGNOSTICS
450 printf("possible states of square (%d,%d) force edge"
451 " (%d,%d)-(%d,%d) to be connected\n",
452 x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
453 #endif
454 }
455 }
456 }
457
458 if (done_something)
459 continue;
460
461 /*
462 * Now for longer-range clue-based deductions (using the
463 * rules that a corner clue must connect to two straight
464 * squares, and a straight clue must connect to at least
465 * one corner square).
466 */
467 for (y = 0; y < h; y++)
468 for (x = 0; x < w; x++)
469 switch (clues[y*w+x]) {
470 case CORNER:
471 for (d = 1; d <= 8; d += d) {
472 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
473 int fx = ex + DX(d), fy = ey + DY(d);
474 int type = d | F(d);
475
476 if (workspace[ey*W+ex] == 1) {
477 /*
478 * If a corner clue is connected on any
479 * edge, then we can immediately nail
480 * down the square beyond that edge as
481 * being a straight in the appropriate
482 * direction.
483 */
484 if (workspace[fy*W+fx] != (1<<type)) {
485 workspace[fy*W+fx] = (1<<type);
486 done_something = true;
487 #ifdef SOLVER_DIAGNOSTICS
488 printf("corner clue at (%d,%d) forces square "
489 "(%d,%d) into state %d\n", x, y,
490 fx/2, fy/2, type);
491 #endif
492
493 }
494 } else if (workspace[ey*W+ex] == 3) {
495 /*
496 * Conversely, if a corner clue is
497 * separated by an unknown edge from a
498 * square which _cannot_ be a straight
499 * in the appropriate direction, we can
500 * mark that edge as disconnected.
501 */
502 if (!(workspace[fy*W+fx] & (1<<type))) {
503 workspace[ey*W+ex] = 2;
504 done_something = true;
505 #ifdef SOLVER_DIAGNOSTICS
506 printf("corner clue at (%d,%d), plus square "
507 "(%d,%d) not being state %d, "
508 "disconnects edge (%d,%d)-(%d,%d)\n",
509 x, y, fx/2, fy/2, type,
510 ex/2, ey/2, (ex+1)/2, (ey+1)/2);
511 #endif
512
513 }
514 }
515 }
516
517 break;
518 case STRAIGHT:
519 /*
520 * If a straight clue is between two squares
521 * neither of which is capable of being a
522 * corner connected to it, then the straight
523 * clue cannot point in that direction.
524 */
525 for (d = 1; d <= 2; d += d) {
526 int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
527 int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
528 int type = d | F(d);
529
530 if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type)))
531 continue;
532
533 if (!(workspace[fy*W+fx] & ((1<<(F(d)|A(d))) |
534 (1<<(F(d)|C(d))))) &&
535 !(workspace[gy*W+gx] & ((1<<( d |A(d))) |
536 (1<<( d |C(d)))))) {
537 workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<type);
538 done_something = true;
539 #ifdef SOLVER_DIAGNOSTICS
540 printf("straight clue at (%d,%d) cannot corner at "
541 "(%d,%d) or (%d,%d) so is not state %d\n",
542 x, y, fx/2, fy/2, gx/2, gy/2, type);
543 #endif
544 }
545
546 }
547
548 /*
549 * If a straight clue with known direction is
550 * connected on one side to a known straight,
551 * then on the other side it must be a corner.
552 */
553 for (d = 1; d <= 8; d += d) {
554 int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
555 int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
556 int type = d | F(d);
557
558 if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type))
559 continue;
560
561 if (!(workspace[fy*W+fx] &~ (bLR|bUD)) &&
562 (workspace[gy*W+gx] &~ (bLU|bLD|bRU|bRD))) {
563 workspace[gy*W+gx] &= (bLU|bLD|bRU|bRD);
564 done_something = true;
565 #ifdef SOLVER_DIAGNOSTICS
566 printf("straight clue at (%d,%d) connecting to "
567 "straight at (%d,%d) makes (%d,%d) a "
568 "corner\n", x, y, fx/2, fy/2, gx/2, gy/2);
569 #endif
570 }
571
572 }
573 break;
574 }
575
576 if (done_something)
577 continue;
578
579 /*
580 * Now detect shortcut loops.
581 */
582
583 {
584 int nonblanks, loopclass;
585
586 dsf_init(dsf, w*h);
587 for (x = 0; x < w*h; x++)
588 dsfsize[x] = 1;
589
590 /*
591 * First go through the edge entries and update the dsf
592 * of which squares are connected to which others. We
593 * also track the number of squares in each equivalence
594 * class, and count the overall number of
595 * known-non-blank squares.
596 *
597 * In the process of doing this, we must notice if a
598 * loop has already been formed. If it has, we blank
599 * out any square which isn't part of that loop
600 * (failing a consistency check if any such square does
601 * not have BLANK as one of its remaining options) and
602 * exit the deduction loop with success.
603 */
604 nonblanks = 0;
605 loopclass = -1;
606 for (y = 1; y < H-1; y++)
607 for (x = 1; x < W-1; x++)
608 if ((y ^ x) & 1) {
609 /*
610 * (x,y) are the workspace coordinates of
611 * an edge field. Compute the normal-space
612 * coordinates of the squares it connects.
613 */
614 int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
615 int bx = x/2, by = y/2, bc = by*w+bx;
616
617 /*
618 * If the edge is connected, do the dsf
619 * thing.
620 */
621 if (workspace[y*W+x] == 1) {
622 int ae, be;
623
624 ae = dsf_canonify(dsf, ac);
625 be = dsf_canonify(dsf, bc);
626
627 if (ae == be) {
628 /*
629 * We have a loop!
630 */
631 if (loopclass != -1) {
632 /*
633 * In fact, we have two
634 * separate loops, which is
635 * doom.
636 */
637 #ifdef SOLVER_DIAGNOSTICS
638 printf("two loops found in grid!\n");
639 #endif
640 ret = 0;
641 goto cleanup;
642 }
643 loopclass = ae;
644 } else {
645 /*
646 * Merge the two equivalence
647 * classes.
648 */
649 int size = dsfsize[ae] + dsfsize[be];
650 dsf_merge(dsf, ac, bc);
651 ae = dsf_canonify(dsf, ac);
652 dsfsize[ae] = size;
653 }
654 }
655 } else if ((y & x) & 1) {
656 /*
657 * (x,y) are the workspace coordinates of a
658 * square field. If the square is
659 * definitely not blank, count it.
660 */
661 if (!(workspace[y*W+x] & bBLANK))
662 nonblanks++;
663 }
664
665 /*
666 * If we discovered an existing loop above, we must now
667 * blank every square not part of it, and exit the main
668 * deduction loop.
669 */
670 if (loopclass != -1) {
671 #ifdef SOLVER_DIAGNOSTICS
672 printf("loop found in grid!\n");
673 #endif
674 for (y = 0; y < h; y++)
675 for (x = 0; x < w; x++)
676 if (dsf_canonify(dsf, y*w+x) != loopclass) {
677 if (workspace[(y*2+1)*W+(x*2+1)] & bBLANK) {
678 workspace[(y*2+1)*W+(x*2+1)] = bBLANK;
679 } else {
680 /*
681 * This square is not part of the
682 * loop, but is known non-blank. We
683 * have goofed.
684 */
685 #ifdef SOLVER_DIAGNOSTICS
686 printf("non-blank square (%d,%d) found outside"
687 " loop!\n", x, y);
688 #endif
689 ret = 0;
690 goto cleanup;
691 }
692 }
693 /*
694 * And we're done.
695 */
696 ret = 1;
697 break;
698 }
699
700 /* Further deductions are considered 'tricky'. */
701 if (difficulty == DIFF_EASY) goto done_deductions;
702
703 /*
704 * Now go through the workspace again and mark any edge
705 * which would cause a shortcut loop (i.e. would
706 * connect together two squares in the same equivalence
707 * class, and that equivalence class does not contain
708 * _all_ the known-non-blank squares currently in the
709 * grid) as disconnected. Also, mark any _square state_
710 * which would cause a shortcut loop as disconnected.
711 */
712 for (y = 1; y < H-1; y++)
713 for (x = 1; x < W-1; x++)
714 if ((y ^ x) & 1) {
715 /*
716 * (x,y) are the workspace coordinates of
717 * an edge field. Compute the normal-space
718 * coordinates of the squares it connects.
719 */
720 int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
721 int bx = x/2, by = y/2, bc = by*w+bx;
722
723 /*
724 * If the edge is currently unknown, and
725 * sits between two squares in the same
726 * equivalence class, and the size of that
727 * class is less than nonblanks, then
728 * connecting this edge would be a shortcut
729 * loop and so we must not do so.
730 */
731 if (workspace[y*W+x] == 3) {
732 int ae, be;
733
734 ae = dsf_canonify(dsf, ac);
735 be = dsf_canonify(dsf, bc);
736
737 if (ae == be) {
738 /*
739 * We have a loop. Is it a shortcut?
740 */
741 if (dsfsize[ae] < nonblanks) {
742 /*
743 * Yes! Mark this edge disconnected.
744 */
745 workspace[y*W+x] = 2;
746 done_something = true;
747 #ifdef SOLVER_DIAGNOSTICS
748 printf("edge (%d,%d)-(%d,%d) would create"
749 " a shortcut loop, hence must be"
750 " disconnected\n", x/2, y/2,
751 (x+1)/2, (y+1)/2);
752 #endif
753 }
754 }
755 }
756 } else if ((y & x) & 1) {
757 /*
758 * (x,y) are the workspace coordinates of a
759 * square field. Go through its possible
760 * (non-blank) states and see if any gives
761 * rise to a shortcut loop.
762 *
763 * This is slightly fiddly, because we have
764 * to check whether this square is already
765 * part of the same equivalence class as
766 * the things it's joining.
767 */
768 int ae = dsf_canonify(dsf, (y/2)*w+(x/2));
769
770 for (b = 2; b < 0xD; b++)
771 if (workspace[y*W+x] & (1<<b)) {
772 /*
773 * Find the equivalence classes of
774 * the two squares this one would
775 * connect if it were in this
776 * state.
777 */
778 int e = -1;
779
780 for (d = 1; d <= 8; d += d) if (b & d) {
781 int xx = x/2 + DX(d), yy = y/2 + DY(d);
782 int ee = dsf_canonify(dsf, yy*w+xx);
783
784 if (e == -1)
785 ee = e;
786 else if (e != ee)
787 e = -2;
788 }
789
790 if (e >= 0) {
791 /*
792 * This square state would form
793 * a loop on equivalence class
794 * e. Measure the size of that
795 * loop, and see if it's a
796 * shortcut.
797 */
798 int loopsize = dsfsize[e];
799 if (e != ae)
800 loopsize++;/* add the square itself */
801 if (loopsize < nonblanks) {
802 /*
803 * It is! Mark this square
804 * state invalid.
805 */
806 workspace[y*W+x] &= ~(1<<b);
807 done_something = true;
808 #ifdef SOLVER_DIAGNOSTICS
809 printf("square (%d,%d) would create a "
810 "shortcut loop in state %d, "
811 "hence cannot be\n",
812 x/2, y/2, b);
813 #endif
814 }
815 }
816 }
817 }
818 }
819
820 done_deductions:
821
822 if (done_something)
823 continue;
824
825 /*
826 * If we reach here, there is nothing left we can do.
827 * Return 2 for ambiguous puzzle.
828 */
829 ret = 2;
830 break;
831 }
832
833 cleanup:
834
835 /*
836 * If ret = 1 then we've successfully achieved a solution. This
837 * means that we expect every square to be nailed down to
838 * exactly one possibility. If this is the case, or if the caller
839 * asked for a partial solution anyway, transcribe those
840 * possibilities into the result array.
841 */
842 if (ret == 1 || partial) {
843 for (y = 0; y < h; y++) {
844 for (x = 0; x < w; x++) {
845 for (b = 0; b < 0xD; b++)
846 if (workspace[(2*y+1)*W+(2*x+1)] == (1<<b)) {
847 result[y*w+x] = b;
848 break;
849 }
850 if (ret == 1) assert(b < 0xD); /* we should have had a break by now */
851 }
852 }
853 }
854
855 sfree(dsfsize);
856 sfree(dsf);
857 sfree(workspace);
858 assert(ret >= 0);
859 return ret;
860 }
861
862 /* ----------------------------------------------------------------------
863 * Loop generator.
864 */
865
866 /*
867 * We use the loop generator code from loopy, hard-coding to a square
868 * grid of the appropriate size. Knowing the grid layout and the tile
869 * size we can shrink that to our small grid and then make our line
870 * layout from the face colour info.
871 *
872 * We provide a bias function to the loop generator which tries to
873 * bias in favour of loops with more scope for Pearl black clues. This
874 * seems to improve the success rate of the puzzle generator, in that
875 * such loops have a better chance of being soluble with all valid
876 * clues put in.
877 */
878
879 struct pearl_loopgen_bias_ctx {
880 /*
881 * Our bias function counts the number of 'black clue' corners
882 * (i.e. corners adjacent to two straights) in both the
883 * BLACK/nonBLACK and WHITE/nonWHITE boundaries. In order to do
884 * this, we must:
885 *
886 * - track the edges that are part of each of those loops
887 * - track the types of vertex in each loop (corner, straight,
888 * none)
889 * - track the current black-clue status of each vertex in each
890 * loop.
891 *
892 * Each of these chunks of data is updated incrementally from the
893 * previous one, to avoid slowdown due to the bias function
894 * rescanning the whole grid every time it's called.
895 *
896 * So we need a lot of separate arrays, plus a tdq for each one,
897 * and we must repeat it all twice for the BLACK and WHITE
898 * boundaries.
899 */
900 struct pearl_loopgen_bias_ctx_boundary {
901 int colour; /* FACE_WHITE or FACE_BLACK */
902
903 bool *edges; /* is each edge part of the loop? */
904 tdq *edges_todo;
905
906 char *vertextypes; /* bits 0-3 == outgoing edge bitmap;
907 * bit 4 set iff corner clue.
908 * Hence, 0 means non-vertex;
909 * nonzero but bit 4 zero = straight. */
910 int *neighbour[2]; /* indices of neighbour vertices in loop */
911 tdq *vertextypes_todo;
912
913 char *blackclues; /* is each vertex a black clue site? */
914 tdq *blackclues_todo;
915 } boundaries[2]; /* boundaries[0]=WHITE, [1]=BLACK */
916
917 char *faces; /* remember last-seen colour of each face */
918 tdq *faces_todo;
919
920 int score;
921
922 grid *g;
923 };
pearl_loopgen_bias(void * vctx,char * board,int face)924 static int pearl_loopgen_bias(void *vctx, char *board, int face)
925 {
926 struct pearl_loopgen_bias_ctx *ctx = (struct pearl_loopgen_bias_ctx *)vctx;
927 grid *g = ctx->g;
928 int oldface, newface;
929 int i, j, k;
930
931 tdq_add(ctx->faces_todo, face);
932 while ((j = tdq_remove(ctx->faces_todo)) >= 0) {
933 oldface = ctx->faces[j];
934 ctx->faces[j] = newface = board[j];
935 for (i = 0; i < 2; i++) {
936 struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i];
937 int c = b->colour;
938
939 /*
940 * If the face has changed either from or to colour c, we need
941 * to reprocess the edges for this boundary.
942 */
943 if (oldface == c || newface == c) {
944 grid_face *f = &g->faces[face];
945 for (k = 0; k < f->order; k++)
946 tdq_add(b->edges_todo, f->edges[k] - g->edges);
947 }
948 }
949 }
950
951 for (i = 0; i < 2; i++) {
952 struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i];
953 int c = b->colour;
954
955 /*
956 * Go through the to-do list of edges. For each edge, decide
957 * anew whether it's part of this boundary or not. Any edge
958 * that changes state has to have both its endpoints put on
959 * the vertextypes_todo list.
960 */
961 while ((j = tdq_remove(b->edges_todo)) >= 0) {
962 grid_edge *e = &g->edges[j];
963 int fc1 = e->face1 ? board[e->face1 - g->faces] : FACE_BLACK;
964 int fc2 = e->face2 ? board[e->face2 - g->faces] : FACE_BLACK;
965 bool oldedge = b->edges[j];
966 bool newedge = (fc1==c) ^ (fc2==c);
967 if (oldedge != newedge) {
968 b->edges[j] = newedge;
969 tdq_add(b->vertextypes_todo, e->dot1 - g->dots);
970 tdq_add(b->vertextypes_todo, e->dot2 - g->dots);
971 }
972 }
973
974 /*
975 * Go through the to-do list of vertices whose types need
976 * refreshing. For each one, decide whether it's a corner, a
977 * straight, or a vertex not in the loop, and in the former
978 * two cases also work out the indices of its neighbour
979 * vertices along the loop. Any vertex that changes state must
980 * be put back on the to-do list for deciding if it's a black
981 * clue site, and so must its two new neighbours _and_ its two
982 * old neighbours.
983 */
984 while ((j = tdq_remove(b->vertextypes_todo)) >= 0) {
985 grid_dot *d = &g->dots[j];
986 int neighbours[2], type = 0, n = 0;
987
988 for (k = 0; k < d->order; k++) {
989 grid_edge *e = d->edges[k];
990 grid_dot *d2 = (e->dot1 == d ? e->dot2 : e->dot1);
991 /* dir == 0,1,2,3 for an edge going L,U,R,D */
992 int dir = (d->y == d2->y) + 2*(d->x+d->y > d2->x+d2->y);
993 int ei = e - g->edges;
994 if (b->edges[ei]) {
995 type |= 1 << dir;
996 neighbours[n] = d2 - g->dots;
997 n++;
998 }
999 }
1000
1001 /*
1002 * Decide if it's a corner, and set the corner flag if so.
1003 */
1004 if (type != 0 && type != 0x5 && type != 0xA)
1005 type |= 0x10;
1006
1007 if (type != b->vertextypes[j]) {
1008 /*
1009 * Recompute old neighbours, if any.
1010 */
1011 if (b->vertextypes[j]) {
1012 tdq_add(b->blackclues_todo, b->neighbour[0][j]);
1013 tdq_add(b->blackclues_todo, b->neighbour[1][j]);
1014 }
1015 /*
1016 * Recompute this vertex.
1017 */
1018 tdq_add(b->blackclues_todo, j);
1019 b->vertextypes[j] = type;
1020 /*
1021 * Recompute new neighbours, if any.
1022 */
1023 if (b->vertextypes[j]) {
1024 b->neighbour[0][j] = neighbours[0];
1025 b->neighbour[1][j] = neighbours[1];
1026 tdq_add(b->blackclues_todo, b->neighbour[0][j]);
1027 tdq_add(b->blackclues_todo, b->neighbour[1][j]);
1028 }
1029 }
1030 }
1031
1032 /*
1033 * Go through the list of vertices which we must check to see
1034 * if they're black clue sites. Each one is a black clue site
1035 * iff it is a corner and its loop neighbours are non-corners.
1036 * Adjust the running total of black clues we've counted.
1037 */
1038 while ((j = tdq_remove(b->blackclues_todo)) >= 0) {
1039 ctx->score -= b->blackclues[j];
1040 b->blackclues[j] = ((b->vertextypes[j] & 0x10) &&
1041 !((b->vertextypes[b->neighbour[0][j]] |
1042 b->vertextypes[b->neighbour[1][j]])
1043 & 0x10));
1044 ctx->score += b->blackclues[j];
1045 }
1046 }
1047
1048 return ctx->score;
1049 }
1050
pearl_loopgen(int w,int h,char * lines,random_state * rs)1051 static void pearl_loopgen(int w, int h, char *lines, random_state *rs)
1052 {
1053 grid *g = grid_new(GRID_SQUARE, w-1, h-1, NULL);
1054 char *board = snewn(g->num_faces, char);
1055 int i, s = g->tilesize;
1056 struct pearl_loopgen_bias_ctx biasctx;
1057
1058 memset(lines, 0, w*h);
1059
1060 /*
1061 * Initialise the context for the bias function. Initially we fill
1062 * all the to-do lists, so that the first call will scan
1063 * everything; thereafter the lists stay empty so we make
1064 * incremental changes.
1065 */
1066 biasctx.g = g;
1067 biasctx.faces = snewn(g->num_faces, char);
1068 biasctx.faces_todo = tdq_new(g->num_faces);
1069 tdq_fill(biasctx.faces_todo);
1070 biasctx.score = 0;
1071 memset(biasctx.faces, FACE_GREY, g->num_faces);
1072 for (i = 0; i < 2; i++) {
1073 biasctx.boundaries[i].edges = snewn(g->num_edges, bool);
1074 memset(biasctx.boundaries[i].edges, 0, g->num_edges * sizeof(bool));
1075 biasctx.boundaries[i].edges_todo = tdq_new(g->num_edges);
1076 tdq_fill(biasctx.boundaries[i].edges_todo);
1077 biasctx.boundaries[i].vertextypes = snewn(g->num_dots, char);
1078 memset(biasctx.boundaries[i].vertextypes, 0, g->num_dots);
1079 biasctx.boundaries[i].neighbour[0] = snewn(g->num_dots, int);
1080 biasctx.boundaries[i].neighbour[1] = snewn(g->num_dots, int);
1081 biasctx.boundaries[i].vertextypes_todo = tdq_new(g->num_dots);
1082 tdq_fill(biasctx.boundaries[i].vertextypes_todo);
1083 biasctx.boundaries[i].blackclues = snewn(g->num_dots, char);
1084 memset(biasctx.boundaries[i].blackclues, 0, g->num_dots);
1085 biasctx.boundaries[i].blackclues_todo = tdq_new(g->num_dots);
1086 tdq_fill(biasctx.boundaries[i].blackclues_todo);
1087 }
1088 biasctx.boundaries[0].colour = FACE_WHITE;
1089 biasctx.boundaries[1].colour = FACE_BLACK;
1090 generate_loop(g, board, rs, pearl_loopgen_bias, &biasctx);
1091 sfree(biasctx.faces);
1092 tdq_free(biasctx.faces_todo);
1093 for (i = 0; i < 2; i++) {
1094 sfree(biasctx.boundaries[i].edges);
1095 tdq_free(biasctx.boundaries[i].edges_todo);
1096 sfree(biasctx.boundaries[i].vertextypes);
1097 sfree(biasctx.boundaries[i].neighbour[0]);
1098 sfree(biasctx.boundaries[i].neighbour[1]);
1099 tdq_free(biasctx.boundaries[i].vertextypes_todo);
1100 sfree(biasctx.boundaries[i].blackclues);
1101 tdq_free(biasctx.boundaries[i].blackclues_todo);
1102 }
1103
1104 for (i = 0; i < g->num_edges; i++) {
1105 grid_edge *e = g->edges + i;
1106 enum face_colour c1 = FACE_COLOUR(e->face1);
1107 enum face_colour c2 = FACE_COLOUR(e->face2);
1108 assert(c1 != FACE_GREY);
1109 assert(c2 != FACE_GREY);
1110 if (c1 != c2) {
1111 /* This grid edge is on the loop: lay line along it */
1112 int x1 = e->dot1->x/s, y1 = e->dot1->y/s;
1113 int x2 = e->dot2->x/s, y2 = e->dot2->y/s;
1114
1115 /* (x1,y1) and (x2,y2) are now in our grid coords (0-w,0-h). */
1116 if (x1 == x2) {
1117 if (y1 > y2) SWAP(y1,y2);
1118
1119 assert(y1+1 == y2);
1120 lines[y1*w+x1] |= D;
1121 lines[y2*w+x1] |= U;
1122 } else if (y1 == y2) {
1123 if (x1 > x2) SWAP(x1,x2);
1124
1125 assert(x1+1 == x2);
1126 lines[y1*w+x1] |= R;
1127 lines[y1*w+x2] |= L;
1128 } else
1129 assert(!"grid with diagonal coords?!");
1130 }
1131 }
1132
1133 grid_free(g);
1134 sfree(board);
1135
1136 #if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
1137 printf("as returned:\n");
1138 for (y = 0; y < h; y++) {
1139 for (x = 0; x < w; x++) {
1140 int type = lines[y*w+x];
1141 char s[5], *p = s;
1142 if (type & L) *p++ = 'L';
1143 if (type & R) *p++ = 'R';
1144 if (type & U) *p++ = 'U';
1145 if (type & D) *p++ = 'D';
1146 *p = '\0';
1147 printf("%3s", s);
1148 }
1149 printf("\n");
1150 }
1151 printf("\n");
1152 #endif
1153 }
1154
new_clues(const game_params * params,random_state * rs,char * clues,char * grid)1155 static int new_clues(const game_params *params, random_state *rs,
1156 char *clues, char *grid)
1157 {
1158 int w = params->w, h = params->h, diff = params->difficulty;
1159 int ngen = 0, x, y, d, ret, i;
1160
1161
1162 /*
1163 * Difficulty exception: 5x5 Tricky is not generable (the
1164 * generator will spin forever trying) and so we fudge it to Easy.
1165 */
1166 if (w == 5 && h == 5 && diff > DIFF_EASY)
1167 diff = DIFF_EASY;
1168
1169 while (1) {
1170 ngen++;
1171 pearl_loopgen(w, h, grid, rs);
1172
1173 #ifdef GENERATION_DIAGNOSTICS
1174 printf("grid array:\n");
1175 for (y = 0; y < h; y++) {
1176 for (x = 0; x < w; x++) {
1177 int type = grid[y*w+x];
1178 char s[5], *p = s;
1179 if (type & L) *p++ = 'L';
1180 if (type & R) *p++ = 'R';
1181 if (type & U) *p++ = 'U';
1182 if (type & D) *p++ = 'D';
1183 *p = '\0';
1184 printf("%2s ", s);
1185 }
1186 printf("\n");
1187 }
1188 printf("\n");
1189 #endif
1190
1191 /*
1192 * Set up the maximal clue array.
1193 */
1194 for (y = 0; y < h; y++)
1195 for (x = 0; x < w; x++) {
1196 int type = grid[y*w+x];
1197
1198 clues[y*w+x] = NOCLUE;
1199
1200 if ((bLR|bUD) & (1 << type)) {
1201 /*
1202 * This is a straight; see if it's a viable
1203 * candidate for a straight clue. It qualifies if
1204 * at least one of the squares it connects to is a
1205 * corner.
1206 */
1207 for (d = 1; d <= 8; d += d) if (type & d) {
1208 int xx = x + DX(d), yy = y + DY(d);
1209 assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
1210 if ((bLU|bLD|bRU|bRD) & (1 << grid[yy*w+xx]))
1211 break;
1212 }
1213 if (d <= 8) /* we found one */
1214 clues[y*w+x] = STRAIGHT;
1215 } else if ((bLU|bLD|bRU|bRD) & (1 << type)) {
1216 /*
1217 * This is a corner; see if it's a viable candidate
1218 * for a corner clue. It qualifies if all the
1219 * squares it connects to are straights.
1220 */
1221 for (d = 1; d <= 8; d += d) if (type & d) {
1222 int xx = x + DX(d), yy = y + DY(d);
1223 assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
1224 if (!((bLR|bUD) & (1 << grid[yy*w+xx])))
1225 break;
1226 }
1227 if (d > 8) /* we didn't find a counterexample */
1228 clues[y*w+x] = CORNER;
1229 }
1230 }
1231
1232 #ifdef GENERATION_DIAGNOSTICS
1233 printf("clue array:\n");
1234 for (y = 0; y < h; y++) {
1235 for (x = 0; x < w; x++) {
1236 printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
1237 }
1238 printf("\n");
1239 }
1240 printf("\n");
1241 #endif
1242
1243 if (!params->nosolve) {
1244 int *cluespace, *straights, *corners;
1245 int nstraights, ncorners, nstraightpos, ncornerpos;
1246
1247 /*
1248 * See if we can solve the puzzle just like this.
1249 */
1250 ret = pearl_solve(w, h, clues, grid, diff, false);
1251 assert(ret > 0); /* shouldn't be inconsistent! */
1252 if (ret != 1)
1253 continue; /* go round and try again */
1254
1255 /*
1256 * Check this puzzle isn't too easy.
1257 */
1258 if (diff > DIFF_EASY) {
1259 ret = pearl_solve(w, h, clues, grid, diff-1, false);
1260 assert(ret > 0);
1261 if (ret == 1)
1262 continue; /* too easy: try again */
1263 }
1264
1265 /*
1266 * Now shuffle the grid points and gradually remove the
1267 * clues to find a minimal set which still leaves the
1268 * puzzle soluble.
1269 *
1270 * We preferentially attempt to remove whichever type of
1271 * clue is currently most numerous, to combat a general
1272 * tendency of plain random generation to bias in favour
1273 * of many white clues and few black.
1274 *
1275 * 'nstraights' and 'ncorners' count the number of clues
1276 * of each type currently remaining in the grid;
1277 * 'nstraightpos' and 'ncornerpos' count the clues of each
1278 * type we have left to try to remove. (Clues which we
1279 * have tried and failed to remove are counted by the
1280 * former but not the latter.)
1281 */
1282 cluespace = snewn(w*h, int);
1283 straights = cluespace;
1284 nstraightpos = 0;
1285 for (i = 0; i < w*h; i++)
1286 if (clues[i] == STRAIGHT)
1287 straights[nstraightpos++] = i;
1288 corners = straights + nstraightpos;
1289 ncornerpos = 0;
1290 for (i = 0; i < w*h; i++)
1291 if (clues[i] == STRAIGHT)
1292 corners[ncornerpos++] = i;
1293 nstraights = nstraightpos;
1294 ncorners = ncornerpos;
1295
1296 shuffle(straights, nstraightpos, sizeof(*straights), rs);
1297 shuffle(corners, ncornerpos, sizeof(*corners), rs);
1298 while (nstraightpos > 0 || ncornerpos > 0) {
1299 int cluepos;
1300 int clue;
1301
1302 /*
1303 * Decide which clue to try to remove next. If both
1304 * types are available, we choose whichever kind is
1305 * currently overrepresented; otherwise we take
1306 * whatever we can get.
1307 */
1308 if (nstraightpos > 0 && ncornerpos > 0) {
1309 if (nstraights >= ncorners)
1310 cluepos = straights[--nstraightpos];
1311 else
1312 cluepos = straights[--ncornerpos];
1313 } else {
1314 if (nstraightpos > 0)
1315 cluepos = straights[--nstraightpos];
1316 else
1317 cluepos = straights[--ncornerpos];
1318 }
1319
1320 y = cluepos / w;
1321 x = cluepos % w;
1322
1323 clue = clues[y*w+x];
1324 clues[y*w+x] = 0; /* try removing this clue */
1325
1326 ret = pearl_solve(w, h, clues, grid, diff, false);
1327 assert(ret > 0);
1328 if (ret != 1)
1329 clues[y*w+x] = clue; /* oops, put it back again */
1330 }
1331 sfree(cluespace);
1332 }
1333
1334 #ifdef FINISHED_PUZZLE
1335 printf("clue array:\n");
1336 for (y = 0; y < h; y++) {
1337 for (x = 0; x < w; x++) {
1338 printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
1339 }
1340 printf("\n");
1341 }
1342 printf("\n");
1343 #endif
1344
1345 break; /* got it */
1346 }
1347
1348 debug(("%d %dx%d loops before finished puzzle.\n", ngen, w, h));
1349
1350 return ngen;
1351 }
1352
new_game_desc(const game_params * params,random_state * rs,char ** aux,bool interactive)1353 static char *new_game_desc(const game_params *params, random_state *rs,
1354 char **aux, bool interactive)
1355 {
1356 char *grid, *clues;
1357 char *desc;
1358 int w = params->w, h = params->h, i, j;
1359
1360 grid = snewn(w*h, char);
1361 clues = snewn(w*h, char);
1362
1363 new_clues(params, rs, clues, grid);
1364
1365 desc = snewn(w * h + 1, char);
1366 for (i = j = 0; i < w*h; i++) {
1367 if (clues[i] == NOCLUE && j > 0 &&
1368 desc[j-1] >= 'a' && desc[j-1] < 'z')
1369 desc[j-1]++;
1370 else if (clues[i] == NOCLUE)
1371 desc[j++] = 'a';
1372 else if (clues[i] == CORNER)
1373 desc[j++] = 'B';
1374 else if (clues[i] == STRAIGHT)
1375 desc[j++] = 'W';
1376 }
1377 desc[j] = '\0';
1378
1379 *aux = snewn(w*h+1, char);
1380 for (i = 0; i < w*h; i++)
1381 (*aux)[i] = (grid[i] < 10) ? (grid[i] + '0') : (grid[i] + 'A' - 10);
1382 (*aux)[w*h] = '\0';
1383
1384 sfree(grid);
1385 sfree(clues);
1386
1387 return desc;
1388 }
1389
validate_desc(const game_params * params,const char * desc)1390 static const char *validate_desc(const game_params *params, const char *desc)
1391 {
1392 int i, sizesofar;
1393 const int totalsize = params->w * params->h;
1394
1395 sizesofar = 0;
1396 for (i = 0; desc[i]; i++) {
1397 if (desc[i] >= 'a' && desc[i] <= 'z')
1398 sizesofar += desc[i] - 'a' + 1;
1399 else if (desc[i] == 'B' || desc[i] == 'W')
1400 sizesofar++;
1401 else
1402 return "unrecognised character in string";
1403 }
1404
1405 if (sizesofar > totalsize)
1406 return "string too long";
1407 else if (sizesofar < totalsize)
1408 return "string too short";
1409
1410 return NULL;
1411 }
1412
new_game(midend * me,const game_params * params,const char * desc)1413 static game_state *new_game(midend *me, const game_params *params,
1414 const char *desc)
1415 {
1416 game_state *state = snew(game_state);
1417 int i, j, sz = params->w*params->h;
1418
1419 state->completed = false;
1420 state->used_solve = false;
1421 state->shared = snew(struct shared_state);
1422
1423 state->shared->w = params->w;
1424 state->shared->h = params->h;
1425 state->shared->sz = sz;
1426 state->shared->refcnt = 1;
1427 state->shared->clues = snewn(sz, char);
1428 for (i = j = 0; desc[i]; i++) {
1429 assert(j < sz);
1430 if (desc[i] >= 'a' && desc[i] <= 'z') {
1431 int n = desc[i] - 'a' + 1;
1432 assert(j + n <= sz);
1433 while (n-- > 0)
1434 state->shared->clues[j++] = NOCLUE;
1435 } else if (desc[i] == 'B') {
1436 state->shared->clues[j++] = CORNER;
1437 } else if (desc[i] == 'W') {
1438 state->shared->clues[j++] = STRAIGHT;
1439 }
1440 }
1441
1442 state->lines = snewn(sz, char);
1443 state->errors = snewn(sz, char);
1444 state->marks = snewn(sz, char);
1445 for (i = 0; i < sz; i++)
1446 state->lines[i] = state->errors[i] = state->marks[i] = BLANK;
1447
1448 return state;
1449 }
1450
dup_game(const game_state * state)1451 static game_state *dup_game(const game_state *state)
1452 {
1453 game_state *ret = snew(game_state);
1454 int sz = state->shared->sz, i;
1455
1456 ret->shared = state->shared;
1457 ret->completed = state->completed;
1458 ret->used_solve = state->used_solve;
1459 ++ret->shared->refcnt;
1460
1461 ret->lines = snewn(sz, char);
1462 ret->errors = snewn(sz, char);
1463 ret->marks = snewn(sz, char);
1464 for (i = 0; i < sz; i++) {
1465 ret->lines[i] = state->lines[i];
1466 ret->errors[i] = state->errors[i];
1467 ret->marks[i] = state->marks[i];
1468 }
1469
1470 return ret;
1471 }
1472
free_game(game_state * state)1473 static void free_game(game_state *state)
1474 {
1475 assert(state);
1476 if (--state->shared->refcnt == 0) {
1477 sfree(state->shared->clues);
1478 sfree(state->shared);
1479 }
1480 sfree(state->lines);
1481 sfree(state->errors);
1482 sfree(state->marks);
1483 sfree(state);
1484 }
1485
1486 static char nbits[16] = { 0, 1, 1, 2,
1487 1, 2, 2, 3,
1488 1, 2, 2, 3,
1489 2, 3, 3, 4 };
1490 #define NBITS(l) ( ((l) < 0 || (l) > 15) ? 4 : nbits[l] )
1491
1492 #define ERROR_CLUE 16
1493
dsf_update_completion(game_state * state,int ax,int ay,char dir,int * dsf)1494 static void dsf_update_completion(game_state *state, int ax, int ay, char dir,
1495 int *dsf)
1496 {
1497 int w = state->shared->w /*, h = state->shared->h */;
1498 int ac = ay*w+ax, bx, by, bc;
1499
1500 if (!(state->lines[ac] & dir)) return; /* no link */
1501 bx = ax + DX(dir); by = ay + DY(dir);
1502
1503 assert(INGRID(state, bx, by)); /* should not have a link off grid */
1504
1505 bc = by*w+bx;
1506 assert(state->lines[bc] & F(dir)); /* should have reciprocal link */
1507 if (!(state->lines[bc] & F(dir))) return;
1508
1509 dsf_merge(dsf, ac, bc);
1510 }
1511
check_completion(game_state * state,bool mark)1512 static void check_completion(game_state *state, bool mark)
1513 {
1514 int w = state->shared->w, h = state->shared->h, x, y, i, d;
1515 bool had_error = false;
1516 int *dsf, *component_state;
1517 int nsilly, nloop, npath, largest_comp, largest_size, total_pathsize;
1518 enum { COMP_NONE, COMP_LOOP, COMP_PATH, COMP_SILLY, COMP_EMPTY };
1519
1520 if (mark) {
1521 for (i = 0; i < w*h; i++) {
1522 state->errors[i] = 0;
1523 }
1524 }
1525
1526 #define ERROR(x,y,e) do { had_error = true; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0)
1527
1528 /*
1529 * Analyse the solution into loops, paths and stranger things.
1530 * Basic strategy here is all the same as in Loopy - see the big
1531 * comment in loopy.c's check_completion() - and for exactly the
1532 * same reasons, since Loopy and Pearl have basically the same
1533 * form of expected solution.
1534 */
1535 dsf = snew_dsf(w*h);
1536
1537 /* Build the dsf. */
1538 for (x = 0; x < w; x++) {
1539 for (y = 0; y < h; y++) {
1540 dsf_update_completion(state, x, y, R, dsf);
1541 dsf_update_completion(state, x, y, D, dsf);
1542 }
1543 }
1544
1545 /* Initialise a state variable for each connected component. */
1546 component_state = snewn(w*h, int);
1547 for (i = 0; i < w*h; i++) {
1548 if (dsf_canonify(dsf, i) == i)
1549 component_state[i] = COMP_LOOP;
1550 else
1551 component_state[i] = COMP_NONE;
1552 }
1553
1554 /*
1555 * Classify components, and mark errors where a square has more
1556 * than two line segments.
1557 */
1558 for (x = 0; x < w; x++) {
1559 for (y = 0; y < h; y++) {
1560 int type = state->lines[y*w+x];
1561 int degree = NBITS(type);
1562 int comp = dsf_canonify(dsf, y*w+x);
1563 if (degree > 2) {
1564 ERROR(x,y,type);
1565 component_state[comp] = COMP_SILLY;
1566 } else if (degree == 0) {
1567 component_state[comp] = COMP_EMPTY;
1568 } else if (degree == 1) {
1569 if (component_state[comp] != COMP_SILLY)
1570 component_state[comp] = COMP_PATH;
1571 }
1572 }
1573 }
1574
1575 /* Count the components, and find the largest sensible one. */
1576 nsilly = nloop = npath = 0;
1577 total_pathsize = 0;
1578 largest_comp = largest_size = -1;
1579 for (i = 0; i < w*h; i++) {
1580 if (component_state[i] == COMP_SILLY) {
1581 nsilly++;
1582 } else if (component_state[i] == COMP_PATH) {
1583 total_pathsize += dsf_size(dsf, i);
1584 npath = 1;
1585 } else if (component_state[i] == COMP_LOOP) {
1586 int this_size;
1587
1588 nloop++;
1589
1590 if ((this_size = dsf_size(dsf, i)) > largest_size) {
1591 largest_comp = i;
1592 largest_size = this_size;
1593 }
1594 }
1595 }
1596 if (largest_size < total_pathsize) {
1597 largest_comp = -1; /* means the paths */
1598 largest_size = total_pathsize;
1599 }
1600
1601 if (nloop > 0 && nloop + npath > 1) {
1602 /*
1603 * If there are at least two sensible components including at
1604 * least one loop, highlight every sensible component that is
1605 * not the largest one.
1606 */
1607 for (i = 0; i < w*h; i++) {
1608 int comp = dsf_canonify(dsf, i);
1609 if ((component_state[comp] == COMP_PATH &&
1610 -1 != largest_comp) ||
1611 (component_state[comp] == COMP_LOOP &&
1612 comp != largest_comp))
1613 ERROR(i%w, i/w, state->lines[i]);
1614 }
1615 }
1616
1617 /* Now we've finished with the dsf and component states. The only
1618 * thing we'll need to remember later on is whether all edges were
1619 * part of a single loop, for which our counter variables
1620 * nsilly,nloop,npath are enough. */
1621 sfree(component_state);
1622 sfree(dsf);
1623
1624 /*
1625 * Check that no clues are contradicted. This code is similar to
1626 * the code that sets up the maximal clue array for any given
1627 * loop.
1628 */
1629 for (x = 0; x < w; x++) {
1630 for (y = 0; y < h; y++) {
1631 int type = state->lines[y*w+x];
1632 if (state->shared->clues[y*w+x] == CORNER) {
1633 /* Supposed to be a corner: will find a contradiction if
1634 * it actually contains a straight line, or if it touches any
1635 * corners. */
1636 if ((bLR|bUD) & (1 << type)) {
1637 ERROR(x,y,ERROR_CLUE); /* actually straight */
1638 }
1639 for (d = 1; d <= 8; d += d) if (type & d) {
1640 int xx = x + DX(d), yy = y + DY(d);
1641 if (!INGRID(state, xx, yy)) {
1642 ERROR(x,y,d); /* leads off grid */
1643 } else {
1644 if ((bLU|bLD|bRU|bRD) & (1 << state->lines[yy*w+xx])) {
1645 ERROR(x,y,ERROR_CLUE); /* touches corner */
1646 }
1647 }
1648 }
1649 } else if (state->shared->clues[y*w+x] == STRAIGHT) {
1650 /* Supposed to be straight: will find a contradiction if
1651 * it actually contains a corner, or if it only touches
1652 * straight lines. */
1653 if ((bLU|bLD|bRU|bRD) & (1 << type)) {
1654 ERROR(x,y,ERROR_CLUE); /* actually a corner */
1655 }
1656 i = 0;
1657 for (d = 1; d <= 8; d += d) if (type & d) {
1658 int xx = x + DX(d), yy = y + DY(d);
1659 if (!INGRID(state, xx, yy)) {
1660 ERROR(x,y,d); /* leads off grid */
1661 } else {
1662 if ((bLR|bUD) & (1 << state->lines[yy*w+xx]))
1663 i++; /* a straight */
1664 }
1665 }
1666 if (i >= 2 && NBITS(type) >= 2) {
1667 ERROR(x,y,ERROR_CLUE); /* everything touched is straight */
1668 }
1669 }
1670 }
1671 }
1672
1673 if (nloop == 1 && nsilly == 0 && npath == 0) {
1674 /*
1675 * If there's exactly one loop (so that the puzzle is at least
1676 * potentially complete), we need to ensure it hasn't left any
1677 * clue out completely.
1678 */
1679 for (x = 0; x < w; x++) {
1680 for (y = 0; y < h; y++) {
1681 if (state->lines[y*w+x] == BLANK) {
1682 if (state->shared->clues[y*w+x] != NOCLUE) {
1683 /* the loop doesn't include this clue square! */
1684 ERROR(x, y, ERROR_CLUE);
1685 }
1686 }
1687 }
1688 }
1689
1690 /*
1691 * But if not, then we're done!
1692 */
1693 if (!had_error)
1694 state->completed = true;
1695 }
1696 }
1697
1698 /* completion check:
1699 *
1700 * - no clues must be contradicted (highlight clue itself in error if so)
1701 * - if there is a closed loop it must include every line segment laid
1702 * - if there's a smaller closed loop then highlight whole loop as error
1703 * - no square must have more than 2 lines radiating from centre point
1704 * (highlight all lines in that square as error if so)
1705 */
1706
solve_for_diff(game_state * state,char * old_lines,char * new_lines)1707 static char *solve_for_diff(game_state *state, char *old_lines, char *new_lines)
1708 {
1709 int w = state->shared->w, h = state->shared->h, i;
1710 char *move = snewn(w*h*40, char), *p = move;
1711
1712 *p++ = 'S';
1713 for (i = 0; i < w*h; i++) {
1714 if (old_lines[i] != new_lines[i]) {
1715 p += sprintf(p, ";R%d,%d,%d", new_lines[i], i%w, i/w);
1716 }
1717 }
1718 *p++ = '\0';
1719 move = sresize(move, p - move, char);
1720
1721 return move;
1722 }
1723
solve_game(const game_state * state,const game_state * currstate,const char * aux,const char ** error)1724 static char *solve_game(const game_state *state, const game_state *currstate,
1725 const char *aux, const char **error)
1726 {
1727 game_state *solved = dup_game(state);
1728 int i, ret, sz = state->shared->sz;
1729 char *move;
1730
1731 if (aux) {
1732 for (i = 0; i < sz; i++) {
1733 if (aux[i] >= '0' && aux[i] <= '9')
1734 solved->lines[i] = aux[i] - '0';
1735 else if (aux[i] >= 'A' && aux[i] <= 'F')
1736 solved->lines[i] = aux[i] - 'A' + 10;
1737 else {
1738 *error = "invalid char in aux";
1739 move = NULL;
1740 goto done;
1741 }
1742 }
1743 ret = 1;
1744 } else {
1745 /* Try to solve with present (half-solved) state first: if there's no
1746 * solution from there go back to original state. */
1747 ret = pearl_solve(currstate->shared->w, currstate->shared->h,
1748 currstate->shared->clues, solved->lines,
1749 DIFFCOUNT, false);
1750 if (ret < 1)
1751 ret = pearl_solve(state->shared->w, state->shared->h,
1752 state->shared->clues, solved->lines,
1753 DIFFCOUNT, false);
1754
1755 }
1756
1757 if (ret < 1) {
1758 *error = "Unable to find solution";
1759 move = NULL;
1760 } else {
1761 move = solve_for_diff(solved, currstate->lines, solved->lines);
1762 }
1763
1764 done:
1765 free_game(solved);
1766 return move;
1767 }
1768
game_can_format_as_text_now(const game_params * params)1769 static bool game_can_format_as_text_now(const game_params *params)
1770 {
1771 return true;
1772 }
1773
game_text_format(const game_state * state)1774 static char *game_text_format(const game_state *state)
1775 {
1776 int w = state->shared->w, h = state->shared->h, cw = 4, ch = 2;
1777 int gw = cw*(w-1) + 2, gh = ch*(h-1) + 1, len = gw * gh, r, c, j;
1778 char *board = snewn(len + 1, char);
1779
1780 assert(board);
1781 memset(board, ' ', len);
1782
1783 for (r = 0; r < h; ++r) {
1784 for (c = 0; c < w; ++c) {
1785 int i = r*w + c, cell = r*ch*gw + c*cw;
1786 board[cell] = "+BW"[(unsigned char)state->shared->clues[i]];
1787 if (c < w - 1 && (state->lines[i] & R || state->lines[i+1] & L))
1788 memset(board + cell + 1, '-', cw - 1);
1789 if (r < h - 1 && (state->lines[i] & D || state->lines[i+w] & U))
1790 for (j = 1; j < ch; ++j) board[cell + j*gw] = '|';
1791 if (c < w - 1 && (state->marks[i] & R || state->marks[i+1] & L))
1792 board[cell + cw/2] = 'x';
1793 if (r < h - 1 && (state->marks[i] & D || state->marks[i+w] & U))
1794 board[cell + (ch/2 * gw)] = 'x';
1795 }
1796
1797 for (j = 0; j < (r == h - 1 ? 1 : ch); ++j)
1798 board[r*ch*gw + (gw - 1) + j*gw] = '\n';
1799 }
1800
1801 board[len] = '\0';
1802 return board;
1803 }
1804
1805 struct game_ui {
1806 int *dragcoords; /* list of (y*w+x) coords in drag so far */
1807 int ndragcoords; /* number of entries in dragcoords.
1808 * 0 = click but no drag yet. -1 = no drag at all */
1809 int clickx, clicky; /* pixel position of initial click */
1810
1811 int curx, cury; /* grid position of keyboard cursor */
1812 bool cursor_active; /* true iff cursor is shown */
1813 };
1814
new_ui(const game_state * state)1815 static game_ui *new_ui(const game_state *state)
1816 {
1817 game_ui *ui = snew(game_ui);
1818 int sz = state->shared->sz;
1819
1820 ui->ndragcoords = -1;
1821 ui->dragcoords = snewn(sz, int);
1822 ui->cursor_active = false;
1823 ui->curx = ui->cury = 0;
1824
1825 return ui;
1826 }
1827
free_ui(game_ui * ui)1828 static void free_ui(game_ui *ui)
1829 {
1830 sfree(ui->dragcoords);
1831 sfree(ui);
1832 }
1833
encode_ui(const game_ui * ui)1834 static char *encode_ui(const game_ui *ui)
1835 {
1836 return NULL;
1837 }
1838
decode_ui(game_ui * ui,const char * encoding)1839 static void decode_ui(game_ui *ui, const char *encoding)
1840 {
1841 }
1842
game_changed_state(game_ui * ui,const game_state * oldstate,const game_state * newstate)1843 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1844 const game_state *newstate)
1845 {
1846 }
1847
1848 #define PREFERRED_TILE_SIZE 31
1849 #define HALFSZ (ds->halfsz)
1850 #define TILE_SIZE (ds->halfsz*2 + 1)
1851
1852 #define BORDER ((get_gui_style() == GUI_LOOPY) ? (TILE_SIZE/8) : (TILE_SIZE/2))
1853
1854 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1855
1856 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
1857 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1858 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) )
1859
1860 #define DS_ESHIFT 4 /* R/U/L/D shift, for error flags */
1861 #define DS_DSHIFT 8 /* R/U/L/D shift, for drag-in-progress flags */
1862 #define DS_MSHIFT 12 /* shift for no-line mark */
1863
1864 #define DS_ERROR_CLUE (1 << 20)
1865 #define DS_FLASH (1 << 21)
1866 #define DS_CURSOR (1 << 22)
1867
1868 enum { GUI_MASYU, GUI_LOOPY };
1869
get_gui_style(void)1870 static int get_gui_style(void)
1871 {
1872 static int gui_style = -1;
1873
1874 if (gui_style == -1) {
1875 char *env = getenv("PEARL_GUI_LOOPY");
1876 if (env && (env[0] == 'y' || env[0] == 'Y'))
1877 gui_style = GUI_LOOPY;
1878 else
1879 gui_style = GUI_MASYU;
1880 }
1881 return gui_style;
1882 }
1883
1884 struct game_drawstate {
1885 int halfsz;
1886 bool started;
1887
1888 int w, h, sz;
1889 unsigned int *lflags; /* size w*h */
1890
1891 char *draglines; /* size w*h; lines flipped by current drag */
1892 };
1893
1894 /*
1895 * Routine shared between multiple callers to work out the intended
1896 * effect of a drag path on the grid.
1897 *
1898 * Call it in a loop, like this:
1899 *
1900 * bool clearing = true;
1901 * for (i = 0; i < ui->ndragcoords - 1; i++) {
1902 * int sx, sy, dx, dy, dir, oldstate, newstate;
1903 * interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
1904 * &dir, &oldstate, &newstate);
1905 *
1906 * [do whatever is needed to handle the fact that the drag
1907 * wants the edge from sx,sy to dx,dy (heading in direction
1908 * 'dir' at the sx,sy end) to be changed from state oldstate
1909 * to state newstate, each of which equals either 0 or dir]
1910 * }
1911 */
interpret_ui_drag(const game_state * state,const game_ui * ui,bool * clearing,int i,int * sx,int * sy,int * dx,int * dy,int * dir,int * oldstate,int * newstate)1912 static void interpret_ui_drag(const game_state *state, const game_ui *ui,
1913 bool *clearing, int i, int *sx, int *sy,
1914 int *dx, int *dy, int *dir,
1915 int *oldstate, int *newstate)
1916 {
1917 int w = state->shared->w;
1918 int sp = ui->dragcoords[i], dp = ui->dragcoords[i+1];
1919 *sy = sp/w;
1920 *sx = sp%w;
1921 *dy = dp/w;
1922 *dx = dp%w;
1923 *dir = (*dy>*sy ? D : *dy<*sy ? U : *dx>*sx ? R : L);
1924 *oldstate = state->lines[sp] & *dir;
1925 if (*oldstate) {
1926 /*
1927 * The edge we've dragged over was previously
1928 * present. Set it to absent, unless we've already
1929 * stopped doing that.
1930 */
1931 *newstate = *clearing ? 0 : *dir;
1932 } else {
1933 /*
1934 * The edge we've dragged over was previously
1935 * absent. Set it to present, and cancel the
1936 * 'clearing' flag so that all subsequent edges in
1937 * the drag are set rather than cleared.
1938 */
1939 *newstate = *dir;
1940 *clearing = false;
1941 }
1942 }
1943
update_ui_drag(const game_state * state,game_ui * ui,int gx,int gy)1944 static void update_ui_drag(const game_state *state, game_ui *ui,
1945 int gx, int gy)
1946 {
1947 int /* sz = state->shared->sz, */ w = state->shared->w;
1948 int i, ox, oy, pos;
1949 int lastpos;
1950
1951 if (!INGRID(state, gx, gy))
1952 return; /* square is outside grid */
1953
1954 if (ui->ndragcoords < 0)
1955 return; /* drag not in progress anyway */
1956
1957 pos = gy * w + gx;
1958
1959 lastpos = ui->dragcoords[ui->ndragcoords > 0 ? ui->ndragcoords-1 : 0];
1960 if (pos == lastpos)
1961 return; /* same square as last visited one */
1962
1963 /* Drag confirmed, if it wasn't already. */
1964 if (ui->ndragcoords == 0)
1965 ui->ndragcoords = 1;
1966
1967 /*
1968 * Dragging the mouse into a square that's already been visited by
1969 * the drag path so far has the effect of truncating the path back
1970 * to that square, so a player can back out part of an uncommitted
1971 * drag without having to let go of the mouse.
1972 *
1973 * An exception is that you're allowed to drag round in a loop
1974 * back to the very start of the drag, provided that doesn't
1975 * create a vertex of the wrong degree. This allows a player who's
1976 * after an extra challenge to draw the entire loop in a single
1977 * drag, without it cancelling itself just before release.
1978 */
1979 for (i = 1; i < ui->ndragcoords; i++)
1980 if (pos == ui->dragcoords[i]) {
1981 ui->ndragcoords = i+1;
1982 return;
1983 }
1984
1985 if (pos == ui->dragcoords[0]) {
1986 /* More complex check for a loop-shaped drag, which has to go
1987 * through interpret_ui_drag to decide on the final degree of
1988 * the start/end vertex. */
1989 ui->dragcoords[ui->ndragcoords] = pos;
1990 bool clearing = true;
1991 int lines = state->lines[pos] & (L|R|U|D);
1992 for (i = 0; i < ui->ndragcoords; i++) {
1993 int sx, sy, dx, dy, dir, oldstate, newstate;
1994 interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
1995 &dir, &oldstate, &newstate);
1996 if (sx == gx && sy == gy)
1997 lines ^= (oldstate ^ newstate);
1998 if (dx == gx && dy == gy)
1999 lines ^= (F(oldstate) ^ F(newstate));
2000 }
2001 if (NBITS(lines) > 2) {
2002 /* Bad vertex degree: fall back to the backtracking behaviour. */
2003 ui->ndragcoords = 1;
2004 return;
2005 }
2006 }
2007
2008 /*
2009 * Otherwise, dragging the mouse into a square that's a rook-move
2010 * away from the last one on the path extends the path.
2011 */
2012 oy = ui->dragcoords[ui->ndragcoords-1] / w;
2013 ox = ui->dragcoords[ui->ndragcoords-1] % w;
2014 if (ox == gx || oy == gy) {
2015 int dx = (gx < ox ? -1 : gx > ox ? +1 : 0);
2016 int dy = (gy < oy ? -1 : gy > oy ? +1 : 0);
2017 int dir = (dy>0 ? D : dy<0 ? U : dx>0 ? R : L);
2018 while (ox != gx || oy != gy) {
2019 /*
2020 * If the drag attempts to cross a 'no line here' mark,
2021 * stop there. We physically don't allow the user to drag
2022 * over those marks.
2023 */
2024 if (state->marks[oy*w+ox] & dir)
2025 break;
2026 ox += dx;
2027 oy += dy;
2028 ui->dragcoords[ui->ndragcoords++] = oy * w + ox;
2029 }
2030 }
2031
2032 /*
2033 * Failing that, we do nothing at all: if the user has dragged
2034 * diagonally across the board, they'll just have to return the
2035 * mouse to the last known position and do whatever they meant to
2036 * do again, more slowly and clearly.
2037 */
2038 }
2039
mark_in_direction(const game_state * state,int x,int y,int dir,bool primary,char * buf)2040 static char *mark_in_direction(const game_state *state, int x, int y, int dir,
2041 bool primary, char *buf)
2042 {
2043 int w = state->shared->w /*, h = state->shared->h, sz = state->shared->sz */;
2044 int x2 = x + DX(dir);
2045 int y2 = y + DY(dir);
2046 int dir2 = F(dir);
2047
2048 char ch = primary ? 'F' : 'M', *other;
2049
2050 if (!INGRID(state, x, y) || !INGRID(state, x2, y2)) return UI_UPDATE;
2051
2052 /* disallow laying a mark over a line, or vice versa. */
2053 other = primary ? state->marks : state->lines;
2054 if (other[y*w+x] & dir || other[y2*w+x2] & dir2) return UI_UPDATE;
2055
2056 sprintf(buf, "%c%d,%d,%d;%c%d,%d,%d", ch, dir, x, y, ch, dir2, x2, y2);
2057 return dupstr(buf);
2058 }
2059
2060 #define KEY_DIRECTION(btn) (\
2061 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
2062 (btn) == CURSOR_LEFT ? L : R)
2063
interpret_move(const game_state * state,game_ui * ui,const game_drawstate * ds,int x,int y,int button)2064 static char *interpret_move(const game_state *state, game_ui *ui,
2065 const game_drawstate *ds,
2066 int x, int y, int button)
2067 {
2068 int w = state->shared->w, h = state->shared->h /*, sz = state->shared->sz */;
2069 int gx = FROMCOORD(x), gy = FROMCOORD(y), i;
2070 bool release = false;
2071 char tmpbuf[80];
2072
2073 bool shift = button & MOD_SHFT, control = button & MOD_CTRL;
2074 button &= ~MOD_MASK;
2075
2076 if (IS_MOUSE_DOWN(button)) {
2077 ui->cursor_active = false;
2078
2079 if (!INGRID(state, gx, gy)) {
2080 ui->ndragcoords = -1;
2081 return NULL;
2082 }
2083
2084 ui->clickx = x; ui->clicky = y;
2085 ui->dragcoords[0] = gy * w + gx;
2086 ui->ndragcoords = 0; /* will be 1 once drag is confirmed */
2087
2088 return UI_UPDATE;
2089 }
2090
2091 if (button == LEFT_DRAG && ui->ndragcoords >= 0) {
2092 update_ui_drag(state, ui, gx, gy);
2093 return UI_UPDATE;
2094 }
2095
2096 if (IS_MOUSE_RELEASE(button)) release = true;
2097
2098 if (IS_CURSOR_MOVE(button)) {
2099 if (!ui->cursor_active) {
2100 ui->cursor_active = true;
2101 } else if (control || shift) {
2102 char *move;
2103 if (ui->ndragcoords > 0) return NULL;
2104 ui->ndragcoords = -1;
2105 move = mark_in_direction(state, ui->curx, ui->cury,
2106 KEY_DIRECTION(button), control, tmpbuf);
2107 if (control && !shift && *move)
2108 move_cursor(button, &ui->curx, &ui->cury, w, h, false);
2109 return move;
2110 } else {
2111 move_cursor(button, &ui->curx, &ui->cury, w, h, false);
2112 if (ui->ndragcoords >= 0)
2113 update_ui_drag(state, ui, ui->curx, ui->cury);
2114 }
2115 return UI_UPDATE;
2116 }
2117
2118 if (IS_CURSOR_SELECT(button)) {
2119 if (!ui->cursor_active) {
2120 ui->cursor_active = true;
2121 return UI_UPDATE;
2122 } else if (button == CURSOR_SELECT) {
2123 if (ui->ndragcoords == -1) {
2124 ui->ndragcoords = 0;
2125 ui->dragcoords[0] = ui->cury * w + ui->curx;
2126 ui->clickx = CENTERED_COORD(ui->curx);
2127 ui->clicky = CENTERED_COORD(ui->cury);
2128 return UI_UPDATE;
2129 } else release = true;
2130 } else if (button == CURSOR_SELECT2 && ui->ndragcoords >= 0) {
2131 ui->ndragcoords = -1;
2132 return UI_UPDATE;
2133 }
2134 }
2135
2136 if (button == 27 || button == '\b') {
2137 ui->ndragcoords = -1;
2138 return UI_UPDATE;
2139 }
2140
2141 if (release) {
2142 if (ui->ndragcoords > 0) {
2143 /* End of a drag: process the cached line data. */
2144 int buflen = 0, bufsize = 256, tmplen;
2145 char *buf = NULL;
2146 const char *sep = "";
2147 bool clearing = true;
2148
2149 for (i = 0; i < ui->ndragcoords - 1; i++) {
2150 int sx, sy, dx, dy, dir, oldstate, newstate;
2151 interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
2152 &dir, &oldstate, &newstate);
2153
2154 if (oldstate != newstate) {
2155 if (!buf) buf = snewn(bufsize, char);
2156 tmplen = sprintf(tmpbuf, "%sF%d,%d,%d;F%d,%d,%d", sep,
2157 dir, sx, sy, F(dir), dx, dy);
2158 if (buflen + tmplen >= bufsize) {
2159 bufsize = (buflen + tmplen) * 5 / 4 + 256;
2160 buf = sresize(buf, bufsize, char);
2161 }
2162 strcpy(buf + buflen, tmpbuf);
2163 buflen += tmplen;
2164 sep = ";";
2165 }
2166 }
2167
2168 ui->ndragcoords = -1;
2169
2170 return buf ? buf : UI_UPDATE;
2171 } else if (ui->ndragcoords == 0) {
2172 /* Click (or tiny drag). Work out which edge we were
2173 * closest to. */
2174 int cx, cy;
2175
2176 ui->ndragcoords = -1;
2177
2178 /*
2179 * We process clicks based on the mouse-down location,
2180 * because that's more natural for a user to carefully
2181 * control than the mouse-up.
2182 */
2183 x = ui->clickx;
2184 y = ui->clicky;
2185
2186 gx = FROMCOORD(x);
2187 gy = FROMCOORD(y);
2188 cx = CENTERED_COORD(gx);
2189 cy = CENTERED_COORD(gy);
2190
2191 if (!INGRID(state, gx, gy)) return UI_UPDATE;
2192
2193 if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
2194 /* TODO closer to centre of grid: process as a cell click not an edge click. */
2195
2196 return UI_UPDATE;
2197 } else {
2198 int direction;
2199 if (abs(x-cx) < abs(y-cy)) {
2200 /* Closest to top/bottom edge. */
2201 direction = (y < cy) ? U : D;
2202 } else {
2203 /* Closest to left/right edge. */
2204 direction = (x < cx) ? L : R;
2205 }
2206 return mark_in_direction(state, gx, gy, direction,
2207 (button == LEFT_RELEASE), tmpbuf);
2208 }
2209 }
2210 }
2211
2212 if (button == 'H' || button == 'h')
2213 return dupstr("H");
2214
2215 return NULL;
2216 }
2217
execute_move(const game_state * state,const char * move)2218 static game_state *execute_move(const game_state *state, const char *move)
2219 {
2220 int w = state->shared->w, h = state->shared->h;
2221 char c;
2222 int x, y, l, n;
2223 game_state *ret = dup_game(state);
2224
2225 debug(("move: %s\n", move));
2226
2227 while (*move) {
2228 c = *move;
2229 if (c == 'S') {
2230 ret->used_solve = true;
2231 move++;
2232 } else if (c == 'L' || c == 'N' || c == 'R' || c == 'F' || c == 'M') {
2233 /* 'line' or 'noline' or 'replace' or 'flip' or 'mark' */
2234 move++;
2235 if (sscanf(move, "%d,%d,%d%n", &l, &x, &y, &n) != 3)
2236 goto badmove;
2237 if (!INGRID(state, x, y)) goto badmove;
2238 if (l < 0 || l > 15) goto badmove;
2239
2240 if (c == 'L')
2241 ret->lines[y*w + x] |= (char)l;
2242 else if (c == 'N')
2243 ret->lines[y*w + x] &= ~((char)l);
2244 else if (c == 'R') {
2245 ret->lines[y*w + x] = (char)l;
2246 ret->marks[y*w + x] &= ~((char)l); /* erase marks too */
2247 } else if (c == 'F')
2248 ret->lines[y*w + x] ^= (char)l;
2249 else if (c == 'M')
2250 ret->marks[y*w + x] ^= (char)l;
2251
2252 /*
2253 * If we ended up trying to lay a line _over_ a mark,
2254 * that's a failed move: interpret_move() should have
2255 * ensured we never received a move string like that in
2256 * the first place.
2257 */
2258 if ((ret->lines[y*w + x] & (char)l) &&
2259 (ret->marks[y*w + x] & (char)l))
2260 goto badmove;
2261
2262 move += n;
2263 } else if (strcmp(move, "H") == 0) {
2264 pearl_solve(ret->shared->w, ret->shared->h,
2265 ret->shared->clues, ret->lines, DIFFCOUNT, true);
2266 for (n = 0; n < w*h; n++)
2267 ret->marks[n] &= ~ret->lines[n]; /* erase marks too */
2268 move++;
2269 } else {
2270 goto badmove;
2271 }
2272 if (*move == ';')
2273 move++;
2274 else if (*move)
2275 goto badmove;
2276 }
2277
2278 check_completion(ret, true);
2279
2280 return ret;
2281
2282 badmove:
2283 free_game(ret);
2284 return NULL;
2285 }
2286
2287 /* ----------------------------------------------------------------------
2288 * Drawing routines.
2289 */
2290
2291 #define FLASH_TIME 0.5F
2292
game_compute_size(const game_params * params,int tilesize,int * x,int * y)2293 static void game_compute_size(const game_params *params, int tilesize,
2294 int *x, int *y)
2295 {
2296 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2297 struct { int halfsz; } ads, *ds = &ads;
2298 ads.halfsz = (tilesize-1)/2;
2299
2300 *x = (params->w) * TILE_SIZE + 2 * BORDER;
2301 *y = (params->h) * TILE_SIZE + 2 * BORDER;
2302 }
2303
game_set_size(drawing * dr,game_drawstate * ds,const game_params * params,int tilesize)2304 static void game_set_size(drawing *dr, game_drawstate *ds,
2305 const game_params *params, int tilesize)
2306 {
2307 ds->halfsz = (tilesize-1)/2;
2308 }
2309
game_colours(frontend * fe,int * ncolours)2310 static float *game_colours(frontend *fe, int *ncolours)
2311 {
2312 float *ret = snewn(3 * NCOLOURS, float);
2313 int i;
2314
2315 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2316
2317 for (i = 0; i < 3; i++) {
2318 ret[COL_BLACK * 3 + i] = 0.0F;
2319 ret[COL_WHITE * 3 + i] = 1.0F;
2320 ret[COL_GRID * 3 + i] = 0.4F;
2321 }
2322
2323 ret[COL_ERROR * 3 + 0] = 1.0F;
2324 ret[COL_ERROR * 3 + 1] = 0.0F;
2325 ret[COL_ERROR * 3 + 2] = 0.0F;
2326
2327 ret[COL_DRAGON * 3 + 0] = 0.0F;
2328 ret[COL_DRAGON * 3 + 1] = 0.0F;
2329 ret[COL_DRAGON * 3 + 2] = 1.0F;
2330
2331 ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2332 ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2333 ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2334
2335 ret[COL_FLASH * 3 + 0] = 1.0F;
2336 ret[COL_FLASH * 3 + 1] = 1.0F;
2337 ret[COL_FLASH * 3 + 2] = 1.0F;
2338
2339 *ncolours = NCOLOURS;
2340
2341 return ret;
2342 }
2343
game_new_drawstate(drawing * dr,const game_state * state)2344 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2345 {
2346 struct game_drawstate *ds = snew(struct game_drawstate);
2347 int i;
2348
2349 ds->halfsz = 0;
2350 ds->started = false;
2351
2352 ds->w = state->shared->w;
2353 ds->h = state->shared->h;
2354 ds->sz = state->shared->sz;
2355 ds->lflags = snewn(ds->sz, unsigned int);
2356 for (i = 0; i < ds->sz; i++)
2357 ds->lflags[i] = 0;
2358
2359 ds->draglines = snewn(ds->sz, char);
2360
2361 return ds;
2362 }
2363
game_free_drawstate(drawing * dr,game_drawstate * ds)2364 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2365 {
2366 sfree(ds->draglines);
2367 sfree(ds->lflags);
2368 sfree(ds);
2369 }
2370
draw_lines_specific(drawing * dr,game_drawstate * ds,int x,int y,unsigned int lflags,unsigned int shift,int c)2371 static void draw_lines_specific(drawing *dr, game_drawstate *ds,
2372 int x, int y, unsigned int lflags,
2373 unsigned int shift, int c)
2374 {
2375 int ox = COORD(x), oy = COORD(y);
2376 int t2 = HALFSZ, t16 = HALFSZ/4;
2377 int cx = ox + t2, cy = oy + t2;
2378 int d;
2379
2380 /* Draw each of the four directions, where laid (or error, or drag, etc.) */
2381 for (d = 1; d < 16; d *= 2) {
2382 int xoff = t2 * DX(d), yoff = t2 * DY(d);
2383 int xnudge = abs(t16 * DX(C(d))), ynudge = abs(t16 * DY(C(d)));
2384
2385 if ((lflags >> shift) & d) {
2386 int lx = cx + ((xoff < 0) ? xoff : 0) - xnudge;
2387 int ly = cy + ((yoff < 0) ? yoff : 0) - ynudge;
2388
2389 if (c == COL_DRAGOFF && !(lflags & d))
2390 continue;
2391 if (c == COL_DRAGON && (lflags & d))
2392 continue;
2393
2394 draw_rect(dr, lx, ly,
2395 abs(xoff)+2*xnudge+1,
2396 abs(yoff)+2*ynudge+1, c);
2397 /* end cap */
2398 draw_rect(dr, cx - t16, cy - t16, 2*t16+1, 2*t16+1, c);
2399 }
2400 }
2401 }
2402
draw_square(drawing * dr,game_drawstate * ds,const game_ui * ui,int x,int y,unsigned int lflags,char clue)2403 static void draw_square(drawing *dr, game_drawstate *ds, const game_ui *ui,
2404 int x, int y, unsigned int lflags, char clue)
2405 {
2406 int ox = COORD(x), oy = COORD(y);
2407 int t2 = HALFSZ, t16 = HALFSZ/4;
2408 int cx = ox + t2, cy = oy + t2;
2409 int d;
2410
2411 assert(dr);
2412
2413 /* Clip to the grid square. */
2414 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2415
2416 /* Clear the square. */
2417 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
2418 (lflags & DS_CURSOR) ?
2419 COL_CURSOR_BACKGROUND : COL_BACKGROUND);
2420
2421
2422 if (get_gui_style() == GUI_LOOPY) {
2423 /* Draw small dot, underneath any lines. */
2424 draw_circle(dr, cx, cy, t16, COL_GRID, COL_GRID);
2425 } else {
2426 /* Draw outline of grid square */
2427 draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID);
2428 draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID);
2429 }
2430
2431 /* Draw grid: either thin gridlines, or no-line marks.
2432 * We draw these first because the thick laid lines should be on top. */
2433 for (d = 1; d < 16; d *= 2) {
2434 int xoff = t2 * DX(d), yoff = t2 * DY(d);
2435
2436 if ((x == 0 && d == L) ||
2437 (y == 0 && d == U) ||
2438 (x == ds->w-1 && d == R) ||
2439 (y == ds->h-1 && d == D))
2440 continue; /* no gridlines out to the border. */
2441
2442 if ((lflags >> DS_MSHIFT) & d) {
2443 /* either a no-line mark ... */
2444 int mx = cx + xoff, my = cy + yoff, msz = t16;
2445
2446 draw_line(dr, mx-msz, my-msz, mx+msz, my+msz, COL_BLACK);
2447 draw_line(dr, mx-msz, my+msz, mx+msz, my-msz, COL_BLACK);
2448 } else {
2449 if (get_gui_style() == GUI_LOOPY) {
2450 /* draw grid lines connecting centre of cells */
2451 draw_line(dr, cx, cy, cx+xoff, cy+yoff, COL_GRID);
2452 }
2453 }
2454 }
2455
2456 /* Draw each of the four directions, where laid (or error, or drag, etc.)
2457 * Order is important here, specifically for the eventual colours of the
2458 * exposed end caps. */
2459 draw_lines_specific(dr, ds, x, y, lflags, 0,
2460 (lflags & DS_FLASH ? COL_FLASH : COL_BLACK));
2461 draw_lines_specific(dr, ds, x, y, lflags, DS_ESHIFT, COL_ERROR);
2462 draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGOFF);
2463 draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGON);
2464
2465 /* Draw a clue, if present */
2466 if (clue != NOCLUE) {
2467 int c = (lflags & DS_FLASH) ? COL_FLASH :
2468 (clue == STRAIGHT) ? COL_WHITE : COL_BLACK;
2469
2470 if (lflags & DS_ERROR_CLUE) /* draw a bigger 'error' clue circle. */
2471 draw_circle(dr, cx, cy, TILE_SIZE*3/8, COL_ERROR, COL_ERROR);
2472
2473 draw_circle(dr, cx, cy, TILE_SIZE/4, c, COL_BLACK);
2474 }
2475
2476 unclip(dr);
2477 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2478 }
2479
game_redraw(drawing * dr,game_drawstate * ds,const game_state * oldstate,const game_state * state,int dir,const game_ui * ui,float animtime,float flashtime)2480 static void game_redraw(drawing *dr, game_drawstate *ds,
2481 const game_state *oldstate, const game_state *state,
2482 int dir, const game_ui *ui,
2483 float animtime, float flashtime)
2484 {
2485 int w = state->shared->w, h = state->shared->h, sz = state->shared->sz;
2486 int x, y, flashing = 0;
2487 bool force = false;
2488
2489 if (!ds->started) {
2490 if (get_gui_style() == GUI_MASYU) {
2491 /*
2492 * Black rectangle which is the main grid.
2493 */
2494 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
2495 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
2496 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
2497 COL_GRID);
2498 }
2499
2500 draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
2501
2502 ds->started = true;
2503 force = true;
2504 }
2505
2506 if (flashtime > 0 &&
2507 (flashtime <= FLASH_TIME/3 ||
2508 flashtime >= FLASH_TIME*2/3))
2509 flashing = DS_FLASH;
2510
2511 memset(ds->draglines, 0, sz);
2512 if (ui->ndragcoords > 0) {
2513 int i;
2514 bool clearing = true;
2515 for (i = 0; i < ui->ndragcoords - 1; i++) {
2516 int sx, sy, dx, dy, dir, oldstate, newstate;
2517 interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
2518 &dir, &oldstate, &newstate);
2519 ds->draglines[sy*w+sx] ^= (oldstate ^ newstate);
2520 ds->draglines[dy*w+dx] ^= (F(oldstate) ^ F(newstate));
2521 }
2522 }
2523
2524 for (x = 0; x < w; x++) {
2525 for (y = 0; y < h; y++) {
2526 unsigned int f = (unsigned int)state->lines[y*w+x];
2527 unsigned int eline = (unsigned int)(state->errors[y*w+x] & (R|U|L|D));
2528
2529 f |= eline << DS_ESHIFT;
2530 f |= ((unsigned int)ds->draglines[y*w+x]) << DS_DSHIFT;
2531 f |= ((unsigned int)state->marks[y*w+x]) << DS_MSHIFT;
2532
2533 if (state->errors[y*w+x] & ERROR_CLUE)
2534 f |= DS_ERROR_CLUE;
2535
2536 f |= flashing;
2537
2538 if (ui->cursor_active && x == ui->curx && y == ui->cury)
2539 f |= DS_CURSOR;
2540
2541 if (f != ds->lflags[y*w+x] || force) {
2542 ds->lflags[y*w+x] = f;
2543 draw_square(dr, ds, ui, x, y, f, state->shared->clues[y*w+x]);
2544 }
2545 }
2546 }
2547 }
2548
game_anim_length(const game_state * oldstate,const game_state * newstate,int dir,game_ui * ui)2549 static float game_anim_length(const game_state *oldstate,
2550 const game_state *newstate, int dir, game_ui *ui)
2551 {
2552 return 0.0F;
2553 }
2554
game_flash_length(const game_state * oldstate,const game_state * newstate,int dir,game_ui * ui)2555 static float game_flash_length(const game_state *oldstate,
2556 const game_state *newstate, int dir, game_ui *ui)
2557 {
2558 if (!oldstate->completed && newstate->completed &&
2559 !oldstate->used_solve && !newstate->used_solve)
2560 return FLASH_TIME;
2561 else
2562 return 0.0F;
2563 }
2564
game_get_cursor_location(const game_ui * ui,const game_drawstate * ds,const game_state * state,const game_params * params,int * x,int * y,int * w,int * h)2565 static void game_get_cursor_location(const game_ui *ui,
2566 const game_drawstate *ds,
2567 const game_state *state,
2568 const game_params *params,
2569 int *x, int *y, int *w, int *h)
2570 {
2571 if(ui->cursor_active) {
2572 *x = COORD(ui->curx);
2573 *y = COORD(ui->cury);
2574 *w = *h = TILE_SIZE;
2575 }
2576 }
2577
game_status(const game_state * state)2578 static int game_status(const game_state *state)
2579 {
2580 return state->completed ? +1 : 0;
2581 }
2582
game_timing_state(const game_state * state,game_ui * ui)2583 static bool game_timing_state(const game_state *state, game_ui *ui)
2584 {
2585 return true;
2586 }
2587
game_print_size(const game_params * params,float * x,float * y)2588 static void game_print_size(const game_params *params, float *x, float *y)
2589 {
2590 int pw, ph;
2591
2592 /*
2593 * I'll use 6mm squares by default.
2594 */
2595 game_compute_size(params, 600, &pw, &ph);
2596 *x = pw / 100.0F;
2597 *y = ph / 100.0F;
2598 }
2599
game_print(drawing * dr,const game_state * state,int tilesize)2600 static void game_print(drawing *dr, const game_state *state, int tilesize)
2601 {
2602 int w = state->shared->w, h = state->shared->h, x, y;
2603 int black = print_mono_colour(dr, 0);
2604 int white = print_mono_colour(dr, 1);
2605
2606 /* No GUI_LOOPY here: only use the familiar masyu style. */
2607
2608 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2609 game_drawstate *ds = game_new_drawstate(dr, state);
2610 game_set_size(dr, ds, NULL, tilesize);
2611
2612 /* Draw grid outlines (black). */
2613 for (x = 0; x <= w; x++)
2614 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black);
2615 for (y = 0; y <= h; y++)
2616 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black);
2617
2618 for (x = 0; x < w; x++) {
2619 for (y = 0; y < h; y++) {
2620 int cx = COORD(x) + HALFSZ, cy = COORD(y) + HALFSZ;
2621 int clue = state->shared->clues[y*w+x];
2622
2623 draw_lines_specific(dr, ds, x, y, state->lines[y*w+x], 0, black);
2624
2625 if (clue != NOCLUE) {
2626 int c = (clue == CORNER) ? black : white;
2627 draw_circle(dr, cx, cy, TILE_SIZE/4, c, black);
2628 }
2629 }
2630 }
2631
2632 game_free_drawstate(dr, ds);
2633 }
2634
2635 #ifdef COMBINED
2636 #define thegame pearl
2637 #endif
2638
2639 const struct game thegame = {
2640 "Pearl", "games.pearl", "pearl",
2641 default_params,
2642 game_fetch_preset, NULL,
2643 decode_params,
2644 encode_params,
2645 free_params,
2646 dup_params,
2647 true, game_configure, custom_params,
2648 validate_params,
2649 new_game_desc,
2650 validate_desc,
2651 new_game,
2652 dup_game,
2653 free_game,
2654 true, solve_game,
2655 true, game_can_format_as_text_now, game_text_format,
2656 new_ui,
2657 free_ui,
2658 encode_ui,
2659 decode_ui,
2660 NULL, /* game_request_keys */
2661 game_changed_state,
2662 interpret_move,
2663 execute_move,
2664 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2665 game_colours,
2666 game_new_drawstate,
2667 game_free_drawstate,
2668 game_redraw,
2669 game_anim_length,
2670 game_flash_length,
2671 game_get_cursor_location,
2672 game_status,
2673 true, false, game_print_size, game_print,
2674 false, /* wants_statusbar */
2675 false, game_timing_state,
2676 0, /* flags */
2677 };
2678
2679 #ifdef STANDALONE_SOLVER
2680
2681 #include <time.h>
2682 #include <stdarg.h>
2683
2684 const char *quis = NULL;
2685
usage(FILE * out)2686 static void usage(FILE *out) {
2687 fprintf(out, "usage: %s <params>\n", quis);
2688 }
2689
pnum(int n,int ntot,const char * desc)2690 static void pnum(int n, int ntot, const char *desc)
2691 {
2692 printf("%2.1f%% (%d) %s", (double)n*100.0 / (double)ntot, n, desc);
2693 }
2694
start_soak(game_params * p,random_state * rs,int nsecs)2695 static void start_soak(game_params *p, random_state *rs, int nsecs)
2696 {
2697 time_t tt_start, tt_now, tt_last;
2698 int n = 0, nsolved = 0, nimpossible = 0, ret;
2699 char *grid, *clues;
2700
2701 tt_start = tt_last = time(NULL);
2702
2703 /* Currently this generates puzzles of any difficulty (trying to solve it
2704 * on the maximum difficulty level and not checking it's not too easy). */
2705 printf("Soak-testing a %dx%d grid (any difficulty)", p->w, p->h);
2706 if (nsecs > 0) printf(" for %d seconds", nsecs);
2707 printf(".\n");
2708
2709 p->nosolve = true;
2710
2711 grid = snewn(p->w*p->h, char);
2712 clues = snewn(p->w*p->h, char);
2713
2714 while (1) {
2715 n += new_clues(p, rs, clues, grid); /* should be 1, with nosolve */
2716
2717 ret = pearl_solve(p->w, p->h, clues, grid, DIFF_TRICKY, false);
2718 if (ret <= 0) nimpossible++;
2719 if (ret == 1) nsolved++;
2720
2721 tt_now = time(NULL);
2722 if (tt_now > tt_last) {
2723 tt_last = tt_now;
2724
2725 printf("%d total, %3.1f/s, ",
2726 n, (double)n / ((double)tt_now - tt_start));
2727 pnum(nsolved, n, "solved"); printf(", ");
2728 printf("%3.1f/s", (double)nsolved / ((double)tt_now - tt_start));
2729 if (nimpossible > 0)
2730 pnum(nimpossible, n, "impossible");
2731 printf("\n");
2732 }
2733 if (nsecs > 0 && (tt_now - tt_start) > nsecs) {
2734 printf("\n");
2735 break;
2736 }
2737 }
2738
2739 sfree(grid);
2740 sfree(clues);
2741 }
2742
main(int argc,char * argv[])2743 int main(int argc, char *argv[])
2744 {
2745 game_params *p = NULL;
2746 random_state *rs = NULL;
2747 time_t seed = time(NULL);
2748 char *id = NULL;
2749 const char *err;
2750
2751 setvbuf(stdout, NULL, _IONBF, 0);
2752
2753 quis = argv[0];
2754
2755 while (--argc > 0) {
2756 char *p = (char*)(*++argv);
2757 if (!strcmp(p, "-e") || !strcmp(p, "--seed")) {
2758 seed = atoi(*++argv);
2759 argc--;
2760 } else if (*p == '-') {
2761 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2762 usage(stderr);
2763 exit(1);
2764 } else {
2765 id = p;
2766 }
2767 }
2768
2769 rs = random_new((void*)&seed, sizeof(time_t));
2770 p = default_params();
2771
2772 if (id) {
2773 if (strchr(id, ':')) {
2774 fprintf(stderr, "soak takes params only.\n");
2775 goto done;
2776 }
2777
2778 decode_params(p, id);
2779 err = validate_params(p, true);
2780 if (err) {
2781 fprintf(stderr, "%s: %s", argv[0], err);
2782 goto done;
2783 }
2784
2785 start_soak(p, rs, 0); /* run forever */
2786 } else {
2787 int i;
2788
2789 for (i = 5; i <= 12; i++) {
2790 p->w = p->h = i;
2791 start_soak(p, rs, 5);
2792 }
2793 }
2794
2795 done:
2796 free_params(p);
2797 random_free(rs);
2798
2799 return 0;
2800 }
2801
2802 #endif
2803
2804 /* vim: set shiftwidth=4 tabstop=8: */
2805