The Manhattan Tourist Problem

What is the best sightseeing strategy?

Imagine you’re a tourist in Midtown Manhattan, and you want to see as many sights as possible on your way from the corner of 59th Street and 8th Avenue to the corner of 42nd Street and 3rd Avenue (figure below). However, you’re short on time, and at each intersection, you can only move south (↓) or east (→). You can choose from many different paths through the map, but no path will visit all the sights. The challenge of finding a legal path through the city that visits the most sights is called the Manhattan Tourist Problem.