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 | |
89 | enum { |
90 | COL_BACKGROUND, |
91 | NCOLOURS |
92 | }; |
93 | |
94 | struct game_params { |
95 | int FIXME; |
96 | }; |
97 | |
98 | struct game_state { |
99 | int FIXME; |
100 | }; |
101 | |
102 | static game_params *default_params(void) |
103 | { |
104 | game_params *ret = snew(game_params); |
105 | |
106 | ret->FIXME = 0; |
107 | |
108 | return ret; |
109 | } |
110 | |
111 | static int game_fetch_preset(int i, char **name, game_params **params) |
112 | { |
113 | return FALSE; |
114 | } |
115 | |
116 | static void free_params(game_params *params) |
117 | { |
118 | sfree(params); |
119 | } |
120 | |
121 | static 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 | |
128 | static void decode_params(game_params *params, char const *string) |
129 | { |
130 | } |
131 | |
132 | static char *encode_params(game_params *params, int full) |
133 | { |
134 | return dupstr("FIXME"); |
135 | } |
136 | |
137 | static config_item *game_configure(game_params *params) |
138 | { |
139 | return NULL; |
140 | } |
141 | |
142 | static game_params *custom_params(config_item *cfg) |
143 | { |
144 | return NULL; |
145 | } |
146 | |
147 | static char *validate_params(game_params *params, int full) |
148 | { |
149 | return NULL; |
150 | } |
151 | |
152 | /* ---------------------------------------------------------------------- |
153 | * Solver. |
154 | */ |
155 | |
156 | int 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 | |
729 | void 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 | |
1021 | static 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 | |
1205 | static char *validate_desc(game_params *params, char *desc) |
1206 | { |
1207 | return NULL; |
1208 | } |
1209 | |
1210 | static 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 | |
1219 | static 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 | |
1228 | static void free_game(game_state *state) |
1229 | { |
1230 | sfree(state); |
1231 | } |
1232 | |
1233 | static char *solve_game(game_state *state, game_state *currstate, |
1234 | char *aux, char **error) |
1235 | { |
1236 | return NULL; |
1237 | } |
1238 | |
fa3abef5 |
1239 | static int game_can_format_as_text_now(game_params *params) |
1240 | { |
1241 | return TRUE; |
1242 | } |
1243 | |
f278dcf4 |
1244 | static char *game_text_format(game_state *state) |
1245 | { |
1246 | return NULL; |
1247 | } |
1248 | |
1249 | static game_ui *new_ui(game_state *state) |
1250 | { |
1251 | return NULL; |
1252 | } |
1253 | |
1254 | static void free_ui(game_ui *ui) |
1255 | { |
1256 | } |
1257 | |
1258 | static char *encode_ui(game_ui *ui) |
1259 | { |
1260 | return NULL; |
1261 | } |
1262 | |
1263 | static void decode_ui(game_ui *ui, char *encoding) |
1264 | { |
1265 | } |
1266 | |
1267 | static void game_changed_state(game_ui *ui, game_state *oldstate, |
1268 | game_state *newstate) |
1269 | { |
1270 | } |
1271 | |
1272 | struct game_drawstate { |
1273 | int tilesize; |
1274 | int FIXME; |
1275 | }; |
1276 | |
1277 | static 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 | |
1283 | static game_state *execute_move(game_state *state, char *move) |
1284 | { |
1285 | return NULL; |
1286 | } |
1287 | |
1288 | /* ---------------------------------------------------------------------- |
1289 | * Drawing routines. |
1290 | */ |
1291 | |
1292 | static void game_compute_size(game_params *params, int tilesize, |
1293 | int *x, int *y) |
1294 | { |
1295 | *x = *y = 10 * tilesize; /* FIXME */ |
1296 | } |
1297 | |
1298 | static void game_set_size(drawing *dr, game_drawstate *ds, |
1299 | game_params *params, int tilesize) |
1300 | { |
1301 | ds->tilesize = tilesize; |
1302 | } |
1303 | |
1304 | static 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 | |
1314 | static 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 | |
1324 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) |
1325 | { |
1326 | sfree(ds); |
1327 | } |
1328 | |
1329 | static 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 | |
1342 | static float game_anim_length(game_state *oldstate, game_state *newstate, |
1343 | int dir, game_ui *ui) |
1344 | { |
1345 | return 0.0F; |
1346 | } |
1347 | |
1348 | static float game_flash_length(game_state *oldstate, game_state *newstate, |
1349 | int dir, game_ui *ui) |
1350 | { |
1351 | return 0.0F; |
1352 | } |
1353 | |
1354 | static int game_timing_state(game_state *state, game_ui *ui) |
1355 | { |
1356 | return TRUE; |
1357 | } |
1358 | |
1359 | static void game_print_size(game_params *params, float *x, float *y) |
1360 | { |
1361 | } |
1362 | |
1363 | static void game_print(drawing *dr, game_state *state, int tilesize) |
1364 | { |
1365 | } |
1366 | |
1367 | #ifdef COMBINED |
1368 | #define thegame pearl |
1369 | #endif |
1370 | |
1371 | const 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 | }; |