あみだくじは,1 から n を表す n 本の縦線と,縦線 2 本の間を結ぶ横棒からなる.横棒を,その横棒が結ぶ2本の縦線のラベルを交換する互換とみなすことで,あみだくじ (つまり横棒と縦線からなるネットワーク) は置換を表すことになる.横棒を比較器とみてソーティングネットワーク (sorting network) として研究されることも多く,特に,隣り合う縦線 2 本の間の互換のみに横棒を制限した場合には primitive sorting network と呼ばれる.菱形タイリングは,辺の長さが同じ菱形を,隙間なく重なりなく敷き詰めたものである.本講演では,あみだくじと菱形タイリングの関係について説明し,逆探索や ZDD (Zero-Suppressed Binary Decision Diagrams; 零抑制型二分決定グラフ) による列挙や,その後の広がりについて述べる.