unfinished/pearl.c

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