[I got this problem from Carroll Morgan.]
A building has 16 rooms, arranged in a 4x4 grid. There is a door between every pair of adjacent rooms ("adjacent" meaning north, south, west, and east, but no diagonals). Only the room in the northeast corner has a door that leads out of the building.
In the initial configuration, there is one person in each room. The person in the southwest corner is a psycho killer. The psycho killer has the following traits: If he enters a room where there is another person, he immediately kills that person . But he also cannot stand the site of blood, so he will not enter any room where there is a dead person.
As it happened, from that initial configuration, the psycho killer managed to get out of the building after killing all the other 15 people. What path did he take?