# Puzzling Adventures: Snow Walkers--How to Clear Streets of Snow More Effectively

A fictional city grapples with the white stuff

Image: Cloe Liane Shasha

Grid City is a small planned city laid out on a completely regular six-by-five grid with streets going north-south and east-west. There is one building per city block.

Grid occasionally suffers major snowstorms. The Grid City Snow Clearing Department (GridClear) wishes to make it possible for residents to move about on paved roads but the effort to move the snow is so great that they want to minimize plowing as well as danger to the public. This means that the path itself may snake through the city and may even loop, but the plows won't double back on a paved road for fear of running over the many pedestrians.

The head of GridClear consults you to help plan the path. You are told the path must start somewhere on the outside boundary of the grid, but you can choose where, because Grid City has many garages available. The goal is to ensure that for any two blocks that neighbor each other north-south or east-west, a resident will need to travel over only a few streets (or through a few buildings) along the cleared path. The "score" of a path is the worst case, that is, the largest number of such streets/buildings that going to a neighbor would require. Crossing a plowed intersection costs nothing, but it is impossible to cross an unplowed intersection or street.

You may assume that each building block has an entrance at every corner and that walking through a building to any other corner (even to the diagonally opposite one) costs the same as walking one city block along a plowed street. You accept this simplification, because there is no ice inside the buildings.

In the warm-up problem and questions to follow, you may find it helpful to look at the very nice applet developed by Arefin Huq, with whom I have worked on this puzzle.
http://www.cims.nyu.edu/~ah203/SnowWalkers.html
All the screen shots that follow are from that applet.

Warm-up Puzzle:

Suppose the city were smaller and set up on a three-by-four city grid like so:
http://cs.nyu.edu/cs/faculty/shasha/papers/warmup3x4.tiff
Try to find a route that requires plowing only five streets, so pedestrians can walk from any block to a neighboring one by crossing at most two streets.

Solution to Warm-up Puzzle

Recall that our city is six by five, as illustrated here:
http://cs.nyu.edu/cs/faculty/shasha/papers/oneplow6x5.tiff
It's still the case that every block has an entrance at every corner and you must begin plowing from the outside of the grid.

Problem 1.
Assuming you have just one plow, can you arrange a path of 15 or fewer streets and guarantee that a pedestrian on any block can reach any east-west or north-south neighbor by walking at most eight blocks? What does your path look like?

Solution to Problem 1

Problem 2.
Still with just one plow, what is the minimum-length path you can design that will guarantee that a pedestrian can walk from any block to any neighboring one across a cleared intersection  (yielding a cost of 0)?

Solution to Problem 2

Problem 3. A nearby city has just given you another plow. You can therefore use two but both must start from the outside of the grid and neither can drive on a city block already plowed by the other (although they can cross at an intersection). Can you figure out a way to use two plows such that each plows nine streets and a pedestrian can walk from any block to any neighboring one across a cleared intersection?

Solution to Problem 3

Dennis Shasha is at the Courant Institute of Mathematical Sciences, New York University. His most recent puzzle book, Puzzles for Programmers and Pros, was published in May 2007 by John Wiley and Sons/Wrox.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Cocktail Party Physics | 10 hours ago

### C'mon Baby Light My (Magnetic) Fire

• The Curious Wavefunction | 13 hours ago

### An invasive ladybug uses a biological weapon to kill off competitors

• Scientific American Mind | 15 hours ago | 1

### MIND Reviews: The Autistic Brain

• News | 16 hours ago

### Audubon's Birds Live On Long after His Death [Slide Show]

• TechMediaNetwork | 16 hours ago | 1

More »

## Latest from SA Blog Network

• ### C'mon Baby Light My (Magnetic) Fire

Cocktail Party Physics | 10 hours ago
• ### With Drones Circling, How Should Lawmakers Respond?

Observations | 13 hours ago
• ### An invasive ladybug uses a biological weapon to kill off competitors

The Curious Wavefunction | 13 hours ago
• ### #DispatchesDNLee: Giant African Land Snails

The Urban Scientist | 14 hours ago
• ### On not overdiffusing flash in macro photography

Compound Eye | 14 hours ago

## Science Jobs of the Week

Puzzling Adventures: Snow Walkers--How to Clear Streets of Snow More Effectively

X

### Subscribe Today

Save 66% off the cover price and get a free gift!

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X