Puzzling Adventures: Square Dancing; September 2001; Scientific American Magazine; by Dennis E. Shasha; 1 Page(s)

Striding gracefully, her white cape undulating slowly behind her, the director of a famous dance company enters my office. "You've heard of ghost writers," she says. "I need a ghost choreographer." I motion for her to sit, and she outlines the particulars of her problem.

The dance company consists of 12 men (colored blue in the illustrations below) and 20 women (colored red). At a key point in their dance, they go from a configuration in which the men surround the women to one in which the women surround the men. The transition has three stages. During each stage, each dancer can either stand in place or take one step in one of four directions: to the left, to the right, forward or backward. There are two important conditions: two dancers cannot swap positions during a step, nor can two dancers occupy the same space at the end of a step. Above all, the dancers want to avoid collisions.