Psycho Killer

Source

I got this problem from Rustan Leino, who got it from Carroll Morgan.

I solved it and wrote up my solution.

Problem    

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, and the rest cannot move because they're chained to the floor. 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 could he have taken?

Solution     Reveal