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).

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • 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 »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2018 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+