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  * This code is restricted to simply connected solutions: that is,
  12  * no single polyomino may completely surround another (not even
  13  * with a corner visible to the outside world, in the sense that a
  14  * 7-omino can `surround' a single square).
  15  *
  16  * It's tempting to think that this is a natural consequence of
  17  * all the ominoes being the same size - after all, a division of
  18  * anything into 7-ominoes must necessarily have all of them
  19  * simply connected, because if one was not then the 1-square
  20  * space in the middle could not be part of any 7-omino - but in
  21  * fact, for sufficiently large k, it is perfectly possible for a
  22  * k-omino to completely surround another k-omino. A simple
  23  * example is this one with two 25-ominoes:
  24  *
  25  *   +--+--+--+--+--+--+--+
  26  *   |                    |
  27  *   +  +--+--+--+--+--+  +
  28  *   |  |              |  |
  29  *   +  +              +  +
  30  *   |  |              |  |
  31  *   +  +              +  +--+
  32  *   |  |              |     |
  33  *   +  +              +  +--+
  34  *   |  |              |  |
  35  *   +  +              +  +
  36  *   |  |              |  |
  37  *   +  +--+--+--+--+--+  +
  38  *   |                    |
  39  *   +--+--+--+--+--+--+--+
  40  *
  41  * I claim the smallest k which can manage this is 23. More
  42  * formally:
  43  *
  44  *   If a k-omino P is completely surrounded by another k-omino Q,
  45  *   such that every edge of P borders on Q, then k >= 23.
  46  *
  47  * Proof:
  48  *
  49  * It's relatively simple to find the largest _rectangle_ a
  50  * k-omino can enclose. So I'll construct my proof in two parts:
  51  * firstly, show that no 22-omino or smaller can enclose a
  52  * rectangle as large as itself, and secondly, show that no
  53  * polyomino can enclose a larger non-rectangle than a rectangle.
  54  *
  55  * The first of those claims:
  56  *
  57  * To surround an m x n rectangle, a polyomino must have 2m
  58  * squares along the two m-sides of the rectangle, 2n squares
  59  * along the two n-sides, and must fill in at least three of the
  60  * corners in order to be connected. Thus, 2(m+n)+3 <= k. We wish
  61  * to find the largest value of mn subject to that constraint, and
  62  * it's clear that this is achieved when m and n are as close to
  63  * equal as possible. (If they aren't, WLOG suppose m < n; then
  64  * (m+1)(n-1) = mn + n - m - 1 >= mn, with equality only when
  65  * m=n-1.)
  66  *
  67  * So the area of the largest rectangle which can be enclosed by a
  68  * k-omino is given by floor(k'/2) * ceil(k'/2), where k' =
  69  * (k-3)/2. This is a monotonic function in k, so there will be a
  70  * unique point at which it goes from being smaller than k to
  71  * being larger than k. That point is between 22 (maximum area 20)
  72  * and 23 (maximum area 25).
  73  *
  74  * The second claim:
  75  *
  76  * Suppose we have an inner polyomino P surrounded by an outer
  77  * polyomino Q. I seek to show that if P is non-rectangular, then
  78  * P is also non-maximal, in the sense that we can transform P and
  79  * Q into a new pair of polyominoes in which P is larger and Q is
  80  * at most the same size.
  81  *
  82  * Consider walking along the boundary of P in a clockwise
  83  * direction. (We may assume, of course, that there is only _one_
  84  * boundary of P, i.e. P has no hole in the middle. If it does
  85  * have a hole in the middle, it's _trivially_ non-maximal because
  86  * we can just fill the hole in!) Our walk will take us along many
  87  * edges between squares; sometimes we might turn left, and
  88  * certainly sometimes we will turn right. Always there will be a
  89  * square of P on our right, and a square of Q on our left.
  90  *
  91  * The net angle through which we turn during the entire walk must
  92  * add up to 360 degrees rightwards. So if there are no left
  93  * turns, then we must turn right exactly four times, meaning we
  94  * have described a rectangle. Hence, if P is _not_ rectangular,
  95  * then there must have been a left turn at some point. A left
  96  * turn must mean we walk along two edges of the same square of Q.
  97  *
  98  * Thus, there is some square X in Q which is adjacent to two
  99  * diagonally separated squares in P. Let us call those two
 100  * squares N and E; let us refer to the other two neighbours of X
 101  * as S and W; let us refer to the other mutual neighbour of S and
 102  * W as D; and let us refer to the other mutual neighbour of S and
 103  * E as Y. In other words, we have named seven squares, arranged
 104  * thus:
 105  *
 106  *     N
 107  *   W X E
 108  *   D S Y
 109  *
 110  * where N and E are in P, and X is in Q.
 111  *
 112  * Clearly at least one of W and S must be in Q (because otherwise
 113  * X would not be connected to any other square in Q, and would
 114  * hence have to be the whole of Q; and evidently if Q were a
 115  * 1-omino it could not enclose _anything_). So we divide into
 116  * cases:
 117  *
 118  * If both W and S are in Q, then we take X out of Q and put it in
 119  * P, which does not expose any edge of P. If this disconnects Q,
 120  * then we can reconnect it by adding D to Q.
 121  *
 122  * If only one of W and S is in Q, then wlog let it be W. If S is
 123  * in _P_, then we have a particularly easy case: we can simply
 124  * take X out of Q and add it to P, and this cannot disconnect X
 125  * since X was a leaf square of Q.
 126  *
 127  * Our remaining case is that W is in Q and S is in neither P nor
 128  * Q. Again we take X out of Q and put it in P; we also add S to
 129  * Q. This ensures we do not expose an edge of P, but we must now
 130  * prove that S is adjacent to some other existing square of Q so
 131  * that we haven't disconnected Q by adding it.
 132  *
 133  * To do this, we recall that we walked along the edge XE, and
 134  * then turned left to walk along XN. So just before doing all
 135  * that, we must have reached the corner XSE, and we must have
 136  * done it by walking along one of the three edges meeting at that
 137  * corner which are _not_ XE. It can't have been SY, since S would
 138  * then have been on our left and it isn't in Q; and it can't have
 139  * been XS, since S would then have been on our right and it isn't
 140  * in P. So it must have been YE, in which case Y was on our left,
 141  * and hence is in Q.
 142  *
 143  * So in all cases we have shown that we can take X out of Q and
 144  * add it to P, and add at most one square to Q to restore the
 145  * containment and connectedness properties. Hence, we can keep
 146  * doing this until we run out of left turns and P becomes
 147  * rectangular. []
 148  *
 149  * ------------
 150  *
 151  * Anyway, that entire proof was a bit of a sidetrack. The point
 152  * is, although constructions of this type are possible for
 153  * sufficiently large k, divvy_rectangle() will never generate
 154  * them. This could be considered a weakness for some purposes, in
 155  * the sense that we can't generate all possible divisions.
 156  * However, there are many divisions which we are highly unlikely
 157  * to generate anyway, so in practice it probably isn't _too_ bad.
 158  *
 159  * If I wanted to fix this issue, I would have to make the rules
 160  * more complicated for determining when a square can safely be
 161  * _removed_ from a polyomino. Adding one becomes easier (a square
 162  * may be added to a polyomino iff it is 4-adjacent to any square
 163  * currently part of the polyomino, and the current test for loop
 164  * formation may be dispensed with), but to determine which
 165  * squares may be removed we must now resort to analysis of the
 166  * overall structure of the polyomino rather than the simple local
 167  * properties we can currently get away with measuring.
 168  */
 169
 170 /*
 171  * Possible improvements which might cut the fail rate:
 172  *
 173  *  - instead of picking one omino to extend in an iteration, try
 174  *    them all in succession (in a randomised order)
 175  *
 176  *  - (for real rigour) instead of bfsing over ominoes, bfs over
 177  *    the space of possible _removed squares_. That way we aren't
 178  *    limited to randomly choosing a single square to remove from
 179  *    an omino and failing if that particular square doesn't
 180  *    happen to work.
 181  *
 182  * However, I don't currently think it's necessary to do either of
 183  * these, because the failure rate is already low enough to be
 184  * easily tolerable, under all circumstances I've been able to
 185  * think of.
 186  */
 187
 188 #include <assert.h>
 189 #include <stdio.h>
 190 #include <stdlib.h>
 191 #include <stddef.h>
 192
 193 #include "puzzles.h"
 194
 195 /*
 196  * Subroutine which implements a function used in computing both
 197  * whether a square can safely be added to an omino, and whether
 198  * it can safely be removed.
 199  *
 200  * We enumerate the eight squares 8-adjacent to this one, in
 201  * cyclic order. We go round that loop and count the number of
 202  * times we find a square owned by the target omino next to one
 203  * not owned by it. We then return success iff that count is 2.
 204  *
 205  * When adding a square to an omino, this is precisely the
 206  * criterion which tells us that adding the square won't leave a
 207  * hole in the middle of the omino. (If it did, then things get
 208  * more complicated; see above.)
 209  *
 210  * When removing a square from an omino, the _same_ criterion
 211  * tells us that removing the square won't disconnect the omino.
 212  * (This only works _because_ we've ensured the omino is simply
 213  * connected.)
 214  */
 215 static int addremcommon(int w, int h, int x, int y, int *own, int val)
 216 {
 217     int neighbours[8];
 218     int dir, count;
 219
 220     for (dir = 0; dir < 8; dir++) {
 221         int dx = ((dir & 3) == 2 ? 0 : dir > 2 && dir < 6 ? +1 : -1);
 222         int dy = ((dir & 3) == 0 ? 0 : dir < 4 ? -1 : +1);
 223         int sx = x+dx, sy = y+dy;
 224
 225         if (sx < 0 || sx >= w || sy < 0 || sy >= h)
 226             neighbours[dir] = -1;      /* outside the grid */
 227         else
 228             neighbours[dir] = own[sy*w+sx];
 229     }
 230
 231     /*
 232      * To begin with, check 4-adjacency.
 233      */
 234     if (neighbours[0] != val && neighbours[2] != val &&
 235         neighbours[4] != val && neighbours[6] != val)
 236         return FALSE;
 237
 238     count = 0;
 239
 240     for (dir = 0; dir < 8; dir++) {
 241         int next = (dir + 1) & 7;
 242         int gotthis = (neighbours[dir] == val);
 243         int gotnext = (neighbours[next] == val);
 244
 245         if (gotthis != gotnext)
 246             count++;
 247     }
 248
 249     return (count == 2);
 250 }
 251
 252 /*
 253  * w and h are the dimensions of the rectangle.
 254  *
 255  * k is the size of the required ominoes. (So k must divide w*h,
 256  * of course.)
 257  *
 258  * The returned result is a w*h-sized dsf.
 259  *
 260  * In both of the above suggested use cases, the user would
 261  * probably want w==h==k, but that isn't a requirement.
 262  */
 263 static int *divvy_internal(int w, int h, int k, random_state *rs)
 264 {
 265     int *order, *queue, *tmp, *own, *sizes, *addable, *removable, *retdsf;
 266     int wh = w*h;
 267     int i, j, n, x, y, qhead, qtail;
 268
 269     n = wh / k;
 270     assert(wh == k*n);
 271
 272     order = snewn(wh, int);
 273     tmp = snewn(wh, int);
 274     own = snewn(wh, int);
 275     sizes = snewn(n, int);
 276     queue = snewn(n, int);
 277     addable = snewn(wh*4, int);
 278     removable = snewn(wh, int);
 279
 280     /*
 281      * Permute the grid squares into a random order, which will be
 282      * used for iterating over the grid whenever we need to search
 283      * for something. This prevents directional bias and arranges
 284      * for the answer to be non-deterministic.
 285      */
 286     for (i = 0; i < wh; i++)
 287         order[i] = i;
 288     shuffle(order, wh, sizeof(*order), rs);
 289
 290     /*
 291      * Begin by choosing a starting square at random for each
 292      * omino.
 293      */
 294     for (i = 0; i < wh; i++) {
 295         own[i] = -1;
 296     }
 297     for (i = 0; i < n; i++) {
 298         own[order[i]] = i;
 299         sizes[i] = 1;
 300     }
 301
 302     /*
 303      * Now repeatedly pick a random omino which isn't already at
 304      * the target size, and find a way to expand it by one. This
 305      * may involve stealing a square from another omino, in which
 306      * case we then re-expand that omino, forming a chain of
 307      * square-stealing which terminates in an as yet unclaimed
 308      * square. Hence every successful iteration around this loop
 309      * causes the number of unclaimed squares to drop by one, and
 310      * so the process is bounded in duration.
 311      */
 312     while (1) {
 313
 314 #ifdef DIVVY_DIAGNOSTICS
 315         {
 316             int x, y;
 317             printf("Top of loop. Current grid:\n");
 318             for (y = 0; y < h; y++) {
 319                 for (x = 0; x < w; x++)
 320                     printf("%3d", own[y*w+x]);
 321                 printf("\n");
 322             }
 323         }
 324 #endif
 325
 326         /*
 327          * Go over the grid and figure out which squares can
 328          * safely be added to, or removed from, each omino. We
 329          * don't take account of other ominoes in this process, so
 330          * we will often end up knowing that a square can be
 331          * poached from one omino by another.
 332          *
 333          * For each square, there may be up to four ominoes to
 334          * which it can be added (those to which it is
 335          * 4-adjacent).
 336          */
 337         for (y = 0; y < h; y++) {
 338             for (x = 0; x < w; x++) {
 339                 int yx = y*w+x;
 340                 int curr = own[yx];
 341                 int dir;
 342
 343                 if (curr < 0) {
 344                     removable[yx] = FALSE; /* can't remove if not owned! */
 345                 } else if (sizes[curr] == 1) {
 346                     removable[yx] = TRUE; /* can always remove a singleton */
 347                 } else {
 348                     /*
 349                      * See if this square can be removed from its
 350                      * omino without disconnecting it.
 351                      */
 352                     removable[yx] = addremcommon(w, h, x, y, own, curr);
 353                 }
 354
 355                 for (dir = 0; dir < 4; dir++) {
 356                     int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
 357                     int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
 358                     int sx = x + dx, sy = y + dy;
 359                     int syx = sy*w+sx;
 360
 361                     addable[yx*4+dir] = -1;
 362
 363                     if (sx < 0 || sx >= w || sy < 0 || sy >= h)
 364                         continue;      /* no omino here! */
 365                     if (own[syx] < 0)
 366                         continue;      /* also no omino here */
 367                     if (own[syx] == own[yx])
 368                         continue;      /* we already got one */
 369                     if (!addremcommon(w, h, x, y, own, own[syx]))
 370                         continue;      /* would non-simply connect the omino */
 371
 372                     addable[yx*4+dir] = own[syx];
 373                 }
 374             }
 375         }
 376
 377         for (i = j = 0; i < n; i++)
 378             if (sizes[i] < k)
 379                 tmp[j++] = i;
 380         if (j == 0)
 381             break;                     /* all ominoes are complete! */
 382         j = tmp[random_upto(rs, j)];
 383 #ifdef DIVVY_DIAGNOSTICS
 384         printf("Trying to extend %d\n", j);
 385 #endif
 386
 387         /*
 388          * So we're trying to expand omino j. We breadth-first
 389          * search out from j across the space of ominoes.
 390          *
 391          * For bfs purposes, we use two elements of tmp per omino:
 392          * tmp[2*i+0] tells us which omino we got to i from, and
 393          * tmp[2*i+1] numbers the grid square that omino stole
 394          * from us.
 395          *
 396          * This requires that wh (the size of tmp) is at least 2n,
 397          * i.e. k is at least 2. There would have been nothing to
 398          * stop a user calling this function with k=1, but if they
 399          * did then we wouldn't have got to _here_ in the code -
 400          * we would have noticed above that all ominoes were
 401          * already at their target sizes, and terminated :-)
 402          */
 403         assert(wh >= 2*n);
 404         for (i = 0; i < n; i++)
 405             tmp[2*i] = tmp[2*i+1] = -1;
 406         qhead = qtail = 0;
 407         queue[qtail++] = j;
 408         tmp[2*j] = tmp[2*j+1] = -2;    /* special value: `starting point' */
 409
 410         while (qhead < qtail) {
 411             int tmpsq;
 412
 413             j = queue[qhead];
 414
 415             /*
 416              * We wish to expand omino j. However, we might have
 417              * got here by omino j having a square stolen from it,
 418              * so first of all we must temporarily mark that
 419              * square as not belonging to j, so that our adjacency
 420              * calculations don't assume j _does_ belong to us.
 421              */
 422             tmpsq = tmp[2*j+1];
 423             if (tmpsq >= 0) {
 424                 assert(own[tmpsq] == j);
 425                 own[tmpsq] = -3;
 426             }
 427
 428             /*
 429              * OK. Now begin by seeing if we can find any
 430              * unclaimed square into which we can expand omino j.
 431              * If we find one, the entire bfs terminates.
 432              */
 433             for (i = 0; i < wh; i++) {
 434                 int dir;
 435
 436                 if (own[order[i]] != -1)
 437                     continue;          /* this square is claimed */
 438
 439                 /*
 440                  * Special case: if our current omino was size 1
 441                  * and then had a square stolen from it, it's now
 442                  * size zero, which means it's valid to `expand'
 443                  * it into _any_ unclaimed square.
 444                  */
 445                 if (sizes[j] == 1 && tmpsq >= 0)
 446                     break;             /* got one */
 447
 448                 /*
 449                  * Failing that, we must do the full test for
 450                  * addability.
 451                  */
 452                 for (dir = 0; dir < 4; dir++)
 453                     if (addable[order[i]*4+dir] == j) {
 454                         /*
 455                          * We know this square is addable to this
 456                          * omino with the grid in the state it had
 457                          * at the top of the loop. However, we
 458                          * must now check that it's _still_
 459                          * addable to this omino when the omino is
 460                          * missing a square. To do this it's only
 461                          * necessary to re-check addremcommon.
 462                          */
 463                         if (!addremcommon(w, h, order[i]%w, order[i]/w,
 464                                           own, j))
 465                             continue;
 466                         break;
 467                     }
 468                 if (dir == 4)
 469                     continue;          /* we can't add this square to j */
 470
 471                 break;                 /* got one! */
 472             }
 473             if (i < wh) {
 474                 i = order[i];
 475
 476                 /*
 477                  * Restore the temporarily removed square _before_
 478                  * we start shifting ownerships about.
 479                  */
 480                 if (tmpsq >= 0)
 481                     own[tmpsq] = j;
 482
 483                 /*
 484                  * We are done. We can add square i to omino j,
 485                  * and then backtrack along the trail in tmp
 486                  * moving squares between ominoes, ending up
 487                  * expanding our starting omino by one.
 488                  */
 489 #ifdef DIVVY_DIAGNOSTICS
 490                 printf("(%d,%d)", i%w, i/w);
 491 #endif
 492                 while (1) {
 493                     own[i] = j;
 494 #ifdef DIVVY_DIAGNOSTICS
 495                     printf(" -> %d", j);
 496 #endif
 497                     if (tmp[2*j] == -2)
 498                         break;
 499                     i = tmp[2*j+1];
 500                     j = tmp[2*j];
 501 #ifdef DIVVY_DIAGNOSTICS
 502                     printf("; (%d,%d)", i%w, i/w);
 503 #endif
 504                 }
 505 #ifdef DIVVY_DIAGNOSTICS
 506                 printf("\n");
 507 #endif
 508
 509                 /*
 510                  * Increment the size of the starting omino.
 511                  */
 512                 sizes[j]++;
 513
 514                 /*
 515                  * Terminate the bfs loop.
 516                  */
 517                 break;
 518             }
 519
 520             /*
 521              * If we get here, we haven't been able to expand
 522              * omino j into an unclaimed square. So now we begin
 523              * to investigate expanding it into squares which are
 524              * claimed by ominoes the bfs has not yet visited.
 525              */
 526             for (i = 0; i < wh; i++) {
 527                 int dir, nj;
 528
 529                 nj = own[order[i]];
 530                 if (nj < 0 || tmp[2*nj] != -1)
 531                     continue;          /* unclaimed, or owned by wrong omino */
 532                 if (!removable[order[i]])
 533                     continue;          /* its omino won't let it go */
 534
 535                 for (dir = 0; dir < 4; dir++)
 536                     if (addable[order[i]*4+dir] == j) {
 537                         /*
 538                          * As above, re-check addremcommon.
 539                          */
 540                         if (!addremcommon(w, h, order[i]%w, order[i]/w,
 541                                           own, j))
 542                             continue;
 543
 544                         /*
 545                          * We have found a square we can use to
 546                          * expand omino j, at the expense of the
 547                          * as-yet unvisited omino nj. So add this
 548                          * to the bfs queue.
 549                          */
 550                         assert(qtail < n);
 551                         queue[qtail++] = nj;
 552                         tmp[2*nj] = j;
 553                         tmp[2*nj+1] = order[i];
 554
 555                         /*
 556                          * Now terminate the loop over dir, to
 557                          * ensure we don't accidentally add the
 558                          * same omino twice to the queue.
 559                          */
 560                         break;
 561                     }
 562             }
 563
 564             /*
 565              * Restore the temporarily removed square.
 566              */
 567             if (tmpsq >= 0)
 568                 own[tmpsq] = j;
 569
 570             /*
 571              * Advance the queue head.
 572              */
 573             qhead++;
 574         }
 575
 576         if (qhead == qtail) {
 577             /*
 578              * We have finished the bfs and not found any way to
 579              * expand omino j. Panic, and return failure.
 580              *
 581              * FIXME: or should we loop over all ominoes before we
 582              * give up?
 583              */
 584 #ifdef DIVVY_DIAGNOSTICS
 585             printf("FAIL!\n");
 586 #endif
 587             retdsf = NULL;
 588             goto cleanup;
 589         }
 590     }
 591
 592 #ifdef DIVVY_DIAGNOSTICS
 593     {
 594         int x, y;
 595         printf("SUCCESS! Final grid:\n");
 596         for (y = 0; y < h; y++) {
 597             for (x = 0; x < w; x++)
 598                 printf("%3d", own[y*w+x]);
 599             printf("\n");
 600         }
 601     }
 602 #endif
 603
 604     /*
 605      * Construct the output dsf.
 606      */
 607     for (i = 0; i < wh; i++) {
 608         assert(own[i] >= 0 && own[i] < n);
 609         tmp[own[i]] = i;
 610     }
 611     retdsf = snew_dsf(wh);
 612     for (i = 0; i < wh; i++) {
 613         dsf_merge(retdsf, i, tmp[own[i]]);
 614     }
 615
 616     /*
 617      * Construct the output dsf a different way, to verify that
 618      * the ominoes really are k-ominoes and we haven't
 619      * accidentally split one into two disconnected pieces.
 620      */
 621     dsf_init(tmp, wh);
 622     for (y = 0; y < h; y++)
 623         for (x = 0; x+1 < w; x++)
 624             if (own[y*w+x] == own[y*w+(x+1)])
 625                 dsf_merge(tmp, y*w+x, y*w+(x+1));
 626     for (x = 0; x < w; x++)
 627         for (y = 0; y+1 < h; y++)
 628             if (own[y*w+x] == own[(y+1)*w+x])
 629                 dsf_merge(tmp, y*w+x, (y+1)*w+x);
 630     for (i = 0; i < wh; i++) {
 631         j = dsf_canonify(retdsf, i);
 632         assert(dsf_canonify(tmp, j) == dsf_canonify(tmp, i));
 633     }
 634
 635     cleanup:
 636
 637     /*
 638      * Free our temporary working space.
 639      */
 640     sfree(order);
 641     sfree(tmp);
 642     sfree(own);
 643     sfree(sizes);
 644     sfree(queue);
 645     sfree(addable);
 646     sfree(removable);
 647
 648     /*
 649      * And we're done.
 650      */
 651     return retdsf;
 652 }
 653
 654 #ifdef TESTMODE
 655 static int fail_counter = 0;
 656 #endif
 657
 658 int *divvy_rectangle(int w, int h, int k, random_state *rs)
 659 {
 660     int *ret;
 661
 662     do {
 663         ret = divvy_internal(w, h, k, rs);
 664
 665 #ifdef TESTMODE
 666         if (!ret)
 667             fail_counter++;
 668 #endif
 669
 670     } while (!ret);
 671
 672     return ret;
 673 }
 674
 675 #ifdef TESTMODE
 676
 677 /*
 678  * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
 679  *
 680  * or to debug
 681  *
 682  * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
 683  */
 684
 685 int main(int argc, char **argv)
 686 {
 687     int *dsf;
 688     int i;
 689     int w = 9, h = 4, k = 6, tries = 100;
 690     random_state *rs;
 691
 692     rs = random_new("123456", 6);
 693
 694     if (argc > 1)
 695         w = atoi(argv[1]);
 696     if (argc > 2)
 697         h = atoi(argv[2]);
 698     if (argc > 3)
 699         k = atoi(argv[3]);
 700     if (argc > 4)
 701         tries = atoi(argv[4]);
 702
 703     for (i = 0; i < tries; i++) {
 704         int x, y;
 705
 706         dsf = divvy_rectangle(w, h, k, rs);
 707         assert(dsf);
 708
 709         for (y = 0; y <= 2*h; y++) {
 710             for (x = 0; x <= 2*w; x++) {
 711                 int miny = y/2 - 1, maxy = y/2;
 712                 int minx = x/2 - 1, maxx = x/2;
 713                 int classes[4], tx, ty;
 714                 for (ty = 0; ty < 2; ty++)
 715                     for (tx = 0; tx < 2; tx++) {
 716                         int cx = minx+tx, cy = miny+ty;
 717                         if (cx < 0 || cx >= w || cy < 0 || cy >= h)
 718                             classes[ty*2+tx] = -1;
 719                         else
 720                             classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx);
 721                     }
 722                 switch (y%2 * 2 + x%2) {
 723                   case 0:              /* corner */
 724                     /*
 725                      * Cases for the corner:
 726                      *
 727                      *  - if all four surrounding squares belong
 728                      *    to the same omino, we print a space.
 729                      *
 730                      *  - if the top two are the same and the
 731                      *    bottom two are the same, we print a
 732                      *    horizontal line.
 733                      *
 734                      *  - if the left two are the same and the
 735                      *    right two are the same, we print a
 736                      *    vertical line.
 737                      *
 738                      *  - otherwise, we print a cross.
 739                      */
 740                     if (classes[0] == classes[1] &&
 741                         classes[1] == classes[2] &&
 742                         classes[2] == classes[3])
 743                         printf(" ");
 744                     else if (classes[0] == classes[1] &&
 745                              classes[2] == classes[3])
 746                         printf("-");
 747                     else if (classes[0] == classes[2] &&
 748                              classes[1] == classes[3])
 749                         printf("|");
 750                     else
 751                         printf("+");
 752                     break;
 753                   case 1:              /* horiz edge */
 754                     if (classes[1] == classes[3])
 755                         printf("  ");
 756                     else
 757                         printf("--");
 758                     break;
 759                   case 2:              /* vert edge */
 760                     if (classes[2] == classes[3])
 761                         printf(" ");
 762                     else
 763                         printf("|");
 764                     break;
 765                   case 3:              /* square centre */
 766                     printf("  ");
 767                     break;
 768                 }
 769             }
 770             printf("\n");
 771         }
 772         printf("\n");
 773         sfree(dsf);
 774     }
 775
 776     printf("%d retries needed for %d successes\n", fail_counter, tries);
 777
 778     return 0;
 779 }
 780
 781 #endif