Tiling a Chessboard with Dominoes

Even the simplest of all polyominoes - the domino - affords interesting puzzles. Here is one example [Levitin, #12]:

Is it possible to tile an 8×8 board with dominoes (2×1 tiles) so that no two dominoes form a 2×2 square.

Solution

References

  1. S. Golomb, Polyominoes, Princeton University Press, 1994
  2. A. Levitin and M. Levitin, Algorithmic Puzzles, Oxford University Press, 2011
  3. G. E. Martin, Polyominoes, MAA, 1996
  4. A. V. Shapovalov, The Principle of Narrow Places, MCCME, 2008 (free pdf, in Russian)

|Contact| |Front page| |Contents| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny

Is it possible to tile an 8×8 board with dominoes (2×1 tiles) so that no two dominoes form a 2×2 square.

Solution

The answer is, No, this is impossible, regardless of the board size. To see why, let's just start placing dominoes on the board one at a time and see where this leads us. Assuming, that it is possible to cover the board, a domino will have to be covering a corner square. Because of the symmetry, we may as well assume that the placement is as in the diagram below:

domino tiling of a board, first domino

The question is where to place the second domino. If the covering is at all possible there have to be dominoes below the one that is already there. Placing it horizontally just below the first one creates a 2×2 square:

domino tiling of a board, second domino horizontal

We are thus forced to place a square vertically:

domino tiling of a board, second domino vertical

The two dominoes form a corner that needs to be filled. As before, a vertical domino will add up to a 2×2 square, so we are forced to place the third domino horizontally:

domino tiling of a board, third domino

We get another corner to handle, and, again, a move is forced:

domino tiling of a board, fourth domino

So we are forced to continue:

domino tiling of a board, reaching the bottom

Now, reaching the bottom we see that the only way to continue is to create a 2×2 square which shows that the answer to the question at hand is negative. The same process actually shows that tiling of rectangles with one dimension odd and the other even is also impossible unless there is at least one 2×2 square.

Obviously this will happen with any square of even size, while there is no question about tiling an odd square.


Related material
Read more...

  • Covering A Chessboard With Domino
  • Dominoes on a Chessboard
  • Vertical and Horizontal Dominoes on a Chessboard
  • Straight Tromino on a Chessboard
  • Golomb's inductive proof of a tromino theorem
  • Tromino Puzzle: Interactive Illustration of Golomb's Theorem
  • Tromino as a Rep-tile
  • Tiling Rectangles with L-Trominoes
  • Squares and Straight Tetrominoes
  • Covering a Chessboard with a Hole with L-Trominoes
  • Tromino Puzzle: Deficient Squares
  • Tiling a Square with Tetrominoes Fault-Free
  • Tiling a Square with T-, L-, and a Square Tetrominoes
  • Tiling a Rectangle with L-tetrominoes
  • Tiling a 12x12 Square with Straight Trominoes
  • Bicubal Domino
  • |Contact| |Front page| |Contents| |Geometry|

    Copyright © 1996-2018 Alexander Bogomolny

    71471404