unfinished/divvy.c

   1 /*
   2  * Library code to divide up a rectangle into a number of equally
   3  * sized ominoes, in a random fashion.
   4  *
   5  * Could use this for generating solved grids of
   6  * http://www.nikoli.co.jp/ja/puzzles/block_puzzle/
   7  * or for generating the playfield for Jigsaw Sudoku.
   8  */
   9
  10 /*
  11  * Possible improvements which might cut the fail rate:
  12  *
  13  *  - instead of picking one omino to extend in an iteration, try
  14  *    them all in succession (in a randomised order)
  15  *
  16  *  - (for real rigour) instead of bfsing over ominoes, bfs over
  17  *    the space of possible _removed squares_. That way we aren't
  18  *    limited to randomly choosing a single square to remove from
  19  *    an omino and failing if that particular square doesn't
  20  *    happen to work.
  21  *
  22  * However, I don't currently think it's neecss~|~
  23  */
  24
  25 #include <assert.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <stddef.h>
  29
  30 #include "puzzles.h"
  31
  32 /*
  33  * Subroutine which implements a function used in computing both
  34  * whether a square can safely be added to an omino, and whether
  35  * it can safely be removed.
  36  *
  37  * We enumerate the eight squares 8-adjacent to this one, in
  38  * cyclic order. We go round that loop and count the number of
  39  * times we find a square owned by the target omino next to one
  40  * not owned by it. We then return success iff that count is 2.
  41  *
  42  * When adding a square to an omino, this is precisely the
  43  * criterion which tells us that adding the square won't leave a
  44  * hole in the middle of the omino. (There's no explicit
  45  * requirement in the statement of our problem that the ominoes be
  46  * simply connected, but we do know they must be all of equal size
  47  * and so it's clear that we must avoid leaving holes, since a
  48  * hole would necessarily be smaller than the maximum omino size.)
  49  *
  50  * When removing a square from an omino, the _same_ criterion
  51  * tells us that removing the square won't disconnect the omino.
  52  */
  53 static int addremcommon(int w, int h, int x, int y, int *own, int val)
  54 {
  55     int neighbours[8];
  56     int dir, count;
  57
  58     for (dir = 0; dir < 8; dir++) {
  59         int dx = ((dir & 3) == 2 ? 0 : dir > 2 && dir < 6 ? +1 : -1);
  60         int dy = ((dir & 3) == 0 ? 0 : dir < 4 ? -1 : +1);
  61         int sx = x+dx, sy = y+dy;
  62
  63         if (sx < 0 || sx >= w || sy < 0 || sy >= h)
  64             neighbours[dir] = -1;      /* outside the grid */
  65         else
  66             neighbours[dir] = own[sy*w+sx];
  67     }
  68
  69     /*
  70      * To begin with, check 4-adjacency.
  71      */
  72     if (neighbours[0] != val && neighbours[2] != val &&
  73         neighbours[4] != val && neighbours[6] != val)
  74         return FALSE;
  75
  76     count = 0;
  77
  78     for (dir = 0; dir < 8; dir++) {
  79         int next = (dir + 1) & 7;
  80         int gotthis = (neighbours[dir] == val);
  81         int gotnext = (neighbours[next] == val);
  82
  83         if (gotthis != gotnext)
  84             count++;
  85     }
  86
  87     return (count == 2);
  88 }
  89
  90 /*
  91  * w and h are the dimensions of the rectangle.
  92  *
  93  * k is the size of the required ominoes. (So k must divide w*h,
  94  * of course.)
  95  *
  96  * The returned result is a w*h-sized dsf.
  97  *
  98  * In both of the above suggested use cases, the user would
  99  * probably want w==h==k, but that isn't a requirement.
 100  */
 101 static int *divvy_internal(int w, int h, int k, random_state *rs)
 102 {
 103     int *order, *queue, *tmp, *own, *sizes, *addable, *removable, *retdsf;
 104     int wh = w*h;
 105     int i, j, n, x, y, qhead, qtail;
 106
 107     n = wh / k;
 108     assert(wh == k*n);
 109
 110     order = snewn(wh, int);
 111     tmp = snewn(wh, int);
 112     own = snewn(wh, int);
 113     sizes = snewn(n, int);
 114     queue = snewn(n, int);
 115     addable = snewn(wh*4, int);
 116     removable = snewn(wh, int);
 117
 118     /*
 119      * Permute the grid squares into a random order, which will be
 120      * used for iterating over the grid whenever we need to search
 121      * for something. This prevents directional bias and arranges
 122      * for the answer to be non-deterministic.
 123      */
 124     for (i = 0; i < wh; i++)
 125         order[i] = i;
 126     shuffle(order, wh, sizeof(*order), rs);
 127
 128     /*
 129      * Begin by choosing a starting square at random for each
 130      * omino.
 131      */
 132     for (i = 0; i < wh; i++) {
 133         own[i] = -1;
 134     }
 135     for (i = 0; i < n; i++) {
 136         own[order[i]] = i;
 137         sizes[i] = 1;
 138     }
 139
 140     /*
 141      * Now repeatedly pick a random omino which isn't already at
 142      * the target size, and find a way to expand it by one. This
 143      * may involve stealing a square from another omino, in which
 144      * case we then re-expand that omino, forming a chain of
 145      * square-stealing which terminates in an as yet unclaimed
 146      * square. Hence every successful iteration around this loop
 147      * causes the number of unclaimed squares to drop by one, and
 148      * so the process is bounded in duration.
 149      */
 150     while (1) {
 151
 152 #ifdef DIVVY_DIAGNOSTICS
 153         {
 154             int x, y;
 155             printf("Top of loop. Current grid:\n");
 156             for (y = 0; y < h; y++) {
 157                 for (x = 0; x < w; x++)
 158                     printf("%3d", own[y*w+x]);
 159                 printf("\n");
 160             }
 161         }
 162 #endif
 163
 164         /*
 165          * Go over the grid and figure out which squares can
 166          * safely be added to, or removed from, each omino. We
 167          * don't take account of other ominoes in this process, so
 168          * we will often end up knowing that a square can be
 169          * poached from one omino by another.
 170          *
 171          * For each square, there may be up to four ominoes to
 172          * which it can be added (those to which it is
 173          * 4-adjacent).
 174          */
 175         for (y = 0; y < h; y++) {
 176             for (x = 0; x < w; x++) {
 177                 int yx = y*w+x;
 178                 int curr = own[yx];
 179                 int dir;
 180
 181                 if (curr < 0) {
 182                     removable[yx] = FALSE; /* can't remove if not owned! */
 183                 } else if (sizes[curr] == 1) {
 184                     removable[yx] = TRUE; /* can always remove a singleton */
 185                 } else {
 186                     /*
 187                      * See if this square can be removed from its
 188                      * omino without disconnecting it.
 189                      */
 190                     removable[yx] = addremcommon(w, h, x, y, own, curr);
 191                 }
 192
 193                 for (dir = 0; dir < 4; dir++) {
 194                     int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
 195                     int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
 196                     int sx = x + dx, sy = y + dy;
 197                     int syx = sy*w+sx;
 198
 199                     addable[yx*4+dir] = -1;
 200
 201                     if (sx < 0 || sx >= w || sy < 0 || sy >= h)
 202                         continue;      /* no omino here! */
 203                     if (own[syx] < 0)
 204                         continue;      /* also no omino here */
 205                     if (own[syx] == own[yx])
 206                         continue;      /* we already got one */
 207                     if (!addremcommon(w, h, x, y, own, own[syx]))
 208                         continue;      /* would non-simply connect the omino */
 209
 210                     addable[yx*4+dir] = own[syx];
 211                 }
 212             }
 213         }
 214
 215         for (i = j = 0; i < n; i++)
 216             if (sizes[i] < k)
 217                 tmp[j++] = i;
 218         if (j == 0)
 219             break;                     /* all ominoes are complete! */
 220         j = tmp[random_upto(rs, j)];
 221 #ifdef DIVVY_DIAGNOSTICS
 222         printf("Trying to extend %d\n", j);
 223 #endif
 224
 225         /*
 226          * So we're trying to expand omino j. We breadth-first
 227          * search out from j across the space of ominoes.
 228          *
 229          * For bfs purposes, we use two elements of tmp per omino:
 230          * tmp[2*i+0] tells us which omino we got to i from, and
 231          * tmp[2*i+1] numbers the grid square that omino stole
 232          * from us.
 233          *
 234          * This requires that wh (the size of tmp) is at least 2n,
 235          * i.e. k is at least 2. There would have been nothing to
 236          * stop a user calling this function with k=1, but if they
 237          * did then we wouldn't have got to _here_ in the code -
 238          * we would have noticed above that all ominoes were
 239          * already at their target sizes, and terminated :-)
 240          */
 241         assert(wh >= 2*n);
 242         for (i = 0; i < n; i++)
 243             tmp[2*i] = tmp[2*i+1] = -1;
 244         qhead = qtail = 0;
 245         queue[qtail++] = j;
 246         tmp[2*j] = tmp[2*j+1] = -2;    /* special value: `starting point' */
 247
 248         while (qhead < qtail) {
 249             int tmpsq;
 250
 251             j = queue[qhead];
 252
 253             /*
 254              * We wish to expand omino j. However, we might have
 255              * got here by omino j having a square stolen from it,
 256              * so first of all we must temporarily mark that
 257              * square as not belonging to j, so that our adjacency
 258              * calculations don't assume j _does_ belong to us.
 259              */
 260             tmpsq = tmp[2*j+1];
 261             if (tmpsq >= 0) {
 262                 assert(own[tmpsq] == j);
 263                 own[tmpsq] = -3;
 264             }
 265
 266             /*
 267              * OK. Now begin by seeing if we can find any
 268              * unclaimed square into which we can expand omino j.
 269              * If we find one, the entire bfs terminates.
 270              */
 271             for (i = 0; i < wh; i++) {
 272                 int dir;
 273
 274                 if (own[order[i]] != -1)
 275                     continue;          /* this square is claimed */
 276
 277                 /*
 278                  * Special case: if our current omino was size 1
 279                  * and then had a square stolen from it, it's now
 280                  * size zero, which means it's valid to `expand'
 281                  * it into _any_ unclaimed square.
 282                  */
 283                 if (sizes[j] == 1 && tmpsq >= 0)
 284                     break;             /* got one */
 285
 286                 /*
 287                  * Failing that, we must do the full test for
 288                  * addability.
 289                  */
 290                 for (dir = 0; dir < 4; dir++)
 291                     if (addable[order[i]*4+dir] == j) {
 292                         /*
 293                          * We know this square is addable to this
 294                          * omino with the grid in the state it had
 295                          * at the top of the loop. However, we
 296                          * must now check that it's _still_
 297                          * addable to this omino when the omino is
 298                          * missing a square. To do this it's only
 299                          * necessary to re-check addremcommon.
 300                          */
 301                         if (!addremcommon(w, h, order[i]%w, order[i]/w,
 302                                           own, j))
 303                             continue;
 304                         break;
 305                     }
 306                 if (dir == 4)
 307                     continue;          /* we can't add this square to j */
 308
 309                 break;                 /* got one! */
 310             }
 311             if (i < wh) {
 312                 i = order[i];
 313
 314                 /*
 315                  * Restore the temporarily removed square _before_
 316                  * we start shifting ownerships about.
 317                  */
 318                 if (tmpsq >= 0)
 319                     own[tmpsq] = j;
 320
 321                 /*
 322                  * We are done. We can add square i to omino j,
 323                  * and then backtrack along the trail in tmp
 324                  * moving squares between ominoes, ending up
 325                  * expanding our starting omino by one.
 326                  */
 327 #ifdef DIVVY_DIAGNOSTICS
 328                 printf("(%d,%d)", i%w, i/w);
 329 #endif
 330                 while (1) {
 331                     own[i] = j;
 332 #ifdef DIVVY_DIAGNOSTICS
 333                     printf(" -> %d", j);
 334 #endif
 335                     if (tmp[2*j] == -2)
 336                         break;
 337                     i = tmp[2*j+1];
 338                     j = tmp[2*j];
 339 #ifdef DIVVY_DIAGNOSTICS
 340                     printf("; (%d,%d)", i%w, i/w);
 341 #endif
 342                 }
 343 #ifdef DIVVY_DIAGNOSTICS
 344                 printf("\n");
 345 #endif
 346
 347                 /*
 348                  * Increment the size of the starting omino.
 349                  */
 350                 sizes[j]++;
 351
 352                 /*
 353                  * Terminate the bfs loop.
 354                  */
 355                 break;
 356             }
 357
 358             /*
 359              * If we get here, we haven't been able to expand
 360              * omino j into an unclaimed square. So now we begin
 361              * to investigate expanding it into squares which are
 362              * claimed by ominoes the bfs has not yet visited.
 363              */
 364             for (i = 0; i < wh; i++) {
 365                 int dir, nj;
 366
 367                 nj = own[order[i]];
 368                 if (nj < 0 || tmp[2*nj] != -1)
 369                     continue;          /* unclaimed, or owned by wrong omino */
 370                 if (!removable[order[i]])
 371                     continue;          /* its omino won't let it go */
 372
 373                 for (dir = 0; dir < 4; dir++)
 374                     if (addable[order[i]*4+dir] == j) {
 375                         /*
 376                          * As above, re-check addremcommon.
 377                          */
 378                         if (!addremcommon(w, h, order[i]%w, order[i]/w,
 379                                           own, j))
 380                             continue;
 381
 382                         /*
 383                          * We have found a square we can use to
 384                          * expand omino j, at the expense of the
 385                          * as-yet unvisited omino nj. So add this
 386                          * to the bfs queue.
 387                          */
 388                         assert(qtail < n);
 389                         queue[qtail++] = nj;
 390                         tmp[2*nj] = j;
 391                         tmp[2*nj+1] = order[i];
 392
 393                         /*
 394                          * Now terminate the loop over dir, to
 395                          * ensure we don't accidentally add the
 396                          * same omino twice to the queue.
 397                          */
 398                         break;
 399                     }
 400             }
 401
 402             /*
 403              * Restore the temporarily removed square.
 404              */
 405             if (tmpsq >= 0)
 406                 own[tmpsq] = j;
 407
 408             /*
 409              * Advance the queue head.
 410              */
 411             qhead++;
 412         }
 413
 414         if (qhead == qtail) {
 415             /*
 416              * We have finished the bfs and not found any way to
 417              * expand omino j. Panic, and return failure.
 418              *
 419              * FIXME: or should we loop over all ominoes before we
 420              * give up?
 421              */
 422 #ifdef DIVVY_DIAGNOSTICS
 423             printf("FAIL!\n");
 424 #endif
 425             retdsf = NULL;
 426             goto cleanup;
 427         }
 428     }
 429
 430 #ifdef DIVVY_DIAGNOSTICS
 431     {
 432         int x, y;
 433         printf("SUCCESS! Final grid:\n");
 434         for (y = 0; y < h; y++) {
 435             for (x = 0; x < w; x++)
 436                 printf("%3d", own[y*w+x]);
 437             printf("\n");
 438         }
 439     }
 440 #endif
 441
 442     /*
 443      * Construct the output dsf.
 444      */
 445     for (i = 0; i < wh; i++) {
 446         assert(own[i] >= 0 && own[i] < n);
 447         tmp[own[i]] = i;
 448     }
 449     retdsf = snew_dsf(wh);
 450     for (i = 0; i < wh; i++) {
 451         dsf_merge(retdsf, i, tmp[own[i]]);
 452     }
 453
 454     /*
 455      * Construct the output dsf a different way, to verify that
 456      * the ominoes really are k-ominoes and we haven't
 457      * accidentally split one into two disconnected pieces.
 458      */
 459     dsf_init(tmp, wh);
 460     for (y = 0; y < h; y++)
 461         for (x = 0; x+1 < w; x++)
 462             if (own[y*w+x] == own[y*w+(x+1)])
 463                 dsf_merge(tmp, y*w+x, y*w+(x+1));
 464     for (x = 0; x < w; x++)
 465         for (y = 0; y+1 < h; y++)
 466             if (own[y*w+x] == own[(y+1)*w+x])
 467                 dsf_merge(tmp, y*w+x, (y+1)*w+x);
 468     for (i = 0; i < wh; i++) {
 469         j = dsf_canonify(retdsf, i);
 470         assert(dsf_canonify(tmp, j) == dsf_canonify(tmp, i));
 471     }
 472
 473     cleanup:
 474
 475     /*
 476      * Free our temporary working space.
 477      */
 478     sfree(order);
 479     sfree(tmp);
 480     sfree(own);
 481     sfree(sizes);
 482     sfree(queue);
 483     sfree(addable);
 484     sfree(removable);
 485
 486     /*
 487      * And we're done.
 488      */
 489     return retdsf;
 490 }
 491
 492 #ifdef TESTMODE
 493 static int fail_counter = 0;
 494 #endif
 495
 496 int *divvy_rectangle(int w, int h, int k, random_state *rs)
 497 {
 498     int *ret;
 499
 500     do {
 501         ret = divvy_internal(w, h, k, rs);
 502
 503 #ifdef TESTMODE
 504         if (!ret)
 505             fail_counter++;
 506 #endif
 507
 508     } while (!ret);
 509
 510     return ret;
 511 }
 512
 513 #ifdef TESTMODE
 514
 515 /*
 516  * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
 517  *
 518  * or to debug
 519  *
 520  * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
 521  */
 522
 523 int main(int argc, char **argv)
 524 {
 525     int *dsf;
 526     int i;
 527     int w = 9, h = 4, k = 6, tries = 100;
 528     random_state *rs;
 529
 530     rs = random_new("123456", 6);
 531
 532     if (argc > 1)
 533         w = atoi(argv[1]);
 534     if (argc > 2)
 535         h = atoi(argv[2]);
 536     if (argc > 3)
 537         k = atoi(argv[3]);
 538     if (argc > 4)
 539         tries = atoi(argv[4]);
 540
 541     for (i = 0; i < tries; i++) {
 542         int x, y;
 543
 544         dsf = divvy_rectangle(w, h, k, rs);
 545         assert(dsf);
 546
 547         for (y = 0; y <= 2*h; y++) {
 548             for (x = 0; x <= 2*w; x++) {
 549                 int miny = y/2 - 1, maxy = y/2;
 550                 int minx = x/2 - 1, maxx = x/2;
 551                 int classes[4], tx, ty;
 552                 for (ty = 0; ty < 2; ty++)
 553                     for (tx = 0; tx < 2; tx++) {
 554                         int cx = minx+tx, cy = miny+ty;
 555                         if (cx < 0 || cx >= w || cy < 0 || cy >= h)
 556                             classes[ty*2+tx] = -1;
 557                         else
 558                             classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx);
 559                     }
 560                 switch (y%2 * 2 + x%2) {
 561                   case 0:              /* corner */
 562                     /*
 563                      * Cases for the corner:
 564                      *
 565                      *  - if all four surrounding squares belong
 566                      *    to the same omino, we print a space.
 567                      *
 568                      *  - if the top two are the same and the
 569                      *    bottom two are the same, we print a
 570                      *    horizontal line.
 571                      *
 572                      *  - if the left two are the same and the
 573                      *    right two are the same, we print a
 574                      *    vertical line.
 575                      *
 576                      *  - otherwise, we print a cross.
 577                      */
 578                     if (classes[0] == classes[1] &&
 579                         classes[1] == classes[2] &&
 580                         classes[2] == classes[3])
 581                         printf(" ");
 582                     else if (classes[0] == classes[1] &&
 583                              classes[2] == classes[3])
 584                         printf("-");
 585                     else if (classes[0] == classes[2] &&
 586                              classes[1] == classes[3])
 587                         printf("|");
 588                     else
 589                         printf("+");
 590                     break;
 591                   case 1:              /* horiz edge */
 592                     if (classes[1] == classes[3])
 593                         printf("  ");
 594                     else
 595                         printf("--");
 596                     break;
 597                   case 2:              /* vert edge */
 598                     if (classes[2] == classes[3])
 599                         printf(" ");
 600                     else
 601                         printf("|");
 602                     break;
 603                   case 3:              /* square centre */
 604                     printf("  ");
 605                     break;
 606                 }
 607             }
 608             printf("\n");
 609         }
 610         printf("\n");
 611         sfree(dsf);
 612     }
 613
 614     printf("%d retries needed for %d successes\n", fail_counter, tries);
 615
 616     return 0;
 617 }
 618
 619 #endif