| 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 | |
| 1239 | static int game_can_format_as_text_now(game_params *params) |
| 1240 | { |
| 1241 | return TRUE; |
| 1242 | } |
| 1243 | |
| 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 = { |
| 1372 | "Pearl", NULL, NULL, |
| 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, |
| 1387 | FALSE, game_can_format_as_text_now, game_text_format, |
| 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 | }; |