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