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
 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 };