TOAD Shuffler Applet v1.3

TOAD Shuffler Help

What is it?

A TOAD is a Tiling Of an Aztec Diamond with domino tiles; a domino is a 2-by-1 rectangle. Set “Initial Size” to 2. Then click on “New AD.” TOAD Shuffler will now display an random Aztec Diamond of order 2. Hit “Iterate Stage” several times. Each time, it will display a larger Aztec Diamond, tiled with dominoes.

An order n Aztec diamond has 2^(n(n+1)/2) different tilings. This program will produce a random tiling from the uniform distribution of all such tilings.

What are the rules?

There are three steps to “growing” a TOAD via the EKLP shuffling algorithm. They are filling, destruction, and sliding.

Rule for Filling:
Divide the untiled area into squares. Then randomly tile each square with either two horizontal dominoes or two vertical dominoes.

Rule for Destruction:
If a north-going domino is about to collide with a south-going domino, delete them both. Same for east and west-going dominoes.

Rule for Sliding:
Move the horizontal dominoes north or south, depending on their color. Move the vertical dominoes east or west, depending on their color.

What do the colors mean?

The colors of each tile represent the direction that they will move in the sliding step of the shuffling algorithm. But the colors come from the position of the tiles. Imagine the Aztec diamond as a large checkerboard where each domino overlaps two squares, a black and a white square. if the black square is to the left of the white square, color it one color, if the black square is to the right, color it another color. The same applies to the two colors of vertical dominoes.

What is a FPL?

A FPL (Fully Packed Loop) is a way to represent an ASM (Alternating Sign Matrix.) Each TOAD corresponds to two ASMs. If you turn on “Show FPL,” TOAD Shuffler will display the two FPLs that correspond to the two ASMs that correspond to the TOAD.


TOAD Shuffler is Copyright (C) 2001-2004 Hal Canary, University of Wisconsin-Madison.

Hal Canary [1] wrote TOAD Shuffler in the Spring of 2001 while working with the Spatial Systems Lab (SSL) [2] at the University of Wisconsin-Madison. This work is based on the program shuffle.tcl by Matthew Blum. [3] TOAD Shuffler demonstrates the domino shuffling algorithm from Elkies, Kuperberg, Larson, and Propp. [4] [5]

SSL is sponsored by the National Science Foundation through their VIGRE (Vertical Integration of Graduate Research and Education) program, with supplemental support from the National Science Foundation's REU (Research Experiences for Undergraduates) program and from the National Security Agency.

TOAD Shuffler comes with ABSOLUTELY NO WARRANTY. This program is free software; you can redistribute it and/or modify it under the terms of version 2 of the GNU General Public License as published by the Free Software Foundation.

Source: tarball and zipfile.





[4] N. Elkies, G. Kuperberg, M. Larsen, and J. Propp. “Alternating-Sign Matrices and Domino Tilings (Part I).” Journal of Algebraic Combinatorics 1 (1992) 111-132.

[5] Jim Propp “The many faces of alternating-sign matrices.” “Discrete Models: Combinatorics, Computation, and Geometry” (special issue of Discrete Mathematics and Theoretical Computer Science), July 2001 (arXiv:math.CO/0208125)