~mdw / sgt / puzzles / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Changed my mind about midend_is_solved: I've now reprototyped it as
[sgt/puzzles] / unfinished / pearl.c
CommitLineData
f278dcf4 1/*
2 * pearl.c: Nikoli's `Masyu' puzzle. Currently this is a blank
3 * puzzle file with nothing but a test solver-generator.
4 */
5
6/*
7 * TODO:
8 *
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
23 * sufficient.
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.
30 *
31 * - Puzzle playing UI and everything else apart from the
32 * generator...
33 */
34
35#include <stdio.h>
36#include <stdlib.h>
37#include <string.h>
38#include <assert.h>
39#include <ctype.h>
40#include <math.h>
41
42#include "puzzles.h"
43
44#define NOCLUE 0
45#define CORNER 1
46#define STRAIGHT 2
47
48#define R 1
49#define U 2
50#define L 4
51#define D 8
52
53#define DX(d) ( ((d)==R) - ((d)==L) )
54#define DY(d) ( ((d)==D) - ((d)==U) )
55
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)
59
60#define LR (L | R)
61#define RL (R | L)
62#define UD (U | D)
63#define DU (D | U)
64#define LU (L | U)
65#define UL (U | L)
66#define LD (L | D)
67#define DL (D | L)
68#define RU (R | U)
69#define UR (U | R)
70#define RD (R | D)
71#define DR (D | R)
72#define BLANK 0
73#define UNKNOWN 15
74
75#define bLR (1 << LR)
76#define bRL (1 << RL)
77#define bUD (1 << UD)
78#define bDU (1 << DU)
79#define bLU (1 << LU)
80#define bUL (1 << UL)
81#define bLD (1 << LD)
82#define bDL (1 << DL)
83#define bRU (1 << RU)
84#define bUR (1 << UR)
85#define bRD (1 << RD)
86#define bDR (1 << DR)
87#define bBLANK (1 << BLANK)
88
89enum {
90 COL_BACKGROUND,
91 NCOLOURS
92};
93
94struct game_params {
95 int FIXME;
96};
97
98struct game_state {
99 int FIXME;
100};
101
102static game_params *default_params(void)
103{
104 game_params *ret = snew(game_params);
105
106 ret->FIXME = 0;
107
108 return ret;
109}
110
111static int game_fetch_preset(int i, char **name, game_params **params)
112{
113 return FALSE;
114}
115
116static void free_params(game_params *params)
117{
118 sfree(params);
119}
120
121static game_params *dup_params(game_params *params)
122{
123 game_params *ret = snew(game_params);
124 *ret = *params; /* structure copy */
125 return ret;
126}
127
128static void decode_params(game_params *params, char const *string)
129{
130}
131
132static char *encode_params(game_params *params, int full)
133{
134 return dupstr("FIXME");
135}
136
137static config_item *game_configure(game_params *params)
138{
139 return NULL;
140}
141
142static game_params *custom_params(config_item *cfg)
143{
144 return NULL;
145}
146
147static char *validate_params(game_params *params, int full)
148{
149 return NULL;
150}
151
152/* ----------------------------------------------------------------------
153 * Solver.
154 */
155
156int pearl_solve(int w, int h, char *clues, char *result)
157{
158 int W = 2*w+1, H = 2*h+1;
159 short *workspace;
160 int *dsf, *dsfsize;
161 int x, y, b, d;
162 int ret = -1;
163
164 /*
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.
167 *
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).
171 *
172 * workspace[(2*y+1)*W+(2*x)], indicates the same about the
173 * vertical edge between (x,y) and (x,y+1).
174 *
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.
179 *
180 * Initially, all edges are unknown, except the ones around the
181 * grid border which are known to be disconnected.
182 */
183 workspace = snewn(W*H, short);
184 for (x = 0; x < W*H; x++)
185 workspace[x] = 0;
186 /* Square states */
187 for (y = 0; y < h; y++)
188 for (x = 0; x < w; x++)
189 switch (clues[y*w+x]) {
190 case CORNER:
191 workspace[(2*y+1)*W+(2*x+1)] = bLU|bLD|bRU|bRD;
192 break;
193 case STRAIGHT:
194 workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD;
195 break;
196 default:
197 workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD|bLU|bLD|bRU|bRD|bBLANK;
198 break;
199 }
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);
204 /* Vertical edges */
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);
208
209 /*
210 * We maintain a dsf of connected squares, together with a
211 * count of the size of each equivalence class.
212 */
213 dsf = snewn(w*h, int);
214 dsfsize = snewn(w*h, int);
215
216 /*
217 * Now repeatedly try to find something we can do.
218 */
219 while (1) {
ffb5d90c 220 int done_something = FALSE;
f278dcf4 221
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]);
226 printf("\n");
227 }
228#endif
229
f278dcf4 230 /*
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.
234 */
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)) {
239 /*
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
243 * the state.
244 */
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] ==
248 ((b & d) ? 2 : 1)) {
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,
254 b, x, y);
255#endif
256 done_something = TRUE;
257 break;
258 }
259 }
260 }
261
262 /*
263 * Consistency check: each square must have at
264 * least one state left!
265 */
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);
ffb5d90c 269#endif
f278dcf4 270 ret = 0;
271 goto cleanup;
f278dcf4 272 }
273 }
274
275 /*
276 * Now go through the states array again, and nail down any
277 * unknown edge if one of its neighbouring squares makes it
278 * known.
279 */
280 for (y = 0; y < h; y++)
281 for (x = 0; x < w; x++) {
282 int edgeor = 0, edgeand = 15;
283
284 for (b = 0; b < 0xD; b++)
285 if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
286 edgeor |= b;
287 edgeand &= b;
288 }
289
290 /*
291 * Now any bit clear in edgeor marks a disconnected
292 * edge, and any bit set in edgeand marks a
293 * connected edge.
294 */
295
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);
ffb5d90c 300#endif
f278dcf4 301 ret = 0;
302 goto cleanup;
f278dcf4 303 }
304
305 for (d = 1; d <= 8; d += d) {
306 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
307
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);
315#endif
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);
323#endif
324 }
325 }
326 }
327
328 if (done_something)
329 continue;
330
331 /*
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).
336 */
337 for (y = 0; y < h; y++)
338 for (x = 0; x < w; x++)
339 switch (clues[y*w+x]) {
340 case CORNER:
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);
344 int type = d | F(d);
345
346 if (workspace[ey*W+ex] == 1) {
347 /*
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
352 * direction.
353 */
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,
360 fx/2, fy/2, type);
361#endif
362
363 }
364 } else if (workspace[ey*W+ex] == 3) {
365 /*
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.
371 */
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);
381#endif
382
383 }
384 }
385 }
386
f278dcf4 387 break;
388 case STRAIGHT:
389 /*
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.
394 */
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);
398 int type = d | F(d);
399
400 if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type)))
401 continue;
402
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))) |
406 (1<<( d |C(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);
413#endif
414 }
415
416 }
417
418 /*
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.
422 */
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);
426 int type = d | F(d);
427
428 if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type))
429 continue;
430
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);
439#endif
440 }
441
442 }
443 break;
444 }
445
446 if (done_something)
447 continue;
448
449 /*
450 * Now detect shortcut loops.
451 */
452
453 {
454 int nonblanks, loopclass;
455
456 dsf_init(dsf, w*h);
457 for (x = 0; x < w*h; x++)
458 dsfsize[x] = 1;
459
460 /*
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.
466 *
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.
473 */
474 nonblanks = 0;
475 loopclass = -1;
476 for (y = 1; y < H-1; y++)
477 for (x = 1; x < W-1; x++)
478 if ((y ^ x) & 1) {
479 /*
480 * (x,y) are the workspace coordinates of
481 * an edge field. Compute the normal-space
482 * coordinates of the squares it connects.
483 */
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;
486
487 /*
488 * If the edge is connected, do the dsf
489 * thing.
490 */
491 if (workspace[y*W+x] == 1) {
492 int ae, be;
493
494 ae = dsf_canonify(dsf, ac);
495 be = dsf_canonify(dsf, bc);
496
497 if (ae == be) {
498 /*
499 * We have a loop!
500 */
501 if (loopclass != -1) {
502 /*
503 * In fact, we have two
504 * separate loops, which is
505 * doom.
506 */
507#ifdef SOLVER_DIAGNOSTICS
508 printf("two loops found in grid!\n");
509#endif
510 ret = 0;
511 goto cleanup;
512 }
513 loopclass = ae;
514 } else {
515 /*
516 * Merge the two equivalence
517 * classes.
518 */
519 int size = dsfsize[ae] + dsfsize[be];
520 dsf_merge(dsf, ac, bc);
521 ae = dsf_canonify(dsf, ac);
522 dsfsize[ae] = size;
523 }
524 }
525 } else if ((y & x) & 1) {
526 /*
527 * (x,y) are the workspace coordinates of a
528 * square field. If the square is
529 * definitely not blank, count it.
530 */
531 if (!(workspace[y*W+x] & bBLANK))
532 nonblanks++;
533 }
534
535 /*
536 * If we discovered an existing loop above, we must now
537 * blank every square not part of it, and exit the main
538 * deduction loop.
539 */
540 if (loopclass != -1) {
541#ifdef SOLVER_DIAGNOSTICS
542 printf("loop found in grid!\n");
543#endif
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;
549 } else {
550 /*
551 * This square is not part of the
552 * loop, but is known non-blank. We
553 * have goofed.
554 */
555#ifdef SOLVER_DIAGNOSTICS
556 printf("non-blank square (%d,%d) found outside"
557 " loop!\n", x, y);
558#endif
559 ret = 0;
560 goto cleanup;
561 }
562 }
563 /*
564 * And we're done.
565 */
566 ret = 1;
567 break;
568 }
569
570 /*
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.
578 */
579 for (y = 1; y < H-1; y++)
580 for (x = 1; x < W-1; x++)
581 if ((y ^ x) & 1) {
582 /*
583 * (x,y) are the workspace coordinates of
584 * an edge field. Compute the normal-space
585 * coordinates of the squares it connects.
586 */
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;
589
590 /*
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.
597 */
598 if (workspace[y*W+x] == 3) {
599 int ae, be;
600
601 ae = dsf_canonify(dsf, ac);
602 be = dsf_canonify(dsf, bc);
603
604 if (ae == be) {
605 /*
606 * We have a loop. Is it a shortcut?
607 */
608 if (dsfsize[ae] < nonblanks) {
609 /*
610 * Yes! Mark this edge disconnected.
611 */
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,
618 (x+1)/2, (y+1)/2);
619#endif
620 }
621 }
622 }
623 } else if ((y & x) & 1) {
624 /*
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.
629 *
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.
634 */
635 int ae = dsf_canonify(dsf, (y/2)*w+(x/2));
636
637 for (b = 2; b < 0xD; b++)
638 if (workspace[y*W+x] & (1<<b)) {
639 /*
640 * Find the equivalence classes of
641 * the two squares this one would
642 * connect if it were in this
643 * state.
644 */
645 int e = -1;
646
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);
650
651 if (e == -1)
652 ee = e;
653 else if (e != ee)
654 e = -2;
655 }
656
657 if (e >= 0) {
658 /*
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
663 * shortcut.
664 */
665 int loopsize = dsfsize[e];
666 if (e != ae)
667 loopsize++;/* add the square itself */
668 if (loopsize < nonblanks) {
669 /*
670 * It is! Mark this square
671 * state invalid.
672 */
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, "
678 "hence cannot be\n",
679 x/2, y/2, b);
680#endif
681 }
682 }
683 }
684 }
685 }
686
687 if (done_something)
688 continue;
689
690 /*
691 * If we reach here, there is nothing left we can do.
692 * Return 2 for ambiguous puzzle.
693 */
694 ret = 2;
695 goto cleanup;
696 }
697
698 /*
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
703 * the result array.
704 */
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)) {
709 result[y*w+x] = b;
710 break;
711 }
712 assert(b < 0xD); /* we should have had a break by now */
713 }
714
715 cleanup:
716 sfree(dsfsize);
717 sfree(dsf);
718 sfree(workspace);
719 assert(ret >= 0);
720 return ret;
721}
722
723/* ----------------------------------------------------------------------
724 * Loop generator.
725 */
726
727void pearl_loopgen(int w, int h, char *grid, random_state *rs)
728{
729 int *options, *mindist, *maxdist, *list;
730 int x, y, d, total, n, area, limit;
731
732 /*
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'.
738 *
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.
741 */
742
743 /*
744 * To begin with, all squares are outside (0), except for one
745 * randomly selected one which is inside (1).
746 */
747 memset(grid, 0, w*h);
748 x = random_upto(rs, w-1);
749 y = random_upto(rs, h-1);
750 grid[y*w+x] = 1;
751
752 /*
753 * I'm also going to need an array to store the possible
754 * options for the next extension of the grid.
755 */
756 options = snewn(w*h, int);
757 for (x = 0; x < w*h; x++)
758 options[x] = 0;
759
760 /*
761 * And some arrays and a list for breadth-first searching.
762 */
763 mindist = snewn(w*h, int);
764 maxdist = snewn(w*h, int);
765 list = snewn(w*h, int);
766
767 /*
768 * Now we repeatedly scan the grid for feasible squares into
769 * which we can extend our loop, pick one, and do it.
770 */
771 area = 1;
772
773 while (1) {
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]);
778 printf("\n");
779 }
780 printf("\n");
781#endif
782
783 /*
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.
788 *
789 * Therefore, we start with a breadth-first search of the
790 * grid to find those minimum distances.
791 */
792 {
793 int head = 0, tail = 0;
794 int i;
795
796 for (i = 0; i < w*h; i++) {
797 mindist[i] = -1;
798 if (grid[i]) {
799 mindist[i] = 0;
800 list[tail++] = i;
801 }
802 }
803
804 while (head < tail) {
805 i = list[head++];
806 y = i / w;
807 x = i % w;
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;
814 }
815 }
816 }
817
818 /*
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.
826 */
827 for (head = tail; head-- > 0 ;) {
828 int max;
829
830 i = list[head];
831 y = i / w;
832 x = i % w;
833
834 max = mindist[i];
835
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];
842 }
843 }
844
845 maxdist[i] = max;
846 }
847 }
848
849 /*
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
854 * labelled 1.
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
860 * it separately.)
861 */
862 total = 0;
863 for (y = 0; y < h-1; y++)
864 for (x = 0; x < w-1; x++) {
865 int ring[8];
866 int rx, neighbours, runs, dist;
867
868 dist = maxdist[y*w+x];
869 options[y*w+x] = 0;
870
871 if (grid[y*w+x])
872 continue; /* it isn't labelled 0 */
873
874 neighbours = 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 ?
879 grid[y2*w+x2] : 0);
880 int g3 = (x3 >= 0 && x3 < w && y3 >= 0 && y3 < h ?
881 grid[y3*w+x3] : 0);
882 ring[rx] = g2;
883 ring[rx+1] = g3;
884 if (g2)
885 neighbours++;
886 }
887
888 if (!neighbours)
889 continue; /* it doesn't have a 1 neighbour */
890
891 runs = 0;
892 for (rx = 0; rx < 8; rx++)
893 if (ring[rx] && !ring[(rx+1) & 7])
894 runs++;
895
896 if (runs > 1)
897 continue; /* too many runs of 1s */
898
899 /*
900 * Now we know this square is a viable extension
901 * candidate. Mark it.
902 *
903 * FIXME: probabilistic prioritisation based on
904 * perimeter perturbation? (Wow, must keep that
905 * phrase.)
906 */
907 options[y*w+x] = dist * (4-neighbours) * (4-neighbours);
908 total += options[y*w+x];
909 }
910
911 if (!total)
912 break; /* nowhere to go! */
913
914 /*
915 * Now pick a random one of the viable extension squares,
916 * and extend into it.
917 */
918 n = random_upto(rs, total);
919 for (y = 0; y < h-1; y++)
920 for (x = 0; x < w-1; x++) {
921 assert(n >= 0);
922 if (options[y*w+x] > n)
923 goto found; /* two-level break */
924 n -= options[y*w+x];
925 }
926 assert(!"We shouldn't ever get here");
927 found:
928 grid[y*w+x] = 1;
929 area++;
930
931 /*
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
934 * all four edges.
935 */
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++) {
940 if (grid[0*w+x])
941 u = TRUE;
942 if (grid[(h-2)*w+x])
943 d = TRUE;
944 }
945 for (y = 0; y < h; y++) {
946 if (grid[y*w+0])
947 l = TRUE;
948 if (grid[y*w+(w-2)])
949 r = TRUE;
950 }
951 if (l && r && u && d)
952 break;
953 }
954 }
955
956 sfree(list);
957 sfree(maxdist);
958 sfree(mindist);
959 sfree(options);
960
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]);
966 printf("\n");
967 }
968 printf("\n");
969#endif
970
971 /*
972 * Now convert this array of 0s and 1s into an array of path
973 * components.
974 */
975 for (y = h; y-- > 0 ;) {
976 for (x = w; x-- > 0 ;) {
977 /*
978 * Examine the four grid squares of which (x,y) are in
979 * the bottom right, to determine the output for this
980 * square.
981 */
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];
986 int type = 0;
987
988 if (ul != ur) type |= U;
989 if (dl != dr) type |= D;
990 if (ul != dl) type |= L;
991 if (ur != dr) type |= R;
992
993 assert((bLR|bUD|bLU|bLD|bRU|bRD|bBLANK) & (1 << type));
994
995 grid[y*w+x] = type;
996
997 }
998 }
999
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];
1005 char s[5], *p = s;
1006 if (type & L) *p++ = 'L';
1007 if (type & R) *p++ = 'R';
1008 if (type & U) *p++ = 'U';
1009 if (type & D) *p++ = 'D';
1010 *p = '\0';
1011 printf("%3s", s);
1012 }
1013 printf("\n");
1014 }
1015 printf("\n");
1016#endif
1017}
1018
1019static char *new_game_desc(game_params *params, random_state *rs,
1020 char **aux, int interactive)
1021{
1022 char *grid, *clues;
1023 int *clueorder;
1024 int w = 10, h = 10;
1025 int x, y, d, ret, i;
1026
1027#if 0
1028 clues = snewn(7*7, char);
1029 memcpy(clues,
1030 "\0\1\0\0\2\0\0"
1031 "\0\0\0\2\0\0\0"
1032 "\0\0\0\2\0\0\1"
1033 "\2\0\0\2\0\0\0"
1034 "\2\0\0\0\0\0\1"
1035 "\0\0\1\0\0\2\0"
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));
1039#elif 0
1040 clues = snewn(10*10, char);
1041 memcpy(clues,
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));
1054#elif 0
1055 clues = snewn(10*10, char);
1056 memcpy(clues,
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));
1069#endif
1070
1071 grid = snewn(w*h, char);
1072 clues = snewn(w*h, char);
1073 clueorder = snewn(w*h, int);
1074
1075 while (1) {
1076 pearl_loopgen(w, h, grid, rs);
1077
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];
1083 char s[5], *p = s;
1084 if (type & L) *p++ = 'L';
1085 if (type & R) *p++ = 'R';
1086 if (type & U) *p++ = 'U';
1087 if (type & D) *p++ = 'D';
1088 *p = '\0';
1089 printf("%2s ", s);
1090 }
1091 printf("\n");
1092 }
1093 printf("\n");
1094#endif
1095
1096 /*
1097 * Set up the maximal clue array.
1098 */
1099 for (y = 0; y < h; y++)
1100 for (x = 0; x < w; x++) {
1101 int type = grid[y*w+x];
1102
1103 clues[y*w+x] = NOCLUE;
1104
1105 if ((bLR|bUD) & (1 << type)) {
1106 /*
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
1110 * corner.
1111 */
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]))
1116 break;
1117 }
1118 if (d <= 8) /* we found one */
1119 clues[y*w+x] = STRAIGHT;
1120 } else if ((bLU|bLD|bRU|bRD) & (1 << type)) {
1121 /*
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.
1125 */
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])))
1130 break;
1131 }
1132 if (d > 8) /* we didn't find a counterexample */
1133 clues[y*w+x] = CORNER;
1134 }
1135 }
1136
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]]);
1142 }
1143 printf("\n");
1144 }
1145 printf("\n");
1146#endif
1147
1148 /*
1149 * See if we can solve the puzzle just like this.
1150 */
1151 ret = pearl_solve(w, h, clues, grid);
1152 assert(ret > 0); /* shouldn't be inconsistent! */
1153 if (ret != 1)
1154 continue; /* go round and try again */
1155
1156 /*
1157 * Now shuffle the grid points and gradually remove the
1158 * clues to find a minimal set which still leaves the
1159 * puzzle soluble.
1160 */
1161 for (i = 0; i < w*h; i++)
1162 clueorder[i] = i;
1163 shuffle(clueorder, w*h, sizeof(*clueorder), rs);
1164 for (i = 0; i < w*h; i++) {
1165 int clue;
1166
1167 y = clueorder[i] / w;
1168 x = clueorder[i] % w;
1169
1170 if (clues[y*w+x] == 0)
1171 continue;
1172
1173 clue = clues[y*w+x];
1174 clues[y*w+x] = 0; /* try removing this clue */
1175
1176 ret = pearl_solve(w, h, clues, grid);
1177 assert(ret > 0);
1178 if (ret != 1)
1179 clues[y*w+x] = clue; /* oops, put it back again */
1180 }
1181
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]]);
1187 }
1188 printf("\n");
1189 }
1190 printf("\n");
1191#endif
1192
1193 break; /* got it */
1194 }
1195
1196 sfree(grid);
1197 sfree(clues);
1198 sfree(clueorder);
1199
1200 return dupstr("FIXME");
1201}
1202
1203static char *validate_desc(game_params *params, char *desc)
1204{
1205 return NULL;
1206}
1207
1208static game_state *new_game(midend *me, game_params *params, char *desc)
1209{
1210 game_state *state = snew(game_state);
1211
1212 state->FIXME = 0;
1213
1214 return state;
1215}
1216
1217static game_state *dup_game(game_state *state)
1218{
1219 game_state *ret = snew(game_state);
1220
1221 ret->FIXME = state->FIXME;
1222
1223 return ret;
1224}
1225
1226static void free_game(game_state *state)
1227{
1228 sfree(state);
1229}
1230
1231static char *solve_game(game_state *state, game_state *currstate,
1232 char *aux, char **error)
1233{
1234 return NULL;
1235}
1236
fa3abef5 1237static int game_can_format_as_text_now(game_params *params)
1238{
1239 return TRUE;
1240}
1241
f278dcf4 1242static char *game_text_format(game_state *state)
1243{
1244 return NULL;
1245}
1246
1247static game_ui *new_ui(game_state *state)
1248{
1249 return NULL;
1250}
1251
1252static void free_ui(game_ui *ui)
1253{
1254}
1255
1256static char *encode_ui(game_ui *ui)
1257{
1258 return NULL;
1259}
1260
1261static void decode_ui(game_ui *ui, char *encoding)
1262{
1263}
1264
1265static void game_changed_state(game_ui *ui, game_state *oldstate,
1266 game_state *newstate)
1267{
1268}
1269
1270struct game_drawstate {
1271 int tilesize;
1272 int FIXME;
1273};
1274
1275static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1276 int x, int y, int button)
1277{
1278 return NULL;
1279}
1280
1281static game_state *execute_move(game_state *state, char *move)
1282{
1283 return NULL;
1284}
1285
1286/* ----------------------------------------------------------------------
1287 * Drawing routines.
1288 */
1289
1290static void game_compute_size(game_params *params, int tilesize,
1291 int *x, int *y)
1292{
1293 *x = *y = 10 * tilesize; /* FIXME */
1294}
1295
1296static void game_set_size(drawing *dr, game_drawstate *ds,
1297 game_params *params, int tilesize)
1298{
1299 ds->tilesize = tilesize;
1300}
1301
1302static float *game_colours(frontend *fe, int *ncolours)
1303{
1304 float *ret = snewn(3 * NCOLOURS, float);
1305
1306 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1307
1308 *ncolours = NCOLOURS;
1309 return ret;
1310}
1311
1312static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1313{
1314 struct game_drawstate *ds = snew(struct game_drawstate);
1315
1316 ds->tilesize = 0;
1317 ds->FIXME = 0;
1318
1319 return ds;
1320}
1321
1322static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1323{
1324 sfree(ds);
1325}
1326
1327static 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)
1330{
1331 /*
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.
1336 */
1337 draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
1338}
1339
1340static float game_anim_length(game_state *oldstate, game_state *newstate,
1341 int dir, game_ui *ui)
1342{
1343 return 0.0F;
1344}
1345
1346static float game_flash_length(game_state *oldstate, game_state *newstate,
1347 int dir, game_ui *ui)
1348{
1349 return 0.0F;
1350}
1351
1cea529f 1352static int game_status(game_state *state)
4496362f 1353{
1cea529f 1354 return 0;
4496362f 1355}
1356
f278dcf4 1357static int game_timing_state(game_state *state, game_ui *ui)
1358{
1359 return TRUE;
1360}
1361
1362static void game_print_size(game_params *params, float *x, float *y)
1363{
1364}
1365
1366static void game_print(drawing *dr, game_state *state, int tilesize)
1367{
1368}
1369
1370#ifdef COMBINED
1371#define thegame pearl
1372#endif
1373
1374const struct game thegame = {
750037d7 1375 "Pearl", NULL, NULL,
f278dcf4 1376 default_params,
1377 game_fetch_preset,
1378 decode_params,
1379 encode_params,
1380 free_params,
1381 dup_params,
1382 FALSE, game_configure, custom_params,
1383 validate_params,
1384 new_game_desc,
1385 validate_desc,
1386 new_game,
1387 dup_game,
1388 free_game,
1389 FALSE, solve_game,
fa3abef5 1390 FALSE, game_can_format_as_text_now, game_text_format,
f278dcf4 1391 new_ui,
1392 free_ui,
1393 encode_ui,
1394 decode_ui,
1395 game_changed_state,
1396 interpret_move,
1397 execute_move,
1398 20 /* FIXME */, game_compute_size, game_set_size,
1399 game_colours,
1400 game_new_drawstate,
1401 game_free_drawstate,
1402 game_redraw,
1403 game_anim_length,
1404 game_flash_length,
1cea529f 1405 game_status,
f278dcf4 1406 FALSE, FALSE, game_print_size, game_print,
1407 FALSE, /* wants_statusbar */
1408 FALSE, game_timing_state,
1409 0, /* flags */
1410};
Simon Tatham's portable puzzles collection; import of svn://svn.tartarus.org/sgt/puzzles