~mdw / sgt / puzzles / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Patch from Lee Dowling to implement mouse control in Sokoban, along
[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) {
220
221#ifdef SOLVER_DIAGNOSTICS
222 for (y = 0; y < H; y++) {
223 for (x = 0; x < W; x++)
224 printf("%*x", (x&1) ? 5 : 2, workspace[y*W+x]);
225 printf("\n");
226 }
227#endif
228
229 int done_something = FALSE;
230
231 /*
232 * Go through the square state words, and discard any
233 * square state which is inconsistent with known facts
234 * about the edges around the square.
235 */
236 for (y = 0; y < h; y++)
237 for (x = 0; x < w; x++) {
238 for (b = 0; b < 0xD; b++)
239 if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
240 /*
241 * If any edge of this square is known to
242 * be connected when state b would require
243 * it disconnected, or vice versa, discard
244 * the state.
245 */
246 for (d = 1; d <= 8; d += d) {
247 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
248 if (workspace[ey*W+ex] ==
249 ((b & d) ? 2 : 1)) {
250 workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<b);
251#ifdef SOLVER_DIAGNOSTICS
252 printf("edge (%d,%d)-(%d,%d) rules out state"
253 " %d for square (%d,%d)\n",
254 ex/2, ey/2, (ex+1)/2, (ey+1)/2,
255 b, x, y);
256#endif
257 done_something = TRUE;
258 break;
259 }
260 }
261 }
262
263 /*
264 * Consistency check: each square must have at
265 * least one state left!
266 */
267 if (!workspace[(2*y+1)*W+(2*x+1)]) {
268#ifdef SOLVER_DIAGNOSTICS
269 printf("edge check at (%d,%d): inconsistency\n", x, y);
270 ret = 0;
271 goto cleanup;
272#endif
273 }
274 }
275
276 /*
277 * Now go through the states array again, and nail down any
278 * unknown edge if one of its neighbouring squares makes it
279 * known.
280 */
281 for (y = 0; y < h; y++)
282 for (x = 0; x < w; x++) {
283 int edgeor = 0, edgeand = 15;
284
285 for (b = 0; b < 0xD; b++)
286 if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
287 edgeor |= b;
288 edgeand &= b;
289 }
290
291 /*
292 * Now any bit clear in edgeor marks a disconnected
293 * edge, and any bit set in edgeand marks a
294 * connected edge.
295 */
296
297 /* First check consistency: neither bit is both! */
298 if (edgeand & ~edgeor) {
299#ifdef SOLVER_DIAGNOSTICS
300 printf("square check at (%d,%d): inconsistency\n", x, y);
301 ret = 0;
302 goto cleanup;
303#endif
304 }
305
306 for (d = 1; d <= 8; d += d) {
307 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
308
309 if (!(edgeor & d) && workspace[ey*W+ex] == 3) {
310 workspace[ey*W+ex] = 2;
311 done_something = TRUE;
312#ifdef SOLVER_DIAGNOSTICS
313 printf("possible states of square (%d,%d) force edge"
314 " (%d,%d)-(%d,%d) to be disconnected\n",
315 x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
316#endif
317 } else if ((edgeand & d) && workspace[ey*W+ex] == 3) {
318 workspace[ey*W+ex] = 1;
319 done_something = TRUE;
320#ifdef SOLVER_DIAGNOSTICS
321 printf("possible states of square (%d,%d) force edge"
322 " (%d,%d)-(%d,%d) to be connected\n",
323 x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
324#endif
325 }
326 }
327 }
328
329 if (done_something)
330 continue;
331
332 /*
333 * Now for longer-range clue-based deductions (using the
334 * rules that a corner clue must connect to two straight
335 * squares, and a straight clue must connect to at least
336 * one corner square).
337 */
338 for (y = 0; y < h; y++)
339 for (x = 0; x < w; x++)
340 switch (clues[y*w+x]) {
341 case CORNER:
342 for (d = 1; d <= 8; d += d) {
343 int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
344 int fx = ex + DX(d), fy = ey + DY(d);
345 int type = d | F(d);
346
347 if (workspace[ey*W+ex] == 1) {
348 /*
349 * If a corner clue is connected on any
350 * edge, then we can immediately nail
351 * down the square beyond that edge as
352 * being a straight in the appropriate
353 * direction.
354 */
355 if (workspace[fy*W+fx] != (1<<type)) {
356 workspace[fy*W+fx] = (1<<type);
357 done_something = TRUE;
358#ifdef SOLVER_DIAGNOSTICS
359 printf("corner clue at (%d,%d) forces square "
360 "(%d,%d) into state %d\n", x, y,
361 fx/2, fy/2, type);
362#endif
363
364 }
365 } else if (workspace[ey*W+ex] == 3) {
366 /*
367 * Conversely, if a corner clue is
368 * separated by an unknown edge from a
369 * square which _cannot_ be a straight
370 * in the appropriate direction, we can
371 * mark that edge as disconnected.
372 */
373 if (!(workspace[fy*W+fx] & (1<<type))) {
374 workspace[ey*W+ex] = 2;
375 done_something = TRUE;
376#ifdef SOLVER_DIAGNOSTICS
377 printf("corner clue at (%d,%d), plus square "
378 "(%d,%d) not being state %d, "
379 "disconnects edge (%d,%d)-(%d,%d)\n",
380 x, y, fx/2, fy/2, type,
381 ex/2, ey/2, (ex+1)/2, (ey+1)/2);
382#endif
383
384 }
385 }
386 }
387
388
389 break;
390 case STRAIGHT:
391 /*
392 * If a straight clue is between two squares
393 * neither of which is capable of being a
394 * corner connected to it, then the straight
395 * clue cannot point in that direction.
396 */
397 for (d = 1; d <= 2; d += d) {
398 int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
399 int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
400 int type = d | F(d);
401
402 if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type)))
403 continue;
404
405 if (!(workspace[fy*W+fx] & ((1<<(F(d)|A(d))) |
406 (1<<(F(d)|C(d))))) &&
407 !(workspace[gy*W+gx] & ((1<<( d |A(d))) |
408 (1<<( d |C(d)))))) {
409 workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<type);
410 done_something = TRUE;
411#ifdef SOLVER_DIAGNOSTICS
412 printf("straight clue at (%d,%d) cannot corner at "
413 "(%d,%d) or (%d,%d) so is not state %d\n",
414 x, y, fx/2, fy/2, gx/2, gy/2, type);
415#endif
416 }
417
418 }
419
420 /*
421 * If a straight clue with known direction is
422 * connected on one side to a known straight,
423 * then on the other side it must be a corner.
424 */
425 for (d = 1; d <= 8; d += d) {
426 int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
427 int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
428 int type = d | F(d);
429
430 if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type))
431 continue;
432
433 if (!(workspace[fy*W+fx] &~ (bLR|bUD)) &&
434 (workspace[gy*W+gx] &~ (bLU|bLD|bRU|bRD))) {
435 workspace[gy*W+gx] &= (bLU|bLD|bRU|bRD);
436 done_something = TRUE;
437#ifdef SOLVER_DIAGNOSTICS
438 printf("straight clue at (%d,%d) connecting to "
439 "straight at (%d,%d) makes (%d,%d) a "
440 "corner\n", x, y, fx/2, fy/2, gx/2, gy/2);
441#endif
442 }
443
444 }
445 break;
446 }
447
448 if (done_something)
449 continue;
450
451 /*
452 * Now detect shortcut loops.
453 */
454
455 {
456 int nonblanks, loopclass;
457
458 dsf_init(dsf, w*h);
459 for (x = 0; x < w*h; x++)
460 dsfsize[x] = 1;
461
462 /*
463 * First go through the edge entries and update the dsf
464 * of which squares are connected to which others. We
465 * also track the number of squares in each equivalence
466 * class, and count the overall number of
467 * known-non-blank squares.
468 *
469 * In the process of doing this, we must notice if a
470 * loop has already been formed. If it has, we blank
471 * out any square which isn't part of that loop
472 * (failing a consistency check if any such square does
473 * not have BLANK as one of its remaining options) and
474 * exit the deduction loop with success.
475 */
476 nonblanks = 0;
477 loopclass = -1;
478 for (y = 1; y < H-1; y++)
479 for (x = 1; x < W-1; x++)
480 if ((y ^ x) & 1) {
481 /*
482 * (x,y) are the workspace coordinates of
483 * an edge field. Compute the normal-space
484 * coordinates of the squares it connects.
485 */
486 int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
487 int bx = x/2, by = y/2, bc = by*w+bx;
488
489 /*
490 * If the edge is connected, do the dsf
491 * thing.
492 */
493 if (workspace[y*W+x] == 1) {
494 int ae, be;
495
496 ae = dsf_canonify(dsf, ac);
497 be = dsf_canonify(dsf, bc);
498
499 if (ae == be) {
500 /*
501 * We have a loop!
502 */
503 if (loopclass != -1) {
504 /*
505 * In fact, we have two
506 * separate loops, which is
507 * doom.
508 */
509#ifdef SOLVER_DIAGNOSTICS
510 printf("two loops found in grid!\n");
511#endif
512 ret = 0;
513 goto cleanup;
514 }
515 loopclass = ae;
516 } else {
517 /*
518 * Merge the two equivalence
519 * classes.
520 */
521 int size = dsfsize[ae] + dsfsize[be];
522 dsf_merge(dsf, ac, bc);
523 ae = dsf_canonify(dsf, ac);
524 dsfsize[ae] = size;
525 }
526 }
527 } else if ((y & x) & 1) {
528 /*
529 * (x,y) are the workspace coordinates of a
530 * square field. If the square is
531 * definitely not blank, count it.
532 */
533 if (!(workspace[y*W+x] & bBLANK))
534 nonblanks++;
535 }
536
537 /*
538 * If we discovered an existing loop above, we must now
539 * blank every square not part of it, and exit the main
540 * deduction loop.
541 */
542 if (loopclass != -1) {
543#ifdef SOLVER_DIAGNOSTICS
544 printf("loop found in grid!\n");
545#endif
546 for (y = 0; y < h; y++)
547 for (x = 0; x < w; x++)
548 if (dsf_canonify(dsf, y*w+x) != loopclass) {
549 if (workspace[(y*2+1)*W+(x*2+1)] & bBLANK) {
550 workspace[(y*2+1)*W+(x*2+1)] = bBLANK;
551 } else {
552 /*
553 * This square is not part of the
554 * loop, but is known non-blank. We
555 * have goofed.
556 */
557#ifdef SOLVER_DIAGNOSTICS
558 printf("non-blank square (%d,%d) found outside"
559 " loop!\n", x, y);
560#endif
561 ret = 0;
562 goto cleanup;
563 }
564 }
565 /*
566 * And we're done.
567 */
568 ret = 1;
569 break;
570 }
571
572 /*
573 * Now go through the workspace again and mark any edge
574 * which would cause a shortcut loop (i.e. would
575 * connect together two squares in the same equivalence
576 * class, and that equivalence class does not contain
577 * _all_ the known-non-blank squares currently in the
578 * grid) as disconnected. Also, mark any _square state_
579 * which would cause a shortcut loop as disconnected.
580 */
581 for (y = 1; y < H-1; y++)
582 for (x = 1; x < W-1; x++)
583 if ((y ^ x) & 1) {
584 /*
585 * (x,y) are the workspace coordinates of
586 * an edge field. Compute the normal-space
587 * coordinates of the squares it connects.
588 */
589 int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
590 int bx = x/2, by = y/2, bc = by*w+bx;
591
592 /*
593 * If the edge is currently unknown, and
594 * sits between two squares in the same
595 * equivalence class, and the size of that
596 * class is less than nonblanks, then
597 * connecting this edge would be a shortcut
598 * loop and so we must not do so.
599 */
600 if (workspace[y*W+x] == 3) {
601 int ae, be;
602
603 ae = dsf_canonify(dsf, ac);
604 be = dsf_canonify(dsf, bc);
605
606 if (ae == be) {
607 /*
608 * We have a loop. Is it a shortcut?
609 */
610 if (dsfsize[ae] < nonblanks) {
611 /*
612 * Yes! Mark this edge disconnected.
613 */
614 workspace[y*W+x] = 2;
615 done_something = TRUE;
616#ifdef SOLVER_DIAGNOSTICS
617 printf("edge (%d,%d)-(%d,%d) would create"
618 " a shortcut loop, hence must be"
619 " disconnected\n", x/2, y/2,
620 (x+1)/2, (y+1)/2);
621#endif
622 }
623 }
624 }
625 } else if ((y & x) & 1) {
626 /*
627 * (x,y) are the workspace coordinates of a
628 * square field. Go through its possible
629 * (non-blank) states and see if any gives
630 * rise to a shortcut loop.
631 *
632 * This is slightly fiddly, because we have
633 * to check whether this square is already
634 * part of the same equivalence class as
635 * the things it's joining.
636 */
637 int ae = dsf_canonify(dsf, (y/2)*w+(x/2));
638
639 for (b = 2; b < 0xD; b++)
640 if (workspace[y*W+x] & (1<<b)) {
641 /*
642 * Find the equivalence classes of
643 * the two squares this one would
644 * connect if it were in this
645 * state.
646 */
647 int e = -1;
648
649 for (d = 1; d <= 8; d += d) if (b & d) {
650 int xx = x/2 + DX(d), yy = y/2 + DY(d);
651 int ee = dsf_canonify(dsf, yy*w+xx);
652
653 if (e == -1)
654 ee = e;
655 else if (e != ee)
656 e = -2;
657 }
658
659 if (e >= 0) {
660 /*
661 * This square state would form
662 * a loop on equivalence class
663 * e. Measure the size of that
664 * loop, and see if it's a
665 * shortcut.
666 */
667 int loopsize = dsfsize[e];
668 if (e != ae)
669 loopsize++;/* add the square itself */
670 if (loopsize < nonblanks) {
671 /*
672 * It is! Mark this square
673 * state invalid.
674 */
675 workspace[y*W+x] &= ~(1<<b);
676 done_something = TRUE;
677#ifdef SOLVER_DIAGNOSTICS
678 printf("square (%d,%d) would create a "
679 "shortcut loop in state %d, "
680 "hence cannot be\n",
681 x/2, y/2, b);
682#endif
683 }
684 }
685 }
686 }
687 }
688
689 if (done_something)
690 continue;
691
692 /*
693 * If we reach here, there is nothing left we can do.
694 * Return 2 for ambiguous puzzle.
695 */
696 ret = 2;
697 goto cleanup;
698 }
699
700 /*
701 * If we reach _here_, it's by `break' out of the main loop,
702 * which means we've successfully achieved a solution. This
703 * means that we expect every square to be nailed down to
704 * exactly one possibility. Transcribe those possibilities into
705 * the result array.
706 */
707 for (y = 0; y < h; y++)
708 for (x = 0; x < w; x++) {
709 for (b = 0; b < 0xD; b++)
710 if (workspace[(2*y+1)*W+(2*x+1)] == (1<<b)) {
711 result[y*w+x] = b;
712 break;
713 }
714 assert(b < 0xD); /* we should have had a break by now */
715 }
716
717 cleanup:
718 sfree(dsfsize);
719 sfree(dsf);
720 sfree(workspace);
721 assert(ret >= 0);
722 return ret;
723}
724
725/* ----------------------------------------------------------------------
726 * Loop generator.
727 */
728
729void pearl_loopgen(int w, int h, char *grid, random_state *rs)
730{
731 int *options, *mindist, *maxdist, *list;
732 int x, y, d, total, n, area, limit;
733
734 /*
735 * We're eventually going to have to return a w-by-h array
736 * containing line segment data. However, it's more convenient
737 * while actually generating the loop to consider the problem
738 * as a (w-1) by (h-1) array in which some squares are `inside'
739 * and some `outside'.
740 *
741 * I'm going to use the top left corner of my return array in
742 * the latter manner until the end of the function.
743 */
744
745 /*
746 * To begin with, all squares are outside (0), except for one
747 * randomly selected one which is inside (1).
748 */
749 memset(grid, 0, w*h);
750 x = random_upto(rs, w-1);
751 y = random_upto(rs, h-1);
752 grid[y*w+x] = 1;
753
754 /*
755 * I'm also going to need an array to store the possible
756 * options for the next extension of the grid.
757 */
758 options = snewn(w*h, int);
759 for (x = 0; x < w*h; x++)
760 options[x] = 0;
761
762 /*
763 * And some arrays and a list for breadth-first searching.
764 */
765 mindist = snewn(w*h, int);
766 maxdist = snewn(w*h, int);
767 list = snewn(w*h, int);
768
769 /*
770 * Now we repeatedly scan the grid for feasible squares into
771 * which we can extend our loop, pick one, and do it.
772 */
773 area = 1;
774
775 while (1) {
776#ifdef LOOPGEN_DIAGNOSTICS
777 for (y = 0; y < h; y++) {
778 for (x = 0; x < w; x++)
779 printf("%d", grid[y*w+x]);
780 printf("\n");
781 }
782 printf("\n");
783#endif
784
785 /*
786 * Our primary aim in growing this loop is to make it
787 * reasonably _dense_ in the target rectangle. That is, we
788 * want the maximum over all squares of the minimum
789 * distance from that square to the loop to be small.
790 *
791 * Therefore, we start with a breadth-first search of the
792 * grid to find those minimum distances.
793 */
794 {
795 int head = 0, tail = 0;
796 int i;
797
798 for (i = 0; i < w*h; i++) {
799 mindist[i] = -1;
800 if (grid[i]) {
801 mindist[i] = 0;
802 list[tail++] = i;
803 }
804 }
805
806 while (head < tail) {
807 i = list[head++];
808 y = i / w;
809 x = i % w;
810 for (d = 1; d <= 8; d += d) {
811 int xx = x + DX(d), yy = y + DY(d);
812 if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
813 mindist[yy*w+xx] < 0) {
814 mindist[yy*w+xx] = mindist[i] + 1;
815 list[tail++] = yy*w+xx;
816 }
817 }
818 }
819
820 /*
821 * Having done the BFS, we now backtrack along its path
822 * to determine the most distant square that each
823 * square is on the shortest path to. This tells us
824 * which of the loop extension candidates (all of which
825 * are squares marked 1) is most desirable to extend
826 * into in terms of minimising the maximum distance
827 * from any empty square to the nearest loop square.
828 */
829 for (head = tail; head-- > 0 ;) {
830 int max;
831
832 i = list[head];
833 y = i / w;
834 x = i % w;
835
836 max = mindist[i];
837
838 for (d = 1; d <= 8; d += d) {
839 int xx = x + DX(d), yy = y + DY(d);
840 if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
841 mindist[yy*w+xx] > mindist[i] &&
842 maxdist[yy*w+xx] > max) {
843 max = maxdist[yy*w+xx];
844 }
845 }
846
847 maxdist[i] = max;
848 }
849 }
850
851 /*
852 * A square is a viable candidate for extension of our loop
853 * if and only if the following conditions are all met:
854 * - It is currently labelled 0.
855 * - At least one of its four orthogonal neighbours is
856 * labelled 1.
857 * - If you consider its eight orthogonal and diagonal
858 * neighbours to form a ring, that ring contains at most
859 * one contiguous run of 1s. (It must also contain at
860 * _least_ one, of course, but that's already guaranteed
861 * by the previous condition so there's no need to test
862 * it separately.)
863 */
864 total = 0;
865 for (y = 0; y < h-1; y++)
866 for (x = 0; x < w-1; x++) {
867 int ring[8];
868 int rx, neighbours, runs, dist;
869
870 dist = maxdist[y*w+x];
871 options[y*w+x] = 0;
872
873 if (grid[y*w+x])
874 continue; /* it isn't labelled 0 */
875
876 neighbours = 0;
877 for (rx = 0, d = 1; d <= 8; rx += 2, d += d) {
878 int x2 = x + DX(d), y2 = y + DY(d);
879 int x3 = x2 + DX(A(d)), y3 = y2 + DY(A(d));
880 int g2 = (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h ?
881 grid[y2*w+x2] : 0);
882 int g3 = (x3 >= 0 && x3 < w && y3 >= 0 && y3 < h ?
883 grid[y3*w+x3] : 0);
884 ring[rx] = g2;
885 ring[rx+1] = g3;
886 if (g2)
887 neighbours++;
888 }
889
890 if (!neighbours)
891 continue; /* it doesn't have a 1 neighbour */
892
893 runs = 0;
894 for (rx = 0; rx < 8; rx++)
895 if (ring[rx] && !ring[(rx+1) & 7])
896 runs++;
897
898 if (runs > 1)
899 continue; /* too many runs of 1s */
900
901 /*
902 * Now we know this square is a viable extension
903 * candidate. Mark it.
904 *
905 * FIXME: probabilistic prioritisation based on
906 * perimeter perturbation? (Wow, must keep that
907 * phrase.)
908 */
909 options[y*w+x] = dist * (4-neighbours) * (4-neighbours);
910 total += options[y*w+x];
911 }
912
913 if (!total)
914 break; /* nowhere to go! */
915
916 /*
917 * Now pick a random one of the viable extension squares,
918 * and extend into it.
919 */
920 n = random_upto(rs, total);
921 for (y = 0; y < h-1; y++)
922 for (x = 0; x < w-1; x++) {
923 assert(n >= 0);
924 if (options[y*w+x] > n)
925 goto found; /* two-level break */
926 n -= options[y*w+x];
927 }
928 assert(!"We shouldn't ever get here");
929 found:
930 grid[y*w+x] = 1;
931 area++;
932
933 /*
934 * We terminate the loop when around 7/12 of the grid area
935 * is full, but we also require that the loop has reached
936 * all four edges.
937 */
938 limit = random_upto(rs, (w-1)*(h-1)) + 13*(w-1)*(h-1);
939 if (24 * area > limit) {
940 int l = FALSE, r = FALSE, u = FALSE, d = FALSE;
941 for (x = 0; x < w; x++) {
942 if (grid[0*w+x])
943 u = TRUE;
944 if (grid[(h-2)*w+x])
945 d = TRUE;
946 }
947 for (y = 0; y < h; y++) {
948 if (grid[y*w+0])
949 l = TRUE;
950 if (grid[y*w+(w-2)])
951 r = TRUE;
952 }
953 if (l && r && u && d)
954 break;
955 }
956 }
957
958 sfree(list);
959 sfree(maxdist);
960 sfree(mindist);
961 sfree(options);
962
963#ifdef LOOPGEN_DIAGNOSTICS
964 printf("final loop:\n");
965 for (y = 0; y < h; y++) {
966 for (x = 0; x < w; x++)
967 printf("%d", grid[y*w+x]);
968 printf("\n");
969 }
970 printf("\n");
971#endif
972
973 /*
974 * Now convert this array of 0s and 1s into an array of path
975 * components.
976 */
977 for (y = h; y-- > 0 ;) {
978 for (x = w; x-- > 0 ;) {
979 /*
980 * Examine the four grid squares of which (x,y) are in
981 * the bottom right, to determine the output for this
982 * square.
983 */
984 int ul = (x > 0 && y > 0 ? grid[(y-1)*w+(x-1)] : 0);
985 int ur = (y > 0 ? grid[(y-1)*w+x] : 0);
986 int dl = (x > 0 ? grid[y*w+(x-1)] : 0);
987 int dr = grid[y*w+x];
988 int type = 0;
989
990 if (ul != ur) type |= U;
991 if (dl != dr) type |= D;
992 if (ul != dl) type |= L;
993 if (ur != dr) type |= R;
994
995 assert((bLR|bUD|bLU|bLD|bRU|bRD|bBLANK) & (1 << type));
996
997 grid[y*w+x] = type;
998
999 }
1000 }
1001
1002#if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
1003 printf("as returned:\n");
1004 for (y = 0; y < h; y++) {
1005 for (x = 0; x < w; x++) {
1006 int type = grid[y*w+x];
1007 char s[5], *p = s;
1008 if (type & L) *p++ = 'L';
1009 if (type & R) *p++ = 'R';
1010 if (type & U) *p++ = 'U';
1011 if (type & D) *p++ = 'D';
1012 *p = '\0';
1013 printf("%3s", s);
1014 }
1015 printf("\n");
1016 }
1017 printf("\n");
1018#endif
1019}
1020
1021static char *new_game_desc(game_params *params, random_state *rs,
1022 char **aux, int interactive)
1023{
1024 char *grid, *clues;
1025 int *clueorder;
1026 int w = 10, h = 10;
1027 int x, y, d, ret, i;
1028
1029#if 0
1030 clues = snewn(7*7, char);
1031 memcpy(clues,
1032 "\0\1\0\0\2\0\0"
1033 "\0\0\0\2\0\0\0"
1034 "\0\0\0\2\0\0\1"
1035 "\2\0\0\2\0\0\0"
1036 "\2\0\0\0\0\0\1"
1037 "\0\0\1\0\0\2\0"
1038 "\0\0\2\0\0\0\0", 7*7);
1039 grid = snewn(7*7, char);
1040 printf("%d\n", pearl_solve(7, 7, clues, grid));
1041#elif 0
1042 clues = snewn(10*10, char);
1043 memcpy(clues,
1044 "\0\0\2\0\2\0\0\0\0\0"
1045 "\0\0\0\0\2\0\0\0\1\0"
1046 "\0\0\1\0\1\0\2\0\0\0"
1047 "\0\0\0\2\0\0\2\0\0\0"
1048 "\1\0\0\0\0\2\0\0\0\2"
1049 "\0\0\2\0\0\0\0\2\0\0"
1050 "\0\0\1\0\0\0\2\0\0\0"
1051 "\2\0\0\0\1\0\0\0\0\2"
1052 "\0\0\0\0\0\0\2\2\0\0"
1053 "\0\0\1\0\0\0\0\0\0\1", 10*10);
1054 grid = snewn(10*10, char);
1055 printf("%d\n", pearl_solve(10, 10, clues, grid));
1056#elif 0
1057 clues = snewn(10*10, char);
1058 memcpy(clues,
1059 "\0\0\0\0\0\0\1\0\0\0"
1060 "\0\1\0\1\2\0\0\0\0\2"
1061 "\0\0\0\0\0\0\0\0\0\1"
1062 "\2\0\0\1\2\2\1\0\0\0"
1063 "\1\0\0\0\0\0\0\1\0\0"
1064 "\0\0\2\0\0\0\0\0\0\2"
1065 "\0\0\0\2\1\2\1\0\0\2"
1066 "\2\0\0\0\0\0\0\0\0\0"
1067 "\2\0\0\0\0\1\1\0\2\0"
1068 "\0\0\0\2\0\0\0\0\0\0", 10*10);
1069 grid = snewn(10*10, char);
1070 printf("%d\n", pearl_solve(10, 10, clues, grid));
1071#endif
1072
1073 grid = snewn(w*h, char);
1074 clues = snewn(w*h, char);
1075 clueorder = snewn(w*h, int);
1076
1077 while (1) {
1078 pearl_loopgen(w, h, grid, rs);
1079
1080#ifdef GENERATION_DIAGNOSTICS
1081 printf("grid array:\n");
1082 for (y = 0; y < h; y++) {
1083 for (x = 0; x < w; x++) {
1084 int type = grid[y*w+x];
1085 char s[5], *p = s;
1086 if (type & L) *p++ = 'L';
1087 if (type & R) *p++ = 'R';
1088 if (type & U) *p++ = 'U';
1089 if (type & D) *p++ = 'D';
1090 *p = '\0';
1091 printf("%2s ", s);
1092 }
1093 printf("\n");
1094 }
1095 printf("\n");
1096#endif
1097
1098 /*
1099 * Set up the maximal clue array.
1100 */
1101 for (y = 0; y < h; y++)
1102 for (x = 0; x < w; x++) {
1103 int type = grid[y*w+x];
1104
1105 clues[y*w+x] = NOCLUE;
1106
1107 if ((bLR|bUD) & (1 << type)) {
1108 /*
1109 * This is a straight; see if it's a viable
1110 * candidate for a straight clue. It qualifies if
1111 * at least one of the squares it connects to is a
1112 * corner.
1113 */
1114 for (d = 1; d <= 8; d += d) if (type & d) {
1115 int xx = x + DX(d), yy = y + DY(d);
1116 assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
1117 if ((bLU|bLD|bRU|bRD) & (1 << grid[yy*w+xx]))
1118 break;
1119 }
1120 if (d <= 8) /* we found one */
1121 clues[y*w+x] = STRAIGHT;
1122 } else if ((bLU|bLD|bRU|bRD) & (1 << type)) {
1123 /*
1124 * This is a corner; see if it's a viable candidate
1125 * for a corner clue. It qualifies if all the
1126 * squares it connects to are straights.
1127 */
1128 for (d = 1; d <= 8; d += d) if (type & d) {
1129 int xx = x + DX(d), yy = y + DY(d);
1130 assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
1131 if (!((bLR|bUD) & (1 << grid[yy*w+xx])))
1132 break;
1133 }
1134 if (d > 8) /* we didn't find a counterexample */
1135 clues[y*w+x] = CORNER;
1136 }
1137 }
1138
1139#ifdef GENERATION_DIAGNOSTICS
1140 printf("clue array:\n");
1141 for (y = 0; y < h; y++) {
1142 for (x = 0; x < w; x++) {
1143 printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
1144 }
1145 printf("\n");
1146 }
1147 printf("\n");
1148#endif
1149
1150 /*
1151 * See if we can solve the puzzle just like this.
1152 */
1153 ret = pearl_solve(w, h, clues, grid);
1154 assert(ret > 0); /* shouldn't be inconsistent! */
1155 if (ret != 1)
1156 continue; /* go round and try again */
1157
1158 /*
1159 * Now shuffle the grid points and gradually remove the
1160 * clues to find a minimal set which still leaves the
1161 * puzzle soluble.
1162 */
1163 for (i = 0; i < w*h; i++)
1164 clueorder[i] = i;
1165 shuffle(clueorder, w*h, sizeof(*clueorder), rs);
1166 for (i = 0; i < w*h; i++) {
1167 int clue;
1168
1169 y = clueorder[i] / w;
1170 x = clueorder[i] % w;
1171
1172 if (clues[y*w+x] == 0)
1173 continue;
1174
1175 clue = clues[y*w+x];
1176 clues[y*w+x] = 0; /* try removing this clue */
1177
1178 ret = pearl_solve(w, h, clues, grid);
1179 assert(ret > 0);
1180 if (ret != 1)
1181 clues[y*w+x] = clue; /* oops, put it back again */
1182 }
1183
1184#ifdef FINISHED_PUZZLE
1185 printf("clue array:\n");
1186 for (y = 0; y < h; y++) {
1187 for (x = 0; x < w; x++) {
1188 printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
1189 }
1190 printf("\n");
1191 }
1192 printf("\n");
1193#endif
1194
1195 break; /* got it */
1196 }
1197
1198 sfree(grid);
1199 sfree(clues);
1200 sfree(clueorder);
1201
1202 return dupstr("FIXME");
1203}
1204
1205static char *validate_desc(game_params *params, char *desc)
1206{
1207 return NULL;
1208}
1209
1210static game_state *new_game(midend *me, game_params *params, char *desc)
1211{
1212 game_state *state = snew(game_state);
1213
1214 state->FIXME = 0;
1215
1216 return state;
1217}
1218
1219static game_state *dup_game(game_state *state)
1220{
1221 game_state *ret = snew(game_state);
1222
1223 ret->FIXME = state->FIXME;
1224
1225 return ret;
1226}
1227
1228static void free_game(game_state *state)
1229{
1230 sfree(state);
1231}
1232
1233static char *solve_game(game_state *state, game_state *currstate,
1234 char *aux, char **error)
1235{
1236 return NULL;
1237}
1238
fa3abef5 1239static int game_can_format_as_text_now(game_params *params)
1240{
1241 return TRUE;
1242}
1243
f278dcf4 1244static char *game_text_format(game_state *state)
1245{
1246 return NULL;
1247}
1248
1249static game_ui *new_ui(game_state *state)
1250{
1251 return NULL;
1252}
1253
1254static void free_ui(game_ui *ui)
1255{
1256}
1257
1258static char *encode_ui(game_ui *ui)
1259{
1260 return NULL;
1261}
1262
1263static void decode_ui(game_ui *ui, char *encoding)
1264{
1265}
1266
1267static void game_changed_state(game_ui *ui, game_state *oldstate,
1268 game_state *newstate)
1269{
1270}
1271
1272struct game_drawstate {
1273 int tilesize;
1274 int FIXME;
1275};
1276
1277static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1278 int x, int y, int button)
1279{
1280 return NULL;
1281}
1282
1283static game_state *execute_move(game_state *state, char *move)
1284{
1285 return NULL;
1286}
1287
1288/* ----------------------------------------------------------------------
1289 * Drawing routines.
1290 */
1291
1292static void game_compute_size(game_params *params, int tilesize,
1293 int *x, int *y)
1294{
1295 *x = *y = 10 * tilesize; /* FIXME */
1296}
1297
1298static void game_set_size(drawing *dr, game_drawstate *ds,
1299 game_params *params, int tilesize)
1300{
1301 ds->tilesize = tilesize;
1302}
1303
1304static float *game_colours(frontend *fe, int *ncolours)
1305{
1306 float *ret = snewn(3 * NCOLOURS, float);
1307
1308 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1309
1310 *ncolours = NCOLOURS;
1311 return ret;
1312}
1313
1314static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1315{
1316 struct game_drawstate *ds = snew(struct game_drawstate);
1317
1318 ds->tilesize = 0;
1319 ds->FIXME = 0;
1320
1321 return ds;
1322}
1323
1324static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1325{
1326 sfree(ds);
1327}
1328
1329static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1330 game_state *state, int dir, game_ui *ui,
1331 float animtime, float flashtime)
1332{
1333 /*
1334 * The initial contents of the window are not guaranteed and
1335 * can vary with front ends. To be on the safe side, all games
1336 * should start by drawing a big background-colour rectangle
1337 * covering the whole window.
1338 */
1339 draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
1340}
1341
1342static float game_anim_length(game_state *oldstate, game_state *newstate,
1343 int dir, game_ui *ui)
1344{
1345 return 0.0F;
1346}
1347
1348static float game_flash_length(game_state *oldstate, game_state *newstate,
1349 int dir, game_ui *ui)
1350{
1351 return 0.0F;
1352}
1353
1354static int game_timing_state(game_state *state, game_ui *ui)
1355{
1356 return TRUE;
1357}
1358
1359static void game_print_size(game_params *params, float *x, float *y)
1360{
1361}
1362
1363static void game_print(drawing *dr, game_state *state, int tilesize)
1364{
1365}
1366
1367#ifdef COMBINED
1368#define thegame pearl
1369#endif
1370
1371const struct game thegame = {
750037d7 1372 "Pearl", NULL, NULL,
f278dcf4 1373 default_params,
1374 game_fetch_preset,
1375 decode_params,
1376 encode_params,
1377 free_params,
1378 dup_params,
1379 FALSE, game_configure, custom_params,
1380 validate_params,
1381 new_game_desc,
1382 validate_desc,
1383 new_game,
1384 dup_game,
1385 free_game,
1386 FALSE, solve_game,
fa3abef5 1387 FALSE, game_can_format_as_text_now, game_text_format,
f278dcf4 1388 new_ui,
1389 free_ui,
1390 encode_ui,
1391 decode_ui,
1392 game_changed_state,
1393 interpret_move,
1394 execute_move,
1395 20 /* FIXME */, game_compute_size, game_set_size,
1396 game_colours,
1397 game_new_drawstate,
1398 game_free_drawstate,
1399 game_redraw,
1400 game_anim_length,
1401 game_flash_length,
1402 FALSE, FALSE, game_print_size, game_print,
1403 FALSE, /* wants_statusbar */
1404 FALSE, game_timing_state,
1405 0, /* flags */
1406};
Simon Tatham's portable puzzles collection; import of svn://svn.tartarus.org/sgt/puzzles