2 * pearl.c: Nikoli's `Masyu' puzzle. Currently this is a blank
3 * puzzle file with nothing but a test solver-generator.
9 * - The generation method appears to be fundamentally flawed. I
10 * think generating a random loop and then choosing a clue set
11 * is simply not a viable approach, because on a test run of
12 * 10,000 attempts, it generated _six_ viable puzzles. All the
13 * rest of the randomly generated loops failed to be soluble
14 * even given a maximal clue set. Also, the vast majority of the
15 * clues were white circles (straight clues); black circles
16 * (corners) seem very uncommon.
17 * + So what can we do? One possible approach would be to
18 * adjust the random loop generation so that it created loops
19 * which were in some heuristic sense more likely to be
20 * viable Masyu puzzles. Certainly a good start on that would
21 * be to arrange that black clues actually _came up_ slightly
22 * more often, but I have no idea whether that would be
24 * + A second option would be to throw the entire mechanism out
25 * and instead write a different generator from scratch which
26 * evolves the solution along with the puzzle: place a few
27 * clues, nail down a bit of the loop, place another clue,
28 * nail down some more, etc. It's unclear whether this can
29 * sensibly be done, though.
31 * - Puzzle playing UI and everything else apart from the
53 #define DX(d) ( ((d)==R) - ((d)==L) )
54 #define DY(d) ( ((d)==D) - ((d)==U) )
56 #define F(d) (((d << 2) | (d >> 2)) & 0xF)
57 #define C(d) (((d << 3) | (d >> 1)) & 0xF)
58 #define A(d) (((d << 1) | (d >> 3)) & 0xF)
87 #define bBLANK (1 << BLANK)
102 static game_params
*default_params(void)
104 game_params
*ret
= snew(game_params
);
111 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
116 static void free_params(game_params
*params
)
121 static game_params
*dup_params(game_params
*params
)
123 game_params
*ret
= snew(game_params
);
124 *ret
= *params
; /* structure copy */
128 static void decode_params(game_params
*params
, char const *string
)
132 static char *encode_params(game_params
*params
, int full
)
134 return dupstr("FIXME");
137 static config_item
*game_configure(game_params
*params
)
142 static game_params
*custom_params(config_item
*cfg
)
147 static char *validate_params(game_params
*params
, int full
)
152 /* ----------------------------------------------------------------------
156 int pearl_solve(int w
, int h
, char *clues
, char *result
)
158 int W
= 2*w
+1, H
= 2*h
+1;
165 * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature
166 * of the square (x,y), as a logical OR of bitfields.
168 * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates
169 * whether the horizontal edge between (x,y) and (x+1,y) is
170 * connected (1), disconnected (2) or unknown (3).
172 * workspace[(2*y+1)*W+(2*x)], indicates the same about the
173 * vertical edge between (x,y) and (x,y+1).
175 * Initially, every square is considered capable of being in
176 * any of the seven possible states (two straights, four
177 * corners and empty), except those corresponding to clue
178 * squares which are more restricted.
180 * Initially, all edges are unknown, except the ones around the
181 * grid border which are known to be disconnected.
183 workspace
= snewn(W
*H
, short);
184 for (x
= 0; x
< W
*H
; x
++)
187 for (y
= 0; y
< h
; y
++)
188 for (x
= 0; x
< w
; x
++)
189 switch (clues
[y
*w
+x
]) {
191 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLU
|bLD
|bRU
|bRD
;
194 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLR
|bUD
;
197 workspace
[(2*y
+1)*W
+(2*x
+1)] = bLR
|bUD
|bLU
|bLD
|bRU
|bRD
|bBLANK
;
200 /* Horizontal edges */
201 for (y
= 0; y
<= h
; y
++)
202 for (x
= 0; x
< w
; x
++)
203 workspace
[(2*y
)*W
+(2*x
+1)] = (y
==0 || y
==h ?
2 : 3);
205 for (y
= 0; y
< h
; y
++)
206 for (x
= 0; x
<= w
; x
++)
207 workspace
[(2*y
+1)*W
+(2*x
)] = (x
==0 || x
==w ?
2 : 3);
210 * We maintain a dsf of connected squares, together with a
211 * count of the size of each equivalence class.
213 dsf
= snewn(w
*h
, int);
214 dsfsize
= snewn(w
*h
, int);
217 * Now repeatedly try to find something we can do.
220 int done_something
= FALSE
;
222 #ifdef SOLVER_DIAGNOSTICS
223 for (y
= 0; y
< H
; y
++) {
224 for (x
= 0; x
< W
; x
++)
225 printf("%*x", (x
&1) ?
5 : 2, workspace
[y
*W
+x
]);
231 * Go through the square state words, and discard any
232 * square state which is inconsistent with known facts
233 * about the edges around the square.
235 for (y
= 0; y
< h
; y
++)
236 for (x
= 0; x
< w
; x
++) {
237 for (b
= 0; b
< 0xD; b
++)
238 if (workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<b
)) {
240 * If any edge of this square is known to
241 * be connected when state b would require
242 * it disconnected, or vice versa, discard
245 for (d
= 1; d
<= 8; d
+= d
) {
246 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
247 if (workspace
[ey
*W
+ex
] ==
249 workspace
[(2*y
+1)*W
+(2*x
+1)] &= ~(1<<b
);
250 #ifdef SOLVER_DIAGNOSTICS
251 printf("edge (%d,%d)-(%d,%d) rules out state"
252 " %d for square (%d,%d)\n",
253 ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2,
256 done_something
= TRUE
;
263 * Consistency check: each square must have at
264 * least one state left!
266 if (!workspace
[(2*y
+1)*W
+(2*x
+1)]) {
267 #ifdef SOLVER_DIAGNOSTICS
268 printf("edge check at (%d,%d): inconsistency\n", x
, y
);
276 * Now go through the states array again, and nail down any
277 * unknown edge if one of its neighbouring squares makes it
280 for (y
= 0; y
< h
; y
++)
281 for (x
= 0; x
< w
; x
++) {
282 int edgeor
= 0, edgeand
= 15;
284 for (b
= 0; b
< 0xD; b
++)
285 if (workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<b
)) {
291 * Now any bit clear in edgeor marks a disconnected
292 * edge, and any bit set in edgeand marks a
296 /* First check consistency: neither bit is both! */
297 if (edgeand
& ~edgeor
) {
298 #ifdef SOLVER_DIAGNOSTICS
299 printf("square check at (%d,%d): inconsistency\n", x
, y
);
305 for (d
= 1; d
<= 8; d
+= d
) {
306 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
308 if (!(edgeor
& d
) && workspace
[ey
*W
+ex
] == 3) {
309 workspace
[ey
*W
+ex
] = 2;
310 done_something
= TRUE
;
311 #ifdef SOLVER_DIAGNOSTICS
312 printf("possible states of square (%d,%d) force edge"
313 " (%d,%d)-(%d,%d) to be disconnected\n",
314 x
, y
, ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
316 } else if ((edgeand
& d
) && workspace
[ey
*W
+ex
] == 3) {
317 workspace
[ey
*W
+ex
] = 1;
318 done_something
= TRUE
;
319 #ifdef SOLVER_DIAGNOSTICS
320 printf("possible states of square (%d,%d) force edge"
321 " (%d,%d)-(%d,%d) to be connected\n",
322 x
, y
, ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
332 * Now for longer-range clue-based deductions (using the
333 * rules that a corner clue must connect to two straight
334 * squares, and a straight clue must connect to at least
335 * one corner square).
337 for (y
= 0; y
< h
; y
++)
338 for (x
= 0; x
< w
; x
++)
339 switch (clues
[y
*w
+x
]) {
341 for (d
= 1; d
<= 8; d
+= d
) {
342 int ex
= 2*x
+1 + DX(d
), ey
= 2*y
+1 + DY(d
);
343 int fx
= ex
+ DX(d
), fy
= ey
+ DY(d
);
346 if (workspace
[ey
*W
+ex
] == 1) {
348 * If a corner clue is connected on any
349 * edge, then we can immediately nail
350 * down the square beyond that edge as
351 * being a straight in the appropriate
354 if (workspace
[fy
*W
+fx
] != (1<<type
)) {
355 workspace
[fy
*W
+fx
] = (1<<type
);
356 done_something
= TRUE
;
357 #ifdef SOLVER_DIAGNOSTICS
358 printf("corner clue at (%d,%d) forces square "
359 "(%d,%d) into state %d\n", x
, y
,
364 } else if (workspace
[ey
*W
+ex
] == 3) {
366 * Conversely, if a corner clue is
367 * separated by an unknown edge from a
368 * square which _cannot_ be a straight
369 * in the appropriate direction, we can
370 * mark that edge as disconnected.
372 if (!(workspace
[fy
*W
+fx
] & (1<<type
))) {
373 workspace
[ey
*W
+ex
] = 2;
374 done_something
= TRUE
;
375 #ifdef SOLVER_DIAGNOSTICS
376 printf("corner clue at (%d,%d), plus square "
377 "(%d,%d) not being state %d, "
378 "disconnects edge (%d,%d)-(%d,%d)\n",
379 x
, y
, fx
/2, fy
/2, type
,
380 ex
/2, ey
/2, (ex
+1)/2, (ey
+1)/2);
390 * If a straight clue is between two squares
391 * neither of which is capable of being a
392 * corner connected to it, then the straight
393 * clue cannot point in that direction.
395 for (d
= 1; d
<= 2; d
+= d
) {
396 int fx
= 2*x
+1 + 2*DX(d
), fy
= 2*y
+1 + 2*DY(d
);
397 int gx
= 2*x
+1 - 2*DX(d
), gy
= 2*y
+1 - 2*DY(d
);
400 if (!(workspace
[(2*y
+1)*W
+(2*x
+1)] & (1<<type
)))
403 if (!(workspace
[fy
*W
+fx
] & ((1<<(F(d
)|A(d
))) |
404 (1<<(F(d
)|C(d
))))) &&
405 !(workspace
[gy
*W
+gx
] & ((1<<( d
|A(d
))) |
407 workspace
[(2*y
+1)*W
+(2*x
+1)] &= ~(1<<type
);
408 done_something
= TRUE
;
409 #ifdef SOLVER_DIAGNOSTICS
410 printf("straight clue at (%d,%d) cannot corner at "
411 "(%d,%d) or (%d,%d) so is not state %d\n",
412 x
, y
, fx
/2, fy
/2, gx
/2, gy
/2, type
);
419 * If a straight clue with known direction is
420 * connected on one side to a known straight,
421 * then on the other side it must be a corner.
423 for (d
= 1; d
<= 8; d
+= d
) {
424 int fx
= 2*x
+1 + 2*DX(d
), fy
= 2*y
+1 + 2*DY(d
);
425 int gx
= 2*x
+1 - 2*DX(d
), gy
= 2*y
+1 - 2*DY(d
);
428 if (workspace
[(2*y
+1)*W
+(2*x
+1)] != (1<<type
))
431 if (!(workspace
[fy
*W
+fx
] &~ (bLR
|bUD
)) &&
432 (workspace
[gy
*W
+gx
] &~ (bLU
|bLD
|bRU
|bRD
))) {
433 workspace
[gy
*W
+gx
] &= (bLU
|bLD
|bRU
|bRD
);
434 done_something
= TRUE
;
435 #ifdef SOLVER_DIAGNOSTICS
436 printf("straight clue at (%d,%d) connecting to "
437 "straight at (%d,%d) makes (%d,%d) a "
438 "corner\n", x
, y
, fx
/2, fy
/2, gx
/2, gy
/2);
450 * Now detect shortcut loops.
454 int nonblanks
, loopclass
;
457 for (x
= 0; x
< w
*h
; x
++)
461 * First go through the edge entries and update the dsf
462 * of which squares are connected to which others. We
463 * also track the number of squares in each equivalence
464 * class, and count the overall number of
465 * known-non-blank squares.
467 * In the process of doing this, we must notice if a
468 * loop has already been formed. If it has, we blank
469 * out any square which isn't part of that loop
470 * (failing a consistency check if any such square does
471 * not have BLANK as one of its remaining options) and
472 * exit the deduction loop with success.
476 for (y
= 1; y
< H
-1; y
++)
477 for (x
= 1; x
< W
-1; x
++)
480 * (x,y) are the workspace coordinates of
481 * an edge field. Compute the normal-space
482 * coordinates of the squares it connects.
484 int ax
= (x
-1)/2, ay
= (y
-1)/2, ac
= ay
*w
+ax
;
485 int bx
= x
/2, by
= y
/2, bc
= by
*w
+bx
;
488 * If the edge is connected, do the dsf
491 if (workspace
[y
*W
+x
] == 1) {
494 ae
= dsf_canonify(dsf
, ac
);
495 be
= dsf_canonify(dsf
, bc
);
501 if (loopclass
!= -1) {
503 * In fact, we have two
504 * separate loops, which is
507 #ifdef SOLVER_DIAGNOSTICS
508 printf("two loops found in grid!\n");
516 * Merge the two equivalence
519 int size
= dsfsize
[ae
] + dsfsize
[be
];
520 dsf_merge(dsf
, ac
, bc
);
521 ae
= dsf_canonify(dsf
, ac
);
525 } else if ((y
& x
) & 1) {
527 * (x,y) are the workspace coordinates of a
528 * square field. If the square is
529 * definitely not blank, count it.
531 if (!(workspace
[y
*W
+x
] & bBLANK
))
536 * If we discovered an existing loop above, we must now
537 * blank every square not part of it, and exit the main
540 if (loopclass
!= -1) {
541 #ifdef SOLVER_DIAGNOSTICS
542 printf("loop found in grid!\n");
544 for (y
= 0; y
< h
; y
++)
545 for (x
= 0; x
< w
; x
++)
546 if (dsf_canonify(dsf
, y
*w
+x
) != loopclass
) {
547 if (workspace
[(y
*2+1)*W
+(x
*2+1)] & bBLANK
) {
548 workspace
[(y
*2+1)*W
+(x
*2+1)] = bBLANK
;
551 * This square is not part of the
552 * loop, but is known non-blank. We
555 #ifdef SOLVER_DIAGNOSTICS
556 printf("non-blank square (%d,%d) found outside"
571 * Now go through the workspace again and mark any edge
572 * which would cause a shortcut loop (i.e. would
573 * connect together two squares in the same equivalence
574 * class, and that equivalence class does not contain
575 * _all_ the known-non-blank squares currently in the
576 * grid) as disconnected. Also, mark any _square state_
577 * which would cause a shortcut loop as disconnected.
579 for (y
= 1; y
< H
-1; y
++)
580 for (x
= 1; x
< W
-1; x
++)
583 * (x,y) are the workspace coordinates of
584 * an edge field. Compute the normal-space
585 * coordinates of the squares it connects.
587 int ax
= (x
-1)/2, ay
= (y
-1)/2, ac
= ay
*w
+ax
;
588 int bx
= x
/2, by
= y
/2, bc
= by
*w
+bx
;
591 * If the edge is currently unknown, and
592 * sits between two squares in the same
593 * equivalence class, and the size of that
594 * class is less than nonblanks, then
595 * connecting this edge would be a shortcut
596 * loop and so we must not do so.
598 if (workspace
[y
*W
+x
] == 3) {
601 ae
= dsf_canonify(dsf
, ac
);
602 be
= dsf_canonify(dsf
, bc
);
606 * We have a loop. Is it a shortcut?
608 if (dsfsize
[ae
] < nonblanks
) {
610 * Yes! Mark this edge disconnected.
612 workspace
[y
*W
+x
] = 2;
613 done_something
= TRUE
;
614 #ifdef SOLVER_DIAGNOSTICS
615 printf("edge (%d,%d)-(%d,%d) would create"
616 " a shortcut loop, hence must be"
617 " disconnected\n", x
/2, y
/2,
623 } else if ((y
& x
) & 1) {
625 * (x,y) are the workspace coordinates of a
626 * square field. Go through its possible
627 * (non-blank) states and see if any gives
628 * rise to a shortcut loop.
630 * This is slightly fiddly, because we have
631 * to check whether this square is already
632 * part of the same equivalence class as
633 * the things it's joining.
635 int ae
= dsf_canonify(dsf
, (y
/2)*w
+(x
/2));
637 for (b
= 2; b
< 0xD; b
++)
638 if (workspace
[y
*W
+x
] & (1<<b
)) {
640 * Find the equivalence classes of
641 * the two squares this one would
642 * connect if it were in this
647 for (d
= 1; d
<= 8; d
+= d
) if (b
& d
) {
648 int xx
= x
/2 + DX(d
), yy
= y
/2 + DY(d
);
649 int ee
= dsf_canonify(dsf
, yy
*w
+xx
);
659 * This square state would form
660 * a loop on equivalence class
661 * e. Measure the size of that
662 * loop, and see if it's a
665 int loopsize
= dsfsize
[e
];
667 loopsize
++;/* add the square itself */
668 if (loopsize
< nonblanks
) {
670 * It is! Mark this square
673 workspace
[y
*W
+x
] &= ~(1<<b
);
674 done_something
= TRUE
;
675 #ifdef SOLVER_DIAGNOSTICS
676 printf("square (%d,%d) would create a "
677 "shortcut loop in state %d, "
691 * If we reach here, there is nothing left we can do.
692 * Return 2 for ambiguous puzzle.
699 * If we reach _here_, it's by `break' out of the main loop,
700 * which means we've successfully achieved a solution. This
701 * means that we expect every square to be nailed down to
702 * exactly one possibility. Transcribe those possibilities into
705 for (y
= 0; y
< h
; y
++)
706 for (x
= 0; x
< w
; x
++) {
707 for (b
= 0; b
< 0xD; b
++)
708 if (workspace
[(2*y
+1)*W
+(2*x
+1)] == (1<<b
)) {
712 assert(b
< 0xD); /* we should have had a break by now */
723 /* ----------------------------------------------------------------------
727 void pearl_loopgen(int w
, int h
, char *grid
, random_state
*rs
)
729 int *options
, *mindist
, *maxdist
, *list
;
730 int x
, y
, d
, total
, n
, area
, limit
;
733 * We're eventually going to have to return a w-by-h array
734 * containing line segment data. However, it's more convenient
735 * while actually generating the loop to consider the problem
736 * as a (w-1) by (h-1) array in which some squares are `inside'
737 * and some `outside'.
739 * I'm going to use the top left corner of my return array in
740 * the latter manner until the end of the function.
744 * To begin with, all squares are outside (0), except for one
745 * randomly selected one which is inside (1).
747 memset(grid
, 0, w
*h
);
748 x
= random_upto(rs
, w
-1);
749 y
= random_upto(rs
, h
-1);
753 * I'm also going to need an array to store the possible
754 * options for the next extension of the grid.
756 options
= snewn(w
*h
, int);
757 for (x
= 0; x
< w
*h
; x
++)
761 * And some arrays and a list for breadth-first searching.
763 mindist
= snewn(w
*h
, int);
764 maxdist
= snewn(w
*h
, int);
765 list
= snewn(w
*h
, int);
768 * Now we repeatedly scan the grid for feasible squares into
769 * which we can extend our loop, pick one, and do it.
774 #ifdef LOOPGEN_DIAGNOSTICS
775 for (y
= 0; y
< h
; y
++) {
776 for (x
= 0; x
< w
; x
++)
777 printf("%d", grid
[y
*w
+x
]);
784 * Our primary aim in growing this loop is to make it
785 * reasonably _dense_ in the target rectangle. That is, we
786 * want the maximum over all squares of the minimum
787 * distance from that square to the loop to be small.
789 * Therefore, we start with a breadth-first search of the
790 * grid to find those minimum distances.
793 int head
= 0, tail
= 0;
796 for (i
= 0; i
< w
*h
; i
++) {
804 while (head
< tail
) {
808 for (d
= 1; d
<= 8; d
+= d
) {
809 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
810 if (xx
>= 0 && xx
< w
&& yy
>= 0 && yy
< h
&&
811 mindist
[yy
*w
+xx
] < 0) {
812 mindist
[yy
*w
+xx
] = mindist
[i
] + 1;
813 list
[tail
++] = yy
*w
+xx
;
819 * Having done the BFS, we now backtrack along its path
820 * to determine the most distant square that each
821 * square is on the shortest path to. This tells us
822 * which of the loop extension candidates (all of which
823 * are squares marked 1) is most desirable to extend
824 * into in terms of minimising the maximum distance
825 * from any empty square to the nearest loop square.
827 for (head
= tail
; head
-- > 0 ;) {
836 for (d
= 1; d
<= 8; d
+= d
) {
837 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
838 if (xx
>= 0 && xx
< w
&& yy
>= 0 && yy
< h
&&
839 mindist
[yy
*w
+xx
] > mindist
[i
] &&
840 maxdist
[yy
*w
+xx
] > max
) {
841 max
= maxdist
[yy
*w
+xx
];
850 * A square is a viable candidate for extension of our loop
851 * if and only if the following conditions are all met:
852 * - It is currently labelled 0.
853 * - At least one of its four orthogonal neighbours is
855 * - If you consider its eight orthogonal and diagonal
856 * neighbours to form a ring, that ring contains at most
857 * one contiguous run of 1s. (It must also contain at
858 * _least_ one, of course, but that's already guaranteed
859 * by the previous condition so there's no need to test
863 for (y
= 0; y
< h
-1; y
++)
864 for (x
= 0; x
< w
-1; x
++) {
866 int rx
, neighbours
, runs
, dist
;
868 dist
= maxdist
[y
*w
+x
];
872 continue; /* it isn't labelled 0 */
875 for (rx
= 0, d
= 1; d
<= 8; rx
+= 2, d
+= d
) {
876 int x2
= x
+ DX(d
), y2
= y
+ DY(d
);
877 int x3
= x2
+ DX(A(d
)), y3
= y2
+ DY(A(d
));
878 int g2
= (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h ?
880 int g3
= (x3
>= 0 && x3
< w
&& y3
>= 0 && y3
< h ?
889 continue; /* it doesn't have a 1 neighbour */
892 for (rx
= 0; rx
< 8; rx
++)
893 if (ring
[rx
] && !ring
[(rx
+1) & 7])
897 continue; /* too many runs of 1s */
900 * Now we know this square is a viable extension
901 * candidate. Mark it.
903 * FIXME: probabilistic prioritisation based on
904 * perimeter perturbation? (Wow, must keep that
907 options
[y
*w
+x
] = dist
* (4-neighbours
) * (4-neighbours
);
908 total
+= options
[y
*w
+x
];
912 break; /* nowhere to go! */
915 * Now pick a random one of the viable extension squares,
916 * and extend into it.
918 n
= random_upto(rs
, total
);
919 for (y
= 0; y
< h
-1; y
++)
920 for (x
= 0; x
< w
-1; x
++) {
922 if (options
[y
*w
+x
] > n
)
923 goto found
; /* two-level break */
926 assert(!"We shouldn't ever get here");
932 * We terminate the loop when around 7/12 of the grid area
933 * is full, but we also require that the loop has reached
936 limit
= random_upto(rs
, (w
-1)*(h
-1)) + 13*(w
-1)*(h
-1);
937 if (24 * area
> limit
) {
938 int l
= FALSE
, r
= FALSE
, u
= FALSE
, d
= FALSE
;
939 for (x
= 0; x
< w
; x
++) {
945 for (y
= 0; y
< h
; y
++) {
951 if (l
&& r
&& u
&& d
)
961 #ifdef LOOPGEN_DIAGNOSTICS
962 printf("final loop:\n");
963 for (y
= 0; y
< h
; y
++) {
964 for (x
= 0; x
< w
; x
++)
965 printf("%d", grid
[y
*w
+x
]);
972 * Now convert this array of 0s and 1s into an array of path
975 for (y
= h
; y
-- > 0 ;) {
976 for (x
= w
; x
-- > 0 ;) {
978 * Examine the four grid squares of which (x,y) are in
979 * the bottom right, to determine the output for this
982 int ul
= (x
> 0 && y
> 0 ? grid
[(y
-1)*w
+(x
-1)] : 0);
983 int ur
= (y
> 0 ? grid
[(y
-1)*w
+x
] : 0);
984 int dl
= (x
> 0 ? grid
[y
*w
+(x
-1)] : 0);
985 int dr
= grid
[y
*w
+x
];
988 if (ul
!= ur
) type
|= U
;
989 if (dl
!= dr
) type
|= D
;
990 if (ul
!= dl
) type
|= L
;
991 if (ur
!= dr
) type
|= R
;
993 assert((bLR
|bUD
|bLU
|bLD
|bRU
|bRD
|bBLANK
) & (1 << type
));
1000 #if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
1001 printf("as returned:\n");
1002 for (y
= 0; y
< h
; y
++) {
1003 for (x
= 0; x
< w
; x
++) {
1004 int type
= grid
[y
*w
+x
];
1006 if (type
& L
) *p
++ = 'L';
1007 if (type
& R
) *p
++ = 'R';
1008 if (type
& U
) *p
++ = 'U';
1009 if (type
& D
) *p
++ = 'D';
1019 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1020 char **aux
, int interactive
)
1025 int x
, y
, d
, ret
, i
;
1028 clues
= snewn(7*7, char);
1036 "\0\0\2\0\0\0\0", 7*7);
1037 grid
= snewn(7*7, char);
1038 printf("%d\n", pearl_solve(7, 7, clues
, grid
));
1040 clues
= snewn(10*10, char);
1042 "\0\0\2\0\2\0\0\0\0\0"
1043 "\0\0\0\0\2\0\0\0\1\0"
1044 "\0\0\1\0\1\0\2\0\0\0"
1045 "\0\0\0\2\0\0\2\0\0\0"
1046 "\1\0\0\0\0\2\0\0\0\2"
1047 "\0\0\2\0\0\0\0\2\0\0"
1048 "\0\0\1\0\0\0\2\0\0\0"
1049 "\2\0\0\0\1\0\0\0\0\2"
1050 "\0\0\0\0\0\0\2\2\0\0"
1051 "\0\0\1\0\0\0\0\0\0\1", 10*10);
1052 grid
= snewn(10*10, char);
1053 printf("%d\n", pearl_solve(10, 10, clues
, grid
));
1055 clues
= snewn(10*10, char);
1057 "\0\0\0\0\0\0\1\0\0\0"
1058 "\0\1\0\1\2\0\0\0\0\2"
1059 "\0\0\0\0\0\0\0\0\0\1"
1060 "\2\0\0\1\2\2\1\0\0\0"
1061 "\1\0\0\0\0\0\0\1\0\0"
1062 "\0\0\2\0\0\0\0\0\0\2"
1063 "\0\0\0\2\1\2\1\0\0\2"
1064 "\2\0\0\0\0\0\0\0\0\0"
1065 "\2\0\0\0\0\1\1\0\2\0"
1066 "\0\0\0\2\0\0\0\0\0\0", 10*10);
1067 grid
= snewn(10*10, char);
1068 printf("%d\n", pearl_solve(10, 10, clues
, grid
));
1071 grid
= snewn(w
*h
, char);
1072 clues
= snewn(w
*h
, char);
1073 clueorder
= snewn(w
*h
, int);
1076 pearl_loopgen(w
, h
, grid
, rs
);
1078 #ifdef GENERATION_DIAGNOSTICS
1079 printf("grid array:\n");
1080 for (y
= 0; y
< h
; y
++) {
1081 for (x
= 0; x
< w
; x
++) {
1082 int type
= grid
[y
*w
+x
];
1084 if (type
& L
) *p
++ = 'L';
1085 if (type
& R
) *p
++ = 'R';
1086 if (type
& U
) *p
++ = 'U';
1087 if (type
& D
) *p
++ = 'D';
1097 * Set up the maximal clue array.
1099 for (y
= 0; y
< h
; y
++)
1100 for (x
= 0; x
< w
; x
++) {
1101 int type
= grid
[y
*w
+x
];
1103 clues
[y
*w
+x
] = NOCLUE
;
1105 if ((bLR
|bUD
) & (1 << type
)) {
1107 * This is a straight; see if it's a viable
1108 * candidate for a straight clue. It qualifies if
1109 * at least one of the squares it connects to is a
1112 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1113 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1114 assert(xx
>= 0 && xx
< w
&& yy
>= 0 && yy
< h
);
1115 if ((bLU
|bLD
|bRU
|bRD
) & (1 << grid
[yy
*w
+xx
]))
1118 if (d
<= 8) /* we found one */
1119 clues
[y
*w
+x
] = STRAIGHT
;
1120 } else if ((bLU
|bLD
|bRU
|bRD
) & (1 << type
)) {
1122 * This is a corner; see if it's a viable candidate
1123 * for a corner clue. It qualifies if all the
1124 * squares it connects to are straights.
1126 for (d
= 1; d
<= 8; d
+= d
) if (type
& d
) {
1127 int xx
= x
+ DX(d
), yy
= y
+ DY(d
);
1128 assert(xx
>= 0 && xx
< w
&& yy
>= 0 && yy
< h
);
1129 if (!((bLR
|bUD
) & (1 << grid
[yy
*w
+xx
])))
1132 if (d
> 8) /* we didn't find a counterexample */
1133 clues
[y
*w
+x
] = CORNER
;
1137 #ifdef GENERATION_DIAGNOSTICS
1138 printf("clue array:\n");
1139 for (y
= 0; y
< h
; y
++) {
1140 for (x
= 0; x
< w
; x
++) {
1141 printf("%c", " *O"[(unsigned char)clues
[y
*w
+x
]]);
1149 * See if we can solve the puzzle just like this.
1151 ret
= pearl_solve(w
, h
, clues
, grid
);
1152 assert(ret
> 0); /* shouldn't be inconsistent! */
1154 continue; /* go round and try again */
1157 * Now shuffle the grid points and gradually remove the
1158 * clues to find a minimal set which still leaves the
1161 for (i
= 0; i
< w
*h
; i
++)
1163 shuffle(clueorder
, w
*h
, sizeof(*clueorder
), rs
);
1164 for (i
= 0; i
< w
*h
; i
++) {
1167 y
= clueorder
[i
] / w
;
1168 x
= clueorder
[i
] % w
;
1170 if (clues
[y
*w
+x
] == 0)
1173 clue
= clues
[y
*w
+x
];
1174 clues
[y
*w
+x
] = 0; /* try removing this clue */
1176 ret
= pearl_solve(w
, h
, clues
, grid
);
1179 clues
[y
*w
+x
] = clue
; /* oops, put it back again */
1182 #ifdef FINISHED_PUZZLE
1183 printf("clue array:\n");
1184 for (y
= 0; y
< h
; y
++) {
1185 for (x
= 0; x
< w
; x
++) {
1186 printf("%c", " *O"[(unsigned char)clues
[y
*w
+x
]]);
1200 return dupstr("FIXME");
1203 static char *validate_desc(game_params
*params
, char *desc
)
1208 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1210 game_state
*state
= snew(game_state
);
1217 static game_state
*dup_game(game_state
*state
)
1219 game_state
*ret
= snew(game_state
);
1221 ret
->FIXME
= state
->FIXME
;
1226 static void free_game(game_state
*state
)
1231 static char *solve_game(game_state
*state
, game_state
*currstate
,
1232 char *aux
, char **error
)
1237 static int game_can_format_as_text_now(game_params
*params
)
1242 static char *game_text_format(game_state
*state
)
1247 static game_ui
*new_ui(game_state
*state
)
1252 static void free_ui(game_ui
*ui
)
1256 static char *encode_ui(game_ui
*ui
)
1261 static void decode_ui(game_ui
*ui
, char *encoding
)
1265 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1266 game_state
*newstate
)
1270 struct game_drawstate
{
1275 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1276 int x
, int y
, int button
)
1281 static game_state
*execute_move(game_state
*state
, char *move
)
1286 /* ----------------------------------------------------------------------
1290 static void game_compute_size(game_params
*params
, int tilesize
,
1293 *x
= *y
= 10 * tilesize
; /* FIXME */
1296 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1297 game_params
*params
, int tilesize
)
1299 ds
->tilesize
= tilesize
;
1302 static float *game_colours(frontend
*fe
, int *ncolours
)
1304 float *ret
= snewn(3 * NCOLOURS
, float);
1306 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1308 *ncolours
= NCOLOURS
;
1312 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1314 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1322 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1327 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1328 game_state
*state
, int dir
, game_ui
*ui
,
1329 float animtime
, float flashtime
)
1332 * The initial contents of the window are not guaranteed and
1333 * can vary with front ends. To be on the safe side, all games
1334 * should start by drawing a big background-colour rectangle
1335 * covering the whole window.
1337 draw_rect(dr
, 0, 0, 10*ds
->tilesize
, 10*ds
->tilesize
, COL_BACKGROUND
);
1340 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1341 int dir
, game_ui
*ui
)
1346 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1347 int dir
, game_ui
*ui
)
1352 static int game_status(game_state
*state
)
1357 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1362 static void game_print_size(game_params
*params
, float *x
, float *y
)
1366 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1371 #define thegame pearl
1374 const struct game thegame
= {
1375 "Pearl", NULL
, NULL
,
1382 FALSE
, game_configure
, custom_params
,
1390 FALSE
, game_can_format_as_text_now
, game_text_format
,
1398 20 /* FIXME */, game_compute_size
, game_set_size
,
1401 game_free_drawstate
,
1406 FALSE
, FALSE
, game_print_size
, game_print
,
1407 FALSE
, /* wants_statusbar */
1408 FALSE
, game_timing_state
,