laydomino.c
void domino_layout_prealloc(int w, int h, random_state *rs,
                            int *grid, int *grid2, int *list)
{
    int i, j, k, m, wh = w*h, todo, done;

    /*
     * To begin with, set grid[i] = i for all i to indicate
     * that all squares are currently singletons. Later we'll
     * set grid[i] to be the index of the other end of the
     * domino on i.
     */
    for (i = 0; i < wh; i++)
        grid[i] = i;

    /*
     * Now prepare a list of the possible domino locations. There
     * are w*(h-1) possible vertical locations, and (w-1)*h
     * horizontal ones, for a total of 2*wh - h - w.
     *
     * I'm going to denote the vertical domino placement with
     * its top in square i as 2*i, and the horizontal one with
     * its left half in square i as 2*i+1.
     */
    k = 0;
    for (j = 0; j < h-1; j++)
        for (i = 0; i < w; i++)
            list[k++] = 2 * (j*w+i);   /* vertical positions */
    for (j = 0; j < h; j++)
        for (i = 0; i < w-1; i++)
            list[k++] = 2 * (j*w+i) + 1;   /* horizontal positions */
    assert(k == 2*wh - h - w);

    /*
     * Shuffle the list.
     */
    shuffle(list, k, sizeof(*list), rs);

    /*
     * Work down the shuffled list, placing a domino everywhere
     * we can.
     */
    for (i = 0; i < k; i++) {
        int horiz, xy, xy2;

        horiz = list[i] % 2;
        xy = list[i] / 2;
        xy2 = xy + (horiz ? 1 : w);

        if (grid[xy] == xy && grid[xy2] == xy2) {
            /*
             * We can place this domino. Do so.
             */
            grid[xy] = xy2;
            grid[xy2] = xy;
        }
    }

#ifdef GENERATION_DIAGNOSTICS
    printf("generated initial layout\n");
#endif

    /*
     * Now we've placed as many dominoes as we can immediately
     * manage. There will be squares remaining, but they'll be
     * singletons. So loop round and deal with the singletons
     * two by two.
     */
    while (1) {
#ifdef GENERATION_DIAGNOSTICS
        for (j = 0; j < h; j++) {
            for (i = 0; i < w; i++) {
                int xy = j*w+i;
                int v = grid[xy];
                int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
                         v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
                putchar(c);
            }
            putchar('\n');
        }
        putchar('\n');
#endif

        /*
         * Our strategy is:
         *
         * First find a singleton square.
         *
         * Then breadth-first search out from the starting
         * square. From that square (and any others we reach on
         * the way), examine all four neighbours of the square.
         * If one is an end of a domino, we move to the _other_
         * end of that domino before looking at neighbours
         * again. When we encounter another singleton on this
         * search, stop.
         *
         * This will give us a path of adjacent squares such
         * that all but the two ends are covered in dominoes.
         * So we can now shuffle every domino on the path up by
         * one.
         *
         * (Chessboard colours are mathematically important
         * here: we always end up pairing each singleton with a
         * singleton of the other colour. However, we never
         * have to track this manually, since it's
         * automatically taken care of by the fact that we
         * always make an even number of orthogonal moves.)
         */
        k = 0;
        for (j = 0; j < wh; j++) {
            if (grid[j] == j) {
                k++;
                i = j;          /* start BFS here. */
            }
        }
        if (k == (wh % 2))
            break;              /* if area is even, we have no more singletons;
                                   if area is odd, we have one singleton.
                                   either way, we're done. */

#ifdef GENERATION_DIAGNOSTICS
        printf("starting b.f.s. at singleton %d\n", i);
#endif
        /*
         * Set grid2 to -1 everywhere. It will hold our
         * distance-from-start values, and also our
         * backtracking data, during the b.f.s.
         */
        for (j = 0; j < wh; j++)
            grid2[j] = -1;
        grid2[i] = 0;              /* starting square has distance zero */

        /*
         * Start our to-do list of squares. It'll live in
         * `list'; since the b.f.s can cover every square at
         * most once there is no need for it to be circular.
         * We'll just have two counters tracking the end of the
         * list and the squares we've already dealt with.
         */
        done = 0;
        todo = 1;
        list[0] = i;

        /*
         * Now begin the b.f.s. loop.
         */
        while (done < todo) {
            int d[4], nd, x, y;

            i = list[done++];

#ifdef GENERATION_DIAGNOSTICS
            printf("b.f.s. iteration from %d\n", i);
#endif
            x = i % w;
            y = i / w;
            nd = 0;
            if (x > 0)
                d[nd++] = i - 1;
            if (x+1 < w)
                d[nd++] = i + 1;
            if (y > 0)
                d[nd++] = i - w;
            if (y+1 < h)
                d[nd++] = i + w;
            /*
             * To avoid directional bias, process the
             * neighbours of this square in a random order.
             */
            shuffle(d, nd, sizeof(*d), rs);

            for (j = 0; j < nd; j++) {
                k = d[j];
                if (grid[k] == k) {
#ifdef GENERATION_DIAGNOSTICS
                    printf("found neighbouring singleton %d\n", k);
#endif
                    grid2[k] = i;
                    break;         /* found a target singleton! */
                }

                /*
                 * We're moving through a domino here, so we
                 * have two entries in grid2 to fill with
                 * useful data. In grid[k] - the square
                 * adjacent to where we came from - I'm going
                 * to put the address _of_ the square we came
                 * from. In the other end of the domino - the
                 * square from which we will continue the
                 * search - I'm going to put the distance.
                 */
                m = grid[k];

                if (grid2[m] < 0 || grid2[m] > grid2[i]+1) {
#ifdef GENERATION_DIAGNOSTICS
                    printf("found neighbouring domino %d/%d\n", k, m);
#endif
                    grid2[m] = grid2[i]+1;
                    grid2[k] = i;
                    /*
                     * And since we've now visited a new
                     * domino, add m to the to-do list.
                     */
                    assert(todo < wh);
                    list[todo++] = m;
                }
            }

            if (j < nd) {
                i = k;
#ifdef GENERATION_DIAGNOSTICS
                printf("terminating b.f.s. loop, i = %d\n", i);
#endif
                break;
            }

            i = -1;                /* just in case the loop terminates */
        }

        /*
         * We expect this b.f.s. to have found us a target
         * square.
         */
        assert(i >= 0);

        /*
         * Now we can follow the trail back to our starting
         * singleton, re-laying dominoes as we go.
         */
        while (1) {
            j = grid2[i];
            assert(j >= 0 && j < wh);
            k = grid[j];

            grid[i] = j;
            grid[j] = i;
#ifdef GENERATION_DIAGNOSTICS
            printf("filling in domino %d/%d (next %d)\n", i, j, k);
#endif
            if (j == k)
                break;             /* we've reached the other singleton */
            i = k;
        }
#ifdef GENERATION_DIAGNOSTICS
        printf("fixup path completed\n");
#endif
    }
}
/*
 * As for domino_layout, but with preallocated buffers.
 * grid and grid2 should be size w*h, and list size 2*w*h.
 */
