# Placing Dominoes on a Checkerboard

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

A classic puzzle asks for the placement of as many disjoint dominoes (1×2 tiles) as possible onto a checkerboard from which some squares have been removed. The problem can be solved by setting up a bipartite graph where one part consists of the white unblocked squares, the other consists of the black unblocked squares, and edges correspond to adjacency of squares. Then a maximum matching (a collection of disjoint edges that is as large as possible) in this graph leads to a solution of the domino problem. In this Demonstration, the blocked squares are red, the graph is shown in blue, and the maximum domino array is shown in yellow.

[more]
Contributed by: Stan Wagon (Macalester College) (July 2010)

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

Snapshot 1: an example in the 8×8 case where both white and black squares remain uncovered by dominoes

Snapshot 2: a similar example, again with a large discrepancy between the maximum possible, 20, and the maximum that can be placed, 14

Snapshot 3: the underlying bipartite graph

The algorithmic solution is based on the existence of a very fast algorithm—usually called the Hungarian algorithm—to find a maximum matching in a bipartite graph. The following two books are good references.

[1] R. A. Brualdi, *Introductory Combinatorics*, 4th ed., Saddle River, NJ: Prentice Hall, 2004.

[2] W. J. Cook, W. H. Cunningham, W. R Pulleyblank, and A. Schrijver, *Combinatorial Optimization*, New York: Wiley, 1998.

## Permanent Citation

"Placing Dominoes on a Checkerboard"

http://demonstrations.wolfram.com/PlacingDominoesOnACheckerboard/

Wolfram Demonstrations Project

Published: July 22 2010