laydomino.c

   1 /*
   2  * laydomino.c: code for performing a domino (2x1 tile) layout of
   3  * a given area of code.
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <assert.h>
   9
  10 #include "puzzles.h"
  11
  12 /*
  13  * This function returns an array size w x h representing a grid:
  14  * each grid[i] = j, where j is the other end of a 2x1 domino.
  15  * If w*h is odd, one square will remain referring to itself.
  16  */
  17
  18 int *domino_layout(int w, int h, random_state *rs)
  19 {
  20     int *grid, *grid2, *list;
  21     int wh = w*h;
  22
  23     /*
  24      * Allocate space in which to lay the grid out.
  25      */
  26     grid = snewn(wh, int);
  27     grid2 = snewn(wh, int);
  28     list = snewn(2*wh, int);
  29
  30     domino_layout_prealloc(w, h, rs, grid, grid2, list);
  31
  32     sfree(grid2);
  33     sfree(list);
  34
  35     return grid;
  36 }
  37
  38 /*
  39  * As for domino_layout, but with preallocated buffers.
  40  * grid and grid2 should be size w*h, and list size 2*w*h.
  41  */
  42 void domino_layout_prealloc(int w, int h, random_state *rs,
  43                             int *grid, int *grid2, int *list)
  44 {
  45     int i, j, k, m, wh = w*h, todo, done;
  46
  47     /*
  48      * To begin with, set grid[i] = i for all i to indicate
  49      * that all squares are currently singletons. Later we'll
  50      * set grid[i] to be the index of the other end of the
  51      * domino on i.
  52      */
  53     for (i = 0; i < wh; i++)
  54         grid[i] = i;
  55
  56     /*
  57      * Now prepare a list of the possible domino locations. There
  58      * are w*(h-1) possible vertical locations, and (w-1)*h
  59      * horizontal ones, for a total of 2*wh - h - w.
  60      *
  61      * I'm going to denote the vertical domino placement with
  62      * its top in square i as 2*i, and the horizontal one with
  63      * its left half in square i as 2*i+1.
  64      */
  65     k = 0;
  66     for (j = 0; j < h-1; j++)
  67         for (i = 0; i < w; i++)
  68             list[k++] = 2 * (j*w+i);   /* vertical positions */
  69     for (j = 0; j < h; j++)
  70         for (i = 0; i < w-1; i++)
  71             list[k++] = 2 * (j*w+i) + 1;   /* horizontal positions */
  72     assert(k == 2*wh - h - w);
  73
  74     /*
  75      * Shuffle the list.
  76      */
  77     shuffle(list, k, sizeof(*list), rs);
  78
  79     /*
  80      * Work down the shuffled list, placing a domino everywhere
  81      * we can.
  82      */
  83     for (i = 0; i < k; i++) {
  84         int horiz, xy, xy2;
  85
  86         horiz = list[i] % 2;
  87         xy = list[i] / 2;
  88         xy2 = xy + (horiz ? 1 : w);
  89
  90         if (grid[xy] == xy && grid[xy2] == xy2) {
  91             /*
  92              * We can place this domino. Do so.
  93              */
  94             grid[xy] = xy2;
  95             grid[xy2] = xy;
  96         }
  97     }
  98
  99 #ifdef GENERATION_DIAGNOSTICS
 100     printf("generated initial layout\n");
 101 #endif
 102
 103     /*
 104      * Now we've placed as many dominoes as we can immediately
 105      * manage. There will be squares remaining, but they'll be
 106      * singletons. So loop round and deal with the singletons
 107      * two by two.
 108      */
 109     while (1) {
 110 #ifdef GENERATION_DIAGNOSTICS
 111         for (j = 0; j < h; j++) {
 112             for (i = 0; i < w; i++) {
 113                 int xy = j*w+i;
 114                 int v = grid[xy];
 115                 int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
 116                          v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
 117                 putchar(c);
 118             }
 119             putchar('\n');
 120         }
 121         putchar('\n');
 122 #endif
 123
 124         /*
 125          * Our strategy is:
 126          *
 127          * First find a singleton square.
 128          *
 129          * Then breadth-first search out from the starting
 130          * square. From that square (and any others we reach on
 131          * the way), examine all four neighbours of the square.
 132          * If one is an end of a domino, we move to the _other_
 133          * end of that domino before looking at neighbours
 134          * again. When we encounter another singleton on this
 135          * search, stop.
 136          *
 137          * This will give us a path of adjacent squares such
 138          * that all but the two ends are covered in dominoes.
 139          * So we can now shuffle every domino on the path up by
 140          * one.
 141          *
 142          * (Chessboard colours are mathematically important
 143          * here: we always end up pairing each singleton with a
 144          * singleton of the other colour. However, we never
 145          * have to track this manually, since it's
 146          * automatically taken care of by the fact that we
 147          * always make an even number of orthogonal moves.)
 148          */
 149         k = 0;
 150         for (j = 0; j < wh; j++) {
 151             if (grid[j] == j) {
 152                 k++;
 153                 i = j;          /* start BFS here. */
 154             }
 155         }
 156         if (k == (wh % 2))
 157             break;              /* if area is even, we have no more singletons;
 158                                    if area is odd, we have one singleton.
 159                                    either way, we're done. */
 160
 161 #ifdef GENERATION_DIAGNOSTICS
 162         printf("starting b.f.s. at singleton %d\n", i);
 163 #endif
 164         /*
 165          * Set grid2 to -1 everywhere. It will hold our
 166          * distance-from-start values, and also our
 167          * backtracking data, during the b.f.s.
 168          */
 169         for (j = 0; j < wh; j++)
 170             grid2[j] = -1;
 171         grid2[i] = 0;              /* starting square has distance zero */
 172
 173         /*
 174          * Start our to-do list of squares. It'll live in
 175          * `list'; since the b.f.s can cover every square at
 176          * most once there is no need for it to be circular.
 177          * We'll just have two counters tracking the end of the
 178          * list and the squares we've already dealt with.
 179          */
 180         done = 0;
 181         todo = 1;
 182         list[0] = i;
 183
 184         /*
 185          * Now begin the b.f.s. loop.
 186          */
 187         while (done < todo) {
 188             int d[4], nd, x, y;
 189
 190             i = list[done++];
 191
 192 #ifdef GENERATION_DIAGNOSTICS
 193             printf("b.f.s. iteration from %d\n", i);
 194 #endif
 195             x = i % w;
 196             y = i / w;
 197             nd = 0;
 198             if (x > 0)
 199                 d[nd++] = i - 1;
 200             if (x+1 < w)
 201                 d[nd++] = i + 1;
 202             if (y > 0)
 203                 d[nd++] = i - w;
 204             if (y+1 < h)
 205                 d[nd++] = i + w;
 206             /*
 207              * To avoid directional bias, process the
 208              * neighbours of this square in a random order.
 209              */
 210             shuffle(d, nd, sizeof(*d), rs);
 211
 212             for (j = 0; j < nd; j++) {
 213                 k = d[j];
 214                 if (grid[k] == k) {
 215 #ifdef GENERATION_DIAGNOSTICS
 216                     printf("found neighbouring singleton %d\n", k);
 217 #endif
 218                     grid2[k] = i;
 219                     break;         /* found a target singleton! */
 220                 }
 221
 222                 /*
 223                  * We're moving through a domino here, so we
 224                  * have two entries in grid2 to fill with
 225                  * useful data. In grid[k] - the square
 226                  * adjacent to where we came from - I'm going
 227                  * to put the address _of_ the square we came
 228                  * from. In the other end of the domino - the
 229                  * square from which we will continue the
 230                  * search - I'm going to put the distance.
 231                  */
 232                 m = grid[k];
 233
 234                 if (grid2[m] < 0 || grid2[m] > grid2[i]+1) {
 235 #ifdef GENERATION_DIAGNOSTICS
 236                     printf("found neighbouring domino %d/%d\n", k, m);
 237 #endif
 238                     grid2[m] = grid2[i]+1;
 239                     grid2[k] = i;
 240                     /*
 241                      * And since we've now visited a new
 242                      * domino, add m to the to-do list.
 243                      */
 244                     assert(todo < wh);
 245                     list[todo++] = m;
 246                 }
 247             }
 248
 249             if (j < nd) {
 250                 i = k;
 251 #ifdef GENERATION_DIAGNOSTICS
 252                 printf("terminating b.f.s. loop, i = %d\n", i);
 253 #endif
 254                 break;
 255             }
 256
 257             i = -1;                /* just in case the loop terminates */
 258         }
 259
 260         /*
 261          * We expect this b.f.s. to have found us a target
 262          * square.
 263          */
 264         assert(i >= 0);
 265
 266         /*
 267          * Now we can follow the trail back to our starting
 268          * singleton, re-laying dominoes as we go.
 269          */
 270         while (1) {
 271             j = grid2[i];
 272             assert(j >= 0 && j < wh);
 273             k = grid[j];
 274
 275             grid[i] = j;
 276             grid[j] = i;
 277 #ifdef GENERATION_DIAGNOSTICS
 278             printf("filling in domino %d/%d (next %d)\n", i, j, k);
 279 #endif
 280             if (j == k)
 281                 break;             /* we've reached the other singleton */
 282             i = k;
 283         }
 284 #ifdef GENERATION_DIAGNOSTICS
 285         printf("fixup path completed\n");
 286 #endif
 287     }
 288 }
 289
 290 /* vim: set shiftwidth=4 :set textwidth=80: */
 291