2
* pearl.c: Nikoli's `Masyu' puzzle.
8
* - The current keyboard cursor mechanism works well on ordinary PC
9
* keyboards, but for platforms with only arrow keys and a select
10
* button or two, we may at some point need a simpler one which can
11
* handle 'x' markings without needing shift keys. For instance, a
12
* cursor with twice the grid resolution, so that it can range
13
* across face centres, edge centres and vertices; 'clicks' on face
14
* centres begin a drag as currently, clicks on edges toggle
15
* markings, and clicks on vertices are ignored (but it would be
16
* too confusing not to let the cursor rest on them). But I'm
17
* pretty sure that would be less pleasant to play on a full
18
* keyboard, so probably a #ifdef would be the thing.
20
* - Generation is still pretty slow, due to difficulty coming up in
21
* the first place with a loop that makes a soluble puzzle even
22
* with all possible clues filled in.
23
* + A possible alternative strategy to further tuning of the
24
* existing loop generator would be to throw the entire
25
* mechanism out and instead write a different generator from
26
* scratch which evolves the solution along with the puzzle:
27
* place a few clues, nail down a bit of the loop, place another
28
* clue, nail down some more, etc. However, I don't have a
29
* detailed plan for any such mechanism, so it may be a pipe
44
#define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0)
55
#define DX(d) ( ((d)==R) - ((d)==L) )
56
#define DY(d) ( ((d)==D) - ((d)==U) )
58
#define F(d) (((d << 2) | (d >> 2)) & 0xF)
59
#define C(d) (((d << 3) | (d >> 1)) & 0xF)
60
#define A(d) (((d << 1) | (d >> 3)) & 0xF)
89
#define bBLANK (1 << BLANK)
92
COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT,
93
COL_CURSOR_BACKGROUND = COL_LOWLIGHT,
95
COL_ERROR, COL_GRID, COL_FLASH,
96
COL_DRAGON, COL_DRAGOFF,
100
/* Macro ickery copied from slant.c */
101
#define DIFFLIST(A) \
104
#define ENUM(upper,title,lower) DIFF_ ## upper,
105
#define TITLE(upper,title,lower) #title,
106
#define ENCODE(upper,title,lower) #lower
107
#define CONFIG(upper,title,lower) ":" #title
108
enum { DIFFLIST(ENUM) DIFFCOUNT };
109
static char const *const pearl_diffnames[] = { DIFFLIST(TITLE) "(count)" };
110
static char const pearl_diffchars[] = DIFFLIST(ENCODE);
111
#define DIFFCONFIG DIFFLIST(CONFIG)
116
int nosolve; /* XXX remove me! */
119
struct shared_state {
121
char *clues; /* size w*h */
125
#define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->shared->w && \
126
(gy) >= 0 && (gy) < (state)->shared->h)
128
struct shared_state *shared;
129
char *lines; /* size w*h: lines placed */
130
char *errors; /* size w*h: errors detected */
131
char *marks; /* size w*h: 'no line here' marks placed. */
132
int completed, used_solve;
133
int loop_length; /* filled in by check_completion when complete. */
136
#define DEFAULT_PRESET 3
138
static const struct game_params pearl_presets[] = {
144
{10, 10, DIFF_TRICKY},
146
{12, 8, DIFF_TRICKY},
149
static game_params *default_params(void)
151
game_params *ret = snew(game_params);
153
*ret = pearl_presets[DEFAULT_PRESET];
154
ret->nosolve = FALSE;
159
static int game_fetch_preset(int i, char **name, game_params **params)
164
if (i < 0 || i >= lenof(pearl_presets)) return FALSE;
166
ret = default_params();
167
*ret = pearl_presets[i]; /* struct copy */
170
sprintf(buf, "%dx%d %s",
171
pearl_presets[i].w, pearl_presets[i].h,
172
pearl_diffnames[pearl_presets[i].difficulty]);
178
static void free_params(game_params *params)
183
static game_params *dup_params(const game_params *params)
185
game_params *ret = snew(game_params);
186
*ret = *params; /* structure copy */
190
static void decode_params(game_params *ret, char const *string)
192
ret->w = ret->h = atoi(string);
193
while (*string && isdigit((unsigned char) *string)) ++string;
194
if (*string == 'x') {
196
ret->h = atoi(string);
197
while (*string && isdigit((unsigned char)*string)) string++;
200
ret->difficulty = DIFF_EASY;
201
if (*string == 'd') {
204
for (i = 0; i < DIFFCOUNT; i++)
205
if (*string == pearl_diffchars[i])
207
if (*string) string++;
210
ret->nosolve = FALSE;
211
if (*string == 'n') {
217
static char *encode_params(const game_params *params, int full)
220
sprintf(buf, "%dx%d", params->w, params->h);
222
sprintf(buf + strlen(buf), "d%c%s",
223
pearl_diffchars[params->difficulty],
224
params->nosolve ? "n" : "");
228
static config_item *game_configure(const game_params *params)
233
ret = snewn(5, config_item);
235
ret[0].name = "Width";
236
ret[0].type = C_STRING;
237
sprintf(buf, "%d", params->w);
238
ret[0].sval = dupstr(buf);
241
ret[1].name = "Height";
242
ret[1].type = C_STRING;
243
sprintf(buf, "%d", params->h);
244
ret[1].sval = dupstr(buf);
247
ret[2].name = "Difficulty";
248
ret[2].type = C_CHOICES;
249
ret[2].sval = DIFFCONFIG;
250
ret[2].ival = params->difficulty;
252
ret[3].name = "Allow unsoluble";
253
ret[3].type = C_BOOLEAN;
255
ret[3].ival = params->nosolve;
265
static game_params *custom_params(const config_item *cfg)
267
game_params *ret = snew(game_params);
269
ret->w = atoi(cfg[0].sval);
270
ret->h = atoi(cfg[1].sval);
271
ret->difficulty = cfg[2].ival;
272
ret->nosolve = cfg[3].ival;
277
static char *validate_params(const game_params *params, int full)
279
if (params->w < 5) return "Width must be at least five";
280
if (params->h < 5) return "Height must be at least five";
281
if (params->difficulty < 0 || params->difficulty >= DIFFCOUNT)
282
return "Unknown difficulty level";
287
/* ----------------------------------------------------------------------
291
int pearl_solve(int w, int h, char *clues, char *result,
292
int difficulty, int partial)
294
int W = 2*w+1, H = 2*h+1;
301
* workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature
302
* of the square (x,y), as a logical OR of bitfields.
304
* workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates
305
* whether the horizontal edge between (x,y) and (x+1,y) is
306
* connected (1), disconnected (2) or unknown (3).
308
* workspace[(2*y+1)*W+(2*x)], indicates the same about the
309
* vertical edge between (x,y) and (x,y+1).
311
* Initially, every square is considered capable of being in
312
* any of the seven possible states (two straights, four
313
* corners and empty), except those corresponding to clue
314
* squares which are more restricted.
316
* Initially, all edges are unknown, except the ones around the
317
* grid border which are known to be disconnected.
319
workspace = snewn(W*H, short);
320
for (x = 0; x < W*H; x++)
323
for (y = 0; y < h; y++)
324
for (x = 0; x < w; x++)
325
switch (clues[y*w+x]) {
327
workspace[(2*y+1)*W+(2*x+1)] = bLU|bLD|bRU|bRD;
330
workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD;
333
workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD|bLU|bLD|bRU|bRD|bBLANK;
336
/* Horizontal edges */
337
for (y = 0; y <= h; y++)
338
for (x = 0; x < w; x++)
339
workspace[(2*y)*W+(2*x+1)] = (y==0 || y==h ? 2 : 3);
341
for (y = 0; y < h; y++)
342
for (x = 0; x <= w; x++)
343
workspace[(2*y+1)*W+(2*x)] = (x==0 || x==w ? 2 : 3);
346
* We maintain a dsf of connected squares, together with a
347
* count of the size of each equivalence class.
349
dsf = snewn(w*h, int);
350
dsfsize = snewn(w*h, int);
353
* Now repeatedly try to find something we can do.
356
int done_something = FALSE;
358
#ifdef SOLVER_DIAGNOSTICS
359
for (y = 0; y < H; y++) {
360
for (x = 0; x < W; x++)
361
printf("%*x", (x&1) ? 5 : 2, workspace[y*W+x]);
367
* Go through the square state words, and discard any
368
* square state which is inconsistent with known facts
369
* about the edges around the square.
371
for (y = 0; y < h; y++)
372
for (x = 0; x < w; x++) {
373
for (b = 0; b < 0xD; b++)
374
if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
376
* If any edge of this square is known to
377
* be connected when state b would require
378
* it disconnected, or vice versa, discard
381
for (d = 1; d <= 8; d += d) {
382
int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
383
if (workspace[ey*W+ex] ==
385
workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<b);
386
#ifdef SOLVER_DIAGNOSTICS
387
printf("edge (%d,%d)-(%d,%d) rules out state"
388
" %d for square (%d,%d)\n",
389
ex/2, ey/2, (ex+1)/2, (ey+1)/2,
392
done_something = TRUE;
399
* Consistency check: each square must have at
400
* least one state left!
402
if (!workspace[(2*y+1)*W+(2*x+1)]) {
403
#ifdef SOLVER_DIAGNOSTICS
404
printf("edge check at (%d,%d): inconsistency\n", x, y);
412
* Now go through the states array again, and nail down any
413
* unknown edge if one of its neighbouring squares makes it
416
for (y = 0; y < h; y++)
417
for (x = 0; x < w; x++) {
418
int edgeor = 0, edgeand = 15;
420
for (b = 0; b < 0xD; b++)
421
if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
427
* Now any bit clear in edgeor marks a disconnected
428
* edge, and any bit set in edgeand marks a
432
/* First check consistency: neither bit is both! */
433
if (edgeand & ~edgeor) {
434
#ifdef SOLVER_DIAGNOSTICS
435
printf("square check at (%d,%d): inconsistency\n", x, y);
441
for (d = 1; d <= 8; d += d) {
442
int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
444
if (!(edgeor & d) && workspace[ey*W+ex] == 3) {
445
workspace[ey*W+ex] = 2;
446
done_something = TRUE;
447
#ifdef SOLVER_DIAGNOSTICS
448
printf("possible states of square (%d,%d) force edge"
449
" (%d,%d)-(%d,%d) to be disconnected\n",
450
x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
452
} else if ((edgeand & d) && workspace[ey*W+ex] == 3) {
453
workspace[ey*W+ex] = 1;
454
done_something = TRUE;
455
#ifdef SOLVER_DIAGNOSTICS
456
printf("possible states of square (%d,%d) force edge"
457
" (%d,%d)-(%d,%d) to be connected\n",
458
x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
468
* Now for longer-range clue-based deductions (using the
469
* rules that a corner clue must connect to two straight
470
* squares, and a straight clue must connect to at least
471
* one corner square).
473
for (y = 0; y < h; y++)
474
for (x = 0; x < w; x++)
475
switch (clues[y*w+x]) {
477
for (d = 1; d <= 8; d += d) {
478
int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
479
int fx = ex + DX(d), fy = ey + DY(d);
482
if (workspace[ey*W+ex] == 1) {
484
* If a corner clue is connected on any
485
* edge, then we can immediately nail
486
* down the square beyond that edge as
487
* being a straight in the appropriate
490
if (workspace[fy*W+fx] != (1<<type)) {
491
workspace[fy*W+fx] = (1<<type);
492
done_something = TRUE;
493
#ifdef SOLVER_DIAGNOSTICS
494
printf("corner clue at (%d,%d) forces square "
495
"(%d,%d) into state %d\n", x, y,
500
} else if (workspace[ey*W+ex] == 3) {
502
* Conversely, if a corner clue is
503
* separated by an unknown edge from a
504
* square which _cannot_ be a straight
505
* in the appropriate direction, we can
506
* mark that edge as disconnected.
508
if (!(workspace[fy*W+fx] & (1<<type))) {
509
workspace[ey*W+ex] = 2;
510
done_something = TRUE;
511
#ifdef SOLVER_DIAGNOSTICS
512
printf("corner clue at (%d,%d), plus square "
513
"(%d,%d) not being state %d, "
514
"disconnects edge (%d,%d)-(%d,%d)\n",
515
x, y, fx/2, fy/2, type,
516
ex/2, ey/2, (ex+1)/2, (ey+1)/2);
526
* If a straight clue is between two squares
527
* neither of which is capable of being a
528
* corner connected to it, then the straight
529
* clue cannot point in that direction.
531
for (d = 1; d <= 2; d += d) {
532
int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
533
int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
536
if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type)))
539
if (!(workspace[fy*W+fx] & ((1<<(F(d)|A(d))) |
540
(1<<(F(d)|C(d))))) &&
541
!(workspace[gy*W+gx] & ((1<<( d |A(d))) |
543
workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<type);
544
done_something = TRUE;
545
#ifdef SOLVER_DIAGNOSTICS
546
printf("straight clue at (%d,%d) cannot corner at "
547
"(%d,%d) or (%d,%d) so is not state %d\n",
548
x, y, fx/2, fy/2, gx/2, gy/2, type);
555
* If a straight clue with known direction is
556
* connected on one side to a known straight,
557
* then on the other side it must be a corner.
559
for (d = 1; d <= 8; d += d) {
560
int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
561
int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
564
if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type))
567
if (!(workspace[fy*W+fx] &~ (bLR|bUD)) &&
568
(workspace[gy*W+gx] &~ (bLU|bLD|bRU|bRD))) {
569
workspace[gy*W+gx] &= (bLU|bLD|bRU|bRD);
570
done_something = TRUE;
571
#ifdef SOLVER_DIAGNOSTICS
572
printf("straight clue at (%d,%d) connecting to "
573
"straight at (%d,%d) makes (%d,%d) a "
574
"corner\n", x, y, fx/2, fy/2, gx/2, gy/2);
586
* Now detect shortcut loops.
590
int nonblanks, loopclass;
593
for (x = 0; x < w*h; x++)
597
* First go through the edge entries and update the dsf
598
* of which squares are connected to which others. We
599
* also track the number of squares in each equivalence
600
* class, and count the overall number of
601
* known-non-blank squares.
603
* In the process of doing this, we must notice if a
604
* loop has already been formed. If it has, we blank
605
* out any square which isn't part of that loop
606
* (failing a consistency check if any such square does
607
* not have BLANK as one of its remaining options) and
608
* exit the deduction loop with success.
612
for (y = 1; y < H-1; y++)
613
for (x = 1; x < W-1; x++)
616
* (x,y) are the workspace coordinates of
617
* an edge field. Compute the normal-space
618
* coordinates of the squares it connects.
620
int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
621
int bx = x/2, by = y/2, bc = by*w+bx;
624
* If the edge is connected, do the dsf
627
if (workspace[y*W+x] == 1) {
630
ae = dsf_canonify(dsf, ac);
631
be = dsf_canonify(dsf, bc);
637
if (loopclass != -1) {
639
* In fact, we have two
640
* separate loops, which is
643
#ifdef SOLVER_DIAGNOSTICS
644
printf("two loops found in grid!\n");
652
* Merge the two equivalence
655
int size = dsfsize[ae] + dsfsize[be];
656
dsf_merge(dsf, ac, bc);
657
ae = dsf_canonify(dsf, ac);
661
} else if ((y & x) & 1) {
663
* (x,y) are the workspace coordinates of a
664
* square field. If the square is
665
* definitely not blank, count it.
667
if (!(workspace[y*W+x] & bBLANK))
672
* If we discovered an existing loop above, we must now
673
* blank every square not part of it, and exit the main
676
if (loopclass != -1) {
677
#ifdef SOLVER_DIAGNOSTICS
678
printf("loop found in grid!\n");
680
for (y = 0; y < h; y++)
681
for (x = 0; x < w; x++)
682
if (dsf_canonify(dsf, y*w+x) != loopclass) {
683
if (workspace[(y*2+1)*W+(x*2+1)] & bBLANK) {
684
workspace[(y*2+1)*W+(x*2+1)] = bBLANK;
687
* This square is not part of the
688
* loop, but is known non-blank. We
691
#ifdef SOLVER_DIAGNOSTICS
692
printf("non-blank square (%d,%d) found outside"
706
/* Further deductions are considered 'tricky'. */
707
if (difficulty == DIFF_EASY) goto done_deductions;
710
* Now go through the workspace again and mark any edge
711
* which would cause a shortcut loop (i.e. would
712
* connect together two squares in the same equivalence
713
* class, and that equivalence class does not contain
714
* _all_ the known-non-blank squares currently in the
715
* grid) as disconnected. Also, mark any _square state_
716
* which would cause a shortcut loop as disconnected.
718
for (y = 1; y < H-1; y++)
719
for (x = 1; x < W-1; x++)
722
* (x,y) are the workspace coordinates of
723
* an edge field. Compute the normal-space
724
* coordinates of the squares it connects.
726
int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
727
int bx = x/2, by = y/2, bc = by*w+bx;
730
* If the edge is currently unknown, and
731
* sits between two squares in the same
732
* equivalence class, and the size of that
733
* class is less than nonblanks, then
734
* connecting this edge would be a shortcut
735
* loop and so we must not do so.
737
if (workspace[y*W+x] == 3) {
740
ae = dsf_canonify(dsf, ac);
741
be = dsf_canonify(dsf, bc);
745
* We have a loop. Is it a shortcut?
747
if (dsfsize[ae] < nonblanks) {
749
* Yes! Mark this edge disconnected.
751
workspace[y*W+x] = 2;
752
done_something = TRUE;
753
#ifdef SOLVER_DIAGNOSTICS
754
printf("edge (%d,%d)-(%d,%d) would create"
755
" a shortcut loop, hence must be"
756
" disconnected\n", x/2, y/2,
762
} else if ((y & x) & 1) {
764
* (x,y) are the workspace coordinates of a
765
* square field. Go through its possible
766
* (non-blank) states and see if any gives
767
* rise to a shortcut loop.
769
* This is slightly fiddly, because we have
770
* to check whether this square is already
771
* part of the same equivalence class as
772
* the things it's joining.
774
int ae = dsf_canonify(dsf, (y/2)*w+(x/2));
776
for (b = 2; b < 0xD; b++)
777
if (workspace[y*W+x] & (1<<b)) {
779
* Find the equivalence classes of
780
* the two squares this one would
781
* connect if it were in this
786
for (d = 1; d <= 8; d += d) if (b & d) {
787
int xx = x/2 + DX(d), yy = y/2 + DY(d);
788
int ee = dsf_canonify(dsf, yy*w+xx);
798
* This square state would form
799
* a loop on equivalence class
800
* e. Measure the size of that
801
* loop, and see if it's a
804
int loopsize = dsfsize[e];
806
loopsize++;/* add the square itself */
807
if (loopsize < nonblanks) {
809
* It is! Mark this square
812
workspace[y*W+x] &= ~(1<<b);
813
done_something = TRUE;
814
#ifdef SOLVER_DIAGNOSTICS
815
printf("square (%d,%d) would create a "
816
"shortcut loop in state %d, "
832
* If we reach here, there is nothing left we can do.
833
* Return 2 for ambiguous puzzle.
842
* If ret = 1 then we've successfully achieved a solution. This
843
* means that we expect every square to be nailed down to
844
* exactly one possibility. If this is the case, or if the caller
845
* asked for a partial solution anyway, transcribe those
846
* possibilities into the result array.
848
if (ret == 1 || partial) {
849
for (y = 0; y < h; y++) {
850
for (x = 0; x < w; x++) {
851
for (b = 0; b < 0xD; b++)
852
if (workspace[(2*y+1)*W+(2*x+1)] == (1<<b)) {
856
if (ret == 1) assert(b < 0xD); /* we should have had a break by now */
868
/* ----------------------------------------------------------------------
873
* We use the loop generator code from loopy, hard-coding to a square
874
* grid of the appropriate size. Knowing the grid layout and the tile
875
* size we can shrink that to our small grid and then make our line
876
* layout from the face colour info.
878
* We provide a bias function to the loop generator which tries to
879
* bias in favour of loops with more scope for Pearl black clues. This
880
* seems to improve the success rate of the puzzle generator, in that
881
* such loops have a better chance of being soluble with all valid
885
struct pearl_loopgen_bias_ctx {
887
* Our bias function counts the number of 'black clue' corners
888
* (i.e. corners adjacent to two straights) in both the
889
* BLACK/nonBLACK and WHITE/nonWHITE boundaries. In order to do
892
* - track the edges that are part of each of those loops
893
* - track the types of vertex in each loop (corner, straight,
895
* - track the current black-clue status of each vertex in each
898
* Each of these chunks of data is updated incrementally from the
899
* previous one, to avoid slowdown due to the bias function
900
* rescanning the whole grid every time it's called.
902
* So we need a lot of separate arrays, plus a tdq for each one,
903
* and we must repeat it all twice for the BLACK and WHITE
906
struct pearl_loopgen_bias_ctx_boundary {
907
int colour; /* FACE_WHITE or FACE_BLACK */
909
char *edges; /* is each edge part of the loop? */
912
char *vertextypes; /* bits 0-3 == outgoing edge bitmap;
913
* bit 4 set iff corner clue.
914
* Hence, 0 means non-vertex;
915
* nonzero but bit 4 zero = straight. */
916
int *neighbour[2]; /* indices of neighbour vertices in loop */
917
tdq *vertextypes_todo;
919
char *blackclues; /* is each vertex a black clue site? */
920
tdq *blackclues_todo;
921
} boundaries[2]; /* boundaries[0]=WHITE, [1]=BLACK */
923
char *faces; /* remember last-seen colour of each face */
930
int pearl_loopgen_bias(void *vctx, char *board, int face)
932
struct pearl_loopgen_bias_ctx *ctx = (struct pearl_loopgen_bias_ctx *)vctx;
934
int oldface, newface;
937
tdq_add(ctx->faces_todo, face);
938
while ((j = tdq_remove(ctx->faces_todo)) >= 0) {
939
oldface = ctx->faces[j];
940
ctx->faces[j] = newface = board[j];
941
for (i = 0; i < 2; i++) {
942
struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i];
946
* If the face has changed either from or to colour c, we need
947
* to reprocess the edges for this boundary.
949
if (oldface == c || newface == c) {
950
grid_face *f = &g->faces[face];
951
for (k = 0; k < f->order; k++)
952
tdq_add(b->edges_todo, f->edges[k] - g->edges);
957
for (i = 0; i < 2; i++) {
958
struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i];
962
* Go through the to-do list of edges. For each edge, decide
963
* anew whether it's part of this boundary or not. Any edge
964
* that changes state has to have both its endpoints put on
965
* the vertextypes_todo list.
967
while ((j = tdq_remove(b->edges_todo)) >= 0) {
968
grid_edge *e = &g->edges[j];
969
int fc1 = e->face1 ? board[e->face1 - g->faces] : FACE_BLACK;
970
int fc2 = e->face2 ? board[e->face2 - g->faces] : FACE_BLACK;
971
int oldedge = b->edges[j];
972
int newedge = (fc1==c) ^ (fc2==c);
973
if (oldedge != newedge) {
974
b->edges[j] = newedge;
975
tdq_add(b->vertextypes_todo, e->dot1 - g->dots);
976
tdq_add(b->vertextypes_todo, e->dot2 - g->dots);
981
* Go through the to-do list of vertices whose types need
982
* refreshing. For each one, decide whether it's a corner, a
983
* straight, or a vertex not in the loop, and in the former
984
* two cases also work out the indices of its neighbour
985
* vertices along the loop. Any vertex that changes state must
986
* be put back on the to-do list for deciding if it's a black
987
* clue site, and so must its two new neighbours _and_ its two
990
while ((j = tdq_remove(b->vertextypes_todo)) >= 0) {
991
grid_dot *d = &g->dots[j];
992
int neighbours[2], type = 0, n = 0;
994
for (k = 0; k < d->order; k++) {
995
grid_edge *e = d->edges[k];
996
grid_dot *d2 = (e->dot1 == d ? e->dot2 : e->dot1);
997
/* dir == 0,1,2,3 for an edge going L,U,R,D */
998
int dir = (d->y == d2->y) + 2*(d->x+d->y > d2->x+d2->y);
999
int ei = e - g->edges;
1002
neighbours[n] = d2 - g->dots;
1008
* Decide if it's a corner, and set the corner flag if so.
1010
if (type != 0 && type != 0x5 && type != 0xA)
1013
if (type != b->vertextypes[j]) {
1015
* Recompute old neighbours, if any.
1017
if (b->vertextypes[j]) {
1018
tdq_add(b->blackclues_todo, b->neighbour[0][j]);
1019
tdq_add(b->blackclues_todo, b->neighbour[1][j]);
1022
* Recompute this vertex.
1024
tdq_add(b->blackclues_todo, j);
1025
b->vertextypes[j] = type;
1027
* Recompute new neighbours, if any.
1029
if (b->vertextypes[j]) {
1030
b->neighbour[0][j] = neighbours[0];
1031
b->neighbour[1][j] = neighbours[1];
1032
tdq_add(b->blackclues_todo, b->neighbour[0][j]);
1033
tdq_add(b->blackclues_todo, b->neighbour[1][j]);
1039
* Go through the list of vertices which we must check to see
1040
* if they're black clue sites. Each one is a black clue site
1041
* iff it is a corner and its loop neighbours are non-corners.
1042
* Adjust the running total of black clues we've counted.
1044
while ((j = tdq_remove(b->blackclues_todo)) >= 0) {
1045
ctx->score -= b->blackclues[j];
1046
b->blackclues[j] = ((b->vertextypes[j] & 0x10) &&
1047
!((b->vertextypes[b->neighbour[0][j]] |
1048
b->vertextypes[b->neighbour[1][j]])
1050
ctx->score += b->blackclues[j];
1057
void pearl_loopgen(int w, int h, char *lines, random_state *rs)
1059
grid *g = grid_new(GRID_SQUARE, w-1, h-1, NULL);
1060
char *board = snewn(g->num_faces, char);
1061
int i, s = g->tilesize;
1062
struct pearl_loopgen_bias_ctx biasctx;
1064
memset(lines, 0, w*h);
1067
* Initialise the context for the bias function. Initially we fill
1068
* all the to-do lists, so that the first call will scan
1069
* everything; thereafter the lists stay empty so we make
1070
* incremental changes.
1073
biasctx.faces = snewn(g->num_faces, char);
1074
biasctx.faces_todo = tdq_new(g->num_faces);
1075
tdq_fill(biasctx.faces_todo);
1077
memset(biasctx.faces, FACE_GREY, g->num_faces);
1078
for (i = 0; i < 2; i++) {
1079
biasctx.boundaries[i].edges = snewn(g->num_edges, char);
1080
memset(biasctx.boundaries[i].edges, 0, g->num_edges);
1081
biasctx.boundaries[i].edges_todo = tdq_new(g->num_edges);
1082
tdq_fill(biasctx.boundaries[i].edges_todo);
1083
biasctx.boundaries[i].vertextypes = snewn(g->num_dots, char);
1084
memset(biasctx.boundaries[i].vertextypes, 0, g->num_dots);
1085
biasctx.boundaries[i].neighbour[0] = snewn(g->num_dots, int);
1086
biasctx.boundaries[i].neighbour[1] = snewn(g->num_dots, int);
1087
biasctx.boundaries[i].vertextypes_todo = tdq_new(g->num_dots);
1088
tdq_fill(biasctx.boundaries[i].vertextypes_todo);
1089
biasctx.boundaries[i].blackclues = snewn(g->num_dots, char);
1090
memset(biasctx.boundaries[i].blackclues, 0, g->num_dots);
1091
biasctx.boundaries[i].blackclues_todo = tdq_new(g->num_dots);
1092
tdq_fill(biasctx.boundaries[i].blackclues_todo);
1094
biasctx.boundaries[0].colour = FACE_WHITE;
1095
biasctx.boundaries[1].colour = FACE_BLACK;
1096
generate_loop(g, board, rs, pearl_loopgen_bias, &biasctx);
1097
sfree(biasctx.faces);
1098
tdq_free(biasctx.faces_todo);
1099
for (i = 0; i < 2; i++) {
1100
sfree(biasctx.boundaries[i].edges);
1101
tdq_free(biasctx.boundaries[i].edges_todo);
1102
sfree(biasctx.boundaries[i].vertextypes);
1103
sfree(biasctx.boundaries[i].neighbour[0]);
1104
sfree(biasctx.boundaries[i].neighbour[1]);
1105
tdq_free(biasctx.boundaries[i].vertextypes_todo);
1106
sfree(biasctx.boundaries[i].blackclues);
1107
tdq_free(biasctx.boundaries[i].blackclues_todo);
1110
for (i = 0; i < g->num_edges; i++) {
1111
grid_edge *e = g->edges + i;
1112
enum face_colour c1 = FACE_COLOUR(e->face1);
1113
enum face_colour c2 = FACE_COLOUR(e->face2);
1114
assert(c1 != FACE_GREY);
1115
assert(c2 != FACE_GREY);
1117
/* This grid edge is on the loop: lay line along it */
1118
int x1 = e->dot1->x/s, y1 = e->dot1->y/s;
1119
int x2 = e->dot2->x/s, y2 = e->dot2->y/s;
1121
/* (x1,y1) and (x2,y2) are now in our grid coords (0-w,0-h). */
1123
if (y1 > y2) SWAP(y1,y2);
1126
lines[y1*w+x1] |= D;
1127
lines[y2*w+x1] |= U;
1128
} else if (y1 == y2) {
1129
if (x1 > x2) SWAP(x1,x2);
1132
lines[y1*w+x1] |= R;
1133
lines[y1*w+x2] |= L;
1135
assert(!"grid with diagonal coords?!");
1142
#if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
1143
printf("as returned:\n");
1144
for (y = 0; y < h; y++) {
1145
for (x = 0; x < w; x++) {
1146
int type = lines[y*w+x];
1148
if (type & L) *p++ = 'L';
1149
if (type & R) *p++ = 'R';
1150
if (type & U) *p++ = 'U';
1151
if (type & D) *p++ = 'D';
1161
static int new_clues(const game_params *params, random_state *rs,
1162
char *clues, char *grid)
1164
int w = params->w, h = params->h, diff = params->difficulty;
1165
int ngen = 0, x, y, d, ret, i;
1169
* Difficulty exception: 5x5 Tricky is not generable (the
1170
* generator will spin forever trying) and so we fudge it to Easy.
1172
if (w == 5 && h == 5 && diff > DIFF_EASY)
1177
pearl_loopgen(w, h, grid, rs);
1179
#ifdef GENERATION_DIAGNOSTICS
1180
printf("grid array:\n");
1181
for (y = 0; y < h; y++) {
1182
for (x = 0; x < w; x++) {
1183
int type = grid[y*w+x];
1185
if (type & L) *p++ = 'L';
1186
if (type & R) *p++ = 'R';
1187
if (type & U) *p++ = 'U';
1188
if (type & D) *p++ = 'D';
1198
* Set up the maximal clue array.
1200
for (y = 0; y < h; y++)
1201
for (x = 0; x < w; x++) {
1202
int type = grid[y*w+x];
1204
clues[y*w+x] = NOCLUE;
1206
if ((bLR|bUD) & (1 << type)) {
1208
* This is a straight; see if it's a viable
1209
* candidate for a straight clue. It qualifies if
1210
* at least one of the squares it connects to is a
1213
for (d = 1; d <= 8; d += d) if (type & d) {
1214
int xx = x + DX(d), yy = y + DY(d);
1215
assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
1216
if ((bLU|bLD|bRU|bRD) & (1 << grid[yy*w+xx]))
1219
if (d <= 8) /* we found one */
1220
clues[y*w+x] = STRAIGHT;
1221
} else if ((bLU|bLD|bRU|bRD) & (1 << type)) {
1223
* This is a corner; see if it's a viable candidate
1224
* for a corner clue. It qualifies if all the
1225
* squares it connects to are straights.
1227
for (d = 1; d <= 8; d += d) if (type & d) {
1228
int xx = x + DX(d), yy = y + DY(d);
1229
assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
1230
if (!((bLR|bUD) & (1 << grid[yy*w+xx])))
1233
if (d > 8) /* we didn't find a counterexample */
1234
clues[y*w+x] = CORNER;
1238
#ifdef GENERATION_DIAGNOSTICS
1239
printf("clue array:\n");
1240
for (y = 0; y < h; y++) {
1241
for (x = 0; x < w; x++) {
1242
printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
1249
if (!params->nosolve) {
1250
int *cluespace, *straights, *corners;
1251
int nstraights, ncorners, nstraightpos, ncornerpos;
1254
* See if we can solve the puzzle just like this.
1256
ret = pearl_solve(w, h, clues, grid, diff, FALSE);
1257
assert(ret > 0); /* shouldn't be inconsistent! */
1259
continue; /* go round and try again */
1262
* Check this puzzle isn't too easy.
1264
if (diff > DIFF_EASY) {
1265
ret = pearl_solve(w, h, clues, grid, diff-1, FALSE);
1268
continue; /* too easy: try again */
1272
* Now shuffle the grid points and gradually remove the
1273
* clues to find a minimal set which still leaves the
1276
* We preferentially attempt to remove whichever type of
1277
* clue is currently most numerous, to combat a general
1278
* tendency of plain random generation to bias in favour
1279
* of many white clues and few black.
1281
* 'nstraights' and 'ncorners' count the number of clues
1282
* of each type currently remaining in the grid;
1283
* 'nstraightpos' and 'ncornerpos' count the clues of each
1284
* type we have left to try to remove. (Clues which we
1285
* have tried and failed to remove are counted by the
1286
* former but not the latter.)
1288
cluespace = snewn(w*h, int);
1289
straights = cluespace;
1291
for (i = 0; i < w*h; i++)
1292
if (clues[i] == STRAIGHT)
1293
straights[nstraightpos++] = i;
1294
corners = straights + nstraightpos;
1296
for (i = 0; i < w*h; i++)
1297
if (clues[i] == STRAIGHT)
1298
corners[ncornerpos++] = i;
1299
nstraights = nstraightpos;
1300
ncorners = ncornerpos;
1302
shuffle(straights, nstraightpos, sizeof(*straights), rs);
1303
shuffle(corners, ncornerpos, sizeof(*corners), rs);
1304
while (nstraightpos > 0 || ncornerpos > 0) {
1309
* Decide which clue to try to remove next. If both
1310
* types are available, we choose whichever kind is
1311
* currently overrepresented; otherwise we take
1312
* whatever we can get.
1314
if (nstraightpos > 0 && ncornerpos > 0) {
1315
if (nstraights >= ncorners)
1316
cluepos = straights[--nstraightpos];
1318
cluepos = straights[--ncornerpos];
1320
if (nstraightpos > 0)
1321
cluepos = straights[--nstraightpos];
1323
cluepos = straights[--ncornerpos];
1329
clue = clues[y*w+x];
1330
clues[y*w+x] = 0; /* try removing this clue */
1332
ret = pearl_solve(w, h, clues, grid, diff, FALSE);
1335
clues[y*w+x] = clue; /* oops, put it back again */
1340
#ifdef FINISHED_PUZZLE
1341
printf("clue array:\n");
1342
for (y = 0; y < h; y++) {
1343
for (x = 0; x < w; x++) {
1344
printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
1354
debug(("%d %dx%d loops before finished puzzle.\n", ngen, w, h));
1359
static char *new_game_desc(const game_params *params, random_state *rs,
1360
char **aux, int interactive)
1364
int w = params->w, h = params->h, i, j;
1366
grid = snewn(w*h, char);
1367
clues = snewn(w*h, char);
1369
new_clues(params, rs, clues, grid);
1371
desc = snewn(w * h + 1, char);
1372
for (i = j = 0; i < w*h; i++) {
1373
if (clues[i] == NOCLUE && j > 0 &&
1374
desc[j-1] >= 'a' && desc[j-1] < 'z')
1376
else if (clues[i] == NOCLUE)
1378
else if (clues[i] == CORNER)
1380
else if (clues[i] == STRAIGHT)
1385
*aux = snewn(w*h+1, char);
1386
for (i = 0; i < w*h; i++)
1387
(*aux)[i] = (grid[i] < 10) ? (grid[i] + '0') : (grid[i] + 'A' - 10);
1396
static char *validate_desc(const game_params *params, const char *desc)
1399
const int totalsize = params->w * params->h;
1402
for (i = 0; desc[i]; i++) {
1403
if (desc[i] >= 'a' && desc[i] <= 'z')
1404
sizesofar += desc[i] - 'a' + 1;
1405
else if (desc[i] == 'B' || desc[i] == 'W')
1408
return "unrecognised character in string";
1411
if (sizesofar > totalsize)
1412
return "string too long";
1413
else if (sizesofar < totalsize)
1414
return "string too short";
1419
static game_state *new_game(midend *me, const game_params *params,
1422
game_state *state = snew(game_state);
1423
int i, j, sz = params->w*params->h;
1425
state->completed = state->used_solve = FALSE;
1426
state->shared = snew(struct shared_state);
1428
state->shared->w = params->w;
1429
state->shared->h = params->h;
1430
state->shared->sz = sz;
1431
state->shared->refcnt = 1;
1432
state->shared->clues = snewn(sz, char);
1433
for (i = j = 0; desc[i]; i++) {
1435
if (desc[i] >= 'a' && desc[i] <= 'z') {
1436
int n = desc[i] - 'a' + 1;
1437
assert(j + n <= sz);
1439
state->shared->clues[j++] = NOCLUE;
1440
} else if (desc[i] == 'B') {
1441
state->shared->clues[j++] = CORNER;
1442
} else if (desc[i] == 'W') {
1443
state->shared->clues[j++] = STRAIGHT;
1447
state->lines = snewn(sz, char);
1448
state->errors = snewn(sz, char);
1449
state->marks = snewn(sz, char);
1450
for (i = 0; i < sz; i++)
1451
state->lines[i] = state->errors[i] = state->marks[i] = BLANK;
1456
static game_state *dup_game(const game_state *state)
1458
game_state *ret = snew(game_state);
1459
int sz = state->shared->sz, i;
1461
ret->shared = state->shared;
1462
ret->completed = state->completed;
1463
ret->used_solve = state->used_solve;
1464
++ret->shared->refcnt;
1466
ret->lines = snewn(sz, char);
1467
ret->errors = snewn(sz, char);
1468
ret->marks = snewn(sz, char);
1469
for (i = 0; i < sz; i++) {
1470
ret->lines[i] = state->lines[i];
1471
ret->errors[i] = state->errors[i];
1472
ret->marks[i] = state->marks[i];
1478
static void free_game(game_state *state)
1481
if (--state->shared->refcnt == 0) {
1482
sfree(state->shared->clues);
1483
sfree(state->shared);
1485
sfree(state->lines);
1486
sfree(state->errors);
1487
sfree(state->marks);
1491
static char nbits[16] = { 0, 1, 1, 2,
1495
#define NBITS(l) ( ((l) < 0 || (l) > 15) ? 4 : nbits[l] )
1497
#define ERROR_CLUE 16
1499
static void dsf_update_completion(game_state *state, int *loopclass,
1500
int ax, int ay, char dir,
1501
int *dsf, int *dsfsize)
1503
int w = state->shared->w /*, h = state->shared->h */;
1504
int ac = ay*w+ax, ae, bx, by, bc, be;
1506
if (!(state->lines[ac] & dir)) return; /* no link */
1507
bx = ax + DX(dir); by = ay + DY(dir);
1509
assert(INGRID(state, bx, by)); /* should not have a link off grid */
1513
assert(state->lines[bc] & F(dir)); /* should have reciprocal link */
1515
/* TODO put above assertion back in once we stop generating partially
1516
* soluble puzzles. */
1517
if (!(state->lines[bc] & F(dir))) return;
1519
ae = dsf_canonify(dsf, ac);
1520
be = dsf_canonify(dsf, bc);
1522
if (ae == be) { /* detected a loop! */
1523
if (*loopclass != -1) /* this is the second loop, doom. */
1527
int size = dsfsize[ae] + dsfsize[be];
1528
dsf_merge(dsf, ac, bc);
1529
ae = dsf_canonify(dsf, ac);
1535
static void check_completion(game_state *state, int mark)
1537
int w = state->shared->w, h = state->shared->h, x, y, i, d;
1538
int had_error = FALSE /*, is_complete = FALSE */, loopclass;
1542
for (i = 0; i < w*h; i++) {
1543
state->errors[i] = 0;
1547
#define ERROR(x,y,e) do { had_error = TRUE; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0)
1550
* First of all: we should have one single closed loop, passing through all clues.
1552
dsf = snewn(w*h, int);
1553
dsfsize = snewn(w*h, int);
1555
for (i = 0; i < w*h; i++) dsfsize[i] = 1;
1558
for (x = 0; x < w; x++) {
1559
for (y = 0; y < h; y++) {
1560
dsf_update_completion(state, &loopclass, x, y, R, dsf, dsfsize);
1561
dsf_update_completion(state, &loopclass, x, y, D, dsf, dsfsize);
1564
if (loopclass != -1) {
1565
/* We have a loop. Check all squares with lines on. */
1566
for (x = 0; x < w; x++) {
1567
for (y = 0; y < h; y++) {
1568
if (state->lines[y*w+x] == BLANK) {
1569
if (state->shared->clues[y*w+x] != NOCLUE) {
1570
/* the loop doesn't include this clue square! */
1571
ERROR(x, y, ERROR_CLUE);
1574
if (dsf_canonify(dsf, y*w+x) != loopclass) {
1575
/* these lines are not on the loop: mark them as error. */
1576
ERROR(x, y, state->lines[y*w+x]);
1584
* Second: check no clues are contradicted.
1587
for (x = 0; x < w; x++) {
1588
for (y = 0; y < h; y++) {
1589
int type = state->lines[y*w+x];
1591
* Check that no square has more than two line segments.
1593
if (NBITS(type) > 2) {
1597
* Check that no clues are contradicted. This code is similar to
1598
* the code that sets up the maximal clue array for any given
1601
if (state->shared->clues[y*w+x] == CORNER) {
1602
/* Supposed to be a corner: will find a contradiction if
1603
* it actually contains a straight line, or if it touches any
1605
if ((bLR|bUD) & (1 << type)) {
1606
ERROR(x,y,ERROR_CLUE); /* actually straight */
1608
for (d = 1; d <= 8; d += d) if (type & d) {
1609
int xx = x + DX(d), yy = y + DY(d);
1610
if (!INGRID(state, xx, yy)) {
1611
ERROR(x,y,d); /* leads off grid */
1613
if ((bLU|bLD|bRU|bRD) & (1 << state->lines[yy*w+xx])) {
1614
ERROR(x,y,ERROR_CLUE); /* touches corner */
1618
} else if (state->shared->clues[y*w+x] == STRAIGHT) {
1619
/* Supposed to be straight: will find a contradiction if
1620
* it actually contains a corner, or if it only touches
1621
* straight lines. */
1622
if ((bLU|bLD|bRU|bRD) & (1 << type)) {
1623
ERROR(x,y,ERROR_CLUE); /* actually a corner */
1626
for (d = 1; d <= 8; d += d) if (type & d) {
1627
int xx = x + DX(d), yy = y + DY(d);
1628
if (!INGRID(state, xx, yy)) {
1629
ERROR(x,y,d); /* leads off grid */
1631
if ((bLR|bUD) & (1 << state->lines[yy*w+xx]))
1632
i++; /* a straight */
1635
if (i >= 2 && NBITS(type) >= 2) {
1636
ERROR(x,y,ERROR_CLUE); /* everything touched is straight */
1641
if (!had_error && loopclass != -1) {
1642
state->completed = TRUE;
1643
state->loop_length = dsfsize[loopclass];
1652
/* completion check:
1654
* - no clues must be contradicted (highlight clue itself in error if so)
1655
* - if there is a closed loop it must include every line segment laid
1656
* - if there's a smaller closed loop then highlight whole loop as error
1657
* - no square must have more than 3 lines radiating from centre point
1658
* (highlight all lines in that square as error if so)
1661
static char *solve_for_diff(game_state *state, char *old_lines, char *new_lines)
1663
int w = state->shared->w, h = state->shared->h, i;
1664
char *move = snewn(w*h*40, char), *p = move;
1667
for (i = 0; i < w*h; i++) {
1668
if (old_lines[i] != new_lines[i]) {
1669
p += sprintf(p, ";R%d,%d,%d", new_lines[i], i%w, i/w);
1673
move = sresize(move, p - move, char);
1678
static char *solve_game(const game_state *state, const game_state *currstate,
1679
const char *aux, char **error)
1681
game_state *solved = dup_game(state);
1682
int i, ret, sz = state->shared->sz;
1686
for (i = 0; i < sz; i++) {
1687
if (aux[i] >= '0' && aux[i] <= '9')
1688
solved->lines[i] = aux[i] - '0';
1689
else if (aux[i] >= 'A' && aux[i] <= 'F')
1690
solved->lines[i] = aux[i] - 'A' + 10;
1692
*error = "invalid char in aux";
1699
/* Try to solve with present (half-solved) state first: if there's no
1700
* solution from there go back to original state. */
1701
ret = pearl_solve(currstate->shared->w, currstate->shared->h,
1702
currstate->shared->clues, solved->lines,
1705
ret = pearl_solve(state->shared->w, state->shared->h,
1706
state->shared->clues, solved->lines,
1712
*error = "Unable to find solution";
1715
move = solve_for_diff(solved, currstate->lines, solved->lines);
1723
static int game_can_format_as_text_now(const game_params *params)
1728
static char *game_text_format(const game_state *state)
1734
int *dragcoords; /* list of (y*w+x) coords in drag so far */
1735
int ndragcoords; /* number of entries in dragcoords.
1736
* 0 = click but no drag yet. -1 = no drag at all */
1737
int clickx, clicky; /* pixel position of initial click */
1739
int curx, cury; /* grid position of keyboard cursor */
1740
int cursor_active; /* TRUE iff cursor is shown */
1743
static game_ui *new_ui(const game_state *state)
1745
game_ui *ui = snew(game_ui);
1746
int sz = state->shared->sz;
1748
ui->ndragcoords = -1;
1749
ui->dragcoords = snewn(sz, int);
1750
ui->cursor_active = FALSE;
1751
ui->curx = ui->cury = 0;
1756
static void free_ui(game_ui *ui)
1758
sfree(ui->dragcoords);
1762
static char *encode_ui(const game_ui *ui)
1767
static void decode_ui(game_ui *ui, const char *encoding)
1771
static void game_changed_state(game_ui *ui, const game_state *oldstate,
1772
const game_state *newstate)
1776
#define PREFERRED_TILE_SIZE 31
1777
#define HALFSZ (ds->halfsz)
1778
#define TILE_SIZE (ds->halfsz*2 + 1)
1780
#define BORDER ((get_gui_style() == GUI_LOOPY) ? (TILE_SIZE/8) : (TILE_SIZE/2))
1782
#define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1784
#define COORD(x) ( (x) * TILE_SIZE + BORDER )
1785
#define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1786
#define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) )
1788
#define DS_ESHIFT 4 /* R/U/L/D shift, for error flags */
1789
#define DS_DSHIFT 8 /* R/U/L/D shift, for drag-in-progress flags */
1790
#define DS_MSHIFT 12 /* shift for no-line mark */
1792
#define DS_ERROR_CLUE (1 << 20)
1793
#define DS_FLASH (1 << 21)
1794
#define DS_CURSOR (1 << 22)
1796
enum { GUI_MASYU, GUI_LOOPY };
1798
static int get_gui_style(void)
1800
static int gui_style = -1;
1802
if (gui_style == -1) {
1803
char *env = getenv("PEARL_GUI_LOOPY");
1804
if (env && (env[0] == 'y' || env[0] == 'Y'))
1805
gui_style = GUI_LOOPY;
1807
gui_style = GUI_MASYU;
1812
struct game_drawstate {
1817
unsigned int *lflags; /* size w*h */
1819
char *draglines; /* size w*h; lines flipped by current drag */
1822
static void update_ui_drag(const game_state *state, game_ui *ui,
1825
int /* sz = state->shared->sz, */ w = state->shared->w;
1829
if (!INGRID(state, gx, gy))
1830
return; /* square is outside grid */
1832
if (ui->ndragcoords < 0)
1833
return; /* drag not in progress anyway */
1837
lastpos = ui->dragcoords[ui->ndragcoords > 0 ? ui->ndragcoords-1 : 0];
1839
return; /* same square as last visited one */
1841
/* Drag confirmed, if it wasn't already. */
1842
if (ui->ndragcoords == 0)
1843
ui->ndragcoords = 1;
1846
* Dragging the mouse into a square that's already been visited by
1847
* the drag path so far has the effect of truncating the path back
1848
* to that square, so a player can back out part of an uncommitted
1849
* drag without having to let go of the mouse.
1851
for (i = 0; i < ui->ndragcoords; i++)
1852
if (pos == ui->dragcoords[i]) {
1853
ui->ndragcoords = i+1;
1858
* Otherwise, dragging the mouse into a square that's a rook-move
1859
* away from the last one on the path extends the path.
1861
oy = ui->dragcoords[ui->ndragcoords-1] / w;
1862
ox = ui->dragcoords[ui->ndragcoords-1] % w;
1863
if (ox == gx || oy == gy) {
1864
int dx = (gx < ox ? -1 : gx > ox ? +1 : 0);
1865
int dy = (gy < oy ? -1 : gy > oy ? +1 : 0);
1866
int dir = (dy>0 ? D : dy<0 ? U : dx>0 ? R : L);
1867
while (ox != gx || oy != gy) {
1869
* If the drag attempts to cross a 'no line here' mark,
1870
* stop there. We physically don't allow the user to drag
1873
if (state->marks[oy*w+ox] & dir)
1877
ui->dragcoords[ui->ndragcoords++] = oy * w + ox;
1882
* Failing that, we do nothing at all: if the user has dragged
1883
* diagonally across the board, they'll just have to return the
1884
* mouse to the last known position and do whatever they meant to
1885
* do again, more slowly and clearly.
1890
* Routine shared between interpret_move and game_redraw to work out
1891
* the intended effect of a drag path on the grid.
1893
* Call it in a loop, like this:
1895
* int clearing = TRUE;
1896
* for (i = 0; i < ui->ndragcoords - 1; i++) {
1897
* int sx, sy, dx, dy, dir, oldstate, newstate;
1898
* interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
1899
* &dir, &oldstate, &newstate);
1901
* [do whatever is needed to handle the fact that the drag
1902
* wants the edge from sx,sy to dx,dy (heading in direction
1903
* 'dir' at the sx,sy end) to be changed from state oldstate
1904
* to state newstate, each of which equals either 0 or dir]
1907
static void interpret_ui_drag(const game_state *state, const game_ui *ui,
1908
int *clearing, int i, int *sx, int *sy,
1909
int *dx, int *dy, int *dir,
1910
int *oldstate, int *newstate)
1912
int w = state->shared->w;
1913
int sp = ui->dragcoords[i], dp = ui->dragcoords[i+1];
1918
*dir = (*dy>*sy ? D : *dy<*sy ? U : *dx>*sx ? R : L);
1919
*oldstate = state->lines[sp] & *dir;
1922
* The edge we've dragged over was previously
1923
* present. Set it to absent, unless we've already
1924
* stopped doing that.
1926
*newstate = *clearing ? 0 : *dir;
1929
* The edge we've dragged over was previously
1930
* absent. Set it to present, and cancel the
1931
* 'clearing' flag so that all subsequent edges in
1932
* the drag are set rather than cleared.
1939
static char *mark_in_direction(const game_state *state, int x, int y, int dir,
1940
int ismark, char *buf)
1942
int w = state->shared->w /*, h = state->shared->h, sz = state->shared->sz */;
1943
int x2 = x + DX(dir);
1944
int y2 = y + DY(dir);
1946
char ch = ismark ? 'M' : 'F';
1948
if (!INGRID(state, x, y) || !INGRID(state, x2, y2)) return "";
1949
/* disallow laying a mark over a line, or vice versa. */
1951
if ((state->lines[y*w+x] & dir) || (state->lines[y2*w+x2] & dir2))
1954
if ((state->marks[y*w+x] & dir) || (state->marks[y2*w+x2] & dir2))
1958
sprintf(buf, "%c%d,%d,%d;%c%d,%d,%d", ch, dir, x, y, ch, dir2, x2, y2);
1962
#define KEY_DIRECTION(btn) (\
1963
(btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
1964
(btn) == CURSOR_LEFT ? L : R)
1966
static char *interpret_move(const game_state *state, game_ui *ui,
1967
const game_drawstate *ds,
1968
int x, int y, int button)
1970
int w = state->shared->w, h = state->shared->h /*, sz = state->shared->sz */;
1971
int gx = FROMCOORD(x), gy = FROMCOORD(y), i;
1972
int release = FALSE;
1975
if (IS_MOUSE_DOWN(button)) {
1976
ui->cursor_active = FALSE;
1978
if (!INGRID(state, gx, gy)) {
1979
ui->ndragcoords = -1;
1983
ui->clickx = x; ui->clicky = y;
1984
ui->dragcoords[0] = gy * w + gx;
1985
ui->ndragcoords = 0; /* will be 1 once drag is confirmed */
1990
if (button == LEFT_DRAG && ui->ndragcoords >= 0) {
1991
update_ui_drag(state, ui, gx, gy);
1995
if (IS_MOUSE_RELEASE(button)) release = TRUE;
1997
if (IS_CURSOR_MOVE(button & ~MOD_MASK)) {
1998
if (!ui->cursor_active) {
1999
ui->cursor_active = TRUE;
2000
} else if (button & (MOD_SHFT | MOD_CTRL)) {
2001
if (ui->ndragcoords > 0) return NULL;
2002
ui->ndragcoords = -1;
2003
return mark_in_direction(state, ui->curx, ui->cury,
2004
KEY_DIRECTION(button & ~MOD_MASK),
2005
(button & MOD_SHFT), tmpbuf);
2007
move_cursor(button, &ui->curx, &ui->cury, w, h, FALSE);
2008
if (ui->ndragcoords >= 0)
2009
update_ui_drag(state, ui, ui->curx, ui->cury);
2014
if (IS_CURSOR_SELECT(button & ~MOD_MASK)) {
2015
if (!ui->cursor_active) {
2016
ui->cursor_active = TRUE;
2018
} else if (button == CURSOR_SELECT) {
2019
if (ui->ndragcoords == -1) {
2020
ui->ndragcoords = 0;
2021
ui->dragcoords[0] = ui->cury * w + ui->curx;
2022
ui->clickx = CENTERED_COORD(ui->curx);
2023
ui->clicky = CENTERED_COORD(ui->cury);
2025
} else release = TRUE;
2026
} else if (button == CURSOR_SELECT2 && ui->ndragcoords >= 0) {
2027
ui->ndragcoords = -1;
2033
if (ui->ndragcoords > 0) {
2034
/* End of a drag: process the cached line data. */
2035
int buflen = 0, bufsize = 256, tmplen;
2037
const char *sep = "";
2038
int clearing = TRUE;
2040
for (i = 0; i < ui->ndragcoords - 1; i++) {
2041
int sx, sy, dx, dy, dir, oldstate, newstate;
2042
interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
2043
&dir, &oldstate, &newstate);
2045
if (oldstate != newstate) {
2046
if (!buf) buf = snewn(bufsize, char);
2047
tmplen = sprintf(tmpbuf, "%sF%d,%d,%d;F%d,%d,%d", sep,
2048
dir, sx, sy, F(dir), dx, dy);
2049
if (buflen + tmplen >= bufsize) {
2050
bufsize = (buflen + tmplen) * 5 / 4 + 256;
2051
buf = sresize(buf, bufsize, char);
2053
strcpy(buf + buflen, tmpbuf);
2059
ui->ndragcoords = -1;
2061
return buf ? buf : "";
2062
} else if (ui->ndragcoords == 0) {
2063
/* Click (or tiny drag). Work out which edge we were
2067
ui->ndragcoords = -1;
2070
* We process clicks based on the mouse-down location,
2071
* because that's more natural for a user to carefully
2072
* control than the mouse-up.
2079
cx = CENTERED_COORD(gx);
2080
cy = CENTERED_COORD(gy);
2082
if (!INGRID(state, gx, gy)) return "";
2084
if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
2085
/* TODO closer to centre of grid: process as a cell click not an edge click. */
2090
if (abs(x-cx) < abs(y-cy)) {
2091
/* Closest to top/bottom edge. */
2092
direction = (y < cy) ? U : D;
2094
/* Closest to left/right edge. */
2095
direction = (x < cx) ? L : R;
2097
return mark_in_direction(state, gx, gy, direction,
2098
(button == RIGHT_RELEASE), tmpbuf);
2103
if (button == 'H' || button == 'h')
2109
static game_state *execute_move(const game_state *state, const char *move)
2111
int w = state->shared->w, h = state->shared->h;
2114
game_state *ret = dup_game(state);
2116
debug(("move: %s\n", move));
2121
ret->used_solve = TRUE;
2123
} else if (c == 'L' || c == 'N' || c == 'R' || c == 'F' || c == 'M') {
2124
/* 'line' or 'noline' or 'replace' or 'flip' or 'mark' */
2126
if (sscanf(move, "%d,%d,%d%n", &l, &x, &y, &n) != 3)
2128
if (!INGRID(state, x, y)) goto badmove;
2129
if (l < 0 || l > 15) goto badmove;
2132
ret->lines[y*w + x] |= (char)l;
2134
ret->lines[y*w + x] &= ~((char)l);
2135
else if (c == 'R') {
2136
ret->lines[y*w + x] = (char)l;
2137
ret->marks[y*w + x] &= ~((char)l); /* erase marks too */
2138
} else if (c == 'F')
2139
ret->lines[y*w + x] ^= (char)l;
2141
ret->marks[y*w + x] ^= (char)l;
2144
* If we ended up trying to lay a line _over_ a mark,
2145
* that's a failed move: interpret_move() should have
2146
* ensured we never received a move string like that in
2149
if ((ret->lines[y*w + x] & (char)l) &&
2150
(ret->marks[y*w + x] & (char)l))
2154
} else if (strcmp(move, "H") == 0) {
2155
pearl_solve(ret->shared->w, ret->shared->h,
2156
ret->shared->clues, ret->lines, DIFFCOUNT, TRUE);
2157
for (n = 0; n < w*h; n++)
2158
ret->marks[n] &= ~ret->lines[n]; /* erase marks too */
2169
check_completion(ret, TRUE);
2178
/* ----------------------------------------------------------------------
2182
#define FLASH_TIME 0.5F
2184
static void game_compute_size(const game_params *params, int tilesize,
2187
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
2188
struct { int halfsz; } ads, *ds = &ads;
2189
ads.halfsz = (tilesize-1)/2;
2191
*x = (params->w) * TILE_SIZE + 2 * BORDER;
2192
*y = (params->h) * TILE_SIZE + 2 * BORDER;
2195
static void game_set_size(drawing *dr, game_drawstate *ds,
2196
const game_params *params, int tilesize)
2198
ds->halfsz = (tilesize-1)/2;
2201
static float *game_colours(frontend *fe, int *ncolours)
2203
float *ret = snewn(3 * NCOLOURS, float);
2206
game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2208
for (i = 0; i < 3; i++) {
2209
ret[COL_BLACK * 3 + i] = 0.0F;
2210
ret[COL_WHITE * 3 + i] = 1.0F;
2211
ret[COL_GRID * 3 + i] = 0.4F;
2214
ret[COL_ERROR * 3 + 0] = 1.0F;
2215
ret[COL_ERROR * 3 + 1] = 0.0F;
2216
ret[COL_ERROR * 3 + 2] = 0.0F;
2218
ret[COL_DRAGON * 3 + 0] = 0.0F;
2219
ret[COL_DRAGON * 3 + 1] = 0.0F;
2220
ret[COL_DRAGON * 3 + 2] = 1.0F;
2222
ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2223
ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2224
ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2226
ret[COL_FLASH * 3 + 0] = 1.0F;
2227
ret[COL_FLASH * 3 + 1] = 1.0F;
2228
ret[COL_FLASH * 3 + 2] = 1.0F;
2230
*ncolours = NCOLOURS;
2235
static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2237
struct game_drawstate *ds = snew(struct game_drawstate);
2241
ds->started = FALSE;
2243
ds->w = state->shared->w;
2244
ds->h = state->shared->h;
2245
ds->sz = state->shared->sz;
2246
ds->lflags = snewn(ds->sz, unsigned int);
2247
for (i = 0; i < ds->sz; i++)
2250
ds->draglines = snewn(ds->sz, char);
2255
static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2257
sfree(ds->draglines);
2262
static void draw_lines_specific(drawing *dr, game_drawstate *ds,
2263
int x, int y, unsigned int lflags,
2264
unsigned int shift, int c)
2266
int ox = COORD(x), oy = COORD(y);
2267
int t2 = HALFSZ, t16 = HALFSZ/4;
2268
int cx = ox + t2, cy = oy + t2;
2271
/* Draw each of the four directions, where laid (or error, or drag, etc.) */
2272
for (d = 1; d < 16; d *= 2) {
2273
int xoff = t2 * DX(d), yoff = t2 * DY(d);
2274
int xnudge = abs(t16 * DX(C(d))), ynudge = abs(t16 * DY(C(d)));
2276
if ((lflags >> shift) & d) {
2277
int lx = cx + ((xoff < 0) ? xoff : 0) - xnudge;
2278
int ly = cy + ((yoff < 0) ? yoff : 0) - ynudge;
2280
if (c == COL_DRAGOFF && !(lflags & d))
2282
if (c == COL_DRAGON && (lflags & d))
2285
draw_rect(dr, lx, ly,
2286
abs(xoff)+2*xnudge+1,
2287
abs(yoff)+2*ynudge+1, c);
2289
draw_rect(dr, cx - t16, cy - t16, 2*t16+1, 2*t16+1, c);
2294
static void draw_square(drawing *dr, game_drawstate *ds, const game_ui *ui,
2295
int x, int y, unsigned int lflags, char clue)
2297
int ox = COORD(x), oy = COORD(y);
2298
int t2 = HALFSZ, t16 = HALFSZ/4;
2299
int cx = ox + t2, cy = oy + t2;
2304
/* Clip to the grid square. */
2305
clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2307
/* Clear the square. */
2308
draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
2309
(lflags & DS_CURSOR) ?
2310
COL_CURSOR_BACKGROUND : COL_BACKGROUND);
2313
if (get_gui_style() == GUI_LOOPY) {
2314
/* Draw small dot, underneath any lines. */
2315
draw_circle(dr, cx, cy, t16, COL_GRID, COL_GRID);
2317
/* Draw outline of grid square */
2318
draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID);
2319
draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID);
2322
/* Draw grid: either thin gridlines, or no-line marks.
2323
* We draw these first because the thick laid lines should be on top. */
2324
for (d = 1; d < 16; d *= 2) {
2325
int xoff = t2 * DX(d), yoff = t2 * DY(d);
2327
if ((x == 0 && d == L) ||
2328
(y == 0 && d == U) ||
2329
(x == ds->w-1 && d == R) ||
2330
(y == ds->h-1 && d == D))
2331
continue; /* no gridlines out to the border. */
2333
if ((lflags >> DS_MSHIFT) & d) {
2334
/* either a no-line mark ... */
2335
int mx = cx + xoff, my = cy + yoff, msz = t16;
2337
draw_line(dr, mx-msz, my-msz, mx+msz, my+msz, COL_BLACK);
2338
draw_line(dr, mx-msz, my+msz, mx+msz, my-msz, COL_BLACK);
2340
if (get_gui_style() == GUI_LOOPY) {
2341
/* draw grid lines connecting centre of cells */
2342
draw_line(dr, cx, cy, cx+xoff, cy+yoff, COL_GRID);
2347
/* Draw each of the four directions, where laid (or error, or drag, etc.)
2348
* Order is important here, specifically for the eventual colours of the
2349
* exposed end caps. */
2350
draw_lines_specific(dr, ds, x, y, lflags, 0,
2351
(lflags & DS_FLASH ? COL_FLASH : COL_BLACK));
2352
draw_lines_specific(dr, ds, x, y, lflags, DS_ESHIFT, COL_ERROR);
2353
draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGOFF);
2354
draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGON);
2356
/* Draw a clue, if present */
2357
if (clue != NOCLUE) {
2358
int c = (lflags & DS_FLASH) ? COL_FLASH :
2359
(clue == STRAIGHT) ? COL_WHITE : COL_BLACK;
2361
if (lflags & DS_ERROR_CLUE) /* draw a bigger 'error' clue circle. */
2362
draw_circle(dr, cx, cy, TILE_SIZE*3/8, COL_ERROR, COL_ERROR);
2364
draw_circle(dr, cx, cy, TILE_SIZE/4, c, COL_BLACK);
2368
draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2371
static void game_redraw(drawing *dr, game_drawstate *ds,
2372
const game_state *oldstate, const game_state *state,
2373
int dir, const game_ui *ui,
2374
float animtime, float flashtime)
2376
int w = state->shared->w, h = state->shared->h, sz = state->shared->sz;
2377
int x, y, force = 0, flashing = 0;
2381
* The initial contents of the window are not guaranteed and
2382
* can vary with front ends. To be on the safe side, all games
2383
* should start by drawing a big background-colour rectangle
2384
* covering the whole window.
2386
draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
2389
if (get_gui_style() == GUI_MASYU) {
2391
* Smaller black rectangle which is the main grid.
2393
draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
2394
w*TILE_SIZE + 2*BORDER_WIDTH + 1,
2395
h*TILE_SIZE + 2*BORDER_WIDTH + 1,
2399
draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
2405
if (flashtime > 0 &&
2406
(flashtime <= FLASH_TIME/3 ||
2407
flashtime >= FLASH_TIME*2/3))
2408
flashing = DS_FLASH;
2410
memset(ds->draglines, 0, sz);
2411
if (ui->ndragcoords > 0) {
2412
int i, clearing = TRUE;
2413
for (i = 0; i < ui->ndragcoords - 1; i++) {
2414
int sx, sy, dx, dy, dir, oldstate, newstate;
2415
interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
2416
&dir, &oldstate, &newstate);
2417
ds->draglines[sy*w+sx] ^= (oldstate ^ newstate);
2418
ds->draglines[dy*w+dx] ^= (F(oldstate) ^ F(newstate));
2422
for (x = 0; x < w; x++) {
2423
for (y = 0; y < h; y++) {
2424
unsigned int f = (unsigned int)state->lines[y*w+x];
2425
unsigned int eline = (unsigned int)(state->errors[y*w+x] & (R|U|L|D));
2427
f |= eline << DS_ESHIFT;
2428
f |= ((unsigned int)ds->draglines[y*w+x]) << DS_DSHIFT;
2429
f |= ((unsigned int)state->marks[y*w+x]) << DS_MSHIFT;
2431
if (state->errors[y*w+x] & ERROR_CLUE)
2436
if (ui->cursor_active && x == ui->curx && y == ui->cury)
2439
if (f != ds->lflags[y*w+x] || force) {
2440
ds->lflags[y*w+x] = f;
2441
draw_square(dr, ds, ui, x, y, f, state->shared->clues[y*w+x]);
2447
static float game_anim_length(const game_state *oldstate,
2448
const game_state *newstate, int dir, game_ui *ui)
2453
static float game_flash_length(const game_state *oldstate,
2454
const game_state *newstate, int dir, game_ui *ui)
2456
if (!oldstate->completed && newstate->completed &&
2457
!oldstate->used_solve && !newstate->used_solve)
2463
static int game_status(const game_state *state)
2465
return state->completed ? +1 : 0;
2468
static int game_timing_state(const game_state *state, game_ui *ui)
2473
static void game_print_size(const game_params *params, float *x, float *y)
2478
* I'll use 6mm squares by default.
2480
game_compute_size(params, 600, &pw, &ph);
2485
static void game_print(drawing *dr, const game_state *state, int tilesize)
2487
int w = state->shared->w, h = state->shared->h, x, y;
2488
int black = print_mono_colour(dr, 0);
2489
int white = print_mono_colour(dr, 1);
2491
/* No GUI_LOOPY here: only use the familiar masyu style. */
2493
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
2494
game_drawstate *ds = game_new_drawstate(dr, state);
2495
game_set_size(dr, ds, NULL, tilesize);
2497
/* Draw grid outlines (black). */
2498
for (x = 0; x <= w; x++)
2499
draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black);
2500
for (y = 0; y <= h; y++)
2501
draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black);
2503
for (x = 0; x < w; x++) {
2504
for (y = 0; y < h; y++) {
2505
int cx = COORD(x) + HALFSZ, cy = COORD(y) + HALFSZ;
2506
int clue = state->shared->clues[y*w+x];
2508
draw_lines_specific(dr, ds, x, y, state->lines[y*w+x], 0, black);
2510
if (clue != NOCLUE) {
2511
int c = (clue == CORNER) ? black : white;
2512
draw_circle(dr, cx, cy, TILE_SIZE/4, c, black);
2517
game_free_drawstate(dr, ds);
2521
#define thegame pearl
2524
const struct game thegame = {
2525
"Pearl", "games.pearl", "pearl",
2532
TRUE, game_configure, custom_params,
2540
FALSE, game_can_format_as_text_now, game_text_format,
2548
PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2551
game_free_drawstate,
2556
TRUE, FALSE, game_print_size, game_print,
2557
FALSE, /* wants_statusbar */
2558
FALSE, game_timing_state,
2562
#ifdef STANDALONE_SOLVER
2567
const char *quis = NULL;
2569
static void usage(FILE *out) {
2570
fprintf(out, "usage: %s <params>\n", quis);
2573
static void pnum(int n, int ntot, const char *desc)
2575
printf("%2.1f%% (%d) %s", (double)n*100.0 / (double)ntot, n, desc);
2578
static void start_soak(game_params *p, random_state *rs, int nsecs)
2580
time_t tt_start, tt_now, tt_last;
2581
int n = 0, nsolved = 0, nimpossible = 0, ret;
2584
tt_start = tt_last = time(NULL);
2586
/* Currently this generates puzzles of any difficulty (trying to solve it
2587
* on the maximum difficulty level and not checking it's not too easy). */
2588
printf("Soak-testing a %dx%d grid (any difficulty)", p->w, p->h);
2589
if (nsecs > 0) printf(" for %d seconds", nsecs);
2594
grid = snewn(p->w*p->h, char);
2595
clues = snewn(p->w*p->h, char);
2598
n += new_clues(p, rs, clues, grid); /* should be 1, with nosolve */
2600
ret = pearl_solve(p->w, p->h, clues, grid, DIFF_TRICKY, FALSE);
2601
if (ret <= 0) nimpossible++;
2602
if (ret == 1) nsolved++;
2604
tt_now = time(NULL);
2605
if (tt_now > tt_last) {
2608
printf("%d total, %3.1f/s, ",
2609
n, (double)n / ((double)tt_now - tt_start));
2610
pnum(nsolved, n, "solved"); printf(", ");
2611
printf("%3.1f/s", (double)nsolved / ((double)tt_now - tt_start));
2612
if (nimpossible > 0)
2613
pnum(nimpossible, n, "impossible");
2616
if (nsecs > 0 && (tt_now - tt_start) > nsecs) {
2626
int main(int argc, const char *argv[])
2628
game_params *p = NULL;
2629
random_state *rs = NULL;
2630
time_t seed = time(NULL);
2631
char *id = NULL, *err;
2633
setvbuf(stdout, NULL, _IONBF, 0);
2637
while (--argc > 0) {
2638
char *p = (char*)(*++argv);
2639
if (!strcmp(p, "-e") || !strcmp(p, "--seed")) {
2640
seed = atoi(*++argv);
2642
} else if (*p == '-') {
2643
fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2651
rs = random_new((void*)&seed, sizeof(time_t));
2652
p = default_params();
2655
if (strchr(id, ':')) {
2656
fprintf(stderr, "soak takes params only.\n");
2660
decode_params(p, id);
2661
err = validate_params(p, 1);
2663
fprintf(stderr, "%s: %s", argv[0], err);
2667
start_soak(p, rs, 0); /* run forever */
2671
for (i = 5; i <= 12; i++) {
2673
start_soak(p, rs, 5);
2686
/* vim: set shiftwidth=4 tabstop=8: */
added
removed
.pc/102_fix-pearl-min-dimensions.diff/pearl.c