As for domino_layout, but with preallocated buffers.
grid and grid2 should be size w*h, and list size 2*w*h.
As for domino_layout but with preallocated buffers . grid and grid2 should be size w * h and list size 2 * w * h .
void domino_layout_prealloc(int w, int h, random_state *rs,
                            int *grid, int *grid2, int *list)
{
    int i, j, k, m, wh = w*h, todo, done;
    for (i = 0; i < wh; i++)
        grid[i] = i;
    k = 0;
    for (j = 0; j < h-1; j++)
        for (i = 0; i < w; i++)
            list[k++] = 2 * (j*w+i);   
    for (j = 0; j < h; j++)
        for (i = 0; i < w-1; i++)
            list[k++] = 2 * (j*w+i) + 1;   
    assert(k == 2*wh - h - w);
    shuffle(list, k, sizeof(*list), rs);
    for (i = 0; i < k; i++) {
        int horiz, xy, xy2;
        horiz = list[i] % 2;
        xy = list[i] / 2;
        xy2 = xy + (horiz ? 1 : w);
        if (grid[xy] == xy && grid[xy2] == xy2) {
            grid[xy] = xy2;
            grid[xy2] = xy;
        }
    }
#ifdef GENERATION_DIAGNOSTICS
    printf("generated initial layout\n");
#endif
    while (1) {
#ifdef GENERATION_DIAGNOSTICS
        for (j = 0; j < h; j++) {
            for (i = 0; i < w; i++) {
                int xy = j*w+i;
                int v = grid[xy];
                int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
                         v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
                putchar(c);
            }
            putchar('\n');
        }
        putchar('\n');
#endif
        k = 0;
        for (j = 0; j < wh; j++) {
            if (grid[j] == j) {
                k++;
                i = j;          
            }
        }
        if (k == (wh % 2))
            break;              
#ifdef GENERATION_DIAGNOSTICS
        printf("starting b.f.s. at singleton %d\n", i);
#endif
        for (j = 0; j < wh; j++)
            grid2[j] = -1;
        grid2[i] = 0;              
        done = 0;
        todo = 1;
        list[0] = i;
        while (done < todo) {
            int d[4], nd, x, y;
            i = list[done++];
#ifdef GENERATION_DIAGNOSTICS
            printf("b.f.s. iteration from %d\n", i);
#endif
            x = i % w;
            y = i / w;
            nd = 0;
            if (x > 0)
                d[nd++] = i - 1;
            if (x+1 < w)
                d[nd++] = i + 1;
            if (y > 0)
                d[nd++] = i - w;
            if (y+1 < h)
                d[nd++] = i + w;
            shuffle(d, nd, sizeof(*d), rs);
            for (j = 0; j < nd; j++) {
                k = d[j];
                if (grid[k] == k) {
#ifdef GENERATION_DIAGNOSTICS
                    printf("found neighbouring singleton %d\n", k);
#endif
                    grid2[k] = i;
                    break;         
                }
                m = grid[k];
                if (grid2[m] < 0 || grid2[m] > grid2[i]+1) {
#ifdef GENERATION_DIAGNOSTICS
                    printf("found neighbouring domino %d/%d\n", k, m);
#endif
                    grid2[m] = grid2[i]+1;
                    grid2[k] = i;
                    assert(todo < wh);
                    list[todo++] = m;
                }
            }
            if (j < nd) {
                i = k;
#ifdef GENERATION_DIAGNOSTICS
                printf("terminating b.f.s. loop, i = %d\n", i);
#endif
                break;
            }
            i = -1;                
        }
        assert(i >= 0);
        while (1) {
            j = grid2[i];
            assert(j >= 0 && j < wh);
            k = grid[j];
            grid[i] = j;
            grid[j] = i;
#ifdef GENERATION_DIAGNOSTICS
            printf("filling in domino %d/%d (next %d)\n", i, j, k);
#endif
            if (j == k)
                break;             
            i = k;
        }
#ifdef GENERATION_DIAGNOSTICS
        printf("fixup path completed\n");
#endif
    }
}
void domino_layout_prealloc ( int w , int h , random_state * rs , int * grid , int * grid2 , int * list ) { int i , j , k , m , wh = w * h , todo , done ; for ( i = 0 ; i < wh ; i ++ ) grid [ i ] = i ; k = 0 ; for ( j = 0 ; j < h - 1 ; j ++ ) for ( i = 0 ; i < w ; i ++ ) list [ k ++ ] = 2 * ( j * w + i ) ; for ( j = 0 ; j < h ; j ++ ) for ( i = 0 ; i < w - 1 ; i ++ ) list [ k ++ ] = 2 * ( j * w + i ) + 1 ; assert ( k == 2 * wh - h - w ) ; shuffle ( list , k , sizeof ( * list ) , rs ) ; for ( i = 0 ; i < k ; i ++ ) { int horiz , xy , xy2 ; horiz = list [ i ] % 2 ; xy = list [ i ] / 2 ; xy2 = xy + ( horiz ? 1 : w ) ; if ( grid [ xy ] == xy && grid [ xy2 ] == xy2 ) { grid [ xy ] = xy2 ; grid [ xy2 ] = xy ; } } #ifdef GENERATION_DIAGNOSTICS printf ( " \n " ) ; #endif while ( 1 ) { #ifdef GENERATION_DIAGNOSTICS for ( j = 0 ; j < h ; j ++ ) { for ( i = 0 ; i < w ; i ++ ) { int xy = j * w + i ; int v = grid [ xy ] ; int c = ( v == xy + 1 ? ' ' : v == xy - 1 ? ' ' : v == xy + w ? ' ' : v == xy - w ? ' ' : ' ' ) ; putchar ( c ) ; } putchar ( ' \n ' ) ; } putchar ( ' \n ' ) ; #endif k = 0 ; for ( j = 0 ; j < wh ; j ++ ) { if ( grid [ j ] == j ) { k ++ ; i = j ; } } if ( k == ( wh % 2 ) ) break ; #ifdef GENERATION_DIAGNOSTICS printf ( " \n " , i ) ; #endif for ( j = 0 ; j < wh ; j ++ ) grid2 [ j ] = -1 ; grid2 [ i ] = 0 ; done = 0 ; todo = 1 ; list [ 0 ] = i ; while ( done < todo ) { int d [ 4 ] , nd , x , y ; i = list [ done ++ ] ; #ifdef GENERATION_DIAGNOSTICS printf ( " \n " , i ) ; #endif x = i % w ; y = i / w ; nd = 0 ; if ( x > 0 ) d [ nd ++ ] = i - 1 ; if ( x + 1 < w ) d [ nd ++ ] = i + 1 ; if ( y > 0 ) d [ nd ++ ] = i - w ; if ( y + 1 < h ) d [ nd ++ ] = i + w ; shuffle ( d , nd , sizeof ( * d ) , rs ) ; for ( j = 0 ; j < nd ; j ++ ) { k = d [ j ] ; if ( grid [ k ] == k ) { #ifdef GENERATION_DIAGNOSTICS printf ( " \n " , k ) ; #endif grid2 [ k ] = i ; break ; } m = grid [ k ] ; if ( grid2 [ m ] < 0 || grid2 [ m ] > grid2 [ i ] + 1 ) { #ifdef GENERATION_DIAGNOSTICS printf ( " \n " , k , m ) ; #endif grid2 [ m ] = grid2 [ i ] + 1 ; grid2 [ k ] = i ; assert ( todo < wh ) ; list [ todo ++ ] = m ; } } if ( j < nd ) { i = k ; #ifdef GENERATION_DIAGNOSTICS printf ( " \n " , i ) ; #endif break ; } i = -1 ; } assert ( i >= 0 ) ; while ( 1 ) { j = grid2 [ i ] ; assert ( j >= 0 && j < wh ) ; k = grid [ j ] ; grid [ i ] = j ; grid [ j ] = i ; #ifdef GENERATION_DIAGNOSTICS printf ( " \n " , i , j , k ) ; #endif if ( j == k ) break ; i = k ; } #ifdef GENERATION_DIAGNOSTICS printf ( " \n " ) ; #endif } }
As for domino_layout, but with preallocated buffers.
As for domino_layout but with preallocated buffers .
/*
     * To begin with, set grid[i] = i for all i to indicate
     * that all squares are currently singletons. Later we'll
     * set grid[i] to be the index of the other end of the
     * domino on i.
     */ /*
     * Now prepare a list of the possible domino locations. There
     * are w*(h-1) possible vertical locations, and (w-1)*h
     * horizontal ones, for a total of 2*wh - h - w.
     *
     * I'm going to denote the vertical domino placement with
     * its top in square i as 2*i, and the horizontal one with
     * its left half in square i as 2*i+1.
     */ /* vertical positions */ /* horizontal positions */ /*
     * Shuffle the list.
     */ /*
     * Work down the shuffled list, placing a domino everywhere
     * we can.
     */ /*
             * We can place this domino. Do so.
             */ /*
     * Now we've placed as many dominoes as we can immediately
     * manage. There will be squares remaining, but they'll be
     * singletons. So loop round and deal with the singletons
     * two by two.
     */ /*
         * Our strategy is:
         *
         * First find a singleton square.
         *
         * Then breadth-first search out from the starting
         * square. From that square (and any others we reach on
         * the way), examine all four neighbours of the square.
         * If one is an end of a domino, we move to the _other_
         * end of that domino before looking at neighbours
         * again. When we encounter another singleton on this
         * search, stop.
         *
         * This will give us a path of adjacent squares such
         * that all but the two ends are covered in dominoes.
         * So we can now shuffle every domino on the path up by
         * one.
         *
         * (Chessboard colours are mathematically important
         * here: we always end up pairing each singleton with a
         * singleton of the other colour. However, we never
         * have to track this manually, since it's
         * automatically taken care of by the fact that we
         * always make an even number of orthogonal moves.)
         */ /* start BFS here. */ /* if area is even, we have no more singletons;
                                   if area is odd, we have one singleton.
                                   either way, we're done. */ /*
         * Set grid2 to -1 everywhere. It will hold our
         * distance-from-start values, and also our
         * backtracking data, during the b.f.s.
         */ /* starting square has distance zero */ /*
         * Start our to-do list of squares. It'll live in
         * `list'; since the b.f.s can cover every square at
         * most once there is no need for it to be circular.
         * We'll just have two counters tracking the end of the
         * list and the squares we've already dealt with.
         */ /*
         * Now begin the b.f.s. loop.
         */ /*
             * To avoid directional bias, process the
             * neighbours of this square in a random order.
             */ /* found a target singleton! */ /*
                 * We're moving through a domino here, so we
                 * have two entries in grid2 to fill with
                 * useful data. In grid[k] - the square
                 * adjacent to where we came from - I'm going
                 * to put the address _of_ the square we came
                 * from. In the other end of the domino - the
                 * square from which we will continue the
                 * search - I'm going to put the distance.
                 */ /*
                     * And since we've now visited a new
                     * domino, add m to the to-do list.
                     */ /* just in case the loop terminates */ /*
         * We expect this b.f.s. to have found us a target
         * square.
         */ /*
         * Now we can follow the trail back to our starting
         * singleton, re-laying dominoes as we go.
         */ /* we've reached the other singleton */