11562

# Domino and Triomino Tilings of a Chessboard

If a single square is removed from a chessboard, then it is always possible to tile the remaining squares using L-shaped triominoes. Likewise, if two opposite-colored squares are removed, then it is always possible to tile the remaining squares using standard dominoes. This Demonstration generates triomino and domino tilings for chessboards of various sizes. Use the controls to select the type of tile used, the size of the board and the location(s) of the blank square(s).

### DETAILS

The triomino tiling algorithm is recursive [1]. Given a board missing one square, divide it into four subboards, one of which is missing a square. From the remaining three subboards, remove the square nearest the center of the original board. This results in four subboards, each missing a square. Three of these missing squares are located near the center of the original board and can easily be tiled by a single L-shaped triomino. To tile the fourth subboard, apply the process recursively until you reach the base case of a board missing a square, which can obviously be tiled by a single L-shaped triomino.
For the domino tiling algorithm [2], begin by finding a Hamiltonian cycle on the original board. Removing two squares cuts this cycle into one or two paths. The tiling can be generated by laying down dominoes along the path or paths. It is only possible to complete this domino tiling if the removed squares are of opposite colors [3]. This is because each domino must cover one black square and one white square, so any board that can be tiled must have the same number of squares of each color.
References
[1] F. E. Su et al. "Inductive Tiling," Math Fun Facts. (Oct 31, 2017) www.math.hmc.edu/funfacts.
[2] J. Kun, "Tiling a Chessboard with Dominoes (Opposite Colors Removed)," Math ⋂ Programming (blog). (Oct 31, 2017) jeremykun.com/2011/11/18/tiling-a-chessboard-2.
[3] F. E. Su et al. "Dominoes on a Chessboard," Math Fun Facts. (Oct 31, 2017) www.math.hmc.edu/funfacts.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.