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